在实际生产中，有可能在软件启动后，对一些数据进行多态扩容，比如，网卡收发包的时候，从协议栈上产生一个需求的包，需要暂时排队，等网卡把数据发送出去后，在在队列里处理，所以这种利用堆中分散的内存，以结点为单位的数据结果是有一定的意义的。
链表的数据的数据结构
typedef struct node
{
int data; //数据域
struct node *next; //指针域
}NODE_t;链表的创建
NODE_t *CreatNodeList()
{
NODE_t *head = NULL;
head = (NODE_t *)malloc(sizeof(NODE_t));
if(!head)
exit(-1);
head->next = NULL;
return head;
}链表的插入，头插入，有个头节点，方便遍历，处理
int InsertNode(NODE_t *head,int data)
{
NODE_t *cur = NULL;
if(!head)
exit(-1);
cur = (NODE_t *)malloc(sizeof(NODE_t));
if(!cur)
exit(-1);
cur->data = data;
//cur 插入到 head 和 head->next 之间
cur->next = head->next;
head->next = cur;
return 0;
}结点的查找
NODE_t *findNode(NODE_t *head,int data)
{
head = head->next;
while(head)
{
if(head->data == data)
{
break;
}
head = head->next;
}
if(head == NULL)
{
printf("sorry,%d is not in the list\n",data);
}
return head;
}结点的删除
int DeleteNodeOfList(NODE_t *head,NODE_t *pfind)
{
// 首先找到这个需要删除指针的前一个节点的指针
// 因为pfind 的合法性在外面判断，此处不再判断
while(head->next != pfind)
{
head = head->next;
}
head->next = pfind->next;
free(pfind);
pfind = NULL;
return 0;
}这里的删除，假设结点数目很多，则会造成一个问题，单链表只能一个方向，则需要找到需要删除的节点的前驱指针，则需要从头开始遍历，比较浪费资源，所以，这个地方存在优化空间，就是，一旦拥有需要删除的节点，则可以这么操作
优化版本如下：
// 优化点： 不必每次都遍历所有的节点，找到前驱节点
// 将这个需要删除的节点的后驱节点的数据域拷贝过来，然后删除这个后驱节点
int DeleteNodeOfList_Better(NODE_t *head,NODE_t *pfind)
{
NODE_t *p = pfind->next;
//最后一个节点，它其后没有后驱节点，所以需要从头遍历，找到它的前置节点
if(pfind->next == NULL)
{
while(head->next != pfind)
{
head = head->next;
}
head->next = pfind->next;
free(pfind);
pfind = NULL;
}
else //对于除最后一个节点的外的其他位置节点，则使用覆盖后删除后置节点的方式实现删除
{
pfind->data = pfind->next->data;
pfind->next = pfind->next->next;
free(p);
p = NULL;
}
return 0;
}一旦找到结点的指针操作只是针对数据域的一个操作，比较便捷
结点的修改
int UpdateNode(NODE_t *head,int olddata,int newdata)
{
NODE_t *p = findNode(head,olddata);
if(p)
{
p->data = newdata;
}
return 0;
}遍历打印显示
void showList(NODE_t *head)
{
head = head->next;
while(head)
{
printf("%d ==> ",head->data);
head = head->next;
}
printf("end..\n");
}链表的排序
int sortList(NODE_t *head)
{
int i = 0,j = 0;
int listlen = 0;
int tmpData = 0;
NODE_t *p = NULL;
// 使用冒泡排序，不动指针域，比较数据域，使用临时变量，将有大小之别的节点的数据域交换
// 得到链表长度，方便冒泡
listlen = ListNodeLen(head);
// 指到首节点
p = head->next;
for(i = 0;i < listlen-1;i++)
{
// 每一轮从头开始
p = head->next;
for(j = 0;j<listlen - i-1;j++)
{
// 将小值排在前面
if(p->data > p->next->data)
{
tmpData = p->data;
p->data = p->next->data;
p->next->data = tmpData;
}
p = p->next;
}
}
return 0;
}这里只是demo，链表的数据域很小，所以这种排序方式可以，但是当数据域的很大时，直接使用这种排序，涉及到大量的搬运内存，将会导致很大的资源消耗，所以这个地方是存在优化的空间的，比如直接改变需要交换结点的指向关系
代码如下
int sortList_better(NODE_t *head)
{
// 当数据域很大的时候，搬远数据很耗费资源，但是指针就4个字节，
// 所以改变指针域的相互指向，就可解决问题
// 思路如下：
// 还是使用冒泡比较，当需要交换时，将两个节点的指针域指向关系互换
int i = 0,j = 0;
int listlen = 0;
NODE_t *p = NULL;
NODE_t *q = NULL;
NODE_t *tmp = NULL;
listlen = ListNodeLen(head);
for(i = 0;i <listlen -1;i++)
{
tmp = head;
p = head->next;
q = p->next; // q 永远指向p结点的下一个结点
for(j = 0;j <listlen-i-1;j++)
{
if(p->data > q->data)
{
// NODE_t *tmp = prePointerOfNode(head,p);
// 现在有三个结点，prep p q 他们分别代表的含义是
// p 为当前结点
// prep为p结点的前驱结点
// q 为p结点的后续结点
// 现在需要将p 和 q的顺序做对调，只需要改变其指向关系即可
// 1. 将prep 的下一个结点指向到q
// 2. 将p结点后续结点指向q的后续结点
// 3. 在第二步里已经在q的后续结点的已经找到，所以这个时候将q的后续结点指向p，
// 这样子，就将p和q的顺序对调过了
tmp->next = q;
p->next = q->next;
q->next = p;
// 因为p和q的顺序已经对调过了，为保证顺序，将p和q的顺序做一次对调,
// 确保q是p的下一个结点
/*
注意p和q都是临时变量，所以，这个地方并非对结点的对调，只是临时指针的对调，就是将q对于结点的指针放到p这个临时变量里
，原来p对应的结点指针放到q这个临时变量中
*/
NODE_t *t = NULL;
t = p;
p = q;
q = t;
}
// 向下走一个
tmp = tmp->next;
p = p->next;
q = p->next;
}
}
return 0;
}链表的逆序
void ReverseList(NODE_t *head)
{
//将头指针和其他链表割裂，这样子就是一个空链表 和一个无头的链表
// 然后将另一个链表的每个结点拆出来，然后使用头插法插入到空链中，这样子最后就实现了链表的逆向排序
NODE_t *HeadNextNode = head->next;
head->next = NULL; //分割链表，分成一个空链和一个链表
// 将第二个链表的每一个结点分别插入到空链的头部
for(HeadNextNode;HeadNextNode !=NULL;HeadNextNode = HeadNextNode->next)
{
InsertNode(head,HeadNextNode->data);
}
}这个思路很好，不易出错，如果贸然的从指向关系上入手，很容易把自己绕晕
链表的销毁
void DestoryNodeList(NODE_t *head)
{
NODE_t *p = NULL;
while(head)
{
p = head->next;
free(head);
head = p;
}
}免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
