实验报告
实验课程:数据结构
实验项目:实验三互联网域名查询
专业:计算机科学与技术
班级:
姓名:
学号:
指导教师:
目录一、问题定义及需求分析
(1)问题描述
(2)实验任务
(3)需求分析
二、概要设计:
(1)抽象数据类型定义
(2)主程序流程
(3) 模块关系
三、详细设计
(1)数据类型及存储结构
(2)模块设计
四、调试分析
(1)调试分析
(2)算法时空分析
(3)经验体会
五、使用说明
(1)程序使用说明
六、测试结果
(1)运行测试结果截图
七、附录
(1)源代码
一、问题定义及需求分析
(1)实验目的
互联网域名查询
互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域,如cn、com等,最底层(第四层)是叶子结点,如www等。因此,域名搜索可以看成是树的遍历问题。
(2)实验任务
设计搜索互联网域名的程序。
(3)需求分析:
1)采用树的孩子兄弟链表等存储结构。
2)创建树形结构。
3)通过深度优先遍历搜索。
4)通过层次优先遍历搜索。
二、概要设计:
采用孩子兄弟链表存储结构完成二叉树的创建;
主程序流程:
创建根节点域名输入域名拆分根据孩子兄弟链表表示的树进行插入调用层次优先遍历输出遍历结果调用深度优先遍历输出遍历结果结束程序
模块关系:
输入域名
创建孩子兄弟树
层次优先遍历输出结果
深度优先遍历输出结果
结束
三、详细设计
孩子兄弟链表结构:
typedef struct CSNode{
ElemType data[10];
struct CSNode *firstchild, *nextsibling;
}*CSTree;
模块一深度优先遍历
算法如下
void DFS(CSNode *root) {
if (!root) return;//递归结束条件
printf("%s\n", root->data);
DFS(root->firstchild);//递归遍历孩子节点
DFS(root->nextsibling);//递归遍历兄弟节点
}
模块二层次优先遍历
算法如下
void BFS(CSNode *root) {
printf("层次优先搜索遍历结果为:\n");
Queue que;
que.Clear();
que.push(root);//根节点入队列
while (!que.empty()) {//队列不空的时候执行循环
CSNode *xx = que.front(); //取队首元素
que.pop();//出队列
printf("%s\n", xx->data);
if (xx->nextsibling) {//出队节点的孩子节点若不空则入队列
que.push(xx->nextsibling);
}
if (xx->firstchild) {//同样若孩子节点不空则入队列
que.push(xx->firstchild);
}
}
}
四、调试分析
问题解决:
在编写层次优先遍历算法的时候遍历结果总是不正确,原因是取完队首元素后没有将出队列,经过改正,在取队首元素后加上出队列函数将队首元素出队;这样便解决了问题;
时空分析:经过孩子兄弟链表表示的树创建后便得到一棵二叉树;对于两个遍历函数,深度优先遍历是递归算法,在时间上,递归算法效率较低,尤其是运算次数较大的时候;层次优先遍历函数借助到队列,所以在内存占用上较多;而深度优先遍历算法的空间占用上更优于层次优先遍历;
经验体会:
孩子兄弟链表表示的树与二叉树可以相互转化;它的深度优先遍历递归算法虽较为简单但相比非递归算法而言效率不高。
五、使用说明
第一步:输入域名
第二步:完成创建
第三步:输出层次优先遍历结果
第四步:输出深度有限遍历结果
六、测试截屏
七、附录
#include
#include
#include
#define ElemType char
#define QueueSize 50
#define push Push
#define empty Empty
#define pop Pop
#define front Front
typedef struct CSNode{
ElemType data[10];
struct CSNode *firstchild, *nextsibling; }*CSTree;//节点结构
void InitTree(CSNode *A)
{ //构造一个空树
A = (CSTree)malloc(sizeof(CSNode));
A->firstchild = A->nextsibling = NULL;
}
int Search_(CSNode *X, char *a)
{ //查找待插入的节点在树中是否存在
CSNode *B;
B = X;//B指向根节点
while (B->data)
{
if (strcmp(B->data, a) == 0)
{
X = B; //若存在相等的则返回1
return 1;
}
else
{
B = B->nextsibling; //否则B指向它的兄弟节点
}
}
return 0;
}
void hanshu1(CSNode *A, ElemType *s)
{//将节点插入到树中
CSNode *B, *X;
char *str;
int i;
X = A; //X指向根节点
B = (CSTree)malloc(sizeof(CSNode));
B->firstchild = B->nextsibling = NULL;
char ZhongZhuan[15]; //中转数组
for (; s != '\0';)
{
//zhongzhuan接受s中xxx.部分或取完翻转zhongzhuan
str = strchr(s, '.');//返回字符串s中第一次出现点的位置
if (str)
{
i = str - s;
ZhongZhuan[i + 1] = '\0';
for (; i >= 0; i--, s++)
{
ZhongZhuan[i] = s[0];//将拆分后的节点传入中转数组中}
}
else
{//字符串中不含点符号
_strrev(s);
i = strlen(s);
ZhongZhuan[i + 1] = '\0';
for (; i >= 0; i--)
{
ZhongZhuan[i] = s[i];//将字符串存入中转数组里
}
s = '\0';
}
if (Search_(X, ZhongZhuan))
{//若要插入的字符串已存在该层面上
X = X->firstchild;//x指向孩子节点
continue;
}
if (X->data[0] == '0')
{
strcpy(X->data, ZhongZhuan);//将中转数组的信息复制给待插入节点
B = (CSTree)malloc(sizeof(CSNode));
B->firstchild = B->nextsibling = NULL;
}
else
{
if (X->firstchild)
{
strcpy(B->data, ZhongZhuan);
X->nextsibling = B;//将B作为X的兄弟节点
B = (CSTree)malloc(sizeof(CSNode));
B->firstchild = B->nextsibling = NULL;
X = X->nextsibling; //x指向它的兄弟节点
}
else
{
strcpy(B->data, ZhongZhuan);
X->firstchild = B;
B = (CSTree)malloc(sizeof(CSNode));
B->firstchild = B->nextsibling = NULL;
X = X->firstchild;
}
}
}
}
struct Queue {
int Top, Tail;
CSNode *a[1000];
void Clear();
void Push(CSNode *e);
void Pop();
CSNode *Front();
bool Empty();
};//队列封装为结构体
void Queue::Clear() {
Top = Tail = 0;
return;
}//清空队列
void Queue::Push(CSNode *e) {
a[Tail++] = e;
return;
}//入队列
void Queue::Pop() {
Top++;
return;
}//出队列
CSNode *Queue::Front() {
return a[Top];
}//取队首元素
bool Queue::Empty() {
return Top == Tail;
}//判空
void BFS(CSNode *root) {
printf("层次优先搜索遍历结果为:\n");
Queue que;
que.Clear();
que.push(root);//根节点入队列
while (!que.empty()) {//队列不空的时候执行循环
CSNode *xx = que.front(); //取队首元素
que.pop();//出队列
printf("%s\n", xx->data);
if (xx->nextsibling) {//出队节点的孩子节点若不空则入队列que.push(xx->nextsibling);
}
if (xx->firstchild) {//同样若孩子节点不空则入队列que.push(xx->firstchild);
}
}
}
void DFS(CSNode *root) {
if (!root) return;//递归结束条件
printf("%s\n", root->data);
DFS(root->firstchild);//递归遍历孩子节点
DFS(root->nextsibling);//递归遍历兄弟节点
}
int main()
{
int j;
CSNode *A;
A = (CSNode*)malloc(sizeof(CSNode));//根节点创建
A->firstchild = A->nextsibling = NULL;
A->data[0] = '0';
char b[30]; //定义字符数组接收域名
char *s;
for (j = 0; j<3; j++)
{
printf("请输入网址:");
gets(b);
s = b;//s指向数组b
_strrev(s);
hanshu1(A, s);//字符串s存入A中
}
BFS(A);//层次优先遍历
printf("深度优先遍历结果为:\n");
DFS(A);//深度优先遍历
}
数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法,并做了相应的性能分析和比较,课程内容丰富,理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: 1)理论艰深,方法灵活,给学习带来困难; 2)内容丰富,涉及的知识较多,学习有一定的难度; 3)侧重于知识的实际应用,要求学生有较好的思维以及较强的分析和解决问题的能力,因而加大了学习的难度; 根据《数据结构》课程本身的特性,通过实验实践内容的训练,突出构造性思维训练的特征,目的是提高学生分析问题,组织数据及设计大型软件的能力。 课程上机实验的目的,不仅仅是验证教材和讲课的内容,检查自己所编的程序是否正确,课程安排的上机实验的目的可以概括为如下几个方面: (1)加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常,实验题中的问题比平时的习题复杂得多,也更接近实际。实验着眼于原理与应用的结合点,使学生学会如何把书上学到的知识用于解决实际问题,培养软件工作所需要的动手能力;另一方面,能使书上的知识变" 活" ,起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时,觉得无从下手。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出
现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法,而实验题是软件设计的综合训练,包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧,多人合作,以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容,进一步提高灵活运用数据结构、算法和程序设计技术的能力,而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点,使学生学会如何把书本上和课堂上学到的知识用于解决实际问题,从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境,学习上机调试程序一个程序从编辑,编译,连接到运行,都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件,软件条件,只有学会使用这些环境,才能进行 程序开发工作。通过上机实验,熟练地掌握程序的开发环境,为以后真正编写计算机程序解决实际问题打下基础。同时,在今后遇到其它开发环境时就会触类旁通,很快掌握新系统的使用。 完成程序的编写,决不意味着万事大吉。你认为万无一失的程序,实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误,也能够顺利运行,但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误,只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作,尽快掌握程序调试方法是非常重要的。分析问题,选择算法,编好程序,只能说完成一半工作,另一半工作就是调试程序,运行程序并得到正确结果。 二、实验要求 常用的软件开发方法,是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高,但为了培养一个软件工作者所应具备的科学工作的方法和作风,也应遵循以下五个步骤来完成实验题目: 1) 问题分析和任务定义 在进行设计之前,首先应该充分地分析和理解问题,明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型,而是对所需完成的任务作出明确的回答。例如:输入数据的类型、值的范围以及输入的
中央电大本科数据结构形成性考核册实验报告 实验名称:实验一线性表 线性表的链式存储结构 【问题描述】 某项比赛中,评委们给某参赛者的评分信息存储在一个带头结点的单向链表中,编写程序: (1)显示在评分中给出最高分和最低分的评委的有关信息(姓名、年龄、所给分数等)。 (2)在链表中删除一个最高分和一个最低分的结点。 (3)计算该参赛者去掉一个最高分和一个最低分后的平均成绩。 【基本要求】 (1)建立一个评委打分的单向链表; (2)显示删除相关结点后的链表信息。 (3)显示要求的结果。 【实验步骤】 (1)运行PC中的Microsoft Visual C++ 6.0程序, (2)点击“文件”→“新建”→对话窗口中“文件”→“c++ Source File”→在“文件名”中输入“X1.cpp” →在“位置”中选择储存路径为“桌面”→“确定”, (3)输入程序代码, 程序代码如下: #include
北京邮电大学电信工程学院 数据结构实验报告 实验名称:实验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 .实验目的 (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<<" 建立一个单链表"<
线性表 代码一 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int * elem; int length; int listsize; }SqList; int InitList_Sq(SqList *L) { L->elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int)); if (!L->elem) return ERROR; L->length = 0; L->listsize = LIST_INIT_SIZE; return OK; } int ListInsert_Sq(SqList *L, int i,int e) { int *p,*newbase,*q; if (i < 1 || i > L->length+1) return ERROR; if (L->length >= L->listsize) { newbase = (int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof (int)); if (!newbase) return ERROR; L->elem = newbase; L->listsize += LISTINCREMENT; } q = &(L->elem[i-1]); //插入后元素后移for(p=&(L->elem[L->length-1]);p>=q;p--) *(p+1)=*p; *q=e; L->length++; return OK; } int ListDelete_Sq(SqList *L, int i, int *e) {
实验报告五查找(学科:数据结构) 姓名单位班级学号实验日期成绩评定教师签名批改日期 实验名称:实验五查找 5.1 折半查找 【问题描述】 某班学生成绩信息表中,每个学生的记录已按平均成绩由高到低排好序,后来发现某个学生的成绩没有登记到信息表中,使用折半查找法把该同学的记录插入到信息表中,使信息表中的记录仍按平均成绩有序。 【基本信息】 (1)建立现有学生信息表,平均成绩已有序。 (2)输入插入学生的记录信息。 (3)用折半查找找到插入位置,并插入记录。 【测试数据】 自行设计。 【实验提示】 (1)用结构数组存储成绩信息表。 (2)对记录中的平均成绩进行折半查找。 【实验报告内容】 设计程序代码如下: #include
low=1; hight=n; strcpy(y,s[0].name ); x=s[0].avg ; while(low<=hight) { mid=(low+hight)/2; if(x>s[mid].avg ) hight=mid-1; else low=mid+1; } for(k=0;k 图实验一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include #include return q; } void Delete_m(Link &L, Link p, Link q)//删除第m个{ p->next = q->next; free(q); } void main() { Link L, p, q; int n, m; L = NULL; InitList(L);//构造出一个只有头结点的空链表 printf("请输入初始密码人数每个人的密码:\n"); scanf("%d", &m);//初始密码为m scanf("%d", &n);// Creatlinklist(n, L);//构建 p = L; for (int i = 1; i <= n; i++) { q = Locate_m(p, m);//找到第m个 printf("%d", q->num); Delete_m(L, p, q);//删除第m个 } system("pause"); } 福建广播电视大学实验报告(学科:数据结构)姓名单位班级学号实验日期成绩评定教师签名批改日期 实验名称:实验四图的存储方式和应用 4.1建立图的邻接矩阵 【问题描述】 根据图中顶点和边的信息编制程序建立图的邻接矩阵。 【基本要求】 (1)程序要有一定的通用性。 (2)直接根据图中每个结点与其他结点的关联情况输入相关信息,程序能自动形成邻接矩阵 【测试用例】 【实现提示】 (1)对图的顶点编号。 (2)在上图中,以顶点1为例,因为顶点2,3,4与顶点1关联,可以输入信息1 2 3 4,然后设法求出与顶点1关联的结点,从而求得邻接矩阵中相应与顶点1的矩阵元素。 实验图4-1 设计程序代码如下: #include #define MaxEdgeNum 20 #define MaxValue 1000 typedef int VertexType; typedef VertexType vexlist [MaxVertexNum]; typedef int adjmatrix [MaxVertexNum] [MaxVertexNum]; void Createl(vexlist Gv,adjmatrix GA,int n,int e) { int i,j,k,w; printf("输入%d个顶点数据\n",n); for(i=0;i 《数据结构》实验报告 专业: 学号: 姓名: 实验二线性表 【实验目的】 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 顺序表的基本操作 #include int j=0; while(L.data[j]!=x) j++; if(j==https://www.doczj.com/doc/0815941003.html,st) { cout<<"所查找值不存在!"< 实验名称:实验一线性表 线性表的链式存储结构 【问题描述】 某项比赛中,评委们给某参赛者的评分信息存储在一个带头结点的单向链表中,编写程序: (1)显示在评分中给出最高分和最低分的评委的有关信息(姓名、年龄、所给分数等)。 (2)在链表中删除一个最高分和一个最低分的结点。 (3)计算该参赛者去掉一个最高分和一个最低分后的平均成绩。 【基本要求】 (1)建立一个评委打分的单向链表; (2)显示删除相关结点后的链表信息。 (3)显示要求的结果。 【实验步骤】 (1)运行PC中的Microsoft Visual C++ 6.0程序, (2)点击“文件”→“新建”→对话窗口中“文件”→“c++ Source File”→在“文件名”中输入“X1.cpp” →在“位置”中选择储存路径为“桌面”→“确定”, (3)输入程序代码, 程序代码如下: #include 邻接矩阵的实现 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 #include 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________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、直接插入排序 2、希尔排序 3、2-路归并排序 4、折半插入排序 5、冒泡排序 6、快速排序 7、堆排序 /*---------------------------------------- * 07_排序.cpp -- 排序的相关操作 * 对排序的每个基本操作都用单独的函数来实现 * 水上飘2011年写 ----------------------------------------*/ // ds07.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "stdio.h" #include int i, j; for (i = dk + 1; i <= L.length; i++) { if (L.arr[i].key 数据结构实验报告图实验
数据结构实验一的源代码
数据结构实验报告4(中央电大)
数据结构线性表实验报告
数据结构图的遍历实验报告
数据结构实验程序
中央电大本科数据结构实验报告
数据结构实验报告图实验
数据结构上机实验线性表单链表源代码
数据结构线性表的应用实验报告
数据结构实验报告无向图
数据结构实验(七种排序算法的实现)题目和源程序