數(shù)據(jù)結(jié)構(gòu)習(xí)題集（李冬梅 第2版）C語(yǔ)言版源程序習(xí)題源代碼 習(xí)題集-算法2-13

1、include include using namespace std;/函數(shù)結(jié)果狀態(tài)代碼define OK 1define ERROR 0define OVERFLOW -2/Status是函數(shù)的返回值類型，其值是函數(shù)結(jié)果狀態(tài)代碼 typedef int Status;#define MAXSIZE 100/存儲(chǔ)數(shù)據(jù)的基地址/當(dāng)前個(gè)數(shù)/順序存儲(chǔ)結(jié)構(gòu)為SqList/初始化/銷毀順序表/取值/插入/求兩個(gè)長(zhǎng)度均為n的序列A和B的中位數(shù)/輸出順序表typedef struct SqList int *elem;int length;SqList;Status InitList(SqList &L)

2、;Status DestroyList(SqList &L);Status GetElem(SqList Lz int iz int &e);Status Listinsert (SqList &L,int ifint e);int Search_Mid(intBz int n);void PrintList(SqList L);int main() (SqList A;InitList(A);Listinsert(A,1,1);Listinsert(Af 2r 3);Listinsert(A,3,5);Listinsert(A,4z 7);Listinsert(A,5,9); coutcc”

3、線性表A為：， PrintList(A);SqList B;InitList(B);Listinsert (B,1,2);Listinsert(B,2,4);ListInsert(B,3r 6);Listinsert(B,4,8);ListInsert(Bz 4 A10); cout”線性表B為：”； PrintList(B);int ans=Search_Mid(Aelem,B.elem,5); 。0a”兩個(gè)列表的中位數(shù)為：。$6。11；DestroyList(A); DestroyList(B);return 0; )/初始化Status InitList(SqList &L)/構(gòu)造一個(gè)空

4、的順序表LL.elem=new intMAXSIZE;if(JL.elem) exit(OVERFLOW);L.length = 0; return OK;/銷毀順序表Status DestroyList(SqList &L) if(L.length) (delete L.elem;L.length = 0; /取值Status GetElem(SqList Lz int irint &e) (if (iL.length) return ERROR; e=L.elemi-l; return OK;)/為順序表分配一個(gè)大小為MAXSIZE的數(shù)組空間/存儲(chǔ)分配失敗退出/空表長(zhǎng)度為0/釋放空間/表長(zhǎng)

5、又變成0/判斷i值是否合理，假設(shè)不合理，返回ERROR /elem i-l 單元存儲(chǔ)第i個(gè)數(shù)據(jù)元素/i值不合法/當(dāng)前存儲(chǔ)空間已滿/插入位置及之后的元素后移/將新元素e放入第i個(gè)位置/表長(zhǎng)加1/序列A的頭、尾指針初始化/序列B的頭、尾指針初始化/插入Status Listinsert(SqList &L,int i,int e)/在順序表L中第i個(gè)位置插入新的元素e, i值的合法范圍是length+lif (iL.length+1) return ERROR; if(L.length=MAXSIZE) return ERROR; for (int j=L.length-1;j=i-l;j-)L.

6、elemj+1=L.elemj;L elemi-1=e;+L ,length;return OK;)/輸出順序表void PrintList(SqList L)(coutHn;for(int i=l;i=L.length;i+) (int e;GetElem(L,i,e);coute;if (i!=L.length) coutnz n;)coutn nendl;)/查找int Search_Mid(int Az int B, int n) /求兩個(gè)長(zhǎng)低均為n的序列A和B的中位數(shù)int startl=0A endl=n-l;int start2=0z end2=n-l;while (startl

7、!=endl| Istart2!=end2)int ml=(startl+endl)/2;/滿足條件，中位數(shù)相等，直接返回值/滿足條件，中位數(shù)相等，直接返回值int m2=(start2+end2)/2;if(Aml=Bm2)return Aml;else if (AmlBm2)/滿足條件，a為較小中位數(shù)時(shí)/分別考慮奇數(shù)和偶數(shù)，保持兩個(gè)子數(shù)組元素個(gè)數(shù)相等if ( (startl+endl)%2=0) (startl=ml; end2=m2;) else (startl=ml+l; end2=m2;) ) else(if ( (startl+endl)%2=0) (endl=ml; start2

8、=m2;) else (endl=ml; start2=m2+l;)if ( (startl+endl)%2=0) (startl=ml; end2=m2;) else (startl=ml+l; end2=m2;) ) else(if ( (startl+endl)%2=0) (endl=ml; start2=m2;) else (endl=ml; start2=m2+l;)/假設(shè)元素為奇數(shù)個(gè)/舍棄A中間點(diǎn)以前的局部且保存中間點(diǎn)/舍棄B中間點(diǎn)以后的局部且保存中間點(diǎn)/假設(shè)元素為偶數(shù)個(gè)/舍棄A的前半局部/舍棄B的后半局部/滿足條件，a為較大中位數(shù)/假設(shè)元素為奇數(shù)個(gè)/舍棄A中間點(diǎn)以后的局部且保存中間點(diǎn)/舍棄B中間點(diǎn)以前的局部且保存