数据结构实验报告_数据结构实验报告答案

数据结构实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验报告答案”。

数据结构实验报告 第四次实验

学号：20141060106

姓名：叶佳伟

一、实验目的1、复习线性表、栈、队列的逻辑结构、存储结构及基本操作；

2、掌握顺序表、（带头结点）单链表、顺序栈、链队列；

3、了解有顺表、链栈、循环队列。

3、了解有顺表、链栈、循环队列。

二、实验内容

1、（必做题）假设有序表中数据元素类型是整型，请采用顺序表或（带头结点）单链表实现：

（1）OrderInsert(&L, e, int(*compare)(a, b))//根据有序判定函数compare，在有序表L的适当位置插入元素e；

（2）OrderInput(&L, int(*compare)(a, b))//根据有序判定函数compare，并利用有序插入函数OrderInsert，构造有序表L；

（3）OrderMerge(&La, &Lb, &Lc, int(*compare)())//根据有序判定函数compare，将两个有序表La和Lb归并为一个有序表Lc。

2、（必做题）假设栈中数据元素类型是字符型，请采用顺序栈实现栈的以下基本操作：（1）Status InitStack(&S)//构造空栈S；（2）Status Push(&S, e)//元素e入栈S；

（3）Status Pop(&S, &e)//栈S出栈，元素为e。

3、（必做题）假设队列中数据元素类型是字符型，请采用链队列实现队列的以下基本操作：（1）Status InitQueue(&Q)//构造空队列Q；（2）Status EnQueue(&Q, e)//元素e入队列Q；（3）Status DeQueue(&Q, &e)//队列Q出队列，元素为e。

三、算法描述

（采用自然语言描述）

⒈⑴分别插入第一个链表和第二个链表的数据；

⑵根据有序判定函数compare，将两个有序表La和Lb归并为个有序表。⑶输出归并后的有序表。2.⑴构造一个栈的结构体

⑵利用函数initstack构造空栈

⑶Push函数将元素依次存储到栈里 ⑷利用pop函数输出栈顶元素 3.⑴ 构造Queueptr的结构体 ⑵ 构造一个队列的结构体

⑶ 利用函数InitQueue构造空队列

⑷ EnQueue函数将元素依次存储到栈里 ⑸ 利用DeQueue函数输出栈顶元素

四、详细设计

（画出程序流程图）

五、程序代码

（给出必要注释）

第一题：#include #include

typedef struct LNode {int date;struct LNode *next;} LNode,*Link;typedef struct LinkList {Link head;int len;} LinkList;

int compare(LinkList *L,int e){int Lc=0;Link p;p=L->head;p=p->next;while(p!=NULL){if(e>p->date){p=p->next;Lc++;} else return Lc;} return Lc;}

void OrderInsert(LinkList *L,int e,int(*compare)()){Link temp,p,q;int Lc,i;temp=(Link)malloc(sizeof(LNode));temp->date=e;p=q=L->head;p=p->next;Lc=(*compare)(L,e);if(Lc==L->len){while(q->next!=NULL){q=q->next;} q->next=temp;temp->next=NULL;} else {for(i=0;inext;q=q->next;} q->next=temp;temp->next=p;} ++L->len;}

void OrderMerge(LinkList *La,LinkList *Lb,int(*compare)()){int i,Lc=0;Link temp,p,q;q=La->head->next;while(q!=NULL){p=Lb->head;temp=(Link)malloc(sizeof(LNode));temp->date=q->date;Lc=(*compare)(Lb,q->date);if(Lc==Lb->len){while(p->next!=NULL){p=p->next;} p->next=temp;temp->next=NULL;} else {for(i=0;inext;} temp->next=p->next;p->next=temp;} q=q->next;++Lb->len;} }

LinkList *Initialize(LinkList *NewList){int i;Link temp;NewList=(LinkList *)malloc((2+1)*sizeof(LinkList));for(i=0;idate=0;temp->next=NULL;(NewList+i)->head=temp;(NewList+i)->len=0;} return NewList;}

void Insert(LinkList *NewList){int a,i;char c;printf(“在第1个表中插入数据，以空格和回车为间隔，输入”.”对下个表插入数据n”);for(i=0;i

{if(i

void Show(LinkList *L){Link p;p=L->head->next;while(p!=NULL){printf(“%dt”,p->date);p=p->next;} }

void Display(LinkList *NewList,void(*Show)()){printf(“所有有序表如下n”);printf(“第一个有序表为：n”);(*Show)(NewList+0);printf(“n”);printf(“第二个有序表为：n”);(*Show)(NewList+1);printf(“n”);printf(“归并后有序表为n”);(*Show)(NewList+2);}

int main(){LinkList *NewList=NULL;int i;printf(“t 开始插入数据n”);NewList=Initialize(NewList);Insert(NewList);for(i=0;i

Display(NewList,Show);return 0;第二题：#include #include #include #define M 50 typedef struct // 定义一个栈结构 { int top;int array[M];}Stack;void Init(Stack *s);// 初始化栈的函数

void Push(Stack *s,int data);// 进行压栈操作的函数 void Traverse(Stack *s);// 遍历栈函数

char Pop(Stack *s);// 进行出栈操作的栈函数 void Clear(Stack *s);// 清空栈的函数 int main(){ Stack s;// 定义一个栈 int i;int num;char data;// 临时保存用户输入的数据 char re_num;// 保存pop函数的返回值 Init(&s);printf(“你想输入几个数据:”);scanf(“%d”,&num);for(i=0;i

printf(“n”);Clear(&s);// 调用清空栈函数 printf(“遍历下看看栈空没n”);Traverse(&s);printf(“n”);return 0;}

void Init(Stack *s)// 进行栈的初始化函数 { s->top=-1;}

void Push(Stack *s,int data)/*进栈*/ { if(s->top>=M-1)return;/*full*/ s->top++;s->array[s->top]=data;} void Traverse(Stack *s)// 遍历栈的函数 { int i;for(i=0;itop;i++)printf(“%2c”,s->array[i]);} char Pop(Stack *s)// 进行出栈操作函数 { char x;x=s->array[s->top];s->top--;return x;} void Clear(Stack *s)// 清空栈的函数 { s->top=-1;}

第三题：

#include #include

typedef void Status;typedef int QElemType;

#define STACK_INIT_SIZE 10//初始容量 #define STACKINCREMENT 5//容量增量

typedef struct QNode{ QElemType data;struct QNode *next;}QNode,*QueuePtr;

typedef struct{ QueuePtr front;//队头指针

QueuePtr rear;//队尾指针 }LinkQueue;

Status InitQueue(LinkQueue &Q){ //构造一个空对列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(-1);Q.front->next=NULL;}

Status EnQueue(LinkQueue &Q,QElemType e){ //插入元素e为对列Q的新元素

QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf(“OVERFLOW”);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;}

Status DeQueue(LinkQueue &Q,QElemType e){ //若对列不空，用e返回其值，并返回OK //否则返回ERROR QueuePtr p;if(Q.front==Q.rear)printf(“ERROR”);p=Q.front->next;e=p->data;printf(“对列中的队头元素为:%dn”,e);Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);}

main(){ LinkQueue Q;int n,i;QElemType e;InitQueue(Q);printf(“请输入队列中要入队列的元素个数:n”);scanf(“%d”,&n);for(i=0;i

六、测试和结果

（给出测试用例以及测试结果）

第二题：

第三题：

：

七、用户手册

（告诉用户如何使用程序）1.使用Microsoft Visual C++ 2.使用Microsoft Visual C++ 3.使用Microsoft Visual C++