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

《数据结构与算法实验指导书》由会员分享，可在线阅读，更多相关《数据结构与算法实验指导书（14页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法数据结构与算法实验指导书实验指导书山东师范大学数学科学学院山东师范大学数学科学学院实验大纲实验大纲序序号号实实 验验名名 称称内内 容容提提 要要每组每组人数人数实验实验时数时数实验实验要求要求实验实验类别类别备注备注1抽象数据类型的 实现求圆的面积、周长等13必做设计2线性表的基本操 作在线性表中插入、删除、查找结点13必做设计3栈和队列及其应 用利用栈或队列解决实际问题 16必做设计4树和二叉树的建 立及应用二叉树的建立、插入、删除、周游19必做设计5查找算法的实现利用检索算法进行查找16必做设计6内排序算法的实 现用某个排序算法进行排序13必做设计7图的建立及应用图的建立等

2、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 *C

3、ircle; 操作： float area(Circle c) 求圆的面积 float circmn(Circle c) 求圆的周长三、实验步骤 1、 启动 TC 2、 输入下面程序： 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- perime

4、ter; main() flaot r; int r printf(“please input a radius to r”);scanf(“%f”,r); printf(“the areas=%fn”,area(r); printf(“the perimeter=%fn”,perimeter(r); 3、运行程序、查错。实验二 线性表的基本操作一、实验目的： 1、掌握线性表的两种存储结构 2、掌握线性表在两种存储结构上建立、插入、删除、查找结点的基本操作 3、会利用线性表解决实际问题 二、实验内容 设有 n 个人围坐在一个圆桌周围，从第 s 个人开始报数，数到第 m 个人出列，然后从出列的下

5、一 个人重新开始报数，数到第 m 的人又出列。 。 。 。 。如此反复直到所有的人全部出列为止。 三、实验步骤 1、 启动 TC 2、 输入下面程序 /*josephus_clist.c*/ /*Josephus 问题：循环链接表实现问题：循环链接表实现*/#include#include #include#include #define FALSE 0 #define TRUE 1 typedef int DataType; /* 定义元素类型为整型，也可定义为其他类型定义元素类型为整型，也可定义为其他类型 */ struct Node;/* 单链表结点类型单链表结点类型 */ typede

6、f 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

7、) );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

8、 =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

9、element: %d n”,p-info); /* 输出最后一个结点输出最后一个结点 */ *pclist=NULL; free(p); main( ) LinkList jos_clist; int n,s,m; /* 输入所需各参数的值输入所需各参数的值 */ doprintf(“n please input the values of n = “);scanf(“%d”,while (n struct SeqStack int MAXNUM;int t;int *s; typedef struct SeqStack *PSeqStack;PSeqStack creatEmptyStac

10、k_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 ) /*

11、在栈中压入一元素 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“ );else pastack-t = pastack-t - 1; int top_seq( PSeqStack pastack ) /* 当 pastack 所指

12、的栈不为空栈时，求栈顶元素的值 */ if (pastack-t = -1 ) printf( “It is empty!n“ );elsereturn (pastack-spastack-t); main() int i,n,a,temp; PSeqStack pst; scanf(“%d“, pst=creatEmptyStack_seq(n);push_seq(pst,1);push_seq(pst,1);printf(“%d,%d,“,1,1);i=1;while(i #include int m=0; typedef int DataType; struct BinTreeNode;

13、 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“,if(x=-1) bt=NULL;elsebt=(PBinTreeNode)malloc(sizeof(struct BinTreeNode);bt-info=x;bt-

14、llink=CreateBinTree();bt-rlink=CreateBinTree();return bt; int countleaf(PBinTree bt) if(bt=NULL) return 0; if(bt-llink=NULLcountleaf(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

15、1 1 6 1 1 输出数据：the count of leaf is 4实验五 查找算法的实现一、实验目的： 1、 掌握字典的存储结构 2、 掌握字典的检索算法 3、 会利用字典结构解决实际问题 二、实验内容 根据学生的学号，查找某个学生的信息 三、实验步骤 1、 启动 TC2。0 2、 输入下面程序 #include typedef struct int num;char name10;char sex;float score; DicElement ; typedef struct int 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;ielement