1、軟件開發(fā)技術(shù)基礎(chǔ)實驗報告 姓名： 學號： 班級： 實驗一 線性表的操作（2學時）實驗類型：驗證性 實驗要求：必修實驗學時： 2學時一、實驗?zāi)康模簠⒄战o定的線性表順序表類和鏈表類的程序樣例，驗證給出的線性表的常見算法。二、實驗要求：1、掌握線性表順序表類和鏈表類的特點。掌握線性表的常見算法。2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。三、實驗內(nèi)容：設(shè)計一個靜態(tài)數(shù)組存儲結(jié)構(gòu)的順序表類，要求編程實現(xiàn)如下任務(wù)：1）建立一個線性表，首先依次輸人整數(shù)數(shù)據(jù)元素（個數(shù)根據(jù)自己的需要鍵盤給定）2）刪除指定位置的數(shù)據(jù)元素（指定元素位置通過鍵

2、盤輸入）再依次顯示刪除后的線性表中的數(shù)據(jù)元素。3）查找指定數(shù)據(jù)的數(shù)據(jù)元素（指定數(shù)據(jù)的大小通過鍵盤輸入），若找到則顯示位置，若沒有找到就顯示0。四、要求1）采用順序表實現(xiàn)，假設(shè)該順序表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過50個。2）寫出完整的程序并能調(diào)試通過即可源程序如下：#include using namespace std;template class sq_LListprivate:int mm;int nn;T *v;public:sq_LList()mm=0;nn=0;return;sq_LList(int);void prt_sq_LList();int flag_sq_LList(

3、);void ins_sq_LList(int,T);void del_sq_LList(int); int search_sq_LList(T x);template sq_LList:sq_LList(int m)mm=m;v=new Tmm;nn=0;return;template void sq_LList:prt_sq_LList()int i;coutnn=nnendl;for(i=0;inn;i+)coutviendl;return;template int sq_LList:flag_sq_LList()if(nn=mm)return(-1);if(nn=0)return(0)

4、;return(1);template void sq_LList:ins_sq_LList(int i,T b)int k;if(nn=mm)coutoverflownn)i=nn+1;if(i=i;k-)vk=vk-1;vi-1=b;nn=nn+1;return;template void sq_LList:del_sq_LList(int i)int k;if(nn=0)coutunderflow!endl;return;if(inn)coutNot this element in the list!endl;return;for(k=i;knn;k+)vk-1=vk;nn=nn-1;r

5、eturn;template int sq_LList:search_sq_LList(T x)int i,j,k;i=1;j=nn;while(i=j)k=(i+j)/2;if(vk-1=x)cout你要查找的數(shù)現(xiàn)在的位置為:(k-1)x)j=k-1;else i=k+1;return(0);int main()int y;sq_LList a(100);cout第一次輸出順序表對象a:endl;a.prt_sq_LList();a.ins_sq_LList(1,1);a.ins_sq_LList(2,3);a.ins_sq_LList(3,5);a.ins_sq_LList(4,7);a.

6、ins_sq_LList(5,9);a.ins_sq_LList(6,11);cout第二次輸出順序表對象a:endl;a.prt_sq_LList();a.del_sq_LList(2);cout第三次輸出順序表對象a:endl;a.prt_sq_LList();cout請輸入要查找的數(shù):y;coutendl;a.search_sq_LList(y);cout第四次輸出順序表對象a:endl;a.prt_sq_LList();return 0;運行結(jié)果如下：心得體會：1. 通過本次試驗，我掌握了線性表的基本概念。2.通過本次試驗，我懂得了如何建立一個順序表，并能對順序表進行基本的建立、插入、

7、檢測、刪除以及查找的操作。3.本次試驗我知道了線性表的順序存儲結(jié)構(gòu)具有如下兩個特點：（1） 線性表中所有元素所占的存儲空間是連續(xù)的。（2） 線性表中各元素在存儲空間中是按邏輯順序依次存放的。實驗二 棧、隊列的操作實驗?zāi)康模簠⒄战o定的棧類和隊列類的程序樣例，驗證給出的棧和隊列的常見算法，并結(jié)合線性表類實現(xiàn)有關(guān)串的操作。實驗內(nèi)容：實驗要求：1 掌握棧、隊列、串的特點。掌握特殊線性表的常見算法。2 提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。3. 棧和隊列的長度都由自己定；4. 寫出完整的程序并能調(diào)試通過即可。5 重點理解棧、隊列

8、和串的算法思想，能夠根據(jù)實際情況選擇合適的存儲結(jié)構(gòu)。6 棧、隊列的算法是后續(xù)實驗的基礎(chǔ)（樹、圖、查找、排序等）。實驗原理：1. 堆棧類測試和應(yīng)用問題。要求： 定義數(shù)據(jù)元素的數(shù)據(jù)類型為如下形式的結(jié)構(gòu)體：typedef struct char taskname10;/任務(wù)名 int taskno;/任務(wù)號 DataType； 設(shè)計一個包含5個數(shù)據(jù)元素的測試數(shù)據(jù)，并設(shè)計一個主函數(shù)實現(xiàn)依次把5個數(shù)據(jù)元素入棧，然后出棧堆棧中的數(shù)據(jù)元素并在屏幕上顯示。2. 隊列類測試和應(yīng)用問題。要求： 設(shè)計一個主函數(shù)對循環(huán)隊列類和鏈式隊列類代碼進行測試.測試方法為：依次把數(shù)據(jù)元素1,2,3,4,5入隊，然后出隊中的數(shù)據(jù)元

9、素并在屏幕上顯示。#includeusing namespace std;/stack-begin#define stacksize 5typedef struct char taskname10;/任務(wù)名 int taskno;/任務(wù)號DataType;class stackprivate:int top;DataType taskstacksize;public:bool init();bool empty();bool push(DataType d);bool pop(DataType &d);bool stack:init()top=0;int i;for(i=0;i0?false:

10、true;bool stack:push(DataType d)if(top=stacksize) return false;strcpy(tasktop.taskname,d.taskname);tasktop.taskno=d.taskno;top+;return true;bool stack:pop(DataType &d)if(topnext=new queue_node(d);rear=rear-next;return true;bool queue:dequeue(int &d)if(front=rear) return false;queue_node *p=front-nex

11、t;d=p-data;front-next=p-next;if(p=rear)rear=front;delete p;return true;/queue-end#define queuesize 10class sqqueueprivate:int * base;int front;int rear;public:bool init();bool enqueue(int d);bool dequeue(int &d);bool sqqueue:init()base=(int *)malloc(queuesize*sizeof(int);if(!base) return false;front

12、=rear=0;return true;bool sqqueue:enqueue(int d)if(rear+1)%queuesize=front) return false;baserear=d;rear=(rear+1)%queuesize;return true;bool sqqueue:dequeue(int &d)if(front=rear) return false;d=basefront;front=(front+1)%queuesize;return true;void main()DataType dd5,tt;char tn=任務(wù)a;int i;for(i=0;i5;i+)

13、strcpy(ddi.taskname,tn);tn4+;ddi.taskno=i+1;stack mystack;mystack.init();for(i=0;i5;i+)mystack.push(ddi);cout入棧完成，按回車鍵繼續(xù);getchar();while(mystack.pop(tt)couttt.taskname tt.tasknoendl;cout出棧完成，按回車鍵繼續(xù);getchar();queue myqueue;myqueue.init();for(i=0;i5;i+)myqueue.enqueue(i+1);cout鏈隊入隊完成，按回車鍵繼續(xù);getchar();

14、for(;myqueue.dequeue(i);)coutiendl;cout鏈隊出隊完成，按回車鍵繼續(xù);getchar(); sqqueue mysqqueue;mysqqueue.init();for(i=0;i5;i+)mysqqueue.enqueue(i+1);cout循環(huán)隊列入隊完成，按回車鍵繼續(xù);getchar();for(;mysqqueue.dequeue(i);)coutiendl; cout循環(huán)隊列出隊完成，按回車鍵退出;getchar(); 實驗步驟：實驗結(jié)果：實驗三 查找算法實現(xiàn)（2學時）實驗類型：驗證性 實驗要求：必修實驗學時： 2學時一、實驗?zāi)康模簠⒄崭鞣N查找算法

15、程序樣例，驗證給出的查找常見算法。 二、實驗要求：1、掌握各種查找算法的特點，測試并驗證查找的常見算法。2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。三、實驗內(nèi)容：1. 建立有序表，采用折半查找實現(xiàn)某一已知的關(guān)鍵字的查找。2利用折半查找算法在一個有序表中插入一個元素，并保持表的有序性。源程序如下：#include using namespace std;template class sL_Listprivate:int mm;int nn;T *v;public:sL_List()mm=0;nn=0;return;sL_L

16、ist(int);int search_sL_List(T);int insert_sL_List(int,T);void prt_sL_List();template sL_List:sL_List(int m)mm=m;v=new Tmm;nn=0;return;template int sL_List:search_sL_List(T x)int i,j,k;i=1;j=nn;while(ix)j=k-1;else i=k+1;return(-1);template int sL_List:insert_sL_List(int p,T x)if(nn=mm)cout溢出！x)vp+1=v

17、p;p=p-1;vp+1=x;nn=nn+1;return(1);template void sL_List:prt_sL_List()int i;for(i=0;inn;i+)coutviendl;return;int main()int k,t,q,result;int a20=10,20,30,40,50,60,70,80;sL_Lists(20);for(k=0;k8;k+)s.insert_sL_List(k+1,ak);cout輸出有序?qū)ο髎:endl;s.prt_sL_List();cout請輸入要查找的數(shù):t;coutendl;cout你要查找的數(shù)在數(shù)組中的位置為:endl;r

18、esult=s.search_sL_List(t);coutresultendl;cout請插入一個元素:q;coutendl;s.insert_sL_List(k+1,q);cout插入后有序表變?yōu)?endl;s.prt_sL_List();return 0;實驗結(jié)果如下：心得體會：1. 通過這次試驗，我知道了一些查找的基本方法，并且了解了折半查找的典型方法及技巧。2. 并且我掌握了利用折半法插入一個元素的方法。3. 常見問題在于在插入位置時，易混淆位置與數(shù)值的關(guān)系，以及c+中的一些基本定義方法易忘記。實驗四 排序綜合實驗（3學時）實驗類型：綜合性 實驗要求：必修實驗學時： 3學時一、實驗?zāi)?/p>

19、的：參照各種排序算法程序樣例，驗證給出的排序常見算法。 二、實驗要求：1、掌握各種排序算法的特點，測試并驗證排序的常見算法。2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。三、實驗內(nèi)容： 輸入一組關(guān)鍵字序列分別實現(xiàn)下列排序: 1.實現(xiàn)直接插入排序； 2.實現(xiàn)冒泡排序算法； 3.實現(xiàn)快速排序算法（取第一個記錄或中間記錄作為基準記錄）；4.快速排序的非遞歸算法；5. 堆排序。 把上述幾種排序的算法編寫成菜單，根據(jù)輸入的數(shù)字不同執(zhí)行對應(yīng)的排序算法。源程序如下：#include using namespace std;/實現(xiàn)簡單插入

20、排序template void insort(T p,int n)int j,k;T t;for(j=1;j=0)&(pkt)pk+1=pk;k=k-1;pk+1=t;return;/實現(xiàn)冒泡排序template void bub(T p,int n)int m,k,j,i;T d;k=0;m=n-1;while(km)j=m-1;m=0;for(i=k;ipi+1)d=pi;pi=pi+1;pi+1=d;m=i;j=k+1;k=0;for(i=m;i=j;i-)if(pi-1pi)d=pi;pi=pi-1;pi-1=d;k=i;return;/實現(xiàn)快速排序template void qck(

21、T p,int n)int m,i;T *s;if(n10)i=split(p,n);qck(p,i);s=p+(i+1);m=n-(i+1);qck(s,m);elsebub(p,n);return;template static int split(T p,int n)int i,j,k,l;T t;i=0;j=n-1;k=(i+j)/2;if(pi=pj)&(pj=pk)l=j;else if(pi=pk)&(pk=pj)l=k;elsel=i;t=pl;pl=pi;while(i!=j)while(i=t)j=j-1;if(ij)pi=pj;i=i+1;while(ij)&(pi=t)i=i+1;if(ij)pj=pi;j=j-1;pi=t;return(i);/實現(xiàn)堆排序template void hap(T p,int n)int i,mm;T t;mm=n/2;for(i=mm-1;i=0;i-)sift(p,i,n-1);for(i=n-1;i=1;i-)t=p0;p0=pi;pi=t;sift(p,0,i-1);return;template static sift(T p,int i,int n)int j;T t;t=pi;j=