数据结构-第2章-线性表.pptx

《数据结构-第2章-线性表.pptx》由会员分享，可在线阅读，更多相关《数据结构-第2章-线性表.pptx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构 新世纪应用型高等教育新世纪应用型高等教育计算机类课程规划教材计算机类课程规划教材新世纪应用型高等教育教材编审委员会新世纪应用型高等教育教材编审委员会 组编组编 主编主编 曹春萍曹春萍2.1 线性表的基本概念第第2 2章章线性表线性表线性表（线性表（linear-list）是一组具有相同特征的数据元素的有限序列。如，某）是一组具有相同特征的数据元素的有限序列。如，某校十个教学班级的学生人数（校十个教学班级的学生人数（50，53，55，52，56，59，60，55，57，51）构成一个线性表。构成一个线性表。线性表可用一个标示符来命名。如用线性表可用一个标示符来命名。如用List来命名上

2、述线性表，则可表示为：来命名上述线性表，则可表示为：List=（50，53，55，52，56，59，60，55，57，51）线性表中所包含的数据元素的个数称为线性表的长度，可用线性表中所包含的数据元素的个数称为线性表的长度，可用n表示。表示。n=0表表示线性表为空，称为空表。示线性表为空，称为空表。线性表中的数据元素可分别用线性表中的数据元素可分别用a1，a2，a3，ai，an表示。其中表示。其中a1是第一个数据元素，是第一个数据元素，an是最后一个数据元素，每个数据元素在表中都有一个唯是最后一个数据元素，每个数据元素在表中都有一个唯一确定的位置，可用下标一确定的位置，可用下标i表示第表示第i

3、个数据元素在表中的位置。个数据元素在表中的位置。2.1 线性表的基本概念第第2 2章章线性表线性表2.1.1 2.1.1 线性表的定义线性表的定义线性表线性表（linear-list）是一组具有相同特征的数据元素的有限序列。如，某）是一组具有相同特征的数据元素的有限序列。如，某校十个教学班级的学生人数（校十个教学班级的学生人数（50，53，55，52，56，59，60，55，57，51）构成一个线性表。构成一个线性表。线性表可用一个标示符来命名。如用线性表可用一个标示符来命名。如用List来命名上述线性表，则可表示为：来命名上述线性表，则可表示为：List=（50，53，55，52，56，59

4、，60，55，57，51）线性表中所包含的数据元素的个数称为线性表的长度，可用线性表中所包含的数据元素的个数称为线性表的长度，可用n表示。表示。n=0表表示线性表为空，称为空表示线性表为空，称为空表。2.1 线性表的基本概念第第2 2章章线性表线性表2.1.2 2.1.2 线性表的特点线性表的特点线性表是一种线性结构，其中的数据元素有序且有限。一个非空的线性表线性表是一种线性结构，其中的数据元素有序且有限。一个非空的线性表具有如下特点具有如下特点：u 有有且仅有一个开始数据元素，该元素没有前驱；且仅有一个开始数据元素，该元素没有前驱；u 有有且仅有一个终端数据元素，该元素没有后继；且仅有一个终

5、端数据元素，该元素没有后继；u 除除开始数据元素外，其它的数据元素有且仅有一个直接前驱；开始数据元素外，其它的数据元素有且仅有一个直接前驱；u 除除终端数据元素外，其它的数据元素有且仅有一个直接后继。终端数据元素外，其它的数据元素有且仅有一个直接后继。2.1 线性表的基本概念第第2 2章章线性表线性表2.1.3 2.1.3 线性表的抽象数据类型线性表的抽象数据类型 线性表的抽象数据类型定义如下：ADT List 定义：一组具有相同特征的数据元素的有限序列 表示：List=（a1，a2，a3，ai，an）基本操作：Initiate（List）操作结果：初始化操作。置一个空的线性表List。Cle

6、arList（List）初始条件：线性表List存在。操作结果：将线性表List置为空表。2.1 线性表的基本概念第第2 2章章线性表线性表 ListEmpty（List）初始条件：线性表List存在。操作结果：若线性表List为空，则返回true；否则返回false。Length（List）初始条件：线性表List存在。操作结果：返回线性表List的长度，若为空，则返回0。Get（List，i，e）初始条件：线性表List存在，1iLength（List）。操作结果：返回线性表List的第i个数据元素，由e返回。Find（List，i，e）初始条件：线性表List存在。操作结果：返回线性表L

7、ist中第一个值为e的数据元素的位置（第 几个元素），值由i返回。若没有找到，则返回-1。2.1 线性表的基本概念第第2 2章章线性表线性表Insert（List，i，e）初始条件：线性表List存在，1iLength（List）+1。操作结果：在线性表List的第i个位置插入元素e，线性表长度加1。Delete（List，i）初始条件：线性表List存在，1iLength（List）。操作结果：删除线性表List第i个位置上的数据元素，线性表长度减1。GetPrior（List，e，pre_e）初始条件：线性表List存在。操作结果：若e是线性表List中的数据元素，且不是第一个数据元素，则

8、用&pre_e返回e的前驱；否则返回NULL。GetNext（List，e，next_e）初始条件：线性表List存在。操作结果：若e是线性表中List的数据元素，且不是最后一个数据元素，则用&next_e返回e的后继；否则返回NULL。2.2 线性表的顺序存储和操作实现第第2 2章章线性表线性表2.2.1 2.2.1 线性表线性表为了用计算机处理线性表，必须为它选择为了用计算机处理线性表，必须为它选择合适的存储结构。线性表的存储结构有顺序、合适的存储结构。线性表的存储结构有顺序、链式、索引、散列等多种方式，其中顺序存链式、索引、散列等多种方式，其中顺序存储和链式存储是两种最简单常用的存储结构

9、。储和链式存储是两种最简单常用的存储结构。本小节主要介绍线性表的顺序存储和相关操本小节主要介绍线性表的顺序存储和相关操作。作。线性表的顺序存储是指用一组地址连续的线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的每一个数据元存储单元依次存储线性表中的每一个数据元素。素。2.2 线性表的顺序存储和操作实现第第2 2章章线性表线性表 2.2.1 2.2.1 线性表线性表 采用采用顺序存储结构的线性表称为顺序表。其特点是：顺序存储结构的线性表称为顺序表。其特点是：线性表线性表的逻辑顺序与物理顺序一致；的逻辑顺序与物理顺序一致；p 线性表线性表的数据元素之间的关系可以通过物理存储之间的相邻

10、关系来体现；的数据元素之间的关系可以通过物理存储之间的相邻关系来体现；p 假设假设顺序表中第一个数据元素的存储位置为顺序表中第一个数据元素的存储位置为LOC(a1)LOC(a1)，每一个数据元素占，每一个数据元素占用的存储单元数为用的存储单元数为c c，则第，则第i i个数据元素的存储位置为：个数据元素的存储位置为：pLOC(ai)=LOC(a1)+(i-1)*cLOC(ai)=LOC(a1)+(i-1)*c2.2 线性表的顺序存储和操作实现第第2 2章章线性表线性表 2.2.2 2.2.2 线性表的基本操作线性表的基本操作 1.1.初始化顺序表初始化顺序表动态分配存储空间，并把顺序表置为空。

11、动态分配存储空间，并把顺序表置为空。Status Initiate_Sq(SqList*L)Status Initiate_Sq(SqList*L)L-L-list=(ElemType*)malloc(LIST_SIZE*sizeof(ElemType);list=(ElemType*)malloc(LIST_SIZE*sizeof(ElemType);/*/*分配内存单元分配内存单元*/if if(!L-list)(!L-list)printf(“Memory allocate failed!n”);printf(“Memory allocate failed!n”);return retu

12、rn ERROR;ERROR;L-L-length=0;length=0;/*/*空表长度为空表长度为0*/0*/L-L-list_size=LIST_SIZE;list_size=LIST_SIZE;/*/*初始存储容量初始存储容量*/return return OK;OK;2.2 线性表的顺序存储和操作实现第第2 2章章线性表线性表 2.2.清除顺序表中所有元素，并将顺序表置为空清除顺序表中所有元素，并将顺序表置为空void ClearList_Sq(SqList*L)void ClearList_Sq(SqList*L)if if(L-list)(L-list)free(L-free(L

13、-list);list);/*/*释放顺序表空间释放顺序表空间*/L-L-list=NULL;list=NULL;L-L-length=0;length=0;/*/*空表长度为空表长度为0*/0*/L-L-list_size=0;list_size=0;2.2 线性表的顺序存储和操作实现第第2 2章章线性表线性表9.9.遍历遍历顺序表中的元素顺序表中的元素Status Tranverse_Sq(SqList*L)Status Tranverse_Sq(SqList*L)int j;int j;if(L-length length 1)/*/*顺序表为空顺序表为空*/return ERROR;r

14、eturn ERROR;printf(“The List is:n”);printf(“The List is:n”);for(j=0;j length 1;j+)for(j=0;j length 1;j+)printf(“list%d=%dn”,j,L-listjprintf(“list%d=%dn”,j,L-listj););/*/*此处设元素类型为整型此处设元素类型为整型*/return OK;return OK;2.2 线性表的顺序存储和操作实现第第2 2章章线性表线性表【例例2-12-1】已有一手机通讯录，各联系人信息按照姓名字母顺序递增的方式排列。现需添已有一手机通讯录，各联系人信

15、息按照姓名字母顺序递增的方式排列。现需添加一联系人信息，希望添加后各联系人信息仍按照姓名字母顺序递增的方式排列加一联系人信息，希望添加后各联系人信息仍按照姓名字母顺序递增的方式排列设计设计思路：将手机通讯录用线性表的结构表示，采用顺序存储方式。即将其视为一个顺思路：将手机通讯录用线性表的结构表示，采用顺序存储方式。即将其视为一个顺序表。首先要判断该顺序表中是否还有剩余空间，如已存满，则利用上述序表。首先要判断该顺序表中是否还有剩余空间，如已存满，则利用上述reallocatereallocate函数重新函数重新分配空间；然后在该顺序表中从后往前寻找插入位置，将姓名字母比待插入联系人姓名字母大分

16、配空间；然后在该顺序表中从后往前寻找插入位置，将姓名字母比待插入联系人姓名字母大（靠后）的记录向后移动，然后插入新的联系人信息。（靠后）的记录向后移动，然后插入新的联系人信息。2.2 线性表的顺序存储和操作实现第第2 2章章线性表线性表程序描述如下：程序描述如下：Status Insert_Sq(SqList*L,ElemType*elem)Status Insert_Sq(SqList*L,ElemType*elem)int j;int j;if(L-length=L-list_size)if(L-length=L-list_size)/*/*是否还有剩余空间是否还有剩余空间*/if(rea

17、llocate(L)=ERROR)if(reallocate(L)=ERROR)/*/*重新分配空间是否失败重新分配空间是否失败*/return return ERROR;ERROR;for(j=L-length 1;j=0;j-for(j=L-length 1;j=0;j-)/*-)/*元素（联系人信息）后移元素（联系人信息）后移*/if(strcmp(L-listj.name,elem-name)0)if(strcmp(L-listj.name,elem-name)0)memcpy memcpy(&L-listj+1,&L-listj,sizeof(ElemType);(&L-listj+

18、1,&L-listj,sizeof(ElemType);elseelsebreak;break;/*/*将新元素放入顺序表第将新元素放入顺序表第i i个位置处个位置处*/memcpymemcpy(&L-listj+1,elem,sizeof(ElemType);(&L-listj+1,elem,sizeof(ElemType);L-length+;L-length+;/*/*顺序表长度加顺序表长度加1*/1*/return OK;return OK;2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表线性表的顺序存储只存储数据元素本身的信息，数据元素之间的关系通过物理存储之间线性表的顺

19、序存储只存储数据元素本身的信息，数据元素之间的关系通过物理存储之间的相邻关系来体现，可以实现随机存取，但也存在插入、删除操作不方便等缺点。而线性表的的相邻关系来体现，可以实现随机存取，但也存在插入、删除操作不方便等缺点。而线性表的链式存储通过同时存储数据元素本身的信息和自己的直接后继（或直接前驱）的存储位置，把链式存储通过同时存储数据元素本身的信息和自己的直接后继（或直接前驱）的存储位置，把所有的数据元素链接起来，克服了顺序存储的缺点所有的数据元素链接起来，克服了顺序存储的缺点。在链式存储中，这两部分信息组成的数据元素在链式存储中，这两部分信息组成的数据元素aiai的存储映像，称为结点（的存储

20、映像，称为结点（NodeNode）。其中）。其中存储数据元素本身信息的部分称为数据域；存储其直接后继（或直接前驱）的存储位置信息的存储数据元素本身信息的部分称为数据域；存储其直接后继（或直接前驱）的存储位置信息的部分称为指针域。指针域中存储的信息可以称为指针或链。如部分称为指针域。指针域中存储的信息可以称为指针或链。如图所图所示。示。2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表2.3.1 2.3.1 单链表单链表1.基本概念基本概念每个节点只包含一个指针域的链表称为单链表，也称为线性链表。一般所讲到的单链表，每个节点只包含一个指针域的链表称为单链表，也称为线性链表。一般所讲到的

21、单链表，每个结点的指针域均指向其后继结点，最后一个结点的指针域为空，用每个结点的指针域均指向其后继结点，最后一个结点的指针域为空，用“”表示。一般用表示。一般用图所图所示的形式表示。示的形式表示。单链表单链表2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表 2.存储结构存储结构单链表的结点主要有数据域和指针域两部分，其存储结构可定义如下：单链表的结点主要有数据域和指针域两部分，其存储结构可定义如下：typedef struct nodeElemType data;struct node*next;LNode,*LinkList;ElemType为数据的类型，应用时要用具体的数据类型

22、来代替。为数据的类型，应用时要用具体的数据类型来代替。LNode可定义元素结点，可定义元素结点，LinkList用于定义单链表的头指针。用于定义单链表的头指针。2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表 3.基本操作基本操作（1）初始化单链表）初始化单链表单链表的初始化操作就是创建一个头结点，并返回头指针。如果操作失败则返回单链表的初始化操作就是创建一个头结点，并返回头指针。如果操作失败则返回ERROR，否则返回，否则返回OK。Status Initiate_List(LNode*head)*head=(LinkList)malloc(sizeof(LNode);/*分配内存

23、单元分配内存单元*/if(!*head)printf(“Memory allocate failed!n”);return ERROR;memset(*head,0,sizeof(LNode);return OK;2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表（2）清除单链表中所有结点，并将单链表置为空）清除单链表中所有结点，并将单链表置为空清除单链表中结点时，需要释放结点所占的空间。清除单链表中结点时，需要释放结点所占的空间。void ClearList_List(LinkList head)LNode*p,*q;p=head-next;while(p)/*循环单链表中所有结点

24、循环单链表中所有结点*/q=p;p=p-next;free(q);/*释放结点所占空间释放结点所占空间*/head-next=NULL;2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表（3）判断单链表是否为空，如果为空返回）判断单链表是否为空，如果为空返回1，否则返回，否则返回0引入头结点之后，即可根据头结点的指针域是否为空来判断单链表是否为空。引入头结点之后，即可根据头结点的指针域是否为空来判断单链表是否为空。int ListEmpty_List(LinkList head)if(head-next=NULL)return 1;elsereturn 0;2.3 线性表的链式存储和

25、操作实现第第2 2章章线性表线性表（4）返回单链表的长度，空表则返回）返回单链表的长度，空表则返回0遍历单链表，结点个数即为链表的长度。为了便于查单链表的长度，也可以将其长度存遍历单链表，结点个数即为链表的长度。为了便于查单链表的长度，也可以将其长度存入头结点中的数据域。入头结点中的数据域。int Length_List(LinkList head)LNode*p;int i=0;p=head-next;while(p)i+;p=p-next;return i;2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表（5）返回单链表的第）返回单链表的第i个结点个结点i大于等于大于等于1，并

26、且小于等于单链表长度；如果，并且小于等于单链表长度；如果i超出范围，则返回超出范围，则返回NULL，否则返回第，否则返回第i个个结点的地址。结点的地址。LNode*GetElem_List(LinkList head,int i)LNode*p;int n=1;p=head-next;while(p&n next;return p;2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表（6）查找单链表中第一个数据域为）查找单链表中第一个数据域为elem的结点位置，如果找不到则返回的结点位置，如果找不到则返回-1 int FindElem_List(LinkList head,ElemTy

27、pe elem)LNode*p;int n=1;p=head-next;while(p&p-data!=elem)n+;p=p-next;if(p=NULL)return-1;elsereturn n;2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表（12）遍历单链表中的元素）遍历单链表中的元素void Tranverse_List(LinkList head)LNode*p;p=head-next;printf(“The list is:n”);while(p)printf(“%dt”,p-data);/*此处假设数据域的类型为整型此处假设数据域的类型为整型*/p=p-next;

28、printf(“n”);2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表【例例2-3】已有一手机通讯录，各联系人信息按照姓名字母顺序递增的方式排列。现希已有一手机通讯录，各联系人信息按照姓名字母顺序递增的方式排列。现希望将各联系人信息按照姓名字母顺序递减的方式排列。望将各联系人信息按照姓名字母顺序递减的方式排列。设计思路：将手机通讯录用线性表的结构表示，采用链式存储方式。即将其视为一个单设计思路：将手机通讯录用线性表的结构表示，采用链式存储方式。即将其视为一个单链表。循环该单链表，用头插法将依次将联系人信息插入到另一单链表中即可实现倒序。链表。循环该单链表，用头插法将依次将联系人信

29、息插入到另一单链表中即可实现倒序。2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表程序描述如下：程序描述如下：void Sort_List(RecordList head)/*将将head所指单链表进行排序，并有所指单链表进行排序，并有head返回结果返回结果*/LRecord*p,*p1,*q,*q1;p1=head-next;/*指向单链表的第一个结点（联系人信息）指向单链表的第一个结点（联系人信息）*/head-next=NULL;/*排序后的单链表为空排序后的单链表为空*/while(p1)/*循环所有待排序结点循环所有待排序结点*/p=p1;/*指示要插入到排序后单链表的

30、结点（联系人信息）指示要插入到排序后单链表的结点（联系人信息）*/p1=p1-next;/*待排序的下一个结点（联系人信息）待排序的下一个结点（联系人信息）*/p-next=head-next;/*插入到排序后的单链表的头结点后插入到排序后的单链表的头结点后*/head-next=p;2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表 2.3.2 2.3.2 单向循环链表单向循环链表1.基本概念基本概念将单链表最后一个结点的指针指向头结点或者存储第一个数据元素的结点，从而使整个链将单链表最后一个结点的指针指向头结点或者存储第一个数据元素的结点，从而使整个链表称为一个环，则构成了单向循

31、环链表。因其环形结构，所以从循环链表的任意一个结点出发，表称为一个环，则构成了单向循环链表。因其环形结构，所以从循环链表的任意一个结点出发，均可以访问到其它所有结点。单向循环链表的一个典型应用就是用于约瑟夫环问题。均可以访问到其它所有结点。单向循环链表的一个典型应用就是用于约瑟夫环问题。根据是否有头结点，可分为带头结点的单向循环链表和不带头结点的单向循环链表。带头根据是否有头结点，可分为带头结点的单向循环链表和不带头结点的单向循环链表。带头结点的单向循环链表操作方便，如结点的单向循环链表操作方便，如图所图所示：示：（a）非空表）非空表 （b）空表）空表2.3 线性表的链式存储和操作实现第第2

32、2章章线性表线性表2.基本操作基本操作单向循环链表与单链表的存储结构相同，操作基本相同，区别仅在于建立空表时的初始化单向循环链表与单链表的存储结构相同，操作基本相同，区别仅在于建立空表时的初始化上和判断最后一个结点的条件上：上和判断最后一个结点的条件上：（1）建立）建立空链表时，应将头结点的指针域指向头结点本身；而单链表则置为空。空链表时，应将头结点的指针域指向头结点本身；而单链表则置为空。（2）单向）单向循环链表中没有循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是判断指针指针。涉及遍历操作时，其终止条件就不再是判断指针是否为空，而是判别它们是否等于头指针。是否为空，而是判别它

33、们是否等于头指针。2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表 2.3.3 2.3.3 双向链表双向链表1.基本概念基本概念在单链表中，只有一个指向其后继结点的指针域。因此，从某一个结点出发，很容易找到在单链表中，只有一个指向其后继结点的指针域。因此，从某一个结点出发，很容易找到其后继结点，但却不容易找到其前驱结点。双向链表即在每个节点中有两个指针域，一个指向其后继结点，但却不容易找到其前驱结点。双向链表即在每个节点中有两个指针域，一个指向后继结点。所以，从双向链表中的任意一个结点开始，都可以很方便地找到它的前驱结点和后后继结点。所以，从双向链表中的任意一个结点开始，都可以很方

34、便地找到它的前驱结点和后继结点。继结点。双向双向链表同样可以分为带头结点的双向链表和不带带头结点的双向链表，也可以有双向循链表同样可以分为带头结点的双向链表和不带带头结点的双向链表，也可以有双向循环链表，同样双向循环链表也可以有是否带头结点之分。环链表，同样双向循环链表也可以有是否带头结点之分。（a）非空表）非空表 （b）空表）空表2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表2.存储结构存储结构双向链表的结点主要有数据域和和两个指针，其存储结构可定义如下：双向链表的结点主要有数据域和和两个指针，其存储结构可定义如下：typedef struct duNodeElemType d

35、ata;typedef struct node*prior,*next;DuLNode,*DuLinkList;ElemType为数据的类型，应用时要用具体的数据类型来代替。为数据的类型，应用时要用具体的数据类型来代替。DuLNode可定义元素结点，可定义元素结点，DuLinkList用于定义双向链表的头指针。用于定义双向链表的头指针。2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表3.基本操作基本操作双向链表的初始化、判断是否为空、获取前驱后继结点等操作和单链表的都基本相同，双向链表的初始化、判断是否为空、获取前驱后继结点等操作和单链表的都基本相同，只是在插入、删除操作的时候涉及

36、了前驱指针域。只是在插入、删除操作的时候涉及了前驱指针域。如图如图2-9，在双向链表的，在双向链表的p结点后插入结点结点后插入结点q的主要步骤如下：的主要步骤如下：（1）q-prior=p；（2）q-next=p-next；（3）if(p-next)p-next-prior=q；（4）p-next=q；2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表（a）插入前）插入前（b）插入后）插入后2.3 线性表的链式存储和操作实现第第2 2章章线性表线性表如如图所图所示，删除双向链表中示，删除双向链表中p所指结点的主要步骤如下：所指结点的主要步骤如下：（1）p-prior-next=p-；

37、（2）if(p-next)p-next-prior=p-prior；（3）free(p)；（a）删除前）删除前（b）删除后）删除后小结第第2 2章章线性表线性表本章本章依次讲解了线性表的定义、特征、存储结构、基于不同存储结构的基本操作实现等知依次讲解了线性表的定义、特征、存储结构、基于不同存储结构的基本操作实现等知识。识。所谓线性表是指一组具有相同特征的数据元素的有限序列。具有顺序存储和链式存储两种所谓线性表是指一组具有相同特征的数据元素的有限序列。具有顺序存储和链式存储两种存储结构。其中顺序存储是一种随机存取结构，链式存储是一种顺序存取结构。了解存储结构存储结构。其中顺序存储是一种随机存取结

38、构，链式存储是一种顺序存取结构。了解存储结构的特点是学习相应地操作实现的前提。的特点是学习相应地操作实现的前提。顺序表和单链表的相关操作是线性表知识在现实生活中最重要的应用之一。它们进行插入、顺序表和单链表的相关操作是线性表知识在现实生活中最重要的应用之一。它们进行插入、删除操作的时间复杂度都为删除操作的时间复杂度都为O（n）。若要频繁查找却很少进行插入和删除操作，或其操作和）。若要频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若要频繁插入和删除时，则宜采元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若要频繁插入和删除时，则宜采用单链表做存储结构。当线性表中元素个数变化较大或者未知时，宜使用单链表实现；而如果用单链表做存储结构。当线性表中元素个数变化较大或者未知时，宜使用单链表实现；而如果事先知道线性表的大致长度，使用顺序表的空间效率会更高。总之，线性表的顺序表和单链表事先知道线性表的大致长度，使用顺序表的空间效率会更高。总之，线性表的顺序表和单链表各有优缺点，应根据具体应用来选择存储方式。各有优缺点，应根据具体应用来选择存储方式。感谢收看