Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1658750
  • 博文数量: 782
  • 博客积分: 2455
  • 博客等级: 大尉
  • 技术积分: 4140
  • 用 户 组: 普通用户
  • 注册时间: 2011-04-06 21:37
个人简介

Linux ,c/c++, web,前端,php,js

文章分类

全部博文(782)

文章存档

2015年(8)

2014年(28)

2013年(110)

2012年(307)

2011年(329)

分类:

2011-09-30 13:22:22

原文地址:再看链表指针 作者:blacksapper

以前没关心过存储结构。一个数组搞天下。大不了范围广一点。没什么大不了。自从递归的全排列算法因为递归太多影响到效率的时候不得不用链表了。搞了两天。折腾了两天。
因为算法的缘故。每次在头结点插入。在头结点删除。极少数在尾结点删除。并且无法估计链表个数。目前已经超过21亿多了。废话不多说。整原理。下面是我的解决方法。也可以用其他的方法。
链表的声明
  1. typedef struct HNode{
  2.     int using;
  3.     struct HNode *next;
  4. }HNode,*HList;
  5. HList Head;//头结点
其实这里的HNode一般用不上。全部用HList完成就可以了。
Head是头结点。申明了。但是没有创建。
创建头结点和其他结点
  1. Head=malloc(HNode);
  2. HList node1=malloc(HNode);
  3. if(Head==NULL||node1==NULL)
  4.  printf("内存不够用了");
删除时带来的问题。
因为我的操作都是在头和尾完成。删除的时候分别带来了下面的问题。

1.头删除的错误代码
  1. //删除node1
  2. HList node2=node1;
  3. node1=Head->next;
  4. free(node2);
因为之前node1就是Head->next;这里一下子两个都删除了。
索性写丑一点的正确代码。
  1. //删除node1
  2. HList node2=node1;
  3. node1=Head;
  4. free(node2);
  5. node1=Head->next;
第二行是为了node1.有所指,这样不会被free掉。而除了头结点后面的全部说不清楚。索性放到头结点。
2.尾指针的错误删除
  1. //删除node1
  2. free(node1);
如不以为尾指针不是尾指针采用pre->next=node1->next;也行。前提是全部指针在创建的时候必须强制node->next=NULL;

产生错误删除的原因是新的尾指针指向的是一个废地址。但是确实存在这个地址。如果需要使用新的尾指针的next的时候是未初始化的值而不是pre->next==NULL
例子
  1. //假设现在处于这样的状态
  2. //Head->node1->node2->....->pre->nodeL->NULL;
  3. //最后一个结点是nodeL。之前的一个是pre
  4. free(nodeL);
  5. HList A=Head;
  6. while(A->next!=pre)
  7.  A=A->next;
  8. //A指向pre的前驱
  9. A=A->next;//A现在指向pre
  10. if(A->next==NULL||A->next)
  11.   printf("OK");
这里的OK是打印不出来的。
正确的删除的方法是
  1. freenode(HList node1){
  2. HList node2=node1;
  3. node1=Head;
  4. while(node1->next!=node2)
  5.  node1=node1->next;
  6. free(node2);
  7. node1->next=NULL;
  8. }
这样就能保证尾结点指向的是NULLl了。也能打印整个链表的值了。



阅读(732) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~