（C）单链表

老师版

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 // 定于Node数据类型
  5 struct Node
  6 {
  7     int data;                     // 数据域
  8     struct Node *next;            // 指针域
  9 };
 10 
 11 // 创建一个单链表，并把head节点返回；
 12 struct Node* createLinkList(void);
 13 struct Node* createLinkList(void)
 14 {
 15     struct Node *head = NULL;
 16     struct Node *tail = NULL;
 17     struct Node *temp = NULL;
 18     
 19     int data;
 20     
 21     scanf("%d",&data);
 22     // data 不等于0
 23     while (data)
 24     {
 25         // malloc 函数申请内存
 26         temp = (struct Node *)malloc(sizeof(struct Node));
 27         temp->data = data;
 28         temp->next = NULL;
 29         
 30         if (head == NULL)
 31         {
 32             head = temp;
 33             tail = temp;
 34         }
 35         else
 36         {
 37             tail->next = temp;
 38             tail = temp;
 39         }
 40         
 41         scanf("%d",&data);
 42     }
 43     
 44     
 45     return  head;
 46 }
 47 
 48 // 输出链表元素
 49 void printLinkList(struct Node *head);
 50 void printLinkList(struct Node *head)
 51 {
 52     struct Node *p = head;
 53     if (p == NULL)
 54     {
 55         return;
 56     }
 57     else
 58     {
 59         while (p)
 60         {
 61             printf("%d-》",p->data);
 62             // 指针重定向
 63             p = p->next;
 64         }
 65     }
 66 }
 67 
 68 //  计算链表的长度
 69 int count(struct Node *head);
 70 int count(struct Node *head)
 71 {
 72     int count = 0;
 73     struct Node *p = NULL;
 74     p = head;
 75     while (p)
 76     {
 77         count++;
 78         p = p->next;
 79     }
 80     
 81     return count;
 82 }
 83 
 84 
 85 int getNode(struct Node *head,int pos);
 86 int getNode(struct Node *head,int pos)
 87 {
 88     if (pos > count(head))
 89     {
 90         return 0;
 91     }
 92     
 93     struct Node *p = head;
 94     for (int i = 1; i < pos; i++)
 95     {
 96         p = p->next;
 97     }
 98     
 99     return p->data;
100 }
101 
102 void insertIntoHead(struct Node **h,int value);
103 void insertIntoHead(struct Node **h,int value)
104 {
105     struct Node *temp = NULL;
106     temp = (struct Node *)malloc(sizeof(struct Node));
107     temp->data = value;
108     temp->next = NULL;
109     
110     if (h == NULL)
111     {
112         *h = temp;
113     }
114     else
115     {
116         temp->next = *h;
117         *h = temp;
118     }
119 }
120 
121 
122 //2、把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０
123 int modifyNode(struct Node *head,int pos,int x);
124 int modifyNode(struct Node *head,int pos,int x)
125 {
126     // 如果链表为空，或者pos 超出链表长度
127     if (head == NULL || pos > count(head))
128     {
129         return 0;
130     }
131     
132     struct Node *p = NULL;
133     p = head;
134     for (int i = 1; i < pos; i++)
135     {
136         p = p->next;
137     }
138     
139     p->data = x;
140     return 1;
141 }
142 
143 void insertIntoTail(struct Node **head,int value);
144 void insertIntoTail(struct Node **head,int value)
145 {
146     struct Node *tmp = NULL;
147     tmp = malloc(sizeof(struct Node));
148     tmp->data = value;
149     tmp->next = NULL;
150     if (*head == NULL)
151     {
152         *head = tmp;
153     }
154     else
155     {
156         struct Node *p;
157         // 定位最后一个节点
158         p = *head;
159         while (p->next)
160         {
161             p = p->next;
162         }
163         // 将申请的tmp加到链表后面
164         p->next = tmp;
165     }
166 }
167 
168 int insertInto(struct Node **head,int pos,int value);
169 int insertInto(struct Node **head,int pos,int value)
170 {
171     if (*head == NULL)
172     {
173         // 在第一个位置添加一个节点
174         insertIntoHead(head, value);
175         return 1;
176     }
177     if (pos > count(*head))
178     {
179         // 在最后一个位置添加一个节点
180         insertIntoTail(head, value);
181         return 1;
182     }
183     // 申请一个节点
184     struct Node *tmp;
185     tmp = malloc(sizeof(struct Node));
186     tmp->data = value;
187     tmp->next = NULL;
188     if (tmp==NULL)//tmp 申请内存失败
189     {
190         return 0;
191     }
192     else
193     {
194         // 声明一个辅助指针
195         struct Node *p;
196         p = *head;
197         // 定位辅助指针，指向pos位置前一个节点
198         for (int i = 1; i<pos-1; i++)
199         {
200             p = p->next;
201         }
202         tmp->next = p->next;
203         p->next = tmp;
204         return 1;
205     }
206 }
207 
208 
209 void insertIntoSortedList(struct Node **head,int value);
210 void insertIntoSortedList(struct Node **head,int value)
211 {
212     // 如果是链表为空，在第一个位置添加
213     if (*head == NULL)
214     {
215         insertIntoHead(head, value);
216         return;
217     }
218     
219     // 记录要添加元素的位置
220     int pos = 1;
221     struct Node *p = NULL;
222     p = *head;
223     while (p)
224     {
225         if (p->data < value)
226         {
227             pos++;
228             p = p->next;
229         }
230         else
231         {
232             // 跳出循环
233             break;
234         }
235     }
236     
237     insertInto(head, pos, value);
238 }
239 
240 int deleteFirstNode(struct Node **head);
241 int deleteFirstNode(struct Node **head)
242 {
243     if (*head == NULL)
244     {
245         return 0;
246     }
247     
248     struct Node *p = NULL;
249     p = *head;
250     
251     *head = p->next;
252     int result = p->data;
253     
254     // 注意释放内存
255     free(p);
256     p = NULL;
257     
258     return result;
259     
260     
261 }
262 
263 int deleteTailNode(struct Node **head);
264 int deleteTailNode(struct Node **head)
265 {
266     if (*head == NULL)
267     {
268         return 0;
269     }
270     
271     struct Node *p,*q;
272     p = q = NULL;
273     p = *head;
274     q = p->next;
275     // 通过循环定位让q指向最后一个节点，p指向q前面一个节点
276     for (int i = 1; i <= count(*head)-2; i++)
277     {
278         p = q;
279         q = q->next;
280     }
281     // 取最后一个节点的数据
282     int result = q->data;
283     
284     p->next = NULL;
285     free(q);
286     q = NULL;
287     
288     return result;
289 }
290 
291 
292 int main(int argc, const char * argv[])
293 {
294 
295     struct Node *head = NULL;
296     // 产生链表
297     head = createLinkList();
298     
299     // 输出链表元素个数
300     int c = count(head);
301     printf("c = %d
",c);
302     
303     
304     //insertIntoHead(&head, 10);
305     
306     //modifyNode(head, 2, 10);
307     
308     //insertIntoTail(&head, 100);
309     //insertInto(&head, 2, 100);
310     
311     //insertIntoSortedList(&head, 6);
312     //deleteFirstNode(&head);
313     int r = deleteTailNode(&head);
314     printf("删除最后一个节点%d
",r);
315     
316     // 输出链表
317     printLinkList(head);
318     
319     
320     /*
321     // 输出第二个节点的数据域；
322     c = getNode(head, 2);
323     printf("
");
324     printf("c = %d
",c);
325     */
326     
327     return 0;
328 }

不才版

  1 #include <stdio.h>
  2 
  3 #include <stdlib.h>
  4 
  5 struct Node
  6 {
  7     int data;
  8     struct Node *next;
  9 };
 10 
 11 struct Node *creatLinkList(void)
 12 {
 13     struct Node *head=NULL;
 14     struct Node *tail=NULL;
 15     struct Node *temp=NULL;
 16     
 17     int data;
 18     scanf("%d",&data);
 19     while (data)
 20     {
 21         temp=malloc(sizeof(struct Node));
 22         temp->data=data;
 23         temp->next=NULL;
 24         
 25         if(head==NULL)
 26             head=tail=temp;
 27         else
 28         {
 29             tail->next=temp;
 30             tail=temp;
 31         }
 32         scanf("%d",&data);
 33     }
 34     return head;
 35 }
 36 
 37 void printLinkList(struct Node *head)
 38 {
 39     struct Node *tmp=head;
 40     if (tmp==NULL) {
 41         return;
 42     }
 43     while (tmp!=NULL) {
 44         printf("%d->>",tmp->data);
 45         tmp=tmp->next;
 46     }
 47     printf("
");
 48 }
 49 
 50 int toNode(struct Node *head,int pos)
 51 {
 52     int data;
 53     for (int i=0; i<pos; i++) {
 54         if ((i!=pos-1)&&(head->next==NULL))
 55             return 0;
 56         data=head->data;
 57         head=head->next;
 58     }
 59     return data;
 60     
 61     //链表长度可以用count(head)算出。
 62 }
 63 
 64 int changeData(struct Node *head,int pos,int x)
 65 {
 66     for (int i=0; i<pos; i++) {
 67         if ((i!=pos-1)&&(head->next==NULL))
 68             return 0;
 69         if (i==pos-1) {
 70             head->data=x;
 71         }
 72         head=head->next;
 73     }
 74     return 1;
 75 }
 76 
 77 void insertNodeInHead(struct Node **head,int value)
 78 {
 79     struct Node *tmp=NULL;
 80     tmp=(struct Node *)malloc(sizeof(struct Node));
 81     tmp->data=value;
 82     tmp->next=*head;
 83     *head=tmp;
 84 }
 85 
 86 void insertNodeInEnd(struct Node *head,int value)
 87 {
 88     struct Node *tmp=NULL;
 89     tmp=(struct Node *)malloc(sizeof(struct Node));
 90     tmp->data=value;
 91     tmp->next=NULL;
 92     if (head==NULL) {
 93         head=tmp;
 94     }
 95     while (head->next!=NULL) {
 96         head=head->next;
 97     }
 98     head->next=tmp;
 99 }
100 
101 int insertData(struct Node *head,int pos,int value)
102 {
103     struct Node *tmp=NULL;
104     tmp=(struct Node *)malloc(sizeof(struct Node));
105     if (tmp==NULL) {
106         return 0;
107     }
108     tmp->data=value;
109     if (pos==0) {
110         return 0;
111     }
112     for (int i=0; i<pos; i++) {
113         
114         if ((i!=pos-1)&&(head->next==NULL)) {
115             return 0;
116         }
117         if (i==pos-1) {
118             tmp->next=head->next;
119             head->next=tmp;
120         }
121         head=head->next;
122     }
123     return 1;
124 }
125 
126 void insertSortData(struct Node *head,int value)
127 {
128     struct Node *tmp=(struct Node *)malloc(sizeof(struct Node));
129     tmp->data=value;
130     while (head->data<tmp->data) {
131         if (head->next->data>=tmp->data) {
132             tmp->next=head->next;
133             head->next=tmp;
134             return;
135         }
136         if (head->next==NULL) {
137             tmp->next=head->next;
138             head->next=tmp;
139             return;
140         }
141         head=head->next;
142     }
143     
144 }
145 
146 int deleteHead(struct Node **pointhead)
147 {
148     int data;
149     data=(*pointhead)->data;
150     struct Node *p=*pointhead;
151     *pointhead=(*pointhead)->next;
152     free(p);
153     p=NULL;
154     if (*pointhead==NULL||(*pointhead)->next==NULL) {
155         return 0;
156     }
157     return data;
158 }
159     
160 int deleteEnd(struct Node *head)
161 {
162     struct Node *tmp=head;
163     int data;
164     if(head==NULL||head->next==NULL)
165         return 0;
166     while (tmp->next!=NULL) {
167         if (tmp->next->next==NULL) {
168             data=tmp->next->data;
169             free(tmp->next);
170             tmp->next=NULL;
171             break;
172         }
173         tmp=tmp->next;
174     }
175     return data;
176 }
177 
178 int main(int argc,const char *argv[]) 
179 {
180     struct Node *h = creatLinkList();
181     printLinkList(h);
182     
183     //1、返回单链表中第pos个结点中的元素，若pos超出范围，则返回０
184     printf("%d
",toNode(h,5));
185     
186     //2、把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０
187     if (changeData(h,5,5)) {
188         printLinkList(h);
189     }
190     
191     //3、向单链表的表头插入一个元素
192     insertNodeInHead(&h, 0);
193     printLinkList(h);
194     
195     //4、向单链表的末尾添加一个元素
196     insertNodeInEnd(h, 50);
197     printLinkList(h);
198     
199     //5、向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０
200     if(insertData(h, 7, 60))
201         printLinkList(h);
202     
203     //6、向有序单链表中插入元素x结点，使得插入后仍然有序
204     insertSortData(h, 6);
205     printLinkList(h);
206     
207     //7、从单链表中删除表头结点，并把该结点的值返回，若删除失败则返回0
208     printf("%d
",deleteHead(&h));
209     printLinkList(h);
210     
211     //8、从单链表中删除表尾结点并返回它的值，若删除失败则返回0
212     printf("%d
",deleteEnd(h));
213     printLinkList(h);
214     
215     return 0;
216 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/mingfung-liu/p/3158901.html