數(shù)據(jù)結構實驗報告

數(shù)據(jù)結構實驗報告課程名稱：數(shù)據(jù)結構實驗一實驗題目設有兩個無頭結點的單鏈表，頭指針分別為ha，hb，鏈中有數(shù)據(jù)域data，鏈域next，兩鏈表的數(shù)據(jù)都按遞增序存放，現(xiàn)要求將hb表歸到ha表中，且歸并后ha仍遞增序，歸并中ha表中已有的數(shù)據(jù)若hb中也有，則hb中的數(shù)據(jù)不歸并到ha中，hb的鏈表在算法中不允許破壞。程序核心代碼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){數(shù)據(jù)結構實驗報告全文共19頁，當前為第1頁。LNode*Lr=(LNode*)malloc(sizeof(LNode));數(shù)據(jù)結構實驗報告全文共19頁，當前為第1頁。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));/*生成新結點*/s->data=e;/*插入L中*/s->next=p->next;p->next=s;return1;數(shù)據(jù)結構實驗報告全文共19頁，當前為第2頁。}數(shù)據(jù)結構實驗報告全文共19頁，當前為第2頁。intmain(){ LinkListha,hb; intn,i; intdata; InitList(&ha); printf("請輸入ha中數(shù)據(jù)的個數(shù)："); scanf("%d",&n); printf("請依次輸入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("請輸入hb中數(shù)據(jù)的個數(shù)："); scanf("%d",&n); printf("請依次輸入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)數(shù)據(jù)結構實驗報告全文共19頁，當前為第3頁。 {數(shù)據(jù)結構實驗報告全文共19頁，當前為第3頁。 printf("%d",p->data); p=p->next; } printf("\n"); system("pause"); return0;}運行結果4.實驗總結要注意歸并時若ha表中已有的數(shù)據(jù)若hb中也有，則hb中的數(shù)據(jù)不歸并到ha中，hb的鏈表在算法中不允許破壞。數(shù)據(jù)結構實驗報告全文共19頁，當前為第4頁。數(shù)據(jù)結構實驗報告全文共19頁，當前為第4頁。實驗二實驗題目結合書上第41頁的例子（一元多項式相加），采用鏈式存儲結構，將兩個線性鏈表表示的一元多項式相加，并輸出。程序核心代碼typedefstructLNode{intdata;//存儲系數(shù)intflag;//存儲對應冪數(shù)structLNode*next;}LNode;//建立帶頭結點的單鏈表，n項多項式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;//插入鏈表}}//多項式L1與L2對應項相加得到新的L2voidPolyoAdd(LNode**L1,LNode**L2){intck;LNode*p,*q;p=NULL;q=NULL;q=(*L1)->next;while(q)數(shù)據(jù)結構實驗報告全文共19頁，當前為第5頁。{數(shù)據(jù)結構實驗報告全文共19頁，當前為第5頁。ck=0;p=(*L2)->next;while(p){if(q->flag==p->flag){ck=1;break;}p=p->next;}if(ck==1)//同類項合并{p->data+=q->data;q=q->next;}else//否則，直接將非同類項插到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("設定多項式A的項數(shù)：\n");scanf("%d",&m);printf("請輸入多項式A的系數(shù)及對應位冪次：\n");CreateList(&p1,m);printf("A");PolyoPrint(&p1);printf("設定多項式B的項數(shù)：\n");scanf("%d",&m);printf("請輸入多項式B的系數(shù)及對應位冪次：\n");CreateList(&p2,m);printf("B");數(shù)據(jù)結構實驗報告全文共19頁，當前為第6頁。PolyoPrint(&p2);數(shù)據(jù)結構實驗報告全文共19頁，當前為第6頁。PolyoAdd(&p1,&p2);printf("相加后的");PolyoPrint(&p2);system("pause");return0;}運行結果實驗總結合并多項式是指相同指數(shù)的項的系數(shù)相加，比較兩個鏈表的節(jié)點的指數(shù)的大小，作為指針移動的條件，同事合并的過程中應消除系數(shù)項為零的節(jié)點。數(shù)據(jù)結構實驗報告全文共19頁，當前為第7頁。數(shù)據(jù)結構實驗報告全文共19頁，當前為第7頁。實驗三實驗題目二叉樹的動態(tài)二叉鏈表結構中的每個結點有三個字段：data，lchild，rchild。其中指針lchild下標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ù)組作為存儲空間，每個數(shù)組元素存儲二叉樹的一個結點，也有三個字段：data，lchild，rchild。所不同的是，lchild和rdhild為integer型，分別用于存儲左右孩子的下標，如果沒有左右孩子，則相應的值為0。例如，二叉樹的靜態(tài)二叉鏈表如上圖所示。編寫算法由二叉樹的動態(tài)二叉鏈表構造出相應的靜態(tài)二叉鏈表a[1..n]，并寫出其調用形式和有關的類型描述。其中n為一個確定的整數(shù)。程序核心代碼typedefstructBiTNode{ chardata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;數(shù)據(jù)結構實驗報告全文共19頁，當前為第8頁。數(shù)據(jù)結構實驗報告全文共19頁，當前為第8頁。typedefstructNode//靜態(tài)鏈表結點結構{chardata;//結點數(shù)據(jù)introw,lchild,rchild;//下標，左右孩子}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;//生成根結點createBiTree(T->lchild);//構造左子樹createBiTree(T->rchild);//構造右子樹}}voidPreOrder(BiTreebt)//先序遍歷二叉樹，填寫靜態(tài)鏈表的“下標”和data域{ if(bt){ st[++num].data=bt->data; st[num].row=num; PreOrder(bt->lchild); PreOrder(bt->rchild); }}intLocate(charx){//在靜態(tài)鏈表中查二叉樹結點的下標inti;{ for(i=1;i<=num;i++)數(shù)據(jù)結構實驗報告全文共19頁，當前為第9頁。 if(st[i].data==x)數(shù)據(jù)結構實驗報告全文共19頁，當前為第9頁。 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;數(shù)據(jù)結構實驗報告全文共19頁，當前為第10頁。 printf("請輸入二叉樹各結點的值:\n");數(shù)據(jù)結構實驗報告全文共19頁，當前為第10頁。 createBiTree(t); nodeNum(t); st=(Node*)malloc(sizeof(structNode)*length); DynaToST(t); show(st); return0;}運行結果實驗體會二叉樹的建立是按照先序遍歷的方式遞歸的建立的，因此在輸入二叉樹的節(jié)點中的值時，要注意#字符的個數(shù)。數(shù)據(jù)結構實驗報告全文共19頁，當前為第11頁。數(shù)據(jù)結構實驗報告全文共19頁，當前為第11頁。實驗四實驗題目設無向圖G有n個點e條邊，編寫算法建立G的鄰接表，并按照深度優(yōu)先搜索輸出頂點，要求該算法時間復雜性為O（n+e），且除鄰接表本身所占空間之外只用O（1）輔助空間。程序核心代碼structedgenode//表結點{ intendver; edgenode*edgenext;};structvexnode//頭結點{ charvertex; edgenode*edgelink;};structGraph//無向圖{ vexnodeadjlists[Max_Ver_Num]; intvexnum,arcnum;};voidCreatAdjList(Graph*G){ inti,j,k; edgenode*p1; edgenode*p2; cout<<"請輸入無向圖的頂點數(shù)和邊數(shù):"<<endl; cin>>G->vexnum>>G->arcnum; cout<<endl; cout<<"開始輸入頂點表:"<<endl;數(shù)據(jù)結構實驗報告全文共19頁，當前為第12頁。數(shù)據(jù)結構實驗報告全文共19頁，當前為第12頁。 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<<"請輸入邊<Vi,Vj>對應的頂點序號:"; cin>>i>>j;cout<<endl; p1=newedgenode; p1->endver=j; p1->edgenext=G->adjlists[i].edgelink;//將結點始終插到表結點后 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){數(shù)據(jù)結構實驗報告全文共19頁，當前為第13頁。 cout<<"該圖的深度優(yōu)先遍歷結果為:"<<endl;數(shù)據(jù)結構實驗報告全文共19頁，當前為第13頁。 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<<"請輸入開始遍歷的頂點:"<<endl; cin>>Vi; DFStraversal(G,Vi);cout<<endl;return0;}數(shù)據(jù)結構實驗報告全文共19頁，當前為第14頁。數(shù)據(jù)結構實驗報告全文共19頁，當前為第14頁。運行結果實驗體會在輸入邊表關系時，要注意因為是無向圖，所以有兩次建立邊表的過程，不需要重復輸入。數(shù)據(jù)結構實驗報告全文共19頁，當前為第15頁。數(shù)據(jù)結構實驗報告全文共19頁，當前為第15頁。實驗五實驗題目二叉排序樹采用二叉鏈表存儲。寫一個算法，刪除結點值是X的結點。要求刪除該結點后,此樹仍然是一棵二叉排序樹，并且高度沒有增長（注：可不考慮被刪除的結點是根的情況）。程序核心代碼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);數(shù)據(jù)結構實驗報告全文共19頁，當前為第16頁。 else數(shù)據(jù)結構實驗報告全文共19頁，當前為第16頁。 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);}}//刪除二叉排序樹中結點pboolDelete(BiTreep){ BiTreeq,s; q=(BiTree)malloc(sizeof(BiTNode)); s=(BiTree)malloc(sizeof(BiTNode)); if(!p->rchild&&!p->lchild)//刪除的節(jié)點是葉子節(jié)點 { 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); } else{//左右子樹都不為空 q=p; s=p->lchild;數(shù)據(jù)結構實驗報告全文