數(shù)據(jù)結(jié)構(gòu)導(dǎo)論作業(yè)

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論1、章節(jié)作業(yè)第一章 概論1設(shè)計(jì)算法在整型數(shù)組An中查找值為K的元素，若找到，則輸出其位置i(0in-1)，否則輸出-1作為標(biāo)志，并分析算法的時(shí)間復(fù)雜度。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； 當(dāng)查找成功時(shí)，Ai與k比較次數(shù)n；當(dāng)查找不成功時(shí)，Ai與k比較n次，所以，算法時(shí)間復(fù)雜度T(n)=O(n)。2寫出計(jì)算方陣Ann與Bnn乘積Cnn的算法，分析算法的時(shí)間復(fù)雜度。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試分別以順序表和帶頭結(jié)點(diǎn)的單鏈表作存儲結(jié)構(gòu)，各寫一個(gè)實(shí)現(xiàn)線性表的就地(即使用盡可能少的附加空間)逆置的算法，在原表的存儲空間內(nèi)將線性表(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;第三章 棧、隊(duì)列和數(shù)組1有一個(gè)整數(shù)序列，其輸入順序?yàn)?0，30，90，-10，45，78，試?yán)脳⑵漭敵鲂蛄懈淖優(yōu)?0，-10，45，90，78，20，試給出該整數(shù)序列進(jìn)棧和出棧的操作步驟。(用push(x)表示x進(jìn)棧，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設(shè)有編號為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺，試寫出這四輛列車開出車站的所有可能的順序。一號列車先出站：1234,1243,1324,1342,1432;二號列車先出站：2134,2143,2314,2341,2431；三好列車先出站：3214,3241,3421；四號列車先出站：4321；但是這里的 4123、4132、4213、4231都不是正解,所以共有14種可能3假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)列尾結(jié)點(diǎn)(注意不設(shè)頭指針)，試編寫相應(yīng)的初始化隊(duì)列、入隊(duì)列和出隊(duì)列算法。類型定義：typedef struct linksd_queueDataType data;struct linked_queue *next; LqueueTp;隊(duì)列的初始化void InitQueue(LqueueTp *rear) LqueueTp *p;p=(LqueueTp *)malloc(sizeof(LqueueTp);rear=p;rear-next=rear;入隊(duì)列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出隊(duì)列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è)以數(shù)組cycquem存放循環(huán)隊(duì)列的元素，同時(shí)設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)列尾元素位置和內(nèi)含元素的個(gè)數(shù)。試給出此循環(huán)隊(duì)列的隊(duì)列滿和隊(duì)列空的條件，并寫出相應(yīng)的入隊(duì)列和出隊(duì)列的算法。類型定義：typedef struct cycqueueDataType datam;int rear;int quelen; CycqueueTp;CycqueueTp *cq隊(duì)列滿條件是：（cq-quelen=m）。隊(duì)列空條件是：（cq-quelen=0）入隊(duì)列：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;出隊(duì)列：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;取隊(duì)列首元素：DataType GetHead(CycqueueTp *cq) DataType x;x=cq-datacq-rear=m-cq-quelen% m;return x;第四章 樹和二叉樹1算法設(shè)計(jì)題 (1)以二叉鏈表作存儲結(jié)構(gòu)，試編寫求二叉樹葉子結(jié)點(diǎn)個(gè)數(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è)計(jì)算法求二叉樹的結(jié)點(diǎn)的個(gè)數(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)設(shè)計(jì)算法按先序次序打印二叉樹T中葉子結(jié)點(diǎn)的值。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樹的存儲結(jié)構(gòu)采用孩子兄弟鏈表，試編寫樹的按層次遍歷算法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求下列有向圖中從頂點(diǎn)vo到其余各頂點(diǎn)的最短路徑及長度(給出求解的過程)。 步驟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寫出將一個(gè)無向圖的鄰接矩陣轉(zhuǎn)換成鄰接表的算法。#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假設(shè)線性表中結(jié)點(diǎn)是按鍵值遞增的順序排列，試寫一順序查找算法，將崗哨設(shè)在高下標(biāo)端。然后分別求出等概率情況下查找成功和不成功時(shí)的平均查找長度。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結(jié)點(diǎn)在給定的二叉排序樹中所在的層數(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，分別畫出應(yīng)用直接插入排序、直接選擇排序、冒泡排序、歸并排序?qū)ι鲜鲂蛄羞M(jìn)行排序過程。直接插入排序序：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趟結(jié)果： 11 22 25 5 34 44 61 76 3 14 100 120第2趟結(jié)果： 11 22 5 25 34 44 61 3 14 76 100 120第3趟結(jié)果： 5 5 22 25 34 44 3 14 61 76 100 120第4趟結(jié)果： 5 11 22 25 34 3 14 44 61 76 100 120第5趟結(jié)果： 5 11 22 25 3 14 34 44 61 76 100 120第6趟結(jié)果： 5 11 22 3 14 25 34 44 61 76 100 120第7趟結(jié)果： 5 11 3 14 22 25 34 44 61 76 100 120第8趟結(jié)果： 5 3 11 14 22 25 34 44 61 76 100 120第9趟結(jié)果： 3 5 11 14 22 25 34 44 61 76 100 120第10趟結(jié)果： 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