201310913232数据结构(3)

实验三 顺序栈和队列基本操作的实现

一、实验学时： 2学时 二、实验目的

实现顺序栈和队列的基本操作

三、实验内容

1．顺序栈的建立、取栈顶元素、入栈、出栈

2．队列的建立、取队中元素、入队、出队、循环队列中入队、出队操作

四、主要仪器设备及耗材

硬件：计算机一台

软件：VC++ 6.0，MSDN2003或者以上版本

五、实验步骤

1. 分析问题 2. 写出算法 3. 编制程序 4. 上机调试 5. 分析结果

六、程序清单

#include #include #define MaxSize 100 #define maxSize 5

typedef char ElemType; typedef struct { ElemType elem[MaxSize]; int top; /*栈指针*/ } SqStack;

9

typedef struct { ElemType elem[maxSize]; int front,rear; /*队首和队尾指针*/ } SqQueue;

extern void InitStack(SqStack *&s); extern void ClearStack(SqStack *&s); extern int StackLength(SqStack *s); extern int StackEmpty(SqStack *s);

extern int Push(SqStack *&s,ElemType e); extern int Pop(SqStack *&s,ElemType &e); extern int GetTop(SqStack *s,ElemType &e); extern void DispStack(SqStack *s); extern void InitQueue(SqQueue *&q); extern void ClearQueue(SqQueue *&q); extern int QueueLength(SqQueue *q); extern QueueEmpty(SqQueue *q);

extern int enQueue(SqQueue *&q,ElemType e); extern int deQueue(SqQueue *&q,ElemType &e); void InitStack(SqStack *&s) { s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; }

void ClearStack(SqStack *&s) { free(s); }

int StackLength(SqStack *s) { return(s->top+1); }

int StackEmpty(SqStack *s) { return(s->top==-1); }

int Push(SqStack *&s,ElemType e) { if (s->top==MaxSize-1) return 0; s->top++; s->elem[s->top]=e; return 1; }

int Pop(SqStack *&s,ElemType &e) { if (s->top==-1) return 0; e=s->elem[s->top]; s->top--; return 1; }

int GetTop(SqStack *s,ElemType &e) { if (s->top==-1) return 0; e=s->elem[s->top]; return 1; }

void DispStack(SqStack *s) { int i; for (i=s->top;i>=0;i--) printf(\ printf(\}

void InitQueue(SqQueue *&q) { q=(SqQueue *)malloc (sizeof(SqQueue));

10

q->front=q->rear=0; }

void ClearQueue(SqQueue *&q) { free(q); }

int QueueEmpty(SqQueue *q) { return(q->front==q->rear); }

int QueueLength(SqQueue *q) { return (q->rear-q->front+maxSize)%maxSize; }

int enQueue(SqQueue *&q,ElemType e) { if ((q->rear+1)%maxSize==q->front) /*队满*/ return 0; q->rear=(q->rear+1)%maxSize; q->elem[q->rear]=e; return 1; }

int deQueue(SqQueue *&q,ElemType &e) { if (q->front==q->rear) /*队空*/ return 0; q->front=(q->front+1)%maxSize; e=q->elem[q->front]; return 1; }

void main() { ElemType e; SqStack *s; printf(\一、对栈的基本操作:\\n\ printf(\初始化栈s\\n\ InitStack(s); printf(\栈为%s\\n\空\非空\ printf(\依次进栈元素a,b,c,d,e\\n\ Push(s,'a'); Push(s,'b'); Push(s,'c'); Push(s,'d'); Push(s,'e'); printf(\栈为%s\\n\空\非空\ printf(\栈长度:%d\\n\ printf(\取栈顶元素:\ GetTop(s,e);printf(\ printf(\ printf(\从栈顶到栈底元素:\ printf(\出栈序列:\ while (!StackEmpty(s)) { Pop(s,e); printf(\ } printf(\ printf(\栈为%s\\n\空\非空\ printf(\释放栈\\n\printf(\

printf(\二、对队列、循环队列的基本操作:\\n\ ClearStack(s); SqQueue *q; printf(\初始化队列q\\n\ InitQueue(q); printf(\依次进队列元素a,b,c\\n\ if (enQueue(q,'a')==0) printf(\队满,不能进队\\n\ if (enQueue(q,'b')==0) printf(\队满,不能进队\\n\

11

}

if (enQueue(q,'c')==0) printf(\队满,不能进队\\n\

printf(\队列为%s\\n\空\非空\if (deQueue(q,e)==0) printf(\队空,不能出队\\n\else printf(\出队一个元素%c\\n\

printf(\队列q的元素个数:%d\\n\printf(\依次进队列元素d,e,f\\n\

if (enQueue(q,'d')==0) printf(\队满,不能进队\\n\if (enQueue(q,'e')==0) printf(\队满,不能进队\\n\if (enQueue(q,'f')==0) printf(\队满,不能进队\\n\

printf(\队列q的元素个数:%d\\n\printf(\出队列序列:\while (!QueueEmpty(q)) { deQueue(q,e); printf(\}

printf(\

printf(\释放队列\\n\ClearQueue(q);

七、运行结果及分析

12

实验四 二叉树基本操作的实现

一、实验学时： 2学时 二、实验目的

1．实现二叉树的有关基本操作 2．实现二叉树遍历操作

三、实验内容

1. 二叉树的建立

2．二叉树的前序遍历、中序遍历、后序遍历

四、主要仪器设备及耗材

硬件：计算机一台

软件：VC++ 6.0，MSDN2003或者以上版本

五、实验步骤

1. 分析问题 2. 写出算法 3. 编制程序 4. 上机调试 5. 分析结果

六、程序清单

#include #include #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data;

/*数据元素*/

13

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库201310913232数据结构(3)在线全文阅读。