数据结构 实验9—顺序查找,hash算法

实验九

实验题目：顺序查找，hash算法

一、实验目的

顺序查找，hash算法，,在vc中实现。本次实验有2个算法，请同学们注意。

二、实验内容：

第一部分：顺序查找算法：

第二部分：Hash算法：

\ 附录：这里的hash函数是k%m,，也就是k%13.

数据结构顺序表真题

第二章复习题 本章重点掌握：线性结构特点，顺序存储结构和链式存储结构特点。 1.在顺序表中插入或删除一个元素，需要平均移动( 一半 )元素，具体移动的元素个数与( 插入或删除的位置 )有关。插入时平均 次数（n/2 ）,删除时平均次数（(n-1)/2 ）。 2.有一个含头结点的循环链表，头指针为 head, 则其为空的条件是：( C ) A)head==NULL B)head->next==NULL C)head->next==head 3.在长度为 n 的顺序表的第 i 个位置上插入一个元素（1≤i≤n+1），元素的移动次数为：( A ) A) n – i + 1 B) n – i C) i D) i – 1 4.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( C ) A)顺序表B) 用头指针表示的循环单链表 C) 用尾指针表示的循环单链表D) 单链表 5.设单链表中结点的结构为（data, link）。已知指针 q 所指结点是指针 p 所指结点的直接前驱，若在*q 与*p 之间插入结点*s，则应执行下列哪一个操作？（ B ） A)s->link = p->link;p->link = s;(B) q->link = s;s->link = p; (C) p->link = s->link;s->link = p;(D) p->link = s;s->link = q; 6.设单链表中结点的结构为（data, link）。已知指针 p 所指结点不是尾结点，若在*p 之后插入结点*s，则应执行下列哪一个操作？（B）

A)s->link = p;p->link = s;(B) s->link = p->link;p->link = s; (C) s->link = p->link;p = s;(D) p->link = s;s->link = p; 7.设单链表中结点的结构为（data, link）。若想摘除结点*p 的直接后继，则应执行下列哪一个操作？（A） (A) p->link = p->link->link; (B) p = p->link;p->link = p->link->link; (C) p->link = p->link;(D) p = p->link->link; 8.设单循环链表中结点的结构为（data, link），且 rear 是指向非空的 带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？（D） (A)s = rear;rear = rear->link;delete s; (B)rear = rear->link;delete rear; (C)rear = rear->link->link;delete rear; (D)s = rear->link->link;rear->link->link = s->link; delete s; （rear 指向尾结点，rear->link->link 指向第一个结点，第一个结点变为原来的第二个结点） 9.设双向循环链表中结点的结构为（data, lLink, rLink），且不带表头 结点。若想在指针 p 所指结点之后插入指针 s 所指结点，则应执 行下列哪一个操作？( D )

二分搜索实验报告

竭诚为您提供优质文档/双击可除 二分搜索实验报告 篇一：算法设计与分析二分查找实验报告 课程设计说明书 设计题目：二分查找程序的实现 专业：班级： 设计人： 山东科技大学年月日 课程设计任务书 学院：信息科学与工程学院专业：班级：姓名： 一、课程设计题目：二分查找程序的实现二、课程设计主要参考资料 （1）计算机算法设计与分析（第三版）王晓东著（2）三、课程设计应解决的主要问题 （1）二分查找程序的实现（2）（3）四、课程设计相关附件（如：图纸、软件等）： （1）（2） 五、任务发出日期：20XX-11-21课程设计完成日期：

20XX-11-24 指导教师签字：系主任签字： 指导教师对课程设计的评语 成绩： 指导教师签字： 年月日 二分查找程序的实现 一、设计目的 算法设计与分析是计算机科学与技术专业的软件方向的必修课。同时，算法设计与分析既有较强的理论性，也有较强的实践性。算法设计与分析的实验过程需要完成课程学习过程各种算法的设计和实现，以达到提高教学效果，增强学生实践动手能力的目标。 用分治法，设计解决二分查找程序的实现问题的一个简捷的算法。通过解决二分查找程序的实现问题，初步学习分治策略。 二、设计要求 给定已按升序排好序的n个元素a[0:n-1]，现要在这n 个元素中找出一特定元素x。实现二分搜索的递归程序并进行跟踪分析其执行过程。 用顺序搜索方法时，逐个比较a[0:n-1]中的元素，直至找出元素x，或搜索遍整个数组后确定x不在其中。这个方

法没有很好的利用n个元素已排好序这个条件，因此在最坏情况下，顺序搜索方法需要o(n)次比较。要求二分法的时间复杂度小于o(n)。 三、设计说明（一）、需求分析 二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用o(logn)时间完成搜索任务。 该算法的流程图如下： （二）、概要设计 二分查(:二分搜索实验报告)找的基本思路是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果 x=a[n/2],则找到x，算法终止；如果xa[n/2]，则只要在数组a的右半部分继续搜索x。 由于二分查找的数组不一定是一个整数数组，所以我采用了c++中的模板函数，将排序函数sort和二分查找函数binarysort写为了模板函数，这样不尽可以查找整数数组，也可以查找小数数组。 由于查找的数组的长度不固定，所以我用了c语言中的malloc和realloc函数，首先定义一个数组指针，用malloc 函数该它分配空间，然后向数组中存数，当数组空间满时，在用realloc函数为数组再次分配空间。由于在随机输入一组数时不知在什么位置停止，所以 篇二：二分搜索实验报告

数据结构二叉树实验报告

实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或VC++的微机。 三、实验内容 1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求 2．二叉树采用动态数组 3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点 五、程序代码 #include #include #include #define OK 1 #define ERROR 0 typedef struct TNode//结构体定义 {

int data; //数据域 struct TNode *lchild,*rchild; // 指针域包括左右孩子指针 }TNode,*Tree; void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值 { int a; scanf("%d",&a); if(a==00) // 结点的值为空 *T=NULL; else // 结点的值不为空 { *T=(Tree)malloc(sizeof(TNode)); if(!T) { printf("分配空间失败！！TAT"); exit(ERROR); } (*T)->data=a; CreateT(&((*T)->lchild)); // 递归调用函数，构造左子树 CreateT(&((*T)->rchild)); // 递归调用函数，构造右子树 } } void InitT(Tree *T)//构建空二叉树 { T=NULL; } void DestroyT(Tree *T)//销毁二叉树 { if(*T) // 二叉树非空 { DestroyT(&((*T)->lchild)); // 递归调用函数，销毁左子树 DestroyT(&((*T)->rchild)); // 递归调用函数，销毁右子树 free(T); T=NULL; } } void visit(int e)//访问结点 { printf("%d ",e); }

数据结构顺序表的查找插入与删除

一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include #include /*顺序表的定义：*/ #include #define ListSize 100 /*表空间大小可根据实际需要而定，这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; void main() { SeqList L; int i,x; int n=10; /*欲建立的顺序表长度*/ L.length=0; void CreateList(SeqList *L,int n); void PrintList(SeqList L,int n); int LocateList(SeqList L,DataType x); void InsertList(SeqList *L,DataType x,int i); void DeleteList(SeqList *L,int i); CreateList(&L,n); /*建立顺序表*/ PrintList(L,n); /*打印顺序表*/ printf("输入要查找的值："); scanf("%d",&x); i=LocateList(L,x); /*顺序表查找*/ printf("输入要插入的位置："); scanf("%d",&i); printf("输入要插入的元素："); scanf("%d",&x); InsertList(&L,x,i); /*顺序表插入*/

(完整word版)查找、排序的应用 实验报告

实验七查找、排序的应用 一、实验目的 1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] 对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算； 2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）； 3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。 [测试数据] 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握哈希表的定义，哈希函数的构造方法。 2、掌握一些常用的查找方法。 1、掌握几种常用的排序方法。 2、掌握直接排序方法。

四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 五、算法设计 a、折半查找 设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较， 若key==r[mid].key，查找成功 若keyr[mid].key，则low=mid+1 重复上述操作，直至low>high时，查找失败 b、顺序查找 从表的一端开始逐个进行记录的关键字和给定值的比较。在这里从表尾开始并把下标为0的作为哨兵。 void chaxun(SqList &ST) //查询信息 { cout<<"\n************************"<=1;j--) if(ST.r[j].xuehao

数据结构实现顺序表的各种基本运算(20210215233821)

实现顺序表的各种基本运算 一、实验目的 了解顺序表的结构特点及有关概念，掌握顺序表的各种基本操作算法思想及其实现。 二、实验内容 编写一个程序，实现顺序表的各种基本运算： 1、初始化顺序表； 2 、顺序表的插入； 3、顺序表的输出； 4 、求顺序表的长度 5 、判断顺序表是否为空； 6 、输出顺序表的第i位置的个元素； 7 、在顺序表中查找一个给定元素在表中的位置； 8、顺序表的删除； 9 、释放顺序表 三、算法思想与算法描述简图

主函数main

四、实验步骤与算法实现 #in clude #in clude #defi ne MaxSize 50 typedef char ElemType; typedef struct {ElemType data[MaxSize]; in t le ngth; void In itList(SqList*&L)〃 初始化顺序表 L {L=(SqList*)malloc(sizeof(SqList)); L->le ngth=0; for(i=0;ile ngth;i++) prin tf("%c ",L->data[i]); } void DestroyList(SqList*&L)〃 {free(L); } int ListEmpty(SqList*L)〃 {retur n( L->le ngth==O); } int Listle ngth(SqList*L)〃 {return(L->le ngth); } void DispList(SqList*L)〃 {int i; 释放顺序表 L

数据结构实验报告-二叉树的实现与遍历

《数据结构》第六次实验报告 学生姓名 学生班级 学生学号 指导老师

一、实验内容 1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。 2) 输出树的深度，最大元，最小元。 二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。 递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法： 首先介绍先序遍历： 先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。 再次介绍中序遍历： 中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。 最后介绍后序遍历： 后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。 三、详细设计 源代码：

数据结构实验2.1顺序表

附页（实验2-1代码）： 头文件“DEFINE2-1.h”： #define MaxSize 10 typedef struct { char data[MaxSize]; int length; }SqList; #include #include #include"DEFINE2-1.h" void InitList(SqList * &L) //初始化线性表 { L = (SqList*)malloc(sizeof(SqList)); //分配存放线性表的空间L->length = 0; //置空线性表长度为0 } bool ListInsert(SqList *&L, int i, char e) //插入数据元素 { int j; if (i<1 || i>L->length + 1) return false; //参数错误是返回false I--; //将顺序表逻辑序号转换为物理序号for (j = L->length; j>i; j--) //将data[i]及后面元素后移一个位置L->data[j] = L->data[j - 1]; L->data[i] = e; //插入元素e L->length++; //顺序表长度+1 return true; //成功插入返回true } void DispList(SqList *L) //输出线性表L { int i; for (i = 0; ilength; i++) //扫描顺序表输出各元素值printf("%3c", L->data[i]); printf("\n\n"); } int ListLength(SqList *L) //求线性表L的长度 { return (L->length); }

二分搜索实验报告

二分搜索 一．实验目的： 1.理解算法设计的基本步骤及各步的主要内容、基本要求； 2.加深对分治设计方法基本思想的理解，并利用其解决现实生活中的问题； 3.通过本次实验初步掌握将算法转化为计算机上机程序的方法。 二．实验内容： 1.编写实现算法：给定n个元素，在这n个元素中找到值为key的元素。 2.将输入的数据存储到指定的文本文件中，而输出数据存放到另一个文本文件中，包括结果和具体的运行时间。 3.对实验结果进行分析。 三．实验操作： 1.二分搜索的思想： 首先，假设表中的元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复上述过程，知道找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。 由于二分搜索是基于有序序列的一种搜索算法，故将输入的一组数据首先进行排序，考虑到输入数据可能有多个，采用快速排或者是合并排序，其中与冒泡做了对比。 冒泡排序算法： void sort(int List[],int length){ int change; for(int i=0;iList[j]){ change=List[i]; List[i]=List[j]; List[j]=change; } } } 快速排序算法： void Qsort(int List[],int low,int high){ if(low>=high) return; int first=low; int last=high; int key=List[first]; while(first=key) --last; List[first]=List[last]; while(first

数据结构实验-二叉树的操作

******************************* 实验题目：二叉树的操作 实验者信息：班级13007102，姓名庞文正，学号1300710226 实验完成的时间3:00 ****************************** 一、实验目的 1,掌握二叉树链表的结构和二叉树的建立过程。 2,掌握队列的先进先出的运算原则在解决实际问题中的应用。 3,进一步掌握指针变量、指针数组、动态变量的含义。 4,掌握递归程序设计的特点和编程方法。 二、实验内容 已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。（所谓层次遍历，是指从二叉树的根结点开始从上到下逐层遍历二叉树，在同一层次中从左到右依次访问各个节点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。 三、算法设计与编码 1.本实验用到的理论知识 总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，最好能加上自己的解释。 本算法要采用一个循环队列que，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。2.算法概要设计 给出实验的数据结构描述，程序模块、功能及调用关系 #include #include #define M 100 typedef struct node //二叉链表节点结构 {int data; //数据域 struct node *lchild,*rchild; //左孩子右孩子链 }bitree; bitree *que[M]; //定义一个指针数组，说明队列中的元素bitree 指针类型 int front=0, rear=0; //初始化循环列队 bitree *creat() //建立二叉树的递归算法 {bitree *t; int x; scanf("%d",&x); if(x==0) t=NULL; //以x=0 表示输入结束 else {t=malloc(sizeof(bitree)); //动态生成节点t，分别给节点t 的数据域，t->data=x; //左右孩子域赋值，给左右孩子赋值时用到 t->lchild=creat(); // 了递归思想 t->rchild=creat(); }

实验一数据结构顺序表的插入和删除

实验一顺序表的操作 1. 实验题目：顺序表的操作 2.实验目的和要求： 1)了解顺 序表的基本概念、顺序表结构的定义及在顺序表上的基本操作(插入、 删除、查找以及线性表合并 )。 2)通过在 Turbo C ( WinTc ，或 visual stdio6 )实现以上操作的 C 语言 代码。 3)提前了解实验相关的知识(尤其是 C 语 言)。 3.实验内容：(二选一) 1) 顺序表的插入算法, 删除算法, 顺序表的合并算法 2) 与线性表应用相关的实例( 自己选择具体实例) 4.部分参考实验代码： ⑴ 顺序表结构的定义： #include #define MAXLEN 255 typedef int ElemType; typedef struct { ElemType elem[MAXLEN]; int length; }sqList; ⑵ 顺序表前插(在第i 号元素前插入一个新的元素) int ListInsert(sqList *la,int i,int x) { int j; if(i<0||i>la-> length +1) { printf( “ n the value of i is wrong! ” ); return 0; } if(la-> length +1>=MAXLEN) { printf( “ n overflow! ” ); return 0; }

. for(j=la-> length;j>=i;j--) la->list[j+1]=la->list[j]; la->list[i]=x; la-> length ++; return 1; } ⑶ 顺序表删除 int ListDelete(sqList *la,int i) { if(i<0||i>la-> length ) { printf( “ return 0; n”); } for(i;i length;i++) la->list[i-1]=la->list[i]; la-> length --; return 1; } 5.附录：实验预备知识： ⑴ 复习 C 语言中数组的用法。 ⑵ 了解线性表和顺序表的概念，顺序表的定义方法； 线性表是n 个数据元素的有限序列，至于每个数据元素的具体含义，在不同的情况下各不相同。 顺序表是线性表的顺序存储表示，是用一组地址连续的存储单元依次存储线性表的数据元素。 在 C 语言中，顺序表是用数组来实现的。 ⑶ 掌握线性表在顺序存储结构上实现基本操作：查找、插入、删除和 合并的算法。 在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要要注意以下内容： 在实现查找的时候，首先要判断该顺序表是否为空，其次要判断查找后的结果（查到时输出查到的数据，未查到时给出未查到提 示）。 在实现插入的时候，首先要判断该顺序表是否为满，如为满则报错 （此时要注意：顺序表是用数组来实现的，它不能随机分配空 间）；如不为满，则需判断要插入的位置是否合法（例如：如果 一个线性表的元素只有10 个，而要在第0 个元素前插入或在第 11 个元素后插入就为不合法）。其次要注意是前插还是后插，两

数据结构实验报告之树与二叉树

学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件142 班 姓名：邹洁蒙 学号： 0143990

学生实验报告 （二） 一、实验综述 1、实验目的及要求 目的：1）掌握树与二叉树的基本概念； 2）掌握二叉树的顺序存储，二叉链表的先序遍历中序遍历和后序遍历算法； 3）掌握树的双亲表示法。 要求：1）编程：二叉树的顺序存储实现； 2）编程：二叉链表的先序遍历中序遍历和后序遍历实现； 3）编程：树的双亲表示法实现。 2、实验仪器、设备或软件 设备：PC 软件：VC6 二、实验过程(编程，调试，运行；请写上源码，要求要有注释) 1.编程：二叉树的顺序存储实现 代码： BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 }

运行截图： 2.编程：二叉链表的先序遍历中序遍历和后序遍历实现代码： void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图：

顺序表的应用数据结构实验报告记录

顺序表的应用数据结构实验报告记录

————————————————————————————————作者：————————————————————————————————日期：

大学数据结构实验报告 课程名称数据结构实验第（三）次实验实验名称顺序表的应用 学生姓名于歌专业班级学号 实验成绩指导老师（签名）日期2018年9月30日一、实验目的 1．学会定义线性表的顺序存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。 2．掌握顺序表的基本操作，实现顺序表的插入、删除、查找以及求并集等运算。 3．掌握对多函数程序的输入、编辑、调试和运行过程。 二、实验要求 1．预习C语言中结构体的定义与基本操作方法。 2．对顺序表的每个基本操作用单独的函数实现。 3．编写完整程序完成下面的实验内容并上机运行。 4．整理并上交实验报告。 三、实验内容： 1．定义一个包含学生信息（学号，姓名，成绩）的顺序表，使其具有如下功能： （1）根据指定学生个数，逐个输入学生信息 （2）逐个显示学生表中所有学生的相关信息 （3）根据姓名进行查找，返回此学生的学号和成绩 （4）根据指定的位置可返回相应的学生信息（学号，姓名，成绩） （5）给定一个学生信息，插入到表中指定的位置 （6）删除指定位置的学生记录 （7）统计表中学生个数 四、实验设计 1．定义一个包含学生信息（学号，姓名，成绩）的顺序表，使其具有如下功能： （1）根据指定学生个数，逐个输入学生信息 for(count=0; count

数据结构顺序表(电话通讯录)

数据结构用顺序表实现的电话通讯录（C语言） #include #include #include #include #define FALSE 0 #define ERROR 0 #define OK 1 #define INFEASIBLE -1 #define LIST_INIT_SIZE 10 #define LIST_INCREMENT 5 #define N 5 typedefint Status; typedefstruct { char name[10]; //姓名 char num[15]; //号码 }student; typedefstruct { student *elem; //存储空间基址 int length; //当前长度 intlistsize; //当前分配的存储空间(以sizeof(student)为单位) }Sqlist; Sqlist L; //定义全局变量L 为Sqllist类型 Status ListInsert(Sqlist&L,inti,student e) { //插入学生信息到顺序表L中 int j; student *newbase; if(i<1||i>L.length+1) return ERROR; //i值不合法 if(L.length>=L.listsize) //当前存储空间已满，增加分配 { newbase=(student *)realloc(L.elem,(LIST_INIT_SIZE+LIST_INCREMENT)*(sizeof(student))); if(!newbase) //存储分配失败 exit(OVERFLOW); L.elem=newbase; //新基址 L.listsize+=LIST_INCREMENT; //增加存储容量 } for(j=L.length;j>=i;j--) L.elem[j]=L.elem[j-1]; //插入位置及之后元素的右移 L.elem[i-1]=e; L.length++; return OK;

数据结构实验报告(三)：实现深度优先搜索与广度优先搜索算法

佛山科学技术学院 实验报告 课程名称数据结构 实验项目实现深度优先搜索与广度优先搜索算法 专业班级 10网络工程2 姓名张珂卿学号 2010394212 指导教师成绩日期 2011年11月16日 一、实验目的 1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历； 2、掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。 二、实验内容 1、建立图的存储方式； 2、图的深度优先搜索算法； 3、图的广度优先搜索算法。 三、实验原理 图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜索与广度优先搜索算法可以进行图的遍历； 深度优先遍历是树的先根遍历的推广，是将某一条枝上的所有节点都搜索到了之后，才转向搜索另一条枝上的所有节点； 广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索。 四、实验步骤 1．建立图的存储结构； 2．输入图的基本接点与信息，初始化图； 3．编写图的深度优先搜索（DFS）和广度优先搜索算法（BFS）程序； 4.采用菜单形式进行显示与选择。 5.测试数据和结果显示 （1）从键盘输入顶点数和边数； （2）输入顶点信息； （3）输入边的信息，以（a,b）的形式输入边的信息，构建一个无向图； （4）对此无向图进行深度优先搜索和广度优先搜索，并输出正确的序列。 五、程序源代码及注释 /******************************* *采用邻接表的存储结构 *构建无向图 *图的创建过程中暂不支持重复验证，

因此不能对一条边进行重复定义 ******************************/ #include #include #include #define MAX_VERTEX_NUM 20 typedef struct ArcNode{ int adjvex; struct ArcNode* nextarc; //InfoType* info; }ArcNode; /********************************* *链表结点的结构用于创建栈或是队列 ********************************/ typedef struct LinkNode{ ArcNode* parc; //存储指针地址 struct LinkNode* next; //指向一下个结点 }LinkNode; typedef struct VNode{ char cData; //顶点元素值 ArcNode* firstarc; //指向第一条依附于该点的边}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum; //图的当前顶点数和弧数 int arcnum; }ALGraph; int Visited[MAX_VERTEX_NUM]; /********************************* *将生成的图打印出来以便确认正确性 ********************************/ int PrintCheck(ALGraph* pag) { int i; ArcNode* p;

数据结构实验报告—二叉树

算法与数据结构》课程实验报告

一、实验目的 1、实现二叉树的存储结构 2、熟悉二叉树基本术语的含义 3、掌握二叉树相关操作的具体实现方法 二、实验内容及要求 1. 建立二叉树 2. 计算结点所在的层次 3. 统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 （1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 （2）功能方面：能够实现二叉树的一些基本操作，主要包括： 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 （1）设计的主要思路 二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。 （2）数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉

数据结构实验一顺序表的实现

数据结构实验一顺序表的实现 班级学号分数 一、实验目的： 1.熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现； 2.以线性表的各种操作的实现为重点； 3.通过本次学习帮助学生加深C语言的使用，掌握算法分析方法并对已经设计 出的算法进行分析，给出相应的结果。 二、实验要求： 编写实验程序，上机运行本程序，保存程序的运行结果，结合程序进行分析并写出实验报告。 三、实验容及分析： 1.顺序表的建立 建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 程序如下： 头文件SqList.h的容如下： #include #include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int ElemType; typedef int Status; typedef struct{ ElemType *elem; int length; int listsize; }SqList; Status InitList_Sq(SqList *L) { L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!L->elem) return(OVERFLOW); L->length=0; L->listsize=LIST_INIT_SIZE; return OK; } Status CreatList_Sq(SqList *L,int n) { int i; printf("输入%d个整数:\n",n); for(i=0;ielem[i]); return OK; } //以下是整个源程序： #include #include"SqList.h" int main() { int i,n; SqList a; SqList *l = &a; if(InitList_Sq(l)==-2) printf("分配失败"); printf("\n输入要建立的线性表l的长度n:");//输入线性表得长度scanf("%d",&n); l->length=n; printf("线性表的长度是:%d\n",l->length); CreatList_Sq(l,n);//生成线性表 printf("输出线性表l中的元素值：");//输出线性表中的元素 for(i=0;ilength;i++) printf("%7d",l->elem[i]); getchar(); } 程序的运行结果：

(new)《数据结构与算法》上机实验要求

《数据结构与算法》课程实验内容与要求 一、 课程简介 本课程着重讲述①线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应的基本算法。②各种查找算法③典型内部排序算法。 二、 实验的作用、地位和目的 数据结构是一门技术基础课，通过实验深刻理解各种逻辑结构、存储结构的特性，培养为实际问题分析其数据对象、基本操作，选择逻辑结构、存储结构灵活应用基本算法，设计出具有专业水准的应用程序的能力。 三、 实验方式与要求 ①首先要求学生在课下完成问题分析、算法设计，基本完成程序设计。 ②实验时，每位学生使用一台微机，独立调试，完成程序。 ③程序调试好后，由指导教师检测运行结果，并要求学生回答相关的问题。教师评出检查成绩。 ④学生记录程序的输入数据，运行结果及源程序。 ⑤在一周内完成实验报告。 四、 考核方式与实验报告要求 实验成绩由指导教师根据学生的实验完成情况、源程序质量、回答问题情况、实验报告质量、实验纪律等方面给分。 学生在实验后的一周内提交实验报告。实验报告按照附件中实验报告模版书写。实验报告中应包括如下内容： 实验内容按任课教师下达的实验任务填写（具体实验题目和要求）； 实验过程与实验结果应包括如下主要内容： 数据结构定义 算法设计思路简介 算法描述：可以用自然语言、伪代码或流程图等方式 算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等 算法时间复杂度分析 源程序清单与实验结果或其它说明可打印，并装订在实验报告之后。 实验报告雷同者，本次实验成绩为0分或雷同实验报告平分得分

五、 实验的软硬件环境 硬件环境：PⅡ以上微型计算机 软件环境：Windows98/2000, VC++6.0或turbo C 六、 实验内容安排 实验一线性表应用 实验时间：2017年3月9日1-2节（地点：7-219），3月10日5-6节（地点：7-215） 实验目的： 理解线性表的逻辑特点；掌握顺序表、链表存储结构，以及线性表的基本操作，如插入、删除、查找，以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法，并能够在实际问题背景下的灵活运用线性表来解决问题，实现相应算法。 每位同学可从下面题目中选择至少2题实现：其中第一题为必做题 1．一元稀疏多项式简单的计算器 1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器 2）要求: （1）采用单链表存储结构一元稀疏多项式 （2）输入并建立多项式 （3）输出多项式 （4）实现多项式加、减运算 3）分析算法时间复杂度 2. 约瑟夫环问题 1）问题描述：有编号为1, 2…n 的n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。 2）要求: 采用顺序和链式两种存储结构实现 3）分析算法时间复杂度 3．单链表基本操作练习 1）问题描述：在主程序中提供下列菜单： 1…建立链表 2…连接链表 3…输出链表 0…结束 2）实验要求：算法中包含下列过程，分别完成相应的功能： CreateLinklist(): 从键盘输入数据，创建单链表 ContLinklist()：将前面建立的两个单链表首尾相连 OutputLinklist()：输出显示单链表 3）分析算法时间复杂度