的顺序不变。设计程序实现。要求:采用顺序存储表示实现;采用链式存储表示方法实现;比较两种方法的优劣。 2. 从单链表中删除指定的元素x,若x在单链表中不存在,给出提示信息。 要求: ①指定的值x由键盘输入; ②程序能处理空链表的情况。 3.设有头结点的单链表,编程对表中的任意值只保留一个结点,删除其余值相同的结点。 要求: ①该算法用函数(非主函数)实现; ②在主函数中调用创建链表的函数创建一个单链表, 并调用该函数,验证算法的正确性。 LinkedList Exchange(LinkedList HEAD,p)∥HEAD是单链表头结点的指针,p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 {q=head->next;∥q是工作指针,指向链表中当前待处理结点。 pre=head;∥pre是前驱结点指针,指向q的前驱。 while(q!=null && q!=p){pre=q;q=q->next;} ∥
数据结构实验报告模板
2009级数据结构实验报告 实验名称:约瑟夫问题 学生姓名:李凯 班级:21班 班内序号:06 学号:09210609 日期:2010年11月5日 1.实验要求 1)功能描述:有n个人围城一个圆圈,给任意一个正整数m,从第一个人开始依次报数,数到m时则第m个人出列,重复进行,直到所有人均出列为止。请输出n个人的出列顺序。 2)输入描述:从源文件中读取。 输出描述:依次从显示屏上输出出列顺序。 2. 程序分析 1)存储结构的选择 单循环链表 2)链表的ADT定义 ADT List{ 数据对象:D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系:R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作: ListInit(&L);//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表,若是,则返回1,否则返回0. ListLength(L); //求单链表L的长度 GetElem(L,i);//返回链表L中第i个数据元素的值; ListSort(LinkList&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除,使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数: 主函数; 结点类; 约瑟夫函数 2.1 存储结构
[内容要求] 1、存储结构:顺序表、单链表或其他存储结构,需要画示意图,可参考书上P59 页图2-9 2.2 关键算法分析 结点类: template class CirList;//声明单链表类 template class ListNode{//结点类定义; friend class CirList;//声明链表类LinkList为友元类; Type data;//结点的数据域; ListNode*next;//结点的指针域; public: ListNode():next(NULL){}//默认构造函数; ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值; ListNode*GetNodePtr(){return next;}//返回结点的指针域的值; void SetNodeData(Type&e){data=e;}//设置结点的数据值; void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值; }; 单循环链表类: templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数,建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数,删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继,若不输入参数,则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继,且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋
数据结构实验报告
数据结构实验报告 第次实验 学号: 20141060106 姓名:叶佳伟 一、实验目的 1、复习二叉树的逻辑结构、存储结构及基本操作; 2、掌握二叉链表及二叉树的创建、遍历; 3、了解二叉树的应用。 二、实验内容 1、(必做题)假设二叉树中数据元素类型是字符型,请采用二叉链表实现二叉树的以下基本操作: (1)根据二叉树的先序序列和中序序列构造二叉树; (2)根据先序遍历二叉树; (3)根据中序遍历二叉树; (4)根据后序遍历二叉树。 测试数据包括如下错误数据: 先序:1234;中序:12345 先序:1234;中序:1245 先序:1234;中序:4231 2、(必做题)对于一棵二叉树,请实现: (1)计算二叉树的叶子数目; (2)计算二叉树的深度。 三、算法描述 (采用自然语言描述) 1、先构造一个二叉树的结构体,再构造createtree的函数实现数据的输入。在键盘上输入先序和中序序列。先判断先序和后序序列是否符合逻辑。若符合逻辑,则在先序、中序、后序函数将二叉树输出。 四、详细设计 (画出程序流程图) 五、程序代码 (给出必要注释) #define max 5 #define TEL 2*max+1
#include "stdio.h" #include "stdlib.h" #include "string.h" typedef char TElemType; typedef struct BiTNode{ TElemType data; //数据域 struct BiTNode *lchild, *rchild; //左右孩子指针域 } BiTNode, *BiTree; BiTNode root; BiTree rt=&root; int calculate(char c,char s[],int st) {char *p; p=s+st; while(*p!=c && *p!='\0') p++; return p-s; } void createtree(BiTree *t,int i1,int i2,int len,char preorder[],char pinorder[]) {int r,llen,rlen; if(len<=0) *t=NULL; else {*t=(BiTree)malloc(sizeof(BiTNode)); (*t)->data=preorder[i1]; r=calculate(preorder[i1],pinorder,i2); llen=r-i2; rlen=len-(llen+1); createtree(&(*t)->lchild,i1+1,i2,llen,preorder,pinorder); createtree(&(*t)->rchild,i1+llen+1,r+1,rlen,preorder,pinorder); } } void PostOrderTraverse(BiTree t) {if(t) {PostOrderTraverse(t->lchild); PostOrderTraverse(t->rchild); putchar(t->data); } } void PreOrderTraverse(BiTree t) {if(t) {putchar(t->data);
数据结构集中上机实验报告
XX大学 信息与计算科学专业 2008级《数据结构》集中上机 设计题目:迷宫求解(非递归求解)设计时间:2010-2011学年第一学期
目录 一、实验内容 (2) 二、需求分析 (2) 三、总体设计 (2) (一)存储结构 (2) (二)流程图 (3) 四、详细设计 (3) (一)基本算法解析 (3) (二)为实现算法,需要的象的数据类型 (4) (三)函数的调用关系 (5) (四)算法时间、空间复杂度 (5) 五、代码 (5) 六、运行结果分析 (10) (一)迷宫路径探索成功 (10) (二)迷宫路径未找到的情况 (13) (三)程序的优缺点与改进 (13) 七、参考文献 (14) 八、心得体会 (14)
一、实验内容 任务:可以输入一个任意大小的迷宫数据,用非递归的方法求出一条走出迷宫的路径,并将路径输出。 二、需求分析 1、可以输入一个任意大小的迷宫数据,用非递归的方法求出一条走出迷宫的路径,并将路径输出;要求使用非递归算法。 2、用户可以根据自己的需求进行输入所需的迷宫,其中1表示迷宫的墙壁,0表示迷宫的通路,从而建立迷宫。 3、可以自行输入迷宫的入口和出口坐标。 4、程序执行的命令包括: (1)构造栈函数。其中包括了构造空栈InitStack;压入新数据元素Push;栈顶元素出栈Pop。 (2)构造求迷宫路径函数。其中定义了二维数组maze[M][N]存取迷宫数据;输出找到的通路MazePath。 (3)建立一个迷宫initmaze。其中包括输入迷宫行数列数以及各行各列;加一圈围墙并输出迷宫。 三、总体设计 (一)存储结构: 首先用二维数组存储迷宫数据,迷宫数据由用户输入。 一个以链表结构作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)形式输出,其中(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向(东南西北所用代表数字,自行定义)。 1.从入口出发,顺着某一个方向进行探索,若能走通,继续往前走,否则沿原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到但没能到达出口,则所设置的迷宫没有通路。 迷宫的入口点的下标(a,b),出口点的下标(m,n)。为方便,可在迷宫周围加一周障碍。对于迷宫的任意位置,均可约定有东西南北4个方向可以走通。经过的位置把0变成-1,输出迷宫路径。 2本程序有三个模块; (1)主程序模块 (2)三个模块即其对象,实现栈链表抽象数据类型 (3)迷宫存储迷宫,寻路径,输出迷宫。
数据结构-实验五-图
数据结构与算法课程实验报告实验五:图的相关算法应用 姓名:cll 班级: 学号:
【程序运行效果】 一、实验内容: 求有向网络中任意两点之间的最短路 实验目的: 掌握图和网络的定义,掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法,掌握求网络的最短路的标号法和floyd算法。 二、问题描述: 对于下面一张若干个城市以及城市间距离的地图,从地图中所有可能的路径中求出任意两个城市间的最短距离及路径,给出任意两个城市间的最短距离值及途径的各个城市。 三、问题的实现: 3.1数据类型的定义 #define MAXVEX 50 //最大的顶点个数 #define MAX 100000 typedef struct{ char name[5]; //城市的名称
}DataType; //数据结构类型 typedef struct{ int arcs[MAXVEX][MAXVEX]; //临接矩阵 DataType data[MAXVEX]; //顶点信息 int vexs; //顶点数 }MGraph,*AdjMetrix; //邻接矩阵表示图 3.2主要的实现思路: 用邻接矩阵的方法表示各城市直接路线的图,之后用Floyd算法求解两点直接的最短距离,并用递归的方法求出途经的城市。 主要源程序代码: #include #include #define MAXVEX 50 #define MAX 100000 typedef struct{ char name[5]; //城市的名称 }DataType; //数据结构类型 typedef struct{ int arcs[MAXVEX][MAXVEX]; //临接矩阵 DataType data[MAXVEX]; //顶点信息 int vexs; //顶点数 }MGraph,*AdjMetrix; //创建临接矩阵 void CreatGraph(AdjMetrix g,int m[][MAXVEX],DataType d[],int n){ /*g表示邻接矩阵,m[][MAXVEX]表示输入的邻接矩阵,d[]表示各城市的名称,n表示城市数目*/ int i,j; g->vexs = n; for(i=0;i < g->vexs;i++){ g->data[i] = d[i]; for(j=0;jvexs;j++){ g->arcs[i][j] = m[i][j]; } } } //求最短路径 void Floyd(AdjMetrix g,int F[][10],int path[][10]){ int i,j,k; for(i=0;ivexs;i++){ for(j=0;jvexs;j++){
数据结构实验报告
《用哈夫曼编码实现文件压缩》 实验报告 课程名称数据结构 实验学期2015至2016学年第一学期 学生所在系部计算机学院 年级2014专业班级物联B142班 学生姓名杨文铎学号201407054201 任课教师白磊 实验成绩
用哈夫曼编码实现文件压缩 1、了解文件的概念。 2、掌握线性表的插入、删除的算法。 3、掌握Huffman树的概念及构造方法。 4、掌握二叉树的存储结构及遍历算法。 5、利用Haffman树及Haffman编码,掌握实现文件压缩的一般原理。 微型计算机、Windows系列操作系统、Visual C++6.0软件 根据ascii码文件中各ascii字符出现的频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩。 本次实验采用将字符用长度尽可能短的二进制数位表示的方法,即对于文件中出现的字符,无须全部都用S为的ascii码进行存储,根据他们在文件中出现的频率不同,我们利用Haffman算法使每个字符能以最短的二进制数字符进行存储,已达到节省存储空间,压缩文件的目的,解决了压缩需要采用的算法,程序的思路已然清晰: 1、统计需压缩文件中的每个字符出现的频率 2、将每个字符的出现频率作为叶子节点构建Haffman树,然后将树中结点引向 其左孩子的分支标“0”,引向其右孩子的分支标“1”;每个字符的编码 即为从根到每个叶子的路径上得到的0、1序列,这样便完成了Haffman 编码,将每个字符用最短的二进制字符表示。 3、打开需压缩文件,再将需压缩文件中的每个ascii码对应的haffman编码按bit 单位输出。 4、文件压缩结束。 (1)构造haffman树的方法一haffman算法 构造haffman树步骤: I.根据给定的n个权值{w1,w2,w3…….wn},构造n棵只有根结点的二叉 树,令起权值为wj。 II.在森林中选取两棵根结点权值最小的树作左右子树,构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和。 III.在森林中删除这两棵树,同时将得到的二叉树加入森林中。 IV.重复上述两步,知道只含一棵树为止,这棵树即哈夫曼树。 对于haffman的创建算法,有以下几点说明: a)这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为
《数据结构》2012级实验报告模板..
实验报告(一) 一、实验目的: 1.掌握VC6.0开发环境下C/C++程序的编辑、编译和运行。 2.通过实验回顾复习C语言中关于结构体、指针等知识的应用。 3.了解学习数据结构的主要方法和课程的主要知识框架。 二、实验环境: 个人电脑、Windows XP、VC6.0或以上版本。 三、实验内容、程序代码、程序测试运行界面 1.设计一个程序,输出所有小于等于n(n为一个大于2的正整数)的素数。要求:(1)每行输出10个素数;(2)尽可能采用较优的算法。 2.编写一个程序,计算任一输入的正整数的各位数字之和,并分析算法的时间复杂度。
3.编写一个程序,判断一个字符串是否为“回文”(顺读和倒读都一样的字符串称为“回文”),并分析算法的时间复杂度。 四、心得体会与建议
实验报告(二) 一、实验目的: 1.熟练掌握线性表的顺序存储结构的概念及各种基本操作的C语言实现。 2.熟练掌握线性表的链式存储结构中的单链表的概念及各种基本操作的C 语言实现。 3.了解双向链表及循环链表的基本操作。 二、实验环境: 个人电脑、Windows XP、VC6.0或以上版本。 三、实验内容、程序代码、程序测试运行界面 1.编写一个程序,实现顺序表的各种基本运算(假设顺序表的元素类型为char),并在此基础上设计一个程序完成如下功能: (1)初始化顺序表L; (2)采用尾插法依次插入元素a,b,c,d,e; (3)输出顺序表L; (4)输出顺序表L长度; (5)判断顺序表L是否为空; (6)输出顺序表L的第3个元素; (7)输出元素a的位置; (8)在第4个位置上插入元素f; (9)输出顺序表L; (10)删除L的第3个元素; (11)输出顺序表L; (12)释放顺序表L。 程序代码如下:
数据结构课程实验报告-实验5
数据结构课程实验报告-实验5
HUNAN UNIVERSITY 课程实习报告 题目:四则运算表达式求值 学生姓名康小雪 学生学号 20090810310 专业班级计科三班 指导老师李晓鸿 完成日期2010-10-24
一、需求分析 1.该程序可以从通过从键盘输入一个中缀表达式,判断该表达式是否合法,若合法将 其转化为后缀表达式,并计算其结果,否则说明该表达式错误 2..输入的表达式包含数字和运算符及括号,之间用空格隔开 3.数字可以为整数和小数 4.运算结果保留两位小数 输入输出举例 输入:21+23*(12-6) 输出:21 23 12 6 -*+ 二、概要设计 在表达式中每个运算符应对应两个操作数,与二叉树中非叶子结点和叶子结点之间的关系刚好相同,于是,本题可采用二叉树来将中缀表达式变为后缀表达式。 最后用堆栈来实现后缀表达式的计算。 抽象数据类型 二叉树 ADT BiTree {
数据对象D:D是具有相同特性的数据元素集合 数据关系R: 若D为空集,则R为空集,则称BinaryTree 为空二叉树; 若D不为空集,否则R={H},H是如下二元关系: (1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2)若D-{root}≠空集,则存在D-{root}的一个划分{D1,Dr} 且D1∩Dr=空集; (3)若D1≠空集,则D1中存在唯一元素x1,∈H,且存在D1shang de guanxi H1=H;ruo Dr≠空集,则Dr中存 在唯一的元素,xr,∈H,且 存在Dr上的关系Hr∈ H;H={,,H1,Hr}; (4)(D1,{H1})是一棵符合本定义的二叉树,称为根的左子树,(Dr,{Hr})是一棵 符合本定义的二叉树,称为根的右子树基本操作P: InitBiTree(&T)
数据结构实验报告及心得体会
2011~2012第一学期数据结构实验报告 班级:信管一班 学号:201051018 姓名:史孟晨
实验报告题目及要求 一、实验题目 设某班级有M(6)名学生,本学期共开设N(3)门课程,要求实现并修改如下程序(算法)。 1. 输入学生的学号、姓名和 N 门课程的成绩(输入提示和输出显示使用汉字系统), 输出实验结果。(15分) 2. 计算每个学生本学期 N 门课程的总分,输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次,总分相同者同名次。 二、实验要求 1.修改算法。将奇偶排序算法升序改为降序。(15分) 2.用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法;。(45分)) 3.编译、链接以上算法,按要求写出实验报告(25)。 4. 修改后算法的所有语句必须加下划线,没做修改语句保持按原样不动。 5.用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义,每种排序算法数据要求均不重复。 (1) 实验题目:《N门课程学生成绩名次排序算法实现》; (2) 实验目的:掌握各种排序算法的基本思想、实验方法和验证算法的准确性; (3) 实验要求:对算法进行上机编译、链接、运行; (4) 实验环境(Windows XP-sp3,Visual c++); (5) 实验算法(给出四种排序算法修改后的全部清单); (6) 实验结果(四种排序算法模拟运行后的实验结果); (7) 实验体会(文字说明本实验成功或不足之处)。
三、实验源程序(算法) Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } for(i=0;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1;
数据结构上机实验5
数据结构上机实验(五)递归 班级:学号:姓名: 上机时间:地点: 一、实验目的 1.理解递归的定义和递归模型。 2.掌握递归设计的一般方法,能用递归算法解决一些较复杂应用问题。 二、实验内容 1.编写程序求解皇后问题 要求:(1)皇后的个数n由用户输入,其值不能超过20; (2)采用递归方法求解。 2.编写一个程序求解背包问题 三、实验过程 1.了解常用函数所在的头文件 stdlib.h stdlib 头文件里包含了C语言的一些函数 该文件包含了的C语言标准库函数的定义 stdlib.h里面定义了五种类型、一些宏和通用工具函数。类型例如size_t、wchar_t、div_t、ldiv_t和lldiv_t;宏例如EXIT_FAILURE、EXIT_SUCCESS、RAND_MAX 和MB_CUR_MAX等等;常用的函数如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、srand()、exit()等等。具体的内容你自己可以打开编译器的include目录里面的stdlib.h头文件看看。 conio.h conio.h不是C标准库中的头文件。 conio是Console Input/Output(控制台输入输出)的简写,其中定义了通过控制台进行数据输入和数据输出的函数,主要是一些用户通过按键盘产生的对应操作,比如getch()函数等等。 &表示引用传递。在函数参数表中,出现带&这个的形参,表示引用传递。2.程序实现(以下代码仅起参考作用) (1)求解皇后问题 #include #include const int N=20; //最多皇后个数 int q[N]; //存放各皇后所在的行号 int cont=0; //存放解个数 void print(int n) //输出一个解 { cont++; int i; printf(" 第%d个解:",cont);