数据结构实验报告

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函数将元素依次存储到栈里利用po

4、p函数输出栈顶元素3.1 构造Queueptr的结构体2 构造一个队列的结构体3 利用函数InitQueue构造空队列4 EnQueue函数将元素依次存储到栈里5 利用DeQueue函数输出栈顶元素四、详细设计（画出程序流程图）五、程序代码（给出必要注释）第一题：#include <stdio.h> #include <stdlib.h> typedef struct LNode int date; struct LNode *next; LNode,*Link; typedef struct LinkList Link head; int len; LinkList;

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

6、ad; 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; i<Lc; i+) p=p->next;q=q->next; q->next=temp;temp->next=p; +L->len; void OrderMerge (LinkList *La,LinkList *Lb,int (*compare)() int i,Lc=0;

7、 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; i<Lc; i+) p=p->next; temp-&g

8、t;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; i<2+1; i+) temp=(Link)malloc(sizeof(LNode); temp->date=0; temp->next=NULL; (NewList+i)->head=temp; (NewList

9、+i)->len=0; return NewList; void Insert (LinkList *NewList) int a,i; char c; printf("在第1个表中插入数据，以空格和回车为间隔，输入”.”对下个表插入数据n"); for(i=0; i<2; i+) while(1) scanf("%d",&a); c=getchar(); if(c='.') if(i<2-2) printf("在第%d个表中插入数据，以空格和回车为间隔，输入”.”对下个表插入数据n",i+2

10、); else if(i=2-2) printf("在第%d个表中插入数据，以空格和回车为间隔，输入”.”结束输出n",i+2); break; else OrderInsert(NewList+i),a,compare); 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(&qu

11、ot;所有有序表如下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=I

12、nitialize(NewList); Insert(NewList); for(i=0; i<2; i+) OrderMerge (NewList+i,NewList+2,compare); Display(NewList,Show); return 0;第二题：#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define M 50typedef struct / 定义一个栈结构 int top; int arrayM; Stack;void Init(Stack *s); / 初始化

13、栈的函数 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"

14、;,&num); for (i=0;i<num;i+) printf("第%d个字符:",i+1); scanf("%s",&data); Push(&s,data); Traverse(&s); / 调用遍历函数 printf("你想去掉几个字符: "); scanf("%d",&num); printf("你去掉的字符是:"); for (i=0;i<num;i+) re_num = Pop(&s); / 调用Pop函数，并把返回至

15、赋给re.num printf("%c ",re_num); printf("看看删除后还有啥:"); Traverse(&s); 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) /*进栈*/ i

16、f (s->top>=M-1)return;/*full*/ s->top+; s->arrays->top=data;void Traverse(Stack *s)/ 遍历栈的函数 int i; for(i=0;i<=s->top;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=

17、-1;第三题：#include<stdio.h>#include<stdlib.h>typedef void Status;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 Ini

18、tQueue(LinkQueue &Q)/构造一个空对列QQ.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,QElemT