第一篇：数据结构实践报告
20XX 报 告 汇 编 Compilation of reports
数据结构实践报告
学
号：
150906112
姓
名：
武锦蓉
班
级：
NET2 班
指导老师：
田喜平
时
间：
2016-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 数据对象：整形 数据关系：线性关系，即
基本操作：
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，来直观表示每一次的排序是否需要发生交换，无交换则已经完成可以结束冒泡。特别地冒泡排序需要增加一个附加的单元来实现元素的交换。在交换时需要留意免得出错。 · 北京联合大学 实训报告 课程（项目）名称： 数据结构 学 院： 专 业： 班 级： 学 号： 姓 名： 成 绩： 2012年 6 月 21 日 数据结构实训任务一 一、任务与目的： 1、用顺序表表示两个无序集合A、B，实现集合的如下操作，求两个集合的并集、交集、差集。 2、用顺序表表示两个集合A、B（集合A、B都是有序递增的情况）实现集合的如下操作，求两个集合的并集、交集、差集。 3、用带头单链表存储结构表示两个无序集合A、B，实现集合的如下操作，求两个集合的并集、交集、差集。 4、用带头单链表存储结构表示两个集合A、B（集合A、B都是有序递增的情况），实现集合的如下操作，求两个集合的并集、交集、差集。 5、杀人游戏 N个人坐成一圈玩杀人游戏，按顺时针编号 N。从1号开始顺时针开始数到第m号就杀掉第一个人，被杀掉的人要退出游戏。 如果数到了编号的末尾，接着数开头的编号。 重复，直至杀掉一半人时，游戏结束，聪明的你能告诉我活到最后的幸存者最初的编号是多少吗？ 输入数据：N、M ；输出数据：幸存者的编号 分析该程序，如果N=20，M=2，……10。聪明的你应选择的编号是多少，（提示，计算出M分别等于1到10的情况下，那些编号生存概率较大）。给出实验结果 6、作业抽查问题：有35个学生的班级，由于某种原因不能够做到全部检查作业，现在希望每次抽查10名学生，希望能够随机抽查，并能够有记忆，即希望抽查过的学生，下次抽查的概率有所减小，但避免不被抽查。设计一个算法实现该功能，给出你的解释。1.void BingSet(SqList A, SqList B,SqList &C){//求并集 int i,j;int flag=0;C.length=0;for(i=0;i if(flag==0) {C.elem[i]=B.elem[j];i++;} } C.length=i;} void JiaoSet(SqList A, SqList B,SqList &C){//求交集 int i,j;int flag=0;C.length=0;i=0;for(j=0;j if(flag!=0) {C.elem[i]=B.elem[j];i++;} } C.length=i;} void ChaSet(SqList A, SqList B,SqList &C){//求差集 int i,j,k;int flag=0;C.length=0;k=0;for(i=0;i if(flag==0) {C.elem[k]=A.elem[i];k++;} } C.length=k;} 运行结果： 2.void BingSet(SqList A, SqList B,SqList &C){//求并集 int i,j,k;k=0;C.length=0;for(i=0,j=0;(i {C.elem[k]=A.elem[i];k++;i++; } else {if(A.elem[i]==B.elem[j]) {C.elem[k]=A.elem[i];k++;i++;j++; } else {C.elem[k]=B.elem[j];k++;j++;} } } if(i {C.elem[k]=A.elem[i];k++;i++; } } if(j {C.elem[k]=B.elem[j];k++;j++;} } C.length=k;} void JiaoSet(SqList A, SqList B,SqList &C){//求交集 int i,j,k;k=0;C.length=0;for(i=0,j=0;(i {i++;} else {if(A.elem[i]==B.elem[j]) {C.elem[k]=A.elem[i];k++;i++;j++; } else {j++;} } } C.length=k;} void ChaSet(SqList A, SqList B,SqList &C){//求差集 int i,j,k;int flag=0;k=0;C.length=0;for(i=0,j=0;(i {C.elem[k]=A.elem[i];i++;k++; } else {if(A.elem[i]==B.elem[j]) {i++;j++;} else {j++; } } } if(i {C.elem[k]=A.elem[i];k++;i++;} } C.length=k;} void InserOrder_Sq(SqList &L,ElemType e){int i,j;for(i=0;i L.elem[j+1]=L.elem[j];L.elem[i]=e;L.length++;} 运行结果： 3.void bing(link &p,link &h,link &q) {//求并集 link l,s,m;int j=0,i=0;q=new LNode;q->date=NULL;q->next=NULL;s=p->next;m=q;while(s){l=new LNode; l->date=s->date; l->next=NULL; s=s->next; m->next=l; m=l; s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==0){l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l; } s=s->next;} } void jiao(link &p,link &h,link &q) { //求交集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q; s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==1) {l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l; } s=s->next;} } void cha(link &p,link &h,link &q) {//求差集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q;s=p->next;while(s){i=s->date; j=Locate(h,i); if(j==0){l=new LNode; l->date=s->date; l->next=NULL; m->next=l;m=l;} s=s->next;} } void shengcheng(link &p,link &h,link &q) { int i,j=0;Elem e;for(i=0;i<11;){if(i==0){p=new LNode; p->date=NULL; p->next=NULL; h=p;q=p;i++;} else {e=rand()%50+1; j=Locate(p,e); if(j==0) {LInsert(p,e);i++;}}}} 运行结果： 4.void bing(link &p,link &h,link &q) { //并集 link l,s,m;int j=0,i=0;q=new LNode;q->date=NULL;q->next=NULL;s=p->next;m=q;while(s){l=new LNode; l->date=s->date; l->next=NULL; s=s->next; m->next=l; m=l;} s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==0) {LInsert(q,i);} s=s->next;} } void jiao(link &p,link &h,link &q) {//交集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q;s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==1) {l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l;} s=s->next;} } void cha(link &p,link &h,link &q) {//差集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q;s=p->next;while(s){i=s->date; j=Locate(h,i); if(j==0) {l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l;} s=s->next;} } void shengcheng(link &p,link &h,link &q) {int i,j=0;Elem e;for(i=0;i<11;){if(i==0) {p=new LNode; p->date=NULL; p->next=NULL; h=p;q=p;i++;} else {e=rand()%50+1; j=Locate(p,e); if(j==0) {LInsert(p,e);i++;}}}} 运行结果： 5.#include struct kill { int num; struct kill *next;}; struct kill *create(int m) {struct kill *head,*p1,*p2;int i;p1=p2=(struct kill*)malloc(LEN);head=p1; head->num=1; for(i=1,p1->num=1;i p2->next=p1;p2=p1;} p2->next=head;return head;} struct kill *findout(struct kill *start,int n){int i; struct kill *p;i=n;p=start; for(i=1;i struct kill *letout(struct kill *last){struct kill *out,*next;out=last->next; last->next=out->next;next=out->next;free(out);return next;} void main() { int m,n,i,servive;struct kill *p1,*p2; cout<<“请输入参加杀人游戏总人数m:”< cout<<“要杀掉的人的序号n:”< { p1=p2=create(m);for(i=1;i p2=letout(p1);p1=p2;} servive=p2->num;free(p2);} cout<<“幸存者是：”< 6.#include //学生id int times; //定义学生抽查数};Student stu[35];//35个学生 int cho[10]; //抽查的10个学生 int top; //已抽查学生数 int choose(){int n=rand()%35;//随机抽取 for(int i=0;i int n2=rand()%stu[n].times;//否则几率按抽取的次数减小,具体为(1/抽取次数)if(n2==0)return n;else return choose();} void main(){char a='Y';srand(time(0));//随机数初始化 int i;for(i=0;i<35;i++)//学生初始化 {stu[i].id=i+1;stu[i].times=0;} while(a=='Y'||a=='y'){int tmp;top=0;for(i=0;i<10;i++)//抽取10个学生 {tmp=choose();//抽取学生 cho[top++]=tmp;stu[tmp].times++;cout<<“第”< 数据结构实训任务二 一、任务与目的：主要考察的是栈与队列的逻辑结构和存储结构。 1、用栈，判断一个算数表达式中的圆括弧、方括弧和花括弧是否匹配。 2、用栈，把十进制的整数转换为二至九之间的任一进制 3、设计一个算法，检测一个字符串数组是否是回文，回文是指这个字符串是否关于中心对称。int Check（char a[]，int n） 4、采用SPT规则的单机生产计划问题。问题描述如下，存在一台机器，要加工n个工件，每个工件i都有一个确定的加工时间，采用按照 递增的顺序，进行加工，计算每个工件的完成时间（初始加工时间为0）。设计一个算法，输入工件数量n，随机在[1，30]的区间内产生每个工件的加工时间。按照SPT规则进行加工，输出每个工件的完成时间。 5、采用EDD规则的单机生产计划问题。问题描述如下，存在一台机器，要加工n个工件，每个工件i都有一个确定的加工时间，同时每个工件都有一个确定的交货期，采用按照 递增的顺序，进行加工，计算每个工件的完成时间（初始加工时间为0）。设计一个算法，输入工件数量n，随机在[1，30]的区间内产生每个工件的加工时间，在区间[2，20*n]内随机产生每个工件的交货期。按照EDD规则进行加工，输出每个工件的完成时间，计算每个工件i完成时间和 的差值。1.void Ininstack(stack &s) {//初始化 s.elem=new stype[SIZE];s.top=-1;s.size=SIZE;s.insize=IN;} void INsize(stack &s) {//扩容 stype *a;int i;a=new stype[s.size+s.insize];for(i=0;i<=s.top;i++)a[i]=s.elem[i];delete []s.elem;s.elem=a;s.size+=s.insize;} void Push(stack &s,stype e) { //入栈 if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} stype Pop(stack &s) {//出栈 stype e;e=s.elem[s.top];s.top--;return e;} stype GetTop(stack s) {//取栈顶 stype e;e=s.elem[s.top ];return e;} void main(){stype e,t,ch;stack s;char a[20];int i=0,n;Ininstack(s);cout<<“请输入算术表达式(以$结尾):”;while(ch!='$'){cin>>ch; a[i]=ch;i++;} n=i;for(i=0;i {e=a[i];Push(s,e);} if(a[i]=='}'||a[i]==']'||a[i==')']) {t=GetTop(s); if(a[i]=='}' && t=='{')Pop(s); else if(a[i]==']' && t=='[') Pop(s);else if(a[i]==')' && t=='(') Pop(s);}} if(s.top==-1) cout<<“括号匹配!”< cout<<“括号不匹配!”< 2.void Ininstack(stack &s) { //初始化 s.elem=new stype[SIZE];s.top=-1;s.size=SIZE;s.insize=IN;} void INsize(stack &s) { //扩容 stype *a;int i;a=new stype[s.size+s.insize];for(i=0;i<=s.top;i++)a[i]=s.elem[i];delete []s.elem;s.elem=a;s.size+=s.insize;} void Push(stack &s,stype e) {//入栈 if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} stype Pop(stack &s) { //出栈 stype e;e=s.elem[s.top];s.top--;return e;} void main(){stack s;int a,b;Ininstack(s);cout<<“请输入任意非负十进制数:”;cin>>a;cout<<“请输入需要转换的进制数(进制数为二至九):”;cin>>b;while(a){Push(s,a%b);a=a/b;} while(!(s.top==-1))cout< 运行结果： 3.void Ininstack(stack &s) { //初始化 s.elem=new stype[SIZE];s.top=-1;s.size=SIZE;s.insize=IN;} void INsize(stack &s) { //扩容 stype *a;int i;a=new stype[s.size+s.insize];for(i=0;i<=s.top;i++)a[i]=s.elem[i];delete []s.elem;s.elem=a;s.size+=s.insize;} void Push(stack &s,stype e) {//入栈 if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} void Error(char *a) { cout< stype Pop(stack &s) { stype e;e=s.elem[s.top];s.top--;return e;} int Check(char a[],int n,stack &s) {//判断 int i;char e;Pop(s);for(i=0;i urn 0;} void main(){stack s; r ch,a[50];t i=0,n,t;instack(s);cout<<“请输入字符串(以$结尾):”;while(ch!='$'){cin>>ch;[i]=ch;ush(s,ch);+;} n=i;Check(a,n,s);if(t==1)cout<<“是回文!”< 运行结果： 4.void chushihua(sqlist &a) //初始化 {a.elem=new elemtype[SIZE]; a.num=new elemtype[SIZE]; a.welem=new elemtype[SIZE]; a.length=0; a.listsize=SIZE; a.incrementsize=INCREMENT;} void paixu(sqlist a) //排序 { int i,j,t,m;for(i=0;i 5.typedef struct {elemtype *elem; //加工时间 elemtype *num; //序号 elemtype *welem; //完成时间 elemtype *jelem; //交货期 elemtype *celem; //差值 int length; //长度 int listsize; //分配量 int incrementsize;//增补量 }sqlist;void chushihua(sqlist &a) //初始化 {a.elem=new elemtype[SIZE]; a.num=new elemtype[SIZE]; a.welem=new elemtype[SIZE]; a.celem=new elemtype[SIZE]; a.jelem=new elemtype[SIZE]; a.length=0; a.listsize=SIZE; a.incrementsize=INCREMENT;} void paixu(sqlist a) //排序 {int i,j,t,m,p;for(i=0;i a.welem[i]=a.elem[i];else {a.welem[i]=a.elem[i]+a.welem[i-1];} a.celem[i]=a.jelem[i]-a.welem[i];cout< 数据结构实训任务书三：二叉树链式存储的基本操作 1、创建二叉树 a)熟悉使用教材的先序创建二叉树的方法 b)编写一个算法，实现在已知二叉树的先序序列和中序序列的情况下创建二叉树。 c)如果已知二叉树的顺序表示形式，将其转换为二叉树的链式存储方式。 2、二叉树的遍历 a)先序、中序和后序三种形式的链式存储递归式算法 b)先序、中序和后序三种形式的链式存储非递归式算法 c)层次遍历的算法。 3、二叉树一些基本操作 a)计算二叉树的深度； b)计算二叉树的叶子节点个数 c)计算二叉树的单支节点的个数 d)计算二叉树的双支节点的个数 4、编写一个主函数能够测试你所设计的算法。 主函数调用教材创建二叉树的创建教材图7-10的二叉树链式存储方式。 {p=st.a[st.top]; st.top--; cout< data; while(p->right!=NULL) {st.top++; st.a[st.top]=p->right; q=p->right; while(q->left!=NULL) {st.top++; st.a[st.top]=q->left; q=q->left; } 代码：#include //二叉树结点的结构体表示形式 {char data;struct node* left,*right;}BTree;typedef BTree *Tree;typedef struct stackelem //栈的结构体表示形式 {BTree* a[MAXSIZE];int top;}Stack;void CreateBiTree_Rec(Tree &T)//先序创建二叉树的方法 {char ch;cin>>ch;if(ch=='#') T=NULL;else {T= new BTree; T->data=ch; CreateBiTree_Rec(T->left); CreateBiTree_Rec(T->right);}} void Preorder(Tree t)//前序遍历，递归的方法 {if(NULL!=t){cout< Preorder(t->left); Preorder(t->right);}} void Preorder2(Tree t)//前序遍历的非递归实现 {Tree p;Stack st;st.top=-1;if(NULL==t){return;} else {st.top++; st.a[st.top]=t; while(st.top!=-1) {p=st.a[st.top]; st.top--; cout< data; if(p->right!=NULL) {st.top++; st.a[st.top]=p->right;} if(p->left!=NULL) {st.top++; st.a[st.top]=p->left;} void Inorder(Tree t)//中序遍历，递归实现 {if(NULL!=t){Inorder(t->left); cout< Inorder(t->right);}} void Inorder2(Tree t)//中序遍历，非递归实现 {Tree p,q;Stack st;st.top=-1;if(NULL==t){return;} else {while(t!=NULL) {st.top++; st.a[st.top]=t; t=t->left; }}} 20 } while(st.top!=-1)break; } }}} void Postorder(Tree t)//后序遍历，递归实现 {if(t!=NULL){Postorder(t->left); Postorder(t->right); cout< {st.top++; st.a[st.top]=t; t=t->left; } m=NULL; flag=1; while(st.top!=-1 && flag) {t=st.a[st.top]; if(t->right==m) {cout< st.top--; m=t;} else {t=t->right; flag=0; }}} while(st.top!=-1);} int Height(Tree t)//求二叉树的高度，递归实现{int depth1,depth2;if(!t){ return 0;} else {depth1=Height(t->left); depth2=Height(t->right); if(depth1>depth2) {return(depth1+1); } else {return(depth2+1); }}} int leafs_rec(Tree t) //叶子结点 {int l,r;if(t==NULL) return 0;else if((t->left==NULL)&&(t->right==NULL)) return 1;else {l=leafs_rec(t->left); r=leafs_rec(t->right); return(l+r);}} int danzhi(Tree t)//单只 {if(t==NULL) return 0;else if((t->left==NULL)&&(t->right!=NULL)) d++;else if((t->left!=NULL)&&(t->right==NULL)) d++;danzhi(t->left);danzhi(t->right);return(d);} int shuangzhi(Tree t) //双只 {if(t==NULL) return 0;else if((t->left!=NULL)&&(t->right!=NULL)) l++;shuangzhi(t->left);shuangzhi(t->right);return(l);} void TraversalOfLevel(Tree t)//层次遍历二叉树 { Tree p,q[100];int f=0,r=0;if(t!=NULL) {p=t; q[r]=t; r++;} while(f!=r){p=q[f];f++; cout< data; if(p->left!=NULL) {q[r]=p->left; r++; } if(p->right!=NULL) {q[r]=p->right; r++;} }} void CreateBiTree_XZ(Tree &T,char a[],int la,int ra,char b[],int lb,int rb)//知先序、中序求二叉树 {int i,lla,lra,llb,lrb,rla,rra,rlb,rrb;if(la>ra) T=NULL;else {T=new BTree; T->data=a[la]; for(i=lb;i<=rb;i++) {if(b[i]==a[la]) break;} lla=la+1; lra=lla+i-lb-1; rla=lra+1; rra=ra;llb=lb; lrb=i-1; rlb=i+1; rrb=rb; CreateBiTree_XZ(T->left,a,lla,lra,b,llb,lrb); CreateBiTree_XZ(T->right,a,rla,rra,b,rlb,rrb);}} void CreateBiTree_SX(Tree &T,char S[],int pos,int n)//二叉树的顺序表示形式，将其转换为二叉树的链式存储方式 {int i;if(S[pos]=='#') T=NULL;else {T=new BTree; T->data=S[pos]; if((i=2*pos+1)<=n) CreateBiTree_SX(T->left,S,i,n); else T->left=NULL; if((i=2*pos+2)<=n) CreateBiTree_SX(T->right,S,i,n); else T->right=NULL;}} void main(){int n,i;char a[30],b[30],c[30];Tree s;Tree m;cout<<“请输入先序:”;CreateBiTree_Rec(m);cout< 数据结构实训任务书四：图的操作 1、建立图的存储结构 a)创建图的邻接矩阵表示方式 b)创建图的邻接表表示方式 c)实现两种方式的互换 2、图的遍历 a)基于邻接矩阵的深度和广度遍历 b)基于邻接表的深度和广度遍历 3、最小生成树，使用Prim算法实现从某一节点出发的图的最小生成树25 4、单源最短路径，算法8-10 5、关键路径算法。 1．代码： typedef enum{DG,DN,UDG,UDN}GKind;typedef enum{FALSE,TRUE}Boolean;Boolean visited[max_v];typedef int VType;typedef int EType;typedef int qtype;typedef struct { qtype *elem;int front;int rear;int qsize;int insize;}squeue;typedef struct { VType vexs[max_v];EType edges[max_v][max_v];int vnum,ednum;GKind kind;}MGraph;typedef struct ENode { int advex;struct ENode *next;int weight;}ENode;typedef struct VNode { VType vex;ENode *first;}VNode,List[max_v];typedef struct { List ver;int vnum,ednum;int kind;}AGraph;int LocatV(MGraph g,VType x){ int k;k=-1;for(k=0;(k //邻接矩阵 { int i,j,k,v1,v2,w;cout<<“请输入顶点数:”;cin>>g.vnum;cout<<“请输入边数:”;cin>>g.ednum;cout<<“请输入构造顶点数组顶点值:”< g.edges[i][j]=infinity;cout<<“请输入构造邻接矩阵:”< cin>>v1; cout<<“请输入顶点V2:”; cin>>v2; cout<<“请输入权值:”; cin>>w; i=LocatV(g,v1); j=LocatV(g,v2); while((i<0)||(i>(g.vnum-1))||(j<0)||(j>(g.vnum-1))) { cout<<“编号超出范围，请重新输入顶点及权值:”< cin>>v1; cin>>v2; cin>>w; i=LocatV(g,v1); j=LocatV(g,v2); g.edges[i][j]=w; g.edges[j][i]=g.edges[i][j];}} int LocatVA(AGraph g,VType x){ int k;k=-1;for(k=0;(k cout<<“编号超出范围，请重新输入:”< cin>>v1; cin>>v2; i=LocatVA(g,v1); j=LocatVA(g,v2);} p=new ENode;p->advex=j;p->next=g.ver[i].first;g.ver[i].first=p;}} void DFS(AGraph g,VType i){ ENode *p;VType w;visited[i]=TRUE;cout< DFS(g,w);}} void Draverse(AGraph g) //邻接表深度遍历 { int i;for(i=0;i DFS(g,i);} void MDFS(MGraph g,VType i){ VType p;visited[i]=TRUE;cout< MDFS(g,p);}} void Mraverse(MGraph g) //邻接矩阵深度遍历 { int i;for(i=0;i MDFS(g,i);} void InQueue(squeue &q) { q.elem=new qtype[SIZE];q.front=q.rear=0;q.qsize=SIZE;q.insize=IN;} void INsize(squeue &q) { qtype *a;int i;a=new qtype[q.qsize+q.insize];for(i=0;i { if(((q.rear+1)%q.qsize)==q.front)INsize(q);q.elem[q.rear]=e;q.rear=(q.rear+1)%q.qsize;} void Error(char *a) //错 { cout< { qtype e;if(q.front==q.rear)Error(“循环队列空!”);e=q.elem[q.front];q.front=(q.front+1)%q.qsize;return e;} void BFS(MGraph g) { int i,w,u;squeue q; //初始化 //扩容 //入队 //出队 //邻接矩阵广度遍历29 for(i=0;i cout< EnQueue(q,i); while(q.front!=q.rear) { u=DeQueue(q); for(w=0;w if(g.edges[u][w]&&(!visited[w])) { visited[w]=TRUE; cout< EnQueue(q,w);}}}} void MBFS(AGraph g) //邻接表广度遍历 { int i,w,u;squeue q;ENode *p;for(i=0;i EnQueue(q,i); while(q.front!=q.rear) {u=DeQueue(q); cout< p=g.ver[u].first; while(p) {w=p->advex; if(visited[w]!=TRUE) { visited[w]=TRUE; EnQueue(q,w);} p=p->next;}}}}} void MatToList(MGraph l,AGraph &g)//此函数用于实现将邻接矩阵转换成邻接表{ int i,j;ENode *p;g.vnum = l.vnum;for(i = 0;i g.ver[i].first = NULL; g.ver[i].vex=l.vexs[i];} for(i=0;i for(j = l.vnum-1;j>=0;j--) { if((l.edges[i][j]!= 0)&&(l.edges[i][j]!=100)){ p =(ENode*)malloc(sizeof(ENode)); p->advex = j; p->next= g.ver[i].first; g.ver[i].first= p;}}} void ListToMat(MGraph &g, AGraph l)//表转矩阵 { int i,j;ENode *p;g.vnum=l.vnum;g.ednum=l.ednum;for(i = 0;i g.edges[i][j] = 0;for(i=0;i while(p){g.edges[i][p->advex] = 1; p=p->next;} }} void main(){ int j=0,i;MGraph g;AGraph h;ENode *p;CreatUDN_MG(g);cout<<“n此无向图共有”< for(j=0;j cout< ”; cout< { p=h.ver[i].first; while(p!=NULL) { cout<<“<”< p=p->next; } } cout< Draverse(h);cout< MatToList(g,h);cout<<“n此无向图共有”< for(j=0;j cout< ”; cout< { p=h.ver[i].first; while(p!=NULL) {cout<<“<”< p=p->next;} }} 2.代码：#include struct edgeNode *link;//与之相连的端点 }; //存储节点信息 vexNode adjlist[MAX];//访问标志 bool visited[MAX];//lowcost[j]存储从开始节点到节点j的最小花费 WeiType lowcost[MAX];//parent[j]表示节点j的前驱节点 int parent[MAX];//建立邻接表存储 void createGraph(vexNode *adjlist,const int n,const int e,const int v0){ edgeNode *p1,*p2;int i,v1,v2;WeiType weight;for(i=1;i<=n;i++){ cout<<“请输入节点”< visited[i] = false;lowcost[i] = Infinity;parent[i] = v0;} for(i=1;i<=e;i++){ cout<<“请输入边”< p1->weight = weight;p1->info = adjlist[v1].info;p1->next = adjlist[v2].link;adjlist[v2].link = p1;p2->no = v2;p2->weight = weight;p2->info = adjlist[v2].info;p2->next = adjlist[v1].link;adjlist[v1].link = p2;}} void f(int n,int e,int v){ int i,j,k;edgeNode *p,*q;WeiType sum = 0,minCost;createGraph(adjlist,n,e,v);p = adjlist[v].link; visited[v] = true;while(p!=NULL){ lowcost[p->no] = p->weight;p = p->next;} for(i=1;i minCost = Infinity; int k; for(j=1;j<=n;j++) { if(minCost>lowcost[j]&&!visited[j]) { minCost = lowcost[j]; k = j; } } sum += minCost; visited[k] = true; q = adjlist[k].link; while(q!= NULL) { if(!visited[q->no]&&q->weight { lowcost[q->no] = q->weight; parent[q->no] = k; } q = q->next;} } cout<<“最小生成树的边集为：”< cout<<“(”< } } 7、评语 工作态度（认真、一般、较差），工作量（饱满、一般、不够），每个任务能够独立（完成、基本完成、在辅导下完成），程序运行结果（正确、基本正确、部分正确），实训报告格式（标准、一般）。创新意识（较强、一般、没有），运行所学知识解决实际问题的能力（强、一般、较差）。 优(100~90)：能够熟练运用开发工具，编程解决实际问题，创意新颖，功能实现完善。 良(89~80)：能够熟练运用开发工具，编程解决实际问题，有一定创新，功能实现较好。 中(79~70)：能够较熟练使用开发工具，编程解决实际问题，独立完成实训，功能实现一般。 及格(69~60)：能够运用开发工具，在教师辅导下完成实训，实现部分功能。 不及格(59~0)：编程解决实际问题的能力差，功能实现较差。 实训成绩为： 分 教师签字： Harbin Institute of Technology at Weihai 数据结构课程设计报告 设计题目： 院 系： 班 级： 学 号： 组 号： 设 计 者： 哈尔滨工业大学（威海）计算机科学与技术学院 哈尔滨工业大学（威海）《数据结构课程设计》报告 前 言 数据结构是计算机专业的必修、主干课程之一，它旨在使读者学会分析研究数据对象的特性，学会数据的组织方法，以便选择合适的数据逻辑结构和存储结构，以及相应的运算(操作)，把现实世界中的问题转化为计算机内部的表示和处理，这是一个良好的程序设计技能训练的过程。在整个教学或学习过程中，解题能力和技巧的训练是一个重要的环节。 本课题设计要求学生分组进行（每组1-2人），自行选题，选题的思想是根据实际需要进行调研，以组为单位提交课程设计任务书，给出所选项目的背景和意义，由导师确定选题的级别，主要是以实用性为主，开发一个具有实际价值的项目，经过2周的课程设计后接受课程设计组老师的解题验收。 计算机科学与工程系 数据结构课程设计报告 课程设计题目 迷宫 航班信息查询系统 学 号 姓 名 班 级 专 业 网络工程 完 成 时 间 2013-1-4 指 导 教 师 数据结构课程设计 迷宫 题目一 1.设计内容 1.1问题描述 求迷宫从入口到出口的所有路径。1.2设计要求 1．迷宫中不能使用递归算法查找路径。2．试探方向限定为上、下、左、右四个方向。3．迷宫采用随机生成和手工生成两种方式。4．生成从迷宫入口到出口的最短和最长路径。5．迷宫的入口和出口由键盘输入。 1.3开发环境 Visual C++6.0的集成化环境 1.4研究思路 对这样的矩形迷宫，可以用N*M的矩阵来描述，N和M分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。为了描述迷宫中位置（i,j）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为1，否则为0。 经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。 2.设计步骤 2.1 需求分析 （1）题目：迷宫的生成与路由。生成一个N*M（N行M列）的迷宫，0和 1-1数据结构课程设计 迷宫 在该程序中，首先进入的是菜单选择，在菜单中有3种选择，选1是手动输入迷宫函数；选2是随机自动生成迷宫；选3是退出程序。在手动生成迷宫时，有两种输出方式，一是矩阵输出，二是图形输出。在矩阵输出时，直接将数组中的数进行输出，在图形输出时，则要判断该点的情况，然后输入迷宫的出入口，再调用mgpath（）函数进行判断是否存在路径，如果存在则将路径经过的点进行输出，并且将经过的点进入到辅助数组中（辅助数组是辅助图形界面的输出），并且将辅助数组初始为1，辅助数组中点为路径的重新赋值为0，然后根据情况输出图形界面。在自动生成迷宫时，用到了c语言随机函数，对于其它问题，和手动情况基本相同。 2.3 详细设计（1）主菜单伪代码： while(flag1){ } {shuru();//输入行列数 printf(“手动建立迷宫矩阵(0表示可通1表示障碍):n”);for(i=1;i<=m;i++) for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]);showplay(mg);// 迷宫输出 churukou();//迷宫出入口的输入 x=Mazepath(mg);// 判断路径函数 数据结构课程设计 迷宫 和“class ‘maze’has an illegal zero-sized array”两行错误。双击错误信息，找到出错的程序段，经过查阅资料发现，在利用顺序栈时，没有定义顺序栈的向量空间大小，导致程序出错。但不要对向量空间定义过大，否则会浪费空间。 （2）算法的时空分析： 由于链栈实际上是运算受限制的单链表。所以取栈顶元素运算的算法、置空栈运算的算法执行时间与问题的规模无关，则该算法的时间复杂度为O(1)；而其入栈运算的算法与出栈运算的算法相当于在链表的表尾进行插入和删除操作，不需要移动元素，时间复杂度也为O（1）。建立迷宫矩阵的时间复杂度为O（x*y）。在查找路径的过程中，最坏的情况下可能要考察每一个非障碍的位置。因此，查找路径的时间复杂度应为O（unblocked）。 链栈的入栈算法、出栈算法、取栈顶元素算法、置空栈算法执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各个算法的空间性能均较好。只是对于存放顺序栈的向量空间大小的定义很难把握好，如果定义过大，会造成不必要的空间浪费。所以在定义时要慎重考虑。 3.用户使用说明 运行该程序，运行的界面的会出现菜单界面，然后用户可根据界面的提示进行相应的操作，生成迷宫的方式有两种方式，手动生成和自动生成，手动生成时、，用户可根据自己的要求输入迷宫的格式，还需输入相应的入出口，确认程序就会生成相应的路径图形；自动生成只需输入所需的行数和列数，就会生成迷宫，接下来的操作和手动操作相同了。 图数据结构课程设计 迷宫 图1-2 图1-3 退出 5.总结与心得体会 本次课程设计过程中由于掌握的知识不牢固，在编程序的过程中得到了同学的帮助和指导，在此表示感谢。课程设计的过程中，遇到了一些问题，大部分是课本中的知识掌握的不牢固，还有就是在以前学习C++的过程中相关的知识掌握的不够全面。在以后的学习过程中，自己一定要把各种知识掌握牢固。 { } mg[i][j]=1;//初始化 矩阵,将最外围置为1 printf(“n输入迷宫入口：n”);scanf(“%d%d”,&x1,&y1);printf(“输入迷宫出口：n”);scanf(“%d%d”,&x2,&y2); }mlink;mlink *stack;//定义一个栈 int m,n,x1,x2,y1,y2;//定义全局变量 } void showplay(int mg[][M+2])//迷宫输出 { n“); for(i=1;i<=m;i++){ printf(”n“);for(j=1;j<=n;j++) printf(”%d “,mg[i][j]); int i,j; printf(”迷宫矩阵如下(0可通)：printf(“输入行数：n”);scanf(“%d”,&m);printf(“输入列数：n”);scanf(“%d”,&n);数据结构课程设计 迷宫 } } printf(“n迷宫图形如下(白色for(i=1;i<=m;i++){ } printf(”n“);for(j=1;j<=n;j++){ } if(mg[i][j]==0)printf(” if(mg[i][j]==1)printf(“ if(mg[stack->row][stack->col+1]== p->next=stack; stack=p;{ p=(mlink 可通)：n”);0)//下面位置可通 *)malloc(sizeof(mlink)); p->row=stack->row;p->col=stack->col+1;□“);//为0的输出□ ■”);//为1的输出■ //入栈 mg[stack->row][stack->col]=1;//将 } else 访问过的标记为1 int Mazepath(int mg[][N+2]){ mlink *p;if(mg[x1][y1]==0){ p=(mlink p->row=x1;p->col=y1;p->next=NULL;stack=p; //将入口 mg[stack->row][stack->col]=1;/while((!(stack->row==NULL& if(mg[stack->row][stack->col-1]==0)//上面可通 //入栈 stack=p; p->next=stack; { p=(mlink *)malloc(sizeof(mlink)); *)malloc(sizeof(mlink)); p->row=stack->row;p->col=stack->col-1;放入堆栈 /标志入口已访问 &stack->col==NULL))&&(!(stack->row==x2&&stack->col==y2)))//循环条件直到找到输入的出口 { mg[stack->row][stack->col]=1;//将 访问过的标记为1 数据结构课程设计 迷宫 void tonglu()//将坐标的顶点输出 { 始化 printf(“(%d%3d)n”,q->row,q->col); 情况 else printf(“□”);//0的 } q=stack;{ } for(i=0;i for(j=0;j = while(q!=NULL)//循环条件 q=q->next;for(j=0;j 情况 } void create(int mg[][N+2])//创建和菜单 { int i,j,x,choice,flag1=1;chushi();while(flag1){ } printf(“n”);printf(“所有通道为（由下而q=stack;{ 上）：n”);while(q!=NULL)//循环条件 printf(“ ## printf(”# n“); *********选择菜单********** #n”); printf(“ ## printf(”输入选项：“);scanf(”%d“,&choice);switch(choice){ case 1://手动建立迷宫 { shuru(); printf(”手动建立for(i=1;i<=m;i++) n“); printf(”# 1-手动生成迷 宫 2-自动生成迷宫 3-退出 #n“);0;//将路径中的点赋给辅助数组a 形的界面输出 迷宫矩阵(0表示可通1表示障碍):n”); for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]); 数据结构课程设计 航班信息查询与检索系统 题目二 1.设计内容 1.1问题描述 设计一个航班信息查询系统，提供信息的管理和使用功能，管理包括更新、添加、删除功能。 1.2设计要求 （1）原始信息存储在文件中，记录不少于50条。（2）用户界面至少包括以下功能： 创建 修改（插入、添加、删除、更新） 查询 浏览 退出管理系统（3）航班信息包括： 航班号：字符序列，具体字符表达的意思上网查询 起点站和终点站：字符串 班期：指一周中哪些天有航班 起飞时间：可将时间定义成一个时、分组成的序列 到达时间：可将时间定义成一个时、分组成的序列 机型：字符序列，具体字符表达的意思上网查询 票价：整型数，具体值可上网查询 （4）创建是指从文件中读取数据，并存入所定义的顺序表中。 （5）可按航班号、起点站、终点站、起飞时间、到达时间等进行查询。查询时要用到顺序查找、二分查找方法。输出查询结果时必须排序。 （6）可按航班号、起点站、起飞时间、票价进行删除和更新操作，删除的记录存入另外的文件中，作为日志文件保存。 （7）作插入操作前，先对信息按起点站进行排序。新记录插入为起点站相同的最后一条记录。 数据结构课程设计 航班信息查询与检索系统 typedef struct node { Time rh;Time lv;}Pnode;（2）飞机结构体： struct Plane { };（3）静态链表： typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price;}Sqlist;2.3 详细设计（1）主函数： do{printf(“* * * * * * * * * * * * * 航班查询系统* * * * * * * * * * * * *n”); printf(“* 1.创建 2.修改 3.查询 4.浏览 5.表长 6.文件 0.退出 *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *n”); scanf(“%d”,&opt);switch(opt){ case 1:Initlist(L);break; case 2:handle(L);break; case 3:search(L);break; case 4:print(L);break;case 5:Get_Sq(L);break;case 6:File(L);break; 数据结构课程设计 航班信息查询与检索系统 } }while(opt!=0);} （4）文件操作： void File(Sqlist &L){ int ch;do{ printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”); printf(“* *n”); printf(“* 1.保存信息到文件 2.从文件读取信息 0 退出 *n”); printf(“* *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”); printf(“请输入选项n”); scanf(“%d”,&ch); switch(ch) { case 1:SaveList(L);break; } }while(ch!=0);case 2:ReadList(L);break; case 0:printf(“退出！n”);break;} （5）浏览信息：就是循环使用输出函数，在此就不必多说了 2.4 调试分析 （1）在课设过程中，遇到问题时，通过与同学、老师交流，在图书馆查阅资料，使问题得以解决。 （2）算法中有许多不是很优化的地方。3.用户使用说明 程序运行后用户根据提示输入要进行的操作选项（应先选择创建选项，这样可以直接读取保存好的文件），然后选择要进行的操作选项。由于主菜单中有修改、查询和浏览项目，每个项目又有各自的子菜单，所以在进行管理和使用时要注意输入的元素是否正确，需按照提示输入。输入操作元素时，元素之间以空格隔开。程序将按输入的操作元素找到相应的算法，然后进行处理，然后将结果打 数据结构课程设计 航班信息查询与检索系统 图2-2 查询信息 图2-3插入 图2-4删除 数据结构课程设计 航班信息查询与检索系统 时就需要重新写出一个子函数，哪怕这个子函数就是在原有的一个子函数的基础上改那么一丁点的地方，例如航班信息查询系统中的查询函数，其实每个子函数只是改了一下关键码而已。 6.附录 #include { } void search_key(Sqlist L)//按航班号查找 { 号：“); Time rh;Time lv; scanf(”%s“,n);int i; printf(”此航班的航班号，起点char n[20]; printf(“请输入要查找的航班 printf(”%dn“,L.length);//表长 }Time;typedef struct node { }Pnode;struct Plane { };typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price; 终点，班期，起飞时间，到达时间，票价：n”); if(strcmp(L.plane[i].key,n)==0) ted，L.plane[i].sche,L.plane[i].lv.hour,L.{ for(i=L.length-1;i>=0;i--){ printf(“%s %s %s %d:%d % d:%d %dn”,L.plane[i].key,L.plane[i].s}Sqlist;int get_Sq(Sqlist &L){ } void Get_Sq(Sqlist &L)return L.length; plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane [i].price); 0数据结构课程设计 航班信息查询与检索系统 printf(“此航班的航班号，起点 ted，{ 终点，班期，起飞时间，到达时间，票价：n”); if(L.plane[i].lv.hour<=hour) ted，L.plane[i].sche,L.plane[i].lv.hour,L.{ for(i=L.length-1;i>=0;i--){ printf(“%s %s %s %d:%d % d:%d %dn”,L.plane[i].key,L.plane[i].s L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane } void search(Sqlist L){ int i;do { printf(“* * * * * * * * * * * } } printf(”%s %s %s %d:%d %d:%d %dn“,L.plane[i].key,L.plane[i].s[i].price);plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane } void search_rh(Sqlist L){ int hour;printf(”请输入你所要求的最scanf(“%d”,&hour);printf(“此航班的航班号，起点 } } [i].price); * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”); printf(“* 1.航班号查询 2.起点终点查询 3.班期查询 4.起飞时间查询 5.到达时间查询 0.退出 *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”); scanf(“%d”,&i); switch(i) { case 晚时间：“);终点，班期，起飞时间，到达时间，票价：n”); if(L.plane[i].rh.hour<=hour)for(int i=L.length-1;i>=0;i--){ 1:search_key(L);break; 2数据结构课程设计 航班信息查询与检索系统 n“); } else { } printf(”查找不成功。 i--;if(i==0) { char c[20]; printf(“输入修改后的scanf(”%s“,c); 内容：”); strcpy(L.plane[i].sche,c); printf(“修改成功！n”);}break;{ int a,b; printf(“输入修改后的int opt;printf(”选择修改对象：“);scanf(”%d“,&opt);switch(opt){ case 1: printf(”修改成功！n“);printf(”修改成功！n“);{ char a[10];printf(”输入修改后的scanf(“%s”,a); case 4: 内容：“); char b[20];printf(”请输入修改后scanf(“%s”,b); scanf(“%d:%d”,&a,&b); L.plane[i].lv.hour=a;L.plane[i].lv.min=b;printf(“修改成功！n”);航班号：“); }break;{ int a,b; printf(”输入修改后的strcpy(L.plane[i].key,a);}break;{ case 5: case 2: 内容：“); scanf(”%d:%d“,&a,&b); L.plane[i].rh.hour=a;L.plane[i].rh.min=b;printf(”修改成功！n“);的内容：”);strcpy(L.plane[i].sted,b);}break; }break;{ int a; case 6: case 3: 4数据结构课程设计 航班信息查询与检索系统 *n“); printf(”* * * * * * * * * * * * * * * * * * * * * * * * *n“); printf(”请输入选项n“); scanf(”%d“,&ch); switch(ch) { case 1:SaveList(L);break;case 2:ReadList(L);break; L.plane[i].sche,&L.plane[i].lv.hour，&L.plane[i].lv.min,&L.plane [i].rh.hour,&L.plane[i].rh.min,&L.pl } void delet_Sq1(Sqlist &L){ char n[10];int i,j; printf(”请输入您要删除的航scanf(“%s”,n);if(L.length==0){ printf(“没有选项！n”);for(i=0;i L.length++; ane[i].price); case 0:printf(“退出！n”);break; } void Initlist(Sqlist &L)//插入存储 { “); 容：”);价n“); scanf(”%s%s%s%d:%d%d:%d%d“,L.plane[i].key,L.plane[i].sted, for(i=0;i 班期 起飞时间 到达时间 票scanf(”%d“,&n);L.length=0;L.plane=(Plane if(!L.plane)exit(0);printf(”请输入顺序表中的内 int i,n;printf(“输入表中航班的数量： } }while(ch!=0); 班号：”); if(strcmp(L.plane[i].key,n)==0) { printf(“所删除的班机*)malloc((n+10000)*sizeof(Plane));的信息：n”); printf(“n航班号 起点终点 printf(”%s %s %s %d:%d %d:% d %dn“,L.plane[i].key,L.plane[i].sted，L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane [i].price); 6数据结构课程设计 航班信息查询与检索系统 n”);} printf(“无法打开文件！} }while(opt!=0); void insert_Sq(Sqlist &L){ 数量 价n”); for(i=0;i printf(“* * * * * * * * * * * scanf(”%s%s%s%d:%d%d:%d%d“,&L.plane[L.length].key,&L.plane[L.length].sted，&L.plane[L.length].sche,&L.plane[ { int a=get_Sq(L); printf(”请输入要添加班机的scanf(“%d”,&n); printf(“请输入要添加的班机printf(”n航班号 起点终点 int i,n; //n表示添加的fprintf(fp,“航班号：%sn起点站：%s 终点站：%sn班期：%dn起飞时间：%d:%d 到达时间：%d:%dn价格：%dnn”, p.key,p.sted,p.sche,p.lv.hour,p.lv.mi n“);} void delet_Sq(Sqlist &L){ int opt;do { fclose(fp);printf(”保存删除的信息成功。n,p.rh.hour,p.rh.min,p.price); 数量：“); 信息：n”); 班期 起飞时间 到达时间 票* * * * * * * * * *n“); printf(”* 1.航班号删除 printf(“* * * * * * * * * * printf(”输入你的选择：“);2.路线删除 0.退出 *n”);* * * * * * * * * * *n“); scanf(”%d“,&opt); switch(opt){ case 1:delet_Sq1(L);break; case 2:delet_Sq2(L);break; case 0:printf(”退出。} L.length].lv.hour,&L.plane[L.length].lv.min，&L.plane[L.length].rh.hour,&L.plan e[L.length].rh.min,&L.plane[L.length].price); } void handle(Sqlist &L){ } L.length++; n");break;第二篇：南航计算机软件数据结构上机实践报告
第三篇：数据结构实训报告
第四篇：数据结构课程设计报告 封面
第五篇：数据结构课程设计报告
点击咨询 