数据结构上机操作实验报告
实验一单链表的基本操作（必做）
一、实验目的
1.掌握单链表的存储、初始化、插入、删除等操作的程序实现。
2.加深对单链表基本概念,基本理论及相应算法的掌握与理解。
3.了解链表的处理方式，学习体会简单的单链表程序实现相关知识。
二、实验内容
1.建立一个链表、设计链表的基本操作实现算法、输出一个链表表，调试并输出结果。
2.编写一个程序实现如下功能：让计算机产生出50个0~9之间的随机数并依次保存到单链表中;输出遍历单链表；从单链表中删除与给定值相等的所有结点；输出遍历单链表；输出单链表长度，调试并输出结果。
三、实验步骤
1.定义一个链表结构体。。
2.利用插入功能插入一个结点。
3.利用删除功能删除一个结点。
四、程序运行测试
1.利用插入功能插入一个结点。
2.利用删除功能删除一个结点。
五、实验报告要求
1.绘制链表操作实现的流程图。
2.详细给出程序运行测试结果（包括测试数据和测试结果）。
3.选试验步骤2-3中的任意一个，给出程序的详细注释。
4.参考程序中某一部分功能的改进（选做）
5.实验心得与体会
6.附录，实验用源程序
六、参考源代码
#include
#include
typedef struct LNode
{int data;
struct LNode *next;
}Lnode, *LinkList;
//假设下面的单链表均为带头结点。
void CreatLinkList(LinkList &L,int j)
{//建立一个单链表L,数据为整数，数据由键盘随机输入。
LinkList p,q;
L=(LinkList )malloc(sizeof(Lnode));
L->next=NULL;
q=L;
cout<<"在单链表内输入整数："< for(int i=0;i p->next=q->next; q->next=p; q=p; } int PrintLinkList(LinkList &L) {//输出单链表L的数据元素 LinkList p; p=L->next; if(L->next==NULL) {cout<<"链表没有元素!"< return 0;} cout<<"单链表的数据元素为:";while(p){ cout< p=p->next;}cout< return 1;} void LinkListLengh(LinkList &L) {//计算单链表L的数据元素个数。 int i=0; LinkList p; p=L->next; while(p) { i++; p=p->next; } cout<<"单链表的数据元素个数为:"< int InsertLinkList(LinkList &L, int i, int x) {//在单链表L的第I个元素前插入一个数据元素X。 LinkList p,s; int j=0; p=L; while(p&&j {p=p->next; ++j;} if(!p||j>i-1){ cout<<"插入元素的位置不合理!"; return 0;} s=(LinkList)malloc(sizeof(LNode)); s->data=x; s->next=p->next; p->next=s; return 1;} int DeleteLinkList(LinkList &L,int i) {//删除单链表L的第I个数据元素。 LinkList p,q; int j=0; p=L; while(p->next&&j p=p->next; ++j;} if(!(p->next)||j>i-1) {cout<<"删除元素的位置不合理!"; return 0; }q=p->next; p->next=q->next; i=q->data; free(q); return 1; } void ClearLinkList(LinkList &L) {//将单链表L置为空表。 L->next=NULL; } void DestroyLinkList(LinkList &L) {//销毁单链表L。 LinkList p,q; p=L->next; while(L->next!=NULL) {q=p->next; L->next=q; free(p);p=q; }free(L); cout<<"链表已经被销毁!"< void main() {//调用上面的各函数，运行并检验程序是否正确。 LinkList L; int i,j,x; cout<<"---------------------------------------"< cout<<" 《单链表实验，按提示操作》"< cout<<"---------------------------------------"< cout<<"输入的元素的个数:"; cin>>j; CreatLinkList(L,j); LinkListLengh(L); PrintLinkList(L); cout<<"在第几个元素前插入:"; cin>>i; cout<<"输入插入的元素:"; cin>>x; InsertLinkList(L,i,x); LinkListLengh(L); PrintLinkList(L); cout<<"输入删除元素的位置:"; cin>>i; DeleteLinkList(L,i); LinkListLengh(L); PrintLinkList(L); ClearLinkList(L); cout<<"清空链表后:"< LinkListLengh(L); PrintLinkList(L); DestroyLinkList(L); } 头文件h文件 #include #include typedef int ElemType; //规定元素类型为整 struct LNode //定义单链表结构 { ElemType data; LNode *next; }; //初始化单链表 void InitList(LNode *& HL) { HL=NULL; //将单链表置空 } void InsertRear(LNode *&HL,const ElemType & item) { LNode *newptr; newptr=new LNode; //为保存新元素分配动态结点， newptr指向这个结点。 if(newptr==NULL) //若未分配到结点，则停止插入，退出程序运行。 {cerr<<"Memory allocation failare!"< exit(1); } newptr->data=item; //把新元素赋给动态结点*newptr的值域 newptr->next=NULL; //给动态结点的指针域置空 if(HL==NULL) HL=newptr; //向空表插入的结点为表头结点 else{ LNode *p=HL; while(p->next!=NULL) //从表头开始遍历到最后一个结点为止 p=p->next; p->next=newptr; //把新结点链接到表尾 }} void TraverseList(LNode *&HL) { LNode *p=HL; while(p!=NULL) {cout< p=p->next; } cout< }int ListSize(LNode *&HL) { LNode *p=HL; int i=0; //用来统计结点的个数 while(p!=NULL) //遍历单链表，统计结点数 { i++; p=p->next; } return i; }int Delete(LNode *&HL,const ElemType & item) {if(HL==NULL){ cerr<<"HL is NULL!"< return 0;} LNode *ap,*cp; ap=NULL;cp=HL; while(cp!=NULL) if(cp->data==item) break; else //使前驱指针和当前指针均指向下一个结点 {ap=cp; cp=cp->next;} if(cp==NULL){ cerr<<"Deleted element is not exist!"< return 0; } if(ap==NULL) //由cp指向的被删除结点是表头结点 HL=HL->next; else //由cp指向被删除结点是非表头结点 ap->next=cp->next; delete cp; return 1; } Cpp文件 #include #include typedef int ElemType; //规定元素类型为整 #include "link.h" //此文件中保存有线性表操作在单链表（由动态独立节点构成）上的实现 void main() { //构成单链表 LNode *head; InitList(head); int i,j; for(i=0;i<50;i++) { j=rand()%10; InsertRear(head,j); } //输出遍历单链表 TraverseList(head); //从单链表中删除与键盘上输入的值相等的所有结点 cout<<"输入一个0~10之间的一个整数："; cin>>j; while(Delete(head,j)){} //输出遍历单链表 TraverseList(head); //输出单链表长度 cout< 实验二链表的应用—飞机票销售系统（选做） 一、实验目的 1.掌握单链表的存储。 2.掌握单链表的插入、删除、查找等操作的程序实现。 3.加深对单链表基本概念,基本理论及相应算法的掌握与理解。 二、实验内容 编制一个简单的飞机票销售系统，它可以完成售票，退票，飞机票剩余情况查询等功能。每张飞机票包含机次，座位信息。在售票，退票，查询剩余票等环节中都会显示出飞机票的信息。 三、实验步骤 1.为每张飞机票建立一个结点。 2.利用插入功能插入一个结点（买票）。 3.利用删除功能删除一个结点（卖票）。 4.查找功能查找链表中的结点信息。 四、程序运行测试 1.利用插入功能插入一个结点（买票）。 2.利用删除功能删除一个结点（卖票）。 3.查找功能查找链表中的结点信息。 五、实验报告要求 1.绘制飞机票销售系统实现的流程图。 2.详细给出程序运行测试结果（包括测试数据和测试结果）。 3.选试验步骤2-4中的任意一个，给出程序的详细注释。 4.参考程序中某一部分功能的改进（选做） 5.实验心得与体会 6.附录，实验用源程序 六、参考源代码 #include #include #include #define null 0 #define elemtype int typedef struct node /*定义个结构*/ { char num[4]; /*机次*/ elemtype seat; /*座位号*/ struct node *next; }ticket; ticket *sale,*back; /*sale为售票链表指针，back为备份链表指针*/ int count() /*查询飞机票剩余情况模块*/ { ticket *q; int n=0; /*机票计数器*/ q=sale; while(q) /*统计机票数*/ { n++; q=q->next; } return(n); } void abort_ticket(elemtype x,char t[]) /*办理退票模块*/ { ticket *s,*q; q=back; /*q指向备份链表*/ s=(ticket *)malloc(sizeof(ticket)); /*需要办理退回的机票*/ s->seat=x; strcpy(s->num,t); while(strcmp(s->num,q->num)&&(s->seat!=q->seat)&&q) /*检查是否为有效票*/ q=q->next; if(!q) printf("对不起！你所退的不是本次飞机的车票！\n"); else /*为有效票办理退回业务*/ { s->next=sale; sale=s; } } void sale_ticket() /*购票模块*/ { ticket *t; if(sale) { t=sale; sale=sale->next; /*从销售链表中删除已售票所在的结点*/ printf("你购买飞机票的车次为：%s,座位号为:%d\n",t->num,t->seat); free(t); } else printf("飞机票已售完！\n"); } void display() /*输出模块*/ { ticket *p; p=sale; if(p==null) printf("飞机票已售完！"); else while(p!=null) /*输出所有剩余机票的机次，座位情况*/ { printf("%3d,%5s",p->seat,p->num); p=p->next; if(p) printf(","); } printf("\n"); } void main() { ticket *q,*p; char tl[4]; int d,i,n,select,flag=1; sale=null; /*销售链表指针初始化*/ back=null; /*备份链表指针初始化*/ printf("请输入飞机座位数："); scanf("%d",&n); for(i=1;i<=n;i++) /*建立所有机票构成的销售链表和备份链表*/ { q=(ticket *)malloc(sizeof(ticket)); p=(ticket *)malloc(sizeof(ticket)); printf("请输入机次："); scanf("%s",q->num); printf("请输入机票座位号："); scanf("%d",&d); q->seat=d; q->next=sale; sale=q; p->seat=d; p->next=back; back=p; printf("\n"); } printf("飞机座位情况为：\n"); display(); printf("\n"); while(flag) { printf("1**********查询剩票数\n"); printf("2**********购票\n"); printf("3**********退票\n"); printf("4**********退出 \n"); printf("请选择您要执行的选项:"); scanf("%d",&select); switch(select) { case 1:{d=count(); printf("\n剩余的机票数为：%d",d); printf("\n座位剩余情况为:"); display(); printf("\n"); } break; case 2:{ printf("\n购买机票:\n"); sale_ticket(); printf("\n"); display(); printf("\n"); } break; case 3:{ printf("\n退票:"); printf("请输入退票的机次:"); scanf("%s",tl); printf("\n请输入退票的座位号:"); scanf("%d",&d); abort_ticket(d,tl); display(); printf("\n"); } break; case 4:flag=0; break; } } } 测试实例 实验三栈和队列的基本操作（必做） 一、实验目的： 1.掌握栈与队列的数据类型描述及特点； 2.掌握栈和队列的存储； 3.掌握栈的顺序和链式存储存表示与入栈、出栈操作的程序实现； 4. 掌握队列的链式存储表示与入队、出队基本操作算法实现 二、实验内容 1.根据栈数据结构，分别建立一个顺序栈和链式栈并实现其上基本操作（出栈和入栈等）； 2.根据队列数据结构，分别建立链队列和循环队列，并完成其上的基本操作（出入队列等）。 三、实验步骤 1.定义一个顺序栈和链栈结构体（队列结构体）。 2.利用入栈功能保存数据。 3.利用出栈删除弹出栈内信息。 4.利用入队功能保存数据。 5.利用出队删除队列信息。 四、程序运行测试 1.入栈功能测试。 2.出栈功能测试。 3.入队功能测试。 4.出队功能测试。 五、实验报告要求 1.绘制程序实现的流程图。 2.详细给出程序运行测试结果（包括测试数据和测试结果）。 3.选试验步骤1、2中的任意一个，3、4中的任意一个给出程序的详细注释。 4.参考程序中某一部分功能的改进（选做） 5.实验心得与体会 6.附录，实验用源程序 六、参考源程序 顺序栈 #include #define STACKSIZE 50 typedef char DateType; typedef struct { DateType s[STACKSIZE]; int top; }SeqStack; int i; DateType x; void InitSt(SeqStack* st) { st->top=0; cout<<"创建成功!"; } void push(SeqStack *st,DateType x) { if(st->top==STACKSIZE) { cout<<"栈已满!"; } else { st->s[st->top]=x; st->top++; cout<<"入栈成功!"; } } void pop(SeqStack *st) { i=st->top; x=st->s[i-1]; if(st->top==0) { cout<<"栈为空!"; } else { st->top--; cout<<"出栈成功!"; cout<<"出栈元素为:"< } } void readTop(SeqStack *st) { i=st->top; if(st->top==0) { cout<<"栈为空!"; } else { i--; cout<<"栈顶元素为:"< } } void showSt(SeqStack *st) { if(st->top==0) { cout<<"栈为空!"; } else { cout<<"栈中元素为:\n"; for(i=0;i { cout< } } } void main() int i,j; DateType x; SeqStack st; while(j) { cout<<"\n\n\n\n"; cout<<"****************************************************************"< cout<<"***①创建顺序栈②入栈③读栈顶元 ***"< cout<<"***④出栈⑤显示链栈元素⑥退出 ***"< cout<<"****************************************************************"< cin>>i; if(i==1) { InitSt(&st); } else if(i==2) { cout<<"请输入入栈元素:"; cin>>x; push(&st,x); } else if(i==4) { pop(&st); } else if(i==3) { readTop(&st); } else if(i==5) { showSt(&st); } else if(i==6) { j=0; cout<<"程序结束!\n"; } } 链栈： #include #include #include typedef char DateType; typedef struct node { DateType data; struct node* next; }LinkStack; LinkStack *top; void InitStack() { top=(LinkStack*)malloc(sizeof(LinkStack)); top->next=NULL; top->data=0; cout<<"初始化链栈成功!"; } void push(DateType x) { LinkStack* s; s=(LinkStack*)malloc(sizeof(LinkStack)); s->data=x; s->next=top; top=s; cout<<"入栈成功!"; } void pop() { LinkStack* s; s=top; if(s==NULL) { cout<<"栈为空!"; } else { top=s->next; free(s); cout<<"出栈成功"; } void readTop() { if(top==NULL) { cout<<"栈为空!"; } else { cout<<"栈顶元素为:"< } } void showStack() { LinkStack* s; s=top; if(s==NULL) { cout<<"栈为空!"; } else { cout<<"链栈元素为:\n"; cout<<"\t\t\t"; while(s!=NULL) { cout<<" "< s=s->next; } } } void main() { int i,j; DateType x; while(j) { cout<<"\n\n\n\n"; cout<<"****************************************************************"< cout<<"*** ①创建链栈②入栈③读栈顶元 ***"< cout<<"*** ④出栈⑤显示链栈元素⑥退出***"< cout<<"****************************************************************"< cin>>i; if(i==1) { InitStack(); } else if(i==2) { if(top==NULL) { cout<<"请先初始化链表!"; } else { cout<<"请输入要入栈的元素:"; cin>>x; push(x); } } else if(i==3) { pop(); } else if(i==4) { readTop(); } else if(i==5) { showStack(); } else if(i==6) { j=0; cout<<"程序结束\n"; } } } 链队列： #include #include #define TRUE 1 #define FALSE 0 typedef int QElemType; typedef struct LNode { QElemType data; struct LNode *next; }LNode , *LinkList; typedef struct { LinkList front; LinkList rear; }LinkQueue;//链式队列 void InitQueue_L(LinkQueue &Q)//引用做参数，Q为结构体 {//初始化队列 Q.front=Q.rear=new LNode; if(!Q.front) {cout<<"存储分配失败！"< } int IsEmpty(LinkQueue &Q) { if(Q.front==Q.rear) { return TRUE; } else { return FALSE; } } //创建队列，数据元素由键盘输入 void CreateQueue_L(LinkQueue &Q) { QElemType temp; LNode *p; cout<<"输入要插入的队列值（输入-1结束）"< cin>>temp; while(temp != -1) { p=new LNode; p->data=temp; p->next=NULL; Q.rear->next=p; Q.rear=p; cin>>temp; } cout<<"创建成功！"< } //入队操作 int EnterQueue(LinkQueue &Q,QElemType x) {//将数据元素x插入到队列Q中 LNode *NewNode=new LNode; if(!NewNode) {cout<<"存储分配失败！"< { NewNode->data=x; NewNode->next=NULL; Q.rear->next=NewNode; Q.rear=NewNode; cout<<"入队成功！"< return(TRUE); } else return(FALSE); //溢出 } //出队操作 int DeleteQueue(LinkQueue &Q,QElemType &x) {//将队列Q的队头元素出队，并存放到x所指的存储空间中 LNode *p; /*if(Q.front==Q.rear) { cout<<"该队列为空！"< return(FALSE); }*/ p=Q.front->next; x=p->data; Q.front->next=p->next; //队头元素p出队 数据结构上机实验报告 数据结构上机实验报告 1、实验目的 本次实验旨在通过实践，加深对数据结构中各种基本数据结构 和算法的理解，并掌握其应用方法，提高编程实践能力。 2、实验内容 2.1 实验环境 2.1.1 硬件环境： - 计算机配置：操作系统，处理器，内存 - 其他硬件设备：无 2.1.2 软件环境： - 开发工具：版本 - 编程语言：版本 - 其他相关软件：无 2.2 实验任务 2.2.1 任务一、线性表的基本操作实现 - 需要实现线性表的初始化、插入、删除、查找等基本操作。 - 使用自定义的数据结构实现线性表，例如顺序表或链表。 2.2.2 任务二、栈和队列的基本操作实现 - 需要实现栈和队列的初始化、压栈、弹栈、入队、出队等基本操作。 - 使用自定义的数据结构实现栈和队列。 2.2.3 任务三、树和图的基本操作实现 - 需要实现树和图的初始化、遍历、添加节点、删除节点等基本操作。 - 使用自定义的数据结构实现树和图。 2.3 实验步骤 2.3.1 任务一实现步骤： 1、按照实验要求，设计并实现线性表的初始化函数。 2、根据实验要求，编写线性表的插入函数，可以在指定位置插入元素。 3、编写线性表的删除函数，可以删除指定位置的元素。 4、实现线性表的查找函数，可以根据元素值查找对应位置。 2.3.2 任务二实现步骤： 1、设计并实现栈的初始化函数。 2、编写栈的压栈函数，将元素添加到栈顶。 3、实现栈的弹栈函数，将栈顶元素弹出。 4、设计并实现队列的初始化函数。 5、编写队列的入队函数，将元素添加到队尾。 6、实现队列的出队函数，将队首元素出队。 2.3.3 任务三实现步骤： 1、设计并实现树的初始化函数。 2、编写树的遍历函数，可以按照先序、中序、后序等方式遍历树的节点。 3、实现树的添加节点函数，可以在指定节点下添加子节点。 4、编写树的删除节点函数，可以删除指定节点及其子节点。 5、设计并实现图的初始化函数。 6、编写图的遍历函数，可以按照广度优先或深度优先方式遍历图的节点。 7、实现图的添加节点函数，可以添加新的节点。 8、编写图的删除节点函数，可以删除指定节点及其相关边。 实验三树和图应用 一、实验目的 光纤管道铺设施工问题 问题描述 设计校园内有N个教学楼及办公楼，要铺设校园光纤网，如何设计施工方案使得工程总的造价为最省。 二、实验要求 设计校园光纤网铺设的最小生成树模拟程序。 1)采用邻接表或邻接矩阵存储结构。 2)分别采用普利姆算法和克鲁斯卡尔算法实现。 输入形式 对应的教学楼、办公楼数目n，各边权值即每栋楼之间的距离 输出形式 最小生成树，即总路程最小的路 程序功能 设计校园光纤网铺设的最小生成树模拟程序 三、设计概要 流程图 抽象数据类型的定义 class prims { private: int n; //节点的个数 int graph_edge[99][4]; //图的边 int g; //图中边的个数 int tree_edge[99][4]; //树的边 int t; //树的边的个数 int s; //源节点 int T1[50],t1; // 第一部分 int T2[50],t2; //第二部分 public: void input(); int findset(int); void algorithm(); void output(); }; 各程序模块之间的调用关系 四、详细设计 定义prims类 private中进行对图的创建 public: void input(); int findset(int); void algorithm(); void output(); 开始界面 实现prims类中图的初始化 分别输入图中的顶点个数、图的边及其权值 算法构造 t=0;//初始化边的个数为0 t1=1; T1[1]=1; //资源节点 t2=n-1; int i; for(i=1;i<=n-1;i++) T2[i]=i+1; cout<<"\n\n*****运算开始*****\n\n\n"; while(g!=0 && t!=n-1) { int min=99; int p; int u,v,w; for(i=1;i<=g;i++) { if(findset(graph_edge[i][1])!=findset(graph_edge[i][2])) //如果u和v在不同的部分{ if(min>graph_edge[i][3]) { min=graph_edge[i][3]; u=graph_edge[i][1]; v=graph_edge[i][2]; w=graph_edge[i][3]; p=i; } } } for(int l=p;l 数据结构实验报告 课程名称：数据结构 实验项目：线性表、树、图、查找、内排序实验地点：*********************** 专业班级：物联网**** 学号：********* 学生姓名： 指导教师：周杰伦 2014年*月*日 实验一线性表 目的与要求 本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机调试并编译执行通过，并观察其结果，然后独立完成后面的实验内容，写出完整的实验报告。编写程序过程中注意养成良好的编程风格与习惯，要求程序结构清晰，程序缩进，适当注释。 实验仪器 使用的计算机联想：硬件配置cpu-i3等、软件环境win7 实验内容 问题描述： 1．设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。 输入：插入见的顺序表，插入的数，插入后的顺序表 输出：插入前的顺序表，插入的数，插入后的顺序表 存储结构：顺序表存储数据 算法基本思想：这里采用了顺序表来存储数据，主要就是考虑插入的位置是不是在最后一个，如果不是在最后一个，那么就要移动数据了，算法很简单就不在这里的数据都看成是整型的 实验代码 #include 数据结构上机实验报告1 班级：1303028姓名：牛雅祺 1、需求分析 1、问题描述：约瑟夫（joseph）问题的一种描述是：编号为1、 2、…、n的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m。从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列。将他的密码作为新的m的值，从他在顺时针方向上方的下一个人开始重新报数，如此下去，直至所有人全部出列为止。式设计一 个程序求出出列顺序。 2、本演示过程前，首先指定报数上限值，建立循环链表中不需要头结点，注意 空表与非空表的界限。 3、演示过程中输入密码为大于0的正整数，否则无法完成约瑟夫过程。 4、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和输 出结果显示在其后。 5、程序执行的命令包括： (1)创建链表； (2)删除结点； (3)输出出列 顺序； (4)结束。 6、测试数据 m的初值为20；n=7,7个人的密码依次为：3,1,7,2,4,8,4， 首先m的值为6（正确的出列顺序为6,1,4,7,2,3,5）。 2概要分析 （1）抽象数据类型的定义： 为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线性表中。 算法的基本思想：约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。 核心算法主要分为两步： 1、确定需要删除的位置， 2、设置并删除该位置。 已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。 反复进行上述确定位置和删除位置的操作，直到顺序表为空。 （2）主程序的流程： 程序由三个模块组成： （1）输入模块：无提示语句，直接输入总人数n和报数次数m，中间用逗号隔开。 （2）构造链表并输入每个人信息模块： （3）主要处理出列的函数：分别在DOS下和文件中，按移除元素的顺序依 数据结构实验报告 课程数据结构 _ 院系 专业班级实验地点 姓名学号 实验时间指导老师 数据结构上机实验报告1 一﹑实验名称： 实验一——链表 二﹑实验目的： 1.了解线性表的逻辑结构特性； 2.熟悉链表的基本运算在顺序存储结构上的实现，熟练掌握链式存 储结构的描述方法； 3.掌握链表的基本操作（建表、插入、删除等） 4. 掌握循环链表的概念，加深对链表的本质的理解。 5.掌握运用上机调试链表的基本方法 三﹑实验内容： （1）创建一个链表 （2）在链表中插入元素 （3）在链表中删除一个元素 （4）销毁链表 四﹑实验步骤与程序 #include } int PrintLinkList(LinkList &L) {//输出链表L的数据元素 LinkList p; p=L->next; if(L->next==NULL) { cout<<"链表没有元素!"< 一．实验目的 理解存储管理、查找和排序的运用。 二．实验内容 利用多关键字排序进行高考分数处理，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序。 三．实验步骤（可选） 详细程序设计：#include 数据结构上机实验报告 欢迎交流（760135448@https://www.wendangku.net/doc/2c19354718.html,） 2015年11月20日 上机实验一 1．上机实验简介 1）实验目的 当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于异常表达式能给出错误提示。 2）开发工具 C++语言，Microsoft Visual C++ 6.0开发软件 3）测试数据 分别对一位数、多位数以及小数的四则运算进行检验，我选取了下面几个式子： 3+4-5*(12/6)# 100+20*(26/13)# 1.3+3.4-(5.6/1.2)# 正确计算结果应分别为-3.00、140.00与0.03，用所做程序计算并与正确结果比较。 2．算法说明 (1)概要说明：为实现上述程序功能： 1. 首先置操作数栈为空栈，表达式起始符＃为运算符栈的栈底元素； 2. 依次扫描表达式中每个字符，若是操作数则进OPND栈；若是运算符，则 和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求 值完毕。 3. 先做一个适合个位的+-*/运算, 其次就要考虑到对n位和小数点的运算。 (2)程序主要模块 主要模块有：头文件、栈定义及栈函数、运算符判断与优先级比较函数、实现计算函数 { InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S已存在。 操作结果：用P返回S的栈顶元素。 Push(&S，e) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。 Pop(&S，e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素。 In(c) 《空间数据结构基础》上机实验报告（2012级） 姓名 班级 学号 环境与测绘学院 实验一顺序表及其基本操作 【实验简介】学会用算法语言C++描述抽象数据类型，使用模板建立数据结构。了解线性数据结构，掌握顺序存储和链式存储的两种线性表的建立和使用方法。 【实验内容】 《数据结构》书上第二章习题2.12 设有两个整数类型的顺序表A（有m个元素）和B（有n个元素），其元素均以从小到大的升序排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也从小到大排序。 【主要代码】 1．#include 《数据结构》上机实验报告—利用栈实现迷宫求解 实验目的： 掌握栈的基本操作和迷宫求解的算法，并能够利用栈实现迷宫求解。实验原理： 迷宫求解是一个常见的路径问题，其中最常见的方法之一是采用栈来实现。栈是一种先进后出的数据结构，适用于这种类型的问题。 实验步骤： 1.创建一个迷宫对象，并初始化迷宫地图。 2.创建一个栈对象，用于存储待探索的路径。 3.将起点入栈。 4.循环执行以下步骤，直到找到一个通向终点的路径或栈为空： a)将栈顶元素出栈，并标记为已访问。 b)检查当前位置是否为终点，若是则路径已找到，结束。 c)检查当前位置的上、下、左、右四个方向的相邻位置，若未访问过且可以通行，则将其入栈。 5.若栈为空，则迷宫中不存在通向终点的路径。 实验结果： 经过多次实验，发现利用栈实现迷宫求解的算法能够较快地找到一条通向终点的路径。在实验中，迷宫的地图可通过一个二维数组表示，其中0表示可通行的路径，1表示墙壁。实验结果显示，该算法能够正确地找 出所有可行的路径，并找到最短路径。实验结果还显示，该算法对于大型迷宫来说，解决速度相对较慢。 实验总结： 通过本次实验，我掌握了利用栈实现迷宫求解的算法。栈作为一种先进后出的数据结构，非常适合解决一些路径的问题。通过实现迷宫求解算法，我深入了解了栈的基本操作，并学会运用栈来解决实际问题。此外，我还了解到迷宫求解是一个复杂度较高的问题，对于大型迷宫来说，解决时间较长。因此，在实际应用中需要权衡算法的速度和性能。 在今后的学习中，我将进一步加深对栈的理解，并掌握其他数据结构和算法。我还将学习更多的路径算法，以便更好地解决迷宫类问题。掌握这些知识将有助于我解决更加复杂的问题，并提升编程能力。 数据结构上机实验报告 姓名学号 班级指导老师 实验1有两个整数集合采用有序单链表存储，设计尽可能高效的算法求两个集合的并集、交集和差集。并用相关数据进行测试。 【程序代码】 #include { int tmp = array2[i];//对数组2进行交换 array2[i] = array2[j]; array2[j] = tmp; swap = true;//设置标志 break; } } if(swap != true)//第一种情况，没有相同元素存在时，将这个元素交换到尚未进行比较的尾部 { int tmp = array1[i]; array1[i] = array1[--end]; array1[end] = tmp; } else i++; } //结果就是在end表示之前的元素都找到了匹配，而end元素之后的元素都未被匹配 //先输出差集 cout<<"only in array1"< 南京工程学院实验报告 <班级>_<学号>_<实验X>.RAR文件形式交付指导老师。 一、实验目的 1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用 程序1的主要代码(附简要注释) public struct sequenlist { public const int MAXSIZE=1024; /*最大值为1024*/ public elemtype[] vec; public int len; /* 顺序表的长度 */ public sequenlist( int n) { vec=new elemtype[MAXSIZE ]; len = n; } }; class Program { static void Main(string[] args) { sequenlist list1 = new sequenlist(5); for (int i = 0; i < 5; i++) { list1.vec[i] = i; } for (int i = 0; i < 5; i++) 实 验 报 告 一、实验目(de) （1） 掌握线性表(de)基本操作（插入、删除、查找）以及线性表合并等运算在顺序存储结构、链式存储结构上(de)实现.重点掌握链式存储结构实现(de)各种操作. （2） 掌握线性表(de)链式存储结构(de)应用. 二、实验内容与实验步骤 （1）实验内容： 实现约瑟夫环,约瑟夫环（Joseph ）问题(de)一种描述是：编号为1、2、3……n(de)n 个人按照顺时针方向围坐一圈,每人持有一个密码（正整数）.一开始任选一个正整数作为报数(de)上限值m,从第一个人开始按照顺时针(de)方向自1开始顺序报数,报到m 时停止报数.报m(de)人出列,将他(de)密码作为新(de)m 值,从他(de)顺时针方向上(de)下一个人开始重新从1报数,如此下去,直至所有人全部出列为止.设计一个程序求出出列顺序. 课程名称：数据结构 班级： 实验成绩： 实验名称：顺序表和链表(de)应用 学号： 批阅教师签字： 实验编号：实验一 姓名： 实验日期：2017-11-25 指导教师： 组号： 实验时间：18:30~22:30 （2）抽象数据类型和设计(de)函数描述,说明解决设想. 首先定义一个链表,用其中(de)data项存储每个人(de)编号,用password项存储每个人所持有(de)密码,并且声明一个指针.之后使用CreatList_CL函数来创建一个循环链表,在其中(de)data和password中存入编号和密码,最后使最后一个节点(de)net指向L,使其能够形成循环队列.定义了函数Display来显示链表当中(de)内容,以确定存储(de)数据没有错误.定义了函数Delete_L来实现约瑟夫环中依次删除(de)功能,依次比较,如果某个人所持(de)密码和m值相等,则删除这个结点,并且输出此时该结点(de)编号和密码,实现出列(de)功能. （3）简短明确地写出实验所采用(de)存储结构,并加以说明. 该实验我主要采用(de)是线性表(de)链式存储结构,首先定义了链表(de)结构,其中包括data项和password项,分别存储每个人(de)编号和所持密码,还声明了指向下一个结点(de)指针,该指针可以连接各个结点,并且将最后一个结点(de)指针指向第一个结点使之成为一个循环链表. 三、实验环境 操作系统：Windows 7 调试软件名称：Visio Studio2017 上机地点：信息楼B405 四、实验过程与分析 （1）主要(de)函数或操作内部(de)主要算法,分析这个算法(de)时、空复杂度,并说明设计(de)巧妙之处. 数据结构上机实验报告 1. 实验目的 本次实验旨在通过编写程序，掌握和理解常见的数据结构及其应用。 2. 实验环境与工具 - 操作系统：Windows 10 - 开发语言：C++ - 集成开发环境（IDE）：Visual Studio Code 3. 实验内容及步骤 3.1 线性表操作演示程序设计与分析 步骤： a) 设计一个线性表类，并包含以下基本功能： i) 初始化线性表； ii) 插入元素到指定位置； iii) 删除指定位置的元素； iv) 获取指定位置处的元素值。 b）使用该线性表类进行一系列测试，验证各个功能是否正常运行。记录并分析每个函数调用所消耗时间以评估算法效率。 3.2 栈和队列综合应用设计与模拟 步骤: a）根据给出问题需求，在已有栈、队列等相关代码基础上完成如下任务： i）利用两个堆栈来模拟浏览器前进后退功能; ii）使用循环链式存储结构表示双向链队, 并对其进行初始化、入队、出队等操作。 b). 运行以上代码片段，并输出相应结果。同时分析算法的时间复杂度和空间复杂度。 4. 实验结果与讨论 a) 线性表操作演示程序设计与分析实验结果： - 初始化线性表所需时间为X秒； - 插入元素到指定位置平均耗时Y毫秒； - 删除指定位置的元素平均耗时Z毫秒。 b）栈和队列综合应用设计与模拟实验结果： i) 浏览器前进后退功能测试：共浏览N个网页，前进M 次、后退K次。运行总体消耗时间T1; ii) 双向链队初始化、入队、出对等操作测试: 共进行P 组数据处理, 运行总体消耗时间T2. 5. 结论 通过本次上机实验，我们掌握了线性表及其相关基本操作，并且成功完成了栈和队列在特定场景下的应用。同时，在代码编写过程中也深刻理解并评估了各种算法效率。 6. 致谢 感谢老师们给予我宝贵意见以及同学们之间相互交流合作提供支持。 7. 附件 8. 法律名词及注释 在此处添加涉及到的法律名词或术语，并提供简要注释。 数据结构上机实验报告 学院：电子工程学院 专业：信息对抗技术 姓名： 学号： 教师：饶鲜日期： 目录 实验一线性表 ........................................................................................................ - 4 - 一、实验目的.................................................................................................... - 4 - 二、实验代码.................................................................................................... - 4 - 三、实验结果.................................................................................................. - 14 - 四、个人思路.................................................................................................. - 15 - 实验二栈和队列 .................................................................................................. - 15 - 一、实验目的.................................................................................................. - 15 - 二、实验代码.................................................................................................. - 16 - 三、实验结果.................................................................................................. - 24 - 四、个人思路.................................................................................................. - 25 - 实验三数组 .......................................................................................................... - 26 - 一、实验目的.................................................................................................. - 26 - 二、实验代码.................................................................................................. - 26 - 三、实验结果.................................................................................................. - 28 - 四、个人思路.................................................................................................. - 28 - 实验四树 .............................................................................................................. - 29 - 一、实验目的.................................................................................................. - 29 - 二、实验代码.................................................................................................. - 29 - C语言数据结构线性表的基本操作实验报告 实验一线性表的基本操作 一、实验目的与基本要求 1．掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。 2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。 3．掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4．掌握运用C语言上机调试线性表的基本方法。 二、实验条件 1．硬件：一台微机 2．软件：操作系统和C语言系统 三、实验方法 确定存储结构后，上机调试实现线性表的基本运算。 四、实验内容 1．建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 2．建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）4．假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。 五、附源程序及算法程序流程图 1.源程序 （1）源程序(实验要求1和3) #include数据结构上机实验报告
东北大学数据结构上机实验报告3
太原理工大学数据结构实验报告
约瑟夫环数据结构实验报告
数据结构上机实验报告
数据结构上机实验报告15
数据结构上机实验报告
空间数据结构基础实验
《数据结构》上机实验报告—利用栈实现迷宫求解
数据结构上机实验报告
《数据结构》实验1实验报告
东北大学数据结构实验报告
数据结构上机实验报告
数据结构上机实验报告
C语言数据结构线性表的基本操作实验报告