第1章第2节练习题7 递减输出
最后更新于：2022-04-01 19:50:51
## 问题描述
> 给定一个带表头结点的单链表，试写出算法：按递减次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作为辅助空间）
## 算法思想
> 如果本题不限制使用数组的话，最快捷的方法便是将链表中的数据复制到数组中，然后使用时间复杂度为 O(nlog2(n))的排序算法进行排序，然后将数组元素输出即可。但是因为本题明确限定了不许使用辅助数组，那么本题完全可以借鉴[第1章第2节练习题3 删除最小值结点](http://blog.csdn.net/u013595419/article/details/50496681)的思想——查找剩余链表中的最大值结点，输出最大值结点，删除最大值结点；
特别应注意当最大值结点为最后一个结点时必须特殊对待，否则在删除最后一个结点时会出错。
## 算法描述
~~~
void DownPrint(LNode *head)
{
LNode *pre=head;
LNode *p=head->next;
LNode *premax=head;
LNode *max=head->next;
while(p){
if(max->datadata){
premax=pre;
max=p;
}
pre=p;
p=p->next;
}
//打印当前链表中的最大值结点
printf("%4d",max->data);
//释放当前链表中的最大值结点
if(max->next==NULL){
premax->next=NULL;
free(max);
}else{
premax->next=max->next;
free(max);
}
}
~~~
具体代码见附件。
## 附件
~~~
#include
#include
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
LinkList CreatList(LNode*);
void DownPrint(LNode*);
int main(int argc, char* argv[])
{
LNode *head;
head=(LNode*)malloc(sizeof(LNode));
head->next=NULL;
head=CreatList(head);
//循环查找剩余链表中最大值结点
while(head->next!=NULL){
DownPrint(head);
}
printf("\n");
return 0;
}
//头插法创建单链表
LinkList CreatList(LNode* head)
{
LNode *L;
ElemType x;
scanf("%d",&x);
while(x!=999){
L=(LNode*)malloc(sizeof(LNode));
L->data=x;
L->next=head->next;
head->next=L;
scanf("%d",&x);
}
return head;
}
//查找最大值结点，然后打印最大值结点，最后删除最大值结点
void DownPrint(LNode *head)
{
LNode *pre=head;
LNode *p=head->next;
LNode *premax=head;
LNode *max=head->next;
while(p){
if(max->datadata){
premax=pre;
max=p;
}
pre=p;
p=p->next;
}
printf("%4d",max->data);
if(max->next==NULL){
premax->next=NULL;
free(max);
}else{
premax->next=max->next;
free(max);
}
}
~~~
';