数据结构(栈及队列)实验报告 C语言版
XXXX学院
计算机课程实验报告（201X～201X年度第X学期）
专业
课程数据结构
班级
组别
教师
琼州学院电子信息工程学院制
实验报告填写说明
1、填写一律用钢笔或圆珠笔填写，要求字迹工整，条理
清晰。
2、“实验题目”可以填写章节名称或用文字表述。
3、“实验目的”要逐条列出，“实验内容”以简练的文
字进行概括。
4、“附注”处填写实验注意事项或调试过程，以及实验
中出现的异常情况和解决方法。
5、“教师批阅”处有课任老师填写评语，给出实验成绩，
并作为平时成绩，参与期末成绩总评。
6、封面和实验报告填写说明正反面打印在一张纸上。
201X年XX月XX日
实验项目：栈及队列的链式和线性存储以及相关操作实现实验目的：
1.掌握数据结构中栈及队列的链式和线性存储结构操作;
2.了解数据结构中栈及队列的基本操作原理
3.掌握C语言中基本程序设计的方法.
4.掌握基本测试方法。
实验仪器：
计算机、C语言版数据结构相关实验题集、编写程序软件
实验规划：（包括函数说明、公共变量说明、测试说明等）
公共变量声明：
#include
#include
#define OK 1
#define ERROR 0
函数说明:
/******************************
Ⅰ、栈的链式存储以及相关操作实现
*******************************/
typedef struct stack
{
int data;
struct TYPE *next;
} ElemType;
栈的初始化：
1.ElemType* InitStack();
进栈：
2.int Push(ElemType *head,int e);
出栈：
3.int Pop(ElemType *head,int *e);
显示：
4.int DisplayStack(ElemType *Head);
返回顶元素：
5.int Gettop(ElemType *head);
小组各成员工作分配情况表：
XXX：统一定义常量，结构体模版，函数格式（参数、返回值）；讲解编写流程，检查编写函数。
XXX：编写测试及美化程序
XXX：编写出栈函数
XXX：编写初始化及取顶函数。
XXX：编写进栈函数。
XXX：编写打印栈顶函数。
实验内容及步骤（或程序清单）：
内容：此栈采用链式存储，实现了建栈、进栈、出栈、打印等功能。
栈链表实现：
/***************************
Time : XX-XX-201X
Made : XXXXX
use : Stack by chain
****************************/
#include
#include
#define OK 1
#define ERROR 0
typedef struct stack
//Define a elemtype for data
{
int data;
struct TYPE *next;
} ElemType;
ElemType* InitStack()
//To initialize an empty stack
{
ElemType *S;
do{
S = (ElemType *)malloc(sizeof(ElemType));
}while(!S);
S->data=0;
S->next=NULL;
printf("Init OK !\n");
return S;
}
int Push(ElemType *head,int e)
{
ElemType *p=NULL,*q = NULL;
p = head;
do{
q = (ElemType *)malloc(sizeof(ElemType)); }while(!q);
q->next = p->next;
p->next = q;
q->data = e;
return OK;
}
int Pop(ElemType *head,int *e)
{
ElemType *p, *q = NULL;
p = head;
if(head->next == NULL)
{
printf("The Stack is empty !\n");
return ERROR;
}
q = head->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
int DisplayStack(ElemType *Head)
//Just for text
{
ElemType *p = NULL;
p = Head->next;
ElemType *E = InitStack();
ElemType *e ;
if(!p) return ERROR;
for(; p!=NULL; p = p->next)
{
Push(E,p->data);
}
e= E->next;
for(;e!=NULL;e=e->next)
{
printf("%5d",e->data);
}
printf("\n");
return OK;
}
int Gettop(ElemType *head)
{
return (*head)->next->data;
}
函数说明:
/******************************
Ⅱ、栈的线性存储以及相关操作实现
*******************************/
typedef struct ASTACK
{
ElemType *top; //栈顶指针(偏移指针)
ElemType *base; //栈基指针
int length; //栈长度
} Stack;
1.初始化：
Stack * InitStack()
2.进栈：
int Push(Stack *S,ElemType e)
3.出栈：
ElemType Pop(Stack *S,ElemType &e)
4.显示：
int PrintStack(Stack *S)
5.返回栈顶元素：
ElemType GetTop(Stack *S)
小组各成员工作分配情况表：
XXX：统一定义常量，结构体模版，函数格式（参数、返回值）；讲解编写流程，检查编写函数。
XXX：编写进栈函数及注释
XXX：编写进栈函数
XXX：编写测试及美化函数。
XXX：编写出栈及显示函数。
XXX：编写初始化函数。
实验内容及步骤（或程序清单）：
内容：此栈采用线性存储，实现了建栈、进栈、出栈、打印栈等功能。
线性栈的实现：
/*****************************
Times: XX-XX-201X
owner: XXXXX
Use : Stack
*****************************/
#include
#include
#define OK 1
#define ERROR 0
#define ElemType int //用自定义代表数据类型方便后来程序修改#define STACK_INIT_SIZE 100 //初始化时栈的容量
#define LISTINCREMENT 10 //当初始化容量不够时每次所增加的容量int TT = 1;
// 定义结构体的类型
typedef struct ASTACK
{
ElemType *top; //栈顶指针(偏移指针)
ElemType *base; //栈基指针
int length; //栈长度
} Stack;
//初始化：
Stack * InitStack(){
Stack *S;
S = (Stack*)malloc(sizeof(Stack));
do{
(*S).base = (ElemType *)malloc(sizeof(ElemType) *
STACK_INIT_SIZE);
}while(!((*S).base));
S->top = S->base;
S->length = STACK_INIT_SIZE;
return S;
}
//进栈：
int Push(Stack *S,ElemType e)
{
if((S->top-S->base) >= S->length) // 如果栈满，则增加容量
{
do{
S->base = (ElemType *)realloc(S->base,
sizeof(ElemType)*(STACK_INIT_SIZE+LISTINCREMENT)); }while(!(S->base));
S->length = STACK_INIT_SIZE+LISTINCREMENT;
}
*(S->top) = e; //将值 e传给栈顶
++(*S).top; //栈顶指针上移，为下一个数据做准备
return OK;
}
//出栈：
ElemType Pop(Stack *S,ElemType &e)
//如果栈不为空，则删除栈顶元素并赋给 e
{
if(S->top == S->base)
{
return ERROR;
}
e = *(S->top-1); // 将栈顶值给 e
--(S->top); //将栈顶指针下移一位
return OK;
}
//返回栈顶元素：
ElemType GetTop(Stack *S)
{
return *((*S).top-1);
}
//显示栈所有元素：
int PrintStack(Stack *S) // Only used for test
{
int i = 0;
ElemType *p;
p = S->base;
for(p;p
{
printf("%5d",*p);
i++;
}
return i;
}
/*********************************
附上JAVA的线性栈实现：
**********************************/
publicclass stackofInt{
privateint [] elemtype = newint[100];
privateint size= 0;
public stackofInt() {
}
public stackofInt(int e) {
this.elemtype = newint[e];
}
publicvoid push(int e){
if(size>elemtype.length){
int[] temp = newint[elemtype.length+10];
System.arraycopy(elemtype, 0, temp, 0, elemtype.length);
elemtype = temp;
}
elemtype[size]= e;
++size;
}
publicint pop(){
if(size==0) {
System.out.println("The stack is empty!");
System.exit(0);
return 0;
}
else{
int a = elemtype[size-1];
--size;
return a;
}
}
publicboolean isempty(){
if(size == 0)
returntrue;
returnfalse;
}
publicvoid toempty(){size = 0; }
publicint gettop(){return elemtype[size-1]; }
publicvoid printstack(){
int i=1;
while(i<=size){
System.out.print(elemtype[i-1]+" ");
i++;
}
}
publicstaticvoid main(String [] agrs){
stackofInt stack = new stackofInt();
for(int i = 1;i<=10;i++)stack.push(i);
stack.printstack();
}
}
/************************************
Ⅲ、队列链式存储以及相关操作实现
*************************************/
公共变量声明：
#include "StackFun.h"
函数说明:
定义结构体：
typedef struct QLink
{
int data;
struct QLink *next;
} ElemType;
typedef struct QUEUE
{
ElemType *front;
ElemType *rear;
int length;
} LinkQueue;
小组各成员工作分配情况表：
XXX：统一定义常量，结构体模版，函数格式（参数、返回值）；讲解编写流程，检查编写函数。
XXX：编写进队函数及注释
XXX：编写出队函数
XXX：编写测试函数及美化。
XXX：编写取顶及显示函数。
XXX：编写初始化函数。
实验内容及步骤（或程序清单）：
内容：此队采用链式存储，实现了建队、进队、出队、打印队等功能。
队的链式实现：
/*********************
Times: XX-XX-201X
owner: XXXXX
Use : Queue
*********************/
#include "StackFun.h"
#include
#include
#define OK 1
#define ERROR 0
typedef struct QNode
/**************************
Define a new elemtype
for Queue
***************************/
{
int data;
struct QNode *next;
} ElemType;
typedef struct QUEUE
/**********************************
*front->The top ptr of Queue
*rear ->The rear ptr of Queue
length->The length of Queue
***********************************/
{
ElemType *front;
ElemType *rear;
int length;
} LinkQueue;
LinkQueue* InitQueue()
/*************************
Initialize the queue !
If successful,print OK;
**************************/
{
LinkQueue *Q=NULL;
Q = (LinkQueue*)malloc(sizeof(LinkQueue)); do
{
(*Q).front = (*Q).rear = (ElemType
*)malloc(sizeof(ElemType));
}
while(!(*Q).front);
(*Q).length = 0;
(*Q).front->next = NULL;
printf("CREATE A EMPTY QUEUE OK !\n");
return Q;
}
int DestroyQueue(LinkQueue *Q)
/******************************************** Like his name,Destroy the queue to make the queue empty;
*********************************************/ {
while((*Q).front)
{
(*Q).rear = (*Q).front->next;
free((*Q).front);
(*Q).front = (*Q).rear;
}
return OK;
}
int EnterQueue(LinkQueue *Q,int e)
/***************************************
Enter a number "e" to the rear of Queue
****************************************/
{
ElemType *p;
do{
p = (ElemType *)malloc(sizeof(ElemType)); }while(!p);
p->data = e;
p->next=NULL;
(*Q).rear->next = p;
(*Q).rear = p;
++(Q->length);
return OK;
}
int DeleteQueue(LinkQueue *Q,int *e)
/******************************************
If the Queue isn't emtpy,take the top of
Queue to e. else return ERROR. So we can
decide how to do from the returned value;
*******************************************/
{
ElemType *p;
if((*Q).front==(*Q).rear) return ERROR;
p=(*Q).front->next;
*e = p->data;
(*Q).front->next = p->next;
--(Q->length);
if((*Q).rear == p)
{
(*Q).rear = (*Q).front;
}
free(p);
return OK;
}
int DisplayQueue(LinkQueue *Q)
/******************************************* Just for Text:
If it can be display, go ahead and return OK; else return ERROR.
*********************************************/ {
ElemType *p;
elem_type *S;
S =InitStack();
if(Q->front == Q->rear)
{
printf("The Queue is emtpy !\n");
return ERROR;
}
p = Q->front->next;
do
{
Push(S,p->data);
p= p->next;
}
while(p != NULL);
DisplayStack(S);
return OK;
}
int GetHead(LinkQueue *Q)
/**********************************
return the front of LinkQueue
***********************************/
{
if((*Q).front == (*Q).rear)
{
printf("The Queue is empty !\n");
exit(0);
}
else
return (*Q).front->next->data;
}
/*************************************
Ⅴ、队列线性存储以及相关操作实现
**************************************/
函数说明：
定义结构体：
typedef struct QUEUE
{
ElemType *base;
ElemType front;
} LinkQueue;
1.队的初始化：LinkQueue* InitQueue();
2.进队：int EnterQueue(LinkQueue *Q,int e);
3.出队：int DeleteQueue(LinkQueue *Q,int *e);
4.销毁队：int DestroyQueue(LinkQueue *Q)
5.显示：int DestroyQueue(LinkQueue *Q)
XXX：统一定义常量，结构体模版，函数格式（参数、返回值）；讲解编写流程，检查编写函数。
XXX：编写进队函数及注释
XXX：编写出队函数
XXX：编写测试函数及美化。
XXX：编写显示函数。
XXX：编写初始化函数。
实验内容及步骤（或程序清单）：
内容：此队采用线性存储，实现了建队、进队、出队、打印队等功能。
队的线性实现：
/*****************************
Times: XX-XX-201X
owner: XXXXX
Use : Queue_S
*******************************/
#include
#include
#define OK 1
#define ERROR 0
#define ElemType int
#define MAXSIZE 5
typedef struct QUEUE
{
ElemType *base;
ElemType front;
} LinkQueue;
LinkQueue* InitQueue()
{
LinkQueue *Q;
do{
Q= (LinkQueue*)malloc(sizeof(LinkQueue));
}while(!Q);
do{
(*Q).base = (ElemType*)malloc(MAXSIZE*sizeof(ElemType));
}while(!(*Q).base);
(*Q).front =0;
printf("CREATE AN EMPTY QUEUE OK !\n");
return Q;
}
int DestroyQueue(LinkQueue *Q)
{
(*Q).front = 0;
return OK;
}
int EnterQueue(LinkQueue *Q,int e)
{
if((*Q).front== MAXSIZE){
(*Q).base =(ElemType * )realloc((*Q).base ,
MAXSIZE*2*sizeof(ElemType));
}
(*Q).base[(*Q).front] = e;
++(Q->front);
return OK;
}
int DeleteQueue(LinkQueue *Q,int *e)
{
if((*Q).front!=0){
int i = 0;
*e = (*Q).base[i];
for(i ;i<(*Q).front;i++)
(*Q).base[i] = (*Q).base[i+1];
--(*Q).front;
return OK;
}
else
return ERROR;
}
int DisplayQueue(LinkQueue *Q)
{
int i =0;
if((*Q).front == i){
printf("The queue is empty !");
return ERROR;
}
for(i;i<(*Q).front;i++)
printf("%5d",(*Q).base[i]);
return OK;
}
栈的测试：
附注1.初始化成功：
2.输入栈长度和数值：
3.显示并提示是否要出栈：
4.出栈：
5.再进栈：
6.输入元素显示并退出：
队的测试：
1.初始化成功：
2.进队：
3.出队：
实验结果分析：栈的建立用的是链式，倒序插入法。刚好符合栈的后入先出。队的建立也是链式，运用了头尾双指针,当然用数组来做也不错。
教师点评：
数据结构-堆栈和队列实验报告
实验二堆栈和队列 实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法；队列链式存储结构下的基本算法；实验内容： 3-18链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化Stacklnitiate （S）, 非空否StackNotEmpty（S），入栈StackiPush（S,x）, 出栈StackPop （S,d）,取栈顶数据元素StackTop（S,d）; （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3, 4，5 入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 3-19对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当 前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写一个主函数进行测试。 实验结果： 3-18 typedef struct snode { DataType data; struct snode *n ext; } LSNode; /* 初始化操作：*/
数据结构实验报告格式
《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时）
完整版数据结构习题集第3章栈和队列
第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从 队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s;
数据结构_实验三_栈和队列及其应用
实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈和队列及其应用_ 一．实验目的及要求 （1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们； （2）本实验训练的要点是“栈”的观点及其典型用法； （3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； （2）应用栈的基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5）利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存： 代码部分： 栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl;
cout << "你的选择是：" ; } 链式储存： 代码部分： 栈"<
数据结构实验报告
数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 一．实验项目名称 循环队列和链式队列的创建 二、实验目的 1、掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等， 2、队列顺序存储结构、链式存储结构和循环队列的实现，以便在 实际问题背景下灵活应用。 三、实验内容 1．链式队列的实现和运算 2．循环队列的实现和运算 四、主要仪器设备及耗材 VC++6.0运行环境实现其操作 五．程序算法 (1) 循环队列操作的算法 1>进队列 V oid enqueue (seqqueue &q, elemtype x) { if ((q.rear+1)%maxsize = = q.front) cout<<”overflow”; else { q.rear=(q.rear+1)%maxsize; //编号加1或循环回第一个单元 q.queue[q.rear]=x; } } 2>出队列 V oid dlqueue(seqqueue &q ) { if (q.rear= =q.front) cout<<”underflow”; else q.front =(q.front+1)%maxsize; } 3>取对头元素 elemtype gethead(seqqueue q ) { if (q.rear= =q.front) { cout<<”underflow”； return NULL;} else return q.queue[(q.front+1)%maxsize]; //front指向队头前一个位置 } 4>判队列空否 int empty(seqqueue q ) { if (q.rear= =q.front) reurn 1; else return 0; } （2）.链队列操作的算法 1>.链队列上的初始化 void INIQUEUE( linkqueue &s) { link *p; p=new link; p->next=NULL; //p是结构体指针类型，用-> s.front=p; //s是结构体变量，用. s.rear=p; //头尾指针都指向头结点 } 2>.入队列 void push(linkqueue &s, elemtype x) { link *p; //p是结构体指针类型，用-> p=new link; p->data=x; p->next=s.rear->next; //s是结构体变量，用. s.rear->next=p; s.rear=p; //插入最后 } 3>判队空 int empty( linkqueue s ) { if (s.front= =s.rear) return 1; else return 0; } 4>.取队头元素 elemtype gethead( linkqueue s ) { if (s.front= =s.rear) return NULL; else retuen s.front->next->data; } 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; 《数据结构》课程实验报告 一、实验目的和要求 （1）熟悉C语言的上机环境，进一步掌握C语言的结构特点。 （2）掌握队列的顺序表示和实现。 二、实验环境 Windows7 ,VC 三、实验内容及实施 实验三：队列 【实验要求】 构建一个循环队列, 实现下列操作 1、初始化队列(清空)； 2、入队； 3、出队; 4、求队列长度； 5、判断队列是否为空； 【源程序】 #include Q.base=new int[MAXSIZE]; Q.front=Q.rear=0; return OK; }//队列的初始化 int EnQueue(SqQueue &Q,int e) { if((Q.rear+1)%MAXSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK; }//队列的入队 int DeQueue(SqQueue &Q,int &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return OK; }//队列的出队 int QueueLength(SqQueue &Q) { int i; i=(Q.rear-Q.front+MAXSIZE)%MAXSIZE; return i; }//求队列长度 void JuQueue(SqQueue &Q) { if(Q.rear==Q.front) printf("队列为空"); else printf("队列不为空"); }//判断队列是否为空 void QueueTraverse(SqQueue &Q) 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 数据结构练习第三章栈和队列 一、选择题 1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2．向顺序栈中压入新元素时，应当（）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（）的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 A. n-i B. n-1-i C. n+l -i D.不能确定 10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．队后 12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（）进行。 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌 系计算机系专业软件工程年级2016 班次(1) 姓名学号 一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作 二、实验内容 1、用栈解决以下问题： （1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序： （1）求n！。 （2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。 3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。 三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值 代码如下： #include 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 实验二栈和队列 一、实验目的 1. 掌握栈的顺序表示和实现 2. 掌握队列的链式表示和实现 二、实验内容 1. 编写一个程序实现顺序栈的各种基本运算。 2. 实现队列的链式表示和实现。 三、实验步骤 1. 初始化顺序栈 2. 插入元素 3. 删除栈顶元素 4. 取栈顶元素 5. 遍历顺序栈 6. 置空顺序栈 7. 初始化并建立链队列 8. 入链队列 9. 出链队列 10. 遍历链队列 四、实现提示 1. /*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack; /*初始化顺序栈函数*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/) /*入栈函数*/ void Push(SqStack *p,ElemType x) {if(p->top 《数据结构》课程实验报告 实验名称栈和队列实验序号实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验项目摘要 编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s； （2）判断栈s是否非空； （3）依次进栈元素a,b,c,d,e； （4）判断栈s是否非空； （5）输出栈长度； （6）输出从栈顶到栈底元素； （7）输出出栈序列； （8）判断栈s是否非空； （9）释放栈。 编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能： （1）初始化队列q； （2）判断队列q是否非空； （3）依次进队列a,b,c； （4）出队一个元素，输出该元素； （5）输出队列q的元素个数； （6）依次进队列元素d,e,f； （7）输出队列q的元素个数； （8）输出出队序列； （9）释放队列。 三、实验预习内容 栈的顺序存储结构及其基本运算实现（初始化栈，销毁栈，求栈的长度，判断栈是否为空，进栈，取栈顶元素，显示栈中元素） 队列的顺序存储结构及其基本运算实现（初始化队列，销毁队列，判断队列是否为空，入队列，出队列） 三、实验结果与分析 3-1 #define maxsize 100 #include 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template队列实验报告
数据结构实验报告全集
数据结构第三章栈和队列3习题
数据结构-队列实验报告
数据结构实验报告模板
数据结构练习 第三章 栈和队列
数据结构实验报告及心得体会
数据结构栈和队列实验报告.doc
数据结构栈和队列习题及答案
数据结构栈和队列
数据结构栈和队列实验报告
数据结构实验报告图实验
- 数据结构实验二题目一栈和队列实验报告
- 数据结构_实验三_栈和队列及其应用
- 数据结构栈和队列的应用表达式的求值
- 《数据结构》实验二 栈和队列
- 2数据结构-实验报告二(栈和队列及其应用)
- 数据结构--栈和队列的应用实验报告
- 数据结构实验报告栈和队列迷宫图最短路径
- 数据结构-堆栈和队列实验报告
- 数据结构堆栈实验报告
- 数据结构栈和队列实验报告
- 数据结构课程实验实训报告--堆栈和队列的基本操作。
- 数据结构堆栈与队列实验报告
- 数据结构实验-栈和队列
- 数据结构实验三栈和队列及其应用
- 数据结构_实验三_栈和队列及其应用
- 《数据结构》栈和队列实验报告
- 2数据结构实验报告二(栈和队列及其应用)
- 数据结构栈和队列实验报告
- 栈和队列实验报告
- 数据结构栈和队列实验报告