下载文档原格式
线性表知识点总结线性表是数据结构中最基本、最简单的数据结构之一，它在计算机科学和程序设计中有着广泛的应用。
接下来，让我们一起深入了解线性表的相关知识。
一、线性表的定义线性表是由零个或多个数据元素组成的有限序列。
其中，每个数据元素的类型相同，并且在逻辑上是线性排列的。
也就是说，除了第一个元素外，每个元素都有且仅有一个直接前驱；除了最后一个元素外，每个元素都有且仅有一个直接后继。
例如，一个整数序列 10, 20, 30, 40, 50 就是一个线性表。
在这个序列中，10 是第一个元素，没有前驱；50 是最后一个元素，没有后继；而 20 的前驱是 10，后继是 30 。
二、线性表的特点1、元素个数有限：线性表中的元素个数是确定的，不能是无限的。
2、元素具有相同的数据类型：这使得对线性表的操作可以统一进行，方便编程实现。
3、元素之间的顺序是线性的：元素按照一定的顺序排列，每个元素都有确定的前驱和后继关系（除了首元素和尾元素）。
三、线性表的存储结构线性表有两种常见的存储结构：顺序存储结构和链式存储结构。
1、顺序存储结构顺序存储结构是指用一组地址连续的存储单元依次存储线性表中的数据元素。
在顺序存储结构中，逻辑上相邻的元素在物理位置上也相邻。
优点：（1）可以随机访问表中的任意元素，时间复杂度为 O(1)。
（2）存储密度高，不需要额外的指针来表示元素之间的关系。
缺点：（1）插入和删除操作需要移动大量元素，时间复杂度为 O(n)。
（2）存储空间大小需要预先分配，如果分配过大，会造成空间浪费；如果分配过小，可能导致溢出。
2、链式存储结构链式存储结构是通过指针将各个数据元素链接起来存储。
每个节点包含数据域和指针域，数据域用于存储数据元素的值，指针域用于指向下一个节点的地址。
优点：（1）插入和删除操作不需要移动大量元素，只需修改指针，时间复杂度为 O(1)。
（2）存储空间可以动态分配，不会造成空间浪费或溢出。
缺点：（1）不能随机访问，只能通过指针顺序访问，时间复杂度为O(n)。
数据结构线性表总结线性表是一种常见的数据结构，它是由一系列元素组成的序列，其中元素的顺序是固定的。
线性表可以通过一维数组或链表来实现，在实际应用中起到了重要的作用。
本文将对线性表进行总结，包括线性表的定义、基本操作、常见实现方式以及一些应用场景。
一、线性表的定义线性表是由n（n>=0）个数据元素a[1]，a[2]，，a[n]组成的有限序列。
其中，元素a[i]所在的位置称为索引i，索引从1开始递增，最大到n。
线性表可以为空表，即n为0的情况。
二、线性表的基本操作⒈初始化操作：创建一个空的线性表，为后续的操作做准备。
⒉插入操作：在线性表的某个位置插入一个元素，需要考虑插入位置的合法性和元素的移动。
⒊删除操作：删除线性表中指定位置的元素，同样需要考虑合法性和元素的移动。
⒋查找操作：根据指定位置或者指定元素值查找线性表中的元素，查找到后可以返回位置或者元素的值。
⒌修改操作：根据指定位置或者指定元素值修改线性表中的元素。
⒍遍历操作：按照顺序访问线性表中的每个元素。
三、线性表的实现方式常见的线性表实现方式有两种：一维数组和链表。
⒈一维数组实现：一维数组是最简单的实现方式，每个元素的存储位置是连续的，可以直接通过下标进行访问。
但是数组的长度固定，删除和插入操作需要进行元素的移动，效率较低。
⒉链表实现：链表是通过节点之间的引用关系形成的动态数据结构。
除了数据部分，每个节点还包含指向下一个节点的引用。
链表的长度可以动态调整，插入和删除操作只需要改变节点的引用，效率较高。
常见的链表类型有单链表、双向链表和循环链表。
四、线性表的应用场景线性表在实际应用中有着广泛的应用场景，包括但不限于以下几种：⒈线性表作为数据结构的基础，被广泛应用在各种编程语言中，用于存储和操作数据。
⒉链表可以用于实现其他数据结构，如栈和队列。
⒊线性表可以用来存储字符串或者文本文档的内容，方便进行增删改查等操作。
⒋在图论中，线性表可以用来存储路径信息，便于实现图的遍历算法。
线性表的概念
线性表是计算机科学中一种重要的数据结构，广泛应用于各种计算任务的解决。
它定义为一种有序的存储结构，由一系列相同数据类型的元素组成，可以顺序访问和操作，元素可以通过索引来查找和修改。
线性表的数据结构特征主要有以下几点：
（1）顺序存储。
线性表中元素是有序排列的，每个元素在内存中都有一个固定的地址。
（2）单向链接。
线性表中的元素只有一个指针，只能指向它的下一个元素，形成一个单向链表，使其更容易进行插入和删除操作。
（3）元素类型。
线性表中的元素类型可以是任何类型的数据，甚至可以是结构体或联合体。
（4）存储量受限。
线性表只能存储有限数量的元素，超出它的存储量后可能要重新分配存储空间，降低程序的效率。
线性表有很多应用场景，比如用于存储处理图形信息的图算法，编码解码软件，操作系统的程序管理，数据库的索引查询等。
线性表的应用场景受到数据结构的影响，有时需要考虑复杂度和存储空间等问题。
近年来，有关线性表的研究也取得了显著进展。
举例来说，基于线性表的静态分析和动态编程技术，利用静态分析技术可以更好地识别和分析程序代码中的控制流和数据流，有效提高程序的性能。
而动态编程技术则可以在线性表中根据元素间的函数关系来构造更加高
效的程序。
总之，线性表是计算机科学中一种重要的数据结构，具有良好的灵活性，可以满足各种程序处理的需求。
由于线性表的易学性和多样性，它被广泛用于计算任务的实现中。
数据结构线性表数据结构线性表1. 概述线性表是一种常用的数据结构，它是一种有序的数据元素集合，其中的每个元素都有唯一的前驱和后继。
线性表中的数据元素分为两类：首元素和末元素。
线性表的实现方式多种多样，例如数组、链表、栈和队列等。
这些实现方式在不同的场景中具有不同的优势和劣势。
本文将介绍线性表的定义、常用操作和常见实现方式，帮助读者更好地理解和应用线性表。
2. 定义线性表的定义如下：```markdown线性表是由 n (n ≥ 0) 个数据元素组成的有限序列。
其中，n 表示线性表中元素的个数，当 n = 0 时，表示线性表为空表。
```3. 常用操作线性表是一种常见的数据结构，其常用的操作包括插入、删除、查找和遍历等。
3.1 插入操作插入操作用于向线性表的指定位置插入一个元素。
假设线性表中有 n 个元素，插入操作的时间复杂度为 O(n)，其中 n 表示线性表中元素的个数。
3.2 删除操作删除操作用于从线性表中删除指定位置的元素。
假设线性表中有 n 个元素，删除操作的时间复杂度为 O(n)，其中 n 表示线性表中元素的个数。
3.3 查找操作查找操作用于在线性表中查找指定元素的位置。
假设线性表中有 n 个元素，查找操作的时间复杂度为 O(n)，其中 n 表示线性表中元素的个数。
3.4 遍历操作遍历操作用于依次访问线性表中的每个元素。
假设线性表中有n 个元素，遍历操作的时间复杂度为 O(n)，其中 n 表示线性表中元素的个数。
4. 实现方式线性表的实现方式有多种，常见的包括数组和链表。
4.1 数组实现数组是一种简单而有效的实现线性表的方式。
它将线性表中的元素按顺序存储在一块连续的内存空间中，可以通过下标访问任意位置的元素。
数组实现的优势是访问元素的时间复杂度为 O(1)，插入和删除元素的时间复杂度为 O(n)。
4.2 链表实现链表是另一种常用的实现线性表的方式。
链表由一系列的节点组成，每个节点包含数据和指向下一个节点的指针。
第三章线性表3.1线性表的类型定义3.2顺序存储的线性表3.3链式存储的线性表3.4有序表3.5顺序表和链表的综合比较3.1线性表的类型定义3.1.1线性表的定义线性表是n(n>=0)个数据元素的有限序列，表中各个元素具有相同地属性，表中相邻元素间存在“序偶”关系。
,a2,…….a i-1,a i,a i+1,…,a n-1,a n)记做：(a1a i-1称为a i的直接前驱元素，a i+1是a i的直接后继元素/线性表的长度：表中的元素个数n位序：i称元素ai在线性表中的位序3.1.2线性表的基本操作InitList(&L)Destroy(&L)ClearList(&L)ListEmpty(L)ListLength(L)GetElem(L,i,&e)1<=i<=ListLength(L)LocateItem(L,e)PriorElem(L,Cur_e,&pre_e)NextElem(L,cur_e,&next_e)ListInsert(&L,i,e)1<=i<=ListLength(L)+1 ListDelete(&L,i,&e)1<=i<=ListLength(L)ListTraverse(L)【例3.4】对两个线性表La、Lb表示的集合A和B，求一个新集合A＝AUB算法3.1a)从Lb中取一个元素，并删除b)在La中查询c)若La中不存在，则将其插入La，重复直至Lb空【例3.5】对两个线性表La、Lb表示的集合A和B，求A=A-B算法3.2a)从Lb中取一个元素，并删除b)在La中查询c)若La中存在，则将从La删除，重复直至Lb空3.2线性表的顺序表示和实现3.2.1顺序表——线性表的顺序存储表示Const LIST_INIT_SIZE=100;(C++规范) Const LISTINCREMENT=10;#define LIST_INIT_SIZE100(C规范) typedef struct{Elemtype*elem;int length;int listsize;int incrementsize;}SqList;3.2.2顺序表中基本操作的实现初始化操作InitList_Sq算法3.3销毁操作DestroyList_Sq算法3.4是否为空ListEmpy_Sq算法3.5是否满ListFull_Sq算法3.6求长度ListLength_sq算法3.7查找元素操作LocateElem_Sq算法3.8获取元素操作GetItem_Sq算法3.9插入元素操作ListInsert_Sq算法3.10时间复杂度O(n)删除元素操作ListDelete_Sq算法3.11时间复杂度O(n)插入和删除操作的时间分析：Ein=Σpi(n-i+1)=n/2Edl=Σqi(n-i)=(n-1)/2查找元素操作算法3.8时间复杂度O(n)例如：顺序表23 75 41 38 54 62 17L.elem L.length = 7L.listsizee =38p pp p pi 12348e =50p 返回值= 4返回值= 0(a 1, …,a i-1,a i , …, a n ) 改变为a 1a 2…a i-1a i …a n a 1a 2…a i-1…a i e a n<a i-1, a i ><a i-1, e>, <e, a i >表的长度增加(a 1, …,a i-1, e,a i , …, a n )插入元素操作算法3.10时间复杂度O(n)删除元素操作算法3.12时间复杂度O(n)(a 1, …,a i-1,a i ,a i+1, …, a n ) 改变为a i+1…a n<a i-1, a i >, <a i , a i+1><a i-1, a i+1>表的长度减少a 1a 2…a i-1a i a i+1 …a n a 1a 2…a i-1(a 1, …,a i-1,a i+1, …, a n )3.2.3顺序表其它算法举例例3.6用顺序表表示集合，完成例3.4。
算法3.13时间复杂度O(n2)例3.10用尽量少得辅助空间将前m个元素和后n 个元素互换–算法3.25exchange1时间复杂度：O(m×n)–算法3.26invert时间复杂度：O(t-s+1)–算法3.27exchange2时间复杂度：O(m+n)3.3线性表的链式表示和实现3.3.1单链表和指针数据域（data）和指针域（next）存储表示typedef struct Lnode{ElemType data;Struct Lnode*next;}Lnode,*LinkList;单链表种类不带头结点单链表带头结点单链表p pp=qq p p=q →nextp p=p→nextqpp→next=qqpp→next=q→next常见指针操作3.3.2单链表的基本操作求线性表的长度算法3.15时间复杂度：O(n)查找元素操作算法3.16时间复杂度：O(n)插入结点操作：前插、后插算法3.17时间复杂度：前插O(n)、后插O(1)删除结点操作算法3.18时间复杂度O(n)逆序创建链表时间复杂度O(n)L∧epdp c p b p a p ∧3.3.3单链表的其它操作举例逆置单链表时间复杂度O(n)逆置线性链表psLa1a2a3a4∧L∧pa1∧s pa2s pa3s pa 4以单链表表示集合，完成例3.1算法3.19时间复杂度O(m×n)void union_L(LinkList&La,LinkList&Lb){ if(!La)La=Lb;return;while(Lb){s=Lb;Lb=Lb->next;p=La;while(p&&p->data!=s->data){pre=p;p=p->next;}//whileif(p)delete s;else{pre->next=s;s->next=NULL;} }//while(Lb)}// union_L【算法改进】Lb中元素只需要和原La元素比较void union_L(LinkList&La,LinkList&Lb){if(!La)La=Lb;return;pa=La;while(Lb){s=Lb;Lb=Lb->next;p=pa;while(p&&p->data!=s->data)p=p->next;if(p)delete s;else{s->next=La;La=s}}//while(Lb)}// union_L3.3.4循环链表什么是循环链表–通常增加头结点–最后一个结点的指针指向头结点–头指针指向最后一个结点–空的循环链表是头结点自循环判断表尾的循环条件：–不是p==NULL，而是p是否等于头指针的next域。
单循环链表3.3.5双向链表概念：两个指针，分别指向前驱和后继typedef struct DuLnode{ElemType data;Struct DuLnode*prior; Struct DuLnode*next;}DuLnode,*DuLinkList;双向循环链表单链表的实际应用改进typedef struct{LinkList head,tail;int length;}AdvancedLinkList;例3.8改写逆序创建链表算法：算法3.23 L.head=NULL;for(i=n-1;i>=0;i--){s=new LNode;s->data=A[i];s->next=L.head;L.head=s;if(i=n-1)L.tail=s;L.length++;}3.4有序表什么是有序表数据元素在线性表中依值非递减或非递增的插入结点操作时间复杂度O(n)例3.9以顺序表表示集合，完成集合的纯化算法3.24时间复杂度O(n)ij 888755433322111098765432102ij j i3j j ji4ji5jji7ji8jjj例3.11两个带头结点的循环有序链表，表示集合A、B，完成C=A U B算法3.28复杂度O(n+m)思考：在头元素中放最大元素MAX简化操作,时间复杂度O(n+m),时间略长，算法表达略简单类似：两个带头结点的有序单链表，表示集合A、B，判断A=B?对比：无序表完成同样功能的时间复杂度为O(n*n)rc5La(a)81822528122245Lbpapb5La(b)818225212453.5顺序表和链表的综合比较•线性表的长度能否预先确定？处理过程中变化范围如何？–长度确定、变化小时用顺序表–长度变化大、难以估计最大长度时宜采用链表•对线性表的操作形式如何？–查询操作多、删除和插入操作少时使用顺序表–频繁插入和删除操作宜采用链表谢谢void union( List &La, List &Lb){La_len=ListLength(La); // 求La的长度while(!ListEmpty(Lb)) // 循环处理Lb中的元素ListDelete(Lb,1,e); // 删除Lb中第一个元素并赋予e If(!LocateItem(La,e))ListInsert(La,++La_len,e);//若e不在La中则插入La的最后一个元素后面}//end whileDestroyList(Lb);}//end unoinvoid minus( List &La, List &Lb){while(!ListEmpty(Lb)) // 循环处理Lb中的元素ListDelete(Lb,1,e); // 删除Lb中第一个元素并赋予e If((i=LocateItem(La,e))!=0)ListDelete(La,i,e);//若e在La中则从La中删除}//end whileDestroyList(Lb);}//end minusvoid InitList_sq(SqList &L,intmsize=LIST_INIT_SIZE){ //构造一个容量是msize的顺序表LL.elem=new ElemType[msize];L.listsize=msize; //顺序表的最大容量L.length=0; // 顺序表初始时的元素数是0 }// end InitList_sq算法3.4void DestroyList_sq(SqList &L) {//销毁顺序表Ldelete [] L.elem; // 释放数组空间L.length=0;L.listsize=0;}// end DestroyList_sq算法3.5 /3.6/ 3.7 bool ListEmpty_sq(SqList L){return (L.lenth==0);}bool ListFull_sq(SqList L){return (L.lenth==L.listsize);}int ListLength_sq(SqList L){return L.lenth;}int LocateItem_sq(SqList L,Elemtype e){//在顺序表L中查找第一个值为e的元素，若找到则返回位序，否则返回0.for(i=1;i<=L.length;i++) //依次查找每个元素if(L.elem[i-1]==e)return i; //找到位序为i的元素return 0; //没有找到值为e的元素}// end LocateItem_sqvoid GetItem_sq(SqList L,int i,Elemtype &e) {//将顺序表L中位序为i的元素值赋予e.e=L.elem[i-1];}// end GetItem_sq算法3.10void ListInsert_sq(SqList &L，int i，Elemtype e) {//在顺序表L中位序为i的元素前插入一个新的元素e //同时需要考虑i的合法性和满状态if(i<1||i>L.length+1){ErrorMsg(“i值非法！”);return;}if(L.length==L.listsize)Increment(L); //当前L已满for(j=L.length-1;j>=i-1;j--) //由后往前逐个后移元素L.elem[j+1]=L.elem[j];L.elem[i-1]=e; //在L.elem[i-1]放入e ++L.length;}// end ListInsert_sq算法3.11#define LIST_INC_SIZE 20void Increment(SqList &L，intinc_size=LIST_INC_SIZE){ //增加顺序表L的容量为listsize+inc_size ElemType *a;a=new ElemType[L.listsize+inc_size];if(!a){ErrorMsg(“分配内存错误！”);return;}for(i=0;i<L.length;i++)a[i]=L.elem[i];delete [] L.elem; // 释放原数组空间L.elem=a; // 将新的数组赋予顺序表的指针L.listsize+=inc_size; // 顺序表的容量增加inc_size}// end ListInsert_sq算法3.12void ListDelete_sq(SqList &L，int i，Elemtype &e) {//从顺序表L中删除位序为i的元素并把值赋予eif(i<1||i>L.length){ErrorMsg(“i值非法！”);return;} e=L.elem[i-1]; //保存L.elem[i-1]到e for(j=i;j<=L.length-1;j++) //由前往后逐个前移L.elem[j-1]=L.elem[j];L.length--;}// end ListDelete_sq算法3.13void Union_sq(SqList &La，SqList &Lb){//实现顺序表A和B所表示的集合的并，结果放在A，销毁B for(i=0;i<Lb.length;i++){ //逐个处理Lb的元素e=Lb.elem[i]; //取Lb中第i个元素j=0;while(j<La.length&&La.elem[j]!=e)++j; //在La中查找eif(j==La.length){ //La中没有找到eLa.elem[La.length]=e; //e插入到La的最后La.length++; //La长度增加1 }//if}//fordelete [] Lb.elem; //释放Lb内存Lb.length=0;Lb.listsize=0;}// end Union_sqvoid InitList_L(LinkList &L) {//初始化链表LL=NULL;}// end InitList_LInt ListLength_L(LinkList L) {//求链表L的长度p=L;k=0;while(p){k++;p=p->next;}//whilereturn k;}// end ListLength_LLNode * LocateItem_L(LinkList L,ElemType e) {//在链表L中查找元素ep=L;while(p&&p->data!=e)p=p->next; return p;}// end LocateItem_L算法3.17void ListInsert_L(LinkList &L,LNode *p，LNode *s) {//在链表L中，在p所指结点前插入s所指的结点if(p==L){ //p是第一个结点s->next=L; L=s;}//ifelse { //p不是第一个结点q=L;while(q&&q->next!=p)q=q->next;//找后继是p 的结点if(q){q->next=s;s->next=p;} //在p前插入selse ErrorMsg(“p不是L中的结点”);}//else}// end ListInsert_L算法3.18void ListDelete_L(LinkList &L,LNode *p，ElemType &e) {//在链表L中，删除p所指结点if(p==L)L=p->next; //p是第一个结点else { //p不是第一个结点q=L;while(q&&q->next!=p)q=q->next;//找后继是p的结点if(q)q->next=p->next; //使p的原前驱直接指向p的后继else ErrorMsg(“p不是L中的结点”); // p不在L中}//elsee=p->data;delete p; //保存被删除的元素值，释放空间}// end ListDelete_L算法3.24void Purge(SqList &L){//把顺序有序表L中相同的元素删除。
