数据结构实验报告
实验名称:实验一线性表——题目1
学生姓名:申宇飞
班级:信通3班
班内序号: 03
学号: 2012210064
日期: 2013年11月4日
1.实验要求
实验目的:
熟练掌握线性表的基本操作,包括:创建、插入、删除、查找、输出、求长度、合并等运算,以及各类操作在顺序存储结构和链式存储结构上的实现。
实验内容:
根据线性表的抽象数据类型的定义,选择下面任一种链式结构实现线性表,并完成线性表的基本功能。
线性表存储结构(五选一):
1、带头结点的单链表
2、不带头结点的单链表
3、循环链表
4、双链表
5、静态链表
线性表的基本功能:
1、构造:使用头插法、尾插法两种方法
2、插入:要求建立的链表按照关键字从小到大有序
3、删除
4、查找
5、获取链表长度
6、销毁
7、其他:可自行定义
编写测试main()函数测试线性表的正确性。
2.程序分析
2.1 存储结构
链表的具体存储表示为:
① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的)
② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址信息(称为指针)
链表的结点结构
┌──┬──┐
│data│next│
└──┴──┘
data 域--存放结点值的数据域
next 域--存放结点的直接后继的地址(位置)的指针域(链域)
地址 内存单元
1000H
头指针 1020H 1080H 10C0H
2.2 关键算法分析
1、关键算法:
1:头插法
自然语言描述:
a:在堆中建立新结点
b:将a[i]写入到新结点的数据域
c:修改新结点的指针域
d:修改头结点的指针域。将新结点加入链表中
伪代码描述
a:Node
b:s->data=a[i]
c:s->next=front->next;
d:front->next=s
2:尾插法
自然语言描述:
a:在堆中建立新结点:
b:将a[i]写入到新结点的数据域:
c:将新结点加入到链表中
d:修改修改尾指针
伪代码描述
a:Node
b:s->data=a[i]
c:r->next=s;
d:r=s
3:析构/删除函数
自然语言描述:
a:新建立一个指针,指向头结点
b:判断要释放的结点是否存在,
c:暂时保存要释放的结点
d:移动a中建立的指针
e:释放要释放的指针
伪代码描述
a:Node
b:while(p)
c:front=p
d:p=p->next
e:delete front
4:按位查找函数
自然语言描述:
a:初始化工作指针p和计数器j,p指向第一个结点,j=1
b:循环以下操作,直到p为空或者j等于1
b1:p指向下一个结点
b2:j加1
c:若p为空,说明第i个元素不存在,抛出异常
d:否则,说明p指向的元素就是所查找的元素,返回元素地址
伪代码描述
a:Node
b:while(p&&j!=1)
b1:p=p->next
b2:j++
c:if(!p) throw ”error”
d:return p
5:按位查找函数
自然语言描述:
a:初始化工作指针p和计数器j,p指向第一个结点,j=1
b:循环以下操作,找到这个元素或者p指向最后一个结点 b1:判断p 指向的结点是不是要查找的值,如果是,返回j,否则p指向下一个结点,并且j 的值加一
c:如果找到最后一个结点还没有找到要查找的元素,返回查找失败信息
伪代码描述
a:Node
b:while(p)
b1: if(p->next==x) return j
p=p->next
j++
c:return “error”
6:插入函数
自然语言描述:
a:在堆中建立新结点
b:将要插入的结点的数据写入到新结点的数据域
c:修改新结点的指针域
d:修改前一个指针的指针域,使其指向新插入的结点的位置
伪代码描述
a:Node
b:s-data=p->data
c:s->next=p->next
d:p->next=s
e:p->data=x
7:删除函数
自然语言描述:
a:从第一个结点开始,查找要删除的位数i前一个位置i-1的结点
b:设q指向第i个元素
c:将q元素从链表中删除
d:保存q元素的数据
e:释放q元素
伪代码描述
a:q=p->next
b:p->next=q->next
c:x=q->data
d:delete q
8:遍历打印函数
自然语言描述:
a:判断该链表是否为空链表,如果是,报错
b:如果不是空链表,新建立一个temp指针
c:将temp指针指向头结点
d:打印temp指针的data域
e:逐个往后移动temp指针,直到temp指针的指向的指针的next域为空伪代码描述
If front->next==NULL
Throw ”an empty list ”
Node
while(temp->next)
{ cout<
temp=temp->next;
}
9:获取链表长度函数
自然语言描述:
a:判断该链表是否为空链表,如果是,输出长度0
b:如果不是空链表,新建立一个temp指针,初始化整形数n为0
c:将temp指针指向头结点
d:判断temp指针指向的结点的next域是否为空,如果不是,n加一,否则return n e: 使temp指针逐个后移,重复d操作,直到temp指针指向的结点的next域为0,返回n 伪代码描述
int n=0
if ront->next==NULL
n=0;
else
{ Node
while(temp->next)
n++;
temp=temp->next;
}
return n;
2、代码详细分析:
(1)从第一个结点开始,查找节点,使它的数据比x大,设p指向该结点:
while (x>p->data) { p=p->next;}
(2)新建一个节点s,把p的数据赋给s:s->data=p->data;
(3)把s加到p后面:s->next=p->next; p->next=s;
(4)p节点的数据用x替换:p->data=x;
示意图如图所示
3、关键算法的时间复杂度:O(1)
3.程序运行结果
程序截图
1. 流程图:
2.测试条件:插入、删除元素的位置一定要在链表的长度范围之内。
3.测试结论:可以正确的对链表进行插入,删除,取长度,输出操作。且插入任意一个元素后,链表的顺序依然是由小到大。
4.总结
1.调试时出现的问题及解决的方法:
(1)刚开始时用NULL置空最后一个节点的指针域,发现调试时出现NULL未声明的情况。最后发现用0去置空最后一个节点的指针域,调试成功。
(2)刚开始遍历总是不能完全遍历链表。最后发现循环语句中两个句子顺序写反,更正顺序后,调试成功。
2.心得体会:
这道题是相对比较基础,目的是实现线性表的基本功能,书上也几乎给出了所有的模板类的定义,但是在自己进行编程时还是出了很多问题。通过这个实例,我对模板类的定义与使用有了个初步的了解,了解了单链表的基本的操作和函数实现。以后必须自己动手编,实现理论与实践相结合,提高自己的编程能力。
3.下一步的改进:
这个程序的交互性不强,可以改进的地方应该是可以从外部输入数组而不仅仅是编程者给定。此外,显示的界面不够友好,有待改善,而且可以增加完善的报错机制。此外,也希望老师
能在课上给出更多的优化指导。
代码
#include "iostream"
using namespace std;
template
struct Node
{
T data;
struct Node * next;
};
template
class LinkList
{
public:
LinkList() //无参构造
{
front = new Node
front->next = NULL;
}
LinkList(T a[], int n);//头插法
//LinkList(T a[],int n);//尾插法
void PrintList();//按次序遍历
int GetLength();//获取线性表的长度
Node
void Insert(int i, T x);//插入
T Delete(int i);//删除
~LinkList();//销毁
private:
Node
};
template
LinkList
{
front = new Node
front->next = NULL;
for(int i = n - 1; i >= 0; i--)
{
Node
s->data = a[i];//给新结点数据域赋值
s->next = front->next;//修改新结点的指针域
front->next = s;//修改头指针的指针域}
}/*
template
LinkList
{
front=new Node
Node
for(int i=0;i { Node s->data=a[i]; r->next=s; r=s; } r->next=NULL; }*/ template void LinkList { Node -p = p->next; while(p->next != NULL){ p = p->next; cout << p->data << endl; } } template int LinkList { Node int n = 0; while(p->next != NULL) { p = p->next; n++; } return n; } template Node { Node int j = 1; while(p&&j != i) { p = p->next; j++; } return p; } template void LinkList { Node if(i != 1) p = Get(i - 1); if(p) { Node s->data = x; s->next = p->next; p->next = s; } else throw "位置错误"; } template T LinkList { Node if(i != 1) { p = Get(i - 1); Node T x = s->data; p->next = s->next; return x; delete s; } else throw "位置错误"; } template LinkList { Node while(p) { p = p->next; delete front; front = p; } } int main() { const int n = 10; int a[n] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; LinkList //list.hLinkList(a,n); //list.rLinkList(a,n); cout << list.GetLength() << endl; cout << endl; list.PrintList(); cout << endl; list.Insert(1, 0); list.PrintList(); cout << list.Get(2) << endl; list.~LinkList(); return 0; } 数据结构实验报告全集 实验一线性表基本操作和简单程序 1.实验目的 (1)掌握使用Visual C++ 6.0上机调试程序的基本方法; (2)掌握线性表的基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2.实验要求 (1)认真阅读和掌握和本实验相关的教材内容。 (2)认真阅读和掌握本章相关内容的程序。 (3)上机运行程序。 (4)保存和打印出程序的运行结果,并结合程序进行分析。 (5)按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 实验代码: 1)头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表,由用户输入各结点data域之值,//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了常用的多种查找和排序技术,并做了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: (1)内容丰富,学习量大,给学习带来困难; (2)贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点; (3)所用到的技术多,而在此之前的各门课程中所介绍的专业性知识又不多,因而加大了学习难度; (4)隐含在各部分的技术和方法丰富,也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性,设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练,突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时,觉得无从下手,做起来特别费劲。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法,如算法设计的构思方法,动态链表,算法的编码,递归技术,与特定问题相关的技术等,要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上,掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时,要求完成以下六个题目: 实习一约瑟夫环问题(2学时) 北京邮电大学电信工程学院 数据结构实验报告 实验名称:实验1——线性表 学生姓名: 班级: 班内序号: 学号: 日期: 1.实验要求 1、实验目的:熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容: 题目1: 线性表的基本功能: 1、构造:使用头插法、尾插法两种方法 2、插入:要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他:可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现:在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现: Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现:a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #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 线性表的基本操作 一、需求分析 目的: 掌握线性表运算与存储概念,并对线性表进行基本操作。 1.初始化线性表; 2.向链表中特定位置插入数据; 3.删除链表中特定的数据; 4.查找链表中的容; 5.销毁单链表释放空间; 二、概要设计 ●基础题 主要函数: 初始化线性表InitList(List* L,int ms) 向顺序表指定位置插入元素InsertList(List* L,int item,int rc)删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2(List* L,int rc) 查找顺序表中的元素 FindList(List L,int item) 输出顺序表元素OutputList(List L) 实验步骤: 1,初始化顺序表 2,调用插入函数 3,在顺序表中查找指定的元素 4,在顺序表中删除指定的元素 5,在顺序表中删除指定位置的元素 6,遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y(x和y自定义)之间的所有元素 方法: 按顺序取出元素并与x、y比较,若小于x且大于y,则存进新表中。 编程实现将两个有序的线性表进行合并,要求同样的数据元素只出现一次。 方法: 分别按顺序取出L1,L2的元素并进行比较,若相等则将L1元素放进L中,否则将L 1,L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList(List* L,int ms) 向顺序表指定位置插入元素InsertList(List* L,int item,int rc)删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2(List* L,int rc) 查找顺序表中的元素 FindList(List L,int item) 输出顺序表元素OutputList(List L) 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList(List* L,int ms) void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 《数据结构》实验报告 专业: 学号: 姓名: 实验二线性表 【实验目的】 1.熟悉VC环境,学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试,进一步理解线性表的基本概念,东运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1、一个线性表有n个元素(n-MAXSIZE.MAXSIZE指线性表的最大长度),且递增有。现有一元素x要插入到线性表的适当位置上,并保持线性表原有的顺序不变。设计程序实现。要求:采用顺序存储表示实现;采用链式存储表示方法实现:比较两种方法的优劣。 2.从单链表中删除指定的元素x,若x在单链表中不存在,给出提示信息。 要求: ①指定的值x由键盘输入; ②程序能处理空链表的情况。 3.设有头结点的单链表,编程对表中的任意值只保留一个结点,删除其余值相同的结点。 要求: ①该算法用函数(非主函数)实现; ②在主函数中调用创建链表的函数创建一个单链表,并调用该函数,验证算法的正确性。LinkedList Exchange(LinkedList HEAD,p) //HEAD是单链表头结点的指针,p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 (q=head->next;//q是工作指针,指向链表中当前待处理结点。 pre=head;//pre是前驱结点指针,指向q的前驱。 while(q'=null &&q1=p)(pre=q;q=q->next;]/未到p结点,后移指针。 if(p->next==null)printf(“p无后继结点\n”);/p是链表中最后一个结点,无后继。 else/处理p和后继结点交换 (q=p->next;//暂存p的后继。 pre->next=q://p前驱结点的后继指向p的后继。 p->next=q->next;//p的后继指向原p后继的后继。 q->next=p://原p后继的后继指针指向p。} }//算法结束。 4.已知非空单链表第一个结点由head指出,请写一算法,交换p所指结点与其下一个结点在链表中的位置。 要求: 实验项目名称:图的遍历 一、实验目的 应用所学的知识分析问题、解决问题,学会用建立图并对其进行遍历,提高实际编程能力及程序调试能力。 二、实验容 问题描述:建立有向图,并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数,能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机,Code::Blocks。 四、实验原理 用邻接表存储一个图,递归方法深度搜索和用队列进行广度搜索,并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;i 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 [内容要求] 1、存储结构:顺序表、单链表或其他存储结构,需要画示意图,可参考书上P59 页图2-9 2.2 关键算法分析 结点类: template 邻接矩阵的实现 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 哈尔滨工业大学计算机科学与技术学院 实验报告 课程名称:数据结构与算法 课程类型:必修 实验项目名称:线性表实验 实验题目:算术表达式求值 班级:0903201 学号:1090320110 姓名:王岳 一、实验目的 二、实验要求及实验环境 三、设计思想(本程序中的用到的所有数据类型的定义,主程序的流程图及各程序模块之间的调用关系) 1.逻辑设计 2.物理设计 四、测试结果 五、系统不足与经验体会 六、附录:源代码(带注释) #include else { this -> top--; return this -> ss[this -> top + 1]; } } void push(elementtype x) { if (this -> top == 511) printf("error:full!!!\n"); else { this -> top++; this -> ss[this -> top] = x; } } }; void change(int &i,int &j,double *a,char *input,stack 班级::学号: 实验一线性表的基本操作 一、实验目的 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; 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________ 实验一.线性表的应用 1.实验目的:掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容: 1)编写函数,实现用链表结构建立多项式; 2)编写函数,实现多项式的加法运算; 3)编写函数,实现多项式的显示; 4)测试:编写主函数,它定义并建立两个多项式,显示 两个多项式,然后将它们相加并显示结果。变换测试用的多项式,检查程序的执行结果。 选做内容:修改程序,选择实现以下功能: 5)多项式求值:编写一个函数,根据给定的x值计算并 返回多项式f(x)的值。测试该函数(从终端输入一个x的值,调用该函数并显示返回结果)。 6)多项式相减:编写一个函数,求两个多项式相减的多 项式。 7)多项式相乘:编写一个函数,求两个多项式的乘积多 项式。 3.算法说明: 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数,使输出的多项式更符合表达规范。 2)多项式减法:同次项的系数相减(缺项的系数是0)。 例如a(x)=-5x2+2x+3,b(x)= -4x3+3x,则a(x)-b(x) =4x3-5x2-x+3。提示:a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法:两个多项式的相乘是“系数相乘,指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘,形成多个多项式,再将它们累加在 一起。例如,a(x)=-5x2+2x+3,b(x)=-4x3+3x,则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤: 根据实验报告的要求,我对文件夹里的C文件进行了丰 富和修改,步骤如下: 链表结构建立多项式: typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数,实现多项式的加法运算; PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。 《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的:掌握无向图的邻接链表存储,熟悉无向图的广度与深度优先遍历。 ◎实验内容:对一个无向图以邻接链表存储,分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中,输入的形式为无向图的邻接链表形式,首先输入该无向图的顶点数和边数,接着输入顶点信息,再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储,并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括:(1)建立一个无向图的邻接链表存储(2)以深度优先遍历输出(3)以广度优先遍历输出(4)结束 5.测试数据: 顶点数和边数:6,5 顶点信息:a b c d e f 边的顶点对应序号: 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出: a d e c b f 广度优先遍历输出: a d c b e f 二概要设计 为了实现上述操作,应以邻接链表为存储结构。 1.基本操作: void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v) 以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块: (1)主程序模块 (2)无向图的邻接链表存储模块 (3)深度优先遍历输出模块 (4)广度优先遍历输出模块 3.模块调用图: 三详细设计 1.元素类型,结点类型和指针类型:typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析: (1)主程序模块 int main() 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境,进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21,23,14,5,56,17,31},然后在第i个位置插入元素68。 3.建立一个带头结点的单链表,结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点,一维数组的机内表示就是顺序结构。因此,可用C语言的一维数组实现线性表的顺序存储。 在此,我们利用C语言的结构体类型定义顺序表: #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里,可避免在后面的参考程序中代码重复书写,另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素,在插入过程中注意溢出情况以及数组的下标与位序(顺序表中元素的次序)的区别。 3.单链表的结点结构除数据域外,还含有一个指针域。用C语言描述结点结构如下: typedef int elemtype; typedef struct node 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;i 班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 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; 图实验 一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template数据结构实验报告全集
数据结构实验报告格式
数据结构实验一题目一线性表实验报告
数据结构实验报告
数据结构实验报告图实验
数据结构_实验1_线性表的基本操作
数据结构线性表实验报告
数据结构图的遍历实验报告
数据结构实验报告模板
数据结构实验报告图实验
哈工大 数据结构 实验一 线性表的实验
数据结构实验一 实验报告
数据结构线性表的应用实验报告
数据结构实验报告无向图
《数据结构》实验一 线性表及其应用
数据结构实验报告及心得体会
数据结构实验一 实验报告
数据结构实验报告图实验