双向链表


  1. // list.cpp : Defines the entry point for the console application.
  2. //
  4. #include "stdafx.h"
  5. #include <iostream>
  6. using namespace std;
  8. typedef struct list_node {
  9. 	int data;
  10. 	list_node *left;
  11. 	list_node *right;
  12. } Node;
  14. Node *create_node(int data)
  15. {
  16. 	Node *node = new Node();
  17. 	node->data = data;
  18. 	node->left = node->right = NULL;
  19. 	return node;
  20. }
  22. void delete_node( Node * p )
  23. {
  24. 	delete p;
  25. 	p = NULL ;
  26. }
  28. void insert_tail(Node *root , int data)
  29. {
  30. 	Node *node = create_node( data );
  31. 	
  32. 	Node *last_node = root;
  33. 	while(last_node->right != NULL) last_node = last_node->right;
  34. 	last_node->right = node;
  35. 	node->left = last_node;
  36. }
  38. Node *find_node(Node *root , int data )
  39. {
  40. 	Node *node = root ;
  41. 	while(node != NULL) {
  42. 		if( data == node->data ) {
  43. 			return node;
  44. 		}
  45. 		node = node->right;
  46. 	}
  47. 	return NULL;
  48. }
  51. void insert_back_node(Node *root, int dat , int data )
  52. {
  53. 	Node *node = find_node(root,dat);
  54. 	if( node == NULL || node->left == NULL ) return;
  55. 	Node *new_node = create_node( data );
  56. 	node->left->right = new_node;
  57. 	new_node->right = node;
  58. }
  60. void insert_front_node(Node *root, int dat , int data )
  61. {
  62. 	Node *node = find_node(root,dat);
  63. 	if( node == NULL ) return;	
  64. 	Node *new_node = create_node( data );
  65. 	new_node->right = node->right;
  66. 	new_node->left = node;	
  67. 	node->right = new_node;
  68. }
  70. void remote_node ( Node *root,int data )
  71. {
  72. 	Node *node = find_node ( root , data );
  73. 	if( node == NULL ) {
  74. 		return ;
  75. 	} else if ( node->left == NULL ) {
  76. 		node->right->left = NULL;
  77. 	} else if ( node->right == NULL ) {
  78. 		node->left->right = NULL ;
  79. 	} else {
  80. 		node->left->right = node->right;
  81. 		node->right->left = node->left;
  82. 	}
  84. 	delete_node( node );
  86. }
  88. void traversal( Node *root )
  89. {
  90. 	Node *last_node = root;
  91. 	do{
  92. 		cout<<last_node->data<<endl ;
  93. 		last_node = last_node->right;
  94. 	} while(last_node != NULL ) ;
  96. }
  98. int main(int argc, char* argv[])
  99. {
  100. 	Node *root = create_node(1);
  102. 	insert_tail(root,4);
  103. 	insert_tail(root,5);
  104. 	insert_tail(root,800);
  105. 	insert_tail(root,6);
  106. 	insert_tail(root,7);
  109. 	Node *p = find_node(root,5);
  110. 	cout << p <<endl;
  111. 	if(p!=NULL) cout<<p->data <<endl;
  113. 	insert_back_node(root,5,20);
  114. 	insert_front_node(root,1,30);
  116. 	remote_node ( root , 6 ) ;
  117. 	traversal( root );
  119. 	return 0;
  120. }





【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/fysola/p/4862563.html