April 5, 2009

資料結構作業四:Inverse Linking List & Double Linking List.

// 環境:Microsoft Visual Studio 2008 or VC6









// For Visual Studio 2008
#include <iostream>
using namespace std;

// For Visual C 6.0
//#include <iostream.h>
//#include <windows.h>

const int TYPE_HEADER  = 0x01;
const int TYPE_NODE = 0x02;
const int TYPE_DOUBLE = 0x04;

typedef struct node
{
 struct node *L_Link;
 int         data;
 char        *NodeType;
 struct node *R_Link;
}node;

node* CreateNode(int TYPE);
void InverseList(void);

void InsertNodeByPointer(node *TargetNode,  node *InsertNode);
void DeleteNodeByPointer(node *TargetNode);

node* FindNodeByData(int value);
node* FindNodeByNumber(int value);
node* FindFinalNode(void);
node* FindNodeByPointer(node* node_x);

void DisplayAllLinks(void);

node *gHeaderNode, *gLastNode;

void main(void)
{
 node *n1, *n2, *n3, *n4, *n5;

 gHeaderNode  = CreateNode(TYPE_HEADER);
 gHeaderNode->data = NULL;

 n1 = CreateNode(TYPE_NODE);
 n1->data = 1;

 n2 = CreateNode(TYPE_NODE);
 n2->data = 2;

 n3 = CreateNode(TYPE_NODE);
 n3->data = 3;

 n4 = CreateNode(TYPE_NODE);
 n4->data = 4;

 cout << "[ Linking List Created. ]\n";
 DisplayAllLinks();

 InverseList();
 cout << "\n[ Linking List Inversed. ]\n";
 DisplayAllLinks();
 system("pause");
 system("cls");

 gHeaderNode  = CreateNode(TYPE_HEADER + TYPE_DOUBLE);
 gHeaderNode->data = NULL;

 n1 = CreateNode(TYPE_NODE + TYPE_DOUBLE);
 n1->data = 1;

 n2 = CreateNode(TYPE_NODE + TYPE_DOUBLE);
 n2->data = 2;

 n3 = CreateNode(TYPE_NODE + TYPE_DOUBLE);
 n3->data = 3;

 n4 = CreateNode(TYPE_NODE + TYPE_DOUBLE);
 n4->data = 4;
 cout << "[ Double Linking List Created. ]\n";
 DisplayAllLinks();

 n5 = CreateNode(TYPE_HEADER + TYPE_DOUBLE);
 n5->data = 5;
 cout << "\n[ Single Node Created. ]\n";
 cout << n5->data <<",    " << n5->NodeType << ",  "<< n5 << ",   " << n5->L_Link << ",    " << n5->R_Link << endl;
 system("pause");
 system("cls");

 InsertNodeByPointer(n1, n5);
 cout << "[ Insert Node 5 behind Node 1. ]\n";
 DisplayAllLinks();

 DeleteNodeByPointer(n4);
 cout << "\n[ Delete Node 4. ]\n";
 DisplayAllLinks();
}

/* ============= 分隔線 ============= */
/* ============= 分隔線 ============= */
/* ============= 分隔線 ============= */
/////////////////////////////////////////////////
// Name  : CreateNode
//
// Input : int TYPE
//         TYPE_HEADER / TYPE_NODE
//
// Output: node *New
//
/////////////////////////////////////////////////
node* CreateNode(int TYPE)
{
 node *New = (node*)malloc(sizeof(node));
 node *ptr;

 if(TYPE & TYPE_HEADER)     // 建立Header
 {
  New->data = NULL;
  New->NodeType = "Header";

  if(TYPE & TYPE_DOUBLE)
  {
   New->L_Link = New->R_Link = New;
  }
  else
  {
   New->L_Link = New->R_Link = NULL;
  }
 }

 if(TYPE & TYPE_NODE) {     // 建立一般Node
  New->NodeType = "Node  ";

  ptr = FindFinalNode();
  ptr->R_Link = New;


  if(TYPE & TYPE_DOUBLE)
  {
   New->R_Link = gHeaderNode;
   New->L_Link = ptr;
   gHeaderNode->L_Link = New;
  }
  else
  {
   New->R_Link = NULL;
   New->L_Link = NULL;
  }

  New->data = NULL;
 }

 return New;
}

/////////////////////////////////////////////////
// Name  :  InverseList
//
// Input :  None
//
// Output:  None
//
/////////////////////////////////////////////////
void InverseList(void)
{
 node *ptr, *temp;

 ptr = gHeaderNode->R_Link;
 gLastNode = gHeaderNode;

 if(ptr != 0 && ptr->L_Link == 0)
 {
  gLastNode = ptr;
  ptr = ptr->R_Link;

  gLastNode->R_Link = NULL;

  if(ptr == 0)
  {
   gHeaderNode->R_Link = gLastNode;
  }
  else
  {
   while(ptr != 0)
   {
    temp = ptr->R_Link;
    ptr->R_Link = gLastNode;
    gLastNode = ptr;
    ptr = temp;
    gHeaderNode->R_Link = gLastNode;
   }
  }
 }
 else
  cout << "\n\n ***** Linking list inservsing failed!\n ***** This node does not exist or this is a double linking list.\n\n";
}


/////////////////////////////////////////////////
// Name  : InsertNodeByPointer
//
// Input : node *TargetNode
//         node *InsertNode
//
// Output: None
//     
/////////////////////////////////////////////////
void InsertNodeByPointer(node *TargetNode,  node *InsertNode)
{
 node *ptr;
 TargetNode = FindNodeByPointer(TargetNode);
 if(TargetNode)
 {
  ptr = TargetNode->R_Link;

  if(TargetNode->L_Link == 0)
   InsertNode->R_Link = TargetNode->R_Link;
  else
  {
   ptr->L_Link = InsertNode;
   InsertNode->R_Link = ptr;
   InsertNode->L_Link  = TargetNode;
  }

  InsertNode->NodeType = "Node  ";
  TargetNode->R_Link = InsertNode;
 }
 else
 {
  cout << "\nTarget Node is not found!\n";
 }
}
/////////////////////////////////////////////////
// Name  : DeleteNodeByPointer
//
// Input : node *TargetNode
//
// Output: None
//
// Note  : Global variable "gLastNode" will be update
/////////////////////////////////////////////////
void DeleteNodeByPointer(node *TargetNode)
{
 node *L_Node, *R_Node;

 TargetNode = FindNodeByPointer(TargetNode);
 if(TargetNode)
 {
  if(TargetNode->R_Link != 0)
  {
   R_Node = TargetNode->R_Link;
   L_Node = TargetNode->L_Link;
   L_Node->R_Link = R_Node;
   R_Node->L_Link = L_Node;
  }
  else
  {

   gLastNode->R_Link = TargetNode->R_Link;
   TargetNode->R_Link = NULL;
  }
  free(TargetNode);
 }
 else
 {
  cout << "\nTarget Node is not found!\n";
 }
}

/////////////////////////////////////////////////
// Name : FindNodeByData
//
// Input : int value
//
// Output: Success = node *ptr
//         Fail = 0
//
// Note  : Global variable "gLastNode" will be update
/////////////////////////////////////////////////
node* FindNodeByData(int value)
{
 node *ptr;
 gLastNode = gHeaderNode;
 ptr = gHeaderNode->R_Link;

 while(ptr != NULL)
 {
  if(ptr->data == value)
  {
   return ptr;
  }
  gLastNode = ptr;
  ptr = ptr->R_Link;
 }
 return 0;
}

/////////////////////////////////////////////////
// Name  : FindNodeByNumber
//
// Input : int value
//
// Output: Success = node *ptr
//         Fail = 0
//
// Note  : Global variable "gLastNode" will be update
/////////////////////////////////////////////////
node* FindNodeByNumber(int value)
{
 int count = 1;
 node *ptr;
 gLastNode = gHeaderNode;
 ptr = gHeaderNode->R_Link;

 while(ptr != NULL)
 {
  if(count == value)
  {
   return ptr;
  }
  gLastNode = ptr;
  ptr = ptr->R_Link;
  count++;
 }
 return 0;
}

/////////////////////////////////////////////////
// Name  : FindFinalNode
//
// Input : None
//
// Output: Success = node *ptr
//         Fail = 0
//
// Note  : Global variable "gLastNode" will be update
/////////////////////////////////////////////////
node* FindFinalNode(void)
{
 node *ptr;

 while(gHeaderNode != NULL)
 {
  if(gHeaderNode->R_Link == NULL)
  {
   return gHeaderNode;
  }

  if(gHeaderNode->L_Link != 0)
  {
   ptr = gHeaderNode->L_Link;
   return ptr;
  }

  ptr = gHeaderNode->R_Link;
  while(ptr->R_Link != NULL)
  {
   gLastNode = ptr;
   ptr = ptr->R_Link;
  }
  return ptr;
 }
 return 0;
}

/////////////////////////////////////////////////
// Name  : FindNodeByPointer
//
// Input : node* TargetNode
//
// Output: Success = node *ptr
//         Fail = 0
//
// Note  : Global variable "gLastNode" will be update
/////////////////////////////////////////////////
node* FindNodeByPointer(node* TargetNode)
{
 node *ptr;
 gLastNode = gHeaderNode;
 ptr = gHeaderNode->R_Link;

 while(ptr != NULL)
 {
  if(ptr == TargetNode)
  {
   return ptr;
  }
  gLastNode = ptr;
  ptr = ptr->R_Link;
 }
 return 0;
}

void DisplayAllLinks(void){
 node *ptr;
 ptr = gHeaderNode;

 cout << "Node, Type,    Pointer,    LeftLink,    RightLink\n";
 cout << "-------------------------------------------------\n";

 while(ptr != NULL)
 {
  cout << ptr->data <<",    " << ptr->NodeType << ",  "<< ptr << ",   " << ptr->L_Link << ",    " << ptr->R_Link << endl;
  ptr = ptr->R_Link;

  if(ptr == gHeaderNode)
   break;
 }
}

Today's Visitors: 0 Total Visitors: 63
[Trackback URL]

Reply
  • 1樓

    1樓搶頭香

    謝謝達叔配合沒秀出全部內容^^

  • Max at April 7, 2009 09:24 AM comment
Post A Comment









Yes No



Please input the magic number:

( Prevent the annoy garbage messages )
( What if you cannot see the numbers? )
Please input the magic number

誰來收藏
Loading ...
unlog_NVPO 0