链表排序算法、再次详细讨论到底什么是算法以及到底什么是泛型【重点】

  1 #include<stdio.h>
  2 #include<malloc.h>
  3 #include<stdlib.h>
  4 
  5 //函数声明
  6 PNODE create_list();//返回值是链表头结点的地址
  7 void traverse_list(PNODE pHead);
  8 bool is_empty(PNODE pHead);
  9 int length_list(PNODE pHead);
 10 bool insert_list(PNODE,int,int);
 11 bool delete_list(PNODE,int,int *);
 12 void sort_list(PNODE pHead);
 13 
 14 
 15 typedef struct Node{
 16     int data;//数据域
 17     struct Node * pNext;//指针域    
 18 }NODE,*PNODE;//NODE等价于struct Node  PNODE等价于struct Node*
 19 
 20 int main(){
 21     PNODE pHead = NULL;//等价于struct Node * pHead = NULL;
 22     
 23     pHead = create_list();//创建一个非循环单链表，并将该链表的头结点的地址赋值给pHead
 24     traverse_list(pHead);//遍历 
 25     sort_list(pHead);//排序
 26     if(is_empty(pHead)){
 27         printf("链表为空");
 28     }
 29     else{
 30         printf("链表不空");
 31     }
 32      
 33      int len = length_list(pHead);
 34      printf("链表长度是%d",len)；
 35      
 36      
 37      
 38     return 0;
 39 }
 40 
 41 PNODE create_list(){
 42     int len;//有效节点的个数
 43     int i;
 44     int val;//临时存放用户输入的结点的值
 45     
 46     //分配一个不存放有效数据的头结点
 47     PNODE pHead = (PNODE)malloc(sizeof(NODE));
 48     if(pHead==NULL){
 49         printf("分配失败，程序终止");
 50         exit(-1);
 51     }
 52     
 53      PNODE pTail = pHead;
 54      pTail->PNext = NULL;//若只有一个结点，此时就为尾节点，指针域应当为空
 55     printf("链表节点个数：");
 56     scanf("%d",&len);
 57     
 58     for(i=0;i<len;i++){
 59         printf("请输入第%d个节点的值:",i+1);
 60         scanf("%d",&val);
 61         
 62         PNODE pNew = (PNODE)malloc(sizeof(NODE));//生成新结点
 63              if(pNew==NULL){
 64             printf("分配失败，程序终止");
 65             exit(-1);
 66         }
 67         pNew->data = val;//把数据存放进数据域
 68         pTail->pNext = pNew;//把新结点地址赋值给尾节点指针域
 69         pNew->pNext = NULL;//把新结点指针域赋值为空
 70         pTail = pNew;//最后一步把新结点地址复制给尾节点（就是让新结点成为尾节点）
 71        // pHead->pNext = pNew;
 72        // pNew->pNext=NULL;//最后一个结点的指针域为空
 73     }
 74     return pHead;
 75 }
 76 
 77 void traverse_list(PNODE pHead){
 78     PNODE p = pHead->pNext;//若链表为空，则头结点指针域就为空，则p就为空
 79     
 80     while(p!=NULL){
 81         printf("%d ",p->data);
 82         p=p->pNext;
 83     }
 84     printf("\n");
 85     return;
 86 }
 87 
 88 bool is_empty(PNODE pHead){
 89     if(pHead->pNext==NULL){//如果头结点的指针域为空，则链表为空
 90         return true;
 91     }
 92     else{
 93         return false;
 94     }
 95 }
 96 
 97 int length_list(PNODE pHead){
 98      PNODE p = pHead->pNext;
 99      int len = 0;
100      while(p!=NULL){
101          len++;
102          p=p->pNext;
103      }
104 }
105 
106 void sort_list(PNODE pHead){
107     int  i ,j , t;
108     int len = length_list(pHead);
109     PNODE p,q;
110     //重点!!!
111     for(i=0,p=pHead->pNext; i<len-1; i++,p=p->pNext){
112         for(j=j+1,q=p->pNext;j<len;j++,q=q->pNext){
113             if(p->data > q->data){ //类似于数组的：a[i]>a[j]
114                 t = p->data;          //t=a[i];
115                 p->data = q->data;    //a[i]=a[j];
116                 q->data = t;          //a[j]=t;  
117             }
118         }
119     }
120 
121 }