数据结构与算法

数据结构与算法(四)-队列单链表实现[转]

大话数据结构笔记， 队列单链表的实现

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
#include <stdio.h>
#include <malloc.h>

//单链表表示队列, 只能存放int型的数据

//单链表节点
struct node{
	int val;           //存储的值
	struct node *next; //指向下一个节点的指针
};

//表头
static struct node *pHead;

//val-传进去的值
static struct node *createNode(int val)
{
	struct node *pnode = NULL;
	pnode = (struct node *)malloc(sizeof(struct node)); //初始化节点
	if(!pnode)
	{
		return NULL;
	}

	pnode->val = val;
	pnode->next = NULL;
}

//销毁单向链表
static int destroySingleLink()
{
	struct node *pnode = NULL;
	while(pHead != NULL)
	{
		pnode = pHead;
		pHead = pHead->next;
		free(pnode);
	}
	return 0;
}

//将val值添加到队列末尾
static void add(int val)
{
	if(!pHead)
	{
		pHead = createNode(val);
		return ;
	}

	struct node *pnode = createNode(val);
	struct node *pend = pHead;
	while(pend->next)
	{
		pend = pend->next;
	}
	pend->next = pnode;
}

//删除并返回队列开头元素
static int pop()
{
	int val = pHead->val;

	struct node *pnode = pHead; //这个地方千万不能判断pHead是否为 NULL, 否则会进入很多次无谓循环了	
	pHead = pHead->next;
		
	free(pnode);		
	
	return val;
}

//返回队列开头元素
int front()
{
	return pHead->val;
}

//返回链表中节点个数
static int size()
{
	int count = 0;
	struct node *pend = pHead;

	while(pend)
	{
		pend = pend->next;
		count++;
	}
	return count;
}

//链表是否为空
static int isEmpty()
{
	return size() == 0;
}

void main()
{
	int tmp = 0;

	//将10， 20， 30一次加入单链表
	add(10);
	add(20);
	add(30);

	tmp = pop();
	printf("tmp=%d\n", tmp);

	tmp = front();
	printf("front=%d\n", tmp);

	add(40);

	printf("isEmpty()=%d\n", isEmpty());
	printf("size()=%d\n", size());

	while(!isEmpty())
	{
		printf("%d\n", pop());
	}

	destroySingleLink();
}

转自

http://www.cnblogs.com/skywang12345/p/3562279.html