文章編輯的實習(xí)報告

文章編輯的實習(xí)報告題目：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。一需求分析：1本程序要求輸入一頁文章，每行做多不超過80個字符，共N行，分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；2統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；刪除某一子串，并將后面的字符前移；3輸入結(jié)束時以Ctrl+E結(jié)束；4在統(tǒng)計時均采用的是鏈表的形式統(tǒng)計，刪除指定的字符串等其它操作5測試數(shù)據(jù)見后二、概要設(shè)計1抽象數(shù)據(jù)結(jié)構(gòu)類型的定義如下：ADTAWord{數(shù)據(jù)對象：D={ai|ai∈字幕字符集,i=1,2,…，n，n≥0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2,…，n}基本操作P：NewWord(&W,characters)初始條件：characters為字符序列。操作結(jié)果：生成一個其值為給定字符序列的單詞。DestroyWord(&W,characters)初始條件：單詞W已存在。操作結(jié)果：銷毀單詞W的結(jié)構(gòu)，并釋放相應(yīng)空間。WordCmp(W1，W2)初始條件：單詞W1，W2已存在。操作結(jié)果：若W1<W2，則返回-1;若W1=W2，則返回0；若W1>W2，則返回1。PrintWord(W)初始條件：單詞W已存在。操作結(jié)果：在計算機(jī)終端上顯示單詞W。}ADTAWordADTTextString{數(shù)據(jù)對象：D={ai|ai∈字符集,i=1,2,…，n，n≥0}數(shù)據(jù)關(guān)系R：D中字符被“換行符”分割成若干行，每一行的字符間滿足下列關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2,…，n}基本操作：Initation(&f)初始條件：文件f已存在。操作結(jié)果：打開文件f，設(shè)定文件指針指向文件中第一行第一個字符。GetAWord(f，&W)初始條件：文件f已打開。操作結(jié)果：從文件指針?biāo)缸址鹛崛∫粋€單詞w。ExtractWords(f,&L)初始條件：文件f已打開，文件指針指向文件中第一行第一個字符。操作結(jié)果：提取該行中所有單詞，并構(gòu)成單詞的有序表L；本操作結(jié)束時，文件指針指向f中下一行的第一個字符。Match(f,pat,&Result)初始條件：文件f已打開，文件指針指向文件中第一個字符;pat為包含所有待查詢單詞的有序表。操作結(jié)果：Result為查詢結(jié)果。}ADTTextString2主程序：voidmain(){}3其它的函數(shù)：主要函數(shù)：統(tǒng)計str在文章中出現(xiàn)的次數(shù)：intFindString(LINE*&head,char*str){}統(tǒng)計字母數(shù)intCountLetter(LINE*&head){do{}while}統(tǒng)計數(shù)字?jǐn)?shù)intCountNumber(LINE*&head){do{}while}其它的函數(shù)模板與這以上時一樣的三詳細(xì)分析:1創(chuàng)建一鏈表，同時向里面輸入文本數(shù)據(jù)typedefstructline{ char*data; structline*next;}LINE;2統(tǒng)計str在文章中出現(xiàn)的次數(shù)intFindString(LINE*&head,char*str)統(tǒng)計str在文章中出現(xiàn)的次數(shù){ LINE*p=head; intcount=0; inth=0; intlen1=0;//保存當(dāng)前行的總字符數(shù) intlen2=strlen(str);//待統(tǒng)計字符串的長度 inti,j,k; do { len1=strlen(p->data);//當(dāng)前行的字符數(shù) 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;}實現(xiàn)思想：1）從字符串s中尋找str第一次出現(xiàn)的位置*p=strstr(s,str)2)len=strlen(s);i=len-strlen9p即前i項恰好不含要刪除的字符串，將前i項復(fù)制到tmp中3）j=i+strlen(str)即要刪除的字符串在i+1和j之間，將j之后的字符串復(fù)制到tmp中4）將tmp賦給串s，返回s2向創(chuàng)建的鏈表中輸入數(shù)據(jù)：voidCreate(LINE*&head){ printf("請輸入一頁文章，以Ctrl+E(^E)為結(jié)尾（每行最多輸入80個字符?。?\n"); LINE*p=newLINE;//首先為鏈表建立一個附加表頭結(jié)點 head=p; chartmp[100]; while(1) { gets(tmp);//輸入字符串 if(strlen(tmp)>80) { printf("每行最多輸入80個字符"); break; } if(tmp[0]==5) break;//如果發(fā)現(xiàn)輸入^E,則退出輸入 p=p->next=newLINE; p->data=newchar[strlen(tmp)+1];//為結(jié)點分配空間 strcpy(p->data,tmp); if(tmp[strlen(tmp)-1]==5) { p->data[strlen(tmp)-1]='\0'; break; } } p->next=NULL;//最后的一個指針為空 head=head->next;}3統(tǒng)計文章的總字?jǐn)?shù)intCountAll(LINE*&head){ LINE*p=head;//保存鏈表的首地址 intcount=0; do//計算總字符數(shù) { 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第一次出現(xiàn)的位置 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);//返回新的字符串}四調(diào)試分析：1再輸入文章時，計算機(jī)怎樣識別文章是否結(jié)束？輸出文章時，怎樣處理表示結(jié)束的字符？通過調(diào)試，找到了解決方案：輸入文章時，以Ctrl+E(^E)為結(jié)尾，當(dāng)tep[0]==5時，發(fā)現(xiàn)輸如^E則退出輸入。輸出文章時，如果tmp[strlen[(tmp)-1]==5即發(fā)現(xiàn)表示結(jié)束的字符^E,用p->data[strlen(tmp)-1]=\0除去最后一個控制符^E2算法改進(jìn)：本程序的文章用戶輸入文章，只能做即時輸入統(tǒng)計，編譯，而不能對已有的磁盤文件中的文章進(jìn)行統(tǒng)計，編譯，如果引進(jìn)文件流類，就可以打開磁盤文件。對其進(jìn)行統(tǒng)計，編譯并保存，還是有待提高改進(jìn)的。五測試結(jié)果：1輸入數(shù)據(jù)的測試：2刪除某一字符串的數(shù)據(jù)：六附錄：#include<iostream.h>#include<string.h>#include<stdio.h>//文本每行以字符串形式存儲，行與行之間以鏈表存儲#include<iomanip.h>typedefstructline{ char*data;structline*next;}LINE;//創(chuàng)建一鏈表，同時向里面輸入文本數(shù)據(jù)voidCreate(LINE*&head){printf("請輸入一頁文章，以Ctrl+E(^E)為結(jié)尾(每行最多輸入80字符!):\n");LINE*p=newLINE;//首先為鏈表建立一個附加表頭結(jié)點head=p;//將p付給表頭指針chartmp[100];while(1){gets(tmp);//輸入字符串！ if(strlen(tmp)>80) { printf("每行最多輸入80字符"); break; } if(tmp[0]==5)break;//如果發(fā)現(xiàn)輸入^E，則退出輸入p=p->next=newLINE;p->data=newchar[strlen(tmp)+1];//為結(jié)點分配空間strcpy(p->data,tmp); if(tmp[strlen(tmp)-1]==5)//除去最后一個控制符^E {p->data[strlen(tmp)-1]='\0';break;}}p->next=NULL;//最后的一個指針為空head=head->next;}//統(tǒng)計字母數(shù)intCountLetter(LINE*&head){ LINE*p=head; intcount=0; do{intLen=strlen(p->data);//計算當(dāng)前data里的數(shù)據(jù)元素的個數(shù)for(inti=0;i<Len;i++)if((p->data[i]>='a'&&p->data[i]<='z')||(p->data[i]>='A'&&p->data[i]<='Z'))/*計算字母數(shù)*/ count++;}while((p=p->next)!=NULL);//遍歷鏈表 returncount;//返回文章的字母總數(shù)}//統(tǒng)計數(shù)字?jǐn)?shù)intCountNumber(LINE*&head){LINE*p=head;intcount=0;do{intLen=strlen(p->data);//計算當(dāng)前data里的數(shù)據(jù)元素的個數(shù)for(inti=0;i<Len;i++)if(p->data[i]>=48&&p->data[i]<=57)count++;//計算數(shù)字?jǐn)?shù)，ASCII碼}while((p=p->next)!=NULL);//遍歷鏈表returncount;}//統(tǒng)計空格數(shù)intCountSpace(LINE*&head){LINE*p=head;intcount=0;do{intLen=strlen(p->data);//計算當(dāng)前data里的數(shù)據(jù)元素的個數(shù)for(inti=0;i<Len;i++)if(p->data[i]==32)count++;//計算空格數(shù)，空格ASCII碼為32}while((p=p->next)!=NULL);//遍歷鏈表returncount;}//統(tǒng)計文章的總字?jǐn)?shù)intCountAll(LINE*&head){LINE*p=head;//保存鏈表的首地址intcount=0;do//計算總字符數(shù){ count+=strlen(p->data); }while((p=p->next)!=NULL);//遍歷鏈表returncount;}//統(tǒng)計str在文章中出現(xiàn)的次數(shù)intFindString(LINE*&head,char*str){LINE*p=head;intcount=0;inth=0;intlen1=0;//保存當(dāng)前行的總字符數(shù)intlen2=strlen(str);//待統(tǒng)計字符串的長度inti,j,k;do{ len1=strlen(p->data);//當(dāng)前行的字符數(shù) 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第一次出現(xiàn)的位置*/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("全部字母數(shù)：%d\n",CountLetter(head));printf("數(shù)字個數(shù)：%d\n",CountNumber(head));printf("空格個數(shù):%d\n",CountSpace(head));printf("文章總字?jǐn)?shù):%d\n",CountAll(head));charstr1[20],str2[20];printf("\n");while(1){printf("1.統(tǒng)計某一字符串在文章所出現(xiàn)的次數(shù)\n");printf("2.刪除文章中的某一字符串\n");printf("3.退出系統(tǒng)\n");printf("請選擇所要操作的選項:\n");scanf("%d",&i); if(i==1){while(1){printf("請輸入要統(tǒng)計的字符串:");scanf("%s",str1);printf("%s出現(xiàn)的次數(shù)為:%d\n",str1,FindString(head,str1));printf("\n");cout<<"請選擇操作方式:"<<endl;cout<<"繼續(xù)統(tǒng)計請選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<<"繼續(xù)刪除請選1，退出請選0.\n"<<endl;scanf("%s",&k);if(k=='0')break; } } elsebreak;}}七設(shè)計體會心得：此次課設(shè)使我對數(shù)據(jù)結(jié)構(gòu)方面的知識有了更深層的了解，也使我認(rèn)識到自己在學(xué)習(xí)編程方面有很多的不足。今后我要多讀一些編程方面的書籍，不能只拘泥于課本上的知識，并注重理論與實踐的結(jié)合，多上機(jī)練習(xí)編寫程序，提高自己的實際動手能力和獨立思考的能力，不斷充實自己，更好的掌握編程思想。線索二叉樹的實習(xí)報告題目：建立中序二叉樹，并且中序遍歷，求中序線索二叉樹上已知結(jié)點中序的前驅(qū)和后繼。一需求分析1先建立二叉樹，然后開始線索二叉樹，中序遍歷2在中序線索二叉樹上尋找指定結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點3在建立二叉樹時，要自己先組建一課二叉樹，根據(jù)它進(jìn)行輸入；4輸出結(jié)點信息后，再輸入一結(jié)點信息，查找它的前驅(qū)和后繼5輸入過程中一定要正確輸入6測試數(shù)據(jù)：輸入一個數(shù)值再分別輸入建立的左右子數(shù)輸出結(jié)點信息二概要分析1抽象數(shù)據(jù)類型樹的定義如下：ADTBinaryTree{數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R：若D=Φ，則R=Φ，稱BinayTree為空二叉樹；若D≠Φ，則R={H}，H是如下二元關(guān)系：在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H喜愛無前驅(qū)；若D-{root}≠Φ,則存在D-{root}={D1，Dr}，且D1∩Dr=Φ;若D1≠Φ,則D1中存在惟一的元素X1,<root,X1>∈H,且存在D1上的關(guān)系H1∈H;若Dr≠Φ,則Dr中存在惟一的元素Xr,<root,Xr>∈H,且存在Dr上的關(guān)系Hr屬于H,H={<root,Xr>,,<root,Xr>,H1,Hr};(D1，{H1})是一顆符合本定義的二叉樹，稱為根的左子樹，(D1，{H1})是一棵符合本定義的二叉樹，稱為根的右子樹。基本操作：InitBiTree(&T);操作結(jié)果：構(gòu)造空二叉樹。CreateBiTree(&T,definittion);初始條件：definittion給出的二叉樹T的定義。操作結(jié)果：按definittion構(gòu)造二叉樹T。BiTreeEmpty(T);初始條件：二叉樹T存在操作結(jié)果：若T為空二叉樹，則返回TRUE，否則FALSE。Value(T,e);初始條件：二叉樹T存在操作結(jié)果：返回E的值。Assign(T,&e,value);初始條件；二叉樹T存在，e是T中的某個結(jié)點。操作結(jié)果：結(jié)點e賦值為value.Leftchild(T,e);初始條件；二叉樹T存在，e是T中的某個結(jié)點。操作結(jié)果;返回e的左孩子。若e無右孩子，則返回“空”。Rightchild(T,e);初始條件；二叉樹T存在，e是T中的某個結(jié)點。操作結(jié)果;返回e的右孩子。若e無右孩子，則返回“空”。LeftSibling(T,e);初始條件；二叉樹T存在，e是T中的某個結(jié)點。操作結(jié)果;返回e的左兄弟。若e是T的左孩子或無左兄弟，則返回“空”。Rightsibling(T,e);初始條件；二叉樹T存在，e是T中的某個結(jié)點。操作結(jié)果;返回e的右兄弟。若e是T的右孩子或無右兄弟，則返回“空”。PreDrderTraverse(T,Visit());初始條件；二叉樹T存在,Visit是對應(yīng)結(jié)點操作的應(yīng)用函數(shù)。操作結(jié)果：先遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且一次，一旦visit（）失敗，則操作失敗。InOrderTraverse(T,Visit());初始條件；二叉樹T存在,Visit是對應(yīng)結(jié)點操作的應(yīng)用函數(shù)。操作結(jié)果：中序遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且一次，一旦visit（）失敗，則操作失敗。PostOrderTraverse(T,Visit());初始條件；二叉樹T存在,Visit是對應(yīng)結(jié)點操作的應(yīng)用函數(shù)。操作結(jié)果：后序遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且一次，一旦visit（）失敗，則操作失敗。LeveOrderTraverse(T,Visit());初始條件；二叉樹T存在,Visit是對應(yīng)結(jié)點操作的應(yīng)用函數(shù)。操作結(jié)果：層序遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且一次，一旦visit（）失敗，則操作失敗。}ADTBinaryTree2主程序voidmain(){ThreadTreet,p;charch[20],x[20];intflag=1;while(flag){printf("\n請選擇需要進(jìn)行的操作:\n");printf("\n1：創(chuàng)建二叉樹\n");printf("\n2：線索二叉樹\n");printf("\n3：中序線索二叉樹\n");printf("\n4：尋找結(jié)點p的中序前驅(qū)結(jié)點\n");printf("\n5：尋找結(jié)點p的中序后繼結(jié)點\n");printf("\n6：查找值為X的結(jié)點\n");printf("\n0：退出！\n\n");scanf("%d",&flag);switch(flag){case1:printf("\n開始創(chuàng)建二叉樹\n");printf("\n請輸入一個數(shù)值:");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://在中序線索二叉樹上尋找結(jié)點p的中序前驅(qū)結(jié)點的算法：printf("\n輸入P節(jié)點信息，以方便查找\n");scanf("%s",x);printf("\n尋找結(jié)點p的中序前驅(qū)結(jié)點!\n");p=Search(t,x);InPreNode(p);break;case5://在中序線索二叉樹上尋找結(jié)點p的中序后繼結(jié)點的算法:printf("\n輸入P節(jié)點信息，以方便查找!\n");scanf("%s",x);printf("\n結(jié)點p的中序后繼結(jié)點信息！\n");printf("\n尋找結(jié)點p的中序后繼結(jié)點!\n");p=Search(t,x);p=InPostNode(p);visite(p->date);break;case6://在中序線索二叉樹上查找值為X的結(jié)點printf("\n請輸入查找的數(shù)值！\n");scanf("%s",x);p=Search(t,x);if(p)printf("\n查找成功！\n\n");elseprintf("\n查找失?。n\n");break;default:break;}三詳細(xì)設(shè)計1二叉樹的二叉鏈表存儲表示typedefstructThreadnode{intltag,rtag;chardate[20];structThreadnode*lchild,*rchild;}Threadnode,*ThreadTree;2初始化二叉樹typedefstructThreadnode{intltag,rtag;chardate[20];structThreadnode*lchild,*rchild;}Threadnode,*ThreadTree;3在中序線索二叉樹上尋找結(jié)點p的中序后繼結(jié)點的算法:ThreadTreeInPostNode(ThreadTreep){ThreadTreepost;post=p->rchild;if(p->rtag==0)while(post->ltag==0)post=post->lchild;return(post);}4在中序線索二叉樹上尋找結(jié)點p的中序前驅(qū)結(jié)點的算法：ThreadTreeInPreNode(ThreadTreep){ThreadTreeprel;prel=p->lchild;if(p->ltag==0)while(prel->rtag==0)prel=prel->rchild;printf("\n結(jié)點p的中序前驅(qū)結(jié)點信息！\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); }}}四調(diào)試分析1對于本實驗來講，首先要創(chuàng)建一課二叉樹，并且初始化，在這里用到了中序遍歷二叉樹的算法，尋找結(jié)點前驅(qū)后繼的算法。2在程序運行期間，建立二叉樹時，要把其左右子樹輸入正確，以免運行會出現(xiàn)錯誤，通過反復(fù)的調(diào)試對其存儲會有更深的印象五測試結(jié)果1創(chuàng)建二叉樹二輸入左子樹右子樹的數(shù)值三中序線索二叉樹結(jié)果四輸出指定結(jié)點的前驅(qū)和后繼七附錄#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輸出節(jié)點信息:");printf("%s",ch);}//初始化二叉樹ThreadTreeCreatThreadTree(charch[]){ThreadTreet;charch1[20],ch2[20];t=(ThreadTree)malloc(sizeof(Threadnode));strcpy(t->date,ch);printf("\n請輸入左子樹的數(shù)值，結(jié)束輸入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請輸入右子樹的數(shù)值，結(jié)束輸入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;}//建立中序線索二叉樹算法實現(xiàn)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);}}//在中序線索二叉樹上尋找結(jié)點p的中序后繼結(jié)點的算法:ThreadTreeInPostNode(ThreadTreep){ThreadTreepost;post=p->rchild;if(p->rtag==0)while(post->ltag==0)post=post->lchild;return(post);}//在中序線索二叉樹上查找值為X的結(jié)點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;}//在中序線索二叉樹上尋找結(jié)點p的中序前驅(qū)結(jié)點的算法：ThreadTreeInPreNode(ThreadTreep){ThreadTreeprel;prel=p->lchild;if(p->ltag==0)while(prel->rtag==0)prel=prel->rchild;printf("\n結(jié)點p的中序前驅(qū)結(jié)點信息！\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請選擇需要進(jìn)行的操作:\n");printf("\n1：創(chuàng)建二叉樹\n");printf("\n2：線索二叉樹\n");printf("\n3：中序線索二叉樹\n");printf("\n4：尋找結(jié)點p的中序前驅(qū)結(jié)點\n");printf("\n5：尋找結(jié)點p的中序后繼結(jié)點\n");printf("\n6：查找值為X的結(jié)點\n");printf("\n0：退出！\n\n");scanf("%d",&flag);switch(flag){case1:printf("\n開始創(chuàng)建二叉樹\n");printf("\n請輸入一個數(shù)值:");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://在中序線索二叉樹上尋找結(jié)點p的中序前驅(qū)結(jié)點的算法：printf("\n輸入P節(jié)點信息，以方便查找\n");scanf("%s",x);printf("\n尋找結(jié)點p的中序前驅(qū)結(jié)點!\n");p=Search(t,x);InPreNode(p);break;case5://在中序線索二叉樹上尋找結(jié)點p的中序后繼結(jié)點的算法:printf("\n輸入P節(jié)點信息，以方便查找!\n");scanf("%s",x);printf("\n結(jié)點p的中序后繼結(jié)點信息！\n")；printf("\n尋找結(jié)點p的中序后繼結(jié)點!\n");p=Search(t,x);p=InPostNode(p);visite(p->date);break;case6://在中序線索二叉樹上查找值為X的結(jié)點printf("\n請輸入查找的數(shù)值！\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");}}八設(shè)計體會心得：經(jīng)過線索而叉樹的設(shè)計編寫，使我對數(shù)據(jù)結(jié)構(gòu)有了更深的了解，要想學(xué)好它重在實踐，我也發(fā)現(xiàn)我的好多不足之處，首先是自己在指法上還不行，經(jīng)過按錯字母等其它的錯誤，這次同過學(xué)習(xí)，對數(shù)據(jù)結(jié)果中較陌生的函數(shù)也有了一定的了解還有以前對函數(shù)的調(diào)用不熟悉，對程序中經(jīng)常出現(xiàn)的錯誤也不懂，通過實踐，使我在這些方面有了提高。通過實踐學(xué)習(xí)，我認(rèn)識到學(xué)好計算機(jī)要注重實踐操作，不僅僅是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，還有其它的語言，以及其它的計算機(jī)要重視實踐，多動手。所以在以后的學(xué)習(xí)過程中，我會更加注視實踐操作，使自己更好的學(xué)好計算機(jī)。校園導(dǎo)游咨詢的的實習(xí)報告題目：編制一個為來訪客人進(jìn)行最短路徑導(dǎo)游的程序一、需求分析1．從中原工學(xué)院信息商務(wù)學(xué)院的平面圖中選取19個有代表性的景點，抽象成一個無向帶權(quán)圖。以圖中頂點表示景點，邊上的權(quán)值表示兩地之間的距離。2.本程序的目的是為用戶提供路徑咨詢。根據(jù)用戶指定的始點和終點輸出相應(yīng)路徑，或者根據(jù)用戶指定的景點輸出景點的信息。3.測試數(shù)據(jù)（附后）二、概要設(shè)計1.抽象數(shù)據(jù)類型圖的定義如下：ADTGraph{數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關(guān)系R：R={VR}VR={(v,w)|v,w}∈V,(v,w)表示v和w之間存在路徑}基本操作P：GreateGraph（&G,V,VR）初始條件：V是圖的頂點集，VR是圖中邊的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G.GrestroyGraph（&G）初始條件：圖G存在。操作結(jié)果：銷毀圖G。LocateVex(G，u)初始條件：圖G存在，u和G中頂點有相同特征。操作結(jié)果：若G中存在頂點u，則返回該頂點在圖中位置；否則返回其他信息。GetVex（G,v）初始條件：圖中存在，v是G中某個頂點。操作結(jié)果：返回v的信息。FirstEdge（G，v）初始條件：圖G存在，v是G中某個頂點。操作結(jié)果：返回依附于v的第一條邊。若該頂點在G中沒有鄰接點，則返回“空”。NextEdge（G,v，w）初始條件：圖G存在，v是G中某個頂點，w是v的鄰接頂點。操作結(jié)果；返回依附于v的（相對于w的）下一條邊。若不存在，則返回“空”。InsertVex（&G，v）初始條件：圖G存在，v和圖中頂點有相同特征。操作結(jié)果：在圖G中增添新頂點v。DeleteVex（&G,v）初始條件：圖G存在，v是G中某個頂點。操作結(jié)果：刪除G中頂點v及其相關(guān)的邊。InsertEdge（&G，v,w）初始條件：圖G存在，v和w是G中兩個頂點。操作結(jié)果：在G中增添邊（v,w）。DeleteEdge（&G，v，w）初始條件：圖G存在，v和w是G中兩個頂點。操作結(jié)果：在G中刪除邊（v，w）。GetShortestPath（G,st，nd，&path）初始條件：圖G存在，st和nd是G中兩個頂點。操作結(jié)果：若st和nd之間存在路徑，則以path返回兩點之間一條最短路徑，否則返回其他信息。}ADTGraph2主程序voidmain(){初始化；switch(k)}3本程序包含兩個模塊：主程序模塊；最短路徑問題；三詳細(xì)分析1#defineMax20//圖中頂點的最大值#defineInit_Length10000//邊的權(quán)值，表示路徑長度2界面輸出函數(shù)：voidprint(){printf("*******歡迎您來到中原工學(xué)院信息商務(wù)學(xué)院********\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.退出系統(tǒng)請輸入e\n");printf("請輸入您的選擇:");}4主函數(shù)部分：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("進(jìn)入景點查詢:\n");introduce();break;case's':printf("進(jìn)入最短路徑查詢:\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;其它部分再此就不詳細(xì)介紹了四、設(shè)計和調(diào)試分析1.原設(shè)計在變的屬性中加上訪問標(biāo)志域mark，意圖以！（p->mark）代替！Inset（w，ss）來判別是否需要檢測該條邊，后發(fā)現(xiàn)，如此只能求出第一對頂點之間的最短路徑。在繼續(xù)求其他對定點的最短路徑時，必須恢復(fù)所有邊的訪問標(biāo)志為FALSE,則需要消耗O(e)的時間，并不比現(xiàn)在的算法優(yōu)越，故舍去之。2.考慮道路網(wǎng)多是稀疏網(wǎng)，故采用鄰接多重表作存儲結(jié)構(gòu)，其空間復(fù)雜度為O（e），此時的時間復(fù)雜度也為O(e)。構(gòu)建鄰接多重表的時間復(fù)雜度為O(n+e)，輸出路徑的時間復(fù)雜度為O(n)。由此，本導(dǎo)游程序的時間復(fù)雜度為O(n+e)。3.由于導(dǎo)游程序在實際執(zhí)行時，需要根據(jù)用戶的臨時輸入求最短路徑。因此，雖然迪杰斯特拉算法的時間復(fù)雜度比費洛依德算法低，但每求一條最短路徑都必須重新搜索一遍，在頻繁查詢時會導(dǎo)致查詢效率降低，而費洛依德算法只要計算一次，即可求得每一對頂點之間的最短路徑，雖然時間復(fù)雜度為O（n3）,但以后每次查詢都只要查表即可，極大地提高了查詢效率，而且費洛依德算法還支持帶負(fù)權(quán)的圖的最短路徑的計算。由此可見，在選用算法時，不能單純地只考慮算法的漸近時間復(fù)雜度，有時還必須綜合考慮各種因素。五測試結(jié)果1界面函數(shù)的顯示：2查詢景點：3查詢最短路徑：七附錄#include<stdio.h>#include<math.h>#include<stdlib.h>#defineMax20#defineInit_Length10000voidshortestdistance();voidprint()//voidmain(){printf("*******歡迎您來到中原工學(xué)院信息商務(wù)學(xué)院********\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.退出系統(tǒng)請輸入e\n");printf("請輸入您的選擇:");}voidintroduce(){inta;printf("請輸入景點編號:");scanf("%d",&a);getchar();printf("\n");while(a<1||a>13){printf("ERROR!請輸入數(shù)字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("進(jìn)入景點查詢:\n");introduce();break;case's':printf("進(jìn)入最短路徑查詢:\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("請輸入您現(xiàn)在所在的位置:\n");scanf("%d",&v0);while(v0>13||v0<1){printf("ERROR!請重新輸入編號從1到13的數(shù)\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]);}八設(shè)計體會心得：在這次的設(shè)計中體會最深的是對最短路徑的分析，在這里要求為來訪客人提供景點的問路查詢，即已知一個景點，查詢到某景點之間的一條最短路徑及長度。在這里引進(jìn)一個輔助向量D，它的每個分量都表示當(dāng)前所找到得從始點v到每個終點Vi的最短路徑長度。他的初始態(tài)為：若從v到vi有弧，則D[j]為弧上的權(quán)值；否則置D[j]為∞，顯然長度為：D[j]=Min{D[j]|Vi∈V}的路經(jīng)就是從V出發(fā)的長度最短的一條最短路徑。在這里選用鄰接矩陣來求最短路徑。從這里學(xué)到了更多是求最短路徑的方法和思想。宿舍管理查詢的實習(xí)報告題目:為宿舍管理人員編寫一個宿舍管理查詢軟件一需求分析1建立數(shù)據(jù)文件，數(shù)據(jù)文件按關(guān)鍵字（姓名、學(xué)號、房號）進(jìn)行排序(選擇、快速排序、堆排序等任選一種)2可以增加，修改，刪除指定信息3查詢:a.按姓名查詢;b.按學(xué)號查詢;c按房號查詢4演示程序時，根據(jù)顯示的信息，用戶可由鍵盤輸入排序表的表長和不同數(shù)據(jù)的數(shù)組。每次測試完畢，列表顯示各種比較指標(biāo)值。5最后對結(jié)果做出簡單分析二概要分析可排序表的抽象數(shù)據(jù)類型定義：ADTOrderableList{數(shù)據(jù)對象：D={ai|ai∈Integerset，i=1,2,…，n，n>=0}數(shù)據(jù)關(guān)系：R1={<ai-1，ai>|ai-1,ai∈D，i=2，…，n}基本操作：InitList(n)操作結(jié)果：構(gòu)造一個長度為n，元素值依次為1,2，…，n的有序表。RandomizeList(d,isInverseOrder)操作結(jié)果：首先根據(jù)isInverseOrder為True或False，將表置為逆序或正序，然后將表進(jìn)行d（0<=d<=8）級隨機(jī)打亂。d為0時表不打亂，d越大，打亂程度越高。RecallList（）操作結(jié)果：恢復(fù)最后一次用RandomizeList隨機(jī)打亂得到的可排序表。ListLength（）操作結(jié)果：返回可排序表的長度。ListEmpty（）操作結(jié)果：若可排序表為空表，則返回True，否則返回False。BubbleSort（&c，&s）操作結(jié)果：進(jìn)行起泡排序，返回關(guān)鍵字比較次數(shù)c和移動次數(shù)s。InsertSort（&c，&s）操作結(jié)果：進(jìn)行插入排序，返回關(guān)鍵字比較次數(shù)c和移動次數(shù)s。SelectSort（&c，&s）操作結(jié)果：進(jìn)行選擇排序，返回關(guān)鍵字比較次數(shù)c和移動次數(shù)s。QuickSort（&c，&s）操作結(jié)果：進(jìn)行快速排序，返回關(guān)鍵字比較次數(shù)c和移動次數(shù)s。ShellSort（&c，&s）操作結(jié)果：進(jìn)行希爾排序，返回關(guān)鍵字比較次數(shù)c和移動次數(shù)s。HeapSort（&c，&s）操作結(jié)果：進(jìn)行堆排序，返回關(guān)鍵字比較次數(shù)c和移動次數(shù)s。ListTraverse（visit（））操作結(jié)果：依次對L中的每個元素調(diào)用函數(shù)visit（）。}ADTOrderableList2本程序包含模板結(jié)構(gòu)如下：1）主程序模板2）針對主程序中的模板寫相對應(yīng)的函數(shù)：如增加學(xué)生信息：voidAdd(){}查找函數(shù)：voidSearching(){}按學(xué)號查找：voidNumSearching(){}按地址查找：voidDNumSearching(){}排序函數(shù)：voidSort(){}修改函數(shù)：voidAmend(){}刪除函數(shù)：voidDelete(){}三詳細(xì)設(shè)計：1宿舍的結(jié)構(gòu)體定義：structDorm{ stringstudent_name; intdorm_num; intstudent_num;};DormS[100];inta=1,n;2內(nèi)部的排序voidSort(){ intk,j,t,temp1,temp2,o; stringx;ifstreaminfile("王琳的宿舍管理系統(tǒng).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.按學(xué)生學(xué)號排序"<<endl; cout<<"3.按學(xué)生宿舍號排序"<<endl; cout<<"4.返回主菜單"<<endl; cout<<"請選擇你要執(zhí)行的操作：\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