算法
定义
解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列
特性
算法效率的度量
运行时间
算法时间复杂度
-
$T(n)=O(f(n))$
-
分类与排序
- $O(1) < O(log(n))< O(n) < O(nlog(n)) < O(n^2) < O(n^3) < O(n!) < O(n^n)$
-
最坏情况与平均情况
- 一般运行时间为最坏运行时间
- 平均运行时间是一个期望值
算法空间复杂度
线性表(List)
线性表(List)定义
- 零个或多个数据元素的有限序列
- 每个元素都有一个直接前驱和直接后继元素
- 数据元素是一对一的关系
抽象数据类型
Operation
IintList(*L);
ListEmpty(L);
GetElem(L,i,*e);
LocateELem(L,e);
ListInsert(*L,i,e);
ListDelete(*L,i,*e);
ListLength(L);
endADT
顺序存储结构
定义
用一段地址连续的存储单元依次存放线性表的数据元素
三个属性
结构代码
1
2
3
4
5
6
7
|
#define MAXSIZE 20
typedef int ElemType
typedef struct
{
ElemType data[MAXSIZE]; //数组存取数据元素
int length; //线性表当前长度
}SqList;
|
插入与删除
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
|
//插入
Status ListInsert(SqList *L,int i, ElemType e)
{
int k;
if (L->length==MAXSIZE)
return -1;
else if (i<1 || i>L->length)
return -1;
else
{
for(k=L->Length-1;k->i-1;k--)
L->data[k+1]=L->data[k];
}
L->data[i-1]=e;
L->length++;
return 0;
}
//删除
Status ListDelete(SqList *L, int i, ElemType e)
{
int k;
if (L->length==0)
return -1;
else if (i<1 || i>L->length)
return -1;
*e=L->data[i-1];
if (i<L->length)
{
for(k=i;k<L->length;k++)
L->data[k+1]=L->data[k];
}
L->length--;
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
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
|
//定义
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList;
//读取
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p;
p = L->next;
j = 1;
while (p && j<i) //p不为空且j小于i的时候
{
p = p>-next;
j++;
}
if (!p || j>i)
return -1; //第i个元素不存在
*e = p->data; // 取第i个元素的数据
return 0;
}
//插入
Status ListInsert(LinkList L,int i,ELemType e)
{
int j;
LinkList,p,s;
p =*L;
j=1;
while(p&&j<i)
{
p=p->next;
++j;
}
if (!p||j>i)
return -1;
s = (LinkList)malloc(sizeof(Node)); //生成新结点
s->data=e;
s->next=p->next;
p->next=s;
return 0;
}
//删除
Status ListDelete(LinkList L,int i,ElemType e)
{
int j;
LinkList p,q;
p =*L;
j=1;
while(p=p->next&&j++<i)
;
if (!(p->next) || j > i)
return -1;
q = p->next;
p ->next = q->next;
*e = q->data //回收删除数据
free(q);
return 0;
}
//整表创建
//头插法
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
for (i=0;i<n;i++)
{
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100+1;
p->next = (*L) ->next;
(*L)->next = p;
}
}
//尾插法
void CreateListTail(LinkList *L, int n)
{
LinkList p,r;
int i;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for(i=0;i<n;i++)
{
p = (Node *)malloc(sizeof(Node));
p->data = rand()%100+1;
r->next = p;
r = p;
}
r->next = NULL;
}
//整表删除
Status ClearList(LinkList *L)
{
LinkList p,q;
*p=(*L)->next;
while(p)
{
q=p->next;
free(q);
p=q;
}
(*L)->next=NULL;
return 0;
}
|
单链表结构和顺序存储结构的优缺点
对比/分类 |
顺序存储结构 |
单链表 |
查找 |
O(1) |
O(n) |
插入和删除 |
O(n) |
O(1) |
空间 |
需要预分配,灵活性和安全性低 |
非常棒 |
静态链表
定义
用数组描述的链表
组成
-
数据域
-
游标(cur)
- 第一个游标存放备用链表第一个结点的下标
- 最后一个游标存放第一个插入元素的下标
- 特殊称呼 —— 备用链表
代码
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
|
//定义
#define MAXSIZE 1000
typedef struct
{
ELemType data;
int cur;
}Component,StaticLinkList[MAXSIZE];
//初始化
Status InitList(StaticLinkList space)
{
int i;
for(i=0;i<MAXSIZE-1;i++)
space[i].cur=i+1;
space[MAXSIZE-1].cur=0;
return 0;
}
//插入
Status ListInsert(StaticLinkList L,int i, Elemtype e)
{
int j,k,l;
k=MAXSIZE-1;
}
|
循环链表
定义
将单链表的最后一个指针指向头结点,形成循环链表
合并循环链表
1
2
3
|
p = rearA->next; //将A的头结点存起来
rearA->next = rearB->next-next;//让A的尾结点指向B的第二个结点,B的头结点被抛弃
rearB->next = p;//让B的结尾指向A的头结点
|
双向链表
定义
- 在每一个结点中设置一个指向其前驱结点的指针的单链表
存储结构
1
2
3
4
5
6
|
typedef struct DulNode
{
Elemtype data;
struct DulNode *prior;
struct DulNode *next;
} DulNode,*DulLinkList;
|
有趣的事实
1
|
p->next->prior = p->prior->next = p
|
代码
1
2
3
4
5
6
7
8
9
10
|
// 插入
s->prior = p;
s->next = p->next;
p->next->prior=s;
p->next=s;
//删除
p->prior->next=p->next;
p-next->prior=p->prior;
free(p);
|