线性结构
线性结构：把所有的结点能够用一根直线穿起来
连续存储【数组】
什么叫数组
元素类型相同，大小相等
优点：存取速度快
缺点：
插入删除元素慢
事先必须知道数组的长度
空间通常有限制，需要大块内存
数组的相关操作
1 # include
2 # include
3
4 //定义了一个数据类型，该数据类的名字叫做struct Arr
5 struct Arr
6 {
7 int* pBase; //存储的是数组第一个元素的地址
8 int len; //数组所能容纳的最大元素的个数
9 int cnt; //当前数组有效的个数
10 };
11
12 void init_arr(struct Arr *,int length);
13 bool append_arr(struct Arr*,int val); //追加
14 bool insert_arr(struct Arr*,int pos,int val); //pos的值从1开始
15 bool delete_arr(struct Arr*, int pos,int * pVal);
16 int get();
17 bool is_empty(struct Arr*);
18 bool is_full(struct Arr*);
19 void sort_arr(struct Arr*);
20 void show_arr(struct Arr*);
21 void inversion_arr(struct Arr*); //反转
22
23 int main(void)
24 {
25 struct Arr arr;
26 int val;
27
28 init_arr(&arr,6);
29 show_arr(&arr);
30 append_arr(&arr, 1);
31 append_arr(&arr, 2);
32 append_arr(&arr, 5);
33 append_arr(&arr, 8);
34 append_arr(&arr, 9);
35 insert_arr(&arr,3, 6);
36 delete_arr(&arr, 2, &val);
37 show_arr(&arr);
38 inversion_arr(&arr);
39 show_arr(&arr);
40 sort_arr(&arr);
41 show_arr(&arr);
42 return 0;
43 }
44
45 void init_arr(struct Arr *pArr,int length)
46 {
47 pArr->pBase = (int*)malloc(sizeof(int) * length);
48 if (NULL == pArr->pBase)
49 {
50 printf("动态内存分配失败！\n");
51 return;//中止整个程序
52 }
53 else
54 {
55 pArr->len = length;
56 pArr->cnt = 0;
57 }
58
59 return;
60 }
61
62 bool is_empty(struct Arr* pArr)
63 {
64 if (0 == pArr->cnt)
65 return true;
66 else
67 return false;
68 }
69
70 bool is_full(struct Arr * pArr)
71 {
72 if (pArr->cnt == pArr->len)
73 return true;
74 else
75 return false;
76 }
77
78 void show_arr(struct Arr* pArr)
79 {
80 if (is_empty(pArr))
81 {
82 printf("数组为空！\n");
83 }
84 else
85 {
86 for (int i = 0;i < pArr->cnt;++i)
87 {
88 printf("%d\t", pArr->pBase[i]); //int *
89 }
90 printf("\n");
91 }
92 }
93
94 bool append_arr(struct Arr* pArr, int val)
95 {
96 //满时返回false
97 if (is_full(pArr))
98 return false;
99 //不满时追加
100 pArr->pBase[pArr->cnt] = val;
101 pArr->cnt++;
102 return true;
103 }
104
105 bool insert_arr(struct Arr* pArr, int pos, int val)
106 {
107 if (is_full(pArr))
108 return false;
109 if (pos<1 || pos>pArr->cnt+1)
110 return false;
111 for (int i = pArr->cnt - 1;i >= pos - 1;--i)
112 {
113 pArr->pBase[i+1] = pArr->pBase[i];
114 }
115 pArr->pBase[pos - 1] = val;
116 pArr->cnt++;
117 return true;
118 }
119
120 bool delete_arr(struct Arr* pArr, int pos, int* pVal)
121 {
122 if (is_empty(pArr))
123 return false;
124 if (pos < 1 || pos > pArr->cnt)
125 return false;
126
127 *pVal = pArr->pBase[pos - 1];
128 for (int i = pos;i < pArr->cnt;i++)
129 {
130 pArr->pBase[i - 1] = pArr->pBase[i];
131 }
132 pArr->cnt--;
133
134 return true;
135 }
136
137 void inversion_arr(struct Arr* pArr)
138 {
139 int i = 0;
140 int j = pArr->cnt - 1;
141 int temp = 0;
142
143 while (i < j)
144 {
145 temp = pArr->pBase[i];
146 pArr->pBase[i] = pArr->pBase[j];
147 pArr->pBase[j] = temp;
148 i++;
149 j--;
150 }
151 return;
152 }
153
154 void sort_arr(struct Arr* pArr)
155 {
156 int temp;
157 for (int i = 0;i < pArr->cnt;i++)
158 {
159 for (int j = 0;j < pArr->cnt - i;j++)
160 {
161 if (pArr->pBase[j] > pArr->pBase[j + 1])
162 {
163 temp = pArr->pBase[j];
164 pArr->pBase[j] = pArr->pBase[j + 1];
165 pArr->pBase[j + 1] = temp;
166 }
167 }
168 }
169 }
离散存储【链表】
优点
空间没有限制
插入删除元素快
缺点：
存取速度慢
typedef 别名
1 # include
2
3 typedef int ZHANGSAN; //为int 在重新多取一个名字，ZHANGSAN等价于int
4
5 typedef struct Student
6 {
7 int sid;
8 char name[100];
9 char sex;
10 }ST;
11
12
13 int main(void)
14 {
15 int i = 10; //等价于ZHANGSAN i=10;
16 ZHANGSAN j = 20;
17 printf("%d\n", j);
18
19 ST st2;
20 st2.sid = 200;
21 printf("%d\n", st2.sid);
22
23 return 0;
24 }
# include
typedef int ZHANGSAN; //为int 在重新多取一个名字，ZHANGSAN等价于int
typedef struct Student
{
int sid;
char name[100];
char sex;
}* PST; //PST 等价于struct Student *
int main(void)
{
struct Student st;
PST ps = &st;
ps->sid = 200;
printf("%d\n", ps->sid);
return 0;
}
# include
typedef int ZHANGSAN; //为int 在重新多取一个名字，ZHANGSAN等价于int
typedef struct Student
{
int sid;
char name[100];
char sex;
}*PSTU,STU; //PST 等价于struct Student *,ST等价于 struct Student
int main(void)
{
STU st; // struct Student st;
PSTU ps = &st; //struct Student * ps = &st;
ps->sid = 200;
printf("%d\n", ps->sid);
return 0;
}
定义
n个节点离散分配
批次通过指针相连
每个节点只有一个前驱节点，每个节点只有一个后续节点
首节点没有前驱节点，尾节点没有后续节点
专业术语
首节点：第一个有效节点
尾节点：最后一个有效节点
头结点：
第一个有效节点之前的那个节点
头结点并不存放有效数据
加头结点的目的主要是为了方便对链表的操作
头结点的数据类型和首节点类型一样
头指针：指向头结点的指针变量
尾指针：指向尾节点的指针变量
如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的哪些参数
只需要一个参数：头指针，因为我们通过头指针可以推算出链表的其他所有信息
分类
单链表
双链表：每一个节点有两个指针域
循环链表：能通过任何一个节点找到其他所有的结点
非循环链表
算法
狭义的算法是与数据的存储方式密切相关的
广义的算法是与数据的存储方式无关
泛型：
利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的
插入一个结点
方法一（伪代码）
r=p->pNext; p->pNext=q; q-pNext=r;
方法二（伪代码）
q->pNext=p->pNext; p->pNext=q;
删除一个节点；
r=p->pNext;
p->pNext=p->pNext->pNext;
free(r)
遍历
查找
清空
销毁
求长度
排序
相关算法
1 #define _CRT_SECURE_NO_WARNINGS 1
2 # include
3 # include
4 # include
5
6 typedef struct Node
7 {
8 int data; //数据域
9 struct Node* pNext; //指针域
10 }NODE,*PNODE; //NODE等价于struct Node PNODE等价于struct Node *
11
12 //函数声明
13 PNODE create_list();
14 void traverse_list(PNODE);
15 bool is_empty(PNODE);
16 int length_list(PNODE);
17 bool insert_list(PNODE, int, int);
18 bool delete_list(PNODE, int, int*);
19 void sort_list(PNODE);
20
21
22 int main(void)
23 {
24 PNODE pHead = NULL; //等价于 struct Node * pHead=NULL;
25 int val;
26
27 pHead = create_list(); //创建一个非循环单链表，并将该链表的头结点的地址赋值给pHead
28 traverse_list(pHead);
29 int len = length_list(pHead);
30 printf("链表的长度为：%d\n", len);
31
32 if (is_empty(pHead))
33 printf("链表为空\n");
34 else
35 printf("链表不空\n");
36
37 //sort_list(pHead);
38
39 //insert_list(pHead, 3, 33);
40 if (delete_list(pHead, 4, &val))
41 {
42 printf("删除成功，您删除的元素是：%d\n", val);
43 }
44 else
45 {
46 printf("删除失败!\n");
47 }
48
49
50 traverse_list(pHead);
51 }
52
53 PNODE create_list()
54 {
55 int len;//y用来存放有效结点的个数
56 int val;//用来临时存放用户输入的结点的值
57
58 //分配了一个不存放有效数据的头结点
59 PNODE pHead = (PNODE)malloc(sizeof(NODE));
60 if (NULL == pHead)
61 {
62 printf("分配失败,程序中止！\n");
63 exit(-1);
64 }
65
66 PNODE pTail = pHead;
67 pTail->pNext = NULL;
68
69
70 printf("请输入您需要生成的链表结点的个数：len = ");
71 scanf("%d", &len);
72 for (int i = 0;i < len;i++)
73 {
74 printf("请输入第%d个节点的值：", i + 1);
75 scanf("%d", &val);
76
77 PNODE pNew = (PNODE)malloc(sizeof(NODE));
78 if (NULL == pNew)
79 {
80 printf("分配失败,程序中止！\n");
81 exit(-1);
82 }
83
84 pNew->data = val;
85 pTail->pNext = pNew;
86 pNew->pNext = NULL;
87 pTail = pNew;
88 }
89
90 return pHead;
91 }
92
93 void traverse_list(PNODE pHead)
94 {
95 PNODE p = pHead->pNext;
96 while (NULL != p)
97 {
98 printf("%d\t", p->data);
99 p = p->pNext;
100 }
101 printf("\n");
102 }
103
104 bool is_empty(PNODE pHead)
105 {
106 if (NULL == pHead->pNext)
107 return true;
108 else
109 return false;
110 }
111
112 int length_list(PNODE pHead)
113 {
114 PNODE p = pHead->pNext;
115 int len = 0;
116
117 while (NULL != p)
118 {
119 ++len;
120 p = p->pNext;
121 }
122 return len;
123 }
124
125 void sort_list(PNODE pHead)
126 {
127 int i, j, temp;
128 int len = length_list(pHead);
129 PNODE p, q;
130
131 for (i = 0,p=pHead->pNext;i
132 {
133 for (j = i+1,q=p->pNext;j < len ;j++,q=q->pNext)
134 {
135 if (p->data > q->data) //类似于数组中的：a[i]>a[j]
136 {
137 temp = p->data; //类似于数组中的：temp=a[i];
138 p->data = q->data; //类似于数组中的：a[i]=a[j];
139 q->data = temp; //类似于数组中的：a[j]=temp;
140 }
141 }
142 }
143 return;
144 }
145
146 //在pHead所指向的链表的第POS个节点的前面插入一个新的节点，该节点的值是val,并且pos的值是从1开始
147 bool insert_list(PNODE pHead, int pos, int val)
148 {
149 int i = 0;
150 PNODE p = pHead;
151
152 while (NULL != p && i < pos - 1)
153 {
154 p = p->pNext;
155 ++i;
156 }
157
158 if (i > pos - 1 || NULL == p)
159 return false;
160
161 PNODE pNew = (PNODE)malloc(sizeof(NODE));
162 if (NULL == pNew)
163 {
164 printf("动态分配内存失败！\n");
165 exit(-1);
166 }
167 pNew->data = val;
168 PNODE q = p->pNext;
169 p->pNext = pNew;
170 pNew->pNext = q;
171
172 return true;
173 }
174
175
176 bool delete_list(PNODE pHead, int pos, int* pVal)
177 {
178 int i = 0;
179 PNODE p = pHead;
180
181 while (NULL != p->pNext && i < pos - 1)
182 {
183 p = p->pNext;
184 i++;
185 }
186
187 if (i > pos - 1 || NULL == p->pNext)
188 return false;
189
190 PNODE q = p->pNext;
191 *pVal = q->data;
192
193 p->pNext = p->pNext->pNext;
194 free(q);
195 q = NULL;
196
197 return true;
198 }
线性结构两种常见应用之一 栈
定义
一种可以实现“先进后出”的存储结构
栈类似于箱子
分类
静态栈（内核数组）
动态栈（内核链表）
算法
出栈
压栈
1 # include
2 # include
3 # include
4
5 typedef struct Node
6 {
7 int data;
8 struct Node* pNext;
9 }NODE,* PNODE;
10
11 typedef struct Stack
12 {
13 PNODE pTop;
14 PNODE pBottom;
15 }STACK, * PSTACK; //PSTACK等价于 struct STACK *
16
17 void init(PSTACK);
18 void push(PSTACK, int);
19 void traverse(PSTACK);
20 bool pop(PSTACK, int *);
21 bool empty(PSTACK);
22 void clear(PSTACK);//清空
23
24 int main(void)
25 {
26 STACK S; //STACK 等价于struct Stack
27 int val;
28
29 init(&S); //目的是早出一个空栈
30
31 push(&S, 1); //压栈
32 push(&S, 2);
33 push(&S, 3);
34 push(&S, 4);
35 push(&S, 5);
36 push(&S, 6);
37 traverse(&S); //遍历输出
38 clear(&S);
39
40 if (pop(&S, &val))
41 {
42 printf("出栈成功，出栈的元素是%d\n", val);
43 }
44 else
45 {
46 printf("出栈失败！\n");
47 }
48
49 traverse(&S); //遍历输出
50
51
52 return 0;
53 }
54
55 void init(PSTACK pStack)
56 {
57 pStack->pTop = (PNODE)malloc(sizeof(NODE));
58
59 if (NULL == pStack->pTop)
60 {
61 printf("动态内存分配失败！\n");
62 exit(-1);
63 }
64 else
65 {
66 pStack->pBottom = pStack->pTop;
67 pStack->pTop->pNext = NULL; //pStack->pBottom->pNext = NULL
68 }
69 }
70
71 void push(PSTACK pStack, int val)
72 {
73 PNODE pNew = (PNODE)malloc(sizeof(NODE));
74
75 pNew->data = val;
76 pNew->pNext = pStack->pTop; //pStack->Top不能改成pStack->Bottom
77 pStack->pTop = pNew;
78
79 return ;
80 }
81
82 void traverse(PSTACK pStack)
83 {
84 PNODE p = pStack->pTop;
85 while (p != pStack->pBottom)
86 {
87 printf("%d ",p->data);
88 p = p->pNext;
89 }
90 printf("\n");
91 return;
92 }
93
94 bool empty(PSTACK pStack)
95 {
96 if (pStack->pTop == pStack->pBottom)
97 return true;
98 else
99 return false;
100 }
101
102 //把pStack指向的栈出栈一次，并把出栈的元素存入pVal形参所指向的变量中，如果出栈失败返回false,否则返回True
103 bool pop(PSTACK pStack, int* pVal)
104 {
105 if (empty(pStack)) //pStack本身存放的就是S的地址
106 {
107 return false;
108 }
109 else
110 {
111 PNODE r = pStack->pTop;
112 *pVal = r->data;
113 pStack->pTop = r->pNext;
114 free(r);
115 r = NULL;
116
117 return true;
118 }
119 }
120
121 void clear(PSTACK pStack)
122 {
123 if (empty(pStack))
124 return;
125 else
126 {
127 PNODE p = pStack->pTop;
128 PNODE q =NULL;
129
130 while (p != pStack->pBottom)
131 {
132 q = p->pNext;
133 free(p);
134 p = q;
135 }
136 }
137 pStack->pTop = pStack->pBottom;
138 }
应用
函数调用
中断
表达式求职
内存分配
缓冲处理
迷宫
线性结构两种常见应用之二 队列
定义
可以实现“先进先出”的存储结构
分类
链式队列 --用链表实现
静态队列 --用数组实现
静态队列通常都必须是循环队列
循环队列的讲解
静态队列为什么必须是循环队列
非循环队列的话，出列后 front会一直++，空间只能使用一次，会造成空间的浪费
循环队列需要几个参数来确定
需要2个参数来确定front,rear
循环队列各个参数的含义
2个参数不同场合有不同的含义
建议初学者先记住，然后慢慢体会
1）队列初始化
front和rear的值都是0
2）队列非空
front代表是队列的第一个元素
rear代表的是队列的最后一个有效元素的下一个元素
3）队列空
front和rear的值相等，但不一定是0
循环队列入队伪算法讲解
两步完成：
1.将值r所代表的位置伪算法
2.错误的写法 rear = rear + 1
正确的写法 rear = (rear + 1) % 数组的长度
循环队列出队伪算法讲解
front = (front+ 1) % 数组的长度
如何判断循环队列是否为空
如果front与rear的值相等，则该队列就一定为空
如何判断循环队列是否已满
预备知识
front的值可能比rear大，也完全有可能比rear小，当然也可能相等
两种方式：
1.多增加一个标识参数
2.少用一个元素【通常使用第二种方式】
if((r+1)%数组长度 == f)
已满
else
不满
算法
入队
出队
1 # include
2 # include
3
4 typedef struct Queue
5 {
6 int* pBase;
7 int front;
8 int rear;
9 }QUEUE;
10
11 void init(QUEUE*);
12 bool en_queue(QUEUE*, int val); //入队
13 void traverse_queue(QUEUE*);
14 bool full_queue(QUEUE*);
15 bool out_queue(QUEUE*, int*); //出队
16 bool empty_queue(QUEUE*);
17
18 int main(void)
19 {
20 QUEUE Q;
21 int val;
22
23 init(&Q);
24 en_queue(&Q, 1);
25 en_queue(&Q, 2);
26 en_queue(&Q, 3);
27 en_queue(&Q, 4);
28 en_queue(&Q, 5);
29 en_queue(&Q, 6);
30
31 traverse_queue(&Q);
32
33 if (out_queue(&Q, &val))
34 {
35 printf("出队成功，队列出队的元素是%d\n", val);
36 }
37 else
38 {
39 printf("出队失败！\n");
40 }
41
42 traverse_queue(&Q);
43
44 return 0;
45 }
46
47 void init(QUEUE* pQ)
48 {
49 pQ->pBase = (int*)malloc(sizeof(int) * 6);
50 pQ->front = 0;
51 pQ->rear = 0;
52 }
53
54 bool full_queue(QUEUE * pQ)
55 {
56 if ((pQ->rear + 1) % 6 == pQ->front)
57 return true;
58 else
59 return false;
60 }
61
62 bool en_queue(QUEUE* pQ, int val)
63 {
64 if (full_queue(pQ))
65 {
66 return false;
67 }
68 else
69 {
70 pQ->pBase[pQ->rear] = val;
71 pQ->rear = (pQ->rear + 1) % 6;
72 return true;
73 }
74 }
75
76 void traverse_queue(QUEUE* pQ)
77 {
78 int i = pQ->front;
79
80 while (i != pQ->rear)
81 {
82 printf("%d ", pQ->pBase[i]);
83 i = (i + 1) % 6;
84 }
85 printf("\n");
86
87 return;
88 }
89
90 bool empty_queue(QUEUE * pQ)
91 {
92 if (pQ->front == pQ->rear)
93 return true;
94 else
95 return false;
96 }
97
98 bool out_queue(QUEUE* pQ, int* pVal)
99 {
100 if (empty_queue(pQ))
101 {
102 return false;
103 }
104 else
105 {
106 *pVal = pQ->pBase[pQ->front];
107 pQ->front = (pQ->front + 1) % 6;
108
109 return true;
110 }
111 }
队列的具体应用
所有和时间有关的操作都有队列的影子