2023年数据结构实验报告5

数据结构实验报告

第四次实验

学号：姓名:叶佳伟

一、实验目的

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

2、掌握顺序表、(带头结点)单链表、顺序栈、链队列;3、了解有顺表、链栈、循环队列。

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

二、实验内容

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

(1)Orderinsert(&L,e,int(*compare)(a,b))〃根据有序鉴定函数com

pare,在有序表L的适当位置插入元素e；

(2)OrderInput(&L,int(*compare)(a,b))//根据有序鉴定函数compa

re,并运用有序插入函数0rderinsert,构造有序表L；

(3)OrderMerge(&La,&Lb,&Lc,int("compare)())//根据有序鉴定函数

compare,将两个有序表La和Lb归并为一个有序表Lc。

2、(必做题)假设栈中数据元素类型是字符型，请采用顺序栈实现栈的以下基本操作：

(1)StatusInitStack(&S)//构造空栈S;

(2)StatusPush(&S,e)〃元素e入栈S；

(3)StatusPop(&S,&e)//栈S出栈,元素为e。

3、(必做题)假设队列中数据元素类型是字符型，请采用链队列实现队列的以下基本操作：

(1)StatusInitQueue(&Q)//构造空队列Q；

(2)StatusEnQueue(&Q,e)//元素e入队列Q；

(3)StatusDeQueue(&Q,&e)//队列Q出队列，

兀素为e°

三、算法描述

(采用自然语言描述)

1-汾别插入第一个链表和第二遍表的数据；

⑵根据有序鉴定函数compare,将两个有序表La和Lb归并为个有序表。

⑶输出归并后的有序表。

2.

(1胸造一个栈的结构体

⑵运用函数initstack构造空栈

(3)Push函数将元素依次存储到栈里

⑷运用p。P函数输出栈顶元素

3.

⑴构造Queueptr的结构体

⑵构造一个队列的结构体

⑶运用函数InitQueue构造空队列

(4)EnQueue函数将元素依次存储到栈里

(5)运用DeQueue函数输出栈顶元素

四、具体设计

(画出程序流程图)

五、程序代码

（给出必要注释）

第一题：#include<stdio.h>

#inc1ude<stdlib.h>

typedefstruetLNode

{intdate;

structLNode*next;

}LNode,*Link;

typedefstructLinkList

{Linkhead;

int1en;

}LinkList；

intcompare(LinkList*L,inte)

{intLc=O;

Linkp;

p=L->head;

p=p->next；

while(p!=NULL)

{if(e>p—>date)

{p=p->next；Lc++;}

else

returnLc;

)

returnLc;

)

voidOrderinsert(LinkList*L,inte,int(^compare)())

{Linktemp,p,q;

intLc,i;

temp=(Link)ma1loc(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；

}

e1se

{for(i=0;i<Lc;i++)

{p=p->next；q=q->next;}

q—>next=temp；temp->next=p;

)

++L->1en;

)

voidOrderMerge(LinkList*La,LinkList*Lb,int(*compare)())

{inti,Lc=0;

Linktemp,p,q;

q二La->head—>next;

while(q!=NULL)

{p=Lb->head;

temp=(Link)ma1loc(sizeof(LNode));

temp—>date=q->date；

Lc=(*compare)(Lb,q->date);

if(Lc==Lb->len)

{whi1e(p->next!=NULL)

{p=p->next;}

p->next=temp；

temp—>next=NULL;

else

{for(i=0;i<Lc；i++)

{p=p->next;}

temp->next=p—>next;

p->next=temp;

)

q=q->next;

++Lb->len;

LinkList*Initia1ize(LinkList*NewList)

{inti;

Linktemp;

NewList=(LinkList*)ma11oc((2+l)*sizeof(LinkList))；

for(i=0;i<2+l;i++)

{temp=(Link)mal1oc(sizeof(LNode));

temp->date=0;

temp->next=NULL;

(NewList+i)-〉head二temp;

(NewList+i)—>1en=0;

)

returnNewList;

voidInsert(LinkList*NewList)

{inta,i;

charc;

printf(〃在第1个表中插入数据，以空格和回车为间隔，输入”.”对下个表插入数据\n〃)；

for(i=0;i<2;i++)

{while(1)

{scanf("%d/z,&a);

c=getchar();

if(c='.’)

{if(i<2-2)

printf("在第％d个表中插入数据，以空格和回车为间隔，输入”.”对下个表插入

数据\n〃，i+2);

eIseif(i==2-2)

printf(〃在第/d个表中插入数据，以空格和回车为间隔，输入"."结束输出\n〃，i+2);

brecik；

)

else

{0rderinsert((NewList+i),a,compare);}

)

}

}

voidShow(LinkList*L)

{Linkp;

p=L->head->next;

while(p!=NULL)

{printf("%d\t”,p->date)；

p=p->next;

)

)

voidDisplay(LinkList*NewList,void(*Show)())

{printf(〃所有有序表如下\n");

printf(〃第一个有序表为:\n〃)；

(*Show)(NewList+0)；

printf(H\n〃)；

printf(〃第二个有序表为:\n〃)；

(*Show)(NewList+1)；

printf(z，\n");

printf(〃归并后有序表为\n'1);

(*Show)(NewList+2);

)

intmain()

{LinkList*NewList=NULL;

inti；

Printf(〃\t开始插入数据\n");

NewList=Initia1ize(NewList);

Insert(NewList);

for(i=0;i<2；i++)

{0rderMerge(NewList+i,NewList+2,compare)；}

Display(NewList,Show);

return0;

第二题:#include<stdio.h>

#include<stdlib.h>

#inc1ude<mal1oc.h>

#defineM50

typedefstruct//定义一个栈结构

(

inttop;

intarray[M]；

}Stack；

voidInit(Stack*s);//初始化栈的函数

voidPush(Stack*s,intdata);//进行压栈操作的函数

voidTraverse(Stack*s);//遍历栈函数

charPop(Stack*s);//进行出栈操作的栈函数

voidClear(Stack*s);//清空栈的函数

intmain()

i

Stacks;//定义一个栈

inti；

intnum；

chardata;//临时保存用户输入的数据

charrenum;//保存pop函数的返

回值

Init(&s);

printf(〃你想输入几个数据:〃)；

scanf(”％d〃,&num);

for(i=0;i<num;i++)

(

printf(〃第％d个字符:〃，i+1);

scanf("%s”,&data);

Push(&s,data);

)

Traverse(&s)；//调用遍历函数

printf(〃你想去掉几个字符：〃)；

scanf("%dz/,&num);

printf(〃你去掉的字符是:〃)；

for(i=0;i<num;i++)

(

re_num=Pop(&s);//调用Pop函数，并把返回至赋给

re.num

printf(〃％c",re_num)；

}

printf(〃看看删除后尚有啥:〃);

Traverse(&s);

Printf(〃\n〃)；

C1ear(&s);//调用清空栈函数

printf(〃遍历下看看栈空没\n”)；

Traverse(&s);

printf('\n");

return0;

voidInit(Stack*s)〃进行栈的初始化函数

s->top=-l；

)

voidPush(Stack*s,intdata)/*进栈*/

(

if(s->top>=M-l)return;/*fu11*/

s->top++;

s—>array[s->top]=data;

)

voidTraverse(Stack*s)//遍历栈的函数

I

inti；

for(i=0;i<=s->top;i++)

printf(〃%2c〃，s->array[i])；

)

charPop(Stack*s)〃进行出栈操作函数

I

charx；

x=s->array[s->top]；

s->top-;

returnx;

}

voidClear(Stack*s)〃清空栈的函数

s->top=-1;

)

第三题：

#inc1ude<stdio.h>

#inc1ude<stdlib.h>

typedefvoidStatus;

typedefintQE1emType;

#defineSTACK_INIT_SIZE10〃初始容量

#defineSTACKINCREMENT5〃容量增量

typedefstruetQNode{

QElemTypedata;

^structQNode*next;

}QNode,*QueuePtr;

typedefstruct{

QueuePtrfront;//队头指针

oQueuePtrrear;//队尾指针

}LinkQueue;

StatusInitQueue(LinkQueue&Q){

〃构造一个空对列Q

Q.front=Q.rear=(QueuePtr)maHoc(sizeof(QNode));

if(!Q.front)exit(—1);

Q.front->next=NULL;

}

StatusEnQueue(LinkQueue&Q,QElemTypee){

。〃插入元素e为对列Q的新元素

QueuePtrp;

p=(QueuePtr)malloc(sizeof(QNode))；

if(!p)printf("OVERFLOW”)；

p—>data=e；p—>next=NULL;

oQ.rear->next=p;

oQ.rear=p;

)

StatusDeQueue(LinkQueue&Q,QElemTypee){

。//若对列不空，用e返回其值,并返回OK

〃否则返回ERROR

QueuePtrp；

-if(Q.frontrear)printf("ERROR")；

。p=Q.front—>next;

e=p->data；

printf(〃对列中的队头元素为:%d\n〃，e);

oQ・front->next=p->next;

或f(Q.rear==p)Q.rear=Q.front;

free(p);

mainO

{6LinkQueueQ：

intn,i;

QE1emTypee;

InitQueue(Q);

printf(〃请输入队列中要入队列的元素个数:\n")；

scanf(/z%d〃，&n);

for(i=0;i<n;i++)