实验报告
实验二 堆栈和队列
实验目的：
1.熟悉栈这种特殊线性结构的特性；
2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算；
3.熟悉队列这种特殊线性结构的特性；
3.熟练掌握队列在链表存储结构下的基本运算。
实验原理：
堆栈顺序存储结构下的基本算法；
堆栈链式存储结构下的基本算法；
队列顺序存储结构下的基本算法；
队列链式存储结构下的基本算法；
实验内容：
3-18 链式堆栈设计。要求
（1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（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 *next;
} LSNode;
/*初始化操作：*/
void StackInitiate(LSNode **head)
/*初始化带头结点链式堆栈*/
{
if((*head = (LSNode *)malloc(sizeof(LSNode))) == NULL) exit(1);
(*head)->next = NULL;
}
/*判非空操作：*/
int StackNotEmpty(LSNode *head)
/*判堆栈是否非空，非空返回1；空返回0*/
{
if(head->next == NULL) return 0;
else return 1;
}
/*入栈操作：*/
int StackPush(LSNode *head, DataType x)
/*把数据元素x插入链式堆栈head的栈顶作为新的栈顶 */
{
LSNode *p;
if((p = (LSNode *)malloc(sizeof(LSNode))) == NULL)
{
printf("内存空间不足无法插入! \n");
return 0;
}
p->data = x;
p->next = head->next; /*新结点链入栈顶*/
head->next = p; /*新结点成为新的栈顶*/
return 1;
}
/*出栈操作：*/
int StackPop(LSNode *head, DataType *d)
/*出栈并把栈顶元素由参数d带回*/
{
LSNode *p = head->next;
if(p == NULL)
{
printf("堆栈已空出错！");
return 0;
}
head->next = p->next; /*删除原栈顶结点*/
*d = p->data; /*原栈顶结点元素赋予d*/
free(p); /*释放原栈顶结点内存空间*/
return 1;
}
/*取栈顶数据元素操作：*/
int StackTop(LSNode *head, DataType *d)
/*取栈顶元素并把栈顶元素由参数d带回*/
{
LSNode *p = head->next;
if(p == NULL)
{
printf("堆栈已空出错！");
return 0;
}
*d = p->data;
return 1;
}
/*撤销*/
void Destroy(LSNode *head)
{
LSNode *p, *p1;
p = head;
while(p != NULL)
{
p1 = p;
p = p->next;
free(p1);
}
}（2）主函数程序：
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
#include "LinStack.h"
void main(void)
{ LSNode *myStack;
int i, x;
StackInitiate(&myStack);
for(i=0;i<5; i++)
{ if(StackPush(myStack,i+1)==0)
{
printf("error!\n");
return;
}
}
if(StackTop(myStack, &x)==0)
{
printf("error!\n");
return;
}
else
printf("The element of local top is :%d\n",x);
printf( "The sequence of outing elements is:\n");
while(StackNotEmpty(myStack))
{
StackPop(myStack, &x);
printf("%d ", x);
}
printf("\n");
Destroy(myStack);
printf("This program is made by10273206\n");
}
运行结果为：
（3）设计结构体和测试函数如下：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct{
char taskName[10];
int taskNo;
}DataType;
#include"LinStack.h"
void main(){
LSNode *myStack;
FILE *fp;
DataType task,x;
if((fp=fopen("task.txt","r"))==NULL){
printf("不能打开文件task.txt!\n");
exit(0);
}
StackInitiate(&myStack);
while(!feof(fp)){
fscanf(fp,"%s %d",&task.taskName,&task.taskNo);
StackPush(myStack,task);
}
fclose(fp);
while(StackNotEmpty(myStack)){
StackPop(myStack,&x);
printf("%s %d\n",x.taskName,x.taskNo);
}
Destroy(myStack);
printf("This program is made by 10273206\n");
}运行结果为：
3-19
（1）
typedef struct
{
DataType queue[MaxQueueSize];
int front; /*队头指针*/
int count; /*计数器*/
} SeqCQueue;
/*初始化操作：QueueInitiate(SeqCQueue *Q) */
void QueueInitiate(SeqCQueue *Q)
/*初始化顺序循环队列Q */
{
Q->front=0; /*定义初始队头指针下标*/
Q->count=0; /*定义初始计数器值*/
}
/*判非空否操作：QueueNotEmpty(SeqCQueue Q)*/
int QueueNotEmpty(SeqCQueue Q)
/*判断顺序循环队列Q非空否，非空时返回1，否则返回0 */
{
if(Q.count!=0)return 1;
else return 0;
}
/*入队列操作：QueueAppend(SeqCQueue *Q, DataType x)*/
int QueueAppend(SeqCQueue *Q, DataType x)
/*把数据元素x插入顺序循环队列Q的队尾，成功时返回1，否则返回0 */
{
if(Q->count==MaxQueueSize)
{
printf("The queue is full!\n");
return 0;
}
else
{ int r;
r=Q->front+Q->count;
Q->queue[r]=x;
Q->count++;
return 1;
}
}
/*出队列操作：QueueDelete(SeqCQueue *Q, DataType *d)*/
int QueueDelete(SeqCQueue *Q, DataType *d)
/*删除顺序循环队列队头数据元素并赋值d，成功时返回1，否则返回0 */
{
if(Q->count==0)
{
printf("The queue is empty!\n");
return 0;
}
else
{
*d=Q->queue[Q->front];
Q->front=(Q->front+1)%MaxQueueSize;
Q->count--;
return 1;
}
}
/*取对头数据元素操作：QueueGet(SeqCQueue Q, DataType *d)*/
int QueueGet(SeqCQueue Q, DataType *d)
/* 取顺序循环队列队头数据元素并赋值d，成功时返回1，否则返回0 */
{
if(Q.count==0)
{
printf("The queue is empty!\n");
return 0;
}
else
{
*d=Q.queue[Q.front];
return 1;
}
}
（2）主函数程序：
#include<stdio.h>
#define MaxQueueSize 100
typedef int DataType;
#include"SeqQueue.h"
void main(void)
{
int i,j,d;
SeqCQueue myQueue;
QueueInitiate(&myQueue);
if(QueueNotEmpty(myQueue)==0)
printf("队列为空！请输入数据元素：\n"); /*判空*/
for(i=0;i<=10;i++)
{
if(QueueAppend(&myQueue,i+1)==0)
break;
}
printf("元素个数为%d\n",myQueue.count); /*输出元素个数*/
for(j=0;j<=9;j++)
{
if(QueueDelete(&myQueue,&d)==0)
break;
printf("%d ",d); /*出队列并显示元素*/
}
printf("\n");
if(QueueNotEmpty(myQueue)==1)
printf("队列不为空\n"); /*再次判空*/
printf("This program is made by 10273206\n");
}
运行结果为：
总结与思考
对于堆栈和队列实验的操作，我明白了栈和队列这两种特殊线性结构的特性，初步掌握了栈在顺序存储结构和链表存储结构下的基本运算。顺序循环队列中初始化，入队列，出队列，取对头元素和判断队列是否为空是关键。此次实验之后我的逻辑又得到了进一步加强。
第二篇：太原理工数据结构实验报告 实验一 顺序表
实验报告
课程名称： 数据结构B
实验项目： 顺序表
实验地点： 实验楼110
专业班级：计科1301班 学号： 2013001989
学生姓名： 杨喆
指导教师： 孟亮
20##年 1 月 1 日
一、实验目的和要求
本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。
要求仔细阅读并理解下列例题，上机调试并编译执行通过，并观察其结果，然后独立完成后面的实验内容，写出完整的实验报告。编写程序过程中注意养成良好的编程风格与习惯，要求程序结构清晰，程序缩进，适当注释。
二、实验内容和原理
1．设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。
2．用单链表ha 存储多项式A（x ）=a0+a1x1+a2x2+…+anxn(其中aI为非零系数)，用单链表hb 存储多项式B（x ）=b0+b1x1+b2x2+…+bmxm(其中bj为非零系数)，要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。试写出程序。
3．设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。
三、主要仪器设备
1.设备: PC微机;
2.实验环境: windows操作系统；VC++6.0,
四、实验结果与分析（必填）
（1）程序清单：
实验1_1:
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 80
#define LISTINCREMENT 10
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
int listsize;
}SqList;
Status InitList_Sq(SqList *L) //构造一个空的线性表
{
L->elem=(ElemType*) malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (!L->elem)
return(OVERFLOW);
L->length=0;
L->listsize=LIST_INIT_SIZE;
return OK;
}
Status ListInsert_Sq(SqList *L,int i,ElemType e) //插入x
{
ElemType *q,*p,*newbase;
if (i<1 || i>L->length+1)
return ERROR;
if (L->length>=L->listsize)
{
newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));
if (!newbase) return(OVERFLOW);
L->elem=newbase;
L->listsize+=LISTINCREMENT;
}
q=&(L->elem[i-1]); //插入位置
for(p=&(L->elem[L->length-1]);p>=q;--p)
*(p+1)=*p; //插入位置之后的元素后移一位
*q=e; //插入e
++L->length; //表长加一
return OK;
}
//将x插入到顺序表（递增有序）的适当位置上
Status InsertOrderList_Sq(SqList *L,ElemType x)
{
int i=1;
ElemType *q,*p;
for(i=L->length; i<=0; i++)
{
printf("%d",i);
if(x >= L->elem[i-1])
{
q=&(L->elem[i-1]);
break;
}
}
for(p=&(L->elem[L->length-1]);p>=q;--p)
*(p+1)=*p; //插入位置之后的元素后移一位
if(i >= L->length) q=&(L->elem[i]);
*q=x; //插入x
++L->length; //表长加一
return OK;
}
Status CreatList_sq(SqList &Lst)
{
int i,n;
printf("请输入你要创建的顺序表的长度");
scanf("%d",&n);
if (InitList_Sq(&Lst)==OK)
{
for(i=n;i>=0;i--) //循环输入一个顺序数组
{
if(ListInsert_Sq(&Lst,1,i)!=OK)
break;
}
printf("\n顺序表已建立:");
for (i=0;i<Lst.length;i++)
printf("%d ",Lst.elem[i]);
}
return 0;
}
Status InsertOrderList_Sq_1(SqList &Lst)
{
int i,n;
printf("\n请输入你要插入的元素");
scanf("%d",&n);
InsertOrderList_Sq(&Lst,n);
printf("\n插入后的顺序表为");
for (i=0;i<Lst.length;i++)
printf("%d ",Lst.elem[i]);
return OK;
}
Status menu_select()
{
int sn;
for(;;)
{
printf("\n请输入您要进行的功能选项");
scanf("%d",&sn);
if(sn<1||sn>3)
printf("\n\t输入错误，请重新输入\n");
else
break;
}
return sn;
}
void main()
{
SqList Lst;
int i;
printf("1.建立一个顺序表;\n2.输入你要插入的元素\n3.结束\n");
while(1)
{
switch(menu_select())
{
case 1:
CreatList_sq(Lst);
printf("\n");
break;
case 2:
InsertOrderList_Sq_1(Lst);
printf("\n");
break;
case 3:
printf("end\n");
return;
}
}
}
实验1_2:
#include<stdio.h>
#include<malloc.h>
#define Ture 1
#define False 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 80
#define LISTINCREMENT 10
typedef int Status;
typedef int ElemType;
typedef struct Lnode
{
ElemType data;
struct Lnode *next;
}Lnode,*LinkList;
Status InitList_L(LinkList &L)
{
L = (Lnode *)malloc(sizeof(Lnode));
if (L)
{
L->next = NULL;
return OK;
}
else
return ERROR;
}
Status ListInsert_Link(LinkList &L, int i, ElemType e)
{
LinkList p,q;
int j=0;
p = L;
while( p && j<i-1)
{
p = p->next;
j++;
//printf("****");
// printf("%d",j);
}
q = (Lnode *)malloc(sizeof(Lnode));
if(!q)
return OVERFLOW;
q->data = e;
q->next = p->next;
p->next = q;
//printf("%d",q->data);
return OK;
}
Status InputFormula(LinkList &L)
{
int b=0,n=0,i;
LinkList p,q;
p = L;
q = L;
printf("您要输入_____项式");
printf("\n");
scanf("%d",&n);
if(n <= 0)
{
printf("请输入正确的内容");
printf("/n");
}
printf("Input a figure according your formula:");
printf("\n");
for(i=1;i<=n;i++)
{
scanf("%d",&b);
//printf("%d",b);
ListInsert_Link(p,i,b);
}
printf("您输入的二项式系数如下，请确认\n");
for(i;i>1;i--)
{
q = q->next;
printf("%d",q->data);
printf(",");
}
printf("\n");
return OK;
}
Status AdditionA_BToClink(LinkList &A, LinkList &B, LinkList &C)
//要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。试写出程序。
{
LinkList p=A, q=B,s=C;
int i=1,j,c;
p = p->next;
q = q->next;
while(p && q)
{
c = p->data + q->data;
ListInsert_Link(s,i,c);
p = p->next;
q = q->next;
i++;
}
while(p)
{
c = p->data;
p = p->next;
ListInsert_Link(s,i,c);
i++;
printf("%d",i);
printf("c的值%d",i);
}
while(q)
{
c = q->data;
q = q->next;
ListInsert_Link(s,i,c);
i++;
}
printf("\n得到C项式项数为：%d",i-1);
if(i<=1)
return ERROR;
printf("\n得到C项式为：");
for(i;i>1;i--)
{
s = s->next;
c = s->data;
printf("%d",c);
printf(",");
}
return OK;
}
Status menu_select()
{
int sn;
for(;;)
{
printf("\n请输入您要进行的功能选项");
scanf("%d",&sn);
if(sn<1||sn>4)
printf("\n\t输入错误，请重新输入\n");
else
break;
}
return sn;
}
void main()
{
LinkList A,B,C;
InitList_L(A);
InitList_L(B);
InitList_L(C);
printf("1.输入A项式;\n2.输入B项式;\n3.合并A，B为C;\n4.结束;\n");
while(1)
{
switch(menu_select())
{
case 1:
InputFormula(A);
printf("\n");
break;
case 2:
InputFormula(B);
printf("\n");
break;
case 3:
AdditionA_BToClink(A,B,C);
printf("\n\n");
break;
case 4:
printf("end\n");
return;
}
}
}
实验1_3
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define MAXQSIZE 100
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int QElemType;
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
int listsize;
}SqList;
typedef struct
{
QElemType *base;
int front;
int rear;
}SqQueue;
//队列
Status InitQueue(SqQueue &Q) //*************------------SqQueue &Q 引用
{
Q.base = (QElemType *)malloc(MAXQSIZE *sizeof(QElemType));
if(!Q.base)
return OVERFLOW;
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) //*******---------这里用&是不是为了返回一个e
{
if(Q.front == Q.rear)
return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
//线性表
Status InitList_Sq(SqList& L) //构造一个空的线性表
{
L.elem=(ElemType*) malloc(100*sizeof(ElemType));
if (!L.elem)
return OVERFLOW;
L.length=0;
return OK;
}
Status ListInsert_Sq(SqList& L,int i,ElemType e) //插入x
{
ElemType *q,*p;
if (i<1 || i>L.length+1)
{
return ERROR;
}
q=&(L.elem[i-1]);
for( p=&( L.elem[L.length-1] ); p>=q; --p )
*(p+1) = *p;
*q = e;
++L.length;
return OK;
}
Status AcquireSqlist(SqQueue &Q,SqList& M,int n,int m, int s);//报数输出新线性表
void main()
{
SqQueue R;
SqList M;
InitQueue(R);
InitList_Sq(M);
int n,s,m;
printf("该圆桌有n人，从第s个人开始报数，数到m出列，\n然后从出列的下一个人重新开始报数，数到m的人又出列，\n如此重复，直到所有的人全部出列为止。\n 请输入n,s,m的值\n");
printf("n=");scanf("%d",&n);
printf("s=");scanf("%d",&s);
printf("m=");scanf("%d",&m);
AcquireSqlist(R,M,n,s,m);
}
Status AcquireSqlist(SqQueue &Q,SqList& M,int n,int s, int m)
{
int i,j=1,f,g,k=1,a;
if(n > MAXQSIZE)
return ERROR;
for(i=1;i<=n;i++)
{
EnQueue(Q,i);
}
for(i=1;i<=s;i++)
{
DeQueue(Q,a);
EnQueue(Q,a);
}
while(k<=n)
{
for(i=1; i<=m-1; i++)
{
DeQueue(Q,a);
EnQueue(Q,a);
}
DeQueue(Q,a);
ListInsert_Sq(M,j,a);
j++;
k++;
}
printf("\n您得到的顺序表为");
for(g=0;g<n;g++)
{
printf("%d ",M.elem[g]);
}
printf("\nend");
return OK;
}
（2）运行结果
实验1_1:
实验1_2：
实验1_3
四、实验感想
学习并掌握了线性结构的各类储存方式及其应用