[工学]数据结构实验教学.doc

数据结构实验指导说明：课内上机要求完成实验一到实验四的内容，并完成实验报告，实验报告在十三周星期三之前交，其他实验请大家课外抽时间完成。给出的示例程序供大家参考，大家实验的时候要自己动手编写程序，切不可完全照抄，每个实验具体的实验题目大家可以做示例的题目，也可以自己定一题目，只需用到该实验的知识点即可。一实验要求：   熟练掌握C语言的编辑、编译、调试程序，会书写类C语言的算法，并将算法转变为程序实现。正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。二主要仪器设备：（所开实验的主要仪器设备）   硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供P及以上的微机。三、实验项目内容简介为了达到实验目的，本课程安排了四个实习单元，训练的重点在于基本的数据结构，而不是强调面面俱到。各实习单元与教科书的各章只具有粗略的对应关系，一个实习题常常涉及到几部分教学内容。1、线性表基本操作 （1) 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现（2)以线性表的各种操作（建立、插入、删除等）的实现为重点（3) 通过本次实习帮助学生加深对高级语言C语言的使用（特别是函数参数、指针类型、链表的使用）。2、栈、队列以及递归算法的设计（1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们（2)  训练的要点是“栈”的观点及其典型用法；问题求解的状态表示及其递归算法；由递归程序到非递归程序的转化方法  3、树、图及其应用 （1)       树和图是两种非线性数据结构，广义表的实质是树结构，而稀疏矩阵的十字链表存储结构也是图的一种存储结构，故本单元是本课的实习重点。（2)       要求学生熟悉各种存储结构的特性，以及如何应用树和图结构求解具体问题。（3)       训练的要点是：递归算法的设计方法；表达式的求值技术；哈夫曼方法及其编译码技术；完整的应用系统的用户界面设计和操作定义方法；矩阵乘法的特殊操作顺序；路径遍历（树、图的遍历）技术。4、查找和排序本次实习旨在集中对几个专门的问题做较为深入的探讨和理解重点在掌握各种内部排序算法、查找算法的思想和实现。学生在实习中体会查找和内部排序算法思想，理解开发高效算法的可能性和寻找、构造高效算法的方法。四、主要参考书1、数据结构题集（C语言版）实习题部分，清华大学出版社,1999.112、数据结构习题与解析（C语言篇），李春葆 编著，清华大学出版社，2000.13、宁正元数据结构习题解析与上机实验指导 水利水电出版社（2003年）实验一 线性表的操作一、实验目的1熟悉C语言的上机环境，掌握C语言的基本结构。2会定义线性表的顺序存储结构。（链式存储结构）3熟悉对顺序表（单链表）的一些基本操作。二、实验要求1认真阅读和掌握本实验内容所给的全部程序。2保存和打印出程序运行结果，并结合程序进行分析。注意事项在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。三、实验内容1、示例（以顺序表为示例，同学们也可以编程实现单链表的创建、查找、插入、删除等功能）以输入整形数据为主，输入后按“？”结束输入。 程序所能表达到的功能为：实现顺序表的创建、查找、插入、删除等功能。程序运行后，输入数据并执行。#include "stdio.h"#include "conio.h"#define MaxSize 50typedef char elemtype;typedef struct node     elemtype dataMaxSize;    int len;lnode,*List;void init(List L) L->len=0;int length(List L) return L->len;elemtype getnode(List L,int pos)    if(pos<1 | pos>L->len) printf("error");    else return L->datapos-1;int locate(List L,elemtype x)   int i=0;    while(i<L->len && L->datai!=x) i+;    if(i=L->len) return -1;    else return(i+1);void insert(List L,int pos,elemtype x)    int j;    if(pos<1 | pos>L->len+1) printf("insert errorn");    else         L->len+;      for(j=L->len;j>=pos;j-)      L->dataj=L->dataj-1;      L->datapos-1=x; ; void delnode(List L,int pos) int j;  if(pos<1 |pos>L->len)printf("del errorn");  else       for(j=pos;j<L->len;j+)      L->dataj-1=L->dataj;       L->len-;        void print(List L)    int i;      for(i=1;i<L->len;i+)      printf("%c->",L->datai-1);      printf("%c",L->dataL->len-1);      main()   int i=1,n;   lnode L;   char ch,x;   init(&L);   printf("nnn*顺序表演示程序*n");   printf("请输入你想建立的顺序表的元素，以？结束:");    ch=getchar();   while(ch!='?')   insert(&L,i,ch);    i+;    ch=getchar();   printf("你建立的顺序表为:");print(&L);printf("n顺序表的长度为:%d",L.len);printf("n输入你想查找的元素：");fflush(stdin);scanf("%c",&x);printf("你查找的元素为%c序位为%d",x,locate(&L,x); printf("n输入你想查找的元素序位:");scanf("%d",&n);   printf("n你查找的元素为：%c",getnode(&L,n); printf("n输入你想插入的元素以及序位:<用逗号隔开>");fflush(stdin);scanf("%c,%d",&x,&n);     insert(&L,n,x);printf("n插入后顺序表为：");     print(&L);     fflush(stdin);printf("n请输入你想删除的元素序位：");scanf("%d",&n);       delnode(&L,n);printf("n删除后的顺序表为：");    print(&L);     getch();四、测试结果运行程序，屏幕显示：“请输入你想建立的顺序表的元素，以？结束:”输入：54381你建立的顺序表为:5>4>3>8>1顺序表的长度为:5输入你想查找的元素：4你查找的元素为4序位为2输入你想查找的元素序位:4你查找的元素为：8 输入你想插入的元素以及序位:<用逗号隔开>"：6，3插入后顺序表为：5>4>6>3>8>1请输入你想删除的元素序位：5删除后的顺序表为：5>4>6>3>1实验二 二叉树的操作一实验目的 理解并熟悉掌握创建二叉树和实现二叉树的三种遍历二实验内容创建二叉树和实现二叉树的三种遍历根据提示输入字符型数据创建二叉树，输入值为所有字符型数据输出为遍历后的每个结点的值的顺序创建二叉树并能实现二叉树的先序、中序、后序遍历如果输入数据为：a b c输出结果为：a b c b a c b c a 程序流程：main()àclrscr()àcreatetree()àpreorder()àinorder()àpostorder源程序#include "stdlib.h"/*引入头文件*/struct tnode/*定义二叉树存储结构*/char data; struct tnode*lchild; struct tnode*rchild;struct tnode tree;/*定义二叉树指针*/void createtree(struct tnode*t)/*创建函数*/struct tnode*p=t;/*把二叉树指针给p*/ char check; if(p->lchild=NULL|p->rchild=NULL) /*判断左右子树是否为空*/ printf("please enter the data:"); /*输入根结点数据*/ scanf("%c",&(p->data); getchar(); if(p->lchild=NULL) printf("%c leftchild is null.Add? y/nn",p->data); /*左子树空，询问是否创建*/ scanf("%c",&check); getchar(); if(check='y') struct tnode*q=(struct tnode*)malloc(sizeof(struct tnode); /*开辟空间*/ q->lchild=NULL; q->rchild=NULL; p->lchild=q; createtree(q); if(p->rchild=NULL) printf("%c rightchild is NULL.Add? y/nn",p->data); /*右子树空，询问是否创建*/ scanf("%c",&check); getchar(); if(check='y') struct tnode*q=(struct tnode*)malloc(sizeof(struct tnode); /*开辟空间*/ q->lchild=NULL; q->rchild=NULL; p->rchild=q; /*连到二叉树上*/ createtree(q); void preorder(struct tnode*t)/*先序遍历函数*/if(t) printf("%c ",t->data);/*输出根结点数据*/ preorder(t->lchild); preorder(t->rchild); void inorder(struct tnode*t) /*中序遍历函数*/if(t) inorder(t->lchild); printf("%c ",t->data); inorder(t->rchild); void postorder(struct tnode*t) /*后序遍历函数*/if(t) postorder(t->lchild); postorder(t->rchild); printf("%c ",t->data); void main() clrscr();/*清屏函数*/ tree.lchild=NULL;/*左子树*/ tree.rchild=NULL;/*右子树*/ createtree(&tree); /*创建二叉树*/ preorder(&tree);/*先序遍历*/ printf("n"); inorder(&tree);/*中序遍历*/ printf("n"); postorder(&tree);/*后序遍历*/三使用说明 程序运行：先输入根结点数据，例如：a输入y或n判断是否创建左子树。输入y然后输入左子树数据输入y或n判断是否创建右子树。输入y然后输入右子树数据按回车可查看遍历结果并退出程序。四测试结果 运行程序，屏幕提示：please enter the data:a /*首先输入根结点，为a*/a leftchild is null.add?y/n /*询问是否输入a结点的左结点*/y /*输入*/please enter the data:b /*输入结点a的左结点，为b*/b leftchild is null.add?y/n /*询问是否输入b结点的左结点*/n /*不输入*/b rightchild is null.add?y/n /*询问是否输入b结点的右结点*/n /*不输入*/a rightchild is null.add?y/n /*询问是否输入a结点的右结点*/y /*输入*/please enter the data:c /*输入结点a的右结点，为c*/c leftchild is null.add?y/n /*询问是否输入c结点的左结点*/n /*不输入*/c rightchild is null.add?y/n /*询问是否输入c结点的右结点*/n /*不输入*/程序退出，显示结果应为： a b c /*先序*/ b a c /*中序*/ b c a /*后序*/实验三 图的遍历操作一实验目的：该实验主要完成对图的创建，并实现图的深度优先遍历和广度优先遍历二实验内容：所输入的数据要为整形数据输出的形式为：每按一次回车，遍历一个结点能创建最大结点树为30的任意图，实现对无向图的两种遍历程序流程：main()àclrscr()àvisited()àDFS()àvisited()àBFS()源程序：#include <stdlib.h>/*引用两个头文件*/#define maxvex 30/*定义MAXVEX=30*/struct edgenode/*定义边的结构体*/int adjvex; char info; struct edgenode*next;struct vexnode/*定义点的结构体*/char data; struct edgenode*link;typedef struct vexnode adjlistmaxvex; /*自定义adjlist为结构体数组类型*/adjlist tu1;/*定义结构体数组变量tu1*/void creategraph(adjlist g,int n)/*图创建函数*/int e,i,s,d;/*定义存储边、点的变量*/ struct edgenode*p,*q;/*定义边的结构体指针*/ printf("the point(n) and edge(e):");/*显示提示输入点，边*/ scanf("%d,%d",&n,&e);/*接收点、边存入n,e中*/ for(i=1;i<=n;i+) getchar(); printf("tthe %d information:",i);/*提示输入结点信息*/ scanf("%c",&gi.data);/*存储信息*/ gi.link=NULL;/*最后指针为空*/ for(i=1;i<=e;i+) printf("nthe%d edges=>nt :",i);/*提示输入边信息*/ scanf("%d,%d",&s,&d);/*接收边的信息*/ p=(struct edgenode*)malloc(sizeof(struct edgenode); q=(struct edgenode*)malloc(sizeof(struct edgenode); /*开辟两个存储边的空间*/ p->adjvex=d;/*把其中一个点存储下来*/ p->info=gd.data; q->adjvex=s;/*把另一个点存储下来*/ q->info=gs.data; p->next=gs.link;/*p和s的link指针连接起来*/ gs.link=p; q->next=gd.link;/*q和s的link指针连接起来*/ gd.link=q;/*完成一个边的创建*/ int visitedmaxvex;/*定义访问数组*/void dfs(adjlist adj,int v)/*深度优先遍历函数*/int i; struct edgenode*p;/*定义边指针*/ visitedv=1;/*把开始遍历的点在访问数组中标识*/ printf("now is at point %d",v); /*输出正访问的点*/ p=adjv.link; printf("the data is %c n",adjv.data);/*输出点的信息*/ getch(); while(p) if(visitedp->adjvex=0) dfs(adj,p->adjvex);/*没有访问的再调用DFS函数*/ p=p->next;/*访问过的判断下一个*/ int quenemaxvex;void bfs(adjlist adj,int vi) /*广度优先遍历函数*/int m=maxvex;/*定义一个队列*/ int front=0,rear=1,v; struct edgenode*p;/*定义边指针*/ visitedvi=1;/*开始访问的点标识一下*/ printf("now visit the point:%dn",vi);/*输出正访问的点*/ getch();quenerear=vi;/*把访问过的点放入数组中*/ while(front!=rear) front=(front+1)%m; v=quenefront; p=adjv.link; while(p) if(visitedp->adjvex=0)/*判断p->adjvex点是否访问过*/ visitedp->adjvex=1;/*访问没有访问过的结点*/printf("now visit the point:%dn",p->adjvex); /*输出正访问的结点*/getch(); rear=(rear+1)%m; quenerear=p->adjvex;/*放入数组中*/ p=p->next;/*指向下一个*/ void main()int i;clrscr(); creategraph(tu1,0);/*创建图*/ for(i=1;i<maxvex;i+) visitedi=0;/*访问数组初始化*/ dfs(tu1,1); /*调用DFS*/getch();/*等待输入*/ for(i=1;i<maxvex;i+) visitedi=0; bfs(tu1,1); /*调用BFS*/三使用说明：根据屏幕上的英文提示先输入结点的个数和边数。然后输入各结点存储的信息，再输入定义的边，形成图。最后分别按照DFS深度优先遍历和BFS广度优先遍历实现对图的遍历。四测试结果：运行程序，屏幕提示：the point(n) and edge(e):4,3 /*输入顶点和边的数目*/the 1 information:a /*各个顶点的信息*/the 2 information:bthe 3 information:cthe 4 information:dthe 1 edges=> /*各个边的连接情况*/:1,2the 2 edges=>:1,3the 3 edges=>:3,4 now is at point 1 the data is a /*深度优先遍历结果*/ now is at point 3 the data is cnow is at point 4 the data is dnow is at point 2 the data is bnow visit the point:1 /*广度优先遍历结果*/now visit the point:3now visit the point:2now visit the point:4cbda实验四 栈的基本操作一、实验目的： 1熟练掌握栈的结构，以及这种数据结构的特点；2 能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；二、实验内容：计算表达式的值【问题描述】计算用运算符后缀法表示的表达式的值。后缀表达式也称逆波兰表达式，比中缀表达式计算起来更方便简单些，中缀表达式要计算就存在着括号的匹配问题，所以在计算表达式值时一般都是先转换成后缀表达式，再用后缀法计算表达式的值。如：表达式(a+b*c)/d-e用后缀法表示应为abc*+d/e-。只考虑四则算术运算，且假设输入的操作数均为1位十进制数（09），并且输入的后缀形式表达式不含语法错误。【数据描述】#define add 43 /*运算符加号+的ASCII码*/#define subs 45 /*运算符减号-的ASCII码*/#define mult 42/*运算符乘号*的ASCII码*/#define div 47/*运算符除号/的ASCII码*/#define MAXSIZE 100typedef struct int stkdataMAXSIZE;/用数组来表示栈空间，定义长度为MAXSIZE的栈 int top; /栈顶指针STKzone;typedef STKzone *STK;typedef enumtrue=1,false=0 bool;typedef enumok,error status; 【C源程序】#include<stdio.h>#define add 43 /*运算符加号+的ASCII码*/#define subs 45 /*运算符减号-的ASCII码*/#define mult 42 /*运算符乘号*的ASCII码*/#define div 47 /*运算符除号/的ASCII码*/#define MAXSIZE 100typedef struct int stkdataMAXSIZE;/*用数组来表示栈空间，定义长度为MAXSIZE的堆栈*/ int top; /*栈顶*/STKzone;typedef STKzone *STK;typedef enumtrue=1,false=0 bool;typedef enumok,error status;STKzone expSTKzone;STK expSTK;STK initSTK(STKzone *stack_zone) /*执行栈初始化，建栈指针*/ STK p; p=stack_zone; p->top=0;status push(int *term,STK pstk)/*将一结构型数据送入栈中*/ if(pstk->top=MAXSIZE) return error; /*栈满，进栈失败*/ pstk->stkdatapstk->top =*term;(pstk->top)+;/*栈顶指针移动*/return ok;/*push*/bool emptySTK(STK pstk)/*判断栈是否为空栈*/return(pstk->top=0);status pop(int *pdata, STK pstk) /*从栈中取出一结构型数据*/if(emptySTK(pstk) return error;(pstk->top)-;/*退栈*/ *pdata =pstk->stkdatapstk->top; return ok;void synerror() printf("n表达式语法错！");exit();int eval(char tag,int a1,int a2) switch(tag) case add:return(a1+a2);case subs:return(a1-a2);case mult:return(a1*a2);case div:return(a1/a2);main() char c; int opd1,opd2,temp,c1; expSTK=initSTK(&expSTKzone); printf("n后置表达式: "); while(c=getchar()!='n') if(c= ' ') continue;if(c>47)&&(c<58)/*判断是否是09的字符*/ putchar(c);c1=c-48;/*把输入的字符型数字转换成数字*/ if(push(&c1,expSTK)=error)/*运算分量进栈*/ printf("n表达式太长n"); exit();else if(c=add)|(c=subs)|(c=mult)|(c=div) putchar(c); if(pop(&opd1,expSTK)=error) /*将运算量1出栈*/ synerror();if(pop(&opd2,expSTK)=error) /*将运算量2出栈*/synerror(); temp=eval(c,opd2,opd1);/*计算得到结果*/ push(&temp,expSTK);/*将运算结果进栈*/ else synerror();/*出现非法字符*/*while*/if(pop(&opd1,expSTK)=error) synerror();if(!(emptySTK(expSTK) synerror();printf(“=%-3dn”,opd1);/*main_end*/【测试数据】输入: 23+输出: =5 (即求2+3的结果)输入: 145*+3/3-输出: 4 (即求(1+4*5)/3-3的结果)【说明】本算法中对后置法表示的表达式求值按如下规则进行：自左向右扫描，每遇到一个n+1元组（opd1,opd2,opdn,opr）(其中opd为操作数，opr为n元运算符)，就计算一次opr（opd1,opd2,opdn）的值，其结果取代原来表达式中n+1元组的位置，再从表达式开头重复上述过程，直到表达式中不含运算符为止。【实验题】1.     假设一个算术表达式中包含零对到多对圆括弧，括弧对之间允许嵌套但不允许交叉，编写一个算法并上机实现：判断输入的表达式是否正确配对。Status correct(string express)；/括弧配对正确，返回ok，否则返回error2. 用栈实现一般表达式（即中缀表达式）到后缀表达式的转换。3. 数制转换。 实验五 数据查找一实验目的： 理解各种查找的思想，实现对数据的查找。例如用：直接查找法和折半查找法。二实验内容：任意输入10个整形数据，然后再输入一个数据进行查找。该程序能对输入的数据进行查找，然后把数据所在的位置输出。例如：输入10个数据：12 3 4 5 6 7 8 9 1 2 输入查找数据：5输出为：the 5 is at 4 position源程序：#include<stdio.h>/*引入头文件*/#include<stdlib.h>void seqsearch(int*,int);/*声明插入查找函数*/void binsearch(int*,int);/*声明折半查找函数*/void bubblesort(int*,int);/*声明起泡排序函数*/void menu() printf(" 1.seqsearch()n"); printf(" 2.binsearch()n"); printf(" 3.exit()n"); printf("please select the method:");void main()int i,j=1; int ch; int a10; clrscr(); printf("please input 10 data:");/*提示输入10个数据*/ for(i=0;i<10;i+) scanf("%d",&(ai);/*接收输入*/ menu();/*显示菜单*/ while(j)/*循环一次*/ scanf("%d",&ch); switch(ch)/*选择执行程序*/ case 1:seqsearch(a,10);break; case 2:binsearch(a,10);break; case 3:j=0;break; default:break; printf("n"); menu(); void seqsearch(int*r,int n)/*直接查找函数*/int i=0,data; printf("please input find data:");/*提示输入查找数据*/ scanf("%d",&data);/*接收数据*/ while(ri!=data)/*循环查找*/ i+; if(i>n) printf("the data is not found");/*输出数据没有找到*/ else printf("the %d position is %d",data,i+1); /*如果找到，输出位置*/ getch();void binsearch(int *r,int n)/*折半查找函数*/int j,data,low=0,high=n,mid,find=0; bubblesort(r,n);/*起泡法排序*/ for(j=0;j<n;j+) printf("%d ",rj);/*排序后输出*/ printf("please input find data:");/*提示输入查找数据*/ scanf("%d",&data); while(low<=high&&!find)/*循环查找*/ mid=(low+high)/2;