数据结构实验四

数据结构实验报告

第四次实验

一、实验目的

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

2、掌握顺序表和(带头结点)单链表；

3、了解有序表。

二、实验内容

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

表实现：

(1)Orderlnsert(&L,e,int(*compare)(a,b))

〃根据有序判定函数compare,在有序表L的适当位置插入元素e；

(2)Orderlnput(&L,int(*compare)(a,b))

〃根据有序判定函数compare,并利用有序插入函数Orderinsert,构造有序表L；

(3)OrderMerge(&La,&Lb,&Lc,int(*compare)())

〃根据有序判定函数compare,将两个有序表La和Lb归并为一个有序表Lc。

2、(必做题)请实现：

(1)升基多项式的构造，升基多项式是指多项式的各项按指数升序有序，约定系数不能

等于0，指数不能小于0；

(2)两个升基多项式的相加。

三、算法描述

(采用自然语言描述)

1、创建带头节点的链表，输入两个有序表数据La、Lb,归并两个有序表得有序表Lc,输

出三个有序表。输入需插入数据e,将e插入有序表Lc,输出插入e后的Lc。

2、创建链表，按指数升序输入多项式得序数和指数，输出多项式。按指数升序输入第二个

多项式得序数和指数，两个多项式相加，输出第二个多项式和两个多项式的和。

四、详细设计

(画出程序流程图)

1、

2、

擅卅敢升序输入专项式用序散和忖也

/喻出多项式」

按排数升序输入第.二个多项式

两个多加式相加

_________,______

物出第二个多项式和两个多项式的和

五、程序代码

(给出必要注释)

1、

#include<stdio.h>

#include<malloc.h>

typedefstructLNode

(

intdate;

structLNode*next;

}LNode,*Link;

typedefstructLinkList

(

Linkhead;

intlenth;

}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)())

{

Linktempzp,q;

intLc,i;

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

temp->date=e;

p=q=L->head;

p=p->next;

Lc=(*compare)(L,e);

if(Lc==L->lenth)

(

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->lenth;

)

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

inti,Lc=O;

Linktemp,pzq;

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->lenth)

(

while(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->lenth;

}

)

LinkList*lnitialize(LinkList*NewList)

(

inti;

Linktemp;

NewList=(LinkList*)malloc((2+l)*sizeof(LinkList));

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

(

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

temp->date=O;

temp->next=NULL;

(NewList+i)->head=temp;

(NewList+i)->lenth=O;

)

returnNewList;

voidInsert(LinkList*NewList)

(

intaj;

charc;

在第1个表中插入数据，输入“N”再对下个表插入数据

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

(

while(l)

c=getchar();

if(c=='N*)

(

if(i<2-2)

在第%d个表中插入数据，输入“N”再对下个表插入数

据

elseif(i==2-2)

在第%d个表中插入数据，输入“N”结束。

break;

)

else

(

Orderlnsert((NewList+i),a,compare);

)

)

)

voidShow(LinkList*L)

(

Linkp;

p=L->head->next;

while(p!=NULL)

p=p->next;

)

)

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

(

有序表如下

第一个有序表为

(*Show)(NewList+0);

第二个有序表为

(*Show)(NewList+l);

归并后有序表为

(*Show)(NewList+2);

}

intmain()

(

LinkList*NewList=NULL;

LinkList*L;

inti,e;

请按要求输入数据

NewList=lnitialize(NewList);

Insert(NewList);

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

(

OrderMerge(NewList+i,NewList+2,compare);

}

visit(NewList,Show);

L=NewList;

请输入将要插入的

Orderlnsert((NewList+i),e,compare);

对归并后有序表插入e后得

Show(NewList+2);

return0;

)

#include<stdio.h>

#include<malloc.h>

typedefstructnode

intxi;

intzi;

structnode*next;

}Node;

Node*Creat()

(

Node*head,*p,*q;

intor,in;

head=(Node*)malloc(sizeof(Node));

head->next=NULL;

q=head;

请输入多项式的序数与指数

按照指数升序输入,系数不能等于0且指数不能小于0,序数与指数之间用空格隔

开，并以00结束输入

while(or)

(

p=(Node*)malloc(sizeof(Node));

p->xi=or;

p->zi=in;

p->next=q->next;

q->next=p;

q=p;

)

returnhead;

)

voidvisit(Node*head)

{

Node*p=head->next;

while(p)

(

p=p->next;

)

}

Node*Add(Node*headl,Node*head2)

(

Node*p,*head,*pl,*p2;

intsum;

head=(Node*)malloc(sizeof(Node));

p=head;

pl=headl->next;

p2=head2->next;

while(pl&&p2)

(

if(pl->zi==p2->zi)

{

sum=pl->xi+p2->xi;

if(sum)

(

pl->xi=sum;

p->next=pl;

p=pl;

)

pl=pl->next;

p2=p2->next;

)

else

(

if(pl->zi<p2->zi)

{

p->next=pl;

P=P1；

pl=pl->next;

)

else

(

p->next=p2;

P=P2；

p2=p2->next;

)

)

)

if(pl)

p->next=pl;

else

p->next=p2;

returnhead;