今天来聊聊数据结构 | 每日一练(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-

正文完