数据结构-双向链表（C语言）_c语言双向链表的代码

一、基本操作

1、定义节点

双向链表是链表的一种，与单链表不同的shi，它的每个数据结点中都有两个指针，分别指向直接前驱和直接后继。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。下图为双向链表的结构图。

typedef struct DoubleLinkNode
{
	char data;
	struct DoubleLinkNode *previous;
	struct DoubleLinkNode *next;
}DLNode,*DLNodeptr;
1
2
3
4
5
6

2、双向链表的初始化

DLNodeptr initLinkList()
{
	DLNodeptr tempHeader=(DLNodeptr)malloc(sizeof(DLNode));
	tempHeader->data='\0';
	tempHeader->previous=NULL;
	tempHeader->next=NULL;
	return tempHeader; 
}
1
2
3
4
5
6
7
8

3、双向链表的打印

与单链表基本一致

void printList(DLNodeptr pHeader)
{
	DLNodeptr p=pHeader->next;
	while(p)
	{
		printf("%c",p->data);
		p=p->next;
	}
	printf("\r\n");
}
1
2
3
4
5
6
7
8
9
10

4、双向链表的插入

同单链表类似
如图所示

void insertElement(DLNodeptr pHeader,char pchar,int pos)
{
	DLNodeptr p,q,r;
	
	p=pHeader;
	int i;
	for(i=0;i<pos;i++)
	{
		p=p->next;
		if(p==NULL)
		{
			printf("该位置不在链表范围内！");
			return; 
		}
	}
	q=(DLNodeptr)malloc(sizeof(DLNode));
	q->data=pchar;
		
	r=p->next;
	q->next=p->next;
	q->previous=p;
	p->next=q;
	if(r!=NULL)
	{
		r->previous=q;
	} 
}
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

5、双向链表的删除

void deleteElement(DLNodeptr pHeader,char Achar)
{
	DLNodeptr p,q,r;
	p=pHeader;
	
	while((p->next) && (p->next->data!=Achar))
	{
		p=p->next;
	}
	
	if(p->next==NULL)
	{
		printf("该数据不存在于链表中！\n"); 
		return;
	}
	q=p->next;
	r=q->next;
	p->next=r;
	if(r)
	{
		r->previous=p;
	}
	free(q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

6、双向链表的元素定位

void locateElement(DLNodeptr pHeader,char Achar)
{
	DLNodeptr p,q;
	p=pHeader;
	
	int i=0;
	while((p->next) && (p->next->data!=Achar))
	{
		p=p->next;
		i++;
	}
	if(p->next ==NULL)
	{
		printf("该元素(%c)不存在于链表中！\n",Achar); 
		return;
	}
	printf("The element(%c)’s location is %d.\n",Achar,i);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

7、链表清空

void destroy_list(DLNodeptr tempList)
{
	DLNodeptr p,q;
	p=tempList;
	if(p)
	{
		q=p;
		p=p->next;
		free(q);
	}
	printf("清空成功!\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

8、测试

 void insert_delete_locate_destroy_list_Text()
{
	DLNodeptr tempList=initLinkList();
	printList(tempList);
	
	insertElement(tempList, 'H', 0);
	insertElement(tempList, 'e', 1);
	insertElement(tempList, 'l', 2);
	insertElement(tempList, 'l', 3);
	insertElement(tempList, 'o', 4);
	insertElement(tempList, '!', 5);
	printList(tempList);

	deleteElement(tempList, 'H');
	deleteElement(tempList, 'a');
	deleteElement(tempList, '!');
	printList(tempList);
	
	insertElement(tempList, 'o', 1);
	printList(tempList);
	
	locateElement(tempList,'p');
	locateElement(tempList,'o');
	
	destroy_list(tempList);
	
}
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

二、完整代码

#include<stdio.h>
#include<malloc.h>

typedef struct DoubleLinkNode
{
	char data;
	struct DoubleLinkNode *previous;
	struct DoubleLinkNode *next;
}DLNode,*DLNodeptr;

DLNodeptr initLinkList()
{
	DLNodeptr tempHeader=(DLNodeptr)malloc(sizeof(DLNode));
	tempHeader->data='\0';
	tempHeader->previous=NULL;
	tempHeader->next=NULL;
	return tempHeader; 
}

void printList(DLNodeptr pHeader)
{
	DLNodeptr p=pHeader->next;
	while(p)
	{
		printf("%c",p->data);
		p=p->next;
	}
	printf("\r\n");
}

void insertElement(DLNodeptr pHeader,char pchar,int pos)
{
	DLNodeptr p,q,r;
	
	p=pHeader;
	int i;
	for(i=0;i<pos;i++)
	{
		p=p->next;
		if(p==NULL)
		{
			printf("该位置不在链表范围内！");
			return; 
		}
	}
	q=(DLNodeptr)malloc(sizeof(DLNode));
	q->data=pchar;
		
	r=p->next;
	q->next=p->next;
	q->previous=p;
	p->next=q;
	if(r!=NULL)
	{
		r->previous=q;
	} 
}

void deleteElement(DLNodeptr pHeader,char Achar)
{
	DLNodeptr p,q,r;
	p=pHeader;
	
	while((p->next) && (p->next->data!=Achar))
	{
		p=p->next;
	}
	
	if(p->next==NULL)
	{
		printf("该数据不存在于链表中！\n"); 
		return;
	}
	q=p->next;
	r=q->next;
	p->next=r;
	if(r)
	{
		r->previous=p;
	}
	free(q);
} 

void locateElement(DLNodeptr pHeader,char Achar)
{
	DLNodeptr p,q;
	p=pHeader;
	
	int i=0;
	while((p->next) && (p->next->data!=Achar))
	{
		p=p->next;
		i++;
	}
	if(p->next ==NULL)
	{
		printf("该元素(%c)不存在于链表中！\n",Achar); 
		return;
	}
	printf("The element(%c)’s location is %d.\n",Achar,i);
}

void insert_delete_locate_destroy_list_Text()
{
	DLNodeptr tempList=initLinkList();
	printList(tempList);
	
	insertElement(tempList, 'H', 0);
	insertElement(tempList, 'e', 1);
	insertElement(tempList, 'l', 2);
	insertElement(tempList, 'l', 3);
	insertElement(tempList, 'o', 4);
	insertElement(tempList, '!', 5);
	printList(tempList);

	deleteElement(tempList, 'H');
	deleteElement(tempList, 'a');
	deleteElement(tempList, '!');
	printList(tempList);
	
	insertElement(tempList, 'o', 1);
	printList(tempList);
	
	locateElement(tempList,'p');
	locateElement(tempList,'o');
	
	destroy_list(tempList);
	
}

void destroy_list(DLNodeptr tempList)
{
	DLNodeptr p,q;
	p=tempList;
	if(p)
	{
		q=p;
		p=p->next;
		free(q);
	}
	printf("清空成功!\n");
}

void main()
{
	insert_delete_locate_destroy_list_Text();
}
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

运行结果：

Hello!
该数据不存在于链表中！
ello
eollo
该元素(p)不存在于链表中！
The element(o)’s location is 1.
清空成功!
1
2
3
4
5
6
7