数据结构 | 每日一练（62）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1. 请写一个算法将顺序存储结构的线性表（a 1 ...a n ）逆置为(a n ...a 1 )。

类似本题的另外叙述有：

(1) 设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成.

(2) 设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为 O（n）。（注：用程序实现）

(3) 试编写求倒排循环链表元素的算法。

(4) 请设计算法将不带头结点的单链表就地逆置。

(5) 试编写算法 ，将不设表头结点的、不循环的单向链表就地逆转。

(6) 有一个单链表 L（至少有 1 个结点），其头结点指针为 head，编写一个过程将 L 逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。

正确答案

ps：||代表注释

1．[题目分析] 顺序存储结构的线性表的逆置，只需一个变量辅助空间。算法核心是选择循环控制变量的初值和终值。

void SeqInvert（ElemType a[ ]， int n）∥a是具有n个元素用一维数组存储的线性表，本算法将其逆置。

{ for（i=0；i<=（n-1）/2；i++）

{t=a[i]；a[i]= a[n-1-i]；a[n-1-i]=t；}

}∥算法结束

[算法讨论] 算法中循环控制变量的初值和终值是关键。C中数组从下标0开始，第n个元素的下标是n-1。因为首尾对称交换，所以控制变量的终值是线性表长度的一半。当n为偶数，“一半”恰好是线性表长度的二分之一；若n是奇数，“一半”是小于n/2的最大整数，这时取大于1/2的最小整数的位置上的元素，恰是线性表中间位置的元素，不需要逆置。另外，由于pascal数组通常从下标1开始，所以，上下界处理上略有不同。这点请读者注意。

类似本题的其它题的解答：

这一组又选了6个题，都是单链表（包括单循环链表）的逆置。链表逆置的通常作法是：将工作指针指向第一个元素结点，将头结点的指针域置空。然后将链表各结点从第一结点开始直至最后一个结点，依次前插至头结点后，使最后插入的结点成为链表的第一结点，第一个插入的结点成为链表的最后结点。

（1）要求编程实现带头结点的单链表的逆置。首先建立一单链表，然后逆置。

typedef struct node

{ int data；∥假定结点数据域为整型。

struct node *next；

}node,*LinkedList；

LinkedList creat（ ）

{LinkedList head，p

int x；

head=（LinkedList）malloc（ sizeof（node））；

head->next=null； /*设置头结点*/

scanf（“%d”，&x）；

while（x!=9999） /*约定输入9999时退出本函数*/

{p=（LinkedList）malloc（ sizeof（node））；

p->data=x；

p->next=head->next；/* 将新结点链入链表*/

head->next=p；

scanf（“%d”，&x）；

}

return（head）；

}∥结束creat函数。

LinkedList invert1（LinkedList head）

/*逆置单链表*/

{LinkedList p=head->next; /*p为工作指针*/

head->next=null；

while（p!=null）

{r=p->next； /*暂存p的后继*/

p->next=head->next；

head->next=p；

p=r；

}

return（head）；

}/*结束invert1函数*/

main（）

{LinkedList la；

la=creat( ）； /*生成单链表*/

la=invert1（la）；/*逆置单链表*/

}

（2）本题要求将数据项递减有序的单链表重新排序，使数据项递增有序，要求算法复杂度为O（n）。虽没说要求将链表逆置，这只是叙述不同，本质上是将单链表逆置，现编写如下：

LinkedList invert2（LinkedList la）∥la是带头结点且数据项递减有序的单链表，本算法将其排列成数据项递增有序的单链表。

{p=la->next； /*p为工作指针*/

la->next=null；

while（p!=null）

{r=p->next； /*暂存p的后继。*/

p->next=la->next；/*将p结点前插入头结点后。*/

la->next=p；p=r；

}

}∥结束算法

（3）本题要求倒排循环链表，与上面倒排单链表处理不同之处有二：一是初始化成循环链表而不是空链表；二是判断链表尾不用空指针而用是否是链表头指针。算法中语句片段如下：

p=la->next； ∥p为工作指针。

la->next=la； ∥初始化成空循环链表。

while（p!=la） ∥当p=la时循环结束。

{r=p->next； ∥暂存p的后继结点

p->next=la->next；∥逆置

la->next=p； p=r；

}

（4）不带头结点的单链表逆置比较复杂，解决方法可以给加上头结点：

la=（LinkedList）malloc（ sizeof（node））；

la->next=L；

之后进行如上面（2）那样的逆置，最后再删去头结点：

L=la->next； ∥L是不带头结点的链表的指针。

free（la）； ∥释放头结点。

若不增加头结点，可用如下语句片段：

p=L->next； ∥p为工作指针。

L->next=null；∥第一结点成为尾结点。

while（p!=null）

{r=p->next；

p->next=L；∥将p结点插到L结点前面。

L=p； ∥L指向新的链表“第一”元素结点。

p=r；

}

（5）同（4），只是叙述有异。

（6）同（2），差别仅在于叙述不同。

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-