双链表的插入/简单版

   今天晚上看完了单链表，又看了一点双链表，本来计划这周，周一到周五，5天的时间看链表这一章，大周一的就快看完了，明天继续看双链表插入的高级版，时间过的真是快啊，就弄出来个只能往中间插入的程序，往链表的头和尾插都不行，明天再继续完善吧：

 

[root@bjxdurs235 20090727]# cat -n double_linked_list.c
     1  #include
     2
     3  typedef struct NODE {
     4          struct NODE *previous;
     5          struct NODE *next;
     6          int         value;
     7  } Node;
     8
     9  int dll_insert( Node **rootp, int value )
    10  {
    11          Node *p;
    12          Node *new_node;
    13          p = (*rootp)->next;
    14          if ( p == NULL ){
    15                  /* empty dll */
    16          }
    17
    18          else
    19          {
    20                  while ( p->value < value && p != NULL ){
    21                          p = p->next;
    22                  }
    23                  if( p->value == value ){
    24                          return 0;
    25                  }
    26
    27                  new_node = ( Node * )malloc( sizeof( Node )  );
    28                  if( new_node == NULL ){
    29                          printf("malloc error !\n");
    30                          exit ( 1 );
    31                  }
    32
    33                  new_node->value = value;
    34
    35                  /* give a right place to new_node */
    36
    37                  p->previous->next = new_node;
    38                  p->previous = new_node;
    39                  new_node->next = p;
    40                  new_node->previous = p->previous;
    41
    42
    43          }
    44
    45
    46  }
    47
    48  int main(void)
    49  {
    50          /* init a dll , which have 3 members */
    51          Node *root;
    52          Node *first;
    53          Node *second;
    54          Node *third;
    55
    56          root = ( Node * )malloc( sizeof( Node ) );
    57          if( root == NULL ){
    58                  printf("malloc error !\n");
    59                  exit ( 1 );
    60          }
    61
    62          first = ( Node * )malloc( sizeof( Node ) );
    63          if( first == NULL ){
    64                  printf("malloc error !\n");
    65                  exit ( 1 );
    66          }
    67
    68          second = ( Node * )malloc( sizeof( Node ) );
    69          if( second == NULL ){
    70                  printf("malloc error !\n");
    71                  exit ( 1 );
    72          }
    73
    74          third = ( Node * )malloc( sizeof( Node ) );
    75          if( third == NULL ){
    76                  printf("malloc error !\n");
    77                  exit ( 1 );
    78          }
    79
    80          root->previous = third;
    81          root->next = first;
    82
    83          first->previous = NULL;
    84          first->next = second;
    85          first->value = 5;
    86
    87          second->previous = first;
    88          second->next = third;
    89          second->value = 10;
    90
    91          third->previous = second;
    92          third->next = NULL;
    93          third->value = 15;
    94
    95          /* insert a value to the dll  */
    96          int value;
    97          scanf("%d",&value);
    98          dll_insert( &root,value );
    99
   100          /* print all members of dll  */
   101
   102          printf("print dll members :\n");
   103          Node *p;
   104          p = root->next;
   105          while ( p != NULL ){
   106                  printf("%d\n",p->value);
   107                  p = p->next;
   108          }
   109
   110  }
[root@bjxdurs235 20090727]# ./a.out
12
print dll members :
5
10
12
15
[root@bjxdurs235 20090727]# ./a.out
4
Segmentation fault

 

ok，总结一下学习到是什么：

1、用**，指向指针的指针传递结构体给函数；

2、手动的初始化root/first/second/third这个双链表，给每个元素赋值，虽然比较弱智，但对其理解还是挺有帮助；

3、在初始化链表时，每初始化一个元素，都采用动态分配内存的方式，注意这里要判断是否分配空间成功；

4、链表的previous和next指来指去容易晕，需要逻辑很清楚才行。

5、链表是数据结构的知识，在这一章里弄不太明白的可以不用深究，下本书就是数据结构啦。