數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---鏈表的創(chuàng)建、插入、刪除、修改

1、<p><b>　　課程設(shè)計報告</b></p><p>　　課程設(shè)計題目：鏈表的創(chuàng)建、插入、刪除、修改</p><p><b>　　學(xué)生姓名 </b></p><p>　　專 業(yè) 信息工程</p><p>　　班 級 </p><p&

2、gt;　　學(xué) 號 </p><p><b>　　指導(dǎo)教師 </b></p><p><b>　　2013年1月9日</b></p><p><b>　　一、實驗題目：</b></p><p>　　實現(xiàn)鏈表的創(chuàng)建、插入、刪除和修改</p>&l

3、t;p>　　任務(wù)：實現(xiàn)鏈表的創(chuàng)建、插入、刪除、修改和輸出 </p><p>　　要求：建立一個簡單的人機對話，創(chuàng)建、插入、刪除、修改和輸出功能可以根據(jù)需要選擇使用。</p><p>　　二、實驗時間、地點：</p><p>　　2011-12-26~ 2011-12-30、信工樓302</p><p><b>　　三、實驗?zāi)康?/p>

4、</b></p><p>　　本次課程設(shè)計的主要目的是綜合運用所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識解決一個比較實際問題，側(cè)重對鏈表、數(shù)組、字符串、圖、樹等相關(guān)內(nèi)容的綜合應(yīng)用，使同學(xué)們能進一步熟悉掌握數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識，進一步提升自己的解決問題和編程調(diào)試能力，為后續(xù)專業(yè)課程的學(xué)習(xí)打下良好的基礎(chǔ)。</p><p><b>　　四、實驗要求</b></p><

5、p>　　1. 了解數(shù)據(jù)結(jié)構(gòu)及其分類、數(shù)據(jù)結(jié)構(gòu)與算法的密切關(guān)系； 2. 熟悉各種基本數(shù)據(jù)結(jié)構(gòu)及其操作，學(xué)會根據(jù)實際問題來選擇數(shù)據(jù)結(jié)構(gòu)； 3. 掌握設(shè)計算法的步驟和分析方法； 4. 掌握數(shù)據(jù)結(jié)構(gòu)在排序和查找等常用算法中的應(yīng)用。</p><p><b>　　5. 獨立完成；</b></p><p>　　6． 每個人需按照選題規(guī)則確定好自己的題目（注意不是多人完成

6、一題，每人獨立完成一題），不得以任何理由選擇其他的題目，當然在完成自己的題目之后根據(jù)個人興趣可以繼續(xù)選做其他的題目；</p><p>　　7．課程設(shè)計完成后嚴格按照報告格式撰寫課程設(shè)計報告，并于結(jié)束后的第三天上交到學(xué)習(xí)委員統(tǒng)一交給老師；</p><p>　　8．課程設(shè)計的成績由兩部分組成：程序檢查成績（40％，每個功能占程序分的20%）＋報告檢查成績（40％）＋平時考核（20%）</

7、p><p><b>　　五、實現(xiàn)思路</b></p><p>　　鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，他的特點是用一組任意的存儲單元（可以是連續(xù)的，也可以是不連續(xù)的）存放數(shù)據(jù)元素。</p><p>　　鏈表中每一個元素成為“結(jié)點”，每一個結(jié)點都是由數(shù)據(jù)域和指針域組成的，每個結(jié)點中的指針域指向下一個結(jié)點。Head是“頭指針”，表示鏈表的開始，用來指向第一個結(jié)點，

8、而最后一個指針的指針域為NULL(空地址)，表示鏈表的結(jié)束。</p><p>　　可以看出鏈表結(jié)構(gòu)必須利用指針才能實現(xiàn)，即一個結(jié)點中必須包含一個指針變</p><p>　　量，用來存放下一個結(jié)點的地址。</p><p>　　實際上，鏈表中的每個結(jié)點可以用若干個數(shù)據(jù)和若干個指針。結(jié)點中只有一個指針的鏈表稱為單鏈表，這是最簡單的鏈表結(jié)構(gòu)。</p><

9、p>　　再c++中實現(xiàn)一個單鏈表結(jié)構(gòu)比較簡單。例如，可定義單鏈表結(jié)構(gòu)的最簡單形式如下</p><p>　　class link</p><p><b>　　{</b></p><p><b>　　public:</b></p><p>　　elemtype data;</p>&

10、lt;p>　　link *next;</p><p><b>　　};</b></p><p>　　這里用到了結(jié)構(gòu)體類型。其中，*next是指針域，用來指向該結(jié)點的下一個結(jié)點；Data是一個整形變量，用來存放結(jié)點中的數(shù)據(jù)。當然，Data可以是任何數(shù)據(jù)類型，包括結(jié)構(gòu)體類型或類類型。</p><p>　　在此基礎(chǔ)上，我們在定義一個鏈表類lis

11、t，其中包含鏈表結(jié)點的插入，刪除，輸出等功能的成員函數(shù)。</p><p>　　void print(link*head) ;//鏈表結(jié)點的輸出</p><p>　　link*Locate(link*head,elemtype x);//鏈表的的查詢</p><p>　　void insert(link*head,elemtype x,elemtype y);//鏈表

12、結(jié)點的插入</p><p>　　void deletel(link*head,elemtype x);//鏈表結(jié)點的刪除</p><p><b>　　v</b></p><p>　　oid change(link*p,elemtype x,elemtype y)；//鏈表的修改</p><p>　　由于鏈表中的各個結(jié)點是

13、由指針鏈接在一起的，其存儲單元文筆是連續(xù)的，因此，對其中任意結(jié)點的地址無法向數(shù)組一樣，用一個簡單的公式計算出來，進行隨機訪問。只能從鏈表的頭指針（即head）開始，用一個指針p先指向第一個結(jié)點，然后根據(jù)結(jié)點p找到下一個結(jié)點。以此類推，直至找到所要訪問的結(jié)點或到最后一個結(jié)點（指針為空）為止。</p><p><b>　　流程圖：</b></p><p><b>

14、;　　Public:</b></p><p><b>　　N</b></p><p><b>　　Y</b></p><p><b>　　N</b></p><p><b>　　Y</b></p><p><b&g

15、t;　　N</b></p><p><b>　　Y</b></p><p><b>　　N</b></p><p><b>　　Y</b></p><p><b>　　N</b></p><p><b>　　Y

16、</b></p><p><b>　　N</b></p><p><b>　　Y</b></p><p><b>　　主函數(shù)流程圖</b></p><p><b>　　N</b></p><p><b>　　Y

17、</b></p><p><b>　　N</b></p><p><b>　　3…</b></p><p><b>　　4…</b></p><p><b>　　5…</b></p><p><b>　　6…&

18、lt;/b></p><p><b>　　7…</b></p><p><b>　　N</b></p><p><b>　　Y</b></p><p><b>　　…….</b></p><p><b>　　…….&

19、lt;/b></p><p><b>　　…….</b></p><p><b>　　六、實現(xiàn)過程</b></p><p>　　#include<iostream.h></p><p>　　#include<windows.h></p><p>

20、　　#include<stdlib.h></p><p>　　#define elemtype int</p><p>　　class link</p><p><b>　　{</b></p><p><b>　　public:</b></p><p>　　ele

21、mtype data;</p><p>　　link *next;</p><p><b>　　};</b></p><p>　　class linklist</p><p><b>　　{</b></p><p>　　protected:</p><p&

22、gt;　　link*head;</p><p><b>　　public:</b></p><p>　　link*rcreat()</p><p><b>　　{</b></p><p>　　link*s,*p,*r;</p><p>　　elemtype i;</p&

23、gt;<p>　　cout<<"輸入多個結(jié)點數(shù)值（用空格分隔），為0是算法結(jié)束";</p><p><b>　　cin>>i;</b></p><p>　　p=r=new link;</p><p>　　p->next=NULL;</p><p><b

24、>　　while(i)</b></p><p><b>　　{</b></p><p>　　s=new link;</p><p>　　s->data=i;</p><p>　　r->next=s;</p><p><b>　　r=s;</b>&

25、lt;/p><p><b>　　cin>>i;</b></p><p><b>　　}</b></p><p>　　r->next=NULL;</p><p><b>　　return p;</b></p><p><b>　　}

26、</b></p><p>　　void print(link*head)</p><p><b>　　{</b></p><p><b>　　link*p;</b></p><p>　　p=head->next;</p><p>　　while(p->

27、next!=NULL)</p><p><b>　　{</b></p><p>　　cout<<p->data<<"->";</p><p>　　p=p->next;</p><p><b>　　}</b></p><

28、p>　　cout<<p->data;</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　link*Locate(link*head,int x)</p><p><b>　　{</b></p>&

29、lt;p><b>　　link*p;</b></p><p><b>　　p=head;</b></p><p><b>　　int j=0;</b></p><p>　　while((p!=NULL)&&(j<x))</p><p>　　{ p=p

30、->next;j++;}</p><p><b>　　return p;</b></p><p><b>　　}</b></p><p>　　void deletel(link*head,elemtype x)</p><p><b>　　{</b></p>

31、<p>　　link*p,*q;</p><p><b>　　q=head;</b></p><p>　　p=head->next;</p><p>　　while((p!=NULL)&&(p->data!=x))</p><p><b>　　{</b><

32、;/p><p><b>　　q=p;</b></p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　if(p==NULL)cout<<"要刪除的結(jié)點不存在";</p><p><b>

33、　　else</b></p><p><b>　　{</b></p><p>　　q->next=p->next;</p><p>　　delete(p);</p><p><b>　　}</b></p><p><b>　　}</b&

34、gt;</p><p>　　void insert(link*head,int x,elemtype y)</p><p><b>　　{</b></p><p>　　link*p,*s;</p><p>　　s=new link;</p><p>　　s->data=y;</p>

35、;<p>　　if(head->next==NULL)</p><p><b>　　{</b></p><p>　　head->next=s;</p><p>　　s->next=NULL;</p><p><b>　　}</b></p><p&g

36、t;　　p=Locate(head,x);</p><p>　　if(p==NULL)</p><p>　　cout<<"插入位置非法";</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　

37、　s->next=p->next;</p><p>　　p->next=s;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void change(link*p,elemtype x,elemtype y)</p>

38、<p><b>　　{</b></p><p><b>　　link*q;</b></p><p>　　q=p->next;</p><p>　　while(q!=NULL)</p><p><b>　　{</b></p><p>　　

39、if(q->data==x)q->data=y;</p><p>　　q=q->next;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int count(link*h)</p><p><b&g

40、t;　　{</b></p><p>　　link*p;int n=0;</p><p>　　p=h->next;</p><p>　　while(p!=NULL)</p><p><b>　　{</b></p><p>　　n++;p=p->next;</p>

41、<p><b>　　}</b></p><p><b>　　return n;</b></p><p><b>　　}</b></p><p><b>　　};</b></p><p>　　void main()</p><

42、p><b>　　{</b></p><p>　　int n,act;</p><p><b>　　char m;</b></p><p>　　elemtype x,y;</p><p>　　link*p,*q; linklist a;</p><p>　　p=a.rcr

43、eat();</p><p>　　a.print(p);</p><p>　　loop1:cout<<"請選擇要進行的操作：\n e:查找； f:刪除； g:插入； h:修改； i:統(tǒng)計; q:退出; c:清屏。\n";</p><p><b>　　cin>>m;</b></p

44、><p>　　if(m=='e') //根據(jù)提示選擇操作</p><p><b>　　{act=1;}</b></p><p>　　if(m=='f')</p><p><b>　　{act=2;}</b></p><p>　

45、　if(m=='g')</p><p><b>　　{act=3;}</b></p><p>　　if(m=='h')</p><p><b>　　{act=4;}</b></p><p>　　if(m=='i')</p><p&g

46、t;<b>　　{act=5;}</b></p><p>　　if(m=='q')</p><p><b>　　{act=6;}</b></p><p>　　if(m=='c')</p><p><b>　　{act=7;}</b></p&

47、gt;<p>　　switch(act)</p><p><b>　　{</b></p><p><b>　　case 1:</b></p><p>　　cout<<"請輸入要查找的元素值";</p><p><b>　　cin>>

48、x;</b></p><p>　　q=a.Locate(p,x);</p><p>　　if(q==NULL)cout<<x<<"不在表中。找不到！"<<endl;</p><p>　　else cout<<x<<"在表中，已找到！"<<end

49、l;</p><p>　　goto loop1;</p><p><b>　　break;</b></p><p>　　case 2:cout<<"請輸入要刪除的元素";</p><p><b>　　cin>>y;</b></p><

50、p>　　a.deletel(p,y);</p><p>　　a.print(p);</p><p>　　goto loop1;</p><p><b>　　break;</b></p><p><b>　　case 3:</b></p><p>　　cout<&l

51、t;"請輸入插入位置的元素（將待插元素插入到它的后面）";</p><p><b>　　cin>>x;</b></p><p>　　cout<<"請輸入待插元素值";</p><p><b>　　cin>>y;</b></p><

52、;p>　　a.insert(p,x,y);</p><p>　　a.print(p);</p><p>　　goto loop1;</p><p><b>　　break;</b></p><p>　　case 4:cout<<"請輸入要修改前后的元素值";</p>&

53、lt;p>　　cin>>x>>y;</p><p>　　a.change(p,x,y);</p><p>　　a.print(p);</p><p>　　goto loop1;</p><p><b>　　break;</b></p><p>　　case 5:n=a

54、.count(p);</p><p>　　cout<<"鏈表中結(jié)點個數(shù)為："<<n<<endl;</p><p>　　goto loop1;</p><p><b>　　break;</b></p><p>　　case 6:system("CLS&quo

55、t;); //清屏</p><p>　　goto loop2;</p><p><b>　　break;</b></p><p>　　case 7:system("CLS"); //清屏</p><p>　　a.print(p);</p><p>　　goto loop1;&l

56、t;/p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　loop2:;</b></p><p><b>　　}</b></p><p>　　七、實驗總結(jié)（分析程序的得與失）

57、</p><p>　　1、經(jīng)過運行本程序能夠進行鏈表的創(chuàng)建、插入、刪除、修改、統(tǒng)計等功能，已具備鏈表試驗的功能，基本達到了題目的要求。</p><p>　　2、在編寫程序的過程中，對字符的判斷做標記，用switch語句選擇運用，使結(jié)構(gòu)更加清晰，能夠用goto語句進行循環(huán)。使程序的可執(zhí)行性更強。</p><p>　　3、本程序還是有一定缺陷，比如運行界面不夠美觀、但基

58、本達到了人機交互的功能達到要求</p><p>　　4、對本程序自我感覺人機交互做的比較好，能夠做到根據(jù)選擇進行操作，主要依靠循環(huán)進行實現(xiàn)，同時我也加入了清屏功能，使操作更加人性化。</p><p>　　5、本程序的但還是比較單一，功能不是很完善，可以對界面進行設(shè)計，是其更加美觀。</p><p><b>　　八、心得體會</b></p&

59、gt;<p>　　課程設(shè)計是培養(yǎng)學(xué)生綜合運用所學(xué)知識，發(fā)現(xiàn)，提出，分析和解決實際問題，鍛煉實踐能力的重要環(huán)節(jié)，是對學(xué)生實際工作能力的具體訓(xùn)練和考察過程。通過本次為期一周的課程設(shè)計課，我有很多感觸，從我拿到題目開始到完全做出程序，我經(jīng)歷了一個波折的一周，但是這周我受益匪淺，明白把理論用到實踐中的不容易。</p><p>　　這是第二次做C的課程設(shè)計，比第一次稍微好一點，遇到問題都自己花時間去查找資料，