搜档网
当前位置:搜档网 › 算法与数据结构实验

算法与数据结构实验

算法与数据结构实验
算法与数据结构实验

教学实践环节安排

学生实验前要提前预习实验内容,正确理解实验中的要求,根据实验要求,设计程序,上机实现并验证实验程序,记录实验结果,总结实验内容,写出实验报告。

实验一线性表(验证性)

一.实验目的:通过该实验,理解与掌握线性表的不同存储结构及其基本操作的特点。二、实验内容与要求:

输入两个集合,分别用顺序和链式存储结构设计与实现两集合的并运算、交运算和差运算。

三、实验原理

四、实验设计相关信息

1.实验环境(上机环境)

2.实验项目组成

3.实验项目的程序结构(程序中的函数调用关系图)

4.实验项目包含的各个文件中的函数的功能描述

5.算法描述或流程图

6.实验数据和实验结果

五、程序盘

提交的程序盘应包含全部的程序清单和可执行文件

实验二栈和队列(验证性)

一、实验目的:通过该实验,掌握栈的用法;理解利用栈结构和回溯法解决实际问题的策略。

二、实验内容与要求:

要求输入一个N×N的迷宫,给出迷宫的入口和出口,输出走出迷宫的路线轨迹。

三、实验原理

四、实验设计相关信息

1.实验环境(上机环境)

2.实验项目组成

3.实验项目的程序结构(程序中的函数调用关系图)

4.实验项目包含的各个文件中的函数的功能描述

5.算法描述或流程图

6.实验数据和实验结果

五.程序盘

提交的程序盘应包含全部的程序清单和可执行文件

实验三查找(设计性)

一、实验目的:通过该实验,理解和掌握折半查找和二叉查找算法的思想。

二、实验内容与要求:

要求输入一个顺序表,首先实现折半查找;然后建立一个二叉排序树,实现二叉查找树的查找;

三、实验原理

四、程序设计相关信息

1.实验环境(上机环境)

2.实验项目组成

3.实验项目的程序结构(程序中的函数调用关系图)

4.实验项目包含的各个文件中的函数的功能描述

5.算法描述或流程图

6.实验数据和实验结果

五.程序盘

提交的程序盘应包含全部的程序清单和可执行文件

实验四二叉树(验证性)

一、实验目的:理解和掌握二叉树的存储结构和遍历方法。

二、实验内容与要求:

要求由键盘输入二叉树各结点的值,并建立以二叉链表为存储结构的二叉树;分别输出其中序遍历和后序遍历序列。

三、实验原理

四、实验设计相关信息

1.实验环境(上机环境)

2.实验项目组成

3.实验项目的程序结构(程序中的函数调用关系图)

4.实验项目包含的各个文件中的函数的功能描述

5.算法描述或流程图

6.实验数据和实验结果

五.程序盘

提交的程序盘应包含全部的程序清单和可执行文件

实验五图(设计性)

一、实验目的:理解和掌握图的基本操作;理解贪心策略在图中的应用;理解利用图结构和贪心法解图()决实际问题的策略。

二、实验内容与要求:

输入n个城市间的距离,输出遍历所有城市的最短回路长度及其路线轨迹;

三、实验原理

四、程序设计相关信息

1.实验环境(上机环境)

2.实验项目组成

3.实验项目的程序结构(程序中的函数调用关系图)

4.实验项目包含的各个文件中的函数的功能描述

5.算法描述或流程图

6.实验数据和实验结果

五.程序盘

提交的程序盘应包含全部的程序清单和可执行文件

实验六排序(验证性)

一、实验目的:理解与掌握不同排序算法的设计思想,分析并并理解不同排序算法的时间复杂度和空间复杂度。

二、实验内容与要求:

由键盘输入一组数据,分别用插入排序和选择排序算法思想对其进行升序或降序排列。

三、实验原理

四、程序设计相关信息

1.实验环境(上机环境)

2.实验项目组成

3.实验项目的程序结构(程序中的函数调用关系图)

4.实验项目包含的各个文件中的函数的功能描述

5.算法描述或流程图

6.实验数据和实验结果

五.程序盘

提交的程序盘应包含全部的程序清单和可执行文件

数据结构与算法基础知识总结

数据结构与算法基础知识总结 1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件:

(1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 非线性结构:不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。 在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 非空线性表的结构特征: (1)且只有一个根结点a1,它无前件; (2)有且只有一个终端结点an,它无后件; (3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。 线性表的顺序存储结构具有以下两个基本特点: (1)线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为:adr(ai)=adr(a1)+(i-1)k,,adr(a1)为第一个元素的地址,k代表每个元素占的字节数。 顺序表的运算:插入、删除。(详见14--16页) 4 栈和队列 栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。 栈按照“先进后出”(filo)或“后进先出”(lifo)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom表示栈底。 栈的基本运算:(1)插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。rear指针指向队尾,front指针指向队头。 队列是“先进行出”(fifo)或“后进后出”(lilo)的线性表。 队列运算包括(1)入队运算:从队尾插入一个元素;(2)退队运算:从队头删除一个元素。循环队列:s=0表示队列空,s=1且front=rear表示队列满

数据结构与算法设计实验一

《数据结构与算法设计》 实验报告 ——实验一 学院: 班级: 学号: 姓名:

一、实验目的 第一题利用单向环表实现约瑟夫环。 第二题归并顺序表。 二、实验内容 第一题采用单向环表实现约瑟夫环。 请按以下要求编程实现: ①从键盘输入整数m,通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1,2,……,m。 ②从键盘输入整数s(1<=s<=m)和n,从环表的第s个结点开始计数为1,当计数到第n个结点时,输出该第n结点对应的编号,将该结点从环表中消除,从输出结点的下一个结点开始重新计数到n,这样,不断进行计数,不断进行输出,直到输出了这个环表的全部结点为止。 例如,m=10,s=3,n=4。则输出序列为:6,10,4,9,5,2,1,3,8,7。 第二题选作:归并顺序表。 请按以下要求编程实现: ①从键盘输入两个升序排列的整数序列linka和linkb,每个序列以输入0为结束标记。 ②将链表linka和linkb归并为linkc,linkc仍然为升序排列。归并完成后,linka 和linkb为空表。输出linkc。 ③对linkc进行处理,保持升序不变,删除其中重复的整数,对重复的整数只保留一个,输出删除重复整数后的链表。 例如:linka输入为:10 20 30 40 50 0 linkb输入为:15 20 25 30 35 40 45 50 0 归并后的linkc为:10 15 20 20 25 30 30 35 40 40 45 50 50 删除重复后的linkc为:10 15 20 25 30 35 40 45 50 三、程序设计 1、概要设计 第一题为了实现程序功能,应当建立单向环表来寄存信息及结点,通过查找结

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

#include"stdio.h" #include"stdlib.h" #define NULL 0 #define maxsize 50 typedef struct node{ char data; struct node *lchild,*rchild; }Bitree; int a[maxsize]; int temp=0; Bitree *Q[maxsize]; Bitree *Creatree(){ char ch; int front,rear; Bitree *T,*S; T=NULL; front=1;rear=0; printf("建立二叉树,以@表示虚节点,以#结束输入:\n"); ch=getchar(); while(ch!='#'){ S=NULL; if(ch!='@'){ //@表示虚节点不是虚节点是建立新节点 S=(Bitree *)malloc(sizeof(Bitree)); S->data=ch; S->lchild=S->rchild=NULL; } rear++;Q[rear]=S; //将虚节点指针NULL或新节点地址入队 if(rear==1) T=S; //输入第一个节点为根节点 else{ if(S!=NULL&&Q[front]!=NULL) if(rear%2==0) Q[front]->lchild=S; else Q[front]->rchild=S; if(rear%2==1) front++; //节点Q[front]的两个孩子已经处理完毕,front+1 } ch=getchar(); } return T; } void Inorder(Bitree *T){ //中序遍历二叉树,并将每个结点数据存入数组中if(T!=NULL){ Inorder(T->lchild);

算法与数据结构复习资料

算法与数据结构复习资料 一、单选题 在一个带有附加表头结点的单链表HL中,若要向表头插入一个由指针p指向的结点,则执行( B)。 A. HL=p;p->next=HL; B.p->next=HL->next;HL->next=p; C.p->next=HL;p=HL; D.p->next=HL;HL=p; 若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储(B)个元素. A. n B.n-1 C.n+1 D.不确定 下述哪一条是顺序存储方式的优点?(A) A.存储密度大B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快 设有一个二维数组A[m][n],假设A[0][0]存放位置在600 (10),A[3][3]存放位置在678 (10) , 每个元素占一个空间,问A[2][3] (10)存放在什么位置?(脚注 (10) 表示用10进制表示,m>3)C A.658 B.648 C.633 D.653 下列关于二叉树遍历的叙述中,正确的是( D) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序遍历最后一个结点 B.若一个点是某二叉树的前序遍历最后一个结点,则它必是该二叉树的中序遍历的最后一个结点 C.若一个结点是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序最后一个结点 D.若一个树叶是某二叉树的前序最后一个结点,则它必是该二叉树的中序遍历最后一个结点 k层二叉树的结点总数最多为(A). A.2k-1 B.2K+1 C.2K-1 D. 2k-1 对线性表进行二分法查找,其前提条件是( C). A.线性表以链接方式存储,并且按关键码值排好序 B.线性表以顺序方式存储,并且按关键码值的检索频率排好序 C. 线性表以顺序方式存储,并且按关键码值排好序 D. 线性表以链接方式存储,并且按关键码值的检索频率排好序 对n个记录进行堆排序,所需要的辅助存储空间为(C) A. O(1og2n) B. O(n) C. O(1) D.O(n2) 对于线性表(7,34,77,25,64,49,20,14)进行散列存储时,若选用H(K)=K%7作为散列函数,则散列地址为0的元素有(D)个, A.1 B.2 C.3 D.4 下列关于数据结构的叙述中,正确的是( D). A. 数组是不同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为精炼 C. 树是一种线性结构 D. 用一维数组存储一棵完全二叉树是有效的存储方法 在决定选取何种存储结构时,一般不考虑( A )。 A.各结点的值如何B.结点个数的多少 C.对数据有哪些运算D.所用的编程语言实现这种结构是否方便 需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是(B)。A.单链表B.静态链表C.线性链表D.顺序存储结构 设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为(A)。 A.q=p->next;p->data=q->data;p->next=q->next;free(q); B.q=p->next;q->data=p->data;p->next=q->next;free(q); C.q=p->next;p->next=q->next;free(q);

数据结构与算法设计知识点

数据结构与算法设计知识点 试题类型: 本课程为考试科目(闭卷笔试),试题类型包括:概念填空题(10 %),是非判断题(10 %),单项选择题(40 %),算法填空题(10%),算法应用题(20 %),算法设计题(10 %)。 第一章绪论 重点内容及要求: 1、了解与数据结构相关的概念(集合、数据、数据元素、数据项、关键字、元 素之间的关系等)。 数据:所有能被输入到计算机中,且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素:是数据(集合)中的一个“个体”,数据结构中的基本 单位,在计算机程序中通常作为一个整体来考虑和处理。 数据项:是数据结构中讨论的最小单位,数据元素可以是一个或 多个数据项的组合 关键码:也叫关键字(Key),是数据元素中能起标识作用的数 据项。 其中能起到唯一标识作用的关键码称为主关键码(简称主码); 否则称为次关键码。通常,一个数据元素只有一个主码,但可以有多 个次码。 关系:指一个数据集合中数据元素之间的某种相关性。 数据结构:带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型:是一个值的集合和定义在此集合上的一组操作的总

称。 2、掌握数据结构的基本概念、数据的逻辑结构(四种)和物理结构(数据元素 的表示与关系的表示、两类存储结构:顺序存储结构和链式存储结构)。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构:是对数据元素之间存在的逻辑关系的一种抽象的描述,可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种:线性结构、树形结构、图状结构、集合结构数据的物理结构:是其逻辑结构在计算机中的表示或实现,因此又称其为存储结构。 存储结构:顺序存储结构和链式存储结构 顺序存储结构:利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系; 链式存储结构:除数据元素本身外,采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法,掌握算法时间复杂度相关的概念。 算法:是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性:1.有穷性2.确定性3.可行性4.有输入5.有输出 设计算法时,通常还应考虑满足以下目标: 1.正确性, 2.可读性, 3.健壮性 4.高效率与低存储量需求

算法与数据结构实验

学生实验报告册 (理工类) 课程名称:算法与数据结构专业班级 学生学号:学生: 所属院部:计算机工程学院指导教师:章海鸥 2016 ——2017 学年第 1 学期 金陵科技学院教务处制 实验报告书写要求 实验报告原则上要求学生手写,要求书写工整。若因课程特点需打印的,要遵照以下字体、字号、间距等的具体要求。纸一律采用 A4的纸。

实验报告书写说明 实验报告中一至四项容为必填项,包括实验目的和要求;实验仪器和设备;实验容与过程;实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。 填写注意事项 (1)细致观察,及时、准确、如实记录。 (2)准确说明,层次清晰。 (3)尽量采用专用术语来说明事物。 (4)外文、符号、公式要准确,应使用统一规定的名词和符号。 (5)应独立完成实验报告的书写,严禁抄袭、复印,一经发现,以零分论处。 实验报告批改说明 实验报告的批改要及时、认真、仔细,一律用红色笔批改。实验报告的批改成绩采用百分制,具体评分标准由各院部自行制定。 实验报告装订要求 实验批改完毕后,任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列,装订成册,并附上一份该门课程的实验大纲。

实验项目名称:顺序表实验学时: 2 同组学生:╱实验地点: 实验日期:实验成绩: 批改教师:批改时间:

实验1 顺序表 一、实验目的和要求 掌握顺序表的定位、插入、删除等操作。 二、实验仪器和设备 VC6.0 三、实验容与过程(含程序清单及流程图) 1、必做题 (1)编写程序建立一个顺序表,并逐个输出顺序表中所有数据元素的值。 编写主函数测试结果。 (2)编写顺序表定位操作子函数,在顺序表中查找是否存在数据元素x。 如果存在,返回顺序表中和x值相等的第1个数据元素的序号(序号 从0开始编号);如果不存在,返回-1。编写主函数测试结果。 (3)在递增有序的顺序表中插入一个新结点x,保持顺序表的有序性。 解题思路:首先查找插入的位置,再移位,最后进行插入操作;从第 一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位 置;然后将从表尾开始依次将元素后移一个位置直至元素i;最后将 新结点x插入到i位置。 (4)删除顺序表中所有等于X的数据元素。 2、选做题 (5)已知两个顺序表A和B按元素值递增有序排列,要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表(允许表中含有值 相同的元素)。 程序清单: (1) #include #define maxsize 20 typedef int datatype; typedef struct{ datatype data[maxsize];

数据结构与算法复习题及参考答案

复习题集─参考答案 一判断题 (√)1. 在决定选取何种存储结构时,一般不考虑各结点的值如何。 (√)2. 抽象数据类型与计算机部表示和实现无关。 (×)3. 线性表采用链式存储结构时,结点和结点部的存储空间可以是不连续的。 (×)4. 链表的每个结点中都恰好包含一个指针。 (×)5.链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。(×)6. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。 (×)7. 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。 (×)8. 线性表在物理存储空间中也一定是连续的。 (×)9. 顺序存储方式只能用于存储线性结构。 (√)10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。 (√)11.对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。 (√)12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。 (√)13.两个栈共享一片连续存空间时,为提高存利用率,减少溢出机会,应把两个栈的栈底分别设在这片存空间的两端。 (×)14.二叉树的度为2。 (√)15.若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有n—1个非空指针域。 (×)16.二叉树中每个结点的两棵子树的高度差等于1。 (√)17.用二叉链表法存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。 (√)18.具有12个结点的完全二叉树有5个度为2的结点。 (√)19.二叉树的前序遍历序列中,任意一个结点均处在其孩子结点的前面。 (×)20.在冒泡法排序中,关键值较小的元素总是向前移动,关键值较大的元素总是向后移动。 (×)21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据] (×)22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 (×)23.算法必须用程序语言来书写。 (×)24.判断某个算法是否容易阅读是算法分析的任务之一。 (×)25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] (√)26.分配给顺序表的存单元地址必须是连续的。 (√)27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] (√)28.树形结构中每个结点至多有一个前驱。 (×)29.在树形结构中,处于同一层上的各结点之间都存在兄弟关系。 (×)30.如果表示图的邻接矩阵是对称矩阵,则该图一定是无向图。 (×)31.如果表示图的邻接矩阵是对称矩阵,则该图一定是有向图。 (×)32.顺序查找方法只能在顺序存储结构上进行。 (×)33.折半查找可以在有序的双向链表上进行。

《算法与数据结构》课程设计报告书

烟台大学计算机学院课程设计(算法与数据结构) 设计题目: 班级 姓名 学号 指导教师 成绩 二○一三年四月十日

内容包括: 一、课程设计题目: 二、课程设计内容: 三、算法设计: 四、程序正确性验证(指边界测试数据,即程序对于精心选择的典型、苛刻 而带有刁难性的几组输入数据能够得出满足要求的结果): 五、课程设计过程中出现的主要问题、原因及解决方法: 六、课程设计的主要收获: 七、对今后课程设计的建议:

算法与数据结构课程设计题目 一、单项分值:25分 1、约瑟夫环游戏 2、八皇后问题(图形表示加20分) 3、表达式的求值问题 4、迷宫问题(图形表示加10分) 二、单项分值:80分 5、HTML文档标记匹配算法 要求:输入一段HTML代码,判断该代码是否符合HTML的语法 提示:HTML文档由不同的标记划分为不同的部分与层次。与括号类似,这些标记需要成对出现,对于名为的起始标记,相应的结束标记为。常用的HTML标记: ● :HTML文档 ● :文档标题 ● :文档体 ●

:节的头部 ●
:居中对齐 ● :左对齐 ● :段落 ●。。。 HTML语言有合理的嵌套,如 6、程序源代码的相似性 问题描述:对于两个C++语言的源程序代码,用哈希表的方法分别统计两个程序中使用C++语言关键字的情况,并最终按定量的计算结果,得出两份程序的相似性。 基本要求:建立C++语言关键字的哈希表,统计在每个源程序中C++关键字出现的频度, 得到两个向量X1和X2,通过计算向量X1和X2的相对距离来判断两个源程序的相似性。 例如: 关键字 Void Int For Char if else while do break class 程序1关键字频度 4 3 0 4 3 0 7 0 0 2 程序2关键字频度 4 2 0 5 4 0 5 2 0 1 X1=[4,3,0,4,3,0,7,0,0,2] X2=[4,2,0,5,4,0,5,2,0,1] 设s是向量X1和X2的相对距离,s=sqrt( ∑(xi1-xi2) 2 ),当X1=X2时,s=0, 反映出可能是同一个程序;s值越大,则两个程序的差别可能也越大。 测试数据: 选择若干组编译和运行都无误的C++程序,程序之间有相近的和差别大的,用上述方法求s, 对比两个程序的相似性。 提高要求:建立源代码用户标识符表,比较两个源代码用户标识符出现的频度,综合关键字频度和用户标识符频度判断两个程序的相似性。

算法与数据结构实验册

实验报告书写要求 实验报告原则上要求学生手写,要求书写工整。若因课程特点需打印的,要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。 实验报告书写说明 实验报告中一至四项内容为必填项,包括实验目的和要求;实验仪器和设备;实验内容与过程;实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。 填写注意事项 (1)细致观察,及时、准确、如实记录。 (2)准确说明,层次清晰。 (3)尽量采用专用术语来说明事物。 (4)外文、符号、公式要准确,应使用统一规定的名词和符号。 (5)应独立完成实验报告的书写,严禁抄袭、复印,一经发现,以零分论处。 实验报告批改说明 实验报告的批改要及时、认真、仔细,一律用红色笔批改。实验报告的批改成绩采用百分制,具体评分标准由各院部自行制定。 实验报告装订要求 实验批改完毕后,任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列,装订成册,并附上一份该门课 程的实验大纲。

实验项目名称:顺序表实验学时: 2 同组学生姓名:全班同学实验地点: 1318 实验日期: 10 月14号实验成绩: 批改教师:批改时间:

实验1 顺序表 一、实验目的和要求 掌握顺序表的定位、插入、删除等操作。 二、实验仪器和设备 Turbo C 2.0 三、实验内容与过程(含程序清单及流程图) 1、必做题 (1)编写程序建立一个数续表,并逐个输出顺序表中所有数据元素的值。 编写主函数测试结果。 (2)编写顺序表定位操作子函数,在顺序表中查找是否存在数据元素x。 如果存在,返回顺序表中和x值相等的第1个数据元素的序号(序号 从0开始编号);如果不存在,返回-1。编写主函数测试结果。 (3)在递增有序的顺序表中插入一个新结点x,保持顺序表的有序性。 解题思路:首先查找插入的位置,再移位,最后进行插入操作;从第 一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位 置;然后将从表尾开始依次将元素后移一个位置直至元素i;最后将新 结点x插入到i位置。 (4)删除顺序表中所有等于X的数据元素。 2、选做题 (5)已知两个顺序表A和B按元素值递增有序排列,要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表(允许表中含有值 相同的元素)。 程序清单: 第一题: #include #define maxsize 100 typedef struct{ int datatype [maxsize]; int last; }sequenlist; void main(){ sequenlist a={{1,2,3,4},4}; for(int i=0;i

计科本科生《算法与数据结构》实验报告4

学院专业姓名学号 实验1:约瑟夫环问题(3学时) [问题描述] 将编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个开始按顺时针方向自1开始报数,报到m时停止报数。报m的人出列,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。 [实验目的] (1)掌握线性表的顺序存储结构和循环顺序存储结构。 [实验内容及要求] (1)构造数据结构。 (2)对线性表进行初始化。 [测试数据] 输入一组n,m值时,程序输出出列顺序。 [思考] (1)你采用的存储结构是顺序表还是循环顺序表?哪个比较合适? (2)当存储结构为循环链表时,如何修改你的程序?并考虑两种存储结构的优缺点。

学院专业姓名学号 实验2:ADT List(线性表)(3学时) [问题描述] 线性表是典型的线性结构,实现ADT List,并在此基础上实现两个集合的交运算或并运算。[实验目的] (1)掌握线性表的链表存储结构。 (2)掌握在单链表上基本操作的实现。 (3)在掌握单链表的基本操作上进行综合题的实现。 [实验内容及要求] (1)要求用带头结点的单链表存储两个集合中的元素和最终的结果。 (2)集合的元素限定为十进制数,程序应对出现重复的数据进行过滤,即链表中没有重复数据。 (3)显示两个集合的内容及其运算结果。 [测试数据] (1)set1={3, 8, 5, 8,11},set2={22, 6, 8, 3, 15,11,20 } set1∪set2= set1∩set2= (2)set1={1, 3, 5, 7},set2={2, 3, 7, 14, 25,38} set1∪set2= set1∩set2=

数据结构与算法知识点必备

数据结构与方法 1、算法的基本特征:可行性、确定性、有穷性、拥有足够的情报 2、算法的基本运算与操作:算术运算、逻辑运算、关系运算、数据传输 3、算法的基本控制结构:顺序结构、选择结构、循环(重复)结构 4、算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法 5、算法的复杂度主要包括:时间复杂度、空间复杂度 6、算法的时间复杂度:指执行算法所需要的计算工作量 7、算法的空间复杂度:指执行这个算法所需要的内存空间 8、数据结构主要研究:数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算 9、数据结构研究的目的:提高数据处理的效率 10、数据处理的效率:数据处理的速度、减少处理过程中占用计算机的存储空间 11、数据处理:指对数据集合中的各元素以各种方式进行运算 12、数据元素:指在数据处理中,每一个需要处理的对象都可以抽象成数据元素 13、数据结构:指反映数据元素之间关系的数据元素集合的表示 14、数据的逻辑结构:指反映数据元素之间逻辑关系的数据结构,两要素:数据元素的集合、数据元素在集合上的关系 15、数据的存储结构:指数据的逻辑结构在计算机存储空间的存放形式,常用的存储结构有:顺序、链接、索引等 16、数据结构的图形表示中每个元素加上方框成为结点 17、数据结构一般分为:线性结构、非线性结构 18、线性结构满足:有且仅有一个根结点、每个结点最多有一个前件与后件、在一个线性结构中插入与删除任何一个结点后还就是线性结构 19、线性表定义:线性表就是由n个数据元素a1、a2、a3、a4……an组成的一个有限序列,表中每一个数据元素,除了第一个外,有且仅有一个前件,除了最后一个外,有且仅有一个后件20、非线性表的特征:有且只有一个根节点a1,它无前件、有且只有一个终结点an,它无后件、除了第一个与最后一个外,其她所有结点只有一个前件与一个后件 21、线性表的长度:线性表中的结点的个数n成为线性表的长度,当n=0时,成为空表 22、线性表的顺序存储的特点:所有元素所占的存储空间就是连续的、各数据元素在存储空间中就是按逻辑顺序一次存放的 23、线性表的随机存取地址计算公式:ADD(ai)=ADD(a1)+(i-1)*k 24、线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转 25、栈的定义:栈就是限定在一端进行插入与删除的线性表,它按照“先进后出,后进先出”的原则组织数据 26、栈的顺序存储:在程序设计语言中,一般一维数组S(1:m)作为栈的顺序存储空间,其中m 为栈的最大容量 27、栈的基本运算:入栈、退栈、读栈顶元素 28、入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,称为“上溢”错误 29、退栈运算:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1。当栈顶指针为0时,说明栈空,成为“下溢”错误 30、队列的定义:队列就是指允许在一端进行插入,而在另一端进行删除的线性表,它按照“先进先出”的原则组织数据 31、循环队列:在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列,

数据结构与算法的实验报告

数据结构与算法第二次实验报告 电子105班 赵萌 2010021526

实验二:栈和队列的定义及基本操作 一、实验目的: . 熟练掌握栈和队列的特点 . 掌握栈的定义和基本操作,熟练掌握顺序栈的操作及应用 . 掌握对列的定义和基本操作,熟练掌握链式队列的操作及应用, 掌握环形队列的入队和出队等基本操作 . 加深对栈结构和队列结构的理解,逐步培养解决实际问题的编程能力 二、实验内容: 定义顺序栈,完成栈的基本操作:空栈、入栈、出栈、取栈顶元素; 实现十进制数与八进制数的转换; 定义链式队列,完成队列的基本操作:入队和出队; 1.问题描述: (1)利用栈的顺序存储结构,设计一组输入数据(假定为一组整数),能够对顺序栈进行如下操作: . 初始化一个空栈,分配一段连续的存储空间,且设定好栈顶和栈底; . 完成一个元素的入栈操作,修改栈顶指针; . 完成一个元素的出栈操作,修改栈顶指针; . 读取栈顶指针所指向的元素的值; . 将十进制数N 和其它d 进制数的转换是计算机实现计算的基本问题,其解决方案很多,其中最简单方法基于下列原理:即除 d 取余法。例如:(1348)10=(2504)8 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 从中我们可以看出,最先产生的余数 4 是转换结果的最低位,这正好符合栈的特性即后进先出的特性。 所以可以用顺序栈来模拟这个过程。以此来实现十进制数与八进制数的转换; . 编写主程序,实现对各不同的算法调用。 (2)利用队列的链式存储结构,设计一组输入数据(假定为一组整数),能够对链式队列进行如下操作: . 初始化一个空队列,形成一个带表头结点的空队; . 完成一个元素的入队操作,修改队尾指针; . 完成一个元素的出队操作,修改队头指针; . 修改主程序,实现对各不同的算法调用。

数据结构算法设计题复习题

算法设计题 1. 设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点,并求出非叶子结点的个数。 【答案】 int count=0; void algo2(BTNode *bt){ if (bt){ if(bt->lchild || bt->rchild){ printf(bt->data); count++; } algo2(bt->lchild); algo2(bt->rchild); } } 2. 阅读下列函数arrange() int arrange(int a[],int 1,int h,int x) {//1和h分别为数据区的下界和上界 int i,j,t; i=1;j=h; while(i=x)j--; while(i=x)i++; if(i

数据结构与算法实验报告册

. . 河南工程学院 理学院学院 实验报告 (数据结构与算法) 学期: 课程: 专业: 班级: 学号: 姓名: 指导教师:

. . 目录 实验一线性表1(顺序表及单链表的合并) (1) 实验二线性表2(循环链表实现约瑟夫环) (1) 实验三栈和队列的应用(表达式求值和杨辉三角) (1) 实验四赫夫曼编码 实验五最小生成树 (1) 实验六排序算法

. . 实验一线性表1 一、实验学时:2学时 二、实验目的 1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系。在计算机中 表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。 2.熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储 结构上的实现。 三、实验内容 1. 编写程序,实现顺序表的合并。 2. 编写程序,实现单链表的合并。 四、主要仪器设备及耗材 硬件:计算机一台 软件:VC++ 6.0,MSDN2003或者以上版本 五、算法设计 1. 顺序表合并的基本思想 程序流程图: 2. 单链表合并的基本思想 程序流程图 六、程序清单

. 七、实现结果 .

. 八、实验体会或对改进实验的建议.

. . 实验二线性表2 一、实验学时:2学时 二、实验目的 1.了解双向循环链表的逻辑结构特性,理解与单链表的区别与联系。 2.熟练掌握双向循环链表的存储结构以及基本操作。 三、实验内容 编写程序,采用循环链表实现约瑟夫环。 设有编号为1,2,……,n的n(n>0)个人围成一个圈,从第1个人开始报数,报到m时停止报数,报m的人出圈,再从他的下一个人起重新报数,报到m时停止报数,报m的出圈,……,如此下去,直到所有人全部出圈为止。当任意给定n和m后,设计算法求n个人出圈的次序。 四、主要仪器设备及耗材 硬件:计算机一台 软件:VC++ 6.0,MSDN2003或者以上版本 五、算法设计 约瑟夫环实现的基本思想 程序流程图: 六、程序清单

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1.实验目的 (1)掌握使用Visual C++ 上机调试程序的基本方法; (2)掌握线性表的基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2.实验要求 (1)认真阅读和掌握和本实验相关的教材内容。 (2)认真阅读和掌握本章相关内容的程序。 (3)上机运行程序。 (4)保存和打印出程序的运行结果,并结合程序进行分析。 (5)按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 实验代码: 1)头文件模块 #include >验目的 掌握顺序栈的基本操作:初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 2.实验要求 (1)认真阅读和掌握和本实验相关的教材内容。 (2)分析问题的要求,编写和调试完成程序。 (3)保存和打印出程序的运行结果,并分析程序的运行结果。 3.实验内容 利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下:

(1)定义栈的顺序存取结构。 (2)分别定义顺序栈的基本操作(初始化栈、判栈空否、入栈、出栈等)。 (3)定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中,括号配对共有四种情况:左右括号配对次序不正确;右括号多于左括号;左括号多于右括号;左右括号匹配正确。 (4)设计一个测试主函数进行测试。 (5)对程序的运行结果进行分析。 实验代码: #include < > #define MaxSize 100 typedef struct { int data[MaxSize]; int top; }SqStack;

数据结构与算法设计课程设计

内江师范学院 数据结构与算法设计课程设计实验报告册 编制算法设计课题组审定曾意 数学与信息科学学院 2014年9月

1. 学生在做实验之前必须要准备实验,主要包括预习与本次实验相关的理论知识,熟练与本次实验相关的软件操作,收集整理相关的实验参考资料,要求学生在做实验时能带上充足的参考资料;若准备不充分,则学生不得参加本次实验,不得书写实验报告; 2. 要求学生要认真做实验,主要是指不得迟到、早退和旷课,在做实验过程中要严格遵守实验室规章制度,认真完成实验内容,极积主动地向实验教师提问等;若学生无故旷课,则本次实验等级计为D; 3. 学生要认真工整地书写实验报告,实验报告的内容要紧扣实验的要求和目的,不得抄袭他人的实验报告; 4. 实验成绩评定分为A+、A、A-、B+、B、C、D 各等级。根据实验准备、 实验态度、实验报告的书写、实验报告的内容进行综合评定,具体对应等级如下:完全符合、非常符合、很符合、比较符合、基本符合、不符合、完全不符 合

实验名称:算法设计基础实验(实验一) 指导教师:牟廉明,刘芳实验时数: 4 实验设备:安装了VC++计算机 实验日期:年_月_日实验地点:第五教学楼北802 实验目的: 掌握算法设计的基本原理,熟悉算法设计的基本步骤及其软件实现。 实验准备: 1. 在开始本实验之前,请复习相关实验内容; 2. 需要一台准备安装Windows XP Professional操作系统和装有VC++6.0的计算机。 实验内容: 求n至少为多大时,n个1组成的整数能被2013整除。 实验过程: 1.1算法思想 2013=61*33,6个1能够整除33,寻找满足n个1能够整除61的n即可。 1.2算法步骤 1?定义变量y储存余数,i储存1的个数,m为被除数,初始化为111111; 2?如果被除数能够除尽61,输出i; 如果被除数不能够除尽61,while继续循环,m=y*1000000+111111,i++; 3?重复2,直到找到满足条件的m为止,输出i; 1.3算法实现(C++程序代码) #in clude using n amespace std; int mai n() { int y,m,i; i=6; m=111111; while(y!=0){ m=y*1000000+111111; y=m%61; i=i+6; } cout<

数据结构与算法基础

数据结构与算法基础 一.判断题: 1.数据元素是数据的最小单位。 2.数据结构是带有结构的数据元素的集合。 3.数据结构、数据元素、数据项在计算机中的映像(或表示)分别称为存储结构、结点、数据域。 4.数据项是数据的基本单位。 5.数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要而建立的。 6.数据的物理结构是指数据在计算机内实际的存储形式。 7.算法和程序没有区别,所以在数据结构中二者是通用的。 答案: 1.错误 2.正确 3.正确 4.错误 5.正确 6.正确 7.错误 二. 数据结构是研究数据的 A 和 B 以及它们之间的相互关系,并对这种结构定义相应的 C ,设计出相应的 D ,而确保经过这些运算后所得到的新结构是 E 结构类型。 供选择答案: A、B:a理想结构b抽象结构c物理结构d逻辑结构 C、D、E:a运算b算法c结构d规则e现在的f原来的 答案: A:cB;dC:aD:bE:f 三.从供选择的答案中选取正确的答案填在下面叙述中的横线上: 1. A 是描述客观事物的数字、字符以及所能输入到计算机中并被计算机程序加工处理的符号的集合。 2. B 是数据的基本单位,即数据集合中的个体。有时一个 B 由若干个___C____组成,在这种情况下,称 B 为记录。 C 是数据的最小单位。而由记录所组成的线性表为 D 。 3. E 是具有相同特性的数据元素的集合,是数据的子集。 4. F是带有结构特性数据元素的集合。 5. 被计算机加工的数据元素不是孤立无关的,它们彼此之间一般存在着某种联系。通常将数据元素的这种关系称为G。 6. 算法的计算量的大小称为计算的H。 供选择的答案: A-F:a数据元素b符号c记录d文件e数据f数据项g数据对象h关键字i数据结构

全国计算机二级第1章数据结构与算法

考点1 算法的复杂度 【考点精讲】 1.算法的基本概念 计算机算法为计算机解题的过程实际上是在实施某种算法。 算法的基本特征:可行性、确定性、有穷性、拥有足够的情报。 2.算法复杂度 算法复杂度包括时间复杂度和空间复杂度。 名称 描述 时间复杂度 是指执行算法所需要的计算工作量 空间复杂度 是指执行这个算法所需要的内存空间 考点2 逻辑结构和存储结构 【考点精讲】 1.逻辑结构 数据的逻辑结构是对数据元素之间的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素:一是数据元素的集合,通常记为D;二是D上的关系,它反映了数据元素之间的前后件关系,通常记为R。一个数据结构可以表示成 B=(D,R) 其中B表示数据结构。为了反映D中各数据元素之间的前后件关系,一般用二元组来表示。例如,如果把一年四季看作一个数据结构,则可表示成 B =(D,R) D ={春季,夏季,秋季,冬季} R ={(春季,夏季),(夏季,秋季),(秋季,冬季)} 2.存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。 由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,因此,为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系(即前后件关系),在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息。 一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接等存

储结构。 顺序存储方式主要用于线性的数据结构,它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里,结点之间的关系由存储单元的邻接关系来体现。 链式存储结构就是在每个结点中至少包含一个指针域,用指针来体现数据元素之间逻辑上的联系。 考点3 线性结构和非线性结构 【考点精讲】 根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件: (1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都线性结构。 如果一个数据结构不是线性结构,则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。 考点4 栈 【考点精讲】 1.栈的基本概念 栈(stack)是一种特殊的线性表,是限定只在一端进行插入与删除的线性表。在栈中,一端是封闭的,既不允许进行插入元素,也不允许删除元素;另一端是开口的,允许插入和删除元素。通常称插入、删除的这一端为栈顶,另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。 栈是按照“先进后出”或“后进先出”的原则组织数据的。例如,枪械的子弹匣就可以用来形象的表示栈结构。子弹匣的一端是完全封闭的,最后被压入弹匣的子弹总是最先被弹出,而最先被压入的子弹最后才能被弹出。 2.栈的顺序存储及其运算 栈的基本运算有三种:入栈、退栈与读栈顶元素。 (1)入栈运算:入栈运算是指在栈顶位置插入一个新元素。 (2)退栈运算:退栈是指取出栈顶元素并赋给一个指定的变量。 (3)读栈顶元素:读栈顶元素是指将栈顶元素赋给一个指定的变量。 考点5 队列 【考点精讲】 1.队列的基本概念 队列是只允许在一端进行删除,在另一端进行插入的顺序表,通常将允许删除的这一端称为队头,允许插入的这一端称为队尾。 当表中没有元素时称为空队列。 队列的修改是依照先进先出的原则进行的,因此队列也称为先进先出的线性表,或者后进后出的线性表。例如:火车进遂道,最先进遂道的是火车头,最后是火车尾,而火车出遂道的时候也是火车头先出,最后出的是火车尾。若有队列: Q =(q1,q2,…,qn) 那么,q1为队头元素(排头元素),qn为队尾元素。队列中的元素是按照q1,q2,…,qn 的顺序进入的,退出队列也只能按照这个次序依次退出,即只有在q1,q2,…,qn-1 都退队之后,qn才能退出队列。因最先进入队列的元素将最先出队,所以队列具有先进先出的

相关主题