June 1, 2009

資料結構作業九:(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; 
}

Today's Visitors: 0 Total Visitors: 116
Personal Category: 台北科技大學 Topic: learning / education / advanced edu.
Previous in This Category: 資料結構作業八之二:WINNER TREE(SELECTION TREE)  
[Trackback URL]

Reply
  • 1樓

    1樓搶頭香

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

  • 爽翻天 at February 14, 2010 09:10 PM comment | Homepage
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