基本数据结构修改.ppt

第二章 基本数据结构及其运算,2.1 数据结构的基本概念 2.2 线性表及其顺序存储结构 2.3 线性链表及其运算 2.4 树与二叉树,第2章 基本数据结构及其运算,2,2.1 数据结构的基本概念,2.1.1 两个例子 2.1.2 什么是数据结构 2.1.3 数据结构的图形表示 2.1.4 线性数据结构与非线性数据结构,第2章 基本数据结构及其运算,3,数据结构三个方面的问题： (1)数据的逻辑结构 (2)数据的存储结构 (3)对各种数据结构进行的运算 目的：提高数据处理的效率 提高数据处理的速度 尽量节省计算机存储空间,第2章 基本数据结构及其运算,4,2.1.1 两个例子 计算机已广泛应用于数据处理。实际问题中的各数据元素之间总是相互关联的。 所谓数据处理，是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，以包括对数据元素进行分析。,第2章 基本数据结构及其运算,5,重要的是知道数据集合中各数据元素之间存在什么关系，为了提高处理效率，应如何组织它们，即如何表示所需要处理的数据元素。,第2章 基本数据结构及其运算,6,例2.1 无序表的顺序查找 35 16 78 85 43 29 33 21 54 46 有序表的对分查找 16 21 29 33 35 43 46 54 78 85 数据元素在表中的排列顺序对查找效率是有很大影响,第2章 基本数据结构及其运算,7,无序表的顺序查找,从第一个元素开始，逐个将表中的元素与被查数进行比较，直到表中的某个元素与被查数相等（即查找成功）或者表中所有元素都与被查数进行了比较且都不相等（即查找失败）为止。 最少次数：被查元素刚好是表中第一个元素时。只需比较一次。 最多次数：被查元素刚好是表中最后一个元素时或表中不存在被查元素。在这种情况下顺序查找是很费时间的。,第2章 基本数据结构及其运算,8,有序表中的二分查找,将被查数与表中的中间这个元素进行比较：若相等，则表示查找成功，查找过程结束；若被查数大于表中的中间这个元素，则表示如果被查数在表中，只能在表的后半部，此时可以舍弃表中的前半部保留后半部；若被查数小于表中的中间元素，则表示如果被查数在表中，只能在表的前半部此时可以舍弃后半部而保留前半部。然后对剩下部分再按照上述方法进行查找，这个过程一直做到在某次的比较中相等（查找成功）或剩下的部分已空（查找失败）为止。,9,在有序表的对分查找中，不论查找的是什么数，也不论要查找的数在表中有没有，都不需要与表中所有元素进行比较，并且只需要与表中很少的元素进行比较。但需要指出的是，对分查找只适用于有序表，而对于无序表是无法进行对分查找的。,第2章 基本数据结构及其运算,10,例2.2 学生情况登记表以学号为顺序排列,第2章 基本数据结构及其运算,11,第2章 基本数据结构及其运算,12,第2章 基本数据结构及其运算,13,结论： 在对数据进行处理时， 可以根据所做的运算不同， 将数据组织成不同的形式， 以便于做该种运算， 从而提高数据处理的效率。,第2章 基本数据结构及其运算,14,2.1.2 什么是数据结构 数据结构是指相互有关联的数据元素集合。 现实世界中客观存在的一切个体都可以是数据元素。,第2章 基本数据结构及其运算,15,描述一年四季的季节名 春，夏，秋，冬 可以作为季节的数据元素； 表示数值的各个数 18，11，35，23，16， 可以作为数值的数据元素； 表示家庭成员的各成员名 父亲，儿子，女儿 可以作为家庭成员的数据元素。,第2章 基本数据结构及其运算,16,前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义是随具体对象的不同而不同。 一般来说，数据元素之间的任何关系都可以用前后件关系来描述。 例如：“春” 是“夏”的前件，“夏”是“春”的后件。 “父亲”是“儿子”，“女儿”的前件， “儿子”，“女儿”是“父亲”的后续。,第2章 基本数据结构及其运算,17,1.数据的逻辑结构 是指反映数据元素之间逻辑关系的数据结构。 （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。,第2章 基本数据结构及其运算,18,数据的逻辑结构有两个要素： 数据元素的集合D； 反映D中各数据元素之间的前后件关系R。 数据结构可以表示成 B（D，R） 其中B表示数据结构。,第2章 基本数据结构及其运算,19,为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。 设a与b是D中的两个数据，则二元组 （a，b） 表示a是b的前件，b是a的后件。 例如 B（D，R） D春，夏，秋，冬 R(春，夏)，(夏，秋)，(秋，冬),第2章 基本数据结构及其运算,20,家庭成员数据结构 B（D，R） D父亲，儿子，女儿 R(父亲，儿子），(父亲，女儿） n维向量 X（x1，x2，xn） 也是一种数据结构。即 X（D，R） Dx1，x2，xn R(x1，x2)，(x2，x3)，(xn1，xn),第2章 基本数据结构及其运算,21,mn的矩阵是一个数据结构。即 A（D，R） DA1，A2，Am R(A1，A2)，(A2，A3)，(Ai，Ai1)，(Am1，Am) 其中Ai=（ai1，ai2，ain），i1，2，m Ai（Di，Ri） Diai1，ai2，ain Ri(ai1，ai2)，(ai2，ai3)，(aij，ai，j1)，(ai，n1，ain),第2章 基本数据结构及其运算,22,2.数据的存储结构（数据的物理结构） 数据的逻辑结构在计算机存储空间中的存放形式。 常用的存储结构有： 顺序、链接、索引等存储结构。 采用不同的存储结构，其数据处理的效率是不同的。,第2章 基本数据结构及其运算,23,2.1.3 数据结构的图形表示 数据集合D中的每一个数据元素用中间标有元素值的方框表示（数据结点，结点） 用一条有向线段从前件结点指向后件结点。,第2章 基本数据结构及其运算,24,一年四季数据结构的图形表示,第2章 基本数据结构及其运算,25,家庭成员间辈份关系数据结的图形表示,第2章 基本数据结构及其运算,26,DS1=(D1,R1) D1=a,b,c,d,e R1=(a,b),(b,c),(c,d),(d,e),(e,a),(a,c),(a,d),(b,e),(c,e),DS1是个无向图,第2章 基本数据结构及其运算,27,DS2=(D2,R2) D2=a,b,c,d,e R2=a,b,b,c,c,d,d,e,e,a,a,c,a,d,b,e,c,e,DS2是一个有向图,第2章 基本数据结构及其运算,28,DS2=(D2,R2) D2=a1,a2,a3,ak R2=| ,这说明这个关系R2任何两递增下标的数据元素都有相邻关系，如图所示,数组的数据结构,第2章 基本数据结构及其运算,29,用图形表示数据结构B（D，R） Ddi |1i7d1，d2，d3，d4，d5，d6，d7 R(d1，d3)，(d1，d7)，(d2，d4)，(d3 ，d6) ，(d4 ，d5 ) ,第2章 基本数据结构及其运算,30,数据结构的相关概念,在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点（也成为叶子结点）；除了根结点与终端结点外的其他结点一般称为内部结点。 数据结构中的相关运算： 插入运算、删除运算。这两个运算是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。 在一个数据结构中元素结点和数据元素之间的关系都可能是动态变化的。,第2章 基本数据结构及其运算,31,2.1.4 线性数据结构与非线性数据结构 线性表的逻辑结构是n个数据元素的有限序列(a1,a2,a3,an) 其中n表示了线性表的长度（n=0）.n=0的表称为空表。 线性结构：数据元素呈线性关系。隐含有序。 （1）有且只有一个根结点； （2）每一个结点最多有一个前件， 也最多有一个后件。 线性结构又称线性表。,第2章 基本数据结构及其运算,32,特别说明,在一个线性结构中插入或删除任何一个结点后还应该是线性结构。如果一个数据结构满足上述两个条件，但当在此数据结构中插入或删除任何一个结点后就不满足这两个条件了，则该数据结构不能称为线性结构。,第2章 基本数据结构及其运算,33,不是线性结构的数据结构特例,第2章 基本数据结构及其运算,34,如果一个数据结构不是线性结构， 则称之为非线性结构,第2章 基本数据结构及其运算,35,2.2 线性表及其顺序存储结构,2.2.1 线性表及其运算 2.2.2 栈及其应用 2.2.3 队列及其应用,第2章 基本数据结构及其运算,36,2.2.1 线性表及其运算 1.什么是线性表(Linear List) 线性表是最简单最常用的一种数据结构。 线性表是由一组数据元素构成。 例如：n维向量(x1，x2，xn)是一个长度为n的线性表，其中的每一个分量就是一个数据元素。 英文小写字母表(a，b，c，z)是一个长度为26的线性表 一年中的四个季节(春，夏，秋，冬)是一个长度为4的线性表 矩阵是一个比较复杂的线性表,第2章 基本数据结构及其运算,37,学生情况登记表是一个复杂的线性表,由若干数据项组成的数据元素称为记录(record) 由多个记录构成的线性表又称为文件(file),第2章 基本数据结构及其运算,38,线性表是由n(n0)个数据元素a1，a2，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为 (a1，a2，ai，an) 其中ai(i1，2，n)是属于数据对象的元素，通常也称其为线性表中的一个结点。,线性表的逻辑结构,第2章 基本数据结构及其运算,39,非空线性表结构特征： (1)有且只有一个根结点a1，它无前件； (2)有且只有一个终端结点an，它无后件； (3)除根结点与终端结点外，其它所有结点有且只有一个前件，也有且只有一个后件。 线性表中结点的个数n称为线性表的长度。当n0时，称为空表。,第2章 基本数据结构及其运算,40,2. 线性表的顺序存储结构 线性表的顺序存储结构基本特点： (1)线性表中所有元素所占的存储空间是连续的； (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 线性表中第i个元素ai在计算机存储空间中 的存储地址为 ADR(ai)ADR(a1)(i1)k,第2章 基本数据结构及其运算,41,长度为n的线性表 (a1，a2，ai，an) 顺序存储结构,第2章 基本数据结构及其运算,42,整型一维数组存放 长度为8的线性表 (29,18,56,63,35,24,31,47),第2章 基本数据结构及其运算,43,建立空线性表的顺序存储空间 （即初始化线性表的顺序存储空间） #include “stdlib.h“ void initsl(v，m，n) ET *v； int m， *n； vmalloc(m*sizeof(ET)； *n0； return； 释放线性表的顺序存储空间 free(v)；,第2章 基本数据结构及其运算,44,线性表顺序存储结构下的主要运算： (1)在线性表的指定位置处加入一个新的元素（即线性表的插入）； (2)在线性表中删除指定的元素（即线性表的删除）； (3)在线性表中查找某个（或某些）特定的元素（即线性表的查找）； (4)对线性表中的元素进行整序（即线性表的排序）； (5)按要求将一个线性表分解成多个线性表（即线性表的分解）； (6)按要求将多个线性表合并成一个线性表（即线性表的合并）； (7)复制一个线性表（即线性表的复制）； (8)逆转一个线性表（即线性表的逆转）等。,第2章 基本数据结构及其运算,45,3.线性表在顺序存储下的插入运算,第2章 基本数据结构及其运算,46,第2章 基本数据结构及其运算,47,线性表在顺序存储下的插入算法 输入：线性表的存储空间V(1：m)；线性表的长度n（nm）；插入的位置i（i表示在第i个元素之前插入）；插入的新元素b。 输出：插入后的线性表存储空间V(1：m)及线性表的长度n。,第2章 基本数据结构及其运算,48,PROCEDURE INSL(V，m，n，i，b) 1. IF (nm) THEN OVERFLOW；RETURN 2. IF (in) THEN in1 3. IF (i1) THEN i1 4. FOR jn TO i BY 1 DO V(j1)V(j) 5. V(i)b 6. nn1 7. RETURN,第2章 基本数据结构及其运算,49,void insl(v，m，n，i，b) ET v，b； int m，n，i； if (nm) printf(“overflow n“)； return； if (in) in1；在最后一个元素 if (i1) i1；在第一个元素之前 for (jn；ji；j) vjvj1； vi1b； n n1； return； ,第2章 基本数据结构及其运算,50,4.线性表在顺序存储下的删除运算,第2章 基本数据结构及其运算,51,第2章 基本数据结构及其运算,52,线性表在顺序存储下的删除算法 输入：线性表的存储空间V(1：m)；线性表的长度n（nm）； 删除的位置i（表示删除第i个元素）。 输出：删除后的线性表存储空间V(1：m)及线性表的长度n。,第2章 基本数据结构及其运算,53,PROCEDURE DESL(V，m，n，i) 1. IF (n0) THEN UNDERFLOW；RETURN 2. IF (i1)or(in) THEN “Not this element in the list”；RETURN 3. FOR ji TO n1 DO V(j)V(j1) 4. nn1 5. RETURN,第2章 基本数据结构及其运算,54,void desl(v，m，n，i) ET v； int m，*n，i； if (*n0) printf(“underflow n“)；return； if (i1) | | (i*n) printf(“Not this element in the list n“)； return； for (ji；j*n1；j) vj1vj； *n *n1； return； ,第2章 基本数据结构及其运算,55,1.什么是栈 栈（stack）是一种特殊的线性表。对它的操作只能是“后进先出”（LIFO），也是使用最为广泛的数据结构之一。因为它的运算次序受到严格的规定，故又称为限定性数据结构。 为了认识栈这种数据结构，首先介绍一个例子。,2.2.2 栈及其应用,第2章 基本数据结构及其运算,56,主程序与子程序之间的调用关系 MAIN SUB1 SUB2 SUB3 SUB4 CALLSUB1 CALLSUB2 CALLSUB3 CALLSUB4 A： B： C： D： END RETURN RETURN RETURN RETURN,第2章 基本数据结构及其运算,57,由这个例子可以看出，在这种特殊的线性表中，其插入与删除运算都只能在线性表的一段进行。即在这种线性表的结构中，一端是封闭的，不允许插入和删除元素；另一端是开口的，允许插入与删除元素。在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其它数据元素的。这种线性表成为栈。,第2章 基本数据结构及其运算,58,栈(stack)是限定在一端进行插入与删除的线性表。 栈顶:允许插入与删除的一端. 栈底:不允许插入与删除的另一端。 栈是按照“先进后出” (FILOFirst In Last Out)或“后进先出” (LIFOLast In First Out)的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。 栈具有记忆作用。用指针top来指示栈顶的位置，用指针bottom指向栈底。 往栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素)称为退栈运算。,关于栈的几个基本概念,第2章 基本数据结构及其运算,59,第2章 基本数据结构及其运算,60,2.栈的顺序存储及其运算,第2章 基本数据结构及其运算,61,top0表示栈空；topm表示栈满。 建立空栈的顺序存储空间 （即初始化栈的顺序存储空间） #include “stdlib.h“ void init_stack(s，m，top) ET *s； int m， *top； smalloc(m*sizeof(ET)； *top0； return； 释放栈的顺序存储空间时 free(s)；,第2章 基本数据结构及其运算,62,(1)入栈运算 PROCEDURE PUSH(S，m，top，x) 1. IF (topm) THEN StackOVERFLOW；RETURN 2. toptop1 3. S(top)x 4. RETURN,void push(s，m，top，x) ET s，x； int m，*top； if (*topm) printf(“Stackoverflown“)；return； *top*top1； s*topx； return； ,第2章 基本数据结构及其运算,63,(2) 退栈运算,PROCEDURE POP(S，m，top，y) 1. IF (top0) THEN StackUNDERFLOW；RETURN 2. yS(top) 3. toptop1 4. RETURN,void pop(s，m，top，y) ET s，*y； int m，*top； if (*top0) printf(“Stackunderflown“)；return； *ys*top； *top*top1； return； ,第2章 基本数据结构及其运算,64,PROCEDURE TOP(S，m，top，y) 1. IF (top0) THEN “Stack empty”；RETURN 2. yS(top) 3. RETURN,(3) 读栈顶元素,void top(s，m，top，y) ET s，*y； int m，*top； if (*top0) printf(“Stack empty n“)；return； *ys*top； return； ,第2章 基本数据结构及其运算,65,3.表达式的计算 运算符栈，用于在表达式处理过程中存放运算符。 在开始时，运算符栈中先压入一个表达式结束符“；”。 操作数栈，用于在表达式处理过程中存放操作数。,第2章 基本数据结构及其运算,66,从左到右依次读出表达式中的各个符号： 若是操作数，则压入操作数栈，依次读下一个符号。 若是运算符，则作进一步判断：,第2章 基本数据结构及其运算,67,若读出运算符的优先级大于运算符栈栈顶运算符的优先级，则将读出的运算符压入运算符栈，并依次读下一个符号。 若读出的是表达式结束符“；”，且运算符栈栈顶的运算符也是表达式结束符“；”，则表达式处理结束，最后的计算结果在操作数栈的栈顶位置。 若读出运算符的优先级不大于运算符栈栈顶运算符的优先级，则从操作数栈连续退出两个操作数，并从运算符栈退出一个运算符，然后作相应的运算（运算符为刚从运算符栈退出的运算符，运算对象为刚从操作数栈退出的两个操作数），并将运算结果压入操作数栈。,第2章 基本数据结构及其运算,68,AB*CD/E；,第2章 基本数据结构及其运算,69,AB*CD/E；,第2章 基本数据结构及其运算,70,AB*CD/E；,第2章 基本数据结构及其运算,71,AB*CD/E；,第2章 基本数据结构及其运算,72,4.递归 依次打印输出自然数1到n的非递归算法 PROCEDURE WRT(n) FOR k1 TO n DO OUTPUT k RETURN 依次打印输出自然数1到n的递归算法 PROCEDURE WRT(n) IF (n0) THEN WRT(n)； OUTPUT n RETURN,第2章 基本数据结构及其运算,73,#include “stdio.h“ wrt(int n) if (n!0) wrt(n1)； printf(“%dn“，n)； return； ,第2章 基本数据结构及其运算,74,2.2.3 队列及其应用 1.什么是队列 队列(equeue)是指允许在一端进行插入、而在另一端进行删除的线性表。 数据结构中的队列与生活中的“排队”极为相似，也是按“先来先解决”的原则行事的，并且既不允许“加塞”，也不允许“中途离队”。,第2章 基本数据结构及其运算,75,关于队列的几个基本概念,允许插入的一端称为队尾，用尾指针(rear)指向队尾元素。 允许删除的一端称为排头(也称队头)，用排头指针(front)指向排头元素的前一个位置。 队列又称为“先进先出” (FIFOFirst In First Out)或“后进后出” (LILOLast In Last Out)的线性表，体现了“先来先服务”的原则。 往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。,第2章 基本数据结构及其运算,76,第2章 基本数据结构及其运算,77,2.循环队列及其运算,第2章 基本数据结构及其运算,78,第2章 基本数据结构及其运算,79,队列空的条件为 s0 队列满的条件为 (s1)且frontrear,第2章 基本数据结构及其运算,80,建立循环队列顺序存储空间 （即初始化循环队列顺序存储空间） #include “stdlib.h“ void init_queue(q，m，front，rear，s) ET *q； int m， *front， *rear， *s； qmalloc(m*sizeof(ET)； *frontm；*rearm；*s0； return； 释放循环队列的顺序存储空间 free(q)；,第2章 基本数据结构及其运算,81,(1) 入队运算 PROCEDURE ADDCQ(Q，m，rear，front，s，x) 1. IF (s1)and(rearfront) THEN QueueOVERFLOW；RETURN 2. rearrear1 3. IF (rearm1) THEN rear1 4. Q(rear)x 5. s1 6. RETURN,第2章 基本数据结构及其运算,82,void addcq(q，m，rear，front，s，x) ET q ，x； int m，*rear，*front，*s； if (*s1) & (*rear *front) printf(“QueueOVERFLOW n“)； return； *rear *rear1； if (*rearm1) *rear1； q*rearx； *s1； return； ,第2章 基本数据结构及其运算,83,(2) 退队运算 PROCEDURE DELCQ(Q，m，rear，front，s，y) 1. IF (s0) THEN QueueUNDERFLOW；RETURN 2. frontfront1 3. IF (frontm1) THEN front1 4. yQ(front) 5. IF (frontrear) THEN s0 6. RETURN,第2章 基本数据结构及其运算,84,void delcq(q，m，rear，front，s，y) ET q ，*y； int m，*rear，*front，*s； if (*s0) printf(“QueueUNDERFLOW n“)； return； *front *front1； if (*frontm1) *front1； *yq*front； if (*front *rear) *s0； return； ,第2章 基本数据结构及其运算,85,3.队列的应用 (1) 给工人分配工作的模拟 开辟一个队列结构的线性表。 设置一个排头指针和一个队尾指针。 初始时队列为空。 每当有一个工人到调度员处报到时（包括新来的与完成任务后返回的），都将他加入到队尾；当需要一名工人去做某项工作时，就排头的工人去做该项工作。,第2章 基本数据结构及其运算,86,(2) 输入输出缓冲区的结构,第2章 基本数据结构及其运算,87,2.3 线性链表及其运算,2.3.1 线性链表的基本概念 2.3.2 线性链表的基本运算 2.3.3 循环链表,第2章 基本数据结构及其运算,88,2.3.1 线性链表的基本概念 1.线性链表 线性表的链式存储结构称为线性链表。,第2章 基本数据结构及其运算,89,第2章 基本数据结构及其运算,90,第2章 基本数据结构及其运算,91,第2章 基本数据结构及其运算,92,第2章 基本数据结构及其运算,93,依次输出线性链表中的各结点值 输入：线性链表的存储空间V(1：m)、NEXT(1：m)； 线性链表的头指针HEAD。 输出：依次输出线性链表中各结点的值。 PROCEDURE PRTLL(HEAD) jHEAD WHILE (j0) DO OUTPUT V(j) ； jNEXT(j) RETURN,第2章 基本数据结构及其运算,94,struct 结构体名 数据成员表； struct 结构体名 *指针变量名； 例如 struct node char name10； /*数据域*/ char sex； /*数据域*/ struct node *next； /*指针域*/ ,第2章 基本数据结构及其运算,95,#include “stdlib.h“/* malloc 函数需要包含头文件stdlib.h*/ struct node /*定义结点类型*/ int d； /*数据域*/ struct node *next； /*指针域*/ main() struct node *p； /*定义该类型的指针变量p*/ p=(struct node *)malloc(sizeof(struct node)； /*申请分配结点存储空间*/ free(p)； /*释放结点存储空间*/ ,第2章 基本数据结构及其运算,96,#include “stdlib.h“ #include “stdio.h“ struct node /*定义结点类型*/ int d； struct node *next； main() int x； struct node *head， *p， *q； headNULL； /*置链表空*/ qNULL； scanf(“%d”， &x)； /*输入一个正整数*/,第2章 基本数据结构及其运算,97,while(x0) /*若输入值大于0*/ p(struct node *)malloc(sizeof(struct node)；/*申请一个结点*/ pdx； pnextNULL； /*置当前结点的数据域和指针域*/ if(headNULL) headp；/*若链表空，则将头指针指向当前结点p*/ else qnextp； /*将当前结点链接在最后*/ qp； /*置当前结点为链表最后一个结点*/ scanf(“%d“， &x)； phead； while(p!NULL) /*从链表第一个结点开始打印各结点元素值，并删除*/ printf(“%5d“， pd)； /*打印当前结点中的数据*/ qp；ppnext；free(q)；/*删除当前结点并释放该结点空间*/ printf(“n“)； ,第2章 基本数据结构及其运算,98,双向链表,第2章 基本数据结构及其运算,99,2.带链的栈,第2章 基本数据结构及其运算,100,可利用栈及其运算,第2章 基本数据结构及其运算,101,将结点送回可利用栈 输入：可利用栈栈顶指针TOP（默认）；送回可利用栈的结点序号p。 输出：结点p入栈后的可利用栈栈顶指针TOP（默认）。 PROCEDURE DISPOSE(p) NEXT(p)TOP； TOPp RETURN 从可利用栈取得一个结点 输入：可利用栈的栈顶指针TOP（默认）。 输出：退栈后的可利用栈栈顶指针TOP（默认）；存放取得结点序号 的变量p。 PROCEDURE NEW(p) pTOP； TOPNEXT(TOP) RETURN,第2章 基本数据结构及其运算,102,带链栈的入栈运算 输入：带链栈的栈顶指针top；入栈的元素值x。 输出：元素x入栈后的带链栈栈顶指针top。 PROCEDURE PUSHLL(top，x) NEW(p) 从可利用栈取得一个新结点 V(p)x 置新结点数据域 NEXT(p)top 置新结点指针域 topp 改变栈顶指针 RETURN,第2章 基本数据结构及其运算,103,#include “stdlib.h“ struct node /*定义结点类型*/ ET d； /*数据元素类型*/ struct node *next； ； pushll(top，x) ET x； struct node *top； struct node *p； p(struct node *)malloc(sizeof(struct node)； pdx； pnext*top；/*置新结点的数据域与指针域*/ *topp； /*改变栈顶指针*/ return； ,第2章 基本数据结构及其运算,104,带链栈的退栈运算 输入：带链栈的栈顶指针top。 输出：退栈后的带链栈栈顶指针top；存放退出结点元素值的变量y。 PROCEDURE POPLL(top，y) yV(top) 取出栈顶元素值 ptop top=NEXT(p) 改变栈顶指针 DISPOSE(p) 被删除结点送回可利用栈 RETURN,第2章 基本数据结构及其运算,105,#include “stdlib.h“ struct node /*定义结点类型*/ ET d； /*数据元素类型*/ struct node *next； ； popll(top，y) ET y； struct node *top； struct node *p； y*topd； /*取出栈顶元素值*/ p*top； *toppnext； /*改变栈顶指针*/ free(p)； return； /*释放被删除结点后返回*/ ,第2章 基本数据结构及其运算,106,3.带链的队列,第2章 基本数据结构及其运算,107,带链队列的入队运算 输入：带链队列的队尾指针rear；入队的新元素x。 输出：元素x入队后的带链队列队尾指针rear。 PROCEDURE ADDLL(rear，x) NEW(p) 从可利用栈取得一个新结点p V(p)x 置新结点的数据域 NEXT(p)0 置新结点的指针为空 NEXT(rear)p 最后一个结点的指针指向新结点 rearp 改变队尾指针 RETURN,第2章 基本数据结构及其运算,108,#include “stdlib.h“ struct node /*定义结点类型*/ ET d； /*数据元素类型*/ struct node *next； ； addll(rear，x) ET x； struct node *rear； struct node *p； p(struct node *)malloc(sizeof(struct node)； pdx； pnextNULL； /*置新结点的数据域与指针域*/ *rearnextp； /*置最后一个结点的指针指向新结点*/ *rearp； /*改变队尾指针*/ return； ,第2章 基本数据结构及其运算,109,带链队列的退队运算 输入：带链队列的排头指针front。 输出：退队后的带链队列排头指针front；存放退出结点值的变量y。 PROCEDURE DELLL(front，y) y=V(front) 取出排头元素值 pfront frontNEXT(front) 改变排头指针 DISPOSE(p) 释放删除的结点 RETURN,第2章 基本数据结构及其运算,110,#include “stdlib.h“ struct node /*定义结点类型*/ ET d； /*数据元素类型*/ struct node *next； ； delll(front，y) ET y； struct node *front； struct node *p； y*frontd； /*取出排头元素值*/ p*front； *frontpnext； /*改变排头指针*/ free(p)； /*释放被删除结点*/ return； ,第2章 基本数据结构及其运算,111,2.3.2 线性链表的基本运算 (1)在线性链表中包含指定元素的结点之前插入 一个新元素。 (2)在线性链表中删除包含指定元素的结点。 (3)将两个线性链表按要求合并成一个线性链表。 (4)将一个线性链表按要求进行分解。 (5)逆转线性链表。 (6)复制线性链表。 (7)线性链表的排序。 (8)线性链表的查找。,第2章 基本数据结构及其运算,112,1.在线性链表中查找指定元素 在非空线性链表中寻找包含元素x的前一个结点p 输入：非空线性链表头指针HEAD；被寻找元素x。 输出：非空线性链表中包含元素x的前一个结点p。 PROCEDURE LOOKST(HEAD，x，p) pHEAD WHILE (NEXT(p)0)and(V(NEXT(p)x) DO pNEXT(p) RETURN,第2章 基本数据结构及其运算,113,struct node /*定义结点类型*/ ET d； /*数据元素类型*/ struct node *next； ； struct node *lookst(head，x) ET x； struct node *head； struct node *p； phead； while(pnext!NULL)&(pnext)d)!x) ppnext； return(p)； ,第2章 基本数据结构及其运算,114,2.线性链表的插入 在链式存储结构下的线性表中 插入一个新元素。,第2章 基本数据结构及其运算,115,可利用栈与线性链表,第2章 基本数据结构及其运算,116,(1)从可利用栈取得一个结点，设该结点号为p。 并置结点p的数据域为插入的元素值b，即V(p)b。 (2)在线性链表中寻找包含元素x的前一个结点q。,第2章 基本数据结构及其运算,117,(3)将结点p插入到结点q之后： 使结点p指向包含元素x的结点，即 NEXT(p)NEXT(q) 使结点q的指针域内容改为指向结点p，即 NEXT(q)p,第2章 基本数据结构及其运算,118,线性链表的插入 输入：线性链表的头指针HEAD；插入位置处的前一个结 点值x；插入的新元素b。 输出：插入后的线性链表。 PROCEDURE INSLST(HEAD，x，b) 1. NEW(p) 2. V(p)b 3. IF (HEAD0) THEN HEADp； NEXT(p)0； RETURN 4. IF (V(HEAD)x) THEN NEXT(p)HEAD； HEADp； RETURN 5. LOOKST(HEAD，x，q) 6. NEXT(p)NEXT(q)； NEXT(q)p 7. RETURN,第2章 基本数据结构及其运算,119,#include “stdlib.h“ struct node /*定义结点类型*/ ET d； struct node *next； ； inslst(head，x，b) ET x，b； struct node *head； struct node *p， *q； p(struct node *)malloc(sizeof(struct node)； pdb； /*置结点的数据域*/ if (*headNULL) /*链表为空*/ *headp；pnextNULL；return； if (*headd)x) /*在第一个结点前插入*/ pnext*head；*headp；return； qlookst(*head，x)；/*寻找包含元素x的前一个结点q*/ pnextqnext；qnextp；/*结点p插到结点q之后*/ return； ,第2章 基本数据结构及其运算,120,3.线性链表的删除 在链式存储结构下的线性表中 删除包含指定元素的结点。,第2章 基本数据结构及其运算,121,可利用栈与线性链表,第2章 基本数据结构及其运算,122,(1)寻找包含元素x的前一个结点q。 则包含元素x的结点序号pNEXT(q)。 (2)将结点q后的结点p删除，即 NEXT(q)NEXT(p)。,第2章 基本数据结构及其运算,123,(3)将包含元素x的结点p送回可利用栈。,第2章 基本数据结构及其运算,124,线性链表的删除 输入：线性链表的头指针HEAD；需删除的元素x。 输出：删除后的线性链表。 PROCEDURE DELST(HEAD，x) 1. IF (HEAD0) THEN “This is a empty list!”； RETURN 2. IF (V(HEAD)x) THEN pNEXT (HEAD)；DISPOSE(HEAD)；HEADp； RETURN 3. LOOKST(HEAD，x，q) 4. IF (NEXT(q)0) THEN “No this node in the list!”；RETURN 5. pNEXT(q)； NEXT(q)NEXT(p) 6. DISPOSE(p) 7. RETURN,第2章 基本数据结构及其运算,125,#include “stdlib.h“ struct node /*定义结点类型*/ ET d； struct node *next； ； delst(head，x) ET x； struct node *head； struct node *p， *q； if (*headNULL) /*链表为空*/ printf(“This is a empty list!n“)；return； if (*headd)x) /*删除第一个结点*/ p*headnext；free(*head) ；*headp；return； qlookst(*head，x) ；/*寻找包含元素x的前一个结点q*/ if (qnextNULL) /*链表中没有包含元素x的结点*/ printf(“No this node in the list!n“)；return； pqnext ；qnextpnext； /*删除结点p*/ free(p) ； /*释放结点p*/ return； ,第2章 基本数据结构及其运算,126,2.3.3 循环链表 与线性链表相比，循环链表具有以下特点： (1)在循环链表中增加了一个表头结点， 其数据域为任意或根据需要来设置， 指针域指向线性表第一个元素的结点。 循环链表的头指针指向表头结点。 (2)循环链表中最后一个结点的指针域不空， 而是指向表头结点。 即在循环链表中，所有结点的指针构成 了一个环状链。,第2章 基本数据结构及其运算,127,(1)在循环链表中，只要指出表中任何一个结点的位置， 就可以从它出发访问到表中其他所有的结点。 (2)空表与非空表的运算统一。,第2章 基本数据结构及其运算,128,在头指针为HEAD的循环链表中寻找包含 元素x的前一个结点 输入：循环链表的头指针HEAD；被寻找的元素x。 输出：循环链表中包含元素x的前一个结点p。 PROCEDURE LOOKCST(HEAD，x，p) pHEAD WHILE (NEXT(p)HEAD)and(V(NEXT(p)x) DO pNEXT(p) RETURN,第2章 基本数据结构及其运算,129,#include “stdlib.h“ struct node /*定义结点类型*/ ET d； struct node *next； ； struct node *lookcst(head，x) ET x； struct node *head； struct node *p； phead； while(pnext!head)&(pnext)d)!x) ppnext； return(p)； ,第2章 基本数据结构及其运算,130,在头指针为HEAD的循环链表中包含元素x的结点前插入新元素b 输入：循环链表的头指针HEAD；插入位置处的前一个结 点值x；插入的新元素b。 输出：插入后的循环链表。 PROCEDURE INSCST(HEAD，x，b) NEW(p) 从可利用栈取得一个新结点p V(p)b 置新结点p的数据域（插入的元素值b） LOOKCST(HEAD，x，q) 寻找循环链表中包含元素x的前一个结点q NEXT(p)NEXT(q)；NEXT(q)p 将新结点p插入到结点q之后 RETURN,第2章 基