计算机软件及应用数据结构吴伟民编著PPT课件

1、第二章 线性表教学目的：（1）了解线性表的逻辑结构特性，以及线性表的两种存储实现方式；（2）熟练掌握顺序表的定义与实现，包括查找、插入、删除算法的实现；（3）熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。教学的重点和难点：链表。 第1页/共51页 2.1 线性表的定义及运算 1.线性表的定义： 是由n(n=0)个数据元素（结点）a1,a2,a3, an组成的有限序列。 其中： n为数据元素的个数，也称为表的长度。 当n=0 时，称为空表。 非空的线性表(n0) 记作： （ a1,a2,a3, an）第2页/共51页 2.线性表的逻辑特征： （1）有且仅有一

2、个开始结点a1(无直接前趋）； （2）有且仅有一个终端结点an(无直接后继）； （3）其余的结点ai 都有且仅有一个直接前趋ai-1和一个直接后继ai+1。)12(ni（4） ai是属于某个数据对象的元素，它可以是一个数字、一个字母或一个记录。第3页/共51页 3.线性表的特性 （1）线性表中的所有数据元素的数据类型是一致的。 （2）数据元素 在线性表中的位置只取决于它的序号。 （3）结点间的逻辑关系是线性的。 a1 a2 an 图2-1 线性表逻辑结构示意图 线性表的形式化定义为：线性表的形式化定义为： linear_list=(D,R)其中其中 D=ai 1in,n0,aielemtype

3、 R= 1in-1第4页/共51页 例1、26个英文字母组成的字母表 （A，B，C、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188）第5页/共51页例例3、学生健康情况登记表如下：、学生健康情况登记表如下：姓 名学 号性 别年龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱 . . .抽象数据类型的定义为：P19第6页/共51页 4. 线性表的运算 数据的运算是定义在逻辑结构上的，而具体的实现则在存储结构上进行。 （1）存取 （

4、2）插入 （3）删除 （4）查找 （5）合并 （6）分解 （7）排序 （8）求线性表的长度 基本运算第7页/共51页 2.2 线性表的顺序存储结构（顺序表） 1.顺序表的定义： 用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。 即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。第8页/共51页2.顺序表中数据元素的存储地址若一个数据元素占L个存储单元，则其存储方式参见下图。a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1Lb=LOC(a1)b + +

5、 L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L Lb +(max-1)+(max-1)L L第9页/共51页 从图中可以看出, LOC（a i+1）=LOC(a i)+l 一般地,有 第i个数据元素的存储位置为： LOC（a i）=LOC(a 1)+(i-1)*l LOC(a 1)称为基地址（第一个数据元素的存储位置）。 显然，数据元素在顺序表中位置取决于数据元素在线性表中的位置。 顺序表的特点 是：逻辑位置相邻，其物理位置也相邻。第10页/共51页一个一维数组，下标的范围是到，每个数组元素用相邻的一个一维数组，下标的范围是到，每个数组元素用相邻的个个字节字节存储。存

6、储器按字节编址，设存储数组元素存储。存储器按字节编址，设存储数组元素 的第一个字节的地址是的第一个字节的地址是，则，则 的第一个字节的地址是的第一个字节的地址是 113例1因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113解：解：地址计算通式为：地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）第11页/共51页 3.顺序表的描述： 由于由于C C语言中的一维数组也是采用顺序存储语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之又因为除了用数组来存储线性表的元素之

7、外，顺序表还应该用一个变量来表示线性外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定表的长度属性，所以我们用结构类型来定义顺序表类型。义顺序表类型。 # define ListSize 100 typedef int ElemType; typedef struc ElemType dataListSize; int length; Sqlist;第12页/共51页4.顺序表的几种基本运算 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。 注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.

8、datai-1。 以下主要讨论线性表的插入和删除两种运算。 1、插入 线性表的插入运算是指在表的第i(1in+1)个位置上，插入一个新结点x，第13页/共51页使长度为n的线性表 (a1，a i-1，ai，an) 变成长度为n+1的线性表 (a1，a i-1，x，ai，an) 插入算法的思想：1、将ai,ai+1,.,an依次后移一个位置，使第i位置留空2、将新元素x放在空出的位置上。3、线性表长度加1。演示第14页/共51页内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+

9、1an-1x第15页/共51页Void InsertList(Sqlist*L，ElemType x，int i) int j; if(iL-length+1) printf(“Position error”); return ERROR; if(L-length=ListSize) printf(“overflow”); exit(overflow); for(j=L-length-1;j=i-1;j-) L-dataj+1=L-dataj; L-datai-1=x; L-length+; 第16页/共51页插入算法分析：上述算法for循环语句的执行次数为n-i+1;若i=1,需移动全部n个

10、结点（最坏：O(n)）若i=n+1（在表尾插入）,无需用移动结点，直接插入即可。（最好O(1)）移动结点的平均次数：)1(11inPEniiI第17页/共51页按等概率考虑： 可能的插入位置为i=1,2,n,n+1共n+1个，则pi=1/(n+1) 所以1111) 1(11) 1(niniiIinninPE2)1(2)1)1()1111nnnnnn（顺序表插入算法平均约需移动一半结点。第18页/共51页 2、删除 线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表： (a1，a i-1，ai，a i+1，an) 变成长度为n-1的线性表 (a1，a i-1，a i+1，an)

11、删除算法的思想：1、将ai+1,.,an依次前移一个位置2、线性表长度减1。演示第19页/共51页内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2第20页/共51页 Void deleteList(Sqlist*L，int i) int j; if(iL-length) printf(“Position error”); return ERROR; for( j=i;jlength-1;j+) L-data j-1=L-data j; L-length-; 第21

12、页/共51页删除算法分析： 上述算法for循环语句的执行次数为n-i; 若i=1,最坏：O(n) 若i=n,无需用移动结点，直接删除即可。（最好O(1)） 移动结点的平均次数：)(1inPEniid第22页/共51页按等概率考虑： 可能的删除位置为i=1,2,n共n个，则pi=1/n 所以顺序表插入算法平均约需移动一半结点。小结：顺序表插入、删除算法平均约需移动一半结点，当n很大时，算法的效率较低。niniiIinninPE11)(1)(212)()11nnnnnn（第23页/共51页顺序表存储空间的动态分配 若将前面线性表的顺序存储结构类型中的数组形式改为指针形式，则得到动态分配形式如下：

13、typedef int ElemType; typedef struct ElemType *elem; int length; int listsize; Sqlist;第24页/共51页顺序存储结构的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充第25页/共51页 2.3 线性表的链式存储结构存储方式 用一组任意的存储单元存储线性表的数据元素 利用指针实现用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点:数据ai的

14、链式存储映象. 数据域：元素本身信息 指针域：指示直接后继的存储位置数据域 指针域结点链式存储结构:n个结点链结成的一个链表第26页/共51页 单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即null（图示中也可用表示)。一、线性链表结点中只含一个指针域的链表叫，也叫单链表例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)的单链表示意图如下第27页/共51页ZHAOQIANSUNLIZHOUWUZHENGWANGH43131NULL3771925数

15、据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针第28页/共51页listnode *h,*p;datanextp结点（*p）(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).nextp-next表示p指向结点的指针域生成一个listnode型新结点：p=(listnode *)malloc(sizeof(listnode);系统回收p结点：free(p)Typedef char Elemtype;Typedef struct node Elemtype data; struct node

16、*next;listnode;用C语言描述的单链表如下：第29页/共51页头结点：在单链表第一个结点前附设一 个结点叫头结点指针域为空表示线性表为空ha1a2头结点an .h空表 不带头结点的单链 表 a1 head a2 an 第30页/共51页 单链表上的查找运算(1) 按序号查找get(L,i)在单链表L中查找第i个位置上的元素，若找到，则返回它的地址，否则返回NULL。算法思想如下： 从头结点开始顺链扫描，用指针p指向当前扫描到的结点，用j作统计已扫描结点数的计数器，当p扫描下一个结点时，j自动加1。 P的初值指向头结点，j的初值为0。 当j=i时，指针p所指的结点就是第i个结点。第3

17、1页/共51页listnode *get(listnode *L,int i) int j; listnode *p; j=1; p=L-next; while(jnext; return p; 算法的时间复杂度都为(n)。 第32页/共51页(2) 按值查找Locate(L,x)在单链表L中，查找值为x的结点，若找到，返回它的地址，否则返回NULL。算法思想如下： 从开始结点出发，顺链逐个结点的值和给定值key作比较。listnode *Locate(listnode *head,elemtype x) listnode *p; p=head-next; while(p!=NULL)&(p-

18、data!=x) p=p-next; return p; 算法的时间复杂度都为算法的时间复杂度都为(n)。 第33页/共51页单链表上的插入运算 若将x插入a和b 之间，插入结点的指针变化如图所示。 算法思想： (1)先求出第i-1个结点 (2)然后在第i-1个结点之后插入结点x。pabxss-next=p-next;p-next=s;第34页/共51页 INSERT（ listnode *L, elemtype x, int i) listnode *p,*s; int j; p=L;j=0; while(p & jnext;+j; if (p=null) printf(“找不到插入点n“）

19、 else s=(listnode*) malloc(sizeof(listnode); s-data=x;s-next=p-next; p-next=s; /*end*/第35页/共51页 单链表上的删除运算若将x删除，删除结点的指针变化所示。 p q a1 x a2 图 删除结点的指针修改 思想：先找到被删结点（第i个）的前趋结点，即第i-1个结点*p,然后删除*p的后继。第36页/共51页DELETE(listnode *L,int i) listnode *p,*q; int j; p=L;j=0; while(p-next & jnext;+j; if (P-next!=null)

20、q=p-next;p-next=q-next; free(q); else printf(“errorn”) /*end*/思考：如何实现删除线性表head中数据域为a的结点。第37页/共51页建立单链表-头插法建表：思想：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。 h头结点an 0h头结点an-10an a2.h头结点an-10an ha1a2头结点an .0h头结点0第38页/共51页Listnode * creatlist(int n) listnode *p,*L; int i; L=(list

21、node *)malloc(sizeof(listnode); L-next=NULL; for(i=n;i0;i-) p=(listnode*)malloc(sizeof(listnode); scanf(&p-data); p-next=L-next; L-next=p; return L; 第39页/共51页单链表特点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢第40页/共51页二、循环链表(circular linked list) 循环链表是表中最后一个结点的指针指向头结点，使链表构成环状 特点：从表中任一结点出发均

22、可找到表中其他结点，提高查找效率 操作与单链表基本一致,循环条件不同 单链表p或p-next=NULL 循环链表p或p-next=Hhh空表第41页/共51页在有些情况下，在循环链表中设立尾指针而不设头指针，可使某些操作简化。例如将两个线性链表合并成一个表时，只需将一个表的表尾与另一个表的表头相接。第42页/共51页例:在链表上实现将两个线性表(a1，a2，a3，an)和(b1，b2，b3，bn)链接成一个线性表的运算。 linklist connect(linklist *heada,linklist *headb) linklist p=heada-next; heada-next=(he

23、adb-next)-next free(headb-next); headb-next=p; return(headb); 第43页/共51页三、双向链表（double linked list）单链表具有单向性的缺点 结点定义typedef struct node elemtype data; struct node *prior,*next;JD;priordatanextL空双向循环链表：非空双向循环链表：LABbcapp-prior-next= p= p-next-proir;第44页/共51页bcaPvoid del_dulist(listnode *p)p-prior-next=p-

24、next; p-next-prior=p-prior; free(p);v删除l 算法描述p-prior-next=p-next;p-next-prior=p-prior;第45页/共51页void ins_dulist(listnode* p,int x)listnode *s; s=(listnode*)malloc(sizeof(listnode); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;l 算法描述xSbaPv插入第46页/共51页2.4 线性表的应用举例 一元多项式的表示及相加 一元多项式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用线性表P表示200001000231)(xxxS但对S(x)这样的多项式浪费空间一般emmnxPxPxPxPee2121)(其中为非零系数）（iPemee210用数据域含两个数据项的线