資料結構作業九:(Doubly) Linked list creat and table sort & exchange.
#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
//using namespace std;
#define MAX 20
#define DOUBLY 0x01
typedef struct TreeNode
{
int Data;
int Link, Linkb;
}TreeNode;
typedef TreeNode *TreePtr;
int CreateLink(TreePtr *BinaryTreeX, int DataSizeX, int cmd);
void ExchangeLinkList(TreePtr *BinaryTreeX, int firstX, int DataSizeX, int cmd);
void PrintArray(TreePtr *BT, int DZ, int cmd);
void main(void)
{
int i, first;
int Data[]={255, 26, 5, 77, 1, 61, 11, 59, 15, 48, 19};
int DataSize = sizeof(Data)/sizeof(int);
TreePtr BinaryTree[MAX];
for(i = 0; i<DataSize; i++)
{
BinaryTree[i] = (TreePtr)malloc(sizeof(TreeNode));
BinaryTree[i]->Data = Data[i];
BinaryTree[i]->Link = NULL;
BinaryTree[i]->Linkb = NULL;
}
cout << "Create linked list and table.\n";
first = CreateLink(BinaryTree, DataSize, NULL);
PrintArray(BinaryTree, DataSize, NULL);
cout << "Exchange the address of linked list (after sorting).\n";
ExchangeLinkList(BinaryTree, first, DataSize, NULL);
for(i = 0; i < DataSize; i++)
{
BinaryTree[i]->Data = Data[i];
BinaryTree[i]->Link = NULL;
BinaryTree[i]->Linkb = NULL;
}
system("pause");
system("cls");
cout << "Create doubly linked list and table.\n";
first = CreateLink(BinaryTree, DataSize, DOUBLY);
PrintArray(BinaryTree, DataSize, DOUBLY);
cout << "Exchange the address of doubly linked list (after sorting).\n";
ExchangeLinkList(BinaryTree, first, DataSize, DOUBLY);
}
int CreateLink(TreePtr *BinaryTreeX, int DataSizeX, int cmd)
{
int temp, ptr, firstX, last, next;
ptr = 1;
firstX = ptr;
BinaryTreeX[firstX]->Link = 0;
if(cmd == DOUBLY)
BinaryTreeX[firstX]->Linkb = 0;
while(1)
{
ptr = ptr + 1;
if(ptr >= DataSizeX)
{
break;
} else {
if(BinaryTreeX[firstX]->Data > BinaryTreeX[ptr]->Data)
{
temp = firstX;
firstX = ptr;
BinaryTreeX[ptr]->Link = temp;
if(cmd == DOUBLY)
{
BinaryTreeX[ptr]->Linkb = BinaryTreeX[temp]->Linkb;
BinaryTreeX[temp]->Linkb = ptr;
}
} else {
last = firstX;
next = BinaryTreeX[firstX]->Link;
while(next != 0)
{
if(BinaryTreeX[next]->Data > BinaryTreeX[ptr]->Data)
{
BinaryTreeX[last]->Link = ptr;
BinaryTreeX[ptr]->Link = next;
if(cmd == DOUBLY)
{
BinaryTreeX[ptr]->Linkb = last;
BinaryTreeX[next]->Linkb = ptr;
}
break;
} else {
last = next;
next = BinaryTreeX[next]->Link;
}
}
BinaryTreeX[last]->Link = ptr;
BinaryTreeX[ptr]->Link = next;
if(cmd == DOUBLY)
BinaryTreeX[ptr]->Linkb = last;
}
}
}
return firstX;
}
void ExchangeLinkList(TreePtr *BinaryTreeX, int firstX, int DataSizeX, int cmd)
{
int ptr, scan, nfirst, tempF;
TreePtr tmp;
ptr = 1;
tmp = (TreePtr)malloc(sizeof(TreeNode));
while(ptr < DataSizeX - 1)
{
tempF = firstX;
while(firstX < ptr)
firstX = BinaryTreeX[firstX]->Link;
if(cmd == DOUBLY)
{
tmp = BinaryTreeX[ptr];
BinaryTreeX[ptr] = BinaryTreeX[firstX];
BinaryTreeX[firstX] = tmp;
scan = ptr;
do
{
if(BinaryTreeX[scan]->Link == ptr)
BinaryTreeX[scan]->Link = firstX;
if(BinaryTreeX[scan]->Linkb == ptr)
BinaryTreeX[scan]->Linkb = firstX;
scan++;
}while(scan < DataSizeX);
firstX = BinaryTreeX[ptr]->Link;
ptr++;
PrintArray(BinaryTreeX, DataSizeX, DOUBLY);
} else {
tmp = BinaryTreeX[ptr];
BinaryTreeX[ptr] = BinaryTreeX[firstX];
nfirst = BinaryTreeX[firstX]->Link;
BinaryTreeX[firstX] = tmp;
BinaryTreeX[ptr]->Link = tempF;
firstX = nfirst;
PrintArray(BinaryTreeX, DataSizeX, NULL);
ptr = ptr+1;
}
}
}
void PrintArray(TreePtr *BT, int DZ, int cmd)
{
int i;
cout << "i =";
for(i = 1; i < DZ; i++)
cout << setw(3) << "R" << i;
cout << endl;
// Output Data
cout << "Key =";
for(i = 1; i < DZ; i++)
cout << setw(3) << BT[i]->Data << " ";
cout << endl;
// Output Link
cout << "link =";
for(i = 1; i < DZ; i++)
cout <<setw(3) << BT[i]->Link << " ";
cout << endl;
if(cmd == DOUBLY)
{
// Output Linkb
cout << "linkb=";
for(i = 1; i < DZ; i++)
cout << setw(3) << BT[i]->Linkb << " ";
cout << endl;
}
cout << endl;
}
Previous in This Category: 資料結構作業八之二:WINNER TREE(SELECTION TREE)


1樓
1樓搶頭香
最資深的專業情趣團隊,把關嚴選給你最性福的情趣用品
感謝數年來網友給我們的支持與肯定
客戶最性福的滿意笑容,是我們用心服務的最大動力
〒 〒爽翻天情趣網~品質服務多元創新〒 〒
〒▉▼快上 http://www.ogc18.tw 歡迎免費加盟!