題目1線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)1報(bào)告.docVIP

理學(xué)院課程設(shè)計(jì)說(shuō)明書(shū)課 程 名 稱(chēng): 數(shù)據(jù)結(jié)構(gòu)與算法A設(shè)計(jì)實(shí)踐課 程 代 碼: 6015059 題 目 一: 線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)1 年級(jí)/專(zhuān)業(yè)/班: 2013/信息與計(jì)算科學(xué)/2 學(xué) 生 姓 名: 劉凱 學(xué) 號(hào): 3120130902212 開(kāi) 始 時(shí) 間: 2015 年 12 月 28 日完 成 時(shí) 間: 2016 年 1 月 10 日課程設(shè)計(jì)成績(jī)：學(xué)習(xí)態(tài)度及平時(shí)成績(jī)（30）技術(shù)水平與實(shí)際能力（20）創(chuàng)新（5）說(shuō)明書(shū)撰寫(xiě)質(zhì)量（45）總 分（100）指導(dǎo)教師簽名： 年 月 日 數(shù)據(jù)結(jié)構(gòu)與算法A設(shè)計(jì)實(shí)踐任務(wù)書(shū)學(xué)院名稱(chēng)： 理學(xué)院 課程代碼：_ 6015059_專(zhuān) 業(yè)： 信科 年 級(jí)： 2013 一、設(shè)計(jì)題目 線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)1（限最多1人完成）二、主要內(nèi)容實(shí)現(xiàn)一些線(xiàn)性表的基本操作。三、具體要求及提交的材料（1）動(dòng)態(tài)地建立單鏈表,實(shí)現(xiàn)插入元素、刪除元素、查詢(xún)、求表長(zhǎng)度；（2）建兩個(gè)有序的單鏈表LA和LB，實(shí)現(xiàn)合并成LC，要求分LC中有和無(wú)重復(fù)值兩種情況的實(shí)現(xiàn)；（3）求兩鏈LA和LB兩鏈元素的交集LD。（4）靜態(tài)鏈表的實(shí)現(xiàn)：使用數(shù)組實(shí)現(xiàn)單向鏈表的建立、插入元素、刪除元素。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫(xiě)明；必須上機(jī)調(diào)試通過(guò)l按數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)大綱中的要求完成課程設(shè)計(jì)報(bào)告格式。設(shè)計(jì)結(jié)束后，每個(gè)學(xué)生必須上交的材料有：1 課程設(shè)計(jì)報(bào)告打印稿一份 2課程設(shè)計(jì)的源代碼電子文檔一份四、主要技術(shù)路線(xiàn)提示合并采用教材相關(guān)的現(xiàn)成算法。注意各種算法的性能比較。五、進(jìn)度安排共計(jì)兩周時(shí)間，建議進(jìn)度安排如下：1. 選題，應(yīng)該在上機(jī)實(shí)驗(yàn)之前完成2. 需求分析、概要設(shè)計(jì)可分配4學(xué)時(shí)完成3. 詳細(xì)設(shè)計(jì)可分配4學(xué)時(shí)4. 調(diào)試和分析可分配10學(xué)時(shí)5. 學(xué)時(shí)的機(jī)動(dòng)，可提前安排部分提前結(jié)束任務(wù)的學(xué)生答辯六、 推薦參考資料1. 馮博琴 等編著，軟件技術(shù)基礎(chǔ)（修改版），西安交通大學(xué)出版社，19972. 嚴(yán)蔚敏 等著，數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社，20033. 李蕓芳 等著，軟件技術(shù)基礎(chǔ)（第二版），清華大學(xué)出版社，20004. 徐孝凱 等著，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述），清華大學(xué)出版社，2004指導(dǎo)教師 簽名日期 年 月 日系 主 任 審核日期 年 月 日目錄摘要- 3 -1 引言- 4 -1.1問(wèn)題的提出- 4 -1.2 C/C+語(yǔ)言- 4 -1.3 C/C+語(yǔ)言發(fā)展過(guò)程- 5 -1.4任務(wù)與分析- 5 -2 設(shè)計(jì)方案- 6 -2.1 步驟- 6 -2.2 設(shè)計(jì)流程圖- 6 -3 程序演示- 7 -3.1 編譯- 7 -3.2 運(yùn)行結(jié)果- 7 -4 結(jié)論- 12 -參考資料：- 13 -附錄：源代碼- 14 -摘要線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰，因此可以隨機(jī)存取表中任一元素，他的存儲(chǔ)位置可用一個(gè)簡(jiǎn)單、直觀的公式來(lái)表示。然而，從另一方面來(lái)看，這個(gè)特點(diǎn)也鑄成了這種存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)：在作插入或刪除操作時(shí)，需要移動(dòng)大量的元素。線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒(méi)有順序存儲(chǔ)結(jié)構(gòu)所具有的弱點(diǎn)。關(guān)鍵詞：鏈?zhǔn)酱鎯?chǔ)，插入，刪除1 引言 1.1問(wèn)題的提出線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒(méi)有順序存儲(chǔ)結(jié)構(gòu)所具有的弱點(diǎn)，但是怎么表示和實(shí)現(xiàn)一些線(xiàn)性表的基本操作呢？1.2 C/C+語(yǔ)言C語(yǔ)言是在70年代初問(wèn)世的。一九七八年由美國(guó)電話(huà)電報(bào)公司(AT&T)貝爾實(shí)驗(yàn)室正式發(fā)表了C語(yǔ)言。同時(shí)由B.W.Kernighan和D.M.Ritchit合著了著名的“THE C PROGRAMMING LANGUAGE”一書(shū)。通常簡(jiǎn)稱(chēng)為K&R，也有人稱(chēng)之為K&R標(biāo)準(zhǔn)。但是，在K&R中并沒(méi)有定義一個(gè)完整的標(biāo)準(zhǔn)C語(yǔ)言，后來(lái)由美國(guó)國(guó)家標(biāo)準(zhǔn)學(xué)會(huì)在此基礎(chǔ)上制定了一個(gè)C 語(yǔ)言標(biāo)準(zhǔn)，于一九八三年發(fā)表。通常稱(chēng)之為ANSI C。C語(yǔ)言是一種結(jié)構(gòu)化語(yǔ)言。它層次清晰，便于按模塊化方式組織程序，易于調(diào)試和維護(hù)。C語(yǔ)言的表現(xiàn)能力和處理能力極強(qiáng)。它不僅具有豐富的運(yùn)算符和數(shù)據(jù)類(lèi)型，便于實(shí)現(xiàn)各類(lèi)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。它還可以直接訪(fǎng)問(wèn)內(nèi)存的物理地址，進(jìn)行位(bit)一級(jí)的操作。由于C語(yǔ)言實(shí)現(xiàn)了對(duì)硬件的編程操作，因此C語(yǔ)言集高級(jí)語(yǔ)言和低級(jí)語(yǔ)言的功能于一體。既可用于系統(tǒng)軟件的開(kāi)發(fā)，也適合于應(yīng)用軟件的開(kāi)發(fā)。此外，C語(yǔ)言還具有效率高，可移植性強(qiáng)等特點(diǎn)。因此廣泛地移植到了各類(lèi)各型計(jì)算機(jī)上，從而形成了多種版本的C語(yǔ)言。C語(yǔ)言既有高級(jí)語(yǔ)言的特點(diǎn)，又具有匯編語(yǔ)言的特點(diǎn)；既是一個(gè)成功的系統(tǒng)設(shè)計(jì)語(yǔ)言，有時(shí)一個(gè)使用的程序設(shè)計(jì)語(yǔ)言；既能用來(lái)編寫(xiě)不依賴(lài)計(jì)算機(jī)硬件的應(yīng)用程序，又能用來(lái)編寫(xiě)各種系統(tǒng)程序；是一種受歡迎、應(yīng)用廣泛的程序設(shè)計(jì)語(yǔ)言。目前主要的C語(yǔ)言版本有：Microsoft Visual C+；Borland Turbo C+1；AT&T C。這些C語(yǔ)言版本不僅實(shí)現(xiàn)了ANSI C標(biāo)準(zhǔn)，而且在此基礎(chǔ)上各自作了一些擴(kuò)充，使之更加方便、完美。在C的基礎(chǔ)上，一九八三年又由貝爾實(shí)驗(yàn)室的Bjarne Strou-strup推出了C+。 C+進(jìn)一步擴(kuò)充和完善了C語(yǔ)言，成為一種面向 對(duì)象的程序設(shè)計(jì)語(yǔ)言。C+目前流行的集成開(kāi)發(fā)環(huán)境最新版本是Borland C+4.5,Symantec C+6.1,和Microsoft VisualC+ 2012。C+提出了一些更為深入的概念，它所支持的這些面向?qū)ο蟮母拍钊菀讓?wèn)題空間直接地映射到程序空間，為程序員提供了一種與傳統(tǒng)結(jié)構(gòu)程序設(shè)計(jì)不同的思維方式和編程方法。因而也增加了整個(gè)語(yǔ)言的復(fù)雜性，掌握起來(lái)有一定難度。但是，C是C+的基礎(chǔ)，C+語(yǔ)言和C語(yǔ)言在很多方面是兼容的。因此，掌握了C語(yǔ)言，再進(jìn)一步學(xué)習(xí)C+就能以一種熟悉的語(yǔ)法來(lái)學(xué)習(xí)面向?qū)ο蟮恼Z(yǔ)言，從而達(dá)到事半功倍的目的。1.3 C/C+語(yǔ)言發(fā)展過(guò)程1973年，美國(guó)貝爾實(shí)驗(yàn)室的D.M.RITCHIE在B語(yǔ)言的基礎(chǔ)上最終設(shè)計(jì)出了一種新的語(yǔ)言，他取了BCPL的第二個(gè)字母作為這種語(yǔ)言的名字，這就是C語(yǔ)言。1977年Dennis M.Ritchie 發(fā)表了不依賴(lài)于具體機(jī)器系統(tǒng)的C語(yǔ)言編譯文本可移植的C語(yǔ)言編譯程序。1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著The C Programming Language，從而使C語(yǔ)言成為目前世界上流行最廣泛的高級(jí)程序設(shè)計(jì)語(yǔ)言。早期的C語(yǔ)言主要是用于UNIX系統(tǒng)。由于C語(yǔ)言的強(qiáng)大功能和各方面的優(yōu)點(diǎn)逐漸為人們認(rèn)識(shí)，到了八十年代，C開(kāi)始進(jìn)入其它操作系統(tǒng)，并很快在各類(lèi)大、中、小和微型計(jì)算機(jī)上得到了廣泛的使用。成為當(dāng)代最優(yōu)秀的程序設(shè)計(jì)語(yǔ)言之一。C語(yǔ)言是當(dāng)今最流行的程序設(shè)計(jì)語(yǔ)言之一，它的功能豐富、表達(dá)力強(qiáng)、使用靈活方便、應(yīng)用面廣、目標(biāo)程序高、可植入性好，既有高級(jí)語(yǔ)言的特點(diǎn)，又有低級(jí)語(yǔ)言的許多特點(diǎn)，適合作為系統(tǒng)描述語(yǔ)言，既可以用來(lái)編寫(xiě)系統(tǒng)軟件，也可以用來(lái)編寫(xiě)應(yīng)用軟件。C語(yǔ)言誕生后，許多原來(lái)用匯編語(yǔ)言編寫(xiě)的軟件，現(xiàn)在都可以用C語(yǔ)言編寫(xiě)了（如UNIX操作系統(tǒng)），而學(xué)習(xí)和適用C語(yǔ)言要比學(xué)習(xí)和適用匯編語(yǔ)言容易得多。1.4任務(wù)與分析（1）動(dòng)態(tài)地建立單鏈表,實(shí)現(xiàn)插入元素、刪除元素、查詢(xún)、求表長(zhǎng)度；（2）建兩個(gè)有序的單鏈表LA和LB，實(shí)現(xiàn)合并成LC，要求分LC中有和無(wú)重復(fù)值兩種情況的實(shí)現(xiàn)；（3）求兩鏈LA和LB兩鏈元素的交集LD。（4）靜態(tài)鏈表的實(shí)現(xiàn)：使用數(shù)組實(shí)現(xiàn)單向鏈表的建立、插入元素、刪除元素。2 設(shè)計(jì)方案2.1 步驟（1）編寫(xiě)主函數(shù)，調(diào)用初始化，建立線(xiàn)性鏈表的算法以及插入和刪除算法。（2）調(diào)試。（3）運(yùn)行輸入數(shù)據(jù)得出結(jié)果并進(jìn)行分析。2.2 設(shè)計(jì)流程圖3 程序演示3.1 編譯編譯之后發(fā)現(xiàn)錯(cuò)誤，error C2144: syntax error : missing ; before type int。缺少分號(hào)。如下圖：修改之后，在編譯一次。沒(méi)有錯(cuò)誤。如下圖：連接沒(méi)有問(wèn)題。如下圖：3.2 運(yùn)行結(jié)果菜單如圖1：圖1動(dòng)態(tài)地建立單鏈表,實(shí)現(xiàn)插入元素、刪除元素、查詢(xún)、求表長(zhǎng)度如圖2所示：圖2建兩個(gè)有序的單鏈表LA和LB，實(shí)現(xiàn)合并成LC，要求分LC中有和無(wú)重復(fù)值兩種情況的實(shí)現(xiàn)如圖3所示：圖3求兩鏈LA和LB兩鏈元素的交集LD如圖4所示：圖4靜態(tài)鏈表的實(shí)現(xiàn)：使用數(shù)組實(shí)現(xiàn)單向鏈表的建立、插入元素、刪除元素如圖5所示：圖54 結(jié)論單鏈表作為一種十分重要的線(xiàn)性表，在日常生活中有著十分重要的作用，在數(shù)據(jù)結(jié)構(gòu)這門(mén)課程中，占著很重的地位，這就要求我們認(rèn)真學(xué)習(xí)體會(huì)它的精髓，熟練掌握它的表示與應(yīng)用。在日常生活中要注意鍛煉自己的邏輯思維和動(dòng)手動(dòng)腦的實(shí)踐能力，才能在日后的計(jì)算機(jī)學(xué)習(xí)中取得長(zhǎng)足的進(jìn)步。這次課程設(shè)計(jì)，體現(xiàn)出自己?jiǎn)为?dú)設(shè)計(jì)程序的能力以及綜合運(yùn)用知識(shí)的能力，體會(huì)了學(xué)以致用、突出自己勞動(dòng)成果的喜悅心情。從中發(fā)現(xiàn)自己平時(shí)學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補(bǔ)。通過(guò)這次課程設(shè)計(jì)，我對(duì)這種寫(xiě)程序的方法有了一定的了解，自己有一個(gè)很明確的思路去寫(xiě)程序，提高了效率。老師嚴(yán)謹(jǐn)細(xì)致、一絲不茍的作風(fēng)一直是我工作、學(xué)習(xí)中的榜樣；老師循循善誘的教導(dǎo)和不拘一格的思路給予我無(wú)盡的啟迪；而您開(kāi)朗的個(gè)性和寬容的態(tài)度，幫助我能夠很順利的完成了這次課程設(shè)計(jì)。同時(shí)感謝對(duì)我?guī)椭^(guò)的同學(xué)們，謝謝你們對(duì)我的幫助和支持，讓我感受到同學(xué)的友誼。由于自己的設(shè)計(jì)能力有限，在設(shè)計(jì)過(guò)程中難免出現(xiàn)錯(cuò)誤，懇請(qǐng)老師多多指教。參考資料：5. 馮博琴 等編著，軟件技術(shù)基礎(chǔ)（修改版），西安交通大學(xué)出版社，19976. 嚴(yán)蔚敏 等著，數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社，20037. 李蕓芳 等著，軟件技術(shù)基礎(chǔ)（第二版），清華大學(xué)出版社，20008. 徐孝凱 等著，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述），清華大學(xué)出版社，2004附錄：源代碼/ 線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)1.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#include stdafx.h#include#include#include#includeusing namespace std;typedef struct LNode int data; struct LNode *next; LNode, LinkList ;typedef struct Arrayint data;int num;Array; LNode *CreateList(LNode *Head) LNode *p,*q,*s,*t; cout開(kāi)始創(chuàng)建鏈表，當(dāng)輸出值為0或者負(fù)數(shù)時(shí)則停止：endl;for(;)p=new LNode;coutp-data;if(p-datanext=NULL; q=p;elseif(p-datadata)p-next=Head;Head=p;else if (p-data=q-data)q-next=p;p-next=NULL;q=p;else s=Head; t=s-next; while(p-data=t-data) s=s-next; t=t-next; s-next=p; p-next=q; return Head; void PrintList (LNode *Head) LNode *pt=Head;if(pt=NULL)cout鏈表為空！按任意鍵返回！endl;system(pause);return;cout線(xiàn)性表為：endl;while (pt)coutdatanext;coutendl;void *InsertList(LNode *Head) if(Head=NULL) coutch; if(ch!=Y&ch!=y)return Head; else Head=CreateList(Head);return Head; LNode *pnew,*pend=Head,*ps,*pe;while(pend-next)pend=pend-next;cout請(qǐng)輸入數(shù)值，當(dāng)數(shù)值data=0則退出：next=NULL;coutpnew-data;if(pnew-datadatadata)pnew-next=Head;Head=pnew;else if(pnew-data=pend-data)pend-next=pnew;pend=pnew;elseps=Head;pe=ps-next;while(pe-datadata)ps=ps-next;pe=pe-next;pnew-next=pe;ps-next=pnew;coutendl; cout添加成功，當(dāng)前線(xiàn)性表為：endl;PrintList(Head) ; coutendl;return Head; void * DeleteList(LNode *Head) cout請(qǐng)輸入你要?jiǎng)h除的數(shù)據(jù)：t; while(temp-data!=t & temp-next!=NULL) p=temp;temp=temp-next; if(temp-data=t) if(temp=Head) Head=Head-next;delete temp; else if(temp-next=NULL) p-next=NULL;delete temp;else p-next=temp-next;delete temp; coutendl; cout刪除成功，當(dāng)前線(xiàn)性表更新為：endl; else cout線(xiàn)性表中無(wú)此數(shù)據(jù)endl; PrintList(Head) ; coutendl; return Head; void SearchList(LNode * Head)LNode *p=Head;cout請(qǐng)輸入你要查找的數(shù)據(jù)：t;while(p) if(t=p-data) flag=1;coutdata 在第j個(gè)位置next; j+;if (flag=0)coutnext; j+; cout線(xiàn)性表的長(zhǎng)度為jendl; return Head; void Work(LNode *Head)label:cout您可以選擇以下數(shù)據(jù)進(jìn)行相應(yīng)操作：endl;coutt 1-查找數(shù)據(jù) endl;coutt 2-添加數(shù)據(jù) endl;coutt 3-刪除數(shù)據(jù) endl;coutt 4-線(xiàn)性表長(zhǎng)度 endl;coutt 5-退出 endl;cout請(qǐng)輸入您的選擇:work;switch(work)case 1: SearchList(Head);goto label;case 2: InsertList(Head); goto label;case 3: DeleteList(Head); goto label; case 4: LengthList(Head); goto label;case 5: break;default:cout操作錯(cuò)誤！datadata)/若為相同值排序時(shí) 將改為data = a-data;a = a-next;else if (a-data=b-data)c-data = a-data;a = a-next;b = b-next;elsec-data = b-data;b = b-next;if (head3=NULL)head3 = c;c-next = NULL;p = c;elsep-next = c;p = p-next;p-next = NULL;if(a!= NULL)p-next=a;if(b!=NULL)p-next=b;return(head3);void second () LNode *Head1=NULL;LNode *Head2=NULL; cout請(qǐng)輸入第一個(gè)鏈表endl; Head1=CreateList(Head1); PrintList(Head1); coutendl; cout請(qǐng)輸入第二個(gè)鏈表endl; Head2=CreateList(Head2); PrintList(Head2);LNode *head3= MergeList(Head1 ,Head2);coutendl;coutdata = p2-data)if (head3 = NULL)head3 = p1;p3 = head3;elsep3-next = p1;p3 = p3-next;break;p2 = p2-next;p1 = p1-next;p2 = head2;p3-next = NULL;return head3;void third() LNode *Head1=NULL;LNode *Head2=NULL; cout請(qǐng)輸入第一個(gè)鏈表endl; Head1=CreateList(Head1); PrintList(Head1); coutendl; cout請(qǐng)輸入第二個(gè)鏈表endl; Head2=CreateList(Head2); PrintList(Head2);LNode *head3= SameList(Head1 ,Head2);coutendl;cout兩鏈表的交集為;PrintList(head3);system(pause);/第三問(wèn)結(jié)束void CreateArray(Array *myA, int n)/建立數(shù)組鏈表int i = 0;cout輸入節(jié)點(diǎn)數(shù)：;while (imyAi.data;myAi.num = i + 1;i+;/myAi - 1.num = NULL;void PrintArray(Array myA)/打印數(shù)組鏈表int i = 0;while (myAi.num != NULL)i = myAi.num;cout myAi.data ;void DeleteArray(Array *mA, int n)/刪除數(shù)組鏈表第n個(gè)結(jié)點(diǎn)Array *myA;myA = mA;int i = 0, m = 0;for (i; in - 1; i+)m = myAm.num;myAm + 1.data = 0;myAm.num = myAmyAm.num.num;myAm + 1.num = NULL;i = 0;while (myAi.num)i = myAi.num;myAi.num = m + 1;void AddArray(Array *myA, int n, int k)/向數(shù)組鏈表第n個(gè)結(jié)點(diǎn)添加結(jié)點(diǎn)kint i1 = 0, i11 = 0, i2 = 0, m = 0;while (myAi1.num != NULL)