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
| #include <stdio.h>
#define maxSize 7
typedef struct {
char data;
int cur;
}component;
// 将结构体数组中所有分量链接到备用链表中
void reserveArr(component *array);
// 初始化静态链表
int initArr(component *array);
// 向链表中插入数据, body 表示链表的头结点在数组中的位置, add 表示插入元素的位置
// a 表示要插入的数据
void insertArr(component * array,int body,int add,char a);
// 删除链表中含有字符 a 的结点
void deletArr(component * array,int body,char a);
// 查找存储有字符 elem 的结点在数组的位置
int selectElem(component * array,int body,char elem);
// 将链表中的字符 oldElem 改为 newElem
void amendElem(component * array,int body,char oldElem,char newElem);
// 输出函数
void displayArr(component * array,int body);
// 从备用链表中摘除空闲节点的实现函数
int mallocArr(component * array);
// 将摘除下来的节点链接到备用链表上
void freeArr(component * array,int k);
int main() {
component array[maxSize];
int body=initArr(array);
printf("静态链表为：\n");
displayArr(array, body);
printf("在第3的位置上插入结点‘e’:\n");
insertArr(array, body, 3,'e');
displayArr(array, body);
printf("删除数据域为‘a’的结点:\n");
deletArr(array, body, 'a');
displayArr(array, body);
printf("查找数据域为‘e’的结点的位置:\n");
int selectAdd=selectElem(array,body ,'e');
printf("%d\n",selectAdd);
printf("将结点数据域为‘e’改为‘h’:\n");
amendElem(array, body, 'e', 'h');
displayArr(array, body);
return 0;
}
// 创建备用链表
void reserveArr(component *array){
for (int i=0; i<maxSize; i++) {
// 将每个数组分量链接到一起
array[i].cur=i+1;
array[i].data=' ';
}
// 链表最后一个结点的游标值为 0
array[maxSize-1].cur=0;
}
// 初始化静态链表
int initArr(component *array){
reserveArr(array);
int body=mallocArr(array);
// 声明一个变量, 把它当指针使, 指向链表的最后的一个结点, 因为链表为空, 所以和头结点重合
int tempBody=body;
for (int i=1; i<5; i++) {
// 从备用链表中拿出空闲的分量
int j=mallocArr(array);
// 将申请的空线分量链接在链表的最后一个结点后面
array[tempBody].cur=j;
// 给新申请的分量的数据域初始化
array[j].data='a'+i-1;
// 将指向链表最后一个结点的指针后移
tempBody=j;
}
// 新的链表最后一个结点的指针设置为 0
array[tempBody].cur=0;
return body;
}
void insertArr(component * array,int body,int add,char a){
int tempBody=body;
for (int i=1; i<add; i++) {
tempBody=array[tempBody].cur;
}
int insert=mallocArr(array);
array[insert].cur=array[tempBody].cur;
array[insert].data=a;
array[tempBody].cur=insert;
}
void deletArr(component * array,int body,char a){
int tempBody=body;
// 找到被删除结点的位置
while (array[tempBody].data!=a) {
tempBody=array[tempBody].cur;
// 当 tempBody 为 0 时, 表示链表遍历结束, 说明链表中没有存储该数据的结点
if (tempBody==0) {
printf("链表中没有此数据");
return;
}
}
// 运行到此, 证明有该结点
int del=tempBody;
tempBody=body;
// 找到该结点的上一个结点, 做删除操作
while (array[tempBody].cur!=del) {
tempBody=array[tempBody].cur;
}
// 将被删除结点的游标直接给被删除结点的上一个结点
array[tempBody].cur=array[del].cur;
freeArr(array, del);
}
int selectElem(component * array,int body,char elem){
int tempBody=body;
// 当游标值为 0 时, 表示链表结束
while (array[tempBody].cur!=0) {
if (array[tempBody].data==elem) {
return tempBody;
}
tempBody=array[tempBody].cur;
}
// 返回 -1, 表示在链表中没有找到该元素
return -1;
}
void amendElem(component * array,int body,char oldElem,char newElem){
int add=selectElem(array, body, oldElem);
if (add==-1) {
printf("无更改元素");
return;
}
array[add].data=newElem;
}
void displayArr(component * array,int body){
// tempBody 准备做遍历使用
int tempBody=body;
while (array[tempBody].cur) {
printf("%c,%d ",array[tempBody].data,array[tempBody].cur);
tempBody=array[tempBody].cur;
}
printf("%c,%d\n",array[tempBody].data,array[tempBody].cur);
}
// 提取分配空间
int mallocArr(component * array){
// 若备用链表非空, 则返回分配的结点下标, 否则返回 0 (当分配最后一个结点时, 该结点的游
// 标值为 0)
int i=array[0].cur;
if (array[0].cur) {
array[0].cur=array[i].cur;
}
return i;
}
// 将摘除下来的节点链接到备用链表上
void freeArr(component * array,int k){
array[k].cur=array[0].cur;
array[0].cur=k;
}
/*
静态链表为：
,2 a,3 b,4 c,5 d,0
在第3的位置上插入结点‘e’:
,2 a,3 b,6 e,4 c,5 d,0
删除数据域为‘a’的结点:
,3 b,6 e,4 c,5 d,0
查找数据域为‘e’的结点的位置:
6
将结点数据域为‘e’改为‘h’:
,3 b,6 h,4 c,5 d,0
*/
|
