登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 科技 ›数据结构-单链表

数据结构-单链表

蒋炸役 昨天 10:39
对于顺序表来说，我要一次性的申请一块内存空间，但有时候用户并不确定要多大的内存空间!有时候可能会向里边添加元素，但是受限于申请的内存大小，导致加入元素的时候并不方便，而且顺序表的插入和删除相对复杂，需要设计元素的移动。基于顺序表的缺陷，引入链表，在创建链表的时候，我只需要申请一个头结点，存储链表的头，当需要添加元素的时候，我就申请一块内存，将链表头的下一个节点的指针，指向该地址空间九就可以完成链表结点的插入，可以方便的实现增删等功能。
创建链表的头
  1. typedef struct LinkedList
  2. {
  3.         DataType_t                   data; //结点的数据域
  4.         struct LinkedList        *next; //结点的指针域
  6. }LList_t;
复制代码
创建一个空链表
  1. LList_t * LList_Create(void)
  2. {
  3.         //1.创建一个头结点并对头结点申请内存
  4.         LList_t *Head = (LList_t *)calloc(1,sizeof(LList_t));
  5.         if (NULL == Head)
  6.         {
  7.                 perror("Calloc memory for Head is Failed");
  8.                 exit(-1);
  9.         }
  11.         //2.对头结点进行初始化，头结点是不存储有效内容的！！！
  12.         Head->next = NULL;
  14.         //3.把头结点的地址返回即可
  15.         return Head;
  16. }
复制代码
创建新结点
  1. //func：创建新结点，并初始化
  2. //argc：要添加的新结点的元素的值
  3. //ret：新结点结构体的地址
  5. LList_t * LList_NewNode(DataType_t data)
  6. {
  7.         //1.创建一个新结点并对新结点申请内存
  8.         LList_t *New = (LList_t *)calloc(1,sizeof(LList_t));
  9.         if (NULL == New)
  10.         {
  11.                 perror("Calloc memory for NewNode is Failed");
  12.                 return NULL;
  13.         }
  14.         //2.对新结点的数据域和指针域进行初始化
  15.         New->data = data;
  16.         New->next = NULL;
  18.         return New;
  19. }
复制代码
头部插入元素
  1. bool LList_HeadInsert(LList_t *Head,DataType_t data)
  2. {
  3.         //1.创建新的结点，并对新结点进行初始化
  4.         LList_t *New = LList_NewNode(data);
  5.         if (NULL == New)
  6.         {
  7.                 printf("can not insert new node\n");
  8.                 return false;
  9.         }
  11.         //2.判断链表是否为空，如果为空，则直接插入即可
  12.         if (NULL == Head->next)
  13.         {
  14.                 Head->next = New;
  15.                 return true;
  16.         }
  18.         //3.如果链表为非空，则把新结点插入到链表的头部
  19.         New->next  = Head->next;
  20.         Head->next = New;
  22.         return true;
  23. }
复制代码
尾部插入元素
  1. bool LList_TailInsert(LList_t *Head,DataType_t data)
  2. {
  3.         LList_t *Phead=Head;
  4.         //1.创建新的结点，并对新结点进行初始化
  5.         LList_t *New = LList_NewNode(data);
  6.         if (NULL == New)
  7.         {
  8.                 printf("can not insert new node\n");
  9.                 return false;
  10.         }
  11.         while(Phead->next != NULL){
  12.                 Phead = Phead->next;
  13.         }
  14.         Phead->next = New;
  15.         return true;
  16. }
复制代码
指定元素后边插入
  1. bool LList_DestInsert(LList_t *Head,DataType_t dest,DataType_t data)
  2. {
  3.         //定义两个指针用于遍历
  4.         LList_t *Pphead;
  5.        
  6.         Pphead = Head->next;
  7.         LList_t *New = LList_NewNode(data);
  8.         if (NULL == New)
  9.         {
  10.                 printf("can not insert new node\n");
  11.                 return false;
  12.         }
  13.         if(Head->next == NULL){
  14.                 printf("this is a void list\n");
  15.                 return false;
  16.         }
  17.         while(Pphead->data != dest){
  18.                 if(Pphead->next == NULL ){
  19.                         printf("NO value\n");
  20.                         return false;
  21.                 }
  22.                 else{
  23.                         Pphead = Pphead->next ;
  24.                 }
  25.         }
  26.         New->next =Pphead->next;
  27.         Pphead->next= New;
  28.         return true;
  30. }
复制代码
首删
  1. bool LList_HeadDel(CircLList_t *Head)
  2. {
  3.         //对单向循环链表的头尾结点的地址进行备份
  4.         CircLList_t *Phead = Head->next;
  5.         CircLList_t *Pphead = Head->next;
  6.         //判断当前链表是否为空，为空则直接退出
  7.         if (Head->next == Head)
  8.         {
  9.                 printf("current linkeflist is empty!\n");
  10.                 return false;
  11.         }
  12.         if(Head->next->next == Head->next){
  13.                 Head->next->next =NULL;
  14.                 free(Head->next);
  15.                 Head->next = Head;
  16.                 return true;
  17.         }
  18.         //遍历链表找到尾结点
  19.         while(Phead->next != Head->next){
  20.                 Phead = Phead->next;
  21.         }
  22.         //进行删除操作，重新连接
  23.         Phead->next = Pphead->next;
  24.         Head->next = Pphead->next;
  25.         Pphead->next = NULL;
  26.         free(Pphead);
  27.         return true;
  29.        
  30. }
复制代码
指定元素删除
  1. bool LList_DestDel(LList_t *Head,DataType_t dest)
  2. {
  3.         LList_t *Phead = Head;
  4.         LList_t *Pphead = Head->next;
  5.         //1.判断链表是否为空，如果为空，则直接退出
  6.         if (NULL == Head->next)
  7.         {
  8.                 return false;
  9.         }
  10.         //循环查找目标节点
  11.         while(Pphead->data != dest){
  12.                 if(Pphead->next == NULL){
  13.                         printf("not exit this node\n");
  14.                         return false;
  15.                 }
  16.                 Phead = Pphead;
  17.                 Pphead = Pphead->next;
  18.         }
  19.         Phead->next = Pphead->next;
  20.         Pphead->next = NULL;
  21.         free(Pphead);
  22.         return true;
  24. }
复制代码
尾部删除
  1. bool LList_TailDel(LList_t *Head)
  2. {
  3.         LList_t *Phead = Head;
  4.         LList_t *Pphead = Head->next;
  5.         //判断链表是否为空
  6.         if(Head->next == NULL){
  7.                 printf("this is a void list，do not del \n");
  8.                 return false;
  9.         }
  10.         //循环找到链表的最后一个节点和倒数第二个节点
  11.         while(Pphead->next != NULL){
  12.                 Phead = Pphead;
  13.                 Pphead = Pphead->next;
  14.         }
  15.         //删除尾节点
  16.         Phead->next = NULL;
  17.         free(Pphead);
  18.         return true;
  20. }
复制代码
删除链表中最小的结点
  1. bool LList_MinDel(LList_t *Head)
  2. {
  3.         LList_t *Phead = Head->next;
  4.         DataType_t min = Phead->data;
  5.         LList_t *Pphead = Head->next;
  6.         //判断链表是否为空
  7.         if(Head->next == NULL){
  8.                 printf("this is a void list，do not del \n");
  9.                 return false;
  10.         }
  11.         //循环找到最小的节点（循环的时候比较不了最后一个元素)
  12.         while(Pphead->next != NULL){
  13.                
  14.                 if(Pphead->data < min){
  15.                         min = Pphead->data;
  16.                         Phead = Pphead;
  17.                 }
  18.                 Pphead = Pphead->next;
  20.         }
  21.          //比较最后一个元素是否是最小的
  22.         if(Pphead->data < min){
  23.                 min = Pphead->data;
  24.                 Phead = Pphead;
  25.         }
  26.         if(Phead->next == NULL){
  27.                 LList_TailDel(Head);
  28.         }
  29.         else{
  30.                 LList_DestDel(Head,min);
  31.         }
  32.        
  33.         return true;
  34.        
  35. }
复制代码
删除链表中倒数k个元素
  1. DataType_t LList_FindnLast(LList_t *Head,unsigned int n)
  2. {
  3.         LList_t *Pphead = Head;
  4.         LList_t *Phead = Head;
  5.         //判断链表是否为空
  6.         if(Head->next == NULL){
  7.                 printf("this is a void list，do not del \n");
  8.                 return false;
  9.         }
  10.         for(int i=1;i<n;i++){
  11.                 Pphead = Pphead->next;
  12.         }
  13.         while(Pphead->next != NULL){
  14.                 Pphead = Pphead->next;
  15.                 Phead = Phead->next;
  16.         }
  17.         return Phead->data;
  18. }
复制代码
遍历链表并打印
  1. void LList_Print(LList_t *Head)
  2. {
  3.         //对链表的头文件的地址进行备份
  4.         LList_t *Phead = Head;
  5.        
  6.         //首结点
  7.         while(Phead->next)
  8.         {
  9.                 //把头的直接后继作为新的头结点
  10.                 Phead = Phead->next;
  12.                 //输出头结点的直接后继的数据域
  13.                 printf("data = %d\n",Phead->data);
  14.         }
  16. }
复制代码
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
相关推荐
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
蒋炸役
昨天 10:39

0

粉丝关注

10

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫