工程软件基础2(计算机软件技术基础)

1、第二章 基本数据结构及其运算,线性表；线性链表；数组；树；图,第二章 基本数据结构,第二章 基本数据结构及运算,1 数据结构的基本概念 2 线性表及其顺序存储结构 3 线性链表及其运算 4 数组 5 树与二叉树 6 图,第二章 基本数据结构,2. 1 数据结构基本概念,数据结构：逻辑结构、存储结构、运算,第二章 基本数据结构,1. 数据结构举例,无序表和有序表,有序表,无序表,第二章 基本数据结构,学生成绩表：,第二章 基本数据结构,第二章 基本数据结构,井字棋对弈的问题：,五叉路口的交通灯管理问题： 右行规则 道路、E的箭头表示单行道 用多少种颜色的交通灯分配路线，不考虑过度灯,第二章 基本

2、数据结构,2. 什么是数据结构, 是指相互有关联的数据元素的集合。 定义理解 数据结构数据元素前后件关系 数据元素（data element）： 是组成数据的基本单位。 前后件关系： 数据元素的任何关系都可以用前后件关系来描述 举例： E.g.1 一年四季数据结构； E.g.2 家庭成员数据结构；,第二章 基本数据结构,3. 数据结构的内涵,数据结构包含三个方面的内容： 数据的逻辑结构； 数据的存储结构; 对数据所施加的运算。,数据的逻辑结构独立于计算机，是数据本身固有的。,是逻辑结构在计算机内存中的映像必须依赖于计算机。,指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依

3、赖于存贮结构。,第二章 基本数据结构,4. 数据逻辑结构,1. 反映数据元素之间逻辑关系的数据结构 逻辑结构表示： B（D，R) 其中D:数据元素集合； R:D中各数据元素之间的前后件关系。 举例： E.g.1 一年四季数据逻辑结构； E.g.2 家庭成员数据逻辑结构； E.g.3 mxn矩阵数据逻辑结构；,第二章 基本数据结构,4. 数据逻辑结构,2. 数据逻辑结构类型 线性结构 线性结构判定条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多一个后件。 线性结构插入或删除任一结点后还是线性结构。 非线性结构 e.g. 树结构和图结构,第二章 基本数据结构,没有前件的结

4、点,4. 数据逻辑结构,E.g. 用图形表示数据结构B（D，R） Ddi |1i7d1，d2，d3，d4，d5，d6，d7 R(d1，d3)，(d1，d7)，(d2，d4)，(d3 ，d6) ，(d4 ，d5 ) ,第二章 基本数据结构,根节点,终端节点,非线性结构,4. 数据逻辑结构,第二章 基本数据结构,A,C,D,B,非线性结构,若在数据结构中，插入或删除任何节点后就不满足线性结构的两个条件，则该结构为非线性结构。,5. 数据存储结构,数据逻辑结构在计算机存储空间中的存放形式 常用的存储结构包括： 顺序存储： 链接存储： 索引存储： 散列存储： 一种逻辑结构可根据需要表示成多种存储结构,

5、第二章 基本数据结构,6. 数据结构的运算,基本运算： 插入 删除,其它运算： 查找 分类 合并 复制 修改 空数据结构,第二章 基本数据结构,2.2 线性表及其顺序存储结构,线性表及其运算 栈及其运算 队列及其运算,第二章 基本数据结构,2.2.1 线性表及其运算,第二章 基本数据结构,1. 什么是线性表,线性表： 是由n(n0)个数据元素组成的有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。 逻辑上为一个一维向量：(a1,a2,a3,an) 特征： 有且只有一个根结点a1，其无前件； 有且只有一个终结点an，其无后件； 其它结点有且只有一个

6、前件及后件。 线性表的长度： n（n=0，定义为空表）,第二章 基本数据结构,英文小写字母表(a，b，c，z)是一个长度为26的线性表 矩阵是一个比较复杂的线性表 学生情况登记表是一个复杂的线性表 由若干数据项组成的数据元素称为记录(record) 由多个记录构成的线性表又称为文件(file),1. 什么是线性表,第二章 基本数据结构,2. 线性表顺序存储结构,对应到程序设计语言中的一维数组,序号,内容,插入前,第二章 基本数据结构,占k个字节,占k个字节,占k个字节,占k个字节,占k个字节,占k个字节,占k个字节,存储地址,ADR(a1),ADR(a1)+k,ADR(a1)+2k,ADR(a

7、1)+(i-1)k,ADR(a1)+ik,ADR(a1)+(i+1)k,ADR(a1)+(n-1)k,用来泛指某种数据类型,3. 线性表C语言描述,#define maxsize maxlen struct sequenlist Elemtype amaxsize; int len; ；,表示线性表（a1，a2， .,an）,len表示线性表的实际长度,maxlen表示线性表允许的最大长度,第二章 基本数据结构,线性表顺序存储结构下的运算： (1)在线性表的指定位置处加入一个新的元素（即线性表的插入） (2)在线性表中删除指定的元素（即线性表的删除） (3)在线性表中查找某个（或某些）特定的元

8、素（即线性表的查找） (4)对线性表中的元素进行整序（即线性表的排序） (5)按要求将一个线性表分解成多个线性表（即线性表的分解） (6)按要求将多个线性表合并成一个线性表（即线性表的合并） (7)复制一个线性表（即线性表的复制） (8)逆转一个线性表（即线性表的逆转）。,第二章 基本数据结构,4.线性表基本运算插入,第二章 基本数据结构,E.g. 用如图为一个长度为8的线性表顺序存储在长度为10的存储空间中。现要求在第2个元素(18)之前插入一个新的元素87，之后在新的线性表的第9个元素之前插入一个新元素23。,87,长度为8的线性表,插入87之后,23,插入23之后,再次插入新元素则会“上

9、溢”,线性表在顺序存储下的插入算法 输入：线性表的存储空间V(1：m)；线性表的长度n（nm）；插入的位置i（i表示在第i个元素之前插入）；插入的新元素b。 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,第二章 基本数据结构,C语言算法描述： 在长度为n的线性表中第i个元素前插入新元素x(i为插入位置),M 为线性表最大长度；n_p

10、ointer存放线性表已有的记录数,int Insert_list(int i, Element x, Element s, int *n_pointer, int M) int j,n; n=*n_pointer; if (n=M) return (0); else if (in) sn=x; for (j=n;j=i;j-) sj=sj-1; si-1=x; n+; *n_pointer=n; return (1);,n为线性表实际长度,从i开始的元素后移,注意“上溢”,第二章 基本数据结构,上文回顾,算法的复杂度分析 数据结构的基本概念 线性表,时间频度、时间复杂度、空间复杂度,逻辑结构

11、: B=(D,R);线性结构;非线性结构 存储结构 运算,特征 顺序存储 表示 插入运算,5.线性表基本运算删除,第二章 基本数据结构,E.g. 用如图为一个长度为8的线性表顺序存储在长度为10的存储空间中。现要求删除线性表中的第一个元素。之后，删除线性表中的第6个元素。,长度为8的线性表,删除29之后,删除31之后,如线性表为空，则“下溢”错误。,线性表在顺序存储下的删除算法 输入：线性表的存储空间V(1：m)；线性表的长度n（nm）；删除的位置i（表示删除第i个元素）。 PROCEDURE DESL(V，m，n，i) 1. IF (n0) THEN UNDERFLOW；RETURN 2.

12、IF (i1)or(in) THEN “Not this element in the list”；RETURN 3. FOR ji TO n DO V(j-1)V(j) 4. nn1 5. RETURN,第二章 基本数据结构,int Delete_list(int i, int s , int *n_pointer) int j,n; n=*n_pointer; if (in)|(n=0) return (0); for (j=i; jtop=0; ,4. 栈的运算栈的判空与判满,栈判空 int StackEmpty(struct SQSTACK stack) if (stack.top=0

13、) return (1); return (0); ,第二章 基本数据结构,栈判满 int StackFull (struct SQSTACK* stack) if (stack-top= M) return (1); return (0); ,5. 栈运算入栈 push,int Push(struct SQSTACK *stack, int x) if (stack-top=M) return (1); stack-top+; stack-elemstack-top-1=x; return (0); ,注意栈上溢,修改栈顶指针,数据入栈,第二章 基本数据结构,6. 栈运算出栈 pop,int

14、 Pop(struct SQSTACK *stack, int *x) if (StackEmpty(*stack) return (1); *x=stack-elemstack-top-1; stack-top-; return (0); ,先判栈空,修改栈顶指针,数据出栈,第二章 基本数据结构,7. 栈运算读栈顶 top,int GetTop(struct SQSTACK stack, int *x) if (stack-top=0) return (1); *x=stack-elemstack-top-1; /stack-top-; return (0); ,不出栈！,第二章 基本数据结

15、构,/ 表示屏蔽该行。,8. 栈运算举例,E.g：表达式计算 A + B * C D / E; 步骤： 首先，设置两个栈：运算符栈和操作数栈； 运算符栈，用于在表达式处理过程中存放运算符。开始时，其中先压入一个表达式结束符“；”。 操作数栈，用于在表达式处理过程中存放操作数。 从左到右按顺序读出表达式中的运算符或操作；按照如下操作进行： 如果是操作数，则操作数压栈；读下一符号； 如果是运算符，则进一步判断。,第二章 基本数据结构,第二章 基本数据结构,若是运算符，则作进一步判断： 若读出运算符的优先级大于运算符栈栈顶运算符的优先级，则将读出的运算符压入运算符栈，并依次读下一个符号。 若读出的是

16、表达式结束符“；”，且运算符栈栈顶的运算符也是表达式结束符“；”，则表达式处理结束，最后的计算结果在操作数栈的栈顶位置。 若读出运算符的优先级不大于运算符栈栈顶运算符的优先级，则从操作数栈连续退出两个操作数，并从运算符栈退出一个运算符，然后作相应的运算（运算符为刚从运算符栈退出的 运算符，运算对象为刚从操作数栈退出的两个操作数），并将运算结果压入操作数栈。,第二章 基本数据结构,(a) 初始状态,；,(b) 读出A+B*C,；,A + B * C D / E;,A,+,B,*,C,(c) 读出-,T1=B*C,T1,；,T2,(d) 重新考虑-,T2=T1+A,第二章 基本数据结构,(f) 读

17、出; T3=D/E,A + B * C D / E;,(c) 重新考虑; T4=T2-T3,(d) 重新考虑; T4作为结果,(e) 重新考虑-,读出D/E,-,D,/,E,T3,；,T4,；,9. 递归与栈,第二章 基本数据结构,依次打印输出自然数1到n的非递归算法 PROCEDURE WRT(n) FOR k1 TO n DO OUTPUT k RETURN 依次打印输出自然数1到n的递归算法 PROCEDURE WRT(n) IF (n0) THEN WRT(n-1)； OUTPUT n RETURN,PROCEDURE WRT1(3) IF (n0) THEN WRT1(31) OUT

18、PUT n RETURN,n=3,PROCEDURE WRT1(0) IF (n0) THEN WRT1(01) OUTPUT n RETURN,PROCEDURE WRT1(2) IF (n0) THEN WRT1(21) OUTPUT n RETURN,PROCEDURE WRT1(1) IF (n0) THEN WRT1(11) OUTPUT n RETURN,3,2,3,3,2,1,1,2,3,第二章 基本数据结构,2.2.3 队列及其应用,第二章 基本数据结构,定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表 。此种结构称为先进先出（FIFO）表。

19、设队列 q = ( a1, a2, a3, , an )中，a1是允许删除的一端，称为队头（front），an是允许插入的一端为队尾（rear）。,front,rear,先进先出FIFO,1. 队列（queue）,rear指向队尾元素,front指向排头元素的前一个位置,第二章 基本数据结构,(a)线性队列,和栈一样，用顺序结构表示队列是一种简单的方法，通常用一维数组实现，其中MAX表示队列允许的最大容量，在队的两端设置两个整型变量作指针，front为头指针，rear为尾指针。,队空时， 令rear=front= 0，当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头

20、指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置,MAX=4,2.队列的存储结构,第二章 基本数据结构,假设MAX=4，rear=4时队满，此时不能插入新元素，但实际上队列可用空间没有满，这是一种假溢出现象。解决方法：将队列头尾相连形成一个环。,线性队列队满的条件： rear = MAX 线性队列队空的条件： rear = front,MAX=4,第二章 基本数据结构,队尾指针rear指向队尾元素,队头指针指向队头元素的前一个元素位置,第二章 基本数据结构,(b) 循环队列,3. 循环队列的插入与删除,front,rear,front,rear,front,rear,一个队列,加

21、入X,Y元素,取出元素,第二章 基本数据结构,4. 循环队列的空满状态,队列空,队列满,都是rear= front！,队列判空标志 s,第二章 基本数据结构,rear=front=m,5.循环队列结构的C语言描述,#define MAXSIZE 50 typedef struct mysqqueue elemtype elemMAXSIZE; int front; int rear; int s; SQQUEUE;,第二章 基本数据结构,6.循环队列的运算初始化与判空,初始化,判空,void InitQueue (SQQUEUE *q) q-front = MAXSIZE; q-rear =

22、MAXSIZE; q-s = 0; ,int QueueIsEmpty (SQQUEUE q) if (q.front=q.rear ,第二章 基本数据结构,7.循环队列运算入队,入队运算：在队列的对尾加入一个新元素。 尾指针rear加1,若rear=MAXSIZE+1,则rear=1),int AddQueue (SQQUEUE *q, elemtype e) if (q-front=q-rear ,先判满,第二章 基本数据结构,8.循环队列运算退队,退队运算：队列的排头退出一个元素，并赋给指定变量 排头指针front加1，若front=MAXSIZE+1,front=1,int DelQu

23、eue (SQQUEUE *q, elemtype *e) if (q-front=q-rear ,先判空,第二章 基本数据结构,(1)、输入输出缓冲区的结构 (2)、火车车厢重排(589147362),第二章 基本数据结构,9.队列的应用,上文回顾,线性表的删除 栈 队列,定义及特征 表示 运算：初始化、判空、判满、入栈、退栈、读栈顶,定义及特征（循环队列的优点） 表示 运算：初始化、判空、判满、入队、退队,2.3 线性链表及其 运算,单链表 循环链表 双向链表 链栈、链队列,第二章 基本数据结构,线性表顺序结构使用的缺陷,当添加和删除数据元素时，其他表数据将产生移位操作，工作量大； 当存储

24、空间满时，继续添加数据元素将产生上溢出； 当存储空间空时，继续删除数据元素将产生下溢出； 静态存储数据，在一些应用中使用不便。,第二章 基本数据结构,2.3.1 线性链表的基本概念,第二章 基本数据结构,定义：用一组地址可以不连续的存储单元（以数据元素为单位）存放线性表的数据元素。 注意：不连续存储单元可零散地分布在内存中的任何位置上。 存在的逻辑关系问题思考： 每个数据元素（称为结点）在内存中的存储位置是任意的，即逻辑上相邻未必在物理上相邻； 在此存储结构中如何表示线性表中数据元素的逻辑关系？ 必然要求在存放数据元素的结点信息中必须包含其后继元素的位置信息，用指针！,线性链表,第二章 基本数

25、据结构,结点的结构：数据域，指针域,数据域：存放数据元素自身值。 指针域：存放后继元素结点的地址。 链表：通过指针域，可将n个结点按其逻辑顺序链接在一起。,如何定义该结点的数据类型？,第二章 基本数据结构,首节点如何处理？,第一个结点（开始结点）：a1所对应的结点，无前件。 最后一个结点（尾结点）：an所对应的结点，无后件，则指针域为空，用0或null表示。 其它结点：由其前驱结点的指针域指向，自身指针域指向后继结点。 头指针：为一个链表设立一个头指针，指向整个链表中第一个结点的存储位置。,单链表,线性表（a1, , ai, , an）的链表存储结构：,Head,NULL,空表,第二章 基本数

26、据结构,头结点：为了操作方便，有时为一个链表添加一个头结点，其数据域可以不存放任何信息，但指针域指向表中第一个结点（a1结点）的指针，而头指针指向头结点。,带头结点的单链表,空表：头指针为空或头结点指针域为空。,空表,第二章 基本数据结构,E.g 线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,头指针,第二章 基本数据结构,单链表存储结构的表示与实现,struct Lnode ElemType data； struct Lnode *next； ； /Lnode:结点类型,注意：若声明 struct Lnode

27、*p，并指向一结点ai，则有： p表示指向结点ai的指针 (*p) 表示p所指向的结点（装ai信息的结点） (*p).data p-data 表示p指向结点的数据域 (*p).next p-next 表示p指向结点的指针域,生成一个新结点 p=(struct Lnode* )malloc(sizeof(struct Lnode); 系统回收p结点：free(p),/数据域,/指针域,第二章 基本数据结构,单链表特点 它是一种动态结构，即链表长度可动态增加； 不需预先分配空间，随用随申请； 指针占用额外存储空间，用于维系逻辑关系； 无法直接获取结点地址，因此不能随机存取结点信息，查找速度慢；,第

28、二章 基本数据结构,空单链表的创建:,第二章 基本数据结构,/不带头结点 void linked_List ( void ) struct Lnode *head; /头指针、工作指针 head= NULL; /置链表空 /带头结点 void linked_List ( void ) struct Lnode *head, *q; /头指针、头结点指针 q= (struct Lnode *) malloc (sizeof(struct Lnode); /申请头结点 q-next=NULL; /置表空 head= q; ,单链表的创建: (前插法),第二章 基本数据结构,从一个空表开始，重复读入

29、数据： 生成新结点 将读入数据存放到新结点的数据域中 将该新结点插入到链表的前端 直到读入结束符为止。,head,p,null,head,p,head,p,null,无头结点,带头结点,null,void createListF ( void ) char ch; struct Lnode *head, *p; /头指针、工作指针 head= NULL; /置链表空 while ( (ch = getchar( ) ) != n ) p = (struct Lnode *) malloc (sizeof(struct Lnode); p-data = ch; /建立新结点 p-next = h

30、ead; /插入到表前端 head= p; ,第二章 基本数据结构,无头结点：,该方法生成的链表的结点次序与输入顺序相反。,void createListF ( void ) char ch; struct Lnode *head, *q,*p; /q:头结点, p:新结点 q= (struct Lnode *) malloc (sizeof(struct Lnode); /申请头结点 q-next=NULL; /置表空 head= q; while ( (ch = getchar( ) ) != n ) p = (struct Lnode *) malloc (sizeof(struct L

31、node); p-data = ch; /建立新结点 p-next = q-next; /插入到表前端 q-next = p; ,第二章 基本数据结构,带头结点：,2.3.2 单链表的基本运算,第二章 基本数据结构,单链表的基本运算包括： 在线性链表中包含指定元素的结点之前插入一个新元素。 在线性链表中删除包含指定元素的结点。 将两个线性链表按要求合并成一个线性链表。 将一个线性链表按要求进行分解。 逆转线性链表。 复制线性链表。 线性链表的排序。 线性链表的查找。,第二章 基本数据结构,1、不带头结点的单链表的插入,第一种情况：在空链表中插入 第二种情况：在链表的第一个结点前插入,（插入前）

32、,head,（插入后）,x,null,（插入后）,x,head,p-next =head; head= p；,第二章 基本数据结构,第三种情况：在链表中间插入(首先找到插入位置的前一个节点q) 第四种情况：在链表的末尾插入(首先找到插入位置的前一个节点q),（插入后）,x,（插入后）,x,null,p-next = q-next; q-next= p；,第二章 基本数据结构,算法描述 int linked_list_Insert (ElemType x, int i ) /在链表第 i 个结点处插入新元素 x struct Lnode * q = head; int k = 0; while

33、( q!= NULL ,第二章 基本数据结构,/创建新结点,p-data = x; if ( head = NULL | i = 1 ) /插入空表或非空表第一个结点之前 p-next = head;/新结点成为第一个结点 head =p; else /插在表中间或末尾 p-next = q-next; q-next = p; return 1; ,第二章 基本数据结构,2、带头结点的单链表的插入,第一种情况：在空链表中插入 第二种情况：在链表的第一个结点前插入,（插入后）,x,null,（插入后）,x,p-next =q-next; q-next= p；,第二章 基本数据结构,第三种情况：在

34、链表中间插入(首先找到插入位置的前一个节点q) 第四种情况：在链表的末尾插入(首先找到插入位置的前一个节点q),（插入后）,x,（插入后）,x,null,p-next = q-next; q-next= p；,第二章 基本数据结构,算法描述 int linked_list_Insert (ElemType x, int i ) /在链表第 i 个结点处插入新元素 x struct Lnode * q = head; int k = 0; while ( q!= NULL ,第二章 基本数据结构,/创建新结点,p-data = x; p-next = q-next; q-next = p; re

35、turn 1; ,第二章 基本数据结构,3、不带头结点的单链表的删除,第一种情况：在空链表中删除 第二种情况：删除链表的第一个结点,（删除前）,无法删除 （删除后）,p=head; /找到需要删除的结点 head=head-next; free(p);,第二章 基本数据结构,第三种情况：删除链表的中间结点p (首先找到删除位置的前一个节点q) 第四种情况：删除链表的末尾结点p(首先找到删除位置的前一个节点q),p=q-next ；/找到需要删除的结点 q-next=p-next； free(p)；,第二章 基本数据结构,null,int linked_list_Delete (int i )

36、/在链表中删除第 i 个结点 struct Lnode *p, *q; /p需要删除的结点，q: 前一结点； if ( i = 1 ) /删除表中第 1 个结点 p = head; head = head-next; else int k = 0; q = head; while ( q != NULL /找第 i-1个结点,算法描述：,第二章 基本数据结构,if ( q = NULL | q-next = NULL ) /找不到第i-1个结点 printf ( “无效的删除位置!n” ); return 0; else /删除中间结点或尾结点元素 p = q-next; q-next = p

37、-next; k= p-data; free ( p); return k; /取出被删结点数据并释放q ,第二章 基本数据结构,4、带头结点的单链表的删除,第一种情况：在空链表中删除 第二种情况：删除链表的第一个结点,无法删除 （删除后）,p=q-next; /找到需要删除的结点 q-next=p-next; free(p);,第二章 基本数据结构,第三种情况：删除链表的中间结点p (首先找到删除位置的前一个节点q) 第四种情况：删除链表的末尾结点(首先找到删除位置的前一个节点q),p=q-next ；/找到需要删除的结点 q-next=p-next； free(p)；,第二章 基本数据结构

38、,null,int linked_list_Delete (int i ) /在链表中删除第 i 个结点 struct Lnode *p, *q; /p需要删除的结点，q: 前一结点； q = head; while ( q != NULL /找第 i-1个结点,算法描述：,第二章 基本数据结构,if ( q = NULL | q-next = NULL ) /找不到第i-1个结点 printf ( “无效的删除位置!n” ); return 0; else /删除结点元素 p = q-next; q-next = p-next; k= p-data; free ( p); return k;

39、 /取出被删结点数据并释放q ,第二章 基本数据结构,2.3.2 单循环链表,第二章 基本数据结构,单循环链表的定义： 在循环链表中增加了一个表头结点， 其数据域为任意或根据需要来设置， 指针域指向线性表第一个元素的结点。 循环链表的头指针指向表头结点。 循环链表中最后一个结点的指针域不空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。,第二章 基本数据结构,an-1,head,a1,a0,head,(空表),(非空表),单循环链表的特点： 若知道链表中某一结点的地址，则可访问到表中所有结点；但访问后件结点时间复杂度为O（1），而寻找前件结点的时间复杂度为O（n） 单循环链

40、表中的结点访问只能沿指针向后继结点方向顺序而行，不可逆向，即循环是单行道。 单循环链表与单链表的的操作基本一致，仅是循环控制不是最后结点的指针域（next）为空，而是是否等于头指针。,第二章 基本数据结构,单循环链表的空表声明：,void linked_CList ( void ) struct Lnode *head, *q; /头指针、头结点指针 q= (struct Lnode *) malloc (sizeof(struct Lnode); /申请头结点 q-next=q; /指向头结点 head= q; ,第二章 基本数据结构,单循环链表的元素插入、元素删除方法与带头结点的单链表的方

41、法相同。,上文回顾,单链表 单循环链表,定义及优点(与顺序存储相比) 表示 空单链表的创建 单链表的创建 单链表的基本运算：插入、删除,定义及优点(与单链表相比) 表示 空单循环链表的创建 单循环链表的基本运算,2.3.3 双向链表,第二章 基本数据结构,指向后件,prior data next,为了克服单链表的单向性缺陷，可以改进结点结构，形成双向链表。双向链表结点结构如下：,指向前件,由双向链表结点组成的链表称为双向链表。 双向链表每个结点有两个指针域，一个指向前驱结点，一个指向后继结点，并且头尾结点相链形成双向循环链表。双向链表通常采用带表头结点的循环链表形式。 双向循环链表可以从向前和

42、向后两个方向访问（遍历）表中所有结点，即双行道。,第二章 基本数据结构,p为双向链表中某结点，则有关系： p=p-prior-next = p-next-prior,非空表 空表,p-prior,p-next,第二章 基本数据结构,双向循环链表的定义,struct DLnode ElemType data; struct DLnode * prior, * next; ;,第二章 基本数据结构,双向循环链表的空表声明：,void linked_DList ( void ) struct Lnode *head, *q; /头指针、头结点指针 q= (struct DLnode *) mallo

43、c (sizeof( struct DLnode); /申请头结点 q-next=q; /指向头结点 q-prior=q; head= q; ,双向循环链表的插入 (非空表),p-prior = q; p-next = q-next; q-next = p; p-next-prior = p;,在结点 q 后插入p,第二章 基本数据结构,x,插入后,双向循环链表的插入 (空表),p-prior = q; p-next = q-next; q-next = p; p-next-prior = p;,x,在头结点 q 后插入q,第二章 基本数据结构,插入后,有兴趣的同学自行写出双向循环链表的插入算

44、法,双向循环链表的删除（删除之后为非空表）,p-next-prior = p-prior; p-prior-next = p-next;,第二章 基本数据结构,删除结点p,p-next-prior = p-prior; p-prior-next = p-next;,第二章 基本数据结构,双向循环链表的删除（删除之后为非空表）,删除结点p,删除后,有兴趣的同学自行写出双向循环链表的插入算法,顺序表与链表的比较,基于空间的比较 存储分配的方式 顺序表的存储空间是静态分配的 链表的存储空间是动态分配的 存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量 顺序表的存储密度 = 1 链表的存

45、储密度 data = x; p-next = top; top = p; ,链栈的入栈操作，相当于在单链表的第一个结点之前进行插入操作。由于是链式存储，不需要像顺序存储那样需要判断栈是否为满。,第二章 基本数据结构,p,链栈的退栈：,ElemType linked_stack_pop (struct Lnode *top) struct Lnode *p; ElemType x; if (top=NULL) /出栈前仍需判栈空 printf (stack is empty n”); return 0; else p=top; x=p-data; top=p-next; free (p);ret

46、urn(x); ,链栈的入栈操作，相当于在单链表中删除第一个结点。由于是链式存储，退栈前需要判断单链表是否为空。,第二章 基本数据结构,2、带链的队列（链队列）,第二章 基本数据结构,与栈类似，队列也是线性表，也可以采用链式存储结构。 链队列常常采用带头结点的单链表。 在链队列里，将队头指针指向单链表的头结点，而将队尾指针指向单链表的最后一个结点。,头结点,队头,队尾,链栈的队列语言描述如下： struct Qnode ElemType data; struct Qnode *next; ; 队头指针为front，队尾指针为rear,其类型为Qnode *，当front=rear，表示一个空链

47、队列。,链队列的定义：,第二章 基本数据结构,链队列的初始化：,void linked_queue_init( ) struct Qnode *q, *front, *rear; q= (struct Qnode *) malloc (sizeof(struct Qnode); front=rear=q; ,第二章 基本数据结构,链队列的入队：,链队列的入队操作，相当于在单链表的最后一个元素之后加入新元素。由于是链式存储，不需要像顺序存储那样需要判断队列是否为满。,第二章 基本数据结构,1、空队,2、x入队,3、y入队,链队列的入队：,第二章 基本数据结构,void linked_queue_

48、Addqueue(ElemType x) struct Qnode *p; p= (struct Qnode *) malloc (sizeof(struct Qnode); p-data=x; p-next=NULL; rear-next=p; /原先队尾结点的指针指向新结点 rear=p; /队尾指针指向新结点 ,链队列的退队：,第二章 基本数据结构,4、x退队,若队列为空，则发出下溢异常 找到队头元素所在的结点 将队头元素所在的结点摘链 如果被删的队头元素同时也是队尾元素，则修改队尾指针。,5、y退队,链队列的退队：,第二章 基本数据结构,void linked_queue_Dequeu

49、e() struct Qnode *p; if (front = rear) printf (Error! n); else p = front-next; /暂存队头元素 front-next = p-next; /队头元素所在结点摘链 if (p-next = NULL) rear = front; free(p); ,2.3.5 多项式的表示与运算,第二章 基本数据结构,一元多项式的线性表表示,可用线性表P表示：,n 阶多项式 Pn(x) 有 n+1 项。 系数 an, an-1, ,a2, a1,a0, 指数 n, n-1,2, 1, 0。按降幂排列,第二章 基本数据结构,一般n次多项

50、式可以写成：,因此可以用一个长度为m，且每个元素包含两个数据项的线性表来表示此类多项式。 如下式：,其存储结构可以用单链表。而对于稀疏项多项式可以节省空间，否则，浪费空间至成倍。,第二章 基本数据结构,但对S(x)这样的多项式浪费空间：,优点是： 多项式的项数可以动态地增长，不存在存储溢出问题，疏项多项式可以节省空间。 插入、删除方便，不移动元素。,exp coef next,struct Lnode int exp; float coef; struct Lnode *next; ;,第二章 基本数据结构,多项式链表中，每一非零项结点的C定义如下:,以单链循环链表为例，空多项式链表的声明：,void linked_Poly ( void ) struct Lnode