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

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn) 4學(xué)號：姓名： 得分： 一、實(shí)驗(yàn)?zāi)康?、復(fù)習(xí)線性表的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及基本操作；2、掌握順序表和（帶頭結(jié)點(diǎn)）單鏈表；3、了解有序表。二、實(shí)驗(yàn)內(nèi)容1、（必做題）假設(shè)有序表中數(shù)據(jù)元素類型是整型，請采用順序表或（帶頭結(jié)點(diǎn)）單鏈表實(shí)現(xiàn)：（1）OrderInsert（&L, e, int （*compare）（a, b）/根據(jù)有序判定函數(shù) compare,在有序表L的適當(dāng)位置插入元素e;（2）OrderInput（&L, int （*compare）（a, b）/根據(jù)有序判定函數(shù) compare，并利用有序插入函數(shù)Orderlnsert，構(gòu)造有序表 L；（3）Or

2、derMerge（&La, &Lb, &Lc, int （*compare）（）/根據(jù)有序判定函數(shù) compare，將兩個(gè)有序表 La和Lb歸并為一個(gè)有序表 Lc。2、（必做題）請實(shí)現(xiàn)：0，指數(shù)不（1）升冪多項(xiàng)式的構(gòu)造，升冪多項(xiàng)式是指多項(xiàng)式的各項(xiàng)按指數(shù)升序有序，約定系數(shù)不能等于 能小于 0；（2）兩個(gè)升冪多項(xiàng)式的相加。三、算法描述（采用自然語言描述）1.創(chuàng)建帶頭節(jié)點(diǎn)的鏈表，輸入兩個(gè)有序表數(shù)據(jù) La Lb歸并兩個(gè)有序表得有序表 Lc輸出三個(gè)有序表輸入需插入數(shù)據(jù) e將 e 插入有序表 Lc輸出插入 e 后的 Lc2.創(chuàng)建鏈表 按指數(shù)升序輸入多項(xiàng)式得序數(shù)和指數(shù) 輸出多項(xiàng)式按指

3、數(shù)升序輸入第二個(gè)多項(xiàng)式得序數(shù)和指數(shù)兩個(gè)多項(xiàng)式相加輸出第二個(gè)多項(xiàng)式和兩個(gè)多項(xiàng)式得和四、詳細(xì)設(shè)計(jì)（畫出程序流程圖）1.創(chuàng)建帶頭節(jié)點(diǎn)的鏈表歸并兩個(gè)有序表得有序表Lc輸出三個(gè)有序表輸入需插入數(shù)據(jù)e將e插入有序表Lc2.創(chuàng)建鏈表按指數(shù)升序輸入多項(xiàng)式得序數(shù)和指數(shù)兩個(gè)多項(xiàng)式相加結(jié)束五、程序代碼(給出必要注釋)1.#include<stdio.h> #include<malloc.h> typedef struct LNodeint date;struct LNode *next; LNode,*Link;typedef struct LinkListLink head;/ 頭結(jié)點(diǎn)in

4、t lenth;/ 鏈表中數(shù)據(jù)元素的個(gè)數(shù) LinkList;int compare (LinkList *L,int e)/ 有序判定函數(shù) compareint Lc=0;Link p;p=L->head;p=p->next;while(p!=NULL)if(e>p->date)p=p->next;Lc+;elsereturn Lc;return Lc;void Orderlnsert (LinkList *L,int e,int (*compare)()根據(jù)有序判定函數(shù)compare，在有序表 L 的適當(dāng)位置插入元素 e；Link temp,p,q;int Lc

5、,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;elsefor(i=0; i<Lc; i+)p=p->next;q=q->next;q->next=temp;temp->next=p;+L->lenth;void OrderMerge (

6、LinkList *La,LinkList *Lb,int (*compare)()/根據(jù)有序判定函數(shù) compare , 將兩個(gè)有序表La 和 Lb 歸并為一個(gè)有序表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->lenth)while(p->next!=NULL)p=p->next

7、;p->next=temp; temp->next=NULL;elsefor(i=0; i<Lc; i+)p=p->next; temp->next=p->next; p->next=temp;q=q->next;+Lb->lenth;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(L

8、Node); temp->date=0;temp->next=NULL;(NewList+i)->head=temp;(NewList+i)->lenth=0;return NewList;void Insert (LinkList *NewList)int a,i;char c;n");printf(" 在第 1 個(gè)表中插入數(shù)據(jù) ,輸入“ N ”再對下個(gè)表插入數(shù)據(jù) for(i=0; i<2; i+)while(1)scanf("%d",&a); c=getchar(); if(c='N')if(i&

9、lt;2-2)n",i+2);printf(" 在第 %d 個(gè)表中插入數(shù)據(jù) ,輸入 “ N ”再對下個(gè)表插入數(shù)據(jù) else if(i=2-2)printf(" 在第 %d 個(gè)表中插入數(shù)據(jù) ,輸入“ N ”結(jié)束。 n",i+2); break;else OrderInsert(NewList+i),a,compare);void Show (LinkList *L)/ 輸出有序表Link p;p=L->head->next; while(p!=NULL)printf("%d ",p->date); p=p->ne

10、xt;void visit(LinkList *NewList,void (*Show)()printf(" 有序表如下 :n");printf(" 第一個(gè)有序表為 :n");(*Show)(NewList+0);printf("n");printf(" 第二個(gè)有序表為 :n");(*Show)(NewList+1);printf("n");printf(" 歸并后有序表為 :n");(*Show)(NewList+2); printf("n");int

11、main()LinkList *NewList=NULL;LinkList *L;int i, e;printf(" 請按要求輸入數(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 請輸入將要插入的 e:n"); scanf("%d",&e);OrderInsert(NewLis

12、t+i),e,compare);printf("對歸并后有序表插入e后得n”)；Show(NewList+2);return 0；2. #include<stdio.h> #include<malloc.h>typedef struct nodeint xi；int zi；struct node *next； Node；Node *Creat()/ 用鏈表儲存多項(xiàng)式的序數(shù)與指數(shù)Node *head,*p,*q；int or,in；head=(Node *)malloc(sizeof(Node)； head->next=NULL； q=head；0 且指數(shù)

13、不能小于printf("請輸入多項(xiàng)式的序數(shù)與指數(shù)n (注意：按照指數(shù)升序輸入，系數(shù)不能等于0，序數(shù)與指數(shù)用空格隔開 ,并以 0 0 結(jié)束輸入) n")；scanf("%d %d",&or,&in)；while(or)p=(Node *)malloc(sizeof(Node)； p->xi=or；p->zi=in； p->next=q->next；q->next=p;q=p;scanf("%d %d",&or,&in);return head;void visit(Node

14、*head) / 輸出多項(xiàng)式Node *p=head->next;while(p)prin tf("%dXA%d+",p->xi,p->zi);p=p->next;printf("NULLnn");Node *Add(Node *head1,Node *head2)/ 多項(xiàng)式相加Node *p,*head,*p1,*p2;int sum;head=(Node *)malloc(sizeof(Node);p=head;p1=head1->next;p2=head2->next;while(p1&&p2)

15、/ 當(dāng)兩多項(xiàng)式都存在時(shí)if(p1->zi=p2->zi) / 如果指數(shù)相等sum=p1->xi+p2->xi;if(sum)p1->xi=sum;p->next=p1;p=p1;p1=p1->next;p2=p2->next;else /指數(shù)不相等分兩種情況if(p1->zi<p2->zi)p->next=p1;p=p1;p1=p1->next;elsep->next=p2;p=p2; p2=p2->next;if(p1) p->next=p1; / 將 1 中剩余結(jié)點(diǎn)接到和鏈表中因?yàn)樽罱K只剩下一段

16、鏈表多項(xiàng)式else p->next=p2; /將 2 中剩余結(jié)點(diǎn)接到和鏈表中 這段鏈的鏈頭接到目標(biāo)鏈表就可以了 return head;int main()printf(" 請輸入第一個(gè)多項(xiàng)式 n");Node *head,*p1,*p2;p1=Creat();printf(" 多項(xiàng)式為 :n");visit(p1);printf(" 請輸入第二個(gè)多項(xiàng)式 n");p2=Creat();printf(" 多項(xiàng)式為 :n");visit(p2);head=Add(p1,p2);printf("n 多項(xiàng)式相加后得： n");visit(head);return 0;六、測試和結(jié)果(給出測試用例，并給出測試結(jié)果)1.詰按要求轍入數(shù)據(jù)在第L個(gè)表中插入數(shù)據(jù).輸入“ X，T再對下個(gè)袁插入數(shù)掲8 4 7 6 N在第2個(gè)表屮価人數(shù)據(jù)，輸入“ X ”站束.1 7 5 2 8 N有序表如下：第一個(gè)有序表為：4 6 7 8第_個(gè)有序表為：12 5 7 8歸并后有序衣為：124567788請輸入將耍插入的E：3對歸井后有序表插入E后得1 2345677882.請輸人第一個(gè)多項(xiàng)式請輸入