数据结构实验报告_15.doc

实验报告 一．约瑟夫环问题 1.问题描述 设编号为1，2，…，n(n0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数；如此下去直到所有人全部出列为止。 2.算法思路 问题的关键在于建立循环链表。每一个节点包含两个数据：一个是座位号element，一个是密码key。循环链表建好之后，便开始运行了。以m值为第一个key，进行循环，删除，并输出删除节点的element，并将删除节点的key赋给m。然后循环，直到表为空为止。 3.程序代码 #includeiostream using namespace std; templateclass Elemclass Link { public: Elem element,key; Link* next; Link(const Elem elemval,const Elem K,Link* nextval=NULL) { element=elemval; key=K; next=nextval; } Link(Link* nextval=NULL){next=nextval;} }; templateclass Elemclass rollList: public LinkElem { private: LinkElem* p; LinkElem* q; LinkElem* r; int n; public: void setn(int x){n=x;} int getn(){return n;} void setRL() { int t[7],k[7]; coutplease input element[7]:endl; for(int a=0;a7;a++)cint[a]; coutplease input key[7]:endl; for(int b=0;b7;b++)cink[b]; r=new Linkint; r-element=t[0]; r-key=k[0]; q=r; for(int i=1;igetn();i++) { p=new Linkint; q=q-next=p; q-element=t[i]; q-key=k[i]; } q-next=r; p=r; } void ysf(int m) { int x; coutThe order is :endl; if(m==1) { LinkElem* temp=p; q-next=p-next; p=p-next; couttemp-element ; x=temp-key; delete temp; n--; } else { for(int i=1;im-1;i++) p=p-next; q=p; LinkElem* temp=p-next; q-next=temp-next; couttemp-element ; x=temp-key; delete temp; p=q-next; n--; } while(n0) { if(x==1) { LinkElem* temp=p; q-next=p-next; p=p-next; couttemp-element ; x=temp-key; delete temp; n--; } else { for(int i=1;ix-1;i++) p=p-next; q=p; LinkElem* temp=p-next; q-next=temp-next; couttemp-element ; x=temp-key; delete temp; p=q-next; n--; } } } }; int main() { rollList int A; A.setn(7); A.setRL(); A.ysf(20); return 0; } 4.运行结果 二．二叉排序树的实现 1.问题描述 采用顺序表作存储结构，实现对二叉排序树的操作。 2.基本要求 用顺序表(一维数组)作存储结构----静态链表 1)以回车符(‘\n’)为输入结束标志，输入数列L，生成一棵二叉排序树T； 2)对二叉排序树T作中序遍历，输出结果； 3)计算二叉排序树T查找成功的平均查找长度，输出结果； 4)输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则，输出信息“无x”； 3算法思路 以回车符(‘\n’)为输入结束标志，因为空格和回车都是char型，可以考虑在输入时设立两个数组，进行交叉输入：一个为int型，为二叉树中的元素；另一