《数据结构》实验指导及报告书（2012） / 学年 第 学期姓 名：______________学 号：______________班 级：______________指导教师：______________信息科学与工程学院2012预备实验 C语言的函数数组指针结构体知识一、实验目的1、复习C语言中函数、数组、指针、结构体与共用体等的概念2、熟悉利用C语言进行程序设计的一般方法二、实验预习说明以下C语言中的概念1、 函数：2、 数组：3、指针：4、结构体5、共用体三、实验内容和要求1、调试程序：输出100以内所有的素数（用函数实现）includeint isprime(int n){ /*判断一个数是否为素数*/ int m; for(m=2;m*m<=n;m++) if(n%m==0) return 0; return 1;}int main(){ /*输出100以内所有素数*/ int i; printf("\n"); for(i=2;i<100;i++) if(isprime(i)==1) printf("%4d",i); return 0;}运行结果：2、 调试程序：对一维数组中的元素进行逆序排列。
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请输入二维数组的数据：\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; /*职业或专业，用s或t表示学生或教师*/ union {int class; /*班级*/char office[10]; /*教研室*/}depa;}stu[N];int main(){ int i; int n;printf(“\n请输入人员数(<10):\n”);scanf(“%d”,&n); for(i=0;i
2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法3、对线性表相应算法的时间复杂度进行分析4、理解顺序表、链表数据结构的特点（优缺点） 二、实验预习说明以下概念1、线性表：2、顺序表：3、链表：三、实验内容和要求1、阅读下面程序，在横线处填写函数的基本功能并运行程序，写出结果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; /*顺序表的当前长度*/ int listsize; /*当前分配的存储空间*/}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:"); /*输入顺序表的元素个数*/ 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 运行结果l 算法分析2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。
删除算法代码：l 运行结果l 算法分析查找算法代码：l 运行结果l 算法分析3、阅读下面程序，在横线处填写函数的基本功能并运行程序，写出结果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); /*输出带头结点单链表的所有元素*/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; /*结点指针域置空*/ p->next=q; /*新结点连在表末尾*/ 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:"); /*输入单链表的元素个数*/ 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 运行结果l 算法分析4、为第3题补充插入功能函数和删除功能函数。
并在主函数中补充代码验证算法的正确性插入算法代码：l 运行结果l 算法分析删除算法代码：l 运行结果l 算法分析以下为选做实验：5、循环链表的应用（约瑟夫回环问题）n个数据元素构成一个环，从环中任意位置开始计数，计到m将该元素从表中取出，重复上述过程，直至表中只剩下一个元素提示：用一个无头结点的循环单链表来实现n个元素的存储l 算法代码6、设一带头结点的单链表，设计算法将表中值相同的元素仅保留一个结点提示：指针p从链表的第一个元素开始，利用指针q从指针p位置开始向后搜索整个链表，删除与之值相同的元素；指针p继续指向下一个元素，开始下一轮的删除，直至p＝＝null为至，既完成了对整个链表元素的删除相同值l 算法代码四、实验小结五、教师评语 实验二 栈和队列一、实验目的1、掌握栈的结构特性及其入栈，出栈操作；2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作二、实验预习说明以下概念1、顺序栈：2、链栈：3、循环队列：4、链队三、实验内容和要求1、阅读下面程序，将函数Push和函数Pop补充完整要求输入元素序列1 2 3 4 5 e，运行结果如下所示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; /*当前已分配的存储空间*/}SqStack;int InitStack(SqStack *S); /*构造空栈*/int push(SqStack *S,ElemType e); /*入栈*/int Pop(SqStack *S,ElemType *e); /*出栈*/int CreateStack(SqStack *S); /*创建栈*/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？体现了栈的什么特性？2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。
l 实现代码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 运行结果：l 输入：a-((c-d)*6-(s/3-x)/2l 运行结果：l 程序的基本功能：以下为选做实验：4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式得结果。
l 实现代码5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法实现代码：四、实验小结五、教师评语 实验三 串的模式匹配一、实验目的1、了解串的基本概念2、掌握串的模式匹配算法的实现 二、实验预习说明以下概念1、模式匹配：2、BF算法：3、KMP算法：三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果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
补充下面程序，实现串的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{ /*节点结构声明*/ char data ; /*节点数据*/ struct BTNode *lchild; struct BTNode *rchild ; /*指针*/}*BiTree;void createBiTree(BiTree *t){ /* 先序遍历创建二叉树*/ 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###运行结果：2、在上题中补充求二叉树中求结点总数算法（提示：可在某种遍历过程中统计遍历的结点数），并在主函数中补充相应的调用验证正确性。
算法代码：3、在上题中补充求二叉树中求叶子结点总数算法（提示：可在某种遍历过程中统计遍历的叶子结点数），并在主函数中补充相应的调用验证正确性算法代码：4、在上题中补充求二叉树深度算法，并在主函数中补充相应的调用验证正确性算法代码：选做实验：（代码可另附纸）4、 补充二叉树层次遍历算法提示：利用队列实现）5、补充二叉树中序、后序非递归算法四、实验小结五、教师评语 实验五 图的表示与遍历一、实验目的1、掌握图的邻接矩阵和邻接表表示2、掌握图的深度优先和广度优先搜索方法 3、理解图的应用方法二、实验预习说明以下概念1、深度优先搜索遍历：2、广度优先搜索遍历：3、拓扑排序：4、最小生成树：5、最短路径：三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果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个顶点出发深度优先搜索*/void tdfs(graph *g); /*深度优先搜索整个图*/void bfs(int k,graph *g); /*从第k个顶点广度优先搜索*/void tbfs(graph *g); /*广度优先搜索整个图*/void init_visit(); /*初始化访问标识数组*/void createGraph(graph *g) /*建立一个无向图的邻接矩阵*/{ int i,j; char v; g->vexnum=0; g->arcnum=0; i=0; printf("输入顶点序列(以#结束)：\n"); while((v=getchar())!='#') { g->vexs[i]=v; /*读入顶点信息*/ i++; } g->vexnum=i; /*顶点数目*/ 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时结束*/ { g->arcs[i][j]=1; g->arcs[j][i]=1; scanf("%d,%d",&i,&j); }}void dfs(int i,graph *g) /*从第i个顶点出发深度优先搜索*/{ 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) /*深度优先搜索整个图*/{ int i; printf("\n从顶点%C开始深度优先搜索序列：",g->vexs[0]); for(i=0;ivexnum;i++) if(visited[i]!=TRUE) dfs(i,g);}void bfs(int k,graph *g) /*从第k个顶点广度优先搜索*/{ 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) /*广度优先搜索整个图*/{ int i; printf("\n从顶点%C开始广度优先搜索序列：",g->vexs[0]); for(i=0;ivexnum;i++) if(visited[i]!=TRUE) bfs(i,g);}void init_visit() /*初始化访问标识数组*/{ int i; for(i=0;i
