2023年數(shù)據(jù)結(jié)構(gòu)實驗報告10

數(shù)據(jù)結(jié)構(gòu)實驗報告一一實驗4學號：姓名：得分：一、實驗目的I、復習線性表的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及基本操作；2、掌握順序表和(帶頭結(jié)點)單鏈表；3、了解有序表。二、實驗內(nèi)容1、(必做題)假設有序表中數(shù)據(jù)元素類型是整型，請采用順序表或(帶頭結(jié)點)單鏈表實現(xiàn)：(1)OrderInsert(&L,e,int(*compare)(a,b))//根據(jù)有序鑒定函數(shù)compare,在有序表L的適當位置插入元素e；(2)0rdcrlnput(&L,int(*comparc)(a,b))〃根據(jù)有序鑒定函數(shù)compare,并運用有序插入函數(shù)0rderInserl,構(gòu)造有序表L；0rdcrMerge(&La,&Lb,&Lc,int(*compare)())〃根據(jù)有序鑒定函數(shù)compare,將兩個有序表La和Lb歸并為一個有序表Lc。2、(必做題)請實現(xiàn)：(1)開事多項式的構(gòu)造，升幕多項式是指多項式的各項按指數(shù)升序有序，約定系數(shù)不能等于0,指數(shù)不能小于0；(2)兩個升基多項式的相加。三、算法描述(采用自然語言描述)創(chuàng)建帶頭節(jié)點的鏈表，輸入兩個有序表數(shù)據(jù)LaLb歸并兩個有序表得有序表Lcvoidvisit(LinkList*NewList,void(*Show)())printf("有序表如下：5")；printf("第一個有序表為:\n");(*Show)(NewList+0);printf("\n")；printf("第二個有序表為：'n")；(*Show)(NewList+1);printf(H\n");printf("歸并后有序表為:\n");(*Show)(NewList+2);printf("'n")；)intmain(){LinkList*NewList=NULL;LinkList*L;inti,e；printf("請按規(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請輸入將要插入的e:\n");seanf("%d",&e);Oiderinsert((NewList+i),e,compare);Printf("對歸并后有序表插入e后得\n”)；Show(NewList+2);return0;)#include<stdio.h>#include<malloc.h>typedefstructnode(intxi；ntzi;structnode*next;}Node;Node*Crcat()〃用鏈表儲存多項式的序數(shù)與指數(shù){Node*head,*p,火q;inior,in;head=(Node*)mal1oc(sizeof(Node));head->next=NULL;q=head：printf(”請輸入多項式的序數(shù)與指數(shù)\n(注意：按照指數(shù)升序輸入,系數(shù)不能等于0且指數(shù)不能小于0,序數(shù)與指數(shù)用空格隔開，并以00結(jié)束輸入)5”)；seanf("%d%d'\&or,&in);while(or){p=(Node*)ma1loc(sizeof(Node))；p->xi=or;p->zi=in:p->next=q—>next;q->ncxt=p;q=P;scanf("%d%d",&or,&in);)returnhead;}voidvisit(Node*head)//輸出多項式(Node*p=head->next;while(p){printf("%dXA%d+",p->xi,p->zi);p=p->ncxt;printf("NULL\n\n");Node*Add(Node*head1.Node*head2)〃多項式相力口{Node*p,*head,*pl,*p2;intsum;head=(Node*)malloc(sizeof(Node));p=head;pl=head1->next;p2=head2->next;whilc(pl&&p2)〃當兩多項式都存在時(if(p1->zi==p2->zi)〃假如指數(shù)相等{sum=pl->xi+p2->xi;if(sum){pl->xi=sum;p->next=pl;P=pl；)pl=p1->next;p2=p2->next;)else〃指數(shù)不相等分兩種情況p->next=p1；P二Pl；pl=p1->next;}

else

(p->next=p2;P=P2；p2=p2->next：})}if(pl)p->next=p1；//將1中剩余結(jié)點接到和鏈表中由于最終只剩下一段鏈表多項式eIsep->next=p2;〃將2中剩余結(jié)點接到和鏈表中這段鏈的鏈頭接到目的鏈表就可以了returnhead;)intmain()(prinlf("請輸入第一個多項式\n");Nodc*head,*p1,*p2;p1=Creat();printf("多項式為：\n”)；Visit(p1);printf("請輸入第二個多項式\n”);p2=Crcat();printf("多項式為:\n");visit(p2);head=Add(pl,p2);printf("\n多項式相加后得:\n");visit(head)；return0;六、測試和結(jié)果（給出測試用例，并給出測試結(jié)果）1.請按要求輸入數(shù)據(jù)在第1個表中插入數(shù)據(jù)，輸入“N”再對下個表插入數(shù)據(jù)8476N在第2個表中插入數(shù)據(jù)，輸入“N”結(jié)束。17528N有序表如下：第一個有序表為：4678第二個有序表為：2578歸并后有序表為：124567788請輸入將要插入的e：3對歸并后有序表插入e后得請輸入第一個多項式請輸入多項式的序數(shù)與指數(shù)（注意：按照指數(shù)升序輸入，系數(shù)不能等于0且指數(shù)不能小于0,序數(shù)與指數(shù)用空格隔開，并以00結(jié)束輸入）25500多項式為：2X"2+5X"5+NULL請輸入第二個多項式請輸入多項式的序數(shù)與指數(shù)（注意：按照指數(shù)升序輸入，系數(shù)不能等于0且指數(shù)不能小于0,序數(shù)與指數(shù)用空格隔開，并以00結(jié)束輸入）33447500多項式為:3X"3+4X"4+7X"5+NULL多項式相加后得：2X-2+3X-3+4X-4+12X"5+NULL七、用戶手冊（告訴用戶如何使用程序，使用注意事項等）.按照規(guī)定輸入輸出三個有序表輸入需插入數(shù)據(jù)e將e插入有序表Lc輸出插入e后的Lc.創(chuàng)建鏈表按指數(shù)升序輸入多項式得序數(shù)和指數(shù)輸出多項式按指數(shù)升序輸入第二個多項式得序數(shù)和指數(shù)兩個多項式相加輸出第二個多項式和兩個多項式得和四、具體設計（畫出程序流程圖）32.五、程序代碼(給出必要注釋)#inc1ude<stdio.h>#inc1ude<mal1oc.h>typedefs(ructLNode(intdate;structLNode*nexl;}LNode,火Link；typedefstructLinkList(Linkhead;//頭結(jié)點int1enth;〃鏈表中數(shù)據(jù)元素的個數(shù)}LinkList;intcompare(LinkList*L,inte)〃有序鑒定函數(shù)compare(ntLc=0;Linkp;p=L->head;p=p—>next；whiic(p!=NULL)if(e>p->date)p=p->next;Lc++;)elsereturnLc;}reiurnLc;IvoidOrderlnsert(LinkList*L,inte,int(*compare)())//根據(jù)有序鑒定函數(shù)compare,在有序表L的適當位置插入元素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)(whi1c(q->ncxt!=NULL)q=q->ncxt；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->lcnth；)voidOrderMerge(LinkList*La,LinkList*Lb,inl(*compare)())//根據(jù)有序鑒定函數(shù)ompare,將兩個有序表La和Lb歸并為一個有序表{inti,Lc=0;Linktemp,p,q;q=La->head—>next;whi1c(q!=NULL)(p=Lb—>hcad;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；Ielse(for(i=0;i<Lc;i++)(p=p->next;)temp->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++){temp=(Link)mal1oc(sizeof(LNode))；temp->date=O；temp->next=NULL;(NewList+i)->head=temp;(NewList+i)—>1enth=O;)retumNewList;IvoidInsert(LinkList*NewList){inta,i;charc；printf("在第1個表中插入數(shù)據(jù)，輸入“N”再對下個表插入數(shù)據(jù)\n");for(i=0;i<2;i++)(whilc(1)(scanf("%d",&a);c=getchar();if(c=='N')if(i<2-2)prinlf("在第％d個表中插入數(shù)據(jù)，輸入"N"再對下個表插入數(shù)據(jù)