第3章数据结构——线性表

1、第三章第三章 线性表线性表DS应用实践 线性表的概念 双向链表 循环链表 线性表的顺序存储 单向链表 线性结构特点线性结构特点在数据元素的非空有限集中在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继3.1 线性表的概念线性表的概念niaaaa,21如例 英文字母表（A,B,C,.Z)是一个线性表 定义：一个线性表是n个数据元素的有限序列3.1.1线性表的定义线性表的定义3.1 线性表的概念线性表的概念 特征： 元素个数n表长度，n=0空

2、表 1in时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继 元素同构，且不能出现缺项3.1.1 线性表的定义线性表的定义3.1.2 线性表的抽象数据类型描述线性表的抽象数据类型描述ADT List 数据对象：D ai | ai ElemType, i=1,2,.,n, n0 数据关系：R |ai-1 ,aiD, i=2,.,n 基本操作： （详见下页） ADT List 基本操作InitList(SqList *L )/线性表的初始化，即构造一个空的线性表LDestroyList(SqList &L )/释放线性表L占用的内存空间ListEmpty(S

3、qList L )/判断线性表L是否为空表ListLength(SqList L ) /求线性表的长度，返回L中元素个数GetElem(SqList L, int i, DataType *e) /求线性表L中第i(1in)个元素的值 基本操作LocateElem(SqList L, DataType e) /返回L中第1个与e满足关系的数据元素位序ListTraverse(SqList L) /依次对线性表L的每个元素进行遍历ClearList(SqList *L ) /将线性表L重置为空表PutElem(SqList L,int i, DataType *e ) /给线性表L中第i个元素赋

4、值ListInsert(SqList *L, int i, DataType e ) /在线性表L的第i个元素之前插入新的元素eListDelete(SqList *L, int i, DataType *e) /删除L的第i个元素，并用e返回其值，L的长度减1 基本操作CreateListHead(SqList *L, int n) /用头插法建立带表头结点的单链线性表LCreateListTail(SqList *L, int n) /用尾插法建立带表头结点的单链线性表L定义：用一组地址连续的存储单元存放一个线性表叫定义：用一组地址连续的存储单元存放一个线性表叫元素地址计算方法元素地址计算

5、方法 LOC(ai+1)=LOC(ai)+d LOC(ai)=LOC(a1)+(i-1)*dd 一个元素占用的存储单元个数LOC(ai)线性表第i个元素的地址3.2 线性表的顺序存储线性表的顺序存储特点：特点： 实现逻辑上相邻实现逻辑上相邻物理地址相邻物理地址相邻 实现随机存取实现随机存取实现：可用C语言的一维数组实现在C语言中，线性表的顺序存储的类型定义如下：typedef int DataType; / DataType类型根据实际情 况而定，这里假设为int#define MAXSIZE 100 / MAXSIZE可根据实际 情况而定 typedef structDataType dat

6、aMAXSIZE; int length; SqList;图3.1 线性表的顺序存储结构 a1a2an01n-112n内存V数组下标元素序号M-1typedef int DataType; #define MAXSIZE 100例 typedef struct DataType dataMAXSIZE int length;SqList;备用空间数据元素不是简单类型时,可定义结构体数组3.2.2顺序表的基本运算顺序表的基本运算 1.线性表的初始化int InitList(SqList *L) L.length=0; /空表，长度为空表，长度为0 return OK; 3.2.2顺序表的基本运算

7、顺序表的基本运算 2.释放线性表void DestroyList(SqList &L) if (L-data) free(L-data); /释放线性表占据的所释放线性表占据的所有存储空间有存储空间 3.2.2顺序表的基本运算顺序表的基本运算 3.判断线性表是否为空表int ListEmpty(SqList L) if (L.length=0) return TRUE; if (L.length!=0) return FALSE; 3.2.2顺序表的基本运算顺序表的基本运算 4.求线性表的长度int ListLength(SqList L) return (L.length); 3.2

8、.2顺序表的基本运算顺序表的基本运算 5.求线性表中第i个元素的值int GetElem(SqList L,int i,DataType *e) if (iL.length) return ERROR; /判断判断i值是否合理，若不合值是否合理，若不合理，返回理，返回ERROR *e=L.datai-1; /数组中第数组中第i-1的单元存储着线的单元存储着线性表中第性表中第i个数据元素的内容个数据元素的内容 return OK; 3.2.2顺序表的基本运算顺序表的基本运算 6.返回线性表中第1个与e满足关系的数据元素位序int LocateElem(SqList L, DataType e)

9、int i; for (i=1; i=L.length; +i) if (e = L.datai-1) return i; return FALSE 3.2.2顺序表的基本运算顺序表的基本运算 7.遍历线性表void ListTraverse(SqList L) int i; for (i=i; ilength=0; /将线性表的长度置为将线性表的长度置为0 3.2.2顺序表的基本运算顺序表的基本运算 9.给线性表中第i个元素赋值int PutElem(SqList L,int i,DataType *e) if (iL.length) return ERROR; /判断判断i值是否合理，若不

10、合值是否合理，若不合理，返回理，返回ERROR L.datai-1=*e; /数组中第数组中第i-1的单元存储着线的单元存储着线性表中第性表中第i个数据元素的内容个数据元素的内容 return OK; v定义：线性表的插入是指在第定义：线性表的插入是指在第i（1 1 i i n+1 n+1）个个元素之前插入一个新的数据元素元素之前插入一个新的数据元素x，使长度为使长度为n的的线性表线性表变成变成长度为长度为n+1的线性表的线性表niiaaaaa,1,21niiaaxaaa,1,21 需将第i至第n共（n-i+1)个元素后移3.2.2顺序表的基本运算顺序表的基本运算 10.插入 数据元素数据元素

11、ai-1和和 ai 的逻辑关系发生了变化。在线性表的逻辑关系发生了变化。在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理的顺序存储结构中，由于逻辑上相邻的数据元素在物理上也是相邻的，因此，除非上也是相邻的，因此，除非i = n + 1，否则必须移动元，否则必须移动元素才能反映这个逻辑关系的变化。素才能反映这个逻辑关系的变化。图图3.2 线性表插入前后的状况内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1xint ListInsert(SqList *L,i

12、nt i,DataType e) int k;if (L-length=MAXSIZE) return ERROR;if (iL-length+1) return ERROR;if (ilength) for(k=L-length-1;k=i-1;k-) L-datak+1=L-datak;L-datai-1=e; L-length+;return OK; 算法时间复杂度算法时间复杂度T(n)设设Pi 是在第是在第i个元素之前插入一个元素的概率，个元素之前插入一个元素的概率，则在长度为则在长度为n的线性表中插入一个元素时，所的线性表中插入一个元素时，所需移动的元素次数的平均次数为：需移动的元素

13、次数的平均次数为：11)1(niiinPEis nOnTninnEisnPnii112)1(1111则若认为11. 线性表中数据元素的删除线性表中数据元素的删除niiaaaaa,1,21 变成变成长度为长度为n-1n-1的线性表的线性表niiaaaaa,11,21 需将第需将第i+1i+1至第至第n n共共（n-i)n-i)个元素前移个元素前移 定义：线性表的删除是指将第定义：线性表的删除是指将第i（1 1 i i n n）个元素删除，使长度为个元素删除，使长度为n的线性表的线性表 图图3.3 线性表删除前后的状况内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1n

14、n+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2int ListDelete(SqList *L,int i,DataType *e) int k; if (L-length=0) return ERROR; if (iL-length) return ERROR; *e=L-datai-1; if (ilength) for(k=i;klength;k+) L-datak-1=L-datak; L-length-; return OK;设设Qi是删除第是删除第i个元素的概率，则在长度为个元素的概率，则在长度为n的线的线性表中删除一个元素所需

15、移动的元素次数的平性表中删除一个元素所需移动的元素次数的平均次数为：均次数为：niideinQE1)( nOnTninnEnQnidei121)(11则若认为故在故在顺序表中插入或删除顺序表中插入或删除一个元素时，平均移一个元素时，平均移动表的一半元素，当动表的一半元素，当n n很大时，很大时，效率很低效率很低v算法评价算法评价 顺序存储结构的优缺点顺序存储结构的优缺点 优点优点逻辑相邻，物理相邻逻辑相邻，物理相邻可随机存取任一元素可随机存取任一元素存储空间使用紧凑存储空间使用紧凑 缺点缺点插入、删除操作需要移动大量的元素插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分

16、预先分配空间需按最大空间分配，利用不充分表容量难以扩充表容量难以扩充练习：练习：1.实现在顺序表中按值插入元素。实现在顺序表中按值插入元素。2.给定一个顺序表给定一个顺序表L=（a1,a2,a3,.,an),请设计请设计一个算法删除所有值大于一个算法删除所有值大于min而且小于而且小于max的元的元素。素。 实现在顺序表中按值插入元素实现在顺序表中按值插入元素int ListInsert(SqList *L,DataType e)int k;if (L-length=MAXSIZE) return ERROR; for(k=L-length;k=1;k-) if(L-datak-1e) L-d

17、atak=L-datak-1;else break; L-datak=e; L-length+;return OK;给定一个顺序表给定一个顺序表L=（a1,a2,a3,.,an),请设计一个请设计一个算法删除所有值大于算法删除所有值大于min而且小于而且小于max的元素的元素int ListDelete(SqList *L,int min,int max) int k,i; if (L-length=0) return ERROR; for(k=1;klength;k+)if(L-datak-1min&L-datak-1max) for(i=k;ilength;i+) L-datai-

18、1=L-datai; L-length-;k-; return OK;3.3 单向链表单向链表 顺序表的存储特点是用物理上的相邻来实现逻辑上的相邻，它要求用连续的存储单元顺序存储线性表中各元素，因此，对顺序表插入、删除时需要通过移动数据元素来实现，影响了运行效率。 线性链表不需要用地址连续的存储单元来实现，而是通过“链”建立起数据元素之间的逻辑结构。 3.3 单向链表单向链表特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息。 这两部分信息组成数据元素的存储映像，称为结结点点。由于

19、上述链表的每个结一个点只有一个指示其直接相继的信息，故将这种链表称为单向链表，单向链表，简称为单链表单链表。 结点数据域：元素本身信息指针域：指示直接后继的存储位置数据域 指针域结点 n个结点（ai(1in)的存储映像）链结成一个链表，即为线性表 (a1, a2, .,an)的链式存储结构。整个链表的存取必须从头指针头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为空(NULL)。 L为单链表的头指针，它指向表中第一个结点。若L为空(NULL)，则所表示的线性表为“空”表，其长度n为“零”

20、。在单链表的第一个结点之前附设一个结点，称之为“头结点头结点”。头结点的数据域可以不存储任何信息，指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。单链表的头指针指向头结点。若线性表为空表，则头结点的指针域为“空”。 (a) 非空表 (b) 空表图图3.4 带头指针的单链表用C语言定义的单链表结构如下：typedef struct Node DataType data; struct Node *next;Node;typedef struct Node *LinkList; ZHAOQIANSUNLIZHOUWUZHENGWANGH例 线性表 (ZHAO,QIAN,SUN,LI,

21、ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针(1) InitList(LinkList *L) /初始化单链表(2) ListEmpty(LinkList L) /判断单链表是否为空(3) ClearList(LinkList *L) /单链表的置空(4) CreateListTail(LinkList *L, int n)/从尾创建添加结点(5) CreateListHead(LinkList *L, int n)/从头创建添加结点(6) ListLe

22、ngth(LinkList L) /获取链表结点数量(表长)(7) GetElem(LinkList L,int i,DataType *e) /获取指定位置结点(8) LocateElem(LinkList L,DataType e) /获取指定数据元素的位序(9) ListInsert(LinkList *L,int i,DataType e) /插入指定位置的数据元素(10) ListDelete(LinkList *L,int i,DataType *e) /删除指定位置的数据元素(11) ListTraverse(LinkList L) /单链表的遍历3.3.3单向链表的基本操作单向

23、链表的基本操作 (1) 初始化单向链表初始化单向链表int InitList(LinkList &L) L=(LinkList)malloc(sizeof(Node); if(!L) return ERROR; L-next=NULL; return OK;算法算法3.3 初始化单链表(2)判断是否为空判断是否为空 若L为空表，则返回TRUE，否则返回FALSE。int ListEmpty(LinkList L) if(L-next) return FALSE; else return TRUE;算法算法3.4 判断单链表是否为空(3) 置空置空int ClearList(LinkLi

24、st &L) LinkList p,q;p=L-next; /p指向第一个结点while(p) /没到表尾q=p-next;free(p);p=q;L-next=NULL; return OK; 算法算法3.5 单链表的置空(4) 求表长求表长int ListLength(LinkList L) int i=0; LinkList p=L-next; while(p) i+; p=p-next; return i; 算法算法3.6 单链表的表长(5) 取值取值int GetElem(LinkList L,int i,DataType *e) int j;LinkList p;p = L

25、-next;j = 1; while (p & jnext; +j;if ( !p | ji ) return ERROR; *e = p-data; return OK;(6) 求位序求位序(查找查找)int LocateElem(LinkList L,DataType e) int i=0; LinkList p=L-next; while(p) i+; if(p-data=e) /找到这样的数据元素 return i; p=p-next; return 0; 算法算法3.8 单链表某元素的位序 nOnT算法评价？算法评价？pabes在线性表两个数据元素a和b间插入e，已知p指向a

26、s-next=p-next;p-next=s; 1OnT算法评价(7) 单链表的插入单链表的插入(7) 单链表的插入单链表的插入int ListInsert(LinkList &L,int i,DataType e) int j;LinkList p,s;p = L; j = 1;while (p & j next;+j; if (!p | j i) return ERROR; (7) 单链表的插入单链表的插入s = (LinkList)malloc(sizeof(Node); /生成新结点s-data = e; s-next = p-next; p-next = s; ret

27、urn OK;pabc 1OnT算法评价单链表中删除b，设p指向ap-next=p-next-next;(8) 单链表的删除单链表的删除q = p-next; p-next = q-next;q(8) 单链表的删除单链表的删除int ListDelete(LinkList &L,int i,DataType *e) int j;LinkList p,q;p = L;j = 1;while (p-next & j next; +j;if (!(p-next) | j i) return ERROR; (8) 单链表的删除单链表的删除q = p-next;p-next = q-ne

28、xt;*e = q-data; /将q结点中的数据给e free(q); /系统回收此结点，释放内存return OK;(9) 单链表的遍历单链表的遍历int ListTraverse(LinkList L) int count =0; LinkList p=L-next; while(p) printf(%d , p-data); p=p-next; count+; printf(n); return (count);(10) 头插法头插法 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）。void CreateListHead(LinkList &L, int n) L

29、inkList p;int i;srand(time(0); /初始化随机数种子L = (LinkList)malloc(sizeof(Node);L-next = NULL; (10) 头插法头插法 for (i=0; idata = rand()%100+1; /随机生成100以内的数字*p-next = L-next; L-next = p;(11) 尾插法尾插法 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）。void CreateListTail(LinkList &L, int n) LinkList p,r;int i;srand(time(0); L =

30、(LinkList)malloc(sizeof(Node); r=L; (11) 尾插法尾插法for (i=0; idata = rand()%100+1; r-next=p; r = p; r-next = NULL; 它是一种动态结构 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢单链表特点1.在下面链表中按顺序插入结点在下面链表中按顺序插入结点q，写出核心程序段写出核心程序段1628H4360 52q设计算法设计算法2.将单链表中所有重复的结点删除，只保留第一个将单链表中所有重复的结点删除，只保留第一个3.3.将两个有序单链表合并成一个有序单链表，合并后将两个有序单链表

31、合并成一个有序单链表，合并后p1为结果链表，为结果链表，p2 为空。为空。2009年研究生考试真题（年研究生考试真题（15分）分）v已知一个带有表头结点的单链表，结点结构为已知一个带有表头结点的单链表，结点结构为v假设该链表只给出了头指针假设该链表只给出了头指针list。在不改变链表。在不改变链表的前提下，请设计一个尽可能高效的算法，查找的前提下，请设计一个尽可能高效的算法，查找链表中倒数第链表中倒数第k个位置上的结点（个位置上的结点（k为正整数）。为正整数）。若查找成功，算法输出该结点的若查找成功，算法输出该结点的data域的值，域的值，并返回并返回1；否则，只返回；否则，只返回0。要求：。

32、要求：（1）描述算法的基本设计思想）描述算法的基本设计思想（2）描述算法的详细实现步骤）描述算法的详细实现步骤（3）根据设计思想和实现步骤，采用程序设计语）根据设计思想和实现步骤，采用程序设计语言描述算法（使用言描述算法（使用C或或C+或或JAVA语言实现），语言实现），关键之处请给出简要注释关键之处请给出简要注释datalink（1）基本思想：从头至尾遍历单链表，并用指针）基本思想：从头至尾遍历单链表，并用指针p指向当前结点的前指向当前结点的前k个结点，当遍历到链表的最后个结点，当遍历到链表的最后一个结点时，指针一个结点时，指针p所指向的结点即为所查找的结所指向的结点即为所查找的结点点（2）

33、详细步骤：增加两个指针变量和一个整形变量，）详细步骤：增加两个指针变量和一个整形变量，从链表头向后遍历，其中指针从链表头向后遍历，其中指针p1指向当前遍历的指向当前遍历的结点，指针结点，指针p指向指向p1所指结点的前所指结点的前k个结点，如果个结点，如果p1之前没有之前没有k个结点，那么个结点，那么p指向表头结点。用整指向表头结点。用整型变量型变量i表示当前遍历了多少个结点，当表示当前遍历了多少个结点，当ik时，时，指针指针p随着每次的遍历，也向前移动一个结点。当随着每次的遍历，也向前移动一个结点。当遍历完成时，遍历完成时，p或者指向表头结点，或者指向链表或者指向表头结点，或者指向链表中倒数第

34、中倒数第k的位置上的结点的位置上的结点（3）int LocateElement(Linklist list,int k) p1=list-link; p=list; i=1; while(p1) p1=p1-link; i+; if(ik) p=p-link; if(p=list) return 0; else printf(“%dn”,p-data); return 1; 3.4 循环链表循环链表v循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，从表中任何一结点出发均可找到表中其他结点。 (a) 非空表 (b) 空表图3.5 单循环链表v

35、循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p-next是否为空，而是在于它们是否等于头指针。3.5 双向链表双向链表(double linked list)v对单链表进行改进的另一种方法是构成双向链表。双向链表中每个结点除了有向后的指针(next)外，还有一个指向前一个结点的指针(prior)，这样形成的链表中有两条不同方向的链，因此，从某一个结点均可向两个方向访问。这样构成的链表有两个方向不同的链，简称为双向链表。3.5 双向链表双向链表(double linked list)图3.7 双向循环链表结点结构其中链域prior和next分别指向本结点的直接前趋结点和直

36、接后继结点。数据域指针域指针域结点结点存储数据元素存储数据元素datadata存储后继结点存储后继结点 的地址的地址nextnext存储前趋结点存储前趋结点 的地址的地址priorpriorv如果循环链表的结点再采用双向指针，就成为双向循环链表也成为双链表。图3.8是一个具有空表头结点的双向循环链表，其表尾结点的向右指针指向空表头结点，空表头结点的向左指针指向表尾结点。 图 3.8 双向循环链表 L空双向循环链表：v双链表较单链表虽然要多占用一些存储单元，但对其插入和删除操作以及查找结点的前趋和后继都非常方便。在链表较长，插入、删除较频繁或需要经常查找结点的前趋和后继的情况下使用双链表比较合适

37、。双链表结构是一种对称结构，设指针p指向双链表的某一结点，则双链表的对称性可用下式来表示： p=(p-next)-prior=(p-prior)-nextv亦即结点*p的地址既存放在其前趋结点*(p-prior)的后继指针域中，又存放在它的后继结点*(p-next)的前趋指针域中。3.5.2 双向链表的基本操作双向链表的基本操作 与单链表相比较，双向链表只是增加了直接前继的指针域，故其存储结构可表示为：typedef struct DuLNode DataType data;struct DuLNode *prior;struct DuLNode *next; DuLNode, *DuLink; 在双向链表上进行操作基本上和单向链表相同，例如，查找结点也是要从头指针指示的头结点开始，但插入和删除时必须同时修改两个方向上的指针。(1) 双向链表的插入双向链表的插入在带头结点的双向链表L 中结点*p 之后