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

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、程序所能達到的功能：根據(jù)提示輸入數(shù)據(jù)，然后根據(jù)數(shù)據(jù)元素類型的不同，將其

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

3、提示，調用其它的各個函數(shù)；建立鏈表并輸入數(shù)據(jù)模塊Create(LinkList *&L)輸出鏈表中的數(shù)據(jù)模塊Printf(LinkList *L)將原鏈表拆分成三個鏈表的模塊：Fun(LinkList *hd,LinkList *ha,LinkList *hb,LinkList *hc）程序流程如下所示開 始Create 函數(shù)Fun 函數(shù)Printf 函數(shù)是否結束是結 束三 詳細設計（一）元素類型、結點類型和指針類型typedef struct LNodechar data;struct LNode *next;LinkList;（二）每個模塊的分析1、主程序模塊分析int main()否Li

4、nkList *hd,*ha,*hb,*hc;/定義四個頭結點指針， *hd 代表待拆分鏈表， *ha,*hb 和 *hc 分別代表字母 ,數(shù)字和其它類型的鏈表ha=(LinkList *)malloc(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 的值之后的回車while(1)Creat

5、e(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ù)字類型）printf(n其它 :);/提示輸出的鏈表中數(shù)據(jù)為其它類型Printf(hc);/調用輸出鏈表元素的函數(shù)，輸出hc 鏈表中的數(shù)據(jù) (其它類型）printf(n);printf(n是否結束scanf(%d,&i);

6、?是,輸入0;否 ,輸入1n);/ 提示是否終止本程序的運行/ 輸入整數(shù)iprintf(n);if(i=1) scanf(%c,&m);/ 存放輸入i 的值之后的回車if(i=0) break;/ 當i 為0 時，結束循環(huán)，結束運行printf(謝謝使用，再見! nn);return 0;2、建立鏈表和輸入數(shù)據(jù)模塊分析void Create(LinkList *&L)LinkList *s,*r;L=(LinkList *)malloc(sizeof(LinkList);L-next=NULL;r=L;printf( 輸入鏈表中的各元素:n);while(1)/創(chuàng)建頭結點/r 始終指向終端結點

7、,開始時指向頭結點/用于提示字符串的輸入s=(LinkList *)malloc(sizeof(LinkList);/創(chuàng)建新結點scanf(%c,&s-data);r-next=s;/輸入新節(jié)點的數(shù)據(jù)/將 *s 插入 *r 之后r=s;if(s-data=n) break;/若輸入回車，則字符串的輸入結束r-next=NULL;/終端結點next 域置NULL3、輸出鏈表元素模塊分析void Printf(LinkList *L)LinkList *p=L-next;while (p!=NULL)printf(%c,p-data);/當指針p 所指結點next域不為NULL時，將該結點的p=p

8、-next;數(shù)據(jù)輸出/p 指針向后移動4、拆分鏈表模塊分析void Fun(LinkList *hd,LinkList *ha,LinkList *hb,LinkList *hc)LinkList *p=hd-next,*ra,*rb,*rc;/ 定義三個指向鏈表結點的指針ra=ha;rb=hb;rc=hc;while(p!=NULL)/ra 始終指向ha 的末尾結點/ra 始終指向ha 的末尾結點/ra 始終指向ha 的末尾結點/當指針 p 所指結點的指針域不為NULL時，執(zhí)行以下循環(huán)過程if(p-data=A&p-datadata=a&p-datanext=p;ra=p;p=p-next;

9、/ 將 *p 鏈接到/p 指針后移ha 單鏈表末尾elseif(p-data=0&p-datanext=p;rb=p;/將 *p鏈接到ha 單鏈表末尾p=p-next;/p 指針后移else/數(shù)據(jù)為其它類型的情況rc-next=p;rc=p;p=p-next;/將 *p 鏈接到/p 指針后移ha 單鏈表末尾ra-next=NULL;rb-next=NULL;rc-next=NULL;/將三個新鏈表尾結點next 域置空四 使用說明、測試分析及結果1、程序使用說明：（1）本程序運行環(huán)境為Visual C+ 6.0；（2）根據(jù)界面提示進行操作，每次從鍵盤輸入數(shù)據(jù)后按回車結束。2、測試結果與分析：根

10、據(jù)提示，當輸入為時，輸出結果如下所示字母 :Li數(shù)字 :900211其它 :*?() 是否結束 ?是 , 輸入0; 否, 輸入10謝謝使用，再見!3、調試過程中遇到的問題及解決方法當代碼編寫完成后， 編譯過程出現(xiàn)了很多小錯誤， 比如語句末尾漏掉分號， 賦值運算符與等號混淆等，但這些問題很快發(fā)現(xiàn)并及時糾正；另外， 在運行時出現(xiàn)可以輸入字符串但卻無法正常輸出結果的現(xiàn)象， 在進一步分析所編寫的代碼后，發(fā)現(xiàn)函數(shù)調用過程不對，在參考程序設計教材后，解決了這一問題。4、運行界面五、實驗總結本次實驗， 我進行了預習，但是預習過程不夠認真，忽略了很多細節(jié)，以致于我用了大約一個小時的時間編寫完代碼，但是對代碼的

11、修改卻花費了大量時間，沒有當堂完成。 課后，我參考了C程序設計的教材并很快發(fā)現(xiàn)自己的問題，又花費了半個小時，才最終修改正確。在最開始編寫程序時，因為長時間沒有應用C 語言， 所以部分基本知識有些生疏，以致于發(fā)生了很多低級的錯誤，比如忽略了字符型數(shù)據(jù)和整型數(shù)據(jù)的區(qū)別，在輸入字符串時以空格分隔各其它字符，導致得不到輸出結果，不過這些錯誤很快糾正。另外，在最初的程序中，通過輸入字符串中字符的個數(shù)然后再輸入字符串，最后輸出結果，因為要輸入字符串中字符的個數(shù)，所以當字符串較長時操作起來不方便。所以我對其進行了修改， 在函數(shù)中判斷是否有回車的輸入，以回車直接結束字符串的輸入，不必再輸入字符個數(shù)，從而操作起

12、來更加方便。我還在主函數(shù)中添加了一個循環(huán)，以輸入0或 1判斷是否繼續(xù)程序的運行，使之更加人性化，但是在此也遇到一個問題。當輸入1時，表示不結束，但是輸入1之后以回車表示輸入的結束，因為回車表示字符串輸入的結束，所以導致之后的操作不能正常進行，為解決這一問題，我在主函數(shù)中重新定義了一個字符型數(shù)據(jù)，以吸收回車。最終程序得以正常運行。本次實驗， 我很感謝老師和同學對我的指點。通過本次實驗， 對鏈表結構有了更深層次的認識，對一些細節(jié)更加理解，收獲了很多。教師評語：實驗成績：指導教師簽名：批閱日期：代碼：# include# include/* 定義單鏈表結點類型*/typedef struct LNo

13、dechar data;/每個結點中存儲的數(shù)據(jù)為字符型struct 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(sizeof(LinkList);/創(chuàng)建新結點s

14、canf(%c,&s-data);/輸入新節(jié)點的數(shù)據(jù)r-next=s;r=s;/將 *s 插入*r 之后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-data);/當指針p 所指結點next 域不為NULL 時，將該結點的數(shù)據(jù)輸出p=p-next;/p指針向后移動/* 拆分鏈表的函數(shù) */void Fun(LinkList *hd,Link

15、List *ha,LinkList *hb,LinkList *hc)LinkList *p=hd-next,*ra,*rb,*rc;/定義三個指向鏈表結點的指針ra=ha;/ra 始終指向ha 的末尾結點rb=hb;/ra 始終指向ha 的末尾結點rc=hc;/ra始終指向ha 的末尾結點while(p!=NULL)/當指針p 所指結點的指針域不為NULL 時，執(zhí)行以下循環(huán)過程if(p-data=A&p-datadata=a&p-datanext=p;ra=p;/將 *p 鏈接到ha 單鏈表末尾p=p-next;/p指針后移elseif(p-data=0&p-datanext=p;rb=p;

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

17、=(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 的值之后的 nwhile(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);/調用