1 /*
  2  * LinkNode.c
  3  *
  4  *  Created on: Jan 14, 2014
  5  *      Author: root
  6  */
  7 #include <stdlib.h>
  8 #include <stdio.h>
  9 #include <malloc.h>
 10 typedef struct node
 11 {
 12     int num;
 13     struct node *next;
 14 }Node,*pNode;
 15 
 16 pNode create();
 17 void printList(pNode pHead);
 18 int InsertNode(pNode pHead,int front,int data);
 19 int DeleteNode(pNode pHead,int pos);
 20 int LengthList(pNode pHead);
 21 void Sort_List(pNode pHead);
 22 int main()
 23 {
 24 
 25     pNode pHead = NULL;
 26     int data;
 27     int front;
 28     int choose;
 29     int return_val;
 30     pHead=create();
 31     printf("你输入的数据是,\n");
 32     int length;
 33     length = LengthList(pHead);
 34     printf("(长度为%d的单链表):\n",length);
 35     printList(pHead);
 36     while(1)
 37     {
 38     printf("是否还要进行如下操作：\n");
 39     printf("1.插入数据      2.删除数据     3.修改数据     4.链表排序     5.退出\n");
 40     scanf("%d",&choose);
 41 
 42     switch(choose)
 43     {
 44         case 1:
 45         {
 46             printf("请输入要在第几个节点前插入数据：");
 47             scanf("%d",&front);
 48             if(front>length)
 49             {
 50                 front = length;
 51                 printf("Warning:输入结点位置大于链表长度，默认在表尾部添加!\n");
 52             }
 53             printf("请输入要插入的数据：");
 54             scanf("%d",&data);
 55             if(InsertNode(pHead,front,data)==1)
 56             {
 57                  printf("插入成功\n插入后的数据是：\n");
 58                  printList(pHead);
 59             }else
 60             {
 61                  printf("插入失败\n");
 62             }
 63                 break;
 64         }
 65         case 2:
 66         {
 67             printf("请输入要删除第几个节点的数据：");
 68             scanf("%d",&front);
 69             if(front>length)
 70             {
 71                 front=length;
 72                 printf("Warning:输入结点位置大于链表长度，默认删除表最后一个结点!\n");
 73             }
 74             return_val = DeleteNode(pHead,front);
 75             if(return_val==0)
 76             {
 77                   printf("删除失败。\n");
 78             }else
 79             {
 80                  printf("删除成功。删除的元素是：%d\n",return_val);
 81             }
 82                  printf("操作完成后的数据是：");
 83                  printList(pHead);
 84                  break;
 85         }
 86         case 3:
 87         {
 88             printf("暂时没有做这个功能!\n");
 89             break;
 90         }
 91         case 4:
 92         {
 93             Sort_List(pHead);
 94             break;
 95         }
 96         case 5:
 97         {
 98             exit(1);
 99         }
100         return 0;
101     }
102 
103     }
104 
105     return 0;
106 }
107 
108 pNode create()
109 {
110     int i;
111     int len;
112     int val;
113     pNode pHead = (pNode)malloc(sizeof(struct node));
114     pNode pTail = pHead;
115     pTail->next = NULL;
116     printf("请输入节点个数：");
117     scanf("%d",&len);
118     for(i=0;i<len;i++)
119     {
120         printf("第 %d 个节点的数值：",i+1);
121         scanf("%d",&val);
122         pNode pNew = (pNode)malloc(sizeof(Node));
123         pNew->num = val;
124         /*
125          *  有序的
126          *  1.将尾节点的next指针指向新节点
127          *  2.然后把新节点next指针设置为空
128          *  3. 最后将新节点作为尾节点
129          */
130         pTail->next=pNew;
131         pNew->next=NULL;
132         pTail = pNew;
133     }
134     return pHead;
135 }
136 
137 void printList(pNode pHead)
138 {
139     pNode p = pHead->next;
140     while(p!=NULL)
141     {
142         printf("%d\n",p->num);
143         p=p->next;
144     }
145     printf("\n");
146 }
147 int InsertNode(pNode pHead,int front,int data)
148 {
149     int i = 0;
150     pNode _node = pHead;
151     pNode pSwap ;
152 
153     if((front<1) || (_node==NULL))
154     {
155         printf("error:List is NULL or front<1");
156         return -1;
157         exit(0);
158     }
159     while(i<front-1)
160     {
161         _node = _node->next;
162         ++i;
163     }
164     pNode pNew = (pNode)malloc(sizeof(Node));
165 
166     pNew->num=data;
167     pSwap = _node->next;
168     _node->next = pNew;
169     pNew->next = pSwap;
170 
171     return 1;
172 }
173 
174 int DeleteNode(pNode pHead,int pos)
175 {
176     int i=0;
177     int data;
178     pNode _node =pHead;
179     pNode pSwap ;
180     if((pos < 1) && (NULL == _node->next))
181         {
182             printf("failed to delete ! \n");
183             return 0;
184         }
185     while(i < pos-1)
186     {
187         _node = _node->next;
188         ++i;
189     }
190     pSwap = _node->next;
191     data = pSwap->num;
192     _node->next = _node->next->next;
193     free(pSwap);
194     return data;
195 }
196 
197 int LengthList(pNode pHead)
198 {
199     int length = 0;
200     pNode temp = pHead->next;
201     while(temp!=NULL)
202     {
203         temp=temp->next;
204         length++;
205     }
206     return length;
207 }
208 
209 void Sort_List(pNode pHead)
210 {
211     int i , j;
212     int swap ;
213     int len=LengthList(pHead);
214     pNode m,n;
215     for(i=0,m=pHead->next;i<len-1;i++,m=m->next)
216     {
217         for(j=i+1,n=m->next;j<len;j++,n=n->next)
218         {
219             if(m->num > n->num)
220             {
221                 swap = m->num;
222                 m->num = n->num;
223                 n->num = swap;
224             }
225         }
226     }
227     printf("排序完后结果为：\n");
228     printList(pHead);
229 }