十年老IT知识分享 – 数据结构 | 每日一练(74)

数据结构

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

——老子

1

每日一练

1.给定(已生成)一个带表头结点的单链表,设 head 为头指针,结点的结构为(data,next),data 为整型元素,next 为指针,试写出算法:按递增次序输出单链表中各结点的数据元素,并释放结点所占的存储空间。(要求;不允许使用数组作辅助空间)。

正确答案

PS:||代表注释

1.[题目分析] 题目要求按递增次序输出单链表中各结点的数据元素,并释放结点所占存储空间。应对链表进行遍历,在每趟遍历中查找出整个链表的最小值元素,输出并释放结点所占空间;再查次最小值元素,输出并释放空间,如此下去,直至链表为空,最后释放头结点所占存储空间。当然,删除结点一定要记住该结点的前驱结点的指针。

void MiniDelete(LinkedList head)∥head是带头结点的单链表的头指针,本算法按递增顺序输出单链表中各结点的数据元素,并释放结点所占的

存储空间。

{ while(head->next!=null) ∥循环到仅剩头结点。

{pre=head; ∥pre为元素最小值结点的前驱结点的指针。

p=pre->next; ∥p为工作指针

while(p->next!=null)

{ if(p->next->data<pre->next->data)pre=p;∥记住当前最小值结点的前驱

p=p->next;

}

printf(pre->next->data);∥输出元素最小值结点的数据。

u=pre->next;pre->next=u->next; free(u);∥删除元素值最小的结点,释放结点空间

}∥ while(head->next!=null)

free(head);} ∥释放头结点。

[算法讨论] 算法中使用的指针变量只有pre,p和u三个,请读者细心体会。要注意没特别记最小值结点,而是记其前驱。

正文完