当前位置：文档之家 › 数据结构实验报告三

数据结构实验报告三

  • 格式：doc
  • 大小：626.05 KB
  • 文档页数：8
5.运行和测试
<1>初始化一个队列。
循环队列：
链队列：
<2>判断是否队空。
循环队列：
链队列：
<3>判断是否队满。
循环队列：
第一组数据：入队n个元素，判断队满
第二组数据：用循环方式将1到99，99个元素入队，判队满
入队
第一组数据：4，7，8，12，20，50
第二组数据：a,b,c,d,f,g
出队
取队头元素
3.数据结构设计
循环队列
4.算法设计
（除书上给出的基本运算（这部分不必给出设计思想），其它实验内容要给出算法设计思想）
求当前队列中的元素个数：书写函数配合出队函数和判对空函数，定义一个整型变量i计数，在一个循环中每出对一次，计数器加一，直到对空，返回i即为队列元素个数。
第二题：首先判断队列是否队满，如果队满打印队满，结束程序，如果队列不满则进行下一步操作，定义一个变量x，从键盘输入其值，判断如果x的值为0，结束程序，如果不为0进入循环，如果x的模运算不等于0，将x入队，反之出队，直到x的模运算等于0，最后通过循环输出队列。
实现:从列不空,删除Q的队头元素用e返回其值，并返回OK,则返回ERROR
Status EnQueue (LinkQueue *Q, QE1emType e) {
QueuePtr p
if (Q->front==Q- >rear)
三、循环队列与链队列性能分析
1.循环队列与链队列基本操作时间复杂度均为0(1);
2.队列的抽象数据队列Data同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。Operation InitQueue(*Q):初始化操作,建立一个空队列Q. DestoryQueue(*Q):若队列Q存在，则销毁它。ClearQueue(*Q):将队列Q清空 GetHead(Q,*e):若队列Q存在且非空,用e返回队列Q的队头元素。EnQueue(*Q,e):若队列Q存在且非空, 插入新元素e到队列Q中并称为队元素。DeQueue(*Q,*e):删除队列Q中队头元素,并用e返回其值QueueL ength(Q)。
循环队列与链队列
队列是一种先进先出(iirst In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。从队列的定义可知，队列的入队操作,其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)。队列的删除操作，与栈不同的是，队列元素的出列是在队头，即小标为0的位置，若要删除一个元素的话， 需要移动队列的所有元素,因此事件复杂度为O(n)。(2)front/rear指针: 为了避免当只有一个元素时，队尾和队头重合使处理变得麻烦，所有引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置,这样当front等于rear时，队列为空(空队列而不是队列还剩下一个元素。
2、链队列结构typedef int QElemType/ *结点结构*/typedef struct QNode{ QElemTypedata; //数据域struct QNode *next; //指针域}QNode,*Queueptr:/*队列的链表结构，*/typedef struct{ Queueptr front,rear; /队头.队尾指针}LinkQueue;3.链队列的入队操作算法:实质为链表尾插入结点，尾指针指向新结点a.为新结点s开辟一段空间, 并判断是否存储分配成功;b.将插入元素存到新结点s的数据域，并初始化s的指针域;c.把拥有元素e新结点s赋值给原队列结点的后继; d.把当前的s设置为队尾结点, rear指向s
数据结构实验报告
姓名
学号
专业班级
指导教师
实验时间
实验地点
（实验名称）
1.实验目标
熟练掌握队列的顺序存储结构和链式存储结构。
熟练掌握队列的有关算法设计，并在循环顺序队列和链队列上实现。
根据具体给定的需求，合理设计并实现相关结构和算法。
2.实验内容和要求
循环顺序队列的实验要求
循环顺序队列结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中直接实现；
实现:插入元素e为Q的新队阮素
Status EnQueue (LinkQueue *Q, QE1 emType e) {QueuePtr s= (QueuePtr) ma11oc (si zeof (Q4.链队列的删除操作算法:緹头结点的后继结点出，将头结点的后继改为他后面的结点,若链表除头结点外,只剩下一个元素时,则需將rear指向头结点。a.定义- 个QueuePtr结点p,盱暂存欲删除的结点Q-> front-next;b.将欲删除结点数据域数据赋值给e;c.将欲删除结点的后继结点(p- > next)赋值给头队头结点的后继(Q-> front-> next)d.判定若队头是队尾，则删除后将rear指向头结点，最后再释放欲删除结点p.
实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求；
程序有适当的注释。
链队列实验要求
本次实验中的链队列结构指不带头结点的单链表；
链队列结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中直接实现；
实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求；
程序有适当的注释。
2.循环队列事先请好空间，使用期间不释放;链队列,无需事先申请空间但是每次申请和释放结点会存在一些事件开销;
3.循环队列必须有一调定的长度,可能存在空间浪费;链队列需要一个指针域，将两个结构体链接在一起。
[7. 附录]
（源代码清单。纸质报告不做要求。电子报告，可直接附源文件，删除编译生成的所有文件）
求当前队列中元素个数
链队列：；
链队列：
编写算法实现
①初始化空循环队列；
②当键盘输入奇数时，此奇数入队；
③当键盘输入偶数时，队头出队；
④当键盘输入0时，算法退出；
⑤每当键盘输入后，输出当前队列中的所有元素。
链队列：
6.总结和心得
1、队列与循环队列1.队列(1)队列(queue)是只允许在一端进行插入操作，而在另-端进行删除操作的线性表,

合集下载

数据结构实验报告 (3)

数据结构实验报告 (3)

数据结构实验报告（五）实验目的：1.掌握顺序表的查找方法，尤其是二分查找方法。

2.掌握二叉排序树的建立及查找。

实验任务：1.对下列数据表，分别采用二分查找算法实现查找，给出查找过程依次所比较的元素（的下标），并以二分查找的判定树来解释。

实验测试数据：数据表为(1,2,3,4,6,7,8,9,10,11,12,13,17,18,19,20,24,25,26,30,35,40,45,50,100)查找的元素分别为：2，8，20, 30，50，5，15，33，1102.设计出在二叉排序树中插入结点的算法，在此基础上实现构建二叉排序树的算法，并给出其中序遍历序列。

实验测试数据：构建二叉排序树的输入序列如下：100，150，120，50，70，60，80，170，180，160，110，30，40，35，1753.设计算法在二叉排序树中查找指定值的结点。

在任务2所建立的二叉排序树中分别查找下列元素：150，70，160，190，10，55，1754.设计算法在二叉排序树中删除特定值的结点。

（选做）在任务2所建立的二叉排序树中依次删除下列元素：30，150，100，并给出中序遍历结果。

程序清单：1.#include<iostream>using namespace std;int key_lib[]={1,2,3,4,6,7,8,9,10,11,12,13,17,18,19,20,24,25,26,30,35,40,45,50,100};int halfsearch(int *lib,int low,int high,int key){static int mid;if(low>high) return -1;else{mid=(low+high)/2;cout<<mid<<" ";if(key<lib[mid]) return halfsearch(lib,low,mid-1,key);else if(key>lib[mid]) return halfsearch(lib,mid+1,high,key);else return mid;}}void main(){cout<<"输出查找的顺序为：";if(halfsearch(key_lib,0,24,2)==-1)cout<<"查无此数！"<<endl;elsecout<<endl;cout<<"输出查找的顺序为：";if(halfsearch(key_lib,0,24,8)==-1)cout<<"查无此数！"<<endl;elsecout<<endl;cout<<"输出查找的顺序为：";if(halfsearch(key_lib,0,24,20)==-1)cout<<"查无此数！"<<endl;elsecout<<endl;cout<<"输出查找的顺序为：";if(halfsearch(key_lib,0,24,30)==-1)cout<<"查无此数！"<<endl;elsecout<<endl;cout<<"输出查找的顺序为：";if(halfsearch(key_lib,0,24,50)==-1)cout<<"查无此数！"<<endl;elsecout<<endl;cout<<"输出查找的顺序为：";if(halfsearch(key_lib,0,24,5)==-1)cout<<"查无此数！"<<endl;elsecout<<endl;cout<<"输出查找的顺序为：";if(halfsearch(key_lib,0,24,15)==-1)cout<<"查无此数！"<<endl;elsecout<<endl;cout<<"输出查找的顺序为：";if(halfsearch(key_lib,0,24,33)==-1)cout<<"查无此数！"<<endl;elsecout<<endl;cout<<"输出查找的顺序为：";if(halfsearch(key_lib,0,24,110)==-1)cout<<"查无此数！"<<endl;elsecout<<endl;}2.3.#include<iostream>using namespace std;struct node{node *lchild;node *rchild;int data;};class searchtree{public:searchtree(int *r,int n);~searchtree(){delete_tree(root);}void Insert(node *&innode,node *s);node *Search(int k){return Search(root,k);}void travel(){travel(root);}private:node *root;void travel(node *p);void delete_tree(node *t);node *Search(node *snode,int k);};searchtree::searchtree(int *r,int n){node *s;root=NULL;for(int i=0;i<n;i++){s=new node;s->data=r[i];s->lchild=s->rchild=NULL;Insert(root,s);}}void searchtree::Insert(node *&innode,node *s){if(innode==NULL)innode=s;else if(s->data<innode->data)Insert(innode->lchild,s);elseInsert(innode->rchild,s);}node * searchtree::Search(node *snode,int k){if(snode==NULL)return NULL;if(snode->data==k) return snode;else if(snode->data>k) return Search(snode->lchild,k);else return Search(snode->rchild,k);}void searchtree::travel(node *p){if(p==NULL) return;travel(p->lchild);cout<<p->data<<" ";travel(p->rchild);}void searchtree::delete_tree(node *t){if(t==NULL) return;delete_tree(t->lchild);delete_tree(t->rchild);delete t;}void main(){int lib[]={100,150,120,50,70,60,80,170,180,160,110,30,40,35,175};searchtree q(lib,15);q.travel();if(q.Search(150)!=NULL)cout<<"150在这个排序树中"<<endl;else cout<<"未找到这个数！"<<endl;if(q.Search(70)!=NULL)cout<<"70在这个排序树中"<<endl;else cout<<"未找到这个数！"<<endl;if(q.Search(160)!=NULL)cout<<"160在这个排序树中"<<endl;else cout<<"未找到这个数！"<<endl;if(q.Search(190)!=NULL)cout<<"190在这个排序树中"<<endl;else cout<<"未找到这个数！"<<endl;if(q.Search(10)!=NULL)cout<<"10在这个排序树中"<<endl;else cout<<"未找到这个数！"<<endl;if(q.Search(55)!=NULL)cout<<"55在这个排序树中"<<endl;else cout<<"未找到这个数！"<<endl;if(q.Search(175)!=NULL)cout<<"175在这个排序树中"<<endl;else cout<<"未找到这个数！"<<endl;}运行结果：1.2.。

数据结构实验报告_实验报告_

数据结构实验报告_实验报告_

数据结构实验报告想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是小编给大家整理收集的数据结构实验报告，供大家阅读参考。

数据结构实验报告1一、实验目的及要求1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。

本实验训练的要点是“栈”和“队列”的观点;二、实验内容1) 利用栈，实现数制转换。

2) 利用栈，实现任一个表达式中的语法检查(选做)。

3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);三、实验流程、操作步骤或核心代码、算法片段顺序栈：Status InitStack(SqStack &S){S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemTyp e));if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}Status DestoryStack(SqStack &S){free(S.base);return OK;}Status ClearStack(SqStack &S){S.top=S.base;return OK;}Status StackEmpty(SqStack S){if(S.base==S.top)return OK;return ERROR;}int StackLength(SqStack S){return S.top-S.base;}Status GetTop(SqStack S,ElemType &e){if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemTyp e));if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;Status Push(SqStack &S,ElemType e){if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemTyp e));if(!S.base)return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}Status Pop(SqStack &S,ElemType &e){if(S.top==S.base)return ERROR;e=*--S.top;return OK;}Status StackTraverse(SqStack S){ElemType *p;p=(ElemType *)malloc(sizeof(ElemType));if(!p) return ERROR;p=S.top;while(p!=S.base)//S.top上面一个...p--;printf("%d ",*p);}return OK;}Status Compare(SqStack &S){int flag,TURE=OK,FALSE=ERROR; ElemType e,x;InitStack(S);flag=OK;printf("请输入要进栈或出栈的元素："); while((x= getchar)!='#'&&flag) {switch (x){case '(':case '[':case '{':if(Push(S,x)==OK)printf("括号匹配成功!\n\n"); break;case ')':if(Pop(S,e)==ERROR || e!='('){printf("没有满足条件\n");flag=FALSE;}break;case ']':if ( Pop(S,e)==ERROR || e!='[')flag=FALSE;break;case '}':if ( Pop(S,e)==ERROR || e!='{')flag=FALSE;break;}}if (flag && x=='#' && StackEmpty(S)) return OK;elsereturn ERROR;}链队列：Status InitQueue(LinkQueue &Q) {Q.front =Q.rear=(QueuePtr)malloc(sizeof(QNode));if (!Q.front) return ERROR;Q.front->next = NULL;return OK;}Status DestoryQueue(LinkQueue &Q) {while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}return OK;}Status QueueEmpty(LinkQueue &Q){if(Q.front->next==NULL)return OK;return ERROR;}Status QueueLength(LinkQueue Q){int i=0;QueuePtr p,q;p=Q.front;while(p->next){i++;p=Q.front;q=p->next;p=q;}return i;}Status GetHead(LinkQueue Q,ElemType &e) {QueuePtr p;p=Q.front->next;if(!p)return ERROR;e=p->data;return e;}Status ClearQueue(LinkQueue &Q){QueuePtr p;while(Q.front->next ){p=Q.front->next;free(Q.front);Q.front=p;}Q.front->next=NULL;Q.rear->next=NULL;return OK;}Status EnQueue(LinkQueue &Q,ElemType e) {QueuePtr p;p=(QueuePtr)malloc(sizeof (QNode));if(!p)return ERROR;p->data=e;p->next=NULL;Q.rear->next = p;Q.rear=p; //p->next 为空return OK;}Status DeQueue(LinkQueue &Q,ElemType &e) {QueuePtr p;if (Q.front == Q.rear)return ERROR;p = Q.front->next;e = p->data;Q.front->next = p->next;if (Q.rear == p)Q.rear = Q.front; //只有一个元素时(不存在指向尾指针) free (p);return OK;}Status QueueTraverse(LinkQueue Q){QueuePtr p,q;if( QueueEmpty(Q)==OK){printf("这是一个空队列!\n");return ERROR;}p=Q.front->next;while(p){q=p;printf("%d<-\n",q->data);q=p->next;p=q;}return OK;}循环队列：Status InitQueue(SqQueue &Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base)exit(OWERFLOW);Q.front=Q.rear=0;return OK;}Status EnQueue(SqQueue &Q,QElemType e){if((Q.rear+1)%MAXQSIZE==Q.front)return ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;}Status DeQueue(SqQueue &Q,QElemType &e){if(Q.front==Q.rear)return ERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return OK;}int QueueLength(SqQueue Q){return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}Status DestoryQueue(SqQueue &Q){free(Q.base);return OK;}Status QueueEmpty(SqQueue Q) //判空{if(Q.front ==Q.rear)return OK;return ERROR;}Status QueueTraverse(SqQueue Q){if(Q.front==Q.rear)printf("这是一个空队列!");while(Q.front%MAXQSIZE!=Q.rear){printf("%d<- ",Q.base[Q.front]);Q.front++;}return OK;}数据结构实验报告2一.实验内容：实现哈夫曼编码的生成算法。

数据结构实验报告三

数据结构实验报告三

L->r[j+1]=L->r[j];
L->r[j+1]=L->r[0];
}
}
main()
{
SortList *L;
int i;
L->r[0].key=0;
L->r[1].key=49;
L->r[2].key=38;
L->r[3].key=65;
L->r[4].key=97;
L->r[5].key=76;
}SortList;
void InsertSort(SortList *L)
{
int i,j;
for(i=2;i<=L->length;i++)
if(L->r[i].key<L->r[i-1].key){
L->r[0]=L->r[i];
for(j=i-1;L->r[0].key<L->r[j].key;j--)
L->r[6].key=13;
L->r[7].key=27;
L->r[8].key=52;
L->length=8;
SelectSort(L);
printf("\n\n");
for(i=1;i<=L->length;i++)
printf("%d\n",L->r[i].key);
}
附2：原程序
#define SORT_LIST_MAXSIZE 20
typedef int KeyType;
typedef int InfoType;
typedef struct{
国家开放大学《数据结构》课程实验报告(实验3 ——栈、队列、递归设计)参考答案

国家开放大学《数据结构》课程实验报告(实验3 ——栈、队列、递归设计)参考答案

{
x=Pop(s); /*出栈*/
printf("%d ",x);
InQueue(sq,x); /*入队*/
}
printf("\n");
printf("(10)栈为%s,",(StackEmpty(s)?"空":"非空"));
printf("队列为%s\n",(QueueEmpty(sq)?"空":"非空"));
ElemType Pop(SeqStack *s); /*出栈*/
ElemType GetTop(SeqStack *s); /*取栈顶元素*/
void DispStack(SeqStack *s); /*依次输出从栈顶到栈底的元素*/
void DispBottom(SeqStack *s); /*输出栈底元素*/
} SeqQueue; /*定义顺序队列*/
void InitStack(SeqStack *s); /*初始化栈*/
int StackEmpty(SeqStack *s); /*判栈空*/
int StackFull(SeqStack *s); /*判栈满*/
void Push(SeqStack *s,ElemType x); /*进栈*/
sq=(SeqQueue *)malloc(sizeof(SeqQueue));
InitQueue(sq);
printf("(8)队列为%s\n",(QueueEmpty(sq)?"空":"非空"));
printf("(9)出栈/入队的元素依次为:");