数据结构实验报告(共10页).doc

《数据结构实验报告(共10页).doc》由会员分享，可在线阅读，更多相关《数据结构实验报告(共10页).doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构实验报告第四次实验学号： 姓名：叶佳伟一、实验目的1、复习线性表、栈、队列的逻辑结构、存储结构及基本操作；2、掌握顺序表、（带头结点）单链表、顺序栈、链队列；3、了解有顺表、链栈、循环队列。3、了解有顺表、链栈、循环队列。二、实验内容1、（必做题）假设有序表中数据元素类型是整型，请采用顺序表或（带头结点）单链表实现：（ 1） OrderInsert(&L, e, int (*compare)(a, b)/根据有序判定函数compare，在有序表L的适当位置插入元素e；（ 2） OrderInput(&L, int (*compare)(a, b)/根据有序判定

2、函数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、（必做题）假设队列中数据元素类型是字符型，请采用链队列实现队列的以下

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构

4、造空队列 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

5、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

6、; 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;

7、 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

8、; void Insert (LinkList *NewList) int a,i; char c; printf(在第1个表中插入数据，以空格和回车为间隔，输入”.”对下个表插入数据n); for(i=0; i2; i+) while(1) scanf(%d,&a); c=getchar(); if(c=.) if(ihead-next; while(p!=NULL) printf(%dt,p-date); p=p-next; void Display (LinkList *NewList,void (*Show)() printf(所有有序表如下n); printf(第一个有序表为：n);

9、 (*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; i2; i+) OrderMerge (NewList+i,NewList+2,compare); Display(NewLis

10、t,Show); return 0;第二题：#include #include #include #define M 50typedef struct / 定义一个栈结构 int top; int arrayM; 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; /

11、 定义一个栈 int i; int num; char data; / 临时保存用户输入的数据 char re_num; / 保存pop函数的返回值 Init(&s); printf(你想输入几个数据:); scanf(%d,&num); for (i=0;inum;i+) printf(第%d个字符:,i+1); scanf(%s,&data); Push(&s,data); Traverse(&s); / 调用遍历函数 printf(你想去掉几个字符: ); scanf(%d,&num); printf(你去掉的字符是:); for (i=0;itop=-1;void Push(Stack

12、 *s,int data) /*进栈*/ if (s-top=M-1)return;/*full*/ s-top+; s-arrays-top=data;void Traverse(Stack *s)/ 遍历栈的函数 int i; for(i=0;itop;i+) printf(%2c,s-arrayi); char Pop(Stack *s)/ 进行出栈操作函数 char x; x=s-arrays-top;s-top-; return x; void Clear(Stack *s)/ 清空栈的函数s-top=-1;第三题：#include#includetypedef void Statu

13、s;typedef int QElemType;#define STACK_INIT_SIZE 10/初始容量#define STACKINCREMENT 5/容量增量typedef struct QNodeQElemType data;struct QNode *next; QNode,*QueuePtr;typedef structQueuePtr front;/队头指针QueuePtr rear;/队尾指针LinkQueue;Status InitQueue(LinkQueue &Q)/构造一个空对列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNod

14、e);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/否则返回ERRORQueuePtr p;if(Q.front

15、=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;in;i+) printf(队列里的第%d个元素为:,i+1); scanf(%d,&e); EnQueue(Q,e);printf(n); DeQueue(Q,e);六、测试和结果（给出测试用例以及测试结果）第二题：第三题：七、用户手册（告诉用户如何使用程序）1. 使用Microsoft Visual C+2. 使用Microsoft Visual C+3. 使用Microsoft Visual C+专心-专注-专业