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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{/*单链表节点结构*/
int data;
struct node *next;
}LinkList;
LinkList *head = NULL;
LinkList *AddHeadl(); /*前插入法建表*/
LinkList *AddHead(); /*尾插入法建表*/
LinkList *InitList(); /*初始化单链表*/
void add(); /*插入元素*/
void delete(); /*删除元素*/
LinkList *GetNode(LinkList *head,int i);/*按序号查找*/
LinkList *LocateNode(LinkList *head,int x);/*按值查找*/
int ListLen(LinkList *head); /*求单链表长度*/
void PrintList(LinkList *head); /*遍历链表*/
int main();
LinkList *AddHeadl()
{/*用头插入法建立带头结点的单链表*/
int x;
int flag = -1;
LinkList *head,*p;
head = (LinkList*)malloc(sizeof(LinkList));
head->next = NULL; /*初始化一个空链表，L为头指针*/
printf("输入元素值（-1停止）");
scanf("%d",&x); /*x是和链表结点的数据域值具有相同类型的变量*/
while (x != flag) /*flag为结束输入的标志*/
{
p=(LinkList*)malloc(sizeof(LinkList));/*生成新的结点*/
p->data = x; /*输入元素值*/
p->next = head->next;head->next = p;/*插入到表头*/
printf("输入元素值（-1停止）");
scanf("%d",&x); /*读入下一个元素的值*/
}
return head;
}
LinkList *AddHead()
{/*尾插入法建立一个带头结点的单链表，返回表头指针*/
LinkList *head = (LinkList*)malloc(sizeof(LinkList));
head->next = NULL;
LinkList *q=head,*p;
int x,flag=-1;
printf("输入元素值（-1停止）");
scanf("%d",&x);
while (x!=flag)
{
p=(LinkList *)malloc(sizeof(LinkList));
p->data = x;
if(head ->next==NULL) head->next=p; /*第一个结点的处理*/
else q->next=p; /*其他结点的处理*/
q=p; /*q指向新的尾结点*/
printf("输入元素值（-1停止）");
scanf("%d",&x);
}
if(q!=NULL) q->next=NULL; /*对于非空表，最后结点的指针域放空指针*/
return head;
}
LinkList *InitList()
{
LinkList *head=(LinkList*)malloc(sizeof(LinkList));
if(head==NULL)
{
printf("内存分配失败\n");
exit(1);
}
head->next=NULL;
return head;
}
void add()
{
LinkList *ptr;
int ch1=0,ch2,d;
printf("(在目标位置的下一个结点处添加)1.按序号查找\n2.按值查找\n");
scanf("%d",&ch1);
printf("输入序号或值\n");
scanf("%d",&ch2);
if(ch1==1)
ptr = GetNode(head,ch2);
else if (ch1==2)
ptr = LocateNode(head,ch2);
printf("输入添加的值\n");
scanf("%d",&d);
LinkList *q;
q = (LinkList*)malloc(sizeof(LinkList));/*申请一个新结点，用q保存结点的地址*/
q->data = d; /*把值d写入q所指的结点的数据域*/
q->next = ptr->next; /*令q->next指向ptr所指结点的下一个结点（或NULL）*/
ptr->next = q; /*令ptr->next指向q所指结点*/
}
void delete()
{
LinkList *ptr;
int ch1=0,ch2;
printf("1.按序号删除\n2.按值删除\n");
scanf("%d",&ch1);
printf("输入序号或值\n");
scanf("%d",&ch2);
if(ch1==1)
ptr = GetNode(head,ch2-1);
else if (ch1==2)
{
ptr = head;
while(ptr->next!=NULL&&ptr->next->data != ch2)
ptr = ptr->next;
}
if (ptr==NULL || ptr->next==NULL)
{
printf("未找到目标结点\n");
return;
}
LinkList *q;
q = ptr->next; /*让q指向ptr所指结点的下一个结点*/
ptr->next = q->next; /*令ptr->next指向q所指结点的下一个结点（或NULL）*/
free(q); /*释放q所指结点*/
printf("删除成功\n");
}
LinkList *GetNode(LinkList *head,int i)
{/*在头结点的单链表中查找第i个结点，找到返回该结点指针，否则返回NULL*/
LinkList *p=head;
int j=0;
while(p->next!=NULL&&j<i)
{
j++;
p=p->next; /*p右移一个结点*/
}
if(j==i) return p;
return NULL;
}
LinkList *LocateNode(LinkList *head,int x)
{/*在带头结点的单链表中查找值为x的结点，找到返回结点指针，否则返回NULL*/
LinkList *p=head->next;
while(p!=NULL&&p->data!=x)
p=p->next;
return p;
}
int ListLen(LinkList *head)
{/*在带头结点的单链表求表的长度*/
int len=0;
LinkList *p=head;
while(p->next!=NULL)
{
len++;
p=p->next;
}
return len;
}
void PrintList(LinkList *head)
{
LinkList *p=head->next; /*head结点为空*/
while(p!=NULL)
{
if(p->next!=NULL)
printf("%d->",p->data);
else printf("%d\n",p->data);
p=p->next;
}
}
int main()
{
head = InitList(head);
int ch=1;
while(ch)
{
printf("1.前插入法建表\n2.尾插入法建表\n3.插入元素\n4.删除元素\n5.输出表长\n6.遍历链表\n0.退出\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
head = AddHeadl();
break;
case 2:
head = AddHead();
break;
case 3:
add();
break;
case 4:
delete();
break;
case 5:
int len=ListLen(head);
printf("长度为%d\n",len);
break;
case 6:
PrintList(head);
break;
case 0:
return 0;
default:
printf("没有这个选项");
}
}
}
|