欢迎来到天天文库
浏览记录
ID:38507837
大小:137.50 KB
页数:30页
时间:2019-06-13
《习题二和上机答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、习题二⒉1描述以下四个概念的区别:头指针变量,头指针,头结点,首结点(第一个结点)。解:头指针变量和头指针是指向链表中第一个结点(头结点或首结点)的指针;在首结点之前附设一个结点称为头结点;首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点,则不管线性表是否为空,头指针均不为空,否则表示空表的链表的头指针为空。2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。解:顺序存储是按索引直接存储数据元素,方便灵活,效率高,但插入、删除操作将引起元素移动,降低了效率;而链式存储的元素存储采用动态分配,利用率高,但须增设表示结点之间有序关系的指针域,存取数据元素不如顺序
2、存储方便,但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素的情况;而链式存储适用于频繁进行元素动态插入或删除操作的场合。2.3在头结点为h的单链表中,把值为b的结点s插入到值为a的结点之前,若不存在a,就把结点s插入到表尾。Voidinsert(Lnode*h,inta,intb){Lnode*p,*q,*s;s=(Lnode*)malloc(sizeof(Lnode));s->data=b;p=h->next;while(p->data!=a&&p->next!=NULL){q=p;p=p->next;}if(p
3、->data==a){q->next=s;s->next=p;}else{p->next=s;s->next=NULL;}}2.4设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B,使A中含有原链表中序号为奇数的元素,而B中含有原链表中序号为偶数的元素,并且保持元素原有的相对顺序。Lnode*cf(Lnode*ha){Lnode*p,*q,*s,*hb;intt;p=ha->next;q=ha;t=0;hb=(Lnode*)malloc(sizeof(Lnode));s=hb;while(p->next!=NULL){if(t==0){q=p;p=p->next;t=1;}
4、else{q->next=p->next;p->next=s->next;s->next=p;s=p;p=p->next;t=0;}}s->next=NULL;return(hb);}2.5设线性表中的数据元素是按值非递减有序排列的,试以不同的存储结构,编写一算法,将x插入到线性表的适当位置上,以保持线性表的有序性。⑴顺序表;解:本题的算法思想是:先找到适当的位置,然后后移元素空出一个位置,再将x插入,并返回向量的新长度。实现本题功能的函数如下:intinsert(vectorA,intn,ElemTypex)/*向量A的长度为n*/{inti,j;if(x>=A[n-1])A[n]=x/*
5、若x大于最后的元素,则将其插入到最后*/else{i=0;while(x>=A[i])i++;/*查找插入位置i*/for(j=n-1;j>=i;j--)A[j+1]=A[j];/*移出插入x的位置*/A[i]=x;n++;/*将x插入,向量长度增1*/}returnn;}⑵单链表。解:本题算法的思想是先建立一个待插入的结点,然后依次与链表中的各结点的数据域比较大小,找到插入该结点的位置,最后插入该结点。实现本题功能的函数如下:node*insertorder(head,x)node*head;ElemTypex;{node*s,*p,*q;s=(node*)malloc(sizeof(no
6、de));/*建立一个待插入的结点*/s->data=x;s->next=NULL;if(head==NULL
7、
8、xdata)/*若单链表为空或x小于第一个结点的date域*/{s->next=head;/*则把s结点插入到表头后面*/head=s;}else{q=head;/*为s结点寻找插入位置,p指向待比较的结点,q指向p的前驱结点*/p=q->next;while(p!=NULL&&x>p->data)/*若x小于p所指结点的data域值*/if(x>p->data)/*则退出while循环*/{q=p;p=p->next;}s->next=p;/*将s结点插入到q和p
9、之间*/q->next=s;}return(head);}2.6假设有A和B分别表示两个递增有序排列的线性表集合(即同一表中元素值各不相同),求A和B的交集C,表C中也依值递增有序排列。试以不同的存储结构编写求得C的算法。⑴顺序表;voidSqList_Intersect_True(SqList&A,SqListB)//求元素递增排列的线性表A和B的元素的交集并存回A中{ i=1;j=1;k=0; whi
此文档下载收益归作者所有