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;
}