C语言链表全操作（增，删，改，查，逆序，递增排序，递减排序，链式队列，链式栈）

一，数据结构——链表全操作：

     链表形式：

        

     其中，每个节点（Node）是一个结构体，这个结构体包含数据域，指针域，数据域用来存放数据，指针域则用来指向下一个节点；

     特别说明：对于单链表，每个节点（Node）可以通过指针域（Node *next）来找到下一个节点，但却不能够找到上一个节点；

                   只需要知道头结点就可以确定整个链表；

                   对链表进行的操作一般都需要遍历链表，而链表结束的标志为NULL（要么next指针为空，要么头结点为空）；

                   若要断开两个节点联系，要先保存下个节点，否则后面的节点无法找到；

                   关于链表逆序，思想为将指针方向对调，最后头节点为原链表最后一个节点；

  

     以下为链表增，删，改，查，逆序，排序的函数实现：

     link.h

 1 #ifndef LINK_H_INCLUDED
 2 #define LINK_H_INCLUDED
 3 #include <stdio.h>
 4 #include <stdlib.h>
 5 #define datatype int
 6 
 7 struct node
 8 {
 9     int num;
10     int data;
11     struct node* next;
12 };
13 
14 typedef struct node Node;
15 
16 void backaddnode(Node **ppnode, int num, datatype data);//增加节点
17 Node *backaddnodeA(Node *pnode, int num, datatype data);//
18 void showallnode(Node *pnode);//显示所有的节点
19 Node *searchfirst(Node *pnode, int num);//查询
20 int change(Node *pnode, int oldnum, int newnum);//修改失败返回0，成功返回1
21 Node *rev(Node *pnode);//链表的逆转
22 Node *del(Node *pnode, int num);//删除
23 Node *insert(Node *pnode, int findnum, int newnum, datatype data);//实现插入，前面插入
24 void sort(Node *pnode, char ch);//ch==>  ch==<
25 
26 
27 #endif // LINK_H_INCLUDED
View Code

     link.cpp

  1 #include "link.h"
  2 
  3 void  backaddnode(Node **ppnode, int num, datatype data)
  4 {
  5     Node *newnode = (Node*)malloc(sizeof(Node));
  6     newnode->num = num;
  7     newnode->data = data;
  8     newnode->next = NULL;
  9 
 10     if (*ppnode == NULL)
 11     {
 12         *ppnode = newnode;
 13     }
 14     else
 15     {
 16         Node *p = *ppnode;
 17         while (p->next != NULL)
 18         {
 19             p = p->next;
 20         }
 21         p->next = newnode;
 22     }
 23 }
 24 
 25 Node *backaddnodeA(Node *pnode, int num, datatype data)
 26 {
 27     Node *newnode = (Node*)malloc(sizeof(Node));
 28     newnode->num = num;
 29     newnode->data = data;
 30     newnode->next = NULL;
 31 
 32     if (pnode == NULL)
 33     {
 34         pnode = newnode;
 35     }
 36 
 37     else
 38     {
 39         Node *p = pnode;
 40         while (p->next != NULL)
 41         {
 42             p = p->next;
 43         }
 44         p->next = newnode;
 45     }
 46     return pnode;
 47 }
 48 
 49 void showallnode(Node *pnode)
 50 {
 51     printf("链表:
");
 52     while (pnode != NULL)
 53     {
 54         printf("%d->", pnode->data);
 55         pnode = pnode->next;
 56     }
 57     printf("NULL
");
 58 }
 59 
 60 Node *searchfirst(Node *pnode, int num)
 61 {
 62     while (num != pnode->num&&pnode != NULL)
 63     {
 64         pnode = pnode->next;
 65     }
 66     return pnode;
 67 }
 68 
 69 int change(Node *pnode, int oldnum, int newnum)
 70 {
 71     while (oldnum != pnode->num&&pnode != NULL)
 72     {
 73         pnode = pnode->next;
 74     }
 75     if (pnode != NULL)
 76     {
 77         pnode->num = newnum;
 78         return 1;
 79     }
 80     else
 81     {
 82         return 0;
 83     }
 84 }
 85 
 86 Node *del(Node *pnode, int num)
 87 {
 88     Node *p = pnode;
 89     Node *ppre = pnode;
 90 
 91     while (p->num != num&&p != NULL)
 92     {
 93         ppre = p;
 94         p = p->next;
 95     }
 96     if (p != pnode)
 97     {
 98         ppre->next = p->next;
 99         free(p);
100         p = NULL;
101 
102     }
103     else
104     {
105         pnode = pnode->next;
106         free(p);
107     }
108     return pnode;
109 }
110 
111 Node * insert(Node *pnode, int findnum, int newnum, datatype data)
112 {
113     Node *newnode = (Node*)malloc(sizeof(Node));
114     newnode->num = newnum;
115     newnode->data = data;
116     newnode->next = NULL;
117     Node *p = pnode;
118     Node *ppre = pnode;
119     while (p->num != findnum&&p != NULL)
120     {
121         ppre = p;
122         p = p->next;
123     }
124 
125     if (p == pnode)
126     {
127         newnode->next = pnode;
128         pnode = newnode;
129     }
130     else if (p != NULL)
131     {
132         ppre->next = newnode;
133         newnode->next = p;
134     }
135     return pnode;
136 }
137 
138 
139 void sort(Node *pnode, char ch)
140 {
141     if (ch == '>')
142     {
143         Node temp;
144         for (Node *p1 = pnode; p1!=NULL; p1=p1->next)
145         {
146             for (Node *p2 = p1; p2 != NULL; p2 = p2->next)
147             {
148                 if (p1->data<p2->data)
149                 {
150                     temp.num = p1->num;
151                     p1->num = p2->num;
152                     p2->num = temp.num;
153 
154                     temp.data = p1->data;
155                     p1->data = p2->data;
156                     p2->data = temp.data;
157                 }
158             }
159         }
160     }
161     else
162     {
163         Node temp;
164         for (Node *p1 = pnode; p1 != NULL; p1 = p1->next)
165         {
166             for (Node *p2 = p1; p2 != NULL; p2 = p2->next)
167             {
168                 if (p1->data>p2->data)
169                 {
170                     temp.num = p1->num;
171                     p1->num = p2->num;
172                     p2->num = temp.num;
173 
174                     temp.data = p1->data;
175                     p1->data = p2->data;
176                     p2->data = temp.data;
177                 }
178             }
179         }
180     }
181 }
182 
183 Node *rev(Node *pnode)
184 {
185     Node *p1, *p2, *p3;
186     if (pnode == NULL || pnode->next==NULL)
187     {
188         return pnode;
189     }
190     else
191     {
192         p1 = pnode;
193         p2 = pnode->next;
194         while (p2 != NULL)
195         {
196             p3 = p2->next;
197             p2->next = p1;
198             p1 = p2;
199             p2 = p3;
200         }
201         pnode->next = NULL;
202         pnode = p1;
203         return pnode;
204     }
205 }
View Code

二，链式队列（入列，出列，清空，打印，优先队列，递归实现）

     队列特点：先进先出（FIFO）

     入列：在链表尾部插入节点；

     出列：指针p记录链表头节点head，然后将头结点head赋值为head->next，释放p并赋值为NULL,新队列头节点为head;

    清空与打印：使用递归，打印时先输出节点信息，再进入下一层递归；清空队列时先进入下一层递归后释放节点空间；

    优先队列：在插入元素时，按优先级使用插入排序即可得到按优先级排列的队列；

    queue_link.h

 1 struct queue
 2 {
 3     int num;//代表数据
 4     int high;//优先级1111
 5     struct queue *pNext;//存储下一个节点的地址
 6 };
 7 
 8 typedef  struct queue Queue;//简化队列
 9 
10 Queue * initque(Queue *queueA);//初始化
11 Queue * EnQueue(Queue *queueA, int num, int high);//入队
12 Queue * DeQueue(Queue *queueA, Queue *pout);//出队
13 Queue * freeall(Queue *queueA);//清空
14 void  sort(Queue *queueA);//优先级排队
15 void printfall(Queue *queueA);//打印所有数据，递归
16 Queue * insertEnQueue(Queue *queueA, int num, int high);
View Code

    queue_link.c

  1 #include "Queue_link.h"
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 
  5 Queue *initque(Queue *queueA)//初始化
  6 {
  7     queueA = NULL;
  8     return queueA;
  9 }
 10 
 11 Queue *EnQueue(Queue *queueA, int num, int high)//入队
 12 {
 13     Queue *newnode = (Queue *)malloc(sizeof(Queue));
 14     newnode->num = num;
 15     newnode->high = high;
 16     newnode->pNext = NULL;
 17 
 18     if (queueA == NULL)
 19     {
 20         queueA = newnode;
 21     }
 22     else
 23     {
 24         Queue *p = queueA;
 25         while (p->pNext!=NULL)
 26         {
 27             p = p->pNext;
 28         }
 29         p->pNext = newnode;
 30     }
 31     return queueA;
 32 }
 33 
 34 Queue *DeQueue(Queue *queueA, Queue *pout)//出队
 35 {
 36     if (queueA == NULL)
 37     {
 38         pout = NULL;
 39         return NULL;
 40     }
 41     else
 42     {
 43         pout->num = queueA->num;
 44         pout->high = queueA->high;
 45         pout->pNext = NULL;
 46 
 47         Queue *p = queueA;
 48         queueA = queueA->pNext;
 49         free(p);
 50     }
 51     return queueA;
 52 }
 53 
 54 Queue *freeall(Queue *queueA)//清空
 55 {
 56     if (queueA == NULL)
 57     {
 58         return queueA;
 59     }
 60     else
 61     {
 62         freeall(queueA->pNext);
 63         free(queueA);
 64         queueA = NULL;
 65     }
 66 }
 67 
 68 //void  sort(Queue *queueA);//优先级排队
 69 
 70 void printfall(Queue *queueA)//打印所有数据，递归
 71 {
 72     if (queueA==NULL)
 73     {
 74         return;
 75     }
 76     else
 77     {
 78         printf("num=%d,high=%d,addr=%p
",queueA->num,queueA->high,queueA);
 79         printfall(queueA->pNext);
 80     }
 81 }
 82 
 83 
 84 Queue * insertEnQueue(Queue *queueA, int num, int high)//按优先级插入队列
 85 {
 86     Queue *newnode = (Queue *)malloc(sizeof(Queue));
 87     newnode->num = num;
 88     newnode->high = high;
 89     newnode->pNext = NULL;
 90 
 91     if (queueA == NULL)
 92     {
 93         queueA = newnode;
 94     }
 95     else if (queueA->high>newnode->high)
 96     {
 97         newnode->pNext = queueA;
 98         queueA = newnode;
 99     }
100     else
101     {
102         Queue *p1;
103         for (p1 = queueA; p1->pNext!=NULL; p1=p1->pNext)
104         {
105             if (newnode->high < p1->pNext->high)
106             {
107                 break;
108             }
109         }
110         
111         newnode->pNext = p1->pNext;
112         p1->pNext = newnode;
113     }
114     return queueA;
115 }
View Code

   

三，链式栈（入栈，出栈，显示，清空）

    栈特点：先进后出（FILO）

    入栈：在链表最后增加新节点；

    出栈：将链表第一个元素输出，并将其从链表删除；

    stack_link.h

 1 #define  datatype  int
 2 struct stacknode
 3 {
 4     int num;//编号
 5     datatype data;//数据
 6     struct stacknode *pNext;//指针域
 7 
 8 };
 9 typedef struct stacknode  StackNode;//简化
10 StackNode * init(StackNode * phead);//初始化
11 StackNode * push(StackNode * phead, int num, datatype data);//进栈
12 StackNode * pop(StackNode * phead, StackNode * poutdata);//出栈
13 StackNode * freeall(StackNode * phead);//清空
14 void printfall(StackNode * phead);//打印
View Code

   stack_link.c

  1 #include "static_link.h"
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 
  5 StackNode * init(StackNode * phead)//初始化
  6 {
  7     phead = NULL;
  8     return phead;
  9 }
 10 
 11 StackNode * push(StackNode * phead, int num, datatype data)//进栈
 12 {
 13     StackNode *newnode = (StackNode*)malloc(sizeof(StackNode));
 14     newnode->num = num;
 15     newnode->data = data;
 16     newnode->pNext = NULL;
 17     if (phead == NULL)
 18     {
 19         phead = newnode;
 20     }
 21     else
 22     {
 23         StackNode *p = phead;
 24         while (p->pNext!=NULL)
 25         {
 26             p = p->pNext;
 27         }
 28         p->pNext = newnode;
 29     }
 30     return phead;
 31 
 32 }
 33 
 34 StackNode * pop(StackNode * phead, StackNode * poutdata)//出栈
 35 {
 36     if (phead == NULL)
 37     {
 38         poutdata = NULL;
 39     }
 40     else if (phead->pNext == NULL)
 41     {
 42         poutdata->num = phead->num;
 43         poutdata->data = phead->data;
 44         poutdata->pNext = NULL;
 45         free(phead);
 46         phead = NULL;
 47     }
 48     else
 49     {
 50         StackNode *p = phead;
 51         while (p->pNext->pNext!=NULL)
 52         {
 53             p = p->pNext;
 54         }
 55         poutdata->num = p->pNext->num;
 56         poutdata->data = p->pNext->data;
 57         poutdata->pNext = NULL;
 58 
 59         free(p->pNext);
 60         p->pNext = NULL;
 61     }
 62     return phead;
 63 }
 64 
 65 
 66 StackNode * freeall(StackNode * phead)//清空
 67 {
 68     if (phead == NULL)
 69     {
 70         return NULL;
 71     }
 72     
 73     else
 74     {
 75         /*StackNode *p1 = phead, *p2 = phead;
 76         while (p1->pNext!=NULL)
 77         {
 78             p2 = p1->pNext;
 79             p1->pNext = p2->pNext;
 80             free(p2);
 81             p2 = NULL;
 82         }
 83         free(phead);
 84         phead = NULL;*/
 85         freeall(phead->pNext);
 86         free(phead);
 87         phead = NULL;
 88     }
 89 }
 90 
 91 
 92 void printfall(StackNode * phead)//打印
 93 {
 94     if (phead == NULL)
 95     {
 96         return ;
 97     }
 98     else
 99     {
100         printf("num=%d,data=%d,addr=%p
",phead->num,phead->data,phead);
101         printfall(phead->pNext);
102     }
103 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/weiyikang/p/5022127.html