技术

数据结构之链表-队列-串

其实在编程中，简单的链表、队列等都构成所有复杂算法、复杂数据结构的基础。因此我们了解了这些数据结构基础，对于那些复合而成的数据结构也就自然明白。

1、链表

顺序表是一种按照某种规则排列在一起的表，它有两种存储方式：一是表元素全部依次相邻存储（顺序存储结构）这里就不详细介绍顺序存储结构了；一是表元素可以放在任意位置，由相应指针指明其相邻元素位置（链式存储），所以也叫链表。
链表也分单链表、双链表、循环链表。

1.1、单向链表

顾名思义，就是链表的指向只有一个，要么从头到尾，要么从尾到头。具体实现

1
2
3
4
struct Node{
	ElementType element;   //结点元素
	Position next;         //指向下一个结点的指针
};

上面就是链表中一个结点的结构，单链表就是由n个这样的结点组成的。
下面需要做的就是编写相关的函数，例如元素插入、删除、显示等。

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
//表头元素存储链表长度
List CreatList()
{
	List L;
	L = malloc(sizeof(struct Node));
	L->element = 0;
	L->next = NULL;
	return L;
}
Status InsertElement(List L,int pos, ElementType element)
{
	Position temp,TmpCell;
	int i;
	temp = L;                                      //位置临时变量
	if( pos > L->element)   //如果插入的位置大于链表长度，则返回
	{
		printf("Please choose right position.\n");
		return 0;
	}
	for( i = 0; i < pos; i++ )    //找到要插入位置前一个元素
	{
		temp = temp->next;
	}
	TmpCell = malloc(sizeof(struct Node));  //创建一个链表节点
	TmpCell->next = temp->next;    //把欲插入位置前元素的后继赋值给插入节点；
	temp->next = TmpCell;  //将插入节点赋值给前元素的后继
	TmpCell->element = element;
	L->element += 1;
	return 1;
}

Status DeleteElement(List L, ElementType element)
{
	Position TmpCell;
	Position P;
	TmpCell = L;
	while( TmpCell->next != NULL && TmpCell->next->element != element)
	{
		TmpCell = TmpCell->next;
	}
	if(TmpCell->next == NULL)
	{
		printf("Do not find the element # %d ",element);
		return 0;
	}		
	else
	{
		P = TmpCell->next;
		TmpCell->next = P->next;
		free(P);
		L->element -=1;
	}
	return 1;
}
Position FindElement(List L, ElementType element)
{
	Position TmpCell;
	TmpCell = L->next;
	while( TmpCell != NULL && TmpCell->element != element)
	{
		TmpCell = TmpCell->next;
	}
	return TmpCell;
}
void DeleteList(List L)
{
	Position P,TmpCell;
	P = L->next;
	while( P != NULL )
	{
		TmpCell = P->next;
		free(P);
		P = TmpCell;
	}
	L->element = 0;
	L->next = NULL;
}
void ShowList(const List L)
{
	Position TmpCell;
	TmpCell = L->next;
	if(!TmpCell)
	{
		printf("Empty List.\n");
	}
	while( TmpCell != NULL)
	{
		printf( "%d ", TmpCell->element);
		TmpCell = TmpCell->next; 
	}	
}

这样单链表的基本功能都有了，复杂的一些查找、删除功能完成可以在这些基本功能上修改得到。

1.2、双向链表

顾名思义，就是链表即可从头到尾，也可从尾到头，双向的。其实很简单，就是在单向链表的基本结构上再加一个指针指向前一个结点，这样就完成双向链表。具体实现：

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
struct Node
{
	ElementType Element;
	Position Next;
	Position Front;
};



List MakeEmpty(List L)
{
	if( L!= NULL)
		DeleteList(L);
	L = malloc(sizeof(struct Node));
	if( L == NULL)
		printf("Out of Memory!\n");
	L->Next = NULL;
	L->Element = 0;
	L->Front = NULL;
	return L;
}

int IsEmpty( List L)
{
	return L->Next == NULL;
}

int IsLast( Position P, List L)
{
	return P->Next == NULL;
}

int IsHead( Position P, List L)
{
	return P->Front == NULL;
}
Position Find( ElementType X, List L)
{
	Position P;
	if( L->Next == NULL )
		printf("Empty List.\n");
	P = L->Next;
	while( P == NULL && P->Element != X )
	{
		P = P->Next;
	}
	return P;
}

Position Get_Last( List L)
{
	Position P;
	P = L->Next;
	while( P->Next != NULL)
		P = P->Next;
	return P;
}

//双链表需要加一个从后面搜索的函数
Position Find_From_Back( ElementType X, List L)
{
	Position Last;
	if( L->Next == NULL )
	{
		printf("Empty List.\n");
		return 0;
	}		
	Last = Get_Last(L);  //自己写的时候，有可能是NULL
	while( Last != NULL && Last->Element != X )
		Last = Last->Front;
	return Last;
}

Position FindPrevious( ElementType X, List L)
{
	//return Find(X,L)->Front;  //这将导致产生NULL的情况
	Position P;
	P = L;
	while( P->Next != NULL && P->Next->Element != X)
		P = P->Next;
	return P;
	//这个函数现在有一个BUG， 就是漏掉第一个元素就是X的情况:原因是我应该把P=L，NOT，L->Next
}

//双链表新增搜索元素前一个位置
Position FindPrevious_Back( ElementType X, List L)
{
	Position Last;
	if( L->Next == NULL )
	{
		printf("Empty List.\n");
		return 0;
	}		
	Last = Get_Last(L);  //自己写的时候，有可能是NULL
	while( Last != NULL && Last->Element != X )
		Last = Last->Front;
	return Last;
}

void Delete( ElementType X, List L)
{
	Position P,TmpCell;
	P = FindPrevious(X,L);   //这里有一个问题，列表为 0012345678  ，找到的P为NULL ，原因是使用了Front
	if(!IsLast( P,L ))
	{
		TmpCell = P->Next;
		TmpCell->Next->Front = TmpCell->Front;
		P->Next = TmpCell->Next;
		free( TmpCell);
	}
}
void Insert( ElementType X, List L, Position P)
{
	Position TmpCell;
	TmpCell = malloc(sizeof(struct Node));
	if(TmpCell == NULL)
		printf("Out of Memory!\n");
	if( P == L)
	{
		TmpCell->Element = X;
		TmpCell->Front = NULL;
		TmpCell->Next = P->Next;
		P->Next = TmpCell;
	}
	else
	{
		TmpCell->Element = X;
		TmpCell->Front = P;
		TmpCell->Next = P->Next;
		P->Next = TmpCell;
	}	
}
void DeleteList( List L)
{
	Position P,TmpCell;
	P = L->Next;
	L->Next = NULL;
	while( P != NULL)
	{
		TmpCell = P->Next;
		//TmpCell->Front = NULL;  //这个是多余的，无谓的引入了一个BUG，就是如果TmpCell是NULL了，这就很危险
		free(P);
		P = TmpCell;
	}
}

void PrintList( const List L)
{
	Position P = Header(L);
	if( IsEmpty(L))
		printf("Empty List.\n");
	else
	{
		do{
			P = Advance(P);
			printf("%d,", Retrieve(P));
		} while( !IsLast(P, L));
		printf("\n");
	}
}

Position Header( List L)
{
	return L;
}

Position Advance( Position P)
{
	return P->Next;
}
ElementType Retrieve( Position P)
{
	return P->Element;
}

1.3、循环链表

顾名思义，就是首尾相连的链表啦，当然可以使单向也可是双向，这里我就以单向介绍
实现循环链表其实很简单，就是把尾结点指向头节点就OK了嘛，连基本结构够不用改。具体实现

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
struct Node
{
	ElementType element;
	Position next;
};

List CreateList()
{
	List L;
	L = malloc(sizeof(struct Node));
	if(!L)
		printf("memory is out");
	L->next = NULL;
	L->element = 0;
	return L;
}
void DeleteList(List L)
{
	Position P,tmpCell;
	Position temp;
	P = L->next;
	if(!P)
	{
		printf("It is an empty list.\n");
		return ;
	}
	temp = P;
	P = P->next;
	while(temp != P)
	{
		tmpCell = P;
		P = P->next;
		free(tmpCell);
		/*
		if(P == P->next)
		{
			free(P);
			P = NULL;
		}
		else
		{
			tmpCell = P; 
			P = P->next;   //这个bug就是p指向自己，然后把自己删除了，野指针了。  free掉指针后，指针默认不为NULL
			free(tmpCell);
			tmpCell = NULL;
		}*/  //这里由于没有哨兵，很容易出现野指针，搞得很是麻烦		
	}
	free(temp);
	L->next = NULL;
}
Position FindElement(List L, ElementType element)
{
	Position P;
	int flag = 0;
	P = L->next;
	if(!P)
	{
		printf("It is an empty lis.\n");
		return NULL;
	}
	while(P->element != element && flag <= 1)
	{
		P = P->next;
		if(P == L->next)
			flag++;
	}
	return P;
}
void PrintList(List L)
{
	Position P, tmpCell;
	P = L->next;
	if(!P)
	{
		printf("It is an empty list . \n");
		return ;
	}
	printf("%d ",P->element);
	if (P == P->next)
	{
		return ;
	}
	P = P->next;  //到头
	while(P != L->next)
	{
		printf("%d ", P->element);
		P = P->next;
	}
}
void InsertElement(ElementType element, int p, List L)
{
	Position tmpCell,P;
	int i=0;
	P = L->next;	
	tmpCell = malloc(sizeof(struct Node));
	tmpCell->element = element;
	if(!P)
	{
		tmpCell->next=tmpCell;
		L->next = tmpCell;
		return;
	}
	for(i=1; i < p; i++)
	{
		P = P->next;
	}	
	tmpCell->next = P->next;
	P->next = tmpCell;
}
void DeleteElement(ElementType element, List L)
{
	Position P,tmpCell;
	P = L->next;
	if(!P)
	{
		printf("It is an empty list.\n");
		return;
	}
	P = FindElement( L, element);
	tmpCell = P;
	P = P->next;
	free(tmpCell);
}

2、队列与栈

队列就是一个先进先出的基本数据结构，栈就是一个先进后出的数据结构；两者都有很多的应用

2.1、栈的实现

栈和队列不同的地方就是只能队尾操作，先进后出。这里也只介绍链式存储的实现

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
typedef struct{
	ElementType data;
	struct StackNode * next;
}StackNode , *LinkStackPtr;

typedef struct{
	LinkStackPtr top;
	int cout;
}LinkStack;

Status visit(ElementType c)
{
	printf("%d ", c);
	return OK;
}

Status InitStack(LinkStack * S)
{
	S->top = (LinkStackPtr)malloc(sizeof(StackNode));
	if(!S->top)
	{
		printf("Sorry Sir, No memory.\n");
		return ERROR;
	}
	S->top = NULL;
	S->cout = 0;
	return OK;
}

Status ClearStack(LinkStack * S)
{
	LinkStackPtr tmpCell;
	while(S->top)
	{
		tmpCell = S->top;
		S->top = S->top->next;		
		free(tmpCell);
	}
	S->cout = 0;
	return OK;
}	

Status StackEmpty(LinkStack S)
{
	//return S.count == 0 ? TRUE : FALSE;
	return S.top == NULL ? TRUE : FALSE;
}

Status GetTop(LinkStack S, ElementType * e)
{
	if(S.top == NULL)
	{
		printf("Sorry Sir, No Element. \n");
		return ERROR;
	}
	*e = S.top->data;
	return OK;
}

int StackLength(LinkStack S)
{
	return S.cout;
}

Status Push(LinkStack * S, ElementType e)
{
	LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
	p->data = e;
	p->next = S->top;
	S->top = p;
	S->cout++;
	return OK;
}

Status Pop(LinkStack * S, ElementType *e)
{
	LinkStackPtr tmpCell;
	if(S->top == NULL)
	{
		printf("Sorry Sir, No Element.\n");
		return ERROR;
	}
	*e = S->top->data;
	tmpCell = S->top;
	S->top = S->top->next;
	S->cout--;
	free(tmpCell);
	return OK;
}

Status StackTraverse(LinkStack S)
{
	LinkStackPtr p;
	p = S.top;
	while(p)
	{
		visit(p->data);
		p = p->next;
	}
	printf("\n");
	return OK;
}

其实实现很简单，也是之前用的链式结构，只是在使用这些数据的方式上发生了一些变化。其基本结构就是栈元素结点（结点元素、下一栈结点指针），栈顶结点（包含栈顶指针、和栈大小），然后就是一些基本的pop\push之类的操作了。

2.2、队列的实现

和之前的线性表一样，有两种存储结构，一种是顺序存储一种是链式存储。这里只介绍链式存储。

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
typedef struct{
	ElementType data;
	struct QueueNode *next;
}QueueNode, *QueuePtr;

typedef struct{
	QueuePtr front;
	QueuePtr rear;
	int count;
}LinkQueue;

Status visit(ElementType C)
{
	printf("%d ", C);
	return OK;
}

Status InitQueue(LinkQueue * Q)
{
	Q->front = malloc(sizeof(QueueNode));
	Q->rear = malloc(sizeof(QueueNode));
	Q->front = NULL;
	Q->rear = NULL;
	Q->count = 0;
	return OK;
}

Status ClearQueue(LinkQueue * Q)
{
	QueuePtr tmpCell,p;
	if(Q->count == 0)
	{
		printf("Sorry Sir, No Element.\n");
		return ERROR;
	}
	while(Q->front)
	{
		tmpCell = Q->front;
		Q->front = Q->front->next;
		free(tmpCell);
	}
	Q->front = NULL;
	Q->rear = NULL;
	Q->count = 0;
	return OK;
}

Status QueueEmpty(LinkQueue  Q)
{
	return (Q.count == 0 ? TRUE : FALSE);
}

int QueueLength(LinkQueue Q)
{
	return Q.count;
}

Status GetHead(LinkQueue Q, ElementType * e)
{
	if(Q.front == NULL)
	{
		printf("Sorry Sir, No Element\n");
		return ERROR;
	}
	*e = Q.front->data;
	return OK;
}

Status EnQueue(LinkQueue * Q, ElementType e)
{
	QueuePtr tmpCell;
	tmpCell = malloc(sizeof(QueueNode));
	tmpCell->data = e;
	tmpCell->next = NULL;
	if(!Q->count)
	{
		Q->rear = tmpCell;
		Q->front = tmpCell;
	}		
	else
		Q->rear->next = tmpCell;
	Q->count++;
	return OK;
}

Status DeQueue(LinkQueue * Q, ElementType * e)
{
	QueueNode * tmpCell;
	if(Q->count == 0)
	{
		printf("Sorry Sir, No Element. \n");
		return ERROR;
	}
	*e = Q->front->data; 
	tmpCell = Q->front;
	Q->front = tmpCell->next;
	free(tmpCell);
	Q->count--;
	return OK;
}

Status QueueTraverse(LinkQueue Q)
{
	QueueNode * tmpCell;
	int k = Q.count;
	if(Q.count == 0)
	{
		printf("Sorry Sir, No Element. \n");
		return ERROR;
	}
	tmpCell = Q.front;
	while(--k)
	{
		visit(tmpCell->data);
		tmpCell = tmpCell->next;
	}
	return OK;
}

如果和栈的实现对比会发现大抵都相同，基本也够也是基本的元素结点、起始结点（包含头、尾、队列大小）。它就是比栈多一个头尾的概念，因为队列的特点就是先进先出。push从队尾进，pop从队首出。

3、串

3.1、串的实现

3.2、朴素的模式匹配算法

3.3、KMP模式匹配算法

这个部分我只是粗略的看了一下，只知道相关的概念也就只把该结构涉及的东西列出，没有亲手实现。