《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)及報告書（2012） / 學(xué)年 第 學(xué)期姓 名：______________學(xué) 號：______________班 級：______________指導(dǎo)教師：______________信息科學(xué)與工程學(xué)院2012預(yù)備實驗 C語言的函數(shù)數(shù)組指針結(jié)構(gòu)體知識一、實驗?zāi)康?、復(fù)習(xí)C語言中函數(shù)、數(shù)組、指針、結(jié)構(gòu)體與共用體等的概念2、熟悉利用C語言進行程序設(shè)計的一般方法二、實驗預(yù)習(xí)說明以下C語言中的概念1、 函數(shù)：2、 數(shù)組：3、指針：4、結(jié)構(gòu)體5、共用體三、實驗內(nèi)容和要求1、調(diào)試程序：輸出100以內(nèi)所有的素數(shù)（用函數(shù)實現(xiàn)）includeint isprime(int n){ /*判斷一個數(shù)是否為素數(shù)*/ int m; for(m=2;m*m<=n;m++) if(n%m==0) return 0; return 1;}int main(){ /*輸出100以內(nèi)所有素數(shù)*/ int i; printf("\n"); for(i=2;i<100;i++) if(isprime(i)==1) printf("%4d",i); return 0;}運行結(jié)果：2、 調(diào)試程序：對一維數(shù)組中的元素進行逆序排列。
include#define N 10int main(){ int a[N]={0,1,2,3,4,5,6,7,8,9},i,temp; printf("\nthe original Array is:\n "); for(i=0;i#define M 3#define N 4int main(){ int a[M][N],i,j,k; printf("\n請輸入二維數(shù)組的數(shù)據(jù)：\n"); for(i=0;ia[i][k]) k=j; for(j=0;j
includeint main(){ int a[3][4]={1,3,5,7,9,11,13,15,17,19,21,23}; int *p; for(p=a[0];p#define N 10struct student{ char name[8]; /*姓名*/ int age; /*年齡*/ char job; /*職業(yè)或?qū)I(yè)，用s或t表示學(xué)生或教師*/ union {int class; /*班級*/char office[10]; /*教研室*/}depa;}stu[N];int main(){ int i; int n;printf(“\n請輸入人員數(shù)(<10):\n”);scanf(“%d”,&n); for(i=0;i
2、掌握順序表與鏈表的建立、插入元素、刪除表中某元素的算法3、對線性表相應(yīng)算法的時間復(fù)雜度進行分析4、理解順序表、鏈表數(shù)據(jù)結(jié)構(gòu)的特點（優(yōu)缺點） 二、實驗預(yù)習(xí)說明以下概念1、線性表：2、順序表：3、鏈表：三、實驗內(nèi)容和要求1、閱讀下面程序，在橫線處填寫函數(shù)的基本功能并運行程序，寫出結(jié)果include#include#define ERROR 0#define OK 1#define INIT_SIZE 5 /*初始分配的順序表長度*/#define INCREM 5 /*溢出時，順序表長度的增量*/typedef int ElemType; /*定義表元素的類型*/typedef struct Sqlist{ ElemType *slist; /*存儲空間的基地址*/ int length; /*順序表的當(dāng)前長度*/ int listsize; /*當(dāng)前分配的存儲空間*/}Sqlist;int InitList_sq(Sqlist *L); /* */int CreateList_sq(Sqlist *L,int n); /* */int ListInsert_sq(Sqlist *L,int i,ElemType e);/* */int PrintList_sq(Sqlist *L); /*輸出順序表的元素*/int ListDelete_sq(Sqlist *L,int i); /*刪除第i個元素*/int ListLocate(Sqlist *L,ElemType e); /*查找值為e的元素*/int InitList_sq(Sqlist *L){ L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType)); if(!L->slist) return ERROR; L->length=0; L->listsize=INIT_SIZE; return OK; }/*InitList*/int CreateList_sq(Sqlist *L,int n){ ElemType e; int i; for(i=0;ilength;i++) printf("%5d",L->slist[i-1]); return OK;}/*PrintList*/int ListInsert_sq(Sqlist *L,int i,ElemType e){ int k;if(i<1||i>L->length+1) return ERROR; if(L->length>=L->listsize){ L->slist=(ElemType*)realloc(L->slist,(INIT_SIZE+INCREM)*sizeof(ElemType)); if(!L->slist) return ERROR; L->listsize+=INCREM; } for(k=L->length-1;k>=i-1;k--){ L->slist[k+1]= L->slist[k]; } L->slist[i-1]=e; L->length++; return OK;}/*ListInsert*//*在順序表中刪除第i個元素*/int ListDelete_sq(Sqlist *L,int i){}/*在順序表中查找指定值元素，返回其序號*/int ListLocate(Sqlist *L,ElemType e){ }int main(){ Sqlist sl; int n,m,k; printf("please input n:"); /*輸入順序表的元素個數(shù)*/ scanf("%d",&n); if(n>0){ printf("\n1-Create Sqlist:\n"); InitList_sq(&sl); CreateList_sq(&sl,n); printf("\n2-Print Sqlist:\n"); PrintList_sq(&sl); printf("\nplease input insert location and data:(location,data)\n"); scanf("%d,%d",&m,&k); ListInsert_sq(&sl,m,k); printf("\n3-Print Sqlist:\n"); PrintList_sq(&sl); printf("\n"); } else printf("ERROR"); return 0;}l 運行結(jié)果l 算法分析2、為第1題補充刪除和查找功能函數(shù)，并在主函數(shù)中補充代碼驗證算法的正確性。
刪除算法代碼：l 運行結(jié)果l 算法分析查找算法代碼：l 運行結(jié)果l 算法分析3、閱讀下面程序，在橫線處填寫函數(shù)的基本功能并運行程序，寫出結(jié)果include#include#define ERROR 0#define OK 1typedef int ElemType; /*定義表元素的類型*/typedef struct LNode{ /*線性表的單鏈表存儲*/ ElemType data; struct LNode *next;}LNode,*LinkList;LinkList CreateList(int n); /* */void PrintList(LinkList L); /*輸出帶頭結(jié)點單鏈表的所有元素*/int GetElem(LinkList L,int i,ElemType *e); /* */LinkList CreateList(int n){ LNode *p,*q,*head; int i; head=(LinkList)malloc(sizeof(LNode)); head->next=NULL; p=head; for(i=0;idata); /*輸入元素值*/ q->next=NULL; /*結(jié)點指針域置空*/ p->next=q; /*新結(jié)點連在表末尾*/ p=q; } return head;}/*CreateList*/void PrintList(LinkList L){ LNode *p; p=L->next; /*p指向單鏈表的第1個元素*/ while(p!=NULL){ printf("%5d",p->data); p=p->next; }}/*PrintList*/int GetElem(LinkList L,int i,ElemType *e){ LNode *p;int j=1; p=L->next; while(p&&jnext;j++; } if(!p||j>i) return ERROR; *e=p->data; return OK;}/*GetElem*/int main(){ int n,i;ElemType e; LinkList L=NULL; /*定義指向單鏈表的指針*/ printf("please input n:"); /*輸入單鏈表的元素個數(shù)*/ scanf("%d",&n); if(n>0){ printf("\n1-Create LinkList:\n"); L=CreateList(n); printf("\n2-Print LinkList:\n"); PrintList(L); printf("\n3-GetElem from LinkList:\n"); printf("input i="); scanf("%d",&i); if(GetElem(L,i,&e)) printf("No%i is %d",i,e); else printf("not exists"); }else printf("ERROR"); return 0;}l 運行結(jié)果l 算法分析4、為第3題補充插入功能函數(shù)和刪除功能函數(shù)。
并在主函數(shù)中補充代碼驗證算法的正確性插入算法代碼：l 運行結(jié)果l 算法分析刪除算法代碼：l 運行結(jié)果l 算法分析以下為選做實驗：5、循環(huán)鏈表的應(yīng)用（約瑟夫回環(huán)問題）n個數(shù)據(jù)元素構(gòu)成一個環(huán)，從環(huán)中任意位置開始計數(shù)，計到m將該元素從表中取出，重復(fù)上述過程，直至表中只剩下一個元素提示：用一個無頭結(jié)點的循環(huán)單鏈表來實現(xiàn)n個元素的存儲l 算法代碼6、設(shè)一帶頭結(jié)點的單鏈表，設(shè)計算法將表中值相同的元素僅保留一個結(jié)點提示：指針p從鏈表的第一個元素開始，利用指針q從指針p位置開始向后搜索整個鏈表，刪除與之值相同的元素；指針p繼續(xù)指向下一個元素，開始下一輪的刪除，直至p＝＝null為至，既完成了對整個鏈表元素的刪除相同值l 算法代碼四、實驗小結(jié)五、教師評語 實驗二 棧和隊列一、實驗?zāi)康?、掌握棧的結(jié)構(gòu)特性及其入棧，出棧操作；2、掌握隊列的結(jié)構(gòu)特性及其入隊、出隊的操作，掌握循環(huán)隊列的特點及其操作二、實驗預(yù)習(xí)說明以下概念1、順序棧：2、鏈棧：3、循環(huán)隊列：4、鏈隊三、實驗內(nèi)容和要求1、閱讀下面程序，將函數(shù)Push和函數(shù)Pop補充完整要求輸入元素序列1 2 3 4 5 e，運行結(jié)果如下所示include#include#define ERROR 0#define OK 1#define STACK_INT_SIZE 10 /*存儲空間初始分配量*/#define STACKINCREMENT 5 /*存儲空間分配增量*/typedef int ElemType; /*定義元素的類型*/typedef struct{ ElemType *base; ElemType *top; int stacksize; /*當(dāng)前已分配的存儲空間*/}SqStack;int InitStack(SqStack *S); /*構(gòu)造空棧*/int push(SqStack *S,ElemType e); /*入棧*/int Pop(SqStack *S,ElemType *e); /*出棧*/int CreateStack(SqStack *S); /*創(chuàng)建棧*/void PrintStack(SqStack *S); /*出棧并輸出棧中元素*/int InitStack(SqStack *S){ S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType)); if(!S->base) return ERROR; S->top=S->base; S->stacksize=STACK_INT_SIZE; return OK;}/*InitStack*/int Push(SqStack *S,ElemType e){}/*Push*/int Pop(SqStack *S,ElemType *e){}/*Pop*/int CreateStack(SqStack *S){ int e; if(InitStack(S)) printf("Init Success!\n"); else{ printf("Init Fail!\n"); return ERROR; } printf("input data:(Terminated by inputing a character)\n"); while(scanf("%d",&e)) Push(S,e); return OK;}/*CreateStack*/void PrintStack(SqStack *S){ ElemType e; while(Pop(S,&e)) printf("%3d",e);}/*Pop_and_Print*/int main(){ SqStack ss; printf("\n1-createStack\n"); CreateStack(&ss); printf("\n2-Pop&Print\n"); PrintStack(&ss); return 0;} l 算法分析：輸入元素序列1 2 3 4 5，為什么輸出序列為5 4 3 2 1？體現(xiàn)了棧的什么特性？2、在第1題的程序中，編寫一個十進制轉(zhuǎn)換為二進制的數(shù)制轉(zhuǎn)換算法函數(shù)（要求利用棧來實現(xiàn)），并驗證其正確性。
l 實現(xiàn)代碼l 驗證3、閱讀并運行程序，并分析程序功能include#include#include#define M 20#define elemtype chartypedef struct{ elemtype stack[M]; int top;}stacknode;void init(stacknode *st);void push(stacknode *st,elemtype x);void pop(stacknode *st);void init(stacknode *st){ st->top=0;}void push(stacknode *st,elemtype x){ if(st->top==M) printf("the stack is overflow!\n"); else { st->top=st->top+1; st->stack[st->top]=x; }}void pop(stacknode *st){if(st->top>0) st->top--; else printf(“Stack is Empty!\n”);}int main(){ char s[M]; int i; stacknode *sp; printf("create a empty stack!\n"); sp=malloc(sizeof(stacknode)); init(sp); printf("input a expression:\n"); gets(s); for(i=0;itop==0) printf("'('match')'!\n"); else printf("'('not match')'!\n"); return 0;}l 輸入：2+((c-d)*6-(f-7)*a)/6l 運行結(jié)果：l 輸入：a-((c-d)*6-(s/3-x)/2l 運行結(jié)果：l 程序的基本功能：以下為選做實驗：4、設(shè)計算法，將一個表達式轉(zhuǎn)換為后綴表達式，并按照后綴表達式進行計算，得出表達式得結(jié)果。
l 實現(xiàn)代碼5、假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點（不設(shè)隊頭指針），試編寫相應(yīng)的置空隊列、入隊列、出隊列的算法實現(xiàn)代碼：四、實驗小結(jié)五、教師評語 實驗三 串的模式匹配一、實驗?zāi)康?、了解串的基本概念2、掌握串的模式匹配算法的實現(xiàn) 二、實驗預(yù)習(xí)說明以下概念1、模式匹配：2、BF算法：3、KMP算法：三、實驗內(nèi)容和要求1、閱讀并運行下面程序，根據(jù)輸入寫出運行結(jié)果include#include#define MAXSIZE 100typedef struct{ char data[MAXSIZE]; int length;}SqString;int strCompare(SqString *s1,SqString *s2); /*串的比較*/void show_strCompare();void strSub(SqString *s,int start,int sublen,SqString *sub); /*求子串*/void show_subString();int strCompare(SqString *s1,SqString *s2){ int i; for(i=0;ilength&&ilength;i++) if(s1->data[i]!=s2->data[i]) return s1->data[i]-s2->data[i]; return s1->length-s2->length;}void show_strCompare(){ SqString s1,s2; int k; printf("\n***show Compare***\n"); printf("input string s1:"); gets(s1.data); s1.length=strlen(s1.data); printf("input string s2:"); gets(s2.data); s2.length=strlen(s2.data); if((k=strCompare(&s1,&s2))==0) printf("s1=s2\n"); else if(k<0) printf("s1s2\n"); printf("\n***show over***\n");}void strSub(SqString *s,int start,int sublen,SqString *sub){ int i; if(start<1||start>s->length||sublen>s->length-start+1){ sub->length=0; } for(i=0;idata[i]=s->data[start+i-1]; sub->length=sublen;}void show_subString(){ SqString s,sub; int start,sublen,i; printf("\n***show subString***\n"); printf("input string s:"); gets(s.data); s.length=strlen(s.data); printf("input start:"); scanf("%d",&start); printf("input sublen:"); scanf("%d",&sublen); strSub(&s,start,sublen,&sub); if(sub.length==0) printf("ERROR!\n"); else{ printf("subString is :"); for(i=0;i
補充下面程序，實現(xiàn)串的BF和KMP算法include#include#define MAXSIZE 100typedef struct{ char data[MAXSIZE]; int length;}SqString;int index_bf(SqString *s,SqString *t,int start);void getNext(SqString *t,int next[]);int index_kmp(SqString *s,SqString *t,int start,int next[]);void show_index();int index_bf(SqString *s,SqString *t,int start){補充代碼.....}void getNext(SqString *t,int next[]){ int i=0,j=-1; next[0]=-1; while(ilength){ if((j==-1)||(t->data[i]==t->data[j])){ i++;j++;next[i]=j; }else j=next[j]; }}int index_kmp(SqString *s,SqString *t,int start,int next[]){ 補充代碼.....}void show_index(){ SqString s,t; int k,next[MAXSIZE]={0},i; printf("\n***show index***\n"); printf("input string s:"); gets(s.data); s.length=strlen(s.data); printf("input string t:"); gets(t.data); t.length=strlen(t.data); printf("input start position:"); scanf("%d",&k); printf("BF:\nthe result of BF is %d\n",index_bf(&s,&t,k)); getNext(&t,next); printf("KMP:\n"); printf("next[]:"); for(i=0;i
include#include#define MAX 20typedef struct BTNode{ /*節(jié)點結(jié)構(gòu)聲明*/ char data ; /*節(jié)點數(shù)據(jù)*/ struct BTNode *lchild; struct BTNode *rchild ; /*指針*/}*BiTree;void createBiTree(BiTree *t){ /* 先序遍歷創(chuàng)建二叉樹*/ char s; BiTree q; printf("\nplease input data:(exit for #)"); s=getche(); if(s=='#'){*t=NULL; return;} q=(BiTree)malloc(sizeof(struct BTNode)); if(q==NULL){printf("Memory alloc failure!"); exit(0);} q->data=s; *t=q; createBiTree(&q->lchild); /*遞歸建立左子樹*/ createBiTree(&q->rchild); /*遞歸建立右子樹*/}void PreOrder(BiTree p){ /* 先序遍歷二叉樹*/ if ( p!= NULL ) { printf("%c", p->data); PreOrder( p->lchild ) ; PreOrder( p->rchild) ; }}void InOrder(BiTree p){ /* 中序遍歷二叉樹*/ if( p!= NULL ) { InOrder( p->lchild ) ; printf("%c", p->data); InOrder( p->rchild) ; }}void PostOrder(BiTree p){ /* 后序遍歷二叉樹*/ if ( p!= NULL ) { PostOrder( p->lchild ) ; PostOrder( p->rchild) ; printf("%c", p->data); }}void Preorder_n(BiTree p){ /*先序遍歷的非遞歸算法*/ BiTree stack[MAX],q; int top=0,i; for(i=0;idata); if(q->rchild!=NULL) stack[top++]=q->rchild; if(q->lchild!=NULL) q=q->lchild; else if(top>0) q=stack[--top]; else q=NULL; }}void release(BiTree t){ /*釋放二叉樹空間*/ if(t!=NULL){ release(t->lchild); release(t->rchild); free(t); }}int main(){ BiTree t=NULL; createBiTree(&t); printf("\n\nPreOrder the tree is:"); PreOrder(t); printf("\n\nInOrder the tree is:"); InOrder(t); printf("\n\nPostOrder the tree is:"); PostOrder(t); printf("\n\n先序遍歷序列（非遞歸）:"); Preorder_n(t); release(t); return 0;}l 運行程序輸入：ABC##DE#G##F###運行結(jié)果：2、在上題中補充求二叉樹中求結(jié)點總數(shù)算法（提示：可在某種遍歷過程中統(tǒng)計遍歷的結(jié)點數(shù)），并在主函數(shù)中補充相應(yīng)的調(diào)用驗證正確性。
算法代碼：3、在上題中補充求二叉樹中求葉子結(jié)點總數(shù)算法（提示：可在某種遍歷過程中統(tǒng)計遍歷的葉子結(jié)點數(shù)），并在主函數(shù)中補充相應(yīng)的調(diào)用驗證正確性算法代碼：4、在上題中補充求二叉樹深度算法，并在主函數(shù)中補充相應(yīng)的調(diào)用驗證正確性算法代碼：選做實驗：（代碼可另附紙）4、 補充二叉樹層次遍歷算法提示：利用隊列實現(xiàn)）5、補充二叉樹中序、后序非遞歸算法四、實驗小結(jié)五、教師評語 實驗五 圖的表示與遍歷一、實驗?zāi)康?、掌握圖的鄰接矩陣和鄰接表表示2、掌握圖的深度優(yōu)先和廣度優(yōu)先搜索方法 3、理解圖的應(yīng)用方法二、實驗預(yù)習(xí)說明以下概念1、深度優(yōu)先搜索遍歷：2、廣度優(yōu)先搜索遍歷：3、拓?fù)渑判颍?、最小生成樹：5、最短路徑：三、實驗內(nèi)容和要求1、閱讀并運行下面程序，根據(jù)輸入寫出運行結(jié)果include#define N 20#define TRUE 1#define FALSE 0int visited[N]; typedef struct /*隊列的定義*/{ int data[N]; int front,rear;}queue;typedef struct /*圖的鄰接矩陣*/{ int vexnum,arcnum; char vexs[N]; int arcs[N][N];}graph;void createGraph(graph *g); /*建立一個無向圖的鄰接矩陣*/void dfs(int i,graph *g); /*從第i個頂點出發(fā)深度優(yōu)先搜索*/void tdfs(graph *g); /*深度優(yōu)先搜索整個圖*/void bfs(int k,graph *g); /*從第k個頂點廣度優(yōu)先搜索*/void tbfs(graph *g); /*廣度優(yōu)先搜索整個圖*/void init_visit(); /*初始化訪問標(biāo)識數(shù)組*/void createGraph(graph *g) /*建立一個無向圖的鄰接矩陣*/{ int i,j; char v; g->vexnum=0; g->arcnum=0; i=0; printf("輸入頂點序列(以#結(jié)束)：\n"); while((v=getchar())!='#') { g->vexs[i]=v; /*讀入頂點信息*/ i++; } g->vexnum=i; /*頂點數(shù)目*/ for(i=0;ivexnum;i++) /*鄰接矩陣初始化*/ for(j=0;jvexnum;j++) g->arcs[i][j]=0; printf("輸入邊的信息：\n"); scanf("%d,%d",&i,&j); /*讀入邊i,j*/ while(i!=-1) /*讀入i,j為－1時結(jié)束*/ { g->arcs[i][j]=1; g->arcs[j][i]=1; scanf("%d,%d",&i,&j); }}void dfs(int i,graph *g) /*從第i個頂點出發(fā)深度優(yōu)先搜索*/{ int j; printf("%c",g->vexs[i]); visited[i]=TRUE; for(j=0;jvexnum;j++) if((g->arcs[i][j]==1)&&(!visited[j])) dfs(j,g);}void tdfs(graph *g) /*深度優(yōu)先搜索整個圖*/{ int i; printf("\n從頂點%C開始深度優(yōu)先搜索序列：",g->vexs[0]); for(i=0;ivexnum;i++) if(visited[i]!=TRUE) dfs(i,g);}void bfs(int k,graph *g) /*從第k個頂點廣度優(yōu)先搜索*/{ int i,j; queue qlist,*q; q=&qlist; q->rear=0; q->front=0; printf("%c",g->vexs[k]); visited[k]=TRUE; q->data[q->rear]=k; q->rear=(q->rear+1)%N; while(q->rear!=q->front) { i=q->data[q->front]; q->front=(q->front+1)%N; for(j=0;jvexnum;j++) if((g->arcs[i][j]==1)&&(!visited[j])) { printf("%c",g->vexs[j]); visited[j]=TRUE; q->data[q->rear]=j; q->rear=(q->rear+1)%N; } }}void tbfs(graph *g) /*廣度優(yōu)先搜索整個圖*/{ int i; printf("\n從頂點%C開始廣度優(yōu)先搜索序列：",g->vexs[0]); for(i=0;ivexnum;i++) if(visited[i]!=TRUE) bfs(i,g);}void init_visit() /*初始化訪問標(biāo)識數(shù)組*/{ int i; for(i=0;i
