数据结构 | 每日一练（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-