數(shù)據(jù)結構導論作業(yè)_第1頁
數(shù)據(jù)結構導論作業(yè)_第2頁
數(shù)據(jù)結構導論作業(yè)_第3頁
數(shù)據(jù)結構導論作業(yè)_第4頁
數(shù)據(jù)結構導論作業(yè)_第5頁
已閱讀5頁,還剩14頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

數(shù)據(jù)結構導論1、章節(jié)作業(yè)第一章 概論1設計算法在整型數(shù)組An中查找值為K的元素,若找到,則輸出其位置i(0in-1),否則輸出-1作為標志,并分析算法的時間復雜度。int search (int A,int n,int k) int i;i=0;while (i=n-1)if (Ai!=k) i+;else break;if (i=n-1) return I;else return -1; 當查找成功時,Ai與k比較次數(shù)n;當查找不成功時,Ai與k比較n次,所以,算法時間復雜度T(n)=O(n)。2寫出計算方陣Ann與Bnn乘積Cnn的算法,分析算法的時間復雜度。void matrixmultiply (int An,int Bn,int Cn,int n) int I,j;for (i=0;in;i+)for (j=0;jn;j+) Cij=0;for (k=0;knext;Int m=0;while (p!=NULL) if(p-data=x) m+;p=p-next;return m;2試分別以順序表和帶頭結點的單鏈表作存儲結構,各寫一個實現(xiàn)線性表的就地(即使用盡可能少的附加空間)逆置的算法,在原表的存儲空間內將線性表(a1,a2,an)逆置為(an,an-1,a1)。順序表逆置算法void inverse_sqlist(Seqlist L)int m,n,k;DataType temp;m=0; n=L.length-1;while (mnext;head-next=NULL;while (p!=NULL)q=p-next;p-next=head-next;head-next=p;p=q;第三章 棧、隊列和數(shù)組1有一個整數(shù)序列,其輸入順序為20,30,90,-10,45,78,試利用棧將其輸出序列改變?yōu)?0,-10,45,90,78,20,試給出該整數(shù)序列進棧和出棧的操作步驟。(用push(x)表示x進棧,pop(x)表示x出棧)push(20),push(30),pop(30),push(90),push(-10),pop(-10),push(45),pop(45),pop(90),push(78),pop(78),pop(20)2設有編號為1,2,3,4的四輛列車,順序進入一個棧式結構的站臺,試寫出這四輛列車開出車站的所有可能的順序。一號列車先出站:1234,1243,1324,1342,1432;二號列車先出站:2134,2143,2314,2341,2431;三好列車先出站:3214,3241,3421;四號列車先出站:4321;但是這里的 4123、4132、4213、4231都不是正解,所以共有14種可能3假設以帶頭結點的循環(huán)鏈表表示隊列,并且只設一個指針指向隊列尾結點(注意不設頭指針),試編寫相應的初始化隊列、入隊列和出隊列算法。類型定義:typedef struct linksd_queueDataType data;struct linked_queue *next; LqueueTp;隊列的初始化void InitQueue(LqueueTp *rear) LqueueTp *p;p=(LqueueTp *)malloc(sizeof(LqueueTp);rear=p;rear-next=rear;入隊列void EnQueue(LqueueTp *rear;DataType x) LqueueTp *p;p=(LqueueTp*)malloc(sizeof(LqueueTp);p-data=x;p-next=rear-next;rear-next=p;rear=p出隊列OutQueue(LqueueTp *rear,DataType *x) LqueueTp *h,*p ;if (rear=rear-next) error; return 0; else h=rear-next;p=h-next;*x=p-data;h-next=p-next;if (p=rear)rear=h;free(p);return 1;4假設以數(shù)組cycquem存放循環(huán)隊列的元素,同時設變量rear和quelen分別指示循環(huán)隊列中隊列尾元素位置和內含元素的個數(shù)。試給出此循環(huán)隊列的隊列滿和隊列空的條件,并寫出相應的入隊列和出隊列的算法。類型定義:typedef struct cycqueueDataType datam;int rear;int quelen; CycqueueTp;CycqueueTp *cq隊列滿條件是:(cq-quelen=m)。隊列空條件是:(cq-quelen=0)入隊列:int EnCycQueue(CycqueueTp *cq;DataType x)if (cq-quelen=m) error; return 0;else cq-rear=(cq-rear+1)%m;cq-datacq-rear=x;cq-quelen=cq-quelen+1;return 1;出隊列:int OutCyQueue(CycqueueTp *cq)if (cq-quelen=0) error; return 0;else cq-quelen=cq-quelen-1;*x=cq-data(cq-rear+m-cq-quelen)% m;return 1;取隊列首元素:DataType GetHead(CycqueueTp *cq) DataType x;x=cq-datacq-rear=m-cq-quelen% m;return x;第四章 樹和二叉樹1算法設計題 (1)以二叉鏈表作存儲結構,試編寫求二叉樹葉子結點個數(shù)的算法。typedef struct btnode DataType data;struct btnode *lchild,*rchild;*BinTree;int leafnode_num(BinTree bt )if (bt=NULL) return 0 ;elseif (bt-lchild=NULL) & (bt-rchild=NULL)return 1;elsereturn leafnode_num (bt-lchild)+leafnode_num (bt-rchild); (2)設計算法求二叉樹的結點的個數(shù)。typedef struct btnodeDataType data;struct btnode *lchild,*rchild;*BinTree;int node_num (BinTree bt)if (bt=NULL) return 0;elsereturn node_num(bt-lchild)+node_num(bt-rchild)+1; (3)設計算法按先序次序打印二叉樹T中葉子結點的值。typedef struct btnode int data;struct btnode *lchild,*rchild;*BinTree;void preorder (BinTree bt) if (bt!=NULL) if (bt-lchild=NULL) & (bt-rchild=NULL))printf(“%d”,bt-dta);preorder(bt-lchild);preorder(bt-rchild);2樹的存儲結構采用孩子兄弟鏈表,試編寫樹的按層次遍歷算法typedef struct tnode int data;struct tnode *son,*brother;*Tree;void tree_travel (Tree root ) InitQueue(Q);if (root1=NULL) EnQueue( q , root );while (!EmptyQueue(Q) p=GetHead(Q); OutQueue (Q);prinf(“%d” , p-data);p=p-son;while (p!=NULL) Enqueue (Q , p);p=p-brother;第五章 圖1求下列有向圖中從頂點vo到其余各頂點的最短路徑及長度(給出求解的過程)。 步驟Sudist1dist2dist3dist4dist5dist6第1步v0123Max_intMax_intMax_int第2步v0,v1V11232Max_intMax_int第3步v0,v1,v4V41232Max_int3第4步v0,v1,v4,v2V21232Max_int3第5步v0,v1,v4,v2,v3V3123263第6步v0,v1,v4,v2,v3,v6V6123263第7步v0,v1,v4,v2,v3,v6,v5V51232632寫出將一個無向圖的鄰接矩陣轉換成鄰接表的算法。#define vnum 20typedef struct graph VertexType vexsvnum;int arcsvnumvnum;int vexnum,arcnum; GraphTp_Mat;typedef struct arcnodeint adjvex;struct arcnode *nextarc; ArcNodeTp;typedef struct vexnode int vertex;ArcNodeTp *firstarc;AdjLisvnum;typedef struct graph AdjLis adjlist;int vexnum,arcnum; GraphTp_Adj;void Matrix_to_Adjlis(GraphTp_Mat *ga,GraphTp_Adj *gp) int I,j;ArcNodeTp *p;gp-vexnum=ga-vexnum;gp-arcnum=ga-arcnum;for ( i =0;Ivexnum;i+) gp-adjlisi.vertex=I;gp-adjlisi.firstarc=NULL;for (i=0;Ivexnum;i+)for (j=0;jvesnum;j+)if (ga-arcsij=1)p=(ArcNodeTp *)malloc(sizeof(ArcNodeTp);p-adjvex=j;p-nextarc=ga-adjlisi.firstarc;ga-adjlisi.firstarc=p;第六章 查找1假設線性表中結點是按鍵值遞增的順序排列,試寫一順序查找算法,將崗哨設在高下標端。然后分別求出等概率情況下查找成功和不成功時的平均查找長度。int search_sqtable(Sqtable R,KeyType k)int i=0;R. elem R.n.key=k;while (R. elem i.keyki=R.n) return -1;else return i;2試編寫算法求鍵值為k結點在給定的二叉排序樹中所在的層數(shù)。int level_count(BinTree bst,KeyType k)int lev=0;BSTNode *p=bst;while (p!=NULL)lev+;if (p-data=k) return lev;if (p-datarchild;elsep=p-lchild;return 0;3試寫出從大到小輸出二叉排序樹中所有不小于x的元素的算法。void Print_NLT(BinTree T,int x)if (T!=NULL)Print_NLT(T-rchild,x);If (T-data=x)printf(“%dn”,T-data);Print_NLT(T-lchild,x);第七章 排序1對于給定的一組鍵值:83,40,63,13,84,35,96,57,39,79,6l,15,分別畫出應用直接插入排序、直接選擇排序、冒泡排序、歸并排序對上述序列進行排序過程。直接插入排序序:83 40 63 13 84 35 96 57 39 79 61 1540 83 63 13 84 35 96 57 39 79 61 1540 63 83 13 84 35 96 57 39 79 61 1513 40 63 83 84 35 96 57 39 79 61 1513 40 63 83 84 35 96 57 39 79 61 1513 35 40 63 83 84 96 57 39 79 61 1513 35 40 63 83 84 96 57 39 79 61 1513 35 40 57 63 83 84 96 39 79 61 1513 35 39 40 57 63 83 84 96 79 61 1513 35 39 40 57 63 79 83 84 96 61 1513 35 39 40 57 61 63 79 83 84 96 1513 15 35 39 40 57 61 63 79 83 84 96直接選擇排序:84 40 63 13 84 35 96 57 39 79 61 1513 40 63 83 84 35 96 57 39 79 61 1513 15 63 83 84 35 96 57 39 79 61 4013 15 35 83 84 63 96 57 39 79 61 4013 15 35 39 84 63 96 57 83 79 61 4013 15 35 39 40 63 96 57 83 79 61 8413 15 35 39 40 57 96 63 83 79 61 8413 15 35 39 40 57 61 63 83 79 96 8413 15 35 39 40 57 61 63 83 79 96 8413 15 35 39 40 57 61 63 83 79 96 8413 15 35 39 40 57 61 63 79 83 96 8413 15 35 39 40 57 61 63 79 83 96 8413 15 35 39 40 57 61 63 79 83 84 96冒泡排序: 初始數(shù)據(jù): 25 11 22 34 5 44 76 61 100 3 14 120第1趟結果: 11 22 25 5 34 44 61 76 3 14 100 120第2趟結果: 11 22 5 25 34 44 61 3 14 76 100 120第3趟結果: 5 5 22 25 34 44 3 14 61 76 100 120第4趟結果: 5 11 22 25 34 3 14 44 61 76 100 120第5趟結果: 5 11 22 25 3 14 34 44 61 76 100 120第6趟結果: 5 11 22 3 14 25 34 44 61 76 100 120第7趟結果: 5 11 3 14 22 25 34 44 61 76 100 120第8趟結果: 5 3 11 14 22 25 34 44 61 76 100 120第9趟結果: 3 5 11 14 22 25 34 44 61 76 100 120第10趟結果: 3 5 11 14 22 25 34 44 61 76 100 120歸并排序:83 40 63 13 84 35 96 57 39 79 61 1540 83 13 63 35 84 57 96 39 79 15 6113 40 63 83 35 57 84 96 15 39 61 7913 35 40 57 63 83 84 96 15 39 61 7913 15 35 3

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論