线性结构总结
线性表
线性表是由n>=0个性质相同的数据元素组成的有限序列，n为线性长度。
线性表的主要操作包括创建空线性表，判断线性表是否为空，以及插入，删除和查找等操作。
顺序表
顺序表是用一组地址连续的储存单元依次储线性表中的各个元素，通过位置来表示数据元素之间的线性逻辑关系。
顺序表的相邻元素在物理位置上也是相邻的。
优点：
- 可以快速获取下标的数据元素，时间复杂度为O(1)
- 逻辑关系是一对一的关系，连续存储单元足以储存，不需要增加额外的存储空间
缺点：
- 插入和删除操作需要移动大量的元素，时间复杂度为O(n)
- 线性表的存储空间大小难以确定，并且不好扩展
- 造成存储空间碎片化
以下为顺序表的基本功能
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
51
52
53
54
55
56
57
58
59
60
61
| {
SeqList slist = (SeqList)malloc(sizeof(struct List));
if (slist != NULL)
{
slist->elem = (DataType*)malloc(sizeof(DataType) * m);
if (slist->elem) {
slist->Max = m;
slist->n = 0;
return(slist);
}
else free(slist);
}
printf("out of space!!\n");
return NULL;
}
int IsNullList_seq(SeqList slist)
{
return(slist->n == 0);
}
int InsertPre_seq(SeqList slist, int p, DataType x)
{
int q;
if (slist->n >= slist->Max) {
printf("overflow");
return(0);
}
if (p<0 || p>slist->n) {
printf("not exist!\n");
return(0);
}
for (q = slist->n - 1; q >= p; q--)
slist->elem[q + 1] = slist->elem[q];
slist->elem[p] = x;
slist->n = slist->n + 1;
return(1);
}
void print(SeqList slist)
{
int i;
for (i = 0; i < slist->n; i++)
printf("%d ", slist->elem[i]);
}
int DelIndex_seq(SeqList slist, int p)
{
int q;
if (p < 0 || p >= slist->n) {
printf("Not exist\n");
return 0;
}
for (q = p; q < slist->n - 1; q++) {
slist->elem[q] = slist->elem[q + 1];
}
slist->n = slist->n - 1;
return 1;
}
```
|
链式线性表-单链表
其中的元素的储存位置是任意的，具体位置在程序运行时动态分布。其在物理位置上相邻元素并不相邻。
存储分配：
- 顺序 -> 一段地址连续的存储空间
- 链式 -> 任意地址存储空间
时间：
- 查找 顺序 -> O(1) 链式 -> O(n)
- 插入和删除 顺序 -> O(n) 链式 -> 寻找相应的节点，时间复杂度为O(n)，然后，插入和> >删除为O(1)
空间：
以下是其基本功能
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
LinkList SetNullList_Link()
{
LinkList head = (LinkList)malloc(sizeof(struct Node));
if (head != NULL) head->next = NULL;
else printf("alloc failure");
return head;
}
void CreateList_Tail(struct Node* head)
{
PNode p = NULL;
PNode q = head;
DataType data;
scanf("%d", &data);
while (data != -1)
{
p = (struct Node*)malloc(sizeof(struct Node));
p->data = data;
p->next = NULL;
q->next = p;
q = p;
scanf("%d", &data);
}
}
int InsertPre_link(LinkList llist,LinkList p, DataType x){
LinkList pre=llist,q=NULL;
while(pre->next!= p){
pre=pre->next;
}
q=(LinkList)malloc(sizeof(LinkList));
q->data=x;
q->next=p;
pre->next=q;
}
void InsertPost_link_value(LinkList head,int finddata,int insertdata){
LinkList p=head;
while(p->data!=finddata){
p=p->next;
}
InsertPre_link(head,p,insertdata);
}
void print(LinkList head)
{
PNode p = head->next;
while (p)
{
printf("%d ", p->data);
p = p->next;
}
}
void DestoryList_Link(LinkList head)
{
PNode pre = head;
PNode p = pre->next;
while (p)
{
free(pre);
pre = p;
p = pre->next;
}
free(pre);
}```
|
单循环链表
在单链表的基础上将最后一个节点的指针指向链表的第一个节点，形成一个环，称之为单循环链表。
双链表和双循环链表
双链表
存在钱去和后继
优点
- 可以实现双向查找
缺点
- 需要额外的储存空间存放前驱节点
双循环链表
把双链表的最后的一个节点的后继指针指向第一个节点，把第一个节点的前驱指针指向最后一个节点，就组成了双循环链表。
栈
栈（英语：stack）又称为堆栈或堆叠，栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
- 定义：只允许在一端进行插入或删除的线性表
- 栈顶（top） ：允许进行插入或删除的一端
- 栈底（bottom）: 与栈顶相对应的一端
- 特点： 先进后出
包含顺序栈，双栈等
队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
