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
| #include<iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef struct Node//结点
{
int data;//数据域
struct Node *next;//指针域
}NODE, *PNODE;//NODE等价于struct Student st||PNODE等价于struct Node *next
PNODE InputStudent(void)
{
int len;
NODE stu;
PNODE pHead = (PNODE)malloc(sizeof(NODE));//定义一个头结点并且为头结点分配内存
if(NULL == pHead) //判断内存是否为空
{
printf("内存分配失败,程序终止!\n");
exit(-1);
}
PNODE pTail = pHead;//定义一个指向头结点的指针
pTail->next = NULL;//清空指针域
printf("请输入个数:");
scanf("%d",&len);
for(int i=0; i<len; i++)
{
printf("请输入第%d个:\n", i+1);
cin>>stu.data;
PNODE pNew = (PNODE)malloc(sizeof(NODE)); //为新节点分配内存
if(NULL == pNew) //判断内存是否为空
{
printf("内存分配失败,程序终止!\n");
exit(-1);
}
pNew->data = stu.data;//初始化结点的数据域
pTail->next = pNew;//将新结点挂到老结点后
pNew->next = NULL;//清空新结点的指针域
pTail = pNew;//将pTail移到新结点上
}
return pHead;
}
void OutputStudent(PNODE pHead)//输出链表
{
PNODE p = pHead->next;//定义一个指针用于遍历
printf("\n数据如下:\n");
while(NULL != p)
{
printf("%d ", p->data);
p = p->next;
}
}
void DeleteEqual(PNODE &pHead){ //删除链表中的重复元素
PNODE p,q,prev;
if (p=pHead->next){
prev=p;
p=p->next;
}
while (p){
if (p->data==prev->data){
q=p;
p=p->next;
prev->next=p;
free(q);
}
else
{
prev=p;
p=p->next;
}
}
}
void DeleteSelect(PNODE &pHead,int min,int max){ //删除递增有序链表中大于min，小于max的元素
PNODE p=pHead,minPrev,maxPrev;
int flag=0;
while (p->next){
if(p->next->data>min&&!flag){
minPrev=p;
flag=1;
}
if(p->next->data>=max){
maxPrev=p;
break;
}
p=p->next;
}
PNODE temp,start;
start=minPrev->next;
while(start->data!=maxPrev->data){
temp=start;
start=start->next;
free(temp);
temp=NULL;
}
minPrev->next=maxPrev->next;
free(maxPrev);
maxPrev=NULL;
}
void LinkListReverse(PNODE &L){ //逆置链表
PNODE pre,current,nextNode; //三个指针维持实现逆置
pre=L->next;
current=pre->next;
nextNode=current->next;
pre->next=NULL; //逆置之后为最后一个
while(nextNode->next){ //三指针依次后移实现逆置
current->next=pre;
pre=current;
current=nextNode;
nextNode=nextNode->next;
}
//循环出来后，最后的指针逆置
current->next=pre;
nextNode->next=current;
L->next=nextNode; //头结点放上就行了
}
PNODE re_list(NODE *node) { //递归
if (node == NULL|| node->next == NULL) return node;
else{
NODE *head = re_list(node->next); //一直到最后一个，head为最后一个的引用，下面的语句反向
node->next->next = node;
node->next = NULL; //逆置后的最后一个指向空
return head;
}
}
void LinkListReverse2(PNODE &pHead){ //逆置链表
if (pHead == NULL || pHead->next == NULL){
return ;
}
NODE *tmp = re_list(pHead);
pHead = tmp;
}
int main(){
PNODE L= InputStudent();
cout<<endl<<"输入的数据如下:";
OutputStudent(L);
// DeleteEqual(L);
// cout<<endl<<"删除后:";
// OutputStudent(L);
// LinkListReverse2(L->next);
// cout<<endl<<"逆置后:";
// OutputStudent(L);
DeleteSelect(L,2,10);
cout<<endl<<"删除后:";
OutputStudent(L);
return 0;
}
|
