数据结构练习-C语言

1.假设有一个带头结点的单链表 L ，每个结点值由单个数字、小写字母和大写字母构成。设计一个算法将其拆分成3个带头结点的单链表L1、L2和L3,L1包含 L 中的所有数字结点，L2包含 L 中的所有小写字母结点，L3包含 L 中的所有大写字母结点。该算法如何设计？

首先创建L1、L2、L3的头结点，然后利用if判断语句将L的单个数字、小写字母和大写字母分配到L1、L2、L3，可以利用尾插法进行分配，最后用建立项目对其验证。

#include<stdio.h>
#include<malloc.h>
//链表结构
typedef struct LNode {
	char data;
	struct LNode* next;
}LN;
//创建链表L
void Create_L(LN*& L, char a[], int n) {
	int i;
	LN* d, * w;
	//建立头结点
	L = (LN*)malloc(sizeof(LN));
	w = L;	//w始终指向尾结点，开始时指向头结点
	//传送数据
	for (i = 0; i < n; i++) {
		d = (LN*)malloc(sizeof(LN));
		d->data = a[i];	//创建数据结点d

		w->next = d;
		w = d;	//尾插法
	}
	w->next = NULL;	//使尾结点next域为NULL
}
//将L分为只含数字、小写字母、大写字母的3个L1、L2、L3
void L123(LN* L, LN*& L1, LN*& L2, LN*& L3) {
	LN* p = L->next, * a, * b, * c, * x, * y, * z;
	//建立头结点
	L1 = (LN*)malloc(sizeof(LN));
	L2 = (LN*)malloc(sizeof(LN));
	L3 = (LN*)malloc(sizeof(LN));
	//x,y,z始终指向尾结点，开始时指向头结点
	x = L1;
	y = L2;
	z = L3;

	while (p != NULL) {
		//判断数据，进行分配
		if (p->data >= '0' && p->data <= '9') {
			a = (LN*)malloc(sizeof(LN));
			a->data = p->data;	//创建数据结点a

			x->next = a;
			x = a;	//尾插法
		}
		else if (p->data >= 'a' && p->data <= 'z') {
			b = (LN*)malloc(sizeof(LN));
			b->data = p->data;	//创建数据结点b

			y->next = b;
			y = b;	//尾插法
		}
		else if (p->data >= 'A' && p->data <= 'Z') {
			c = (LN*)malloc(sizeof(LN));
			c->data = p->data;	//创建数据结点c

			z->next = c;
			z = c;	//尾插法
		}
		else
			printf("错误");

		p = p->next;
	}
	//使尾结点next域为NULL，结束分配
	x->next = NULL;
	y->next = NULL;
	z->next = NULL;
}
//显示链表
void Display_L(LN* L) {
	LN* p = L->next;
	while (p != NULL) {
		printf("%c ", p->data);
		p = p->next;
	}
	printf("\b\n");
}
//主函数，执行任务
int main() {
	LN* L, * L1, * L2, * L3;
	//开始创建L
	char a[9] = { '3','d','G','A','9','c','K','W','4' };
	Create_L(L, a, 9);
	//将L分为只含数字、小写字母、大写字母的3个L1、L2、L3
	L123(L, L1, L2, L3);
	//显示L,L1,L2,L3
	Display_L(L);
	Display_L(L1);
	Display_L(L2);
	Display_L(L3);
}

2.二叉树的顺序存储结构和二叉链存储结构各有什么优缺点？

(1)二叉树的顺序存储结构是将完全二叉树从上到下、从左到右按顺序存储。

①优点：自带元素之间的逻辑关系，方便查找双亲和孩子。

②缺点：在存储非完全二叉树的时候空间利用率低。

(2)二叉链存储结构是由数据域和左右指针域组成，左、右指针分别指向该结点左孩子和右孩子所在的链结点的存储地址。

①优点：知道某结点就知道其左孩子和右孩子；存储利用率高。

②缺点：查找指定结点效率低；包含指针，存储密度小。

3.假设二叉树采用二叉链存储结构，设计一个算法输出从根结点到某个叶子结点的路径逆序列。（遍历算法不限）。

采用后序遍历非递归算法：

①先沿着根结点依次入栈，分配左孩子直到其为空；

②取栈顶元素。若右孩子非空且未被访问过，将右子树转执行①；否则，栈顶元素出栈并访问。

#include<stdio.h>
#include<malloc.h>
//二叉树采用二叉链存储结构
typedef struct BLnode {
	char data;
	struct BLnode *lchild;
	struct BLnode *rchild;
}BLnode,*BT;
//创建二叉树
void Create_BT(BT& T) {
	char a;
	scanf("%c", &a);

	if (a == '#')
		T = NULL;
	else {
		T = (BT)malloc(sizeof(BT));
		T->data = a;	//分配数据
		Create_BT(T->lchild);	//左孩子
		Create_BT(T->rchild);	//右孩子
	}
}
//输出逆序列
void Disp_Inv_Seq(BT &T)
{
	BT b[100], p;
	int top = -1, i,k;
	if(!T) return;	//无值不参与
	do {
		while (T != NULL) {
			b[++top] = T;
			T = T->lchild;	//顺序优先分配左孩子
		}
		p = NULL;	//指针先空
		k = 1;
		while (top != -1 && k) {
			T = b[top];	//取出栈顶
			if (T->rchild == p) {
				//判断是否是叶子结点
				if (T->lchild == NULL && T->rchild == NULL) {
					//输出一个逆序列
					for (i = top; i >= 0; i--)
						printf("%c ", b[i]->data);
					printf("\n");
				}
				top--;
				p = T;
			}
		    else {	//分配右孩子
				T = T->rchild;
				k = 0;
		    }
		}
	} while (top != -1);	//先分配一次，再判断是否取完
}
//主函数
int main() {
	BT T;
	Create_BT(T);
	Disp_Inv_Seq(T);
}

4.给定一个 M x N 的迷宫图、入口与出口、行走规则。求一条从指定入口到出口的路径。（注：栈、队列、递归等方法可任选一种。所求路径必须是简单路径，即路径不重复。）

1.首先设置一个二维数组，元素状态0表示通道，状态1表示障碍物。为了算法方便，一般在迷宫外围加上了一条围墙（表示为1）。

2.采取栈的顺序存储结构。对于每个方块( i , j )，都有相同的行走规则：上、下、左、右相邻方块行走。

先按从方位0到方位3的方向查找下一个可走的相邻方块。由于迷宫存在死路，走入死路需原路返回，因此还需要记下所走的方位。而退回是先进后出，因此采用栈较为方便。

3.路径不重复：

若方块(i,j)可走，则其进栈，设其方位为-1（还没试探其附近，为后面找路时不再探索(i,j)，退栈时恢复为0）。再找其附近方位，若方位x附近(i1,j1)可走，则将方块(i,j)方位变为x，(i1,j1)进栈。重复操作。若方位附近不可走，则退栈。

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MaxSize 200
#define a 10
#define b 10
//定义方块结构
typedef struct {
	int i;     //方块行
	int j;     //方块列
	int di;   //下一个可走相邻方块的方位
}Block;
//定义顺序栈结构
typedef struct {
	Block data[MaxSize];
	int top;	//栈顶指针
}Zhan;
//初始化栈顶指针
void InitStack(Zhan*& s) {
	s = (Zhan*)malloc(sizeof(Zhan));
	s->top = -1;
}
//销毁栈
void DestroyStack(Zhan*& s) {
	free(s);
}
//判断栈是否为空
bool StackEmpty(Zhan* s) {
	return(s->top == -1);
}
//进栈
bool Push(Zhan*& s, Block e) {
	//如果栈满
	if (s->top == MaxSize - 1)
		return false;
	s->top++;	//栈顶指针增1
	s->data[s->top] = e;	//元素放在栈顶指针处
	return true;
}
//出栈
bool Pop(Zhan*& s, Block& e) {
	//如果栈空
	if (s->top == -1)
		return false;
	e = s->data[s->top];	//取栈顶指针元素的元素
	s->top--;	//栈顶指针减1
	return true;
}
//取栈
bool GetTop(Zhan* s, Block& e) {
	//如果栈空
	if (s->top == -1)
		return false;
	e = s->data[s->top];	//取栈顶指针元素的元素 
	return true;
}

//求解路径为(xi,yi)->(xo,yo)
bool FindRoad(int xi, int yi, int xo, int yo, char mig[a][b]) {
	Block road[MaxSize], e;
	int i, j, di, i1, j1, k;
	bool find;
	//定义和初始化栈s
	Zhan* s;
	InitStack(s);
	//设置e为入口
	e.i = xi;
	e.j = yi;
	e.di = -1;
	//进栈
	Push(s, e);
	mig[xi][yi] = -1;	//将入口置-1，避免重复探索该方块而导致死循环
	//入口已入栈，开始探索寻找出口
	while (!StackEmpty(s)) {
		//取栈顶元素e
		GetTop(s, e);
		//将栈顶方块元素赋值给i,j,di
		i = e.i;
		j = e.j;
		di = e.di;
		//判断该位置是否为出口
		if (i == xo && j == yo) {
			printf("该迷宫的一条路径为：\n");
			k = 0;	//k表示路径中的方块数
			//入口先入后出，所以要倒序输出
			while (!StackEmpty(s)) {
				Pop(s, e);			//出栈方块e
				road[k] = e;		//将e添加到road中
				k++;				//下一个方块
			}
			//k多加了1
			while (k > 0) {
				k--;
				printf("(%d,%d)->", road[k].i, road[k].j);
			}
			printf("\b\b. \n");
			DestroyStack(s);
			return true;	//输出一条迷宫路径后成功，返回true
		}
		//该位置找不到出口
		find = false;
		//找到方块(i,j)的下一个相邻方块(i1,j1)
		while (di < 4 && !find) {
			di++;	//选择下一个方位
			switch (di) {
				case 0:	i1 = i - 1; j1 = j; break;
				case 1:	i1 = i; j1 = j + 1; break;
				case 2:	i1 = i + 1; j1 = j; break;
				case 3:	i1 = i; j1 = j - 1; break;
				}
			//找到下一个可走的方块，find置为真
			if (mig[i1][j1] == 0)	find = true;
		}
		//如果找到一个相邻可走的方块(i1,j1)
		if (find) {
			//s指向栈顶元素di，改变原栈顶元素di
			s->data[s->top].di = di;
			e.i = i1;
			e.j = j1;
			e.di = -1;
			//相邻可走的方块e进栈
			Push(s, e);
			mig[i1][j1] = -1;	//将(i1,j1)迷宫值置为-1，避免重复走到该方块
		}
		//没有路可走
		else {
			Pop(s, e);				//将栈顶方块退栈
			mig[e.i][e.j] = 0;		//将退栈的方块变为其他可走的方块
		}
	}
	printf("该迷宫无路可走");	//表示没有路径可走，返回false
	DestroyStack(s);
	return false;		
}

//主函数
int main() {
	//char mig[a][b];
	int m, n;
	//输入迷宫地图
	// for(m=0;m<a;m++)
	// 	for (n = 0; n< b; n++)
	// 		scanf("%d", &mig[m][n]);
	char mig[a][b] = {
		{1,1,1,1,1,1,1,1,1,1},
		{1,0,0,0,1,1,0,0,1,1},
		{1,0,1,0,0,0,0,0,0,1},
		{1,0,0,0,1,1,1,1,1,1},
		{1,1,0,0,0,0,0,0,0,1},
		{1,1,1,1,0,1,1,0,1,1},
		{1,0,1,0,0,1,1,0,0,1},
		{1,0,0,0,1,1,0,0,1,1},
		{1,1,0,0,0,1,0,0,0,1},
		{1,1,1,1,1,1,1,1,1,1}
	};
	//输出迷宫地图
	printf("迷宫如下：\n");
	for (m = 0; m < a; m++) {
		for (n = 0; n < b; n++)
			printf("%d ", mig[m][n]);
			printf("\n");
	}
	//寻找并显示路径
	FindRoad(1,1,a-2,b-2, mig);
	return 0;
}