C语言之单向链表详解及实例代码

时间:2022-10-12 16:42:19

1,单向链简洁。

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指列表中的下一个结点;列表是由结点构成,由head指针指向第一个成为表头的结点而终止于最后一个指向nuLL的指针;

2,例子要求:

根据示例代码中的例子,完成单向链表(single linked list)中的以字符串为数据的链表的插入、删除以及查找,并支持单向链表的反转;

3,代码实现。

?
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
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <memory.h>
#include <malloc.h>
 
 
//节点的定义
typedef struct Node {
 void *data; //数据域 //链域
 struct Node *next;
} NodeStruct, *pNode;
 
 
pNode head = NULL;
 
 
 
 
typedef char (*pCompareFunc)(void *a, void *b);
typedef void* (*pChar)(void *p);
 
 
// 字符串判断
int str_compare(void *a, void *b) {
 char *pa = (char*)a;
 char *pb = (char*)b;
 return strcmp(pa , pb);
}
 
 
// 分配一个节点
pNode allocate_node(void *data, pChar char_func) {
 pNode node = allocate();
 node->data = char_func(data);
 return node;
}
 
 
// 创建节点
pNode allocate() {
 void *p = malloc(sizeof(NodeStruct));
 pNode node = (pNode)p;
 node->next = NULL;
 node->data = NULL;
 return node;
}
 
 
// 添加一个节点
void insertNode(pNode node){
 if (head == null){
  head=node;
  }
  else {
  node->next = head;
  head = node;
  }
}
 
 
void* char_char(void *p) {
 char* pa = (char*)malloc(sizeof(char));
 memcpy(pa, p, sizeof(char));
 return pa;
}
 
 
// 初始化节点
pNode allocate_node(void *data, pChar char_func) {
 pNode node = allocate();
 node->data = char_func(data);
 return node;
}
 
 
 
 
 
 
 
 
 
// 释放资源
void free_list(pNode node) {
 pNode next = node;
 
 
 while (next != NULL) {
  if (next->data != NULL)
   free(next->data);
  pNode temp = next;
  next = next->next;
  free(temp);
 }
}
 
 
// 1.1 添加一个节点
void insert(pNode node) {
 if (head == NULL)
  head = node;
 else {
  node->next = head;
  head = node;
 }
}
 
 
//1.2查找
int str_search(void* data,pCompareFunc compare){
 pNode next = head;
 pNode prev = NULL;
 while (next != NULL ) {
  if (compare(data, next->data) == 0) {
   // 如果查找到了,就退出返回1
   return 1;
   break;
  }
  prev = next;
  next = next->next;
 }
 // 如果一直查找不到,就返回0
 return 0;
}
 
 
// 1.3删除节点
void remove(void* data,pCompareFunc compare) {
 pNode next = head;
 pNode prev = NULL;
 while (next != NULL) {
 
 
  if (compare(data, next->data) == 0) {
   if (prev == NULL) {
    head = next->next;
    next->next = NULL;
    free_list(next);
   } else {
    prev->next = next->next;
    next->next = NULL;
    free_list(next);
   }
   break;
  }
  prev = next;
  next = next->next;
 }
 
 
}
 
 
//1.4反转
void invert_order()
{
  node *This,*prev;
  p=head.next;
  This=NULL;
  while(p) {
    prev=This;
    This=p;
    p=p->next;
    This->next=prev;
 
 
  }
  head.next=This;
}
 
 
 
 
 
 
 
 
void main(){
 // 1单向链表
 char a1[] = 'aaa1';
 char a2[] = 'aaa2';
 char a3[] = 'aaa3';
 // 1.1添加
 insertNode(allocate_node(a1, init_char));
 insertNode(allocate_node(a2, init_char));
 insertNode(allocate_node(a3, init_char));
 // 1.2查找
 int flag = 0;
 flag = str_search(&a2,str_compare);
 // 1.3删除
 remove(&a2,str_compare);
 // 1.4反转
  invert_order();
 
 
}

 以上就是对 C语言单向联表的资料整理,后续继续补充相关资料,谢谢大家对本站的支持!