鏈式簡單選擇排序課程設計

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

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　鏈式簡單選擇排序　　1 設計題目　　鏈式簡單選擇排序　　2 問題描述　　鏈式簡單選擇排序即以單鏈表

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

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

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

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

6、 //初始化指針成員和數據的構造函數　　data=item; 　　next=ptr;　　}; 　　}; //結構體定義“;”

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

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

9、gt;　　輸入節(jié)點數據函數：　　利用后插法建立鏈表，算法如下　　void list::input(int endTag)　　//其中DendTag為約定的輸入序列結束標括志；利用后插法建立單鏈表　　{</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; //可有可無,表收尾　　}　　函數SelectSort1( )和SelectSort2( )的基本實現思想是一樣的，只是一些細節(jié)有所不同。兩者構成了本程序的主體部分，鏈式簡單選擇排序

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

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

17、，518487，215398，127498。　　再輸入若干整數，例如輸入98375 ， 69828， 76837， 10738， 63874， 90897，對其進行從大到小的排序，排序后結果應為10738， 63874，69828，76837，90897， 98375 。　　4 調試報告

18、　　本實驗需要采用支持標準Microsoft Visual C++ 2010 Express編譯器，并采用最基礎的Win32控制臺程序。　　在調試程序時，出現錯誤提示如下：　?。?）　　1>------ 已啟動生成：項目: 鏈式簡單選擇排序--初級

19、版, 配置: Debug Win32 ------　　1> 鏈排序.cpp　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈式簡單選擇排序--初級版\鏈式簡單選擇排序--初級版\鏈排序.cpp(11): error C2236: 意外的“class”“l(fā)ist”

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

21、tor\documents\visual studio 2010\projects\鏈式簡單選擇排序--初級版\鏈式簡單選擇排序--初級版\鏈排序.cpp(11): error C2447: “{”: 缺少函數括題(是否是老式的形式表？）　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈式簡單選擇排序--初級

22、版\鏈式簡單選擇排序--初級版\鏈排序.cpp(24): error C2653: “l(fā)ist”:不是類或命名空間名稱　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈式簡單選擇排序--初級版\鏈式簡單選擇排序--初級版\鏈排序.cpp(46): error C2653: “l(fā)ist”:不是類或命名空間名稱&

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

24、visual studio 2010\projects\鏈式簡單選擇排序--初級版\鏈式簡單選擇排序--初級版\鏈排序.cpp(59): error C2065: “first”: 未聲明的標識符　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈式簡單選擇排序--初級版\鏈式簡單選擇排序--初級版\鏈排序.c

25、pp(59): error C2227: “->next”的左邊必須指向類結構/聯合/泛型類型　　1>類型是“unknown-type”　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈式簡單選擇排序--初級版\鏈式簡單選擇排序--初級版\鏈排序.cpp(

26、79): error C2653:“l(fā)ist”:不是類或命名空間名稱　　1>c:\users\administrator\documents\visual studio 2010\projects\鏈式簡單選擇排序--初級版\鏈式簡單選擇排序--初級版\鏈排序.cpp(83): error C2065:“first”:未聲明的標識符　　1>1

27、>c:\users\administrator\documents\visual studio 2010\projects\鏈式簡單選擇排序--初級版\鏈式簡單選擇排序--初級版\鏈排序.cpp(83): error C2227: “->next”的左邊必須指向類結構/聯合/泛型類型　　1>類型是“unknown-type”　　1>

28、;c:\users\administrator\documents\visual studio 2010\projects\鏈式簡單選擇排序--初級版\鏈式簡單選擇排序--初級版\鏈排序.cpp(101): error C2653:“l(fā)ist”:不是類或命名空間名稱　　1>c:\users\administrator\documents\visual studio 2010\project

29、s\鏈式簡單選擇排序--初級版\鏈式簡單選擇排序--初級版\鏈排序.cpp(104): error C2227:“->next”的左邊必須指向類結構/聯合/泛型類型　　1> 類型是“unknown-type”　　1>c:\users\administrator\d鏈排序.cpp(104): fatal error C1903:無法從以前

30、的錯誤中恢復；正在停止編譯　　==========生成:成功 0 個，失敗 1 個，最新 0 個，跳過 0 個==========　　========== 生成:成功 0 個，失敗 1 個，最新 0 個，跳過 0 個documents\visual studio 2010\projects\鏈式簡單選擇排序--初級版\鏈式簡單選擇排序--初級版\====

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

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

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

34、要求。當遇到各種編譯或語法錯誤時，我們必須靜下心來，仔細思考問題，理清編程時的思路，確保思路正確，然后反復的調試，直至寫出正確的，健壯的計算機程序。如果自己實在找不出錯誤原因，我們仍可以找同學一起討論。　　總之，通過課程設計，我認識到我們在平常上課時就應該去了解每種算法解決的問題，去認真學習并嘗試編寫經典算法，去認真聽老師講的每一個程序，從老師那里去了解他們比較成熟的編程思想，并學以致用。同時我

35、了解到在平時學習中就應該經常鍛煉自己的動手能力，并鞏固我們課堂上學習的基礎知識，這樣才能讓自己的計算機編程能力進步的更快。　　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;}; 　　//初始化指針成員的構造函數　　link_node(const int &item,link_node*ptr=NULL)&l

38、t;b>　　{　　data=item; 　　next=ptr;　　}; // 初始化指針成員和數據的構造函數　　}; //錯誤：結構

39、體定義結束需要用“;”結束　　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：只聲明未定義該函數&

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

42、 *first;　　}; 　　void list::input(int endTag)　　//其中DendTag為約定的輸入序列結束標括志；利用后插法建立單鏈表　　{&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ù)結點　　cout<<current->data<<" "; //輸出結點儲存的值　　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用于指向已經查詢過的數據中的最小元素　　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語句結合找出本趟查詢最小的元素　　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; //從頭結點開始刪除　　delete q;　　}　　}　　int

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

64、 //0為終止符　　cout<<"您輸入的數據為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排序后的數列為（從小到大排序）："<<endl;<p&g

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

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

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

69、鏈式簡單選擇排序，其數據比較次數與待排序序列的初始順序無關，其比較次數總是O(n*n),但元素移動次數則與待排序元素序列有關，最好情況下數據一次也不用移動，最壞情況下元素每一趟都要進行結點數據交換，總的移動次數為3(n-1)。　　運行輸出結果：　　從大到小排列

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

溫馨提示

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

鏈式簡單選擇排序課程設計

文檔簡介

溫馨提示

最新文檔

評論

鏈式簡單選擇排序課程設計

文檔簡介

溫馨提示

最新文檔

評論

免費下載