## 问题描述 > 给定一个带表头结点的单链表，试写出算法：按递减次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作为辅助空间） ## 算法思想 > 如果本题不限制使用数组的话，最快捷的方法便是将链表中的数据复制到数组中，然后使用时间复杂度为 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->data<p->data){ 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<stdio.h> #include<stdlib.h> 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->data<p->data){ 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); } } ~~~