数据结构实训报告_数据结构实训报告样本

其他范文时间：2020-02-28 06:50:43 收藏本文下载本文

【www.daodoc.com - 其他范文】

数据结构实训报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实训报告样本”。

北京联合大学

实训报告

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

姓名：成绩：

2012年 6 月 21 日

数据结构实训任务一

一、任务与目的：

1、用顺序表表示两个无序集合A、B，实现集合的如下操作，求两个集合的并集、交集、差集。

2、用顺序表表示两个集合A、B（集合A、B都是有序递增的情况）实现集合的如下操作，求两个集合的并集、交集、差集。

3、用带头单链表存储结构表示两个无序集合A、B，实现集合的如下操作，求两个集合的并集、交集、差集。

4、用带头单链表存储结构表示两个集合A、B（集合A、B都是有序递增的情况），实现集合的如下操作，求两个集合的并集、交集、差集。

5、杀人游戏 N个人坐成一圈玩杀人游戏，按顺时针编号

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

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

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

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

{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

{C.elem[k]=A.elem[i];k++;i++;

} } if(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

{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

{C.elem[k]=A.elem[i];i++;k++;

}

else

{if(A.elem[i]==B.elem[j])

{i++;j++;}

else

{j++;

}

} } if(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=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

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

{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 #include #include #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;inum=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

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;

cout>n;if(n==1){ servive=m;} else

{ p1=p2=create(m);for(i=1;i

p2=letout(p1);p1=p2;}

servive=p2->num;free(p2);}

cout

6.#include #include #include 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

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>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

{ //入栈

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>ch;

a[i]=ch;i++;} n=i;for(i=0;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

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

{//入栈

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>a;cout>b;while(a){Push(s,a%b);a=a/b;} while(!(s.top==-1))cout

运行结果：

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

{//入栈

if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} void Error(char *a)

{ cout

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

urn 0;} void main(){stack s;

r ch,a[50];t i=0,n,t;instack(s);cout>ch;[i]=ch;ush(s,ch);+;} n=i;Check(a,n,s);if(t==1)cout

运行结果：

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;ia.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

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;ia.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.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

运行结果：

数据结构实训任务书三：二叉树链式存储的基本操作

1、创建二叉树

a)熟悉使用教材的先序创建二叉树的方法

b)编写一个算法，实现在已知二叉树的先序序列和中序序列的情况下创建二叉树。

c)如果已知二叉树的顺序表示形式，将其转换为二叉树的链式存储方式。

2、二叉树的遍历

a)先序、中序和后序三种形式的链式存储递归式算法 b)先序、中序和后序三种形式的链式存储非递归式算法 c)层次遍历的算法。

3、二叉树一些基本操作 a)计算二叉树的深度； b)计算二叉树的叶子节点个数 c)计算二叉树的单支节点的个数 d)计算二叉树的双支节点的个数

4、编写一个主函数能够测试你所设计的算法。

主函数调用教材创建二叉树的创建教材图7-10的二叉树链式存储方式。

{p=st.a[st.top];

st.top--;

coutdata;

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 #include #include #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){coutdata;

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--;

coutdata;

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);

coutdata;

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;

}}} 20

}

while(st.top!=-1)break;

}

}}} void Postorder(Tree t)//后序遍历，递归实现 {if(t!=NULL){Postorder(t->left);

Postorder(t->right);

coutdata;}} 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;

while(st.top!=-1 && flag)

{t=st.a[st.top];

if(t->right==m)

{coutdata;

st.top--;

m=t;} else

{t=t->right;

flag=0;

}}}

while(st.top!=-1);} int Height(Tree t)//求二叉树的高度，递归实现{int depth1,depth2;if(!t){

return 0;}

else {depth1=Height(t->left);

depth2=Height(t->right);

if(depth1>depth2)

{return(depth1+1);

}

else

{return(depth2+1);

}}} int leafs_rec(Tree t)

//叶子结点

{int l,r;if(t==NULL)

return 0;else if((t->left==NULL)&&(t->right==NULL))

return 1;else {l=leafs_rec(t->left);

r=leafs_rec(t->right);

return(l+r);}} int danzhi(Tree t)//单只 {if(t==NULL)

return 0;else if((t->left==NULL)&&(t->right!=NULL))

d++;else if((t->left!=NULL)&&(t->right==NULL))

d++;danzhi(t->left);danzhi(t->right);return(d);} int shuangzhi(Tree t)

//双只

{if(t==NULL)

return 0;else if((t->left!=NULL)&&(t->right!=NULL))

l++;shuangzhi(t->left);shuangzhi(t->right);return(l);} void TraversalOfLevel(Tree t)//层次遍历二叉树 { Tree p,q[100];int f=0,r=0;if(t!=NULL)

{p=t;

q[r]=t;

r++;} while(f!=r){p=q[f];f++;

coutdata;

if(p->left!=NULL)

{q[r]=p->left;

r++;

}

if(p->right!=NULL)

{q[r]=p->right;

r++;} }} void CreateBiTree_XZ(Tree &T,char a[],int la,int ra,char b[],int lb,int rb)//知先序、中序求二叉树

{int i,lla,lra,llb,lrb,rla,rra,rlb,rrb;if(la>ra)

T=NULL;else

{T=new BTree;

T->data=a[la];

for(i=lb;i

{if(b[i]==a[la])

break;}

lla=la+1;

lra=lla+i-lb-1;

rla=lra+1;

rra=ra;llb=lb;

lrb=i-1;

rlb=i+1;

rrb=rb;

CreateBiTree_XZ(T->left,a,lla,lra,b,llb,lrb);

CreateBiTree_XZ(T->right,a,rla,rra,b,rlb,rrb);}} void CreateBiTree_SX(Tree &T,char S[],int pos,int n)//二叉树的顺序表示形式，将其转换为二叉树的链式存储方式 {int i;if(S[pos]=='#')

T=NULL;else {T=new BTree;

T->data=S[pos];

if((i=2*pos+1)

CreateBiTree_SX(T->left,S,i,n);

else

T->left=NULL;

if((i=2*pos+2)

CreateBiTree_SX(T->right,S,i,n);

else

T->right=NULL;}} void main(){int n,i;char a[30],b[30],c[30];Tree s;Tree m;cout

cout>n;cout>a[i];cout>b[i];CreateBiTree_XZ(s,a,0,n-1,b,0,n-1);cout>n;cout>c[i];CreateBiTree_SX(s,c,0,n-1);cout

数据结构实训任务书四：图的操作

1、建立图的存储结构

a)创建图的邻接矩阵表示方式 b)创建图的邻接表表示方式 c)实现两种方式的互换

2、图的遍历

a)基于邻接矩阵的深度和广度遍历 b)基于邻接表的深度和广度遍历

3、最小生成树，使用Prim算法实现从某一节点出发的图的最小生成树254、单源最短路径，算法8-105、关键路径算法。

1．代码：

typedef enum{DG,DN,UDG,UDN}GKind;typedef enum{FALSE,TRUE}Boolean;Boolean visited[max_v];typedef int VType;typedef int EType;typedef int qtype;typedef struct { qtype *elem;int front;int rear;int qsize;int insize;}squeue;typedef struct { VType vexs[max_v];EType edges[max_v][max_v];int vnum,ednum;GKind kind;}MGraph;typedef struct ENode { int advex;struct ENode *next;int weight;}ENode;typedef struct VNode { VType vex;ENode *first;}VNode,List[max_v];typedef struct { List ver;int vnum,ednum;int kind;}AGraph;int LocatV(MGraph g,VType x){ int k;k=-1;for(k=0;(k

void CreatUDN_MG(MGraph &g)

//邻接矩阵 { int i,j,k,v1,v2,w;cout>g.vnum;cout>g.ednum;cout>g.vexs[i];for(i=0;i

g.edges[i][j]=infinity;cout

cin>>v1;

cout

cin>>v2;

cout

cin>>w;

i=LocatV(g,v1);

j=LocatV(g,v2);

while((i(g.vnum-1))||(j(g.vnum-1)))

{ cout

cin>>v1;

cin>>v2;

cin>>w;

i=LocatV(g,v1);

j=LocatV(g,v2);

g.edges[i][j]=w;

g.edges[j][i]=g.edges[i][j];}} int LocatVA(AGraph g,VType x){ int k;k=-1;for(k=0;(k>g.vnum;cout>g.ednum;cout>g.ver[i].vex;g.ver[i].first=NULL;} cout>v1;cin>>v2;i=LocatVA(g,v1);j=LocatVA(g,v2);while((i(g.vnum-1))||(j(g.vnum-1))){

cout

cin>>v1;

cin>>v2;

i=LocatVA(g,v1);

j=LocatVA(g,v2);} p=new ENode;p->advex=j;p->next=g.ver[i].first;g.ver[i].first=p;}} void DFS(AGraph g,VType i){ ENode *p;VType w;visited[i]=TRUE;coutnext){ w=p->advex;if(!visited[w])

DFS(g,w);}} void Draverse(AGraph g)

//邻接表深度遍历 { int i;for(i=0;i

DFS(g,i);} void MDFS(MGraph g,VType i){ VType p;visited[i]=TRUE;cout

{ if(!visited[p])

MDFS(g,p);}} void Mraverse(MGraph g)

//邻接矩阵深度遍历 { int i;for(i=0;i

MDFS(g,i);} void InQueue(squeue &q)

{ q.elem=new qtype[SIZE];q.front=q.rear=0;q.qsize=SIZE;q.insize=IN;} void INsize(squeue &q)

{ qtype *a;int i;a=new qtype[q.qsize+q.insize];for(i=0;i

{ if(((q.rear+1)%q.qsize)==q.front)INsize(q);q.elem[q.rear]=e;q.rear=(q.rear+1)%q.qsize;} void Error(char *a)

//错 { cout

{ qtype e;if(q.front==q.rear)Error(“循环队列空!”);e=q.elem[q.front];q.front=(q.front+1)%q.qsize;return e;} void BFS(MGraph g)

{ int i,w,u;squeue q;

//初始化 //扩容

//入队

//出队

//邻接矩阵广度遍历29

for(i=0;i

cout

EnQueue(q,i);

while(q.front!=q.rear)

{ u=DeQueue(q);

for(w=0;w

if(g.edges[u][w]&&(!visited[w]))

{ visited[w]=TRUE;

cout

EnQueue(q,w);}}}} void MBFS(AGraph g)

//邻接表广度遍历 { int i,w,u;squeue q;ENode *p;for(i=0;i

EnQueue(q,i);

while(q.front!=q.rear)

{u=DeQueue(q);

cout

p=g.ver[u].first;

while(p)

{w=p->advex;

if(visited[w]!=TRUE)

{ visited[w]=TRUE;

EnQueue(q,w);}

p=p->next;}}}}} void MatToList(MGraph l,AGraph &g)//此函数用于实现将邻接矩阵转换成邻接表{ int i,j;ENode *p;g.vnum = l.vnum;for(i = 0;i

g.ver[i].first = NULL;

g.ver[i].vex=l.vexs[i];} for(i=0;i

for(j = l.vnum-1;j>=0;j--)

{ if((l.edges[i][j]!= 0)&&(l.edges[i][j]!=100)){ p =(ENode*)malloc(sizeof(ENode));

p->advex = j;

p->next= g.ver[i].first;

g.ver[i].first= p;}}} void ListToMat(MGraph &g, AGraph l)//表转矩阵 { int i,j;ENode *p;g.vnum=l.vnum;g.ednum=l.ednum;for(i = 0;i

g.edges[i][j] = 0;for(i=0;i

while(p){g.edges[i][p->advex] = 1;

p=p->next;} }} void main(){ int j=0,i;MGraph g;AGraph h;ENode *p;CreatUDN_MG(g);cout

for(j=0;j

cout

“;

cout

{

p=h.ver[i].first;

while(p!=NULL)

{ coutadvex].vex”

p=p->next;

} } cout

Draverse(h);cout

MatToList(g,h);cout

for(j=0;j

cout

“;

cout

{

p=h.ver[i].first;

while(p!=NULL)

{coutadvex].vex”

p=p->next;} }} 2.代码：#include #define MAX 100 #define Infinity 65535 typedef int WeiType;using namespace std;struct edgeNode { int no;//边端的序号 char info;//边端的名称 WeiType weight;//边的权值 struct edgeNode * next;//下一个 } struct vexNode { char info;//节点名称

struct edgeNode *link;//与之相连的端点 };

//存储节点信息

vexNode adjlist[MAX];//访问标志

bool visited[MAX];//lowcost[j]存储从开始节点到节点j的最小花费 WeiType lowcost[MAX];//parent[j]表示节点j的前驱节点 int parent[MAX];//建立邻接表存储

void createGraph(vexNode *adjlist,const int n,const int e,const int v0){ edgeNode *p1,*p2;int i,v1,v2;WeiType weight;for(i=1;i>adjlist[i].info;adjlist[i].link = NULL;//初始化

visited[i] = false;lowcost[i] = Infinity;parent[i] = v0;} for(i=1;i>v1>>v2;cout>weight;p1 =(edgeNode*)malloc(sizeof(edgeNode));p2 =(edgeNode*)malloc(sizeof(edgeNode));p1->no = v1;

p1->weight = weight;p1->info = adjlist[v1].info;p1->next = adjlist[v2].link;adjlist[v2].link = p1;p2->no = v2;p2->weight = weight;p2->info = adjlist[v2].info;p2->next = adjlist[v1].link;adjlist[v1].link = p2;}} void f(int n,int e,int v){ int i,j,k;edgeNode *p,*q;WeiType sum = 0,minCost;createGraph(adjlist,n,e,v);p = adjlist[v].link;

visited[v] = true;while(p!=NULL){ lowcost[p->no] = p->weight;p = p->next;} for(i=1;i

minCost = Infinity;

int k;

for(j=1;j

{

if(minCost>lowcost[j]&&!visited[j])

{ minCost = lowcost[j];

k = j;

}

sum += minCost;

visited[k] = true;

q = adjlist[k].link;