數(shù)據(jù)結構導論作業(yè)

數(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