数据结构实验报告[4]

《数据结构实验报告[4]》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、云南大学〔据结构实验报告第四次实验学号：姓名:一、实验目的1.复习线性表的逻辑结构，存储结构及基本操作；2.掌握顺序表和(带头结点)单链表；3.了解有序表。二、实验内容1.(必做题)假设有序表屮数据元素类型是整型，请采用顺序表或(带头结点)单链表实现：(l)Orderlnsert(&L,e,int(^compare)())//根据有序判定函数compare,在有序表L的适当位置插入元素e;⑵利用Orderlnsert()构造有序表;(3)0rderMerge(&La,&Lb,&Lc,int(^compare)())//根据有序判定函数comp

2、are,将两个有序表La和Lb归并为一个有序表Lc。2.(选做题)请采用(带头结点)单链表实现：⑴升幂多项式的构造，即各个结点存储各项系数与指数，并且链表按指数升序有序；约定系数不能等于0,指数不能小于0)⑵两个升幂多项式的相加。三、算法描述(采用自然语言描述)1.(1)分别插入第一个链表和第二个链表的数据；⑵根据有序判定函数compare,将两个有序表U和Lb归并为一个有序表。(3)输出归并后的有序表。四、详细设计(画出程序流程图)五、程序代码(给出必要注释)1.#include#includetype

3、defstructLNode{intdate;structLNode*next;}LNode，*Link;//线性表的单链表存储结构typedefstructLinkList{Linkhead;//指向线性链表中的头结点intkn;//指示链表中数据元素的个数}LinkList;intcompare(LinkList*L,inte){intLc=0;Linkp;p=L->head;p=p->next;while(p!=NULL){if(e>p->date){p=p->next;Lc++;}elsereturnLc;}returnLc;}//有

4、序判定函数comparevoidOrderinsert(LinkList*L，inte,int(*compare)()){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->len){while(q->next!=NULL){q=q->next;}q->next=temp;temp->next=NULL;}else{for(i=0;i

5、next;q=q->next;}q->next=temp;temp->next=p;}++L->len;}//利用OrderlnsertO构造有序表；根据有序判定函数compare，在有序表L的适当位置插入元素e;voidOrderMerge(LinkList*La，LinkList*Lb,int(*conipare)()){inti，Lc=0;Linktemp，p，q;q=La->head->next;while(q!=NULL){p=Lb->head;temp=(Link)malloc(sizeof(LNode));temp->date=

6、q->date;Lc=(*compare)(Lb，q->date);if(Lc==Lb->len){while(p->next!=NULL){p=p->next;}p->next=temp;temp->next=NULL;}else{for(i=0;inext;}temp->next=p->next;p->next=temp;}q=q->next;++Lb->len;}}//根据有序判定函数compare,将两个有序表La和Lb归并为一个有序表LinkList^Initialize(LinkList*NevvLis

7、t){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)->len=O;}returnNewList;}voidInsert(LinkList*NewList){inta，i;charc;priiitf(”在第1个表中插入数据，以空格和回车

8、为间隔，输入对下个表插入数据”);for(i=0;i<2;i++){while(l){scanf(’,o/od"，&a);c=getchar();if(c==’