整合建立输出增删改查的链表

简单贴一下链表的建立等常用操作

链表定义

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和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
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
#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct Student)

//输入格式 1 89
// 2 99
// 0 0
struct Student {
long num;
float score;
struct Student *next;
};
int n;
struct Student *creat();
struct Student *del(struct Student *head,long num);
struct Student *insert(struct Student *head,struct Student *stu);
void print(struct Student *head);
int main() {

struct Student *head,*stu;
long del_num;
printf("请输入数据:\n");
head=creat();
print(head);
printf("请输入要删除的数字:\n");
scanf("%ld",&del_num);
while(del_num!=0) { //当输入的学号为0时结束循环
head=del(head,del_num); //删除结点后返回链表的头地址
print(head); //输出全部结点
printf("请输入要删除的数字:\n");
scanf("%ld",&del_num);
}
printf("请输入要添加的数据:\n");
stu=(struct Student *)malloc(LEN); //开辟一个新结点
scanf("%ld %f",&stu->num,&stu->score);
while(stu->num!=0) { //当输入的学号为0时结束循环
head=insert(head,stu); //返回链表的头地址,赋值给head
print(head); //输出全部结点
printf("请输入要添加的数据:\n");
stu=(struct Student *)malloc(LEN); //开辟一个新结点
scanf("%ld %f",&stu->num,&stu->score);
}
return 0;
}

struct Student *creat(void) { //返回一个指向链表头的指针
struct Student *head;
struct Student *p1,*p2;
n=0;
p1=p2=(struct Student *)malloc(LEN);//开辟一个新的结点使p1,p2指向它
scanf("%ld %f",&p1->num,&p1->score);//输入第1个学生的学号和成绩
head=NULL;
while(p1->num!=0) {
n=n+1;
if(n==1) { //如果这个结点是头结点,那么就把head指向p1
head=p1;
} else {
p2->next=p1; //如果不是,则使这个结点的next指向新开辟结点
}
p2=p1; //使p2指向刚才建立的结点
p1=(struct Student *)malloc(LEN);//生成新的结点 ,使p1指向它
scanf("%ld %f",&p1->num,&p1->score);
}
p2->next=NULL; //当p2是表尾时,把NULL赋值给next,结束链表建立
return(head);
}

void print(struct Student *head) {
struct Student *p;
printf("\nNow,These %d records are:\n",n);
p=head;
if(head!=NULL) {
do {
printf("%ld %5.1f\n",p->num,p->score);
p=p->next;
} while(p!=NULL);
}
}

struct Student *insert(struct Student *head,struct Student *stu) {
struct Student *p0,*p1,*p2;
p1=head; //使p1指向头结点
p0=stu; //指向要插入的结点
if(head==NULL) { //原来的链表是空表
head=p0;
p0->next=NULL;
} else {
while((p0->num>p1->num)&&(p1->next!=NULL)) {
p2=p1; //使p2指向刚才p1指向的结点
p1=p1->next;//p1后移一个结点
}
if(p0->num<p1->num) {
if(head==p1) {
head=p0; //插到原来第1个结点之前
} else {
p2->next=p0;//插到p2指向的结点之后
p0->next=p1;
}
} else {
p1->next=p0;
p0->next=NULL; //插到最后的结点之后
}
}
n=n+1;
return(head); //结点数+1
}

struct Student *del(struct Student *head,long num) {
struct Student *p1,*p2;
if(head==NULL) {
printf("这是一张空表\n");
return(head);
}
p1=head; //使p1指向第1个结点
while(num!=p1->num&&p1->next!=NULL) { //p1指向的不是所要找的结点且后面还有结点
p2=p1;
p1=p1->next; //p1向后移一个结点
}
if(num==p1->num) { //找到了
if(p1==head) { //若p1指向的是首结点,把第2个结点地址赋予head
head=p1->next;
} else { //否则将下一个结点地址赋给前一结点地址
p2->next=p1->next;
}
printf("删除:%ld\n",num);
n=n-1;
} else {
printf("%ld没有找到\n",num);//找不到该结点
}
return(head);

}
打赏了解一下?
0%