1、12.1 ai ElemType2.2.1 线性表的定义线性表的定义线性表线性表(Linear List)是具有相同属性是具有相同属性的数据元素的一个有限序列。的数据元素的一个有限序列。(a1,a2,ai,ai+1,an)a1 a2 .ai ai+1 an2 ADT LinearList is Data:L=(a1,a2,ai,ai+1,an )Operation:void InitList(&L);/初始化线性表初始化线性表 void ClearList(&L);/删除线性表中所有元素，使之成为一个空表删除线性表中所有元素，使之成为一个空表 int ListSize(&L);/得到线性表的长
2、度得到线性表的长度 bool ListEmpty(&L);/检查线性表是否为空检查线性表是否为空 ElemType GetElem(&L,int pos);/得到线得到线 性表中指定序号的元素性表中指定序号的元素3void TraverseList(&L);/遍历一个线性表遍历一个线性表bool Find(&L,ElemType&item);/从线性表中从线性表中 查找具有给定值的元素查找具有给定值的元素bool Update(&L,const ElemType&item);/更新线性表中具有给定值的元素更新线性表中具有给定值的元素void InsertRear(&L,const ElemTy
3、pe&item);/向线性表的末尾添加一个元素向线性表的末尾添加一个元素void InsertFront(&L,const ElemType&item);/向线性表的表头插入一个元素向线性表的表头插入一个元素4void Insert(&L,const ElemType&item);/向线性表中满足条件的位置插入一个元素向线性表中满足条件的位置插入一个元素ElemType DeleteFront(&L);/从线性表中删除表头元素从线性表中删除表头元素bool Delete(&L,const ElemType&item);/从线性表中删除等于给定值的元素从线性表中删除等于给定值的元素void So
4、rt(&L);/对线性表进行排序对线性表进行排序end LinearList56 把线性表中的所有元素按照其逻辑顺序依次把线性表中的所有元素按照其逻辑顺序依次存储到计算机存储器中从指定存储位置开始的存储到计算机存储器中从指定存储位置开始的一块连续的存储空间中。一块连续的存储空间中。特点特点：逻辑关系逻辑关系 物理位置物理位置 a1 a2 ai ai+1 an 0 1 i-1 i n-1 MaxSize-17const int MaxSize=50;struct List ElemType listMaxSize;int size;/当前线性表长度当前线性表长度 ;在在C+中，线性表的顺序存储结
5、构是中，线性表的顺序存储结构是利用数组实现的。利用数组实现的。8一、有关空表的操作一、有关空表的操作 1.1.初始化操作初始化操作2.2.清空操作清空操作3.3.判空操作判空操作91 1、初始化线性表、初始化线性表void InitList(List&L)L.size=0;102 2、删除线性表中的所有元、删除线性表中的所有元 素，使之成为一个空表素，使之成为一个空表void ClearList(List&L)L.size=0;113 3、得到线性表的长度、得到线性表的长度int ListSize(List&L)return L.size;124 4、检查线性表是否为空、检查线性表是否为空bo
6、ol ListEmpty(List&L)return (L.size=0);13二、有关查找的操作二、有关查找的操作2、查找具有给定值的元素、查找具有给定值的元素1 1、遍历线性表操作、遍历线性表操作3 3、更新表中具有给定值的、更新表中具有给定值的 元素元素145、得到线性表中指定序号的元素、得到线性表中指定序号的元素 3 7 4 6 8 9序号序号123456L.size下标下标012345L.size-1线性表中第线性表中第 5 个元素是个元素是 815ElemType GetElem(List&L,int pos)if (pos L.size)cerr “pos is not rang
7、e!”endl;exit(1);return L.listpos-1;16 6.遍历一个线性表遍历一个线性表从表头元素起从表头元素起依次访问依次访问每一个元每一个元素，并且每个元素只被访问一次素，并且每个元素只被访问一次 a1 a2 ai-1 ai an基地址基地址最后一个最后一个17 3 7 4 6 8 95下标下标 0 1 2 3 4 5 L.size-1 6.遍历一个线性表遍历一个线性表347689518void TraverseList(List&L)for(int i=0;iL.size;i+)cout L.listi;cout endl;19 3 7 4 6 8 95下标下标 0
8、1 2 3 4 5 L.size-1查找值为查找值为 8 的元素的元素7 7、从线性表中查找具有给定值的元素、从线性表中查找具有给定值的元素查找成功！查找成功！20bool Find(List&L,ElemType&item)for (int i=0;iL.size,i+)if (L.listi=item)item=L.listi;return true;return false;21 3 7 4 6 8 95下标下标 0 1 2 3 4 5 L.size-1查找查找 8 并更新为并更新为 28 8、更新线性表中具有给定值的元素、更新线性表中具有给定值的元素222bool Update(Lis
9、t&L,const ElemType&item)for (int i=0;iL.size,i+)if(L.listi=item)L.listi=item;return true;return false;23三三 、有关插入的操作、有关插入的操作 2 2、表头插入表头插入1 1、表尾添加表尾添加3 3、满足条件的位置插入、满足条件的位置插入24 3 7 4 6 85下标下标 0 1 2 3 4 L.size-1向线性表的末尾添加向线性表的末尾添加 29 9、向线性表的末尾添加一个元素、向线性表的末尾添加一个元素 2L.size25void InsertRear(List&L,const Ele
10、mType&item)if (L.size=maxsize)cerr “List overflow!”endl;exit(1);L.listL.size=item;L.size+;26 3 7 4 6 85下标下标 0 1 2 3 45向线性表的表头插入向线性表的表头插入 2 561010、向线性表的表头插入一个元素、向线性表的表头插入一个元素 8 6 4 7 3 227 3 7 4 6 85下标下标 0 1 2 3 45向线性表的表头插入向线性表的表头插入 2 561010、向线性表的表头插入一个元素、向线性表的表头插入一个元素 3 7 4 6 8 228void InsertFront(L
11、ist&L,const ElemType&item)if(L.size=Maxsize)cerr “List overflow!”=0;i )L.listi+1=L.listi;L.list0=item;L.size+;29 2 4 5 91012下标下标 0 1 2 3 45向线性表插入向线性表插入 8 1211.向线性表中满足条件的位置插向线性表中满足条件的位置插 入一个元素入一个元素6 10 9 830 2 4 5 91012下标下标 0 1 2 3 45向线性表插入向线性表插入 8 1211.向线性表中满足条件的位置插向线性表中满足条件的位置插 入一个元素入一个元素6 9 10 831
12、 void Insert(List&L,const ElemType&item)if (L.size=Maxsize)cerr “List overflow!”endl;exit(1);for (int i=0;i L.size;i+)if(item=i;j-)L.listj+1=L.listj;L.listi=item;L.size+;32i i位置位置for(int j=L.size-1;j =i;j-)L.list j+1=L.list j ;最后的位置最后的位置 L.sizeL.size a0 a1 ai-1 ai an a0 a1 ai-1 e ai an表的长度增表的长度增 133
13、四、有关删除的操作四、有关删除的操作 2.2.删除删除i i位置位置元素操作元素操作1.1.删除删除表头表头元素操作元素操作34 3 7 4 6 895下标下标 0 1 2 3 45从线性表中删除表头元素插从线性表中删除表头元素插 3 7612.从线性表中删除表头元素从线性表中删除表头元素 4 6 8 9 535 3 7 4 6 895下标下标 0 1 2 3 45从线性表中删除表头元素插从线性表中删除表头元素插 3 7612.从线性表中删除表头元素从线性表中删除表头元素 4 6 8 9 536 ElemType Delete(List&L)if(L.size=0)cerr “Deleting
14、 From an empty list!”endl;exit(1);ElemType temp=L.list0;for(int i=1;i L.size;i+)L.listi-1=L.listi;L.size-;return temp;37 3 7 4 6 895下标下标 0 1 2 3 45从线性表中删除元素从线性表中删除元素 66 8 9 513.从线性表中删除等于给定从线性表中删除等于给定 值的元素值的元素38 3 7 4 6 895下标下标 0 1 2 3 45从线性表中删除元素从线性表中删除元素 66 813.从线性表中删除等于给定从线性表中删除等于给定 值的元素值的元素 9 539
15、bool Delete(List&L,const ElemType&item)if (L.size=0)cerr “L is an empty list!”endl;return false;for(int i=0;i L.size;i+)if(L.listi=item)break;if (i=L.size)cerr“Deleted element is not exist!”endl;return false;for (int j=i+1;j L.size;j+)L.listj-1=L.listj;L.size-;return true;40i i位置位置for(int j=i+1;j L.
16、size;j+)L.list j-1=L.list j ;最后的位置最后的位置 L.sizeL.size a0 a1 ai-1ai+1 an a0 a1 ai-1 aiai+1 an表的长度减表的长度减 14114.14.对对线线性性表表进进行行排排序序 void Sort(List&L)int i,j;ElemType x;for (i=1;i=0;j-)if(x L.listj)L.listj+1=L.listj;else break;L.listj+1=x;42 0 1 2 3 4 5 6 7 4265807428443665(1)4265807428443665(2)426580742
17、8443665(3)4265748028443665(4)2842657480443665(5)2842446574803665(6)2836424465748065(7)2836424465657480 线性表插入排序过程线性表插入排序过程432.2.3 线性表顺序存储空间的动态分配线性表顺序存储空间的动态分配Struct List ElemType*list;int size;记录存储类型定义：记录存储类型定义：44void InitList(List&L)L.list=new ElemTypeMaxsize;if (L.list=NULL)cerr“Memory allocation f
18、ailure!”endl;exit(1);L.size=0;初始化操作：初始化操作：4546 每个存储结点不仅含有所存元素本身的每个存储结点不仅含有所存元素本身的信息，而且含有元素之间逻辑关系的信息。信息，而且含有元素之间逻辑关系的信息。存储结点的结构为：存储结点的结构为：Data p1 p2 pm值域值域指指 针针 域域 单链表：单链表：每个结点只含有一个指针域的链每个结点只含有一个指针域的链接表。接表。47 表头表头指针指针中间中间结点结点表尾表尾结点结点表头表头结点结点H a1 a2 ai ai+1 an B a1 a2 .a i ai+1 an 48 a 3.3.在单链表插入和删除操作
19、在单链表插入和删除操作 有序对有序对改变为改变为a,和和,c b c a插入插入49s-next=p-next;p-next=s;b a c asp在单链表中插入结点在单链表中插入结点50s-next=p-next;c apq bsqsHLp-next=s;在单链表中插入结点在单链表中插入结点51 x y z xq=p-next;s=q;p-next=q-next;delete s;pS=q在单链表中删除结点在单链表中删除结点524.单链表中的结点类型单链表中的结点类型struct LNode struct LNode /单链表结点类型定义单链表结点类型定义 /独立结点独立结点 ElemTyp
20、e data;ElemType data;Lnode Lnode*next;next;例例 data next 值域值域指针域指针域 data next 指向后继结点指向后继结点53利用数组建立的单链表：作为单链表结点类型的数组元素的类型：作为单链表结点类型的数组元素的类型：struct ALNode /元素结点元素结点 ElemType data;int next;构造单链表的数组类型定义为：构造单链表的数组类型定义为：typedef ALNode ALinkListMaxsize;若单链表中的结点来自数组中的元素，则若单链表中的结点来自数组中的元素，则 next next域指向的是后继结点
21、所在的下标。域指向的是后继结点所在的下标。54利用数组建立单向链表示意图利用数组建立单向链表示意图 0 1 2 3 4 5 6 7 8 MaxSize-1 data75 62 83 44 57 94 50 68 next 4 3 8 6 7 2 0 5 1 通常下标为通常下标为0 0的数组元素用来保存表头指针，的数组元素用来保存表头指针，下标为下标为1 1的数组元素用来保存空闲表的表头指针。的数组元素用来保存空闲表的表头指针。4 7 5 2 8 1 3 6 44 50 57 62 68 75 83 94 0 f55 当向数组中的单链表插入一个新元素时，当向数组中的单链表插入一个新元素时，首先从
22、空闲表中取出首先从空闲表中取出(即删除即删除)表头结点作为保表头结点作为保存新元素的结点使用，然后再把该结点按条件存新元素的结点使用，然后再把该结点按条件插入到单链表中；当从数组中的单链表删除一插入到单链表中；当从数组中的单链表删除一个元素结点时，首先从单链表中取出这个结点，个元素结点时，首先从单链表中取出这个结点，然后再把该结点插入到空闲单链表的表头。然后再把该结点插入到空闲单链表的表头。数组的初始化数组的初始化 0 1 2 3 4 5 6 7 8 MaxSize-1 data next 0 2 3 4 5 6 7 8 9 0 插插 入入 3535302 插插 入入 68（表尾插入）（表尾插
23、入）68403 删除删除 35342565.双向链表中的结点类型和插入与双向链表中的结点类型和插入与 删除操作删除操作struct DNode ElemType data;DNode*left;DNode *right;双向链表中双向链表中的结点类型的结点类型 left data right指向后继结点指向后继结点指向后继结点指向后继结点值域值域指针域指针域指针域指针域57利用数组建立的双向链表利用数组建立的双向链表作为双链表结点类型的数组元素的类型：作为双链表结点类型的数组元素的类型：struct ADNode ElemType data;int left;int right;构造双链表的数
24、组类型定义为：构造双链表的数组类型定义为：typedef ADNode ALinkListMaxsize;58acb(1)q-right=p-right;(3)q-left=p;(2)q-right-left=q;(4)p-right=q;pqac插入插入双向链表双向链表59qeq-right=p-right;p-right=q;q-right-left=q;q-left=p;pai-1ai插入插入60a删除删除bc(1)p-left-right=p-right;(2)p-right-left=p-left;p61删除删除aip-right=p-right-right;p-right-left
25、=p;pai-1ai+1626.6.带带表头附加结点表头附加结点的线性链表的线性链表表头附加结点表头附加结点 B a1 a2 a3 an H a1 a2 a3 an 带表头附加结点的单链表带表头附加结点的单链表带表头附加结点的双向链表带表头附加结点的双向链表空链条件：空链条件：HL next=NULL空链条件：空链条件：HL lefy=HL-right=NULL63循环单链表：循环单链表：最后一个结点的指针域又指最后一个结点的指针域又指 回第一个结点。回第一个结点。7.7.循环链表循环链表判别判别链表中最后一个结点的链表中最后一个结点的条件条件不再是不再是“后继后继是否为空是否为空”，而是，而
26、是“后继是否为头结点后继是否为头结点”。带表头附加结点的循环单链表带表头附加结点的循环单链表 H a1 a2 an 64循环双链表：循环双链表：最后一个结点的右指针域指向最后一个结点的右指针域指向 第一个结点，第一个结点的左第一个结点，第一个结点的左 指针域指向最后一个结点。指针域指向最后一个结点。带表头附加结点的循环双链表带表头附加结点的循环双链表 B a1 a2 an 65 在利用数组链结存储一个线性表时，得在利用数组链结存储一个线性表时，得到的单链表就是一个带有表头附加结点的循到的单链表就是一个带有表头附加结点的循环链表，其表头附加结点就是下标为环链表，其表头附加结点就是下标为 0 0
27、的元的元素，该元素的指针域指向表头结点，此链表素，该元素的指针域指向表头结点，此链表的表尾结点的指针域为的表尾结点的指针域为0 0，正好是附加表头结，正好是附加表头结点的存储位置。点的存储位置。注注:66 H a1 a2 ai ai+1 an 671.1.初始化单链表初始化单链表 void InitList(LNode*&HL)HL=NULL:68 2.2.删除单链表中所有结点删除单链表中所有结点,使之成为一个空表使之成为一个空表HL a1 a2 a3 a4 a5 cpnpcpnpcpnpcpnpcpnpcp69void ClearList(LNode*&HL)LNode*cp,*np;cp=
28、HL;while(cp!=NULL)np=cp-next;delete cp;cp=np;HL=NULL:703.3.得到单链表的长度得到单链表的长度HL 27 18 35 72 96 HLi=0i=1HLi=2HLi=3HLi=4HLi=5HL单链表的长度等于单链表的长度等于 571int ListSize(LNode*HL)int i=0;while(HL!=NULL)i+;HL=HL-next;return i;724.检查单链表是否为空bool ListEmpty(LNode*HL)return (HL=NULL);735.5.得到单链表中第得到单链表中第 pos pos 个结点中的元
29、素个结点中的元素HL 27 18 35 72 96 单链表中第单链表中第 3个结点中的元素是个结点中的元素是HLi=0i=1HLi=2HLi=33574ElemType GetElem(LNode*HL,int pos)if(pos1)cerrpos is out range!next;if(HL!=NULL)return HL-data;else cerrpos is out range!endl;exit(1);756.6.遍历一个单链表遍历一个单链表HL 27 18 35 72 96 HL27HL18HL35HL72HL96HL76 void TraverseList(LNode*HL)
30、while(HL!=NULL)coutdatanext;coutdata=item)item=p-data;return true;else p=p-next;return false;79HL 27 18 35 72 96 p查找查找35并更新为并更新为36pp8.更新单链表中具有给定值的元素3680bool Update(LNode*HL,const ElemType&item)LNode*p=HL;while(p!=NULL)if(p-data=item)break;else p=p-next;if(p=NULL)return false;else p-data=item;return
31、true;819.9.向单链表的末尾添加一个元素向单链表的末尾添加一个元素HL 27 18 35 72 newptr向单链表的末尾添加元素向单链表的末尾添加元素969696 pppp82void InsertRear(LNode*&HL,const Elemtype&item)LNode*newptr;newptr=new LNode;if(newptr=NULL)cerrMemory allocation failuredata=item;newptr-next=NULL;if(HL=NULL)HL=newptr;else LNode*P=HL;while(p-next!=NULL)p=p-
32、next;p-next=newptr;8310.10.向单链表的表头插入一个元素向单链表的表头插入一个元素向单链表的表头添加元素向单链表的表头添加元素2727HL 18 35 72 96 2784void InsertFront(LNode*&HL,const ElemType&item)LNode*newptr;newptr=new LNode;if(newptr=NULL)cerrMemory allocation failure!data=item;newptr-next=HL;HL=newptr;8511.11.向单链表中满足条件的位置向单链表中满足条件的位置 插入一个元素插入一个元素
33、HL 18 27 35 96 向（有序）单链表中插入元素向（有序）单链表中插入元素7272apcpapcpapcp72 newptr86void Insert(LNode*&HL,const ElemType&item)LNode*newptr;newptr=new Lnode;if(newptr=NULL)cerrMemory allocation failure!data=item;if(HL=NULL|itemdata)newptr-next=HL;HL=newptr;return;LNode*cp;LNode*ap;ap=HL;cp=HL-next;while(cp!=NULL)if(
34、itemdata)break;else ap=cp;cp=cp-next;newptr-next=cp;ap-next=newptr;8712.12.从单链表中删除表头元素从单链表中删除表头元素HL 27 18 35 72 96 p88ElemType DeleteFront(LNode*&HL)if(HL=NULL)cerrDeleting from an empty list!next;ElemType temp=p-data;delete p;return temp;8913.13.从单链表中删除等于给定从单链表中删除等于给定 值的元素值的元素HL 27 18 35 72 96 从单链表
35、中删除元素从单链表中删除元素7272apcpapcpapcp90bool Delete(LNode*&HL,const ElemType&item)if(HL=NULL)cerrHL is NULL!data=item)LNode*p=HL;HL=HL-next;delete p;return true;LNode*ap,*cp;ap=HL;cp=HL-next;while(cp!=NULL)if(cp-data=item)break;else ap=cp;cp=cp-next;if(cp=NULL)cerrDeleted element is not exist!next=cp-next;d
36、elete cp;return true;9114.14.利用单链表进行数据排序利用单链表进行数据排序 假定待排序的假定待排序的 n个数据存在于一维数组个数据存在于一维数组an中，当利用单链表进行排序时，从空中，当利用单链表进行排序时，从空链表开始，每次调用链表开始，每次调用Insert算法算法(有序插入有序插入)向单链表中插入数组向单链表中插入数组a a中的一个元素中的一个元素,经经n n次调用后，单链表成为包含数组次调用后，单链表成为包含数组a中中n个元个元素的有序表，最后遍历单链表，把每个结素的有序表，最后遍历单链表，把每个结点的植依次写入到数组点的植依次写入到数组a中。中。92void LinkSort(Element a ,int n)LNode*head=NULL;int i;for(i=0;idata;p=p-next;ClearList(head);93
