链表的基本操作(数据结构)

单链表

#include 
#include 
#include 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

打印链表 
void PrintList(LNode *p)
{
	LNode *temp;
	temp = p->next;
	printf("链表的顺序:");
	while(temp!=NULL)
	{
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}

//头插法
LinkList HeadInsert(LinkList &L){
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	L->next=NULL;
	printf("请输入数字:");
	scanf("%d",&x);
	while(x!=000){
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		printf("请输入数字:");
		scanf("%d",&x);
	}
	return L;
} 

//尾插法
LinkList TailInsert(LinkList &L){
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s,*r=L;
	printf("请输入数字:");
	scanf("%d",&x);
	while(x!=000){
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		printf("请输入数字:");
		scanf("%d",&x);
	}
	r->next=NULL;
	return L;
} 

//按序号查找结点
LNode *GetElem(LinkList L){
	int i;
	printf("请输入要查找的节点:"); 
	scanf("%d",&i);
	if(i<1) return NULL;
	int j=1;
	LNode *p = L->next;
	while(p!=NULL&&j<i){
		p=p->next;
		j++;
	}
	return p;
} 

//按照值来查找 
int LocateElem(LinkList &L){
	int x;
	int i=0;
	printf("请输入你要查询的数字:");
	scanf("%d",&x);
	LNode *p = L->next;
	while(p!=NULL&&p->data!=x){
		p = p->next;
		i++;
	}
	return i+1;
}

//前插入节点
LinkList ListInsert(LinkList L,int i,int n)//插入一个数(后插法) 
{
	if(i<1) return L;
	LNode *p;
	int j=0;
	p=L->next;
	while(p!=NULL&&j<i-2){
		p=p->next;
		j++;
	}
	if(p==NULL)     //i值不合适 
		return L;
	
	LNode *s = (LNode*)malloc(sizeof(LNode));
	s->data = n;
	s->next = p->next;
	p->next = s;
	printf("success\n"); 
	return L;
} 

//后插入节点
LinkList ListNextInsert(LinkList &L,int i,int n){
	if(i<1) return L;
	LNode *p;
	int j=0;
	p=L->next;
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++;
	}
	if(L==NULL) return L;
	LNode *s = (LNode*)malloc(sizeof(LNode));
	if(s==NULL) return L;
	s->data= n;
	s->next = p->next;
	p->next = s;
	printf("success\n"); 
	return L;
} 


int main(){
	LinkList L;
	HeadInsert(L);
	PrintList(L);
	TailInsert(L);
	PrintList(L);
	//按序号查找
	LNode *p;
	p = GetElem(L);
	printf("查找出来值为:%d\n",p->data);
	//按值查找
	int i;
	i = LocateElem(L);
	printf("找出位置:%d\n",i);
	//前插入
	printf("插入(L,2,99)");
	ListInsert(L,2,99);
	PrintList(L); 
	//后插入
	printf("插入(L,3,99)");
	ListNextInsert(L,3,100);
	PrintList(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

双链表

#include 
#include 
#include 
typedef struct DNode{
	int data;
	struct DNode *prior,*next;
}DNode,*DLinkList;

//初始化双链表
bool InitDLinkList(DLinkList &L){
	L = (DNode *)malloc(sizeof(DNode));//分配一个头结点
	if(L==NULL){
		return false;
	} 
	L->prior = NULL;//头节点的prior永远指向NULL 
	L->next = NULL;//头节点之后暂时还没有节点 
	return true;
} 

//判断双链表是否为空(头节点)
bool Empty(DLinkList L){
	if(L->next==NULL){
		return true;
	}
	else{
		return false;
	}
} 

//双链表的插入 
bool InserNextDNode(DNode *p,DNode *s){
	if(p==NULL || s==NULL){
		return false;
	}
	s->next = p->next;
	if(p->next!=NULL){//如果p结点有后继节点 
		p->next->prior = s;
	}
	s->prior = p;
	p->next = s;
	return true;
}

//双链表的删除
bool DeleteNextDNode(DNode *p){
	if(p==NULL) return false;
	DNode *q = p->next; //找到p的后继节点
	if(q==NULL) return false;//p没有后继节点
	p->next = q->next;
	if(q->next!=NULL){
		q->next->prior = p;
	} 
	free(q);
	return true;
	 
} 
 
//销毁双链表
void DestoryList(DLinkList &L){
	//循环释放各个数据结点
	while(L->next!=NULL){
		DeleteNextDNode(L);
	} 
	free(L);
	L=NULL;
} 
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

循环单链表

#include 
#include 
#include 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

//初始化一个循环单链表
bool InitList(LinkList &L){
	L = (LNode *)malloc(sizeof(LNode));
	if(L==NULL) return false;
	L->next = L //头节点next指向头节点
	return true; 
} 

//判断循环单链表是否为空
bool Empty(LinkList L){
	if(L->next==L) return true;
	else return false;
} 

//判断节点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){
	if(p->next == L) return true;
	else return false;
} 

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

循环双链表

#include 
#include 
#include 
typedef struct DNode{
	int data;
	struct DNode *prior,*next;
}DNode,*DLinkList;

//初始化空的循环双链表
bool InitDLinkList(DLinkList &L){
	L = (DNode *)malloc(sizeof(DNode));
	if(L==NULL) return false;
	L->prior = L;
	L->next = L;
	return true;
}

//判断循环双链表是否为空
bool Empty(DLinkList L){
	if(L->next==L) return true;
	else return false;
} 

//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinkList &L,DNode *p){
	if(p->next==L) return true;
	else return false;
} 
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