数据结构(栈及队列)实验报告 C语言版.doc

XXXX学 院计 算 机 课 程 实 验 报 告（201X201X年度第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-201XMade : XXXXXuse : Stack by chain*/#include #include #define OK 1#define ERROR 0typedef 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;ptop;p+) printf(%5d,*p); i+; return i;/*附上JAVA的线性栈实现：*/public class stackofIntprivate int elemtype = new int100;private int size= 0;public stackofInt() public stackofInt(int e) this.elemtype = new inte;public void push(int e)if(sizeelemtype.length)int temp = new intelemtype.length+10;System.arraycopy(elemtype, 0, temp, 0, elemtype.length);elemtype = temp;elemtypesize= e;+size;public int pop()if(size=0) System.out.println(The stack is empty!);System.exit(0);return 0;elseint a = elemtypesize-1;-size;return a;public boolean isempty()if(size = 0)return true;return false;public void toempty()size = 0; public int gettop()return elemtypesize-1; public void printstack()int i=1;while(i=size)System.out.print(elemtypei-1+ );i+;public static void 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 0typedef 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 thequeue 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 isnt 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 QUEUEElemType *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 5typedef struct QUEUEElemType *base; ElemType front; LinkQueue;LinkQueue* InitQueue()LinkQueue *Q;doQ= (LinkQueue*)malloc(sizeof(LinkQueue);while(!Q);do (*Q).base = (ElemType*)ma