Question

求数据结构高手帮忙解决小问题,如果采用另追加250

本人需要下面三个小程序中的任一个做为例题参考学习
1）线形表的应用——迷宫求解
2）二叉树的应用——哈夫曼编码
3）图的应用——最短路径
要求:最好用数据结构中的内容编写
如果原代码太长可以直接发到我邮箱三sdlylfk@163.com
如果合适一定再加分
不要从网上下载的！
如何调试?可不可以把调试过程发过来

Answer 1

　　1）线形表的应用——迷宫求解
　　#include <stdio.h>
　　#include <stdlib.h>
　　#include <string.h>
　　#define TRUE 1
　　#define FALSE 0
　　#define OK 1
　　#define ERROR 0
　　#define OVERFLOW -2
　　typedef int Status;

　　//stack.h
　　#include "base.h"
　　#define INIT_SIZE 100 //存储空间初始分配量
　　#define INCREMENT 10 //存储空间分配增量
　　typedef struct{ //迷宫中r行c列的位置
　　int r;
　　int c;
　　}PostType;
　　typedef struct{
　　int ord; //当前位置在路径上的序号
　　PostType seat;//当前坐标
　　int di; //往下一坐标的方向
　　}SElemType; //栈元素类型
　　typedef struct
　　{
　　SElemType* base;//栈基址,构造前销毁后为空
　　SElemType* top;//栈顶
　　int stackSize; //栈容量
　　}Stack; //栈类型
　　Status InitStack(Stack &S){ //构造空栈s
　　S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType));
　　if(!S.base)
　　exit(OVERFLOW);//存储分配失败
　　S.top=S.base;
　　S.stackSize=INIT_SIZE;
　　return OK;
　　}//InitStack
　　Status StackEmpty(Stack S){
　　//若s为空返回TRUE,否则返回FALSE
　　if(S.top==S.base)
　　return TRUE;
　　return FALSE;
　　}//StackEmpty
　　Status Push(Stack &S,SElemType e){
　　//插入元素e为新的栈顶元素
　　if(S.top-S.base >=S.stackSize){//栈满，加空间
　　S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
　　if(!S.base)
　　exit(OVERFLOW); //存储分配失败
　　S.top=S.base+S.stackSize;
　　S.stackSize+=INCREMENT;
　　}
　　*S.top++=e;
　　return OK;
　　}//push
　　Status Pop(Stack &S,SElemType &e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERROR
　　if(S.top==S.base)
　　return ERROR;
　　e=*--S.top;
　　return OK;
　　}//Pop
　　Status DestroyStack(Stack &S){//销毁栈S,
　　free(S.base);
　　S.top=S.base;
　　return OK;
　　}//DestroyStack

　　//maze.cpp
　　#include "stack.h"
　　#define MAXLEN 10//迷宫包括外墙最大行列数目
　　typedef struct{
　　int r;
　　int c;
　　char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#'
　　}MazeType; //迷宫类型
　　Status InitMaze(MazeType &maze){
　　//初始化迷宫若成功返回TRUE,否则返回FALSE
　　int m,n,i,j;
　　printf("Enter row and column numbers: ");
　　scanf("%d%d",&maze.r,&maze.c); //迷宫行和列数
　　for(i=0;i<=maze.c+1;i++){//迷宫行外墙
　　maze.adr[0][i]='1';
　　maze.adr[maze.r+1][i]='1';
　　}//for
　　for(i=0;i<=maze.r+1;i++){//迷宫列外墙
　　maze.adr[i][0]='1';
　　maze.adr[i][maze.c+1]='1';
　　}
　　for(i=1;i<=maze.r;i++)
　　for(j=1;j<=maze.c;j++)
　　maze.adr[i][j]=' ';//初始化迷宫
　　printf("Enter block's coordinate((-1,-1) to end): ");
　　scanf("%d%d",&m,&n);//接收障碍的坐标
　　while(m!=-1){
　　if(m>maze.r || n>maze.c)//越界
　　exit(ERROR);
　　maze.adr[m][n]='1';//迷宫障碍用'#'标记
　　printf("Enter block's coordinate((-1,-1) to end): ");
　　scanf("%d%d",&m,&n);
　　}//while
　　return OK;
　　}//InitMaze
　　Status Pass(MazeType maze,PostType curpos){
　　//当前位置可通则返回TURE,否则返回FALSE
　　if(maze.adr[curpos.r][curpos.c]==' ')//可通
　　return TRUE;
　　else
　　return FALSE;
　　}//Pass
　　Status FootPrint(MazeType &maze,PostType curpos){
　　//若走过并且可通返回TRUE,否则返回FALSE
　　//在返回之前销毁栈S
　　maze.adr[curpos.r][curpos.c]='0';//"*"表示可通
　　return OK;
　　}//FootPrint
　　PostType NextPos(PostType &curpos,int i){
　　//指示并返回下一位置的坐标
　　PostType cpos;
　　cpos=curpos;
　　switch(i){ //1.2.3.4分别表示东,南,西,北方向
　　case 1 : cpos.c+=1; break;
　　case 2 : cpos.r+=1; break;
　　case 3 : cpos.c-=1; break;
　　case 4 : cpos.r-=1; break;
　　default: exit(ERROR);
　　}
　　return cpos;
　　}//Nextpos
　　Status MarkPrint(MazeType &maze,PostType curpos){
　　//曾走过但不是通路标记并返回OK
　　maze.adr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通
　　return OK;
　　}//MarkPrint
　　Status MazePath(MazeType &maze,PostType start,PostType end){
　　//若迷宫maze存在从入口start到end的通道则求得一条存放在栈中
　　//并返回TRUE,否则返回FALSE
　　Stack S;
　　PostType curpos;
　　int curstep;//当前序号,1.2.3.4分别表示东,南,西,北方向
　　SElemType e;
　　InitStack(S);
　　curpos=start; //设置"当前位置"为"入口位置"
　　curstep=1; //探索第一步
　　do{
　　if(Pass(maze,curpos)){//当前位置可以通过,
　　//即是未曾走到过的通道
　　FootPrint(maze,curpos);//留下足迹
　　e.ord=curstep;
　　e.seat=curpos;
　　e.di=1;
　　Push(S,e); //加入路径
　　if(curpos.r==end.r&& curpos.c==end.c)
　　if(!DestroyStack(S))//销毁失败
　　exit(OVERFLOW);
　　else
　　return TRUE; //到达出口
　　else{
　　curpos=NextPos(curpos,1);
　　//下一位置是当前位置的东邻
　　curstep++; //探索下一步
　　}//else
　　}//if
　　else{ //当前位置不通
　　if(!StackEmpty(S)){
　　Pop(S,e);
　　while(e.di==4
　　&& !StackEmpty(S)){
　　MarkPrint(maze,e.seat);
　　Pop(S,e);
　　//留下不能通过的标记,并退一步
　　}//while

　　if(e.di < 4){
　　e.di++;//换下一个方向探索
　　Push(S,e);
　　curpos=NextPos(e.seat,e.di);//设定当前位置是该
　　//新方向上的相邻
　　}//if
　　}//if
　　}//else
　　}while(!StackEmpty(S));
　　if(!DestroyStack(S))//销毁失败
　　exit(OVERFLOW);
　　else
　　return FALSE;
　　}//MazePath
　　void PrintMaze(MazeType &maze){
　　//将标记路径信息的迷宫输出到终端(包括外墙)
　　int i,j;
　　printf("\nShow maze path(*---pathway):\n\n");
　　printf(" ");
　　for(i=0;i<=maze.r+1;i++)//打印列数名
　　printf("%4d",i);
　　printf("\n\n");
　　for(i=0;i<=maze.r+1;i++){
　　printf("%2d",i);//打印行名
　　for(j=0;j<=maze.c+1;j++)
　　printf("%4c",maze.adr[i][j]);//输出迷宫//当前位置的标记
　　printf("\n\n");
　　}
　　}//PrintMaze
　　void main(){ //主函数
　　MazeType maze;
　　PostType start,end;
　　char cmd;
　　do{
　　printf("-------FOUND A MAZEPATH--------\n");
　　if(!InitMaze(maze)){ //初始化并创建迷宫
　　printf("\nInitialization errors!!!\n");
　　exit(OVERFLOW); //初始化错误
　　}
　　do{ //输入迷宫入口坐标
　　printf("\nEnter entrance coordinate of the maze: ");
　　scanf("%d%d",&start.r,&start.c);
　　if(start.r>maze.r || start.c>maze.c){
　　printf("\nBeyond the maze!!!\n");
　　continue;
　　}
　　}while(start.r>maze.r || start.c>maze.c);
　　do{ //输入迷宫出口坐标
　　printf("\nEnter exit coordinate of the maze: ");
　　scanf("%d%d",&end.r,&end.c);
　　if(end.r>maze.r || end.c>maze.c){
　　printf("\nBeyond the maze!!!\n");
　　continue;
　　}
　　}while(end.r>maze.r || end.c>maze.c);
　　if(!MazePath(maze,start,end))//迷宫求解
　　printf("\nNo path from entrance to exit!\n");
　　else
　　PrintMaze(maze);//打印路径
　　printf("\nContinue?(y/n): ");
　　scanf("%s",&cmd);
　　}while(cmd=='y' || cmd=='Y');
　　}//main
　　2）二叉树的应用——哈夫曼编码
　　二叉树具有以下重要性质：
　　性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。
　　证明：用数学归纳法证明：
　　归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。
　　归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。
　　归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。

　　性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
　　证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：
　　20+21+…+2k-1=2k-1
　　故命题正确。

　　性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。
　　证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：
　　n=no+n1+n2 (式子1)
　　另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：
　　nl+2n2
　　树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
　　n=n1+2n2+1 (式子2)
　　由式子1和式子2得到：
　　no=n2+1

　　满二叉树和完全二叉树是二叉树的两种特殊情形。
　　1、满二叉树(FullBinaryTree)
　　一棵深度为k且有2k-1个结点的二又树称为满二叉树。
　　满二叉树的特点：
　　（1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
　　（2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
　　【例】图(a)是一个深度为4的满二叉树。

　　2、完全二叉树(Complete BinaryTree)
　　若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
　　特点：
　　（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
　　（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
　　（3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
　　【例】如图(c)中，结点F没有左孩子而有右孩子L，故它不是一棵完全二叉树。
　　【例】图(b)是一棵完全二叉树。

　　性质4 具有n个结点的完全二叉树的深度为

　　证明：设所求完全二叉树的深度为k。由完全二叉树定义可得：
　　深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。
　　由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：
　　n>2k-1-1。
　　另一方面，由性质2可得：
　　n≤2k-1，
　　即：2k-1-l<n≤2k-1
　　由此可推出：2k-1≤n<2k，取对数后有：
　　k-1≤lgn<k
　　又因k-1和k是相邻的两个整数，故有
　　,
　　由此即得
　　3.图的应用——最短路径
　　设G=(V,E)是一个每条边都有非负长度的有向图，有一个特异的顶点s称为缘。
　　单源最短路径问题，或者称为最短路径问题，是要确定从s到V中没一个其他
　　顶点的距离，这里从顶点s到x的距离定义为从s到x的最短路径问题。这个问题
　　可以用Dijkstra算法解决。下面我给我了c++下的源代码！ --by 伟伟猪
　　************************************************/
　　#include<iostream.h>
　　void main()
　　{
　　int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
　　cout<<"input the value of n:";
　　cin>>n;
　　cout<<endl;

　　d=new int[n];
　　s=new int[n];
　　p=new int[n];
　　w=new int*[n];
　　for(i=0;i<n;i++) {w[i]=new int[n];}
　　for(i=0;i<n;i++)
　　for(j=0;j<n;j++)
　　cin>>w[i][j];

　　for(s[0]=1,i=1;i<n;i++)
　　{
　　s[i]=0;d[i]=w[0][i];
　　if(d[i]<infinity) p[i]=0;
　　else p[i]=-1;
　　}

　　for(i=1;i<n;i++)
　　{
　　t=infinity;k=1;
　　for(j=1;j<n;j++)
　　if((!s[j])&&(d[j]<t)) {t=d[j];k=j;}
　　s[k]=1;//point k join the S
　　for (j=1;j<n;j++)
　　if((!s[j])&&(d[j]>d[k]+w[k][j]))
　　{d[j]=d[k]+w[k][j];p[j]=k;}

　　}
　　cout<<"从源点到其它顶点的最短距离依次如下：";
　　for(i=1;i<n;i++) cout<<d[i]<<" ";

　　}
　　/*********
　　顶点个数用n表示，这里给出的例子n=6
　　100 1 12 100 100 100
　　100 100 9 3 100 100
　　100 100 100 100 5 100
　　100 100 4 100 13 15
　　100 100 100 100 100 4
　　100 100 100 100 100 100

　　答案尽供参考