实验报告一 顺序表和链表
（1）实验内容
1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。
2．遍历单向链表。
3．把单向链表中元素逆置（不允许申请新的结点空间）。
4．在单向链表中删除所有的偶数元素结点。
5．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。
6．利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。
7．利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。
8．利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。
* 9．采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。
10．在主函数中设计一个简单的菜单，分别调试上述算法。
*11．综合训练：利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中）
1）顺序表实现基本操作
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10
using namespace std;
typedef int Elemtype;
//抽象化元素类型，到时候可根据需要将int修改成其他的基本数据类型
typedef struct {
Elemtype data[MaxSize];
int length;
}Sqlist;
//1.构造新的顺序表L
//这种创建方法在逻辑上是不对的，因为数组的长度已经规定，不能无限制地输入数据元素
Sqlist createSqlist(){
Sqlist l;//length此时不为0，而是随机分配的一个数字
int x;
scanf ("%d",&x);
int i=0;
l.length=0;
while (x!=-999){
l.data[i]=x;
l.length++;
i++;
scanf("%d",&x);//勿忘重新读入数据
}
return l;
}
void displaySqlist(Sqlist &l){//加不加引用的区别？？
for (int i=0;i<l.length;i++){
printf("%d ",l.data[i]);
}
printf("\n");
}
//初始化顺序表
void InitSqlist(Sqlist &l){
l.length=0;
}
//插入：在第i个元素之前
void InsertSqlist(Sqlist &l,int i,Elemtype e){
//1.判断I的位置是否合理
if (i<1||i>l.length+1)//可以插在最后一个位置
printf("positon error");
for (int j=l.length;j>i-1;j--){
l.data[j]=l.data[j-1];
}
l.data[i-1]=e;
l.length++;
}
void readitemSqlist(Sqlist &l){
int x;
scanf ("%d",&x);
int i=0;
while (x!=-999&&l.length<=MaxSize){
l.data[i]=x;
i++;
scanf ("%d",&x);
l.length++;
}
}
//有返回值的插入方法
int InsertSqlist2(Sqlist &l,int i,Elemtype e){
//1.判断I的位置是否合理
if (i<1||i>l.length+1){
printf("positon error");
return 0;
}
for (int j=l.length;j>i-1;j--){
l.data[j]=l.data[j-1];
}
l.data[i-1]=e;
l.length++;
return 1;
}
int deleteSqlist (Sqlist &l,int i,Elemtype &e){
//删除i之前的元素，回收到e中
if (i<1||i>l.length){
printf("positon error");
return 0;
}
e=l.data[i-1];
for (int j=i-1;j<l.length-1;j++){
l.data[j]=l.data[j+1];
}
l.length--;
return 1;
}
int locateSqlist (Sqlist &l,Elemtype e){
for (int i=0;i<l.length;i++){
if (l.data[i]==e)
return i+1;//返回的是序号
}
printf("can not find it !");
return 0;
//另一种做法
//int i=l.length;
//while (i>=0&&l.data[i]!=x) i--;
//return i+1;
//if (i==-1)
//return 0;
}
int main()
{
Sqlist l;
InitSqlist(l);
readitemSqlist(l);
displaySqlist(l);
Elemtype e=5;
int i=locateSqlist(l,e);
printf("%d",i);
}
2）单链表实现基本操作
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef int Elemtype;
typedef struct node
{
Elemtype data;
struct node *next;
} node,*linklist;
linklist creatlinklist()
{
//尾插法建立单链表
linklist l,p,q;
l=(linklist)malloc(sizeof(node));
p=l;
int x;
scanf("%d",&x);
while (x!=-999)
{
q=(linklist)malloc(sizeof(node));
q->data=x;
p->next=q;
q->next=NULL;
p=q;
scanf("%d",&x);
}
return l;
}
void displaylinklist(linklist l)
{
linklist p=l->next;
while (p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
void nizhilinklist(linklist &l)
{
linklist p,q;//p指向后面结点，q指向当前结点
q=l;
p=l->next;
l->next=NULL;//解放头结点
while(p!=NULL)
{
q=p;//q指向即将头插法的结点
p=p->next;//保存后面的结点首地址；
q->next=l->next;
l-> next=q;
}
}
void deletelinklist(linklist &l)
{
linklist p=l;
//p指向待删除元素的前面的位置，必须要从L开始，不然第一个元素无法删除
while (p!=NULL)
{
if(p->next==NULL)//如果最后一个元素是奇数要特别对待
break;
if (p->next->data%2==0)
{
p->next=p->next->next;
}
p=p->next;
}
}
void insertlinklist(linklist &l)
{
Elemtype x;
scanf("%d",&x);
linklist p;
linklist q;
p=l;
while (p->next!=NULL&&p->next->data < x)
{
p=p->next;
}
if (p->next!=NULL){
q=(linklist )malloc(sizeof(node));
q->data=x;
q->next=p->next;
p->next=q;
}
if (p->next==NULL)
{
p->next=q;
q->next=NULL;
}
}
void mergelinklist(linklist &la,linklist &lb,linklist &lc){
//假设la与lb为非递减有序单向链表
lc=la;
linklist pa=la->next,pb=lb->next,pc=lc;
lc->next=NULL;
while (pa!=NULL&&pb!=NULL){
if (pa->data > pb->data){
pc->next=pb;
pc=pb;
pb=pb->next;
}
if (pa->data <= pb->data){
pc->next=pa;
pc=pa;
pa=pa->next;
}
}
if (pa!=NULL)
pc->next=pa;
if (pb!=NULL)
pc->next=pb;
free(lb);
//free(la)??
//这里判断条件如果用==，那么while循环出来的一定都满足该条件，所以要用不等于
}
void mergenizhilinklist(linklist &la,linklist &lb,linklist &lc){
mergelinklist(la,lb,lc);
nizhilinklist(lc);
}
linklist dividelinklist(linklist &l){
linklist h=(linklist)malloc(sizeof(node));
h->next=NULL;
linklist p=l,q=h;
while(p!=NULL){
if(p->next==NULL)
break;//最后为偶数
if (p->next->data%2!=0){
q->next=p->next;
q=p->next;
p->next=q->next;
p=p->next;
}
p=p->next;
}
q->next=NULL;
return h;
//这里或许可以用头插法建立？？
}
//实现一元多项式
typedef struct {
float conf;
int expn;
}Elemtype;
typedef struct pnode{
Elemtype data;
struct pnode *next;
}pnode,*linklist;
linklist creatPolylist(){
linklist l=(linklist )malloc(sizeof(pnode));
linklist p=l,q;
float con;
int exp;
scanf ("%f %d",&con,&exp);
while (exp!=-1){
q=(linklist )malloc(sizeof(pnode));
(q->data).conf=con;
(q->data).expn=exp;
p->next=q;
p=q;
scanf ("%f %d",&con,&exp);
}
p->next=NULL;
return l ;
}
void displayPoly(linklist &l){
linklist p=l->next;
while (p!=NULL){
printf("(%.2f %d)",((p->data).conf),((p->data).expn));
p=p->next;
}
printf("\n");
}
void addPoly(linklist &la,linklist &lb){
linklist pa=la,pb=lb,qa,qb;
qa=pa->next;
qb=pb->next;
int sum;
while (qa!=NULL&&qb!=NULL){
if (qa->data.expn < qb->data.expn){
pa=qa;
qa=qa->next;
}else if(qa->data.expn = qb->data.expn){
sum=qa->data.conf + qb->data.conf;
if (sum!=0){
qa->data.conf=sum;
pa=qa;
qa=qa->next;
pb=qb->next;
free(qb);
qb=qb->next;//释放B链表中的重复系数结点，这样不占用任何多余空间。
}else {
pa=qa->next;
pb=qb->next;
free(qa);
free(qb);
qa=pa->next;
qb=pb->next;//两个结点都要释放
}
}else {
pa->next=qb;
qb->next=qa;
pa=qb;
qb=qb->next;//在la链表中插入B中的一个结点，仍旧保持Pa为Qa的前驱，qb后移
}
}
if(qb!=NULL)
qa->next=qb;
}
实验二 栈、队列
（1）实验内容
1．采用链式存储实现栈的初始化、入栈、出栈操作。
2．采用顺序存储实现栈的初始化、入栈、出栈操作。
3．采用链式存储实现队列的初始化、入队、出队操作。
4．采用顺序存储实现循环队列的初始化、入队、出队操作。
5．在主函数中设计一个简单的菜单，分别测试上述算法。
*6．综合训练:1)利用栈实现表达式求值算法。
2)利用栈实现迷宫求解。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define OVERFLOW -2
using namespace std;
//顺序栈
typedef int Elemtype;
typedef struct {
Elemtype elem[MAXSIZE];
int top;
}SeqStack;
void initSeqStack(SeqStack &s){
s.top=-1;
}
int stackEmpty(SeqStack &s){
if (s.top==-1)
return 1;
return 0;//或者返回 表达式的真值return s.top==-1;
}
int push(SeqStack &s,Elemtype e){
if (s.top>=MAXSIZE-1)
return 0;
else {
s.top++;
s.elem[s.top]=e;
return 1;
}
}
int pop(SeqStack &s,Elemtype &e){
if (s.top==-1)
return 0;
else {
e=s.elem[s.top];
s.top--;
return 1;
}
}
int gettop(SeqStack &s,Elemtype &e){
if (s.top==-1)
return 0;
else {
e=s.elem[s.top];
return 1;
}
}
void display(SeqStack &s){
for (int i=0;i<=s.top;i++){
cout<<s.elem[i]<<" ";
}
cout<<endl;
}
//链栈
typedef struct node {
Elemtype data;
struct node *next;
}node,*linkstack;
void initLinkstack(linkstack &top){
top=NULL;//无头节点的链栈
}
int linkstackEmpty(linkstack &top){
return top==NULL;
}
int linkstackPush(linkstack &top,Elemtype e){
linkstack p=(linkstack )malloc (sizeof(node));
if (!p) exit(OVERFLOW);
p->data=e;
p->next=top;
top=p;
return 1;
}
int linkstackPop(linkstack &top,Elemtype &e){
e=top->data;
linkstack p=top;
top=top->next;
free(p);
return 1;
}
void getTop(linkstack &top,Elemtype &E){
E=top->data;
}
void displaylinkstack(linkstack &top){
linkstack p=top;
while (p){
printf ("%d ",p->data);
p=p->next;
}
printf ("\n");
}
//顺序循环队列
typedef int Elemtype;
typedef struct{
Elemtype data[MAXSIZE];
int rear,front;
}Seqqueue;
void initSeqqueue(Seqqueue &q){
q.rear=q.front=-1;
}
int emptySeqqueue(Seqqueue &q){
return q.rear==q.front;
}
int enSeqqueue(Seqqueue &q,Elemtype e){
//先判断是否队满
if ((q.rear+1)%MAXSIZE==q.front){
printf ("full!\n");
return 0;
}
q.rear=(q.rear+1)%MAXSIZE;
q.data[q.rear]=e;
return 1;
}
int deSeqqueue(Seqqueue &q,Elemtype &e){
if (emptySeqqueue(q)){
printf ("null!\n");
return 0;
}
q.front=(q.front+1)%MAXSIZE;
e=q.data[q.front];
return 1;
}
Elemtype getFront(Seqqueue &q){
if (emptySeqqueue(q)){
printf ("null!\n");
}
else {
Elemtype e;
q.front=(q.front+1)%MAXSIZE;
e=q.data[q.front];
return e;
}
}
int length(Seqqueue &q){
return (q.rear-q.front+MAXSIZE)%MAXSIZE;
}
void display(Seqqueue &q){
if (emptySeqqueue(q)){
printf ("null!\n");
}
else {
int i=(1+q.front)%MAXSIZE;
for (int j=0;j<length(q);j++){
printf ("%d ",q.data[i]);
i++;
}
printf ("\n");
}
}
//链队列
typedef int Elemtype;
typedef struct qnode {
Elemtype data;
struct qnode *next;
}qnode,*Queueptr;
typedef struct {
Queueptr front ;
Queueptr rear;
}linkQueue;
int initQueue(linkQueue &q){
Queueptr lq=(Queueptr)malloc(sizeof(qnode));
if (!lq) exit(OVERFLOW);
lq->next=NULL;
q.front=q.rear=lq;
}
int isempty(linkQueue q){
return q.front==q.rear;
}
int enterQueue(linkQueue &q,Elemtype e){
Queueptr p=(Queueptr)malloc(sizeof(qnode));
if (!p) exit(OVERFLOW);
p->data=e;
p->next=q.rear->next;
q.rear->next=p;
q.rear=p;
return 1;
}
int deQueue(linkQueue &q,Elemtype &e){
//出队依旧要判空，入队不需要判满了
if (q.rear==q.front){
printf("null\n");
return 0;
}
Queueptr p=q.front->next;
e=p->data;
q.front->next=p->next;
//这里要特别注意如果链表中唯一的元素要出队，尾指针必须要重新指向头结点，不然丢失该指针了
if (q.front->next==NULL){//或者q.rear==p;
q.rear=q.front;
}
free(p);
return 1;
}
void display(linkQueue &q){
Queueptr p=q.front->next;
while (p){
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main()
{
SeqStack s;
Elemtype e;
linkstack top;
Seqqueue q;
linkQueue Q;
cout<<"---------------------------------------------------"<<endl;
cout<<"1.采用顺序存储实现栈的初始化、入栈、出栈操作"<<endl;
cout<<"2.采用链式存储实现栈的初始化、入栈、出栈操作"<<endl;
cout<<"3.采用顺序存储实现队列的初始化、入队、出队操作"<<endl;
cout<<"4.采用链式存储实现循环队列的初始化、入队、出队操作"<<endl;
cout<<"---------------------------------------------------"<<endl;
int x,i;
cout<<"请输入您的选择！"<<endl;
while (cin>>x){
switch(x){
case 1:{
initSeqStack(s);
cout<<"初始化顺序栈成功！"<<endl;
cout<<"请输入压栈的内容！"<<endl;
cin>>i;
while (i!=-999){
push(s,i);
cin>>i;
}
cout<<"压栈成功！显示栈内数字！"<<endl;
display(s);
cout<<"获取栈顶元素！"<<endl;
gettop(s,e);
printf ("%d\n",e);
cout<<"弹栈！"<<endl;
while (s.top>0){
pop(s,e);
cout<<"弹出元素："<<e<<" ";
}
cout<<endl;
cout<<"显示栈内数字！"<<endl;
display(s);
break;
}
case 2:
initLinkstack(top);
cout<<"初始化链栈成功！"<<endl;
cout<<"请输入压栈的内容！"<<endl;
cin>>i;
while (i!=-999){
linkstackPush(top,i);
cin>>i;
}
cout<<"压栈成功！显示栈内数字！"<<endl;
displaylinkstack(top);
cout<<"获取栈顶元素！"<<endl;
getTop(top,e);
printf ("%d\n",e);
while (top){
linkstackPop(top,e);
cout<<"弹出元素："<<e<<" ";
}
cout<<endl;
cout<<"显示栈内数字！"<<endl;
displaylinkstack(top);
break;
case 3:
initSeqqueue(q);
cout<<"初始化顺序队列成功！"<<endl;
cout<<"请输入进队的内容！"<<endl;
cin>>i;
while (i!=-999){
enSeqqueue(q,i);
cin>>i;
}
cout<<"进队成功！显示队内数字！"<<endl;
display(q);
cout<<"返回队头元素！"<<endl;
e=getFront(q);
cout<<e<<endl;
while (!emptySeqqueue(q)){
deSeqqueue(q,e);
cout<<"出队元素"<<e<<" ";
}
cout<<endl;
cout<<"显示队内数字"<<endl;
display(q);
break;
case 4:
initQueue(Q);
cout<<"初始化链队列成功！"<<endl;
cout<<"请输入进队的内容！"<<endl;
cin>>i;
while (i!=-999){
enterQueue(Q,i);
cin>>i;
}
cout<<"进队成功！显示队内数字！"<<endl;
display(Q);
while (!isempty(Q)){
deQueue(Q,e);
cout<<"出队元素"<<e<<" ";
}
cout<<endl;
cout<<"显示队内数字"<<endl;
display(Q);
break;
}
cout<<"请输入您的选择！"<<endl;
}
return 0;
}
实验报告3 树
1）顺序二叉树
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <string.h>
#include <math.h>
#define MAXSIZE 20
//顺序二叉树
using namespace std;
typedef int Elemtype;
typedef struct SqBinode
{
Elemtype data[MAXSIZE];
} SqBinode,SqBiTree;
typedef struct
{
int level;//第几层
int order;//本层序号，(level,order)类似于（i，j）
} position;
void initBiTree(SqBiTree &bt)
{
for (int i=0; i<MAXSIZE; i++)
{
bt.data[i]=NULL;
}
}
int createBiTree(SqBiTree &bt)
{
cout<<"无节点处请输入0,输入完毕请输入-999"<<endl;
int i=0,n;
cin>>n;
while (n!=-999&&i<=MAXSIZE)
{
bt.data[i]=n;
i++;
if (i!=0&&bt.data[(i+1)/2-1]==NULL&&bt.data[i]!=NULL)
{
cout<<"存在双亲为空且自身为空且不为根节点的点！"<<endl;
return 0;
}
cin>>n;
}
if (i>MAXSIZE)
return 0;
return 1;
}
int BiTreeEmpty(SqBiTree bt)
{
if (bt.data[0]==NULL)
return 1;
else
return 0;
}
int BiTreeDepth(SqBiTree bt)
{
int n=0,i=0;//N为节点个数
for (i=0;i<MAXSIZE-1;i++)
{
if (bt.data[i]!=NULL)
n++;
}
int k=0;
do
{
k++;
}
while (pow(2,k-1)<=n);
return k-1;
}
Elemtype Root(SqBiTree bt)
{
if (bt.data[0])
return bt.data[0];
else
return 0;
}
void initPosition(position &p,int a,int b)
{
p.level=a;
p.order=b;
}
void Value(SqBiTree bt,Elemtype &e,position p)
{
//根据E的位置P找到它
int n=pow(2,p.level-1)+p.order-2;
e=bt.data[n];
}
void Assign(SqBiTree &bt,position &p,Elemtype e)
{
int x=pow(2,p.level-1)+p.order-2;
bt.data[x]=e;
}
void print(SqBiTree bt)
{
int i,j,k=0;
for (i=1;i<=BiTreeDepth(bt); i++)
{
cout<<"第"<<i<<"层";
for (j=1; j<=pow(2,i-1); j++)
{
if (bt.data[k]!=NULL)
cout<<"("<<j<<","<<bt.data[k]<<") ";
k++;
}
cout<<endl;
}
}
void valueP(int i,int j,position &p)
{
p.level=i;
p.order=j;
}
int Parent(SqBiTree &bt,Elemtype e)
{
if (bt.data[0]==e)
return NULL;
int i=1;
while (bt.data[i]!=e && i<=MAXSIZE-1) i++;
return bt.data[(i+1)/2-1];
}
int LeftChild(SqBiTree &bt,Elemtype e)
{
//1.叶子结点无左孩子 2.非叶子结点的左孩子是2*i
int i=0;
while (bt.data[i]!=e && i<=MAXSIZE-1) i++;
//循环停止时应当是找到了值为E的结点，但不知道是叶子节点还是非叶子
if (bt.data[2*i+1]!=NULL)
return bt.data[2*i+1];
else
return NULL;
}
int RightChild(SqBiTree &bt,Elemtype e)
{
//1.叶子结点无左孩子 2.非叶子结点的左孩子是2*i
int i=0;
while (bt.data[i]!=e && i<=MAXSIZE-1) i++;
//循环停止时应当是找到了值为E的结点，但不知道是叶子节点还是非叶子
if (bt.data[2*i+2]!=NULL)
return bt.data[2*i+2];
else
return NULL;
}
int LeftSibling(SqBiTree &bt,Elemtype e)
{
int i=0;
if (!bt.data[0]) return NULL;//空树不用查找
if (bt.data[0]==e) return NULL;//根节点没有左兄弟
while (bt.data[i]!=e && i<=MAXSIZE-1) i++;
//1.左兄弟为-1 2. 为最左侧的一列，没有左兄弟
if (i%2==0) return bt.data[i-1];//序号为偶节点才有左兄弟
else return NULL;
}
int RightSibling(SqBiTree &bt,Elemtype e)
{
int i=0;
if (!bt.data[0]) return NULL;//空树不用查找
if (bt.data[0]==e) return NULL;//根节点没有左兄弟
while (bt.data[i]!=e && i<=MAXSIZE-1) i++;
//1.左兄弟为-1 2. 为最左侧的一列，没有左兄弟
if (i%2!=0) return bt.data[i+1];//序号为偶节点才有左兄弟
else return NULL;
}
void Move(SqBiTree &bt,int k,SqBiTree &q,int g)
{
if (bt.data[2*k+1]!=NULL) //左孩子不空
Move(bt,2*k+1,q,2*g+1);
if (bt.data[2*k+2]!=NULL)//右孩子不空
Move(bt,2*k+2,q,2*g+2);
q.data[g]=bt.data[k];
bt.data[k]=NULL;
}
int InsertChild(SqBiTree &bt,Elemtype e,int LR,SqBiTree &c)
{
//1.找到E所在结点的序号
int i =0;
while (bt.data[i]!=e &&i<=MAXSIZE-1 ) i++;
int k=2*i+LR+1;//得到E结点的LR孩子的序号
if (bt.data[k])//如果LR结点存在，需要转移到C的右子树,也就是K结点的右子树
Move(bt,k,bt,2*k+2);
Move(c,0,bt,k);
return 1;
}
void del(SqBiTree &bt ,int k)
{
//删除bt的k结点作为根结点的非空树
if (!bt.data[2*k+1])//左子树非空
del(bt,2*k+1);
if (!bt.data[2*k+2])
del(bt,2*k+2);
bt.data[k]=NULL;
}
int DeleteChild(SqBiTree &bt,Elemtype e,int lr)
{
//删除e元素对应的左或右子树
//1 find the number of e
int i=0;
while (bt.data[i]!=e &&i<=MAXSIZE-1) i++;
//2 找到要删除的左或右子树
int k =2*i+1+lr;
if (bt.data[k]!=NULL) //非空则删除
del(bt,k);
else
{
cout<<"不存在左或右子树，无法删除"<<endl;
return 0;
}
}
void PreOrder(SqBiTree &bt ,int i)
{
cout<<bt.data[i]<<" ";
if (bt.data[2*i+1])//左子树非空
PreOrder(bt,2*i+1);
if (bt.data[2*i+2])//右子树非空
PreOrder(bt,2*i+2);
}
int PreOrderTraverse(SqBiTree &bt)
{
int i=0;
if (bt.data[i])
PreOrder(bt,i);//遍历左子树
else
{
cout<<"此树为空，不能遍历"<<endl;
return 0;
}
return 1;
}
void InOrder(SqBiTree &bt ,int i)
{
if (bt.data[2*i+1])//左子树非空
PreOrder(bt,2*i+1);
cout<<bt.data[i]<<" ";
if (bt.data[2*i+2])//右子树非空
PreOrder(bt,2*i+2);
}
int InOrderTraverse(SqBiTree &bt)
{
int i=0;
if (bt.data[i])
InOrder(bt,i);//遍历左子树
else
{
cout<<"此树为空，不能遍历"<<endl;
return 0;
}
return 1;
}
void PostOrder(SqBiTree &bt ,int i)
{
if (bt.data[2*i+1])//左子树非空
PostOrder(bt,2*i+1);
if (bt.data[2*i+2])//右子树非空
PostOrder(bt,2*i+2);
cout<<bt.data[i]<<" ";
}
int PostOrderTraverse(SqBiTree &bt)
{
int i=0;
if (bt.data[i])
PostOrder(bt,i);//遍历左子树
else
{
cout<<"此树为空，不能遍历"<<endl;
return 0;
}
return 1;
}
int main()
{
cout<<"---顺序二叉树的基本操作实现 twomeng---"<<endl;
cout<<"--------------------------------------"<<endl;
cout<<"1 InsertChild()"<<endl;
cout<<"2 DeleteChild()"<<endl;
cout<<"3 PreOrderTraverse()"<<endl;
cout<<"4 InOrderTraverse()"<<endl;
cout<<"5 PostOrderTraverse()"<<endl;
cout<<"6 Parent()"<<endl;
cout<<"7 LeftChild()"<<endl;
cout<<"8 RightChild()"<<endl;
cout<<"9 leftSibling()"<<endl;
cout<<"10 RightSibling()"<<endl;
cout<<"11 Root()"<<endl;
cout<<"12 Value()"<<endl;
cout<<"13 Assign()"<<endl;
cout<<"--------------------------------------"<<endl;
ll1:cout<<"请输入您选择的函数序号:)"<<endl;
int number;
cin>>number;
SqBiTree bt;
initBiTree(bt);
createBiTree(bt);//创建一个可以公用的二叉树bt
Elemtype e;position p;
switch(number){
case 1:
SqBiTree c;
initBiTree(c);
createBiTree(c);
InsertChild(bt,3,1,c);
print(bt);
break;
case 2:
DeleteChild(bt,3,1);
print(bt);
break;
case 3:
PreOrderTraverse(bt);
break;
case 4:
InOrderTraverse(bt);
break;
case 5:
PostOrderTraverse(bt);
break;
case 6:
cout<<"输入E的值"<<endl;
cin>>e;
cout<<Parent(bt,e);
break;
case 7:
cout<<"输入E的值"<<endl;
cin>>e;
cout<<LeftChild(bt,e);
break;
case 8:
cout<<"输入E的值"<<endl;
cin>>e;
cout<<RightChild(bt,e);
break;
case 9:
cout<<"输入E的值"<<endl;
cin>>e;
cout<<LeftSibling(bt,e);
break;
case 10:
cout<<"输入E的值"<<endl;
cin>>e;
cout<<RightSibling(bt,e);
break;
case 11:
cout<<Root(bt);
break;
case 12:
cout<<"请输入P的位置(level,order)"<<endl;
int a,b;
cin>>a>>b;
initPosition(p,a,b);
Value(bt,e,p);
cout<<e<<endl;
break;
case 13:
cout<<"请输入P的位置(level,order)和E的值"<<endl;
cin>>a>>b>>e;
initPosition(p,a,b);
Assign(bt,p,e);
print(bt);
break;
}
cout<<"您是否想要继续调用函数？yes/no"<<endl;
string s;cin>>s;
if (!s.compare("yes"))
goto ll1;
else
return 0;
}
链式二叉树
1.实验内容
1．输入字符序列，建立二叉链表。 1
2．中序遍历二叉树:递归算法。3
3．中序遍历二叉树:非递归算法。（最好也能实现先序，后序非递归算法）4
4．求二叉树的高度 。1
5．求二叉树的叶子个数。1
*6．将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数。1
*7．建立中序线索二叉树，并实现中序遍历。1
8．借助队列实现二叉树的层次遍历。1
9．在主函数中设计一个简单的菜单，分别调试上述算法。1
*10．综合训练：为N个权值设计哈夫曼编码。
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <string.h>
#include <math.h>
#define MAXSIZE 10
//链式二叉树
using namespace std;
typedef char Elemtype;
typedef struct BiTNode{
Elemtype data;
struct BiTNode *left,*right;
}BiTNode,*BiTree;
void InitBiTree(BiTree &bt)
{
bt=NULL;//构造空的二叉树
}
void CreateBiTree(BiTree &bt)
{
Elemtype e;
scanf("%c",&e);
if (e==' ')
{
bt=NULL;//如果输入空格则将该结点置空
}
else
{
bt=(BiTree)malloc(sizeof(BiTNode));
bt->data=e;
CreateBiTree(bt->left);
CreateBiTree(bt->right);
}
}
void PreOrderTraverse(BiTree &bt)
{
if (bt!=NULL)
{
printf("%c",bt->data);
PreOrderTraverse(bt->left);
PreOrderTraverse(bt->right);
}
}
void InOrderTraverse(BiTree &bt)
{
if (bt)//如果是空则不用遍历左右子树，如果不空则遍历
{
InOrderTraverse(bt->left);
printf("%c",bt->data);
InOrderTraverse(bt->right);
}
}
void PostOrderTraverse(BiTree &bt )
{
if (bt)
{
PostOrderTraverse(bt->left);
PostOrderTraverse(bt->right);
printf("%c",bt->data);
}
}
void LevelOrderTraverse(BiTree &bt)
{
BiTree q[MAXSIZE];//指针数组
int front,rear;
//初始化队列
front=rear=-1;
if (bt)
{
rear=(rear+1)%MAXSIZE;
q[rear]=bt;//安置根节点
//不断循环，直到队空为止
while (front!=rear)
{
//如果队不空，队头出队
front=(front+1)%MAXSIZE;
printf("%c",q[front]->data);
//左右孩子不空则入队
if (q[front]->left)
{
rear=(rear+1)%MAXSIZE;
q[rear]=q[front]->left;//安置根节点
}
if (q[front]->right)
{
rear=(rear+1)%MAXSIZE;
q[rear]=q[front]->right;//安置根节点
}
}
}
}
int BiTreeEmpty(BiTree &bt)
{
if (!bt)
return 1;
}
int BiTreeDepth(BiTree &bt)
{
int depth=0;
int depthL,depthR;
if (!bt)
depth=0;
else
{
depthL=BiTreeDepth(bt->left);
depthR=BiTreeDepth(bt->right);
depth=1+(depthL>depthR?depthL:depthR);
}
return depth;
}
Elemtype Root (BiTree &bt)
{
if (bt)
{
return bt->data;
}
else
return 0;
}
Elemtype Value(BiTree &p)
{
//P是二叉树中某个节点
return p->data;
}
void Assign(BiTree &bt,Elemtype e)
{
bt->data=e;
}
Elemtype Parent(BiTree &bt,Elemtype e)
{
//e为二叉树bt中的某个节点，输出他的双亲
BiTree q[MAXSIZE],p;
int rear,front;
rear=front =-1 ;
if (bt)
{
rear=(rear+1)%MAXSIZE;
q[rear]=bt;//根节点入队
while (rear!=front)
{
//如果队不空则队头出队
front=(front+1)%MAXSIZE;
p=q[front];
if (p && p->left->data ==e || p && p->right->data == e )
{
//如果P本身不空并且有一个孩子等于E,则返回该双亲节点的值
return p->data;
}
//说明这次没有找到和E相等的节点，则把左孩子和右孩子送入队列
if (p->left)
{
rear=(rear+1)%MAXSIZE;
q[rear]=p->left;
}
if (p->right)
{
rear=(rear+1)%MAXSIZE;
q[rear]=p->right;
}
}
}
}
BiTree findE(BiTree &bt,Elemtype e)
{
BiTree q[MAXSIZE],p;
int rear,front;
rear=front=-1;
if (bt)
{
rear=(rear+1)%MAXSIZE;
q[rear]=bt;//根入队
while (front!=rear)
{
front=(front+1)%MAXSIZE;
p=q[front];//取出队头元素
if (p->data == e)
{
return p;
}
if (p->left)
{
rear=(rear+1)%MAXSIZE;
q[rear]=p->left;//left child enqueue
}
if (p->right)
{
rear=(rear+1)%MAXSIZE;
q[rear]=p->right;//left child enqueue
}
}
}
}
Elemtype LeftChild( BiTree &bt,Elemtype e)
{
//找到指向E的指针
BiTree p=findE(bt,e);
if (p &&p->left )
{//P不为空并且左孩子不为空
return p->left->data;
}
else
return 0;
}
Elemtype RightChild( BiTree &bt,Elemtype e)
{
//找到指向E的指针
BiTree p=findE(bt,e);
if (p &&p->right )
{//P不为空并且左孩子不为空
return p->right->data;
}
else
return 0;
}
BiTree findP(BiTree &bt,Elemtype e)
{
//e为二叉树bt中的某个节点，输出他的双亲
BiTree q[MAXSIZE],p;
int rear,front;
rear=front =-1 ;
if (bt)
{
rear=(rear+1)%MAXSIZE;
q[rear]=bt;//根节点入队
while (rear!=front)
{
//如果队不空则队头出队
front=(front+1)%MAXSIZE;
p=q[front];
if (p && p->left->data ==e || p && p->right->data == e )
{
//如果P本身不空并且有一个孩子等于E,则返回该双亲节点的值
return p;
}
//说明这次没有找到和E相等的节点，则把左孩子和右孩子送入队列
if (p->left)
{
rear=(rear+1)%MAXSIZE;
q[rear]=p->left;
}
if (p->right)
{
rear=(rear+1)%MAXSIZE;
q[rear]=p->right;
}
}
}
}
Elemtype LeftSibling(BiTree &bt,Elemtype e)
{
BiTree parent = findP(bt,e);//找到E元素的双亲指针
if (parent->left)
{
return parent->left->data;
}
}
Elemtype RightSibling(BiTree &bt,Elemtype e)
{
BiTree parent = findP(bt,e);//找到E元素的双亲指针
if (parent->right)
{
return parent->right->data;
}
}
int InsertChild(BiTree &p ,int lr,BiTree &c)
{//插入更简单了！！
if (p)
{
if (lr==0)//把C移到P的左子树上
{
c->right=p->left;
p->left=c;
}else
{
c->right=p->right;
p->right=c;
}
return 1;
}
else
return 0;//P为空
}
void clearBiTree(BiTree &bt)
{
//同样用递归！
if (bt)
{
if (bt->left)
clearBiTree(bt->left);
if (bt->right)
clearBiTree(bt->right);
free(bt);
bt=NULL;
}
}
void DeleteChild(BiTree &p,int LR)
{
// 初始条件: 二叉树T存在,p指向T中某个结点,LR为0或1
// 操作结果: 根据LR为0或1,删除T中p所指结点的左或右子树
if (p)
{
if (LR == 1)
{
clearBiTree(p->left);
}else
{
clearBiTree(p->right);
}
}
}
//非递归实现pre/in/post 遍历二叉树
//使用栈实现中序遍历
typedef BiTree Elemtype1;
typedef struct {
Elemtype1 elem[MAXSIZE];
int top;
}SeqStack;
void initSeqStack(SeqStack &s){
s.top=-1;
}
int stackEmpty(SeqStack &s){
if (s.top==-1)
return 1;
return 0;//或者返回 表达式的真值return s.top==-1;
}
int push(SeqStack &s,Elemtype1 e){
if (s.top>=MAXSIZE-1)
return 0;
else {
s.top++;
s.elem[s.top]=e;
return 1;
}
}
int pop(SeqStack &s,Elemtype1 &e){
if (s.top==-1)
return 0;
else {
e=s.elem[s.top];
s.top--;
return 1;
}
}
int gettop(SeqStack &s,Elemtype1 &e){
if (s.top==-1)
return 0;
else {
e=s.elem[s.top];
return 1;
}
}
//中序遍历非递归算法
void InOrderTraverse2(BiTree &bt)
{
//精髓是把每个结点的地址存入栈中，通过push & pop实现过程
SeqStack s;
initSeqStack(s);
BiTree p=bt;
while (p!=NULL || !stackEmpty(s))
{
//当且仅当两者都空时结束循环
if (p)
{
push(s,p);
p=p->left;
}
else
{
pop(s,p);//弹回根节点
printf("%c ",p->data);//第二次回到根节点时才打印输出
p=p->right;
}
}
}
//先序遍历非递归算法
void PreOrderTraverse2(BiTree p)
{
//这里不加&即为形参，便不用定义新的变量作为移动的指针了
SeqStack s;
initSeqStack(s);
do
{
if (p)
{
printf("%c ",p->data);
push(s,p);
p=p->left;
}
else
{
pop(s,p);
p=p->right;
}
}while (p || !stackEmpty(s));
}
//后序遍历非递归算法
void PostOrderTraverse2(BiTree p)
{
struct
{
BiTree pp;//pointer
int tag;//标记位
}s[MAXSIZE];//定义一个结构体数组,即为一个栈s
//这里struct之前不能加typedef ,因为s[]是结构体数组而不是别名
int top=0;//栈顶指针
while ( p || top>0)
{
while (p)//一直走到最左边
{
top++;
s[top].pp=p;
s[top].tag=0;
p=p->left;
}
if (top>0)
{
if (s[top].tag == 0)
{
//如果栈顶元素标志位为0，即为第二次遇到该结点元素
s[top].tag=1;
p=s[top].pp;
p=p->right;//继续向右孩子深入
}
else
{
p=s[top].pp;
printf("%c ",p->data);//如果是第二次遇到该节点则输出
top--;
p=NULL;//不用往深处走了，直接退栈继续循环
}
}
}
}
//找到叶子结点个数，左右孩子都空
int findleaf(BiTree p,int &count1)
{
if (p)
{
if ( !p->left &&!p->right)
count1++;
findleaf(p->left,count1);
findleaf(p->right,count1);
}
}
int findrightleaf(BiTree p,int &count1)
{
if (p)
{
if (!p->right)
count1++;
findleaf(p->left,count1);
findleaf(p->right,count1);
}
}
void PreOrderfindall(BiTree &bt,int &count2)
{
if (bt!=NULL)
{
count2++;
PreOrderfindall(bt->left,count2);
PreOrderfindall(bt->right,count2);
}
}
int findleafinforest(BiTree &bt)
{
//假设bt代表一个森林，求森林中叶子的个数
//利用理论：假设森林中有N个非终端结点，则二叉树中右指针域为空的结点个数为N+1
if (bt)
{
int count1 = 0;
findrightleaf(bt,count1);
//count即为二叉树中右指针域为空的结点的个数
int count2=0;
PreOrderfindall(bt,count2);
//count2即为二叉树中所有节点的个数，也就是森林总结点个数
return (count2-count1+1);
}
else
return 0;
}
//建立中序线索二叉树并遍历
typedef enum PointerTag {link=0,thread=1};//link=0 指针，thread=1 线索
typedef struct BithrNode{
Elemtype data;
struct BithrNode *left,*right;
PointerTag ltag,rtag;
}BithrNode,*BithrTree;
int InOrderThreading(BithrTree &thrt,BithrTree bt)
{
void Inthreading(BithrTree &p,BithrTree &pre);
//将普通二叉树线索化成thrt
//1.建立头结点
thrt = (BithrTree)malloc(sizeof(BithrNode));
BithrTree pre;
thrt->right=thrt;
thrt->ltag=link;
thrt->rtag=thread;
if (!bt)
thrt->left=thrt;
else
{
thrt->left = bt;
pre=thrt;//前驱指针指向头结点
Inthreading(bt,pre);
//线索化二叉树
pre->right=thrt;
pre->rtag=thread;
thrt->right=pre;
//线索化最后pre指向树中最后一个结点，进行最后的处理：连接树中最后一个结点与头结点，形成循环的线索树
}
}
void Inthreading(BithrTree &p,BithrTree &pre)
{
if (p)
{
Inthreading(p->left,pre);
if (!p->left)//P的左孩子为空
{
p->ltag=thread;
p->left=pre;
}
if (!pre->right)//Pre的右孩子为空
{
pre->rtag=thread;
pre->right=p;
}
pre=p;
Inthreading(p->right,pre);
}
}
//遍历线索二叉树
int InOrderTraverseThrtree(BithrTree &thrt)
{
BithrTree p=thrt->left;
while (p != thrt)
{
//线索树不为空时
while(p && p->ltag !=thread)
{
p=p->left;
}
printf("%c",p->data);
while(p->rtag == thread && p->right != thrt)
{
//如果p->right==T,则不用继续往右走
p=p->right;
printf("%c",p->data);
}
p=p->right;//没有右线索，只有右孩子
}
}
void CreateBithrTree(BithrTree &bt)
{
Elemtype e;
scanf("%c",&e);
if (e==' ')
{
bt=NULL;//如果输入空格则将该结点置空
}
else
{
bt=(BithrTree)malloc(sizeof(BithrNode));
bt->data=e;
CreateBithrTree(bt->left);
CreateBithrTree(bt->right);
}
}
int main()
{
cout<<"---二叉树的基本操作实现 twomeng---"<<endl;
cout<<"--------------------------------------"<<endl;
cout<<"1 InsertChild()"<<endl;
cout<<"2 DeleteChild()"<<endl;
cout<<"3 PreOrderTraverse()"<<endl;
cout<<"4 InOrderTraverse()"<<endl;
cout<<"5 PostOrderTraverse()"<<endl;
cout<<"6 Parent()"<<endl;
cout<<"7 LeftChild()"<<endl;
cout<<"8 RightChild()"<<endl;
cout<<"9 leftSibling()"<<endl;
cout<<"10 RightSibling()"<<endl;
cout<<"11 Root()"<<endl;
cout<<"12 Value()"<<endl;
cout<<"13 Assign()"<<endl;
cout<<"14 LevelOrderTraverse()"<<endl;
cout<<"15 BiTreeDepth()"<<endl;
cout<<"16 findleaf()"<<endl;
cout<<"17 PreOrderTraverse2()"<<endl;
cout<<"18 InOrderTraverse2()"<<endl;
cout<<"19 PostOrderTraverse2()"<<endl;
cout<<"20 findleafinforest()"<<endl;
cout<<"21 线索化二叉树并中序遍历输出"<<endl;
cout<<"--------------------------------------"<<endl;
ll1:cout<<"请输入您选择的函数序号:)"<<endl;
int number;
cin>>number;
BiTree bt,p;
InitBiTree(bt);
Elemtype e;int count3 = 0;
cout<<"请按照先序顺序输入一棵树！没有结点的地方请输入空格"<<endl;
fflush(stdin);
CreateBiTree(bt);//创建一个可以公用的二叉树bt;
switch(number)
{
case 1:
PreOrderTraverse(bt);
BiTree c;
InitBiTree(c);
cout<<"请按照先序顺序输入一棵Insert树！没有结点的地方请输入空格"<<endl;
fflush(stdin);
CreateBiTree(c);
LevelOrderTraverse(c);
cout<<"输入完毕！"<<endl;
cout<<"如果您想插入到左子树，输入0；如果您想插入到右子树，输入1 "<<endl;
int x;cin>>x;
InsertChild(bt,x,c);
PreOrderTraverse(bt);
break;
case 2:
PreOrderTraverse(bt);
cout<<endl;
cout<<"删除左子树，请输入1；删除右子树，请输入0"<<endl;
cin>>x;
DeleteChild(bt,x);
PreOrderTraverse(bt);
break;
case 3:
PreOrderTraverse(bt);
break;
case 4:
InOrderTraverse(bt);
break;
case 5:
PostOrderTraverse(bt);
break;
case 6:
char ch;
cout<<"请输入您要寻找的节点数值"<<endl;
cin>>ch;
cout<<Parent(bt,ch);
break;
case 7:
cout<<"输入E的值"<<endl;
cin>>e;
cout<<LeftChild(bt,e);
break;
case 8:
cout<<"输入E的值"<<endl;
cin>>e;
cout<<RightChild(bt,e);
break;
case 9:
cout<<"输入E的值"<<endl;
cin>>e;
cout<<LeftSibling(bt,e);
break;
case 10:
cout<<"输入E的值"<<endl;
cin>>e;
cout<<RightSibling(bt,e);
break;
case 11:
cout<<Root(bt);
break;
case 12:
p=bt->left;
cout<<Value(p)<<endl;
break;
case 13:
p=bt->left;
cout<<"请输入您要赋的值"<<endl;
cin>>e;
Assign(p,e);
cout<<"assign函数调用成功！其中的值现在为："<<endl;
cout<<p->data<<endl;
break;
case 14:
LevelOrderTraverse(bt);
break;
case 15:
cout<<BiTreeDepth(bt)<<endl;
break;
case 16:
findleaf(bt,count3);
cout<<count3<<endl;
break;
case 17:
PreOrderTraverse2(bt);
break;
case 18:
InOrderTraverse2(bt);
break;
case 19:
PostOrderTraverse2(bt);
break;
case 20:
cout<<findleafinforest(bt)<<endl;
break;
case 21:
BithrTree bt;
CreateBithrTree(bt);
BithrTree thrt;
cout<<"线索化二叉树成功！"<<endl;
InOrderThreading(thrt,bt);
InOrderTraverseThrtree(thrt);
cout<<"遍历线索二叉树成功！"<<endl;
break;
}
cout<<"您是否想要继续调用函数？yes/no"<<endl;
string s;cin>>s;
if (!s.compare("yes"))
goto ll1;
else
return 0;
}
我这个哈夫曼树貌似有点问题，结果不太对啊。。有空再调一调
哈夫曼测试数据：
8
5 29 7 8 14 23 3 11
未调试出来的哈夫曼：
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <string.h>
#include <math.h>
#define MAXSIZE 20
using namespace std;
//哈夫曼编码
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char* *Huffmancode;//定义一个指针数组存放编码
int min(HuffmanTree t,int i)
{ // 函数void select()调用
int j,flag;
unsigned int k=UINT_MAX; // 取k为不小于可能的值
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}
void select(HuffmanTree t,int i,int &s1,int &s2)
{ // s1为最小的两个值中序号小的那个
int j;
s1=min(t,i);
s2=min(t,i);
if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}
}
void HuffmanCoding(HuffmanTree &ht,Huffmancode &hc,int *w,int n)
{
int i;
if (n<=1)
return;//判断N(字符个数)的输入是否合法
int m;//哈夫曼树结点个数
m = 2*n-1;
//哈夫曼树是一个数组，我们要先定义出来， 再初始化数组
ht = (HuffmanTree )malloc((m+1)*sizeof(HTNode));//0 单元未用
//给初始字符赋权值
HuffmanTree p;
p=ht;
p++;
int *t;t=w;
for (i=1,t++;i<=n;i++,p++,t++)
{
(*p).weight=*t;
(*p).lchild=0;
(*p).rchild=0;
(*p).parent=0;
}
//给还没计算的结点赋值0
for (p=&ht[n+1],i=n+1;i<=m;i++,p++)
{
(*p).weight=0;
(*p).lchild=0;
(*p).rchild=0;
(*p).parent=0;
}
//建立哈夫曼树
for(int i=n+1;i<=m;i++)
{
int s1,s2;
select(ht,i-1,s1,s2);//最小的两个结点序号为s1,s2
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
//show()
// for (i=1 ; i<=m ; i++)
// {
// cout<< ht[i].weight <<" " <<ht[i].parent <<" "<<ht[i].lchild <<" "<<ht[i].rchild<<endl;
// }
//进行哈夫曼编码
int c,f;
hc=(Huffmancode)malloc(sizeof(char *)*(n+1));//头指针向量
char *cd = (char *)malloc(sizeof(char)*n);//一个字符编码的数组指针
cd[n-1]='\0';
for (int i=1;i<=n;i++)//循环N个字符
{
int start = n-1;//从叶节点开始往上编
for (c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)
{
//定义C是为了不动I，顺次往上找双亲，判断自己是双亲的左子树还是右子树
if (ht[f].lchild == c)
cd[--start]='0';
else
cd[--start]='1';
}
for (int x = n-start;x<n;x++)
cout<<cd[x];
hc[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(hc[i],cd);
//cout<<hc[i]<<endl;
}
}
int main()
{
int *w,*ww;
int n;
cout<<"请输入字符数N"<<endl;
cin>>n;
w=(int *)malloc(sizeof(int)*(n+1));//0号单元未用
ww=w;
int i;
cout<<"请依次输入字符的权值"<<endl;
for (ww++,i=1;i<=n;i++,ww++)
{
cin>> *ww;
}
HuffmanTree ht;
Huffmancode hc;
HuffmanCoding(ht,hc,w,n);
Huffmancode q=hc;
for (int k=1;k<=n;k++)
puts(hc[k]);
return 0;
}
实验报告4 图的有关操作
无向网的创建、求度、深度遍历、广度遍历
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#define MAX_VERTEX_NUM 20
using namespace std;
//1.建立无向网的邻接表
typedef int InfoType;//权值
typedef char VertexType ;
typedef struct ArcNode
{
int adjvex;//该弧的弧尾
struct ArcNode *nextarc;//指向的下一个弧
InfoType *info;
}ArcNode;
typedef struct VNode
{
VertexType data;//顶点类型和数据
ArcNode *firstarc;//指向的第一条邻接弧
}VNode,AdjList[MAX_VERTEX_NUM];//表头
typedef struct
{
AdjList vertices;//
int vexnum,arcnum;
int kind; //DG 0 DN 1 UDG 2 UDN 3
}ALGraph;//adjacency list graph 邻接表
int locate(ALGraph &g,char v)
{
int i=0;
for (i;i<g.vexnum;i++)
{
if (g.vertices[i].data == v)
return i;
}
}
void createUDN(ALGraph &g)
{
cout<<"构造无向网：请输入网的顶点个数和弧的个数"<<endl;
cin>>g.vexnum>>g.arcnum;
g.kind = 3;
//构造顶点向量
int i,j,k;
//请输入每个顶点的值
for (i=0;i<g.vexnum;i++)//初始化
{
cin>> g.vertices[i].data;
g.vertices[i].firstarc = NULL;//头结点置空
}
//构造链表们
char v1,v2;
int w;
cout<<"请输入每条弧的弧头 、弧尾、权值"<<endl;
for(k=0;k<g.arcnum;k++)
{
cin>>v1>>v2>>w;
i = locate(g,v1);//弧尾
j = locate(g,v2);//弧头
ArcNode *p ;
p = (ArcNode *)malloc(sizeof(ArcNode));//新建一块表结点空间
p->adjvex = j;
p->info = (int *)malloc(sizeof(int));//对于网，用来存放权值
p->info = &w;
p->nextarc = g.vertices[i].firstarc;//置空
g.vertices[i].firstarc = p;//头插法建表
if (g.kind >= 2) //如果是无向图或者无向网，需要做对称
{
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = i;
p->info = (int *)malloc(sizeof(int));
p->info = &w;
p->nextarc = g.vertices[j].firstarc ;
g.vertices[j].firstarc = p;
}
}
}
//求邻接表的入度和出度
int* out(ALGraph &g)
{
int *p,*q;
p = (int *) malloc((g.vexnum)*sizeof(int));//申请一个动态数组，存放的是每一个顶点对应的出度
q=p;
int i =0;
int cou =1;//计数器
for (i;i<g.vexnum ; i++)
{
//对每一个结点进行计算出度，循环一遍
ArcNode *q=g.vertices[i].firstarc;//q指向第一个结点
while (q->nextarc)
{
cou++;
q=q->nextarc;
}
*p = cou;
p++;
cou=0;//清空计数器
}
return q;
}
int * in(ALGraph &g)
{
int *p;
p = (int *)malloc((g.vexnum)*sizeof(int));
int i=0;
int j=0;
int cou=0;
ArcNode *q;
for (i;i<g.vexnum;i++)
{//外层循环遍历每个结点，计算入度
for (j;j<g.vexnum;j++)
{
//内层循环遍历全部表元素
q = g.vertices[j].firstarc;
while (q->nextarc)
{
if (q->adjvex == i)
cou++;
}
}
*p=cou;
p++;
cou=0;
}
return p;
}
//深度优先搜索
bool visited[MAX_VERTEX_NUM];
void DFSTraverse(ALGraph g)
{
void DFS(ALGraph g,int v);
int v;
//visited数组初始化
for (v=0;v<g.vexnum;v++)
visited[v]=false;
for(v=0;v<g.vexnum;v++)
if (!visited[v])//如果结点未被访问过 ,则深度遍历该结点
DFS(g,v);
}
int FirstAdjVex(ALGraph &g,int v)
{
//对于无向网来说，每个顶点必定有一个邻接点
return g.vertices[v].firstarc->adjvex;//返回V结点的第一个邻接结点的序号
}
int NextAdjVex(ALGraph &g,int v,int w)
{//必须要讨论有没有除了第一个邻接点之外的第二个邻接点
//注意要找
ArcNode *p=g.vertices[v].firstarc;
while (p->adjvex!=w)
p=p->nextarc;
p = p->nextarc;
if (!p)
return -1;
else
return p->adjvex;//所以我们的条件为w>=0
}
void DFS(ALGraph g,int v)
{
visited[v]=true;//置标志
cout<<g.vertices[v].data<<" ";
int w;
for (w = FirstAdjVex(g,v);w>=0;w=NextAdjVex(g,v,w))
if (!visited[w])
DFS(g,w);
}
//广度优先搜索
typedef int Elemtype;
//进队出队为序号，输出时打印char数据，这样比较方便
typedef struct
{
Elemtype data[MAX_VERTEX_NUM];
int rear,front;
}SeqQueue;
void InitQueue(SeqQueue &q)
{
q.rear = q.front = -1;
}
void EnQueue(SeqQueue &q,Elemtype e )
{
q.rear = (q.rear+1)%MAX_VERTEX_NUM;
q.data[q.rear] = e;
}
void deQueue(SeqQueue &q,Elemtype &e)
{
if (q.rear == q.front)
{
printf("empty queue");
}
q.front = (q.front + 1)% MAX_VERTEX_NUM;
e = q.data[q.front];
}
int QueueEmpty(SeqQueue &q)
{
return q.rear == q.front;
}
void BFSTraverse(ALGraph &g)
{
int v,u,w;
for (v=0;v<g.vexnum;v++)
visited[v]=false;
SeqQueue q;
InitQueue(q);
for (v=0;v<g.vexnum;v++)
{
if (!visited[v])
{
visited[v]=true;
printf("%c ",g.vertices[v].data);
EnQueue(q,v);
while (!QueueEmpty(q))
{
deQueue(q,u);
for ( w = FirstAdjVex(g,u);w>=0;w=NextAdjVex(g,u,w))
{
if (!visited[w])
{
visited[w]=true;
printf("%c ",g.vertices[w].data);
EnQueue(q,w);
}
}
}
}
}
}
int main()
{
ALGraph g;
createUDN(g);
//1.求无向网的度
cout<<"无向图的度为"<<endl;
int *p;p=out(g);int i=0;
for (p,i;i<g.vexnum;i++,p++)
cout<<*p<<" ";
cout<<endl;
//2.深度优先遍历
cout<<"深度优先遍历无向图"<<endl;
DFSTraverse(g);
//3.广度优先遍历
cout<<"广度优先遍历无向图"<<endl;
BFSTraverse(g);
return 0;
}
实验报告内容：
１．键盘输入数据，建立一个有向图的邻接表。
２．输出该邻接表。
*３．建立一个无向图的十字链表。
４．在有向图的邻接表的基础上计算各顶点的度，并输出。
５．以有向图的邻接表为基础实现输出它的拓扑排序序列。
*６．采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。
７．采用邻接表存储实现无向图的深度优先非递归遍历。
８．采用邻接表存储实现无向图的广度优先遍历。
*９．采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。
*10．判断无向图任意两个顶点间是否有路径，若有输出路径上的顶点序列。
11．在主函数中设计一个简单的菜单，分别调试上述算法。
*12．综合训练：为计算机专业设计教学计划：4个学年，每学年2个学期，开设50门课程，每学期所开课程门数尽量均衡，课程的安排必须满足先修关系。
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
using namespace std;
//1.定义有向网的邻接表结构
typedef int InfoType;//权值
typedef char VertexType ;
typedef struct ArcNode
{
int adjvex;//该弧的弧尾
struct ArcNode *nextarc;//指向的下一个弧
InfoType info;
}ArcNode;
typedef struct VNode
{
VertexType data;//顶点类型和数据
ArcNode *firstarc;//指向的第一条邻接弧
}VNode,AdjList[MAX_VERTEX_NUM];//表头
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
int kind; //DG 0 DN 1 UDG 2 UDN 3 kind =1
}ALGraph;//adjacency list graph 邻接表
//一个桟
typedef int Elemtype;
typedef struct
{
VertexType data[MAX_VERTEX_NUM];
int top;
}SeqStack;
void InitStack(SeqStack &s)
{
s.top=-1;
}
int isEmpty(SeqStack &s)
{
return s.top==-1;
}
void push(SeqStack &s,Elemtype e)
{
if (s.top == MAX_VERTEX_NUM)
printf("full stack!");
s.top++;
s.data[s.top]=e;
}
void pop(SeqStack &s,Elemtype &e)
{
if (isEmpty(s))
printf("empty stack !");
e = s.data[s.top--];
}
int getTop(SeqStack &s)
{
return s.data[s.top];
}
//2.创建有向网
//定位函数
int locate(ALGraph &g,char v)
{
int i=0;
for (i;i<g.vexnum;i++)
{
if (g.vertices[i].data == v)
return i;
}
}
void createDN(ALGraph &g)
{
cout<<"构造有向网：请输入网的顶点个数和弧的个数"<<endl;
cin>>g.vexnum>>g.arcnum;
g.kind = 1;
//构造顶点向量
int i,j,k;
cout<<"请输入每个顶点的值"<<endl;
for (i=0;i<g.vexnum;i++)//初始化
{
cin>> g.vertices[i].data;
g.vertices[i].firstarc = NULL;//头结点置空
}
//构造链表们
char v1,v2;
int w;
cout<<"请输入每条弧的弧头 、弧尾、权值"<<endl;
for(k=0;k<g.arcnum;k++)
{
cin>>v1>>v2>>w;
i = locate(g,v1);//弧尾
j = locate(g,v2);//弧头
ArcNode *p ;
p = (ArcNode *)malloc(sizeof(ArcNode));//新建一块表结点空间
p->adjvex = j;
// InfoType *info;
// p->info = (int *)malloc(sizeof(int));//对于网，用来存放权值
// p->info = &w;
p->info = w;
p->nextarc = g.vertices[i].firstarc;//置空
g.vertices[i].firstarc = p;//头插法建表
}
}
// 创建无向网
void createUDN(ALGraph &g)
{
cout<<"构造无向网：请输入网的顶点个数和弧的个数"<<endl;
cin>>g.vexnum>>g.arcnum;
g.kind = 3;
//构造顶点向量
int i,j,k;
//请输入每个顶点的值
for (i=0;i<g.vexnum;i++)//初始化
{
cin>> g.vertices[i].data;
g.vertices[i].firstarc = NULL;//头结点置空
}
//构造链表们
char v1,v2;
int w;
cout<<"请输入每条弧的弧头 、弧尾、权值"<<endl;
for(k=0;k<g.arcnum;k++)
{
cin>>v1>>v2>>w;
i = locate(g,v1);//弧尾
j = locate(g,v2);//弧头
ArcNode *p ;
p = (ArcNode *)malloc(sizeof(ArcNode));//新建一块表结点空间
p->adjvex = j;
p->info = w;
p->nextarc = g.vertices[i].firstarc;//置空
g.vertices[i].firstarc = p;//头插法建表
if (g.kind >= 2) //如果是无向图或者无向网，需要做对称
{
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = i;
p->info = w;
p->nextarc = g.vertices[j].firstarc ;
g.vertices[j].firstarc = p;
}
}
}
//3.输出邻接表
void printALGraph(ALGraph &g)
{
int i=0;
ArcNode *p;
for (i;i< g.vexnum ;i++)
{
printf("弧头：%c ",g.vertices[i].data);
p=g.vertices[i].firstarc;//P指向链表的第一个结点
while (p)
{
printf("(弧尾：%d,权值：%d) ",p->adjvex,p->info);
p=p->nextarc;
}
cout<<endl;
}
}
// 4.有向网的十字链表
typedef struct ArcBox
{
int tailvex,headvex;
struct ArcBox *hlink,*tlink;
InfoType info;
}ArcBox;
typedef struct VexNode
{
VertexType data;
ArcBox *firstin,*firstout;
}VexNode;
typedef struct
{
VexNode xlist[MAX_VERTEX_NUM];//表头向量
int vexnum,arcnum;
}OLGraph;
int locate(OLGraph &g,char v)
{
int i=0;
for (i;i<g.vexnum;i++)
{
if (g.xlist[i].data == v)
{
return i;
}
}
}
void createOLDN(OLGraph &g)
{
cout <<"请输入有向网的顶点个数、弧的个数"<<endl;
cin>>g.vexnum>>g.arcnum;
int i,j,k;
cout<<"请输入顶点值"<<endl;
for (i=0;i<g.vexnum;i++)
{
cin>>g.xlist[i].data;
g.xlist[i].firstin=g.xlist[i].firstout=NULL;
}
cout<<"请输入每条弧的弧头和弧尾和权值"<<endl;
char v1,v2;int w;
ArcBox *p;
fflush(stdin);
for (k=0;k<g.arcnum;k++)
{
cin>>v1>>v2>>w;
i=locate(g,v1);
j=locate(g,v2);
p=(ArcBox *)malloc(sizeof(ArcBox));
//对弧结点赋值
p->headvex = j;//弧的弧头
p->tailvex = i;//弧的弧尾 逆邻接表
p->hlink = g.xlist[j].firstin;//弧头相同的结点 逆邻接表
p->tlink = g.xlist[i].firstout;//弧尾相同的结点
p->info = w;
g.xlist[j].firstin = g.xlist[i].firstout = p;
}
}
//输出有向网的十字链表，分为邻接表和逆邻接表
void printOLGraph(OLGraph &g)
{
cout<<"输出邻接表"<<endl;
int i=0;
ArcBox *p;
for (i;i< g.vexnum ;i++)
{
printf("弧头：%c ",g.xlist[i].data);
p=g.xlist[i].firstout;//P指向链表的第一个结点
while (p)
{
printf("(弧尾：%d,权值：%d) ",p->headvex,p->info);
p=p->tlink;
}
cout<<endl;
}
cout<<"输出逆邻接表"<<endl;
for (i=0;i< g.vexnum ;i++)
{
printf("弧头：%c ",g.xlist[i].data);
p=g.xlist[i].firstin;//P指向链表的第一个结点
while (p)
{
printf("(弧尾：%d,权值：%d) ",p->tailvex,p->info);
p=p->hlink;
}
cout<<endl;
}
}
//5.无向图的十字链表
void createOLUDG(OLGraph &g)
{
cout <<"请输入有向网的顶点个数、弧的个数"<<endl;
cin>>g.vexnum>>g.arcnum;
int i,j,k;
cout<<"请输入顶点值"<<endl;
for (i=0;i<g.vexnum;i++)
{
cin>>g.xlist[i].data;
g.xlist[i].firstin=g.xlist[i].firstout=NULL;
}
cout<<"请输入每条弧的弧头和弧尾"<<endl;
char v1,v2;
ArcBox *p;
fflush(stdin);
for (k=0;k<g.arcnum;k++)
{
cin>>v1>>v2;
i=locate(g,v1);
j=locate(g,v2);
p=(ArcBox *)malloc(sizeof(ArcBox));
//对弧结点赋值
p->headvex = j;//弧的弧头
p->tailvex = i;//弧的弧尾 逆邻接表
p->hlink = g.xlist[j].firstin;//弧头相同的结点 逆邻接表
p->tlink = g.xlist[i].firstout;//弧尾相同的结点
g.xlist[j].firstin = g.xlist[i].firstout = p;
//无向图做对称
p=(ArcBox *)malloc(sizeof(ArcBox));
//对弧结点赋值
p->headvex = i;//弧的弧头
p->tailvex = j;//弧的弧尾 逆邻接表
p->hlink = g.xlist[i].firstin;//弧头相同的结点 逆邻接表
p->tlink = g.xlist[j].firstout;//弧尾相同的结点
g.xlist[i].firstin = g.xlist[j].firstout = p;
}
}
//输出无向图
void printOLGraph2(OLGraph &g)
{
cout<<"输出邻接表"<<endl;
int i=0;
ArcBox *p;
for (i=0;i< g.vexnum ;i++)
{
printf("弧头：%c->",g.xlist[i].data);
p=g.xlist[i].firstout;//P指向链表的第一个结点
while (p)
{
printf("%d->",p->headvex);
p=p->tlink;
}
cout<<"NULL"<<endl;
}
cout<<"输出逆邻接表"<<endl;
for (i=0;i< g.vexnum ;i++)
{
printf("弧头：%c->",g.xlist[i].data);
p=g.xlist[i].firstin;//P指向链表的第一个结点
while (p)
{
printf("%d->",p->tailvex);
p=p->hlink;
}
cout<<"NULL"<<endl;
}
}
//6.求邻接表的入度和出度
int* out(ALGraph &g)
{
int *p,*q;
p = (int *) malloc((g.vexnum)*sizeof(int));//申请一个动态数组，存放的是每一个顶点对应的出度
q=p;
int i =0;
int cou =0;//计数器
for (i=0;i<g.vexnum ; i++)
{
//对每一个结点进行计算出度，循环一遍
ArcNode *q=g.vertices[i].firstarc;//q指向第一个结点
while (q)
{
cou++;
q=q->nextarc;
}
*p = cou;
p++;
cou=0;//清空计数器
}
return q;
}
int * in(ALGraph &g)
{
int *p;
p = (int *)malloc((g.vexnum)*sizeof(int));
int i=0;
int j=0;
int cou=0;
ArcNode *q;
for (i=0;i<g.vexnum;i++)
{//外层循环遍历每个结点，计算入度
for (j=0;j<g.vexnum;j++)
{
//内层循环遍历全部表元素
q = g.vertices[j].firstarc;
while (q)
{
if (q->adjvex == i)
cou++;
q=q->nextarc;
}
}
p[i]=cou;
cou=0;
}
return p;
}
int *InAndOut(ALGraph &g)
{
int *p=in(g);
int *q=out(g);
int *k;
k=(int *)malloc((g.vexnum)*sizeof(int));
for (int i=0;i<g.vexnum;i++)
{
k[i]=p[i]+q[i];
}
return k;
}
//7.深度优先搜索
bool visited[MAX_VERTEX_NUM];
void DFSTraverse(ALGraph g)
{
void DFS(ALGraph g,int v);
int v;
//visited数组初始化
for (v=0;v<g.vexnum;v++)
visited[v]=false;
for(v=0;v<g.vexnum;v++)
if (!visited[v])//如果结点未被访问过 ,则深度遍历该结点
DFS(g,v);
}
int FirstAdjVex(ALGraph &g,int v)
{
//对于无向网来说，每个顶点必定有一个邻接点
return g.vertices[v].firstarc->adjvex;//返回V结点的第一个邻接结点的序号
}
int NextAdjVex(ALGraph &g,int v,int w)
{//必须要讨论有没有除了第一个邻接点之外的第二个邻接点
//注意要找
ArcNode *p=g.vertices[v].firstarc;
while (p->adjvex!=w)
p=p->nextarc;
p = p->nextarc;
if (!p)
return -1;
else
return p->adjvex;//所以我们的条件为w>=0
}
void DFS(ALGraph g,int v)
{
visited[v]=true;//置标志
cout<<g.vertices[v].data<<" ";
int w;
for (w = FirstAdjVex(g,v);w>=0;w=NextAdjVex(g,v,w))
if (!visited[w])
DFS(g,w);
}
// 非递归
/*
1.栈初始化
2.输出起始顶点；起始顶点改为“已访问”标记；将起始顶点进桟
3.重复直到桟空
3.1 取栈顶元素（不出桟）
3.2 栈顶元素顶点存在未被访问过的邻接点W，则
3.2.1 输出顶点W
3.2.2 将顶点W改为已访问标志
3.2.3 将顶点W进桟
3.3 否则，当前顶点退桟
*/
int hasNextAdjVex(ALGraph &g,int h)
{
//找到H的未被访问过的邻接点
ArcNode *p=g.vertices[h].firstarc;
if (!p)
return -1;
while (visited[p->adjvex])
{
p=p->nextarc;
}
return p->adjvex;
}
void DFS_2(ALGraph &g,int v)
{
SeqStack s;
InitStack(s);
printf("%c",g.vertices[v].data);
visited[v]=true;
push(s,v);
int h,w,e;
while (!isEmpty(s))
{
h=getTop(s);
w=hasNextAdjVex(g,h);
if (w>=0)
{
printf("%c",g.vertices[w].data);
visited[w]=true;
push(s,w);
}
else
pop(s,e);
}
}
void DFSTraverse_2(ALGraph g)
{
int v;
//visited数组初始化
for (v=0;v<g.vexnum;v++)
visited[v]=false;
for(v=0;v<g.vexnum;v++)
if (!visited[v])//如果结点未被访问过 ,则深度遍历该结点
DFS_2(g,v);
}
//8.广度优先搜索
typedef int Elemtype;
//进队出队为序号，输出时打印char数据，这样比较方便
typedef struct
{
Elemtype data[MAX_VERTEX_NUM];
int rear,front;
}SeqQueue;
void InitQueue(SeqQueue &q)
{
q.rear = q.front = -1;
}
void EnQueue(SeqQueue &q,Elemtype e )
{
q.rear = (q.rear+1)%MAX_VERTEX_NUM;
q.data[q.rear] = e;
}
void deQueue(SeqQueue &q,Elemtype &e)
{
if (q.rear == q.front)
{
printf("empty queue");
}
q.front = (q.front + 1)% MAX_VERTEX_NUM;
e = q.data[q.front];
}
int QueueEmpty(SeqQueue &q)
{
return q.rear == q.front;
}
void BFSTraverse(ALGraph &g)
{
int v,u,w;
for (v=0;v<g.vexnum;v++)
visited[v]=false;
SeqQueue q;
InitQueue(q);
for (v=0;v<g.vexnum;v++)
{
if (!visited[v])
{
visited[v]=true;
printf("%c ",g.vertices[v].data);
EnQueue(q,v);
while (!QueueEmpty(q))
{
deQueue(q,u);
for ( w = FirstAdjVex(g,u);w>=0;w=NextAdjVex(g,u,w))
{
if (!visited[w])
{
visited[w]=true;
printf("%c ",g.vertices[w].data);
EnQueue(q,w);
}
}
}
}
}
}
//9.拓扑排序
// 建立辅助数组indegree 存放每个顶点的入度
void FindInDegree(ALGraph &g,int in[])
{
int i=0,j=0;
ArcNode *p;
int count=0;
for (i;i<g.vexnum;i++)
{
for (j=0;j<g.vexnum;j++)
{
p=g.vertices[j].firstarc;
while (p)
{
if (p->adjvex == i)
count++;
p=p->nextarc;
}
}
in[i] = count;
cout<<count<<' ' ;
count = 0;
}
}
//这里需要一个栈
//拓扑排序算法
void TopologicalSort(ALGraph g)
{
int indegree[g.vexnum];//定义一个入度的辅助数组
int i,k;
for (i=0;i<g.vexnum;i++)
indegree[i]=0;
FindInDegree(g,indegree);
SeqStack s;
InitStack(s);
//如果入度为零则进栈
for (i=0;i<g.vexnum;i++)
{
if (!indegree[i])
push(s,i);//序号进栈
}
int count = 0;//对输出顶点个数进行计数
ArcNode *p;
while (!isEmpty(s))
{
pop(s,i);
printf("%d:%c ",i,g.vertices[i].data);
count++;
for (p=g.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if (!(--indegree[k]))
push(s,k);
}
}
if (count < g.vexnum)
printf("该有向图有回路\n");
else
printf("该有向图无回路\n");
}
//10. PRIM 算法
//prim algorithm
//邻接矩阵
typedef int VRType;
typedef int VertexType2;
typedef int InfoType;
typedef struct ArcCell
{
VRType adj;
InfoType info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType2 vex[MAX_VERTEX_NUM];//顶点向量
AdjMatrix arcs;//邻接矩阵
int vexnum,arcnum;
int kind;
}MGraph;
int locate(MGraph &g,int v)
{
int i;
for (i=0;i<g.vexnum;i++)
{
if (g.vex[i] == v)
return i;
}
}
//邻接数组创建无向图
void createUDG(MGraph &g)
{
cout<<"请输入无向图的顶点个数和边的个数"<<endl;
cin>>g.vexnum>>g.arcnum;
int i,j,k;
//初始化顶点向量
for (i=0;i<g.vexnum;i++)
cin>>g.vex[i];
//初始化邻接矩阵
for (i=0;i<g.vexnum;i++)
for (j=0;j<g.vexnum;j++)
g.arcs[i][j].adj = INFINITY;
cout<<"请输入每条边的顶点和权值"<<endl;
for (k=0;k<g.arcnum;k++)
{
int v1,v2;
int w;
cin>>v1>>v2>>w;
i=locate(g,v1);
j=locate(g,v2);
g.arcs[i][j].adj=w;
g.arcs[j][i].adj=g.arcs[i][j].adj;//无向图为对称的！
}
}
typedef struct node {
VertexType2 adjvex;//权最小的顶点
VRType lowcost;//最小的权
}closedge[MAX_VERTEX_NUM];
int mininum(closedge close,int n)
{
int i=0;
int min = 999;
int k;
for (i=1;i<n;i++)
{
if (close[i].lowcost < min && close[i].lowcost !=0)
{
min = close[i].lowcost;
k = i;
}
}
return k;
//k记录最小权值顶点的序号
}
//最小生成树——PRIM算法
void MinispanTree_PRIM(MGraph g,VertexType2 u)
{
closedge close;
int k=locate(g,u);
int i,j;
//辅助数组初始化
for (j=0;j<g.vexnum;j++)
if (j!=k)
{
close[j].adjvex=u;
close[j].lowcost = g.arcs[k][j].adj;
}
close[k].lowcost = 0;
for (i=1;i<g.vexnum;i++)
{
k = mininum(close,g.vexnum);
cout<<"("<<close[k].adjvex<<","<<g.vex[k]<<")";//输出这条边的两个顶点
close[k].lowcost = 0;
for (j=0;j<g.vexnum;j++)
{
if (g.arcs[k][j].adj < close[j].lowcost)
{
close[j].adjvex = g.vex[k];
close[j].lowcost = g.arcs[k][j].adj;
}
}
}
}
int main()
{
cout << "------------------------------------"<<endl;
cout << "1.createDN():建立一个有向网的邻接表 "<<endl;
cout << "2.printALGraph():输出邻接表"<<endl;
cout << "3.createOLDN():创建有向网十字链表并输出其邻接表和逆邻接表"<<endl;
cout << "4.createOLUDG():创建无向图十字链表并输出其邻接表和逆邻接表"<<endl;
cout << "5.in():求有向图/网的出度"<<endl;
cout << "6.out():求有向图/网的入度"<<endl;
cout << "7.InAndOut():求有向图的度"<<endl;
cout << "8.DFSTraverse():无向图的深度优先遍历"<<endl;
cout << "9.BFSTraverse():无向图的广度优先遍历"<<endl;
cout << "10.TopologicalSort():以有向图的邻接表为基础实现输出它的拓扑排序序列。"<<endl;
cout << "11.MinispanTree_PRIM():采用邻接矩阵存储实现无向图的最小生成树的PRIM算法"<<endl;
cout << "12.DFS_2():非递归实现深度优先搜索"<<endl;
cout << "------------------------------------"<<endl;
LL1:
cout<< "请输入您要选择的函数序号:)"<<endl;
int num,i;cin>>num;int *p;
switch(num)
{
case 1:
ALGraph g;
createDN(g);
cout<<"创建一个有向网的邻接表成功！"<<endl;
break;
case 2:
createDN(g);
printALGraph(g);
break;
case 3:
OLGraph g1;
createOLDN(g1);
printOLGraph(g1);
break;
case 4:
createOLUDG(g1);
printOLGraph2(g1);
break;
case 5:
createDN(g);
p=in(g);
for (i=0;i<g.vexnum;i++,p++)
cout<<g.vertices[i].data<<":"<<*p<<" ";
cout<<endl;
break;
case 6:
createDN(g);
p=out(g);
for (i=0;i<g.vexnum;i++,p++)
cout<<g.vertices[i].data<<":"<<*p<<" ";
cout<<endl;
break;
case 7:
createDN(g);
p=InAndOut(g);
for (i=0;i<g.vexnum;i++)
cout<<g.vertices[i].data<<":"<<(p[i])<<" ";
cout<<endl;
break;
case 8:
createUDN(g);
DFSTraverse(g);
break;
case 9:
createUDN(g);
BFSTraverse(g);
break;
case 10:
createDN(g);
TopologicalSort(g);
break;
case 11:
MGraph gg;
createUDG(gg);
MinispanTree_PRIM(gg,0);
break;
case 12:
createUDN(g);
DFSTraverse_2(g);
}
fflush(stdin);
char c;
cout <<"您是否要继续测试函数？y/n"<<endl;
cin >> c;
if (c == 'y')
goto LL1;
else
return 0;
}
第6，10题在此单独测试：
#include <iostream>
#define MAX_VERTEX_NUM 20
#define INFINITY INT_MAX
using namespace std;
//判断无向图任意两个顶点间是否有路径，若有输出路径上的顶点序列。
//floid 算法
//邻接矩阵
typedef char VertexType;
typedef int VRType;
typedef int InfoType;
typedef struct ArcCell
{
VRType adj;
InfoType *info;
}ArcCell,ArcMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
int kind ;
int vexnum,arcnum;
VertexType vexs[MAX_VERTEX_NUM];
ArcMatrix arcs;
}MGraph;
int locate(MGraph &g,VertexType v)
{
int i;
for (i=0;i<g.vexnum;i++)
{
if (g.vexs[i] == v)
return i;
}
}
void createUDN(MGraph &g)
{
cout <<"请输入顶点个数和弧的条数"<<endl;
cin >> g.vexnum>>g.arcnum;
int i,j,k;
cout <<"请输入顶点集合"<<endl;
for (i=0;i<g.vexnum;i++)
{
cin >>g.vexs[i];
for (j=0;j<g.vexnum;j++)
{
if (i!=j)
g.arcs[i][j].adj=INFINITY;
else
g.arcs[i][j].adj=0;
}
}
cout <<"请输入各条弧的弧头、弧尾以及权值"<<endl;
char v1,v2;
int w;
for (k=0;k<g.arcnum;k++)
{
cin >>v1>>v2>>w;
i=locate(g,v1);
j=locate(g,v2);
g.arcs[i][j].adj=w;
//无向网做对称
g.arcs[j][i].adj=w;
}
}
void printAdjMatrix(MGraph &g)
{
int i,j;
for (i=0;i<g.vexnum;i++)
{
for (j=0;j<g.vexnum;j++)
cout <<g.arcs[i][j].adj<<" ";
cout <<endl;
}
}
typedef bool PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int distanceMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
void ShortestPath_FLOYD(MGraph &g,PathMatrix &p,distanceMatrix &d)
{
void printD(MGraph g,distanceMatrix &d);
int v,w,u,i;
for (v=0;v<g.vexnum;v++)
for (w=0;w<g.vexnum;w++)
{
d[v][w]=g.arcs[v][w].adj;
for (u=0;u<g.vexnum;u++)
{
p[v][w][u]=false;
}
if (d[v][w] < INFINITY )
{
p[v][w][v]=true;
p[v][w][w]=true;
}
}
for (u=0;u<g.vexnum;u++)
for (v=0;v<g.vexnum;v++)
for (w=0;w<g.vexnum;w++)
{
if (d[v][u]!=INFINITY && d[u][w]!=INFINITY )
if (d[v][u] + d[u][w] < d[v][w])
{
d[v][w] = d[v][u]+d[u][w];
for (i=0;i<g.vexnum ;i++)
p[v][w][i]=p[v][u][i] || p[u][w][i];
}
}
}
void printD(MGraph g,distanceMatrix &d)
{
int i,j;
for(i=0;i<g.vexnum;i++)
{
for (j=0;j<g.vexnum;j++)
{
cout << d[i][j]<<" ";
}
cout <<endl;
}
}
void printShortestPath_FLOIY(MGraph g,PathMatrix &p,distanceMatrix &d)
{
int i,j,k;
for (i=0;i<g.vexnum;i++)
{
for (j=0;j<=i;j++) // 输出一半即可
{
cout <<"顶点对： <"<<g.vexs[i]<<","<<g.vexs[j]<<"> (";
for (k=0;k<g.vexnum;k++)
{
if (p[i][j][k])
cout <<g.vexs[k]<<" ";
}
cout <<" )"<<" 路径长度："<<d[i][j]<<endl;
}
}
}
int main()
{
MGraph g;
createUDN(g);
PathMatrix p;
distanceMatrix d;
ShortestPath_FLOYD(g,p,d);
cout << " 输出每对顶点的最短路径"<<endl;
printShortestPath_FLOIY(g,p,d);
return 0;
}
#include <iostream>
#define MAX_VERTEX_NUM 20
#define INFINITY INT_MAX
using namespace std;
//采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。
//迪杰特斯拉
typedef char VertexType;
typedef int VRType;
typedef int InfoType;
typedef struct ArcCell
{
VRType adj;
InfoType *info;
}ArcCell,ArcMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
int kind ;
int vexnum,arcnum;
VertexType vexs[MAX_VERTEX_NUM];
ArcMatrix arcs;
}MGraph;
int locate(MGraph &g,VertexType v)
{
int i;
for (i=0;i<g.vexnum;i++)
{
if (g.vexs[i] == v)
return i;
}
}
void createDN(MGraph &g)
{
cout <<"请输入顶点个数和弧的条数"<<endl;
cin >> g.vexnum>>g.arcnum;
int i,j,k;
cout <<"请输入顶点集合"<<endl;
for (i=0;i<g.vexnum;i++)
{
cin >>g.vexs[i];
for (j=0;j<g.vexnum;j++)
g.arcs[i][j].adj=INFINITY;
}
cout <<"请输入各条弧的弧头、弧尾以及权值"<<endl;
char v1,v2;
int w;
for (k=0;k<g.arcnum;k++)
{
cin >>v1>>v2>>w;
i=locate(g,v1);
j=locate(g,v2);
g.arcs[i][j].adj=w;
}
}
void printAdjMatrix(MGraph &g)
{
int i,j;
for (i=0;i<g.vexnum;i++)
{
for (j=0;j<g.vexnum;j++)
cout <<g.arcs[i][j].adj<<" ";
cout <<endl;
}
}
typedef int ShortPathTable[MAX_VERTEX_NUM];
typedef bool PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
void shortestPath_DIJ(MGraph &g,int v0,PathMatrix &p,ShortPathTable &d)
{
// final d p
bool final[g.vexnum];
int v,w,i,j;
for (v=0;v<g.vexnum;v++)
{
final[v]=false;
d[v]=g.arcs[v0][v].adj;
for (w=0;w<g.vexnum;w++)
p[v][w]=false;
if (d[v] < INFINITY)
{
p[v][v0]=true;
p[v][v]=true;
}
}
d[v0]=0;//自己到自己
final[v0]=true;//并到S集合中
int min;
for (i=0;i<g.vexnum;i++)
{
min = INFINITY;
for (w=0;w<g.vexnum;w++)
{
if (!final[w])
if (d[w]<min)
{
v=w;
min=d[w];
}
}
final[v]=true;
for (w=0;w<g.vexnum;w++)
{
//对于每个顶点，在介入离V0最近的点之后是否会离v0更近呢？
if (!final[w]&&(min+g.arcs[v][w].adj<d[w]))
{
d[w]=min+g.arcs[v][w].adj;
//p[w]=p[v];
for (j=0;j<g.vexnum;j++)
p[w][j]=p[v][j];
p[w][w]=true;
}
}
}
}
void printP(PathMatrix &p)
{
int i,j;
for (i=0;i<6;i++)
{
for (j=0;j<6;j++)
cout << p[i][j]<<" ";
cout <<endl;
}
}
void printD(ShortPathTable &d)
{
int i;
for (i=0;i<6;i++)
cout<<d[i]<<" ";
cout<<endl;
}
void printShortestPath(MGraph &g,PathMatrix &p,ShortPathTable &d)
{
int i,j;
for (i=1;i<g.vexnum;i++)
{
cout <<g.vexs[i]<<":";
cout <<" 最短路径：(";
for (j=0;j<g.vexnum;j++)
if (p[i][j])
cout <<g.vexs[j]<<" ";
cout <<") 路径长度："<<d[i]<<endl;
}
}
int main()
{
MGraph g;
createDN(g);
printAdjMatrix(g);
PathMatrix p;
ShortPathTable d;
shortestPath_DIJ(g,0,p,d);
// v0 = 0 为单源点
printP(p);
printD(d);
printShortestPath(g,p,d);
return 0;
}
实验报告五 查找的相关操作
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define INFINITY INT_MAX
#define MAXSIZE 20
using namespace std;
//1.折半查找
typedef int KeyType;
typedef struct
{
KeyType key;
char data1;
}ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length;
}SeqList;
void createSeqList(SeqList &l)
{
cout<<"请输入关键字个数"<<endl;
cin>>l.length;
cout<<"请顺序输入一组有序的数据及其关键字（key,data1）"<<endl;
for (int i=1;i<=l.length;i++)
{
scanf("%d%c",&l.data[i].key,&l.data[i].data1);
}
}
int Search_Bin(SeqList &l,KeyType key)
{
int low=1,high=l.length;
int mid;
while (low<=high)
{
mid=(low+high)/2;
if (key == l.data[mid].key)
return mid;
else if (key < l.data[mid].key )
high=mid-1;
else
low=mid+1;
}
return 0;
}
//2.二叉排序树
typedef struct BiTNode
{
ElemType data;
struct BiTNode *left,*right;
}BiTNode,*BiTree;
// 查找二叉排序树
int SearchBST(BiTree t,KeyType key,BiTree f,BiTree &p)
{
if (!t) {p=f;return 0;}
else if (key==t->data.key){p=t;return 1;}
else if (key <t->data.key)
return SearchBST(t->left,key,t,p);
else return SearchBST(t->right,key,t,p);
}
// 插入一个数据到二叉排序树
int InsertBST(BiTree &t,ElemType e)
{
BiTree p,s;
if (!SearchBST(t,e.key,NULL,p))
{
s=(BiTree)malloc(sizeof(BiTNode));
s->data.key=e.key;
s->data.data1=e.data1;
s->left=s->right=NULL;
if (!p)
t=s;
else if (e.key < p->data.key )
p->left=s;
else
p->right=s;
return 1;
}
else
return 0;
}
// 循环插入一组数据，建立二叉排序树
void InsertBST_for()
{
void InOrderTraverse(BiTree &t);
void DeleteBST(BiTree &t,KeyType key);
BiTree t;
t=NULL;
ElemType e;
int n;
cout<<"请输入您要输入的数据个数"<<endl;
cin>>n;
cout<<"请依次输入您要插入的数据及其关键字（key,data1）"<<endl;
for (int i=0;i<n;i++)
{
cin>>e.key>>e.data1;
InsertBST(t,e);
}
cout<<"中序遍历输出的结果为："<<endl;
InOrderTraverse(t);
cout<<"请输入您要删除的某一元素的关键字"<<endl;
KeyType key;
cin>>key;
DeleteBST(t,key);
cout<<"删除指定元素后的中序遍历结果为："<<endl;
InOrderTraverse(t);
}
// 中序遍历二叉排序树
void InOrderTraverse(BiTree &t)
{
if (t)
{
InOrderTraverse(t->left);
cout<<t->data.key<<" ";
InOrderTraverse(t->right);
}
}
// 二叉排序树删除:删除某一指定结点
int Delete(BiTree &p)
{
BiTree q,s;
if (!p->right)
{
q=p;
p=p->left;
free(q);
}
else if (!p->right)
{
q=p;
p=p->right;
free(q);
}
else
{
q=p;
s=p->left;
while (s->right)
{
q=s;
s=s->right;
}
p->data.key=s->data.key;
p->data.data1=s->data.data1;
if (q!=p)
q->right=s->left;
else
q->left=s->left;
delete(s);
}
return 1;
}
// 删除某关键字
int DeleteBST(BiTree &t,KeyType key)
{
if (!t)
return 0;
else
{
if (key == t->data.key )
return Delete(t);
else if (key < t->data.key)
return DeleteBST(t->left,key);
else
return DeleteBST(t->right,key);
}
return 1;
}
// AVL
typedef struct BSTNode
{
ElemType data;
int bf;
struct BSTNode *left,*right;
}BSTNode,*BSTree;
// 右旋
void R_Rotate(BSTree &p)
{
BSTree lc;
lc=p->left;
p->left=lc->right;
lc->right=p;
p=lc;
}
//左旋
void L_Rotate(BSTree &p)
{
BSTree lc;
lc=p->right;
p->right=lc->left;
lc->left=p;
p=lc;
}
//左平衡
void LeftBalance(BSTree &t)
{
BSTree lc,rd;
lc=t->left;
switch(lc->bf)
{
case 1:
t->bf=lc->bf=0;
R_Rotate(t);
break;
case -1:
rd=lc->right;
switch(rd->bf)
{
case 1:
t->bf=-1;
lc->bf=0;
break;
case 0:
t->bf=lc->bf=0;
break;
case -1:
t->bf=0;
lc->bf=1;
break;
}
rd->bf=0;
L_Rotate(t->left);
R_Rotate(t);
}
}
//右平衡
void RightBalance(BSTree &t)
{
BSTree lc,rd;
lc=t->right;
switch(lc->bf)
{
case 1:
rd=lc->left;
switch(rd->bf)
{
case 1:
t->bf=0;
lc->bf=-1;
break;
case 0:
t->bf=lc->bf=0;
break;
case -1:
t->bf=1;
lc->bf=0;
break;
}
rd->bf=0;
R_Rotate(t->right);
L_Rotate(t);
break;
case -1:
t->bf=lc->bf=0;
L_Rotate(t);
}
}
//插入建立平衡二叉排序树
int InsertAVL(BSTree &t,ElemType e,bool taller)
{
if (!t)
{
t=(BSTree )malloc(sizeof(BSTNode));
t->bf=0;
t->left=t->right=NULL;
t->data.data1=e.data1;
t->data.key=e.key;
taller=true;//树长高则为正
}
else
{
if (e.key==t->data.key)
{
taller=false;
return 0;
}
if (e.key < t->data.key)
{
if (!InsertAVL(t->left,e,taller))
return 0;
if (taller)
{
switch(t->bf)
{
case 1:
LeftBalance(t);
taller=false;
break;
case 0:
t->bf=1;
taller=true;
break;
case -1:
t->bf=0;
taller=false;
break;
}
}
}
else
{
if (!InsertAVL(t->right,e,taller))
return 0;
if (taller)
{
switch(t->bf)
{
case 1:
t->bf=0;
taller=false;
break;
case 0:
t->bf=-1;
taller=true;
break;
case -1:
RightBalance(t);
taller=false;
break;
}
}
}
}
return 1;
}
// 中序遍历平衡二叉排序树
void InOrderTraverse_BST(BSTree &t)
{
if (t)
{
InOrderTraverse_BST(t->left);
cout<<t->data.key<<" ";
InOrderTraverse_BST(t->right);
}
}
// 线性探测法建立散列表
typedef struct
{
ElemType data[MAXSIZE];
int count;
}HashTable;
// 哈希函数
int Hash(KeyType k)
{
int p=13;
return k%13;
}
//发生冲突之后求出下一探查地址
void collision(HashTable h,int &p)
{
p=(p+1+MAXSIZE)%MAXSIZE;
}
// 在哈希表中查找某关键字
int SearchHash(HashTable h,KeyType key,int &p)
{
p=Hash(key);// 哈西地址
while (h.data[p].key!=NULL && key!=h.data[p].key )
collision(h,p);
if (key==h.data[p].key)
return 1;
else
return 0;
}
// 插入机建立线性探测哈希表
int InsertHash(HashTable &h,ElemType e)
{
int p;
h.count=0;
if (SearchHash(h,e.key,p))
return 0;
else
h.data[p].key=e.key;
h.data[p].data1=e.data1;
h.count++;
return 1;
}
// 遍历输出线线性探测哈希表
void TraverseHash(HashTable h)
{
int i;
for (i=0;i<MAXSIZE;i++)
cout<<"("<<h.data[i].key<<","<<h.data[i].data1<<")";
cout<<endl;
}
// 外拉链法建立哈希表
typedef struct Node
{
ElemType e;
struct Node *next;
}Node,HashTable2[MAXSIZE];
// 查找外拉链表
int searchHash2(HashTable2 h,ElemType e,int &p)
{
p=Hash(e.key);// 哈西地址
Node *q;
q=h[p].next;
while (q)
{
if (q->e.key==e.key)
return 1;
q=q->next;
}
return 0;
}
// 插入建立外拉链表
int InsertHash2(HashTable2 h,ElemType e)
{
int p;
Node *q;
if (searchHash2(h,e,p))
return 0;
else
{
q=(Node*)malloc(sizeof(Node));
q->e.key=e.key;
q->e.data1=e.data1;
q->next=h[p].next;//头插法插入元素
h[p].next=q;
}
return 1;
}
// 遍历外拉链表
void TraverseHash2(HashTable2 h)
{
int i;
Node *p;
for (i=0;i<MAXSIZE;i++)
{
p=h[i].next;
while (p)
{
cout<<"("<<p->e.key<<","<<p->e.data1<<")";
p=p->next;
}
}
}
int main()
{ cout<<"--------------------------------------------------------"<<endl;
cout<<"1.Search_Bin():采用折半查找实现某一已知的关键字的查找"<<endl;
cout<<"2.InsertBST()&&DeleteBST():插入算法建立二叉排序树并删除某指定元素"<<endl;
cout<<"3.InsertAVL():建立AVL树并实现删除某一指定关键字元素"<<endl;
cout<<"4.InsertHash():线性探测法建立哈希表"<<endl;
cout<<"5.InsertHash2():外拉链法建立哈希表"<<endl;
cout<<"--------------------------------------------------------"<<endl;
ll1:cout<<"请输入您选择的函数序号"<<endl;
int x;cin>>x;
ElemType e;int n;
switch(x)
{
case 1:
{
SeqList l;
createSeqList(l);
cout<<"请输入任一关键字"<<endl;
KeyType key;
cin>>key;
int location=Search_Bin(l,key);
printf("查找位置为：%d\n",location);
break;
}
case 2:
{
InsertBST_for();
break;
}
case 3:
{
BSTree t1;
t1=NULL;
cout<<"请输入数据个数"<<endl;
cin>>n;
cout<<"请输入一组数据（key,data1）以建立平衡二叉树"<<endl;
for (int i=0;i<n;i++)
{
cin>>e.key>>e.data1;
InsertAVL(t1,e,false);
}
cout<<"建立结束，现在中序遍历"<<endl;
InOrderTraverse_BST(t1);
break;
}
case 4:
HashTable h;
for (int i=0;i<MAXSIZE;i++)
{
h.data[i].key=0;
h.data[i].data1='z';
}
cout<<"请输入元素个数"<<endl;
cin>>n;
cout<<"请输入一组关键字（key,data1）"<<endl;
for (int i=0;i<n;i++)
{
cin>>e.key>>e.data1;
InsertHash(h,e);
}
cout<<"建立结束，遍历哈希表,(0,z)表示NULL"<<endl;
TraverseHash(h);
break;
case 5:
HashTable2 h1;
for (int i=0;i<MAXSIZE;i++)
{
h1[i].next=NULL;
}
cout<<"请输入元素个数"<<endl;
cin>>n;
cout<<"请输入一组关键字（key,data1）"<<endl;
for (int i=0;i<n;i++)
{
cin>>e.key>>e.data1;
InsertHash2(h1,e);
}
cout<<"建立结束，遍历哈希表"<<endl;
TraverseHash2(h1);
break;
}
cout<<"您是否还要继续测试其他函数？y/n"<<endl;
fflush(stdin);
char z;
cin>>z;
if (z=='y')
goto ll1;
else
return 0;
}
实验6 排序
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define INFINITY INT_MAX
#define MAXSIZE 100
using namespace std;
typedef struct list
{int key;
}ElemType;
typedef struct {
ElemType data[MAXSIZE+1];
int length; /*参加排序元素的实际个数*/
}SeqList;
//创建顺序表
void creatList(SeqList &l)
{
cout<<"请输入数据个数"<<endl;
cin>>l.length;
cout<<"请顺次输入一组无序数据"<<endl;
for (int i=1;i<=l.length;i++)
{
cin>>l.data[i].key;
}
}
// 直接插入排序
void InsertSort(SeqList &l)
{
int i,j;
for (i=2;i<=l.length;i++)
{
if (l.data[i].key < l.data[i-1].key )
{
l.data[0].key=l.data[i].key;
l.data[i].key=l.data[i-1].key;
for (j=i-2;l.data[0].key < l.data[j].key ;j--)
l.data[j+1].key=l.data[j].key;
l.data[j+1].key=l.data[0].key;
}
}
}
//输出顺序表元素
void print(SeqList l)
{
int i;
for (i=1;i<=l.length;i++)
cout<<l.data[i].key<<" ";
cout<<endl;
}
//冒泡排序
void BubbleSort(SeqList &l)
{
int i,j;
for (i=1;i<=l.length-1;i++)
for (j=1;j<=l.length-i;j++)
{
if (l.data[j].key > l.data[j+1].key)
{
l.data[0]=l.data[j];
l.data[j]=l.data[j+1];
l.data[j+1]=l.data[0];
}
}
}
// 直接选择排序
void SelectSort(SeqList &l)
{
int i,j,k;
for (i=1;i<=l.length-1;i++)
{
k=i;
for (j=i;j<=l.length;j++)
{
if (l.data[j].key<l.data[k].key)
{
k=j;
}
}
if (k!=i)
{
l.data[0]=l.data[k];
l.data[k]=l.data[i];
l.data[i]=l.data[0];
}
}
}
//希尔插入
void ShellInsert(SeqList &l,int dk)
{
//dk是位置增量
int i,j;
for (i=dk+1;i<=l.length;i++)
{
if (l.data[i].key < l.data[i-dk].key)
{
l.data[0]=l.data[i];
for (j=i-dk;j>0&&l.data[0].key<l.data[j].key;j=j-dk)
{
l.data[j+dk]=l.data[j];
}
l.data[j+dk]=l.data[0];
}
}
}
//希尔排序
void ShellSort(SeqList &l,int dlta[],int t)
{
//dlta[]是增量数组，每一次循环以dlta[k]为增量，dlta[0---t-1]
int k;
for (k=0;k<t;k++)
ShellInsert(l,dlta[k]);
}
//快排
int Partition(SeqList &l,int low,int high)
{
l.data[0]=l.data[low];
int p;
p=l.data[low].key;
while (low<high)
{
while (low<high&&l.data[high].key>=p) high--;
l.data[low]=l.data[high];
while (low<high&&l.data[low].key<=p) low++;
l.data[high]=l.data[low];
}
l.data[low]=l.data[0];
return low;
}
void QSort(SeqList &l,int low,int high)
{
int p;
if (low<high)
{
p=Partition(l,low,high);
QSort(l,low,p-1);
QSort(l,p+1,high);
}
}
//堆调整
void HeapAdjust(SeqList &l,int s,int m)
{
ElemType rc=l.data[s];
int j;
for (j=2*s;j<=m;j*=2)
{
if (j<m && l.data[j].key < l.data[j+1].key)
j++;
if (!(rc.key < l.data[j].key))
break;
l.data[s]=l.data[j];s=j;
}
l.data[s]=rc;
}
//堆排序
void HeapSort(SeqList &l)
{
int i;
for (i=l.length/2;i>0;i--)
HeapAdjust(l,i,l.length);
for (i=l.length;i>1;i--)
{
l.data[0]=l.data[1];
l.data[1]=l.data[i];//data[1]即为最大的数
l.data[i]=l.data[0];
HeapAdjust(l,1,i-1);
}
}
//折半插入排序
void BinInsertSort(SeqList &l)
{
int i,j,low,high,mid;
for (i=2;i<=l.length;i++)
{
l.data[0]=l.data[i];
low=1;high=i-1;
while (low<=high)
{
mid=(low+high)/2;
if (l.data[0].key < l.data[mid].key ) high=mid-1;
else low=mid+1;
}
for (j=i-1;j>=high+1;j--)
l.data[j+1]=l.data[j];
l.data[high+1]=l.data[0];
}
}
// 链式存储实现简单选择排序
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*linklist;
//创建单链表l
void createLinkList(linklist &l)
{
linklist p,q;
l=(linklist)malloc(sizeof(LNode));
p=l;
cout<<"请输入数据个数"<<endl;
int n;cin>>n;
cout<<"请输入一组数据"<<endl;
ElemType e;
for (int i=0;i<n;i++)
{
cin>>e.key;
q=(linklist)malloc(sizeof(LNode));
q->data.key=e.key;
q->next=NULL;
p->next=q;
p=q;
}
}
// 简单选择排序
void SelectSort_linklist(linklist &l)
{
ElemType tmp;
linklist p,q,k;//P为工作指针，Q为指向最小元素的指针,k为前面指向第一个为排序元素的指针
p=l->next;q=p;k=p;
while (k)
{
while (p)
{
if (p->data.key < q->data.key )
{
q=p;
}
p=p->next;
}
if (k!=q)
{
tmp=k->data;
k->data=q->data;
q->data=tmp;
}
k=k->next;
p=k;
q=k;
}
}
//打印链表
void print_linklist(linklist l)
{
linklist p=l->next;
while (p)
{
cout<<p->data.key<<" ";
p=p->next;
}
cout<<endl;
}
// 链式直接插入排序
void InsertSort_linklist(linklist &l)
{
linklist p,q,t;
p=l->next->next;//把P插入到链表L中
l->next->next=NULL;
q=l;
while (p)
{
while (q->next && p->data.key >q->next->data.key)
q=q->next;
if (!q)
{
q->next = p;
p=p->next;
p->next=NULL;
}
else
{
t=p;p=p->next;
t->next=q->next;
q->next=t;
}
q=l;
}
}
// 链式冒泡排序
void BubbleSort_linklist(linklist &l)
{
linklist p=l->next,q,c;
q=p->next;
ElemType e;
c=p;
while (c)
{
while (q)
{
if (p->data.key > q->data.key )
{
e=p->data;
p->data=q->data;
q->data=e;
}
p=p->next;q=q->next;
}
p=l->next,q=p->next;
c=c->next;
}
}
int main()
{ cout<<"--------------------------------------------------------"<<endl;
cout<<"1.InsertSort():直接插入排序"<<endl;
cout<<"2.Bl.data[1]ubbleSort():冒泡排序"<<endl;
cout<<"3.SelectSort():直接选择排序"<<endl;
cout<<"4.ShellSort():希尔排序"<<endl;
cout<<"5.QSort():快速排序"<<endl;
cout<<"6.HeapSort():堆排序"<<endl;
cout<<"7.BinInsertSort():折半插入排序"<<endl;
cout<<"9.SelectSort_linklist():链式简单选择排序"<<endl;
cout<<"10.InsertSort_linklist():链式直接插入排序"<<endl;
cout<<"11.BubbleSort_linklist():链式冒泡排序"<<endl;
cout<<"--------------------------------------------------------"<<endl;
ll1:cout<<"请输入您选择的函数序号"<<endl;
int x;cin>>x;
SeqList l;
linklist l1;
switch(x)
{
case 1:
{
creatList(l);
cout<<"直接插入排序前的结果"<<endl;
print(l);
InsertSort(l);
cout<<"直接插入排序后的结果"<<endl;
print(l);
break;
}
case 2:
{
creatList(l);
cout<<"冒泡排序前的结果"<<endl;
print(l);
BubbleSort(l);
cout<<"冒泡排序后的结果"<<endl;
print(l);
break;
}
case 3:
{
creatList(l);
cout<<"直接选择排序前的结果"<<endl;
print(l);
SelectSort(l);
cout<<"直接选择排序后的结果"<<endl;
print(l);
break;
}
case 4:
creatList(l);
cout<<"希尔排序前的结果"<<endl;
print(l);
int dlta[3];dlta[0]=5;dlta[1]=3;dlta[2]=1;
ShellSort(l,dlta,3);
cout<<"希尔排序后的结果"<<endl;
print(l);
break;
case 5:
creatList(l);
cout<<"快速排序前的结果"<<endl;
print(l);
QSort(l,1,8);
cout<<"快速排序后的结果"<<endl;
print(l);
break;
case 6:
{
creatList(l);
cout<<"堆排序前的结果"<<endl;
print(l);
HeapSort(l);
cout<<"堆排序后的结果"<<endl;
print(l);
break;
}
case 7:
{
creatList(l);
cout<<"折半插入排序前的结果"<<endl;
print(l);
BinInsertSort(l);
cout<<"折半插入排序后的结果"<<endl;
print(l);
break;
}
case 9:
{
createLinkList(l1);
cout<<"链式简单选择排序之前："<<endl;
print_linklist(l1);
SelectSort_linklist(l1);
cout<<"链式简单选择排序之后："<<endl;
print_linklist(l1);
break;
}
case 10:
{
createLinkList(l1);
cout<<"链式直接插入排序之前："<<endl;
print_linklist(l1);
InsertSort_linklist(l1);
cout<<"链式直接插入排序之后："<<endl;
InsertSort_linklist(l1);
break;
}
case 11:
{
createLinkList(l1);
cout<<"链式冒泡排序之前："<<endl;
print_linklist(l1);
BubbleSort_linklist(l1);
cout<<"链式冒泡排序之后："<<endl;
print_linklist(l1);
break;
}
}
cout<<"您是否还要继续测试其他函数？y/n"<<endl;
fflush(stdin);
char z;
cin>>z;
if (z=='y')
goto ll1;
else
return 0;
}