## 問題描述 > 給定一個帶表頭結點的單鏈表，試寫出算法：按遞減次序輸出單鏈表中各結點的數據元素，并釋放結點所占的存儲空間（要求：不允許使用數組作為輔助空間） ## 算法思想 > 如果本題不限制使用數組的話，最快捷的方法便是將鏈表中的數據復制到數組中，然后使用時間復雜度為 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); } } ~~~