Chinaunix首页 | 论坛 | 博客
  • 博客访问: 927876
  • 博文数量: 177
  • 博客积分: 8613
  • 博客等级: 中将
  • 技术积分: 2835
  • 用 户 组: 普通用户
  • 注册时间: 2006-03-12 04:16
文章分类
文章存档

2012年(12)

2011年(24)

2010年(24)

2009年(75)

2008年(42)

我的朋友

分类: C/C++

2009-07-28 23:25:10

     今天看完了链表这一章,做习题的时候要求实现:
1、求单链表的节点个数;
2、删除单链表的一个节点
     这是我的实现:
 
[root@bjxdurs235 20090728]# cat -n single_linked_list_num.c
     1  #include
     2  #include
     3
     4  typedef struct NODE {
     5          struct NODE *link;
     6          int         value;
     7  } Node;
     8
     9  int linked_list_print( Node *root )
    10  {
    11          printf("now, print the linked list:\n");
    12          while ( root->link != NULL ){
    13                  printf("%d\n",root->value);
    14                  root = root->link;
    15          }
    16          printf("%d\n",root->value);
    17  }
    18
    19  int linked_list_len( Node *root )
    20  {
    21          int i = 1;
    22          while ( root->link != NULL ){
    23                  i++;
    24                  root=root->link;
    25          }
    26          return i;
    27  }
    28
    29  int linked_list_remove( Node **rootp, Node *node )
    30  {
    31          Node *current;
    32          /* old stytle
    33             Node *previous;
    34             previous = *rootp;
    35             current = previous->link;
    36             while ( current != NULL ){
    37             if ( current == node ){
    38             previous->link = node->link;
    39             return 1;
    40             }
    41             previous = current;
    42             current=current->link;
    43             }
    44             return 0;
    45           */
    46          /* new stytle */
    47
    48          current = *rootp;
    49          if ( current == node ){
    50                  *rootp = node->link;
    51                  return 1;
    52          }
    53
    54          while ( current != NULL ){
    55                  if ( current->link == node ){
    56                          current->link = node->link;
    57                          return 1;
    58                  }
    59                  current = current->link;
    60          }
    61          return 0;
    62
    63  }
    64
    65  int main(void)
    66  {
    67          int i,length;
    68          Node *root;
    69          Node *first;
    70          Node *second;
    71          Node *third;
    72
    73          /*
    74             malloc mem to store root and 3 nodes
    75           */
    76
    77          first = (Node *)malloc( sizeof(Node) );
    78          if ( first == NULL ){
    79                  printf("malloc error!\n");
    80                  exit ( 1 );
    81          }
    82
    83          second = (Node *)malloc( sizeof(Node) );
    84          if ( second == NULL ){
    85                  printf("malloc error!\n");
    86                  exit ( 1 );
    87          }
    88
    89          third = (Node *)malloc( sizeof(Node) );
    90          if ( third == NULL ){
    91                  printf("malloc error!\n");
    92                  exit ( 1 );
    93          }
    94
    95          root = first;
    96          first->link = second;
    97          first->value = 5;
    98          second->link = third;
    99          second->value = 10;
   100          third->link = NULL;
   101          third->value = 15;
   102
   103          /* old code
   104             head->link = NULL;
   105             previous = head;
   106
   107             fill 3 members of this linked list
   108             for ( i=0; i<3; i++ ){
   109             current = (Node *)malloc( sizeof(Node) );
   110             if ( current == NULL ){
   111             printf("malloc error!\n");
   112             exit ( 1 );
   113             }
   114
   115             printf( "please input value :\n" );
   116             scanf( "%d",¤t->value );
   117
   118             previous->link = current;
   119             current->link = NULL;
   120             previous = current;
   121
   122
   123             }
   124
   125           */
   126          /*
   127             printf every member of this linked list
   128
   129             printf("now, print the linked list:\n");
   130             Node *p;
   131             for ( p=head->link; p->link != NULL; p=p->link ){
   132             printf("%d\n",p->value);
   133             }
   134             printf("%d\n",p->value);
   135
   136             length = linked_list_len(head);
   137             printf("length of this ll is : %d\n",length);
   138           */
   139          linked_list_print(root);
   140          printf("length of ll: %d\n",linked_list_len(root));
   141          linked_list_remove( &root, first );
   142          linked_list_print(root);
   143          printf("length of ll: %d\n",linked_list_len(root));
   144  }
[root@bjxdurs235 20090728]# ./a.out
now, print the linked list:
5
10
15
length of ll: 3
now, print the linked list:
10
15
length of ll: 2
 
学习到的总结:
 
1、单链表的静态初始化,当然,和双链表一样都需要malloc;
2、求单链表的长度、打印单链表的元素的时候都要注意最后一个元素,因为一般的判断条件是link是否为NULL,是NULL就不执行了,但是最后一个元素还是要处理的,改打印的单独打印,改计数的单独计数啊;
3、在删除一个节点时,刚开始想到的办法是定义一个previous的Node *指针,指向到删除节点的前一节点,后来想想这是没有必要的,直接找到某个节点的link是他,改这个link到下一个即可。
 
阅读(1393) | 评论(0) | 转发(0) |
0

上一篇:双链表的插入/简单版

下一篇:fgrep的实现

给主人留下些什么吧!~~