数据结构——单链表查询、逆序、排序

本文主要是介绍数据结构——单链表查询、逆序、排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、思维导图

2、查、改、删算法

//快慢排序法找中间值
int mid_link(Link_t *plink)
{Link_Node_t *pfast = plink->phead;Link_Node_t *pslow = pfast;int m = 0;while(pfast != NULL){pfast = pfast->pnext;++m;if(m % 2 == 0){pslow = pslow->pnext;}}printf("%d\n",pslow->data);printf("%p\n",pslow);}//快慢排序法查询倒数第k个
Link_Node_t *recipe_link_count(Link_t *plink)
{Link_Node_t *pfast = plink->phead;Link_Node_t *pslow = pfast;int m = 0;int n;scanf("%d",&n);while(pfast != NULL && m < n){pfast = pfast->pnext;m++;}while(pfast != NULL){pfast = pfast->pnext;pslow = pslow->pnext;}//printf("%d\n",pslow->data);//printf("%p\n",pslow);return pslow;
}//删除指定节点
int pop_point_node(Link_t *plink)
{int n;int m = 0;printf("选择删除节点：");scanf("%d",&n);Link_Node_t *p = plink->phead;Link_Node_t *pdel = NULL;Link_Node_t *ptmp = NULL;if(p == NULL){return 0;}else if(p->data == n){pdel = p;plink->phead = p->pnext;}else if(p != NULL){while(p->data != n){ptmp = p;p = p->pnext;}pdel = p;ptmp->pnext = pdel->pnext;}free(pdel);return 0;
}

3、单链表逆序

//链表逆序
int reverse_link(Link_t *plink)
{if(is_empty_link(plink))return 0;Link_Node_t *ptmp = plink->phead;Link_Node_t *pinsert = NULL;plink->phead = NULL;while(ptmp != NULL){pinsert = ptmp;ptmp = ptmp->pnext;pinsert->pnext = plink->phead;plink->phead = pinsert;}
}

4、插入排序（从未排序部分取出一个元素，插入到已排序部分的正确位置）

void insert_sort_link(Link_t *plink)
{if(is_empty_link(plink) || 1 == plink->clen){return;}Link_Node_t *ptmp = plink->phead->pnext;Link_Node_t *pinsert = NULL;Link_Node_t *p = NULL;plink->phead->pnext = NULL;while(ptmp != NULL){pinsert = ptmp;ptmp = ptmp->pnext;if(pinsert->data <= plink->phead->data){pinsert->pnext = plink->phead; //头插plink->phead = pinsert;}else{p = plink->phead;while(p->pnext != NULL && p->pnext->data < pinsert->data){p = p->pnext;}pinsert->pnext = p->pnext;  //尾插p->pnext = pinsert;   }}
}

双向链表——插删查改：

#include<stdio.h>
#include"dlink.h"
#include<stdlib.h>DLink_t *create_doulink()
{DLink_t *pdoulink = malloc(sizeof(DLink_t));if(NULL == pdoulink){perror("fail creat");return NULL;}pdoulink->phead = NULL;pdoulink->clen = 0;pthread_mutex_init(&pdoulink->mutex,NULL);return pdoulink;
}//判空
int is_empty_doulink(DLink_t *pdoulink)
{return NULL == pdoulink->phead;
}//头插
int push_doulink_head(DLink_t *pdoulink,DataType data)
{DLink_Node_t *pnode = malloc(sizeof(DLink_Node_t));if(NULL == pnode){perror("fail malloc");return -1;}pnode->ppre = NULL;pnode->pnext = NULL;pnode->data = data;if(is_empty_doulink(pdoulink)){pdoulink->phead = pnode;}else{pnode->pnext = pdoulink->phead;pdoulink->phead->ppre = pnode;pdoulink->phead = pnode;}pdoulink->clen++;
}//遍历
void print_pdoulink(DLink_t *pdoulink,int flag)
{if(is_empty_doulink(pdoulink))return;DLink_Node_t *p = pdoulink->phead;if(flag){while(p != NULL){printf(" %d %s %d\n",p->data.id,p->data.name,p->data.score);p = p->pnext;}}else{while(p->pnext != NULL){p = p->pnext;}while(p != NULL){printf(" %d %s %d\n",p->data.id,p->data.name,p->data.score);p = p->ppre;}}}//尾插
int push_doulink_tail(DLink_t *pdoulink ,DataType data)
{DLink_Node_t *pnode = malloc(sizeof(DLink_Node_t));if(pnode == NULL){perror("fail malloc");return -1;}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;if((is_empty_doulink(pdoulink))){push_doulink_head(pdoulink,data);free(pnode);}else{DLink_Node_t *p = pdoulink->phead;while(p->pnext != NULL){p = p->pnext;}p->pnext = pnode;pnode->ppre = p;}}//头删
int pop_head(DLink_t *pdoulink)
{if(is_empty_doulink(pdoulink)){return 0;}DLink_Node_t *p = pdoulink->phead;pdoulink->phead = p->pnext;if(p->pnext != NULL){p->pnext->ppre = NULL;}free(p);
}//尾删
int pop_tail(DLink_t *pdoulink)
{DLink_Node_t *p = pdoulink->phead;if(is_empty_doulink(pdoulink)){return 0;}else if(p->pnext == NULL){pop_head(pdoulink);}else{while(p->pnext->pnext != NULL){p = p->pnext;}free(p->pnext);p->pnext = NULL;}
}//查找 name
DataType *find_dliink_data(DLink_t *pdoulink,char *data)
{if(is_empty_doulink(pdoulink))return NULL;DLink_Node_t *p = pdoulink->phead;while(p != NULL){if(strcmp(p->data.name,data) == 0){return &(p->data);}p = p->pnext;}return NULL;
}//修改(根据name查找)
void update_dlink_data(DLink_t *pdoulink,char *old_data,char *new_data)
{if(is_empty_doulink(pdoulink))return;DLink_Node_t *p = pdoulink->phead;while(p != NULL){if(strcmp(p->data.name,old_data) == 0){strcpy(p->data.name,new_data);break;}p = p->pnext;}}//销毁void destory_dlink(DLink_t *pdoulink)
{while(!(is_empty_doulink(pdoulink))){pop_head(pdoulink);}free(pdoulink);
}

这篇关于数据结构——单链表查询、逆序、排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---