單鏈表的基本操作 C語言課程設(shè)計(jì)

1、課程設(shè)計(jì)(論文)題 目 名 稱 單鏈表的基本操作 課 程 名 稱 C語言程序課程設(shè)計(jì) 學(xué) 生 姓 名 學(xué) 號 系 、專 業(yè) 信息工程系、網(wǎng)絡(luò)工程專業(yè) 指 導(dǎo) 教 師 成婭輝 2013年 6月 6 日目 錄1 前言32 需求分析32.1 課程設(shè)計(jì)目的32.2 課程設(shè)計(jì)任務(wù)32.3 設(shè)計(jì)環(huán)境32.4 開發(fā)語言33 分析和設(shè)計(jì)33.1 模塊設(shè)計(jì)33.2 系統(tǒng)流程圖43.3 主要模塊的流程圖64 具體代碼實(shí)現(xiàn)95 課程設(shè)計(jì)總結(jié)125.1 程序運(yùn)行結(jié)果125.2 課程設(shè)計(jì)體會(huì)12參考文獻(xiàn)13致 謝131 前言 我們這學(xué)期學(xué)習(xí)了開關(guān)語句，循環(huán)語句、鏈表、函數(shù)體、指針等的應(yīng)用，我們在完成課程設(shè)計(jì)任務(wù)時(shí)就主要

2、用到這些知識點(diǎn)，本課題是單鏈表的簡單操作，定義四個(gè)子函數(shù)分別用來創(chuàng)建鏈表、輸出鏈表、插入數(shù)據(jù)以及刪除數(shù)據(jù)，主函數(shù)中主要用到開關(guān)語句來進(jìn)行選擇調(diào)用哪個(gè)子函數(shù)，下面就是課程設(shè)計(jì)的主要內(nèi)容。2 需求分析2.1 課程設(shè)計(jì)目的學(xué)生在教師指導(dǎo)下運(yùn)用所學(xué)課程的知識來研究、解決一些具有一定綜合性問題的專業(yè)課題。通過課程設(shè)計(jì)（論文），提高學(xué)生綜合運(yùn)用所學(xué)知識來解決實(shí)際問題、使用文獻(xiàn)資料、及進(jìn)行科學(xué)實(shí)驗(yàn)或技術(shù)設(shè)計(jì)的初步能力，為畢業(yè)設(shè)計(jì)（論文）打基礎(chǔ)。2.2 課程設(shè)計(jì)任務(wù)輸入一組正整數(shù)，以-1標(biāo)志結(jié)束，用函數(shù)實(shí)現(xiàn)：（1）將這些正整數(shù)作為鏈表結(jié)點(diǎn)的data域建立一個(gè)非遞減有序的單鏈表，并輸出該單鏈表；（2）往該鏈表中

3、插入一個(gè)正整數(shù)，使其仍保持非遞減有序，輸出插入操作后的單鏈表；（3）刪除鏈表中第i個(gè)結(jié)點(diǎn)，輸出刪除操作后的單鏈表，i從鍵盤輸入。2.3 設(shè)計(jì)環(huán)境（1）WINDOWS 7系統(tǒng)（2）Visual C+2.4 開發(fā)語言C語言3 分析和設(shè)計(jì)3.1 模塊設(shè)計(jì)定義鏈表結(jié)點(diǎn)類型struct node表示結(jié)點(diǎn)中的信息,信息包括數(shù)據(jù)域data（用于存放結(jié)點(diǎn)中的有用數(shù)據(jù)）以及指針域next（用于存放下一個(gè)結(jié)點(diǎn)的地址），并將鏈表結(jié)點(diǎn)類型名改為NODE。如下所示：typedef struct nodeint data;struct node *next;NODE;定義函數(shù)NODE *create_llist_sort

4、ed()，用來創(chuàng)建非遞減有序帶頭結(jié)點(diǎn)的單鏈表，定義四個(gè)指針NODE*h,*p,*q,*s，頭指針指向第一個(gè)結(jié)點(diǎn)，并且分配空間給頭指針h，使頭指針不為空，*p指向單鏈表中某一結(jié)點(diǎn)，*q指向*p的前驅(qū),*s指向輸入的數(shù)據(jù)，將數(shù)據(jù)逐個(gè)輸入，將輸入的數(shù)據(jù)通過循環(huán)語句不斷進(jìn)行比較，其中先使*q指向*h所指位置，*p指向*h的下一個(gè)位置，不斷將輸入的每一個(gè)數(shù)據(jù)與鏈表中的數(shù)據(jù)相比較，找到插入位置，然后移動(dòng)*p，*q，直到*p為空指針且*s所指數(shù)據(jù)小于等于*p所指數(shù)據(jù)，從而使數(shù)據(jù)有序，最后返回頭指針。詳細(xì)程序見后文中的具體代碼實(shí)現(xiàn)。定義函數(shù)void output()，用來輸出頭指針h所指的單鏈表，因?yàn)榇随湵碛?/p>

5、頭結(jié)點(diǎn)， 所以定義一個(gè)指針NODE *p，*p指向h的下一個(gè)位置，不斷地將*p所指數(shù)據(jù)輸出并且移動(dòng)*p，直到*p為空指針。詳細(xì)程序見后文中的具體代碼實(shí)現(xiàn)。定義函數(shù)void insert(NODE *h, int x)，使元素x插入到單鏈表h中之后鏈表中數(shù)據(jù)仍有序，定義三個(gè)指針NODE *p,*q,*m，*q指向頭指針?biāo)肝恢茫?p指向*q的下一個(gè)位置，*m指向要插入的數(shù)據(jù)x，將數(shù)據(jù)插入鏈表中去后將數(shù)據(jù)不斷進(jìn)行比較，直至*p為空指針且*m所指數(shù)據(jù)小于等于*p所指數(shù)據(jù)，移動(dòng)*p,*q,使數(shù)據(jù)仍然有序。詳細(xì)程序見后文中的具體代碼實(shí)現(xiàn)。定義函數(shù)NODE *del(NODE *h, int i)，用于刪

6、除單鏈表h中第i個(gè)結(jié)點(diǎn)，定義兩個(gè)指針*p，*q，用指針p來從第一個(gè)結(jié)點(diǎn)開始查找需要?jiǎng)h除的結(jié)點(diǎn)，指針q是指針p的前驅(qū)，查找過程中，不斷移動(dòng)指針p，q，直至找到需要?jiǎng)h除的結(jié)點(diǎn)，如果*p為空指針，則表示鏈表中沒有需要?jiǎng)h除的結(jié)點(diǎn)，最后返回頭指針。詳細(xì)程序見后文中的具體代碼實(shí)現(xiàn)。主函數(shù)主要是采用開關(guān)分支語句對幾個(gè)子函數(shù)進(jìn)行調(diào)用。3.2系統(tǒng)模塊流程圖開 始輸出菜單 1N Y輸入n n=1 N Y調(diào)用創(chuàng)建單鏈表函NODE*create_llist_sorted();數(shù)n=3n=2?NY調(diào)用輸出函數(shù)void output(NODE *h)Nn=0?n=4n=4?Y調(diào)用插入函數(shù)void insert(NODE

7、*h, int x);并輸出N結(jié) 束調(diào)用刪除函數(shù)NODE *del(NODE *h, int i)退出Y結(jié)束Y 圖3.1系統(tǒng)模塊流程圖3.3主要模塊的流程圖（1）輸出函數(shù)流程圖（如圖3.2）p=h->nextp!=NULL？N Y輸出p->data p=p->next 圖3.2. 輸出函數(shù)流程圖（2）插入函數(shù)流程圖（如圖3.3）m=(NODE *)malloc(sizeof(NODE);m->data=x; q=h；p=q->next;m->data=x; q=h;p=q->next;q=h;p=q->next;p!=NULL&&

8、m->data>p->dataN Yq=q->next;p=p->next;m->next=p;q->next=m;圖3.3插入函數(shù)流程圖（3）刪除函數(shù)流程圖（如圖3.4）p=h輸入待刪結(jié)點(diǎn)ip!=NULL&&p->data!=i？NYq=p;p=p->next;p=h？NYp=NULL？NNh=h->next;free(p); Yq->next=p->next;free(p);printf("not been findn”)圖3.4刪除函數(shù)流程圖（4）創(chuàng)建單鏈表函數(shù)流程圖（如圖3.5）h=(NO

9、DE *)malloc(sizeof(NODE);h->next=NULL輸入xx!= -1N Ys=(NODE *)malloc(sizeof(NODE) q=h,p=h->next ;s->data=x; s->next=NULL;p!=NULL&&s->data>p->data？NYq->next=ss->next=p;s->next=p;p=p->next,q=q->next輸入x圖3.5創(chuàng)建單鏈表函數(shù)流程圖4 具體代碼實(shí)現(xiàn)/*單鏈表的基本操作*/#include"stdio.h"

10、;#include"math.h"#include"string.h"#include"stdlib.h"typedef struct nodeint data; struct node *next;NODE;/*鏈表結(jié)點(diǎn)類型定義*/*函數(shù)聲明*/NODE *create_llist_sorted();/*建立一個(gè)非遞減有序的帶頭結(jié)點(diǎn)的單鏈表，返回其頭指針*/void output(NODE *h);/*輸出頭指針h所指單鏈表*/void insert(NODE *h, int x);/*將元素x插入到單鏈表h中仍有序*/NODE *

11、del(NODE *h, int i);/*刪除單鏈表h中第i個(gè)結(jié)點(diǎn)*/*主函數(shù)*/void main()NODE *head;int x,i,n; printf("*單鏈表的基本操作*n"); /*輸出菜單*/ printf(" 1. 建立n"); printf(" 2. 輸出n"); printf(" 3. 插入n"); printf(" 4. 刪除n"); printf(" 0. 退出n"); while(1) printf("請選擇："); sca

12、nf("%d",&n); switch(n) case 1:head=create_llist_sorted();break; case 2:output(head);break; case 3:printf("please input inserted data:");scanf("%d",&x); insert(head,x);output(head);break; case 4:printf("please input deleted location:"); scanf("%d&q

13、uot;,&i);del(head,i);output(head);break; case 0:exit(0); default:printf("輸入錯(cuò)誤，請重新選擇!n"); /*子函數(shù)*/NODE *create_llist_sorted()/*建立一個(gè)非遞減有序的帶頭結(jié)點(diǎn)的單鏈表，返回其頭指針*/int x;NODE *h,*p,*q,*s; /*p指向單鏈表中某一結(jié)點(diǎn)，q指向*p的前驅(qū)*/ h=(NODE *)malloc(sizeof(NODE);h->next=NULL; scanf("%d",&x); while(x!

14、=-1) s=(NODE *)malloc(sizeof(NODE); s->data=x; s->next=NULL; for(q=h,p=h->next;p!=NULL&&s->data>p->data;p=p->next,q=q->next);/*不斷比較，找到插入位置。注意：循環(huán)條件p!=NULL必須先判斷，即放在&&左邊*/ q->next=s;s->next=p; scanf("%d",&x); return h;void output(NODE *h)/*輸出頭

15、指針h所指單鏈表*/ NODE *p;p=h->next;while(p!=NULL)printf("%d ",p->data); p=p->next;printf("n");NODE *del(NODE *h, int i)/*刪除單鏈表h中第i個(gè)結(jié)點(diǎn)*/ NODE*p,*q; p=h;while(p!=NULL&&p->data!=i)q=p;p=p->next;if(p=h)h=h->next;free(p);else if(p=NULL)printf("not been findn&q

16、uot;);elseq->next=p->next;free(p);return(h);void insert(NODE *h, int x)/*將元素x插入到單鏈表h中仍有序*/ NODE *p,*q,*m;m=(NODE *)malloc(sizeof(NODE); m->data=x; q=h;p=q->next;while(p!=NULL&&m->data>p->data)q=q->next; p=p->next;m->next=p; q->next=m; 5 課程設(shè)計(jì)總結(jié)5.1 程序運(yùn)行結(jié)果 輸入源程序

17、后，先進(jìn)行調(diào)試，經(jīng)調(diào)試無錯(cuò)誤后開始運(yùn)行，屏幕上會(huì)顯示菜單，會(huì)出現(xiàn)提示語“請選擇”，選擇1即建立了一個(gè)鏈表，然后鍵入一組正整數(shù)，以-1標(biāo)志結(jié)束，按回車鍵；繼續(xù)選擇2即執(zhí)行輸出函數(shù)，按回車鍵后屏幕上會(huì)輸出之前鍵入的數(shù)據(jù)，按回車鍵；繼續(xù)選擇3即執(zhí)行插入函數(shù)，按回車鍵后鍵入一個(gè)需要插入的數(shù)據(jù)，按回車鍵屏幕上輸出插入數(shù)據(jù)后的一組新數(shù)據(jù)，按回車鍵；繼續(xù)選擇4即執(zhí)行刪除函數(shù)，按回車鍵后鍵入一個(gè)需要?jiǎng)h除的數(shù)的所在的節(jié)點(diǎn)，繼續(xù)按回車鍵屏幕上會(huì)輸出刪除節(jié)點(diǎn)后的一組新數(shù)據(jù)，按回車鍵；繼續(xù)選擇0即退出程序，運(yùn)行結(jié)果如下圖所示 圖5.1運(yùn)行結(jié)果示意圖5.2 課程設(shè)計(jì)體會(huì) 總體來說，這個(gè)課程設(shè)計(jì)的優(yōu)勢在于條理較為清晰，內(nèi)

18、容比較充實(shí)，源程序也是比較清晰明了的，方便使用，不足之處在于流程圖不夠規(guī)范整潔，其他地方都還有待提高。我覺得課程設(shè)計(jì)中最核心的部分是編程，在編程的過程中，最關(guān)鍵的是要有扎實(shí)的知識功底，最重要的是需要細(xì)心和耐心。擁有扎實(shí)的知識功底，看到課題，我們便能靈活運(yùn)用老師所教的知識，較為清晰地、快速地想出大概的程序框架，然后再正式地進(jìn)行編程。在編程時(shí)，細(xì)心是必要的，因?yàn)橐粋€(gè)小小的錯(cuò)誤便會(huì)導(dǎo)致整個(gè)程序不能正常運(yùn)行，便要進(jìn)行一系列的復(fù)雜的調(diào)試工作，所以細(xì)心能避免一些不必要的麻煩。同時(shí)，耐心也是必不可少的，當(dāng)我們在編程過程中可能會(huì)遇到一些困惑和難點(diǎn)以及錯(cuò)誤，需要我們有一定的耐心堅(jiān)持下去，不輕言放棄，不斷地進(jìn)行調(diào)試和運(yùn)行，有不懂的地方和同學(xué)討論，向老師請教，直到使程序正常運(yùn)行。 通過這次的課程設(shè)計(jì)，我收獲了許多，了解了如何正確規(guī)范地進(jìn)行課程設(shè)計(jì)，為以后能快速高效進(jìn)行課程設(shè)計(jì)打下一定的基礎(chǔ)。參考文獻(xiàn)1黃同成，周紅波程序設(shè)計(jì)基礎(chǔ)教程（C語言）M湖南人民出版社，20112黃同成，黃磊程序設(shè)計(jì)實(shí)踐教程（C語言）M湖南人民出版社，20113譚浩強(qiáng)C程序設(shè)計(jì)（第三版）M北京：清華大學(xué)出版社，2005致 謝首先，我想要感謝編寫C語言相關(guān)書籍的各位老師以及我們的授課老師，讓我們了解并掌握了有關(guān)C語言的大量的基礎(chǔ)知識，讓我們有足夠的知識儲(chǔ)備和扎