Joseph问题C++程序（可在nlgn时间求解并显示）

/* 求Joseph排列 先建立具有n个结点的平衡二叉树，在建树的过程中记录每个结点的次序，然后用求余运算 计算所查找的结点的位置，输出该结点元素，并删除，如此直到输出最后一个元素。由于向平 衡二叉树中插入的元素本身就是单调递增有序的，所以在插入时只需用到平衡二叉树的RR型调 整操作即可。 */ #include <iostream.h> #include <sys/timeb.h> #include <stdlib.h> int y; template <class T> class BSTree; template <class T> struct TNode /* 平衡二叉树的结点类型定义 */ { private: TNode <T> *left; /* 左子树指针 */ TNode <T> *right; /* 右子树指针 */ public: int balance; /* 平衡因子 */ int lsize; /* lsize域表示该结点的左子树的结点总数加1 */ T data; /* 数据域 */ friend class BSTree <T>; TNode() { left = NULL; right = NULL; balance = 0; lsize = 1; } /* 构造函数 */ TNode(T item, TNode <T> *left1, TNode <T> *right1) { balance = 0; data = item; lsize = 1; left = left1; right = right1; } }; template <class T> class BSTree { public: BSTree(TNode <T> *&root) { root = NULL; } /* 构造函数 */ void RR(TNode <T> **a, TNode <T> **b); /* RR型调整操作 */ TNode <T> *Delete(TNode <T> *&root, int key); /* 删除关键字为key的结点 */ TNode <T> *BSTLocateTree(TNode <T> *&root, int k, int n); /* 确定树中第k小的结点的位置 */ void BSTInsert(TNode <T> *&root, T item); /* 向平衡二叉树中插入元素 */ }; template <class T> void BSTree <T>::RR(TNode <T> **a, TNode <T> **b) { (*a)->right = (*b)->left; (*a)->balance = 0; (*b)->left = (*a); (*b)->balance = 0; (*b)->lsize = (*b)->lsize + (*a)->lsize; } template <class T> TNode <T> *BSTree <T>::Delete(TNode <T> *&root, int key) { /* 在二叉排序树中删除关键字为k的结点 */ TNode <T> *t, *f, *s, *q; t = root; f = NULL; while (t) /* 查找关键字为k的待删结点t */ { if (key == t->data) /* 找到，则跳出查找循环 */ break; else { f = t; /* f指向t结点的双亲结点 */ if (key < t->data) t = t->left; else t = t->right; } } if (t == NULL) /* 若找不到，则返回原来的二叉排序树 */ return root; if (t->left == NULL) /* t无左子树 */ { if (f == NULL) root = t->right; /* t是原二叉排序树的根 */ else if (f->left == t) /* t是f的左孩子 */ f->left = t->right; /* 将t的右子树链到f的左链上 */ else /* t是f的右孩子 */ f->right = t->right; /* 将t的右子树链到f的右链上 */ free(t); /* 释放被删除的结点t */ } else /* t有左子树 */ { q = t; s = t->left; while (s->right) /* 在t的左子树中查找最右下结点 */ { q = s; s = s->right; } t->data = s->data; /* 将s的值赋给t */ if (q == t) q->left = s->left; /* 将s的左子树链到q上 */ else q->right = s->left; free(s); } return root; } template <class T> TNode <T> *BSTree <T>::BSTLocateTree(TNode <T> *&root, int k, int n) { /* 在含lsize域的二叉排序树中确定第k小的结点指针 */ TNode <T> *t; t = root; if (!t) /* k小于1或大于树结点总数 */ return NULL; if (t->lsize == k) /* 就是这个结点 */ { t->lsize--; /* 结点的次序减1 */ if(n <= 100) cout<<t->data<<" "; /* 输出第k小结点的值 */ y = t->data; Delete(root, t->data); /* 删除第k小结点 */ return t; } else if (k < t->lsize) /* 在左子树中寻找 */ { t->lsize--; return BSTLocateTree(t->left, k, n); } else /* 在右子树中寻找，修改k的值 */ return BSTLocateTree(t->right, k - t->lsize, n); } template <class T> void BSTree <T>::BSTInsert(TNode <T> *&root, T item) { TNode <T> *t, *p, *newN, *a, *b, *f; newN = new TNode<T>; /* 申请平衡因子为0的新结点 */ newN->data = item; if (root == NULL) /* 若为空树，则建立只有一个结点的平衡二叉搜索树 */ { root = newN; root->lsize = 1; return; } /* 在插入结点的过程中，寻找离插入结点最近且平衡因子不为0的结点； */ /* 同时使指针a与f分别指向这个结点和它的双亲。如果插入破坏了平衡，*/ /* 这个结点就是最小不平衡子树的根 */ t = root; p = NULL; a = t; f = p; while (t) { if (t->balance != 0) { a = t; f = p; } p = t; if (item < t->data) t = t->left; else t = t->right; } if (item < p->data) p->left = newN; else p->right = newN; /* 从最小不平衡子树的根到插入结点的路径上，除根以外，其余结点的平衡因子原来 */ /* 为0，现在要因结点的插入而做相应的改变 */ if (item < a->data) b = t = a->left; else b = t = a->right; while (t != NULL && t->data != item) { if (item < t->data) { t->balance = 1; t = t->left; } else { t->balance = -1; t = t->right; } } if (a->balance == 0) /* 确定最小不平衡子树的类型，做相应的调整 */ { if (item < a->data) a->balance = 1; else a->balance = -1; return; } else { RR(&a, &b); if (f == NULL) root = b; /* 将最小不平衡子树与其双亲结点连接 */ else { if (f->left == a) f->left = b; else f->right = b; } } } TNode <int> *q; void main() { int n, m, s=0, i; cout<<"请输入数n和m(m<=n, n<=10^6):"; cin>>n>>m; cout<<"("<<n<<", "<<m<<")"<<"-Joseph排列为: "; if (n < m) { cout<<"输入错误!"<<endl; return; } timeb t1, t2; int t0; int *test = new int[n+1]; for (i=0; i<n; i++) { test[i] = i+1; } BSTree <int> t(q); ftime(&t1); /* 开始记录时间 */ for (i=0; i<n; i++) t.BSTInsert(q, test[i]); /* 将元素插入到平衡二叉树中 */ for (i=n; i>=1; i--) { s = (s+m-1)%i; /* 用求余运算在i移动到数组最后一个元素时将它移到数组的第一个元素 */ t.BSTLocateTree(q, test[s], n); /* 查找第k小的元素，输出，并将其删除 */ } cout<<endl; if (n > 100) cout<<"最后一个数为: "<<y<<endl; ftime(&t2); /* 停止记录时间 */ t0 = (t2.time-t1.time)*1000+(t2.millitm-t1.millitm); /* 计算程序运行时间 */ cout<<"用时 "<<t0/1000<<" 秒"<<endl; }