第一篇：数据结构实践报告
20XX 报 告 汇 编 Compilation of reports
数据结构实践报告
学
号：
150906112
姓
名：
武锦蓉
班
级：
NET2 班
指导老师：
田喜平
时
间：
2022-12-21
报告文档·借鉴学习word 可编辑·实用文档
项目名称
一、项目构思 程序由三个模块组成：
（1）输入模块：无提示语句，直接输入总人数 n 和报数次数 m，中间用逗号隔开。
（2）处理模块：将元素储存于顺序表中。在主函数中根据报数间隔确定需要删除的元素的位置，在顺序表中设置该位置并删除该位置，同时输出该位置的值。反复设置并删除直到表空。
（3）输出模块：分别在 DOS 下和文件中，按移除元素的顺序依次显示其位置。
约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。
核心算法主要分为两步：
1、确定需要删除的位置，2、设置并删除该位置。
已知报数间隔 m，我们可以把当前位置加上 m 获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。
反复进行上述确定位置和删除位置的操作，直到顺序表为空。
程序主要功能模块 1、输入的形式和输入值的范围：
每一次输入的值为两个正整数，中间用逗号隔开。
若分别设为 n,m，则输入格式为：“n,m”。
不对非法输入做处理，即假设输入都是合法的。、输出的形式：
输出格式 1：在字符界面上输出这 n 个数的输出序列 输出格式 2：将这 n 个数的输出序列写入到文件中、程序所能达到的功能：
对于输入的约瑟夫环长度 n 和间隔 m，输出约瑟夫环的出列顺序。、测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。
正确：
输入：10,3
输出：3 6 9 2 7 1 8 5 10 4
报告文档·借鉴学习word 可编辑·实用文档
输入：41,3 输出：3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31
错误：
输入：10 3 输出：6 8 7 1 3 4 2 9 5 10 二、程序清单 1、抽象数据类型的定义：
为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线性表中。线性表 ADT 定义如下：
ADT list 数据对象：整形 数据关系：线性关系，即(0≤a＜n)。
基本操作：
bool remove(int &elem)//移除一个元素，被移除的元素赋给 elem
//如果操作成功，返回 true,否则返回 false
bool isEmpty()//判断数组的元素是否清空，空返回 true,否则返回false
bool setPos(int place)//设置当前元素的位置，设置成功返回 true,否则返回 false
int getLength()//获取数组的实际长度、各程序模块之间的层次（调用）关系：
主函数会按设计的方法调用顺序表中“获取实际长度”、“设置需要删除元素的位置”、“移除该位置元素”和“判断是否为空表”四种方法方法，使元素依次出列，并正确结束程序。
用整形存储用户输入的整数。
用顺序表实现线性表：
class AList {
private:
int *listArray;//指向数组的指针
int realSize;//数组中含有元素的实际长度
报告文档·借鉴学习word 可编辑·实用文档
int fence;//指向当前元素下标
public:
AList(int s)//构造函数，初始化数组
{
listArray=new int[s];
for(int i=0;i
listArray[i]=i 1;//数组值等于数组下标 1
realSize=s;
fence=0;//指向首元素
}
bool remove(int &elem)//移除一个元素
{
if(isEmpty())return false;//如果数组为空返回 false
elem = listArray[fence];
for(int i=fence;i
{
listArray[i]=listArray[i 1];
}
realSize--;
return true;
}
bool isEmpty()//判断数组的元素是否清空
{
if(realSize==0)return true;
else return false;
}
bool setPos(int place)//设置当前元素的位置
{
if(place>=0&&place<=realSize)
{
fence=place;
return true;
}
return false;
}
报告文档·借鉴学习word 可编辑·实用文档
int getLength()//获取数组长度
{
return realSize;
}
};
在主函数中调用上述模块的方法：
ofstream fout;//文件流
fout.open(“C:Josephus.txt”);//设置文件路径
int n,m,elem,point=0;
scanf(“%d,%d”,&n,&m);//获得用户输入
AList alist(n);//创建顺序表对象
while(!alist.isEmpty())//如果顺序表不为空，继续删除
{
m=m%alist.getLength();//调整计数的长度
if(m==0)m=alist.getLength();
if(point m-1
else{point=point m-alist.getLength()-1;}
alist.setPos(point);//设置当前需要删除的位置
alist.remove(elem);//删除元素
cout<
fout<
四、测试结果（截图显示）
报告文档·借鉴学习word 可编辑·实用文档
五、遇到的问题及解决方法 1、初始化部分为循环赋值，时间复杂度为Θ(n)。
2、处理部分，我为了提高效率没有采用循环寻找的方法，直接利用数学关系通过当前位置获得下一位置，因此对于长度为 n 的约瑟夫环，只做了 n 次定位，每次定位的复杂度为Θ(1)，所以时间复杂度为Θ(n)。
但是用顺序表实现时，每次其移除的方法是时间复杂度为Θ(k)的(k 与实际长度有关)，所以处理部分总的结果是(2)1(n n )的，化简后时间复杂度仍然为Θ(n 2)。
综上，该算法的时间代价为Θ(n 2)。
（PS：如果是用循环查找，在 n 次定位中每次都使用了 m 次的循环，至少是Θ(n*m)，然后再用顺序表的移除方法，总的复杂度应该是Θ(m*n 2)的。）
事实上要用线性表来完成这道题，其复杂度最好也是Θ(n 2)的，毕竟对于 n个数据，每个都要进行时间复杂度为Θ(n)的删除工作。欲到达Θ(n)的效率除非不用线性表来实现。
六、体会
输入人数 n,报数间隔 m，创建顺序表对象。
报告文档·借鉴学习word 可编辑·实用文档
主程序
输入和输出的格式：
输入：10,3 输出：3
10（文本中的输出）：3
！isEmpty()//顺序表不为空 确定需要删除的位置
Remove（）//调用删除方法
第二篇：南航计算机软件数据结构上机实践报告
数据结构实践报告整理 031040102 刘玉 简述每一部分的对象、目的和要求；
画出程序流程图；另附A4纸手绘； 附源程序清单； 实验的收获：遇到的问题以及解决的办法、方法的优缺点。
实验一 单链表的基本操作与运算
题目一：单链表的定义、创建、插入和删除操作，将数据元素显示出来。
本题目针对单链表。联表示通过一组任意的存储单元来存储线性表格中的数据元素。为了建立起数据元素之间的存储关系，设置每一个结点，结点既存放数据data，又存放其后继地址的部分next。而每个结点中只有一个指向后继的指针，所以称其为单链表。本题目的要求是创建一个新的链表，并且完成链表的创建定义。链表是一种动态管理的存储结构，链表中的每一个结点所占用的空间是根据运行是的实际需要的空间生成的。因此建立单链表是从空链表开始的，每次读入一个数据元素就申请一个结点链表的一段。在单链表中插入一个结点不需要移动元素指针的指向。而删除则需要找到木比啊偶元素的前驱结点，并且修改指针的指向。题目一需要的操作就是，对于一个新建的空链表，以其为对象进行具体的数据的插入填写。待链表中存有数据后，再进行数据的整理查找，然后删除目标数据。
//031040102单链表 #include
//定义一个链表 { int data;SLNODE *next;};void CREATE_SL(SLNODE *h)//创建一个单链表 { SLNODE *p,*s;int x;h->next=NULL;
cout<<“输入以-1结尾的一组数”<
cin>>x;
//开始输入数据
while(x!=-1)
{
s=new SLNODE[sizeof(SLNODE)];
//申请一个动态新空间
s->data=x;
if(h->next==NULL)
h->next=s;
else
p->next=s;
p=s;
cin>>x;
}
p->next=NULL;
//链表最后指向空 };int Insert_LinkList(SLNODE *h,int i,int x)
//在单链表第i个位置插入x {
SLNODE *p,*s;int j=0;
p=h;while(p->next!=NULL&&j
{
p=p->next;
j ;
}
if(j!=i-1){
cout<<“i is invalid!”<
return 0;}
else {
s=new SLNODE[sizeof(SLNODE)];
s->data=x;
s->next=p->next;
p->next=s;
return 1;
} };int Del_LinkList(SLNODE *h,int i)
//删除单链表上第i个结点 {
SLNODE *p,*s;int j=0;p=h;while(p->next!=NULL&&j
p=p->next;j ;
} if(j!=i-1){
cout<<“i is invalid!”<
return 0;4 6 8 9 7 2 6 9 7 5-1 } 链表数据如下
else 4 6 8 9 7 2 6 9 7 5 { 输入需插入的数据8
if(p->next==NULL)输入需插入的结点3
{ 插入成功
cout<<“第i个结点不存在链表数据如下 ”<
return 0;输入需删除的结点 4
} 删除成功
else 链表数据如下
{s=p->next;p->next=s->next;
7 2 6 9 7 */
//删除结点
Deletes;
//释放结点空间
return 1;
} } };void Print_LinkList(SLNODE *h)//输出链表中所有元素
{ SLNODE *p;p=h->next;cout<<“链表数据如下”<
cout<
data<<'t';} cout<
data<
cout<<“插入成功”<
cout<<“插入失败”<
cout<<“删除成功”<
cout<<“删除失败”<
实验一的收获
实验一让我对于链表的创建于定义有了更多的接触与认识。之前的学习经验里主要是 扎实，VC ，涉及链表的内容，我学的不够所以这次在软件基础时间里重新再次
学习。题目一比较简单，设仅是创建和插入以及删除的基本操作。实验一的困难较小，我也是比较顺利参照课本，完成体题目一，也让我对于进一步学习链表有了兴趣和动力。由浅入深，我会一点点开展学习。在图书馆借阅一本《数据结构教程上机实验指
导》，里面对于实验的指导比较全面而且有很多实例可以参考。
上机实践二 题目二：栈、队列的顺序存储结构、链式存储结构的定义、创建、插入和删除操作，将数据元素显示出来。本题目要求掌握栈和列队。栈和列队是
两种常见的数据结构。它们的逻辑结构和线性表相同。其特点是，插入和删除等运算的位置有所限制：栈是按照先进后出的规则进行操作，而是按照先进先出的规则进行操作。堆栈技术现在的应用非常广泛，不管是编译软件还是程序设计，在操作系统和事务管理中则是广泛应用了队列技术。栈是限制在一段进行插入和删除的线性表，允许插入删除的这一端称为栈顶，固定端称为栈底。栈是运算受到限制的一种线
性表，采用顺序存储的是顺序栈，采用链式存储的是链栈。题目要求对于两种存储结构
的栈进行定义创建。对于顺序栈，首先需要申请共享的一位数组空间。即为先置空栈，然后入栈插入元素（特别要注意栈满不能插入），删除出栈（特别要注意栈空不能出栈）。对于链栈，采用带头指针的单链表来实现.队列操作的顺序队列，插入在表的队尾一端，删除在表的另外的队头一端。队的队头和队尾都是活动的，特别地需要设置队头和队尾两个指针。需要实现置空队、入队、出对、以及判别队列是否为空的运算。对于链式队列，通常是用带头结点的单链表实现的，并且设置一个队头指针（始终指向头结点）和一个队尾指针（指向当前的最后一个元素），特别地，当队列为空时队头和队尾指针均指向头结点。显示创建一个带头结点的空队，申请头尾结点，然后进行如对操作不断申请新的结点，还需要进行队列是否为空的判断操作，队空则出队失败。
//031040102 顺序栈 #include
return 1;else
return 0;};int Push_SeqStack(SqStack *s,ElemType x)//入栈 { if(s->top==MaxSize-1)
return 0;else {
s->top ;
s->data[s->top]=x;
return 1;
}
};int Pop_SeqStack(SqStack *s,ElemType x)
//出栈
{ if(IsEmpty_SeqStack(s))
return 0;else
{
x=s->data[s->top];
s->top--;
return 1;
}
};
ElemType Top_SeqStack(SqStack *s)
//取出栈顶元素 {
if(IsEmpty_SeqStack(s))
return 0;
else
return(s->data[s->top]);
};void Print(SqStack *s)
//输出栈内所有元素 {
if(IsEmpty_SeqStack(s))
cout<<“
此栈为空
”<
cout<<“栈内元素为”<
for(int i=s->top;i>-1;i--)
cout<
} };void main(){ SqStack *s;int x;
s=Init_SeqStack();cout<<“
输入一组以-1结尾的数”<
s->top ;
s->data[s->top]=x;
cin>>x;} Print(s);cout<<“输入需插入的数”<
cout<<“插入成功”<
cout<<“插入失败”<
Print(s);
delete p;if(Pop_SeqStack(s,x))
return top;
cout<<“删除成功”<
cout<<“删除失败”<
Print(s);} 输入一组以-1结尾的数 5 8 9 7 3 6 2 1 8-1 栈内元素为 8 1 2 6 3 7 9 8 5 输入需插入的数4 插入成功 栈内元素为 4 8 1 2 6 3 7 9 8 5 删除成功 栈内元素为 8 1 2 6 3 7 9 8 5 //031040102 链栈 #include
//定义一个链栈 { elemtype data;LinkStack *next;};LinkStack *Init_LinkStack()//链栈的初始化 { LinkStack *top;top=new LinkStack[sizeof(LinkStack)];top=NULL;return top;};LinkStack *Push_LinkStack(LinkStack *top,elemtype x)
//数据入栈 { LinkStack *s;s=new LinkStack[sizeof(LinkStack)];s->data=x;s->next=top;top=s;return top;};LinkStack *Pop_LinkStack(LinkStack *top,elemtype x)
//数据出栈 { LinkStack *p;if(top==NULL)
return NULL;else {
x=top->data;
p=top;
top=top->next;//输出栈内所有元素 { LinkStack *p;p=top;if(p==NULL)
cout<<“此栈为空”<
cout<<“栈内元素为”<
for(;p->next!=NULL;p=p->next)
cout<
data<<'t';
cout<
data<
s=new LinkStack[sizeof(LinkStack)];
s->data=x;
s->next=top;
top=s;
cin>>x;} Print(top);cout<<“输入需插入的数”<
输入需插入的数15 栈内元素为 15 65 23 1 6 3 4 8 9 7 栈内元素为 65 23 1 6 3 4 8 9 7
//031040102 顺序队列 #include
typedef struct queue //定义一个顺序队列 { ElemType data[MaxSize];int rear,front;}SeQueue;SeQueue*Init_Queue()//队列的初始化 { SeQueue *sq;sq=new SeQueue[sizeof(SeQueue)];sq->front=sq->rear=-1;return sq;};int IsEmpty_Queue(SeQueue *sq)//判空队列 { if(sq->rear==-1)
return 1;else
return 0;};int In_Queue(SeQueue *sq,ElemType x)
//入队 { if(sq->rear==MaxSize-1)
return 0;else {
sq->rear ;
sq->data[sq->rear]=x;
return 1;} };int Out_Queue(SeQueue*sq)
//出队 { if(IsEmpty_Queue(sq))
return 0;else {
sq->front ;
return(sq->data[sq->front]);} };int Front_Queue(SeQueue *sq)//读队头元素 { if(IsEmpty_Queue(sq))
return 0;else {
return(sq->data[sq->front 1]);} };void Print(SeQueue *sq)//输出队列所有元素 { if(IsEmpty_Queue(sq))
cout<<“此队列为空”<
cout<<“队列内元素为”<
for(int i=sq->front 1;i<=sq->rear;i )
cout<
cout<
cin>>x;while(x!=-1){
sq->rear ;
sq->data[sq->rear]=x;
cin>>x;} Print(sq);cout<<“输入需插入的数”<
cout<<“插入成功”<
cout<<“插入失败”<
cout<<“删除成功”<
cout<<“删除失败”<
//定义链队的结点类型 {
ElemType data;QNODE *next;};
typedef struct linkqueue
p=q->front->next;
//封装头尾指针
if(IsEmpty_LQueue(q)){
cout<<“此栈为空”<
cout<<“
队列内元素为
”<
{
for(;p->next!=q->rear->next;p=p->next)LinkQueue *q;
cout<
data<<'t';QNODE *p;
cout<
data<
} //申请头尾节点
p=new QNODE[sizeof(QNODE)];//申请链队头结点
p->next=NULL;q->front=q->rear=p;return q;};void In_LQueue(LinkQueue *q,ElemType x)//入队操作 {
QNODE *p;p=new QNODE[sizeof(QNODE)];//申请新结点
p->data=x;p->next=NULL;q->rear->next=p;q->rear=p;};int IsEmpty_LQueue(LinkQueue *q)//判队空 { if(q->front==q->rear)
return 1;else
return 0;};int Out_LQueue(LinkQueue *q,ElemType x)//出队操作 { QNODE *p;if(IsEmpty_LQueue(q))
return 0;else {
p=q->front->next;
q->front->next=p->next;
x=p->data;
delete p;
if(q->front->next==NULL)
//一个元素时，出队后队空还要改队尾指针
q->rear=q->front;
return 1;} };void Print(LinkQueue *q){ QNODE *p;};
void main(){ LinkQueue *q;QNODE *s;int x;
q=Init_LQueue();cout<<“输入一组以-1结尾的数”<
{
s=new QNODE[sizeof(QNODE)];
s->data=x;
s->next=NULL;
q->rear->next=s;
q->rear=s;
cin>>x;
}
Print(q);cout<<“输入需插入的数”<
cout<<“删除成功”<
else
cout<<“删除失败”<
队列内元素为 8 9 4 5 3 2 1
实验二的收获
实验二是全新的知识需要理解。在之前的学习经历中没有接触到栈和队列。所以这
次是从概念开始学习的。在具体程序的学习应用时候，我对于书上提到的，首先需要的是为栈申请共享空间，有了理解和认识。特别地，在栈空的时候有s->top[0]==-1;s->top[1]==Maxsize。再有就是栈满的时候不可以入栈操作，未满的入栈操作则是先移动再赋入值。例如语句(两句的顺序不可以颠倒)s->top ;s->data[s->top]=x;由于栈的主要运算是在栈顶插入、删除。因此我在链表的头部作为栈顶，这样方便了程序，而且不需要像单链表一样为了运算方便附加一个头结点。在联系队列的相关程序时候，我理解了，列队单向空间无法利用，即为前面的已经被指针制动过的空间不能释放也无法利用。除此，队列的操作里面。有可能出现“队满”“队空”的条件相同，front==rear;需要具体区分。
上机实践三
题目三：二叉树的链式存储结构的数据结构定义、创建、先序和后序遍历，并将结果序列输出。
二叉树是有限个元素的集合，该集合或者为空、或者由一个称为根的元素以及两个不相交的、被称为左子树右子树的二叉树组成。二叉树的脸是存储结构是指，用链表来表示一颗二叉树，即用链表来表示元素的逻辑关系。二叉树的链表存储的结点有三个域组成，除了数据域外，还有两个指针域，分别用来指向该节点的左子结点和右子结点的存储地址。当左子结点或者右子结点不存在的时候，相应的指针值域为空。二叉树的遍历是指按照某种顺序结构访问二叉树的每个结点，使每个结点仅被访问一次。限定先左后右，只有三种方式即为先序遍历、中序遍历、后序遍历。遍历其实是一个递归的过程，若二叉树为空，则遍历结束，不然就按照顺序依次访问根结点、左结点、右结点。
//031040102 二叉树 #include
//定义二叉树结点 { elemtype data;
BiTNode *lchild,*rchild;//两结点指针
}BiTree;
BiTree *Create()//二叉树的创建,递归算法 { BiTree *bt;elemtype ch;cin>>ch;if(ch=='0'){
bt=NULL;} else {
bt=new BiTNode[sizeof(BiTNode)];
bt->data=ch;
bt->lchild=Create();
bt->rchild=Create();} return bt;};
void PreOrder(BiTree *bt)
//先序遍历二叉树，递归算法 { if(bt==NULL)
return;cout<
void PostOrder(BiTree *bt)
//先序遍历二叉树，递归算法 { if(bt==NULL)
return;PostOrder(bt->lchild);PostOrder(bt->rchild);cout<
void main(){ BiTree *bt;cout<<“输入所需字符（空结点以零代替）”<
输入所需字符（空结点以零代替）frt0e000qj00m00
先序遍历可得二叉树元素为 f r t e q j m 后序遍历可得二叉树元素为 e t r j m q f
实验三的收获
二叉树可以用计算机语言来读取，通过遍历可以恢复二叉树。通过这次试验更加深刻理解二叉树。本体操作不断调用函数，递归实现遍历。实际需要的时候对于已知的二叉树的每个结点逐一访问。一次完整的便利科室的一个二叉树的结点信息由非线性排列转变为意义上的线性排列。在二叉树的链表中无法根据结点找到其父结点。不过，二叉树的链表结构灵巧简便、操作方便。特别地还节省空间。对于一个庞大的工程型程序的话，空间与简便十分重要。同样的目的，同样的结果，需要比较选择，肯定是精巧简单操作性强等等优势作为判断取舍。
上机实践四
题目四：查找：顺序查找、二分查找
查找是许多程序中最为耗费时间的部分。因此需要方法提高运行的速度和效率。顺序查找又称为线性查找，也是最为基本的查找方法之一。具体实现为：从表的一端开始，依次将关键码与给定的值比较，若找到查找成功，并且给出数据元素在表中的位置，若整个表查找完成仍未找到相同的关键码，则查找失败给出失败信息。
二分法查找只适用于顺序存储的有序表。有序表即是表中数据元素按照关键码的升序或者降序排列。去中间元素作为比较对象，若给定值与中间元素的关键码相等，则为查找成功；若给定值小于中间元素的关键码，则在中间元素的左半区继续查找，若给定值大于中间元素的关键码，则在中间元素的右半区继续查找。不断重复上述的查找过程直到查找成功，或者所查找的区域，没有该元素查找失败。
//031040102顺序查找 #include
#define MaxSize 1024 typedef struct { KeyType key;
//定义关键码字段
ElemType elem;//定义其他字段 }elemtype;
typedef struct
//顺序存储结构定义 { elemtype elem[MaxSize];//定义数组
int length;
//表长度 }S_TBL;
S_TBL *Init_S_TBL()
//顺序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;};
int s_search(S_TBL *tbl,KeyType kx)//在表tbl中查找关键码为kx的数据元素 { tbl->elem[0].key=kx;
//存放检测
for(int
i=tbl->length;tbl->elem[i].key!=kx;i--);
//从表尾向前查找
return i;};
void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“输入一组以-1结尾的数(关键码字段)”<
tbl->length ;
i=tbl->length 1;
tbl->elem[i].key=k;
cin>>k;} i=1;cout<<“输入一组以-1结尾的数(数据元素)”<
tbl->elem[i].elem=k;
i ;
cin>>k;} cout<<“请输入所需查找数的关键码字段：”<
{
flag=mid;
cout<<“查找成功”<
break;
cout<<“所查找的数为//查找成功，元素位置设置到flag中 ”<
} } } else return flag;
cout<<“查找失败”<
//定义关键码字段
ElemType elem;
//定义其他字段 }elemtype;typedef struct
//顺序存储结构定义 { elemtype elem[MaxSize];//定义数组
int length;
//表长度 }S_TBL;S_TBL *Init_S_TBL()
//顺序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;};int Binary_search(S_TBL *tbl,KeyType kx)//在表tbl中查找关键码为kx的数据元素 { int mid,flag=0,low=1,high=tbl->length;//1.设置初始区间
while(low<=high)
//2.表空测试
{
//非空，进行比较测试
mid=(low high)/2;
//3.得到中间点
if(kx
high=mid-1;
//调整到左半区
else if(kx>tbl->elem[mid].key)
low=mid 1;
//调整到右半区
else
{ //返回该元素在表中的位置，或返回0 };void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“输入一组以-1结尾的数(关键码字段)”<
tbl->length ;
i=tbl->length 1;
tbl->elem[i].key=k;
cin>>k;} i=1;cout<<“输入一组以-1结尾的数(数据元素)”<
tbl->elem[i].elem=k;
i ;
cin>>k;} cout<<“输入所需查找数的关键码字段”<
cout<<“查找成功”<
cout<<“所查找的数为”<
}
else
cout<<“查找失败”<
-1结尾的数(数据元素)33 22 11 55 99 77 88 66 44-1 输入所需查找数的关键码字段3 查找成功
所查找的数为33 实验四的收获
查找的程序对我来说不陌生。两种基本方法的比较和应用里，我留意了最大查找次
数的不同。顺序查找的进行，如果查找不成功那么会议共比较N 1次。当数据量很大的时候，平均查找长度过大，当然顺序查找对于数据的存贮方式没有任何的要求。折半查找会有一个平均查找长度以及查找的最大长度。
我比较倾向于这本查找，其查找的效率明显会高于顺序查找。特别地，我还留意到对于单链表结构，无法进行二分法的查找，因为全部的元素的定位只能从指针开始。对于线性列表只能采取顺序查找的方式。
上机实践五
题目五：排序(插入排序选择排序冒泡排序)排序是数据处理中经常使用的一种重要的运算，其目的就是将一组数据按照规定的顺序进行排列。排序的目的是便于查询和处理。插入排序的基本思想是每一步将一个待排序的元素，按照其关键字吗的大小，插入到前面已经排序号的一组元素的适当的位置上，知道所有的元素都插入为止。一般地认为插入排序是一个稳定的排序方法。选择排序，每次从当前待排序的记录中，通过依次地进行关键字妈的比较从中选择一个关键字最小的记录，并且把它与当前待排序的第一个记录进行交换。直接选择排序是一个不稳定的排序方法。冒泡排序是一种简单的交换排序的方法。一次地比较相邻两个记录的关键字，若发现两个记录的次序相反（即位前一个记录的关键字大雨后有一个记录的关键字），进行记录的交换一直到没有反序为止。极端情况下，冒泡排序会有最短与最长时间，整个队列越是接近有序，则冒泡排序的进行次数越少。
//031040102 插入排序 #include
//定义关键码字段
ElemType elem;
//定义其他字段 }elemtype;
typedef struct
//顺序存储结构定义 { elemtype elem[MaxSize];
//定义数组
int length;
//表长度 }S_TBL;
S_TBL *Init_S_TBL()
//顺序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;};
int Binary_search(S_TBL *tbl,KeyType kx)//在表tbl中查找关键码为kx的数据元素 { int mid,flag=0,low=1,high=tbl->length;//1.设置初始区间
while(low<=high)
//2.表空测试
{
//非空，进行比较测试
mid=(low high)/2;
//3.得到中间点
if(kx
high=mid-1;
//调整到左半区
else if(kx>tbl->elem[mid].key)
low=mid 1;
//调整到右半区
else
{
flag=mid;
break;
//查找成功，元素位置设置到flag中
} } Return flag;//返回该元素在表中的位置，或返回0 };
void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“输入一组以-1结尾的数(关键码字段)”<
tbl->length ;
i=tbl->length 1;
tbl->elem[i].key=k;
cin>>k;} i=1;cout<<“输入一组以-1结尾的数(数据元素)”<
while(k!=-1)};{ void Print(RecType R[],int n)
tbl->elem[i].elem=k;
i ;
cin>>k;} cout<<“输入所需查找数的关键码字段”<
cout<<“查找成功”<
cout<<“所查找的数为”<
cout<<“查找失败”<
k=i;
for(j=i 1;j<=n;j )
if(R[j].key
k=j;
if(k!=i)
{
R[0]=R[k];
R[k]=R[i];
R[i]=R[0];
} } //输出数组内所有元素 { cout<<“关键字段为：”<
cout<
cout<
R[ n].key=x;
cin>>x;} n=0;cout<<“请输入一组以-1结尾的数(数据元素)：”<
R[ n].otherinfo=x;
cin>>x;}
cout<<“
排序前
”<
Print(R,n);SelectSort(R,n);cout<<“排序后”<
请输入一组以-1结尾的数(数据元素)： 33 22 11 44 55 66 99 88 77-1 排序前 关键字段为： 6 9 7 4 1 5 6 8 3 所有元素为： 33 22 11 44 55 66 99 88
排序后 关键字段为： 1 3 4 5 6 6 7 8 9 所有元素为： 55 44 66 33 99 11 88 22 //031040102 冒泡排序 #include
#define MaxSize 50
cin>>x;typedef struct RecType
}
//定义排序记录的形式
cout<<“排序前：”<
请输入一组以
-1结尾的数(关键码字段)： //选择排序函数 { int i,j,flag;for(i=1;i
flag=1;
for(j=1;j<=n-i;j )
if(R[j 1].key
{
flag=0;
R[0]=R[j];
R[j]=R[j 1];
R[j 1]=R[0];
}
if(flag==1)
return;} };void Print(RecType R[],int n)//输出数组内所有元素 { cout<<“关键字段为：”<
cout<
cout<
R[ n].key=x;
cin>>x;} n=0;cout<<“请输入一组以-1结尾的数(数据元素)：”<
R[ n].otherinfo=x;9 8 7 4 1 5 6-1 请输入一组以-1结尾的数(数据元素)： 11 22 33 44 66 55 77 88-1 排序前： 关键字段为： 6 9 8 7 4 1 5 6 所有元素为： 11 22 33 44 66 55 77 88 排序后： 关键字段为： 1 4 5 6 6 7 8 9 所有元素为： 55 66 77 11 88 44 33 22 实验五的收获
三种不同的排序方式，都是之前C 学习时候的重点掌握内容。
直接插入排序的算法很简洁，也很容易实现。从空间看，它只需要一个元素的辅助，从实践看该算法的主程序运行次数只比元素的个数少一。当然由于原列表的排序状况未知，其总比较次数和总的移动次数也是未定的，取平均数约为0.25N^2。对于直接选择排序，比较次数与原表元素的排列顺序无关，移动次数有关。根据冒泡排序的思想，待排序的记录有序之
后，则在下一趟的排序时候不会再有记录的交换位置，由此，我增加了一个标记flag，来直观表示每一次的排序是否需要发生交换，无交换则已经完成可以结束冒泡。特别地冒泡排序需要增加一个附加的单元来实现元素的交换。在交换时需要留意免得出错。
·
第三篇：数据结构实习报告
数据结构第六次作业p134
——11411203张玉
24.template
void Seueue
if(IsFull()==true){
maxSize=2*maxSize;
elements[rear]=x;
rear=(rear 1)%maxSize;
}
elements[rear]=x;
rear=(rear 1)%maxSize;
};
template
bool Seueue
if(rear<=maxSize/4){
maxSize=maxSize/2;
x=elements[front];
front=(front 1)%maxSize;
}
x=elements[front];
front=(front 1)%maxSize;
return true;
};
29.// 利用优先级队列实现栈和队列
#include
template
template
template
class PQueueNode
{
friend class PQueue
friend class Queue
public:
PQueueNode(T &value, int newpriority, PQueueNode
virtual int GetPriority(){ return priority;}//取得结点优先级
virtual PQueueNode
virtual void SetData(T& value){ data = value;}//修改结点数据
virtual void SetPriority(int newpriority){ priority = newpriority;} //修改结点优先级
virtual void SetLink(PQueueNode
T data;//数据
int priority;//优先级
PQueueNode
};
//优先级队列的类定义
template
class PQueue
{
friend class Stack
friend class Queue
public:
PQueue():front(NULL), rear(NULL){}//构造函数
virtual ~PQueue(){ MakeEmpty();}//析构函数
virtual void Insert(T &value, int newpriority);//插入新元素value到队尾 virtual T Remove();//删除队头元素并返回 virtual T Get();//读取队头元素的值 virtual void MakeEmpty();//置空队列
virtual int IsEmpty(){ return front == NULL;}//判队列空否private:
PQueueNode
};template
void PQueue
{
//将优先级队列置空
PQueueNode
while(front!= NULL)//链不空时, 删去链中所有结点
{
//循链逐个删除
q = front;
front = front->link;
delete q;
}
rear = NULL;//队尾指针置空
}template
void PQueue
{
//插入函数
PQueueNode
front = rear = q;//队列空时新结点为第一个结点
else
{
PQueueNode
while(p!= NULL && p->priority >= newpriority)//队列中按优先级从大到小链接{
pr = p;
p = p->link;
}
if(pr == NULL)
{
//插入在队头位置
q->link = front;
front = q;
}
else
{
q->link = p;
pr->link = q;//插入在队列中部或尾部
if(pr == rear)
rear = q;
}
}
}
//删除队头元素并返回
template
T PQueue
{
if(IsEmpty())
return NULL;PQueueNode
front = front->link;//将队头结点从链中摘下
T &retvalue = q->data;
delete q;
if(front == NULL)
rear = NULL;return retvalue;
}
//读取队头元素的值
template
T PQueue
if(IsEmpty())
return NULL;
else
return front->data;
}
//(1)栈的定义与实现
template
class Stack:public PQueue
{
//栈类定义
public:
Stack():PQueue
void Insert(T & value);//插入新元素value到队尾
};template
void Stack
{
//插入函数
PQueueNode
else
{
//插入在前端
q->link = front;
front = q;
}
}//--------------------------Queue //(2)队列的定义与实现
template
class Queue:public PQueue
{
//队列类定义
public:
Queue():PQueue
void Insert(T & value);//插入新元素value到队尾
};template
void Queue
{
//插入函数
PQueueNode
if(IsEmpty())
front = rear = q;//队列空时新结点为第一个结点
else
rear = rear->link = q;//插入在队尾位置
void main(){
Stack
int n = 1;
aStack.Insert(n);aQueue.Insert(n);}
第四篇：数据结构实习报告
数据结构课程设计的实习报告怎么写呀，请求做过课设的同学发一篇范文过来谢谢-_-规范实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：
1、需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么?明确规定：(1)输入的形式和输入值的范围；(2)输出的形式；(3)程序所能达到的功能；(4)测试数据：包括正确地输入及其输出结果和含有错误的输入及其输出结果，数据结构实习报告。
2、概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。
3、详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数的调用关系图。
4、调试分析内容包括：(1)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；(2)算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进思想；(3)经验和体会等，实习报告《数据结构实习报告》。
5、用户使用说明说明如何使用你编写的程序，详细列出每一步操作步骤。
6、测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。
7、附录题目：约瑟夫-实习报告尺寸：约瑟夫-实习报告.doc目录：
一、需求分析
二、概要设计
三、程序具体设计及函数调用关系
四、调试分析
五、测试结果原文：实习报告题目：约瑟夫(Joseph)问题的一种描述是：编号为1，2，.，n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个开始重新从1报数，如此下去，直至年有人全部出列为止。试设计一个程序求出出列顺序。班级：姓名：学号：完成日期：
一、需求分析1.本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据(即n个人的编号和密码)。2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。3.程序执行的命令包括：1)构造单向循环链表；2)4.测试数据m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6(正确的出列顺序为6，1，4，7，2，1，3，5)。
二、概要设计1.单向循环链表的抽象数据类型定义为：ADT List{数据对象：D={ai|ai∈正整数，I=1，2，.，n,n≥0}数据关系：R1={ai-1，ai|，ai-1，ai∈D,I=1，2，.，n}基本操作：Init List(&L)操作结果：构造一个空的线性表L。List Insert(&L,i,e)初始条件：线性表L已存在，1≤i≤List Length(L) 1.操作结果：在L中第i个位置之前插入新的数据无素e，L长度加1。List Delete(&L,i,&e)初始条件：线性表L存在非空，1≤i≤List Length(L).操作结果：删除L的第i个元素，并用e返回其值，L长度减1。2.程序包含四个模块：1)主程序模块：void main(){.
第五篇：数据结构课程设计报告
青岛理工大学
数据结构课程设计报告
题目：宿舍管理查询软件
院（系）：计算机工程学院
学生姓名:谢茂盛
班级：网络121学号: 202207131
起迄日期:2022.07.07-2022.07.20
指导教师:张艳
一、需求分析（所有大标题宋体加粗四号，下同）（小标题宋体加粗小四，下同）
1.问题描述：
以无歧义的陈述详细说明对自己所选题目的解释性描述，可以补充说明该设计中要做的具体任务。强调的是程序要做什么？
2.基本功能
要求分别列出该设计要实现的功能，（每个功能要尽量和概要设计中的模块函数对应起来）。
二、概要设计
1.设计思路：
解决问题的思路概述，拟采用的算法的简介。
2.数据结构设计：
要求分别列出拟采用的数据结构及其定义，分为逻辑结构（线性？树状？图状？）和存储结构（顺序？链式？）。采用该结构的原因，如果有定义的抽象数据类型，可以列出其定义及各种操作。如下为抽象数据类型定义的模板。
定义程序中用到的抽象数据类型；
设计中所用到的数据结构或抽象数据类型的说明，以及在程序中的作用
抽象数据类型线性表的定义如下：
ADT List{
数据对象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0}
数据关系：R1={| ai-1,ai ∈D,i=1,2,3,……，n}
基本操作：
Insert(&L,i,j)
初始条件：线性表L已存在，1≤i≤n 1。
操作结果：在L中第i个位置之前插入新的数据元素j,L的长度加1。
Del(&L,i,j)
初始条件：线性表L已存在，1≤i≤n。
操作结果：删除L的第i个数据元素,L的长度减1
Xg(&L,i,j)
初始条件：线性表L已存在。
操作结果：用新的输入数据项j代替原有的指定要修改的数据项i。
Search(&L,i,e)
初始条件：线性表L已存在。
操作结果：查找指定的某元素i，并将值赋给e,用e 输出。
}
3.软件结构设计：
按需求分析中的功能进行模块划分，建立模块的层次结构及调用关系。
三、详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪代码算法；对主程序和其他模块也都需要写出伪代码算法（伪代码算法达到的详细程度建议为：按照伪代码算法可以在计算机键盘直接输入高级程序设计语言程序）)；可采用流程图、活动图进行描述，画
出函数和过程的调用关系图。
实现设计中主程序和其他子模块的算法，以流程图的形式表示，需画出函数和过程的调用关系图。
本小节内所有的图均要求用Visio或Word进行绘制，不允许用bmp或其他格式的图片。绘图内文字均采用宋体五号（如果图比较大，排版不好看的话，可以根据需要缩小字体），单倍行间距，段前段后均设置为0行。
1.定义程序中所有用到的数据及其数据结构，及其基本操作的实现；
2．主函数和其他函数的伪码算法；
3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表示。
4.画出函数之间的调用关系图。
四、调试分析
内容包括：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析。
1.实际完成的情况说明（完成的功能，支持的数据类型等）；
2.程序的性能分析，包括时空分析；
3.上机过程中出现的问题及其解决方案；
4.程序中可以改进的地方说明；
5.程序中可以扩充的功能及设计实现假想。
五、测试结果
列出你的测试结果，包括输入和输出。注意测试数据应该完整和严格，至少给出2组测试结果（含合法数据与非法数据）。
六、用户手册
说明如何使用你编写的程序，详细列出每一步的具体操作步骤。这里可以有适当的运行结果抓图。用户手册与开发过程无关，只与使用有关，必须是Step by Step的。
所有运行结果截图均要求有实际数据的内容，截图尺寸要求按页宽排版两张大小，且要求有每张图下面有规范的标题说明如何使用你编写的程序，详细列出每一步的操作步骤。
七、体会与自我评价
写出本设计的总结思考，收获心得体会，要求不少于600字，不得摘抄网上资料，只能参考。
正文（各标题除外），均采用宋体和Times New Roman字体，小四号字，1.25倍行距。
八、参考文献（列出你参考的书，格式按照下面的例子来写）例如：
[1]严蔚敏．数据结构(C语言)．清华大学出版社，2022
