第二章线性表

《第二章线性表》由会员分享，可在线阅读，更多相关《第二章线性表（80页珍藏版）》请在装配图网上搜索。

1、第二章第二章 线性表线性表n学习要点 n了解线性表的逻辑结构是数据元素了解线性表的逻辑结构是数据元素之间存在着线性关系。之间存在着线性关系。n熟练掌握线性表的两种存储结构，熟练掌握线性表的两种存储结构，即顺序存储结构和链式存储结构。即顺序存储结构和链式存储结构。n熟练掌握线性表的两种存储结构的熟练掌握线性表的两种存储结构的基本算法基本算法:查找、插入、删除等。查找、插入、删除等。线性表线性表是一种最简单的线性结构线性结构线性结构的线性结构的基本特征基本特征为为:1存在唯一的一个存在唯一的一个“第一元素第一元素”；2存在唯一的一个存在唯一的一个“最后元素最后元素”；3除最后元素在外，均有除最后元

2、素在外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。在数据元素的在数据元素的非空有限集非空有限集中中2.1 线性表的类型定义线性表的类型定义2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 一元多项式的表示及相加一元多项式的表示及相加2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.1 线性表的类型定义线性表的类型定义n线性表是线性表是n 个类型相同数据元个类型相同数据元素的有限序列素的有限序列例如例如英文字母表英文字母表学校计算机数量学校计算机数量学生健康情况登记表学生健康情况登记表例例1.26个英文字母组成的字母表个英文字母

3、组成的字母表 （A，B，C，Z）例例2.某校从某校从1985年到年到1990年各种型号的计算机拥年各种型号的计算机拥有量的变化情况。有量的变化情况。（6，17，28，50，92，188）例例3.学生健康情况登记表如下：学生健康情况登记表如下：.神经衰弱 17 男790634张立立 健康 21 男790633刘建平 一般 20 女790632陈 红 健康 18 男790631王小林健康情况年龄性 别学 号姓 名若将线性表记为若将线性表记为 （a1,.,ai-1,ai,ai+1,an）1)不同线性表中数据元素的类型可以不同线性表中数据元素的类型可以是各种各样的，但同一线性表中的元素是各种各样的，但

4、同一线性表中的元素必须是必须是同一类型同一类型的；的；2)在表中在表中 ai-1 领先于领先于ai，ai 领先于领先于ai+1，称称ai-1是是ai的的直接前驱直接前驱，ai+1是是ai的的直接直接后继后继；3)在线性表中，除第一个元素和最后在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个元素之外，其他元素都有且仅有一一个直接前驱个直接前驱，有且仅有，有且仅有一个直接后继一个直接后继，这是所有这是所有线性结构线性结构的共同特征。线性表的共同特征。线性表是一种线性数据结构；是一种线性数据结构；4)线性表中元素的个数线性表中元素的个数n 称为称为线性表的线性表的长度长度，n=0

5、时称空表；时称空表；5)ai是线性表的第是线性表的第i 个元素，称个元素，称i为数据为数据元素元素ai 的的位序位序，每一个元素在线性表中，每一个元素在线性表中的位置，仅取决于它的的位置，仅取决于它的位序位序；抽象数据类型线性表线性表的定义如下：ADT List 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,aiD,i=2,.,n 基本操作：基本操作：结构操作结构操作 引用型操作引用型操作 加工型操作加工型操作 ADT List 结构操作结构操作 InitList(&L)操作结果：操作结果：构造一个空的线性表L。初始化操作初始化操

6、作结构销毁操作结构销毁操作 DestroyList(&L)初始条件：初始条件：线性表 L 已存在。操作结果：操作结果：销毁线性表 L。ListEmpty(L)ListLength(L)GetElem(L,i,&e)引用型操作引用型操作:LocateElem(L,e,compare()ListEmpty(L)初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。（线性表判空）ListLength(L)初始条件：操作结果：线性表L已存在。返回L中元素个数。（求线性表的长度）GetElem(L,i,&e)初始条件：操作结果：线性表L已存在，且 1iLengthList(L)

7、。用e 返回L中第 i 个元素的值。（求线性表中某个数据元素）LocateElem(L,e,compare()初始条件：操作结果：线性表L已存在，e为给定值，compare()是元素判定函数。返回L中第中第1个个与e满足满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）加工型操作加工型操作 ListInsert(&L,i,e)ListDelete(&L,i,&e)ListInsert(&L,i,e)初始条件：操作结果：线性表L已存在，且 1iLengthList(L)+1。在L的第i个元素之前之前插入新的元素e，L的长度增1。（插入数据元素）ListDele

8、te(&L,i,&e)初始条件：操作结果：线性表L已存在且非空，1iLengthList(L)。删除L的第i个元素，并用e返回其值，L的长度减1。（删除数据元素）利用上述定义的线性表线性表 可以实现其它更复杂的操作例例 2-2例例 2-1例 2-1 假设:有两个集合A和B分别用两个线性表 LA 和 LB 表示(线性表中的数据元素即为集合中的成员)。现要求一个新的集合AAB。例 2-2 已知线性表 LA 和 LB 中的数据元素按非递减有序排列。现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按非递减有序排列。如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？存储线性表

9、，至少要保存两类信息：存储线性表，至少要保存两类信息：1 1）线性表中的数据元素；）线性表中的数据元素；2 2）线性表中数据元素的顺序关系；）线性表中数据元素的顺序关系；2.2 线性表的顺序表示和实现线性表的顺序表示和实现 用一组地址连续地址连续的存储单元 依次存放依次存放线性表中的数据元素 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址称作线性表的基地址基地址以“存储位置相邻存储位置相邻”表示有序对 即：LOC(ai)=LOC(ai-1)+l 一个数据元素所占存储量一个数据元素所占存储量所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第

10、一个数据元素的存储位置 LOC(ai)=LOC(a1)+(i-1)l 基地址基地址顺序映像的顺序映像的 C 语言描述语言描述typedef struct SqList;#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量ElemType*elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量 /(以sizeof(ElemType)为单位)#include stdlib.h/malloc头文件头文件/函数结果状态代码函数结果状态代码#defin

11、e OK1#define ERROR0#define OVERFLOW-2typedef int Status;/定义定义ElemType的类型的类型typedef int ElemType;C语言数组的下标从语言数组的下标从0开始，则表中第开始，则表中第i个数个数据元素是据元素是L.elemi-1a1a2aianL.elemL.lengthL.listsize设设L是是SqList 类型的结构变量，则类型的结构变量，则L在内存中的状态如图所示：在内存中的状态如图所示：线性表的基本操作在顺序表中的实线性表的基本操作在顺序表中的实现现InitList_Sq(&L)/结构初始化结构初始化ListI

12、nsert _Sq(&L,i,e)/插入元素插入元素ListDelete _Sq(&L,i)/删除元素删除元素v malloc(int size)功能：在系统内存中分配功能：在系统内存中分配size个的存储单元，并返个的存储单元，并返回该空间的基址。回该空间的基址。使用方法：使用方法：.int m=100;float*p;p=(float*)malloc(m*sizeof(float);0 1 2 99p&常用函数说明常用函数说明v free(p)功能：将指针变量功能：将指针变量p所指示的存储空间回收到系统所指示的存储空间回收到系统内存空间中去。内存空间中去。使用方法：使用方法：int m=1

13、00;float*p;p=(float*)malloc(m*sizeof(float);/一旦一旦p所指示的内存空间不再使用所指示的内存空间不再使用 /调用调用free()将其回收将其回收 free(p);调用调用free(p)0 1 2 99p&常用函数说明常用函数说明v函数函数realloc()格格 式：式：void*realloc(void*p,unsigned size)功功 能：将能：将p所指向的已分配内存区域的大小改为所指向的已分配内存区域的大小改为size。size可以比原来分配的空间大或小。可以比原来分配的空间大或小。&常用函数说明常用函数说明Status InitList_S

14、q(SqList&L)/构造一个空的线性表 /InitList_SqL.elem=(ElemType*)malloc(LIST_ INIT_SIZE sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;线性表操作 ListInsert_Sq(&L,i,e)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？21 18 30 75 42 56 8721 18 30 75例如：ListInsert_Sq(L,5,66)L.length-

15、10pppq87564266q=&(L.elemi-1);/q 指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;p插入操作移动元素的平均情况插入操作移动元素的平均情况:假设在第 i 个元素之前插入的概率为 ，则在长度为n 的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为：ip11)1(niiisinpE11)1(11niisinnE2n 若假定假定在线性表中任何一个位置上进行插入插入的概率的概率都是相等相等的，则移动元素的期望值移动元素的期望值为：线性表操作ListDelete_Sq(&L,i,&e)的实现首

16、先分析：删除元素时，线性表的逻辑结构发生什么变化？删除操作移动元素的平均情况删除操作移动元素的平均情况:假设删除第 i 个元素的概率为 ,则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值移动元素次数的期望值为：iqniidlinqE1)(nidlinnE1)(121n若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值移动元素的期望值为：在顺序存储结构的线性表中插入或在顺序存储结构的线性表中插入或删除一个数据元素平均约移动表中删除一个数据元素平均约移动表中的一半元素。若表长为的一半元素。若表长为n，则算法，则算法ListInsert_Sq和和ListDelet

17、e_Sq的的时时间复杂度均为间复杂度均为O(n)。void union(List&La,List Lb)/InitList_SqLa_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);if(!LocateElem(La,e,equal)ListInsert(La,+La_Len,e);int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/LocateElem_Sqi=1;/第1个元素的位序p=L.e

18、lem;/第1个元素的存储位置while(i=L.length&!(*compare)(*p+,e)+i;if(i=L.length)return i;else return 0;void MergeList_Sq(SqList La,SqList Lb,SqList&Lc)/pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb,length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);if(!Lc.elem)exit(OVERFLOW);pa_last=La.e

19、lem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&pb=pb_last)if(*pa=*pb)*pc+=*pa+;else*pc+=*pa+;while(pa=pa_last)*pc+=*pb+;while(pbnext;j=1;/p p指向第一个结点，指向第一个结点，j j为计数器为计数器while(p&jnext;+j;/顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素个元素 /或或 p p 为空为空if(!p|ji)return ERROR;/第第 i i 个元素不存在个元素不存在e=p

20、-data;/取得第取得第 i i 个元素个元素return OK;ai-1 线性表的操作 ListInsert(&L,i,e)在单链表中的实现：有序对有序对 改变为改变为 和和 eaiai-1 Status ListInsert_L(LinkList L,int i,ElemType e)/L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 /在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e /LinstInsert_Lp=L;j=0;while(p&j next;+j;/寻找第寻找第 i-1 个结点个结点if(!p|j i-1)return E

21、RROR;/i 大于表长或者小于大于表长或者小于1 s=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;p-next=s;/插入return OK;eai-1aiai-1sp算法的算法的时间复杂度时间复杂度为:O(n)线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1 Status ListDelete_L(LinkList L,int i,ElemType&e)/删除以 L 为头指针(带头结点)的单链表中第 i 个结点 /ListDelete_

22、L算法的算法的时间复杂度时间复杂度为:O(n)p=L;j=0;while(p-next&j next;+j;/寻找第 i 个结点，并令 p 指向其前趋if (!(p-next)|j i-1)return ERROR;/删除位置不合理q=p-next;p-next=q-next;/删除并释放结点e=q-data;free(q);return OK;操作 ClearList(&L)在链表中的实现:void ClearList(&L)/将单链表重新置为一个空表/ClearListwhile(L-next)p=L-next;L-next=p-next;free(p);算法时间复杂度：O(n)如何创建一

23、个单链表？如何创建一个单链表？链表是一个动态的结构，它不需要链表是一个动态的结构，它不需要予分配空间，因此予分配空间，因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入”的过程。的过程。&头插法建表示意图头插法建表示意图LpLLpLpvoid CreateList_L(LinkList&L,int n)/逆序输入 n 个数据元素，建立带头结点的单链表/CreateList_L算法的算法的时间复杂度时间复杂度为:O(n)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表for(i=n;i 0;-i)p=(Li

24、nkList)malloc(sizeof(LNode);scanf(&p-data);/输入元素值 p-next=L-next;L-next=p;/插入LlastLplastLlastp&尾插法建表示意图尾插法建表示意图void CreateList_L(LinkList&L,int n)/尾插法/CreateList_LL=(LinkList)malloc(sizeof(LNode);for(i=n;i 0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(&p-data);/输入元素值last-next=p;last=p;/插入last-next=NULL

25、;如何将两个有序链表归并一个有序链表？如何将两个有序链表归并一个有序链表？void MergeList_L(LinkList&La;&Lb;&Lc)pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);静态链表静态链表#define MAXSIZE 1000 typedef structElemTypeElemType data；/存储数据元素int cur；/游

26、标component,SLinkListMAXSIZE；针对不设“指针”的编程语言，怎样用不连续的内存区域来描述线性表？我们想到用一维数组来表示这种情况下的链表。用数组的一个分量表示一个结点，同时用游用数组的一个分量表示一个结点，同时用游标标curcur代替指针指示结点在数组的相对位置。代替指针指示结点在数组的相对位置。(a)修改前状态(b)修改后状态在在LiLi后插入后插入ShiShi；删除元素；删除元素ZhengZheng0123456789ZHAOQIANSUNLI ZHOUWUZHENGWANG1234567800123456789ZHAOQIANSUNLI ZHOUWUZHENGWA

27、NGSHI1234567805 最后一个结点的指针域的指针又指回第一个结点的链表2.3.2 循环链表循环链表 a1 a2 .an 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。a1 a2 .anAp a1 a2 .anBqp=A-next;q=B-next;A-next=q-next;B-next=p;free(q);算法的算法的时间复杂度时间复杂度为:O(1)循环链表的合并循环链表的合并2.3.3 双向链表双向链表typedef struct DuLNode ElemType data;/数据域 struct DuLNode *prior

28、;/指向前驱的指针域 struct DuLNode *next;/指向后继的指针域 DuLNode,*DuLinkList;双向循环链表双向循环链表空表空表非空表非空表 a1 a2 .an双向链表的操作特点：双向链表的操作特点：“查询查询”和单链表相同。和单链表相同。“插入插入”和和“删除删除”时需要同时修时需要同时修改两个方向上的指针。改两个方向上的指针。Status ListInsert_DuL(DULinkList&L,int i,ElemType e)/ListInsert_DuLif(!(p=GetElemP_DuL(L,i)return ERROR;if(!(s=(DuLinkLi

29、st)malloc(sizeof(DulNod)return ERROR;s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;return OK;Status ListDelete_DuL(DULinkList&L,int i,ElemType e)/ListDelete_DuLif(!(p=GetElemP_DuL(L,i)return ERROR;p-prior-next=p-next;p-next-prior=p-prior;e=p-data;free(p);return OK;用单链表实现线性表的操作时，存在的用单链表实

30、现线性表的操作时，存在的问题问题：改进链表的设置：改进链表的设置：1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值；1增加增加“表长表长”、“表尾指针表尾指针”和和“表头表头指针指针”三个数据域；三个数据域；2在单链表的最后一个元素之后插入元素时，在单链表的最后一个元素之后插入元素时，需遍历整个链表；需遍历整个链表；3在链表中，元素的在链表中，元素的“位序位序”概念淡化，结点的概念淡化，结点的 “位置位置”概念加强。概念加强。2将基本操作中的将基本操作中的“位序位序 i”改变为改变为“指针指针 p”。一个带头结点的线性链表类型一个带头结点的线性链表类型typedef struct LN

31、ode /结点类型结点类型 ElemType data;struct LNode *next;*Link,*Position;typedef struct /链表类型链表类型 Link head,tail;/分别指向头结点和 /最后一个结点的指针 int len;/指示链表长度 LinkList;nnnxpxpxppxp.)(2210在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示:P=(p0,p1,，pn)一元多项式一元多项式但是对于形如但是对于形如 S(x)=1+3x10000 2x20000的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？2.4 一元多

32、项式的表示及相加一元多项式的表示及相加 一般情况下的一元稀疏多项式一元稀疏多项式可写成 Pn(x)=p1xe1+p2xe2+pmxem其中其中：pi 是指数为ei 的项的非零系数，0 e1 e2 em=n可以下列线性表表示：（p1,e1）,(p2,e2),(pm,em)）P999(x)=7x3-2x12-8x999例如例如:可用线性表 (7,3),(-2,12),(-8,999)表示T 7 3-2 12-8999一元多项式的实现：一元多项式的实现：typedef struct /项项的表示 float coef;/系数系数 int expn;/指数指数 term,ElemType;typede

33、f LinkList polynomial;/用带表头结点的有序链表表示多项式用带表头结点的有序链表表示多项式结点的数据元素类型定义为:void CreatPolyn(polynomail&P,int m)/输入输入m项的系数和指数，建立表示一元多项式的有序链表项的系数和指数，建立表示一元多项式的有序链表P/CreatPolynInitList(P);h=GetHead(P);e.coef=0.0;e.expn=-1;SetCurElem(h,e);/设置头结点的数据元素for(i=1;iexpq-exp。将两结点系数相加：将两结点系数相加：和为和为0删除结点删除结点qa、qb和不为和不为0修

34、改修改qa系数并插入，删除系数并插入，删除qb本章小结本章小结1.1.了解线性表的逻辑结构特性是数据元素之间了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。用后者表示的线性表简称为链表。2.2.熟练掌握这两类存储结构的描述方法，以及熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。线性表的各种基本操作的实现。3.3.能够从

35、时间和空间复杂度的角度综合比较线性能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。表两种存储结构的不同特点及其适用场合。作业二n四、基础知识题四、基础知识题(2.12.3)P13n设有一个由正整数组成的无序单链表，编设有一个由正整数组成的无序单链表，编写算法完成以下功能：写算法完成以下功能：n找出最小值结点，且输出该数值；找出最小值结点，且输出该数值；n将链表排列为奇数在前，偶数在后。将链表排列为奇数在前，偶数在后。n编写一算法将单循环链表逆置。编写一算法将单循环链表逆置。n编写一在双向循环链表中值编写一在双向循环链表中值x结点之前插入结点之前插入值为值为y结点的算法。结点的算法。