请选择 进入手机版 | 继续访问电脑版
电路城论坛交流群:579145816
查看: 19|回复: 2

[单片机资料] 链表与内存--头节点的登场和链表分割详解

[复制链接]

签到天数: 335 天

[LV.8]指点江湖

发表于 2018-8-8 21:57:56 | 显示全部楼层 |阅读模式

上篇写到了链表,后来发现自己对链表的理解还有些偏差,重新做了下链表测试,优化了相关代码。具体可参看文章链表与内存块
主要改动的地方是:之前理解的链表为一个节点一个节点串联起来,后来查看资料,发现如果给链表增加一个空节点,使用起来会更加方便。也就是说,链表表头的第一个节点只有地址,没有实际数据,当然我们也可以给他填充上一些数据比如链表长度等。从第二个节点开始节点有了地址和数据,我们称第二个节点为头指针。很显然,头节点不一定是头指针,头节点可以没有,但头指针必须有。
[头节点] -> [头指针]->[ ] -> NULL
那么加入头节点之后,代码瞬间就变得统一起来,而且也更加好理解。
如增加一个节点到链表,可以如下定义,可对比之前的文章中的添加节点代码。
下面是增加头节点后的代码,敬请参考。

增加元素到链表
  1. /* 增加一个元素到链表中
  2. *   head -- 链表头节点
  3. *   item -- 要增加的加点
  4. *   Opr  -- 0(增加到头指针) -1(增加到尾指针) >0 增加到对应节点之后
  5. */
  6. U8 NodeAdd(struct node **head, struct node *item, S8 Oper)
  7. {
  8.     struct node *temp;

  9.     /* 头节点为空,链表未分配地址 */
  10.     if (*head == NULL)
  11.     {
  12.         return 0;
  13.     }

  14.     /* 添加到头指针 */
  15.     if (Oper == 0)
  16.     {
  17.         item->next = (*head)->next;
  18.         (*head)->next = item;
  19.         (*head)->data++;
  20.         return 1;
  21.     }
  22.     else if (Oper == -1) /* 添加到尾指针 */
  23.     {
  24.         temp = (*head)->next; /* 获取链表头指针 */
  25.         while(temp)
  26.         {
  27.             if (temp->next == NULL)
  28.             {
  29.                 item->next = *head;
  30.                 //item->next = NULL;        /* 先续尾 */
  31.                 temp->next = item;      /* 再接头 */
  32.                 (*head)->data++;
  33.                 return 1;
  34.             }
  35.             temp = temp->next;
  36.         }
  37.     }
  38.     else
  39.     {
  40.         temp = (*head)->next; /* 获取链表头指针 */
  41.         while(temp)
  42.         {
  43.             if (temp->index == Oper)
  44.             {
  45.                 item->next = temp->next;    /* 先续尾 */
  46.                 temp->next = item;          /* 再接头 */
  47.                 (*head)->data++;
  48.                 return 1;
  49.             }
  50.             temp = temp->next;
  51.         }
  52.     }
  53.     return 2;//节点索引错误
  54. }
复制代码
删除链表中节点
  1. /* 在链表中删除指定节点 */
  2. U8 NodeDel(struct node **head, U8 DelIndex)
  3. {
  4.     struct node *nodeforward; /* 查询节点指针 */
  5.     struct node *nodetemp;      /* 暂存节点指针 */

  6.     /* 头节点空 */
  7.     if (*head == NULL)
  8.     {
  9.         return 0;
  10.     }

  11.     nodeforward = (*head); /* 查询指针指向头节点 */

  12.     while(nodeforward->next)
  13.     {
  14.         nodetemp = nodeforward;
  15.         nodeforward = nodeforward->next;

  16.         if (nodeforward->index == DelIndex)
  17.         {
  18.             nodetemp->next = nodeforward->next;
  19.             (*head)->data--;
  20.             return 1;
  21.         }
  22.     }
  23.     return 2;
  24. }
复制代码
修改指定节点的值
  1. //修改指定节点中的值
  2. U8 NodeModifyIndex(struct node **head, U8 *data,U8 modifyindex)
  3. {
  4.     struct node *temp;

  5.     if (*head == NULL)
  6.     {
  7.         return 0;
  8.     }

  9.     temp = *head;

  10.     while(temp)
  11.     {
  12.         if (temp->index == modifyindex)//找到指定节点
  13.         {
  14.             memcpy(&temp->data,data,sizeof(temp->data));
  15.             return 1;
  16.         }
  17.         temp = temp->next;
  18.     }
  19.     return 2;//没有找到对应节点
  20. }
复制代码
将一个链表按顺序分割
  1. /*
  2. *   将一个链表按照给定值val排序,大于等于val的放在后面,小于val的放在前面
  3. *   链表带头结点: [头结点] -> [头指针] -> [] -> []
  4. *   头结点存放结点个数,索引为0
  5. */
  6. U8 NodeCut2Parts(struct node **head,U8 val)
  7. {
  8.     struct node *temp = NULL;
  9.     struct node *small = NULL;
  10.     struct node *big = NULL;
  11.     struct node *ptrsmall = NULL; /* 指向small链表各结点的指针 */
  12.     struct node *ptrbig = NULL;

  13.     small = (struct node *)malloc(sizeof(struct node));
  14.     big = (struct node *)malloc(sizeof(struct node));

  15.     ptrsmall = small;
  16.     ptrbig = big;

  17.     if (*head == NULL)/* 链表为空,头节点 */
  18.     {
  19.         free(small);
  20.         free(big);
  21.         return 0;
  22.     }
  23.     else
  24.     {
  25.         temp = (*head)->next;/* 头指针赋值 */

  26.         while(temp)
  27.         {
  28.             if (temp->index < val)
  29.             {
  30.                 ptrsmall->next = temp;
  31.                 ptrsmall = ptrsmall->next; /* small链表节点指针后移 */
  32.             }
  33.             else
  34.             {
  35.                 ptrbig->next = temp;
  36.                 ptrbig = ptrbig->next;  /* big链表节点指针后移 */
  37.             }
  38.             temp = temp->next; /* 原链表节点指针后移 */
  39.         }
  40.         /* 将大小链表的最后节点指向NULL */
  41.         ptrsmall->next = NULL;
  42.         ptrbig->next = NULL;

  43.         ptrsmall->next = big->next; /* 大小链表合并 */
  44.         (*head)->next = small->next;/* 合并后赋值给原链表 */
  45.         free(small);
  46.         free(big);
  47.     }
  48. }
复制代码
主程序可以用来测试功能
  1. void main()
  2. {
  3.     U8 datamodify = 0xAB;
  4.     struct node *NewNodeList;
  5.     struct node Node[10];


  6.     NewNodeList->data = 0;
  7.     NewNodeList->index = 0;
  8.     NewNodeList->next = NULL;

  9.     /* 给10个节点赋值 */
  10.     for (i=0;i<10;i++)
  11.     {
  12.         Node[i].index = i+1;
  13.         Node[i].data = (U8)(((i+1)&0x0F)|(((i+1)<<4)&0xF0));
  14.         Node[i].next = NULL;
  15.     }

  16.     //1. 分别把Node1,2,3 加入链表
  17.     NodeAdd(&NewNodeList,&Node[0],0);
  18.     NodeAdd(&NewNodeList,&Node[5],0);
  19.     NodeAdd(&NewNodeList,&Node[3],0);
  20.     NodeAdd(&NewNodeList,&Node[8],0);
  21.     NodeAdd(&NewNodeList,&Node[1],-1);

  22.     //GetNodeNum(&NewNodeList);

  23.     NodeAdd(&NewNodeList,&Node[6],-1);
  24.     NodeAdd(&NewNodeList,&Node[2],-1);
  25.     NodeAdd(&NewNodeList,&Node[7],-1);
  26.     NodeAdd(&NewNodeList,&Node[4],6);
  27.     NodeAdd(&NewNodeList,&Node[9],1);

  28.     //4. 删除指定节点
  29.     NodeDel(&NewNodeList,2);

  30.     //5. 修改某个节点的值
  31.     NodeModifyIndex(&NewNodeList,&datamodify,1);

  32.     NodeCut2Parts(&NewNodeList,5);
  33. }
复制代码












签到天数: 639 天

[LV.9]元老将成

发表于 2018-8-9 08:31:12 | 显示全部楼层
不错的资料
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

站长推荐上一条 /1 下一条


返回顶部