王道数据结构 C++/C实现单链表（带头结点）的建立，删除，查找（可直接运行）_c++查找链表

王道数据结构 -----C++/C实现单链表（带头结点）的建立，删除，查找（可直接运行）

#include<bits/stdc++.h>
#include <stdlib.h>
#include <stdio.h>
typedef int ElemType;
typedef struct LNode{
	ElemType data;
	struct LNode *next; 
}LNode, *LinkList; 
//typedef struct LNode LNode等价于struct LNode = LNode (LNode* 强调返回的是结点 )。
//typedef struct LNode* *LinkList等价于struct LNode* = LinkList (LinkList* 强调返回的是结点 )
//初始化一个单链表 
bool InitList(LinkList &L){
	L = (LNode*)malloc(sizeof(LNode));//L作为头结点指向分配空间的第一个节点 
	if(L == NULL) return false; //分配失败 
	L-> next = NULL; //头结点之后设为空 
	return true;
} 
///带头结点/ 

//查找第i-1个节点
LNode * Find_i_1(LinkList L, ElemType i){
	if(i<1) return false;
	LNode *p;//指针p指向当前扫描的结点 
	int j=0;//j表示p当前指向的结点 
	p=L; //L指向头指针，头指针是第0个节点，不存数据 
	while(p!=NULL &&j<i-1){ //循环找到第i-1个结点 
		p=p->next;
		j++; 
	}
	return p; //返回找到的第 i-1个结点 
} 
//****************** ************************  插入  ******************

//指定结点后插操作:给一个结点p，在之后插入元素e 
bool InsertNextNode(LNode *p, ElemType e){
	if(p == NULL) return false;
	LNode *s =(LNode *) malloc(sizeof(LNode)); //申请一个节点 
	if(s == NULL) return false;
	s->data = e;   //将插入元素的值给新节点 
	s->next = p->next;//使新结点指向第i个节点 
	p->next = s;//将i-1指向新节点，这一步使新节点插入到i-1结点和i结点之间，成为新的i结点 
	return true;
} 
//按位序插入，在表中第i个位置上插入指定元素e,(也算带头结点后插） 
bool ListInsert(LinkList &L,ElemType i,ElemType e){
	if(i<1) return false; 
	LNode *p =(LNode *) malloc(sizeof(LNode));
	p = Find_i_1(L,i);
	return InsertNextNode(p,e);
} //时间复杂度为O(n) 

//指定节点前插操作：未知头指针，在p结点前插入元素e：通过在p后插入结点s，然后将p的值给s，e值给p，实现表面上的前插 
bool InsertPriorNode_e(LNode *p,ElemType e){
	if(p==NULL) return false;
	LNode *s = (LNode *) malloc(sizeof(LNode));
	if(s==NULL) return false;//内存分配失败 
	s->next =p->next; //s结点指向p结点之后 
	p->next =s;       //p结点指向s结点，即将p结点之后增加了s结点 
	s->data =p->data; //将p的值给s 
	p->data =e;      //将p的值变为插入的元素e 
	return true; 
}
//（带头结点）指定节点前插操作：未知头指针，在p结点前插入结点s： 
bool InsertPriorNode_s(LNode *p,LNode *s){
	if(p==NULL||s == NULL) return false;
	s->next=p->next;
	p->next = s;    //p结点指向s结点，即将p结点之后增加了s结点 
	ElemType temp = p->data;//交换数据域部分 
	p->data = s->data;
	s->data =temp; 
	return true; 
} 
//指定结点前插操作：已知头指针， 在p结点前插入e(循环查找p的前面那一个节点s，然后对s节点进行后插)
bool L_InsertPriorNode(LinkList &L,LNode *p,ElemType e){
	LNode *s =(LNode *) malloc(sizeof(LNode));
	if(s == NULL) return false;
	s = L; 
	while(s!=NULL && s->next!=p){
		s = s->next;
	}
	return InsertNextNode(s,e);
}
*********** **********************删除 *************

//按位序删除节点 
bool ListDelete(LinkList &L, int i, ElemType &e){
	if(i<1) return false; 
	LNode* p = Find_i_1(L,i);//找到i-1个节点；
	if( p == NULL|| p->next ==NULL) return false; //p结点为空，或者i-1个结点后面为空
	LNode *s = p->next; //令s指向被删除的结点
	e = s->data;//返回被删除的e 
	p->next = s->next; //删除结点p；
	free(s);
	return true; 	 
} //时间负责度O(n)

//指定结点删除（等于将后继的值给p然后把后继删除 
 bool DeletedNode(LNode *p){
 	if(p==NULL) return false;
 	int e =-2;
 	LNode *s = p->next; //令s指向删除的p结点后继 
 	e =p->data;
	p->data = p->next->data;//让p与其后继交换数据域 
	p->next = s->next; //让p指向后继结点的后继，即删除了后继结点 
	printf("删除成功! 删除值为：%d", e); 
	free(s);
	return true; 
 } //O(1)
 //按位查找
 LNode *GetElem(LinkList L ,int i){
 	if(i<0) return NULL;
 	LNode *p = Find_i_1(L,i);//找到i-1个节点；
 	return p->next;
 } //O(n)
 //按值查找 
 LNode *LocateElem(LinkList L, ElemType e){
 	LNode *p = L->next;//p指向第一个结点
	 while(p!=NULL && p->data!=e){
	 	p=p->next;
	 }
	 return p;//返回找到的结点； 
 }
 //求单链表长度
 int  Length(LinkList L){
 	int len =0;//记录表长 
 	LNode *p =L;
 	while(p->next!=NULL){//当p结点后面是NULL时，说明现在已经计数到了NUll前一个结点即最后一个节点 
 		p = p->next;
 		len++;
	 }
	 return len; 
 }//O（n） 
 //头插法建立单链表 
 LinkList List_HeadInsert(LinkList &L){//逆向建立单链表 
 	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode)); //建立头结点 
	L->next = NULL; //初始为空链表
	scanf("%d",&x); //输入插入值 
	while(x!=-1){
	 	LNode *s =(LNode *) malloc(sizeof(LNode));
	 	s->data =x;
	 	s->next = L->next;//值为x的s结点指向L指向的结点 
	 	L->next =s;//L指向s结点，头部插入成功 
	 	scanf("%d",&x);
	 	//printf("插入成功  ",s->data);
	 }
	 //printf("\n"); 
	 return L; 
 } //O（n） 
 //尾插建立单链表 
LinkList List_TailInsert(LinkList &L){
    int x;
    L = (LinkList)malloc(sizeof(LNode));//建立头结点
	L->next = NULL; //初始为空链表
	LNode *s,*r = L;//s携带x的结点，,r指向尾指针 
	scanf("%d",&x); //输入插入值 
    while(x!=-1){
	 	s =(LNode *) malloc(sizeof(LNode));
	 	s->data =x;
	 	r->next = s;//尾指针指向值为x的s结点
	 	r = s;//尾指针更新为新节点，L链上已经插入x值 
	 	scanf("%d",&x);
	 	//printf("插入成功：%d \n",s->data);
	 }
	 r->next = NULL;//尾结点指针置空
	 return L; 
}
/
int main(){
	LinkList L;
	InitList(L);//初始化L 
	LNode *p;
//头插法建立单链表 3 2 3 4 5 6 8 9 4 -1
    List_HeadInsert(L);
    p=L;
	while(p->next!=NULL){
		p = p->next;
		printf("%d ",p->data);
	} 

//尾插法建立单链表 3 2 3 4 5 6 8 9 4 -1
/**	List_TailInsert(L);
	p=L;
	while(p->next!=NULL){
		p = p->next;
		printf("%d ",p->data);
	} 
**/
//按位插入，在第四个位置插入-3	
/**	ListInsert(L,4,-3);
		while(p->next!=NULL){
		p = p->next;
		printf("%d ",p->data);
	} 

//（带头结点）指定结点后插操作:给一个结点p，在之后插入元素e 
    LNode *q;  
    q=L->next->next->next;//第三个结点后插入-2 
    ElemType e = -2;
    InsertNextNode(q, e);


//（带头结点）指定节点前插操作：未知头指针，在p结点前插入元素e：
    LNode *q;  
    q=L->next->next->next;//给定第三个结点 ，在第三个结点前插入-2 
    ElemType e = -2;
    InsertPriorNode_e(q, e);


//（带头结点）指定节点前插操作：未知头指针，在p结点前插入结点s：
    LNode *q;  
    q=L->next->next->next;//给定第三个结点 ，在第三个结点前插入-结点s 
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = -2;
    InsertPriorNode_s(q, s);


//（带头结点）指定结点前插操作：已知头指针， 在p结点前插入e
    LNode *q;  
    q=L->next->next->next;//给定第三个结点 ，在第三个结点前插入-结点s 
    ElemType e = -2;
    L_InsertPriorNode(L,q,e);



//按位序删除节点
    ElemType e = -2;
    ListDelete(L, 3, e);
    printf("删除成功! 删除值为：%d", e); 

//指定结点删除
    LNode *q;  
    q=L->next->next->next;//删除第三个节点 
    DeletedNode(q);
 

  //按位查找
    LNode *q= GetElem(L ,3);
    printf("查找到结点值为：%d", q->data); 
  **/  
     
/**
  //按值查找 
 LocateElem(LinkList L, ElemType e)
  //求单链表长度
**/

printf("\n单链表长度为：%d", Length(L)); 

	return 0;
}
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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252