數(shù)據(jù)結(jié)構(gòu)實驗報告4933

課程名稱：數(shù)據(jù)結(jié)構(gòu)實驗一1.實驗題目設(shè)有兩個無頭結(jié)點的單鏈表，頭指針分別為ha，hb，鏈中有數(shù)據(jù)域data，鏈域next，兩鏈表的數(shù)據(jù)都按遞增序存放，現(xiàn)要求將hb表歸到ha表中，且歸并后ha仍遞增序，歸并中ha表中已有的數(shù)據(jù)若hb中也有，則hb中的數(shù)據(jù)不歸并到ha中，hb的鏈表在算法中不允許破壞。2.程序核心代碼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));1Lr->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é)點*/s->data=e;/*插入L中*/s->next=p->next;p->next=s;return1;}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){3

4.實驗總結(jié)要注意歸并時若ha表中已有的數(shù)據(jù)若hb中也有，則hb中的數(shù)據(jù)不歸并到ha中，hb的鏈表在算法中不允許破壞。4實驗二1.實驗題目結(jié)合書上第41頁的例子（一元多項式相加），采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，將兩個線性鏈表表示的一元多項式相加，并輸出。2.程序核心代碼typedefstructLNode{intdata;//存儲系數(shù)intflag;//存儲對應(yīng)冪數(shù)structLNode*next;}LNode;//建立帶頭結(jié)點的單鏈表，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對應(yīng)項相加得到新的L2voidPolyoAdd(LNode**L1,LNode**L2){intck;LNode*p,*q;p=NULL;q=NULL;q=(*L1)->next;while(q){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("設(shè)定多項式A的項數(shù)：\n");scanf("%d",&m);printf("請輸入多項式CreateList(&p1,m);printf("A");A的系數(shù)及對應(yīng)位冪次：\n");PolyoPrint(&p1);printf("設(shè)定多項式B的項數(shù)：\n");scanf("%d",&m);printf("請輸入多項式B的系數(shù)及對應(yīng)位冪次：\n");CreateList(&p2,m);printf("B");PolyoPrint(&p2);6

4.實驗總結(jié)合并多項式是指相同指數(shù)的項的系數(shù)相加，比較兩個鏈表的節(jié)點的指數(shù)的大小，作為指針移動的條件，同事合并的過程中應(yīng)消除系數(shù)項為零的節(jié)點。7實驗三1.實驗題目二叉樹的動態(tài)二叉鏈表結(jié)構(gòu)中的每個結(jié)點有三個字段：data，lchild，rchild。其中指針lchild下標(biāo)datalchildrchild1234567ABCDEFG23050006400070和rchild的類型為bitree。靜態(tài)二叉鏈表是用數(shù)組作為存儲空間，每個數(shù)組元素存儲二叉樹的一個結(jié)點，也有三個字段：data，lchild，rchild。所不同的是，lchild和rdhild為integer型，分別用于存儲左右孩子的下標(biāo)，如果沒有左右孩子，則相應(yīng)的值為0。例如，二叉樹的靜態(tài)二叉鏈表如上圖所示。編寫算法由二叉樹的動態(tài)二叉鏈表構(gòu)造出相應(yīng)的靜態(tài)二叉鏈表a[1..n]，并寫出其調(diào)用形式和有關(guān)的類型描述。其中n為一個確定的整數(shù)。2.程序核心代碼typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;8typedefstructNode//靜態(tài)鏈表結(jié)點結(jié)構(gòu){chardata;//結(jié)點數(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é)點createBiTree(T->lchild);//構(gòu)造左子樹createBiTree(T->rchild);//構(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é)點的下標(biāo)inti;{for(i=1;i<=num;i++)if(st[i].data==x)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);elsest[i].lchild=0;//無左孩子，其lchild域填0if(p->rchild)st[i].rchild=Locate(p->rchild->data);elsest[i].rchild=0;//無右孩子，其rchild域填0}}intmain(){BiTreet;printf("請輸入二叉樹各結(jié)點的值:\n");10

4.實驗體會二叉樹的建立是按照先序遍歷的方式遞歸的建立的，因此在輸入二叉樹的節(jié)點中的值時，要注意#字符的個數(shù)。實驗四1.實驗題目設(shè)無向圖G有n個點e條邊，編寫算法建立G的鄰接表，并按照深度優(yōu)先搜索輸出頂點，要求該算法時間復(fù)雜性為O（n+e），且除鄰接表本身所占空間之外只用O（1）輔助空間。2.程序核心代碼structedgenode//表{intendver;edgenode*edgenext;結(jié)點};structvexnode//頭結(jié)點{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;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>對應(yīng)的頂點序號:";cin>>i>>j;cout<<endl;p1=newedgenode;p1->endver=j;p1->edgenext=G->adjlists[i].edgelink;//將結(jié)點始終插到表結(jié)點后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;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;}14

4.實驗體會在輸入邊表關(guān)系時，要注意因為是無向圖，所以有兩次建立邊表的過程，不需要重復(fù)輸入。實驗五1.實驗題目二叉排序樹采用二叉鏈表存儲。寫一個算法，刪除結(jié)點值是X的結(jié)點。要求刪除該結(jié)點后,此樹仍然是一棵二叉排序樹，并且高度沒有增長（注：可不考慮被刪除的結(jié)點是根的情況）。2.程序核心代碼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);else16

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é)點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;wh