大數(shù)據(jù)結構 將一個鏈表拆分成三個鏈表

《大數(shù)據(jù)結構 將一個鏈表拆分成三個鏈表》由會員分享，可在線閱讀，更多相關《大數(shù)據(jù)結構 將一個鏈表拆分成三個鏈表（8頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、《數(shù)據(jù)結構》實驗報告 ◎實驗題目：將一個鏈表拆分成三個鏈表。 ◎實驗目的：1、掌握使用Visual C++6.0上機調試程序的基本方法; 2、 掌握鏈表結構中的基本操作并學會靈活運用； 3、 提高自己分析問題和解決問題的能力，在實踐中理解教材上的理論。 ◎實驗內容：建立鏈表并存儲輸入的數(shù)據(jù)，根據(jù)各節(jié)點數(shù)據(jù)的類型，建立三個鏈表并將不 同類型的數(shù)據(jù)分別輸出。 、需求分析 1、 輸入的形式和輸入值的范圍：根據(jù)提示，輸入鏈表中的各數(shù)據(jù)，輸入回車結束輸入，所 輸入的數(shù)據(jù)元素為字符類型。 2、 輸出的形式：根據(jù)輸入的字符串中數(shù)據(jù)的類型(字母、數(shù)字和其它)，分類輸出。 3、 程序所能達到的

2、功能：根據(jù)提示輸入數(shù)據(jù)，然后根據(jù)數(shù)據(jù)元素類型的不同，將其分別輸 出，輸出結束后提示是否結束，根據(jù)需要繼續(xù)操作。由此可以實現(xiàn)實驗內容中的要求。 4、 測試數(shù)據(jù)： 輸入鏈表中的各元素: *?9Li(0)@02 11\ 字母:Li 數(shù)字：900211 其它：*?()@ \ 是否結束?是，輸入0;否，輸入1 0 謝謝使用，再見! 二概要設計 本程序使用單鏈表表示的線性表，建立鏈表并存儲數(shù)據(jù)，拆分后的三個鏈表都用帶頭結 點的單鏈表存放，先建立三個頭結點，用一指針掃描待拆分的鏈表，然后根據(jù)各結點的數(shù)據(jù) 的類型不同將其分別插入三個新鏈表中，由此實現(xiàn)了對鏈表的拆分，最后將鏈表中的數(shù)據(jù)輸 出

3、即可實現(xiàn)題目要求。 本程序的基本操作和模塊： ① 主程序模塊main () 對輸入的操作進行提示，調用其它的各個函數(shù)； ② 建立鏈表并輸入數(shù)據(jù)模塊Create(LinkList *&L) ③ 輸出鏈表中的數(shù)據(jù)模塊Printf(LinkList *L) ④ 將原鏈表拆分成三個鏈表的模塊： Fun(LinkList *hd,LinkList *ha,LinkList *hb,LinkList *hc) 程序流程如下所示 三詳細設計 (一)元素類型、結點類型和指針類型 typedef struct LNode ( char data; struct LNode *ne

4、xt; }LinkList; (二)每個模塊的分析 1、主程序模塊分析 main() int ( LinkList *hd,*ha,*hb,*hc; 〃定義四個頭結點指針，*hd代表待拆分鏈表， 其它類型的鏈表 ha=(LinkList hb=(LinkList hc=(LinkList int i; *ha,*hb和*hc分別代表字母，數(shù)字 止本 char m; *)malloc(sizeof(LinkList)); *)malloc(sizeof(LinkList)); *)malloc(sizeof(LinkList)); //創(chuàng)建ha頭結點 //創(chuàng)建hb頭

5、結點 //創(chuàng)建hc頭結點 //定義整型數(shù)據(jù)i，用于判斷是否終 程序的運行 〃定義字符型數(shù)據(jù)m,存放輸入i的值之 的回車 while(1) ( Create(hd); //調用建立單鏈表并輸入數(shù)據(jù)的函數(shù) Fun(hd,ha,hb,hc); //調用拆分鏈表的函數(shù) printf("\n字母：")； //提示輸出的鏈表中數(shù)據(jù)為字母類型 Printf(ha); 〃調用輸出鏈表元素的函數(shù)，輸出ha鏈表中的數(shù)據(jù)(字 母類型) printf (-\n數(shù)字：")； //提示輸出的鏈表中數(shù)據(jù)為數(shù)字類型 Printf(hb); 〃調用輸出鏈表元素的函數(shù)，輸出hb鏈表中的數(shù)據(jù)(數(shù) 字類

6、型) printf (-\n其它：")； //提示輸出的鏈表中數(shù)據(jù)為其它類型 Printf(hc); 〃調用輸出鏈表元素的函數(shù)，輸出hc鏈表中的數(shù)據(jù)(其 它類型) printf("\n"); printf(-\n是否結束?是，輸入0;否，輸入1\n"); //提示是否終止本程序的 運行 scanf("%d",&i); //輸入整數(shù) i printf("\n"); if(i==1) scanf("%c",&m); //存放輸入i的值之后的 回車 if(i==0) break; 〃當i為0時，結束循環(huán)，結束運行 } printf("謝謝使用，再見！ \n\n"); return 0;

7、 } 2、建立鏈表和輸入數(shù)據(jù)模塊分析 void Create(LinkList *&L) LinkList *s,*r; L=(LinkList *)malloc(sizeof(LinkList)); //創(chuàng)建頭結點 L->next=NULL; //r始終指向終端結點，開始時指向 〃用于提示字符串的輸入 r=L; 頭結點 printf("輸入鏈表中的各元素:\n"); while(1) { s=(LinkList *)malloc(sizeof(LinkList)); //創(chuàng)建新結點 scanf("%c",&s->data); //輸入新節(jié)點的數(shù)據(jù) r->next=

8、s; r=s; if(s->data=='\n') break; 結束 } r->next=NULL; } //將*，插入*r之后 〃若輸入回車，則字符串的輸入 〃終端結點next域置NULL 3、輸出鏈表元素模塊分析 void Printf(LinkList *L) ( LinkList *p=L->next; while (p!=NULL) ( printf("%c",p->data); //當指針p所指結點next域不為NULL時，將該結 點的 數(shù)據(jù)輸出 p=p->next; //p指針向后移動 } } 4、拆分鏈表模塊分析 void

9、Fun(LinkList *hd,LinkList *ha,LinkList *hb,LinkList *hc) { //ra始終指向ha的末尾結點 //ra始終指向ha的末尾結點 //ra始終指向ha的末尾結點 //當指針p所指結點的指針域不為NULL時，執(zhí)行以下循環(huán)過程 LinkList *p=hd->next,*ra,*rb,*rc;//定義三個指向鏈表結點的指針 ra=ha; rb=hb; rc=hc; while(p!=NULL) { if(p->data>='A'&&p->data<='Z'||p->data>='a'&&p->data<='z') 〃若數(shù)據(jù)

10、為字母型 ra->next=p;ra=p; //將*?鏈接到ha單鏈表末尾 p=p->next; //p 指針后移 } else { if(p->data>='0'&&p->data<='9') //如果數(shù)據(jù)為數(shù)字類型 { rb->next=p;rb=p; p=p->next; } else { rc->next=p;rc=p; p=p->next; } //將*?鏈接到ha單鏈表末尾 //p指針后移 〃數(shù)據(jù)為其它類型的情況 //將*?鏈接到ha單鏈表末尾 //p指針后移 } ra->next=NULL;rb->next=NULL; r

11、c->next=NULL; //將三個新鏈表尾結點next域置空 四使用說明、測試分析及結果 1、 程序使用說明： (1) 本程序運行環(huán)境為Visual C++ 6.0; (2) 根據(jù)界面提示進行操作，每次從鍵盤輸入數(shù)據(jù)后按回車結束。 2、 測試結果與分析： 根據(jù)提示，當輸入為*?9Li(0)@02 11\時，輸出結果如下所示 字母:Li 數(shù)字：900211 其它：*?()@ \ 是否結束?是，輸入0;否，輸入1 0 謝謝使用，再見！ 3、 調試過程中遇到的問題及解決方法 ① 當代碼編寫完成后，編譯過程出現(xiàn)了很多小錯誤，比如語句末尾漏掉分號，賦值運算符與 等號混淆

12、等，但這些問題很快發(fā)現(xiàn)并及時糾正； ② 另外，在運行時出現(xiàn)可以輸入字符串但卻無法正常輸出結果的現(xiàn)象，在進一步分析所編寫 的代碼后，發(fā)現(xiàn)函數(shù)調用過程不對，在參考程序設計教材后，解決了這一問題。 4、 運行界面 五、實驗總結 本次實驗，我進行了預習，但是預習過程不夠認真，忽略了很多細節(jié)，以致于我用了大 約一個小時的時間編寫完代碼，但是對代碼的修改卻花費了大量時間，沒有當堂完成。課后， 我參考了C程序設計的教材并很快發(fā)現(xiàn)自己的問題，又花費了半個小時，才最終修改正確。 在最開始編寫程序時，因為長時間沒有應用C語言，所以部分基本知識有些生疏，以致 于發(fā)生了很多低級的錯誤，比如忽略了字符

13、型數(shù)據(jù)和整型數(shù)據(jù)的區(qū)別，在輸入字符串時以空 格分隔各其它字符，導致得不到輸出結果，不過這些錯誤很快糾正。 另外，在最初的程序中，通過輸入字符串中字符的個數(shù)然后再輸入字符串，最后輸出結 果，因為要輸入字符串中字符的個數(shù)，所以當字符串較長時操作起來不方便。所以我對其進 行了修改，在函數(shù)中判斷是否有回車的輸入，以回車直接結束字符串的輸入，不必再輸入字 符個數(shù)，從而操作起來更加方便。 我還在主函數(shù)中添加了一個循環(huán)，以輸入0’或‘1’判斷是否繼續(xù)程序的運行，使之 更加人性化，但是在此也遇到一個問題。當輸入1’時，表示不結束，但是輸入1’之后 以回車表示輸入的結束，因為回車表示字符串輸入的結束，所以導

14、致之后的操作不能正常進 行，為解決這一問題，我在主函數(shù)中重新定義了一個字符型數(shù)據(jù)，以吸收回車。最終程序得 以正常運行。 本次實驗，我很感謝老師和同學對我的指點。通過本次實驗，對鏈表結構有了更深層次 的認識，對一些細節(jié)更加理解，收獲了很多。 教師評語： 實驗成績： 指導教師簽名: 批閱日期: 代碼： # include # include /*************** 定義單鏈表結點類型 ***************/ typedef struct LNode { char data; //每個結點中存儲的數(shù)據(jù)為字符型 str

15、uct LNode *next; //指向后繼結點 }LinkList; /************建立單鏈表并輸入數(shù)據(jù)的函數(shù)**********/ void Create(LinkList *&L) { LinkList *s,*r; L=(LinkList *)malloc(sizeof(LinkList)); //創(chuàng)建頭結點 L->next=NULL; 〃頭結點的next域置空 r=L; //r始終指向終端結點，開始時指向頭結點 printf(-輸入鏈表中的各元素：\n"); //用于提示字符串的輸入 while(1) { s=(LinkList *)malloc

16、(sizeof(LinkList));//創(chuàng)建新結點 scanf("%c”,&s->data); //輸入新節(jié)點的數(shù)據(jù) r->next=s; 〃將*s插入*匕之后 r=s; if(s->data=='\n') break; //若輸入回車，則字符串的輸入結束 } r->next=NULL; 〃終端結點 next 域置 NULL } /***********輸出鏈表中的所有元素的函數(shù)***********/ void Printf(LinkList *L) { LinkList *p=L->next; while (p!=NULL) { printf("%c",p->d

17、ata); //當指針p所指結點next域不為NULL時，將該結點的數(shù)據(jù)輸出 p=p->next; //p指針向后移動 } } /*****************拆 分鏈表的函數(shù) *****************/ void Fun(LinkList *hd,LinkList *ha,LinkList *hb,LinkList *hc) { LinkList *p=hd->next,*ra,*rb,*rc;//定義三個指向鏈表結點的指針 ra=ha; //ra始終指向ha的末尾結點 rb=hb; //ra始終指向ha的末尾結點 rc=hc; //ra始終指向ha的末尾結點

18、 while(p!=NULL) //當指針p所指結點的指針域不為NULL時，執(zhí)行以下循環(huán)過程 { if(p->data>='A'&&p->data<='Z'||p->data>='a'&&p->data<='z')//如果數(shù)據(jù)為字母類型 { ra->next=p;ra=p;//將*p鏈接到ha單鏈表末尾 p=p->next; //p 指針后移 } else { if(p->data>='0'&&p->data<='9') //如果數(shù)據(jù)為數(shù)字類型 { rb->next=p;rb=p;//將*p鏈接到ha單鏈表末尾 p=p->next; //p 指針后移 } else

19、〃數(shù)據(jù)為其它類型的情況 { rc->next=p;rc=p;//將*p鏈接到ha單鏈表末尾 p=p->next; //p 指針后移 } ra->next=NULL; rb->next=NULL; rc->next=NULL;//將三個新鏈表尾結點的 next 域置空 } /********************主 函數(shù) ********************/ int main() { LinkList *hd,*ha,*hb,*hc; 〃定義四個頭結點指針，*hd代表待拆分鏈表，*ha,*hb和*hc分別代表字母，數(shù)字和其它類型的鏈表 ha=(LinkList *)m

20、alloc(sizeof(LinkList));//創(chuàng)建 ha 頭結點 hb=(LinkList *)malloc(sizeof(LinkList));//創(chuàng)建 hb 頭結點 hc=(LinkList *)malloc(sizeof(LinkList));//創(chuàng)建 hc 頭結點 int i; //定義整型數(shù)據(jù)i，用于判斷是否終止本程序的運行 char m; 〃定義字符型數(shù)據(jù)m,存放輸入i的值之后的’\n' while(1) { Create(hd); //調用建立單鏈表并輸入數(shù)據(jù)的函數(shù) Fun(hd,ha,hb,hc); //調用拆分鏈表的函數(shù) printf("\n字母：")；

21、//提示輸出的鏈表中數(shù)據(jù)為字母類型 Printf(ha); //調用輸出鏈表元素的函數(shù)，輸出ha鏈表中的數(shù)據(jù)(字母類型) printf("\n數(shù)字：”)； //提示輸出的鏈表中數(shù)據(jù)為數(shù)字類型 Printf(hb); //調用輸出鏈表元素的函數(shù)，輸出hb鏈表中的數(shù)據(jù)(數(shù)字類型) printf("\n其它：”)； //提示輸出的鏈表中數(shù)據(jù)為其它類型 Printf(hc); //調用輸出鏈表元素的函數(shù)，輸出hc鏈表中的數(shù)據(jù)(其它類型) printf("\n是否結束?是，輸入0;否，輸入1\n"); //提示是否終止本程序的運行 scanf("%d”,&i); 〃輸入整數(shù) i printf("\n"); if(i==1) scanf("%c",&m); 〃存放輸入 i 的值之后的’\n' if(i==0) break; 〃當i為0時，結束循環(huán)，結束運行 } printf("謝謝使用，再見！ \n\n"); return 0;