数据结构实训报告(常用版).doc

数据结构实训报告（常用版）
(可以直接使用，可编辑 完整版资料，欢迎下载）
北京联合大学
实训报告

课程（项目）名称： 数据结构
学 院： 专 业：
班 级： 学 号：
姓 名： 成 绩：

2012年　6　月　21　日

数据结构实训任务一
一、任务与目的：
1、用顺序表表示两个无序集合A、B，实现集合的如下操作，求两个集合的并集、交集、差集。
2、 用顺序表表示两个集合A、B（集合A、B都是有序递增的情况）实现集合的如下操作，求两个集合的并集、交集、差集。
3、用带头单链表存储结构表示两个无序集合A、B，实现集合的如下操作，求两个集合的并集、交集、差集。
4、用带头单链表存储结构表示两个集合A、B（集合A、B都是有序递增的情况），实现集合的如下操作，求两个集合的并集、交集、差集。
5、杀人游戏 N个人坐成一圈玩杀人游戏，按顺时针编号 1 2 3 N。从1号开始顺时针开始数到第m号就杀掉第一个人，被杀掉的人要退出游戏。 如果数到了编号的末尾，接着数开头的编号。 重复，直至杀掉一半人时，游戏结束，聪明的你能告诉我活到最后的幸存者最初的编号是多少吗？ 输入数据：N、M ；输出数据：幸存者的编号 分析该程序，如果N=20，M=2，……10。聪明的你应选择的编号是多少，（提示，计算出M分别等于1到10的情况下，那些编号生存概率较大）。给出实验结果
6、作业抽查问题：有35个学生的班级，由于某种原因不能够做到全部检查作业，现在希望每次抽查10名学生，希望能够随机抽查，并能够有记忆，即希望抽查过的学生，下次抽查的概率有所减小，但避免不被抽查。设计一个算法实现该功能，给出你的解释。
1. void BingSet(SqList A, SqList B,SqList &C)
{//求并集
int i,j;
int flag=0;
C.length=0;
for(i=0;i<A.length;i++)
{C.elem[i]=A.elem[i];
}
for(j=0;j<B.length;j++)
{flag=LocateElem_Sq(A, B.elem[j]);
if(flag==0)
{C.elem[i]=B.elem[j];i++;}
}
C.length=i;
}

void JiaoSet(SqList A, SqList B,SqList &C)
{//求交集
int i,j;
int flag=0;
C.length=0;
i=0;
for(j=0;j<B.length;j++)
{flag=LocateElem_Sq(A, B.elem[j]);
if(flag!=0)
{C.elem[i]=B.elem[j];i++;}
}
C.length=i;
}

void ChaSet(SqList A, SqList B,SqList &C)
{//求差集
int i,j,k;
int flag=0;
C.length=0;
k=0;
for(i=0;i<A.length;i++)
{flag=LocateElem_Sq(B,A.elem[i]);
if(flag==0)
{C.elem[k]=A.elem[i];k++;}
}
C.length=k;
}

运行结果：

2. void BingSet(SqList A, SqList B,SqList &C)
{//求并集
int i,j,k;
k=0;
C.length=0;
for(i=0,j=0;(i<A.length)&&(j<B.length);)
{if(A.elem[i]<B.elem[j])
{C.elem[k]=A.elem[i];k++;i++;
}
else
{if(A.elem[i]==B.elem[j])
{C.elem[k]=A.elem[i];k++;i++;j++;
}
else
{C.elem[k]=B.elem[j];k++;j++;}
}
}
if(i<A.length)
{for(;i<A.length;i++)
{C.elem[k]=A.elem[i];k++;i++;
}
}
if(j<B.length)
{for(;j<B.length;j++)
{C.elem[k]=B.elem[j];k++;j++;}
}
C.length=k;
}
void JiaoSet(SqList A, SqList B,SqList &C)
{//求交集
int i,j,k;
k=0;
C.length=0;
for(i=0,j=0;(i<A.length)&&(j<B.length);)
{if(A.elem[i]<B.elem[j])
{i++;}
else
{if(A.elem[i]==B.elem[j])
{C.elem[k]=A.elem[i];k++;i++;j++;
}
else
{j++;}
}
}
C.length=k;
}

void ChaSet(SqList A, SqList B,SqList &C)
{//求差集
int i,j,k;
int flag=0;
k=0;
C.length=0;
for(i=0,j=0;(i<A.length)&&(j<B.length);)
{if(A.elem[i]<B.elem[j])
{C.elem[k]=A.elem[i];i++;k++;
}
else
{if(A.elem[i]==B.elem[j])
{i++;j++;}
else
{j++;
}
}
}
if(i<A.length)
{for(;i<A.length;i++)
{C.elem[k]=A.elem[i];k++;i++;}
}
C.length=k;
}

void InserOrder_Sq(SqList &L,ElemType e)
{int i,j;
for(i=0;i<L.length;i++)
{if(L.elem[i]>=e)
break;
}
for(j=L.length-1;j>=i;j--)
L.elem[j+1]=L.elem[j];
L.elem[i]=e;
L.length++;
}
运行结果：

3. void bing(link &p,link &h,link &q)
{//求并集
link l,s,m;
int j=0,i=0;
q=new LNode;
q->date=NULL;
q->next=NULL;
s=p->next;
m=q;
while(s)
{l=new LNode;
l->date=s->date;
l->next=NULL;
s=s->next;
m->next=l;
m=l;
s=h->next;
while (s)
{i=s->date;
j=Locate(p,i);
if(j==0)
{l=new LNode;
l->date=s->date;
l->next=NULL;
m->next=l;
m=l;
}
s=s->next;}
}
void jiao(link &p,link &h,link &q)
{ //求交集
link l,s,t,m;
int j=0;
Elem i=0;
q=new LNode;
q->date=NULL;
q->next=NULL;
m=q;

s=h->next;
while (s)
{i=s->date;
j=Locate(p,i);
if(j==1)
{l=new LNode;
l->date=s->date;
l->next=NULL;
m->next=l;
m=l;
}
s=s->next;
}
}
void cha(link &p,link &h,link &q)
{//求差集
link l,s,t,m;
int j=0;
Elem i=0;
q=new LNode;
q->date=NULL;
q->next=NULL;
m=q;
s=p->next;
while (s)
{i=s->date;
j=Locate(h,i);
if(j==0)
{l=new LNode;
l->date=s->date;
l->next=NULL;
m->next=l; m=l;}
s=s->next;} }
void shengcheng(link &p,link &h,link &q)
{ int i,j=0;
Elem e;
for(i=0;i<11;)
{if(i==0)
{p=new LNode;
p->date=NULL;
p->next=NULL;
h=p;q=p;i++;}
else
{e=rand()%50+1;
j=Locate(p,e);
if(j==0)
{LInsert(p,e);i++;}}}}
运行结果：

4. void bing(link &p,link &h,link &q)
{ //并集
link l,s,m;
int j=0,i=0;
q=new LNode;
q->date=NULL;
q->next=NULL;
s=p->next;
m=q;
while(s)
{l=new LNode;
l->date=s->date;
l->next=NULL;
s=s->next;
m->next=l;
m=l;}
s=h->next;
while (s)
{i=s->date;
j=Locate(p,i);
if(j==0)
{LInsert(q,i);}
s=s->next;} }
void jiao(link &p,link &h,link &q)
{//交集
link l,s,t,m;
int j=0;
Elem i=0;
q=new LNode;
q->date=NULL;
q->next=NULL;
m=q;
s=h->next;
while (s)
{i=s->date;
j=Locate(p,i);
if(j==1)
{l=new LNode;
l->date=s->date;
l->next=NULL;
m->next=l;
m=l;}
s=s->next;} }
void cha(link &p,link &h,link &q)
{//差集
link l,s,t,m;
int j=0;
Elem i=0;
q=new LNode;
q->date=NULL;
q->next=NULL;
m=q;
s=p->next;
while (s)
{i=s->date;
j=Locate(h,i);
if(j==0)
{l=new LNode;
l->date=s->date;
l->next=NULL;
m->next=l;
m=l;}
s=s->next;} }
void shengcheng(link &p,link &h,link &q)
{int i,j=0;
Elem e;
for(i=0;i<11;)
{if(i==0)
{p=new LNode;
p->date=NULL;
p->next=NULL;
h=p;q=p;i++;}
else
{e=rand()%50+1;
j=Locate(p,e);
if(j==0)
{LInsert(p,e);i++;}}}}
运行结果：

5. #include <stdio.h>
#include<malloc.h>
#include <iostream.h>
#define LEN sizeof(struct kill)
//定义struct kill 类型长度
struct kill
{ int num;
struct kill *next; };
struct kill *create(int m)
{struct kill *head,*p1,*p2; int i;
p1=p2=(struct kill*)malloc(LEN);
head=p1;
head->num=1;
for(i=1,p1->num=1;i<m;i++)
{ p1=(struct kill*)malloc(LEN);
p1->num=i+1;
p2->next=p1; p2=p1; }
p2->next=head;
return head; }
struct kill *findout(struct kill *start,int n)
{int i;
struct kill *p;
i=n;
p=start;
for(i=1;i<n-1;i++)
p=p->next;
return p; }
struct kill *letout(struct kill *last)
{struct kill *out,*next;
out=last->next;
last->next=out->next;
next=out->next;
free(out);
return next; }
void main()
{ int m,n,i,servive;
struct kill *p1,*p2;
cout<<"请输入参加杀人游戏总人数m:"<<endl;
cin>>m;
cout<<"要杀掉的人的序号n:"<<endl;
cin>>n;
if(n==1)
{ servive=m; }
else
{ p1=p2=create(m);
for(i=1;i<m;i++)
{ p2=findout(p1,n);
p1=p2;
p2=letout(p1);
p1=p2; }
servive=p2->num;
free(p2); }
cout<<"幸存者是："<<endl;
cout<<servive<<endl; }
运行结果：

6. #include <iostream>
#include <cmath>
#include <ctime>
using namespace std;//定义结构体
struct Student
{int id; //学生id
int times; //定义学生抽查数};
Student stu[35]; //35个学生
int cho[10]; //抽查的10个学生
int top; //已抽查学生数
int choose()
{int n=rand()%35; //随机抽取
for(int i=0;i<top;i++)
{if(cho[i]==n) //如果抽到的已经存在,重新抽取
return choose();}
if(stu[n].times==0) return n;//如果第一次抽取直接返回
int n2=rand()%stu[n].times;//否则几率按抽取的次数减小,具体为(1/抽取次数)
if(n2==0) return n;
else return choose();}
void main()
{char a='Y';
srand(time(0)); //随机数初始化
int i;for(i=0;i<35;i++)//学生初始化
{stu[i].id=i+1;stu[i].times=0;}
while(a=='Y'||a=='y')
{int tmp;top=0;
for(i=0;i<10;i++) //抽取10个学生
{tmp=choose(); //抽取学生
cho[top++]=tmp;
stu[tmp].times++;
cout<<"第"<<i+1<<"个:"<<tmp+1<<"下次抽到的概率:"<<(1.0/(35*stu[tmp].times))<<endl;//打印抽取结果}
cout<<"Continue?(Y/N)"<<endl; //是否继续抽取
cin>>a;}}
运行结果：

数据结构实训任务二
一、任务与目的：主要考察的是栈与队列的逻辑结构和存储结构。
1、用栈，判断一个算数表达式中的圆括弧、方括弧和花括弧是否匹配。
2、用栈，把十进制的整数转换为二至九之间的任一进制
3、设计一个算法，检测一个字符串数组是否是回文，回文是指这个字符串是否关于中心对称。int Check（char a[]，int n）
4、采用SPT规则的单机生产计划问题。问题描述如下，存在一台机器，要加工n个工件，每个工件i都有一个确定的加工时间 ，采用按照 递增的顺序，进行加工，计算每个工件的完成时间（初始加工时间为0）。设计一个算法，输入工件数量n，随机在[1，30]的区间内产生每个工件的加工时间 。按照SPT规则进行加工，输出每个工件的完成时间。
5、采用EDD规则的单机生产计划问题。问题描述如下，存在一台机器，要加工n个工件，每个工件i都有一个确定的加工时间 ，同时每个工件都有一个确定的交货期 ，采用按照 递增的顺序，进行加工，计算每个工件的完成时间（初始加工时间为0）。设计一个算法，输入工件数量n，随机在[1，30]的区间内产生每个工件的加工时间 ，在区间[2，20*n]内随机产生每个工件的交货期 。按照EDD规则进行加工，输出每个工件的完成时间，计算每个工件i完成时间和 的差值。

1. void Ininstack(stack &s)
{//初始化
s.elem=new stype[SIZE];
s.top=-1;
s.size=SIZE;
s.insize=IN;}
void INsize(stack &s)
{//扩容
stype *a;int i;
a=new stype[s.size+s.insize];
for(i=0;i<=s.top;i++)
a[i]=s.elem[i];
delete []s.elem;
s.elem=a;
s.size+=s.insize;}
void Push(stack &s,stype e)
{ //入栈
if(s.top==(s.size-1))
INsize(s);s.top++;
s.elem[s.top]=e;}
stype Pop(stack &s)
{//出栈
stype e;e=s.elem[s.top];
s.top--;return e;}
stype GetTop(stack s)
{//取栈顶
stype e;e=s.elem[s.top ];
return e;}
void main()
{stype e,t,ch;
stack s;char a[20];
int i=0,n;Ininstack(s);
cout<<"请输入算术表达式(以$结尾):";
while(ch!='$')
{cin>>ch;
a[i]=ch;i++;}
n=i;
for(i=0;i<n;i++)
{if(a[i]=='{'||a[i]=='['||a[i]=='(')
{e=a[i];Push(s,e);}
if(a[i]=='}'||a[i]==']'||a[i==')'])
{t=GetTop(s);
if(a[i]=='}' && t=='{')Pop(s);
else if(a[i]==']' && t=='[')
Pop(s);else if(a[i]==')' && t=='(')
Pop(s);}}
if(s.top==-1)
cout<<"括号匹配!"<<endl;
else
cout<<"括号不匹配!"<<endl;}
运行结果：

2. void Ininstack(stack &s)
{ //初始化
s.elem=new stype[SIZE];s.top=-1;
s.size=SIZE;s.insize=IN;}
void INsize(stack &s)
{ //扩容
stype *a;int i;
a=new stype[s.size+s.insize];
for(i=0;i<=s.top;i++)
a[i]=s.elem[i];
delete []s.elem;
s.elem=a;s.size+=s.insize;}
void Push(stack &s,stype e)
{//入栈
if(s.top==(s.size-1))
INsize(s);s.top++;
s.elem[s.top]=e;}
stype Pop(stack &s)
{ //出栈
stype e;e=s.elem[s.top];s.top--;
return e;}
void main()
{stack s;int a,b;Ininstack(s);
cout<<"请输入任意非负十进制数:";
cin>>a;
cout<<"请输入需要转换的进制数(进制数为二至九):";
cin>>b;
while(a)
{Push(s,a%b);a=a/b;}
while(!(s.top==-1))
cout<<Pop(s);
cout<<endl;}
运行结果：

3. void Ininstack(stack &s)
{ //初始化
s.elem=new stype[SIZE];
s.top=-1;s.size=SIZE;s.insize=IN;}
void INsize(stack &s)
{ //扩容
stype *a;int i;
a=new stype[s.size+s.insize];
for(i=0;i<=s.top;i++)a[i]=s.elem[i];
delete []s.elem;
s.elem=a;s.size+=s.insize;}
void Push(stack &s,stype e)
{//入栈
if(s.top==(s.size-1))INsize(s);
s.top++;s.elem[s.top]=e;}
void Error(char *a)
{ cout<<a<<endl;exit(1);}

stype Pop(stack &s)
{ stype e;e=s.elem[s.top];
s.top--;return e;}
int Check(char a[],int n,stack &s)
{//判断
int i;char e;Pop(s);
for(i=0;i<n-1;i++)
{e=Pop(s);
if(a[i]!=e) reak;}
if(i==n-1)return 1;
else urn 0;}
void main()
{stack s; r ch,a[50]; t i=0,n,t; instack(s);
cout<<"请输入字符串(以$结尾):";
while(ch!='$')
{cin>>ch; [i]=ch; ush(s,ch); +;}
n=i; Check(a,n,s);
if(t==1)cout<<"是回文!"<<endl;
else
cout<<"不是回文!"<<endl;}
运行结果：

4. void chushihua(sqlist &a) //初始化
{a.elem=new elemtype[SIZE];
a.num=new elemtype[SIZE];
a.welem=new elemtype[SIZE];
a.length=0;
a.listsize=SIZE;
a.incrementsize=INCREMENT;}
void paixu(sqlist a) //排序
{ int i,j,t,m;for(i=0;i<a.length;i++)
for(j=0;j<a.length-i-1;j++)
if(a.elem[j]>a.elem[j+1])
{ t=a.elem[j];m=a.num[j];
a.elem[j]=a.elem[j+1];
a.num[j]=a.num[j+1];
a.elem[j+1]=t;a.num[j+1]=m;}}
void shuchu(sqlist &a)
{int i;for(i=0;i<a.length;i++)
{if(i==0) a.welem[i]=a.elem[i];
else
{a.welem[i]=a.elem[i]+a.welem[i-1];}
cout<<setw(4)<<a.num[i]<<setw(11)<<a.elem[i]<<setw(10)<<a.welem[i]<<endl;;}
cout<<endl<<endl;
}
运行结果：

5. typedef struct
{elemtype *elem; //加工时间
elemtype *num; //序号
elemtype *welem; //完成时间
elemtype *jelem; //交货期
elemtype *celem; //差值
int length; //长度
int listsize; //分配量
int incrementsize; //增补量
}sqlist;
void chushihua(sqlist &a) //初始化
{a.elem=new elemtype[SIZE];
a.num=new elemtype[SIZE];
a.welem=new elemtype[SIZE];
a.celem=new elemtype[SIZE];
a.jelem=new elemtype[SIZE];
a.length=0;
a.listsize=SIZE;
a.incrementsize=INCREMENT;}
void paixu(sqlist a) //排序
{int i,j,t,m,p;
for(i=0;i<a.length;i++)
for(j=0;j<a.length-i-1;j++)
if(a.jelem[j]>a.jelem[j+1])
{ t=a.elem[j];
p=a.jelem[j];
m=a.num[j];
a.elem[j]=a.elem[j+1];
a.jelem[j]=a.jelem[j+1];
a.num[j]=a.num[j+1];
a.elem[j+1]=t;
a.jelem[j+1]=p;
a.num[j+1]=m;}}
void shuchu(sqlist &a)
{int i;for(i=0;i<a.length;i++)
{if(i==0)
a.welem[i]=a.elem[i];
else
{a.welem[i]=a.elem[i]+a.welem[i-1];}
a.celem[i]=a.jelem[i]-a.welem[i];
cout<<setw(4)<<a.num[i]<<setw(10)<<a.elem[i]<<setw(10)<<a.welem[i]<<setw(13)<<a.jelem[i]<<setw(11)<<a.celem[i]<<endl;;}
cout<<endl<<endl; }

运行结果：

数据结构实训任务书三：二叉树链式存储的基本操作
1、 创建二叉树
a) 熟悉使用教材的先序创建二叉树的方法
b) 编写一个算法，实现在已知二叉树的先序序列和中序序列的情况下创建二叉树。
c) 如果已知二叉树的顺序表示形式，将其转换为二叉树的链式存储方式。
2、 二叉树的遍历
a) 先序、中序和后序三种形式的链式存储递归式算法
b) 先序、中序和后序三种形式的链式存储非递归式算法
c) 层次遍历的算法。
3、 二叉树一些基本操作
a) 计算二叉树的深度；
b) 计算二叉树的叶子节点个数
c) 计算二叉树的单支节点的个数
d) 计算二叉树的双支节点的个数
4、 编写一个主函数能够测试你所设计的算法。
主函数调用教材创建二叉树的创建教材图7-10的二叉树链式存储方式。
{p=st.a[st.top];
st.top--;
cout<<p->data;
while (p->right!=NULL)
{st.top++;
st.a[st.top]=p->right;
q=p->right;
while (q->left!=NULL)
{st.top++;
st.a[st.top]=q->left;
q=q->left;
}
代码：#include <stdio.h>
#include <malloc.h>
#include <iostream.h>
#define MAXSIZE 20
int d=0;
int l=0;
typedef struct node //二叉树结点的结构体表示形式
{char data;
struct node* left,*right;
}BTree;
typedef BTree *Tree;
typedef struct stackelem //栈的结构体表示形式
{BTree* a[MAXSIZE];
int top;
}Stack;
void CreateBiTree_Rec(Tree &T) //先序创建二叉树的方法
{char ch;
cin>>ch;
if(ch=='#')
T=NULL;
else
{T= new BTree;
T->data=ch;
CreateBiTree_Rec(T->left);
CreateBiTree_Rec(T->right); }}
void Preorder(Tree t) //前序遍历，递归的方法
{if (NULL!=t)
{cout<<t->data;
Preorder(t->left);
Preorder(t->right); }}
void Preorder2(Tree t) //前序遍历的非递归实现
{Tree p;
Stack st;
st.top=-1;
if (NULL==t)
{return; }
else
{st.top++;
st.a[st.top]=t;
while (st.top!=-1)
{p=st.a[st.top];
st.top--;
cout<<p->data;
if (p->right!=NULL)
{st.top++;
st.a[st.top]=p->right; }
if (p->left!=NULL)
{st.top++;
st.a[st.top]=p->left; } }}}
void Inorder(Tree t)
//中序遍历，递归实现
{if (NULL!=t)
{Inorder(t->left);
cout<<t->data;
Inorder(t->right); }}
void Inorder2(Tree t)
//中序遍历，非递归实现
{Tree p,q;
Stack st;
st.top=-1;
if (NULL==t)
{return;
}
else
{while (t!=NULL)
{st.top++;
st.a[st.top]=t;
t=t->left;
}
while (st.top!=-1)
break;
}
}}}
void Postorder(Tree t)
//后序遍历，递归实现
{if (t!=NULL)
{Postorder(t->left);
Postorder(t->right);
cout<<t->data;
}}
void Postorder2(Tree t)
//后序遍历，非递归实现
{Stack st;
st.top=-1;
Tree m;
int flag;
do
{while (t!=NULL)
{st.top++;
st.a[st.top]=t;
t=t->left;
}
m=NULL;
flag=1;
wh