表顺序存储（数组）

  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


#include <iostream>
using namespace std;
class Arr
{
public:
	int * pbase;
	int len;
	int cnt;
};
void init(Arr*, int);
bool append(Arr*, int);
void show_arr(Arr*);
bool insert(Arr*, int, int);
bool delete_arrr(Arr*, int, int*);
void inversion_arr(Arr*);
void sort(Arr*);
int main()
{
	Arr arr;
	int val;
	init(&arr, 7);
	append(&arr, 18);
	append(&arr, 3);
	append(&arr, 7);
	append(&arr, 3);
	append(&arr, 1);
	append(&arr, 2);
	show_arr(&arr);
	insert(&arr, 2, 5);
	cout << endl;
	show_arr(&arr);
	delete_arrr(&arr, 2, &val);
	cout << endl;
	cout << "你删除的元素为：" << val << endl;
	show_arr(&arr);
	inversion_arr(&arr);
	cout << endl;
	cout << "数值倒置后为：";
	show_arr(&arr);
	sort(&arr);
	cout << endl;
	cout << "排序后为：";
	show_arr(&arr);
	return 0;
}

void init(Arr* parr, int length)
{
	parr->pbase = new int[length];
	parr->len = length;
	parr->cnt = 0;
	return;
}

bool is_full(Arr *parr)
{
	if (parr->cnt == parr->len)
		return true;
	else
		return false;
}
bool append(Arr* parr, int val)
{
	if (is_full(parr))
	{
		return false;
	}
	else
	{
		parr->pbase[parr->cnt] = val;
		++(parr->cnt);
		return true;
	}
}

bool isempty(Arr*parr)
{
	if (0 == parr->cnt)
		return true;
	else
		return false;
}
void show_arr(Arr* parr)
{
	if (isempty(parr))
	{
		cout << "数组为空" << endl;
	}
	else
	{
		for (int i = 0; i < parr->cnt; ++i)
		{
			cout << parr->pbase[i] << " ";
		}
	}

}
bool insert(Arr*parr, int pos, int val)
{
	if (is_full(parr))
	{
		return false;
	}
	if (pos<1 || pos>parr->cnt + 1)
	{
		return false;
	}

	for (int i = parr->cnt - 1; i >= pos - 1; --i)
	{
		parr->pbase[i + 1] = parr->pbase[i];
	}
	parr->pbase[pos - 1] = val;
	++(parr->cnt);
	return true;

}
bool delete_arrr(Arr* parr, int pos, int* pval)
{
	if (isempty(parr))
		return false;
	if (pos<1 || pos>parr->cnt)
		return false;
	*pval = parr->pbase[pos - 1];

	for (int i = pos; i < parr->cnt; ++i)
	{
		parr->pbase[i - 1] = parr->pbase[i];
	}
	--(parr->cnt);
	return true;
}
void inversion_arr(Arr* parr)
{
	int i = 0, j = parr->cnt - 1;
	int t;
	while (i < j)
	{
		t = parr->pbase[i];
		parr->pbase[i] = parr->pbase[j];
		parr->pbase[j] = t;
		++i;
		--j;
	}
	return;
}
void sort(Arr*parr)
{
	int i, j, t;
	for (i = 0; i < parr->cnt; ++i)
	{
		for (j = i + 1; j < parr->cnt; ++j)
		{
			if (parr->pbase[i] < parr->pbase[j])
			{
				t = parr->pbase[i];
				parr->pbase[i] = parr->pbase[j];
				parr->pbase[j] = t;
			}

		}
	}
	return;
}

表链式存储

  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


#include<iostream>
using namespace std;
class node
{
public:
	int data;
	node* pnext;
};
node* create_list(void);
void traverse_list(node*phead);
bool empty_list(node*phead);
int length_list(node*phead);
bool insert_list(node*phead, int pos, int val);
bool delte_list(node*phead, int pos, int*);
bool replace(node*phead, int pos, int val);
int main()
{
	node* phead;
	int val;
	phead = create_list();
	traverse_list(phead);
	cout << endl;
	cout << "链表长度为：" << length_list(phead);
	/*delte_list(phead, 2, &val);
	insert_list(phead, 2, 888);*/
	replace(phead, 2, 888);
	delte_list(phead, 4, &val);
	insert_list(phead, 4, 999);
	cout << endl;
	cout << "某个位置插入新值后的链表遍历：";
	traverse_list(phead);
	cout << endl;
	cout << "插入元素后链表长度为：" << length_list(phead);
	delte_list(phead, 2, &val);
	cout << endl;
	cout << "删除的元素是:" << val;
	cout << endl;
	cout << "删除元素后链表长度为：" << length_list(phead);
	cout << endl;
	cout << "删除值后的链表遍历：";
	traverse_list(phead);

	return 0;
}
node* create_list(void)
{
	int len;
	int val;
	cout << "请输入要存放结点的个数:len=";
	cin >> len;
	node* phead = new node;
	node* ptail = phead;
	ptail->pnext = NULL;
	for (int i = 0; i < len; ++i)
	{
		cout << "请输入第" << i + 1 << "个结点的值：";
		cin >> val;
		node* pnew = new node;
		pnew->data = val;
		ptail->pnext = pnew;
		pnew->pnext = NULL;
		ptail = pnew;
	}
	return phead;
}
void traverse_list(node*phead)
{
	node*p = phead->pnext;
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->pnext;
	}
	return;
}
bool empty_list(node*phead)
{
	if (phead->pnext == NULL)
		return true;
	else
		return false;
}
int length_list(node*phead)
{
	int len = 0;
	while (phead->pnext != NULL)
	{
		phead = phead->pnext;
		++len;
	}
	return len;
}
bool insert_list(node*phead, int pos, int val)
{
	int i = 0;
	node*p = phead;
	while (p != NULL&&i < pos - 1)
	{
		p = p->pnext;
		++i;
	}
	if (p == NULL || i > pos - 1)
	{
		return false;
	}
	node* pnew = new node;
	pnew->data = val;
	pnew->pnext = p->pnext;
	p->pnext = pnew;
	return true;
}
bool delte_list(node*phead, int pos, int *pval)
{
	int i = 0;
	node*p = phead;
	while (p != NULL&&i < pos - 1)
	{
		p = p->pnext;
		++i;
	}
	if (p == NULL || i > pos - 1)
	{
		return false;
	}
	node* q = p->pnext;
	*pval = q->data;
	p->pnext = q->pnext;
	delete q;

	return true;
}
bool replace(node*phead, int pos, int val)
{
	int poss = pos;
	int vall = val;
	delte_list(phead, poss, &val);
	insert_list(phead, poss, vall);
	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


#include <iostream>
using namespace std;
class Node
{
public:
	int data;
	Node * pnext;
protected:
private:
};
class Stack
{
public:
	Node * ptop;
	Node * pbottom;
protected:
private:
};
void init(Stack* ps);
void push(Stack*, int);
void traverse(Stack*);
bool pop(Stack*, int *);
void clear(Stack *);
int main(void)
{
	Stack s;
	int val;
	init(&s);
	push(&s, 1);
	push(&s, 5);
	push(&s, 6);
	push(&s, 8);
	/*clear(&s);*/
	traverse(&s);
	if (pop(&s, &val))
	{
		cout << "出栈成功" << "出栈的元素为：" << val;
	}
	else
	{
		cout << "出栈失败";
	}

	return 0;

}
void init(Stack* ps)
{
	ps->ptop = new Node;
	ps->pbottom = ps->ptop;
	ps->ptop->pnext = NULL;
}
void push(Stack*ps, int val)
{
	Node* pnew = new Node;
	pnew->data = val;
	pnew->pnext = ps->ptop;//先让新的结点的指针域向下指向栈顶中哪个结点
	ps->ptop = pnew;//再将栈顶指针指向新的结点
	return;
}
void traverse(Stack*ps)
{
	Node* p = ps->ptop;
	while (p != ps->pbottom)
	{
		cout << p->data << endl;
		p = p->pnext;
	}
	return;
}
bool empty(Stack*ps)
{
	if (ps->ptop == ps->pbottom)
		return true;
	else
		return false;
}
bool pop(Stack*ps, int *pval)
{
	if (empty(ps))
	{
		return false;
	}
	else
	{
		Node* r = ps->ptop;
		*pval = r->data;
		ps->ptop = r->pnext;
		free(r);
		r = NULL;
		return true;
	}
}
void clear(Stack* ps)
{
	if (empty(ps))
	{
		return;
	}
	else
	{
		Node* p = ps->ptop;
		Node* q = NULL;
		while (p != ps->pbottom)
		{
			q = p->pnext;
			free(p);
			p = q;
		}
		ps->ptop = ps->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
 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


# include <iostream>
using namespace std;

class Queue
{
public:
	int * pBase;
	int front;
	int rear;
};

void init(Queue *);
bool en_queue(Queue *, int val);  //入队
void traverse_queue(Queue *);
bool full_queue(Queue *);
bool out_queue(Queue *, int *);
bool emput_queue(Queue *);

int main(void)
{
	Queue Q;
	int val;
	init(&Q);
	en_queue(&Q, 1);
	en_queue(&Q, 2);
	en_queue(&Q, 3);
	en_queue(&Q, 4);
	en_queue(&Q, 5);
	en_queue(&Q, 6);
	en_queue(&Q, 7);
	en_queue(&Q, 8);

	traverse_queue(&Q);

	if (out_queue(&Q, &val))
	{
		printf("出队成功，队列出队的元素是: %d\n", val);
	}
	else
	{
		printf("出队失败!\n");
	}
	traverse_queue(&Q);

	return 0;
}

void init(Queue *pQ)
{
	pQ->pBase = new int[6];
	pQ->front = 0;
	pQ->rear = 0;
}

bool full_queue(Queue * pQ)
{
	if ((pQ->rear + 1) % 6 == pQ->front)
		return true;
	else
		return false;
}

bool en_queue(Queue * pQ, int val)
{
	if (full_queue(pQ))
	{
		return false;
	}
	else
	{
		pQ->pBase[pQ->rear] = val;
		pQ->rear = (pQ->rear + 1) % 6;
		return true;
	}
}

void traverse_queue(Queue * pQ)
{
	int i = pQ->front;

	while (i != pQ->rear)
	{
		cout << pQ->pBase[i];
		i = (i + 1) % 6;
	}
	cout << endl;

	return;
}

bool emput_queue(Queue * pQ)
{
	if (pQ->front == pQ->rear)
		return true;
	else
		return false;
}

bool out_queue(Queue * pQ, int * pVal)
{
	if (emput_queue(pQ))
	{
		return false;
	}
	else
	{
		*pVal = pQ->pBase[pQ->front];
		pQ->front = (pQ->front + 1) % 6;

		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
117
118
119
120
121
122
123
124
125
126
127
128


#include<stdio.h>
#include<stdlib.h>
#define NULL 0
typedef char TElemType;
//动态二叉链表
typedef struct BiTNode {
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

#define MAXSIZE 100
typedef BiTNode* SElemType;
typedef struct SqStack {
	SElemType data[MAXSIZE];
	int top;//指向栈顶元素
}SqStack;

//初始化空栈
void initStack(SqStack &s) {
	s.top = 0;
}

//判栈空
bool isEmpty(SqStack s) {
	if (s.top == 0) {
		//printf("是空栈\n");//
		return true;
	}
	else {
		return false;
	}
}

//判栈满
bool isFull(SqStack s) {
	if (s.top == MAXSIZE) {
		return true;
	}
	else {
		return false;
	}
}

//取栈顶元素
void getTopElem(SqStack s, SElemType &e) {
	if (!isEmpty(s))
		e = s.data[s.top - 1];
	else
		printf("此栈为空栈，取栈顶元素失败\n");
}

//入栈
void push(SqStack &s, SElemType e) {
	if (!isFull(s)) {
		s.data[s.top] = e;
		s.top++;
	}
	else
		printf("此栈已满，入栈操作失败\n");
}

//出栈
void pop(SqStack &s, SElemType &e) {
	if (!isEmpty(s)) {
		e = s.data[s.top - 1];
		s.top--;
	}
	else
		printf("此栈为空栈，出栈操作失败\n");
}
//利用先序序列建立一颗二叉树，先序序列读入：'a', 'b', 'c', '.', '.', 'd', 'e', '.', 'g', '.', '.', 'f', '.', '.', '.' 
//,'.'代表空树
//测试用例：abc..de.g..f...#
void createBiTreeByPreOrder(BiTree &T) {
	//按先序次序输入二叉树中节点的值（一个字符），点号字符表示空树，构造二叉链表表示的二叉树
	//注意：若输入的字符数（不含#号）为n个，则相应的空树即点号就应该有n+1个
	char ch;
	scanf_s("%c", &ch);
	//printf("test:%c\n", ch);
	if (ch != '#') {
		if (ch == '.') {
			T = NULL;
		}
		else {
			T = (BiTNode *)malloc(sizeof(BiTNode));
			T->data = ch;
			createBiTreeByPreOrder(T->lchild);
			createBiTreeByPreOrder(T->rchild);
		}
	}
}
//后序遍历打印二叉树的非递归算法（左、右、根）
void postOrderPrint2(BiTree T) {
	SqStack s;
	initStack(s);
	BiTNode *p = T;
	while (p || !isEmpty(s)) {
		if (p) {
			push(s, p);
			p = p->lchild;
		}
		else {
			BiTNode *top;
			getTopElem(s, top);//取得栈顶元素
			if (top->data > 0) {//栈顶元素的右子树还没有被访问过
				p = top->rchild;
				top->data = -top->data;//赋右子树已遍历标志

			}
			else {//栈顶元素的右子树已经访问过了
				printf("%c ", -top->data);
				pop(s, top);
				//p = NULL;				
			}
		}
	}
}
void main() {
	BiTree T;
	printf("请按先序次序输入二叉树各节点的值，以点号表示空树，以#号结束:\n");
	createBiTreeByPreOrder(T);

	printf("后序遍历打印二叉树（非递归算法）:\n");
	postOrderPrint2(T);
	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


#include <stdio.h>
int book[101], sum, n, e[101][101];
void dfs(int cur) //当前所在的顶点编号
{
	int i;
	printf("%d", cur);
	sum++;//每访问一个顶点，sum就加1
	if (sum == n)
		return;//所有的顶点都已经访问过则直接退出
	for (i = 1; i <= n; i++)//从1号顶点到n号顶点依次尝试，看哪些顶点与当前顶点cur有边相连
	{
		//判断当前顶点cur到顶点i是否有边，并判断顶点i是否已访问过
		if (e[cur][i] == 1 && book[i] == 0)
		{
			book[i] = 1;//标记顶点i已经访问过
			dfs(i);//从顶点i再出发继续遍历
		}
	}
	return;
}
int main()
{
	int i, j, m, a, b;
	scanf_s("%d %d", &n, &m);
	//初始化二维矩阵
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (i == j)
				e[i][j] = 0;
			else
				e[i][j] = 99999999;//假设9999999位正无穷
								   //读入顶点之间的边
	for (i = 1; i <= m; i++)
	{
		scanf_s("%d %d", &a, &b);
		e[a][b] = 1;
		e[b][a] = 1;//这里是无向图，所以需要将e[b][a]也赋值为1
	}
	//从1号顶点出发
	book[1] = 1;//标记1号顶点已访问
	dfs(1);//从1号顶点开始遍历
	getchar();
	getchar();
	return 0;

}

数据结构与算法练习

文章目录

表顺序存储（数组）

表链式存储

栈动态栈

队列静态队列

二叉树动态存储

深度优先搜索

文章目录

表 顺序存储（数组）

表 链式存储

栈 动态栈

队列 静态队列

二叉树 动态存储

深度优先搜索

表顺序存储（数组）

表链式存储

栈动态栈

队列静态队列

二叉树动态存储