链表
- 链表的基本概念
- 单向链表的操作
- 其他链表的概念及应用
链表的基本概念
定义：链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现一种线性的存储结构。
特点：链表是由咦嘻嘻额的节点（链表中每一个元素称为节点）组成，节点在运行时动态生成(malloc/calloc),每个节点包括两个部分：
- 一个是存储数据的
数据域
- 另一个是存储下一个节点地址的
指针域
链表的构成：
拓展：数组分为静态数组和动态数组
链表节点的定义（结构体实现）
1
2
3
4
5
6
7
8
9
10
|
typedef struct stu{
int num;
char name[32];
float score;
struct stu *next;
}STU;
|
静态链表（玩玩）
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
| #include <stdio.h>
typedef struct stu{
int num;
char name[32];
float score;
struct stu *next;
}STU;
int main(int argc,char *argv[])
{
STU data1={100,"lucy",60};
STU data2={101,"bob",87};
STU data3={102,"mack",65};
STU data4={103,"jane",93};
STU *head=NULL;
head=&data1;
data1.next=&data2;
data2.next=&data3;
data3.next=&data4;
data4.next=NULL;
STU *pb=head;
while(pb != NULL){
printf("num=%d name=%s score=%f\n",pb->num,pb->name,pb->score);
pb=pb->next;
}
return 0;
}
|
运行结果：
动态链表（分文件、分函数实现）
案例：学生信息系统
main.c link.c link.h
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
| #define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
void stu_help(void);
int main(int argc, char* argv[]) {
stu_help();
while (1) {
char cmd[32] = "";
printf("请输入操作指令:\n");
scanf("%s", cmd);
if (strcmp(cmd, "help") == 0)
{
stu_help();
}
else if(strcmp(cmd, "insert") == 0){
printf("-------inset--------\n");
}
else if (strcmp(cmd, "print") == 0) {
printf("-------print--------\n");
}
else if (strcmp(cmd, "delete") == 0) {
printf("-------delete--------\n");
}
else if (strcmp(cmd, "free") == 0) {
printf("-------free--------\n");
}
else if (strcmp(cmd, "quit") == 0) {
break;
}
}
return 0;
}
void stu_help(void) {
printf("###################################\n");
printf("#help:打印帮助信息 #\n");
printf("#insert:插入链表节点 #\n");
printf("#print:遍历链表节点信息 #\n");
printf("#search:查询链表节点 #\n");
printf("#delete:删除链表节点 #\n");
printf("#free:释放链表 #\n");
printf("#quit:退出 #\n");
printf("###################################\n");
return;
}
|
2、insert功能实现
1、链表插入之头部之前插入
link.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#ifndef __LINK_H__
#define __LINK_H__
typedef struct stu {
int num;
char name[32];
float score;
struct stu* next;
}STU;
extern STU* insert_link(STU* head, STU tmp);
extern void pritn_link(STU* head);
#endif
|
link.c
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
| #include"link.h"
#include<stdio.h>
#include<stdlib.h>
STU* insert_link(STU* head, STU tmp) {
STU* pi = (STU*)calloc(1, sizeof(STU));
if (pi == NULL) {
perror("calloc");
return head;
}
*pi = tmp;
pi->next = NULL;
if (head == NULL) {
head = pi;
}
else {
pi->next = head;
head = pi;
}
return head;
}
void pritn_link(STU *head){
if (head == NULL) {
printf("链表不存在\n");
return;
}
else
{
STU* pb = head;
while (pb != NULL) {
printf("num=%d name=%s score=%f\n", pb->num, pb->name, pb->score);
pb = pb->next;
}
}
return;
}
|
运行结果：
2、链表插入之尾部插入
link.c
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
|
STU* insert_link(STU* head, STU tmp) {
STU* pi = (STU*)calloc(1, sizeof(STU));
if (pi == NULL) {
perror("calloc");
return head;
}
*pi = tmp;
pi->next = NULL;
if (head == NULL) {
head = pi;
}
else {
STU* pb = head;
while (pb->next != NULL) {
pb = pb->next;
}
pb->next = pi;
return head;
}
return head;
}
|
4、链表的有序插入
以num的顺序从小到大插入
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
|
STU* insert_link(STU* head, STU tmp) {
STU* pi = (STU*)calloc(1, sizeof(STU));
if (pi == NULL) {
perror("calloc");
return head;
}
*pi = tmp;
pi->next = NULL;
if (head == NULL) {
head = pi;
}
else {
STU* pb = head, * pf = head;
while (pi->num > pb->num && pb->next!=NULL) {
pf = pb;
pb = pb->next;
}
if (pi->num <= pb->num) {
if (pb == head) {
pi->next = head;
head = pi;
return head;
}
else
{
pi->next = pb;
pf->next = pi;
return head;
}
}
else if (pi->num > pb->num && pb->next == NULL)
{
pb->next = pi;
return head;
}
}
return head;
}
|