2023年數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告10

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告一一實(shí)驗(yàn)4

學(xué)號(hào)：姓名：得分：

一、實(shí)驗(yàn)?zāi)康?/p>

1、復(fù)習(xí)線性表的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作；

2,掌握順序表和(帶頭結(jié)點(diǎn))單鏈表；

3、了解有序表。

二、實(shí)驗(yàn)內(nèi)容

1、(必做題)假設(shè)有序表中數(shù)據(jù)元素類型是整型，請(qǐng)采用順序表或(帶頭結(jié)點(diǎn))單鏈表實(shí)現(xiàn)：

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

//根據(jù)有序鑒定函數(shù)compare,在有序表L的適當(dāng)位置插入元素e；

(2)0rderlnput(&L,int(*compare)(a,b))

〃根據(jù)有序鑒定函數(shù)compare,并運(yùn)用有序插入函數(shù)OrderInsert,構(gòu)造有序表L；

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

〃根據(jù)有序鑒定函數(shù)compare,將兩個(gè)有序表La和Lb歸并為一個(gè)有序表Lc。

2、(必做題)請(qǐng)實(shí)現(xiàn)：

(1)升基多項(xiàng)式的構(gòu)造，升基多項(xiàng)式是指多項(xiàng)式的各項(xiàng)按指數(shù)升序有序，約定系數(shù)不能等于0,指數(shù)不能小

于0;

(2)兩個(gè)升幕多項(xiàng)式的相加。

三、算法描述

(采用自然語(yǔ)言描述)

1.

創(chuàng)建帶頭節(jié)點(diǎn)的鏈表，

輸入兩個(gè)有序表數(shù)據(jù)LaLb

歸并兩個(gè)有序表得有序表Lc

輸出三個(gè)有序表

輸入需插入數(shù)據(jù)e

將e插入有序表Lc

輸出插入e后的Lc

2.

創(chuàng)建鏈表

按指數(shù)升序輸入多項(xiàng)式得序數(shù)和指數(shù)

輸出多項(xiàng)式

按指數(shù)升序輸入第二個(gè)多項(xiàng)式得序數(shù)和指數(shù)

兩個(gè)多項(xiàng)式相加

輸出第二個(gè)多項(xiàng)式和兩個(gè)多項(xiàng)式得和

四、具體設(shè)計(jì)

（畫出程序流程圖）

2.

她擊

五、程序代碼

(給出必要注釋)

1.

#inc1ude<stdio.h>

#inc1ude<mal1oc.h>

typedefstructLNode

(

intdate;

structLNode*next;

}LNode,*Link；

typedefstructLinkList

(

Linkhead;//頭結(jié)點(diǎn)

intlenth;//鏈表中數(shù)據(jù)元素的個(gè)數(shù)

}LinkList;

intcompare(LinkList*L,inte)//有序鑒定函數(shù)compare

(

intLc=0;

Linkp;

p=L—>head;

p=p—>next；

while(p!=NULL)

if(e>p->date)

p=p->next;

Lc++;

}

else

returnLc;

)

returnLc;

)

voidOrderlnsert(LinkList*L,inte,int(*compare)())//根據(jù)有序鑒定函數(shù)compare,在有序表L

的適當(dāng)位置插入元素e;

(

Linktemp,p,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)

(

whi1e(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)())//根據(jù)有序鑒定函數(shù)c

ompare,將兩個(gè)有序表La和Lb歸并為一個(gè)有序表

(

inti,Lc=0;

Linktemp,p,q;

q=La->head—>next;

whi1e(q!=NULL)

(

p=Lb—>head;

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

I

else

(

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

{

p=p->next;

}

ternp->next=p->next;

p->next=temp;

)

q=q->next;

++Lb->lenth；

LinkList*Initialize(LinkList*NewList)

inti；

Linktemp;

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

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

(

ternp=(Link)mal1oc(sizeof(LNode));

temp->date=0；

temp->next=NULL;

(NewList+i)->head=temp;

(NewList+i)—>1enth=O;

)

returnNewList;

)

voidInsert(LinkList*NewList)

(

inta,i;

charc；

printf("在第1個(gè)表中插入數(shù)據(jù)，輸入"N”再對(duì)下個(gè)表插入數(shù)據(jù)\n”);

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

(

while(1)

{

scanf("％d”,&a);

c=getchar();

if(c=='Nz)

if(i<2-2)

primf("在第％€1個(gè)表中插入數(shù)據(jù)，輸入“N”再對(duì)下個(gè)表插入數(shù)據(jù)

\n"，i+2);

eIseif(i==2-2)

printff在第％<1個(gè)表中插入數(shù)據(jù)，輸入“N”結(jié)束。\n”,i+2);

break;

)

else

(

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

voidShow(LinkList*L)〃輸出有序表

(

Linkp;

p=L->head->next;

while(p!=NULL)

(

printf("%dp->date);

p=p->next；

)

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

printf(H有序表如下：\n");

printf("第一個(gè)有序表為:\n");

(*Show)(NewList+0);

printf("\n“)；

printf("第二個(gè)有序表為:\n");

(*Show)(NewList+1);

printf(M\n”);

printf("歸并后有序表為:\n”);

(*Show)(NewList+2);

printf(“\n")；

)

intmain()

(

LinkList*NewList=NULL;

LinkList*L;

inti,e；

printf("請(qǐng)按規(guī)定輸入數(shù)據(jù)\n”)；

NewList=Initialize(NewList);

Insert(NewList);

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

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

visit(NewList,Show);

L=NewList；

printf(n\n請(qǐng)輸入將要插入的e:\n");

seanf("%dn,&e);

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

Printf("對(duì)歸并后有序表插入e后得\n”)；

Show(NewList+2);

return0;

)

2.

#include<stdio.h>

#include<malloc.h>

typedefstructnode

(

intxi；

intzi;

struetnode*next;

}Node;

Node*Creat()〃用鏈表儲(chǔ)存多項(xiàng)式的序數(shù)與指數(shù)

(

Node*head,*p,*q;

intor,in;

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

head->next=NULL;

q=head；

printf(”請(qǐng)輸入多項(xiàng)式的序數(shù)與指數(shù)\n(注意：按照指數(shù)升序輸入,系數(shù)不能等于0且指數(shù)不能小于

0,序數(shù)與指數(shù)用空格隔開，并以00結(jié)束輸入)\n“)；

seanf("%d%d,,,&or,&in);

while(or)

(

p=(Node*)ma1loc(sizeof(Node))；

p->xi=or;

p->zi=in;

p—>next=q—>next;

q->next=p;

q=P;

scanf(u%d%d",&or,&in);

)

returnhead;

)

voidvisit(Node*head)//輸出多項(xiàng)式

(

Node*p=head->next;

while(p)

(

printf("%dXA%d+n,p->xi,p->zi);

p=p->next;

)

printf("NULL\n\nH);

Node*Add(Node*headl,Node*head2)〃多項(xiàng)式相力口

{

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

intsum;

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

p=head;

pl=head1->next;

p2=head2->next;

while(p1&&p2)〃當(dāng)兩多項(xiàng)式都存在時(shí)

(

if(p1->zi==p2->zi)〃假如指數(shù)相等

(

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

if(sum)

{

pl->xi=sum;

p->next=pl;

P=P1；

)

pl=p1->next;

p2=p2->next;

else〃指數(shù)不相等分兩種情況

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

p->next=p1；

p=pl;

p1=p1->next;

)

else

(

p->next=p2;

P=P2；

p2=p2->next；

)

)

)

if(pl)p->next=p1；//將1中剩余結(jié)點(diǎn)接到和鏈表中由于最終只剩下一段鏈表多項(xiàng)式

eIsep->next=p2;〃將2中剩余結(jié)點(diǎn)接到和鏈表中這段鏈的鏈頭接到目的鏈表就可以了

returnhead;

)

intmain()

(

printf("請(qǐng)輸入第一個(gè)多項(xiàng)式\n”);

Node*head,*p1,*p2;

p1=Creat();

pri