资源预览内容
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
第9页 / 共10页
第10页 / 共10页
亲,该文档总共10页全部预览完了,如果喜欢就下载吧!
资源描述
DS线性表习题参考解答精品文档第2章 线 性 表 习题参考解答一、 简答题1试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。【答】头指针:是指向链表中的第一个结点的指针。头结点:在开始结点之前附加上的一个结点。开始结点:链表的第一个结点。 头指针是一个指向地址的变量,用于表示一个链表的开始。引入头结点可以更加方便的进行链表是否为空的判断,同时方便了插入和删除结点。开始结点用于存储链表的第一个数据元素。2何时选用顺序表、何时选用链表作为线性表的存储结构为宜?【答】顺序表中查找元素、获取表长非常容易,但是,要插入或者删除一个元素却需要移动大量的元素;相反,链表中却是方便插入或者删除元素,在查找元素的是,需要进行遍历。因此,当所涉及的问题常常进行查找等操作,而插入、删除相对较少的是,适合采用顺序表;当常常需要插入、删除的时候,适合采用链表。3为什么在单循环链表中设置尾指针比设置头指针更好?【答】在单循环链表中,设置尾指针,可以更方便的判断链表是否为空。4在单链表、双链表和单循环链表中,若仅知道指针p指向某结点,不知道头指针,能否将结点*p从相应的链表中删去?【答】本题分三种情况讨论:1、单链表:当知道指针p指向某结点时,能够根据该指针找到其直接后继,但是不知道头指针,因此不能找到该结点的直接前趋,因此,无法删除该结点。2、双链表:根据指针p可以找到该结点的直接前趋和直接后继,因此,能够删除该结点。3、单循环链表:和双链表类似,根据指针p也可以找到该结点的直接前趋和直接后继,因此,也可以删除该结点。5下述算法的功能是什么? LinkList Demo(LinkList *L) /* L是无头结点单链表*/ LNode *Q,*P; if(L&L-next) Q=L;L=L-next;P=L; while (P-next) P=P-next; P-next=Q; Q-next=NULL; return L; /* Demo */【答】将原来的第一个结点变成末尾结点,原来的第二个结点变成链表的第一个结点。二、算法设计题1试分别用顺序表和单链表作为存储结构,实现将线性表(a0,a1,.an-1)就地逆置的操作,所谓就地指辅助空间应为O(1)。【答】分两种情况讨论如下。 顺序表:要将该表逆置,可以将表中的开始结点与终端结点互换,第二个结点与倒数第二个结点互换,如此反复,就可将整个表逆置了。算法如下:void reverlist(sequenlist *L) datatype t; /* 设置临时空间用于存放data */int i;for (i=0;ilength/2;i+) t=L-datai; /* 交换数据 */L-datai=L-dataL-length-1-i;L-dataL-length-1-i=t; 链表:可以利用指针的指向转换来达到表逆置的目的。算法是这样的:LinkList *reverselist(LinkList *head)/* 将head 所指的单链表逆置 */ LNode *p,*q ; /* 设置两个临时指针变量 */ if(head-next!=NULL) & (head-next-next!=NULL) /* 当链表不是空表或单结点时 */ p=head-next; q=p-next; p-next=NULL; /*将开始结点变成终端结点 */ while (q) /* 每次循环将后一个结点变成开始结点 */ p=q; q=q-next; p-next= head- next; head-next=p; return head; return head; /* 如是空表或单结点表,直接返回head */2顺序表L是一个递增有序表,试写一算法,将x插入L中,并使L仍是一个有序表。【答】因已知顺序表L是递增有序表,所以只要从头找起找到第一个比它大(或相等)的结点数据,把x插入到这个数所在的位置就是了。算法如下:void InsertIncreaseList( Sequenlist *L , Datatype x ) int i; for (i=0; ilength & L-datainext ) p=p-next; /* 查找终端结点 */ p-next = q-next ; /* 将L2的开始结点链接在L1之后 */ return L1 ;本算法的主要操作时间花费在查找L1的终端结点上,与L2的长度无关,所以本算的法时间复杂度为:O(m)5A和B是两个单链表,其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C,并要求辅助空间为O(1),请分析算法的时间复杂度。【答】根据已知条件,A和B是两个递增有序表,所以我们可以以A表为基础,按照插入单个元素的办法把B表的元素插入A表中,完成后,将表逆置就得到了一个按元素值递减有序的单链表C了。算法如下:LinkList *MergeSort(LinkList *A , LinkList *B )/* 归并两个递增有序表为一个递减有序表 */LNode *pa , *pb , *qa , *qb ;pa=A;pb=B;qa=A-next;qb=B-next;while (qa &qb)if(qb-datadata ) /* 当B中的元素小于A中当前元素时,插入到它的前面 */ pb=qb; qb=qb-next ; /* 指向B中下一元素 */pa-next=pb;pb-next=qa;pa=pb;elseif ( qb-data=pa-data & qb-datadata)/* 当B中元素大于等于A中当前元素,且小于等于A中后一元素时,将此元素插入到A的当前元素之后 */pa=qa;qa=qa-next; /* 保存A的后一元素位置 */pb=qb;qb=qb-next; /* 保存B的后一元素位置 */ a-next=pb; /* 插入元素 */pb-next=qa;else /* 如果B中元素总是更大,指针移向下一个A元素 */pa=qa;qa=qa-next;if (qb )/* 如果A表已到终端而B表还有结点未插入 */ /* 将B表接到A表后面 */pa-next=qb; C= reverselist(A); /*调用前面所设计的逆置函数 */return C; /* 返回新的单链表C, 已是递减排列 */该算法的时间复杂度分析如下:算法中只有一个while循环,在这个循环中,按照最坏的情况是B元素既有插到A的最前的,也有插到最后的,也就是说需要把A中元素和B中元素全部检查比较过,这时的所费时间就是m+n. 而新链表的长度也是m+n+1 (有头结点),这样逆置函数的执行所费时间为m+n+1。所以可得整个算法的时间复杂度为:m+n+m+n+1=2(m+n)+1= O(m+n)6试编写一算法将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母字符、数字字符和其它字符),试编写算法构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。【答】本题分为两个部分,第一部分是删除重复结点,第二部分链表的分解。首先看第一部分:要删除重复结点,有两种方式,第一种方式:先取开始结点中的值,将它与其后的所有结点值一一比较,发现相同的就删除掉,然后再取第二结点的值,重复上述过程直到最后一个结点。第二种方式:将单链表按值的大小排序,排好后的结点按相同的删除。我们这里给出第一种方式的算法,如下所示:void sc(LinkList *head) LinkList *p,*q,*w;p=head-next; while(p!=NULL) q=p-next; w=p; while(q!=NULL) /*比较p所指节点的值与链表中后续节点的值,不相等q指针后移,相等则删除*/ if (p-data!=q-data)w=q;q=q-next; else w-next=q-next;w=q;q=q-next; p=p-next; 第二部分:本部分的思路和第一部分类似,首先构造三个新的链表,然后遍历原链表,检测每一个元素,如果是第一类元素,则把该结点从原链表中删除,但是不释放空间,而是添加到第一个新链表中;同样的,如果是第二类元素,则添加到第二个新链表中;以此类推,直到所有的节点都检测完毕。具体算法如下:void split(LinkList *ha) LinkList *hb,*hc,*ra,*rb,*rc,*p; char c; hb=(linklist*)malloc(sizeof(linklist); hc=(linklist*)malloc(sizeof(linklist); p=ha-next; ra=pa; ra-next=NULL; rb=hb; rb-next=NULL; rc=hc; rc-next=NULL; while(p!=ha) c=p-data; if (c=a& c=C & cnext=p;ra=p; else if(c=0 & cnext=p; rb=p;else rc-next=p; rc=p;p=p-next; ra-next=ha;rb-next=hb;rc-=next=hc; 7设在长度大于1的单循环链表中,既无头结点也无头指针。s为指向链表中某个结点的指针,试编写算法删除结点*s的直接前趋结点。【答】已知指向这个结点的指针是*s,那
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号