武科大數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院試驗(yàn)匯報(bào)課程名稱：數(shù)據(jù)結(jié)構(gòu)專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：級(jí)1班學(xué)號(hào)：13137024姓名：鎮(zhèn)方權(quán)指導(dǎo)老師：邱奕敏試驗(yàn)一試驗(yàn)題目設(shè)有兩個(gè)無頭結(jié)點(diǎn)單鏈表，頭指針分別為ha，hb，鏈中有數(shù)據(jù)域data，鏈域next，兩鏈表數(shù)據(jù)都按遞增序存放，現(xiàn)要求將hb表歸到ha表中，且歸并后ha仍遞增序，歸并中ha表中已經(jīng)有數(shù)據(jù)若hb中也有，則hb中數(shù)據(jù)不歸并到ha中，hb鏈表在算法中不允許破壞。程序關(guān)鍵代碼structLNode{intdata;structLNode*next;};typedefstructLNode*LinkList;LinkListUnion(LinkListha,LinkListhb){LinkListhead=(LNode*)malloc(sizeof(LNode));head->next=ha;LNode*pa,*pb,*pTmp;pa=ha->next;pb=hb->next;pTmp=ha;while(pa&&pb){if(pa->data<pb->data){pTmp=pa;pa=pa->next;}elseif(pa->data>pb->data){LNode*Lr=(LNode*)malloc(sizeof(LNode));Lr->data=pb->data;Lr->next=pa;pTmp->next=Lr;pTmp=Lr;pb=pb->next;}else{pTmp=pa;pa=pa->next;pb=pb->next;}}if(pa){pTmp->next=pa;}else{while(pb){LNode*Lr=(LNode*)malloc(sizeof(LNode));Lr->data=pb->data;pTmp->next=Lr;pTmp=Lr;pb=pb->next;}pTmp->next=NULL;}free(head);returnha;}intListInsert(LinkListL,inti,inte){intj=0;LinkListp=L,s;while(p&&j<i-1){p=p->next;j++;}if(!p||j>i-1)return0;s=(LinkList)malloc(sizeof(structLNode));/*生成新結(jié)點(diǎn)*/s->data=e;/*插入L中*/s->next=p->next;p->next=s;return1;}intmain(){ LinkListha,hb; intn,i; intdata; InitList(&ha); printf("請(qǐng)輸入ha中數(shù)據(jù)個(gè)數(shù)："); scanf("%d",&n); printf("請(qǐng)依次輸入ha中數(shù)據(jù)：\n"); for(inti=1;i<=n;i++) { scanf("%d",&data); ListInsert(ha,i,data); } printf("ha="); LinkListp=ha->next; while(p) { printf("%d",p->data); p=p->next; } printf("\n"); InitList(&hb); printf("請(qǐng)輸入hb中數(shù)據(jù)個(gè)數(shù)："); scanf("%d",&n); printf("請(qǐng)依次輸入hb中數(shù)據(jù)：\n"); for(i=1;i<=n;i++) { scanf("%d",&data); ListInsert(hb,i,data); } printf("hb="); p=hb->next; while(p) { printf("%d",p->data); p=p->next; } printf("\n"); printf("hb歸并到ha后，新ha="); p=Union(ha,hb)->next; while(p) { printf("%d",p->data); p=p->next; } printf("\n"); system("pause"); return0;}運(yùn)行結(jié)果4.試驗(yàn)總結(jié)要注意歸并時(shí)若ha表中已經(jīng)有數(shù)據(jù)若hb中也有，則hb中數(shù)據(jù)不歸并到ha中，hb鏈表在算法中不允許破壞。試驗(yàn)二試驗(yàn)題目結(jié)合書上第41頁例子（一元多項(xiàng)式相加），采取鏈?zhǔn)酱娣沤Y(jié)構(gòu)，將兩個(gè)線性鏈表表示一元多項(xiàng)式相加，并輸出。程序關(guān)鍵代碼typedefstructLNode{intdata;//存放系數(shù)intflag;//存放對(duì)應(yīng)冪數(shù)structLNode*next;}LNode;//建立帶頭結(jié)點(diǎn)單鏈表，n項(xiàng)多項(xiàng)式voidCreateList(LNode**L,intn){LNode*p;inti=0;*L=(LNode*)malloc(sizeof(LNode));(*L)->next=NULL;for(i=0;i<n;++i){p=(LNode*)malloc(sizeof(LNode));scanf("%d%d",&(p->data),&(p->flag));p->next=(*L)->next;(*L)->next=p;//插入鏈表}}//多項(xiàng)式L1與L2對(duì)應(yīng)項(xiàng)相加得到新L2voidPolyoAdd(LNode**L1,LNode**L2){intck;LNode*p,*q;p=NULL;q=NULL;q=(*L1)->next;while(q){ck=0;p=(*L2)->next;while(p){if(q->flag==p->flag){ck=1;break;}p=p->next;}if(ck==1)//同類項(xiàng)合并{p->data+=q->data;q=q->next;}else//不然，直接將非同類項(xiàng)插到L2最前面{(*L1)->next=q->next;q->next=(*L2)->next;(*L2)->next=q;q=(*L1)->next;}}}intmain(){intm=0;LNode*p1,*p2;p1=NULL;p2=NULL;printf("設(shè)定多項(xiàng)式A項(xiàng)數(shù)：\n");scanf("%d",&m);printf("請(qǐng)輸入多項(xiàng)式A系數(shù)及對(duì)應(yīng)位冪次：\n");CreateList(&p1,m);printf("A");PolyoPrint(&p1);printf("設(shè)定多項(xiàng)式B項(xiàng)數(shù)：\n");scanf("%d",&m);printf("請(qǐng)輸入多項(xiàng)式B系數(shù)及對(duì)應(yīng)位冪次：\n");CreateList(&p2,m);printf("B");PolyoPrint(&p2);PolyoAdd(&p1,&p2);printf("相加后");PolyoPrint(&p2);system("pause");return0;}運(yùn)行結(jié)果試驗(yàn)總結(jié)合并多項(xiàng)式是指相同指數(shù)項(xiàng)系數(shù)相加，比較兩個(gè)鏈表節(jié)點(diǎn)指數(shù)大小，作為指針移動(dòng)條件，同事合并過程中應(yīng)消除系數(shù)項(xiàng)為零節(jié)點(diǎn)。試驗(yàn)三試驗(yàn)題目二叉樹動(dòng)態(tài)二叉鏈表結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)有三個(gè)字段：data，lchild，rchild。其中指針lchild下標(biāo)datalchildrchild

1

A

2

6

2

B

3

4

3

C

0

0

4

D

5

0

5

E

0

0

6

F

0

7

7

G

0

0和rchild類型為bitree。靜態(tài)二叉鏈表是用數(shù)組作為存放空間，每個(gè)數(shù)組元素存放二叉樹一個(gè)結(jié)點(diǎn)，也有三個(gè)字段：data，lchild，rchild。所不一樣是，lchild和rdhild為integer型，分別用于存放左右孩子下標(biāo)，假如沒有左右孩子，則對(duì)應(yīng)值為0。比如，二叉樹靜態(tài)二叉鏈表如上圖所表示。編寫算法由二叉樹動(dòng)態(tài)二叉鏈表結(jié)構(gòu)出對(duì)應(yīng)靜態(tài)二叉鏈表a[1..n]，并寫出其調(diào)用形式和關(guān)于類型描述。其中n為一個(gè)確定整數(shù)。程序關(guān)鍵代碼typedefstructBiTNode{ chardata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedefstructNode//靜態(tài)鏈表結(jié)點(diǎn)結(jié)構(gòu){chardata;//結(jié)點(diǎn)數(shù)據(jù)introw,lchild,rchild;//下標(biāo)，左右孩子}Node;Node*st;//st容量足夠大staticintlength=0;staticintnum=0;voidcreateBiTree(BiTree&T){charch;scanf("%c",&ch);if(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))printf("error");T->data=ch;//生成根結(jié)點(diǎn)createBiTree(T->lchild);//結(jié)構(gòu)左子樹createBiTree(T->rchild);//結(jié)構(gòu)右子樹}}voidPreOrder(BiTreebt)//先序遍歷二叉樹，填寫靜態(tài)鏈表“下標(biāo)”和data域{ if(bt){ st[++num].data=bt->data; st[num].row=num; PreOrder(bt->lchild); PreOrder(bt->rchild); }}intLocate(charx){//在靜態(tài)鏈表中查二叉樹結(jié)點(diǎn)下標(biāo)inti;{ for(i=1;i<=num;i++) if(st[i].data==x) return(i);}}BiTreeLevelOrderLocateP(BiTreeroot,charx){ intfront,rear; BiTreequeue[MAXSIZE],p; p=root; front=rear=0; if(p){ queue[rear++]=p; while(front<rear) { p=queue[front++]; if(p->data==x) returnp; if(p->lchild) queue[rear++]=p->lchild; if(p->rchild) queue[rear++]=p->rchild; } }}voidDynaToST(BiTreet){inti; BiTreep; PreOrder(t); for(i=1;i<=num;i++) { p=LevelOrderLocateP(t,st[i].data); if(p->lchild) st[i].lchild=Locate(p->lchild->data); else st[i].lchild=0; //無左孩子，其lchild域填0 if(p->rchild) st[i].rchild=Locate(p->rchild->data); else st[i].rchild=0; //無右孩子，其rchild域填0 }}intmain(){ BiTreet; printf("請(qǐng)輸入二叉樹各結(jié)點(diǎn)值:\n"); createBiTree(t); nodeNum(t); st=(Node*)malloc(sizeof(structNode)*length); DynaToST(t); show(st); return0;}運(yùn)行結(jié)果試驗(yàn)體會(huì)二叉樹建立是按照先序遍歷方式遞歸建立，所以在輸入二叉樹節(jié)點(diǎn)中值時(shí)，要注意#字符個(gè)數(shù)。試驗(yàn)四試驗(yàn)題目設(shè)無向圖G有n個(gè)點(diǎn)e條邊，編寫算法建立G鄰接表，并按照深度優(yōu)先搜索輸出頂點(diǎn)，要求該算法時(shí)間復(fù)雜性為O（n+e），且除鄰接表本身所占空間之外只用O（1）輔助空間。程序關(guān)鍵代碼structedgenode//表結(jié)點(diǎn){ intendver; edgenode*edgenext;};structvexnode//頭結(jié)點(diǎn){ charvertex; edgenode*edgelink;};structGraph//無向圖{ vexnodeadjlists[Max_Ver_Num]; intvexnum,arcnum;};voidCreatAdjList(Graph*G){ inti,j,k; edgenode*p1; edgenode*p2; cout<<"請(qǐng)輸入無向圖頂點(diǎn)數(shù)和邊數(shù):"<<endl; cin>>G->vexnum>>G->arcnum; cout<<endl; cout<<"開始輸入頂點(diǎn)表:"<<endl; for(i=1;i<=G->vexnum;i++) { cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL; } cout<<endl; cout<<"開始輸入邊表信息:"<<endl;cout<<endl; for(k=1;k<=G->arcnum;k++) { cout<<"請(qǐng)輸入邊<Vi,Vj>對(duì)應(yīng)頂點(diǎn)序號(hào):"; cin>>i>>j;cout<<endl; p1=newedgenode; p1->endver=j; p1->edgenext=G->adjlists[i].edgelink;//將結(jié)點(diǎn)一直插到表結(jié)點(diǎn)后 G->adjlists[i].edgelink=p1; p2=newedgenode; p2->endver=i; p2->edgenext=G->adjlists[j].edgelink; G->adjlists[j].edgelink=p2; }}voidDFS(Graph*G,inti,intvisited[]){ cout<<G->adjlists[i].vertex<<""; visited[i]=1; edgenode*p=newedgenode; p=G->adjlists[i].edgelink; if(G->adjlists[i].edgelink&&!visited[p->endver]) { DFS(G,p->endver,visited); }}voidDFStraversal(Graph*G,charc){ cout<<"該圖深度優(yōu)先遍歷結(jié)果為:"<<endl; intvisited[Max_Ver_Num]; for(inti=1;i<=G->vexnum;i++) { visited[i]=0; } for(inti=1;i<=G->vexnum;i++) { if(G->adjlists[i].vertex==c) { DFS(G,i,visited); break; } } for(inti=1;i<=G->vexnum;i++) { if(visited[i]==0) DFS(G,i,visited); } cout<<endl;}//主程序intmain(){ Graph*G=newGraph; CreatAdjList(G); PrintGaph(G); charVi; cout<<"請(qǐng)輸入開始遍歷頂點(diǎn):"<<endl; cin>>Vi; DFStraversal(G,Vi);cout<<endl;return0;}運(yùn)行結(jié)果試驗(yàn)體會(huì)在輸入邊表關(guān)系時(shí)，要注意因?yàn)槭菬o向圖，所以有兩次建立邊表過程，不需要重復(fù)輸入。試驗(yàn)五試驗(yàn)題目二叉排序樹采取二叉鏈表存放。寫一個(gè)算法，刪除結(jié)點(diǎn)值是X結(jié)點(diǎn)。要求刪除該結(jié)點(diǎn)后,此樹依然是一棵二叉排序樹，而且高度沒有增加（注：可不考慮被刪除結(jié)點(diǎn)是根情況）。程序關(guān)鍵代碼typedefstructBiTNode{ ElemTypedata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;staticBiTreehead;//建二叉排序樹BiTreecreateBST(BiTreehead,intnumber){ BiTreep; p=(BiTree)malloc(sizeof(BiTNode));p->data=number; p->lchild=p->rchild=NULL; if(head==NULL) {returnp; } else {if(p->data<head->data) head->lchild=createBST(head->lchild,number); else head->rchild=createBST(head->rchild,number);returnhead; }}//求p雙親BiTreesearchParent(BiTreehead,BiTreep){if(head->lchild==p||head->rchild==p||head==p||head==NULL)returnhead;else{if(p->data<head->data)returnsearchParent(head->lchild,p);elsereturnsearchParent(head->rchild,p);}}//刪除二叉排序樹中結(jié)點(diǎn)pboolDelete(BiTreep){ BiTreeq,s; q=(BiTree)malloc(sizeof(BiTNode)); s=(BiTree)malloc(sizeof(BiTNode)); if(!p->rchild&&!p->lchild)//刪除節(jié)點(diǎn)是葉子節(jié)點(diǎn) { q=searchParent(head,p); if(q->lchild==p)q->lchild=NULL; elseq->rchild=NULL; } elseif(!p->rchild){//左子樹不為空，右子樹為空 searchParent(head,p)->lchild=p->lchild; free(p); } elseif(!p->lchild){//右子樹不為空，左子樹為空searchParent(head,p)->rchild=p->rchild; free(p);