Chinaunix首页 | 论坛 | 博客
  • 博客访问: 56994
  • 博文数量: 16
  • 博客积分: 306
  • 博客等级: 二等列兵
  • 技术积分: 162
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-20 15:08
文章分类

全部博文(16)

文章存档

2013年(1)

2012年(15)

我的朋友

分类: C/C++

2012-10-31 17:46:06

链表是一种线性的数据结构,其一个已有的链表中插入、删除一个链表结点的时间复杂度是O(n)。
以下为一个单链表C++简单的实现版本。
具体为:
头插法、尾插法,链表翻转的递归版和非递归版。

点击(此处)折叠或打开

  1. #include <cstdio>

  2. struct Node
  3. {
  4.     int data ;
  5.     Node *next ;
  6. } ;

  7. void Insert_Head( Node *&head , const int &val ) // 头插法
  8. {
  9.     Node *ptr = new Node() ;
  10.     ptr->next = head ;
  11.     ptr->data = val ;
  12.     head = ptr ;
  13. }

  14. void Insert_Back( Node *&head , Node *&back ,const int &val ) // 尾插法
  15. {
  16.     Node *ptr = new Node() ;
  17.     ptr->data = val ;
  18.     ptr->next = NULL ;
  19.     if ( head == NULL )
  20.         head = back = ptr ;
  21.     else {
  22.         back->next = ptr ;
  23.         back = ptr ;
  24.     }
  25. }

  26. void Print( Node * const &head ) // 单链表的打印函数
  27. {
  28.     for ( Node *it = head ; it != NULL ; it = it ->next )
  29.         printf("%d " , (*it).data );
  30.     puts("") ;
  31. }

  32. void Reverse_not_Dfs( Node *&head ) // 翻转(非递归)
  33. {
  34.     if ( head == NULL )
  35.         return ;
  36.     Node *pre , *cur , *nxt ;
  37.     pre = head ;
  38.     cur = head->next ;
  39.     while ( cur )
  40.     {
  41.         nxt = cur->next ;
  42.         cur->next = pre ;
  43.         pre = cur ;
  44.         cur = nxt ;
  45.     }
  46.     head->next = NULL ;
  47.     head = pre ;
  48. }

  49. Node* Reverse_Dfs( Node *p , Node *&head ) // 翻转(递归)
  50. {
  51.     if ( p->next == NULL )
  52.     {
  53.         head->next = NULL ;
  54.         head = p ;
  55.         return p ;
  56.     }

  57.     Node *tmp = Reverse_Dfs(p->next , head) ;
  58.     tmp->next = p ;
  59.     return p ;
  60. }

  61. int main()
  62. {
  63.     int n;
  64.     while ( ~scanf("%d" , &n) )
  65.     {
  66.         Node *Fhead = NULL , *Bhead = NULL ,*back = NULL ;
  67.         int val , i ;
  68.         for ( i = 0; i < n; i++ )
  69.         {
  70.             scanf("%d" , &val ) ;
  71.             Insert_Head( Fhead , val ) ;
  72.             Insert_Back( Bhead, back , val ) ;

  73.         }

  74.         printf( "Print Insert_head list : " ) ;
  75.         Print( Fhead ) ;

  76.         printf( "Print Insert_back list : ") ;
  77.         Print(Bhead) ;

  78.         printf( "The Insert_head list after Reverse : " ) ;
  79.         Reverse_not_Dfs( Fhead ) ;
  80.         Print( Fhead ) ;

  81.         printf( "The Insert_back list after Reverse : " ) ;
  82.         Reverse_Dfs(Bhead , Bhead) ;
  83.         Print( Bhead ) ;
  84.     }
  85.     return 0 ;
  86. }
简单的有序链表合并:

点击(此处)折叠或打开

  1. // 合并两个有序的链表 eg: 1 4 6 , 3 5 9 -> 1 3 4 5 6 9
  2. Node* Merge_not_Dfs( Node *head1 , Node *head2 ) // 非递归版
  3. {
  4.     if ( head1 == NULL ) return head2 ;
  5.     if ( head2 == NULL ) return head1 ;

  6.     Node *head = NULL , *ptr1 = NULL , *ptr2 = NULL ;
  7.     if ( head1->data < head2->data )
  8.     {
  9.         head = head1 ;
  10.         ptr1 = head->next ;
  11.         ptr2 = head2 ;
  12.     }
  13.     else
  14.     {
  15.         head = head2 ;
  16.         ptr2 = head2->next ;
  17.         ptr1 = head1 ;
  18.     }

  19.     Node *cur = head ;
  20.     while ( ptr1 != NULL && ptr2 != NULL )
  21.     {
  22.         if ( ptr1->data <= ptr2->data )
  23.         {
  24.             cur->next = ptr1 ;
  25.             cur = ptr1 ;
  26.             ptr1 = ptr1->next ;
  27.         }
  28.         else
  29.         {
  30.             cur->next = ptr2 ;
  31.             cur = ptr2 ;
  32.             ptr2 = ptr2->next ;
  33.         }
  34.     }
  35.     if ( ptr1 != NULL )
  36.         cur->next = ptr1 ;
  37.     if ( ptr2 != NULL )
  38.         cur->next = ptr2 ;
  39.     return head ;
  40. }

  41. Node* Merge_Dfs( Node *head1 , Node *head2 ) // 递归版
  42. {
  43.     if ( head1 == NULL ) return head2 ;
  44.     if ( head2 == NULL ) return head1 ;

  45.     Node *head =NULL ;
  46.     if ( head1->data < head2->data )
  47.     {
  48.         head = head1 ;
  49.         head->next = Merge_Dfs( head1->next , head2 ) ;
  50.     }
  51.     else
  52.     {
  53.         head = head2 ;
  54.         head->next = Merge_Dfs( head1 , head2->next) ;
  55.     }
  56.     return head ;
  57. }


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