数据结构学习总结－5－排序－R Time:2007-9-9

============================ 选择排序法 ===============================

#include <iostream>

using namespace std ;

const int MAX_SIZE = 20;

void Select_Sort(int *a, const int SIZE) ;

int main()

{

int a[MAX_SIZE] = { 0 } ;

cout << "-------------- Selection Sort ----------------------" << endl << endl

<< "Please Enter The Numbers : " << endl << endl ;

for (int i=0; i<MAX_SIZE; i++)

{

cout << "a[" << i << "] : " ;

cin >> a[i] ;

}

cout << "Before Sorting : " ;

for (i=0; i<MAX_SIZE; i++)

cout << a[i] << " " ;

Select_Sort(a, MAX_SIZE) ;

cout << endl << endl ;

cout << "After Sorting : " ;

for (i=0; i<MAX_SIZE; i++)

cout << a[i] << " " ;

cout << endl << endl ;

cout << "-------------- Selection Sort ----------------------" << endl << endl ;

return 0 ;

}

void Select_Sort(int *a, const int SIZE)

{

int temp = 0 ;

for (int i=0; i <= SIZE-2; i++) // Outer Loop : 0 ~ SIZE-2

{

for (int j = i+1; j <= SIZE-1; j++) // Inner Loop : i+1 ~ SIZE-1

{

if (a[i] > a[j])

{

temp = a[i] ;

a[i] = a[j] ;

a[j] = temp ;

}

}

}

}

数据结构学习总结－5－排序－R Time:2007-9-9

============================ 冒泡排序法 ===============================

#include <iostream>

using namespace std ;

const int MAX_SIZE = 10;

void Bubble_Sort(int *a, const int SIZE) ;

int main()

{

int a[MAX_SIZE] = { 0 } ;

cout << "-------------- Bubble Sort ----------------------" << endl << endl

<< "Please Enter The Numbers : " << endl << endl ;

for (int i=0; i<MAX_SIZE; i++)

{

cout << "a[" << i << "] : " ;

cin >> a[i] ;

}

cout << "Before Sorting : " ;

for (i=0; i<MAX_SIZE; i++)

cout << a[i] << " " ;

Bubble_Sort(a, MAX_SIZE) ;

cout << endl << endl ;

cout << "After Sorting : " ;

for (i=0; i<MAX_SIZE; i++)

cout << a[i] << " " ;

cout << endl << endl ;

cout << "-------------- Selection Sort ----------------------" << endl << endl ;

return 0 ;

}

void Bubble_Sort(int *a, const int SIZE)

{

int temp = 0 ;

for (int i=SIZE-1; i>=1; i--) // I : SIZE-1 ~ 1

{

for (int j=0; j<=i-1; j++) // J : 0 ~ I-1

{

if (a[j] > a[j+1])

{

temp = a[j] ;

a[j] = a[j+1] ;

a[j+1] = temp ;

}

}

}

}

数据结构学习总结－5－排序－R Time:2007-9-9

============================ 插入排序法 ===============================

#include <iostream>

using namespace std ;

const int MAX_SIZE = 10;

void Insertion_Sort(int *a, const int SIZE) ;

int main()

{

int a[MAX_SIZE] = { 0 } ;

cout << "-------------- Bubble Sort ----------------------" << endl << endl

<< "Please Enter The Numbers : " << endl << endl ;

for (int i=0; i<MAX_SIZE; i++)

{

cout << "a[" << i << "] : " ;

cin >> a[i] ;

}

cout << endl ;

cout << "Before Sorting : " ;

for (i=0; i<MAX_SIZE; i++)

cout << a[i] << " " ;

Insertion_Sort(a, MAX_SIZE) ;

cout << endl << endl ;

cout << "After Sorting : " ;

for (i=0; i<MAX_SIZE; i++)

cout << a[i] << " " ;

cout << endl << endl ;

cout << "-------------- Selection Sort ----------------------" << endl << endl ;

return 0 ;

}

void Insertion_Sort(int *a, const int SIZE)

{

int temp = 0 ;

for (int i=1; i<=SIZE-1; i++) // Outer : SIZE-1 ~ 1

{

temp = a[i] ;

for (int j=0; j<=i-1; j++) // Inner : 0 ~ I-1

{

if (a[j] > a[i]) // if find the number larger than a[i], then moving...and insert it {

for (int k=i; k>=j+1; k--)

a[k] = a[k-1] ;

a[j] = temp ;

}

}

}

}

数据结构学习总结－5－排序－R Time:2007-9-9

============================ 二叉树排序法 ===============================

/************************************************************************************ ** Program Name : Binary Search Tree

** Author : Lu Jian Hua

** Time : 2007-6-2

************************************************************************************/

#include <iostream>

using namespace std ;

const int LEFT = 0 ;

const int RIGHT = 1 ;

/*-------------------------------------Class Node ( Node Of BTree )----------------START--------------------*/ class Node // Node of tree

{

public:

char c ; // data portion

Node *L_Child ; // left child

Node *R_Child ; // right child

Node *next ;

Node() : c(0), L_Child(NULL), R_Child(NULL) {}

Node(char ch) : c(ch), L_Child(NULL), R_Child(NULL), next(NULL) {}

} ;

/*-------------------------------------Class Node ( Node Of BTree )-----------------END---------------------*/

/*--------------------------------------Class Stack---------------------------------START-------------------*/ class Stack

{

public:

Stack(int max_size) ; // constructor

Node* GetTopValue() const ; // get the top value of stack

void Push(Node* value) ; // push

Node* Pop() ; // pop

void Init() ; // initialize the stack

bool IsEmpty() ; // is empty ?

private:

enum { MAX_SIZE = 100 } ;

int top ;

Node* element[MAX_SIZE] ;

} ;

Stack::Stack(int max_size) : top(-1) {}

Node* Stack::GetTopValue() const

{

if (top < 0)

{

return 0 ;

}

return element[top] ;

数据结构学习总结－5－排序－R Time:2007-9-9

}

void Stack::Push(Node* value) // Operation:push a element into stack {

if (top >= MAX_SIZE-1)

{

cout << "The stack is full! " << endl << endl ;

return ;

}

top++ ; // 1> move the top pointer

element[top] = value ; // 2> infill the space top pointer directing }

Node* Stack::Pop() // Operation:Pop a element from stack {

if (top < 0)

{

return 0 ;

}

Node* temp = element[top] ; // 1> get the value

top-- ; // 2> move the top pointer

return temp ;

}

void Stack::Init()

{

top = -1 ;

}

bool Stack::IsEmpty() // test if the stack is empty ?

{

return ( top < 0 ) ;

}

/*--------------------------------------Class Stack---------------------------------END---------------------*/

/*--------------------------------------Class Queue---------------------------------START-------------------*/

class Queue // class of Queue

{

public:

Queue() ;

Node* GetValue() const ; // get the current value of Queue

Node* Delete() ; // out_Queue

void Append(Node* value) ; // In__Queue

bool IsEmpty() const ; // is empty ?

bool IsFull() const ; // is full ?

private:

int front ; // front

int rear ; // rear

enum { MAX_SIZE = 500 } ; // Notice:remember ; at the end

Node* element[MAX_SIZE] ; // implement with array

} ;

数据结构学习总结－5－排序－R Time:2007-9-9

Queue::Queue() : front(0), rear(0) {}

Node* Queue::GetValue() const

{

if ( IsEmpty() )

{

cout << "The queue is empty!" << endl << endl ;

return 0 ;

}

int temp = front ;

return element[++temp] ;

}

void Queue::Append(Node* value)

{

if ( IsFull() )

{

cout << "The queue is full!" << endl << endl ;

return ;

}

rear = (rear+1) % MAX_SIZE ;

element[rear] = value ;

}

Node* Queue::Delete()

{

if ( IsEmpty() )

{

cout << "The queue is empty!" << endl << endl ;

return 0 ;

}

//return element[(++front) % MAX_SIZE] ; // different from the next sentence?? front = (front+1) % MAX_SIZE ;

return element[front] ;

}

bool Queue::IsEmpty() const

{

return (rear == front) ;

}

bool Queue::IsFull() const

{

return ( (rear+1) % MAX_SIZE == front ) ;

}

/*--------------------------------------Class Queue---------------------------------END---------------------*/

/*--------------------------------------GLOBAL VARIABLE-----------------------------START-------------------*/

数据结构学习总结－5－排序－R Time:2007-9-9

Node* TAG = (Node*)10000 ;

const int ROW = 80 ;

const int COL = 80 ;

char a[ROW][COL] ;

Node *RFPrint = NULL ; // root_for_print

/*--------------------------------------GLOBAL VARIABLE-----------------------------END---------------------*/

void operator <<(ostream os, Node node) //-------------- output a node directly ---------------------- {

os << node.c << " " ;

}

/*--------------------------------------------------------------------------------------------------------

** Function Name : Add_New_Node

** Parameters : Node **root

** : Node *temp (any node)

** Return Value : void

** Details : add a new node into a binary search tree

**--------------------------------------------------------------------------------------------------------*/

void Add_New_Node(Node **root, Node *temp)

{

if (*root == NULL)

{

*root = temp ;

return ;

}

if ( temp->c < (*root)->c )

root = &( (*root)->L_Child ) ;

else

root = &( (*root)->R_Child ) ;

Add_New_Node(root, temp) ;

}

/*--------------------------------------------------------------------------------------------------------

** Function Name : Print

** Parameters : Node *root (the root of a binary tree)

** int x (x coordinate of the certain node)

** int y (y coordinate of the certain node)

** Return Value : void

** Details : print the architecture to a table

**--------------------------------------------------------------------------------------------------------*/

void Print(Node *r, int x, int y) // r==root, a=arry, x=coordinate x, y=coordinate y

{

Queue queue ;

static Queue *q = &queue ;

if (r == NULL)

return ;

q->Append(r) ;

while (q->IsEmpty() == false)

{

Node *temp = q->Delete() ;

a[x][y] = temp->c ;

数据结构学习总结－5－排序－R Time:2007-9-9

if (temp->L_Child)

a[x+1][y-1] = '/' ;

if (temp->R_Child)

a[x+1][y+1] = '\\' ;

if (temp->L_Child)

q->Append(temp->L_Child) ;

if (temp->R_Child)

q->Append(temp->R_Child) ;

}

}

/*-------------------------------------------------------------------------------------------------------- ** Function Name : Get_Node_Rank

** Parameters : Node *root (the root of a binary tree)

** Node *recent (the recent node to be disposed) ** Return Value : void

** Details : get the rank of a certain node in the binary tree

** root : 1

** .... : 2

** .... : 3

** .... : 4

** ........

**--------------------------------------------------------------------------------------------------------*/ int Get_Node_Rank(Node *root, Node *recent)

{

bool found = false ;

int count = 0 ;

Stack s(100) ; // the stack may be used

while (root)

{

s.Push(root) ;

if ( s.GetTopValue() == recent )

{

found = true ;

break ;

}

else

root = root->L_Child ;

if (root == NULL)

{

Node *temp = s.GetTopValue() ;

s.Push(TAG) ;

root = temp->R_Child ;

if (root == NULL)

{

while (true)

{

if (s.GetTopValue() == TAG)

{

s.Pop() ;

s.Pop() ;

}

数据结构学习总结－5－排序－R Time:2007-9-9

else

{

if (s.GetTopValue() == NULL)

cout << "Null Pointer Exists..." << endl << endl ; root = ( s.GetTopValue()) ->R_Child ;

if (root == NULL)

{

s.Pop() ;

continue ;

}

else

{

s.Push(TAG) ;

break ;

}

}

}

}

}

}

if (found)

{

while (s.IsEmpty() == false)

{

if (s.Pop() != TAG)

count ++ ;

}

}

else

return 0 ;

return count ;

}

/*--------------------------------------------------------------------------------------------------------

** Function Name : Print_Tree

** Parameters : Node *root (the root of a binary tree)

** int x (x coordinate of the certain node)

** int y (y coordinate of the certain node)

** Return Value : void

** Details : print the architecture to the screen(through a table)

**--------------------------------------------------------------------------------------------------------*/

void Print_Tree(Node *r, int x, int y)

{

int num = ( Get_Node_Rank(RFPrint, r) <= 7 ? (8-Get_Node_Rank(RFPrint,r)) : 1 ) ; a[x][y] = r->c ;

for (int i=1; i<=num; i++)

{

if (r->L_Child)

a[x+i][y-i] = '/' ;

if (r->R_Child)

a[x+i][y+i] = '\\' ;

}

if (r->L_Child)

数据结构学习总结－5－排序－R Time:2007-9-9

{

Print_Tree(r->L_Child, x+(num+1), y-(num+1)) ;

}

if (r->R_Child)

{

Print_Tree(r->R_Child, x+(num+1), y+(num+1)) ;

}

}

/*-------------------------------------------------------------------------------------------------------- ** Function Name : Init_Table

** Parameters : NULL

** Return Value : void

** Details : initialize all the elements of the table with NULL character

**--------------------------------------------------------------------------------------------------------*/ void Init_Table()

{

for (int i=0; i<ROW; i++) // initialize the char table for (int j=0; j<COL; j++)

a[i][j] = ' ' ;

}

/*-------------------------------------------------------------------------------------------------------- ** Function Name : Print_Table

** Parameters : NULL

** Return Value : void

** Details : print the table to the screen

**--------------------------------------------------------------------------------------------------------*/ void Print_Table()

{

for (int i=0; i<ROW; i++) // print the tree for (int j=0; j<COL; j++)

cout << a[i][j] ;

}

/*-------------------------------------------------------------------------------------------------------- ** Function Name : Build_BSTree

** Parameters : Node **root

** Return Value : void

** Details : Build a binary search tree

**--------------------------------------------------------------------------------------------------------*/ void Build_BSTree(Node **root)

{

while (true)

{

char c = 0 ;

cout << "Another Node ? (Y/N) " ;

cin >> c;

if (c != 'n' && c != 'N')

{

Node *temp = new Node() ;

cout << "Please Enter The Value : " ;

cin >> temp->c ;

temp->L_Child = temp->R_Child = NULL ;

Add_New_Node(root, temp) ;

}

数据结构学习总结－5－排序－R Time:2007-9-9

else

break ;

}

}

int main()

{

Node *root = NULL ;

Build_BSTree(&root) ; // build the Binary Search Tree

/*---------------------------------- Print The Tree ----------------------------------*/

Init_Table() ;

RFPrint = root ;

Print_Tree(root, 0, 40) ;

Print_Table() ;

/*---------------------------------- Print The Tree ----------------------------------*/

return 0 ;

}