數(shù)據(jù)結(jié)構(gòu)作業(yè)匯總

1、作業(yè)：分別以順序表和單鏈表為存儲結(jié)構(gòu)，為線性表類添加一個(gè)成員函數(shù)，實(shí)現(xiàn)線性表中 所有元素就地逆置。順序表的就地逆置算法：template void SeqList:Reverse()for(int i=0; ilength/2 ; i+)int temp=datai;datai=datalength-i-1 ;datalength-i-1=temp ;具體實(shí)需注意事項(xiàng)單鏈表的就地逆置算法： 算法一：要修改每個(gè)結(jié)點(diǎn)的指針域，即把指向后繼結(jié)點(diǎn)的指針改為指向前軀結(jié)點(diǎn)， 現(xiàn)辦法就是在掃描遍歷過程中，對工作指針P所指結(jié)點(diǎn)作指針域前指操作。(1) 逆置后原來指向后繼結(jié)點(diǎn)的指針被破壞，需要保留；(2) 逆置

2、需要將P的前軀結(jié)點(diǎn)地址填入后繼位置，為此需保存前軀結(jié)點(diǎn)地址；(3) 全部逆置后，頭結(jié)點(diǎn)的指針域應(yīng)指向最后結(jié)點(diǎn)。template void LinkList:Reverse()p=first-next ; pre=null ;while (p)r=p-next;p-next=pre;pre=p;p=r;first-next=pre;算法二：利用頭插法將單鏈表逆置。將原來表的頭結(jié)點(diǎn)作為新鏈表的頭結(jié)點(diǎn)，依次取原來 表中的結(jié)點(diǎn)插到新表的頭結(jié)點(diǎn)之后。注意：后繼結(jié)點(diǎn)會遭破壞，需暫存。void LinkList:Reverse()p=first-next ;first-next=null ;while (p

3、)r=p-next;p-next=first-next;first-next=p;p=r;作業(yè)：設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為0(n)的算法，實(shí)現(xiàn)數(shù)組 An中所有元素循環(huán)左移k個(gè)位置。算法一：將數(shù)組中的前k個(gè)元素存放到一個(gè)臨時(shí)數(shù)組中，再將余下的n-k個(gè)元素左移k個(gè)位置,最后將前k個(gè)元素從臨時(shí)數(shù)組復(fù)制到原來數(shù)組中的后k個(gè)位置。時(shí)間復(fù)雜度 0(n); 空間復(fù)雜度 0(k)算法二：先設(shè)計(jì)一個(gè)函數(shù)將數(shù)組向左循環(huán)移動(dòng)一個(gè)位置，然后再調(diào)用這個(gè)函數(shù)k次，顯然，該算法的時(shí)間復(fù)雜度 0(n*k)算法三：將這個(gè)問題看做是把數(shù)組ab轉(zhuǎn)換成數(shù)組ba,( aTbT)T=baVoid converse ( int A, int n

4、, int k)Reverse (A, 0, k-1);Reverse (A, k, n-1);Reverse (A, 0, n-1);Void Reverse （ int A, int from, int to）For （i=0; i（to-from+1）/2; i+）Afrom+iAto-i;作業(yè)：約瑟夫環(huán)問題描述：設(shè)有編號為1, 2,n的n（n0）個(gè)人圍坐成一個(gè)圈，每個(gè)人持有一個(gè)密碼m,從第1個(gè)人開始報(bào)數(shù)，報(bào)到 m停止，報(bào)m的人出圈，如此下去，直到所有人全部出圈為止。當(dāng)任意給 定n和m后，設(shè)計(jì)算法求n個(gè)人出圈的次序。要求：（1）分析問題,建立數(shù)據(jù)模型；（2）設(shè)計(jì)適合的存儲結(jié)構(gòu)；（3）設(shè)計(jì)

5、相應(yīng)算法；（4）分析算法時(shí)間和空間復(fù)雜度；（ 5）調(diào)試算法,上機(jī)實(shí)現(xiàn)。解：（1）由約瑟夫環(huán)問題的求解過程可以把問題的輸入（即n個(gè)人的編號）看成是一個(gè)線性序列,每個(gè)人的編號看成是一個(gè)數(shù)據(jù)元素。因此,問題抽象的數(shù)據(jù)模型是“線性表”；（2）線性表有兩種基本的存儲結(jié)構(gòu)順序存儲和鏈接存儲 ;（ 3）A. 用順序存儲結(jié)構(gòu)實(shí)現(xiàn)約瑟夫問題void Josephus （int a , int n, int m）/約瑟夫環(huán)初始化：for （int i=0; i1）/ 每出圈一次表長減 1s=( s+m-1)% length;cout as;s為第m個(gè)人for (int i=s+1; ilength; i+)ai-

6、1=ai;刪除第m個(gè)人length-;coutdata=a0;rear=first;for (int i=1; idata=ai;rear-next=s;rear=s;rear-next=first;/ 由刪除操作輸出出圈序列Node *pre, *p, *q;int count=2;pre=first; p=first-next;while ( pre !=p )if ( count=m)coutdatanext;pre-next=p;delete q;count=1;elsepre=p; p=p-next; count+;coutdataendl;delete p;delete pre;d

7、elete first; delete rear;時(shí)間復(fù)雜度 O(n*m) ； 空間復(fù)雜度 O(n)作業(yè)：設(shè)順序棧s中有2n個(gè)元素，從棧頂?shù)綏５椎脑匾淮螢閍2n,a2n-1,a1,要求通過一個(gè)循環(huán)隊(duì)列重新排列棧中的元素，使得從棧頂?shù)綏５椎脑匾来蝍2n,a2n-2,a2, a2n-1,a2n-3,al，請?jiān)O(shè)計(jì)算法實(shí)現(xiàn)該操作；要求空間復(fù)雜度和時(shí)間復(fù)雜度均為O (n)。算法步驟：( 1)將所有元素出棧入隊(duì)；( 2)依次將隊(duì)列元素出隊(duì)，如果是偶數(shù)結(jié)點(diǎn)則再入隊(duì)；如果是奇數(shù)結(jié)點(diǎn)則入棧；( 3)將奇數(shù)結(jié)點(diǎn)出棧并入隊(duì)；( 4)將偶數(shù)結(jié)點(diǎn)出隊(duì)并入棧；( 5)將所有元素出棧并入隊(duì)；( 6)將所有元素出隊(duì)并入棧

8、。作業(yè)：設(shè)計(jì)算法，把十進(jìn)制整數(shù)轉(zhuǎn)換為二進(jìn)制至九進(jìn)制之間的任一進(jìn)制輸出。分析 ： N=(N/D)*D+N%D 先得到的余數(shù)為低位，后輸出；后得到的余數(shù)為高位，后輸出； 因此，可將余數(shù)放入棧中，再將棧元素依次輸出。void decimaltor ( int num, int r )top=-1;while (num!=0)k=num%r;s+top=k;num=num/r;while (top!=-1)printf (stop- -);作業(yè)：設(shè)計(jì)算法，判斷給定模式是否為兩個(gè)主串的公共子序列。分析 ：調(diào)用兩次子序列判定函數(shù)即可。子序列判定函數(shù)偽代碼如下1 初始化比較的起始位置 , i=0,j=0;2

9、. length仁字符串A的長度，length2=字符串B的長度；3. 當(dāng) ile ngthl &jle ngth2,重復(fù)下面操作3.1 if Ai=Bj, i+, j+3.2 else i+;4. if j=length2,說明 B 中字符匹配成功，return 1; else return 0;作業(yè)：若在矩陣A中存在一個(gè)元素是第i行中最小值，又是第j列中最大值，則稱此元素為該 矩陣的一個(gè)鞍點(diǎn)。假設(shè)以二維數(shù)組存儲矩陣A，設(shè)計(jì)算法求矩陣中的所有鞍點(diǎn)，并分析最壞情況下的時(shí)間復(fù)雜度。void andian (int a , int n, int m)for (i=0; in ; i+)min=ai

10、O; k=0;/ min 為 i行中的最小值for (p=0; pm; j+)If (aipmin) min=aip; k=p; aik為第i行最小值for (q=0; qmin) break;If (q= =n) cout “輸出鞍點(diǎn)：” ikaik;復(fù)雜度分析：O(nm+n 2)作業(yè)：編寫非遞歸算法，統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)方法一：const int maxsize=100;template struct BiNodeDataType data;BiNode *lchild;BiNode *rchild;template int BiTree:LeafNumber(BiNode *root

11、) int num=0;BiNode* smaxsize;/采用順序棧，并假定不會發(fā)生上溢int top = -1;while (root != NULL | top != -1)while (root != NULL)coutdata;if( root-lchild=NULL & root-rchild=Null) num+; s+top = root;root = root-lchild;if (top != -1) root = stop-;root = root-rchild;return num;方法二：int getleafnum( BiNode* root)int num=0;B

12、iNode* p=root;SeqStack s;s.Init();s.push(p);while (!s.empty()while( p=s.gettop() & p!=NULL)s.push(p-lchlid);if (!s.empty()p=s.pop();if (p-lchild=NULL & p-rchilid=NULL) num+;elses.push (p-rchild);return num;作業(yè)：設(shè)計(jì)哈夫曼樹構(gòu)造算法中的 SELECT 函數(shù)void Select (element huffTree , int &i1, int &i2)int j, t=0;while (huffTreet.parent != -1)t+;i1=t;for(j=0; j2*n-1,j+)if (huffTreej.parent=-1 & huffTreej.weighthuffTreei1.weight) i1=j;/ 以上找到最小值，下面代碼查找次小值t=0;while (huffTreet.parent != -1 | t=i1)t+;i2=t;for(j=0; j2*n-1,j+)i2=j;if (huffTreej.parent=-1 & huffTreej.weighthuffTreei2.weigh