淮海工学院计算机科学系实验报告书
课程名:《数据结构》
题目:线性数据结构实验
班级:
学号:
姓名:
线性表算法实现与应用报告要求
1目的与要求:
1)掌握栈与队列的数据类型描述及特点;
2)掌握栈的顺序和链式存储存表示与基本算法的实现;
3)掌握队列的链式和循环存储表示与基本操作算法实现;
4) 掌握栈与队列在实际问题中的应用和基本编程技巧;
5)按照实验题目要求,独立完成实际程序的编写编写、调试和运行,并通过用例数的运行过程抓获相关屏面验证程序设计的正确性;
7)认真书写实验报告,并在下周一以前按时提交。
2 实验内容或题目
1、实现顺序栈的创建(初始化)、压入(插入)、弹出(删除)操作,要求给出栈的操作变化过
程;
2、实现链栈的创建(初始化)、压入(插入)、弹出(删除)操作,要求给出栈的操作变化过程;
3、实现循环队列的创建、进队、出队等基本操作,并实时给出队列的操作变化状态;
4、实现链式队列的创建、进队、出队等基本操作,并实时给出队列的操作变化状态;
3 实验步骤与源程序
实验步骤
第一题
先定义该顺序栈元素的数据类型为char型,再定义顺序栈,再对栈进行初始化,设一个位置指针top来动态地指示栈顶元素在顺序栈中的位置,以top=-1表示空栈。再写进栈算法,在此过程中,先判断栈中元素是否已满,若满了,则返回FALSE,否则让栈顶位置加1,把要压入的元素压到栈顶元素的位置。编写出栈算法时,先判断栈是否为空,若栈为空则返回FALSE,否则,将栈顶元素弹出,放到x所指的存储空间中,修改栈顶指针,使栈顶指针减1。然后再写main主函数,在调用压入函数和删除函数之前,要先调用初始化函数。
第二题
先定义该链栈元素的数据类型为char型,定义链栈的结构,对链栈进行初始化。在写进栈算法时,先判断空间有没有申请成功,若申请失败返回FALSE,否则,压入数据,修改当前的栈顶指针,使当前指针指向新插入数据元素的地址。在main主函数中,在调用压入和删除元素之前,要先调用初始化函数。
第三题
定义一个循环队列,定义队列的元素空间,及头指针和尾指针指示器。将*Q初始化为一个空的循环队列,即Q->front=Q->rear=0。在写入队操作时,先用(Q->rear+1)%MAXSIZE==Q->front语句判断队列是否已满,若满了,则返回FALSE,否则,让尾指针指向该元素地址,然后重新设置队尾指针。在进行出队操作时,用(Q->front==Q->rear判断队列是否为空,若为空,则返回FALSE,否则,用*x返回该队头元素值,然后重新设置对尾指针。在main主函数中,在调用入队和出队操作
之前,要先调用初始化函数。
第四题
定义一个链队列,设置一个队头指针及一个队尾指针,将Q初始化为一个空的链队列,在进行入队操作时,先判断新申请的指针是否为空,若为空,则输出FALSE,否则,进行 NewNode->data=x; NewNode->next=NULL;Q->rear->next=NewNode;Q->rear=NewNode;的操作。在进行输出操作时,先用Q->front==Q->rear判断该队列是否为空,若为空,则输出FALSE否则,让队头元素出队,并释放该元素的存储空间。在main主函数中,在调用入队和出队操作之前,要先调用初始化函数。
源程序
第一题
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define Stack_Size 50
typedef char StackElementType;
typedef struct
{
StackElementType elem[Stack_Size];
int top;
}SeqStack;
void InitStack(SeqStack *S)
{
S->top=-1;
}
int Push(SeqStack *S,StackElementType x)
{
if(S->top==Stack_Size-1)
return (FALSE);
S->top++;
S->elem[S->top]=x;
return(TRUE);
}
int Pop(SeqStack *S,StackElementType *x)
{
if(S->top==-1)
return(FALSE);
else
{
*x=S->elem[S->top];
S->top--;
return(TRUE);
}
}
void print(SeqStack *t)
{
int i;
for(i=t->top;i>=0;i--)
{
printf("%c",t->elem[i]);
}
printf("\n");
}
int main()
{
SeqStack m;
StackElementType n;
int flag=1;
int choice;
InitStack(&m);
printf("请先输入顺序栈数据:\n");
while(flag)
{
n=getchar();
if(n!='$')
Push(&m,n);
else
flag=0;
}
printf("该顺序栈中的元素为:\n");
print(&m);
printf("\n\n 1.压入数据\n\n"); printf(" 2.删除栈顶元素\n\n"); printf(" 3.退出该程序\n\n\n"); while(1)
{
printf("请输入要进行的操作:");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("请输入要压入该顺序栈的数据:");
cin>>n;
Push(&m,n);
print(&m);break;
case 2:
printf("删除顺序栈的栈顶元素后该栈的元素变为:\n"); Pop(&m,&n);
print(&m);
break;
case 3:printf("退出程序,欢迎使用!\n");break;
default:printf("输入错误,请重新输入!");break;
}
if(choice>=3)break;
}
return 0;
}
第二题
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
typedef char StackElementType;
typedef struct node
{
StackElementType data;
struct node *next;
}LinkStackNode;
typedef LinkStackNode *LinkStack;
void InitStack(LinkStack *top)
{
*top=(LinkStack)malloc(sizeof(LinkStackNode));
(*top)->next=NULL;
}
int Push(LinkStack top,StackElementType x)
{
LinkStackNode *temp;
temp=(LinkStackNode *)malloc(sizeof(LinkStackNode)); if(temp==NULL)
return(FALSE);
temp->data=x;
temp->next=top->next;
top->next=temp;
return(TRUE);
}
int Pop(LinkStack top,StackElementType *x)
{
LinkStackNode *temp;
temp=top->next;
if(temp==NULL)
return(FALSE);
top->next=temp->next;
*x=temp->data;
free(temp);
return(TRUE);
}
void Print(LinkStack top)
{
LinkStackNode *temp;
temp=top->next;
while(temp!=NULL)
{
printf("%c",temp->data);
temp=temp->next;
}
printf("\n");
}
int main()
{
LinkStack t;
InitStack(&t);
int flag=1;
int choice;
char n;
printf("请先输入链栈数据:\n");
while(flag)
{
n=getchar();
if(n!='$')
Push(t,n);
else
flag=0;
}
printf("该链栈中的元素为:\n");
Print(t);
printf("\n 1.压入数据\n\n");
printf(" 2.删除栈顶元素\n\n");
printf(" 3.退出该程序\n\n");
while(1)
{
printf("请输入要进行的操作:");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("请输入要压入该链栈的数据:");
cin>>n;
Push(t,n);
printf("元素进栈后的情况:\n");
Print(t);break;
case 2:
printf("删除元素!!");
Pop(t,&n);
printf("元素出栈后的情况为:\n");
Print(t);break;
case 3:
printf("退出程序,欢迎使用!\n");break;
}
if(choice>=3)break;
}
return 0;
}
第三题
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define MAXSIZE 50
typedef char QueueElementType;
typedef struct
{
QueueElementType element[MAXSIZE];
int front;
int rear;
}SeqQueue;
void InitQueue(SeqQueue *Q)
{
Q->front=Q->rear=0;
}
int EnterQueue(SeqQueue *Q,QueueElementType x) {
if((Q->rear+1)%MAXSIZE==Q->front)
return(FALSE);
Q->element[Q->rear]=x;
Q->rear=(Q->rear+1)%MAXSIZE;
return(TRUE);
}
int DeleteQueue(SeqQueue *Q,QueueElementType *x) {
if(Q->front==Q->rear)
return(FALSE);
*x=Q->element[Q->front];
Q->front=(Q->front+1)%MAXSIZE;
return(TRUE);
}
void print(SeqQueue *s)
{
int i;
for(i=s->front;i<=s->rear;i++)
{
printf("%c",s->element[i]);
}
printf("\n");
}
int main()
{
SeqQueue t;
char s,n;
int flag=1;
int choice;
InitQueue(&t);
printf("请先输入循环队列数据:\n");
while(flag)
{
n=getchar();
if(n!='$')
EnterQueue(&t,n);
else
flag=0;
}
printf("该循环队列的数据为:\n");
print(&t);
printf("\n 1.数据进队\n\n");
printf(" 2.出队\n\n");
printf(" 3.退出该程序\n\n");
while(1)
{
printf("请输入要进行的操作:");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("输入要进队的数据:");
cin>>n;
EnterQueue(&t,n);
printf("该数据进队后,循环队列变为:\n");
print(&t);break;
case 2:
DeleteQueue(&t,&s);
printf("删除队头元素后该循环队列变为:\n");
print(&t);break;
case 3:
printf("退出程序,欢迎使用!\n");break;
}
if(choice>=3)break;
}
return 0;
}
第四题
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
typedef char QueueElementType;
typedef struct Node
{
QueueElementType data;
struct Node *next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode *front;
LinkQueueNode *rear;
}LinkQueue;
int InitQueue(LinkQueue *Q)
{
Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); if(Q->front!=NULL)
{
Q->rear=Q->front;
Q->front->next=NULL;
return(TRUE);
}
else
return(FALSE);
}
int EnterQueue(LinkQueue *Q,QueueElementType x)
{
LinkQueueNode *NewNode;
NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); if(NewNode!=NULL)
{
NewNode->data=x;
NewNode->next=NULL;
Q->rear->next=NewNode;
Q->rear=NewNode;
return(TRUE);
}
else
return(FALSE);
}
int DeleteQueue(LinkQueue *Q,QueueElementType *x)
{
LinkQueueNode *p;
if(Q->front==Q->rear)
return(FALSE);
p=Q->front->next;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
*x=p->data;
free(p);
return(TRUE);
}
void print(LinkQueue *Q)
{
LinkQueueNode *temp;
temp=Q->front->next;
while(temp!=NULL)
{
printf("%c",temp->data);
temp=temp->next;
}
printf("\n");
}
int main()
{
LinkQueue p;
int flag=1;
int choice;
char n;
InitQueue(&p);
printf("请先输入链队列数据:\n"); while(flag)
{
n=getchar();
if(n!='$')
EnterQueue(&p,n);
else
flag=0;
}
printf("该链队中的元素为:\n"); print(&p);
printf("\n 1.数据入队\n\n"); printf(" 2.数据出队\n\n"); printf(" 3.退出该程序\n\n"); while(1)
{
printf("请输入要进行的操作:");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("请输入要进入该链队的数据:");
cin>>n;
EnterQueue(&p,n);
printf("元素进队后该链队的数据变为:\n");
print(&p);break;
case 2:
printf("删除元素!!");
DeleteQueue(&p,&n);
printf("元素出队后该链队的数据变为:\n"); print(&p);break;
case 3:
printf("退出程序,欢迎使用!\n");break;
}
if(choice>=3)break;
}
return 0;
}
4 测试数据与实验结果(可以抓图粘贴)
第一题
第二题
第三题
第四题
5 结果分析与实验体会
数据结构实验报告全集 实验一线性表基本操作和简单程序 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、通过建立通讯录结构体,对信息进行存储,建立链表,建立信息之间 的联系。 typedef struct { }DataType;结构体来存储通讯录中的基本信息 typedef struct node { DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ }ListNode,*LinkList; 2、信息插入操作,将信息查到链表的后面。 void ListInsert(LinkList list){ //信息插入 ListNode *w; w=list->next; while(w->next!=NULL) { w=w->next; } ListNode *u=new ListNode; u->next=NULL; cout<<"员工编号:";cin>>u->data.num; cout<<"员工姓名:";cin>>u->https://www.wendangku.net/doc/603499610.html,; cout<<"手机号码:";cin>>u->data.call; cout<<"员工邮箱:";cin>>u->data.email; cout<<"办公室电话号码:";cin>>u->data.phone; w->next=u;w=w->next; }
北京邮电大学电信工程学院 数据结构实验报告 实验名称:实验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.初始化线性表; 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;
学生实验报告册 (理工类) 课程名称:算法与数据结构专业班级 学生学号:学生: 所属院部:计算机工程学院指导教师:章海鸥 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
数据结构实验报告(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.熟悉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所指结点与其下一个结点在链表中的位置。 要求: 《空间数据结构基础》 课程实习报告(测绘10级) 姓名 班级 学号 环境与测绘学院 1C++面向对象程序设计基础 【实验简介】学会用算法语言C++描述抽象数据类型,使用模板建立数据结构。理解数据结构的组成分为两部分,第一部分是数据集(数据元素),第二部分是在此数据集上的操作。从面向对象的观点看,这两部分代表了对象的属性和方法。掌握用C++描述数据结构的基本方法,即通过建立类来描述抽象数据类型。类的数据成员提供对象属性,成员函数提供操作方法,方法是公共接口,用户通过调用方法实现对属性的访问。 【实验内容】 1.定义三维空间的坐标点TPoint 2.描述三维空间的球TBall,实现其主要操作(如计算体积和表面积,输出空间坐标 等)。 【主要代码】 头文件: TPoint.h: #ifndef TPOINT_H #define TPOINT_H #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)迷宫存储迷宫,寻路径,输出迷宫。 哈尔滨工业大学计算机科学与技术学院 实验报告 课程名称:数据结构与算法 课程类型:必修 实验项目名称:线性表实验 实验题目:算术表达式求值 班级: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.掌握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。 程序代码如下: 班级::学号: 实验一线性表的基本操作 一、实验目的 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; 《数据结构》课程 实验报告一线性表的顺序实现 一、实验目的和要求: 1.掌握顺序表的存储结构形式及其描述和基本运算的实现。 2.掌握用顺序表表示集合等数据的方法,并能设计出合理的存储结构,编写出有关运算的算法。 二、实验内容:(给出具体的说明文字和操作图片) 已知顺序表结构与相关函数定义在sequlist.h文件中,基于该文件完成所有实验题。 1.基于sequlist.h中定义的顺序表L,设计一个算法void delx(sequence_list *L, datatype x),删除其中所有值等于x 的元素,要求算法的时间复杂度为O(n)、空间复杂度为0(1)。 #include void initseqlist(sequence_list *L)//初始化OK { L->size=0; } void input(sequence_list *L) { datatype x; initseqlist(L); printf("请输入一组数据,以0做为结束符:\n"); scanf("%d",&x); while (x) { L->a[L->size++]=x; scanf("%d",&x); } } 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________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.熟悉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 《数据结构与数据库/操作系统》实验课作业和要求 实验一、线性表的应用:稀疏一元多项式运算器 实验目的: ?熟练掌握指针和链表操作的基本功 ?熟练掌握数组操作的基本功 ?模块化程序设计(程序的分层结构、函数的功能和接口) ?人机交互界面设计(界面美观,使用方便、操作的弹性好) ?源程序的书写风格(缩进式,加注释,可读性要好) ?对程序健壮性的处理 ?程序的调试技术训练(debug方法和测试数据的选择) ?时空效率 实验学时: 12学时(第1,2,3次实验) 实验内容: 基本功能(必做): 1. 创建 2. 显示 3. 复制 4. 求和 5. 求差 6. 求值 7. 销毁 8. 清空 9. 修改(①插入新的结点、②删除已有结点、③修改已有结点的系数和指数) 拓展功能(选做): 10. 微分(N阶导数) 11. 不定积分 12. 定积分 13. 乘法和乘方 14. 除法 15. 最大公约式和最小公倍式 16. 多项式的四则运算(如“(1+2*3)/4”) 数据组织: ?多项式用带头结点的单链表表示 ?用指针数组存放N个多项式的头指针 存储结构示意图: 用户操作界面: 推荐用菜单驱动 实验二、栈的应用 实验目的: ?掌握栈的后进先出特点 ?掌握栈的表示和实现技术 ?掌握如何运用栈的特点来构建算法 实验内容 (在题目1~6中任选1题): 题目1. 简单的行编辑器(提高难度:实现对文本文件的编辑)题目2. 括号配对检验(提高难度:实现对括号优先级的检测)题目3. 波兰式计算(提高难度:操作数为浮点数) 题目4. 逆波兰式计算(提高难度:操作数为浮点数) 题目5. 中缀式计算(提高难度:操作数为浮点数) 题目6. 迷宫求解(提高难度: 随机迷宫、最短路径的提取) 附加题: 一般表达式的计算,即在表达式中包含其他函数的运算,如: 2.5^3*tan(sin(1.2)+cos( 3.5)) 实验学时:4学时(第4次实验课当堂完成) 华北水利水电大学数据结构实验报告 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.写出算法设计小结和心得。 四、程序源代码: 五、程序运行情况(采用截图方式给出运行结果) 六、小结(包括收获、心得体会、存在的问题及解决问题的方法、建议等) 注:内容一律使用宋体五号字,单倍行间距 班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 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辆车,后来的车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其它车辆再按 实验报告 实验一线性表 实验目的: 1.理解线性表的逻辑结构特性; 2.熟练掌握线性表的顺序存储结构的描述方法,以及在该存储结构下的基本操作;并能灵活运用; 3.熟练掌握线性表的链表存储结构的描述方法,以及在该存储结构下的基本操作;并能灵活运用; 4.掌握双向链表和循环链表的的描述方法,以及在该存储结构下的基本操作。 实验原理: 线性表顺序存储结构下的基本算法; 线性表链式存储结构下的基本算法; 实验内容: 2-21设计单循环链表,要求: (1)单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取消数据元素操作和判非空操作。 (2)设计一个测试主函数,实际运行验证所设计单循环链表的正确性。 2-22 .设计一个有序顺序表,要求: (1)有序顺序表的操作集合有如下操作:初始化、求数据元素个数、插入、删除和取数据元素。有序顺序表与顺序表的主要区别是:有序顺序表中的数据元素按数据元素值非递减有序。 (2)设计一个测试主函数,实际运行验证所设计有序顺序表的正确性。 (3)设计合并函数ListMerge(L1,L2,L3),功能是把有序顺序表L1和L2中的数据元素合并到L3,要求L3中的数据元素依然保持有序。并设计一个主函数,验证该合并函数的正确性。 程序代码: 2-21(1)头文件LinList.h如下: typedef struct node { DataType data; struct node *next; }SLNode; /*(1)初始化ListInitiate(SLNode * * head)*/ void ListInitiate(SLNode * * head) { /*如果有内存空间,申请头结点空间并使头指针head指向头结点*/ if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)exit(1);数据结构线性表实验报告
数据结构课程设计实验报告
数据结构集中上机实验报告
哈工大 数据结构 实验一 线性表的实验
《数据结构》2012级实验报告模板..
数据结构实验一 实验报告
《数据结构》课程实验报告一
数据结构线性表的应用实验报告
《数据结构》实验一 线性表及其应用
《数据结构与数据库操作系统》实验课作业和要求
《数据结构》实验一
数据结构实验一 实验报告
东北大学数据结构实践实验报告
数据结构线性表实验报告