d02-2011线性表习题课

线性表习题编程题1编写一算法，实现单链表的原地置逆。即利用原来的结点将线性表L=（a1,a2,……,an）变换为：L

=（

an, ……

,

a2,

a1）第2

页La1a2a3线性表习题编程题1succ

p标志后继结点（*succ）；修改指针（将*p

在头结点之后）；重置结点*p（p重新指向原表中后继）；第3

页线性表习题void inverse(

LinkList

&L

){ //

逆置

结点的单链表

Lp

=

L->next;

L->next

=

NULL;while

(

p

!=

NULL

){ succ=p->next;

//succ指向

*p

的后继在头结点之后p->next

=

L->next;L->next

=

p; //

*pp

=

succ;}}第4

页线性表习题第5

页编程题2将两个非递减有序的有序单链表la和lb归并为非递增的有序表。Typedef

struct LNode

{intstruct

Lnodedata;*next;//数据域//指针域}

LNode,

*LinkList;LinkList

la,

lb；//单链表的头指针请用la

和lb

中的结点合并生成一个新的非递增的有序单链表lc。合并完成后，原来的la

和lb

成为空链表。线性表习题操作步骤建空表Lc;依次从La

或Lb

中“”元素值较小的4)结点

到

Lc表中第一个结点之前直至其中一个表变空为止;3)

继续将La

或Lb

其中一个表的剩余结点插入在Lc

表的表头结点之后;La

表和Lb

表的表头结点。第6

页线性表习题void

union

(

LinkList&

Lc,

LinkList&

La,

LinkList&

Lb

){//将非递减的有序表La

和Lb归并为非递增的//有序表Lc,归并之后，La和Lb表不再存在。//

上述三个表均为

结点的单链表，Lc

表//中的结点即为原

La

或Lb

表中的结点。Lc

=

new

LNode;

Lc->next

=

NULL;pa=La->next; pb=Lb->next;

//初始化……

……

//归并dele

a;

dele

b;

//}//unionLa

和Lb的头结点第7

页线性表习题while

(

pa

!=

NULL

||

pb

!=

NULL

){

if (

pa

==NULL

){

q

=

pb; pb

=

pb->next;

}elseif (

pb

==NULL

){

q

=

pa; pa

=

pa->next;}else

if

(

pa->data

<=

pb->data

){

q

=

pa; pa

=

pa->next;}else{

q

=

pb; pb

=

pb->next;

}q->next

=

Lc->next;

//Lc->next

=

q;}第8

页线性表习题已知一带有表头结点的单链表，结点结构为如下：第9

页假设该链表只给出了头指针

list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，输出该结点的data的值，并返回1；否则，返回

0。datalink线性表习题问题关键如何尽可能高效？常规算法对链表进行第一遍扫描，计算出链表的长度

len，然后进行第二遍扫描，计数到len-k的位置即为需要查找的倒数第k

个元素。算法时间复杂度：O(n)。问题：是否有更高效的算法能否只进行一遍扫描即可完成？第10

页线性表习题算法的基本设计思想假设链表的最后一个结点为倒数第1

个结点。对链表进行扫描：用指针p

和q

分别指向两个结点，且保持指针p

和指针q

之间的“距离”（包含的结点数）为k，当p

指向最后一个结点时，q

指向的就是倒数第k

个结点。第11

页线性表习题算法的详细实现步骤假表头指针为list，两个指针变量p

和q：

距离计数器count

=0；p=q=list->link，指向链表第一个数据结点；若p

非空，则执行③和④；否则，转⑤；

如果count

小于k，则count

=count

+1；否则q

指向下一个结点；p

指向下一个结点，转步骤②；

若count

等于k，则查找成功，输出q

结点的data值，返回1；否则，返回0。结束。第12

页线性表习题第13

页int SearchRevk(

pLinkList

list, intk)intcount; /*

距离计数器*//*

p和q指向第一个数据结点*/{

pLinkList p,

q;p=q

=

list->link;count

=

0;while

(

p!=

NULL

){

if

(count<k)

count++; /*

计数器+1

*/elsep

=p->

link;q=q->link; /*

q指向下一结点*//*

p指向下一个结点*/}if

(count==k) /*查找成功

*/{

printf("%d\n",

q->data); return

1;}else

return

0; /*

查找失败*/}线性表习题求循环小数对于任意的真分数N/M

(0<N<M<500)，均可以求出对应的小数。如果采用链表表示各个小数，对于循环节采用循环链表表示。head11/8=

0.125形式2∧5.

.0.

6125

（循环节125）形式5261head第14

页线性表习题算法设计模拟手工计算过程。关键：记录计算过程中的余数和对应的商，一旦发现余数出现重复，则找到循环节。算法实现动态申请有M个元素的指针数组：以每次求得的余数作为下标，对应的数组元素保存该余数对应的商。第15

页线性表习题第16

页void

change(int

n,

int

m,

NODE

*

head

){ NODE

*

*

array; NODE

*

p=head; intk;array=(NODE

**)malloc(sizeof(NODE

*

)*

m);

for(k=0;k<m;k++)

//建立保存余数的数组array[k] =NULL;while

(n!=0)

//余数不为0，则继续循环{

if

(n*10%m==0)

//若能够整除，则处理，结束{

p->next=

(NODE

*)

malloc(

sizeof(NODE)

);p->next->data

=

n*10

/m;p->next->next

=

NULL;n=

0;}else

{

处理一般情况}}}线性表习题第17

页else{

if

(array[n]==NULL)

//若该余数第一次出现{

array[n]=p->next=(NODE

*)malloc(sizeof(NODE));

p->next->data=n

*

10/m;

//保存商n=n*

10%m;

//余数扩大10倍p

=

p->next;}else

//该余数不是第一次出现，则发现循环节{

p->next=array[n];

//建立环n

=0;}}线性表习题求循环节编写一个尽可能高效的查找循环节起始点的函数：NODE

*

find(

NODE

*

head)。函数的返回值为循环节的起点（即图中的指针p）。head11/8=

0.125形式2∧5.

.0.

6125

（循环节125）形式5261head第18

页线性表习题第19

页算法设计关键是要找出高效算法。判断是否有环。在确认有环的情况下，找到环的开始。线性表习题第20

页NODE

*

find(

NODE

*

head,

int

*

n

){ int

count=0,

ring; NODE

*

p,

*q;p

=

q=

head->next;while

(

p!=NULL&&

q!=NULL){ count

++;//p指针一次走一步p

=

p->next;q

=

q->next;if

(q!=NULL

)if

(p==q)//q指针一次走两步q=q->next;break;

//找到重合点则退出}if

(

q

==

NULL)//如果不存在环则返回{ *n

=0;return

NULL;}线性表习题第21

页ring

=

1;while

(q->next

!=p

)//求环长{ q

=

q->next; ring

++;}count

=

0; q

=

p

=

head->next;while(count<ring)

//求环的起始点{ count

++; p

=

p->next;}while

(p!=q){ p

=

p->next; q

=

q->next;}*n

=ring;returnp;}线性表习题将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R

中保有的序列循环左移p（0﹤p﹤n）个位置，即将R中的数据由：(x0,

x1,…,xp-1,xp,xp+1,…,xn-1)变换为：(xp,xp+1,……,xn-1,x0,x1,……,xp-1)第22

页线性表习题问题关键如何尽可能高效？常规算法一般的循环左移算法的时间复杂度肯定是比较大的。的法：采用一个变量作为辅助空间，每次移动一位，反复进行移动K次，则时间复杂度为O(

n*k)。另一种算法是采用p

位辅助空间，空间复杂度O(

p)，时间复杂度O(

n+p)。第23

页线性表习题第24

页基本设计思想先将前面p个元素置反，再将后边n-p元素置反，最后整体置反。参考程序void

leftShift(

int

r[

],

int

n,

int

p){ if

(

p>0

&&

p<n

){

rever(r,

0,

n-1);rever(r,

0,

n-p-1);rever(r,

n-p,

n-1);}}线性表习题void

rever(

int

a[

],

int

left,

int

right

){

int k=lift,

j=right,

temp;while

(

k

<

j

){ temp

=

r[k];r[k]

=

r[j];r[j]

=

temp;k++;j--;}}算法时间复杂度为O(n)，空间复杂度为O(1)。第25

页线性表习题第26

页本题曾经出现在《编程珠玑》中。基本思想从第n个元素开始移位，将它直接移到第n-p位，然后再对第n-p位操作，依次类推n-2p，n-3p.....；上述移位操作经过一定次数后，必定又重新对第n位操作，此时完成了一次循环；例如，当n=6，p=2时，先将第6位移到第4

位，第4

位移到第2位，第2位移到第

6

位，循环一次，此时一次循环未能将数组移位完毕。当n=6，p=5

时，6->1；1->2；

2->3；3->4；4->5；5->6；此时一次循环即将整个数组移位完毕。线性表习题基本思想当一次循环不能将整个数组完全移位时，可从第n-1位，再进行第（1）步的操作；如果还没移完，继续从第n-2位开始循环，依次类推。现在的关键之处是移动需要多少次循环。由数论性质可知：a.当n

和p的最大公约数（记为(n,p)）为1时，一次循环必定将整个数组移动完毕。b.

当

n

和

p

的最大公约数（记为

(

n,

p

)）大于

1时，则需要的循环次数就是

(n,p)！如

n=6，p=2，

(6,

2)

=2，第一次循环从第

6

位开始，第二次循环从第5

位开始，两次后完成！第27

页线性表习题定义：一个长度为L（L≥1）的升序序列S，处在第L/2

个位置的数称为S的中位数。

例如，若序列S1=(11,13,15,17,19)，则S1

的中位数是15。两个序列的中位数是含它们所有元素的升序

序列的中位数。例如，若S2=(2,4,6,8,20)，则S1

和S2

的中位数是11。现有两个等长升序序列A和B，设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A

和B

的中位数。第28

页线性表习题较小者即为所求的中位数。第29

页基本设计思想分别求两个升序序列A、B的中位数，设为a和b。求中位数的过程如下：若a=b，则a或b即为所求的中位数，结束；若a<b，则舍弃A中较小一半，同时舍弃B中较大一半，要求两次舍弃的元素个数相同。若a>b，则舍弃A中较大一半，同时舍弃B中较小一半，要求两次舍弃的元素个数相同。在保留的两个升序序列中，重复上述过程，直到两个序列中均只含1

个元素时为止，则线性表习题}第30

页基本设计思想int

M_Search

(intA[],

intB[],intn){ int

start1,

end1,

mid1,

start2,

end2,

mid2;start1=

0;end1=

n-1; start2

=

0;

end2=

n-1;while (

start1!=

end1

||start2

!=end2

){ mid1