數(shù)據(jù)結構課件-作業(yè)詳解

數(shù)據(jù)結構作業(yè)詳解

作業(yè)1線性表1.將順序表逆置，要求用最少的附加空間。(略)2.從鍵盤讀入n個整數(shù)(升序)，請編寫算法實現(xiàn)：

(1)CreateList()：建立帶表頭結點的單鏈表；

(2)PrintList()：顯示單鏈表，(H->10->20->30->40);(3)InsertList()：在有序單鏈表中插入元素x；

(4)ReverseList()：單鏈表就地逆置；

(5)DelList()：在有序單鏈表中刪除所有值大于mink且小于maxk的元素。

typedefintElemType;typedefstructnode{

ElemTypedata;

structnode*link;}Lnode,*LinkList;

作業(yè)1線性表2.(1)CreateList()：建立帶表頭結點的單鏈表；voidCreate_L(LinkList&L,intn){LinkListp;inti;L=(LinkList)malloc(sizeof(Lnode));L->data=0;L->link=NULL;

for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(Lnode));scanf("%d",&p->data);

p->link=L->link;L->link=p; }}生成頭結點L頭結點0^pan^

作業(yè)1線性表2.(1)CreateList()：建立帶表頭結點的單鏈表；voidCreate_L(LinkList&L,intn){LinkListp;inti;L=(LinkList)malloc(sizeof(Lnode));L->data=0;L->link=NULL;

for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(Lnode));scanf("%d",&p->data);

p->link=L->link;L->link=p; }}生成頭結點L頭結點0pan-1an

^

作業(yè)1線性表2.(1)CreateList()：建立帶表頭結點的單鏈表；voidCreate_L(LinkList&L,intn){LinkListp;inti;L=(LinkList)malloc(sizeof(Lnode));L->data=0;L->link=NULL;

for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(Lnode));scanf("%d",&p->data);

p->link=L->link;L->link=p; }}生成頭結點L頭結點0an-1

an

^

作業(yè)1線性表2.(1)CreateList()：建立帶表頭結點的單鏈表；voidCreate_L(LinkList&L,intn){LinkListp;inti;L=(LinkList)malloc(sizeof(Lnode));L->data=0;L->link=NULL;

for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(Lnode));scanf("%d",&p->data);

p->link=L->link;L->link=p; }}生成頭結點L頭結點0a1

a2

^an

^……

作業(yè)1線性表2.(2)PrintList()：顯示單鏈表，(H->10->20->30->40);voidxsList(LinkListL){ LinkListp=L->link; while(p) { printf("%d",p->data);

p=p->link; }}L頭結點0a1

a2

^an

^……

作業(yè)1線性表2.(3)InsertList()：在有序單鏈表中插入元素x；voidyxcharu(LinkList&L,ElemTypee){ LinkListpre,p,s;

pre=L; p=L->link; while(p&&p->data<e) {pre=p; p=p->link; } s=(LinkList)malloc(sizeof(Lnode));

s->data=e;

s->link=p;

pre->link=s;}L頭結點0a1

a2

^an

^……

作業(yè)1線性表2.(4)ReverseList()：單鏈表就地逆置；La1a2頭結點a4

^a3La4a3頭結點a1

^a2q

作業(yè)1線性表2.(4)ReverseList()：單鏈表就地逆置；voidnizhi(LinkList&L){ LinkListp=L->link,q=L->link->link,u;

p->link=NULL; while(q) { u=q->link; q->link=L->link; L->link=q; q=u;}}La1^a2頭結點a4

^a3q將以q為頭指針的鏈表中結點依次插入為L的后繼pu

作業(yè)1線性表2.(5)DelList()：在有序單鏈表中刪除所有值大于mink且小于maxk的元素。

voidDelList(LinkList&L,ElemTypemink,ElemTypemaxk){ LinkListp=L,q; while(p->link&&p->link->data<mink)

p=p->link; q=p; while(q&&q->data<maxk)

q=q->link; p->link=q;}L1020頭結點40

^30刪除15-35間的元素ppp——第一個刪除元素的前驅qqqqq——最后一個刪除元素的后繼

作業(yè)1線性表main(){ LinkListL; intn,i,mink,maxk;

ElemTypee;charchoice='0';

while(choice!='q') {printf("\n****************\n"); printf("1.建立單鏈表"); printf("2.取元素值"); printf("3.查找\n"); printf("4.插入"); printf("5.刪除"); printf("6.顯示\n"); printf("7.刪除大于mink且小于maxk的元素值"); printf("8.就地升序排序\n"); printf("9.就地逆置"); printf("a.有序表插入"); printf("q.退出\n"); printf("\n請選擇操作："); fflush(stdin); scanf("%c",&choice);

作業(yè)1線性表switch(choice){case'1':printf("請輸入單鏈表中結點個數(shù)：");

scanf("%d",&n);Create_L(L,n);break;case'2':printf("請輸入元素位序："); scanf("%d",&i);GetElem_L(L,i,e); printf("元素值為：%d\n",e);break;case'3':printf("請輸入要查找的元素："); scanf("%d",&e); if(dlbcz(L,e))printf("查找成功！");else printf("查找失敗。");break;……}}//endofwhile(choice!='q')}//endofmain()

作業(yè)2棧、隊列、數(shù)組

1.若進棧序列為ABCD，請寫出全部可能的出棧序列和不可能的出棧序列。

可能的出棧序列：(14種)dcbacdbabacdcbdaadcbcbadbdcaacdbbcdaacbdbcadabdcbadcabcd不可能的出棧序列：(10種)dbcadbacdabcdacbdcabcabdcdabbdaccadbadbc2.簡要說明循環(huán)隊列如何判斷隊滿和隊空？當犧牲一個存儲結點時(以“隊列頭指針在隊列尾指針的下一位置”作為隊列“滿”狀態(tài)的標志)隊滿的條件：(rear+1)%MaxQsize==front；判斷隊空的條件為：front==rear。

作業(yè)2棧、隊列、數(shù)組

3.設A為n階對稱矩陣，采用壓縮存儲存放于一維數(shù)組F[n(n+1)/2]中（從F[0]開始存放），請分別給出存放上三角陣時任一矩陣元素aij（1≤i,j≤n）的地址計算公式和存放下三角陣時任一矩陣元素aij（1≤i,j≤n）的地址計算公式。存放上三角陣時，任一矩陣元素aij（1≤i,j≤n）的地址計算公式為：

存放下三角陣時，任一矩陣元素aij（1≤i,j≤n）的地址計算公式為：

作業(yè)2棧、隊列、數(shù)組

4.寫出下面稀疏矩陣的三元組順序表和十字鏈表表示

。5.棧采用順序棧存儲，試設計算法實現(xiàn)將表達式轉換成后綴表達式輸出。(略)

作業(yè)3樹

1.請分別畫出具有3個結點的樹和3個結點的二叉樹的所有不同形態(tài)。

樹二叉樹

作業(yè)3樹

2.已知二叉樹的先序遍歷序列是EABDCFHGIKJ，中序遍歷序列是ABCDEFGHIJK，請構造二叉樹，并寫出其層次遍歷序列和后序遍歷序列。先序左子樹右子樹根中序左子樹右子樹根先序EABDCFHGIKJ中序ABCDEFGHIJKEAAABBBDDDCFFFHHGHIIIKKJ層次序列為：后序序列為：EAFBHIGDCJKCDBAGJKIHFE

作業(yè)3樹

3.將下圖所示的森林轉換成一棵二叉樹。

ABCDKLEFGHIJABCDEFGHIJKLABCDEFGHIJKL

作業(yè)3樹

3.將下圖所示的二叉樹還原成樹或森林。ABCDEFGHIKLMNJABCDEFGHIKLMNJABCDLMNEFGHIJK

作業(yè)3樹

3.假設用于通信的電文由7個字母組成{A,B,C,D,E,F,G}，字母在電文中出現(xiàn)的頻率分別為0.17、0.09、0.12、0.06、0.32、0.03、0.21。試為這7個字母設計哈夫曼編碼，并計算其帶權路徑長度WPL。

0.17A0.09B0.12C0.06D0.32E0.03F0.21G0.090.180.290.390.611.00010000011111A:B:C:D:E:F:G:101001100000111000001WPL=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56

作業(yè)3樹

4.二叉樹采用二叉鏈表存儲，試設計算法實現(xiàn):(1)CreateBT(BiTree&T)：從鍵盤輸入二叉樹的先序遍歷序列字符串（以”#”代表空結點），建立其二叉鏈表;

如輸入：AB#D##CE#F###(2)ExchangeBT(BiTreeT):設計遞歸算法實現(xiàn)二叉樹中所有結點的左右孩子交換；(3)CountLeaf(BiTreeT,TElemTypex,int&count):統(tǒng)計以值為x的結點為根的子樹中葉子結點的數(shù)目；(4)DispBiTree(BiTreeT,intlevel):按樹狀打印二叉樹ABDCEF打印得到：#C###F##EA##D#B

作業(yè)3樹

4.二叉樹采用二叉鏈表存儲，試設計算法實現(xiàn):(1)CreateBT(BiTree&T)：從鍵盤輸入二叉樹的先序遍歷序列字符串（以”#”代表空結點），建立其二叉鏈表;voidCreateBT(BiTree&T){charch;scanf("%c",&ch);

if(ch=='#')T=NULL;

else{ T=(BiTNode*)malloc(sizeof(BiTNode));T->data=ch;

CreateBT(T->lchild); CreateBT(T->rchild); }}

作業(yè)3樹

(2)ExchangeBT(BiTreeT):設計遞歸算法實現(xiàn)二叉樹中所有結點的左右孩子交換；voidExchangeBT(BiTreeT){ BiTreetemp;if(T){ temp=T->lchild; T->lchild=T->rchild; T->rchild=temp;

ExchangeBT(T->lchild); ExchangeBT(T->rchild); }}

作業(yè)3樹

(3)CountLeaf(BiTreeT,TElemTypex,int&count):統(tǒng)計以值為x的結點為根的子樹中葉子結點的數(shù)目；//查找值為x的結點BiTreeSearchTree(BiTreeT,charx){BiTreebt;if(T){ if(T->data==x) returnT;

bt=SearchTree(T->lchild,x);if(bt==NULL)

bt=SearchTree(T->rchild,x);

returnbt; }

returnNULL;}

作業(yè)3樹

(3)CountLeaf(BiTreeT,TElemTypex,int&count):統(tǒng)計以值為x的結點為根的子樹中葉子結點的數(shù)目；//統(tǒng)計根為T的子樹的葉子結點個數(shù)intLeafCount(BiTreeT){staticintcount;if(T){if((T->lchild==NULL)&&(T->rchild==NULL))count++;else{count=LeafCount1(T->lchild);count=LeafCount1(T->rchild);

}}

returncount;}

作業(yè)3樹

(4)DispBiTree(BiTreeT,intlevel):按樹狀打印二叉樹voidDispBiTree(BiTreeT,intlevel){inti;

if(T){ DispBiTree(T->rchild,level+1);

for(i=0;i<level;i++)printf("#"); printf("%c\n",T->data);

DispBiTree(T->lchild,level+1); }}ABDCEF打?。?C###F##EA##D#B對于根為T，層次為level的子樹：①打印其下一層(level+1層)右子樹；②打印level個#后，打印根結點；③打印其下一層(level+1層)左子樹；

*結點左邊的’#’個數(shù)為其層次數(shù)*

作業(yè)3樹

main(){BiTreeT,SubT;charSubch;

intcountl=0;printf("輸入先序序列建立二叉樹：\n");CreateBT(T);printf("\n二叉樹為：\n");DispBiTree(T,0);printf("交換結點的左右孩子\n");ExchangeBT(T);printf("\n此時二叉樹為：\n");DispBiTree(T,0);printf("輸入要統(tǒng)計葉子結點個數(shù)的子樹的根：");fflush(stdin); scanf("%c",&Subch);

SubT=SearchTree(T,Subch);

countl=LeafCount1(SubT);printf("葉子結點數(shù)為：%d\n",countl);}

作業(yè)4圖

1.已知帶權有向圖，畫出該圖的鄰接矩陣存儲結構。2afbdgche69783251302421

作業(yè)4圖

2.無向圖鄰接表存儲結構如圖所示：(1)畫出該無向圖；(2)寫出在該鄰接表上，從頂點1出發(fā)所得到的深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)序列。

作業(yè)4圖

(1)畫出該無向圖；13247586

作業(yè)4圖

(2)寫出在該鄰接表上，從頂點1出發(fā)所得到的深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)序列。

深度遍歷：1347865200000000visited[M]1234567811111111結束

作業(yè)4圖

(2)寫出在該鄰接表上，從頂點1出發(fā)所得到的深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)序列。

廣度遍歷：1324765800000000visited[M]1234567811111111結束

作業(yè)5

查找、排序

1.對下標為1～9的有序表進行折半查找，畫出折半查找的判定樹；并計算在等概率情況下查找成功的平均查找長度ASL。12345678951319213756647580527136849ASL=(1+2*2+3*4+4*2)/9=25/9

作業(yè)5

查找、排序

2.設有關鍵字序列{25，40，33，47，12，66，72，87，94，22，5，58}，散列表長12，散列函數(shù)為h(key)=key%11，用線性探查再散列、鏈地址法處理沖突，請分別畫出散列表，并計算。3661010730035用線性探查再散列法處理沖突72402547873312669422558113126113591ASL=(1*6+2*1+3*2+5*1+6*1+9*1)/12=2.83

作業(yè)5

查找、排序

2.設有關鍵字序列{25，40，33，47，12，66，72，87，94，22