单链表实现

  1 #include<stdio.h>
  2 #include<malloc.h>
  3 #include<stdlib.h>
  4 
  5 typedef struct Node
  6 {
  7     int data;  //数据域
  8     struct Node * pNext;  //指针域 
  9 }NODE, *PNODE;   //NODE等价于struct Node，PNODE等价于struct Node *  
 10 
 11 //函数声明 
 12 PNODE creat_list();
 13 void traverse_list(PNODE pHead);
 14 bool is_empty(PNODE pHead);
 15 int length_list(PNODE pHead);
 16 bool insert_list(PNODE pHead,int pos,int val); 
 17 bool delete_list(PNODE pHead,int,int*); 
 18 void sort_list(PNODE pHead);
 19 
 20 int main()
 21 {
 22     PNODE pHead = NULL;  //等价于struct Node * pHead = NULL；头结点 
 23     int val;
 24     
 25     pHead = creat_list();
 26     traverse_list(pHead);
 27     if( is_empty(pHead) )
 28         printf("链表为空\n");
 29     else
 30         printf("链表不空\n"); 
 31     int len = length_list(pHead);
 32     printf("链表长度是%d\n",len);
 33     
 34     if( insert_list(pHead,4,33) )
 35     {
 36         printf("第四个节点插入数据成功!\n"); 
 37     } 
 38     else
 39     {
 40         printf("插入失败!\n");
 41     }
 42     traverse_list(pHead);
 43     
 44     if( delete_list(pHead,4,&val) )
 45     {
 46         printf("删除成功，您删除的元素是:%d\n",val); 
 47     } 
 48     else
 49     {
 50         printf("删除失败！您删除的元素不存在!\n");
 51     }
 52     traverse_list(pHead);
 53     
 54     sort_list(pHead);
 55     printf("链表由小到大排序\n");
 56     traverse_list(pHead);
 57     
 58     return 0;
 59 } 
 60 
 61 PNODE creat_list()
 62 {
 63     int len;   //用来存放有效节点的个数 
 64     int val;   //用来临时存放用户输入节点的值
 65     
 66     PNODE pHead = (PNODE)malloc(sizeof(NODE));
 67     if(NULL == pHead)
 68     {
 69         printf("分配失败,程序终止"); 
 70         exit(-1);
 71     } 
 72     PNODE pTail = pHead;  
 73     pTail->pNext = NULL;
 74     
 75     printf("请输入您需要生成的链表节点的个数:len = ");
 76     scanf("%d",&len);
 77     
 78     for(int i=0;i<len;++i)
 79     {
 80         printf("请输入第%d个节点的值:",i+1);
 81         scanf("%d",&val);
 82         
 83         PNODE pNew = (PNODE)malloc(sizeof(NODE));
 84         if(NULL == pNew)
 85         {
 86             printf("分配失败,程序终止"); 
 87             exit(-1);
 88         } 
 89         pNew->data = val;   //尾插法 
 90         pTail->pNext = pNew;
 91         pNew->pNext = NULL;
 92         pTail = pNew;  //pTail在不断的移动，相当于指向要插入节点上一个节点指针 
 93     }
 94     return pHead; 
 95 }
 96 
 97 void traverse_list(PNODE pHead)
 98 {
 99     PNODE p = pHead->pNext;
100     while(NULL != p)
101     {
102         printf("%d ",p->data);
103         p = p->pNext;
104     }
105     printf("\n");
106     return;
107 } 
108 
109 bool is_empty(PNODE pHead)
110 {
111     if(NULL == pHead->pNext)
112         return true;
113     else
114         return false;
115 }
116 
117 int length_list(PNODE pHead)
118 {
119     PNODE p = pHead->pNext;
120     int len=0; 
121     while(NULL != p)
122     {
123         ++len;
124         p = p->pNext;
125     }
126     return len;
127 }
128 
129 void sort_list(PNODE pHead)   //选择排序算法 
130 {
131     PNODE p,q; 
132     int i,j,t;
133     int len = length_list(pHead);
134     
135     for(i=0,p=pHead->pNext;i<len-1;++i,p=p->pNext)
136     {
137         for(j=0,q=p->pNext;j<len;++j,q=q->pNext)
138         {
139             if(p->data > q->data)   //类似于数组中的:a[i]>a[j] 
140             {
141                 t = p->data;//类似于数组中的:t = a[i];
142                 p->data = q->data;//类似于数组中的:a[i] = a[j];
143                 q->data = t;//类似于数组中的:a[j] = t;
144             } 
145         }
146     }
147     return;
148 }
149 
150 bool insert_list(PNODE pHead,int pos,int val)
151 {
152     int i=0;
153     PNODE p = pHead;
154     
155     while(NULL!=p && i<pos-1)
156     {
157         p = p->pNext;
158         ++i;
159     }
160     if(i>pos-1 || NULL==p)
161         return false;
162         
163     PNODE pNew =(PNODE)malloc(sizeof(NODE));
164     if(NULL == pNew)
165     {
166         printf("动态分配内存是啊比!\n");
167         exit(-1);
168     }
169     pNew->data = val;
170     PNODE q = p->pNext;
171     p->pNext = pNew;
172     pNew->pNext = q;
173     return true;
174 }
175 
176 bool delete_list(PNODE pHead,int pos,int* pVal)
177 {
178     int i=0;
179     PNODE p = pHead;
180     
181     while(NULL!=p->pNext && i<pos-1)
182     {
183         p = p->pNext;
184         ++i;
185     }
186     if(i>pos-1 || NULL==p->pNext)
187         return false;
188         
189     PNODE q = p->pNext;   //将要删除的节点赋值给临时指针q 
190     *pVal = q->data;
191     
192     //删除p节点后面的节点
193     p->pNext = p->pNext->pNext;
194     free(q);
195     q = NULL; 
196     return true;    
197 }