数据结构基础之线性表

  数据结构也是算法学习的一部分,最近比较忙,在对所学的知识查漏补缺,没有学习什么新的东西,于是干脆就对一直在复习数据结构来了个大总结,这篇博客主要是数据结构的线性表部分,争取尽快把其他部分总结完。接下来的一段时间可能不会经常去 Leetcode 刷题了,近期的算法学习这一系列的博客将以数据结构为主,因为近来有更重要的事情要做,毕竟精力有限,刷题这一块就先放一放咯。

线性表的基本概念

  定义:具有相同数据类型的n(n>=0)个数据元素的有限序列

  线性表的特点:

  1. 表中的元素个数有限。
  2. 表中元素具有逻辑上的顺序性,在序列中各元素排列有其先后顺序。
  3. 表中元素都是数据元素,每个元素都是单个元素。
  4. 表中元素的数据类型都相同。
  5. 表中元素具有抽象性。即仅讨论元素间的逻辑关系,不考虑元素究竟表示什么内容。

顺序存储

顺序表

  线性表的顺序存储。用一组地址连续的存储单元,依次存储线性表中的数据元素,使得逻辑上相邻的两个元素在物理上也相邻。

6-3

  注意:顺序表的位序是从1开始的,而数组中元素的下标是从0开始的。

  • 基本操作
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define OVERFLOW -2
#define true 1
#define false 0
#define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量
#define LIST_INCREMENT 2 //线性表存储空间的分配增量
typedef struct{
ElemType *data; //存储空间基址
int length; //当前长度
int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
}SeqList;
/********初始化********/
int InitList(SeqList *L){
L->data = (ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);
if(!L->data)
return OVERFLOW;
L->length = 0;
L->listsize = LIST_INIT_SIZE;
return true;
}
/****************插入操作*****************/
int ListInsert(SeqList *L,int i,ElemType e){
int j;
if(i<1||i>L->length+1) //判断i的范围是否有效
return false;
if(L->length == L->listsize) //存储空间已满时不能插入
return OVERFLOW;
for(j=L->length;j>=i;j--) //将第i个元素及之后的元素后移
L->data[j]=L->data[j-1];
L->data[i-1]=e; //在位置i处放入e
L->length++; //线性表长度加1
return true;
}
/***********删除操作***********/
int ListDelete(SeqList *L,int i){
int j;
if(i<1||i>L->length+1) //判断i的范围是否有效
return false;
for(j=i;j<L->length;j++) //将第i个位置之后的元素前移
L->data[j-1] = L->data[j];
L->length--; //线性表长度减1
return true;
}
/**********按位置查找************/
ElemType GetElem(SeqList *L,int i){
if(i<1||i>L->length+1) //判断i的范围是否有效
return false;
return L->data[i-1];
}
/*************按值查找**************/
int LocateElem(SeqList *L,ElemType e){
int i;
for(i=0;i<L->length;i++){
if(L->data[i] == e)
return i+1;
}
return 0;
}
/*********求表长**********/
int ListLength(SeqList *L){
return L->length;
}
/******判断是否是空表*****/
void ListEmpty(SeqList *L){
if(L->length == 0)
return true;
else
return false;
}
/*********输出表*********/
void printList(SeqList *L){
int i;
for(i=0;i<L->length;i++)
printf("%d ",L->data[i]);
}
/*********清空表********/
void ClearList(SeqList *L){
L->length = 0;
}
/*********销毁表********/
void DstroyList(SeqList *L){
free(L->data);
L->data = NULL;
L->length = 0;
L->listsize = 0;
}
int main(){
SeqList L;
InitList(&L);
....
进行插入、删除、查找结点等操作
....
return 0;
}
  • 扩展操作
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
/********将顺序表的所有元素逆置******/
void Reverse(SeqList *L){
int i;
ElemType temp; //辅助变量
for(i=0;i<((L->length)/2);i++){ //扫描顺序表L,进行元素交换
temp = L->data[i];
L->data[i] = L->data[L->length-1-i];
L->data[L->length-1-i] = temp;
}
}
/******删除有序顺序表中重复的元素******/
void Del_same(SeqList *L){
int i,j;
for(i=0,j=1;j<L->length;j++){ //i存储第一个不相同的元素,j工作指针
if(L->data[i] != L->data[j]){ //查找下一个与上一个元素值不相同的元素
L->data[++i] = L->data[j]; //找到后,则将元素前移
}
}
L->length = i+1; //删除相同元素后,线性表的长度
}
/*****将两个有序顺序表合并成一个新的有序顺序表*****/
int Merge(SeqList *L1,SeqList *L2,SeqList *L){
if(L1->length + L2->length > L->length) //大于合并表的长度
return false;
while(i < L1->length && j < L2->length){ //循环,两两比较,较小的存入结果表
if(L1->data[i] <= L2->data[j])
L->data[k++] = L1->data[i];
else
L->data[k++] = L2->data[j];
}
while(i < L1->length) //处理剩下没比完的顺序表
L->data[k++] = L1->data[i++];
while(j < L2->length)
L->data[k++] = L2->data[i++];
return true;
}

链式存储

单链表

  单链表:通过一组任意的存储单元来存储线性表中的数据元素。

6-2

  头结点head指向单链表的第一个结点。

  结点由两部分组成:数据域data,指针域next(存放直接后继元素的地址)。

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define true 1
#define false 0
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
/************头插法建立链表*************/
LinkList HeadInsert_CreatList(LinkList L){
int n;
LNode *s;
L = (LinkList)malloc(sizeof(LNode)); //创建头结点
L->next = NULL;
printf("采用头插法建立链表,请输入结点值,以9999结束:\n");
scanf("%d",&n);
while(n!=9999){
s = (LinkList *)malloc(sizeof(LNode)); //创建新结点
s->data = n;
s->next = L->next;
L->next = s; //将新结点插入表中
scanf("%d",&n);
}
return L;
}
/************尾插法建立链表*************/
LinkList RearInsert_CreatList(LinkList L){
int n;
LNode *s,*r;
L = (LinkList)malloc(sizeof(LNode)); //创建头结点
r = L;
printf("采用尾插法建立链表,请输入结点值,以9999结束:\n");
scanf("%d",&n);
while(n!=9999){
s = (LNode *)malloc(sizeof(LNode)); //创建新结点
s->data = n;
r->next = s;
r = s; //r指向新的表尾结点
scanf("%d",&n);
}
r->next = NULL; //表尾结点指针置空
return L;
}
/*******按序号查找结点值*******/
LNode* GetElem(LinkList L,int i){
int j = 1;
LNode *p = L->next; //头结点指针赋给p
if(i==0) //i=0返回头结点
return L;
if(i<1) //i无效则返回NULL
return NULL;
while(p&&j<i){ //从第1个结点开始查找第i个结点
p = p->next;
j++;
}
return p; //返回第i个结点的指针
}
/*************按值查找结点*************/
LNode* LocateElem(LinkList L,ElemType e){
LNode *p = L->next; //头结点指针赋给p
while(p!=NULL&&p->next!=e) //从第1个结点开始查找值为e的结点
p = p->next;
return p; //找到则返回值为e的结点,否则返回NULL
}
/****************插入结点****************/
int ListInsert(LinkList L,int i,ElemType x){
LNode *s,*p;
p = GetElem(L,i-1); //查找插入位置的前驱结点
s = (LNode *)malloc(sizeof(LNode)); //创建新结点
s->data = x;
s->next = p->next;
p->next = s;
return true;
}
/*********求表长*********/
int ListLength(LinkList L){
int len = 0;
LNode *p = L->next; //头结点指针赋给p
while(p){
len++; //记录表中结点个数
p = p->next;
}
return len; //返回表长
}
/***********删除结点***********/
int ListDelete(LinkList L,int i){
LNode *p = GetElem(L,i-1); //查找待删除结点的前驱结点
LNode *q = p->next; //p指向需要删除的结点
p->next = q->next; //修改指针
free(q); //释放删除结点的存储空间
return true;
}
/*****打印链表结点值******/
int ListPrint(LinkList L){
LNode *p = L->next; //头结点指针赋给p
while(p){
printf("%d ",p->data); //按顺序依次输出结点值
p = p->next;
}
printf("\n");
}
int main()
{
LinkList L1,L2;
L1 = HeadInsert_CreatList(L1);
printf("采用头插法建立的链表L1的结点值为:");
ListPrint(L1);
L2 = RearInsert_CreatList(L2);
printf("采用尾插法建立的链表L2的结点值为:");
ListPrint(L2);
....
进行插入、删除、查找结点等操作
....
return 0;
}
双链表

  每个结点设置两个指针prior和next,分别指向其前驱结点和后继结点。

6-5

1
2
3
4
typedef struct DNode{
ElemType data; //数据域
struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinkList;

  插入操作:

1
2
3
4
5
//将结点*s插入到结点*p之后
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;

  删除操作:

1
2
3
4
//删除结点*p的后继结点*q
p->next = q->next;
q->next->proir = p;
free(q);

循环单链表

  将单链表的最后一个指针由NULL改为指向头结点,使整个链表形成一个环。

6-4

  判空条件为:头结点的指针是否等于头结点。插入删除与单链表相同。

静态链表

  借助数组来描述线性表的链式存储结构。

6-1

  结点由两部分组成:数据域data,下一个元素的数组下标next。

1
2
3
4
typedef struct{
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MAXSIZE];

  以next=-1作为其结束的标志。

顺序表和链表的比较

存取方式

  顺序表:可以顺序存取也可以随机存取。

  链表:只能从表头顺序存取元素。

逻辑结构与物理结构

  顺序表:逻辑上相邻的元素,其对应的物理存储位置也相邻。

  链表:逻辑上相邻的元素,其物理存储位置则不一定相邻。

查找、插入和删除操作

  查找:按值查找时,顺序表无序时,顺序表和链表的时间复杂度均为O(n),但是当顺序表有序时,可采用折半查找,时间复杂度为O(log2n)。

  查找:按序号查找时,顺序表的时间复杂度仅为O(1),而链表的平均时间复杂度为O(n)。

  插入和删除:顺序表平均需要移动半个表长的元素,而链表只需要修改相关指针即可。

空间分配

  顺序存储在空间分配中存在诸多问题与隐患,比如内存溢出、内存闲置等,而链式存储的结点空间只在需要的时候申请分配,只要内存有空间就可以分配,操作灵活、高效。

坚持原创技术分享,您的支持将鼓励我继续创作!