第一篇：数据结构上机作业
实验一 线性表
一、实验题
线性表的应用———多项式计算
二、程序设计思路
包括每个函数的功能说明，及一些重要函数的算法实现思路一链式存储：
1.void InitPoly(LNode *&p)初始化多项式 2.void TraversePoly(LNode *&p)遍历多项式 3.void ClearPoly(LNode *&p)清除多项式
4.void InsertPoly(LNode *&p, double a, int e)插入一项 5.void DeletetPoly(LNode *&p,int pos)
删除一项
6.double PolySum(LNode *&p, double x)
多项式求值 7.LNode * PolyAdd(LNode *&p1,LNode *& p2)
多项式相加 顺序存储：
1.void InitPoly1(SeqList &L)初始化多项式 2.void ClearPoly1(SeqList &L)清除多项式 3.void TraversePoly1(SeqList L)
遍历多项式
4.bool InsertPoly1(SeqList &L, ElemType item)插入一项 5.double PolySum1(SeqList L,double x)
多项式求值 6.bool DeleteList1(SeqList &L,int pos)
删除一项
7.SeqList PolyAdd1(SeqList &L1,SeqList& L2)
多项式相加
三、源程序代码
#include
{ if(pos>1||pos<-1)return false;NodeType *cp=p->next;NodeType *np=p;if(pos==0){ while(cp!=p){ if(cp->coef==a&&cp->exp==e)break;else{ np=cp;cp=cp->next;} } } else if(pos==-1)while(cp!=p){
删除np=cp;cp=cp->next;} np->next=cp->next;delete cp;return true;} double PolySum(NodeType *p, float x)//多项式求值 { int i;double sum=0,item;NodeType *cp=p->next;while(cp!=p){ item=1;for(i=1;i<=cp->exp;i++)item=item*x;sum=sum+item*cp->coef;cp=cp->next;} return sum;} NodeType *PolyAdd(NodeType *p1, NodeType *p2)//多项式相加 { float coef;NodeType *a=p1->next,*b=p2->next,*c,*pc;InitPoly(c);pc=c;while(a!=p1&&b!=p2){ if(a->exp==b->exp){ coef=a->coef+b->coef;if(coef!=0){ InsertPoly(pc, coef, a->exp);pc=pc->next;} a=a->next;b=b->next;} else if(a->exp 输出多项式 } void ClearPoly1(ListType &p)//清除多项式 { if(p.list!=NULL){ delete []p.list;p.list=NULL;} p.size=0;} void InsertPoly1(ListType &p, float a, int e)//项 { p.list[e]=a;if(p.size { int i,n;if(p.size==0){ cout<<“多项式为空,删除无效!”< 插入一if(p.list[e]==a)p.list[e]=0;else if(pos==-1)p.list[p.size]=0;return true;} double PolySum1(ListType p, float x)//值 { double sum=0,item;int i,j;for(i=0;i<=p.size;i++){ item=1;for(j=1;j<=i;j++)item=item*x;sum=sum+item*p.list[i];} return sum;} ListType PolyAdd1(ListType p1, ListType p2)//项式相加 { ListType p;InitPoly1(p);float coef; 多项式求多int i,j;for(i=0;i<=p1.size;i++){ coef=p1.list[i]+p2.list[i];InsertPoly1(p, coef, i);} if(i<=p1.size)for(j=i;j<=p1.size;j++)InsertPoly1(p, p1.list[j], j);if(i<=p2.size)for(j=i;j<=p2.size;j++)InsertPoly1(p, p2.list[j], j);return p;四实验结果分析 五.心得体会 对于结构体的认识增加了，对于动态存储也有了更多的认识，也是在不知不觉中提高了。 实验二 字符串的操作 一、实验题目——字符串的操作 二、程序设计思路 采用定长顺序存储表示，由用户创建串s和串t，实现在串s中下标为pos的字符之前插入串t。 三、源程序代码 #define MAXLEN 10 typedef struct { /*串结构定义*/ char ch[MAXLEN]; int len;}SString;void createstring(SString *s) /*创建串s*/ { int i,j;char c;printf(“input the length of the string:”); scanf(“%d”,&j); for(i=0;i { printf(“input the %d:”,i+1); fflush(stdin); scanf(“%c”,&c); s->ch[i] = c; } s->len = j;} void output(SString *s) /*输出串s*/ { int i;for(i=0;i printf(“%c ”,s->ch[i]); printf(“n”);} int StrInsert(SString *s, int pos, SString *t)/*在串s中下标为pos的字符之前插入串t */ { int i;if(pos<0 || pos>s->len) /*插入位置不合法*/ return(0); if(s->len + t->len<=MAXLEN) /*插入后串长≤MAXLEN*/ { for(i=s->len + t->len-1;i>=t->len + pos;i--) s->ch[i]=s->ch[i-t->len];/*将下标为pos的字符后的元素往后移动t->len个长度*/ for(i=0;i s->ch[i+pos]=t->ch[i]; /*将串t从下标为pos位置开始插入到串s*/ s->len=s->len+t->len;} else { if(pos+t->len<=MAXLEN)/*插入后串长>MAXLEN,但串t的字符序列可以全部插入*/ { for(i=MAXLEN-1;i>t->len+pos-1;i--) s->ch[i]=s->ch[i-t->len]; for(i=0;i s->ch[i+pos]=t->ch[i]; /*将串t从下标为pos位置开始插入到串s*/ s->len=MAXLEN; } else /*插入后串长>MAXLEN,并且串t的部分字符也要舍弃*/ { for(i=0;i s->ch[i+pos]=t->ch[i]; /*直接从下标为pos的位置按顺序插入串t*/ s->len=MAXLEN; } return(1);} } void main(){ SString *str1;SString *str2;int i,j,k,pos;int flag=0;str1 =(SString *)malloc(sizeof(SString));str1->len = 0;printf(“creat the string 1:n”);createstring(str1);printf(“creat the string 2:n”);createstring(str2);printf(“input the insert local:”);scanf(“%d”,&pos);flag=StrInsert(str1,pos,str2);if(flag == 0) printf(“insert error!”);else { printf(“after insert:n”); output(str1);} } 四、实验结果 五、实验体会 通过本次实验，我加深了对串数据结构的理解。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。在存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率。 实验三 一、实验题目——非递归算法对二叉树进行中前序遍历 二、程序设计思路 创建一棵10个节点构造的完全二叉树，并对其进行前、中、后序遍历。 三、源程序代码 #define STUDENT EType #define SType SType #define HeadEType int #include //定义数据结构类型 struct STUDENT { char name[8];int age;char number[15];char address[20];}; struct BinaryTreeNode { EType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;};typedef BinaryTreeNode BinaryTree; typedef struct { BinaryTreeNode *ptr;bool status;}SType; typedef struct { SType *element;int top;int MaxSize;}Stack; void CreatStack(Stack &S, int MaxStackSize){// 构造一个最大容量为MaxStackSize 的堆栈 S.MaxSize = MaxStackSize; S.element = new SType[S.MaxSize]; S.top =-1;} bool IsEmpty(Stack &S){// 判断堆栈S是否为空 if(S.top ==-1) return true; return false;} bool IsFull(Stack &S){// 判断堆栈S是否为空 if(S.top == MaxSize-1) return true; return false;} bool Push(Stack &S , SType &x){// x进s栈，返回进栈后的状态值 if(IsFull(S)) return false; S.top++; S.element[S.top] = x; return true;} bool Pop(Stack &S , SType &x){// 将s栈顶的值取至x中，返回出栈后的状态值 if(IsEmpty(S)) return false; x = S.element[S.top]; S.top--; return true;} BinaryTreeNode *MakeNode(EType &x) {//构造结点 BinaryTreeNode *ptr; ptr = new BinaryTreeNode; if(!ptr)return NULL; ptr->data = x; ptr-> LChild = NULL; ptr-> RChild = NULL; return ptr;} void MakeBinaryTree(BinaryTreeNode *root, BinaryTreeNode *left, BinaryTreeNode *right){// 联接root，left, right所指的结点指针为二叉树 root->LChild=left; root->RChild=right;} void PreOrderNoRecursive(BinaryTreeNode *BT){//二叉树前序遍历非递归的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假设堆的空间足够大，即MaxStackSize值足够大 CreatStack(S,MaxStackSize);//产生一个空栈 while(q||!IsEmpty(S)){ if(q) { cout< ele.ptr=q; Push(S,ele);//节点指针进栈，以后回溯时在退栈 q=q->LChild;//指针指向刚刚被访问的“根”节点的左子树 } else //当左子树为空时，利用堆栈回溯 if(!IsEmpty(S)) { Pop(S,ele);//退栈回溯 q=ele.ptr;//指针重新指向刚刚被访问的“根”节点 q=q->RChild;//指针指向该回溯节点的右子树 } } } void InOrderNoRecursive(BinaryTreeNode *BT){//二叉树的中序遍历非递归的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假设堆的空间足够大，即MaxStackSize值足够大 CreatStack(S,MaxStackSize);//产生一个空栈 while(q ||!IsEmpty(S)){ while(q)//找到最左边的子树 { ele.ptr=q; Push(S,ele);//指针非空时，将当前的“根”节点指针进栈，用于以后回溯 q=q->LChild;//指针继续指向该“根”节点的左子树 } if(!IsEmpty(S))//当左子树为空时，进行退栈回溯 { Pop(S,ele);//从堆栈中回溯节点指针（节点还未访问） q=ele.ptr; cout< q=q->RChild;//指针向回溯的节点右子树推进 } } } void PostOrderNoRecursive(BinaryTreeNode *BT){//二叉树的后序遍历非递归的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假设堆的空间足够大，即MaxStackSize值足够大 CreatStack(S,MaxStackSize);//产生一个空栈 while(q ||!IsEmpty(S)){ if(q)//找最左边的子树 { ele.ptr=q; ele.status=false;//进栈前标记为第一次进栈 Push(S,ele); q=q->LChild;//指针继续向左推进 } else if(!IsEmpty(S))//直到左子树为空时，退栈回溯 { Pop(S,ele);//从堆栈中弹出回溯节点（还未访问） q=ele.ptr;//q指向当前回溯节点 if(ele.status)//判断节点进栈标志，是否对其进行访问 { cout< q=NULL;//将q设为空，为了继续退栈 } else { ele.status=true;//改变回溯节点的进栈标记，以便再次进栈 Push(S,ele); q=q->RChild;//指针向该回溯节点的右孩子推进 } } } } //主函数 void main(){ BinaryTreeNode *ptr[11]; char Name[][8]={“ ”,“A”,“B”,“C”,“D”,“E”,“F”,“G”,“H”,“I”,“J”};EType x[11];for(int i=1;i<11;i++){ strcpy(x[11-i].name,Name[11-i]); ptr[11-i]=MakeNode(x[11-i]);//构造10个二叉树节点 } //将节点链接域填值，构造一个二叉树 //这里构造的是一棵有10个节点的完全二叉树 for(int j=1;j<5;j++){ MakeBinaryTree(ptr[j],ptr[2*j],ptr[2*j+1]);} MakeBinaryTree(ptr[5],ptr[10],NULL);//该完全二叉树构造完毕 //***********对已构造的完全二叉树进行前序非递归遍历************// cout<<“对该二叉树进行前序遍历结果：”< //***********对已构造的完全二叉树进行中序非递归遍历************// cout< //***********对已构造的完全二叉树进行中序非递归遍历************// cout< 四、实验结果分析 五、实验总结 二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。 实验四 一、实验题目——深度优先算法实现图的遍历 二、程序设计思路 以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先，并输出遍历的结点序列。首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先，并输出遍历的结果。 三、源程序代码 #include };struct vexnode { char vertex;edgenode* edgelink;};struct Graph { vexnode adjlists[MaxVerNum];int vexnum;int arcnum;};//队列的定义及相关函数的实现 struct QueueNode { int nData;QueueNode* next;};struct QueueList { QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e){ QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q==NULL) return;if(Q->rear==NULL) Q->front=Q->rear=q;else { Q->rear->next=q; Q->rear=Q->rear->next;} } void DeQueue(QueueList* Q,int* e){ if(Q==NULL) return;if(Q->front==Q->rear){ *e=Q->front->nData; Q->front=Q->rear=NULL;} else { *e=Q->front->nData; Q->front=Q->front->next;} } //创建图 void CreatAdjList(Graph* G){ int i,j,k;edgenode* p1;edgenode* p2;cout<<“请输入顶点数和边数:”< cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL;} cout<<“开始输入边表信息:”< cout<<“请输入边 cin>>i>>j; p1=new edgenode; p1->endver=j; p1->edgenext=G->adjlists[i].edgelink; G->adjlists[i].edgelink=p1; p2=new edgenode; p2->endver=i; p2->edgenext=G->adjlists[j].edgelink; G->adjlists[j].edgelink=p2; //因为是无向图，所以有两次建立边表的过程 } } //------------------------------深度优先遍历 void DFS(Graph *G,int i,int visit[]){ cout< DFS(G,p->endver,visit);} } void DFStraversal(Graph *G,char c)//深度优先遍历 { cout<<“该图的深度优先遍历结果为:”< visit[i]=0;//全部初始化为0，即未访问状态 } int m;for(i=0;i if(G->adjlists[i].vertex==c)//根据字符查找序号 { m=i; DFS(G,i,visit); break; } } //继续访问未被访问的结点 for(i=0;i if(visit[i]==0) DFS(G,i,visit);} cout< int e=0; DeQueue(Q,&e); cout< visit[e]=1; edgenode* p=new edgenode; p=G->adjlists[e].edgelink; if(p) { int m=p->endver; if(m==0) { EnQueue(Q,m); while(visit[m]==0) { p=p->edgenext; if(p==NULL) break; m=p->endver; EnQueue(Q,m); } } } } } void BFStraversal(Graph *G,char c){ cout<<“该图的广度优先遍历结果为:”< visited[i]=0;} int m;for(i=0;i if(G->adjlists[i].vertex==c) { m=i; BFS(G,i,visited); break; } } //继续访问未被访问的结点 for(i=0;i if(visited[i]==0) BFS(G,i,visited);} cout< 四、实验结果及分析 五、实验总结 本次试验采用的是邻接表的方式实现图的深度优先遍历和。对于深度优先遍历，主要是采用递归的方式。试验本身问题不是太大，但要注意输入的问题，什么时候用空格，什么时候用回车，这一点是需要注意的，因为一旦数据的输入有问题，结果当然也就不可能正确了。只有正确的输入数据，建立图，才能得出正确的遍历结果。 “计算机软件技术基础”课程实验报告 （六）实验名称：数据库及SQL语言 班级_______ 姓名__________ 学号______实验日期： 实验机时：3 学时实验成绩： ----------------- 一.实验目的： 1、学习数据库设计的一般过程及相关技术； 2、学习access数据库管理系统； 3、掌握数据库的输入、查询、更新操作。 二.实验内容： 1、需求陈述：某校图书馆要建立一个图书数据管理系统。该图书馆的图书（书名、分类号、作者、出版社）存放在不同的借阅室（室名），读者（姓名、系名、类别）在书架上找到所需图书后，可以到服务台办理借阅（借阅时间）。 设计要求： 分析需求，建立数据库的概念模型； 将概念模型转换为关系模型（注意：是否需要作规范化处理）； 写出创建基本表的SQL语句； 写出以下查询要求的SQL语句： （1）所有“高等数学习题集”书的信息； （2）读者“李林”借了什么书？ （3）“社会学原理”在哪个借阅室？ 2、在access数据库管理系统中建立所设计的关系表； 3、向各表中输入一组实验数据（元组）（注意：关系完整性）； 4、对数据库进行查询。 三.实验结果： 1、实体-关系图； 2、数据库表； 3、创建基本表的语句； 4、查询语句。 “计算机软件技术基础”课程实验报告 （五）实验名称：排序算法 班级_______ 姓名__________ 学号______实验日期： 实验机时：3 学时实验成绩： ----------------- 一.实验目的： 1、掌握主要排序算法的思想和实现技术。 二.实验内容： 1、设计一程序，要求：输入学生“软件技术基础”课的成绩（学 号、姓名、平均成绩、总学分）；按总学分对学生数据进行排序。（要求：实现任选3种排序算法） 三.程序： 1、程序规范（输入数据、功能、输出数据） 2、设计分析（数据表示、算法） 3、C源代码（电子版） 四.程序调试： 数据结构实验报告 课程 数据结构 _ 院 系 专业班级 实验地点 姓 名 学 号 实验时间 指导老师 数据结构上机实验报告1 一﹑实验名称： 实验一——链表 二﹑实验目的： 1.了解线性表的逻辑结构特性； 2.熟悉链表的基本运算在顺序存储结构上的实现，熟练掌握链式存储结构的描述方法； 3.掌握链表的基本操作（建表、插入、删除等）4.掌握循环链表的概念，加深对链表的本质的理解。5.掌握运用上机调试链表的基本方法 三﹑实验内容： （1）（2）（3）（4）创建一个链表 在链表中插入元素 在链表中删除一个元素 销毁链表 四﹑实验步骤与程序 #include LinkList p,q;L=(LinkList)malloc(sizeof(Lnode));L->next=NULL;q=L; cout<<“请输入一个链表：”< for(int i=0;i { p=(LinkList)malloc(sizeof(Lnode)); cin>>p->data; p->next=q->next; q->next=p; q=p; } } int PrintLinkList(LinkList &L){//输出链表L的数据元素 LinkList p; } void LinkListLengh(LinkList &L){//计算链表L的数据元素个数。int i=0;p=L->next;if(L->next==NULL){ } cout<<“链表的数据元素为:”;while(p) { cout< data<<“ ”; p=p->next;} cout<<“链表没有元素!”< } LinkList p;p=L->next;while(p){ i++; p=p->next; } cout<<“链表的数据元素个数为:”< LinkList p,s;int j=0;p=L; while(p&&j } if(!p||j>i-1){ p=p->next;++j; } } 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 } if(!(p->next)||j>i-1){ p=p->next;++j; } } cout<<“删除元素的位置不合理!”;return 0;q=p->next;p->next=q->next;i=q->data;free(q);return 1;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<<“链表已经被销毁!”< LinkList L; int i,j,x;cout<<“第一次数据结构上机实验—链表”< 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); cout<<“销毁程序后为:”< DestroyLinkList(L);} 五﹑实验结果 六﹑实验心得体会： 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。 实验的程序设计规划（实现的功能、分几个模块、子函数）（1）编写链表创建子函数void CreatLinkList(L,j)（2）编写链表插入子函数 int InsertLinkList(LinkList &L, int i, int x)（3）链表的打印int PrintLinkList(LinkList &L)（4）编写链表删除子函数 int DeleteLinkList(LinkList &L,int i)（5）编写链表销毁子函数void DestroyLinkList(LinkList &L)（6）编写主函数Main()，通过功能菜单调用子函数（7）编译调试程序 经过多次的调试，修改，实验结果终于正确了，在这个过程中，经历了不知道怎么进行声明区的编写如包含文件，宏定义，函数声明，全局变量声明，结构体等的定义等的结合，到学会了使用先把程序主要规划为四个部分来写就简单多了，第一，定义；第二，写所要调用的子函数；第三，写主函数，调用子函数；第四就是程序的编译与调试，修改。数据结构实验需要我们对每个程序的算法有深刻的理解，才能应用到实际中去，因此我们需要在做实验之前要熟悉实验的内容，且先把所要实验的程序写出来，在实验中就可以查找错误并加以改正，这是一个成长的过程。 数据结构上机实验报告一﹑实验名称： 实验二—队列 二﹑实验目的： 1.掌握队列这种抽象数据类型的特点, 掌握栈与队列在实际问题中的应用和基本编程技巧,并能在相应的问题中选用它;2.熟练掌握循环队列和链队列的基本操作实现算法，特别是队满和队空的描述方法； 3．掌握栈与队列的数据类型描述及特点； 4.掌握栈的顺序和链式存储存表示与基本算法的实现； 5.掌握队列的链式存储表示与基本操作算法实现;6.按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数据的运行过程抓获相关屏面验证程序设计的正确性； 7.认真书写实验报告，并按时提交。 三﹑实验内容： 对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）掌握栈和队列的特点，即后进先出和先进先出的原则。（2）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （3）编写主函数进行测试。 四﹑实验步骤与程序 #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef struct QNode { int data;struct QNode *next;}QNode,*QueuePtr;typedef struct { QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q){ } Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode));if(!Q.rear)exit(OVERFLOW);Q.front->next=NULL;return OK;void QueueEmpty(LinkQueue Q){ } void EnQueue(LinkQueue &Q,int e){ } int EnnQueue(LinkQueue &Q,int e){ QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf(“error”);if(Q.front==Q.rear)printf(“该链队为空:”);else printf(“该链队不为空:”);p->data=e;Q.rear->next=p;Q.rear=p;printf(“元素%d入队成功”,e); } if(!p)return ERROR;p->data=e;Q.rear->next=p;Q.rear=p; return OK;void DeQueue(LinkQueue &Q){ } void GetHead(LinkQueue &Q){ QueuePtr p;QueuePtr p;if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);printf(“队首元素删除成功”); } if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;printf(“队首元素为:%d”,p->data);void OutQueue(LinkQueue &Q){ } void LengthQueue(LinkQueue &Q){ int f=0;QueuePtr p;if(Q.front==Q.rear)QueuePtr p;if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;while(p!=Q.rear->next){ } printf(“%d%,”,p->data);p=p->next; } printf(“该队列的长度为:%d”,f);else { } p=Q.front->next;while(p!=Q.rear->next){ } printf(“该队列的长度为:%d”,f);p=p->next;f++;void main(){ system(“cls”);int flag=1,i;LinkQueue Q;InitQueue(Q);printf(“************************链队列功能菜单***********************n”);printf(“1:初始化链队列，2:判断链队列是否为空, 3:进入队列，4:取出队首元素n”);printf(“5:输出该队列的所有元素,6:输出该队列的长度，7:结束程序，8:清屏n”); while(flag){ printf(“n请输入操作符:”);scanf(“%d”,&i);switch(i){ case 1: int e,n,k;printf(“请输入队列的长度:”);scanf(“%d”,&n);printf(“请输入队列的元素:”);for(e=1;e<=n;e++){ } printf(“初始化链队成功”);break;scanf(“%d”,&k);EnnQueue(Q,k);case 2: QueueEmpty(Q); break;case 3: int j;printf(“请输入要进入队列的元素”);scanf(“%d”,&j);EnQueue(Q,j);break;case 4: GetHead(Q);break;case 5: printf(“该队列的元素为:”);OutQueue(Q);break; case 6: LengthQueue(Q);break;case 7: flag=0;break;case 8: system(“cls”);} break; } } 五﹑实验结果 六﹑实验心得体会： 程序主要构造了主函数main（）和 InitQueue（），QueueEmpty（）EnQueue()，OutQueue()等调用函数，实现了队列的创立，队列是否为空的判断，入队和出队等功能。 通过此次实验，加深了对队列的存储结构的了解，同时也对程序设计能力有了提高，加深了对队列先进先出性质的理解，它允许在表的一端进行插入，在另一端删除元素，这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。我们往往写不出程序，这其中的原因我觉得是对程序的结构不是很了解，对实验的内容也不熟练的结果，数据结构给我们许多程序的算法和模型，对我们写程序的思维有很大的锻炼，我们应珍惜每次上机实验的机会去实践课堂上所学的东西并从中发现问题，从而达到提升写程序的能力。 数据结构上机实验报告一﹑实验名称： 实验三—二叉树的遍历 二﹑实验目的： 1、熟悉二叉树的结构特性，了解相应的证明方法； 2、掌握二叉树的生成，掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法； 3、理解二叉树的三种遍历方法：先序遍历、中序遍历和后序遍历； 4、学会编写实现树的各种操作的算法。 二、实验内容： 1、使用类定义实现二叉树，补充完整所缺的函数，并实现创建和遍历二叉树的基本操作； 2、编程实现在二叉链表这种存储方式下，实现二叉的遍历，可采用递归或者非递归实现，遍历算法为在先序、中序和后序遍历算法。 三、实验步骤与程序： #include void PreOrder(BiTree T)//先序 { if(T!=NULL){ printf(“%c”,T->data);PreOrder(T->lchild);PreOrder(T->rchild);} } void InOrder(BiTree T)//中序 { if(T!=NULL){ InOrder(T->lchild);printf(“%c”,T->data);InOrder(T->rchild);} } void PostOrder(BiTree T)//后序 { if(T!=NULL){ PostOrder(T->lchild);PostOrder(T->rchild);printf(“%c”,T->data);} } void main()//主函数 { printf(“------------二叉树的遍历-------------n”);printf(“请输入要遍历的数：”);BiTree Ta;Ta=CreateBiTree();printf(“先序遍历:”);printf(“n”);PreOrder(Ta);printf(“n”);printf(“中序遍历:”);printf(“n”);InOrder(Ta);printf(“n”);printf(“后序遍历:”);printf(“n”);PostOrder(Ta);} 五﹑实验结果 六﹑实验心得体会： 实验的程序设计规划（实现的功能、分几个模块、子函数）（1）先序遍历递归算法函数：void PreOrder(BiTree T)（2）中序遍历递归算法函数：void InOrder(BiTree T)（3）后续遍历递归算法函数：void PostOrder(BiTree T)（4）主函数的实现：void main() 在实验前我认真阅读关于二叉树的实现的内容，为编程实现第一步，本次实验通过按上述的实验步骤一步步实现的，实验过程中出现了一些错误，经过一步步的调试，修改错误，得到了二叉树的遍历用递归运算的方法的程序。通过这个实验，我体会到了理解数据结构的重要性，这有真正理解了定义数据类型的好处，才能用好这样一种数据结构。二叉树的先序，中序与后序的输出都用了递归的算法，而且用起来不是很复杂，这使我更进一步理解了函数递归调用并得到灵活运用；在实现算法上，从算法的效率看，递归方法书写形式较为简洁，更为直观，一般具有较好的空间效率。 总之，不管做什么实验，我们在做实验前都要先预习，对所做的实验有较深的理解，在做实验的时候需要很严谨，仔细的查找错误，从而能在实验中收获知识，提升自己。 数据结构上机实验报告4 一﹑实验名称： 实验四—查找 二﹑实验目的： 1、熟悉掌握顺序表的查找方法； 2、熟练掌握二叉排序树的构造方法和查找算法 3、掌握描述查找过程的判定树的构造方法，以及按照定义计算各种查找方法在等概率情况下查找成功时的平均查找长度； 4、学会定义线性表的储存类型，实现C++程序的基本结构对线性表的一些基本操作和具体的函数定义； 5、掌握顺序表的基本操作，实现顺序表的查找的等基本运算； 6、掌握对于多函数程序的输入，编辑，调试和运算过程。 二、实验内容： 1、实现顺序表的查找算法 2、关于衡量查找的主要操作—查找的查找平均效率的平均长度的讨论。 三、实验步骤与程序： #include element list[MAX_SIZE]; int seqsearch(element list[],int searchnum,int num);int main(){ int i,num,searchnum,k; printf(“---------------数据结构查找实验-------------n”);printf(“请输入数据元素的个数：”);scanf(“%d”,&num);printf(“请输入数据的元素：n”);for(i=0;i printf(“请输入要查询的数据元素:”);scanf(“%d”,&searchnum);k=seqsearch(list,searchnum,num);if(k!=-1){ printf(“所查询元素的下标为：”);printf(“%dn”,k);} else printf(“查询元素不存在。n”);} return 0;} int seqsearch(element list[],int searchnum,int num){ int j; list[num].key=searchnum; for(j=0;list[j].key!=searchnum;j++);return j 六﹑实验心得体会： 实验的程序设计规划为先写一个主函数int main()，再写一个查找的子函数int seqsearch(element list[],int searchnum,int num)，主函数通过调用子函数的方法实现程序的设计。 所谓“查找”即为在一个众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录），通过本次实验，我更进一步的了解数据结构程序实验设计实现算法的基本模型，和算法实现等基本内容，学会了顺序表的查找方法。 数据结构上机实验报告5 一﹑实验名称： 实验五—内部排序 二﹑实验目的： 1、通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况，并加以灵活应用。 2、掌握各种排序时间复杂度的分析方法。 二、实验内容： 1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。 2、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。 3、讨论各种内部排序方法的基本思路，算法特点，排序过程及它们的时间复杂度的分析。 三、实验步骤与程序： #include } int x;void charu();void kuaisu();printf(“----------内部排序---------n”);printf(“ 1、插入排序：n”);printf(“ 2、选择排序：n”);printf(“请根据序号选择：”);scanf(“%d”,&x);if(x==1)charu();else kuaisu();void charu(){ int a[7],j,i,m; printf(“插入排序n”); printf(“请输入个您想排序的数据:n”); for(i=0;i<7;i++)scanf(“%d”,&a[i]); for(j=1;j<7;j++) { m=a[j]; for(i=j-1;i>=0;i--) { if(a[i] break; else a[i+1]=a[i]; } a[i+1]=m; } printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} quick(int first,int end,int L[]){ int left=first,right=end,key; key=L[first]; while(left { while((left right--; if(left L[left++]=L[right]; while((left left++; if(left L[left]=key; return left; } quick_sort(int L[],int first,int end) { int split; if(end>first) { split=quick(first,end,L); quick_sort(L,first,split-1); quick_sort(L,split+1,end); } } void kuaisu(){ int a[7],i; printf(“快速排序n”); printf(“请输入个您想排序的数据:n”); for(i=0;i<7;i++) scanf(“%d”,&a[i]); quick_sort(a,0,9); printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} 五﹑实验结果： 六﹑实验心得体会： 排序的功能是将一个数据元素（或记录）的任意序列，从新排成按关键字有序的序列；直接插入排序的稳定性比快速排序高，且算法较简单。本次实验运用到的是插入排序和快速排序。 实习报告 题 目 : 实现一个约瑟夫环程序 班级：031021姓名：王帅学号：03102076 一、需求分析 1． 本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号和密码）。 2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。 3． 程序执行的命令包括： 1)构造单向循环链表；2）进行数值的输入，并作判断分析；3）约瑟夫算法的实现与结果输出；4）结束。 4． 测试数据 m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，（正确的出列顺序为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() { 初始化； for（;;） {} while（命令=开始） { 接受命令； 处理命令； } for（;;） { } } 2）有序表单元模块——实现有序表的抽象数据类型； 3）节点结构单元模块——定义有序表的节点结构； 4）数据输入分析模块——判断输入数据正确有效； 各模块之间的调用关系如下： 主程序模块 ↓ 有序表结构模块 ↓ 节点结构单元模块 ↓ 数据输入分析模块 三、详细设计 1、结点类型，指针类型 TypedefstructLNode{ int code,date;//code 为人所在位置 date为人持有的密码 struct LNode *next; };// 结点类型，指针类型 2、构造单向循环链表 struct LNode *p,*head,*q;//定义头节点，和指针 for(i=2;i<=n;i++) { struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode));//分配 新结点空间 s->code=i; input(s->date); p->next=s; p=p->next; } p->next=head;//根据输入的人数，进行单项循环链表的创建，p指向最后一个结点，并与头节点链接，形成单项循环链表 3、约瑟夫环的程序实现部分 while(n!=1)//判断输入人数，如为1则直接输出结果，不循环 { for(i=1，m=m%n;i { p=p->next; } q=p->next;//找到要删除节点 p->next=q->next;//找到要删除节点的后继，并连接新环m=q->date;//找到下一个密码 printf(“%d”,q->code); free(q);//释放已删除节点空间 n--;//链表长度减一 } printf(“%d”,p->code);//约瑟夫环的结果输出 4、其他函数代码 数值的输入限制 int input() { int y,k,z=0; char c;//元素类型 char a[4];//数组初始化 if(!z)//输入判断，确定位数字或控制字符且位置和密码不为零 { for(y=0;y<4;y++) { c=getch(); if(c>=48&&c<=57)//确定为输入数字 {a[y]=c; putch(c); } else { y--; if(c=='r')//确定输入为控制字符 即回车或者删除 break; else if(c==8) {a[y]='n'; y--;} continue; } } k=atoi(a);//确定最终输入数字的值 printf(“n”); z=k; if(z==0) printf(“ERROR!The number couldn't be 0!n”);// 输入为零，重新输入 } return(k);//数值的返回 5、函数的调用关系图反映程序层次结构 Main→input 四、调试分析 1、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时候会经常出错。比如是输入字母，或者输入0，大于32767溢出； 2、早期的循环过程中没有进行优化，导致循环次数过多，浪费时间； 3、为了输出时美观，分别在input和main函数主体内做了两次，输入非零的判断，浪费了资源； 4、算法的时空分析 为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是do……while循环，复杂度为o（1）; 当n大于1时： 在数据输入中，链表的创建是for循环，时间复杂度为o（n-1） 在约瑟夫环实现程序中，为for循环。时间复杂度为o（m%n-1） 当n=1时，复杂度为o（1）。 五、用户手册 用户根据提示，先输入起始密码m，然后输入人数n，再根据人数，分别输入每个人的密码date，数值均不能为0，否则会提示重新输入，输入为字母则自动丢弃，输入错误可用删除键进行修改，输入完成后按回车键确定本次输入完毕（若输入数字大于9999，则第五位自动转换为下一个数字的起始位，依此类推）。 当n个数字全部输入完毕，则自动显示结果，按任意键则退出本程序。 六、测试结果 第一组：m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，出列顺序为6，1，4，7，2，1，3，5。 第二组： m 的初值为30；n=8，7个人的密码依次为：5，1，6，9，4，7，2，3，出列顺序为6，5，2，3，7，1，4，8。 第三组 : m 的初值为15；n=6，7个人的密码依次为：5，3，4，7，6，9，出列顺序为3，1，2，6，4，5。 七、附录 源程序头文件名清单： #include “malloc.h”//内存空间分配头文件 #include “stdio.h”//输入输出函数头文件 #include “stdlib.h”//input函数中字符串转短整形函数的头文件 #include “conio.h”//最后显示结果、清屏函数头文件第二篇：《数据结构》上机作业——实验报告(六)
第三篇：《数据结构》上机作业——实验报告(五)[推荐]
第四篇：数据结构上机实验报告
第五篇：数据结构上机实验报告
点击咨询 