回顾数据结构的基础知识

发表于 | 更新于 | 分类于 | 阅读次数 次
字数统计 4,392 字

之前在写Java中的容器时，有写到一些关于数据结构的部分，可以参考《Java的List、Set、Map容器》一文。这里再详细回顾一下对数据结构的学习。

C语言及指针回顾

字节：存储数据的单元，是硬件所能访问的最小单位。
1字节=8位，1k=1024字节，1M=1024k，1G=1024M。对于4G内存的电脑来说，所能存放数据最多是（4*1024*1024*1024*8）位的二进制数据。
物理内存地址：内存单元的编号，从零开始的非负整数
指针：指针就是地址，地址就是指针。
指针变量：存放内存单元编号的变量，就是存放地址的变量。
结构体：把一些基本类型数据组合在一起，形成一个新的复合数据类型。
一个指针变量，无论它指向的变量占几个字节，该指针变量本身只占4个字节。用第一个字节的地址表示整个变量的地址。一个变量的地址是用该变量首字节的地址来表示。CPU通过地址总线、控制总线、数据总线，俗称三根总线，来操作物理内存。

看懂一个程序的三个步骤

  1. 程序的流程
  2. 每个语句的功能
  3. 试数

问题规模的增加，算法对运算处理的性能消耗

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
package datastructure.part.one;
import java.util.Arrays;
/**
 * @description
 * @author Denghs
 * @version 1.0,2017年11月23日 下午2:43:18
 * @remark
 */
public class TestOn {
	public static void main(String[] args) {
		long n = 10000;
		
		method1(n);
		
		method2(n);
		
		long start = System.currentTimeMillis();
		long sum = method3(n);
		System.out.println("method3：" + (System.currentTimeMillis() - start) + "毫秒，sum=" + sum);
	}
	/**
	 * 用for循环进行1+2+3+...+100的计算。 该方法的时间复杂度是O（n）
	 * @param n
	 */
	public static void method1(long n) {
		long start = System.currentTimeMillis();
		long sum = 0;
		for (long i = 1; i <= n; i++) {
			sum += i;
		}
		System.out.println("method1： " + (System.currentTimeMillis() - start) + "毫秒，sum=" + sum);
	}
	/**
	 * 用高斯公式进行1+2+3+...+100的计算。 该方法的时间复杂度是O（1）
	 * @param n
	 */
	public static void method2(long n) {
		long start = System.currentTimeMillis();
		long sum = (n + 1) * n / 2;
		System.out.println("method2： " + (System.currentTimeMillis() - start) + "毫秒，sum=" + sum);
	}
	
	/**
	 * 用递归的方式计算1+2+3+...+100的和。数值过大，会导致内存溢出，递归本质是函数的不停的压栈、出栈的操作
	 * @param n
	 */
	public static long method3(long n) {
		if(n == 1){
			return 1;
		}else{
			return n + method3(n-1);
		}
	}
}


从上图的运行结果可以明显的看到，当问题计算的规模n=10000时，好像method1、method2、method3彼此的计算耗时都是0毫秒。但是当n再扩大10倍时，method1花了2毫秒，method3直接抛异常了，而method2而然是0毫秒。
method1是用for循环的方式，method2则是高斯公式，method3是用递归的方式。
在数据结构领域，关于算法的时间复杂度，有一个计算公式，大O表示法。这里不做过多说明，教科书上有该公式的计算方法跟定论。

线性结构

数据结构中关于数据的逻辑结构，只分为线性结构、非线程结构。所谓的线性结构，我们可以用一个生活化的场景来理解它，用穿好线的针能够一次把元素都串起来。线性结构是指元素只能有一个顶点、一个端点，中间的元素只有一个前驱跟一个后继。

顺序表

可以把串在一起的元素，紧紧的挤压在一个方向。让元素紧挨着元素。这就可以理解成是一个顺序表。顺序表其实就是数组，一次给一片连续的空间，然后把空间按一个一个的小格子划分好。其特点是：当CPU在内存中找不到连续一片的符合要求的空间，会导致分配失败。可以通过存放元素格子的宽度，也就是偏移量乘以第几个元素，获取指定地址空间上的元素。

代码示例

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
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
//连续存储数组的算法
struct Arr
{	
	int * pBase;	//存储容器中第一个元素的地址
	int capacity;	//所能容纳元素的最大容量
	int length;		//当前有效元素的个数
};
void init_arr(struct Arr *, int capacity);//初始化容器
bool append_arr(struct Arr *, int value);//追加元素
bool insert_arr(struct Arr *, int index, int value);//在指定的角标处插入元素
bool delete_arr(struct Arr *, int index, int * delete_value);//删除指定角标处的元素，并返回被删除的元素的值
int get(struct Arr *, int index);//获取指定角标的元素
bool is_empty(struct Arr *);//容器是否空
bool is_full(struct Arr *);//容器是否已满
void sort_arr(struct Arr *);//按元素的值自然排序
void print_arr(struct Arr *);//输出元素的值
void invert_arr(struct Arr *);//元素值前后倒置
void main()
{	
	int delete_value;
	int get_value;
	struct Arr array;
	init_arr(&array, 10);
	print_arr(&array);
	printf("\n-------分隔符-追加-----\n");
	append_arr(&array, 10);
	append_arr(&array, 6);
	append_arr(&array, 2);
	append_arr(&array, -1);
	append_arr(&array, 9);
	print_arr(&array);
	printf("\n-------分隔符-插入-----\n");
	insert_arr(&array, 0, 7);
	//insert_arr(&array, 6, -18);
	//insert_arr(&array, 1, 72);
	print_arr(&array);
	/**printf("\n-------分隔符-删除-----\n");
	bool flag = delete_arr(&array, 5, &delete_value);
	print_arr(&array);
	if(flag){
		printf("被删除的元素的值：%d\n", delete_value);
	}
	printf("\n-------分隔符-获取-----\n");
	get_value = get(&array, 5);
	printf("角标 %d 的元素值：%d\n", 5 ,get_value);
	get_value = get(&array, 0);
	printf("角标 %d 的元素值：%d\n", 0 ,get_value);
	printf("\n-------分隔符-倒置-----\n");
	invert_arr(&array);
	print_arr(&array);
	
	printf("\n-------分隔符-排序-----\n");
	sort_arr(&array);
	print_arr(&array);*/
	
}
//初始化容器
void init_arr(struct Arr * pArr, int capacity)
{	
	pArr->pBase = (int *)malloc(sizeof(int) * capacity);//动态分配内存
	if(NULL == pArr->pBase){
		printf("动态分配内存失败！\n");
		exit(-1);//程序退出。跟Java中的System.exit(-1);一样
	}
	pArr->capacity = capacity;
	pArr->length = 0;//未存储元素，有效元素为0个
}
//输出元素的值
void print_arr(struct Arr * pArr){
	printf("容器大小为：%d，有效元素个数为：%d\n", pArr->capacity, pArr->length);
	if(is_empty(pArr)){
		printf("空容器！\n");
	}else{
		for(int i=0; i<pArr->length; i++){
			printf("%d ", pArr->pBase[i]);
		}
		printf("\n");
	}
}
//容器是否空
bool is_empty(struct Arr * pArr){
	//有效元素的个数为0
	return pArr->length == 0 ? true:false;
}
//容器是否已满
bool is_full(struct Arr * pArr){
	//有效元素的个数=容器的长度
	return pArr->length == pArr->capacity ? true:false;
}
//追加
bool append_arr(struct Arr * pArr, int value){
	//如果容器满了
	if(is_full(pArr)){
		return false;
	}
	//在当前容器的最后一个位置处追加元素
	pArr->pBase[pArr->length] = value;
	pArr->length++;
	return true;
}
//在指定的角标处插入元素
bool insert_arr(struct Arr * pArr, int index, int value){
	int i = 0;
	//如果容器满了
	if(is_full(pArr)){
		printf("容器已满！\n");
		return false;
	}
	//index的值不能是负数，不是超过容器存储的有效元素个数
	//index=有效元素个数时，表示在最后一个元素处追加一个元素值
	if(index < 0 || index > pArr->length){
		return false;
	}
	//先移位，把指定角标位及该角标之后存放的元素，往后挪一个位子存放
	for(i = pArr->length - 1; i >= index; i--){
		pArr->pBase[i+1] = pArr->pBase[i];
	}
	//把值存入指定角标处
	pArr->pBase[index] = value;
	pArr->length++;
	return true;
}
//删除指定角标处的元素，并返回被删除的元素的值
bool delete_arr(struct Arr * pArr, int index, int * delete_value)
{	
	int i;
	//如果容器满了
	if(is_empty(pArr)){
		printf("容器已空！\n");
		return false;
	}
	//index的值不能是负数，不是超过容器存储的有效元素个数
	if(index < 0 || index > pArr->length-1){
		return false;
	}
	//把要删除的指定角标处的值取出来
	*delete_value = pArr->pBase[index];
	//需要移位，要删除的指定角标之后的值需要往前移动一位
	for(i = index + 1; i < pArr->length; i++){
		pArr->pBase[i-1] = pArr->pBase[i];
	}
	pArr->length--;
	return true;
}
//获取指定角标位置的元素值
int get(struct Arr * pArr, int index){
	//index的值不能是负数，不是超过容器存储的有效元素个数
	if(index < 0 || index > pArr->length-1){
		//应该是Java中的数组角标越界异常，不能确定此处返回的值是否是一个有效的值
		return -1;
	}
	return pArr->pBase[index];
}
//元素值前后倒置
void invert_arr(struct Arr * pArr){
	int start = 0;
	int end = pArr->length-1;
	int temp;
	while(start < end){
		temp = pArr->pBase[start];
		pArr->pBase[start] = pArr->pBase[end];
		pArr->pBase[end] = temp;
		start++;
		end--;
	}
}
//按元素的值自然排序
void sort_arr(struct Arr * pArr){
	int i, j, temp;
	for(i = 0; i<pArr->length; i++){
		for(j=i+1; j<pArr->length; j++){
			if(pArr->pBase[i] > pArr->pBase[j]){
				temp = pArr->pBase[j];
				pArr->pBase[j] = pArr->pBase[i];
				pArr->pBase[i] = temp;
			}
		}
	}
}

链式结构

可以把串在一起的元素，中间的线还流出一点点来。只要顺着线能找到元素。这就可以理解成是一个链式结构。每一个数据元素的地址可以是分散开来的，动态分配，彼此通过指针相连。每个结点只有一个后续结点，首结点没有前驱，尾结点没有后续。链式结构，也就是俗称的链表。对于链表的操作，额外增加一个头结点，以方便对整个链表的操作。头结点跟头指针是两个不同的概念。头结点的数据域部分是空的。

单链表

在单链表的结构中，数据元素要有两部分，一部分存放数据元素的数据部分，一部分存放下一个数据元素的地址。

代码示例

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
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct Node{
	int data;//数据域
	struct Node * pNext;//指针域
}NODE, *PNODE;
//创建链表
PNODE creat_list();
//输出链表
void print_list(PNODE);
//是否为空链表
bool is_empty(PNODE);
//获取链表的长度
int get_len(PNODE);
//对链表进行排序：按自然顺序
void sort_list(PNODE);
//插入结点
bool insert_node(PNODE,int,int);
//删除结点
bool delete_node(PNODE,int,int*);
void main(){
	int len;
	int deleteVal;
	PNODE pHead = NULL;
	pHead = creat_list();
	//输出值
	print_list(pHead);
	if(is_empty(pHead)){
		printf("空链表\n");
	}else{
		printf("链表不为空\n");
	}
	//获取链表长度
	len = get_len(pHead);
	printf("链表的长度为：%d\n", len);
	//排序
	sort_list(pHead);
	print_list(pHead);
	
	//插入
	if(insert_node(pHead, 1, 33)){
		printf("插入成功！\n");
	}else{
		printf("插入失败！\n");
	}
	print_list(pHead);
	
	//删除
	if(delete_node(pHead, 0, &deleteVal)){
		printf("删除成功！\n");
	}else{
		printf("删除失败！\n");
	}
	print_list(pHead);
}
//创建链表
PNODE creat_list(){
	int len;
	int value;
	int i;
	//创建头结点
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if(NULL == pHead){
		//创建失败
		printf("分配内存失败，程序终止!\n");
		exit(-1);
	}	
	printf("请输出链表的结点个数：");
	scanf("%d", &len);
	PNODE pTail = pHead;
	pTail->pNext = NULL;
	//循环生成链表的每个节点
	for(i=0; i<len; i++){
		printf("请输出第%d个结点的值：", i+1);
		scanf("%d", &value);
			
		//创建一个新的结点
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		pNew->data = value;
		pTail->pNext = pNew;
		pNew->pNext = NULL;
		pTail = pNew;
	}
	return pHead;
}
//输出链表
void print_list(PNODE pHead){
	PNODE p = pHead->pNext;
	while(NULL != p){
		printf("%d ", p->data);
		p = p->pNext;
	}
	printf("\n");
}
//是否为空链表
bool is_empty(PNODE pHead){
	return NULL == pHead->pNext ? true:false;
}
//获取链表的长度
int get_len(PNODE pHead){
	int len = 0;
	PNODE p = pHead->pNext;
	while(NULL != p){
		p = p->pNext;
		len++;
	}
	return len;
}
//对链表进行排序：按自然顺序
void sort_list(PNODE pHead){
	int i, j, temp;
	//总长度
	int len = get_len(pHead);
	//一个当前节点，一个当前节点的下一个节点
	PNODE pNow, pNext;
	
	for(i=0, pNow=pHead->pNext;i<len-1;i++, pNow = pNow->pNext){
		for(j=i+1, pNext = pNow->pNext;j<len;j++, pNext = pNext->pNext){
			if(pNow->data > pNext->data){	//a[i] > a[j]
				temp =	pNow->data;			//temp = a[i]
				pNow->data = pNext->data;	//a[i] = a[j]
				pNext->data	= temp;	//a[j] = temp;
			}
		}
	}
	
}
//在指定位置插入结点，position从0开始
bool insert_node(PNODE pHead, int position, int value){
	//获取链表的总长度
	//int len = get_len(pHead);
	//判断position是否是一个有效数。长度是5，position为6，表示是在末尾处添加。index为7，超过有效值
	//if(position > len + 1){
		//return false;
	//}
	int len = 0;
	//直接定位到需要插入结点的前一结点
	PNODE p = pHead;
	while(NULL != p && len < position){
		p = p->pNext;
		len++;
	}
	//结点不存在
	if(len > position || NULL == p){
		return false;
	}
	//创建一个新结点
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if(NULL == pNew){
		printf("动态内存分配失败！程序退出\n");
		exit(-1);
	}
	pNew->data = value;
	pNew->pNext = p->pNext;
	p->pNext = pNew;
	return true;
}
//删除指定位置的结点，position从0开始
bool delete_node(PNODE pHead, int position ,int* deleteVal){
	int len = 0;
	//直接定位到需要插入结点的前一结点
	PNODE p = pHead;
	while(NULL != p->pNext && len < position){
		p = p->pNext;
		len++;
	}
	if(len > position || NULL == p->pNext){
		return false;
	}
	
	//要删除的结点
	PNODE q = p->pNext;
	*deleteVal = q->data;
	
	//把p的指针域指向要删除结点的下一个节点
	p->pNext = p->pNext->pNext;
	//释放删除结点的内存空间
	free(q);
	q = NULL;
	return true;
}

双链表

在双链表的结构中，数据元素要有三部分，一部分存放数据元素的数据部分，一部分存放下一个数据元素的地址，一部分存放上一个数据元素的地址。

线性结构的应用-队列、栈

队列

操作受限的线性表，也称先进先出表。队尾插入，队头取出元素。在非空队列中，队头指针始终指向队头元素，队尾指针始终指向队尾元素的下一个位置。

循环队列


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
#include <stdio.h>
#include <malloc.h>
//循环队列，先进先出
typedef struct Queue{
	int * pBase;//动态数组
	int front;//队列中有效元素的头元素
	int rear;//队列中有效元素的尾元素
}QUEUE;
//初始化循环队列
void init(QUEUE *);
//入队，在队列有效元素的尾部添加
bool add(QUEUE *, int);
//出队，从队头开始获取
bool get(QUEUE *, int *);
//是否已经满
bool isFull(QUEUE *);
//是否已经空
bool isEmpty(QUEUE *);
//打印元素
void print(QUEUE *);
void main(){
	QUEUE q;
	int delValue;
	init(&q);
	
	add(&q, 1);
	add(&q, 2);
	add(&q, 3);
	add(&q, 4);
	add(&q, 5);
	add(&q, 6);
	add(&q, 7);
	add(&q, 8);
	print(&q);
	get(&q, &delValue);
	printf("1出队的值为：%d\n", delValue);
	get(&q, &delValue);
	printf("2出队的值为：%d\n", delValue);
	get(&q, &delValue);
	printf("3出队的值为：%d\n", delValue);
	get(&q, &delValue);
	printf("4出队的值为：%d\n", delValue);
	get(&q, &delValue);
	printf("5出队的值为：%d\n", delValue);
	get(&q, &delValue);
	printf("6出队的值为：%d\n", delValue);
	add(&q, 8);
	add(&q, 9);
	get(&q, &delValue);
	printf("7出队的值为：%d\n", delValue);
}
//初始化循环队列
void init(QUEUE * pQueue){
	pQueue->pBase = (int *) malloc(sizeof(int) * 6);
	pQueue->front = 0;
	pQueue->rear = 0;
}
//入队，在队列有效元素的尾部添加
bool add(QUEUE * pQueue, int value){
	if(isFull(pQueue)){
		printf("队列已经放满了！\n");
		return false;
	}else{
		pQueue->pBase[pQueue->rear] = value;
		pQueue->rear = (pQueue->rear + 1) % 6;
		return true;
	}
}
//出队，从队头开始获取
bool get(QUEUE * pQueue, int * delValue){
	if(isEmpty(pQueue)){
		printf("队列已经空了！\n");
		return false;
	}else{
		*delValue = pQueue->pBase[pQueue->front];
		pQueue->front = (pQueue->front + 1) % 6;
		return true;
	}
}
//是否已经满
bool isFull(QUEUE * pQueue){
	if((pQueue->rear+1) % 6 == pQueue->front){
		return true;
	}
	return false;
}
//是否已经空
bool isEmpty(QUEUE * pQueue){
	if(pQueue->rear == pQueue->front){
		return true;
	}
	return false;
}
//打印元素
void print(QUEUE * pQueue){
	int front = pQueue->front;
	//队头数不等于队尾数，则表示一直都有元素
	while(front != pQueue->rear){
		printf("%d ", pQueue->pBase[front]);
		front = (front+1) % 6;
	}
	printf("\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
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>
#include <stdlib.h>
//链表的节点数据对象
typedef struct Node{
	int data;//数据域
	struct Node * pNext;//指针域
}NODE, * PNODE;
//栈-->类似箱子，先进后出
typedef struct Stack{
	PNODE pTop;
	PNODE pBottom;
}STACK, * PSTACK;
//初始化栈
void init(PSTACK);
//压栈
bool push(PSTACK, int);
//输出栈中的数据
void print(PSTACK);
//出栈
bool pop(PSTACK, int*);
//清空
void clear(PSTACK);
//是否是空栈
bool isEmpty(PSTACK);
void main(){
	STACK stack;
	int value;
	int i = 0;
	init(&stack);
	push(&stack, 1);
	push(&stack, 2);
	push(&stack, 3);
	push(&stack, 4);
	push(&stack, 5);
	push(&stack, 6);
	print(&stack);
	clear(&stack);
	if(pop(&stack, &value)){
		printf("出栈成功！元素值为：%d\n", value);
	}else{
		printf("出栈失败！");
	}
	
	print(&stack);
}
//初始化栈
void init(PSTACK pStack){
	pStack->pTop = (PNODE)malloc(sizeof(NODE));
	if(NULL == pStack->pTop){
		printf("分配内存失败!\n");
		exit(-1);
	}else{
		pStack->pBottom = pStack->pTop;
		pStack->pTop->data = NULL;
	}
}
//压栈
bool push(PSTACK pStack, int value){
	//先造一个节点出来
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if(NULL == pNew){
		printf("分配内存失败!\n");
		return false;
	}else{
		pNew->data = value;
		pNew->pNext = pStack->pTop;
		pStack->pTop = pNew;
		return true;
	}
}
//输出栈中的数据
void print(PSTACK pStack){
	PNODE node = pStack->pTop;
	while(node != pStack->pBottom){
		printf("%d ", node->data);
		node = node->pNext;
	}
	printf("\n");
}
//出栈
bool pop(PSTACK pStack, int * value){
	if(isEmpty(pStack)){
		printf("已经是空栈了\n");
		return false;
	}else{
		//要出栈的节点
		PNODE node = pStack->pTop;
		//出栈节点的值
		*value = node->data;
		//pTop往下移一个
		pStack->pTop = node->pNext;
		//释放出栈节点的内存
		free(node);
		return true;
	}
}
//是否是空栈
bool isEmpty(PSTACK pStack){
	return pStack->pTop == pStack->pBottom ? true : false;
}
//清空
void clear(PSTACK pStack){
	PNODE p = pStack->pTop;
	PNODE q = NULL;
	while(p != pStack->pBottom){
		q = p->pNext;
		//释放内存
		free(p);
		p = q;
	}
	pStack->pTop = pStack->pBottom;
}

顺序表栈

顺序表栈，适合开口向左或向右的操作。顺序存储结构，采用数组实现。

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
package datastructure.part.one;
/**
 * @description
 * @author Denghs
 * @version 1.0,2018年2月8日 上午9:37:53
 * @remark 数组结构的顺序栈
 */
public class Stack<T> {
	private int maxSize; // 栈空间的大小
	private T[] stackArray;// 顺序栈，采用泛型确定栈空间的存放的数据类型
	private int top; // 栈顶指针
	public Stack(int size) {
		maxSize = size;
		stackArray = (T[]) new Object[maxSize];
		top = -1;
	}
	
	/**
	 * 入栈
	 * @param element
	 */
	public void push(T element) {
		stackArray[++top] = element;
		if (top > (maxSize - 1)){
			top = maxSize - 1;
		}
	}
	public void pretendedPush() {
		++top;
		if (top > (maxSize - 1)) {
			top = maxSize - 1;
		}
	}
	
	/**
	 * 出栈
	 * @return
	 */
	public T pop() {
		if (top == -1) {
			return null;
		} else {
			return stackArray[top--];
		}
	}
	
	/**
	 * 查看栈顶元素，但是不出栈
	 * @return
	 */
	public T peek() {
		return stackArray[top];
	}
	
	/**
	 * 判断栈是否空
	 * @return
	 */
	public boolean isEmpty() {
		return top == -1;
	}
	
	/**
	 * 判断栈是否满
	 * @return
	 */
	public boolean isFull() {
		return top == maxSize - 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
package datastructure.part.one;
/**
 * @description
 * @author Denghs
 * @version 1.0,2018年4月5日 下午12:06:32
 * @remark
 */
public class TestStack {
	public static void main(String[] args) {
		Stack<Student> stack = new Stack<Student>(10);
		stack.push(new Student("张三"));
		stack.push(new Student("李四"));
		stack.push(new Student("王五"));
		stack.push(new Student("麻六"));
		stack.push(new Student("黑七"));
		System.out.println(stack.pop().getName());
		System.out.println(stack.pop().getName());
		System.out.println(stack.pop().getName());
	}
}
谢谢你请我吃糖果

--------- 本文结束，感谢您的审阅 ---------
0%