/************************************************************************************ ** Program Name : Implementation of Generalized List
** Author : Lu Jian Hua
** Time : 20xx-5-29
************************************************************************************/
#include <iostream>
using namespace std ;
class GLNode // class of node in generalized lists
{
public:
GLNode() : type(0), next(NULL) {}
int type ; // type of the node
union
{
char value ; // value of the node
GLNode *link ;
} ;
GLNode *next ; // next node
} ;
GLNode* Create_GLNode()
{
GLNode *temp = NULL ; // notice: new a structor, but not only a null pointer
cout << "Another node ? (Y/N) " ;
char c = 0 ;
cin >> c ; cout << endl ;
if (c != 'n' && c != 'N')
{
temp = new GLNode() ; // new a GLNode object
cout << "Please select :" << endl << endl
<< "1> An atom" << endl << endl
<< "2> A GLNode link " ;
char select = 0 ;
cin >> select ; cout << endl ;
if (select == '1') // an atom
{
temp->type = 0 ; // indicate the node is an atom
cout << "Please enter the value : " ;
cin >> temp->value ;
cout << endl ;
}
else // a GLNode link
{
temp->type = 1 ;
temp->link = Create_GLNode() ;
}
temp->next = Create_GLNode() ; // continue the next node...
}
return temp ;
}
/************************************************************************************ ** Program Name : Deepth_Of_GLNode
** Parameters : GLNode *front (the front pointer)
** Value Returned : int (the deepth of the generalized list)
** Details : get the deepth of a generalized list
************************************************************************************/ int Deepth_Of_GLNode(const GLNode *front) // compute the deepth of the Generalized List {
static int max_deepth = 0 ;
int deepth = 0 ;
while (front)
{
if (front->type == 0) // if type=0, deepth = 0
deepth = 0 ;
else if (front->type == 1 && front->link == NULL)// if type=1 and the link is null, deepth=1
deepth = 1 ;
else
deepth += Deepth_Of_GLNode(front->link) ;// other conditions, the same disposal
if (max_deepth < deepth)
max_deepth = deepth ;
front = front->next ;
}
return (1+max_deepth) ;
}
/********************************************************************************* ** Program Name : GLNode_Printer
** Parameters : GLNode *front (the front pointer)
** Value Returned : void
** Details : print all the nodes of the generalized list
*********************************************************************************/ void GLNode_Printer(const GLNode *front)
{
const GLNode *recent = front ;
cout << "{" ;
while (recent)
{
if (recent->type == 0)
cout << recent->value ;
else if ( recent->type == 1 && recent->link == NULL)
cout << "{}" ;
else
GLNode_Printer(recent->link) ;
if (recent->next != NULL)
cout << "," ;
recent = recent->next ;
}
cout << "}" ;
}
int main()
{
GLNode *front = Create_GLNode() ;
GLNode_Printer(front) ;
cout << "\n\nThe max deepth of the Generalized list is : " << Deepth_Of_GLNode(front) << endl << endl ;
return 0 ;
}
/******************************************************************************** *
* Notice : This Program Can Be Launched In VC6.0 Environment
*
********************************************************************************/
第二篇：数据结构学习总结-4-队列-R
1：队列的性质
1> 先进的先出（FIFO）
2> 只能从front出，只能从rear进
2：队列的两个变量
1> front
2> rear
3> max_size
3：循环队列顺序表示时，空和满的表示
1> 空：if ( front == rear)
2> 满：if ( (rear+1)%max_size = front )
4：循环时用到的模思想
Rear = (rear+1)%max_size
5：队列的两个操作
1> 出队：front = (front+1)%max_size ;
2> 入队：rear = (rear+1)%max_size ;
6：注意
在循环队列中，当队列满时，仍会有一个空间没有使用
7：--------------------implementation of circle queue ( by array )-------------------------------------------
/********************************************************************************* ** Program Name : implementation of circle queue ( by array )
** Author Name : Lu Jian Hua
** Time : 20xx-5-23
**********************************************************************************/
#include <iostream>
using namespace std ;
class Queue // class of Queue
{
public:
Queue() ;
int GetValue() const ; // get the current value of Queue int Delete() ; // out_Queue
void Append(int value) ; // In__Queue
bool IsEmpty() const ; // is empty ?
bool IsFull() const ; // is full ?
private:
int front ; // front
int rear ; // rear
enum { MAX_SIZE = 10 } ; // Notice:remember ; at the end int element[MAX_SIZE] ; // implement with array
} ;
Queue::Queue() : front(0), rear(0) {}
int Queue::GetValue() const
{
if ( IsEmpty() )
{
cout << "The queue is empty!" << endl << endl ;
return 0 ;
}
int temp = front ;
return element[++temp] ;
}
void Queue::Append(int value)
{
if ( IsFull() )
{
cout << "The queue is full!" << endl << endl ;
}
rear = (rear+1) % MAX_SIZE ;
element[rear] = value ;
}
int 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 ) ;
}
Queue* CreateQueue()
{
Queue *ptr = new Queue() ;
return ptr ;
}
int main()
{
Queue *ptr = CreateQueue() ;
while (true)
{
cout << "-------------------------------------------------" << endl
<< "1> Append" << endl
<< "2> Delete" << endl
<< "3> Get the value" << endl
<< "4> Is empty ? " << endl
<< "5> Is Full? " ;
char c = 0 ;
cin >> c ;
cout << endl ;
int value = 0 ;
switch (c)
{
case '1':
cout << "Enter the value : " ;
cin >> value ;
ptr->Append(value) ;
break ;
case '2':
cout << "The value deleted : " ;
if ( ptr->IsEmpty() )
cout << "NULL" << endl << endl ;
else
cout << ptr->Delete() << endl << endl ;
break ;
case '3':
cout << "The value getted : " ;
if ( ptr->IsEmpty() )
else
cout << ptr->GetValue() << endl << endl ;
break ;
case '4':
cout << "Is empty ? " << ( ptr->IsEmpty() ? "Yes" : "No" ) << endl << endl ; break ;
case '5':
cout << "Is full ? " << ( ptr->IsFull() ? "Yes" : "No" ) << endl << endl ; break ;
default:
break ;
}
}
return 0 ;
}
8：------------------------Implementation Of Queue By Chain--------------------------------
/********************************************************************************* ** Program Name : implementation of circle queue ( by chain )
** Author Name : Lu Jian Hua
** Time : 20xx-5-23
**********************************************************************************/
#include <iostream>
using namespace std ;
class Node
{
public:
Node() : data(0), next(NULL) {}
int data ;
Node *next ;
} ;
class Queue // class of Queue
{
public:
Queue() ;
Node* GetValue() const ; // get the current value of Queue void Delete() ; // out_Queue
void Append(int value) ; // In__Queue
void Cleaner() ; // cleaner of Queue bool IsEmpty() const ; // is empty ?
bool IsFull() const ; // is full ?
private:
Node* front ; // front
Node* rear ; // rear
} ;
Queue::Queue() : front(NULL), rear(NULL) {}
Node* Queue::GetValue() const
{
if ( IsEmpty() )
{
cout << "The queue is empty!" << endl << endl ;
return 0 ;
}
return front ;
}
void Queue::Append(int value)
{
Node *temp = new Node() ;
temp->data = value ;
if (front == NULL) // no element in the queue {
front = temp ;
rear = front ;
rear->next = NULL ;
}
else
{
rear->next = temp ;
rear = temp ;
rear->next = NULL ;
}
}
void Queue::Delete()
{
if ( IsEmpty() )
{
cout << "The queue is empty!" << endl << endl ;
return ;
}
Node *record = front ;
front = front->next ;
delete record ;
cout << "The specific node has beend deleted!" << endl << endl ;
}
void Queue::Cleaner()
{
while (front)
{
Node *record = front->next ;
delete front ;
front = record ;
}
cout << "Cleaner has done it's work...\n\n" ;
}
bool Queue::IsEmpty() const
{
return (front == NULL) ;
}
bool Queue::IsFull() const
{
return ( false ) ; // never full until no enough memory accommodated }
Queue* CreateQueue()
{
Queue *ptr = new Queue() ;
return ptr ;
}
int main()
{
Queue *ptr = CreateQueue() ;
while (true)
{
cout << "-------------------------------------------------" << endl
<< "1> Append" << endl
<< "2> Delete" << endl
<< "3> Get the value" << endl
<< "4> Is empty ? " << endl
<< "5> Is Full? " << endl
<< "6> Release the queue? " ;
char c = 0 ;
cin >> c ;
cout << endl ;
int value = 0 ;
} } return 0 ; switch (c) { case '1': cout << "Enter the value : " ; cin >> value ; ptr->Append(value) ; break ; case '2': ptr->Delete() ; break ; case '3': cout << "The value getted : " ; if ( ptr->IsEmpty() ) cout << "NULL" << endl << endl ; else cout << (ptr->GetValue())->data << endl << endl ; break ; case '4': cout << "Is empty ? " << ( ptr->IsEmpty() ? "Yes" : "No" ) << endl << endl ; break ; case '5': cout << "Is full ? " << ( ptr->IsFull() ? "Yes" : "No" ) << endl << endl ; break ; case '6': ptr->Cleaner() ; break ; default: break ; }