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

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告冊(cè) 班級(jí)：學(xué)號(hào)：姓名：試驗(yàn)題目：試驗(yàn)一次序表操作試驗(yàn)日期：/11/14試驗(yàn)要求：1.認(rèn)真閱讀和掌握本試驗(yàn)相關(guān)知識(shí)。2.對(duì)給出程序認(rèn)真閱讀，把相關(guān)缺失程序補(bǔ)充完整。3.上機(jī)運(yùn)行補(bǔ)充后程序。4.保留程序運(yùn)行結(jié)果，結(jié)合程序分析次序結(jié)構(gòu)特點(diǎn)。5.填寫試驗(yàn)匯報(bào)。概要設(shè)計(jì)：在VC++6.0運(yùn)行環(huán)境下，編寫C或C++語(yǔ)言程序，利用次序存放方式來(lái)實(shí)現(xiàn)以下功效：(1)依照鍵盤輸入數(shù)據(jù)建立一個(gè)次序表，而且輸出該次序表。(2)依照屏幕菜單來(lái)選擇數(shù)據(jù)插入、刪除以及查找操作。(3)完成插入或刪除數(shù)據(jù)操作后，把操作后線性表進(jìn)行輸出。(4)在完成插入、刪除和查找操作后，選擇菜單上0，退出該程序運(yùn)行，結(jié)束試驗(yàn)內(nèi)容。在次序表第i個(gè)位置上要求插入一個(gè)數(shù)據(jù)元素時(shí)候，先將次序表第i個(gè)位置元素后全部數(shù)據(jù)元素按次序后移一個(gè)位置，在插入地方空出一個(gè)位置，然后把要插入新數(shù)據(jù)元素插入到該位置，同時(shí)將表長(zhǎng)加一。在次序表中刪除表中第i個(gè)位置數(shù)據(jù)元素時(shí)候，先將該位置數(shù)據(jù)元素刪除，然后將第i個(gè)位置后其余剩下元素按次序依次向前移動(dòng)一個(gè)位置，同時(shí)將表長(zhǎng)減一。次序表中查找一個(gè)數(shù)據(jù)元素值，需要遍歷整個(gè)次序表，如要找道該值，則返回該值在次序表中位置，不然繼續(xù)查找。假如遍歷整個(gè)次序表都沒(méi)有找到該值，則要求函數(shù)返回-1 詳細(xì)設(shè)計(jì)：//.建立線性表儲(chǔ)存結(jié)構(gòu)#defineMAXSIZE20typedefintElemType;typedefstruct{ ElemTypea[MAXSIZE]; intlength;}SqList;//在線性表第i個(gè)位置插入數(shù)據(jù)元素evoidinsert_sq(SqList*L,inti,ElemTypee){intj; if(i<1||i>L->length)printf("\n輸入插入位置不存在："); for(j=L->length;j>=i;j--) L->a[j]=L->a[j-1]; L->a[i-1]=e; L->length++;}//刪除第i個(gè)數(shù)據(jù)元素，返回其值ElemTypedelete_sq(SqList*L,inti){intj; ElemTypey; if(i<1||i>L->length) return-1; y=L->a[i-1]; for(j=i;j<L->length;j++) { L->a[j-1]=L->a[j]; } L->length--; returny;}//查找值為e元素，返回它值intlocat_sq(SqListL,ElemTypee){ inti=0; while(i<=L.length-1&&L.a[i]!=e) i++; if(i<=L.length-1) return(i+1); else return(-1);}1.建立線性表儲(chǔ)存結(jié)構(gòu)2.在線性表第i個(gè)位置插入數(shù)據(jù)元素L1L1L2L3..LiLi+1......開(kāi)始intj;i<i||i>L->lengthprintf(“\n輸出插入位置“)j>=ij=L->lengthL->a[j]=L->a[j-1];j--;L->a[j-1]=e;結(jié)束3.刪除第i個(gè)數(shù)據(jù)元素，返回其值4.查找值為e元素，返回它值開(kāi)始開(kāi)始intj;i<1||i>L->lengthreturn-1;Y=L->a[i-1];j=i;j<L->length;L->a[j-1]=L->a[j];j++;L->length;returny;結(jié)束開(kāi)始intj=0;i<=l.length-1&&L.a[i]!=e;i++;i<=L.length-1;return(i+1);return(-1);結(jié)束調(diào)試分析：在VC++6.0運(yùn)行環(huán)境下，編譯設(shè)計(jì)程序，出現(xiàn)了以下錯(cuò)誤：（1）在out-list函數(shù)輸錯(cuò)了一個(gè)“：”符號(hào)，把錯(cuò)誤“：”符號(hào)改成“；”。就能夠正確得到結(jié)果了。測(cè)試結(jié)果：試驗(yàn)成績(jī)：試驗(yàn)題目：試驗(yàn)二單鏈表操作試驗(yàn)日期：/11/18試驗(yàn)要求：1.認(rèn)真閱讀和掌握本試驗(yàn)相關(guān)知識(shí)。2.對(duì)給出程序認(rèn)真閱讀，把相關(guān)缺失程序補(bǔ)充完整。3.上機(jī)運(yùn)行補(bǔ)充后程序。4.保留程序運(yùn)行結(jié)果，結(jié)合程序分析鏈?zhǔn)浇Y(jié)構(gòu)特點(diǎn)。5.填寫試驗(yàn)匯報(bào)概要設(shè)計(jì)：編寫C語(yǔ)言程序，利用鏈?zhǔn)酱娣欧绞絹?lái)實(shí)現(xiàn)以下功效：(1)依照鍵盤輸入數(shù)據(jù)建立一個(gè)單鏈表，而且輸出該單鏈表。(2)依照屏幕菜單來(lái)選擇數(shù)據(jù)插入、刪除以及查找操作。(3)完成插入或刪除數(shù)據(jù)操作后，把操作后線性表進(jìn)行輸出。(4)在完成插入、刪除和查找操作后，選擇菜單上0，退出該程序運(yùn)行，結(jié)束試驗(yàn)內(nèi)容。在單鏈表第i個(gè)位置上要求插入一個(gè)數(shù)據(jù)元素時(shí)候，先生成一個(gè)存放單元S來(lái)存放插入數(shù)據(jù)元素X值，其次修改第i個(gè)位置結(jié)點(diǎn)Pnext域值，讓其存入是結(jié)點(diǎn)S所在存放單元地址值，再次修改結(jié)點(diǎn)Snext域值，讓Snext域值為第i+1結(jié)點(diǎn)地址值。在單鏈表中刪除表中第i個(gè)位置數(shù)據(jù)元素時(shí)候，先修改第i-1個(gè)數(shù)據(jù)元素next域地址值，使其值為第i+1個(gè)數(shù)據(jù)元素存放單元地址值，最終釋放第i個(gè)存放單元，使用函數(shù)free()。在單鏈表中查找一個(gè)數(shù)據(jù)元素值，需要遍歷整個(gè)整個(gè)單鏈表，如要找道該值，則返回該值，不然繼續(xù)查找。假如遍歷整個(gè)次序表都沒(méi)有找到該值，則要求函數(shù)返回-1詳細(xì)設(shè)計(jì)：typedefintElemType;typedefstructLNode{ ElemTypedata; structLNode*next;}LNode;LNode*L;//在單鏈表中第i個(gè)位置插入數(shù)據(jù)元素evoidinsert_L(LNode*L,inti,ElemTypee){intj=1; LNode*node,*temp; node=(LNode*)malloc(sizeof(LNode)); if(node==NULL) printf("儲(chǔ)存空間分配不成功："); node->data=e; temp=L; if(temp==NULL) { if(i==0) { L->next=node; node->next=NULL; } else printf("沒(méi)有適宜插入點(diǎn)："); } while(j<i&&temp!=NULL) { temp=temp->next; j++; } if(temp==NULL) printf("沒(méi)有適宜插入點(diǎn)："); node->next=temp->next; temp->next=node;}//刪除第i個(gè)數(shù)據(jù)元素，返回其值ElemTypedelete_L(LNode*L,inti){LNode*temp,*p; intx,j=1; temp=L; while(j<i-1&&temp!=NULL) { j++; temp=temp->next; }x=temp->next->data;p=temp->next;temp->next=temp->next->next;returnx;free(p);}}1.刪除第i個(gè)數(shù)據(jù)元素，返回其值2.單鏈表中第i個(gè)位置插入數(shù)據(jù)元素e開(kāi)始開(kāi)始j<i-1&&temp!=nullLNode*temp,*p;j++;x=temp->next->data;returnx;free(p);結(jié)束開(kāi)始intj=1;node==nullprintf（“存放空間不足”）？？node->data=e;temp==null;i==1;L->next=node;node->next=null; node->next=NULLL->next=node; node->next=NULLnode->next=temp->next; temp->next=node;結(jié)束j<i&&temp!=NULL調(diào)試分析：把輸入“while”改成“else”就得到正確結(jié)果了。（2）在編譯時(shí)候出現(xiàn)沒(méi)有定義“Node”這個(gè)變量錯(cuò)誤，再重新檢驗(yàn)所寫函數(shù)，發(fā)覺(jué)把變量寫錯(cuò)了，把變量“Node”改成“node”，錯(cuò)誤得到處理。(3)在調(diào)試時(shí)候出現(xiàn)了要插入位置與顯示結(jié)果不相符，把insert_L函數(shù)中語(yǔ)句“temp=L->next;”改成“temp=L；”，問(wèn)題得到處理。測(cè)試結(jié)果：試驗(yàn)成績(jī)：試驗(yàn)題目：試驗(yàn)三棧鏈?zhǔn)酱娣沤Y(jié)構(gòu)表示和實(shí)現(xiàn)試驗(yàn)日期：/11/25試驗(yàn)要求：1.認(rèn)真閱讀和掌握本試驗(yàn)相關(guān)知識(shí)。2.編寫程序?qū)崿F(xiàn)棧鏈?zhǔn)酱娣欧绞健?.編寫程序?qū)崿F(xiàn)對(duì)?？张袛嘁约皸Ｈ霔：统鰲２僮?、取棧頂元素。4.保留程序運(yùn)行結(jié)果，結(jié)合程序分析鏈?zhǔn)浇Y(jié)構(gòu)特點(diǎn)。5.填寫試驗(yàn)匯報(bào)概要設(shè)計(jì)：(1)初始化鏈棧。(2)將鏈棧置空。(3)完成入棧和出棧操作，完成取棧頂元素操作。(4)選擇菜單上0，退出該程序運(yùn)行，結(jié)束試驗(yàn)內(nèi)容。初始化棧操作，將棧棧頂指針置為空值，即設(shè)棧S和棧頂指針top，S→top=null。假如所建棧里有數(shù)據(jù)元素，要將其置空，一樣也是將棧頂指針值置為空值。入棧操作，向棧里插入數(shù)據(jù)元素。首先要為插入數(shù)據(jù)元素分配結(jié)點(diǎn)，將插入數(shù)據(jù)元素值賦值給插入結(jié)點(diǎn)數(shù)據(jù)域，其次修改棧頂指針指向關(guān)系，即修改插入結(jié)點(diǎn)和棧頂指針地址，最終修改棧頂指針。出棧操作，從棧里刪除數(shù)據(jù)元素。首先要判斷棧是否為空棧，如是空棧則操作失敗。不然，進(jìn)行出棧操作，修改刪除結(jié)點(diǎn)和棧頂指針，最終釋放刪除結(jié)點(diǎn)。取棧頂元素。詳細(xì)設(shè)計(jì)：//鏈棧類型定義typedefintElemType;typedefstructstacknode{ ElemTypedata; stacknode*next;}StackNode;typedefstruct{ stacknode*top;}LinkStack;//入棧voidpushLstack(LinkStack*s,ElemTypex){ StackNode*p; p=newStackNode; p->data=x; p->next=s->top; s->top=p;}//出棧ElemTypepopstack(LinkStack*s){ ElemTypex; StackNode*p; p=s->top; if(s->top==0) { printf("?？?不能出棧!!\n"); return0; exit(0); } x=p->data; printf("%d\n",x); s->top=p->next;deletep; returnx;}//取棧頂元素ElemTypeStackTop(LinkStack*s){ ElemTypex; if(s->top==0) { printf("鏈棧空!!\n"); return0; } else { x=s->top->data; printf("當(dāng)前鏈棧棧頂元素為%d",x); return0; }} 1,入棧示意圖topXXana1^anan-1a12，出棧示意圖top top3，出棧4，取棧頂元素開(kāi)始開(kāi)始ElemTypex；s->tope==0Printf(“?？?，不能出?！?x=p->datas->top=p->next;deletep;returnx;結(jié)束ElemTypex;開(kāi)始s->top==0Printf(“鏈棧為空X=s->top->data;returno;returno結(jié)束調(diào)試分析：在調(diào)試中出現(xiàn)了初始化以后，沒(méi)有在主菜單中選擇操作就直接運(yùn)行入棧了，經(jīng)過(guò)查找原程序發(fā)覺(jué)在swich語(yǔ)句中少了break。測(cè)試結(jié)果：試驗(yàn)成績(jī)：試驗(yàn)題目：試驗(yàn)四二叉樹(shù)遍歷算法設(shè)計(jì)試驗(yàn)日期：/試驗(yàn)要求：1.認(rèn)真閱讀和掌握本試驗(yàn)相關(guān)知識(shí)。2.編寫程序?qū)崿F(xiàn)二叉樹(shù)鏈?zhǔn)酱娣欧绞健?.編寫程序?qū)崿F(xiàn)對(duì)二叉樹(shù)先序遍歷、中序遍歷和后序遍歷算法實(shí)現(xiàn)。4.保留程序運(yùn)行結(jié)果，結(jié)合程序分析二叉樹(shù)結(jié)構(gòu)特點(diǎn)。5.填寫試驗(yàn)匯報(bào)概要設(shè)計(jì)：編寫C或C++語(yǔ)言程序，利用鏈?zhǔn)酱娣欧绞絹?lái)實(shí)現(xiàn)以下功效：(1)采取二叉樹(shù)性質(zhì)5來(lái)建立二叉樹(shù)。(2)完成二叉樹(shù)三種遍歷算法。(3)選擇菜單上0，退出該程序運(yùn)行，結(jié)束試驗(yàn)內(nèi)容。(1)定義二叉樹(shù)結(jié)點(diǎn)值數(shù)據(jù)類型，將其定義為字符型數(shù)據(jù)，定義二叉樹(shù)中結(jié)點(diǎn)結(jié)構(gòu)類型。(2)利用性質(zhì)5建立二叉樹(shù)，設(shè)置序號(hào)為1結(jié)點(diǎn)為二叉樹(shù)根結(jié)點(diǎn)，序號(hào)為偶數(shù)結(jié)點(diǎn)為該二叉樹(shù)左孩子，序號(hào)為奇數(shù)結(jié)點(diǎn)為該二叉樹(shù)右孩子。(3)采取遞歸方式來(lái)遍歷二叉樹(shù)，也就是實(shí)現(xiàn)二叉樹(shù)遍歷是利用遞歸方法來(lái)實(shí)現(xiàn)，即先序遞歸遍歷、中序遞歸遍歷、后序遞歸遍歷。先序遞歸遍歷算法描述：訪問(wèn)二叉樹(shù)根結(jié)點(diǎn)。先序遍歷左子樹(shù)。先序遍歷右子樹(shù)。中序遞歸遍歷算法描述：中序遍歷左子樹(shù)。訪問(wèn)根結(jié)點(diǎn)。中序遍歷右子樹(shù)。后序遞歸遍歷算法描述：后序遍歷左子樹(shù)。后序遍歷右子樹(shù)。訪問(wèn)根結(jié)點(diǎn)。詳細(xì)設(shè)計(jì)：typedefcharElemType;constintMaxLength=10;typedefstructBTNode{ElemTypedata;structBTNode*lchild,*rchild;}BTNode,*BiTree;voidCreateBiTree(BiTree&T){//按先序次序輸入，結(jié)構(gòu)二叉鏈表表示二叉樹(shù)T，空格表示空樹(shù)//if(T)return;charch;ch=getchar();if(ch=='')T=NULL;else{if(!(T=(BTNode*)malloc(sizeof(BTNode))))cout<<"mallocfail!";T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}voidPreOrderTraverse(BiTreeT){//先序遍歷if(T){cout<<T->data<<'';PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}voidInOrderTraverse(BiTreeT){//中序遍歷if(T){InOrderTraverse(T->lchild);cout<<T->data<<'';InOrderTraverse(T->rchild);}}voidPostOrderTraverse(BiTreeT){//后序遍歷if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);cout<<T->data<<'';}}二叉樹(shù)遞歸遍歷(以先序遍歷為例)結(jié)點(diǎn)為空結(jié)點(diǎn)為空N后序遍歷左子樹(shù)后序遍歷右子樹(shù)先序遍歷方式遍歷右子樹(shù)結(jié)束Y開(kāi)始二叉樹(shù)遞歸遍歷(后序遞歸遍歷為例)結(jié)點(diǎn)為空結(jié)點(diǎn)為空N先序遍歷方式遍歷右子樹(shù)先序遍歷方式遍歷左子樹(shù)訪問(wèn)根結(jié)點(diǎn)結(jié)束Y開(kāi)始調(diào)試分析：在調(diào)試中出現(xiàn)了主菜單以后，在主菜單中選擇操作就沒(méi)有反應(yīng)了，經(jīng)過(guò)查找原程序發(fā)覺(jué)在swich語(yǔ)句中少了少了case語(yǔ)句。測(cè)試結(jié)果：試驗(yàn)成績(jī)：試驗(yàn)題目：試驗(yàn)五采取鄰接表實(shí)現(xiàn)圖DFS和BFS試驗(yàn)日期：/試驗(yàn)要求：1.認(rèn)真閱讀和掌握本試驗(yàn)相關(guān)知識(shí)。2.編寫程序?qū)崿F(xiàn)圖鄰接表存放方式。3.編寫程序?qū)崿F(xiàn)對(duì)圖DFS（遞歸）和BFS（非遞歸）算法實(shí)現(xiàn)。4.保留程序運(yùn)行結(jié)果，結(jié)合程序分析這兩種遍歷結(jié)構(gòu)特點(diǎn)。5.填寫試驗(yàn)匯報(bào)概要設(shè)計(jì)：編寫C或C++語(yǔ)言程序，實(shí)現(xiàn)圖以下功效：(1)利用鄰接表結(jié)構(gòu)特征實(shí)現(xiàn)對(duì)圖中各個(gè)頂點(diǎn)存放。(2)利用DFS算法對(duì)圖中各個(gè)頂點(diǎn)進(jìn)行遍歷而且輸出遍歷結(jié)果。(3)利用BFS算法對(duì)圖中各個(gè)頂點(diǎn)進(jìn)行遍歷而且輸出遍歷結(jié)果。(4)選擇菜單上0，退出該程序運(yùn)行，結(jié)束試驗(yàn)內(nèi)容。分析：(1)建立無(wú)向圖鄰接表，而且輸出該無(wú)向圖鄰接表。(2)輸入DFS出發(fā)點(diǎn)，按照DFS遍歷算法遍歷圖中頂點(diǎn)。(3)輸入BFS出發(fā)點(diǎn)，因?yàn)锽FS采取是非遞歸形式，所以要經(jīng)過(guò)建立隊(duì)列來(lái)實(shí)現(xiàn)BFS遍歷過(guò)程。所以，在編寫該算法過(guò)程中，就要建立隊(duì)列，即隊(duì)列初始化操作、判斷隊(duì)是否為空、入隊(duì)和出隊(duì)操作。詳細(xì)設(shè)計(jì)：//-----------------對(duì)圖G作深度優(yōu)先遍歷--------------voidDfstraverse(){ inti; for(i=0;i<G.vexnum;i++)visited[i]=0; printf("深度優(yōu)先遍歷："); for(i=0;i<G.vexnum;i++) if(!visited[i])DFS(i); printf("\n");}voidInitqueue()//結(jié)構(gòu)一個(gè)空隊(duì)列s{ s.head=(int*)malloc(Max*sizeof(int)); if(!s.head)exit(0);//存放分配失敗 s.front=s.rear=s.head; s.stacksize=Max;}//---------------按廣