實驗一線性表應(yīng)用類實驗

1、實驗一 線性表應(yīng)用類實驗一、 問題定義及需求分析1.問題描述對線性表中的前M個元素和后N個元素整體互換。2.實驗要求設(shè)計元素整體互換的模擬程序。a.采用順序表存儲結(jié)構(gòu)實現(xiàn)。b.采用鏈表存儲結(jié)構(gòu)實現(xiàn)。3.輸入形式輸入數(shù)字M，N。4.輸入值的范圍 M和N都是由1到表長maxlen-1（1）高效算法：M+N=50（2）低效算法：M+N<=505.輸出形式互換過與互換前的線性表（含有元素位置以及元素數(shù)據(jù)）6.測試數(shù)據(jù) 順序表：（1）高效算法：M:45,N:5（2）低效算法：M:45,N:5二、 概要設(shè)計1.抽象數(shù)據(jù)類型的定義：struct List int datamaxlen; int lis

2、tlen; seqlist; /順序表 2.主程序流程圖：（1）高效算法：（2）低效算法：3. 函數(shù)執(zhí)行情況說明：（1）低效算法int main() 載入順序表，接受屏幕輸入的M和N的值。并且調(diào)用change(&seqlist.data0, seqlist.listlen, x, y)，輸出換前換后的結(jié)果。int change(&seqlist.data0, seqlist.listlen, x, y) 運用一個輔助空間ptr，使前m個元素與后n個元素整體互換，ptr為數(shù)組頭指針，length為數(shù)組長度。含有判斷流程，使得不符合輸入要求的數(shù)據(jù)M和N被排除。 （2）高效算法int

3、 main()載入順序表，接受屏幕輸入的M和N的值，并且調(diào)用change(&seqlist.data0, seqlist.listlen, x, y)，輸出換前換后的結(jié)果。int ListChange(int* ptr, int length)給定頭指針和序列長度，執(zhí)行逆置功能int change(int* ptr, int length, int m, int n)調(diào)用ListChange(int* ptr, int length)，先將前M個和后N個元素整體的進(jìn)行逆置處理，再分別對前M個和后N個元素進(jìn)行逆置處理。三、 詳細(xì)設(shè)計 （1） 低效算法：int change(int* pt

4、r, int length, int m, int n) /一個輔助空間使前m個元素與后n個元素整體互換，ptr為數(shù)組頭指針，length為數(shù)組長度 if(M+N>表長最大值) return -1; if(前后調(diào)換數(shù)據(jù)個數(shù)相同) /中間數(shù)據(jù)不用移動 只需要把前后的元素一一對應(yīng)地調(diào)換就可以 else if(M比N大) /m>n，中間數(shù)據(jù)整體前移 前后元素對應(yīng)調(diào)換 中間數(shù)據(jù)整體前移 else /m<n，中間數(shù)據(jù)整體后移 前后元素對應(yīng)調(diào)換中間數(shù)據(jù)整體后移 int main()存入50個數(shù)據(jù)元素接受屏幕輸入M和N的值判斷M和N的值是否符合要求輸入互換后的結(jié)果（2） 高效算法：int

5、ListChange(int* ptr, int length) /給定頭指針和序列長度，逆置 執(zhí)行對定長的順序表的逆置功能int change(int* ptr, int length, int m, int n) if(m + n !=50) return -1; n = 50 - m; 對整個順序表逆置對第一個數(shù)據(jù)到第m個數(shù)據(jù)進(jìn)行逆置對于后n個數(shù)據(jù)進(jìn)行逆置int main()存入50個數(shù)據(jù)元素接受屏幕輸入M和N的值判斷M和N的值是否符合要求輸入互換后的結(jié)果四、 調(diào)試分析1.在程序驗收之前，使用順序表儲存結(jié)構(gòu)實現(xiàn)中我只做了用低效算法實現(xiàn)互換的程序，算法時間復(fù)雜度為O(n2)。在程序驗收后，

6、我重新添加了用高效算法實現(xiàn)元素互換的程序，算法時間復(fù)雜度為O(n)。五、 使用說明：按照程序中屏幕提示輸入M和N的值并回車查看輸出結(jié)果六、 測試結(jié)果（1） 低效算法（2） 高效算法七、 附錄(a)高效算法#include <stdio.h>#include <iostream>#include <iomanip> /格式輸出, setw()using namespace std;#define maxlen 50struct List int datamaxlen; int listlen; seqlist; /順序表int ListChange(int*

7、ptr, int length) /給定頭指針和序列長度，逆置 int *p, *q, temp; for(p = ptr, q = ptr + length; p < q; p+,q-) temp = *p; *p = *q; *q = temp; return 0;int change(int* ptr, int length, int m, int n) if(m + n !=50) return -1; n = 50 - m; ListChange(&seqlist.data0, 50); ListChange(&seqlist.data0, m); ListCh

8、ange(ptr+m, 50-m); return 1;int main() int i,x,y; seqlist.listlen = 0; for(i=0; i<maxlen; i+) /存入50個數(shù)據(jù)元素 seqlist.datai = i; seqlist.listlen+; cout<<"將前M個數(shù)與后N個數(shù)交換位置(M+N=50)，請分別輸入M和N: " cin>>x>>y; if(-1 = change(&seqlist.data0, seqlist.listlen, x, y) cout << &q

9、uot;Error! " << endl; /如果m+n>順序表實際長度，則認(rèn)為出錯 cout<<"換前 換后"<<endl; for(i=0; i<maxlen; i+) cout << "" << setw(2) << i << " : " << seqlist.datai << endl; /設(shè)置域?qū)?return 0;（3） 低效算法#include <stdio.h>#include

10、<iostream>#include <iomanip> /格式輸出, setw()using namespace std;#define maxlen 50struct List int datamaxlen; int listlen;seqlist; /順序表int change(int* ptr, int length, int m, int n) /一個輔助空間使前m個元素與后n個元素整體互換，ptr為數(shù)組頭指針，length為數(shù)組長度 int i,j; int temp; /一個輔助空間 int* mark; if(m+n>length) return

11、-1; if(m = n) /前后調(diào)換個數(shù)相同，中間數(shù)據(jù)不用移動 for(i=0; i<m; i+) temp = *ptr; *ptr = *(ptr + length - n); *(ptr + length - n) = temp; ptr+; else if(m > n) /m>n，中間數(shù)據(jù)整體前移 for(i=0; i<n; i+) temp = *ptr; *ptr = *(ptr + length - n); *(ptr + length - n) = temp; ptr+; mark = ptr; for(j=0; j<m-n; j+) temp

12、= *ptr; for(i=n; i<length-1; i+) *ptr = *(ptr + 1); ptr+; *ptr = temp; ptr = mark; else /m<n，中間數(shù)據(jù)整體后移 for(i=0; i<m; i+) temp = *ptr; *ptr = *(ptr + length - n); *(ptr + length - n) = temp; ptr+; mark = ptr + length - n; for(j=0; j<n-m; j+) ptr = mark; temp = *ptr; for(i=length-n+m; i>

13、m; i-) *ptr = *(ptr - 1); ptr-; *ptr = temp; mark+; return 0;int main() int i,x,y; seqlist.listlen = 0; for(i=0; i<maxlen; i+) /存入50個數(shù)據(jù)元素 seqlist.datai = i; seqlist.listlen+; cout<<"將前x個數(shù)與后y個數(shù)交換位置(M+N<=50)，請分別輸入M和N: " cin>>x>>y; if(-1 = change(&seqlist.data0, seqlist.listlen, x, y) cout << "Error! " << endl; /如果m+n>順序表實際長度，則認(rèn)為出錯