数据结构实验二11180

《数据结构》实验报告模板(附实例)---实验一线性表的基本操作实现实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现，其中以熟悉各种链表的操作为重点。

2、巩固高级语言程序设计方法与技术，会用线性链表解决简单的实际问题。

二、实验内容√ 1、单链表的表示与操作实现 ( * )2、约瑟夫环问题3、Dr.Kong的艺术品三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。

2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。

3、严格按照数据结构实验报告模板和规范，及时完成实验报告。

四、实验步骤（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（成员函数）的伪码算法、函数实现、程序编码、调试与分析、总结、附流程图与主要代码）㈠、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、单链表的结点类型定义/* 定义DataType为int类型 */typedef int DataType;/* 单链表的结点类型 */typedef struct LNode{ DataType data;struct LNode *next;}LNode,*LinkedList;2、初始化单链表LinkedList LinkedListInit( ){ // 每个模块或函数应加注释，说明函数功能、入口及出口参数 }3、清空单链表void LinkedListClear(LinkedList L){// 每个模块或函数应加注释，说明函数功能、入口及出口参数}4、检查单链表是否为空int LinkedListEmpty(LinkedList L){ …. }5、遍历单链表void LinkedListTraverse(LinkedList L){….}6、求单链表的长度int LinkedListLength(LinkedList L){ …. }7、从单链表表中查找元素LinkedList LinkedListGet(LinkedList L,int i){ //L是带头结点的链表的头指针，返回第 i 个元素 }8、从单链表表中查找与给定元素值相同的元素在链表中的位置LinkedList LinkedListLocate(LinkedList L, DataType x){ …… }9、向单链表中插入元素void LinkedListInsert(LinkedList L,int i,DataType x) { // L 为带头结点的单链表的头指针，本算法// 在链表中第i 个结点之前插入新的元素 x}10、从单链表中删除元素void LinkedListDel(LinkedList L,DataType x){ // 删除以 L 为头指针的单链表中第 i 个结点 }11、用尾插法建立单链表LinkedList LinkedListCreat( ){ …… }㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结五、主要算法流程图及程序清单1、主要算法流程图：2、程序清单（程序过长，可附主要部分）说明：以后每次实验报告均按此格式书写。

数据结构实验报告实验名称:实验二一一栈和队学生姓名:申宇飞班级：班内序03号：学号：日期2013年11月18日：1- 实验要求1.1实验目的：通过选择卞面五个题目之一进行实现，掌握如卞内容：>进一步掌握指针、模板类、异常处理的使用>掌握栈的操作的实现方法>掌握队列的操作的实现方法>学习使用栈解决实际问题的能力>学习使用队列解决实际问题的能力1.2实验内容题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。

要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试mainO函数测试线性表的正确性。

2.程序分析2.1存储结构链栈：栈的链式存储结构,其实现原理类似于单链表，结点结构与单链表相同，但链栈在实现时直接采用栈顶指针指向栈顶元素。

第］页北京邮电大学信息与通信工程学院data next栈顶栈底关键算法分析链栈：一、入栈操作算法步骤：自然语言描述：1、建立新结点2、给p结点的数据域赋值3、修改p结点的指针域，将其指向栈顶结点4、栈顶指针指向p结点伪代码描述：1)Node<T> * s = new Node<T>;2)p->data = x;3)p->next = top;4)top = p;二、出栈操作算法步骤：自然语言描述：1、判断栈是否为空2、保存栈顶结点的数据域3、定义指针p指向栈顶结点4、栈顶指针指向下一个结点5、释放p结点伪代码描述：1)if(EmptyO)throw" F溢“；2)T x = top->data;3)Node<T> * p = top;4)top = top->next;5)elete p;三、链栈的取栈顶元素算法步骤：自然语言描述：1、判断栈是否为空第3页2、定义指针p指向栈顶结点3、返回栈顶元素的值，不删除伪代码描述1)if(EmptyO)tlu'ow H卜溢"；2)Node<T>*p=top;3)cout«p->data;四、遍历链栈元素算法步骤：自然语言描述：1、定义指针p指向栈顶结点2、判断栈是否为空3、返回栈元素的值4、把下一个指针的值赋给p 伪代码描述：1)Node<T>*p = top;2)while(p !=NULL)3)cout« p->data ;4)p = p->next;五、析构函数算法步骤：自然语言描述：1、判断栈顶指针是否为空2、定义指针p指向栈顶结点3、把下一个指针的值赋给栈顶指针4、释放要释放的指针伪代码描述：1)while(top)2)strnct Node <T> * p = top;3)top = top->next;4)deletep; 时间复杂的：0(1)。

实验2 线性表课程实验共安排8个难度各易的实验，训练重点在于掌握基本的数据结构，而不强调面面俱到。

通过实验，掌握抽象数据类型的概念和基本数据结构，掌握各种数据结构内在的逻辑关系，各种数据结构在计算机中的存储表示，基于各种数据结构上的基本运算、算法实现及算法分析。

●实验目的(1) 掌握用Turbo C 2.0上机调试线性表的基本方法。

(2) 掌握线性表基本操作，如：插入、删除、查找、线性表合并等运算在顺序存储结构和链式存储结构上的运算。

●实验内容1. 线性表基本操作的实现[问题描述] 当要在线性表顺序存储结构上的第i个位置上插入一个数据元素时，必须首先将线性表中第i个元素之后的所有数据元素依次后移一个位置，以便腾空一个位置；再把新元素插入到该位置上。

当要删除第i个数据元素时，也必须把第i个元素之后的所有数据元素前移一个位置。

[基本要求] 要求生成线性表时，可从键盘上读取元素，用顺序和链式存储结构实现存储；要求插入和删除之后输出线性表。

2. 约瑟夫环问题[问题描述] 设有n个人围坐在一圈，现在从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出现了；如此下去，直到所有人都出列为止，试设计确定他们出列次序序列的程序。

[基本要求] 选择单向循环链表作为存储结构，模拟报数过程，并且依次输出出列每个人的编号。

3. 一元多项式简单计算[问题描述] 设计一个一元多项式简单的计算器。

[基本要求] 一元多项式简单计算器的基本功能是：(1) 输入并建立多项式；(2) 输出多项式；(3) 两个多项式相加、相减、相乘，建立并输出多项式。

●实验要求(1) 认真分析题目。

(2) 进行算法设计。

(3) 编写程序代码(4) 上机调试程序。

(5) 保存和打印出程序的运行结果，并结合程序进行分析。

浙江师范大学实验报告学院：数理与信息工程学院专业：计算机科学与技术姓名：杨富生学号： 201531910137课程名称：数据结构指导教师：钟发荣实验时间： 2016-06-152016年6月15日实验一1.实验要求1.1掌握数据结构中线性表的基本概念。

1.2熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构上的实验。

2.实验内容2.1编写一个函数，从一个给定的顺序表A中删除元素值在x到y之间的所有元素，要求以较高效率来实现。

#include<stdio.h>typedef int elemtype;#define maxsize 10int del(int A[],int n,elemtype x,elemtype y){int i=0,k=0;while(i<n){if(A[i]>=x&&A[i]<=y)k++;elseA[i-k]=A[i];i++;}return(n-k);}void main(){int i,j;int a[maxsize];printf("输入%d个数:\n",maxsize);for(i=0;i<maxsize;i++)scanf("%d,",&a[i]);j=del(a,maxsize,1,3);printf("输出删除后剩下的数:\n");for(i=0;i<j;i++)printf("%d "\n,a[i]);}2.2试写一个算法，在无头结点的动态单链表上实现线性表插入操作INSERT(L,i,b)。

void Insert(Linklist &L,int i,elemtype x){if(!L){L=(Linklist)malloc(sizeof(Lnode));(*L).data=x;(*L).next=NULL;}else{if(i==1){s=(Linklist)malloc(sizeof(Lnode));s->data=x;s->next=L;L=s;}else{p=L;j=1;while(p&&j<i-1){j++;p=p->next;}if(p||j>i-1)return error;s=(Linklist)malloc(sizeof(Lnode));s->data=x;s->next=p->next;p->next=s;}}}2.3生成两个多项式PA和PB，求他们的和，输出“和多项式”。

数据结构实验报告实验名称:学生姓名:班级:班内序号:学号:日期:一．实验描述: 利用栈结构实现八皇后问题。

二．八皇后问题19世纪著名的数学家高斯于1850年提出的。

他的问题是：在8*8的棋盘上放置8个皇后, 使其不能互相攻击, 即任意两个皇后都不能处于同一行、同一列、同一斜线上。

请设计算法打印所有可能的摆放方法。

三．程序分析1.存储结构: 栈2.关键算法分析:a)比较函数: 比较某两个皇后是否在同一横、竖、斜线上。

行数:a和b。

列数:row[a]和row[b]。

主对角线数:(a+row[a])和(b+row[b])。

副对角线数:(a+7-row[a])和(b+7-row[b])。

b)八皇后实现（非递归）:放置每一行的皇后时, 考虑其与已放好的之前行是否存在矛盾, 并作出相应的退栈、进栈或改变位置的反应。

放置完8行后, 计算下一个解。

当最后取得的解与第一个解重复时, 已取得全部解, 结束程序。

3.代码详细分析:#include<iostream>using namespace std;bool CompArray(int a[],int b[],int n)//用来比较两组解是否相等的函数{bool e=1;for(int i=0;i<n;i++){if(a[i]!=b[i])e=0;}return e;}class Stack //栈{public:Stack();void Push(int n);void Pop();bool Compare(int a,int b);void EightQueen();private:int row[8];//row[i]代表第i行皇后的列数是row[i], 因为八皇后不同行, 所以每行都有且只有一个皇后int top;};Stack::Stack() //置空栈{top=-1;}void Stack::Push(int n) //压栈函数{row[++top]=n; //int n进栈, top指针+1}void Stack::Pop() //退栈函数{top-=1; //top指针-1}bool Stack::Compare(int a,int b) //比较函数, 比较某两个皇后是否在同一行、列或对角线上{return row[a]==row[b]||(a+row[a])==(b+row[b])||(a+7-row[a])==(b+7-row[b]);} /*输入的行数a和b本来就不相等比较列数row[a]和row[b]是否相等比较主对角线数(a+row[a])和(b+row[b])是否相等比较副对角线数(a+7-row[a])和(b+7-row[b])是否相等bool输出0表示以上均不相等*/void Stack::EightQueen() //八皇后判断函数{int count=0; //计数量, 计解的个数int a[8]; //存储数组, 存储第一个解以便比较while(1) //控制每次进栈的大循环{Push(0);//为当前指针所指的下一位进栈0, 表示上一行皇后位置判断完成, 进入下一行判断loop:for(int j=0;j<top;j++)//将当前指针所在行与之前每一行进行对比, 以判断本行当前列是否可放置皇后的比较循环{if(Compare(top,j)!=0){row[top]++;//如果有任何一次比较的结论是不可放置, 本行的列数+1while(1)//如果列数+1之后超出8列, 则退栈, 给上一行列数加1, 如再超列再退栈, 以此类推{if(row[top]>7){Pop();row[top]++;}else break;}goto loop;//进行下一次比较循环}}if(top==7)//如果top=7, 说明已经判断完了第8行, 可以输出解{if(count==0)//用a[]记录第一个解{for(int i=0;i<8;i++){a[i]=row[i];}}else{if(CompArray(a,row,8)==1)break;//当再次求出的解与第一个解相同时, 说明已经输出了全部的解, 将不再输出}count++;//解的计数量+1cout<<"第"<<count<<"个解:"<<endl;//输出解for(int i=0;i<8;i++){cout<<"第"<<i+1<<"个皇后在第"<<i+1<<"行, 第"<<row[i]+1<<"列"<<endl;}cout<<endl;row[top]++;//本次求解后, 给第8行列数+1, 以进行下一次求解while(1)//超列则当前位列数置零, 退栈后列数+1{if(row[top]>7){row[top]=0;row[--top]++;}else break;}goto loop;//进入比较循环, 开始下一次求解}}}main(){Stack S1;S1.EightQueen();}a） 4.时间复杂度计算: (皇后数为n,解的个数为m)某一行取某个值时与之前每行比较: O(n)。

2023年408数据结构题目二：1. 题目描述：在2023年408数据结构考试中，第二题要求考生使用C++语言实现一个双向链表，包括双向链表的初始化、插入、删除、查找等基本操作，并且要求实现双向链表的倒序输出功能。

2. 解题思路：在解决这道题目时，我们首先需要了解什么是双向链表，双向链表是一种链表结构，每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。

双向链表的插入和删除操作比较灵活，可以在节点之间进行插入和删除操作。

我们可以通过使用C++语言来实现双向链表的结构，定义一个节点类来表示链表的节点，包含数据域和指针域，然后实现双向链表的初始化、插入、删除和查找操作。

3. 实现过程：我们需要定义一个节点类：```c++class Node {public:int data;Node *prev;Node *next;Node(int data) {this->data = data;this->prev = nullptr;this->next = nullptr;}};```我们可以定义一个双向链表类，包含双向链表的初始化、插入、删除和查找操作：```c++class DoublyLinkedList {private:Node *head;Node *tail;public:DoublyLinkedList() {head = nullptr;tail = nullptr;}void insert(int data) {Node *newNode = new Node(data); if (head == nullptr) {head = newNode;tail = newNode;} else {tail->next = newNode;newNode->prev = tail;tail = newNode;}}void delete(int data) {Node *current = head;while (current != nullptr) {if (current->data == data) {if (current == head) {head = current->next;head->prev = nullptr;} else if (current == tail) {tail = current->prev;tail->next = nullptr;} else {current->prev->next = current->next; current->next->prev = current->prev; }delete current;break;}current = current->next;}}Node* search(int data) {Node *current = head;while (current != nullptr) {if (current->data == data) {return current;}current = current->next;}return nullptr;}};```接下来，我们需要实现双向链表的倒序输出功能，可以通过递归或者栈来实现：```c++void reversePrint(Node *current) {if (current == nullptr) {return;}reversePrint(current->next);std::cout << current->data << " ";}```4. 总结：通过以上步骤，我们可以完成2023年408数据结构考试中第二题的要求，实现了双向链表的初始化、插入、删除、查找以及倒序输出功能。

引言概述正文内容
1.实验环境配置
1.1硬件要求
计算机硬件配置要求
操作系统要求
附加硬件设备要求（如虚拟机等）
1.2软件要求
编程语言要求（如C/C++、Java等）开发环境配置（如IDE、编译器等）1.3实验库和工具
实验需要使用的库文件和工具
如何获取和配置实验库和工具
2.实验内容介绍
2.1实验目标和背景
数据结构实验的作用和意义
实验背景和相关应用领域介绍
2.2实验概述
实验内容的大致流程和步骤
实验中可能遇到的问题和挑战
2.3实验要求
对学生实验流程和实验结果的要求
实验过程中需要注意的事项和技巧
3.实验步骤
3.1实验准备
配置实验环境
获取实验所需数据和文件
3.2实验具体步骤
根据实验要求将数据结构知识应用到具体问题中根据实验要求实现相应的算法和数据结构
3.3实验示例代码
提供示例代码以供学生参考和学习
解析示例代码中的关键步骤和实现细节
4.实验答案
4.1实验题目
实验题目及相关说明
确定实验的具体要求和目标
4.2实验答案解析
对实验答案的具体实现进行解析
对实验中可能遇到的问题和错误进行分析和解决4.3实验答案示例
提供实验答案的示例代码
解析实验答案中的关键实现步骤和说明
5.实验总结
5.1实验成果评估
对学生实验成果进行评估
分析实验结果的优点和不足
5.2实验心得
学生对本次实验的收获和感想
学生对未来实验的建议和展望
总结。