数据结构实验报告.docx

1、数据结构实验报告数据结构实验报告第四次实验学号：20141060106 姓名：叶佳伟一、实验目的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.1 构造Queueptr的结构体2 构造一个队列的结构体3 利用函数I

4、nitQueue构造空队列4 EnQueue函数将元素依次存储到栈里5 利用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!

5、=NULL) if(ep-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; e

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

7、) 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; ret

8、urn NewList; 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(

9、第一个有序表为：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; i2; i+) OrderMerge (NewList+i,NewList+2,compare); Dis

10、play(NewList,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()

11、 Stack s; / 定义一个栈 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

12、 Push(Stack *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#includetypede

13、f 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)

14、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 /否

15、则返回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;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+