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
|
/**
说明：带头节点链表的C语言实现
author : gsscsd
data : 2017-3-13
**/
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define MaxSize 100
//定义链表节点
typedef struct Lnode
{
ElemType data;
struct Lnode *next;
}LinkList;
//初始化链表
void InitList(LinkList **list);
//遍历链表
void Traverse(LinkList *list);
//查找指定位置元素
ElemType GetElem(LinkList *list,int p);
//在指定位置插入元素,失败返回-1，成功返回1
int InsertList(LinkList **list,int p,ElemType e);
//删除指定位置的元素,失败返回-1，成功返回1
int DeleteList(LinkList **list,int p,ElemType *e);
//链表是否为空，空返回1
int IsEmpty(LinkList *list);
//计算链表长度，返回链表长度
int LengthList(LinkList *list);
//主函数
int main(int argc, char const *argv[])
{
LinkList *list = NULL;
ElemType e = 9;
InitList(&list);
//插入元素
InsertList(&list,4,e);
//删除元素
DeleteList(&list,4,&e);
//查找元素
e = GetElem(list,3);
printf("Find Elem is :%d\n",e);
Traverse(list);
return 0;
}
//初始化链表
void InitList(LinkList **list)
{
puts("InitList");
int i = 0,n = 0;
*list = malloc(sizeof(LinkList));
LinkList *temp,*rNext;
// (*list)->next = NULL;
rNext = *list;
puts("Input InitList Numbers:");
scanf("%d",&n);
for(i = 0; i < n; i++)
{
temp = malloc(sizeof(LinkList));
puts("Input Number:");
scanf("%d",&(temp->data));
//接下来有两种方法，头插，尾差，这里采用尾差
rNext->next = temp;
rNext = rNext->next;
}
rNext->next = NULL;
}
//遍历链表
void Traverse(LinkList *list)
{
puts("Begin Traverse:");
LinkList *temp = list->next; //临时变量，方便遍历
while(temp != NULL)
{
printf("%d\t",temp->data);
temp = temp->next;
}
putchar('\n');
puts("Finished Traverse.");
}
//查找指定位置的元素
ElemType GetElem(LinkList *list,int p)
{
printf("Find %d Elem:\n",p);
if((p<0)||(p>LengthList(list)))
{
return -1;
}
else
{
LinkList *rNext = list->next;
for(int i = 0;i<p-1;i++)
{
rNext = rNext->next;
}
puts("End Find.");
return rNext->data;
}
}
//在指定位置插入元素,失败返回-1，成功返回1
int InsertList(LinkList **list,int p,ElemType e)
{
if((p<0)||(p>LengthList(*list)+1))
{
return -1;
}
else
{
printf("Begin Insert Elem:%d\n",e);
int i = 0;
LinkList *temp = malloc(sizeof(LinkList)); //一个暂时变量
LinkList *rNext = *list; //其实感觉这里应该是(*list)->next
LinkList *q;
temp->data = e;
while(i < p-1) //p-1,这里的bug是运算符优先级，找了好久
{
rNext = rNext->next;
i++;
}
//以下是尾插法
if(!IsEmpty(rNext))
{
q = rNext->next;
rNext->next = temp;
temp->next = q;
puts("End Insert.");
return 1;
}
return -1;
}
}
//删除指定位置的元素,失败返回-1，成功返回1
int DeleteList(LinkList **list,int p,ElemType *e)
{
if((p<0)||(p>LengthList(*list)))
{
return -1;
}
else
{
puts("Begin Delete Elem:");
int i = 0;
LinkList *rNext = (*list)->next;
LinkList *temp;
while(i<p-2) //注意是这里p-2,我们要找到删除元素的前一个节点,没毛病
{
i++;
rNext = rNext->next;
}
if(!IsEmpty(rNext))
{
temp = rNext->next;
*e = temp->data;
rNext->next = temp->next;
free(temp);
printf("End Delete:%d\n",*e);
return 1;
}
}
}
//链表是否为空，空返回1
int IsEmpty(LinkList *list)
{
if(list->next == NULL)
{
return 1;
}
return 0;
}
//计算链表长度，成功返回链表长度
int LengthList(LinkList *list)
{
LinkList *rNext = list->next;
int length = 0;
while(rNext != NULL)
{
length++;
rNext = rNext->next;
}
return length;
}
|
