資料結構作業四: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;
}
}
Previous in This Category: 資料結構作業三:Linking List, Create、Insert、Delete and Search(Node, Data, Number and Final). Next in This Category: 資料結構作業五之一:Creat PreOrder Binary Tree


1樓
1樓搶頭香
謝謝達叔配合沒秀出全部內容^^