文章编辑的实习报告

文章编辑的实习报告题目：输入一页文字，程序可以统计出文字、数字、空格的个数。一需求分析：1本程序要求输入一页文章，每行做多不超过80个字符，共N行，分别统计出其中英文字母数和空格数及整篇文章总字数；2统计某一字符串在文章中出现的次数，并输出该次数；删除某一子串，并将后面的字符前移；3输入结束时以Ctrl+E结束；4在统计时均采用的是链表的形式统计，删除指定的字符串等其它操作5测试数据见后二、概要设计1抽象数据结构类型的定义如下：ADTAWord{数据对象：D={ai|ai∈字幕字符集,i=1,2,…，n，n≥0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2,…，n}基本操作P：NewWord(&W,characters)初始条件：characters为字符序列。操作结果：生成一个其值为给定字符序列的单词。DestroyWord(&W,characters)初始条件：单词W已存在。操作结果：销毁单词W的结构，并释放相应空间。WordCmp(W1，W2)初始条件：单词W1，W2已存在。操作结果：若W1<W2，则返回-1;若W1=W2，则返回0；若W1>W2，则返回1。PrintWord(W)初始条件：单词W已存在。操作结果：在计算机终端上显示单词W。}ADTAWordADTTextString{数据对象：D={ai|ai∈字符集,i=1,2,…，n，n≥0}数据关系R：D中字符被“换行符”分割成若干行，每一行的字符间满足下列关系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2,…，n}基本操作：Initation(&f)初始条件：文件f已存在。操作结果：打开文件f，设定文件指针指向文件中第一行第一个字符。GetAWord(f，&W)初始条件：文件f已打开。操作结果：从文件指针所指字符起提取一个单词w。ExtractWords(f,&L)初始条件：文件f已打开，文件指针指向文件中第一行第一个字符。操作结果：提取该行中所有单词，并构成单词的有序表L；本操作结束时，文件指针指向f中下一行的第一个字符。Match(f,pat,&Result)初始条件：文件f已打开，文件指针指向文件中第一个字符;pat为包含所有待查询单词的有序表。操作结果：Result为查询结果。}ADTTextString2主程序：voidmain(){}3其它的函数：主要函数：统计str在文章中出现的次数：intFindString(LINE*&head,char*str){}统计字母数intCountLetter(LINE*&head){do{}while}统计数字数intCountNumber(LINE*&head){do{}while}其它的函数模板与这以上时一样的三详细分析:1创建一链表，同时向里面输入文本数据typedefstructline{ char*data; structline*next;}LINE;2统计str在文章中出现的次数intFindString(LINE*&head,char*str)统计str在文章中出现的次数{ LINE*p=head; intcount=0; inth=0; intlen1=0;//保存当前行的总字符数 intlen2=strlen(str);//待统计字符串的长度 inti,j,k; do { len1=strlen(p->data);//当前行的字符数 for(i=0;i<len1;i++)//字符匹配 { if(p->data[i]==str[0]) { k=0; for(j=0;j<len2;j++) if(p->data[i+j]==str[j]) k++; if(k==len2) { count++; i=i+k-1; } } } } while((p=p->next)!=NULL);//遍历链表 returncount;}实现思想：1）从字符串s中寻找str第一次出现的位置*p=strstr(s,str)2)len=strlen(s);i=len-strlen9p即前i项恰好不含要删除的字符串，将前i项复制到tmp中3）j=i+strlen(str)即要删除的字符串在i+1和j之间，将j之后的字符串复制到tmp中4）将tmp赋给串s，返回s2向创建的链表中输入数据：voidCreate(LINE*&head){ printf("请输入一页文章，以Ctrl+E(^E)为结尾（每行最多输入80个字符！）:\n"); LINE*p=newLINE;//首先为链表建立一个附加表头结点 head=p; chartmp[100]; while(1) { gets(tmp);//输入字符串 if(strlen(tmp)>80) { printf("每行最多输入80个字符"); break; } if(tmp[0]==5) break;//如果发现输入^E,则退出输入 p=p->next=newLINE; p->data=newchar[strlen(tmp)+1];//为结点分配空间 strcpy(p->data,tmp); if(tmp[strlen(tmp)-1]==5) { p->data[strlen(tmp)-1]='\0'; break; } } p->next=NULL;//最后的一个指针为空 head=head->next;}3统计文章的总字数intCountAll(LINE*&head){ LINE*p=head;//保存链表的首地址 intcount=0; do//计算总字符数 { count+=strlen(p->data); }while((p=p->next)!=NULL);//遍历链表 returncount;}4删除指定的字符串voidDelstringword(char*s,char*str)//*s为输入的字符串，*str为将要删除的字符{ char*p=strstr(s,str);//从字符串s中寻找str第一次出现的位置 chartmp[80]; intlen=strlen(s); inti=len-strlen(p); intj=i+strlen(str); intcount=0; for(intm=0;m<i;m++) tmp[count++]=s[m]; for(intn=j;n<len;n++) tmp[count++]=s[n]; tmp[count]='\0'; strcpy(s,tmp);//返回新的字符串}四调试分析：1再输入文章时，计算机怎样识别文章是否结束？输出文章时，怎样处理表示结束的字符？通过调试，找到了解决方案：输入文章时，以Ctrl+E(^E)为结尾，当tep[0]==5时，发现输如^E则退出输入。输出文章时，如果tmp[strlen[(tmp)-1]==5即发现表示结束的字符^E,用p->data[strlen(tmp)-1]=\0除去最后一个控制符^E2算法改进：本程序的文章用户输入文章，只能做即时输入统计，编译，而不能对已有的磁盘文件中的文章进行统计，编译，如果引进文件流类，就可以打开磁盘文件。对其进行统计，编译并保存，还是有待提高改进的。五测试结果：1输入数据的测试：2删除某一字符串的数据：六附录：#include<iostream.h>#include<string.h>#include<stdio.h>//文本每行以字符串形式存储，行与行之间以链表存储#include<iomanip.h>typedefstructline{ char*data;structline*next;}LINE;//创建一链表，同时向里面输入文本数据voidCreate(LINE*&head){printf("请输入一页文章，以Ctrl+E(^E)为结尾(每行最多输入80字符!):\n");LINE*p=newLINE;//首先为链表建立一个附加表头结点head=p;//将p付给表头指针chartmp[100];while(1){gets(tmp);//输入字符串！ if(strlen(tmp)>80) { printf("每行最多输入80字符"); break; } if(tmp[0]==5)break;//如果发现输入^E，则退出输入p=p->next=newLINE;p->data=newchar[strlen(tmp)+1];//为结点分配空间strcpy(p->data,tmp); if(tmp[strlen(tmp)-1]==5)//除去最后一个控制符^E {p->data[strlen(tmp)-1]='\0';break;}}p->next=NULL;//最后的一个指针为空head=head->next;}//统计字母数intCountLetter(LINE*&head){ LINE*p=head; intcount=0; do{intLen=strlen(p->data);//计算当前data里的数据元素的个数for(inti=0;i<Len;i++)if((p->data[i]>='a'&&p->data[i]<='z')||(p->data[i]>='A'&&p->data[i]<='Z'))/*计算字母数*/ count++;}while((p=p->next)!=NULL);//遍历链表 returncount;//返回文章的字母总数}//统计数字数intCountNumber(LINE*&head){LINE*p=head;intcount=0;do{intLen=strlen(p->data);//计算当前data里的数据元素的个数for(inti=0;i<Len;i++)if(p->data[i]>=48&&p->data[i]<=57)count++;//计算数字数，ASCII码}while((p=p->next)!=NULL);//遍历链表returncount;}//统计空格数intCountSpace(LINE*&head){LINE*p=head;intcount=0;do{intLen=strlen(p->data);//计算当前data里的数据元素的个数for(inti=0;i<Len;i++)if(p->data[i]==32)count++;//计算空格数，空格ASCII码为32}while((p=p->next)!=NULL);//遍历链表returncount;}//统计文章的总字数intCountAll(LINE*&head){LINE*p=head;//保存链表的首地址intcount=0;do//计算总字符数{ count+=strlen(p->data); }while((p=p->next)!=NULL);//遍历链表returncount;}//统计str在文章中出现的次数intFindString(LINE*&head,char*str){LINE*p=head;intcount=0;inth=0;intlen1=0;//保存当前行的总字符数intlen2=strlen(str);//待统计字符串的长度inti,j,k;do{ len1=strlen(p->data);//当前行的字符数 for(i=0;i<len1;i++)//字符匹配 { if(p->data[i]==str[0]) { k=0;for(j=0;j<len2;j++)if(p->data[i+j]==str[j])k++; if(k==len2) {count++;i=i+k-1;}} }}while((p=p->next)!=NULL);//遍历链表returncount;}voiddelstringword(char*s,char*str)//删除指定的字符串//s为输入的字符串，*str为将要删除的字符{//while(1){ //if(strstr(s,str)){ char*p=strstr(s,str);/*从字符串s中寻找str第一次出现的位置*/chartmp[80];intlen=strlen(s);inti=len-strlen(p);intj=i+strlen(str);intcount=0; for(intm=0;m<i;m++)tmp[count++]=s[m];for(intn=j;n<len;n++)tmp[count++]=s[n];tmp[count]='\0'; strcpy(s,tmp); // break; //}/*返回新的字符串*/ //else // cout<<"未找到记录，请重新输入要删除的字符:"<<endl;//}}voidDelString(LINE*&head,char*str){LINE*p=head;do{if(strstr(p->data,str)!=NULL)delstringword(p->data,str); } while((p=p->next)!=NULL);//遍历链表}//向屏幕输出文章voidOutPut(LINE*&head){LINE*p=head;do {printf("%s\n",p->data);} while((p=p->next)!=NULL);//遍历链表}voidmain(){chark;inti;LINE*head;Create(head);printf("输入的文章为:\n");OutPut(head);printf("\n");printf("全部字母数：%d\n",CountLetter(head));printf("数字个数：%d\n",CountNumber(head));printf("空格个数:%d\n",CountSpace(head));printf("文章总字数:%d\n",CountAll(head));charstr1[20],str2[20];printf("\n");while(1){printf("1.统计某一字符串在文章所出现的次数\n");printf("2.删除文章中的某一字符串\n");printf("3.退出系统\n");printf("请选择所要操作的选项:\n");scanf("%d",&i); if(i==1){while(1){printf("请输入要统计的字符串:");scanf("%s",str1);printf("%s出现的次数为:%d\n",str1,FindString(head,str1));printf("\n");cout<<"请选择操作方式:"<<endl;cout<<"继续统计请选1，退出请选0.\n"<<endl;scanf("%s",&k);if(k=='0')break; } }elseif(i==2){while(1){printf("请输入要删除的某一字符串：");scanf("%s",str2);DelString(head,str2);printf("删除%s后的文章为:\n",str2);OutPut(head);cout<<"请选择操作方式:"<<endl;cout<<"继续删除请选1，退出请选0.\n"<<endl;scanf("%s",&k);if(k=='0')break; } } elsebreak;}}七设计体会心得：此次课设使我对数据结构方面的知识有了更深层的了解，也使我认识到自己在学习编程方面有很多的不足。今后我要多读一些编程方面的书籍，不能只拘泥于课本上的知识，并注重理论与实践的结合，多上机练习编写程序，提高自己的实际动手能力和独立思考的能力，不断充实自己，更好的掌握编程思想。线索二叉树的实习报告题目：建立中序二叉树，并且中序遍历，求中序线索二叉树上已知结点中序的前驱和后继。一需求分析1先建立二叉树，然后开始线索二叉树，中序遍历2在中序线索二叉树上寻找指定结点的前驱结点和后继结点3在建立二叉树时，要自己先组建一课二叉树，根据它进行输入；4输出结点信息后，再输入一结点信息，查找它的前驱和后继5输入过程中一定要正确输入6测试数据：输入一个数值再分别输入建立的左右子数输出结点信息二概要分析1抽象数据类型树的定义如下：ADTBinaryTree{数据对象D：D是具有相同特性的数据元素的集合数据关系R：若D=Φ，则R=Φ，称BinayTree为空二叉树；若D≠Φ，则R={H}，H是如下二元关系：在D中存在唯一的称为根的数据元素root，它在关系H喜爱无前驱；若D-{root}≠Φ,则存在D-{root}={D1，Dr}，且D1∩Dr=Φ;若D1≠Φ,则D1中存在惟一的元素X1,<root,X1>∈H,且存在D1上的关系H1∈H;若Dr≠Φ,则Dr中存在惟一的元素Xr,<root,Xr>∈H,且存在Dr上的关系Hr属于H,H={<root,Xr>,,<root,Xr>,H1,Hr};(D1，{H1})是一颗符合本定义的二叉树，称为根的左子树，(D1，{H1})是一棵符合本定义的二叉树，称为根的右子树。基本操作：InitBiTree(&T);操作结果：构造空二叉树。CreateBiTree(&T,definittion);初始条件：definittion给出的二叉树T的定义。操作结果：按definittion构造二叉树T。BiTreeEmpty(T);初始条件：二叉树T存在操作结果：若T为空二叉树，则返回TRUE，否则FALSE。Value(T,e);初始条件：二叉树T存在操作结果：返回E的值。Assign(T,&e,value);初始条件；二叉树T存在，e是T中的某个结点。操作结果：结点e赋值为value.Leftchild(T,e);初始条件；二叉树T存在，e是T中的某个结点。操作结果;返回e的左孩子。若e无右孩子，则返回“空”。Rightchild(T,e);初始条件；二叉树T存在，e是T中的某个结点。操作结果;返回e的右孩子。若e无右孩子，则返回“空”。LeftSibling(T,e);初始条件；二叉树T存在，e是T中的某个结点。操作结果;返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。Rightsibling(T,e);初始条件；二叉树T存在，e是T中的某个结点。操作结果;返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。PreDrderTraverse(T,Visit());初始条件；二叉树T存在,Visit是对应结点操作的应用函数。操作结果：先遍历T，对每个结点调用函数Visit一次且一次，一旦visit（）失败，则操作失败。InOrderTraverse(T,Visit());初始条件；二叉树T存在,Visit是对应结点操作的应用函数。操作结果：中序遍历T，对每个结点调用函数Visit一次且一次，一旦visit（）失败，则操作失败。PostOrderTraverse(T,Visit());初始条件；二叉树T存在,Visit是对应结点操作的应用函数。操作结果：后序遍历T，对每个结点调用函数Visit一次且一次，一旦visit（）失败，则操作失败。LeveOrderTraverse(T,Visit());初始条件；二叉树T存在,Visit是对应结点操作的应用函数。操作结果：层序遍历T，对每个结点调用函数Visit一次且一次，一旦visit（）失败，则操作失败。}ADTBinaryTree2主程序voidmain(){ThreadTreet,p;charch[20],x[20];intflag=1;while(flag){printf("\n请选择需要进行的操作:\n");printf("\n1：创建二叉树\n");printf("\n2：线索二叉树\n");printf("\n3：中序线索二叉树\n");printf("\n4：寻找结点p的中序前驱结点\n");printf("\n5：寻找结点p的中序后继结点\n");printf("\n6：查找值为X的结点\n");printf("\n0：退出！\n\n");scanf("%d",&flag);switch(flag){case1:printf("\n开始创建二叉树\n");printf("\n请输入一个数值:");scanf("%s",ch);t=CreatThreadTree(ch);printf("\n\n\n\n\n");break;case2:printf("\n开始线索二叉树！\n");InThread(t);break;case3:printf("\n中序线索二叉树！\n");InOrderTh(t);break;case4://在中序线索二叉树上寻找结点p的中序前驱结点的算法：printf("\n输入P节点信息，以方便查找\n");scanf("%s",x);printf("\n寻找结点p的中序前驱结点!\n");p=Search(t,x);InPreNode(p);break;case5://在中序线索二叉树上寻找结点p的中序后继结点的算法:printf("\n输入P节点信息，以方便查找!\n");scanf("%s",x);printf("\n结点p的中序后继结点信息！\n");printf("\n寻找结点p的中序后继结点!\n");p=Search(t,x);p=InPostNode(p);visite(p->date);break;case6://在中序线索二叉树上查找值为X的结点printf("\n请输入查找的数值！\n");scanf("%s",x);p=Search(t,x);if(p)printf("\n查找成功！\n\n");elseprintf("\n查找失败！\n\n");break;default:break;}三详细设计1二叉树的二叉链表存储表示typedefstructThreadnode{intltag,rtag;chardate[20];structThreadnode*lchild,*rchild;}Threadnode,*ThreadTree;2初始化二叉树typedefstructThreadnode{intltag,rtag;chardate[20];structThreadnode*lchild,*rchild;}Threadnode,*ThreadTree;3在中序线索二叉树上寻找结点p的中序后继结点的算法:ThreadTreeInPostNode(ThreadTreep){ThreadTreepost;post=p->rchild;if(p->rtag==0)while(post->ltag==0)post=post->lchild;return(post);}4在中序线索二叉树上寻找结点p的中序前驱结点的算法：ThreadTreeInPreNode(ThreadTreep){ThreadTreeprel;prel=p->lchild;if(p->ltag==0)while(prel->rtag==0)prel=prel->rchild;printf("\n结点p的中序前驱结点信息！\n");visite(prel->date);return(prel);}//中序线索二叉树的遍历算法voidInOrderTh(ThreadTreet){ThreadTreep;if(t){p=t;while(p->ltag==0)p=p->lchild;while(p){visite(p->date);p=InPostNode(p); }}}四调试分析1对于本实验来讲，首先要创建一课二叉树，并且初始化，在这里用到了中序遍历二叉树的算法，寻找结点前驱后继的算法。2在程序运行期间，建立二叉树时，要把其左右子树输入正确，以免运行会出现错误，通过反复的调试对其存储会有更深的印象五测试结果1创建二叉树二输入左子树右子树的数值三中序线索二叉树结果四输出指定结点的前驱和后继七附录#include"stdio.h"#include"stdlib.h"#include"string.h"typedefstructThreadnode{intltag,rtag;chardate[20];structThreadnode*lchild,*rchild;}Threadnode,*ThreadTree;ThreadTreepre=NULL;voidvisite(char*ch){printf("\n输出节点信息:");printf("%s",ch);}//初始化二叉树ThreadTreeCreatThreadTree(charch[]){ThreadTreet;charch1[20],ch2[20];t=(ThreadTree)malloc(sizeof(Threadnode));strcpy(t->date,ch);printf("\n请输入左子树的数值，结束输入0:\n");scanf("%s",ch1);if(strcmp(ch1,"0")==0){t->ltag=1;t->lchild=NULL;}else{t->ltag=0;t->lchild=CreatThreadTree(ch1);}printf("\n请输入右子树的数值，结束输入0:\n");scanf("%s",ch2);if(strcmp(ch2,"0")==0){t->rtag=1;t->rchild=NULL;}else{t->rtag=0;t->rchild=CreatThreadTree(ch2);}returnt;}//建立中序线索二叉树算法实现voidInThread(ThreadTreet){if(t){InThread(t->lchild);if(t->lchild==NULL){t->ltag=1;t->lchild=pre;}if(t->rchild==NULL)t->rtag=1;if((pre)&&(pre->rtag==1))pre->rchild=t;pre=t;InThread(t->rchild);}}//在中序线索二叉树上寻找结点p的中序后继结点的算法:ThreadTreeInPostNode(ThreadTreep){ThreadTreepost;post=p->rchild;if(p->rtag==0)while(post->ltag==0)post=post->lchild;return(post);}//在中序线索二叉树上查找值为X的结点ThreadTreeSearch(ThreadTreet,charx[]){ThreadTreep;p=t;if(p){while(p->ltag==0)p=p->lchild;while(p&&strcmp(p->date,x)!=0)p=InPostNode(p);}returnp;}//在中序线索二叉树上寻找结点p的中序前驱结点的算法：ThreadTreeInPreNode(ThreadTreep){ThreadTreeprel;prel=p->lchild;if(p->ltag==0)while(prel->rtag==0)prel=prel->rchild;printf("\n结点p的中序前驱结点信息！\n");visite(prel->date);return(prel);}//中序线索二叉树的遍历算法voidInOrderTh(ThreadTreet){ThreadTreep;if(t){p=t;while(p->ltag==0)p=p->lchild;while(p){visite(p->date);p=InPostNode(p); }}}voidmain(){ThreadTreet,p;charch[20],x[20];intflag=1;while(flag){printf("\n请选择需要进行的操作:\n");printf("\n1：创建二叉树\n");printf("\n2：线索二叉树\n");printf("\n3：中序线索二叉树\n");printf("\n4：寻找结点p的中序前驱结点\n");printf("\n5：寻找结点p的中序后继结点\n");printf("\n6：查找值为X的结点\n");printf("\n0：退出！\n\n");scanf("%d",&flag);switch(flag){case1:printf("\n开始创建二叉树\n");printf("\n请输入一个数值:");scanf("%s",ch);t=CreatThreadTree(ch);printf("\n\n\n\n\n");break;case2:printf("\n开始线索二叉树！\n");InThread(t);break;case3:printf("\n中序线索二叉树！\n");InOrderTh(t);break;case4://在中序线索二叉树上寻找结点p的中序前驱结点的算法：printf("\n输入P节点信息，以方便查找\n");scanf("%s",x);printf("\n寻找结点p的中序前驱结点!\n");p=Search(t,x);InPreNode(p);break;case5://在中序线索二叉树上寻找结点p的中序后继结点的算法:printf("\n输入P节点信息，以方便查找!\n");scanf("%s",x);printf("\n结点p的中序后继结点信息！\n")；printf("\n寻找结点p的中序后继结点!\n");p=Search(t,x);p=InPostNode(p);visite(p->date);break;case6://在中序线索二叉树上查找值为X的结点printf("\n请输入查找的数值！\n");scanf("%s",x);p=Search(t,x);if(p)printf("\n查找成功！\n\n");elseprintf("\n查找失败！\n\n");break;default:break;}if(flag!=0)printf("\n****************请选择操作*****************\n");}}八设计体会心得：经过线索而叉树的设计编写，使我对数据结构有了更深的了解，要想学好它重在实践，我也发现我的好多不足之处，首先是自己在指法上还不行，经过按错字母等其它的错误，这次同过学习，对数据结果中较陌生的函数也有了一定的了解还有以前对函数的调用不熟悉，对程序中经常出现的错误也不懂，通过实践，使我在这些方面有了提高。通过实践学习，我认识到学好计算机要注重实践操作，不仅仅是学习数据结构，还有其它的语言，以及其它的计算机要重视实践，多动手。所以在以后的学习过程中，我会更加注视实践操作，使自己更好的学好计算机。校园导游咨询的的实习报告题目：编制一个为来访客人进行最短路径导游的程序一、需求分析1．从中原工学院信息商务学院的平面图中选取19个有代表性的景点，抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地之间的距离。2.本程序的目的是为用户提供路径咨询。根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息。3.测试数据（附后）二、概要设计1.抽象数据类型图的定义如下：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={(v,w)|v,w}∈V,(v,w)表示v和w之间存在路径}基本操作P：GreateGraph（&G,V,VR）初始条件：V是图的顶点集，VR是图中边的集合。操作结果：按V和VR的定义构造图G.GrestroyGraph（&G）初始条件：图G存在。操作结果：销毁图G。LocateVex(G，u)初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。GetVex（G,v）初始条件：图中存在，v是G中某个顶点。操作结果：返回v的信息。FirstEdge（G，v）初始条件：图G存在，v是G中某个顶点。操作结果：返回依附于v的第一条边。若该顶点在G中没有邻接点，则返回“空”。NextEdge（G,v，w）初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果；返回依附于v的（相对于w的）下一条边。若不存在，则返回“空”。InsertVex（&G，v）初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v。DeleteVex（&G,v）初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的边。InsertEdge（&G，v,w）初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添边（v,w）。DeleteEdge（&G，v，w）初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除边（v，w）。GetShortestPath（G,st，nd，&path）初始条件：图G存在，st和nd是G中两个顶点。操作结果：若st和nd之间存在路径，则以path返回两点之间一条最短路径，否则返回其他信息。}ADTGraph2主程序voidmain(){初始化；switch(k)}3本程序包含两个模块：主程序模块；最短路径问题；三详细分析1#defineMax20//图中顶点的最大值#defineInit_Length10000//边的权值，表示路径长度2界面输出函数：voidprint(){printf("*******欢迎您来到中原工学院信息商务学院********\n");printf("**********************************************\n");printf("******************祝您旅途愉快****************\n");printf("以下是您可能要前往的地方\n");printf("1——************男生1号寝室楼************——\n");printf("2——************女生2号寝室楼************——\n");printf("3——************女生3号寝室楼***********——\n");printf("4——************女生4号寝室楼***********——\n");printf("5——************男生5号寝室楼***********——\n");printf("6——************女生6号寝室楼***********——\n");printf("7——************主教楼***********——\n");printf("8——************图书馆***********——\n");printf("9——************1号篮球场***********——\n");printf("10——************2号篮球场***********——\n");printf("11——************食堂***********——\n");printf("12——************运动场***********——\n"); printf("13——************主操场***********——\n");printf("功能1.景点查询请输入i\n");printf("功能2.查询最短路径请输入s\n");printf("功能3.退出系统请输入e\n");printf("请输入您的选择:");}4主函数部分：voidmain(){chark;print();scanf("%c",&k);while((k!='i')&&(k!='e')&&(k!='s')){getchar();printf("ERROR请输入i或s或e\n");scanf("%c",&k);}switch(k){case'i':printf("进入景点查询:\n");introduce();break;case's':printf("进入最短路径查询:\n");shortestdistance();break;case'e':exit(0);}}最短路径：voidshortestdistance(){inti,v,w,v0,j;intmin;inttop[14]={0};intcost[14][14];intpath[14][14];intfinal[14]={0};intD[14];for(i=0;i<14;i++)for(j=0;j<14;j++)cost[i][j]=Init_Length;cost[1][3]=cost[3][1]=10;cost[3][5]=cost[5][3]=40;cost[1][7]=cost[7][1]=10;cost[3][7]=cost[7][3]=30;cost[2][7]=cost[7][2]=20;cost[2][6]=cost[6][2]=10;cost[4][6]=cost[6][4]=10;cost[4][13]=cost[13][4]=10;cost[6][12]=cost[12][6]=20;cost[12][8]=cost[8][12]=10;cost[8][9]=cost[9][8]=10;cost[6][9]=cost[9][6]=15;cost[10][9]=cost[9][10]=10;cost[6][10]=cost[10][6]=20;cost[9][10]=cost[10][9]=10;cost[9][11]=cost[11][9]=10;其它部分再此就不详细介绍了四、设计和调试分析1.原设计在变的属性中加上访问标志域mark，意图以！（p->mark）代替！Inset（w，ss）来判别是否需要检测该条边，后发现，如此只能求出第一对顶点之间的最短路径。在继续求其他对定点的最短路径时，必须恢复所有边的访问标志为FALSE,则需要消耗O(e)的时间，并不比现在的算法优越，故舍去之。2.考虑道路网多是稀疏网，故采用邻接多重表作存储结构，其空间复杂度为O（e），此时的时间复杂度也为O(e)。构建邻接多重表的时间复杂度为O(n+e)，输出路径的时间复杂度为O(n)。由此，本导游程序的时间复杂度为O(n+e)。3.由于导游程序在实际执行时，需要根据用户的临时输入求最短路径。因此，虽然迪杰斯特拉算法的时间复杂度比费洛依德算法低，但每求一条最短路径都必须重新搜索一遍，在频繁查询时会导致查询效率降低，而费洛依德算法只要计算一次，即可求得每一对顶点之间的最短路径，虽然时间复杂度为O（n3）,但以后每次查询都只要查表即可，极大地提高了查询效率，而且费洛依德算法还支持带负权的图的最短路径的计算。由此可见，在选用算法时，不能单纯地只考虑算法的渐近时间复杂度，有时还必须综合考虑各种因素。五测试结果1界面函数的显示：2查询景点：3查询最短路径：七附录#include<stdio.h>#include<math.h>#include<stdlib.h>#defineMax20#defineInit_Length10000voidshortestdistance();voidprint()//voidmain(){printf("*******欢迎您来到中原工学院信息商务学院********\n");printf("**********************************************\n");printf("******************祝您旅途愉快****************\n");printf("以下是您可能要前往的地方\n");printf("1——************男生1号寝室楼************——\n");printf("2——************女生2号寝室楼************——\n");printf("3——************女生3号寝室楼***********——\n");printf("4——************女生4号寝室楼***********——\n");printf("5——************男生5号寝室楼***********——\n");printf("6——************女生6号寝室楼***********——\n");printf("7——************主教楼***********——\n");printf("8——************图书馆***********——\n");printf("9——************1号篮球场***********——\n");printf("10——************2号篮球场***********——\n");printf("11——************食堂***********——\n");printf("12——************运动场***********——\n"); printf("13——************主操场***********——\n");printf("功能1.景点查询请输入i\n");printf("功能2.查询最短路径请输入s\n");printf("功能3.退出系统请输入e\n");printf("请输入您的选择:");}voidintroduce(){inta;printf("请输入景点编号:");scanf("%d",&a);getchar();printf("\n");while(a<1||a>13){printf("ERROR!请输入数字1到13:\n\n");scanf("%d",&a);}switch(a){case1:printf("1:男生1号寝室楼\n\n");break;case2:printf("2:女生2号寝室楼\n\n");break;case3:printf("3:女生3号寝室楼\n\n");break;case4:printf("4:女生4号寝室楼\n\n");break;case5:printf("5:男生5号寝室楼\n\n");break;case6:printf("6:女生6号寝室楼\n\n");break;case7:printf("7:主教楼\n\n");break;case8:printf("8:图书馆\n\n");break;case9:printf("9:1号篮球场\n\n");break;case10:printf("10:2号篮球场\n\n");break;case11:printf("11:食堂\n\n");break;case12:printf("12:运动场\n\n");break;case13:printf("13:主操场\n\n");break;}printf("/n");}voidmain(){chark;print();scanf("%c",&k);while((k!='i')&&(k!='e')&&(k!='s')){getchar();printf("ERROR请输入i或s或e\n");scanf("%c",&k);}switch(k){case'i':printf("进入景点查询:\n");introduce();break;case's':printf("进入最短路径查询:\n");shortestdistance();break;case'e':exit(0);}}voidshortestdistance(){inti,v,w,v0,j;intmin;inttop[14]={0};intcost[14][14];intpath[14][14];intfinal[14]={0};intD[14];for(i=0;i<14;i++)for(j=0;j<14;j++)cost[i][j]=Init_Length;cost[1][3]=cost[3][1]=10;cost[3][5]=cost[5][3]=40;cost[1][7]=cost[7][1]=10;cost[3][7]=cost[7][3]=30;cost[2][7]=cost[7][2]=20;cost[2][6]=cost[6][2]=10;cost[4][6]=cost[6][4]=10;cost[4][13]=cost[13][4]=10;cost[6][12]=cost[12][6]=20;cost[12][8]=cost[8][12]=10;cost[8][9]=cost[9][8]=10;cost[6][9]=cost[9][6]=15;cost[10][9]=cost[9][10]=10;cost[6][10]=cost[10][6]=20;cost[9][10]=cost[10][9]=10;cost[9][11]=cost[11][9]=10;printf("请输入您现在所在的位置:\n");scanf("%d",&v0);while(v0>13||v0<1){printf("ERROR!请重新输入编号从1到13的数\n");scanf("%d",&v0);}for(i=1;i<14;i++)for(j=1;j<14;j++)path[i][j]=0;for(v=1;v<14;v++){D[v]=cost[v0][v];if(D[v]<Init_Length){path[v][(++(top[v]))]=v0;path[v][(++(top[v]))]=v;}}D[v0]=0;final[v0]=1;for(i=2;i<14;++i){min=Init_Length;for(w=1;w<14;++w){if((final[w]==0)&&(D[w]<min)){v=w;min=D[w];}}final[v]=1;for(w=1;w<14;++w){if((final[w]==0)&&(min+cost[v][w]<D[w])){D[w]=min+cost[v][w];for(j=1;j<14;j++)path[w][j]=path[v][j];top[w]=top[v]+1;path[w][(top[w])]=w;}}}printf("请输入你要去的地方:\n");scanf("%d",&w);printf("\n");while(w>13||w<1){printf("ERROR!输入错误,请重新输入编号从1到13\n");scanf("%d",&w);}printf("最短路径为:\n");for(i=1;path[w][i]!=0;i++)printf("-->%d",path[w][i]);printf("\n");printf("最短路径的长度为:%d\n",D[w]);}八设计体会心得：在这次的设计中体会最深的是对最短路径的分析，在这里要求为来访客人提供景点的问路查询，即已知一个景点，查询到某景点之间的一条最短路径及长度。在这里引进一个辅助向量D，它的每个分量都表示当前所找到得从始点v到每个终点Vi的最短路径长度。他的初始态为：若从v到vi有弧，则D[j]为弧上的权值；否则置D[j]为∞，显然长度为：D[j]=Min{D[j]|Vi∈V}的路经就是从V出发的长度最短的一条最短路径。在这里选用邻接矩阵来求最短路径。从这里学到了更多是求最短路径的方法和思想。宿舍管理查询的实习报告题目:为宿舍管理人员编写一个宿舍管理查询软件一需求分析1建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(选择、快速排序、堆排序等任选一种)2可以增加，修改，删除指定信息3查询:a.按姓名查询;b.按学号查询;c按房号查询4演示程序时，根据显示的信息，用户可由键盘输入排序表的表长和不同数据的数组。每次测试完毕，列表显示各种比较指标值。5最后对结果做出简单分析二概要分析可排序表的抽象数据类型定义：ADTOrderableList{数据对象：D={ai|ai∈Integerset，i=1,2,…，n，n>=0}数据关系：R1={<ai-1，ai>|ai-1,ai∈D，i=2，…，n}基本操作：InitList(n)操作结果：构造一个长度为n，元素值依次为1,2，…，n的有序表。RandomizeList(d,isInverseOrder)操作结果：首先根据isInverseOrder为True或False，将表置为逆序或正序，然后将表进行d（0<=d<=8）级随机打乱。d为0时表不打乱，d越大，打乱程度越高。RecallList（）操作结果：恢复最后一次用RandomizeList随机打乱得到的可排序表。ListLength（）操作结果：返回可排序表的长度。ListEmpty（）操作结果：若可排序表为空表，则返回True，否则返回False。BubbleSort（&c，&s）操作结果：进行起泡排序，返回关键字比较次数c和移动次数s。InsertSort（&c，&s）操作结果：进行插入排序，返回关键字比较次数c和移动次数s。SelectSort（&c，&s）操作结果：进行选择排序，返回关键字比较次数c和移动次数s。QuickSort（&c，&s）操作结果：进行快速排序，返回关键字比较次数c和移动次数s。ShellSort（&c，&s）操作结果：进行希尔排序，返回关键字比较次数c和移动次数s。HeapSort（&c，&s）操作结果：进行堆排序，返回关键字比较次数c和移动次数s。ListTraverse（visit（））操作结果：依次对L中的每个元素调用函数visit（）。}ADTOrderableList2本程序包含模板结构如下：1）主程序模板2）针对主程序中的模板写相对应的函数：如增加学生信息：voidAdd(){}查找函数：voidSearching(){}按学号查找：voidNumSearching(){}按地址查找：voidDNumSearching(){}排序函数：voidSort(){}修改函数：voidAmend(){}删除函数：voidDelete(){}三详细设计：1宿舍的结构体定义：structDorm{ stringstudent_name; intdorm_num; intstudent_num;};DormS[100];inta=1,n;2内部的排序voidSort(){ intk,j,t,temp1,temp2,o; stringx;ifstreaminfile("王琳的宿舍管理系统.txt",ios::in); if(!infile) { cerr<<"打开失败"<<endl; exit(1); } for(inti=1;i<=a;i++) { infile>>S[i].student_name>>S[i].student_num>>S[i].dorm_num; } cout<<"请选择排序的类型"<<endl; cout<<"1.按姓名首字母排序"<<endl; cout<<"2.按学生学号排序"<<endl; cout<<"3.按学生宿舍号排序"<<endl; cout<<"4.返回主菜单"<<endl; cout<<"请选择你要执行的操作：\n"; cin>>t; if(t==1) { for(i=1;i<a;i++) { k=i; for(j=i+1;j<a;j++) if(S[j].student_name<S[k].student_name) k=j; if(k!=j) { x=S[i].student_name;S[i].student_name=S[k].student_name;S[k].student_name=x; temp1=S[i].student_num;S[i].student_num=S[k].student_num;S[k].student_num=temp1; temp2=S[i].dorm_num;S[i].dorm_num=S[k].dorm_num;S[k].dorm_num=temp2; } } } else if(t==2) { for(i=1;i<a;i++) { k=i; for(j=i+1;j<a;j++) if(S[j].student_num<S[k].student_num) k=j; if(k!=j) { x=S[i].student_name;S[i].student_name=S[k].student_name;S[k].student_name=x; temp1=S[i].student_num;S[i].student_num=S[k].student_num;S[k].student_num=temp1; temp2=S[i].dorm_num;S[i].dorm_num=S[k].dorm_num;S[k].dorm_num=temp2; } } } elseif(t==3) { for(i=1;i<a;i++) { k=i; for(j=i+1;j<a;j++) if(S[j].dorm_num<S[k].dorm_num) k=j; if(k!=j) { x=S[i].student_name;S[i].student_name=S[k].student_name;S[k].student_name=x; temp1=S[i].student_num;S[i].student_num=S[k].student_num;S[k].student_num=temp1; temp2=S[i].dorm