数据结构：第2章线性表D

1、1 日日 一一 二二 三三 四四 五五 六六 1919 20 21 20 21 22 23 2422 23 24 25 25 26 27 28 29 30 26 27 28 29 30 1 21 2 3 4 5 6 73 4 5 6 7 8 8 9 9其中：红色为休假其中：红色为休假 调课：调课：9.199.19上周四的课上周四的课 9.259.25上周五的课上周五的课 9.269.26上周三的课上周三的课 10.910.9上周四的课上周四的课 9 9月月2727日晚日晚 上机（南一楼上机（南一楼2 2楼东头）楼东头）中秋中秋国庆国庆调课调课2下周二交第下周二交第2章作业（章作业（ 2.8 2

2、.10 2.21 2.22 2.34 2.35）第第1次上机次上机 第第4周一晚（周一晚（18:3021:30）请各班负责人到机房办理机时卡；请各班负责人到机房办理机时卡；上机内容：上机内容：线性表的插入与删除线性表的插入与删除试用试用C语言编写一个语言编写一个算法，将一循算法，将一循环单链表就地逆置。（带或不带头结点均可）环单链表就地逆置。（带或不带头结点均可）运用链表知识自编一个运用链表知识自编一个实用实用小小软件，并撰写较为规范的文档。软件，并撰写较为规范的文档。34链表三例链表三例例例1 1：试用试用C C或类或类C C语言编写一个高效算法，将一循语言编写一个高效算法，将一循环单链表就

3、地逆置。环单链表就地逆置。其关键语句如下：其关键语句如下：p= head;p= head; q q=NULL; =NULL; head=NULLhead=NULL; ; /不宜设头结点不宜设头结点while(while(p p) ) / q q只是临时变量只是临时变量 q q = = p p-next;-next; p p-next =-next = head head; ; head = p;head = p; p p = = q q; ; 例例2 2：在双向链表中如何实现插入和删除运算？在双向链表中如何实现插入和删除运算？prior data nexttypedef struct DuLN

4、ode ElemType data; /数据域数据域 struct DuLNode *prior; /前驱指针域前驱指针域 struct DuLNode *next; /后继指针域后继指针域 DuLNode , *DuLinkList ; 双向链表类型的定义如下：双向链表类型的定义如下：双向链表的插入和删除操作是怎样的？双向链表的插入和删除操作是怎样的？自学或等待后续课程（二叉树操作）自学或等待后续课程（二叉树操作）讨论：讨论： 若某种高级语言没有指针类型，能否实若某种高级语言没有指针类型，能否实现链式存储和运算？如何实现？现链式存储和运算？如何实现？具体实现方法：具体实现方法：定义一个结构型

5、数组（每个元定义一个结构型数组（每个元素都含有数据域和指示域），就可以完全描述素都含有数据域和指示域），就可以完全描述链表，指示域就相当于动态链表中的指针。链表，指示域就相当于动态链表中的指针。指示域也常称为指示域也常称为“游标游标”问：静态链表的操作与动态链表有何不同？问：静态链表的操作与动态链表有何不同？动态链表样式：动态链表样式：静态链表样式：静态链表样式：指针指针指针指针指针指针指示指示指示指示指示指示指示指示指示指示数组中每个元素数组中每个元素都至少有两个分都至少有两个分量，属于量，属于结构型结构型数组数组。常用于常用于无指针类无指针类型的型的高级语言中。高级语言中。例例 3：一：一

6、线性表线性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )，用静态链表如何表示？，用静态链表如何表示？教材教材P32例题例题 data356042cur说明说明1 1：假设假设S S为为SLinkListSLinkList型变量，则型变量，则SMAXSIZESMAXSIZE 为一个静态链表；为一个静态链表；S0.curS0.cur则表示第则表示第1 1个结点在数组中的个结点在数组中的位置。位置。说明说明2 2：如果数组的第如果数组的第i i个分量表示链表个分量表示链表的第的第k k个结点，则：个结点，则：Si.dataSi.data表示第表示第k k个结点的数据；

7、个结点的数据；Si.curSi.cur 表示第表示第k+1k+1个结点个结点( (即即k k的直接的直接后继后继) )的位置。的位置。i说明说明3 3：静态链表的插入与删除操作与普通链表一样，不需要移静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。动元素，只需修改指示器就可以了。例如：在线性表例如：在线性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )的的QIAN, SUN之间之间LIU，可以这样实现：，可以这样实现：Step2:Step2:将将QIANQIAN的游标换为新元素的游标换为新元素LIULIU的的下标：下标：Step1:

8、Step1:将将QIANQIAN的游标值存入的游标值存入LIULIU的游的游标中：标中：data240653curi12小结：小结： 顺序存储和链式存储的区别和优缺点？顺序存储和链式存储的区别和优缺点？顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点

9、值，另一部分存放表示结点间关系的指针。链式存储的一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。空间利用率低。顺序表顺序表适宜于做适宜于做查找查找这样的静态操作；这样的静态操作；链表链表宜于做宜于做插入、删除插入、删除这样的动态操作。这样的动态操作。若若线性表的长度变化不大线性表的长度变化不大，且其主要操作是查找，则采用顺序表；，且其主要操作是查找，则采用顺序表；若若线性表的长度变化较大线性表的长度变化较大，且其主要操作是插入、删除操作，则采，

10、且其主要操作是插入、删除操作，则采用链表。用链表。循环链表的特点：循环链表的特点：双向链表的特点：双向链表的特点：可方便可方便静态链表的特点：静态链表的特点：不用指针也能实现链式存储和运算不用指针也能实现链式存储和运算几种特殊链表的特点：几种特殊链表的特点：14习题集习题集2.8 2.10 2.21 2.22 2.34 2.35教案下载请到教案下载请到: :或本科教学网或本科教学网 http:/ : 站内站内“在线答疑在线答疑”区区算法书籍哪种好算法书籍哪种好算法导论（第二版）算法导论（第二版）被被程序员程序员等评为等评为0606年最受读者喜爱的十大年最受读者喜爱的十大ITIT图书之一图书之一

11、指针的物理意义指针的物理意义&和和*的区别的区别循环单链表高效逆置的算法循环单链表高效逆置的算法讨论讨论1 1：什么是指针？指针的作用？什么是指针？指针的作用？ 指针指针即变量的内存地址。指针主要功能有二：即变量的内存地址。指针主要功能有二：提供了一种快速访问数组单元的途径；提供了一种快速访问数组单元的途径；使使C C语言函数可以修改其调用的参数。语言函数可以修改其调用的参数。 & &-指针操作符（单目），返回操作数地址；指针操作符（单目），返回操作数地址； *-运算符（单目），是对运算符（单目），是对&的补充，返回位于这个的补充，返回位于这个地址内的变量之值。

12、地址内的变量之值。例：例： q=*m意即意即“q取地址取地址m中的值中的值”。如果数值。如果数值100存存储在内存地址储在内存地址2000中，而这一地址又存在中，而这一地址又存在m中，则中，则q=(2000)=100而而 q=&m q=&m 则意味着则意味着 q=2000q=2000& & 类似于类似于“直接寻址直接寻址”，* * 类似于类似于“间接寻址间接寻址”讨论讨论2 2：与指针有关的符号与指针有关的符号& &和和* *之间有何区别？之间有何区别？P43P43程序中，程序中，switch(switch(* *cmp(a,b) cmp(a,b) 的的cmp(a,bcmp(a,b) )一定是一定是个特殊变量，它的值是一个内存地址，而个特殊变量，它的值是一个内存