2023青海省數(shù)據(jù)庫入門入門

1、1、編程實現(xiàn)單鏈表的就地逆置。23在數(shù)組 A1.n中有n個數(shù)據(jù)，試建立一個帶有頭結(jié)點的循環(huán)鏈表，頭指針為h，要求鏈中數(shù)據(jù)從小到大排列，重復的數(shù)據(jù)在鏈中只保存一個.2、二路插入排序是將待排關(guān)鍵字序列r1.n中關(guān)鍵字分二路分別按序插入到輔助向量d1.n前半部和后半部注:向量d可視為循環(huán)表，其原那么為，先將rl賦給d1，再從r2 記錄開始分二路插入。編寫實現(xiàn)二路插入排序算法。3、有一個帶頭結(jié)點的單鏈表，每個結(jié)點包括兩個域，一個是整型域info，另一個是指向下一個結(jié)點的指針域next。假設(shè)單鏈表已建立，設(shè)計算法刪除單鏈表中所有重復出現(xiàn)的結(jié)點，使得info域相等的結(jié)點只保存一個。#include typ

2、edef char datatype;typedef struct node datatype data; struct node * next; listnode;typedef listnode* linklist;/*-*/* 刪除單鏈表中重復的結(jié)點 */*-*/linklist deletelist(linklist head) listnode *p,*s,*q; p=head-next; while(p) s=p; q=p-next; while(q) if(q-data=p-data) s-next=q-next;free(q); q=s-next; else s=q; /*找與

3、P結(jié)點值相同的結(jié)點*/ q=q-next; p=p-next; return head; 4、編寫一個過程，對一個nn矩陣，通過行變換，使其每行元素的平均值按遞增順序排列。5、約瑟夫環(huán)問題Josephus問題是指編號為1、2、，n的nn0個人按順時針方向圍坐成一圈，現(xiàn)從第s個人開始按順時針方向報數(shù)，數(shù)到第m個人出列，然后從出列的下一個人重新開始報數(shù)，數(shù)到第m的人又出列，如此重復直到所有的人全部出列為止?，F(xiàn)要求采用循環(huán)鏈表結(jié)構(gòu)設(shè)計一個算法，模擬此過程。#includetypedef int datatype;typedef struct nodedatatype data; struct nod

4、e *next;listnode;typedef listnode *linklist;void jose(linklist head,int s,int m)linklist k1,pre,p; int count=1; pre=NULL; k1=head; /*k1為報數(shù)的起點*/ while (count!=s) /*找初始報數(shù)起點*/ pre=k1; k1=k1-next; count+; while(k1-next!=k1) /*當循環(huán)鏈表中的結(jié)點個數(shù)大于1時*/ p=k1; /*從k1開始報數(shù)*/ count=1; while (count!=m) /*連續(xù)數(shù)m個結(jié)點*/ pre=

5、p; p=p-next; count+; pre-next=p-next; /*輸出該結(jié)點，并刪除該結(jié)點*/ printf(%4d,p-data); free(p); k1=pre-next; /*新的報數(shù)起點*/ printf(%4d,k1-data); /*輸出最后一個結(jié)點*/ free(k1);main()linklist head,p,r; int n,s,m,i; printf(n=); scanf(%d,&n); printf(s=); scanf(%d,&s); printf(m=,&m); scanf(%d,&m); if (n1) printf(ndata=n; r=head

6、; for (i=n-1;i0;i-) /*建立剩余n-1個結(jié)點*/ p=(linklist)malloc(sizeof(listnode); p-data=i; p-next=head; head=p; r-next=head; /*生成循環(huán)鏈表*/ jose(head,s,m); /*調(diào)用函數(shù)*/ 6、數(shù)組A和B的元素分別有序，欲將兩數(shù)組合并到C數(shù)組，使C仍有序，應(yīng)將A和B拷貝到C，只要注意A和B數(shù)組指針的使用，以及正確處理一數(shù)組讀完數(shù)據(jù)后將另一數(shù)組余下元素復制到C中即可。void union(int A,B,C,m,n)/整型數(shù)組A和B各有m和n個元素，前者遞增有序，后者遞減有序，本算法

7、將A和B歸并為遞增有序的數(shù)組C。i=0; j=n-1; k=0;/ i，j，k分別是數(shù)組A,B和C的下標，因用C描述，下標從0開始while(i=0) if(aibj) ck+=ai+ else ck+=bj-;while(i=0) ck+=bj-;算法結(jié)束4、要求二叉樹按二叉鏈表形式存儲。15分1寫一個建立二叉樹的算法。2寫一個判別給定的二叉樹是否是完全二叉樹的算法。BiTree Creat() /建立二叉樹的二叉鏈表形式的存儲結(jié)構(gòu)ElemType x；BiTree bt;scanf(“%d,&x); /此題假定結(jié)點數(shù)據(jù)域為整型if(x=0) bt=null;else if(x0) bt=(

8、BiNode *)malloc(sizeof(BiNode);bt-data=x; bt-lchild=creat(); bt-rchild=creat(); else error(“輸入錯誤)；return(bt);/結(jié)束 BiTreeint JudgeComplete(BiTree bt) /判斷二叉樹是否是完全二叉樹,如是，返回1，否那么，返回0int tag=0; BiTree p=bt, Q; / Q是隊列，元素是二叉樹結(jié)點指針，容量足夠大if(p=null) return (1);QueueInit(Q); QueueIn(Q,p); /初始化隊列，根結(jié)點指針入隊while (!Q

9、ueueEmpty(Q)p=QueueOut(Q); /出隊 if (p-lchild & !tag) QueueIn(Q,p-lchild); /左子女入隊 else if (p-lchild) return 0; /前邊已有結(jié)點為空，本結(jié)點不空 else tag=1; /首次出現(xiàn)結(jié)點為空 if (p-rchild & !tag) QueueIn(Q,p-rchild); /右子女入隊 else if (p-rchild) return 0; else tag=1; /whilereturn 1; /JudgeComplete7、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊

10、，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對邊進行排序，然后從大到小將邊刪除。每刪除一條當前權(quán)值最大的邊后，就去測試圖是否仍連通，假設(shè)不再連通，那么將該邊恢復。假設(shè)仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。 void SpnTree (AdjList g) /用“破圈法求解帶權(quán)連通無向圖的一棵最小代價生成樹。typedef struct int i,j,wnode; /設(shè)頂點信息就是頂點編號，權(quán)是整型數(shù) node edge; scanf( %d%d,&e,&n) ; /輸入邊數(shù)和頂點數(shù)。 for (i=1;i=e;i+) /輸入e條邊：頂點，權(quán)值。 scanf(%d%d%d ,

11、&edgei.i ,&edgei.j ,&edgei.w); for (i=2;i=e;i+) /按邊上的權(quán)值大小，對邊進行逆序排序。 edge0=edgei; j=i-1;while (edgej.w=n) /破圈，直到邊數(shù)e=n-1. if (connect(k) /刪除第k條邊假設(shè)仍連通。 edgek.w=0; eg-; /測試下一條邊edgek，權(quán)值置0表示該邊被刪除k+; /下條邊 /while /算法結(jié)束。 connect()是測試圖是否連通的函數(shù)，可用圖的遍歷實現(xiàn)，8、二叉樹的層次遍歷序列的第一個結(jié)點是二叉樹的根。實際上，層次遍歷序列中的每個結(jié)點都是“局部根。確定根后，到二叉樹的

12、中序序列中，查到該結(jié)點，該結(jié)點將二叉樹分為“左根右三局部。假設(shè)左、右子樹均有，那么層次序列根結(jié)點的后面應(yīng)是左右子樹的根；假設(shè)中序序列中只有左子樹或只有右子樹，那么在層次序列的根結(jié)點后也只有左子樹的根或右子樹的根。這樣，定義一個全局變量指針R，指向?qū)哟涡蛄写幚碓?。算法中先處理根結(jié)點，將根結(jié)點和左右子女的信息入隊列。然后，在隊列不空的條件下，循環(huán)處理二叉樹的結(jié)點。隊列中元素的數(shù)據(jù)結(jié)構(gòu)定義如下：typedef struct int lvl; /層次序列指針，總是指向當前“根結(jié)點在層次序列中的位置int l,h; /中序序列的下上界int f; /層次序列中當前“根結(jié)點的雙親結(jié)點的指針int lr

13、; / 1雙親的左子樹 2雙親的右子樹qnode; BiTree Creat(datatype in,level,int n)/由二叉樹的層次序列l(wèi)eveln和中序序列inn生成二叉樹。 n是二叉樹的結(jié)點數(shù)if (ndata=level0; p-lchild=null; p-rchild=null; /填寫該結(jié)點數(shù)據(jù)for (i=0; ilchild=null; s.lvl=+R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s); else if (i=n-1) /根結(jié)點無右子樹，遍歷序列的1n-1是左子樹p-rchild=null; s.lvl=+

14、R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); else /根結(jié)點有左子樹和右子樹s.lvl=+R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);/左子樹有關(guān)信息入隊列s.lvl=+R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);/右子樹有關(guān)信息入隊列while (!empty(Q) /當隊列不空，進行循環(huán)，構(gòu)造二叉樹的左右子樹 s=delqueue(Q); father=s.f; for (i=s.l; idata=levels.lvl; p-lchild=n

15、ull; p-rchild=null; /填寫該結(jié)點數(shù)據(jù) if (s.lr=1) father-lchild=p; else father-rchild=p； /讓雙親的子女指針指向該結(jié)點 if (i=s.l)p-lchild=null; /處理無左子女s.lvl=+R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); else if (i=s.h) p-rchild=null; /處理無右子女 s.lvl=+R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); elses.lvl=+R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);/左子樹有關(guān)信息入隊列 s.lvl=+R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); /右子樹有關(guān)信息入隊列 /結(jié)束while (!