-
Notifications
You must be signed in to change notification settings - Fork 0
/
list.cpp
155 lines (121 loc) · 2.89 KB
/
list.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
//
// Created by go_fo on 2019/8/1.
//
#include <cstdio>
#include <malloc.h>
typedef struct Node {
int data;
struct Node *pNext;
} Node, *PNode;
PNode create_list();
void traverse_list(PNode);
bool is_empty(PNode);
int length_list(PNode);
bool insert_list(PNode, int, int);
bool delete_list(PNode, int, int*);
void sort_list(PNode);
int main() {
PNode pHead = nullptr;
pHead = create_list();
sort_list(pHead);
traverse_list(pHead);
if (is_empty(pHead)) {
printf("链表为空\n");
}
printf("链表长度为%d\n", length_list(pHead));
insert_list(pHead, -1, 123);
printf("插入后");
traverse_list((pHead));
int *i = nullptr;
delete_list(pHead, 3, i);
printf("删除后");
traverse_list((pHead));
return 0;
}
PNode create_list() {
int len;
int i;
int val;
printf("输入要创建的节点的个数:");
scanf("%d", &len);
PNode pHead = (PNode) malloc(sizeof(Node));
PNode pTail = pHead;
pTail->pNext = nullptr;
for (i = 0; i < len; i++) {
printf("输入第%d个节点的值", i + 1);
scanf("%d", &val);
Node *pNew = (Node *) malloc(sizeof(Node));
pNew->data = val;
pNew->pNext = nullptr;
pTail->pNext = pNew;
pTail = pNew;
}
return pHead;
}
void traverse_list(PNode pNode) {
pNode = pNode->pNext;
printf("链表为");
while (pNode != nullptr) {
printf("%d ", pNode->data);
pNode = pNode->pNext;
}
printf("\n");
}
bool is_empty(PNode pNode) {
return pNode->pNext == nullptr;
}
int length_list(PNode pNode) {
int len = 0;
while (pNode->pNext != nullptr) {
len++;
pNode = pNode->pNext;
}
return len;
};
//只交换数据域
void sort_list(PNode pHead) {
PNode p1 = pHead->pNext;
PNode p2 = p1->pNext;
int len = length_list(pHead);
int cnt = 1;
while (cnt < len) {
while (p2 != NULL) {
if (p1->data > p2->data) {
int tmp = p1->data;
p1->data = p2->data;
p2->data = tmp;
}
p2 = p2->pNext;
}
p1 = p1->pNext;
p2 = p1->pNext;
cnt++;
}
};
bool insert_list(PNode pNode, int pos, int val) {
int len = length_list(pNode);
if (pos > len || pNode == nullptr) return false;
int i = 0;
PNode tmp = pNode;
for (i = 1; i < pos; ++i) {
tmp = tmp->pNext;
}
auto newNode = (PNode) malloc(sizeof(pNode));
newNode->pNext = tmp->pNext;
newNode->data = val;
tmp->pNext = newNode;
return true;
};
bool delete_list(PNode pNode, int pos, int *val) {
int len = length_list(pNode);
if (pos > len || pNode == nullptr) return false;
int i = 0;
PNode tmp = pNode;
for (i = 1; i < pos; ++i) {
tmp = tmp->pNext;
}
PNode toDelete = tmp->pNext;
tmp->pNext = toDelete->pNext;
free(toDelete);
return false;
};