南阳理工学院_软件学院数据结构上机实验指导书全部答案

南阳理工学院

数据结构上机实验指导书

（2011版）

答案（仅内供）

软件学院·软件工程教研室

2011.3

目 录

实验1 线性表应用 .................................................................. 2 实验2 栈和队列的应用 ........................................................ 14 实验3 线性表应用 ................................................................ 27 实验4 图论及其应用 ............................................................ 46 实验5 查找 ............................................................................ 59 实验6 排序 ............................................................................ 64

实验1 线性表应用

一、实验目的

1. 了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在

计算机中的实现。

2. 能够利用线性表结构对实际问题进行分析建模，利用计算机求解。 3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特

点及其适用场合。

二、实验内容及步骤

1. 利用程序设计语言分别实现顺序表和链表的抽象数据类型。 2. 掌握程序分文件（头文件和实现文件）书写的方式。

3. 分别用顺序表和链表实现课本算法2.2：合并两个非递减有序序列，并

对其时间性能做出分析。

顺序表的非递减数列合并

实验2 栈和队列的应用

一、实验目的

1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正

确选用它们。

2. 熟练掌握栈类型的两种实现方法。

3. 熟练掌握循环队列和链队列的基本操作实现算法。

二、实验内容及步骤

1. 用程序设计语言实现栈和队列的抽象数据类型。 2. 在第一题的基础上完成以下选择：

选择一：

1) 设计并实现括号匹配算法。

2) 用队列实现在屏幕上打印杨辉三角。 选择二：

分别用栈和队列实现迷宫问题求解。

选择三：

分别用栈和队列实现一个列车调度系统。

括号匹配算法。

#include<stdio.h> #include<malloc.h> #include<stdlib.h> #include "string.h" return 0; }

int PushStack(LinkStack top, DataType e)

/*进栈操作就是要在链表的第一个结点前插入一个新结点，进栈成功返回1*/ {

LStackNode *p;

/*定义指向第i个元素的前驱结点指针pre，指针p指向

新生成的结点*/

if((p=(LStackNode*)malloc(sizeof(LStackNode)))==NULL) { }

p->data=e;

/*指针p指向头结点*/

printf("内存分配失败!"); exit(-1);

p->next=top->next; top->next=p; return 1;

}

int PopStack(LinkStack top,DataType *e)

/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回0*/ {

LStackNode *p; p=top->next; if(!p) {

printf("栈已空"); q=p;

p=p->next; free(q); } }

int GetTop(LinkStack top,DataType *e) {

LStackNode *p;

/*判断链栈是否为空*/

p=top->next; if(!p) {

printf("栈已空");

/*判断链栈是否为空*/

return 0; }

*e=p->data;

/*将出栈元素赋值给e*/

return 1; }

void main() { case '[': case '{': PushStack(S,*p++);

break;

case ')': case ']': case '}': if(StackEmpty(S)) { else {

GetTop(S,&e);

printf("缺少右括号.\n");

}

int Match(DataType e,DataType ch) { if(e=='('&&ch==')')

return 1;

else if(e=='['&&ch==']')

return 1;

else if(e=='{'&&ch=='}')

return 1;

else

return 0;

typedef struct QNode {

DataType data; struct QNode* next; }LQNode,*QueuePtr; typedef struct {

QueuePtr front; QueuePtr rear; }LinkQueue;

void InitQueue(LinkQueue *LQ) /*将返回1，否则返回0*/ return 1; else return 0; }

int EnterQueue(LinkQueue *LQ,DataType e) /*将元素e插入到链式队列LQ中，插入成功返回1*/ {

LQNode *s;

LQ->rear=s;

/*将队尾指针指向p*/

return 1; }

//int DeleteQueue(LinkQueue *LQ,DataType *e)

///*删除链式队列中的队头元素，并将该元素赋值给e，删除成功返回1，否则返回0*/ //{

// LQNode空*/ }

/*出队操作。*/

int DeleteQueue(LinkQueue *Q,DataType *x) {

/* 将队列Q的队头元素出队，并存放到x所指的存储空间中 */ LQNode * p; if(Q->front==Q->rear)

retu

return 0;

else { }

s=LQ.front->next; /*将指针p指向队列的第一个元素即队头元素*/ *e=s->data; return 1;

/*将队头元素赋值给e，取出队头元素*/

/*产生第中间n-2行的元素*/ for(n=2;n<=N;n++)

/*产生第i行元素并入队，同时将第i-1行的

元素保存在临时数组中*/

{

k=0;

EnterQueue(&Q,1);

/*第i行的第一个元素入队*/

for(i=1;i<=n-2;i++) /*利用队列中第i-1行元素产生第i行的中间

i-2个元素并入队列*/ }

void main() { } }

int n;

printf("请输入要打印的行数：n=:"); scanf("%d",&n); YangHuiTriangle(n);

{

DeleteQueue(&Q,&t); temp[k++]=t;

/*将第i-1行的元素存入临时数组*/

/*将最后一行元素存入临时数组*/

while(!QueueEmpty(Q)) { }

DeleteQueue(&Q,&t); temp[k++]=t; if(QueueEmpty(Q))

PrintArray(temp,k,N);

用栈实现迷宫问题求解 #include<stdio.h> #include<stdlib.h> #define OVERFLOW -1 #define MAX 100 typedef struct { int x; int y; int d; }Data; typedef struct {

int pos;

Data data[MAX]; }SNode,*Stack;

Stack InitStack() {

Stack pStack;

pStack=(Stack)malloc(sizeof(SNode)); if(!pStack)

if(pStack->pos==-1) exit(OVERFLOW); else

pStack->pos--; }

Data GetTop(Stack pStack) {

revoid DisplayPath(Stack pStack) {

Data element; printf("The path is:\n"); while(!IsEmpty(pStack))

{

element=GetTop(pStack); Pop(pStack);

printf("The node is:(%d,%d)\n",element.x,element.y);

}

}

void MazePa{ int i …… 此处隐藏：3061字，全部文档内容请下载后查看。喜欢就下载吧 ……