本文实例讲述了C语言实现的循环单链表功能。分享给大家供大家参考,具体如下:
SClist.h
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
|
#ifndef __SCLIST_H__
#define __SCLIST_H__
#include<cstdio>
#include<malloc.h>
#include<assert.h>
typedef int ElemType;
typedef struct Node {
ElemType data;
struct Node *next;
}Node,*PNode;
typedef struct List {
PNode first;
PNode last;
size_t size;
}List;
void InitSClist(List *list); //初始化循环单链表
void push_back(List *list, ElemType x); //在循环单链表的末尾插入元素
void push_front(List *list, ElemType x); //在循环单链表的头部插入元素
void show_list(List *list); //打印循环单链表
void pop_back(List *list); //删除循环单链表的最后一个元素
void pop_front(List *list); //删除循环单链表的第一个元素
void insert_val(List *list, ElemType val); //将数据元素插入到循环单链表中(要求此时循环单链表中的数据元素顺序排列)
Node* find(List *list, ElemType x); //查找循环单链表中数据值为x的结点
int length(List *list); //求循环单链表的长度
void delete_val(List *list, ElemType x); //按值删除循环单链表中的某个数据元素
void sort(List *list); //对循环单链表进行排序
void reverse(List *list); //逆置循环单链表
void clear(List *list); //清除循环单链表
void destroy(List *list); //摧毁循环单链表
//优化
Node* _buynode(ElemType x); //创建结点
#endif
|
SClist.cpp
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
|
#include"SClist.h"
Node* _buynode(ElemType x) {
Node *s = (Node*) malloc ( sizeof (Node));
assert (s != NULL);
s->data = x;
s->next = NULL;
return s;
}
void InitSClist(List *list) {
Node *s = (Node*) malloc ( sizeof (Node));
assert (s != NULL);
list->first = list->last = s;
list->last->next = list->first; //让链表最后一个结点的指针域指向头结点,从而时链表循环
list->size = 0;
}
void push_back(List *list, ElemType x) {
Node *s = _buynode(x);
list->last->next = s;
list->last = s;
list->last->next = list->first;
list->size++;
}
void push_front(List *list, ElemType x) {
Node *s = _buynode(x);
s->next = list->first->next;
list->first->next = s;
if (list->last == list->first)
list->last = s;
list->size++;
}
void show_list(List *list) {
Node *p = list->first->next;
while (p != list->first) {
printf ( "%d->" , p->data);
p = p->next;
}
printf ( "Nul.\n" );
}
void pop_back(List *list) {
if (list->size == 0) return ;
Node *p = list->first;
while (p->next != list->last)
p = p->next;
free (list->last);
list->last = p;
list->last->next = list->first;
list->size--;
}
void pop_front(List *list) {
if (list->size == 0) return ;
Node *p = list->first->next;
list->first->next = p->next;
if (list->size == 1)
list->last = list->first;
free (p);
list->size--;
}
void insert_val(List *list, ElemType x) {
Node *p = list->first;
while (p->next != list->last && p->next->data < x)
p = p->next;
if (p->next == list->last && p->next->data < x)
push_back(list, x);
else {
Node *s = _buynode(x);
s->next = p->next;
p->next = s;
list->size++;
}
}
Node* find(List *list, ElemType key) {
if (list->size == 0) return NULL;
Node *p = list->first->next;
while (p != list->first && p->data != key)
p = p->next;
if (p == list->first)
return NULL;
return p;
}
int length(List *list) {
return list->size;
}
void delete_val(List *list, ElemType x) {
if (list->size == 0) return ;
Node *p = find(list, x);
if (p == NULL) {
printf ( "没有要删除的数据!\n" );
return ;
}
if (p == list->last)
pop_back(list);
else {
Node *q = p->next;
p->data = q->data;
p->next = q->next;
free (q);
list->size--;
}
}
void sort(List *list) {
if (list->size == 0 || list->size == 1) return ;
Node *s = list->first->next;
Node *q = s->next;
list->last->next = NULL;
list->last = s;
list->last->next = list->first;
while (q != NULL) {
s = q;
q = q->next;
Node *p = list->first;
while (p->next != list->last && p->next->data < s->data)
p = p->next;
if (p->next == list->last &&p->next->data < s->data) {
list->last->next = s;
list->last = s;
list->last->next = list->first;
}
else {
s->next = p->next;
p->next = s;
}
}
}
void reverse(List *list) {
if (list->size == 0 || list->size == 1) return ;
Node *p = list->first->next;
Node *q = p->next;
list->last->next = NULL;
list->last = p;
list->last->next = list->first;
while (q != NULL) {
p = q;
q = q->next;
p->next = list->first->next;
list->first->next = p;
}
}
void clear(List *list) {
Node *p = list->first->next;
while (p != list->first) {
list->first->next = p->next;
free (p);
p = list->first->next;
}
list->last = list->first;
list->last->next = list->first;
list->size = 0;
}
void destroy(List *list) {
clear(list);
free (list->first);
list->first = list->last = NULL;
}
|
main.cpp
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
|
#include"SClist.h"
void main() {
List mylist;
InitSClist(&mylist);
ElemType item;
Node *p = NULL;
int select = 1;
while (select) {
printf ( "*******************************************\n" );
printf ( "*[1] push_back [2] push_front *\n" );
printf ( "*[3] show_list [4] pop_back *\n" );
printf ( "*[5] pop_front [6] insert_val *\n" );
printf ( "*[7] find [8] length *\n" );
printf ( "*[9] delete_val [10] sort *\n" );
printf ( "*[11] reverse [12] clear *\n" );
printf ( "*[13*] destroy [0] quit_system *\n" );
printf ( "*******************************************\n" );
printf ( "请选择:>>" );
scanf ( "%d" , &select);
if (select == 0) break ;
switch (select) {
case 1:
printf ( "请输入要插入的数据(-1结束):>" );
while ( scanf ( "%d" , &item), item != -1) {
push_back(&mylist, item);
}
break ;
case 2:
printf ( "请输入要插入的数据(-1结束):>" );
while ( scanf ( "%d" , &item), item != -1) {
push_front(&mylist, item);
}
break ;
case 3:
show_list(&mylist);
break ;
case 4:
pop_back(&mylist);
break ;
case 5:
pop_front(&mylist);
break ;
case 6:
printf ( "请输入要插入的数据:>" );
scanf ( "%d" , &item);
insert_val(&mylist, item);
break ;
case 7:
printf ( "请输入要查找的数据:>" );
scanf ( "%d" , &item);
p = find(&mylist, item);
if (p == NULL)
printf ( "要查找的数据在单链表中不存在!\n" );
break ;
case 8:
printf ( "单链表的长度为%d\n" , length(&mylist));
break ;
case 9:
printf ( "请输入要删除的值:>" );
scanf ( "%d" , &item);
delete_val(&mylist, item);
break ;
case 10:
sort(&mylist);
break ;
case 11:
reverse(&mylist);
break ;
case 12:
clear(&mylist);
break ;
//case 13:
//destroy(&mylist);
//break;
default :
printf ( "选择错误,请重新选择!\n" );
break ;
}
}
destroy(&mylist);
}
|
希望本文所述对大家C语言程序设计有所帮助。
原文链接:http://www.cnblogs.com/duwenxing/p/7606397.html