数据结构实验
【实验内容】
约瑟夫问题的实现：n只猴子要选猴王，所有的猴子按1,2，…，n编号围坐一圈，从第一号开始按1,2…，m报数，凡报到m号的猴子退出圈外，如此次循环报数，知道圈内剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。【实验要求】
1、要求用顺序表和链表分别实现约瑟夫问题。
2、独立完成，严禁抄袭。
3、上的实验报告有如下部分组成：
①实验名称
②实验目的
③实验内容：问题描述：数据描述：算法描述：程序清单：测试数据
算法：
#include
#include
typedef struct LPeople
{
int num;
struct LPeople *next;
}peo;
void Joseph(int n,int m) //用循环链表实现
{
int i,j;
peo *p,*q,*head;
head=p=q=(peo *)malloc(sizeof(peo));
p->num=0;p->next=head;
for(i=1;i { p=(peo *)malloc(sizeof(peo)); p->num=i;q->next=p;p->next=head; } q=p;p=p->next; i=0;j=1; while(i { if(j%m==0) { q->next=p->next; p=q->next; printf("%4d",j%n); i++; } else { q=p;p=p->next; } j++; } printf("\n"); } void main() { int n,m; /*人的个数*/ printf("Please Enter n amd m(n>m):\n"); scanf("%d%d",&n,&m); Joseph(n,m); } 【实验内容】（问题描述，数据描述，算法描述，程序清单，测试数据）二叉树采用二叉链表作存储结构，用编程实现二叉树的如下基本操作：1．按先序序列构造一棵二叉链表表示的二叉树T； 2．对这棵二叉树进行中序遍历，输出结点的遍历序列； 3．给定的顶点和边的信息构造图的邻接矩阵存储； 4．对改图进行深度优先搜索，输出搜索得到的结点序列。 【实验要求】 上交实验报告，要求同上。 关于树： #include #include "BiTree.h" using namespace std; BiTree BITREE::CreateBiTree() { BiTree bt; char x; x = getchar(); if(x == '#' ) { bt = NULL; } else { bt = new BiTNode; bt->data = x; bt->lchild = this->CreateBiTree(); bt->rchild = this->CreateBiTree(); this->T = bt; return bt; }; void BITREE::InOrderTraverse(BiTree bt) { if(bt != NULL) { if(bt->lchild != NULL) { this->InOrderTraverse(bt->lchild); } cout< if(bt->rchild != NULL) { this->InOrderTraverse(bt->rchild); } } else { return; } //-+a##*b##-c##d##/e##f## }; void BITREE::Destory(BiTree bt) { if(bt != NULL) { if(bt->lchild != NULL) { this->Destory(bt->lchild); } if(bt->rchild != NULL) { this->Destory(bt->rchild); } cout< delete bt; } else { return; } 关于图： #include "MGraph.h" void main() { MGRAPH G; G.CreateUDN(); cout< <<"------邻接矩阵------" < G.DisplayMatrix(); cout< G.Depth_FirstSearch(); cout< } 【实验内容】 1、要求将二叉排序树的建立、插入、删除、显示等算法合并在一个综合程序中，用户 可通过菜单选择方式运行各种操作算法。 2、一直哈希表的表长为m，哈希函数为H(key)=key MOD p，用开放定址法（增量序 列采用线性探测再散列）解决冲突，试编写构造哈希表的程序。 二叉排排序树： #include #include #define TRUE 1 #define FALSE 0 typedef int DataType; typedef int KeyType; struct BinTreeNode; typedef struct BinTreeNode * PBinTreeNode; struct BinTreeNode { KeyType key; DataType other; /*元素的属性*/ PBinTreeNode llink,rlink; }; typedef struct BinTreeNode * BinTree; typedef BinTree * PBinTree; int searchNode(PBinTree ptree,KeyType key,PBinTreeNode *position) { PBinTreeNode p,q; p=*ptree;q=p; while(p!=NULL) { q=p; if(p->key==key) { *position=p; return(TRUE); }else if(p->key>key)p=p->llink; else p=p->rlink; } *position=q; return(FALSE); } void insertNode(PBinTree ptree,KeyType key) { PBinTreeNode p,position; if(searchNode(ptree,key,&position)==TRUE) return; p=(PBinTreeNode)malloc(sizeof(struct BinTreeNode)); if(p==NULL){printf("Error!\n");exit(1);} p->key=key; p->llink=p->rlink=NULL; if(position==NULL) *ptree=p; else if(key position->llink=p; else position->rlink=p; } void midOrder(PBinTreeNode ptree) { PBinTreeNode p; p=ptree; if(p==NULL)return; midOrder(p->llink); printf(" %d ",p->key); midOrder(p->rlink); } void preOrder(PBinTreeNode ptree) { PBinTreeNode p; if(p==NULL)return; printf(" %d ",p->key); preOrder(p->llink); preOrder(p->rlink); } void postOrder(PBinTreeNode ptree) { PBinTreeNode p; p=ptree; if(p==NULL)return; postOrder(p->llink); postOrder(p->rlink); printf(" %d ",p->key); } void deleteTree(PBinTreeNode pbtree) { PBinTreeNode p=pbtree; if(p==NULL)return; deleteTree(pbtree->llink); deleteTree(pbtree->rlink); free(p); } void deleteNode(PBinTree pbtree,KeyType key) { PBinTreeNode position,p,q,parent; p=*pbtree,parent=p; int tag=0; position=NULL; while(p!=NULL){ // printf("%d",p->key); if(p->key==key){ position=p; break; }else if(p->key>key){ parent=p; p=p->llink; tag=-1; }else { parent=p; p=p->rlink; } } position=p; if(position == NULL){ printf("\n不含有此关键字！\n"); return; }else if(position==*pbtree){ printf("\n是根节点！"); tag=0; } else printf("\n它的父节点是%d",parent->key); if(position->llink==NULL){ if(tag==-1)parent->llink=position->rlink; if(tag==1)parent->rlink=position->rlink; free(position); }else{ PBinTreeNode trchild=position->llink; while(trchild->rlink!=NULL){ trchild=trchild->rlink; } trchild->rlink=position->rlink; if(tag==-1)parent->llink=position->llink; if(tag==1)parent->rlink=position->llink; if(tag==0)*pbtree=position->llink; free(position); } } int main() { PBinTree newBTree; insertNode(newBTree,5); insertNode(newBTree,3); insertNode(newBTree,7); insertNode(newBTree,2); insertNode(newBTree,4); insertNode(newBTree,6); insertNode(newBTree,8); insertNode(newBTree,1); printf("---------midOrder-----"); midOrder(*newBTree); printf("\n---------preOrder-----"); preOrder(*newBTree); deleteNode(newBTree,5); printf("\n---------midOrder-----"); midOrder(*newBTree); printf("\n---------preOrder-----"); preOrder(*newBTree); printf("\n"); deleteTree(*newBTree); } 哈希表： #include #include #define NULL 0 typedef char * InfoType; typedef int KeyType; typedef struct node { KeyType key; InfoType data; struct node *next; }SNode; typedef struct hnode { struct node *next; }HNode; //插入指定关键字 void InsertHT2(HNode *ha[],KeyType k,int p) { int adr; HNode *q; SNode *s,*t; adr=k%p; s=(SNode *)malloc(sizeof(SNode)); s->key=k; s->next=NULL; q=ha[adr]; t=q->next; if(t==NULL) q->next=s; else {while(t->next!=NULL) t=t->next; t->next=s; } } //建立哈希表 void CreatHT2(HNode *ha[],KeyType x[],int n,int p) { int i=0; for(i=0;i { ha[i]=(HNode *)malloc(sizeof(HNode)); ha[i]->next=NULL; } for(i=0;i InsertHT2(ha,x[i],p); } //输出哈希表 void DispHT2(HNode *ha[],int p) { SNode *q; int i; for 9i=0;i { printf ("%3d:",i); q=ha[i]->next; while(q!=NULL) { printf("->%3d",q->key); q=q->next; } printf("->^\n"); } } 【实验内容】 有如下数据： 成绩：75 87 68 92 88 61 77 96 80 72 姓名王华李英张萍陈涛刘丽章强孙军朱彬徐伟曾亚 以成绩做关键字，试编写程序实现如下基本操作： 1、用冒泡排序对上面数据按成绩非递减排列，并分析时空复杂度。 2、用快速排序对上面数据按成绩非递减排列，并分析时空复杂度。 3、用二路归并排序树对上面数据成绩按成绩非递减排列，并分析时空复杂度。算法： #include #include "BiTree.h" using namespace std; BiTree BITREE::CreateBiTree() { BiTree bt; char x; x = getchar(); if(x == '#' ) { bt = NULL; } else { bt = new BiTNode; bt->data = x; bt->lchild = this->CreateBiTree(); bt->rchild = this->CreateBiTree(); } this->T = bt; return bt; }; void BITREE::InOrderTraverse(BiTree bt) { if(bt != NULL) { if(bt->lchild != NULL) { this->InOrderTraverse(bt->lchild); } cout<<"("< if(bt->rchild != NULL) { this->InOrderTraverse(bt->rchild); } } else { return; } //-+a##*b##-c##d##/e##f## }; void BITREE::Destory(BiTree bt) { if(bt != NULL) { if(bt->lchild != NULL) { this->Destory(bt->lchild); } if(bt->rchild != NULL) { this->Destory(bt->rchild); } cout< delete bt; } else { return; } } 上机实验要求及规范 《数据结构》课程具有比较强的理论性，同时也具有较强的可应用性和实践性，因此上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性，但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程，而是应该按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体步骤如下： 1.问题分析与系统结构设计 充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？），然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。 2.详细设计和编码 详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。 编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。 3.上机准备 熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。 4.上机调试程序 调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。 5.整理实验报告 在上机实验开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析，写出实验报告。 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法； 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找； 2.建立二叉排序树并对该树进行查找； 3.确定hash函数及冲突处理方法，建立一个hash表并实现查找。 程序代码 #include cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 长春大学计算机学院网络工程专业 数据结构实验报告 实验名称：实验二栈和队列的操作与应用 班级：网络14406 姓名：李奎学号：041440624 实验地点：日期： 一、实验目的： 1．熟练掌握栈和队列的特点。 2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。 3．掌握链队的入队和出队等基本操作。 4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境： 注：将完成的实验报告重命名为：班级+学号+姓名+（实验二），（如：041340538张三（实验二）），发邮件到：ccujsjzl@https://www.sodocs.net/doc/df10916247.html,。提交时限：本次实验后24小时之内。 阅读程序，完成填空，并上机运行调试。 1、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作（存储结构由SqStackDef.h 定义） Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数，即栈的长度, 编写此函数 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 班级：：学号： 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息（学号，，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; 数据结构实验报告(2015级)及答案 《数据结构》实验报告 专业__信息管理学院______ 年级__2015级___________ 学号___ _______ 学生姓名___ _ _______ 指导老师____________ 华中师范大学信息管理系编 I 实验要求 1．每次实验中有若干习题，每个学生至少应该完成其中的两道习题。 2．上机之前应作好充分的准备工作，预先编好程序，经过人工检查无误后，才能上机，以提高上机效率。 3．独立上机输入和调试自己所编的程序，切忌抄袭、拷贝他人程序。 4．上机结束后，应整理出实验报告。书写实验报告时，重点放在调试过程和小节部分，总结出本次实验中的得与失，以达到巩固课堂学习、提高动手能力的目的。 II 实验内容 实验一线性表 【实验目的】 1．熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2．通过编程、上机调试，进一步理解线性表的基本概念,熟练运用C语言实现线性表基本操作。 3．熟练掌握线性表的综合应用问题。 【实验内容】 1．一个线性表有n个元素（n 的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现；比较两种方法的优劣。 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；} ∥ 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 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）迷宫存储迷宫，寻路径，输出迷宫。 《数据结构》实验报告 实验序号：1 实验项目名称：概论 附源程序清单： 1. #include 2. #include 实验报告（一） 一、实验目的： 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。 程序代码如下： 附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的, 无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图； 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的xx优先搜索 3.图的xx优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "stdio.h" #include "stdlib.h" #define MAXSIZE 30 typedefstruct{charvertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZE intedges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵 }MGraph;//MGraph为采用邻近矩阵存储的图类型 voidCreatMGraph(MGraph *g,inte,int n) {//建立无向图的邻近矩阵g->egdes，n为顶点个数，e为边数inti,j,k; printf("Input data of vertexs(0~n-1): \n"); for(i=0;i 华北水利水电大学数据结构实验报告 2017～2018学年第二学期2017级计算机科学与技术（专升本）专业班级：学号：姓名： 实验一线性表及其应用 一、实验目的： 1．掌握用C/C++语言调试程序的基本方法。 2．掌握线性表的基本运算，如插入、删除等。 二、实验内容： 1．编写一个程序，实现顺序表的各种基本运算，在此基础上完成如下功能： （1）初始化顺序表L。 （2）依次在顺序表L中插入元素a、b、c、e。 （3）输出顺序表L。 （4）输出顺序表L的长度。 （5）输出顺序表L的第3个元素。 （6）输出元素a的位置。 （7）在第4个元素之前插入元素f。 （8）输出顺序表L。 （9）删除第3个元素。 （10）输出顺序表L。 2．编写一个程序，实现以下功能，L1=（x1，x2，…，x n），L2=(y1，y2，…，y m)，它们是两个线性表（L1和L2中的值都不重复），采用带头结点的单链表存储，设计一个算法合并L1和L2，结果存放在线性表L3中，要求如下： L3=(x1，y1，x2，y2，…，x m，y m，x m+1，…，x n) 当m n时 L3=(x1，y1，x2，y2，…，x n，y n，y n+1，…，y m) 当m>n时 L3仍采用单链表存储，算法的空间复杂度为O（1）。 （1）建立两个单链表L1和L2并输出。 （2）将合并L1和L2为L3。 （3）输出单链表L3。 三、实验要求： 1．完成程序设计并上机调试通过。 2．撰写实验报告，提供实验结果和数据。 3．写出算法设计小结和心得。 四、程序源代码： 五、程序运行情况（采用截图方式给出运行结果） 六、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等） 注：内容一律使用宋体五号字，单倍行间距 天津科技大学 2015—2016学年第2学期数据结构实验任务书 课程名称：数据结构实验学时： 2 实验题目：线性表的基本操作 实验环境： Visual C++ 实验目的： 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 实验内容： 定义一个包含学生信息（学号，姓名，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据姓名进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 实验提示： 学生信息的定义： typedef struct { char no[8]; //8位学号 char name[20]; //姓名 int score; //成绩 }Student; 顺序表的定义 typedef struct { Student *elem; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList； 链表的定义： typedef struct LNode{ Student data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; 实验要求： (1) 程序要添加适当的注释，程序的书写要采用缩进格式。 (2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。 (3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。 (4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。 (5) 以班为单位实验周周五上传源程序和实验报告。顺序表的源程序保存为SqList.cpp，链表的源程序保存为LinkList.cpp，实验报告命名为：实验报告1.doc。源程序和实验报告压缩为一个文件（如果定义了头文件则一起压缩），按以下方式命名：学号姓名.rar，如07081211薛力.rar。 精品文档数据结构 实 验 报 告 目的要求 １．掌握图的存储思想及其存储实现。 ２．掌握图的深度、广度优先遍历算法思想及其程序实现。 ３．掌握图的常见应用算法的思想及其程序实现。 实验内容 １．键盘输入数据，建立一个有向图的邻接表。 ２．输出该邻接表。 3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接表存储实现无向图的深度优先递归遍历。 6．采用邻接表存储实现无向图的广度优先遍历。 7．在主函数中设计一个简单的菜单，分别调试上述算法。 源程序： 主程序的头文件：队列 #include 班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include { char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; } Status GetElem(LinkList L,int i,ElemType &e) // 访问链表,找到i位置的数据域,返回给 e { LinkList p; p=L->next; 课程编号：B080109010 数据结构课程设计 总结报告 东北大学软件学院 第一章需求分析 1.1建立主程序应用菜单选项 主程序应用菜单选项包含所实现的所有功能，并且对选项采用数字标识进行选择，对其他错误输入可以进行判别，提示输入错误。 1.2导游线路图的创建级景区分布图的输出 用邻接链表存储景点分布图的信息，（带权无向）图的邻接链表。输出景区景点分布图（邻接矩阵）。图中边的权值∞用32767表示。 1.3输出导游线路图 景区旅游信息管理系统中制订旅游景点导游线路策略，首先通过遍历景点，给出一个入口景点，建立一个导游线路图，导游线路图用有向图表示。 1.4输出导游线路图中是否有回路 景区旅游信息管理系统中，创建好导游路线图后，判断该图中是否存在回路。 1.5查找及排序 ●查找功能：可以根据用户输入的关键字进行景点的查找，关键字可以在景点名称也 可以在景点介绍中。查找成功则返回景点的相关简介，如果查找不成功请给予正确 提示。 ●排序功能：按景点欢迎度，景点的岔路数对景点进行排序并打印出来排序顺序。 1.6输出两个景点之间最短路径和最短距离 求出两个景点间的最短路径和最短距离，并且输出道路修建规划图。算法采用迪杰斯特拉算法。 1.7输出道路修建规划图 道路建设首先要保证能连通所有景点，但又要花最小的代价。 1.8输出车辆的进出信息 1.8.1具体需求： 停车场是一个可以停放n辆汽车，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次排列，若车场内已停满n辆车，后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按计10--数据结构专题实验rev2
数据结构实验十一：图实验
数据结构实验
数据结构实验报告图实验
数据结构实验报告
数据结构实验
数据结构实验报告图实验
数据结构实验一 实验报告
数据结构实验报告(2015级)及答案
数据结构实验
数据结构集中上机实验报告
数据结构实验1
《数据结构》2012级实验报告模板..
数据结构实验报告(图)
数据结构图实验报告
《数据结构》实验一
数据结构实验1
数据结构实验—图实验报告
数据结构实验一 实验报告
东北大学数据结构实践实验报告