28文档仅供参考第三题课题内容从键盘接收一串电文字符，输出对应的Huffman编码。同时，能翻译由Huffman编码生成的代码串，输出对应的电文字符串。课题要求l构造一棵Huffman树。l实现Huffman编码，并用Huffman编码生成的代码串进行译码。l程序中字符和权值是可变的，实现程序的灵活性。设计思想题目明显意见，我们能够使用哈夫曼的相关函数和变量来对题目的相关要求进行实现。哈夫曼树结点的结构typedefstruct{DataTypedata;//数据用字符表示intweight;//权值intparent;//双亲1102020年4月19日
29文档仅供参考intleft;//左孩子intright;//右孩子}HuffNode;哈夫曼编码的存储结构typedefstruct{DataTypecd[MAXNUM];//存放编码位串intstart;//编码的起始位置}HuffCode;问题分析本题可利用哈夫曼树的相关函数来完成此题的相关要求。建立哈夫曼树该算法执行的时间复杂度为：O（n2）哈夫曼编码该算法执行的时间复杂度为：O（n）哈夫曼译码：该算法执行的时间复杂度为：O（n2）；1102020年4月19日
30文档仅供参考程序实现的相关函数如下：intHuffmanCreate(HuffNode*ht)//建立哈夫曼树voidEncoding(HuffNodeht[],HuffCodehcd[],intn)//哈夫曼编码voidDecoding(HuffNodeht[],HuffCodehcd[],intn)//哈夫曼译码1102020年4月19日
31文档仅供参考流程图图12建立哈夫曼树算法流程图1102020年4月19日
32文档仅供参考图13哈夫曼编码流程图译码过程是编码的逆过程，算法流程图此处省略。1102020年4月19日
33文档仅供参考伪代码测试和分析1.建立哈夫曼树：2.哈夫曼编码：1102020年4月19日
34文档仅供参考1.哈夫曼译码：第四题课题内容当我们参观某校园时，就会遇到这样一个问题：从当前所处的位置出发去校园另外某个位置，要走什么样的路线距离最近（或最省时）？本课程设计实例在给出校园各主要建筑的名称信息及有路线连通的建筑之间的距离（或行进时间）的基础上，利用校园导航系统计算出给定的起点到终点之间距离最近（或进行时间最短）的行进路线。课题要求l从地图文件中读取校园主要建筑信息及建筑间的距离（或行进时间）信息。1102020年4月19日
35文档仅供参考l计算给出定的起点到终点之间距离最近（或行进时间最短）的行进路线。l输出该路线（包含路过哪些建筑）及其总距离（或总行进时间）。l若输入错误，则给出提示信息。问题分析本题可利用狄克斯特拉算法算法的相关函数来完成此题的相关要求。读入校园网要求执行时需要建立1个文档文件，并置文件属性为可读，并将文件中的字符读入到文件中。执行该算法的时间复杂度为：O（n）最短路径查找迪克斯特拉算法的执行。该算法的时间复杂度为：O（m+nlogn)程序实现的相关函数如下：voidInit(GraphMatrix*g)//初始化有向网,读入校园地图文件voidDijkstra(GraphMatrix*pgraph,Pathdist[],intstart)//狄克斯特拉算法的执行1102020年4月19日
36文档仅供参考流程图图14校园网读入新建数组流程图1102020年4月19日
37文档仅供参考图15狄克斯特拉算法流程图伪代码typedefstruct{intn;/*图的顶点个数*/VexTypevexs[MAXVEX];/*顶点信息文字*/AdjTypearcs[MAXVEX][MAXVEX];/*边信息*/}GraphMatrix;typedefstruct/*保存最短路径的结构体*/{AdjTypelen;/*最短路径长度*/intpre;/*前一顶点*/}Path;Thenread“campusnav.txt”读入网的顶点个数构造顶点向量初始化邻接矩阵Dijkstra算法在文件中查找路径1102020年4月19日
38文档仅供参考测试和分析经过测试得知该程序查找正确。总程序1、问题描述将四个题目放在一个大程序中完成2、设计要求程序中要有菜单选择进入各个子功能，最好做到两级以上的菜单。能够利用文件处理的一定要用文件进行数据的存储。3、解题分析设计界面，并调用各个功能模块的主调用函数。4、数据结构描述switch(j){case1:program1();break;case2:program2();break;1102020年4月19日
39文档仅供参考case3:program3();break;case4:program4();break;case5:exit(0);}5、算法流程图描述6、算法复杂度分析主函数的时间复杂度为O(1)。7、测试数据（1）主界面：1102020年4月19日
40文档仅供参考（2）：选择功能界面：附录程序清单总程序#include#includeintprogram1();intprogram2();intprogram3();intprogram4();intmain(){intc,a;printf("******请选择要进行的操作******
41");printf("******1:程序功能选择******
42");1102020年4月19日
43文档仅供参考printf("******2:退出******
44");while(1){scanf("%d",&c);if(c!=1&&c!=2){printf("程序功能输入有误，请再输入一次。");scanf("%d",&c);}elseif(c==1){printf("******请选择要进行的功能******
45");printf("******1:数据库管理系统******
46");printf("******2:大整数计算器******
47");printf("******3:电文的译码和编码******
48");printf("******4:校园导航******
49");scanf("%d",&a);if(a!=1&&a!=2&&a!=3&&a!=4){printf("您的输入有误，请重新输入！
50");scanf("%d",&a);}1102020年4月19日
51文档仅供参考switch(a){case1:program1();break;case2:program2();break;case3:program3();break;case4:program4();break;}}elseif(c==2){exit(0);}scanf("%d",&c);}return0;}1102020年4月19日
52文档仅供参考第一题#include"consts.h"#include/*文件相关函数*/intlength=1;intfangwen=0;intgo;/*存储当前指向的记录的编号值*/typedefstruct_node/*定义数据库的类型*/{chardata[110];/*存储输入的数据*/chartype[110];/*存储输入的数据类型*/struct_node*next;}Linklist;struct_point{chardata[20];};struct_pointwj[200][10];/*定义结构体型的二维数组以便用来与文件进行交互*/charmem[110];/*分别存储文件的每一行，再复制给wj数组*/charch;/*分别接收文件的每一个字符*/introw=0;/*wj数组的行数，也就是数据库中的记录数目*/intlie=0;1102020年4月19日
53文档仅供参考intcom=0;/*记录wj的列数*/inti,j,bianlen,fanlen=0;charmember[110];charbian[100];/*自动生成的编号转换为相对应的字符串*/charfabian[100];/*反向存储bian数组*/FILE*fp;voidSwitch(charbian[],intnum)/*把数字转换为字符数组*/{intl=0;intn=num;while(1)/*把数转化为相应的字符串并存放到bian数组中*/{if(n==0)break;n=num%10;bian[l]=n+48;l++;n=n/10;}}/*（1）显示帮助界面函数1102020年4月19日
54文档仅供参考输出"命令一览表"，帮助用户正确使用命令。*/voidHelp(){printf("*命令一览表*
55");printf("*1,创立数据库命令语法格式->creatdatabasename*
56");printf("*2,追加字段的命令->mingling*
57");printf("*3,浏览数据库中所有字段命令->brows*
58");printf("*4,go-disp命令语法格式->gonumber(eg:go1)go定位浏览字段,用disp浏览定位的字段*
59");printf("*5,条件定位命令语法格式->locatefor字段名=\"字段内容\"*
60");printf("*6,按条件删除命令语法格式->deletefor字段名=\"字段内容\"*
61");printf("*7,全部删除命令->zap*
62");printf("*8,按条件修改命令->changefor字段名=\"字段内容\"*
63");printf("*9,按条件排序命令->升序:sorton字段名/a降序:sorton字段名/d*
64");printf("*10,打开帮助文档命令->help*
65");printf("*11，打开已创立的数据库文件->use文件名(eg:use1)*
66");printf("*12,关闭已打开的数据库文件->/use*
67");1102020年4月19日
68文档仅供参考printf("*13,退出数据库管理系统->quit*
69");}/*（2）创立数据库函数模块首先为数据库分配内存，输入第0个字段为"编号"，以后每追加一条数据，都自动对其进行编号，方便之后进行定位，、删除等操作。编写一个while无限循环，引导用户定义字段，包括输入字段名和定义字段类型，直至输入'$'结束，跳出循环。字段类型可为：string，int，double，。用户每输入一个字段类型，程序调转执行到loop，也是一个无限while循环，判断字段类型是否规范。规范的字段类型包括：string，int，double。所有字段定义结束后，输出定义的全部字段及其类型，方便用户使用。*/voidCreateStruct(Linklist*database[],int*length)/*建立数据库类型*/{charch[110],type[110],tou[]="编号\0";/*建立库结构时候自动建立编号字段*/introw,i;database[0]=(Linklist*)malloc(sizeof(Linklist));strcpy(database[0]->data,tou);/*建立编号字段*/strcpy(database[0]->type,"char");/*建立库结构*/printf(".请输入字段%d的名称以'$'结束输入
70",*length);printf(".");1102020年4月19日
71文档仅供参考scanf("%s",ch);if(strcmp(ch,"$")==0)printf("数据库没有构建成功！");else{printf(".请输入字段%d的类型(string,int,double)
72",*length);scanf("%s",type);loop:while(1){if(strcmp(type,"string")==0||strcmp(type,"int")==0||strcmp(type,"double")==0)/*判断结构类型*/break;else{printf("您输入的类型非法！请重新输入
73");printf(".请输入字段%d的类型(string,int,double)
74",*length);scanf("%s",type);}}while(1)/*循环输入库结构类型以"$"结束输入*/1102020年4月19日
75文档仅供参考{row=strlen(ch);ch[row]='';ch[row+1]='\0';database[*length]=(Linklist*)malloc(sizeof(Linklist));strcpy(database[*length]->data,ch);strcpy(database[*length]->type,type);*length=*length+1;printf(".请输入字段%d的名称以'$'结束输入
76",*length);printf(".");scanf("%s",ch);if(strcmp(ch,"$")==0)break;printf(".请输入字段%d的类型(string,int,double)
77",*length);scanf("%s",type);gotoloop;/*如果输入的类型不匹配则跳转到loop*/}for(i=0;i<*length;i++)printf("%s(%s)",database[i]->data,database[i]->type);/*输入结束时输出数据库字段和类型*/}}/*（3）打开数据库函数模块1102020年4月19日
78文档仅供参考以读写模式打开已经存在的文件，将其中数据读到数组ch中，然后将获得的数据按行存入二维数组wj中，。其中，以空格为字段值的分隔符，以回车为行的分隔符。*/voidOpen(charapp[],int*com,int*row,charbian[],charfabian[]){/*打开数据库文件而且将文件中的数据存入结构体二维数组中*/FILE*fp;charch;charmem[110];intlie=0;memset(bian,'\0',sizeof(bian));/*开始字符型数组初始化*/memset(mem,'\0',sizeof(mem));/*开始字符型数组初始化*/memset(fabian,'\0',sizeof(fabian));/*开始字符型数组初始化*/fp=fopen(app,"r+");/*打开相应的数据库文件*/ch=fgetc(fp);/*获得文件中的每一个字符一直到文件末尾*/while(ch!=EOF)/*把获取的字符按行存入到wj数组里*/{if(ch=='')/*如果遇到空格就把mem复制到wj的一个单元中*/{strcpy(wj[*row][*com].data,mem);1102020年4月19日
79文档仅供参考*com=*com+1;memset(mem,'\0',sizeof(mem));/*把mem复制到wj的一行后初始化mem数组*/lie=0;}elseif(ch=='
80')/*如果遇见回车则结束wj的一行，开始存储下一行*/{*row=*row+1;*com=0;/*列恢复0*/}else{mem[lie]=ch;/*把在数据库文件中读出的一行存放在mem数组中*/lie++;}ch=fgetc(fp);/*获取文件的下一个字符*/}*row=*row+1;/*每存完一行行数自加*/}/*（4）追加数据函数模块1102020年4月19日
81文档仅供参考首先为追加的数据自动生成编号：若数据库中已存在记录，则追加的数据标号为其上一个数据的编号+1。因此，先取出上一条数据的编号（字符型），将其转化成int型，然后+1，即为追加的数据的编号，再将其转化成字符型，存入数据库。若数据库中没有数据，则追加数据编号为1，存入数据库。其次，编辑for循环，引导用户输入对应字段的数据信息，将其存入数据库，追加数据操作完成。*/voidappend(charbian[],intfanlen,charfabian[],intbianlen,int*com,int*row)/*追加记录*/{inti,j,k=1,sum=0;memset(bian,'\0',sizeof(bian));/*初始化数组的值*/if(*row>1)/*自动生成编号的值*/{j=strlen(wj[*row-1][0].data);for(i=j-1;i>=0;i--)/*将数据库最后一条记录的编号值转化为整型*/{sum=sum+(wj[*row-1][0].data[i]-'0')*k;k*=10;}sum++;/*追加记录的编号为其最后一条记录的编号加1*/1102020年4月19日
82文档仅供参考Switch(bian,sum);}elseSwitch(bian,1);/*将其编号的值转化为相对应的字符串*/fanlen=0;memset(fabian,'\0',sizeof(fabian));bianlen=strlen(bian);for(i=bianlen-1;i>=0;i--)fabian[fanlen++]=bian[i];/*因为转化的字符串为该编号的逆序因此将其反向存贮*/fabian[fanlen]='\0';strcpy(wj[*row][0].data,fabian);for(i=1;i<*com;i++)/*分别最加各条记录的值*/{printf("请输入：%s",wj[0][i].data);scanf("%s",wj[*row][i].data);}*row=*row+1;/*追加成功后行数自加*/printf("该数据添加成功！
83");}/*（5）浏览数据库函数模块1102020年4月19日
84文档仅供参考此模块功能为：格式输出数据库中数据，起到浏览数据功能。首先编写嵌套for循环，记录每个字段值中最长的字段的长度maxlen。然后，再用嵌套for循环输出数据库中数据，按照最长的字段格式输出，不足的字段，以空格补充，使得浏览输出的数据整齐清晰。*/voidDisplay(charmem[],int*com,int*row)/*浏览写进数组中的数据*/{inti,j,k,flen,maxlen=-1;memset(mem,'\0',sizeof(mem));for(i=0;i<*row;i++)/*记录每个字段值中最大的程度以便调整输出的格式*/for(j=0;j<*com;j++){flen=strlen(wj[i][j].data);if(flen>maxlen)maxlen=flen;//maxlen是输出的格式的标准}//输出的星号的个数是字段中含字符个数最多的字段的字符个数值for(i=0;i<*row;i++)/*输出wj中所有的字段内容*/1102020年4月19日
85文档仅供参考{for(j=0;j<*com;j++){printf("%s",wj[i][j].data);for(k=strlen(wj[i][j].data);k<=maxlen;k++)printf("");}printf("
86");}printf("
87");}/*（6）浏览定位函数模块DispGo浏览定位的数据，go为浏览定位编号。浏览数据时，首先记录最长字段的长度，以便调整输出格式。然后，以调整好的格式输出第一行，也就是输出数据库的字段名。最后，格式输出指定的编号为'go'的一行数据。*/voidDispGo(intgo,int*com,int*row)/*DispGo函数*/{inti,j,k,maxlen=-1,flen;for(i=0;i<*row;i++)/*记录每个字段值中最大的程度以便调整输出的格式*/for(j=0;j<*com;j++)1102020年4月19日
88文档仅供参考{flen=strlen(wj[i][j].data);if(flen>maxlen)maxlen=flen;}printf("
89");for(i=0;i<*com;i++)/*输出wj第一行，也就是数据库类型行*/{printf("%s",wj[0][i].data);for(k=strlen(wj[0][i].data);k90");printf("
91");for(j=0;j<*com;j++)/*格式化输出go所指的字段值*/{printf("%s",wj[go][j].data);for(k=strlen(wj[go][j].data);k<=maxlen;k++)printf("");}printf("
92");printf("
93");1102020年4月19日
94文档仅供参考}/*（7）按条件删除函数模块删除的命令格式为：deletefor字段名="字段内容"，先将命令第二个字符串存入link，对比是否为for，若不是，提示命令错误；若为for，再用for循环将"字段名="字段内容""存入数组value，遍历该数组，经过比对"="，取出"="号前面的字段名，存入数组zd。类似的，比对双引号""，取出两个双引号之间的字符串，即为字段内容，存入数组lx，若没有""，同样提示命令错误。在数据库中字段中匹配zd，若不存在，提示数据库没有该字段；若存在，定位这个字段，将这个字段下所有的值与lx对比。若存在lx，依次将它后面的数据依次前移，覆盖掉需要删除的字段，实现删除功能。*/voidDelete(charmem[],int*com,int*row)/*删除函数*/{charlink[110],value[110],zd[110],lx[110];/*link接收输入的for命令,value为接收所要删除的字段的名称和内容zd数组为接收要查找的字段，lx为要查找字段的内容*/intlxlen=0,vlen,start=-1,end=-1,i,j,flag1=0,linklen,jilu=-1,dingwei=-1,zdlen=0;scanf("%s",link);/*接收输入的for*/scanf("%s",value);/*接受输入的for后面的字符串*/vlen=strlen(value);1102020年4月19日
95文档仅供参考linklen=strlen(link);link[linklen]='';link[linklen+1]='\0';memset(mem,'\0',sizeof(mem));memset(zd,'\0',sizeof(zd));memset(lx,'\0',sizeof(lx));for(i=0;i96");gotoloop;}for(i=0;i97文档仅供参考start=i;flag1=1;}elseif(value[i]==34&&flag1==1){end=i;/*遇见最后一个双引号记录下标并退出*/break;}}if(start==-1||end==-1)/*如果没有遇见一对引号说明输入的语法错误*/{printf("您输入的命令语法有错误！
98");gotoloop;}for(i=start+1;i99文档仅供参考if(strcmp(wj[0][i].data,zd)==0)jilu=i;if(jilu==-1){printf("数据库没有该字段的值!
100");gotoloop;}for(i=0;i<*row;i++)/*如果匹配到该行，则dingwei变量定位到该行*/{if(strcmp(wj[i][jilu].data,lx)==0){dingwei=i;break;}}if(dingwei==-1){printf("数据库中没有符合该条件的字段！
101");gotoloop;}for(i=dingwei;i<*row-1;i++)/*删除其匹配成功的字段并删除*/1102020年4月19日
102文档仅供参考{for(j=1;j<*com;j++)strcpy(wj[i][j].data,wj[i+1][j].data);/*删除该行后除编号字段，后面所有字段所对应数据向上移动一行*/}*row=*row-1;/*删除后总行数减1*/printf("删除成功！
103");loop:;}/*（8）按条件定位模块Locate的命令格式为locatefor字段名="字段内容"先用link1数组接受"for"字符串，然后进行判断link数组中接受的字符串是否为"for"，如果不是for，输出语法错误，用loop命令跳到函数末尾；如果是"for"则用value1接受输入的条件字符串。然后用zd1接受value1中"="号以前的字符，如果没有"="则输出语法错误，跳到函数末尾。用lx1数组接受双引号之间的字符，如果没有出现双引号则输出语法错误，用loop命令跳到函数末尾，否则在wj数组中符合zd1的那一列中匹配和lx1数组中内容相符的那一行。然后用disp进行浏览，然后再用continue命令查找符合条件的下一行，再用disp进行浏览。如果wj中没有符合条件的字段，则输出"数据库没有符合该条件的字段"。*/1102020年4月19日
104文档仅供参考voidLocate(charmem[],int*com,int*row)/*筛选特定字段的函数*/{charlink[110],value[110],zd[110],lx[110];intj,k,flen,maxlen=-1;intzdlen=0,lxlen=0,vlen,start=-1,end=-1,i,flag1=0,linklen,jilu=-1,dingwei=-1;scanf("%s",link);/*存放for字符串*/scanf("%s",value);/*存放for后面的字符串*/vlen=strlen(value);/*测量value数组的长度*/linklen=strlen(link);/*测量link数组的长度*/link[linklen]='';link[linklen+1]='\0';memset(mem,'\0',sizeof(mem));/*初始化数组*/memset(zd,'\0',sizeof(zd));/*初始化字段数组*/memset(lx,'\0',sizeof(lx));/*初始化要匹配的内容数组*/for(i=0;i105文档仅供参考zd[zdlen]='\0';/*末尾赋予结束标识*/if(strcmp(link,"for")!=0)/*如果link没有与"for"匹配成功则说明命令语法有错误*/{printf("您输入的命令有语法错误！
106");gotoloop;/*跳到loop指向的位置，也就是函数末尾*/}for(i=0;i107文档仅供参考if(start==-1||end==-1)/*如果start或者end没有全部找到则说明命令有错误*/{printf("您输入的命令语法有错误！
108");gotoloop;/*跳到loop指定的位置，也就是函数末尾*/}for(i=start+1;i109");gotoloop;/*跳到loop指向的位置，也就是函数末尾*/}1102020年4月19日
110文档仅供参考for(i=0;i<*row;i++)/*记录每个字段值中最大的程度以便调整输出的格式*/for(j=0;j<*com;j++){flen=strlen(wj[i][j].data);if(flen>maxlen)maxlen=flen;}printf("
111");for(i=0;i<*com;i++)/*输出wj第一行，也就是数据库类型行*/{printf("%s",wj[0][i].data);for(k=strlen(wj[0][i].data);k112");for(i=0;i<*row;i++)/*在匹配成功的字段中查找满足条件的内容的行的位置*/{if(strcmp(wj[i][jilu].data,lx)==0)/*如果找到则dingwei等于该行所在的位置*/1102020年4月19日
113文档仅供参考{for(j=0;j<*com;j++)/*格式化输出go所指的字段值*/{printf("%s",wj[i][j].data);for(k=strlen(wj[i][j].data);k<=maxlen;k++)printf("");}printf("
114");}}loop:;}/*（9）按条件修改数据函数模块用相同的方法，取出需要修改的字段名和字段值。将得到的字段名与数据库里的字段名对比，若不一致，则显示命令错误。之后将需要修改的数据的值与数据库中该字段的所有数据对比，若存在，提示用户根据字段依次输入新的数据；若不存在，显示没有符合该条件的字段。*/voidChange(charmem[],int*com,int*row)/*修改字段的函数*/1102020年4月19日
115文档仅供参考{charlink[110],value[110],zd[110],lx[110];intzdlen=0,lxlen=0,vlen,start=-1,end=-1,i,flag1=0,linklen,jilu=-1,dingwei=-1,gailen;scanf("%s",link);/*存放for字符串*/scanf("%s",value);/*存放for后面的字符串*/vlen=strlen(value);/*测量value数组的长度*/linklen=strlen(link);/*测量link数组的长度*/link[linklen]='';/*将link数组末尾追加一个空格以便匹配"for"*/link[linklen+1]='\0';/*追加空格后link末尾+1打上结束标识*/memset(mem,'\0',sizeof(mem));/*初始化数组*/memset(zd,'\0',sizeof(zd));/*初始化字段数组*/memset(lx,'\0',sizeof(lx));/*初始化要匹配的内容数组*/for(i=0;i116文档仅供参考"匹配成功则说明命令语法有错误*/{printf("您输入的命令有语法错误！
117");gotoloop;/*跳到loop指向的位置，也就是函数末尾*/}for(i=0;i118文档仅供参考printf("您输入的命令语法有错误！
119");gotoloop;/*跳到loop指定的位置，也就是函数末尾*/}for(i=start+1;i120");gotoloop;/*跳到loop指向的位置，也就是函数末尾*/}for(i=0;i<*row;i++)/*在匹配成功的字段中查找满足条件的内容的行的位置*/{1102020年4月19日
121文档仅供参考if(strcmp(wj[i][jilu].data,lx)==0)/*如果找到则dingwei等于该行所在的位置*/{dingwei=i;break;}}if(dingwei==-1)/*如果dingwei等于-1说明没有找到满足条件的行*/{printf("数据库中没有符合该条件的字段！
122");gotoloop;/*跳到loop指定的位置，也就是函数末尾*/}for(i=1;i<*com;i++)/*找到该行后对该行的每个字段进行修改*/{printf("请输入%s的值：
123",wj[0][i].data);printf("%s->",wj[dingwei][i].data);scanf("%s",wj[dingwei][i].data);gailen=strlen(wj[dingwei][i].data);wj[dingwei][i].data[gailen]='\0';}printf("字段修改成功！
124");loop:;1102020年4月19日
125文档仅供参考}/*（10）按字段排序函数模块相同的方法，取得需要排序的字段的字段名，然后判断字段名之后的那个字符是否为@、a、A、d、D的其中一个（a表示升序，d表示降序，不区分大小写，默认排序为升序），若不是，提示命令错误；若是，调用Px_()函数按冒泡排序思想进行排序操作。*/voidPx(charziduan[],charch,int*com,int*row)/*排序函数*/{inti,j,k,reg=-1;chartemp[20];memset(temp,'\0',sizeof(temp));for(i=0;i<*com;i++)/*查找满足条件的字段*/if(strcmp(wj[0][i].data,ziduan)==0)reg=i;if(reg==-1)/*如果该字段在数据库中不存在则reg=-1*/printf("数据库中没有该字段!
126");if(reg!=-1)/*否则进行排序*/{if(ch=='d'||ch=='D')/*如果ch='d'或者'D'则为降序排列*/{for(i=1;i<*row;i++)/*利用气泡降序排序*/{1102020年4月19日
127文档仅供参考for(j=i+1;j<*row;j++){if(strcmp(wj[i][reg].data,wj[j][reg].data)<0||(strlen(wj[i][reg].data)128文档仅供参考{if(strcmp(wj[i][reg].data,wj[j][reg].data)>0||(strlen(wj[i][reg].data)>strlen(wj[j][reg].data))){for(k=0;k<*com;k++){strcpy(temp,wj[i][k].data);strcpy(wj[i][k].data,wj[j][k].data);strcpy(wj[j][k].data,temp);memset(temp,'\0',sizeof(temp));}}}}}}}voidSort(int*com,int*row){charsecond[110],value[110],ziduan[110],ch='@';intlenv,i,lenzd=0,com1=*com,row1=*row;1102020年4月19日
129文档仅供参考memset(second,'\0',sizeof(second));/*初始化数组*/memset(value,'\0',sizeof(value));/*初始化数组*/memset(ziduan,'\0',sizeof(ziduan));/*初始化数组*/scanf("%s",second);/*接收"on"*/scanf("%s",value);/*接收"on"后面的字符*/if(strcmp(second,"on")!=0)/*如果second不等于"on"则说明语法错误*/{printf("语法错误!
130");gotoloop;/*跳到loop指定的位置也就是函数末尾*/}lenv=strlen(value);/*测量value数组的长度*/for(i=0;i131文档仅供参考if(value[i]==92)/*如果输入的字符存在'\'则说明命令中有非法字符*/{printf("您输入的语法中含有非法字符'\\'
132");gotoloop;/*跳到函数末尾*/}}if(ch=='@')/*如果ch没有接受到字符则默认为升序排列*/ziduan[lenzd]='\0';elseziduan[lenzd-1]='\0';if(ch=='a'||ch=='@'||ch=='d'||ch=='D'||ch=='A')/*调用PxDbm函数进行排序*/Px(ziduan,ch,&com1,&row1);elseprintf("语法错误!
133");loop:;}/*（11）关闭数据库函数模块用fopen以读写的方式打开指定文件，若文件不存在，则创立文件。之后用嵌套for循环fprintf将数据库中的数据以字符串写入文件。最后关闭文件，并将各变量格式化。*/voidClose(charsecondinput[],int*com,int*row,charmem[],char1102020年4月19日
134文档仅供参考bian[])/*关闭函数*/{FILE*fp;inti,j;fp=fopen(secondinput,"w+");/*以读写的方式打开指定的文件*/for(i=0;i<*row-1;i++)/*向指定的数据库文件写内容*/{for(j=0;j<*com;j++)fprintf(fp,"%s",wj[i][j].data);fputc('
135',fp);}for(i=0;i<*com;i++)fprintf(fp,"%s",wj[*row-1][i].data);fclose(fp);memset(wj,'\0',sizeof(wj));/*向数据库文件写完内容后对以下数组进行初始化*/memset(mem,'\0',sizeof(mem));memset(bian,'\0',sizeof(bian));*row=0;/*wj数组的行与列进行初始化*/1102020年4月19日
136文档仅供参考*com=0;}/*（12）主函数模块首先声明一些必要的变量，调用帮助菜单，然后做一个while循环程序，直至用户输入完全结束，循环体内经过依次匹配字符串判定用户输入的命令，并调用相应函数模块进行操作。其中比较复杂的是创立数据库。若用户命令为creat创立数据库，首先读入数据库名，然后创立数据库并将内存地址赋给handle，再调用创立数据库函数Create_Struct()在内存中创立数据库，之后循环将内存中的数据写入指定文件。最后调用Open_()函数，打开该数据库，方便进行下一步操作。*/intmain(){Linklist*database[1100];/*创立库结构*/charinput[1100],mingling[1100];/*存放命令字符串*/inti,l=0,l1=0,num=0,handle,length=1,fangwen=0;intgo;/*当执行go命令时候存储当前所指向的记录*/charerror[110];/*接收错误命令后面的命令字符串*/charmem[110];/*分别存储文件的每一行，在复制给wj数组*/introw=0;/*wj数组的行数，也就是数据库中的记录数目*/intlie=0;intcom=0;/*记录wj的列数*/1102020年4月19日
137文档仅供参考intbianlen,fanlen=0;charbian[100];/*自动生成的编号转换为相对应的字符串*/charfabian[100];/*反向存储bian数组*/FILE*fp;charsecondinput[1100];Help();printf("请输入命令：");while(scanf("%s",input)!=EOF)/*连续输入，一直输入到文件尾结束*/{if(strcmp(input,"creat")==0)/*如果输入命令为"creat"则创立数据库文件*/{scanf("%s",secondinput);/*输入数据库的名称*/handle=creat(secondinput,S_IREAD|S_IWRITE);/*创立数据库文件*/CreateStruct(database,&length);/*调用CreateStruct函数向数据库添加字段*/for(i=0;idata,strlen(database[i]->data));printf("
138");gotoloop5;/*跳转到loop5位置*/1102020年4月19日
139文档仅供参考}elseif(strcmp(input,"quit")==0)/*退出系统*/{printf("谢谢使用！
140");break;}elseif(strcmp(input,"help")==0)/*调用help函数显示帮助文档*/{Help();}elseif(strcmp(input,"use")==0)/*打开数据库命令*/{scanf("%s",secondinput);if((fp=fopen(secondinput,"r"))==NULL)/*判断数据库在本地磁盘是否存在*/{printf("数据库不存在！
141");printf("请再次输入命令：");continue;}else/*如果存在则打开该数据库*/{1102020年4月19日
142文档仅供参考loop5:printf("数据库已成功打开!
143");Open(secondinput,&com,&row,bian,fabian);}printf("请输入命令：");scanf("%s",mingling);/*数据库打开成功后输入操作数据库的命令*/while(1){if(strcmp(mingling,"/use")==0)/*关闭数据库*/{Close(secondinput,&com,&row,mem,bian);printf("数据库成功关闭！");break;}elseif(strcmp(mingling,"append")==0)/*向数据库追加内容*/append(bian,fanlen,fabian,bianlen,&com,&row);elseif(strcmp(mingling,"brows")==0)/*浏览数据库*/Display(mem,&com,&row);elseif(strcmp(mingling,"go")==0)/*执行go命令定位指定的行数*/scanf("%d",&go);1102020年4月19日
144文档仅供参考elseif(strcmp(mingling,"disp")==0||strcmp(mingling,"DISP")==0)/*浏览go命令所定位的行*/DispGo(go,&com,&row);elseif(strcmp(mingling,"delete")==0||strcmp(mingling,"DELETE")==0)Delete(mem,&com,&row);/*按条件删除数据库所匹配的行*/elseif(strcmp(mingling,"zap")==0||strcmp(mingling,"ZAP")==0){/*将数据库的内容全部删除，只保留库结构*/row=1;printf("表中记录已经全部删除!
145");}elseif(strcmp(mingling,"locate")==0||strcmp(mingling,"LOCATE")==0)Locate(mem,&com,&row);/*按条件查找数据库所匹配的行*/elseif(strcmp(mingling,"change")==0||strcmp(mingling,"CHANGE")==0)Change(mem,&com,&row);/*修改符合条件的一行*/elseif(strcmp(mingling,"sort")==0)/*按条件对数据库的内容进行排序*/1102020年4月19日
146文档仅供参考Sort(&com,&row);elseif(strcmp(mingling,"help")==0)/*打开帮助文档*/Help();elseif(strcmp(input,"quit")==0)/*退出系统*/{printf("谢谢使用！
147");break;}elseprintf("您输入的命令符错误！请重新输入
148");printf("请输入命令：");scanf("%s",mingling);}}else{scanf("%s",error);/*接收错误命令后面的字符串*/printf("您输入的命令符错误！请重新输入");}printf("
149");}1102020年4月19日
150文档仅供参考return0;}第二题//大整数的加减乘除#include"consts.h"#defineMAXNUM200//题目要求最大位数为200#defineMAXLENMAXNUM//设置数组的容纳量typedefcharDataType;intCompare(constDataType*a,constDataType*b){intlena=strlen(a);intlenb=strlen(b);if(lena!=lenb)returnlena>lenb?1:-1;elsereturnstrcmp(a,b);}//判断两个数是否相等，为后来的计算方便voidAdditionInt(DataType*augend,DataType*addend,DataType*sum){1102020年4月19日
151文档仅供参考intcaug[MAXLEN]={0};//用来存储被加数的整型数组intcadd[MAXLEN]={0};//用来存储加数的整型数组intcsum[MAXLEN]={0};//用来存储两数之和的整型数组intcarry=0;//进位ints=0;//两数之和intlenaug=strlen(augend),lenadd=strlen(addend);//被加数和加数字符串的长度intlenmin=lenaug152文档仅供参考{s=caug[i]+carry;csum[i]=s%10;carry=s/10;i++;}while(i0)//处理最后一个进位csum[i++]=carry;for(j=0;j153文档仅供参考intlen,lenm,lenS,lenmin,i,j,k;intflag;//记录结果是整数还是负数intcm[MAXLEN]={0};//用来存储被减数的整型数组intcs[MAXLEN]={0};//用来存储减数的整型数组intcd[MAXLEN]={0};//用来存储两数之差的整型数组if(strcmp(minuend,subtrahend)==0)//如果两数相等,返回"0"{strcpy(difference,"0");return;}lenm=strlen(minuend),lenS=strlen(subtrahend);//被减数和减数字符串的长度lenmin=lenm0)//逆序复制减数和被减数到整型数组（因为减法运算是从低位开始）,保证cm大于cs{flag=0;//被减数大于减数,结果为正数for(i=0;i154文档仅供参考}else{flag=1;//被减数小于减数,结果为负数,此时要用subtrahend-minuendfor(i=0;i=cs[i])//被减数大于减数,直接相减cd[i]=cm[i]-cs[i];else//否则要向前借位{cd[i]=cm[i]+10-cs[i];--cm[i+1];}}len=lenm>lenS?lenm:lenS;while(i155文档仅供参考{if(cm[i]>=0)cd[i]=cm[i];else{cd[i]=cm[i]+10;--cm[i+1];}i++;}while(cd[i-1]==0)i--;j=0;if(flag==1)//如果被减数小于减数,返回一个负数difference[j++]='-';//为了和文字之间保持一个空格的距离for(k=i-1;k>=0;k--,j++)//逆序存储两数之差到字符串sumdifference[j]=cd[k]+'0';difference[j]='\0';}voidMultiplicationInt(DataType*multiplicand,DataType*multiplier,DataType*product){1102020年4月19日
156文档仅供参考intcd[MAXLEN]={0};//用来存储被乘数的整型数组intcr[MAXLEN]={0};//用来存储乘数的整型数组intcp[MAXLEN]={0};//用来存储两数之乘积的整型数组DataTypetcp[MAXLEN]="";//用来存储两数之乘积的整型数组intlenD=strlen(multiplicand),lenR=strlen(multiplier);//被乘数和乘数字符串的长度inti,j,k;intcarry;//进位intmul=0;//两数之乘积for(i=0;i157文档仅供参考//两个乘数之积与进位相加作为当前位乘积cp[j]=mul%10;//存储当前位carry=mul/10;//获取进位}if(carry>0)//获取最后一个进位cp[j++]=carry;while(cp[j-1]==0)//去掉多余的0--j;for(k=0;k158文档仅供参考if(Compare(dividend,divisor)==0)//被除数等于除数{strcpy(quotient,"1");strcpy(remainder,"0");return;}if(strcmp(divisor,"0")==0||Compare(dividend,divisor)<0)//被除数小于除数{strcpy(quotient,"0");strcpy(remainder,dividend);return;}strcpy(remainder,"");//先使product的值为空for(i=0,k=0;dividend[i]!='\0';i++){s=0;buf[0]=dividend[i];strcat(remainder,buf);//接上被除数的一位数,改变当前余数while(Compare(remainder,divisor)>=0)//连减试商{s++;1102020年4月19日
159文档仅供参考SubtrationInt(remainder,divisor,remainder);}quotient[k++]=s+'0';//记录每一位得到的商值if(strcmp(remainder,"0")==0)strcpy(remainder,"");//使product的值为空,去掉多余的0}quotient[k]='\0';for(i=0;quotient[i]=='0';i++)//去掉多余的0;for(j=i;j<=k;j++)quotient[j-i]=quotient[j];}intpanduan(DataType*a,DataType*b)//判断输入的数中有没有小数{inti=0,j=0,lenc=strlen(a),lend=strlen(b);for(i;i160文档仅供参考if(b[j]=='.')break;}if(i!=lenc||j!=lend)//当其中一个数为小数时则不能进行计算return0;elsereturn1;}intmain(intargc,char*argv[]){intpanduanzhi;DataTypea[MAXLEN]={0};DataTypeb[MAXLEN]={0};DataTypec[3*MAXLEN]={0};DataTyped[MAXLEN]={0};printf("请输入第一个数：");gets(a);printf("请输入第二个数：");gets(b);panduanzhi=panduan(a,b);if(panduanzhi==1){1102020年4月19日
161文档仅供参考AdditionInt(a,b,c);printf("两者之和：");puts(c);SubtrationInt(a,b,c);printf("两者之差：");puts(c);MultiplicationInt(a,b,c);printf("两者之积：");puts(c);DivisionInt(a,b,c,d);printf("两者之商：");puts(c);printf("余数：");puts(d);}elseprintf("输入数值有误，不能进行计算！
162");return0;}第三题//哈夫曼编译码1102020年4月19日
163文档仅供参考#include"consts.h"typedefcharDataType;#defineMAXNUM50typedefstruct//哈夫曼树结点的结构{DataTypedata;//数据用字符表示intweight;//权值intparent;//双亲intleft;//左孩子intright;//右孩子}HuffNode;typedefstruct//哈夫曼编码的存储结构{DataTypecd[MAXNUM];//存放编码位串intstart;//编码的起始位置}HuffCode;//建立哈夫曼树intHuffmanCreate(HuffNode*ht){inti,k,n,m1,m2,p1,p2;printf("请输入元素个数：");scanf("%d",&n);1102020年4月19日
164文档仅供参考for(i=1;i<=n;i++)//输入结点值和信息{getchar();//接收回车printf("第%d个元素的=>
165\t结点值：",i);scanf("%c",&ht[i].data);printf("\t权重：");scanf("%d",&ht[i].weight);}for(i=1;i<=2*n-1;i++)//对数组初始化ht[i].parent=ht[i].left=ht[i].right=0;for(i=n+1;i<=2*n-1;i++){m1=m2=32767;//初始化，令m1、m2为整数最大值p1=p2=1;for(k=1;k<=i-1;k++)//从数组ht[1]到ht[i-1]中找出if(ht[k].parent==0)//parent为0而且权值最小的两个结点if(ht[k].weight166文档仅供参考m1=ht[k].weight;//m1存放最小权值p1=k;}elseif(ht[k].weight167");returnn;//返回结点个数}voidEncoding(HuffNodeht[],HuffCodehcd[],intn)//哈夫曼编码{HuffCoded;1102020年4月19日
168文档仅供参考inti,k,f,c;for(i=1;i<=n;i++)//对所有结点循环{d.start=n+1;//起始位置c=i;//从叶结点开始向上f=ht[i].parent;while(f!=0)//直到树根为止{if(ht[f].left==c)d.cd[--d.start]='0';//规定左树为代码0elsed.cd[--d.start]='1';//规定右树为代码1c=f;//c指孩子的位置f=ht[f].parent;//f指双亲的位置}hcd[i]=d;}printf("输出哈夫曼编码：
169");for(i=1;i<=n;i++)//输出哈夫曼编码{printf("%c:",ht[i].data);//先输出结点for(k=hcd[i].start;k<=n;k++)//再输出其对应的编码1102020年4月19日
170文档仅供参考printf("%c",hcd[i].cd[k]);printf("
171");}}voidDecoding(HuffNodeht[],HuffCodehcd[],intn)//哈夫曼译码{intf,m,k;DataTypec,ch[200];//c接收输入电文，ch存储printf("请输入电文(0or1)，以#为结束标志：
172");c=getchar();k=1;while(c!='#')//单个字符循环输入，以'#'结束{ch[k]=c;//将单个字符依次存入ch字符串中c=getchar();k=k+1;//ch数组下标后移}m=k;//标记数组存储末尾位置f=2*n-1;k=1;//k记录电文字符的个数printf("输出哈夫曼译码：
173");while(k174文档仅供参考{while(ht[f].left!=0)//直到左孩子结点为0结束{if(ch[k]=='0')//若接收的字符为0，则存为左孩子f=ht[f].left;if(ch[k]=='1')//若接收的字符为1，则存为右孩子f=ht[f].right;k++;//ch数组下标后移}printf("%c",ht[f].data);f=2*n-1;//每次都从根结点开始查找}printf("
175");}intmain(intargc,char*argv[]){intn,select,flag=FALSE;//flag为0时标记第一次选择功能HuffNodeht[2*MAXNUM];//定义存放哈夫曼树的数组HuffCodehcd[MAXNUM];//定义存放编码的数组while(TRUE){printf("\t请选择您所要实现的功能：（请输入1102020年4月19日
176文档仅供参考1-4数字）
177");printf("\t1---建立哈夫曼树
178");printf("\t2---编码
179");printf("\t3---译码
180");printf("\t4---退出系统
181");scanf("%d",&select);if(select!=1&&select!=4&&flag==0){//提示先建立哈夫曼树或退出printf("请先建立哈夫曼树再选择其它功能！
182");continue;}flag=TRUE;switch(select)//选择功能{case1:n=HuffmanCreate(ht);break;case2:Encoding(ht,hcd,n);break;case3:Decoding(ht,hcd,n);1102020年4月19日
183文档仅供参考break;case4:exit(0);}}return0;}第四题//顶点对最短路径迪杰斯特拉算法#include"consts.h"#defineMAXVEX30#defineMAXNAME20typedefcharVexType[MAXNAME];typedefintAdjType;typedefstruct{intn;//图的顶点个数VexTypevexs[MAXVEX];//顶点信息AdjTypearcs[MAXVEX][MAXVEX];//边信息}GraphMatrix;1102020年4月19日
184文档仅供参考typedefstruct//保存最短路径的结构体{AdjTypelen;//最短路径长度intpre;//前一顶点}Path;intLocateVex(GraphMatrix*g,VexTypeu)//在图g中查找顶点u的编号{inti;for(i=0;in;++i)if(strcmp(u,g->vexs[i])==0)returni;returnERROR;}voidInit(GraphMatrix*g)//初始化有向网,读入校园地图文件{inti,j,k,w;intedgeNums;//网中边的条数VexTypeva,vb;//定位边的两个顶点FILE*graphlist;graphlist=fopen("campusnav.txt","r");//打开数据文件,并以1102020年4月19日
185文档仅供参考graphlist表示（就是将文件复制过去）fscanf(graphlist,"%d",&g->n);//读入网的顶点个数（该句的意思是从graphlist中读取一个整数存入变量中）fscanf碰到空格就停止fscanf(graphlist,"%d",&edgeNums);for(i=0;in;++i)//构造顶点向量fscanf(graphlist,"%s",g->vexs[i]);for(i=0;in;++i)//初始化邻接矩阵for(j=0;jn;++j)g->arcs[i][j]=INT_MAX;//有权值的网，无路径则置路径为无穷for(k=0;karcs[i][j]=w;//有向网else{printf("%s<->%s读取错误,请您仔细检查!!",va,vb);exit(0);1102020年4月19日
186文档仅供参考}}for(i=0;in;i++)//顶点到自身的权值为0g->arcs[i][i]=0;fclose(graphlist);//关闭数据文件}voidDijkstra(GraphMatrix*pgraph,Pathdist[],intstart){inti,j,min;AdjTypeminw;dist[start].len=0;dist[start].pre=0;pgraph->arcs[start][start]=1;//表示顶点start在集合U中for(i=0;in;i++)//初始化集合V-U中顶点的距离值{dist[i].len=pgraph->arcs[start][i];//初始距离为给定起始点到各顶点的边的权值if(dist[i].len!=INT_MAX)//若边存在则顶点i的前趋顶点为start,否则不存在置为-1dist[i].pre=start;else1102020年4月19日
187文档仅供参考dist[i].pre=-1;}dist[start].pre=-1;//出发点的前趋置为-1for(i=0;in;i++){minw=INT_MAX;min=start;for(j=0;jn;j++)if((pgraph->arcs[j][j]==0)&&(dist[j].lenarcs[min][min]=1;//集合V-U中路径最小的顶点为min,置访问标志for(j=0;jn;j++)//调整集合V-U中的顶点的最短路径{if(pgraph->arcs[j][j]==1)//1102020年4月19日
188文档仅供参考该顶点已经并入,不用再考虑continue;if(dist[j].len>dist[min].len+pgraph->arcs[min][j]&&dist[min].len+pgraph->arcs[min][j]>0){dist[j].len=dist[min].len+pgraph->arcs[min][j];dist[j].pre=min;}}}}intmain(intargc,char*argv[]){GraphMatrixgraph;Pathpath[MAXVEX];inttmp,cnt=0,pre=-1;inttemppath[MAXVEX];intm,n;VexTypeva,vb;//待查询的两个地点longtotallen=0;//总路径长度longcurlen=0;//当前路径长度Init(&graph);1102020年4月19日
189文档仅供参考printf("
190请输入您要查询的起点:
191");scanf("%s",va);printf("
192请输入您要查询的终点:
193");scanf("%s",vb);m=LocateVex(&graph,va);//查找图中的两个顶点n=LocateVex(&graph,vb);if(m!=ERROR&&n!=ERROR)//两个顶点都在图中，则找出二者间最短路径输出{Dijkstra(&graph,path,m);//因为求得的路径上顶点是从终点推到起点,现在将之逆置for(tmp=0;tmp194文档仅供参考if(cnt<=0)//没有路径if(m!=n)printf("%s->%s无路可走
195!",graph.vexs[m],graph.vexs[n]);elseprintf("您输入的顶点重合!
196");else{tmp=cnt;printf("%s->",graph.vexs[temppath[tmp]]);for(;tmp>0;tmp--){printf("%s(%d)->",graph.vexs[temppath[tmp-1]],graph.arcs[temppath[tmp]][temppath[tmp-1]]);totallen+=graph.arcs[temppath[tmp]][temppath[tmp-1]];}printf("共:%d
197",totallen);}}else1102020年4月19日
198文档仅供参考printf("(%s<->%s)中有不存在的地点,请您仔细检查!!",va,vb);return0;}1102020年4月19日
