链表的经典算例（包含创建、遍历、删除、排序等）

  1 #include<stdio.h>
  2 #include<malloc.h>
  3 #include<stdlib.h>
  4 
  5 typedef struct node
  6 {
  7     int date;
  8     struct node *pNext;
  9 } NODE,*PNODE;
 10 PNODE create_list();//创建链表 
 11 void traverse_list(PNODE pHead);//遍历链表 
 12 bool is_empty(PNODE pHead);//判断链表是否为空 
 13 bool delete_list(PNODE,int,int*);//删除链表中需要删除的节点，并返回节点中的值 
 14 int length_list(PNODE);//求链表长度 
 15 void sort_list(PNODE);//对链表排序 
 16 bool insert_list(PNODE,int,int);//插入节点 
 17 int main()
 18 {
 19     int cnt,val;
 20     PNODE pHead=create_list();//定义头结点指针，并赋值 
 21     traverse_list(pHead);
 22     /*if(insert_list(pHead,1,66))
 23         traverse_list(pHead);*/
 24     if(delete_list(pHead,3,&val))
 25     {
 26         printf("成功删除元素%d\n",val);    
 27         traverse_list(pHead);    
 28     }
 29     /*cnt=length_list(pHead);
 30     printf("节点数=%d\n",cnt);
 31     sort_list(pHead);
 32     traverse_list(pHead);*/
 33     return 0;
 34 }
 35 PNODE create_list()
 36 {
 37     int len;//链表成员数 
 38     int val;//链表成员值 
 39     PNODE pHead=(PNODE)malloc(sizeof(NODE));
 40     if(NULL==pHead)
 41         {
 42             printf("头结点分配有误\n");
 43             exit(-1);
 44         }
 45     PNODE pTail=pHead;
 46     pTail->pNext=NULL;   // 此步必须有 
 47     printf("请输入有效节点数：");
 48     scanf("%d",&len) ;
 49     /*if(len<1)
 50         {
 51             printf("无节点\n");
 52             exit(-1);
 53     }*/
 54     for(int i=0;i<len;i++)
 55     {    
 56         printf("请输入第%d个有效节点的值：",i+1);
 57         scanf("%d",&val) ;
 58         PNODE pNew=(PNODE)malloc(sizeof(NODE));
 59         if(NULL==pNew)
 60         {
 61             printf("结点分配有误\n");
 62             exit(-1);
 63         }
 64         pNew->date=val;
 65         pTail->pNext=pNew;
 66         pNew->pNext=NULL;
 67         pTail=pNew;
 68     }
 69     return pHead;
 70 }
 71 void traverse_list(PNODE pHead)
 72 {
 73     PNODE p=pHead->pNext;
 74     while(p!=NULL)
 75     {
 76         printf("%d\t",p->date);
 77         p=p->pNext;
 78     }
 79     printf("\n");
 80     return;
 81 }
 82 int length_list(PNODE pHead)
 83 {
 84     int cnt=0;
 85     PNODE p=pHead->pNext;
 86     while(NULL!=p)
 87     {
 88         cnt++;
 89         p=p->pNext;
 90     }
 91     return cnt;
 92 }
 93 void sort_list(PNODE pHead)
 94 {
 95     int i,j,t;
 96     PNODE p,q;
 97     int len=length_list( pHead);
 98     p=pHead->pNext;
 99     for(i=0,p=pHead->pNext;i<len-1;++i,p=p->pNext)
100     {
101         for(j=i+1,q=p->pNext;j<len;++j,q=q->pNext) 
102         {
103             if(p->date>q->date)
104             {
105                 t=p->date;
106                 p->date=q->date;
107                 q->date=t; 
108             } 
109         }
110     }
111     return;
112 } 
113 bool insert_list(PNODE pHead,int pos,int val)
114 {
115     int i=0;
116     PNODE p=pHead;
117     while(i<pos-1&&NULL!=p) //循环到p指向pos-1的位置，即插入节点的前一个节点地址 
118     {
119         p=p->pNext;
120         i++; 
121     }
122     if(i>pos-1||NULL==p)
123         return false;    
124     PNODE pNew=(PNODE)malloc(sizeof(NODE));
125     if(NULL==pNew)
126     {
127         printf("动态分配有误！\n") ;
128         exit(-1);
129     }
130     pNew->date=val;
131     PNODE q=p->pNext;
132     p->pNext=pNew;
133     pNew->pNext=q;
134     return true;
135 }
136 bool delete_list(PNODE  pHead,int pos,int* pVal)
137 {
138     int i=0;
139     PNODE p=pHead;
140     PNODE q;
141     while(i<pos&&NULL!=p->pNext) //循环到p指向pos的位置，即所要删除的节点 
142     {
143         q=p;//循环结束时为所需要删除节点的前一个节点地址 
144         p=p->pNext;
145         i++; 
146     }
147     if(i>pos||NULL==p->pNext)
148     {
149         printf("删除失败\n");
150         return false;
151     }
152     q->pNext=p->pNext;
153     *pVal=p->date;
154     free(p);//释放所删节点内存 
155     return true;
156 }