1、数数 据据 结结 构构线性结构线性结构 数据结构 逻辑结构和物理结构 四种逻辑结构 集合、线性结构、树形结构、图状结构 什么是线性结构？存在唯一的被称作“第一个”的数据元素 存在唯一的被称作“最后一个”的数据元素 除第一个之外，每个数据元素只有一个前驱；除最后一个之外，每个元素只有一个后继。本章目标：本章目标：l理解线性表的逻辑结构及定义l掌握线性表的顺序存储表示和操作实现l掌握线性表的链式存储表示和操作实现l线性表结构的应用举例第二章第二章 线性表线性表 线性表(Linear List)：n个数据元素组成的有限序列，记做(a1,a2,an)。数据元素的个数n定义为表的长度。当n=0时称为空表
2、。数据元素ai(1in)在不同的情况下有不同的含义。例：26个英文字母组成的字母表（A，B，C、Z）是一个线性表：长度为26 每个数据元素代表一个英文字母2.1 线性表的定义线性表的定义例：一副扑克的点数也可以看成一个线性表：（2，3，4，J，Q，K，A）例：某校从1978年到1983年计算机拥有量的变化情况用线性表表示为：（6，17，28，50，92，188）线性表举例线性表举例线性表举例线性表举例 例：学生健康情况登记表如下 数据元素（记录）、数据项（表项）、线性表（文件）姓 名学 号性 别年龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平790633
3、 男 21 健康张立立790634 男 17 神经衰弱.请大家列举线性表ADT定义的三要素：数据对象D=ai|i=1,2,n,n0数据关系R=|aiD,i=2,n基本操作创建空表、销毁表、清空、返回表长；查询、修改、插入、删除表中元素；返回前驱、返回后继P19在这些基本操作上，可以进行更复杂的操作。抽象数据类型线性表的定义抽象数据类型线性表的定义 例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。void union(List&La，List Lb)La-len=ListLength(La);Lb-len=ListLength(Lb);for(i=1;i=L
4、b-len;i+)GetElem(Lb，i，e);if(!LocateElem(La，e，equal)ListInsert(La，+La-len，e)利用基本操作进行线性表合并利用基本操作进行线性表合并 例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。分析：LA=3,5,8,11 LB=2,6,8,9,11,15,20；那么 LC=？算法归纳 当a b时，c=a 当ab时，c=b 利用基本操作进行线性表有序合并利用基本操作进行线性表有序合并void MergeList(list La，list
5、Lb，list&Lc)InitList(Lc);i=j=1;k=0;La-len=ListLength(La);Lb-len=ListLength(Lb);while(i=La-len)&(j=Lb-len)GetElem(La，i，ai);GetElem(Lb，j，bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;else ListInsert(Lc,+k,bj);+j;while(i=La-len)GetElem(La，i+，ai);ListInsert(Lc，+k，ai);while(jnext指向线性表中的第i+1个元素（结点ai+1）.p-data=ai,那么
6、p-next-data=ai+1 单链表中，查找第i个元素也必须从头指针出发，进行依次查找。While循环体中的语句执行次数与被查找元素的位置有关，1i n时频度是i-1,否则为n。算法时间复杂度为O(n)。GetElem()在单链表中的实现在单链表中的实现 在链表中插入一个元素的示意图如下：链表中插入的实现链表中插入的实现xsbapabp插入步骤（即核心语句）：插入步骤（即核心语句）：Step 1：s-next=p-next;Step 2：p-next=s;p-nexts-next元素x结点应预先生成：s=(LinkList)malloc(sizeof(LNode);s-data=x;s-n
7、ext=p-next相关函数介绍相关函数介绍sizeof(x)计算变量x的长度；malloc(m)开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)释放指针p所指变量的存储空间，即彻底删除一个变量。在单链表中实现插入在单链表中实现插入 时间复杂度同GetElem()查找特定结点一样，为O(n)。链表中删除的实现链表中删除的实现 在链表中删除元素b的示意图如下：cabp删除步骤（即核心语句）：删除步骤（即核心语句）：q=p-next;q=p-next;/保存b的指针，靠它才能指向cp-next=q-next;p-next=q-next;/a、c两结点相连free(q)free(q)
8、；/删除b结点，彻底释放p-next(p-next)-next 时间复杂度为O(n)在单链表中实现删除在单链表中实现删除/找到第i-1个结点动态链表和静态链表动态链表和静态链表 链表和顺序存储结构不同，是一种动态结构：每个链表占用的空间不需预先分配划定，而是根据需求即时生成。在没有指针的程序设计语言中，我们使用结构体数组来模拟链表。循环链表是一种头尾相接的环形链表。将链表中最后一个结点的指针域指向头结点，就得到了单循环链表。循环链表中也可设置一个头结点。思考：空表应该如何表示？循环链表循环链表 a1 an .headhead单循环链表的操作单循环链表的操作 循环链表的操作和单链表一致，差别仅在
9、于算法中的循环条件：单链表中:while(p&jnext&ji-1)循环链表中：while(p=L&jnext=L)&jnext-next和rear，显然，查找时间都是O(1)。a1 an .rear 单链表和循环链表中都只有一个指示直接后继的指针，因此只能从前向后进行查找。思考：如果我们需要查找某个结点n的前驱，怎么办？我们只能从表头指针出发，依次查找，直到当前结点的后继是结点n为止。在单链表中，查找后继和前驱的时间复杂度分别是？查找后继O(1)查找前驱O(n)单指针域链表的缺陷单指针域链表的缺陷双向链表双向链表 为了克服单链表这种单向性的缺点，我们可以设计一种双向链表，每个结点含有两个指针
10、域，一个指向直接后继，一个指向直接前驱。双向链表的定义双向链表的定义 双向链表在C语言中描述如下：若d为指向某一个结点的指针，显然有双向链表的操作双向链表的操作 双向链表中，ListLength,GetElem和LocateElem等涉及向后移动的操作均和单链表相同。但在插入和删除操作时就需要修改两个方向的指针。双向链表的插入双向链表的插入双向链表的删除双向链表的删除线性表上的基本操作线性表上的基本操作 P37页中给出了线性链表的基本操作，这些都是需要程序员实现，并提供给用户使用的。上机练习上机练习 请同学们借鉴本章的伪代码算法，动态构造一个带头结点的线性表。每个链表的元素个数，和每个结点的值
11、均由用户输入。将构造线性表的函数独立出来。另外实现一个函数，用户输入序号，程序能够根据序号输出对应结点的元素值。Exercises Under the guidance of pseudo-code algorithms in this chapter,please write a program to create an Linear List with head node.Users should input the number of nodes and the data value of each node.Use a function to initiate the linear list.Write another function to get and show the data value of the element specified by user.(It is for Feili,others can ignore this slide.)
