//////////////////////////////////////////////  <算法 i~iv> //  //  Exercise : 3.43  , Page : 75//  exercise description://   实现一个程序,互换一个双向链表中两个给定的节点的位置.//   //  P.S: 对于相邻节点尚未考虑,还需几行代码即可//  zhaoyg   2008.2.//////////////////////////////////////////// #include <iostream> using namespace std; const int times = 10; struct node { int item; node *prev; node *next;  node (int value , node *p , node *n) {  item = value;  prev = p;  next = n; }}; void creat_node(node **head,int times);void test_list(node *temp);void transposition(node **head,int item_1,int item_2);void free_list(node *head); int main(){ node *head = NULL; node *temp; int item_a,item_b;  cout <<"请输入需要交换节点的位置,用空格分隔\n当前链表中共有"<<times<<"个节点"<<endl; cin >> item_a >> item_b;  creat_node (&head,times);  temp = head->next ;  test_list(temp);//display  transposition(&head,item_a,item_b); //transposition  cout <<"\n\nAfter transposition"<<endl;  temp = head->next ; test_list(temp);//display  free_list(head); system("pause"); return 0;} void creat_node(node **head , int times)  //times 控制分配节点的个数{ node *current = NULL; int value=0;  while (value<times) {  if (*head == NULL)  {   *head = new node ( 0 , current , NULL );   current = *head;  }  else  {   current->next = new node ( ++value , current , NULL );   current = current->next;  } }} void test_list(node *temp)//测试双向链表{ cout<<"顺序显示:"<<endl; for (int i=0;i<times;i++) {  cout<<temp->item<<",";  if (temp->next !=NULL)   temp=temp->next; }  cout<<"\n逆序显示:"<<endl; for (int j=0;j<times;j++) {  cout<<temp->item<<",";  temp=temp->prev; }} void transposition(node **head,int item_x,int item_y){ node *x,*y; node *t_next,*t_prev;  x = y = *head;  for (int i = 0;i<item_x;i++)  x = x->next ;  for (int j = 0; j<item_y;j++)  y = y->next ;  t_next = x->next ; t_prev = x->prev ;  x->next = y->next ; y->next = t_next ;  x->prev = y->prev ; y->prev = t_prev ;  y->prev->next = y; y->next->prev = y; x->prev->next = x;  if (x->next !=NULL)  //当两个待换位节点中的之一不是最后一个节点时  x->next->prev = x;} void free_list(node *head){ node *current=head,*temp;  while (current!=NULL) {  temp=current->next;  free(current);  current=temp; }}

评论