March 30, 2009

資料結構作業三:Linking List, Create、Insert、Delete and Search(Node, Data, Number and Final).

// 環境:Microsoft Visual Studio 2008

#include <iostream>
using namespace std;

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

typedef struct node
{
 int data;
 struct node *next;
}node;

node* CreateNode(int TYPE);

void InsertNodeByData(int TargetData,  node *InsertNode);
void InsertNodeByNumber(node *TargetNumber,  node *InsertNode);
void InsertNodeByPointer(node *TargetNode,  node *InsertNode);
void InsertFinalNode(node *InsertNode);

void DeleteNodeByData(int value);
void DeleteNodeByNumber(int value);
void DeleteNodeByPointer(node *TargetNode);
void DeleteFinalNode(void);

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, *n6, *n7, *n8, *n9, *n10;

 gHeaderNode  = CreateNode(TYPE_HEADER);
 gHeaderNode->data = 0xAAAAAAAA;
 cout << "\n[ Create Header ]" << endl;
 DisplayAllLinks();

 n1 = CreateNode(TYPE_NODE);
 n1->data = 0x11111111;
 cout << "\n[ Create Node 1 ]" << endl;
 DisplayAllLinks();

 n2 = CreateNode(TYPE_NODE);
 n2->data = 0x22222222;
 cout << "\n[ Create Node 2 ]" << endl;
 DisplayAllLinks();

 n3 = CreateNode(TYPE_NODE);
 n3->data = 0x33333333;
 cout << "\n[ Create Node 3 ]" << endl;
 DisplayAllLinks();

 n4 = CreateNode(TYPE_NODE);
 n4->data = 0x44444444;
 cout << "\n[ Create Node 4 ]" << endl;
 DisplayAllLinks();

 n5 = CreateNode(TYPE_NODE);
 n5->data = 0x55555555;
 cout << "\n[ Create Node 5 ]" << endl;
 DisplayAllLinks();

 n6 = CreateNode(TYPE_NODE);
 n6->data = 0x66666666;
 cout << "\n[ Create Node 6 ]" << endl;
 DisplayAllLinks();

 system("pause");
 system("cls");

 n7 = CreateNode(TYPE_HEADER);
 n7->data = 0x77777777;
 cout << "\n[ Create Node 7 ]" << endl;
 cout << n7 << ", 0x" << hex << uppercase << n7->data << ", " << n7->next << endl;

 n8 = CreateNode(TYPE_HEADER);
 n8->data = 0x88888888;
 cout << "\n[ Create Node 8 ]" << endl;
 cout << n8 << ", 0x" << hex << uppercase << n8->data << ", " << n8->next << endl;

 n9 = CreateNode(TYPE_HEADER);
 n9->data = 0x99999999;
 cout << "\n[ Create Node 9 ]" << endl;
 cout << n9 << ", 0x" << hex << uppercase << n9->data << ", " << n9->next << endl;

 n10 = CreateNode(TYPE_HEADER);
 n10->data = 0x10101010;
 cout << "\n[ Create Node 10 ]" << endl;
 cout << n10 << ", 0x" << hex << uppercase << n10->data << ", " << n10->next << endl;

 system("pause");
 system("cls");

 InsertNodeByPointer(n3, n7);
 cout << "\n[ Insert n7 behind n3 ]" << endl;
 DisplayAllLinks();

 DeleteFinalNode();
 cout << "\n[ Delete Final Node ]" << endl;
 DisplayAllLinks();

 InsertNodeByData(0x11111111, n8);
 cout << "\n[ Insert n8 behind Data 0x11111111 ]" << endl;
 DisplayAllLinks();

 DeleteNodeByPointer(n2);
 cout << "\n[ Delete n2 ]" << endl;
 DisplayAllLinks();

 system("pause");
 system("cls");

 InsertNodeByNumber(3, n9);
 cout << "\n[ Insert n9 behind Node Number 3 ]" << endl;
 DisplayAllLinks();

 DeleteNodeByNumber(2);
 cout << "\n[ Delete Number 2 ]" << endl;
 DisplayAllLinks();

 InsertFinalNode(n10);
 cout << "\n[ Insert n10 to the final ]" << endl;
 DisplayAllLinks();

 DeleteNodeByData(0x77777777);
 cout << "\n[ Delete Data 0x77777777 ]" << endl;
 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->next = NULL;
 }
 
 if(TYPE == TYPE_NODE) {  // 建立一般Node
  ptr = FindFinalNode();
  ptr->next = New;

  New->next = NULL;
  New->data = NULL;
 }

 return New;
}

/////////////////////////////////////////////////
//Name : InsertNodeByData
//
//Input : int TargetData
//  node *InsertNode
//
//Output : None
//      
/////////////////////////////////////////////////
void InsertNodeByData(int TargetData,  node *InsertNode)
{
 node *TargetNode;
 TargetNode = FindNodeByData(TargetData);
 if(TargetNode)
 {
  InsertNode->next = TargetNode->next;
  TargetNode->next = InsertNode;
 }
 else
 {
  cout << "\nTarget Data is not found!\n";
 }
}
/////////////////////////////////////////////////
//Name : InsertNodeByNumber
//
//Input : int TargetNumber
//  node *InsertNode
//
//Output : None
//      
/////////////////////////////////////////////////
void InsertNodeByNumber(int TargetNumber,  node *InsertNode)
{
 node *TargetNode;
 TargetNode = FindNodeByNumber(TargetNumber);
 if(TargetNode)
 {
  InsertNode->next = TargetNode->next;
  TargetNode->next = InsertNode;
 }
 else
 {
  cout << "\nTarget Number is not found!\n";
 }
}
/////////////////////////////////////////////////
//Name : InsertNodeByPointer
//
//Input : node *TargetNode
//  node *InsertNode
//
//Output : None
//      
/////////////////////////////////////////////////
void InsertNodeByPointer(node *TargetNode,  node *InsertNode)
{
 TargetNode = FindNodeByPointer(TargetNode);
 if(TargetNode)
 {
  InsertNode->next = TargetNode->next;
  TargetNode->next = InsertNode;
 }
 else
 {
  cout << "\nTarget Node is not found!\n";
 }
}
/////////////////////////////////////////////////
//Name : InsertFinalNode
//
//Input : node *InsertNode
//
//Output : None
//      
/////////////////////////////////////////////////
void InsertFinalNode(node *InsertNode)
{
 node *TargetNode;
 TargetNode = FindFinalNode();
 if(TargetNode)
 {
  InsertNode->next = TargetNode->next;
  TargetNode->next = InsertNode;
 }
 else
 {
  cout << "\nFinal Node is not found!\n";
 }
}
/////////////////////////////////////////////////
//Name : DeleteNodeByPointer
//
//Input : node *TargetNode
//
//Output : None
//
//Note:  Global variable "gLastNode" will be update
/////////////////////////////////////////////////
void DeleteNodeByPointer(node *TargetNode)
{
 TargetNode = FindNodeByPointer(TargetNode);
 if(TargetNode)
 {
  gLastNode->next = TargetNode->next;
  TargetNode->next = NULL;
  free(TargetNode);
 }
 else
 {
  cout << "\nTarget Node is not found!\n";
 }
}

/////////////////////////////////////////////////
//Name : DeleteNodeByNumber
//
//Input : node *TargetNode
//
//Output : None
//
//Note:  Global variable "gLastNode" will be update
/////////////////////////////////////////////////
void DeleteNodeByNumber(int value)
{
 node *TargetNode;
 TargetNode = FindNodeByNumber(value);
 if(TargetNode)
 {
  TargetNode = gLastNode->next;
  gLastNode->next = TargetNode->next;
  TargetNode->next = NULL;
  free(TargetNode);
 }
 else
 {
  cout << "\nTarget Node Number is not found!\n";
 }
}

/////////////////////////////////////////////////
//Name : DeleteNodeByData
//
//Input : in value
//
//Output : None
//
//Note:  Global variable "gLastNode" will be update
/////////////////////////////////////////////////
void DeleteNodeByData(int value)
{
 node *TargetNode;
 TargetNode = FindNodeByData(value);
 if(TargetNode)
 {
  gLastNode->next = TargetNode->next;
  TargetNode->next = NULL;
  free(TargetNode);
 }
 else
 {
  cout << "\nTarget Data is not found!\n";
 }
}

/////////////////////////////////////////////////
//Name : DeleteFinalNode
//
//Input : None
//
//Output : None
//
//Note:  Global variable "gLastNode" will be update
/////////////////////////////////////////////////
void DeleteFinalNode(void)
{
 node *TargetNode;
 TargetNode = FindFinalNode();
 if(TargetNode)
 {
  gLastNode->next = NULL;
  TargetNode->next = NULL;
  free(TargetNode);
 }
 else
 {
  cout << "\nFinal 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->next;

 while(ptr != NULL)
 {
  if(ptr->data == value)
  {
   return ptr;
  }
  gLastNode = ptr;
  ptr = ptr->next;
 }
 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->next;

 while(ptr != NULL)
 {
  if(count == value)
  {
   return ptr;
  }
  gLastNode = ptr;
  ptr = ptr->next;
  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->next == NULL)
  {
   return gHeaderNode;
  }

  ptr = gHeaderNode->next;
  while(ptr->next != NULL)
  {
   gLastNode = ptr;
   ptr = ptr->next;
  }
  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->next;

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

void DisplayAllLinks(void){
 node *ptr;
 ptr = gHeaderNode;
 while(ptr != NULL)
 {
  cout << ptr << ", 0x" << hex << uppercase << ptr->data << ", " << ptr->next << endl;
  ptr = ptr->next;
 }
}

Today's Visitors: 0 Total Visitors: 121
Personal Category: 台北科技大學 Topic: goups / school-wise / school clubs
Previous in This Category: 資料結構作業二:老鼠走迷宮(堆疊)   Next in This Category: 資料結構作業二:老鼠走迷宮(堆疊)
[Trackback URL]

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