C和指针12章 链表

1.链表分为单链表和双链表.其中单链表只能从表头到表尾操作,双链表可以从表头到表尾,也可以从表尾到表头,也可以一时从表头到表尾,一时从表尾到表头.链表包括数据域和指针域,指针域指向下一个节点.

2.链表的结构清楚之后就是使用了,主要是插入,删除,改变,查找.这里给出插入的函数,首先我们插入的时候可能插入到表头,可能插入到表尾,也可能插入到表的中间.当然表的中间是最简单的,只需要改变两个指针值就行了,插入到表尾的时候也只要注意下查找时的判断条件就行了,同时是改变两个指针值,但是如果插入的是表头的话,我们呢就要特别处理了,有些人说我们可以单独加一个表头节点,这个节点没有数据域,不过这个有点问题,一是创建的时候要创建一个空表头[这个也好操作?],二是各种操作的时候要跳过这个空表头[这个还是好操作],三是会浪费空间.下面是单链表的插入函数,不过插入到表头的时候,得注意下一些小细节

int sll_insert(Node **linkp,int new_value)//这里是指向Node的指针的指针,因为会可能插入到表头

{

Node *current;

Node *new;

//寻找正确的插入位置,方法是按顺序访问链表,直到到达一个其值大于或等于

//新值的节点.这个函数会重复插入

while((current=*linkp)!=NULL && current->value<new_value)        linkp=&current->link;

//为新节点分配内存,并把新值存储到新节点中,如果内存分配失败,

//函数返回FALSE(FALSE表示0 TRUE表示1)

new = (Node *)malloc(sizeof(Node));

if(NULL == new)

  return FALSE;

new->value=new_value;

//在链表中插入新节点 并返回TRUE

new->link=current;

*linkp=new;

return TRUE;

}

这个函数考虑了插入位置是表头表尾表中的情况,不过这个函数有很大的隐患.主要是这里面的linkp=&current->link;这条语句.取地址存在很大的隐患,C语言取地址既威力巨大,又暗伏凶险.C语言的指针哲学:给你锤子,实际上你可以使用好几种锤子,祝你好运.

3.双链表可以单独拿两个指针来存表头和表尾 也可以单独拿出一个节点存.这样会浪费数据域.这里就看你的取舍了,当然你可以把指针域单独拿出来放在一个struct里面.然后Node这样struct里面包括上面那个struct和一个数据域.这里只需要一个结构标签的不完整声明就OK了.下面给出完整的插入函数

typedef struct a

{

struct a *fwd;

struct a *bwd;

int value;

}Node;下面用到的结构体

int dll_insert(register Node *rootp,int value)

{

register Node *this;

register Node *next;

register Node *newnode;

//查找value是否已经存在于链表中,如果是就返回(这个函数不会重复插入)

//否则,为新值创建一个新节点("newnode"将指向它)

//"this"将指向应该在新节点之前的那个节点

//"next"将指向应该在新节点之后的那个节点

for(this=rootp;(next=this->fwd)!=NULL;this=next)

   {

      if(next->value==value)

        return 0;

      if(next->value>value)

        break;

   }

newnode=(Node *)malloc(sizoef(Node));

if(NULL == newnode)

  return -1;

newnode->value=value;

//把新节点添加到链表中

newnode->fwd=next;

  this->fwd=newnode;

 if(this != rootp)

  newnode->bwd=this;

else

  newnode->bwd=NULL;

if(next != NULL)

  next->bwd=newnode;

else

  rootp->bwd=newnode;

return 1;

}

本章的警告总结:

1.落到链表尾部的外面

2.使用指针时应该格外小心,因为C并没有对它们的使用提供安全网

3.从if语句中提炼语句可能会改变测试结果

Comments

2011-04-06
▲