目录

线性表

线性表的定义

非空线性表的常见概念

表名

表头元素

表尾元素

前驱

后继

结点 位序

线性结构的特点

顺序性

有限性

相同性

抽象性

线性表的存储

顺序表

顺序表的定义

线性表的存储位置

随机存取

顺序表的定义与初始化

C/C++顺序表创立写法

JAVA顺序表创立写法

python顺序表创立写法

顺序表的基本操作

查找

按位序查找（取值）

按值查找

插入

插入操作的代码实现

删除

删除的代码实现

链表

单链表

顺序表内存图

单链表内存图

单链表的定义与表示

结点

数据域

指针域

指针 链、链表

头指针

单链表-定义

尾插法

头结点

首元结点

头插法

单链表-查找

按值查找

按位序查找

单链表-插入

单链表-删除

双向链表

前驱指针

后继指针

双链表-插入

双链表删除

循环链表

循环单列表

循环双链表

线性表

所有数据结构中最常用的是线性表（Liner List）

线性表的定义

由n(n>=0)个相同数据类型的数据元素组成的有限序列

n=0时，线性表中无任何数据元素，称为空表

注：数据元素也可以为结构体类型

比如：（地址：0~专业：计算机科学与技术）这一排整体作为一个数据元素存入线性表，那么这个线性表之后存储的所有数据元素都必须得是该结构体类型

非空线性表的常见概念

记非空线性表：

表名

L即线性表的表名

表头元素

线性表内的第一个数据元素，亦称表头元素，即

表尾元素

线性表内的最后一个数据元素，亦称表尾元素，即

前驱

对于线性表内某元素，它前面的元素称为它的直接前驱，简称前驱。

后继

对于线性表内某元素，它后面的元素称为它的直接后继，简称后继。

结点 位序

对于线性表内某元素，下标是其结点，亦称位序

如此线性表，记：

为其表名，为表头元素，后继为，且无前驱；对于元素而言，其结点为，（直接）前驱为，（直接）后继为；表尾元素为，前驱为，无后继

线性结构的特点

顺序性

顺序性（序列）：元素具有线性顺序，除第一个数据元素无前驱、最后一个数据元素无后继之外，其他每个数据元素均有一个前驱和一个后继

有限性

有限性（有限）：元素个数有限，在计算机中处理的对象都是有限的

相同性

相同性（相同特性）：所有数据元素的类型相同，即数据元素来自于同一数据对象

抽象性

抽象性（元素类型不确定）：数据元素的类型需要根据实际的具体问题而确定，在定义中是不具体的，而是抽象的

线性表的存储

顺序表

从逻辑结构上分析了线性表的概念和特性后，应当考虑其实际应用，为此引入顺序表

线性表-逻辑结构

顺序表-存储结构

顺序表的定义

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这 种表示也称作线性表的顺序存储结构或顺序映像。

通常，称这种存储结构的线性表为顺序表 （Sequential List）。

其特点：逻辑上相邻的数据元素，其物理位置也是相邻的。

如图中绿色阴影的,其逻辑上是线性表：。将其依次存放入内存中一段连续的存储空间里为

这表明：逻辑上相邻的数据元素，其物理位置也是相邻的。

线性表的存储位置

元素是相邻的并不代表每个元素在地址上相差1，其实际取决于元素的类型所占地址的大小。

设表头元素的存储位置为，每个元素占的存储单元为.

则有顺序表的存储位置关系与满足：

随机存取

顺序表可以通过存储位置公式通过下标访问任一位置上的元素。这个特性叫做：线性表的随机存取

如上图一维数组就是按照这个特性来访问对应元素的。

顺序表的定义与初始化

我们需要用顺序表来存放一些数据元素，于是我们需要给出顺序表的长度上限，其代表最多可以存储多少个元素；长度上限是静态的，一般记

//定义顺序表的上限，100代表其最多可以存储的元素个数，可以根据实际调整 #define MAXSIZE 100 int data[MAXSIZE];

但是我们不是必须需要填满整个顺序表，一个最大长度为10的顺序表，我只需要存储8个元素，剩下的两个位置是空的，目前不需要。于是这个表的实际长度为8，我们需要用一个变量来专门存储它，于是将它称为长度，长度是动态的，其合法区间为：

记：

int length;//记录顺序表的实际长度

我们将其封装在一起，定义一个结构体

C/C++顺序表创立写法

#define MAXSIZE 100 typedef struct{ int data[MAXSIZE]; int length; // int length = 0;初始化，创建一个空表 }Sqlist;

JAVA顺序表创立写法

public class SqList{ public static final int MAXSIZE = 100;//等价#define MAXSIZE 100 public int data[];//等价 int data[MAXSIZE]; public int length;//等价 int length; } public SqList{ this.data = new int[MAXSIZE]; this.length = 0; }

• Java 中数组必须在运行时分配，所以用new int[MAXSIZE]初始化。

• length需要显式赋初值 0，Java 中 int 成员默认就是 0，但显式写出更清晰。

• MAXSIZE用static final表示常量。

python顺序表创立写法

class SqList: MAXSIZE = 100 def __init__(self): self.data = [] def length(self): return len(self.data)

例1

通过输入函数定义一个长度L为5的顺序表，并依次填入元素1，2，3，4，5

C++版

#include <stdio.h> #define MAXSIZE 100//定义最大长度 typedef struct{ int data[MAXSIZE];//定义data数组存储数据 int length;//定义实际存储长度 }SqList; int main(){ SqList L;//调用结构体L int num; printf("请定义顺序表的实际长度L："); scanf("%d",&L.length); printf("请填入顺序表的%d个元素：\n",L.length); for(num = 0;num<L.length;num++){ scanf("%d",&L.data[num]); } printf("顺序表打印："); for(num = 0;num<L.length;num++){ printf("%d ",L.data[num]); } } /* 请定义顺序表的实际长度L：10 请填入顺序表的10个元素： 1 2 3 4 5 6 7 8 9 10 顺序表打印：1 2 3 4 5 6 7 8 9 10

Java版

import java.util.Arrays; import java.util.Scanner; public class SqList { public static final int MAXSIZE = 10; public int[] data; public int length; @Override public String toString() { return "SqList{" + "data=" + Arrays.toString(data) + ", length=" + length + '}'; } public SqList(){ data = new int[MAXSIZE]; System.out.println("请输入顺序表的实际长度L："); Scanner sc = new Scanner(System.in); length = sc.nextInt(); System.out.println("请录入顺序表的元素："); for(int i=0;i<length;i++){ data[i]=sc.nextInt(); } } public static void main(String[] args) { SqList sl = new SqList(){}; System.out.println(sl); } } /* 10 请录入顺序表的元素： 1 2 3 4 5 6 7 8 9 SqList{data=[9, 1, 2, 3, 4, 5, 6, 7, 8, 9], length=10} */

python的C风格：

class SqList: MAXSIZE = 100 # 保留这个常量，只是为了对应教材概念，实际上 Python 不需要 def __init__(self, data=None): # 直接使用 list 作为底层存储 self.data = list(data) if data else [] # 可选：如果你非要限制最大长度 if len(self.data) > self.MAXSIZE: raise OverflowError("超出最大长度限制") # 像内置 list 一样使用 len(L) def __len__(self): return len(self.data) # 支持下标访问 L[0] def __getitem__(self, index): return self.data[index] # 支持 print(L) 直接打印 def __repr__(self): return "[" + ", ".join(map(str, self.data)) + "]" # 支持 print(L) 友好输出 def show(self): print("顺序表内容为:", *self.data) print("带下标形式:", end=" ") for i, v in enumerate(self.data): print(f"[{i}]={v}", end=" ") print() def main(): # 读取数据 nums = list(map(int, input("请输入顺序表元素(空格分隔): ").split())) # 实例化顺序表 L = SqList(nums) # 使用内置 len() print(f"当前顺序表长度为: {len(L)}") # 打印 L.show() # 支持下标访问 if len(L) > 0: print(f"第一个元素是: {L[0]}") if __name__ == "__main__": main()

标准pythpon风格

def main(): # 1. 一行读入多个整数，存入列表（这就是顺序表） # 比如输入: 1 2 3 4 5 data = list(map(int, input("请输入顺序表元素(空格分隔): ").split())) # 2. 打印整个顺序表 print("顺序表内容为:", *data) # * 是解包，自动空格分隔 # 或者用更严格的格式：print("顺序表内容为:", " ".join(map(str, data))) # 3. 带下标打印 print("带下标形式:", end=" ") for i, v in enumerate(data): print(f"[{i}]={v}", end=" ") print() if __name__ == "__main__": main()

顺序表的基本操作

查找

查找操作是根据指定的元素值e，查找顺序表中第1个值与e相等的元素。 若查找成功，则返回该元素在表中的位置序号；若查找失败，则返回0

按位序查找（取值）

找第个元素：

根据随机存储的特性，时间复杂度为：

arr[10] = {1,2,3,4,5,6,7,8,9,0}; printf("%d",arr[0]); //结果：1

按值查找

按值查找的过程：设要找的元素为

每次自表头元素开始遍历，将与顺序表内元素逐个比对，直到找到第一个对应元素为止，找到返回下标，未找到返回-1

当这个数不存在于这个顺序表内或者在顺序表末尾时，都一共比对了次，当这个数在表头元素时，只比较了1次

则最好情况下的时间复杂度：

则最坏情况下的时间复杂度：

对于其平均时间复杂度，假设遍历次，元素依次在表头元素，第二个元素，...，表尾元素，当依次查找次数为：、、、...、，总次数为：

故平均时间复杂度为：

即：

顺序表按值查找的效率为：

C++语言风格：

int find(SqList L,int e){ for(int i =0;i<L.length;i++){ if(L.data[i] == e){ return i+1;//找到返回下标 } } return -1;//否则返回-1 }

例·

#include <stdio.h> #define MAXSIZE 100 typedef struct{ int data[MAXSIZE]; int length; }SqList; int find(SqList L,int e){//定义查找内容函数，形式参数为L和需找元素e for(int i =0;i<L.length;i++){ if(L.data[i] == e){ return i+1;//能找到返回位序i+1 } } return -1;//否则返回-1 } int main(){ SqList L; int num; printf("请定义顺序表的实际长度L："); scanf("%d",&L.length); printf("请填入顺序表的%d个元素：\n",L.length); for(num = 0;num<L.length;num++){ scanf("%d",&L.data[num]); } printf("顺序表打印："); for(num = 0;num<L.length;num++){ printf("%d ",L.data[num]); } printf("\n"); printf("位序：%d\n",find(L,5));//调用find函数 return 0; } /* 请定义顺序表的实际长度L：10 请填入顺序表的10个元素： 1 2 3 4 5 6 7 8 9 0 顺序表打印：1 2 3 4 5 6 7 8 9 0 位序：5 */

插入

如图data数组长度为length = 5，存储着5个元素,现令，直接表示存储数据元素个数。

执行操作操作，比如在索引0处的元素7插入新元素-1，那么原先的所有元素整体右移1位，共有5个元素，那么整体一共移动5*1=5次。插入操作可在顺序表表尾元素后面直接插入新元素，这个叫做追加，那么长度为的顺序表可操作的元素个数为：

类似python的：

lst = [] lst.append(0)

那么设data数组存在个数据元素。

最优时间复杂度：当在表尾元素插入新元素后，仅需移动表尾元素，即移动1次；或者插入表尾元素后面的空位，此时序列的操作也是1次

则时间复杂度为：

最劣时间复杂度：当在表头元素插入新元素后，需要移动个元素

则时间复杂度：

平均时间复杂度：对于个可操作元素

插入第个元素，移动次

插入第个元素，移动次

...

插入第个元素，移动次

插入第个元素（追加），移动次

则平均时间复杂度为：

即：

插入操作的代码实现

在顺序表第个元素（位序：）插入新元素

设为元素的位序，为长度，为上限，为索引.

那么当表示顺序表空间已满，无法再插入

表示越界

皆非法

于是代码逻辑应为：

if(L.length == MAXSIZE) return false; if(i<1 || i>L.length+1) return false; //增强代码的健壮性（鲁棒性）

那么在合法范围内,索引为的元素当右移到的元素上

for(j=L.length-1;j>=j-1;j--){ L.data[j+1] = L.data[j];//将第j个元素后移一位到j+1 } L.data[i-1] = e;//将指定元素e插入第i个元素 L.length++;//插完后，表尾元素将会右移1位，那么必须将length增1

C++代码：

//在元素i位置插入新元素e bool Insert(SqList &L,int i,int e){//需要插入的顺序表L，插入的位置i，插入的元素e //&引用符表示对顺序表L的修改，若为SqList L,那么实际参数L仅仅传递副本给形式参数L if(L.length == MAXSIZE) return false; if(i<1 || i>L.length+1) return false; //从表尾元素~要移动的元素依次后移1位 for(int j = L.length-1;j>=i-1;j--){ L.data[j+1] = L.data[j];//先移动 } L.data[i-1] = e;//后将元素e插入位序i L.length++; return true; }

删除

设顺序表：

当我们需要删除元素，比如删除元素，那么顺序表为：，那么自的元素都得从后向前移一位

继续考虑时间复杂度

最优时间复杂度：当我们要删除末尾的元素，那么其前面的所有元素都保持不动即可，那么此时的时间复杂度为：

最劣时间复杂度：当我们需要删除表头元素时，的元素都得向前移动次

那么时间复杂度为：

平均时间复杂度：删除表头元素(第1个)需要移动次，删除第二个元素需要移动次,...,删除表尾元素(第n个)需要移动次，对于一共个元素而言的平均时间复杂度：

即：

删除的代码实现

在顺序表中删除第个元素（位序：）

设为元素的位序，为长度，为索引.

先考虑非法位序：

if(i<1 || i>L.length) return false;

将元素通通向前移动1位

for(int j = i;j <= L.length-1;j++){ L.data[j-1] = L.data[j]; } L.length--;

//删除位序为i的元素 bool Delete(SqList &L,int i){ if(i<1 || i>L.length) return false; for(int j=i;j<=L.length;j++){ L.data[j-1] = L.data[j]; } L.length--;//第j个元素移动到了j-1，那么第j各元素位置为空，执行本行代码删除这一位置 }

链表

线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储 单元可以是连续的，也可以是不连续的）

单链表

顺序表内存图

单链表内存图

顺序表的存储是连续的，逻辑、物理上都是相邻的。这有利于它随机存储()，但插入、删除操作却比较复杂（）。为此引入单链表。

单链表的定义与表示

结点

对于某一个元素而言，在单链表中除了存储该元素的本身信息外还需要记录元素与其直接后继元素的逻辑关系。这两部分信息组成数据元素ai的存储映像，称为结点

数据域

存储数据元素信息的域叫做数据域

指针域

存储该元素的直接后继存储位置的域叫做指针域

指针 链、链表

指针域的内容叫做指针或链

n个结点(的存储映像)链接成一个链表，即线性表

每个结点只包含一个指针域，故曰：线性链表、单链表

单链表在内存中的表示

相较于顺序表插入、删除操作需要整体平移元素，单链表的优势在于插入删除只需修改指针

但缺点是：丧失了顺序表的随机存储特性

比较：

顺序表-直接访问元素：

顺序表-插入、删除元素：

单链表-直接访问元素：

单链表-插入、删除元素：

头指针

从头指针开始进行，头指针指示链表中第一个结点（第一个数据元素的存储映像，也称首元结 点）的存储位置。同时，由于最后一个数据元素没有直接后继，则单链表中最后一个结点的指 针为空（NULL）

单链表-定义

C++写法

链表：linked List Node简写LNode

数据域：data

指针域：next

struct LNode{ int data;//数据域 LNode *next;//指针域 };

尾插法

定义好LNode后，创建一个空链表，创建一个tail指针始终指向尾结点L->NULL；创建malloc函数使其自动为链表分配空间；给定一个元素e，当这个链表为空表时（L == NULL）使L和tail均指向元素e,然后让元素e指向NULL(e->next = NULL)

L->e ->NULL

^

|

tail

插入第二个元素f，前面同理，但插入前链表不空，这时将指向e的尾指针tail指向f,后再指向尾结点

L->e->f->NULL

^

|

tail

typedef struct LNode{ int data; struct LNode *next; }LNode; LNode *L = NULL;//创建空列表 LNode *tail =NULL;//始终指向表尾结点 int nums;//定义该链表的上限 scanf("%d",&nums); for(int i=0;i<nums;i++){ //新建一个节点并读入数据 LNode *s = (LNode *)malloc(sizeof(LNode)); scanf("%d",&s->data); s->next = NULL; //介入链表部分 if(L == NULL){ L = tail = s;//插入第一个结点，头、尾指针都指向它 } else{ tail->next = s;//将尾指针指向s tail = s;//尾指针继续指向尾结点 } }

头结点

尾插法中指针指向的第一个结点，本身不存储数据。其存在只是为了统一第一个结点和其他节点的操作。

首元结点

定义尾插法中第一个存储数据的结点为首元结点

头插法

头插法就是在头节点处不断插入新的元素而形成一个单链表，但所得的单链表和输入的元素的逻辑位置是相反的

头插法主要代码：

L->next = NULL;L.next即头结点，初始化：让头结点指向NULL值 s->next = L->next;将L->next赋值给s->next，即先让待插元素的指针域先指向头结点指向的元素A，防止A丢失 L->next = s;再令L指向s的数据域

根据以上分析可以有：

typedef struct LNode{ int data; struct LNode *next; }LNode; LNode *L = (LNode *)malloc(sizeof(LNode)); L->next = NULL; int num; int count = 0; printf("请输入单链表元素上限"); scanf("%d",&num); for(int i = 0;i<num;i++){ LNode *s = (LNode *)malloc(sizeof(LNode)); s->next = L->next; L-> next = s; }

单链表-查找

按值查找

查找需要定义两个形式参数，链表头指针 查找元素

LNode* Find(LNode *L,int e)

查找过程：在单链表中逐个查找对应元素e，找到返回其序列或索引；找不到返回NULL

时间复杂度：

//在链表中查找值为e的元素 LNode* Find(LNode* L,int e){ LNode *p = L->next;//先令p指向首元结点 while(p != NULL && p->data != e){ p =p->next; } return p;//无论如何，均返回指针p，找不到返回NULL }

按位序查找

查找需要定义两个形式参数，链表头指针 查找元素的索引

LNode* FindKth(LNode *L,int k)

时间复杂度：

LNode* FindKth(LNode *L,int k){ if(k<0) return NULL; LNode *p = L;//直接令头结点作第0结点 int i = 0; while(p != NULL && i<k){ p = p->next; i++; } return p; }

单链表-插入

在第个元素插入一个新元素e，注意到这和头尾插法的思路是一致的。

设第个元素的指针为

则在第~个元素之间插入新元素的核心操作为：

LNode *s = (LNode*)malloc(sizeof(LNode));//创建s结点 s->data = e;//将s结点的指针指向e s->next = p->next; p->next = s;

单纯的单链表操作时间复杂度：

但需考虑位序查找的操作，综合的时间复杂度：

但自头结点或首元结点到第个元素的过程需要按位序查找到第个元素退出

bool Insert(LNode *L,int i,int e){ LNode *p = FindKth(L,i-1); //将第i-1个元素的地址赋给p if(p == NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = e;//让指针s指向 e的数据域 s->next = p->next; p->next = s; return true; }

单链表-删除

我们考虑删除第个元素，但在此之前我们必须得知道它的直接前驱和直接后继，即第个元素和第个元素。因为是单链表，则第，我们删除第个元素后，希望的指针是。

对此令指针指向第个数据元素，我们需要根据第个元素与第个元素的指针关系得出第个元素指向第个元素

p->next = p->next->next

但是 p->next->next不够美观，且无法直接释放掉待删除元素；令指针指向第个元素，则

q->nextp->next->next，最后通过free(q)函数即可释放掉第个元素。

综合时间复杂度：

bool Delete(LNode *L,int i){ LNode *p = FindKth(L,i-1); if(p == NULL || p->next == NULL) return false; LNode *q = p->next;//令q指针指向p（第i-1个） 的下一位元素（第i个） p->next = q->next;//让 p（第i-1个） 的下一位元素直接指向q（第i个） 元素的下一位元素--第i+1个元素 free(q);//释放q return true; }

双向链表

在前面的单向链表中，所有元素的指针都是向后的，这很有利于我们去访问后继元素，但对于前驱元素的访问却很困难。于是引入双向链表

前驱指针

前驱指针：prior

对于某个结点而言，指向其前驱元素的指针域叫做前驱指针。表头元素的前驱指针指向NULL

后继指针

后继指针：next

对于某个结点而言，指向其后继元素的指针域叫做后继指针。表尾元素的后继指针指向NULL

C++写法

struct DLNode{ int data; DLNode *prior;//定义前驱指针 DLNode *next;//定义后继指针 };

类C写法

struct DLNode{ int data; struct DLNode *prior;//定义前驱指针 struct DLNode *next;//定义后继指针 }DLNode;

双链表-插入

在第到之间插入一个新元素e(结点：s)，令p指针指向

第个元素的后继指针指向当指向第个元素的前驱指针域；第个元素的前驱指针当指向第个元素的后继指针域。

当插入新元素后，我们希望的后继指针能指向s的前驱指针域，的前驱指针能指向s的后继指针域。

为了防止数据的丢失，我们参照单链表的插入、删除中对新元素的操作，先令s的前驱指针指向的数据域，后继指针指向的数据域，这样能使这三个元素联系上。

再仿照双向链表的前驱、后继指针，同时令和元素的对应指针指向s的数据域，最后“拉直”就是一个新的双链表。

显然的操作顺序为：

p->prior->next = s;//p->prior->next的意思是第i-1个元素的后继指针，则让i-1的后继指针指向s s->prior = p->prior;//让s的前驱指针指向i-1的前驱 p->prior = s;//将p的前驱指针指向s的后继 s->next = p;//再让s的后继指针指向p

顺序不能颠倒（只要不是以下顺序皆可）

在结点后面进行插入操作同理，略去。

双链表删除

循环链表

循环链表（Circular Linked List）是另一种形式的链式存储结构。

其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点。

循环单列表

在单列表的基础上，令尾结点的指针域由NULL指向头结点

我们可以构造循环单链表来对链表内的结点进行遍历，当我们需要停止时：

if(p->next == L){//p->next == L,因为是循环列表，我们需要判断p的下一项是否指向头结点L return true; }else{ return false; }

设R指针指向（rear、tail都表示末尾）表尾结点，则通过R可以快速找到首元结点：

R->next->next

其中：R->next表示头结点

循环双链表

在双列表的基础上，令尾结点的后继指针由NULL指向头结点；首元结点的前驱指针由NULL指向表尾结点