鏈?zhǔn)胶唵芜x擇排序課程設(shè)計

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：12 大?。?37.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩11頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　鏈?zhǔn)胶唵芜x擇排序　　1 設(shè)計題目　　鏈?zhǔn)胶唵芜x擇排序　　2 問題描述　　鏈?zhǔn)胶唵芜x擇排序即以單鏈表

2、為存儲結(jié)構(gòu)，實現(xiàn)簡單選擇排序的功能。顯然，實現(xiàn)該程序就是先要建立一個單鏈表，利用單鏈表對數(shù)據(jù)進行存儲、操作。將輸入的整型數(shù)據(jù)以結(jié)點的形式存儲在這個建立的單鏈表中。然后對單鏈表中的這些結(jié)點的值進行簡單選擇排序。　　該問題中，以帶有附加頭結(jié)點的單鏈表為存儲結(jié)構(gòu)，排序分為從大到小排序和從小到大排序兩種方式，我們可以用這兩種方法分別實現(xiàn)進行排序，分別得到結(jié)果。&

3、lt;b>　　3 設(shè)計　　3.1 存儲結(jié)構(gòu)設(shè)計　　線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是用一組任意的可以是不連續(xù)的存儲單元存儲線性表的數(shù)據(jù)元素。它包括兩個域：其中存儲數(shù)據(jù)元素信息的稱為數(shù)據(jù)域；存儲直接后繼存儲位置的域稱為指針域。　　單鏈表結(jié)構(gòu)體的定義如下：

4、　　Struct link_node //鏈表節(jié)點類的定義　　{　　int data; //指針域　　link_node*next; //值域，不是float *next; 關(guān)于鏈表中的

5、　//指針指向問題 　　link_node(link_node*ptr=NULL){next=ptr;}; 　　//初始化指針成員的構(gòu)造函數(shù)　　link_node(const int &item,link_node*ptr=NULL)　　{

6、 //初始化指針成員和數(shù)據(jù)的構(gòu)造函數(shù)　　data=item; 　　next=ptr;　　}; 　　}; //結(jié)構(gòu)體定義“;”

7、結(jié)束　　其中，值域data以整型存儲了所要排序的關(guān)鍵字值，而指針域next以指針型存儲了指向下一個結(jié)點的地址。其中兩個構(gòu)造函數(shù)分別用于初始化數(shù)據(jù)和指針成員。Link_node是定義的一個全局結(jié)構(gòu)體變量，可以在下面的任何函數(shù)中調(diào)用。　　3.2 主要算法設(shè)計　　本程序中主要用到5個函數(shù)，分別是構(gòu)造函數(shù)list()、輸

8、入結(jié)點數(shù)據(jù)input(int)、輸出數(shù)據(jù)函數(shù)output()、從小到大排列函數(shù)SelectSort1()、從大到小排列函數(shù) void SelectSort2()。　　構(gòu)造函數(shù)：　　list(){first=new link_node;}; //創(chuàng)建附加頭結(jié)點，first指向該結(jié)點<p&

9、gt;　　輸入節(jié)點數(shù)據(jù)函數(shù)：　　利用后插法建立鏈表，算法如下　　void list::input(int endTag)　　//其中DendTag為約定的輸入序列結(jié)束標(biāo)括志；利用后插法建立單鏈表　　{</b&

10、gt;　　link_node *newnode,*last;　　int val;　　make_empty(); //清空鏈表 　　cin>&g

11、t;val;　　last=first; 　　while (val!=endTag) //last指向表尾　　{　　newnode=new link_node(val);<

12、;/p>　　if(newnode==NULL)　　{　　cerr<<"存儲分配失誤"<<endl;　　exit(1);　　}

13、 //動態(tài)分配失敗　　last->next=newnode;　　last=newnode; //last永遠指向表尾　　cin>>val; //插入到表末端　　}&

14、lt;/b>　　last->next=NULL; //可有可無,表收尾　　}　　函數(shù)SelectSort1( )和SelectSort2( )的基本實現(xiàn)思想是一樣的，只是一些細節(jié)有所不同。兩者構(gòu)成了本程序的主體部分，鏈?zhǔn)胶唵芜x擇排序

15、的基本思想是：每一趟排序（例如第i趟，i=0,1,2，…，n-2）在后面n-i個待排序的節(jié)點數(shù)據(jù)中找出最小的元素，作為有序元素排列的第i個元素。待到第n-2趟做完，待排序元素只剩一個了，就不用再選了。　　SelectSort1( ) //實現(xiàn)從小到大排序，其實現(xiàn)代碼見附表實驗代碼。　　SelectSort2( ) //實現(xiàn)從大到小排序，其實現(xiàn)代碼

16、見附表實驗代碼。　　這樣，主要算法中的函數(shù)，只需在主函數(shù)中調(diào)用即可實現(xiàn)。　　3.3 測試用例設(shè)計　　任意輸入幾個數(shù)據(jù)，以0為終止符，例如輸入972845 ，634873，127498， 928134， 518487， 215398，對其進行從大到小的排序，排序后結(jié)果應(yīng)為972845 ，928134，634873

17、，518487，215398，127498。　　再輸入若干整數(shù)，例如輸入98375 ， 69828， 76837， 10738， 63874， 90897，對其進行從大到小的排序，排序后結(jié)果應(yīng)為10738， 63874，69828，76837，90897， 98375 。　　4 調(diào)試報告

18、　　本實驗需要采用支持標(biāo)準(zhǔn)Microsoft Visual C++ 2010 Express編譯器，并采用最基礎(chǔ)的Win32控制臺程序。　　在調(diào)試程序時，出現(xiàn)錯誤提示如下：　?。?）　　1>------ 已啟動生成：項目: 鏈?zhǔn)胶唵芜x擇排序--初級

19、版, 配置: Debug Win32 ------　　1> 鏈排序.cpp　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.cpp(11): error C2236: 意外的“class”“l(fā)ist”

20、，是否忘記了“;”?　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.cpp(11): error C2143: 語法錯誤: 缺少“;”(在“{”的前面)　　1>c:\users\administra

21、tor\documents\visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.cpp(11): error C2447: “{”: 缺少函數(shù)括題(是否是老式的形式表？）　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級

22、版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.cpp(24): error C2653: “l(fā)ist”:不是類或命名空間名稱　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.cpp(46): error C2653: “l(fā)ist”:不是類或命名空間名稱&

23、lt;/p>　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.cpp(55): error C2653: “l(fā)ist”:不是類或命名空間名稱　　1>c:\users\administrator\documents\

24、visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.cpp(59): error C2065: “first”: 未聲明的標(biāo)識符　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.c

25、pp(59): error C2227: “->next”的左邊必須指向類結(jié)構(gòu)/聯(lián)合/泛型類型　　1>類型是“unknown-type”　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.cpp(

26、79): error C2653:“l(fā)ist”:不是類或命名空間名稱　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.cpp(83): error C2065:“first”:未聲明的標(biāo)識符　　1>1

27、>c:\users\administrator\documents\visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.cpp(83): error C2227: “->next”的左邊必須指向類結(jié)構(gòu)/聯(lián)合/泛型類型　　1>類型是“unknown-type”　　1>

28、;c:\users\administrator\documents\visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.cpp(101): error C2653:“l(fā)ist”:不是類或命名空間名稱　　1>c:\users\administrator\documents\visual studio 2010\project

29、s\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈排序.cpp(104): error C2227:“->next”的左邊必須指向類結(jié)構(gòu)/聯(lián)合/泛型類型　　1> 類型是“unknown-type”　　1>c:\users\administrator\d鏈排序.cpp(104): fatal error C1903:無法從以前

30、的錯誤中恢復(fù)；正在停止編譯　　==========生成:成功 0 個，失敗 1 個，最新 0 個，跳過 0 個==========　　========== 生成:成功 0 個，失敗 1 個，最新 0 個，跳過 0 個documents\visual studio 2010\projects\鏈?zhǔn)胶唵芜x擇排序--初級版\鏈?zhǔn)胶唵芜x擇排序--初級版\====

31、======　　原因分析：　　(1)結(jié)構(gòu)體定義結(jié)束之后應(yīng)用“；”結(jié)束。　　(2)兩節(jié)點數(shù)據(jù)作比較時不應(yīng)該是 if(current2<=current3) if(current2->data>=current3->data)或者if(current2-&

32、gt;data<=current3->data）。　　因為結(jié)點包含兩個數(shù)據(jù)。　　5 經(jīng)驗和體會　　本實驗課題的設(shè)計中涉及到了數(shù)據(jù)結(jié)構(gòu)中單鏈表鏈表和選擇排序兩個知識點，通過本次課程設(shè)計，我對鏈表的一些操作：如帶附加頭結(jié)點的鏈表的創(chuàng)建，鏈表數(shù)據(jù)的輸入，節(jié)點數(shù)據(jù)的輸出以

33、及簡單選擇排序有了深刻的理解，通過自己動手寫代碼，同時加深了對選擇排序執(zhí)行過程的了解。同時也鍛煉了自己的動手寫代碼的能力。　　在實驗中遇到了平時只看書認識不到的各種語法錯誤和編譯錯誤，之前對鏈表有一些錯誤的認識，通過不斷地調(diào)試，對之前的錯誤觀點進行了糾正。編寫程序的能力是逐步鍛煉出來的，除了對知識的熟悉程度，還要用耐心去處理程序編寫過程中的各種小錯大錯，這是對一個將要從事計算機編程行業(yè)的人的基本

34、要求。當(dāng)遇到各種編譯或語法錯誤時，我們必須靜下心來，仔細思考問題，理清編程時的思路，確保思路正確，然后反復(fù)的調(diào)試，直至寫出正確的，健壯的計算機程序。如果自己實在找不出錯誤原因，我們?nèi)钥梢哉彝瑢W(xué)一起討論。　　總之，通過課程設(shè)計，我認識到我們在平常上課時就應(yīng)該去了解每種算法解決的問題，去認真學(xué)習(xí)并嘗試編寫經(jīng)典算法，去認真聽老師講的每一個程序，從老師那里去了解他們比較成熟的編程思想，并學(xué)以致用。同時我

35、了解到在平時學(xué)習(xí)中就應(yīng)該經(jīng)常鍛煉自己的動手能力，并鞏固我們課堂上學(xué)習(xí)的基礎(chǔ)知識，這樣才能讓自己的計算機編程能力進步的更快。　　6 附錄　　6.1 源程序清單　　#include<iostream><

36、;p>　　using namespace std;　　Struct link_node //鏈表節(jié)點類的定義　　{　　int data; //值域　　link_node*next;

37、 //指針域 　　link_node(link_node*ptr=NULL){next=ptr;}; 　　//初始化指針成員的構(gòu)造函數(shù)　　link_node(const int &item,link_node*ptr=NULL)&l

38、t;b>　　{　　data=item; 　　next=ptr;　　}; // 初始化指針成員和數(shù)據(jù)的構(gòu)造函數(shù)　　}; //錯誤：結(jié)構(gòu)

39、體定義結(jié)束需要用“;”結(jié)束　　class list{　　public:　　list(){first=new link_node;};　　void input(int); //輸入<p&g

40、t;　　void output(); //輸出　　void SelectSort1(); //從小到大排列　　void SelectSort2(); //從大到小排列　　void make_empty(); //錯誤2：只聲明未定義該函數(shù)&

41、lt;p>　　~list()　　{make_empty();}; //析構(gòu)函數(shù) 　　private:　　link_node

42、 *first;　　}; 　　void list::input(int endTag)　　//其中DendTag為約定的輸入序列結(jié)束標(biāo)括志；利用后插法建立單鏈表　　{&l

43、t;p>　　link_node *newnode,*last;　　int val;　　make_empty(); //清空鏈表 　　cin>>val;&

44、lt;/p>　　last=first; 　　while (val!=endTag){ //last指向表尾　　newnode=new link_node(val);　　if(newnode==NULL)&l

45、t;b>　　{　　cerr<<"存儲分配失誤"<<endl;　　exit(1);　　} //動態(tài)分配失敗　　last->next=

46、newnode;　　last=newnode; //last永遠指向表尾　　cin>>val; //插入到表末端　　}　　last->next=NULL; //可有可

47、無,表收尾　　}　　void list::output()　　{　　link_node*current=first->next ;　　while (

48、current!=NULL) { //輸出停止，即無后續(xù)結(jié)點　　cout<<current->data<<" "; //輸出結(jié)點儲存的值　　current=current->next;　　}</p&

49、gt;　　}　　void list::SelectSort1() //從小到大的排序　　{　　link_node*current1,*current2,*current3;<

50、p>　　int temp;　　for(current1=first->next;current1->next!=NULL;current1=current1->next)　　{ //current1指向本趟查詢的首元素　　/

51、/current2用于查找最小元素　　//current3用于指向已經(jīng)查詢過的數(shù)據(jù)中的最小元素　　current3=current1;　　for(current2=current1->next;current2->next!=NULL;current2=current2->next)</p

52、>　　{　　if(current2->data<=current3->data)　　current3=current2;　　}　　if(current

53、2->data<=current3->data)　　current3=current2; 　　//與上面for語句結(jié)合找出本趟查詢最小的元素　　if (current1->next!=current3->next){

54、　　temp=current1->data;　　current1->data=current3->data;　　current3->data=temp;　　} //將本趟查詢的最小元素與本趟查找首元素交換位置<b&g

55、t;　　}　　}　　void list::SelectSort2() 　　//從大到小排序，原理與從小到大排序相同　　{</b&g

56、t;　　link_node*current1,*current2,*current3;　　int temp;　　for(current1=first->next;current1->next!=NULL;current1=current1->next)<

57、;/p>　　{　　current3=current1;　　for(current2=current1->next;current2->next!=NULL;current2=current2->next)　　{&

58、lt;/b>　　if(current2->data>=current3->data)　　current3=current2;　　}　　if(current2->data>=current3->

59、data)　　current3=current2;　　if (current1->next!=current3->next){　　temp=current1->data;　　current1->data=current3->data;<

60、/p>　　current3->data=temp;　　}　　}　　}　　void list:: make_empty()&l

61、t;/p>　　{　　link_node *q;　　while(first->next!=NULL)　　{　　q=first->next;

62、　　first->next=q->next; //從頭結(jié)點開始刪除　　delete q;　　}　　}　　int

63、main()　　{ 　　list a; //建立對象　　cout<<"向鏈表括中輸入數(shù)據(jù)（0表示終止字符）：\n";　　a.input(0);

64、 //0為終止符　　cout<<"您輸入的數(shù)據(jù)為a：\n";　　a.output();　　cout<<"\n選單：\n.從小到大排列\(zhòng)n2.從大到小排列\(zhòng)n";　　int c

65、hoice;　　cin>>choice;　　if(choice==1){　　a.SelectSort1();　　cout<<"\n排序后的數(shù)列為（從小到大排序）："<<endl;<p&g

66、t;　　a.output();　　cout<<"\n";　　}　　else if(choice==2){　　a.SelectSort2();　　cout<

67、<"\n排序后的數(shù)列為（從大到小排序）："<<endl;　　a.output();　　cout<<"\n";　　}　　else

68、　　cout<<"輸入錯誤";　　return 0;　　}　　6.2運行結(jié)果　　對于

69、鏈?zhǔn)胶唵芜x擇排序，其數(shù)據(jù)比較次數(shù)與待排序序列的初始順序無關(guān)，其比較次數(shù)總是O(n*n),但元素移動次數(shù)則與待排序元素序列有關(guān)，最好情況下數(shù)據(jù)一次也不用移動，最壞情況下元素每一趟都要進行結(jié)點數(shù)據(jù)交換，總的移動次數(shù)為3(n-1)。　　運行輸出結(jié)果：　　從大到小排列

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

鏈?zhǔn)胶唵芜x擇排序課程設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

鏈?zhǔn)胶唵芜x擇排序課程設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

免費下載