数据结构与算法(2) -- love_you_forever-- 编程爱好者博客

16,链栈(模板编写,无主函数) template<class T> struct Node { T data; Node<T> *next; }; template<class T> class LinkStack { private: Node<T> *top; public: LinkStack() { top=NULL; } ~LinkStack(); bool IsEmpty() const { return top==NULL; } void Push(const T& x); T Pop(); T GetTop() const; }; template<class T> LinkStack<T>::~LinkStack() { Node<T> *p; while(top) { p=top; top=top->next; delete p; } } template<class T> void LinkStack<T>::Push(const T& x) { Node<T> *s=new Node<T>; s->data=x; s->next=top; top=s; } template<class T> T LinkStack<T>::Pop() { if(IsEmpty()) { cerr<<"堆栈空！";exit(1); } T temp=top->data; Node<T> *p=top; top=top->next; delete p; return temp; } template<class T> T LinkStack<T>::GetTop() const { if(IsEmpty()) { cerr<<"堆栈空！";exit(1); } return top->data; } -------------------------------------------------------------------------------- 17,队列（数组存储的循环队列） template<class T> class Queue { private: int front, rear; int MaxSize; T *data; public: Queue(int size=100); ~Queue() { delete [] data; } bool IsEmpty() const { return front == rear; } bool IsFull() const { return (rear+1) % MaxSize == front; } void Add(const T& x); void Delete(T& x); T First() const; }; template<class T> Queue<T>::Queue(int size) { MaxSize = size+1; data = new T[MaxSize]; front = rear = 0; } template<class T> void Queue<T>::Add(const T& x) { if(IsFull()) { cerr<<"队列满！"; exit(1); } data[rear] = x; rear = (rear+1) % MaxSize; } template<class T> void Queue<T>::Delete(T& x) { if(IsEmpty()) { cerr<<"队列空！"; exit(1); } x = data[front]; front = (front+1) % MaxSize; } template<class T> T Queue<T>::First() const { if(IsEmpty()) { cerr<<"队列空！"; exit(1); } return data[front]; } -------------------------------------------------------------------------------- 18,链式队列(模板编写,无主函数) template<class T> struct Node { T data; Node<T> *next; }; template<class T> class LinkQueue { private: Node<T> *front, *rear; public: LinkQueue(); ~LinkQueue(); bool IsEmpty() const { return front == NULL; } void Add(const T& x); void Delete(T& x); T First() const; }; template<class T> LinkQueue<T>::~LinkQueue(int size) { Node<T> *p; while(front) { p = front; front = front->next; delete p; } } template<class T> void LinkQueue<T>::Add(const T& x) { Node<T> *s = new Node<T>; s->data = x; s->next = NULL; if(front == NULL) { rear->next = s; r = s; } else { front = s; r = s; } } template<class T> void LinkQueue<T>::Delete(T& x) { if(IsEmpty()) { cerr<<"队列空！";exit(1); } x = front->data; Node<T> *p = front; front = front->next; delete p; if(front == NULL) rear = NULL; } template<class T> T LinkQueue<T>::First() const { if(IsEmpty()) { cerr<<"队列空！";exit(1); } return front->data; } -------------------------------------------------------------------------------- 19,比较完整的二叉检索树(模板编写,有主函数,编译通过) #include<iostream>#include<cstdlib>#include"Stack.h"#include"Queue.h"using namespace std;template<class type>class treenode{public: type data; treenode<type> *leftptr; treenode<type> *rightptr; treenode(type);};template<class type>treenode<type>::treenode(type _data):data(_data),leftptr(0),rightptr(0){}template<class type>class tree{private: treenode<type> *root; treenode<type> *getnew(type); void Tpreorderhelper(treenode<type> *); void Tinorderhelper(treenode<type> *); void Tpostorderhelper(treenode<type> *); int Height(treenode<type> *); int Leaf(treenode<type> *); int Size(treenode<type> *); void Change(treenode<type> *); void Swap(treenode<type> *,treenode<type> *); void MaxValuehelper(treenode<type> *,type &);public: tree(); void create(); void insert(treenode<type> *&,type); void preorder();//非递归写法,前序遍历; void inorder();//非递归写法,中序遍历,排序算法; void postorder();//非递归写法,后序遍历; void Tpreorder() {Tpreorderhelper(root);}//递归写法,前序遍历; void Tinorder() {Tinorderhelper(root);}//递归写法,中序遍历; void Tpostorder(){Tpostorderhelper(root);}//递归写法,后序遍历; int Height() { return Height(root); } //二叉树高度 int Leaf() { return Leaf(root); } //叶子结点数 int Size() { return Size(root); } //结点数 void Change(){ Change(root); }//交换左右子树; type MaxValue();//返回树的最大值; void levelprint();//按层遍历};template<class type>type tree<type>::MaxValue(){ type temp=root->data; MaxValuehelper(root,temp); return temp;}template<class type>void tree<type>::MaxValuehelper(treenode<type> *_root,type &temp){ if(_root!=0) { if(temp<_root->data) temp=_root->data; MaxValuehelper(_root->leftptr,temp); MaxValuehelper(_root->rightptr,temp); }}template<class type>int tree<type>::Height(treenode<type> *p){ if(p==0) return 0; return Height(p->leftptr)+1>Height(p->rightptr)+1 ? Height(p->leftptr)+1:Height(p->rightptr)+1;}template<class type>int tree<type>::Leaf(treenode<type> *p){ if(p==0) return 0; if(p->leftptr==0 && p->rightptr==0) return 1; return Leaf(p->leftptr)+Leaf(p->rightptr);}template<class type>int tree<type>::Size(treenode<type> *p){ if(p==0) return 0; return Size(p->leftptr)+Size(p->rightptr)+1;}template<class type>void Swap(treenode<type> *left,treenode<type> *right){ treenode<type> *temp=left; left=right; right=temp;temp=0;}template<class type>void tree<type>::Change(treenode<type> *p){ if(p==0) return; if(p->leftptr==0 && p->rightptr==0) return; swap(p->leftptr,p->rightptr); Change(p->leftptr); Change(p->rightptr);}template<class type>void tree<type>::Tpreorderhelper(treenode<type> *p){ if(p!=0) { cout<<" "<<p->data; Tpreorderhelper(p->leftptr); Tpreorderhelper(p->rightptr); }}template<class type>void tree<type>::Tinorderhelper(treenode<type> *p){ if(p!=0) { Tinorderhelper(p->leftptr); cout<<" "<<p->data; Tinorderhelper(p->rightptr); }}template<class type>void tree<type>::Tpostorderhelper(treenode<type> *p){ if(p!=0) { Tpostorderhelper(p->leftptr); Tpostorderhelper(p->rightptr); cout<<" "<<p->data; }}template<class type>tree<type>::tree():root(0){}template<class type>void tree<type>::create(){ cout<<"start to build the tree:"<<endl;type value; for(int i=0;i<10;i++) { cout<<"integer the value"<<i+1<<":"; cin>>value; insert(root,value); }}template<class type>treenode<type> *tree<type>::getnew(type _data){ treenode<type> *cur=new treenode<type>(_data); return cur;}template<class type>void tree<type>::insert(treenode<type> *&_root,type _data){ treenode<type> *temp=getnew(_data); if(_root==0) _root=temp; else { if(_data<=_root->data) insert(_root->leftptr,_data); else insert(_root->rightptr,_data); }}template<class type>void tree<type>::preorder(){ treenode<type> *p=root;cout<<"Preorder:"; Stack<treenode<type> *> q;treenode<type> *temp; while(p||!q.IsEmpty()) { if(p) { q.Push(p); cout<<" "<<p->data; p=p->leftptr; } else { q.Del(temp); p=temp->rightptr; } }}template<class type>void tree<type>::inorder(){ treenode<type> *p=root;cout<<"Inorder:"; Stack<treenode<type> *> q;treenode<type> *temp; while(p||!q.IsEmpty()) { if(p) { q.Push(p); p=p->leftptr; } else { q.Del(temp); cout<<" "<<temp->data; p=temp->rightptr; } }}template<class type>void tree<type>::postorder(){ treenode<type> *p=root;cout<<"Postorder:"; Stack<treenode<type> *> q; Stack<int> t;int n; treenode<type> *temp; while(p||!q.IsEmpty()) { if(p) { q.Push(p); t.Push(1); p=p->leftptr; } else { q.Del(temp); t.Del(n); if(n==1) { q.Push(temp); t.Push(2); p=temp->rightptr; } else { cout<<" "<<temp->data; p=0; } } }}template<class type>void tree<type>::levelprint(){ cout<<"LevelPrint:"; treenode<type> *p=root;treenode<type> *temp; if(p==0)return; Queue<treenode<type> *> q;q.In(p); while(!q.IsEmpty()) { q.Out(temp); cout<<" "<<temp->data; if(temp->leftptr)q.In(temp->leftptr); if(temp->rightptr)q.In(temp->rightptr); }} int main(){ tree<int> first; first.create(); first.preorder();cout<<endl; first.inorder();cout<<endl; first.postorder();cout<<endl; first.levelprint();cout<<endl; cout<<"The Tree Hight is:"<<first.Height()<<endl; cout<<"The Tree Leaves is:"<<first.Leaf()<<endl; cout<<"The Tree Nodes is:"<<first.Size()<<endl; cout<<"The Max Value is:"<<first.MaxValue()<<endl; system("pause"); return 0;} 此二叉树中用到的栈: //**********************************// #include<iostream>using namespace std;template<class type>class Stacknode{public: type data; Stacknode<type> *next; Stacknode(type _data):data(_data),next(0){}};template<class type>class Stack{private: Stacknode<type> *top; Stacknode<type> *getnew(type);public: Stack():top(0){} void Push(type); void Del(type &); bool IsEmpty();};template<class type>bool Stack<type>::IsEmpty(){ return top==0;}template<class type>Stacknode<type> *Stack<type>::getnew(type _data){ Stacknode<type> *cur=new Stacknode<type>(_data); return cur;}template<class type>void Stack<type>::Push(type _data){ Stacknode<type> *temp=getnew(_data); if(top==0) top=temp; else { temp->next=top; top=temp; }}template<class type>void Stack<type>::Del(type &temp){ Stacknode<type> *cur=top; if(IsEmpty()) return; else { temp=top->data; top=top->next; delete cur; }} 此二叉树中用到的队列: //***************************************// #include<iostream>using namespace std;template<class type>class Queuenode{public: type data; Queuenode<type> *next; Queuenode(type _data):data(_data),next(0){}};template<class type>class Queue{private: Queuenode<type> *front; Queuenode<type> *rear; Queuenode<type> *getnew(type);public: Queue():front(0),rear(0){} void In(type); void Out(type &); bool IsEmpty();};template<class type>bool Queue<type>::IsEmpty(){ return front==0;}template<class type>Queuenode<type> *Queue<type>::getnew(type _data){ Queuenode<type> *cur=new Queuenode<type>(_data); return cur;}template<class type>void Queue<type>::In(type _data){ Queuenode<type> *temp=getnew(_data); if(front==0) { rear=temp;front=rear;} else { rear->next=temp; rear=rear->next; }}template<class type>void Queue<type>::Out(type &temp){ Queuenode<type> *cur=front; if(IsEmpty()) return; else { temp=front->data; front=front->next; delete cur; }} --------------------------------------------------------------------------------大概就这么多吧,可能还有些好的写法没发上来,如果大家有什么好算法,都可以贴上来.!希望这些对大家能有些帮助! -------------------------------------------------------------------------------- ******八皇后问题****** #include<iostream>#include<cstdlib>using namespace std;class Queen{ private: int k; bool x[9];//1...8 bool a[15];//0...14 bool b[17];//2...16 int s[9][9]; public: Queen(); void test(int);};Queen::Queen(){ for(int i=1;i<9;i++) x[ i]=true; for(int i=0;i<15;i++) a[ i]=true; for(int i=2;i<17;i++) b[ i]=true; for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) s[ i][ j]=0; k=0;}void Queen::test(int i){ for(int j=1;j<=8;j++) { if(x[ j]==true && a[ i-j+7]==true && b[ i+j]==true) { s[ i][ j]=1;k++; x[ j]=false; a[ i-j+7]=false; b[ i+j]=false; if(i<8) test(i+1); if(i==8) { cout<<"the result is:"<<endl; for(int ci=1;ci<=8;ci++) { for(int cj=1;cj<=8;cj++) cout<<" "<<s[ ci][cj]; cout<<endl; } return; } x[ j]=true; a[ i-j+7]=true; b[ i+j]=true; s[ i][ j]=0; } }}int main(){ Queen first; first.test(1); system("pause"); return 0;} 下面是我在网上找的，也许说的更好！八皇后问题：〖问题描述〗在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。〖问题分析〗(聿怀中学吕思博)这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：1、冲突。包括行、列、两条对角线：（1）列：规定每一列放一个皇后，不会造成列上的冲突；（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2、数据结构。（1）解数组A。A[I]表示第I个皇后放置的列；范围：1..8（2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：1..8（3）对角线冲突标记数组C、D。C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：2..16 〖算法流程〗１、数据初始化。２、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于０（未被占领）:如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。３、当n>8时，便一一打印出结果。〖优点〗逐一测试标准答案，不会有漏网之鱼。 Pascal实现： program tt;var a:array [1..8] of integer; b,c,d:array [-7..16] of integer; t,i,j,k:integer;procedure print;begin t:=t+1; write(t,' '); for k:=1 to 8 do write(a[k],' '); writeln;end; procedure try(i:integer);var j:integer;begin for j:=1 to 8 do {每个皇后都有8种可能位置} if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判断位置是否冲突} begin a[i]:=j; {摆放皇后} b[j]:=1; {宣布占领第J行} c[i+j]:=1; {占领两个对角线} d[i-j]:=1; if i<8 then try(i+1) {8个皇后没有摆完，递归摆放下一皇后} else print; {完成任务，打印结果} b[j]:=0; {回溯} c[i+j]:=0; d[i-j]:=0; end;end;begin for k:=-7 to 16 do {数据初始化} begin b[k]:=0; c[k]:=0; d[k]:=0; end; try(1);{从第1个皇后开始放置}end. java实现： /** ８皇后问题：** 问题描述：* 在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相冲突*（在每一横列，竖列，斜列只有一个皇后）。** 数据表示：* 用一个 8 位的 8 进制数表示棋盘上皇后的位置：* 比如：45615353 表示：* 第0列皇后在第4个位置* 第1列皇后在第5个位置* 第2列皇后在第6个位置* 。。。* 第7列皇后在第3个位置** 循环变量从 00000000 加到 77777777 （8进制数）的过程，就遍历了皇后所有的情况* 程序中用八进制数用一个一维数组 data[] 表示** 检测冲突：* 横列冲突：data[i] == data[j]* 斜列冲突：(data[i]+i) == (data[j]+j) 或者 (data[i]-i) == (data[j]-j)** 好处：* 采用循环，而不是递规，系统资源占有少* 可计算 n 皇后问题* 把问题线性化处理，可以把问题分块，在分布式环境下用多台计算机一起算。** ToDo：* 枚举部分还可以进行优化，多加些判断条件速度可以更快。* 输出部分可以修改成棋盘形式的输出** @author cinc 2002-09-11**/ public class Queen { int size; int resultCount; public void compute ( int size ) { this.size = size; resultCount = 0; int data[] = new int[size]; int count; // 所有可能的情况个数 int i,j; // 计算所有可能的情况的个数 count = 1; for ( i=0 ; i<size ; i++ ) { count = count * size; } // 对每一个可能的情况 for ( i=0 ; i<count ; i++ ) { // 计算这种情况下的棋盘上皇后的摆放位置，用 8 进制数表示 // 此处可优化 int temp = i; for ( j=0 ; j<size ; j++ ) { data [j] = temp % size; temp = temp / size; } // 测试这种情况是否可行，如果可以，输出 if ( test(data) ) output( data ); } } /* * 测试这种情况皇后的排列是否可行 * */ public boolean test( int[] data ) { int i,j; for ( i=0 ; i<size ; i++ ) { for ( j=i+1 ; j<size ; j++ ) { // 测试是否在同一排 if ( data[i] == data[j] ) return false; // 测试是否在一斜线 if ( (data[i]+i) == (data[j]+j) ) return false; // 测试是否在一反斜线 if ( (data[i]-i) == (data[j]-j) ) return false; } } return true; } /* * 输出某种情况下皇后的坐标 * */ public void output ( int[] data ) { int i; System.out.print ( ++resultCount + ": " ); for ( i=0 ; i<size ; i++ ) { System.out.print ( "(" + i + "," + data[i] + ") " ); } System.out.println (); } public static void main(String args[]) { (new Queen()).compute( 8 ); }} C实现： /*八皇后问题：问题提出： 8×8的棋盘上放置8个皇后，在同一横线、竖线、对角线上会产生冲突，求不产生冲突即8个皇后都安全的放置方法。这里改变NCOUNT即可以求出n皇后的n×n棋盘的放置方法张可彦： kyany@sina.com*/#include "stdio.h" #define NCOUNT 8int nArray[NCOUNT][NCOUNT]; // 判断一个点是否是安全点bool IsSafe(int i,int j){int x=i,y=j;while(1){x -= 1;if( x<0 )break;y -= 1;if( y<0)break;if( nArray[x][y] == 1)return false;}x=i;y=j;while(1){x += 1;if( x>NCOUNT-1 )break;y += 1;if( y >NCOUNT-1 )break;if( nArray[x][y] == 1)return false;}x=i;y=j;while(1){x -=1;if( x<0 )break;y +=1;if( y>NCOUNT-1 )break;if( nArray[x][y] == 1)return false;}x=i;y=j;while(1){x +=1;if( x>NCOUNT-1 )break;y-=1;if( y<0 )break;if( nArray[x][y] == 1)return false;}x=i;y=j;while(1){x -=1;if( x<0 )break;if( nArray[x][y] == 1)return false;}x=i;y=j;while(1){x +=1;if( x>NCOUNT-1 )break;if( nArray[x][y] == 1)return false;}x=i;y=j;while(1){y -=1;if( y<0 )break;if( nArray[x][y] == 1)return false;}x=i;y=j;while(1){y +=1;if( y>NCOUNT-1 )break;if( nArray[x][y] == 1)return false;}return true;} void main(){int nVe=-1,nHo=0;bool bRetry = false;int nSol = 0; // 清除棋盘for(int i=0;i<NCOUNT;i++){for( int j=0;j<NCOUNT;j++)nArray[i][j] = 0;} while(1){nVe += 1;if( nVe>NCOUNT-1){// 棋盘放满，打印当前棋盘上棋子位置nSol++;printf("Sol %d: ",nSol);for(int i=0;i<NCOUNT;i++){for( int j=0;j<NCOUNT;j++)if( nArray[i][j]==1)printf("(%d,%d) ",i,j);}printf("\r\n");// 回溯查找下一个可行方案nVe -= 2;bRetry = true;continue;} int nFill = 0;if( bRetry ){ // 回溯计算bRetry = false;for( i=0;i<NCOUNT;i++){// 得到棋子的位置if( nArray[nVe][i] == 1){nArray[nVe][i] = 0;nFill = i;break;}}if( nFill == NCOUNT-1){// 棋子在当前行已经是最后的位置// 如果是第一行，算法结束if( nVe == 0)return;// 否则回溯nVe -= 2;bRetry = true;continue; }// 从当前位置之后查找一个安全点nFill += 1;} bool bFilled = false;for( i=nFill;i<NCOUNT;i++){// 当前行查找一个安全点if( IsSafe(nVe,i)){bFilled = true;nArray[nVe][i] = 1;break;}}// 找不到安全点，回溯if( !bFilled ){nVe -= 2;bRetry = true;}}}

博客介绍

正文

数据结构与算法(2)2006-01-28 17:21:00

评论