////////////////////////////////////////////
//  <算法 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;
 }
}

评论