数据结构与算法实验指导书.doc

数据结构与算法实验指导书山东师范大学数学科学学院实验大纲序号实 验名 称内 容提 要每组人数实验时数实验要求实验类别备注1抽象数据类型的实现求圆的面积、周长等13必做设计2线性表的基本操作在线性表中插入、删除、查找结点13必做设计3栈和队列及其应用利用栈或队列解决实际问题 16必做设计4树和二叉树的建立及应用二叉树的建立、插入、删除、周游19必做设计5查找算法的实现利用检索算法进行查找16必做设计6内排序算法的实现用某个排序算法进行排序13必做设计7图的建立及应用图的建立等13必做设计8综合实验学生管理、订票系统等13必做综合实验一：抽象数据类型的实现一、实验目的：1、 了解抽象数据类型的表示和实现方法2、 会用C语言中已存在的数据类型来说明新的结构。3、 能用已实现的操作来组合新的操作。4、 熟悉C语言的程序设计二、实验内容输入圆的半径，输出圆的面积和周长。设计一个圆的抽象数据类型，并定义求圆的面积和周长的两个操作,输入数据是圆的半径r，圆的面积S=r2,圆的周长L=2r。圆的类型定义：struct circle float r;float area;float cirm;typedef struct circle *Circle;操作：float area(Circle c)求圆的面积float circmn(Circle c)求圆的周长三、实验步骤1、 启动TC2、 输入下面程序：struct circle float r;float area;float perimeter;typedef struct circle *Circle;float area(Circle c) c-area=3.14*c-r*c-r; return c-area;float perimeter (Circle c) c- perimeter =2*3.14*c-r; return c- perimeter;main()struct circle c;printf(“please input a radius to r”);scanf(“%f”,&c.r);printf(“the areas=%fn”,area(&c);printf(“the perimeter=%fn”,perimeter(&c);3、运行程序、查错。实验二 线性表的基本操作一、实验目的：1、掌握线性表的两种存储结构2、掌握线性表在两种存储结构上建立、插入、删除、查找结点的基本操作3、会利用线性表解决实际问题二、实验内容设有n个人围坐在一个圆桌周围，从第s个人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列。如此反复直到所有的人全部出列为止。三、实验步骤1、 启动TC2、 输入下面程序/*josephus_clist.c*/*Josephus问题：循环链接表实现*/#include #include #define FALSE 0#define TRUE 1typedef int DataType; /* 定义元素类型为整型，也可定义为其他类型 */struct Node;/* 单链表结点类型 */typedef struct Node *PNode;/ 结点指针类型 */struct Node /* 单链表结点结构 */ DataType info;PNode link;typedef struct Node *LinkList;typedef LinkList *PLinkList;int init_clist( PLinkList pclist, int n )/* 用1，2，n为*pclist所示的循环表初始化 */ PNode p,q; int i; q = (PNode)malloc( sizeof( struct Node ) ); if ( q = NULL ) return ( FALSE ); *pclist=q; q-info = 1; q-link = q; if (n=1) return (TRUE); for(i=2;iinfo=i; p-link=q-link; q-link=p; q=p; return (TRUE);void josephus_clist( PLinkList pclist, int s,int m )PNode p,pre;int i;p=*pclist; /* 找第s个元素 */if (s=1)pre =p; p=p-link; while (p!=*pclist) pre =p; p=p-link; else for(i=1;ilink; while (p!=p-link)/* 当链表中结点个数大于1时 */ for (i=1;ilink; printf(“ out element: %d n”,p-info); /* 输出该结点 */ if (*pclist =p) /* 该结点是第一个结点时，删除时需特殊处理一下 */ *pclist =p-link; pre-link = p-link;/* 删除该结点 */ free(p); p = pre-link; printf(“ out element: %d n”,p-info); /* 输出最后一个结点 */*pclist=NULL;free(p);main( )LinkList jos_clist;int n,s,m;/* 输入所需各参数的值 */do printf(“n please input the values of n = “); scanf(“%d”,&n); while (n1);do printf(“ please input the values of s = “); scanf(“%d”,&s); while (s1);do printf(“ please input the values of m = “); scanf(“%d”,&m); while (m1);if (init_clist(&jos_clist,n) josephus_clist(&jos_clist,s,m);else printf(“Out of space!n”);3、 编译、链接、运行、查错。实验三 栈和队列及其应用一、实验目的1、 掌握栈和队列的存储结构及在两种存储结构上的基本操作2、 会利用栈和队列解决实际问题二、实验内容Fibonacci数列1,1,2,3,5,8,13,21,输入n的值，输出前n个元素的值三、实验步骤1、启动TC2.02、输入下面程序#include struct SeqStack int MAXNUM; int t; int *s; ;typedef struct SeqStack *PSeqStack;PSeqStack creatEmptyStack_seq(int m) PSeqStack pastack = (PSeqStack)malloc(sizeof(struct SeqStack); if (pastack!=NULL) pastack-s = (int*)malloc(sizeof(int)*m); if (pastack-s) pastack-MAXNUM=m; pastack -t = -1; return (pastack); else free (pastack); printf(Out of space!n); return NULL;void push_seq( PSeqStack pastack, int x )/* 在栈中压入一元素x */ if( pastack-t = pastack-MAXNUM - 1 ) printf( Overflow! n ); else pastack-t = pastack-t + 1; pastack-spastack-t = x; void pop_seq( PSeqStack pastack )/* 删除栈顶元素 */ if (pastack-t = -1 )printf( Underflow!n ); elsepastack-t = pastack-t - 1;int top_seq( PSeqStack pastack )/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */ if (pastack-t = -1 )printf( It is empty!n ); else return (pastack-spastack-t);main()int i,n,a,temp;PSeqStack pst;scanf(%d,&n);pst=creatEmptyStack_seq(n); push_seq(pst,1); push_seq(pst,1); printf(%d,%d,1,1); i=1; while(i=n) temp= top_seq(pst); pop_seq(pst);a= top_seq(pst); pop_seq(pst); a += temp; push_seq(pst,temp); push_seq(pst,a);printf(%d, a); i+; 3、 运行程序实验四 树和二叉树的建立及应用一、实验目的：1、 掌握树特别是二叉树的建立、插入、删除、周游等算法2、 掌握二叉树的存储方法3、 会利用树结构解决实际问题二、实验内容计算一棵二叉树的叶结点数。用链表存储一棵二叉树，对每个结点判断是否是叶结点，用变量m记录叶结点的个数。输入一棵二叉树，输出该二叉树的叶结点个数。三、实验步骤1、 启动TC2.02、 输入下面程序#include int m=0;typedef int DataType;struct BinTreeNode;typedef struct BinTreeNode *PBinTreeNode;typedef struct BinTreeNode *PBinTree;struct BinTreeNode DataType info; PBinTreeNode llink; PBinTreeNode rlink; ;PBinTree CreateBinTree(void)PBinTree bt; DataType x; scanf(%d,&x); if(x=-1) bt=NULL; else bt=(PBinTreeNode)malloc(sizeof(struct BinTreeNode); bt-info=x; bt-llink=CreateBinTree(); bt-rlink=CreateBinTree(); return bt;int countleaf(PBinTree bt)if(bt=NULL) return 0;if(bt-llink=NULL&bt-rlink=NULL) m+; countleaf(bt-llink); countleaf(bt-rlink);main() PBinTree bt; bt=CreateBinTree(); countleaf(bt); printf(the count of leaf is %dn,m); 3、 调试程序、运行程序。4、 输入数据：1 2 4 1 1 1 3 5 7 1 1 8 1 1 6 1 1输出数据：the count of leaf is 4实验五 查找算法的实现一、实验目的：1、 掌握字典的存储结构2、 掌握字典的检索算法3、 会利用字典结构解决实际问题二、实验内容根据学生的学号，查找某个学生的信息三、实验步骤1、 启动TC2。02、 输入下面程序#include typedef structint num; char name10; char sex; float score;DicElement ;typedef structint m;DicElement *element;HashDictionary;int h(int key)return key%13;HashDictionary* createEmptyDictionary (int m ) int i; HashDictionary* phd = (HashDictionary*)malloc(sizeof(HashDictionary); if (phd!=NULL) phd-element = (DicElement *)malloc(sizeof(DicElement)*m); if (phd-element) phd-m=m;for(i=0;ielementi.num=0; /*初始化*/ return (phd); else free(phd); printf(Out of space!n); /* 存储分配失败 */ return NULL;int linearInsert(HashDictionary *phash, DicElement ele) int position; if (linearSearch(phash, ele.num, &position)=1 ) /*散列表中已有关键码为key的结点 */ printf(Findn); else if(position!=-1) phash-elementposition =ele;/* 插入结点*/ else return(0);/* 散列表溢出 */ return(1);int linearSearch(HashDictionary * phash, int num, int *position)int d, inc;d=h(num);/* d为散列地址，散列函数为h(key) */for(inc=0; incm; inc+) if(phash-elementd.num=num) *position=d;/* 检索成功 */ return(1); else if(phash-elementd.num=0) *position=d;/* 检索失败，找到插入位置 */ return(0); d=(d+1)%phash-m; *position = -1;/* 散列表溢出 */ return(0);main()HashDictionary* phd;int m,i,num,p;DicElement elem;phd=createEmptyDictionary (100 );printf(input the number of student);scanf(%d,&m);for(i=1;ielementp.num,,phd-elementp.sex,phd-elementp.score);3、运行程序实验六 内排序算法的实现一、实验目的：1、理解排序的基本概念2、掌握几种排序的方法3、会比较不同排序方法的优劣二、实验内容试通过随机数据比较各算法的关键字移动次数和所用时间。1、 启动TC2.02、 输入下面程序#include #include #include typedef int KeyType;typedef int DataType;typedef struct KeyType key; DataType info;RecordNode;typedef struct int n; RecordNode *record;SortObject;void selectSort(SortObject * pvector) /* 按递增序进行直接选择排序 */int i, j, k,m=0;RecordNode temp;float t;t=clock();for( i = 0; i n-1; i+ )/* 做n-1趟选择排序 */ k=i; for(j=i+1; jn; j+)/* 在无序区内找出排序码最小的记录Rk*/ if(pvector-recordj.keyrecordk.key) k=j; if(k!=i) /* 记录Rk与Ri互换 */temp=pvector-recordi;pvector-record i= pvector-record k;pvector-record k=temp; m+; printf(nthe number of move is %dn,m);printf(the time of sort is %fsn,(clock()-t)/CLK_TCK);main()int i;SortObject a;randomize();printf(input a number);scanf(%d,&a.n);a.record=(RecordNode*)malloc(sizeof(RecordNode)*a.n);for(i=0;ia.n;i+) a.recordi.key=random(1000); printf(%d ,a.recordi.key); selectSort(&a);for(i=0;ia.n;i+)printf(%d ,a.recordi.key);3、 运行实验七 图的建立及应用一、实验目的：1、 掌握图的存储结构2、 掌握图的基本操作3、 会利用图结构解决实际问题二、实验内容若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何用最低的经济代价建设这个通信网。三、实验步骤1、 启动TC2。02、 输入下面程序#include #define MAXNUM 32767typedef char VexType;typedef int AdjType;typedef struct int n;/* 图的顶点个数 */VexType *vexs;/* 顶点信息 */AdjType *arcs;/* 边信息 */GraphMatrix;typedef structint start_vex, stop_vex;/* 边的起点和终点 */AdjType weight;/* 边的权 */Edge;/* Prim算法*/void prim(GraphMatrix * pgraph, Edge *mst)int i, j, min, vx, vy;float weight, minweight;Edge edge;for(i=0; in-1; i+)msti.start_vex=0; msti.stop_vex=i+1; msti.weight=pgraph-arcs0i+1;for(i=0; in-1; i+)/* 共选n-1条边 */ minweight=MAXNUM; min=i; for(j=i; jn-1; j+)/* 从所有边(vx,vy)(vxU,vyV-U)中选出最短的边 */if(mstj.weightminweight) minweight=mstj.weight; min=j; /* mstmin是最短的边(vx