数据结构实用教程讲课教案.doc

数据结构实用教程讲课教案这次由本人主讲的数据结构（本科）IP课程共分为10讲，每讲大致为50分钟。第一讲 数据结构概述第二讲 集合与线性表第三讲 栈和队列第四讲 二叉树第五讲 二叉搜索树和堆第六讲 平衡二叉树第七讲 图的概念和存储结构第八讲 二分查找和散列查找第九讲 选择排序第十讲 快速排序和归并排序第一讲 数据结构概述一、数据结构的分类二、数据结构的定义三、数据结构的图形表示四、数据结构的二元组表示五、数据结构的应用实例 六、算法的时间复杂度一、数据结构的分类数据结构又分为数据的逻辑结构和数据的存储结构这两个方面，我们时常把数据的逻辑结构简称为数据结构，而在讨论数据的存储结构时则必须指明是数据的存储结构。数据结构的分类：这里是指数据的逻辑结构的分类。总体来说数据的逻辑结构被分为集合结构、线性结构、树结构和图结构等四种基本类型。对于一些复杂的数据结构可以由这四种基本的数据结构，根据实际需要进行组合或嵌套所构成。 数据的存储结构分类：被分为顺序、链接、索引和散列四种，由它们的组合和嵌套可以构成更复杂的存储结构。 广义的数据结构的概念还包含对数据进行的各种运算，通常有插入、删除、查找、更新、排序、遍历等运算。二、数据结构的定义1、集合结构集合结构是指数据中各元素之间没有任何次序。如一个容器中的所有乒乓球，一个俱乐部里的所有成员，可以认为它们之间没有任何次序，它们均为集合结构。2、线性结构线性结构是指数据中各元素之间具有1对1的先后次序关系。如在一个列车时刻表中，各车次记录之间是按照发车时间的先后次序排列的；在一个人事职工表中，各职工记录之间是按照职工编号的先后次序排列的。所以，它们的表结构都是线性结构。3、树结构 树结构是指数据中各元素之间具有1对多的先后次序关系，并且只有一个元素称为树根结点，其余均为树枝结点和树叶结点。如在一个企业的组织机构中，总经理只有一个，相当于是树根；它下属多个部门，每个部门又各有一个部门经理，相当于是树枝；每个部门又有多名员工，属于部门经理领导，相当于是树叶。所以，企业的组织结构是一个树结构。 4、图结构 图结构是指数据中各元素之间具有多对多的关系。这是数据结构中最复杂的结构。如在一个城市交通图中，所有道路连接成一个复杂的图结构，交叉路口就是图中的顶点，每条道路就是图中的边，从一个交叉路口可以到达与其连接的其他交叉路口。 三、数据结构的图形表示 各种数据结构类型的图形表示如下： 从图形表示中可以清醒地看出：集合结构中的元素是各自独立的，元素之间没有联系。线性结构中的元素是一个接一个串联起来的，它有一个头元素A和一个尾元素G，其余为中间元素；每个中间元素既有前驱元素，又有后继元素，如B的前驱元素为A，后继元素为C；C的前驱元素为B，后继元素为D，,头元素A没有前驱元素，只有后继元素B；尾元素G只有前驱元素F，没有后继元素。树结构的图形表示象倒着画的一棵树，树中有一个树根元素A，它有3个后继元素，又称为A的孩子结点B、C和D，C结点有两个孩子E和F，D结点有一个孩子G，由于B、E、F、G没有孩子，所以称它们为叶子结点，而A、C、D被称为树枝结点或分支结点，同时A又是唯一的一个树根结点。 在树结构中，树根结点只有后继结点，而没有前驱结点；如A为树根结点，它没有前驱结点，或者说其前驱结点为空，它有后继结点为B、C和D；除树根结点外，每个结点都有唯一一个前驱结点，又称为是父结点或双亲结点；如C的前驱结点为A，G的前驱结点为D，每个结点的前驱结点即双亲结点，从图形中都能够很容易得到。 在图结构中，每个结点或称顶点都可以有任意多个前驱结点和任意多个后继结点。如(d)图所示的图中，顶点A没有前驱结点，或者说它有0个前驱结点，A有3个后继结点B、C和G；G有2个前驱结点A和D，有一个后继结点F；E有一个前驱结点C和0个后继结点，或者说，E没有后继，对于图形中的其他结点都能够很容易得到其前驱和后继结点。 从数据结构的图形表示中还可以清楚地看出：树结构是图结构的特例，若在图结构中，每个结点的前驱不能有任意多个，而只能有一个，并且只能有一个结点没有前驱，则就成为了树结构；线性结构是树结构的特例，若在树结构中，每个结点不能有任意多个后继，而只能有一个后继，则就成为了线性结构。为了区别于线性结构，时常把树结构和图结构称为非线性结构。 四、数据结构的二元组表示 数据结构的二元组表示采用B=(K，R)的形式，其中第一元K给出数据结构中所有元素的集合，第二元R给出数据结构中所有元素具有的二元关系的集合，通常对每个二元关系分别进行讨论，所以直接用R表示这一种二元关系，该二元关系是有序对的集合，又称是序偶的集合，每个有序对（即序偶）是用一对尖括号括起来的、具有前驱和后继关系的两个元素。 对于前面图形中给出的四种数据结构，下面分别讨论它们的二元组表示。 集合结构中的元素集合K和二元关系R分别为： K=A，B，C，D，E，F，G R= 因为集合中的元素为孤立顶点，它们之间没有前驱和后继的关系，所以对应的二元关系为空。 线性结构中的元素集合K和二元关系R分别为： K=A，B，C，D，E，F，G R=， 因为A和B构成一对前驱和后继关系，对应图形中的一条有向边，它的起点为A，终点为B，它就构成了R中的一个有序对，同理，B和C、C和D等都是R中的有序对。由于该线性结构包含有7个元素，所以二元关系R中共含有6个有序对。 树结构中的元素集合K和二元关系R分别为： K=A，B，C，D，E，F，G R=， 因为A和B构成一对前驱和后继关系，所以它是R中的一个有序对，同理，A和C、A和D等都是R中的有序对。由于该树结构包含有7个元素，所以二元关系R中共含有6个有序对，即每个元素对应唯一一个有序对，并且是有序对中的后继元素，而树根结点没有对应的、作为后继元素的有序对。所以当一棵树具有n个结点时，它必然具有n-1个有序对，对应图形中为n-1条有向边。 图结构中的元素集合K和二元关系R分别为： K=A，B，C，D，E，F，G R=， 在线性结构和树结构中，若元素个数为n，则有序对个数必然为n-1；而在图结构中不存在这种对应的关系，也就是说，其有序对的个数又称有向边数可能大于、等于或小于n-1。在这个图结构的例子中，元素个数为7个，边数为8个。 五、数据结构应用实例 下面为某个公司的职工简表职工号姓名性别出生日期职务部门01万明华男1962-03-20经理02赵 宁男1968-06-14主管销售部03张 利女1964-12-07主管财务部04赵书芳女1972-08-05主任办公室05刘永年男1959-08-15科员销售部06王明理女1975-04-01科员销售部07王 敏女1972-06-28科员财务部08张 才男1967-03-17科员财务部09马立仁男1975-10-12科员财务部10邢怀常男1976-07-05科员办公室 该表中包含有10条职工记录，每条记录都由六个数据项所组成，由于每条记录的职工号各不相同，所以可把每条记录的职工号作为该记录的关键字，并在下面的讨论中，用记录的关键字来代表整个记录。 对于上面所述的一张表，假定不考虑该表中记录之间的任何次序，则该表中的数据就是一个集合结构，对应的记录集合以及二元关系为： K=01,02,03,04,05,06,07,08,09,10 R= 若考虑到该表中的职工记录是按照职工号从小到大有序排列的这个特点，则这个职工表又是一个线性结构，其中表头元素为01号职工，接着为02号职工，依次类推，表尾元素为10号职工。该线性结构包含的记录集合和二元关系为： K=01,02,03,04,05,06,07,08,09,10 R=, , 有时需要按职工的出生日期进行数据结构的定义和处理，则可以把表中的所有职工看作是按照出生日期，从小到大有序的，由此对应的数据结构也是一种线性结构，其中05号职工的出生日期最早，即年龄最大，为表头元素，01号职工年龄次之，为这种线性结构中的第二个元素，依次类推，10号职工的出生日期最晚，为表尾元素。该线性结构包含的记录集合和二元关系为： K=01,02,03,04,05,06,07,08,09,10 R=, ,对应的图形表示为： 从图形表示中能够清楚地看出每个职工出生日期的先后排列次序。 在上面职工表中，还存在职工人员之间领导与被领导的关系，其中01号职工为经理，直接领导02、03和04号职工，他们分别是相应部门的主管，02号职工直接领导05和06号职工，03号职工直接领导07、08和09号职工，04号职工直接领导10号职工。由此可知，该职工表是一种树结构，包含的职工集合和二元关系分别为： K=01,02,03,04,05,06,07,08,09,10 R=, , 对应的图形表示为： 若要反映职工之间的好友关系，假定01和02号职工是好友，01和04号是好友，02和03、02和06、02和07、03和07、04和06、05和07之间是好友，则反映这种好友关系的数据结构是图结构，二元组中的元素集合和有序对集合分别为： K=01,02,03,04,05,06,07,08,09,10 R=, , 对应的图形表示如下面左图所示，其中08、09和10号职工无好友，在图形中为孤立顶点，省略未画；图形中每对顶点之间的两条相反的有向边，表示这两个顶点职工是一对好朋友，为了简化起见，两条相反的有向边可以用一条无向边来代替，隐含着该无向边是双向的，即连接的两个顶点互为前驱和后继，则对应的无向图表示如下面右图所示。 从上面左图可以看出，R是K上的对称关系，即若存在这个序偶，则必然存在这个序偶与之对应。为了简化起见，我们在二元组表示中把和这两个对称序偶用一个无序对(x,y)或(y,x)来代替，这样R关系可改写为： R=(01,02),(01,04),(02,03),(02,06),(02,07),(03,07),(04,06),(05,07) 可见R成为了一个无序对的集合，其中的每个元素为用圆括号括起来的一个无序对，对应图形中的一条无向边，由无向边构成的图形称为无向图，反之为有向图。 六、算法的时间复杂度 算法的时间复杂度是一个算法运行时间的相对量度。一个算法的运行时间是指在计算机上从开始到结束运行所花费的时间长短，它大致等于计算机执行一种简单操作(如赋值、比较、计算、转向、返回、输入、输出等)所需的时间与算法中进行简单操作次数的乘积。因为执行一种简单操作所需的时间随机器而异，它是由机器本身硬软件环境决定的，与算法无关，所以我们只讨论影响运行时间的另一个因素算法中进行简单操作次数的多少。不管一个算法是简单还是复杂，最终都是被编译后分解成简单操作再通过CPU来具体执行的。因此，每个算法都对应着一定的简单操作的次数。显然，在一个算法中，进行简单操作的次数越少，其运行时间也就相对地越短；次数越多，其运行时间也就相对地越长。所以，通常把算法中包含简单操作次数的多少叫做该算法的时间复杂度，或者叫做时间复杂性，用它来衡量一个算法的运行时间性能或称计算性能。若解决一个问题的规模为n，即表示待处理的数据中包含有n个元素，则算法的时间复杂度通常是n的一个函数，假定记为f(n)。 算法的时间复杂度通常采用数量级的形式表示，所以求一个算法的时间复杂度只要分析清楚算法中主要的循环体内简单操作的执行次数，或递归函数的调用次数即可。例如，对于一个含有nC次循环的算法，其中n表示待处理问题的规模，C是一个常量，nC，则该算法的时间复杂度为O(n)；对于一个含有双重循环的算法，循环次数的主体呈现在n2数量级上，所以则该算法的时间复杂度为O(n2)。 算法的时间复杂度通常具有O(1)、O()、O(n)、O(log2n)、O(n*log2n)、O(n2)、O(n3)、O(2n)和O(n!)等形式。其中O(1)表示算法的时间复杂度为常量，它不随数据量n的改变而改变，如访问一个数据表中第一个元素时，无论该表的大小如何，其时间复杂度均为O(1)。O()表示算法的时间复杂度与数据量大小n的平方根成正比，如计算满足不等式中的最大i值时，其算法的时间复杂度就是O()。具有O(n)数量级的算法被称为具有线性数量级的算法，其运行时间与n成正比，如对一个表进行顺序查找时，其时间复杂度就是O(n)。有一些算法的时间复杂度为O(log2n)，即与n的对数成正比，如在有序表上进行二分查找的算法就是如此。对数组进行简单插入或选择排序的算法的时间复杂度为O(n2)，当n加倍时，其运行时间将增长4倍。 一个算法的时间复杂度还可以具体分为最好、最差和平均三种情况来讨论。下面结合从一维数组an中顺序查找其值等于给定值item的元素的算法进行说明。 int SequenceSearch(int a, int n, int item) /若查找成功则返回元素的下标，否则返回-1。 for(int i=0; in; i+) if(ai=item) return i; return -1; 此算法的时间复杂度主要取决于for循环体被反复执行的次数。最好情况是第一个元素a0的值就等于item，此时只需要进行元素的一次比较就查找成功，相应的时间复杂度为O(1)；最差情况是最后一个元素an-1的值等于item，此时需要进行同全部n个元素的比较才能查找成功，相应的时间复杂度为O(n)；平均情况是：每一个元素都有相同的概率（即均为）等于给定值item，则查找成功需要同元素进行比较的平均次数为，相应的时间复杂度为O(n)，它同最坏情况具有相同的数量级，因为它们之间的比较次数只在n的系数项和常数项上有差别，而在n的指数上没有差别。 当在数组a上顺序比较所有n个元素后仍找不到等于给定值item的元素，则表明查找失败，这种情况所对应的时间复杂度也为O(n)。 对于许多算法来说，平均和最差这两种情况下的时间复杂度的数量级形式往往是相同的，它们主要是差别在最高次幂的系数上。另外有一些算法，其最好、最差和平均情况下的时间复杂度或相应的数量级都是相同的，如求出n个元素平均值的算法就是如此，其时间复杂度的最好、最差和平均情况均为O(n)。 上面从数据结构的分类、数据结构的定义、数据结构的二元组表示、数据结构的图形表示、数据结构的应用举例等多个方面，对数据结构的含义进行了详细地阐述，以便使同学们能够更好地利用数据结构组织数据和处理问题。这一讲也同时简要地介绍了算法的时间复杂度，与时间复杂度相类似的还有算法的空间复杂度，它是算法在运行过程中临时占用内存空间大小的相对量度，它也有常量级O(1)、平方根级O()、线性级O(n)、平方级O(n2)、对数级O(log2n)等不同级别。例如，对于下面的算法：int f(int n) if(n0) return -1; else if(n=0) rerun 0; else retun n+f(n-1);这是一个递归算法，其功能是计算出1+2+n的累加和，该算法要被递归调用n+1次，其参数值依次为n、n-1、1、0，每次调用都是执行一条条件语句，而且都要把n值保存起来，所以该算法的时间复杂度和空间复杂度均为O(n)。这一讲到此结束，同学们再见！同学们好:第二讲 集合与线性表 一、集合的定义 二、集合的抽象数据类型 三、集合的顺序存储结构和操作实现 四、集合的链接存储结构和操作实现 五、集合运算的时间复杂度分析 六、线性表的存储和运算简介 一、集合的定义 集合是集合结构的简称，它是具有相同属性的数据元素按任何次序排列而成的。该集合中数据元素的个数称为集合的长度，通常用n表示，n0。当n=0时则为空集。若集合为空，则表示为，若非空则表示为： a1,a2,ai,ai+1,an 其中每个元素的下标为对该元素的编号，它是为了区别而任意标注的，不代表任何次序。因为集合中的元素可以按任何次序排列，假定就按元素前后位置编号的次序排列，那么a1就是集合中的第一个元素，a2就是集合中的第二个元素,ai就是第i个元素,an就是第n个（即最后一个）元素。 集合中不含有任何关系，或者说含有的关系为空。 集合中的元素类型可以为任何一种类型，假定用标识符ElemType表示。若实际的元素类型为某一具体类型，如整型int，则可以通过如下语句把ElemType类型等价定义为int类型。 Typedef int ElemType; 二、集合的抽象数据类型 集合的抽象数据类型包括数据和操作两个部分。数据部分为一个集合，假定用标识符S表示。操作部分包含对集合进行的各种常用运算，如初始化一个集合，向集合中插入一个元素，从集合中删除一个元素，从集合中查找一个元素等。 集合结构的抽象数据类型可定义如下： ADT SET is /其中SET表示集合的抽象数据类型名 Data: /表明为数据部分 一个集合S Operation: /表明为操作部分 void InitSet(&S) /初始化集合为空 bool InsertSet(&S, item); /向集合中插入一个元素 bool DeleteSet(&S, item); /从集合中删除一个元素 bool FindSet(&S, &item); /从集合中查找一个元素 . /还有其他对集合的运算 end SET 初始化集合、向集合中插入元素和从集合中删除元素等，都需要改变集合的状态，所以函数中的集合参数S必须定义为引用参数，这样才能够把运算后的结果反映到实参变量上，当从集合中查找元素时，它不会改变集合的状态，所以其集合参数可以使用引用参数，也可以使用值参数，若使用值参数，将会花费时间用来实现实参向值参变量的内容复制上，所以对集合的查找也最好采用引用参数为宜。另外，为了保护引用参数的值在查找过程中不被改变，可以使用常量引用，即在引用参数前加上const保留字。 三、集合的顺序存储结构和操作实现 集合的顺序存储结构就是把集合中的所有元素，按照一定的次序顺序存储到内存中一块连续的存储空间中。我们知道，一个数组空间是内存的一块连续的存储空间，该空间中的存储位置是按照数组下标的次序顺序排列的，所以只要按照集合元素的编号次序把每个元素存储到数组中相应下标的存储位置，就实现了集合的顺序存储结构。假定用标识符set指向动态分配的数组空间，用标识符len表示集合当前长度的变量，用标识符MaxSize表示数组空间的大小，即数组中下标位置的个数，则集合的顺序存储结构类型，定义如下： struct SetSq /这里假定用标识符SetSq表示这种结构类型 ElemType *set; /set用来指向动态分配的数组空间 int len; /存集合当前长度，即当前集合中所含元素的个数 int MaxSize; /存set数组长度，亦即所能存储集合的最大长度 ; 集合的顺序存储结构的示意图如下所示： len set 0 1 2 n-1 n n+1 MaxSize-1a1a2a3 an 在这里，a1元素被存储到数组中下标为0的数组单元中，a2元素被存储到下标为1的单元中，依次类推，最后一个元素an被存储到下标为n-1的单元中，存储集合长度len变量的值等于n，存储数组长度MaxSize变量的值等于数组空间的最大下标值加1。 下面给出对顺序存储的集合S进行初始化以及插入、删除和查找元素的算法。 1. 初始化集合 初始化集合需要为集合动态分配数组存储空间，并使set指向这个数组空间，该空间的大小由参数ms决定，当然ms的值要大于等于1。 void InitSet(SetSq& S, int ms) if(ms=0) coutms值非法!endl; exit(1); S.MaxSize=ms; /置数组空间大小为ms S.set=new ElemTypems; /动态分配数组存储空间 S.len=0; /初始置集合为空，即置当前集合长度为0 2. 向集合中插入一个元素此算法包含如下五个步骤： (1) 检查存储集合的数组空间是否被用完，若是则停止运行；(2) 顺序查找集合中是否存在值为待插值item的元素，若存在则不能插入，返回假， 因为集合中不允许存在重复的元素； (3) 把item值插入到最后一个集合元素的后面空位置上； (4) 集合长度增1； (5) 返回真表示插入成功。 对应的算法描述如下： bool InsertSet(SetSq& S, ElemType item) if(S.len=S.MaxSize) cout集合空间满!endl; exit(1); for(int i=0; iS.len; i+) if(S.seti=item) cout元素已存在!endl; return false; S.setS.len=item; S.len+; return true; 3. 从集合中删除一个元素 此算法首先从集合中顺序查找值等于待删值item的元素，若存在则删除它，删除过程是把最后一个元素直接移动到该元素空出的位置，接着使集合长度减1，返回真表示删除成功；若不存在，则无法删除，返回假表示删除失败。 bool DeleteSet(SetSq& S, ElemType item) for(int i=0; iS.len; i+) if(S.seti=item) break; if(iS.len) S.seti=S.setS.len-1; S.len-; return true; /删除成功返回真 else return false; /删除失败返回假 4. 从集合中查找一个元素 此算法首先从集合中顺序查找值等于待查值item的元素，若存在则把该元素值赋给item引用参数带回，并返回真表示查找成功；若不存在，则返回假表示查找失败。 通常传递给item的待查值是一个元素的关键字，不是完整的记录，如对于学生记录，待查值是学号，对于产品记录，待查值是产品号；若查询到对应值的元素，则需要把该元素的完整值赋给item带回，以便使用。如可以通过item得到某个学生的成绩，某个产品的价格等。 bool FindSet(SetSq& S, ElemType& item) for(int i=0; iS.len; i+) if(S.seti=item) break; if(idata=item) break; else p=p-next; if(p!=NULL) return false; /插入失败返回假 /建立值为item的新结点 sNode* tp=new sNode; tp-data=item; /新结点tp插入到单链表的表头 tp-next=head; head=tp; /返回真表示插入成功 return true; 3. 从集合中删除一个元素(1) 顺序查找集合单链表中是否存在值为待删除值为item的元素，若不存在则返回假，表示删除失败； (2) 从单链表中删除结点，即把被删除结点的指针域的值赋给其前驱结点的指针域，若删除的是单链表中的表头结点，则把该结点的指针域的值赋给表头指针即可； (3) 返回真表示删除成功。 bool DeleteSet(sNode*& head, ElemType item) /从单链表中顺序查找是否存在值为item的结点 sNode *p=head, *q=NULL; /q指向p的前驱结点，开始时p指表头，q为空 while(p!=NULL) if(p-data=item) break; else q=p; p=p-next; if(p=NULL) return false; /删除失败，返回假 /从单链表中删除已找到的p结点，它的前驱结点为q结点 if(q=NULL) head=p-next; /删除表头结点，从单链表中摘除 else q-next=p-next; /删除非表头结点 /回收p结点后返回真 delete p; return true; 4. 从集合中查找一个元素 bool FindSet(sNode* head, ElemType& item) /从单链表中顺序查找是否存在值为item的结点 sNode* p=head; while(p!=NULL) if(p-data=item) break; else p=p-next; /若存在由item带回已查找到的元素并返回真，否则返回假 if(p!=NULL) item=p-data; return true; else return false; 五、集合运算的时间复杂度分析 插入运算：若已知插入的元素是集合中没有的，则可以省略从集合中查找该元素的步骤，把该元素直接写入到集合顺序表的表尾后的位置，使之成为新的表尾，或者把该元素直接链接到集合单链表的表头，成为新的表头结点，这种情况的时间复杂度为O(1)；若在插入时不省略查找步骤，则向集合插入元素的时间复杂度为O(n)。 删除运算：需要从集合中先顺序查找出待删除的元素，然后再从集合中删除该元素，所以其时间复杂度为O(n)。 查找运算：需要顺序查找出给定元素，所以其时间复杂度为O(n)。 六、线性表的存储和运算简介 线性表是线性结构的一种表现形式。 线性表的定义、抽象数据类型、存储结构和运算等都同集合类似。 线性表就是一种线性结构，即是具有相同属性的一个有限序列，序列中的元素是一个接一个有序的，序列中元素的个数就是该线性表的长度，若用n表示，则n大于等于0，当n等于0时其线性表为空。线性表中的所有元素通常用一对圆括号括起来，元素之间的位置排列次序就是它们的先后逻辑顺序。线性表中的元素个数也随着插入和删除元素的变化而变化。当向线性表中插入一个元素时，其长度就增加1，相反，当从线性表中删除一个元素后，其长度就减少1。 线性表的抽象数据类型也同样包括数据和操作两个部分，数据部分是一个用顺序或链接存储的线性表，操作部分包括线性表的初始化，插入、删除、查找元素等操作。 线性表的存储结构也通常采用顺序和链接两种方式，顺序存储方式也是依靠数组实现的，链接存储方式也是依靠存储结点链接实现的。这都和集合的存储结构类似。 线性表的插入运算与集合结构有所不同。向集合中插入一个元素是插入到顺序存储的集合的表尾，或者链接存储的集合的表头，它不涉及到其他任何元素或结点的改变；而向线性表中插入一个元素时，是按照逻辑次序进行插入，若要插入到顺序存储的线性表的第i个元素之后，则第i+1至第n个的所有位置上的元素都要后移一个位置，腾出第i+1个位置，以便存储待插入的元素；若要插入到链接存储线性表的第i个元素之后，则要把新插入元素结点链接到对应的第i个元素结点之后，第i+1个元素结点之前，为此需把第i个结点的指针域的值赋给新插入结点的指针域，使其指向后继的第i+1个结点，接着把新插入结点的地址赋给第i个结点的指针域，使其指向新插入的结点。 下面来看一下向线性表插入元素的例子。 假定一个包含6个元素的线性表为（23,15,48,34,79,60） 假定被顺序存储在一维数组A的前6个下标位置，如下所示： 下标 0 1 2 3 4 5 6 7 8 9231548347960 假定需要在下标为3的位置插入一个元素56，则首先需要把位置3至表尾位置5的所有元素依次后移一个位置，注意，应该按下标从大到小的次序，后移对应的元素，使下标为3的位置空出来，如下所示： 下标 0 1 2 3 4 5 6 7 8 9231548347960 接着把新元素56写入到已经空出的下标为3的位置，如下所示： 下标 0 1 2 3 4 5 6 7 8 923154856347960 再修改线性表中保存的当前长度的值，使之增加1，即由6变为7。这样，对顺序存储的线性表的插入过程就结束了。 若用链接的方式存储上述所给的线性表，则如下所示： 若要在值为48的结点之后插入一个值为56的新结点，则得到的链接存储结构如下： 此时，48结点的后继结点不是34结点，而是56结点，即首先需要把原48结点的next域的值赋给新结点56的指针域使之指向34结点，接着把新结点56的地址赋给48结点的指针域，使之指向新插入的56结点，这样就完成了在链接存储的线性表上插入元素的运算。 若在顺序存储的线性表上删除一个元素，则需要把该元素位置之后的所有元素依次前移一个位置，然后再使线性表的长度减1即可。 例如，一个线性表的顺序存储结构为： 下标 0 1 2 3 4 5 6 7 8 9231548347960 若要删除下标为1位置上的元素15，则使其后的每个元素前移，如下所示： 下标 0 1 2 3 4 5 6 7 8 92348347960 然后，使线性表的长度由6减1后变为5，则删除操作就此完成。 若要在链接存储的线性表上删除一个结点，则同在链接存储的集合上的删除完全相同，就是把被删除结点的指针域的值赋给其前驱结点的指针域即可。 例如，一个线性表的链接存储结构如下： 若要从中删除值为34的结点，则把结点34的指针域的值赋给其前驱结点48的指针域即可，得到的结果如下： 特殊地，若删除的是表头结点，即head指针所指向的值为23的结点，则需要把需要把23结点的指针域的值赋给表头指针变量head，使head指向了值为15的结点，即原单链表中的第二个结点，运算结果如下： 这一讲就讲到这里，同学们再见！同学们好:第三讲 栈和队列第一部分 栈一、栈的定义 二、栈的抽象数据类型三、栈的顺序存储结构和操作实现四、栈的链接存储结构和操作实现五、栈的简单应用举例一、栈的定义 栈（Stack）是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把对栈进行运算的一端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。 在日常生活中，有许多类似栈的例子，如刷洗盘子时，依次把每个洗净的盘子放到洗好的一摞盘子的上面，此操作相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。又如向枪支弹夹里装子弹时，子弹被一个接一个地压入，则称为进栈；射击时子弹总是从顶部一个接一个地被射出，此称为子弹出栈。 由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称为后进先出表(Last In First Out, 简称LIFO)。 假定一个栈S为(a,b,c)，其中表尾的一端为栈顶，字符c为栈顶元素。若向S压入一个元素d，则S变为(a,b,c,d)，此时字符d为栈顶元素；若接着从栈S中依次删除两个元素，则首先删除的是元素d，接着删除的是元素c，栈S变为(a,b)，栈顶元素为b。 二、栈的抽象数据类型 栈的抽象数据类型中的数据部分为具有ElemType元素类型的一个栈，它可以采用任一种存储结构实现；操作部分应包括元素进栈、元素出栈、读取栈顶元素、检查栈是否为空等。下面给出栈的抽象数据类型的具体定义。 ADT STACK is /STACK是栈的抽象数据类型名 Data: 一个栈S，存储栈中的所有元素 Operation: void InitStack(&S); /初始化栈S,即把它置为空 void Push(&S, item) /元素进栈，即把元素item插入到栈顶 ElemType Pop(&S) /删除栈顶元素并返回之 ElemType Peek(&S) /返回栈顶元素的值，但不改变栈的状态 bool EmptyStack (&S); /判断S是否为空 void ClearStack(&S); /清除栈中所有元素，使之成为空栈 end STACK 对于判断栈是否为空和返回栈顶元素这两种操作，由于它们不改变栈的状态，所以可在引用参数前使用常量定义符const，使得函数操作不能有意或无意地改变栈的状态。 假定栈a的元素类型为int，下面给出调用上述栈操作的一些例子。 (1) InitStack(a); /表示把栈a置空 (2) Push(a,18); /表示元素18进栈 (3) int x=46; Push(a,x); /表示x的值46进栈 (4) Push(a,x/3); /表示x除以3的整数值15进栈 (5) x=Pop(a); /表示栈顶元素15退栈并赋给x (6) coutPeek(a); /表示读取当前栈顶元素46并输出 (7) Pop(a); /栈顶元素46出栈，返回值46自动丢失 (8) EmptyStack(a); /因此时栈a非空，所以返回的值false (9) coutPop(a)endl; /栈顶元素18退栈并输出，此时栈已空 (10) x=EmptyStack(a); /因栈为空，返回true，接着把对应的整数值1赋给x三、栈的顺序存储结构和操作实现 栈的顺序存储结构同集合的顺序存储结构类似，定义的结构类型如下： struct Stack / Stack为结构类型名 ElemType *stack; /指向动态分配的数组存储空间的首地址的指针 int top; /栈顶指针，存储栈顶元素所在的下标位置 int MaxSize; /保存stack所指向的栈空间的大小 ; 在顺序存储的栈中，top的值为-1表示栈空，每次向栈中压入一个元素时，首先使top增1，用以指示新的栈顶位置，然后再把元素赋值到这个空位置上，每次从栈中弹出一个元素时，首先取出栈顶元素，然后使top减1，指示出前一个元素成为新的栈顶元素。由此可知，对顺序栈的插入和删除运算相当于是在顺序表的表尾进行的，其时间复杂度为O(1)。 在一个顺序栈中，若top已经指向了MaxSize-1的位置，则表示栈满，若再向其插入新元素时就需要进行栈满处理，如分配更大的存储空间满足插入要求，或输出栈满信息告之用户等；相反，若top的值已经等于-1，则表示栈空，通常利用栈空作为循环结束的条件，表明栈中的数据已经处理完毕。 设一个栈S为(a,b,c,d,e)，对应的顺序存储结构如下图(a)所示。若向S中插入一个元素f，则对应如下图(b)所示。若接着执行两次出栈操作后，则栈S对应如下图(c)所示。若依次使栈S中的所有元素出栈，则s变为空，如下图(d)所示。 下面给出栈在顺序存储结构下的操作实现。 1. 初始化栈S为空 初始化顺序栈需要为其动态分配数组存储空间，并使stack指向这个数组空间，该空间的大小由参数ms决定，当然ms的值要大于等于1。 void InitStack(Stack& S, int ms) if(ms=0) coutms值非法!endl; exit(1); /初始设置栈空间大小为ms的值 S.MaxSize=ms; /动态存储空间分配 S.stack=new ElemTypeS.MaxSize; /初始置栈为空 S.top=-1; 2. 元素item进栈，即插入到栈顶