一，数据结构——链表全操作：
链表形式：
其中，每个节点（Node）是一个结构体，这个结构体包含数据域，指针域，数据域用来存放数据，指针域则用来指向下一个节点；
特别说明：对于单链表，每个节点（Node）可以通过指针域（Node *next）来找到下一个节点，但却不能够找到上一个节点；
只需要知道头结点就可以确定整个链表；
对链表进行的操作一般都需要遍历链表，而链表结束的标志为NULL（要么next指针为空，要么头结点为空）；
若要断开两个节点联系，要先保存下个节点，否则后面的节点无法找到；
关于链表逆序，思想为将指针方向对调，最后头节点为原链表最后一个节点；
以下为链表增，删，改，查，逆序，排序的函数实现：
link.h
#ifndef LINK_H_INCLUDED
#define LINK_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#define datatype int struct node
{
int num;
int data;
struct node* next;
}; typedef struct node Node; void backaddnode(Node **ppnode, int num, datatype data);//增加节点
Node *backaddnodeA(Node *pnode, int num, datatype data);//
void showallnode(Node *pnode);//显示所有的节点
Node *searchfirst(Node *pnode, int num);//查询
int change(Node *pnode, int oldnum, int newnum);//修改失败返回0，成功返回1
Node *rev(Node *pnode);//链表的逆转
Node *del(Node *pnode, int num);//删除
Node *insert(Node *pnode, int findnum, int newnum, datatype data);//实现插入，前面插入
void sort(Node *pnode, char ch);//ch==> ch==< #endif // LINK_H_INCLUDED
link.cpp
#include "link.h" void backaddnode(Node **ppnode, int num, datatype data)
{
Node *newnode = (Node*)malloc(sizeof(Node));
newnode->num = num;
newnode->data = data;
newnode->next = NULL; if (*ppnode == NULL)
{
*ppnode = newnode;
}
else
{
Node *p = *ppnode;
while (p->next != NULL)
{
p = p->next;
}
p->next = newnode;
}
} Node *backaddnodeA(Node *pnode, int num, datatype data)
{
Node *newnode = (Node*)malloc(sizeof(Node));
newnode->num = num;
newnode->data = data;
newnode->next = NULL; if (pnode == NULL)
{
pnode = newnode;
} else
{
Node *p = pnode;
while (p->next != NULL)
{
p = p->next;
}
p->next = newnode;
}
return pnode;
} void showallnode(Node *pnode)
{
printf("链表:\n");
while (pnode != NULL)
{
printf("%d->", pnode->data);
pnode = pnode->next;
}
printf("NULL\n");
} Node *searchfirst(Node *pnode, int num)
{
while (num != pnode->num&&pnode != NULL)
{
pnode = pnode->next;
}
return pnode;
} int change(Node *pnode, int oldnum, int newnum)
{
while (oldnum != pnode->num&&pnode != NULL)
{
pnode = pnode->next;
}
if (pnode != NULL)
{
pnode->num = newnum;
return ;
}
else
{
return ;
}
} Node *del(Node *pnode, int num)
{
Node *p = pnode;
Node *ppre = pnode; while (p->num != num&&p != NULL)
{
ppre = p;
p = p->next;
}
if (p != pnode)
{
ppre->next = p->next;
free(p);
p = NULL; }
else
{
pnode = pnode->next;
free(p);
}
return pnode;
} Node * insert(Node *pnode, int findnum, int newnum, datatype data)
{
Node *newnode = (Node*)malloc(sizeof(Node));
newnode->num = newnum;
newnode->data = data;
newnode->next = NULL;
Node *p = pnode;
Node *ppre = pnode;
while (p->num != findnum&&p != NULL)
{
ppre = p;
p = p->next;
} if (p == pnode)
{
newnode->next = pnode;
pnode = newnode;
}
else if (p != NULL)
{
ppre->next = newnode;
newnode->next = p;
}
return pnode;
} void sort(Node *pnode, char ch)
{
if (ch == '>')
{
Node temp;
for (Node *p1 = pnode; p1!=NULL; p1=p1->next)
{
for (Node *p2 = p1; p2 != NULL; p2 = p2->next)
{
if (p1->data<p2->data)
{
temp.num = p1->num;
p1->num = p2->num;
p2->num = temp.num; temp.data = p1->data;
p1->data = p2->data;
p2->data = temp.data;
}
}
}
}
else
{
Node temp;
for (Node *p1 = pnode; p1 != NULL; p1 = p1->next)
{
for (Node *p2 = p1; p2 != NULL; p2 = p2->next)
{
if (p1->data>p2->data)
{
temp.num = p1->num;
p1->num = p2->num;
p2->num = temp.num; temp.data = p1->data;
p1->data = p2->data;
p2->data = temp.data;
}
}
}
}
} Node *rev(Node *pnode)
{
Node *p1, *p2, *p3;
if (pnode == NULL || pnode->next==NULL)
{
return pnode;
}
else
{
p1 = pnode;
p2 = pnode->next;
while (p2 != NULL)
{
p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
}
pnode->next = NULL;
pnode = p1;
return pnode;
}
}
二，链式队列（入列，出列，清空，打印，优先队列，递归实现）
队列特点：先进先出（FIFO）
入列：在链表尾部插入节点；
出列：指针p记录链表头节点head，然后将头结点head赋值为head->next，释放p并赋值为NULL,新队列头节点为head;
清空与打印：使用递归，打印时先输出节点信息，再进入下一层递归；清空队列时先进入下一层递归后释放节点空间；
优先队列：在插入元素时，按优先级使用插入排序即可得到按优先级排列的队列；
queue_link.h
struct queue
{
int num;//代表数据
int high;//优先级1111
struct queue *pNext;//存储下一个节点的地址
}; typedef struct queue Queue;//简化队列 Queue * initque(Queue *queueA);//初始化
Queue * EnQueue(Queue *queueA, int num, int high);//入队
Queue * DeQueue(Queue *queueA, Queue *pout);//出队
Queue * freeall(Queue *queueA);//清空
void sort(Queue *queueA);//优先级排队
void printfall(Queue *queueA);//打印所有数据，递归
Queue * insertEnQueue(Queue *queueA, int num, int high);
queue_link.c
#include "Queue_link.h"
#include <stdio.h>
#include <stdlib.h> Queue *initque(Queue *queueA)//初始化
{
queueA = NULL;
return queueA;
} Queue *EnQueue(Queue *queueA, int num, int high)//入队
{
Queue *newnode = (Queue *)malloc(sizeof(Queue));
newnode->num = num;
newnode->high = high;
newnode->pNext = NULL; if (queueA == NULL)
{
queueA = newnode;
}
else
{
Queue *p = queueA;
while (p->pNext!=NULL)
{
p = p->pNext;
}
p->pNext = newnode;
}
return queueA;
} Queue *DeQueue(Queue *queueA, Queue *pout)//出队
{
if (queueA == NULL)
{
pout = NULL;
return NULL;
}
else
{
pout->num = queueA->num;
pout->high = queueA->high;
pout->pNext = NULL; Queue *p = queueA;
queueA = queueA->pNext;
free(p);
}
return queueA;
} Queue *freeall(Queue *queueA)//清空
{
if (queueA == NULL)
{
return queueA;
}
else
{
freeall(queueA->pNext);
free(queueA);
queueA = NULL;
}
} //void sort(Queue *queueA);//优先级排队 void printfall(Queue *queueA)//打印所有数据，递归
{
if (queueA==NULL)
{
return;
}
else
{
printf("num=%d,high=%d,addr=%p\n",queueA->num,queueA->high,queueA);
printfall(queueA->pNext);
}
} Queue * insertEnQueue(Queue *queueA, int num, int high)//按优先级插入队列
{
Queue *newnode = (Queue *)malloc(sizeof(Queue));
newnode->num = num;
newnode->high = high;
newnode->pNext = NULL; if (queueA == NULL)
{
queueA = newnode;
}
else if (queueA->high>newnode->high)
{
newnode->pNext = queueA;
queueA = newnode;
}
else
{
Queue *p1;
for (p1 = queueA; p1->pNext!=NULL; p1=p1->pNext)
{
if (newnode->high < p1->pNext->high)
{
break;
}
} newnode->pNext = p1->pNext;
p1->pNext = newnode;
}
return queueA;
}
三，链式栈（入栈，出栈，显示，清空）
栈特点：先进后出（FILO）
入栈：在链表最后增加新节点；
出栈：将链表第一个元素输出，并将其从链表删除；
stack_link.h
#define datatype int
struct stacknode
{
int num;//编号
datatype data;//数据
struct stacknode *pNext;//指针域 };
typedef struct stacknode StackNode;//简化
StackNode * init(StackNode * phead);//初始化
StackNode * push(StackNode * phead, int num, datatype data);//进栈
StackNode * pop(StackNode * phead, StackNode * poutdata);//出栈
StackNode * freeall(StackNode * phead);//清空
void printfall(StackNode * phead);//打印
stack_link.c
#include "static_link.h"
#include <stdio.h>
#include <stdlib.h> StackNode * init(StackNode * phead)//初始化
{
phead = NULL;
return phead;
} StackNode * push(StackNode * phead, int num, datatype data)//进栈
{
StackNode *newnode = (StackNode*)malloc(sizeof(StackNode));
newnode->num = num;
newnode->data = data;
newnode->pNext = NULL;
if (phead == NULL)
{
phead = newnode;
}
else
{
StackNode *p = phead;
while (p->pNext!=NULL)
{
p = p->pNext;
}
p->pNext = newnode;
}
return phead; } StackNode * pop(StackNode * phead, StackNode * poutdata)//出栈
{
if (phead == NULL)
{
poutdata = NULL;
}
else if (phead->pNext == NULL)
{
poutdata->num = phead->num;
poutdata->data = phead->data;
poutdata->pNext = NULL;
free(phead);
phead = NULL;
}
else
{
StackNode *p = phead;
while (p->pNext->pNext!=NULL)
{
p = p->pNext;
}
poutdata->num = p->pNext->num;
poutdata->data = p->pNext->data;
poutdata->pNext = NULL; free(p->pNext);
p->pNext = NULL;
}
return phead;
} StackNode * freeall(StackNode * phead)//清空
{
if (phead == NULL)
{
return NULL;
} else
{
/*StackNode *p1 = phead, *p2 = phead;
while (p1->pNext!=NULL)
{
p2 = p1->pNext;
p1->pNext = p2->pNext;
free(p2);
p2 = NULL;
}
free(phead);
phead = NULL;*/
freeall(phead->pNext);
free(phead);
phead = NULL;
}
} void printfall(StackNode * phead)//打印
{
if (phead == NULL)
{
return ;
}
else
{
printf("num=%d,data=%d,addr=%p\n",phead->num,phead->data,phead);
printfall(phead->pNext);
}
}