线性表

线性表是具有相同数据类型的n个数据元素的有限序列,其中n为表长,当n=0时表是一个空表

除了第一个元素和最后一个元素外,每个元素有且仅有一个直接前驱和直接后继

逻辑结构

image-20220506165445334


基本运算和操作

包括初始化,销毁,插入,删除,查找,求表长等操作,针对不同的存储结构,其实现形式有所不同


存储结构

顺序表

即是用顺序存储方式实现的线性表,把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现

可以通过静态分配或动态分配的方式实现顺序表

特点:

  • 随机访问,在O(1)时间内找到第i个元素
  • 存储密度高,每个节点都只存储数据元素
  • 拓展容量不方便(只能通过动态分配)
  • 插入,删除不方便,要移动大量元素

代码实现:

定义

1
2
3
4
5
6
//顺序表的结构体定义 
typedef struct
{
int *data; //存放顺序表元素的数组
int length; //存放顺序表的长度
}Sqlist; //顺序表类型的定义

初始化

1
2
3
4
5
6
7
8
//初始化顺序表 
Sqlist initList()
{
Sqlist L;
L.data = (int*)malloc(maxSize*sizeof(int)); //动态分配数组空间
L.length = 0;
return L;
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//在顺序表的第p个位置上插入新的元素e。如果p输入不正确,返回0,p输入正确,插入成功,返回1。 
int insertElem(Sqlist &L, int p, int e)
{
int i;
if(p<0||p>L.length||L.length==maxSize)
return 0;
for(i=L.length-1;i>=p;--i)
{
L.data[i+1] = L.data[i];
}
L.data[p] = e;
++L.length;
return 1;
}

平均移动次数是 n/2

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//删除表L中下标为p的元素,成功返回1,否则返回0,并将被删除元素的值赋给e。 
int deleteElem(Sqlist &L, int p, int &e)
{
int i;
if (p<0||p>L.length-1)
return 0;
e = L.data[p];
for(i=p;i<L.length-1;++i)
{
L.data[i] = L.data[i+1];
}
--L.length;
return 1;
}

单链表

每个结点除了存放数据元素外,还要存储指向下一个节点的指针

image-20220507145406767

定义

1
2
3
4
5
6
//链表的定义
typedef struct Node
{
int data;
struct Node* next;
}Node, *LinkList;

初始化

1
2
3
4
5
6
7
8
9
10
11
12
//单链表的初始化

LinkList LinkedListInit() { // 为什么用指针操纵结构体?因为比起直接传递结构体,指针的效率更高  
Node* L;
L = (Node*)malloc(sizeof(Node)); //动态分配内存,申请结点空间,此语言的意思是开辟一个大小为一个Node字节数的内存区域,而L指向的就是该区域
if (L == NULL) { //判断是否有足够的内存空间
printf("申请内存空间失败\n");
}
L->next = NULL; //指针使用->运算符,表示直接操作结构体成员,将next设置为NULL,初始长度为0的单链表
return L;
}

创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//链表的创建
//头插法,将新加入的元素都插到表头中
LinkList LinkListCreatH() {
Node* L;
L = (Node*)malloc(sizeof(Node)); //申请头结点空间
L->next = NULL; //初始化一个空链表
int m;
printf("您要创建长度为多少的链表:");
scanf_s("%d", &m);
for (int i = 0; i < m; i++) {

int x; //x为链表数据域中的数据
scanf_s("%d", &x);

Node* p;
p = (Node*)malloc(sizeof(Node)); //申请新的结点
p->data = x; //结点数据域赋值
p->next = L->next; //将结点插入到表头L-->|2|-->|1|-->NULL
L->next = p;
}

return L;
}
//尾插法,将新加入的元素都插入到表尾中
LinkList LinkListCreatT()
{
Node* L;
L = (Node*)malloc(sizeof(Node));
L->next = NULL;
int m;
printf("您要创建长度为多少的链表:");
scanf_s("%d", &m);
Node* s;
s = L; // 设置一个和头结点相同起点的的尾巴指针
for (int i = 0; i < m; i++) {

int x; //x为链表数据域中的数据
scanf_s("%d", &x);

Node* p;
p = (Node*)malloc(sizeof(Node)); //申请新的结点

p->data = x; //结点数据域赋值
p->next = NULL; //将结点插入到表尾L-->|1|-->|2|-->NULL
s->next = p;
s = p;

}
return L;
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//链表的插入
LinkList LinkedListInsert(LinkList L, int i, int x) {
Node* pre; //pre为前驱结点
pre = L; // pre 首先指向头结点
int tempi = 0;
for (tempi = 1; tempi < i; tempi++) {
pre = pre->next; //查找第i个位置的前驱结点
}
Node* p; //插入的结点为p
p = (Node*)malloc(sizeof(Node)); // 为插入的结点初始化内存
p->data = x; // 为数据域赋值
p->next = pre->next;
pre->next = p;

return L;
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//链表的删除
LinkList LinkedListDelete(LinkList L, int x)
{
Node* p;
Node* pre; //pre为前驱结点,p为查找的结点。
pre = (Node*)malloc(sizeof(Node)); // 为插入的结点初始化内存
p = L->next;
while (p->data != x) { //查找值为x的元素
pre = p;
p = p->next;
}
pre->next = p->next; //删除操作,将其前驱next指向其后继。
free(p);
return L;
}

双链表

在单链表的基础上,增加了指向前驱结点的指针

image-20220507145324905

定义

1
2
3
4
5
6
typedef struct DoubleNode
{
int data;
struct DoubleNode* prior;
struct DoubleNode* next;
}Dnode,*DnodeList;

初始化和创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
DnodeList CreatDnodeH() {
DnodeList L;
L = (Dnode*)malloc(sizeof(Dnode));
L->next = NULL;
L->prior = NULL;
int x;
printf("number:");
scanf_s("%d", &x);

for (int i = 0; i < x; i++) {
DnodeList P;
P= (Dnode*)malloc(sizeof(Dnode));
int m;
scanf_s("%d", &m);
P->data = m;
//很明显是头插法
P->next = L->next;
L->next = P;
P->prior = L;
}
return L;
}

插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
DnodeList InsertDnode(DnodeList L,int i,int x) {
DnodeList P;
P = (Dnode*)malloc(sizeof(Dnode));
P->data = x;
DnodeList pre;
pre = L;
for (int m = 1; m < i; m++) {
pre = pre->next;
}

P->next=pre->next;
pre->next->prior=P;
P->prior = pre;
pre->next = P;

return L;
}

链表不具备随机存取特性,查找操作只能通过顺序遍历实现


循环链表

在单链表/双链表的基础上,尾结点不指向NULL,而是指向头结点,这种链表称作循环链表

image-20220507144839138


静态链表

分配一整片连续的内存空间,各个结点集中安置

image-20220507145636932

0号结点当作头结点,游标为-1表示已经到达表尾,其他的游标表示下一个结点的数组下标

本质上是用数组形式实现的链表,优点是增删不需要大量移动元素,缺点是不能随机存取,只能从头结点开始一次查找,容量固定不可变

适用于数据元素数量固定不变的场景(操作系统的文件分配表FAT


顺序表和链表的比较

顺序表

  • 优点:支持随机存取,存储密度高
  • 缺点:大片连续空间分配不方便,改变容量不方便

链表

  • 优点:离散的小空间分配方便,改变容量方便
  • 缺点:不可随机存取,存储密度低