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

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

3、)r=p-next;p-next=first-next;first-next=p;p=r;作業：設計一個時間復雜度為0(n)的算法，實現數組 An中所有元素循環左移k個位置。算法一：將數組中的前k個元素存放到一個臨時數組中，再將余下的n-k個元素左移k個位置,最后將前k個元素從臨時數組復制到原來數組中的后k個位置。時間復雜度 0(n); 空間復雜度 0(k)算法二：先設計一個函數將數組向左循環移動一個位置，然后再調用這個函數k次，顯然，該算法的時間復雜度 0(n*k)算法三：將這個問題看做是把數組ab轉換成數組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;作業：約瑟夫環問題描述：設有編號為1, 2,n的n（n0）個人圍坐成一個圈，每個人持有一個密碼m,從第1個人開始報數，報到 m停止，報m的人出圈，如此下去，直到所有人全部出圈為止。當任意給 定n和m后，設計算法求n個人出圈的次序。要求：（1）分析問題,建立數據模型；（2）設計適合的存儲結構；（3）設計

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

6、1=ai;刪除第m個人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;時間復雜度 O(n*m) ； 空間復雜度 O(n)作業：設順序棧s中有2n個元素，從棧頂到棧底的元素一次為a2n,a2n-1,a1,要求通過一個循環隊列重新排列棧中的元素，使得從棧頂到棧底的元素依次a2n,a2n-2,a2, a2n-1,a2n-3,al，請設計算法實現該操作；要求空間復雜度和時間復雜度均為O (n)。算法步驟：( 1)將所有元素出棧入隊；( 2)依次將隊列元素出隊，如果是偶數結點則再入隊；如果是奇數結點則入棧；( 3)將奇數結點出棧并入隊；( 4)將偶數結點出隊并入棧；( 5)將所有元素出棧并入隊；( 6)將所有元素出隊并入棧

8、。作業：設計算法，把十進制整數轉換為二進制至九進制之間的任一進制輸出。分析 ： N=(N/D)*D+N%D 先得到的余數為低位，后輸出；后得到的余數為高位，后輸出； 因此，可將余數放入棧中，再將棧元素依次輸出。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- -);作業：設計算法，判斷給定模式是否為兩個主串的公共子序列。分析 ：調用兩次子序列判定函數即可。子序列判定函數偽代碼如下1 初始化比較的起始位置 , i=0,j=0;2

9、. length仁字符串A的長度，length2=字符串B的長度；3. 當 ile ngthl &jle ngth2,重復下面操作3.1 if Ai=Bj, i+, j+3.2 else i+;4. if j=length2,說明 B 中字符匹配成功，return 1; else return 0;作業：若在矩陣A中存在一個元素是第i行中最小值，又是第j列中最大值，則稱此元素為該 矩陣的一個鞍點。假設以二維數組存儲矩陣A，設計算法求矩陣中的所有鞍點，并分析最壞情況下的時間復雜度。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 “輸出鞍點：” ikaik;復雜度分析：O(nm+n 2)作業：編寫非遞歸算法，統計二叉樹中葉子結點個數方法一：const int maxsize=100;template struct BiNodeDataType data;BiNode *lchild;BiNode *rchild;template int BiTree:LeafNumber(BiNode *root

11、) int num=0;BiNode* smaxsize;/采用順序棧，并假定不會發生上溢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;作業：設計哈夫曼樹構造算法中的 SELECT 函數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