數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)報告樣本

實(shí)驗(yàn)一線性表實(shí)驗(yàn)規(guī)定掌握數(shù)據(jù)構(gòu)造中線性表基本概念。純熟掌握線性表基本操作：創(chuàng)立、插入、刪除、查找、輸出、求長度及合并并運(yùn)算在順序存儲構(gòu)造上實(shí)驗(yàn)。純熟掌握鏈表各種操作和應(yīng)用。實(shí)驗(yàn)內(nèi)容編寫一種函數(shù)，從一種給定順序表A中刪除元素值在x到y(tǒng)之間所有元素，規(guī)定以較高效率來實(shí)現(xiàn)。試寫一種算法，在無頭結(jié)點(diǎn)動態(tài)單鏈表上實(shí)現(xiàn)線性表插入操作設(shè)計(jì)一種記錄選票算法，輸出每個候選人得票成果。實(shí)驗(yàn)代碼2.1代碼：#include<stdio.h>typedefintelemtype;#definemaxsize10intdel(intA[],intn,elemtypex,elemtypey){ inti=0,k=0; while(i<n) {if(A[i]>=x&&A[i]<=y) k++; else A[i-k]=A[i]; i++; } return(n-k);}voidmain(){ inti,j; inta[maxsize]; printf("輸入%d個數(shù):\n",maxsize); for(i=0;i<maxsize;i++) scanf("%d,",&a[i]);j=del(a,maxsize,1,3);printf("輸出刪除后剩余數(shù):\n");for(i=0;i<j;i++) printf("%d"\n,a[i]);}2.2代碼：INSERT(L,i,b)。voidInsert(Linklist&L,inti,elemtypex){ if(!L) { L=(Linklist)malloc(sizeof(Lnode)); (*L).data=x;(*L).next=NULL; } else { if(i==1) { s=(Linklist)malloc(sizeof(Lnode)); s->data=x;s->next=L;L=s; } else { p=L;j=1; while(p&&j<i-1) {j++;p=p->next;} if(p||j>i-1) returnerror; s=(Linklist)malloc(sizeof(Lnode)); s->data=x;s->next=p->next;p->next=s; } }}2.3代碼：typedefintelemtypetypedefstructlinknode{ elemtypedata; structlinknode*next;}nodetype;nodetype*create(){ elemtyped; nodetypeh=NULL,*s,*t; inti=1; printf("建立單鏈表:\n"); while(1) { printf("輸入第%d個結(jié)點(diǎn)數(shù)據(jù)域",i); scanf("%d",&d); if(d==0)break; if(i==1) { h=(nodetype*)malloc(sizeof(nodetype)); h->data=d;h->next=NULL;t=h; } else { s=(nodetype*)malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s; } i++; } returnh;}voidsat(nodetype*h,inta[]){ nodetype*p=h; while(p!=NULL) { a[p->data]++; p=p->next; }}voidmain(){ inta[N+1],i; for(i=0;i<N;i++) a[i]=0; nodetype*head; head=create(); sat(head,a); printf("候選人:"); for(i=1;i<=N;i++)printf("%3d",i); printf("\n得票數(shù)\n"); for(i=1;i<=N;i++) printf("%3d",a[i]); printf("\n");}實(shí)驗(yàn)小結(jié)線性表是最簡樸、最慣用一種數(shù)據(jù)構(gòu)造，是實(shí)現(xiàn)其她數(shù)據(jù)構(gòu)造基本。實(shí)驗(yàn)二棧與隊(duì)列實(shí)驗(yàn)規(guī)定理解棧和隊(duì)列特性，以便靈活運(yùn)用。純熟掌握棧和關(guān)于隊(duì)列各種操作和應(yīng)用。實(shí)驗(yàn)內(nèi)容設(shè)一種算術(shù)表達(dá)式涉及圓括號，方括號和花括號三種括號，編寫一種算法判斷其中括號與否匹配。實(shí)驗(yàn)代碼2.1代碼：#include<stdio.h>#include<malloc.h>#include<string.h>#defineNULL0typedefstructlist{ charstr; structlist*next;}list;voidpush(char,list*);intpop(char.list*);voiddeal(char*str);main(void){charstr[20];printf("\n請輸入一種算式:\n");gets(str);deal(str);printf("對的!");getchar();return0;}voiddeal(char*str){list*L;L=(list*)malloc(sizeof(list));if(!L){ printf("錯誤!"); exit(-2);}L->next=NULL;while(*str){ if(*str=='('||*str=='['||*str=='{') push(*str,L); else if(*str==')'||*str==']'||*str=='}') if(pop(*str,L)) {puts("錯誤,請檢查!"); puts("按回車鍵退出"); getchar();exit(-2); } str++;}if(L->next){puts("錯誤,請檢查!");puts("按任意鍵退出");getchar();exit(-2);}}voidpush(charc,list*L){list*p;p=(list*)malloc(sizeof(list));if(!p){ printf("錯誤!"); exit(-2);}p->str=c;p->next=L->next;L->next=p;}#definecheck(s)if(L->next->str==s){p=l->next;L->next=p->next;free(p);return(0);}intpop(charc,list*L){ list*p; if(L->next==NULL)return1; switch(c) { case')':check('(')break; case']':check('[')break; case'}':check('{')break; } return1;實(shí)驗(yàn)小結(jié)棧和隊(duì)列是最基本一種數(shù)據(jù)構(gòu)造之一，為實(shí)現(xiàn)其她數(shù)據(jù)構(gòu)造奠定基石。實(shí)驗(yàn)三樹實(shí)驗(yàn)規(guī)定掌握二叉樹，二叉樹排序數(shù)概念和存儲辦法。掌握二叉樹遍歷算法。純熟掌握編寫實(shí)現(xiàn)樹各種運(yùn)算算法。實(shí)驗(yàn)內(nèi)容編寫程序，求二叉樹結(jié)點(diǎn)數(shù)和葉子數(shù)。編寫遞歸算法，求二叉樹中以元素值為X結(jié)點(diǎn)為根子數(shù)深度。編寫程序，實(shí)現(xiàn)二叉樹先序，中序，后序遍歷，并求其深度。實(shí)驗(yàn)代碼2.1代碼：#include<stdio.h>#include<malloc.h>structnode{ chardata; structnode*lchild,*rchild;}bnode;typedefstructnode*blink;blinkcreat(){ blinkbt; charch; ch=getchar(); if(ch=='')return(NULL); else { bt=(structnode*)malloc(sizeof(bnode)); bt->data=ch; bt->lchild=creat(); bt->rchild=creat(); } returnbt;}intn=0,n1=0;voidpreorder(blinkbt){ if(bt) { n++; if(bt->lchild==NULL&&bt->rchild==NULL) n1++; preorder(bt->lchild); preorder(bt->rchild); }}voidmain(){ blinkroot; root=creat(); preorder(root); printf("此二叉數(shù)接點(diǎn)數(shù)有:%d\n",n); printf("此二叉數(shù)葉子數(shù)有:%d\n",n1);}2.2代碼：intget_deep(bitreeT,intx){ if(T->data==x) { printf("%d\n",get_deep(T)); exit1; } else { if(T->lchild)get_deep(T->lchild,x); if(T->rchild)get_deep(T->rchild,x); }intget_depth(bitreeT){ if(!T)return0; else { m=get_depth(T->lchild); n=get_depth(T->rchild); return(m>n?m:n)+1; }}2.3代碼：#include<stdio.h>#include<malloc.h>structnode{ chardata; structnode*lchild,*rchild;}bnode;typedefstructnode*blink;blinkcreat(){ blinkbt; charch; ch=getchar(); if(ch=='')return(NULL); else { bt=(structnode*)malloc(sizeof(bnode)); bt->data=ch; bt->lchild=creat(); bt->rchild=creat(); } returnbt;}voidpreorder(blinkbt){ if(bt) { printf("%c",bt->data); preorder(bt->lchild); preorder(bt->rchild); }}voidinorder(blinkbt){ if(bt) { inorder(bt->lchild); printf("%c",bt->data); inorder(bt->rchild); }}voidpostorder(blinkbt){ if(bt) { postorder(bt->lchild); postorder(bt->rchild); printf("%c",bt->data); }}intmax(intx,inty){ if(x>y) returnx; else returny;}intdepth(blinkbt){ if(bt) return1+max(depth(bt->lchild),depth(bt->rchild)); else return0;}voidmain(){ blinkroot; root=creat(); printf("\n"); printf("按先序排列:"); preorder(root);printf("\n"); printf("按中序排列:"); inorder(root);printf("\n"); printf("按后序排列:"); postorder(root);printf("\n"); printf("此二叉數(shù)深度是:"); printf("depth=%d\n",depth(root));}實(shí)驗(yàn)小結(jié)通過本章學(xué)習(xí)實(shí)驗(yàn)，對樹有了初步結(jié)識。樹就是一種非線性數(shù)據(jù)構(gòu)造，描述了客觀世界中事物之間層次關(guān)系。這種構(gòu)造有著廣泛應(yīng)用，一切具備層次關(guān)系問題都可以用樹來表達(dá)。實(shí)驗(yàn)四圖實(shí)驗(yàn)規(guī)定熟悉圖各種存儲辦法。掌握遍歷圖遞歸和非遞歸算法。理解圖關(guān)于算法。實(shí)驗(yàn)內(nèi)容寫出將一種無向圖鄰接矩陣轉(zhuǎn)換成鄰接表算法。以鄰接表作存儲構(gòu)造，給出拓?fù)渑判蛩惴▽?shí)現(xiàn)。實(shí)驗(yàn)代碼2.1代碼：voidmattolist(inta[][],adjlistb[],intn)/*n為圖結(jié)點(diǎn)個數(shù)*/{ for(i=0;i<n;i++)b[i].firstarc=NULL；/*鄰接表置空*/ for(i=0;i<n;i++)/*逐行進(jìn)行*/ for(j=n-1;j>=0;j--) if(a[i][j]!=0) {p=(arcnodetp*)malloc(sizeof(arcnodetp));/*產(chǎn)生鄰接點(diǎn)*/ p->adjvex=j； p->nextare=b[i].firstare; b[i].firstarc=p; }}2.2代碼：typedefstructvexnode{ VertexTypevertex; intin;/*增長一種入度域*/ ArecNodeTp*fristarc;}AdjList[vnum];typedefstructgraph{ AdjListadjlist; intvexnum,arcnum;}GraphTp;Top_Sort(GraphTpg){ LstackTp*p;/*建立入度為0頂點(diǎn)棧S*/intm,i,v; initStack(S); for(i=0;i<g.vexnum;i++) if(g.adjlist[i].in==0)/*if(w入度==0)*/ push(S,&v);/*w入S棧*/ m=0; whlie(!EmptyStack(S)){ Pop(S,&v)//S出棧->v printf("%d",v);/*輸出v*/ m++; p=g.adjlist[i].fristarc;/*p=圖g中頂點(diǎn)v第一種鄰接點(diǎn)*/ while(p!=NULL){//p存在 (g.adjlist[p->adjvex].in)--;/*p入度--*/ if(g.adjlist[p->adjvex].in==0)/*if(p入度==0)*/ Push(S,p->adjvex);/*p入S棧*/ p=p->nextarc;/*p=圖g中頂點(diǎn)v下一種鄰接點(diǎn)*/ } } if(m<g.vexnum)return0;/*圖具有環(huán)*/ elsereturn1;}實(shí)驗(yàn)小結(jié)通過本章學(xué)習(xí)實(shí)驗(yàn)，對圖有了詳細(xì)結(jié)識。圖也是一種非線性數(shù)據(jù)構(gòu)造，這種構(gòu)造有著廣泛應(yīng)用，一切具備關(guān)系問題都可以用圖來表達(dá)。實(shí)驗(yàn)五查找實(shí)驗(yàn)規(guī)定掌握順序查找、二分法查找、分塊查找和哈希表查找算法。能運(yùn)用線性表查找辦法解決實(shí)際問題。實(shí)驗(yàn)內(nèi)容編寫一種算法，運(yùn)用二分查找算法在一種有序表中插入一種元素X，并保持表有序性。依照給定數(shù)據(jù)表，先建立索引表，然后進(jìn)行分塊查找。實(shí)驗(yàn)代碼2.1代碼：#include<stdio.h>#include<string.h>#defineMAXNUM20intinput(int*);/*輸入數(shù)據(jù)*/intsearch(int*,int,int);/*查找插入位置*/voidplug(int*,int,int);/*插入數(shù)據(jù)*/voidmain(void){ intdata[MAXNUM],m; intinsert=1; m=input(data); printf("Inputtheinsertnum:"); scanf("%d",data); insert=search(data,1,m);/*返回插入位置*/ plug(data,insert,m); for(insert=1;insert<=m+1;insert++)/*顯示數(shù)據(jù)*/ printf("%3d",*(data+insert)); getch();}intinput(int*data){ inti,m; printf("\nInputthemaxnum:");scanf("%d",&m);printf("inputdata\n");for(i=1;i<=m;i++) scanf("%d",data+i); returnm;}intsearch(int*data,intlow,inthigh)/*遞歸查找插入位置*/{ intmid; if(low>high)returnlow;/*沒有找到插入數(shù)據(jù)，返回low*/ else{ mid=(low+high)/2; if(*(data+mid)==*data)retunmid;/*找到插入數(shù)據(jù)，返回mid*/ elseif(*(data+mid)<*data) elseif(*()data+mid)>*data) } search(data,low,high);}voidplug(int*data,intinsert,intm){ inti; for(i=m;i>insert;i--) *(data+i+1)=*(data+i); *(data+insert)=*data}2.2代碼：#include<stdio.h>#include<conio.h>#include<malloc.h>#definrN18/*元素個數(shù)*/#definrBlocknum3/*分塊數(shù)*/typedefstructindexterm{ intkey;/*最大核心字*/ intaddr;/*塊起始地址*/}index；/*索引表數(shù)據(jù)類型*/index*CreateList(intdata[],intn)/*建索引表*/{ index*p; intm,j,k; m=n/BlockNum;/*分為BlockNum塊，每塊有m個元素*/ p=(index*)malloc(BlockNum*sizeof(index)); for(k=0;k<BlockNum;k++){ (p+k)-