c语言数据结构(考题,测试你的能力)--编写源代码
/*使用递归,理论上说可以对任意多位数组合,但位数太多了,可能发生堆栈溢出.
以下程序在VC++6.0中编译通过.
*/
#include
#include
#define MAX_NUMBER 6 //修改这个参数来允许最大的位数,现设为6位
void GetZhe (const char * preStr,const char * strNum)
{
char newPreStr[MAX_NUMBER];
char tmpStr[MAX_NUMBER];
int i,j,k,iCnt;
k = strlen(strNum);
if (k>MAX_NUMBER) {
printf("超过最大允许的位数:%d!",MAX_NUMBER);
return ;
}
switch(k)
{
case 0:
return;
case 1:
strcpy(tmpStr,preStr);
strcat(tmpStr,strNum);
printf("%s
",tmpStr);
break;
default:
tmpStr[0] = 0;
for (i=0;i<k;i++)
{
strcpy(newPreStr,preStr);
j = strlen(newPreStr);
newPreStr[j] = strNum[i];
newPreStr[j+1] = 0;
iCnt = 0;
for (j=0;j<k;j++)
{
if(j != i)
{
tmpStr[iCnt] = strNum[j];
iCnt ++ ;
}
}
tmpStr[iCnt] = 0;
GetZhe(newPreStr,tmpStr);
}
}
}
int main(int argc, char* argv[])
{
GetZhe("","123456");
return 0;
}
这个绝对满足了你的要求了,谢谢采纳`
#include
#include
#include
class List;
class person
{
public:
friend class List;
private:
person() {next=0;}
person *next;
char name[10],tel[15];
};
class List
{
public:
List(){list=0;}
int gncd(); // 功能菜单
int print(); // 输出所有信息
int append(); // 增加一个信息
int revise(); // 根据姓名、电话修改信息
int dele(); // 根据姓名、电话删除信息
int exit(); // 退出
private:
person *end();
person *list;
};
int List::exit()
{
abort();
return 1;
}
int List::gncd()
{
cout<<"************欢迎使用****************************"<<endl;
cout<<"1.输入信息。"<<endl;
cout<<"2.根据姓名、电话修改信息。"<<endl;
cout<<"3.根据姓名、电话删除信息"<<endl;
cout<<"4.输出所有现有成员信息"<<endl;
cout<<"5.退出"<<endl;
cout<<"选择:";
int a;
cin>>a;
switch(a)
{
case(1):this->append();break;
case(2):this->revise();break;
case(3):this->dele();break;
case(4):this->print();break;
case(5):this->exit();break;
}
this->gncd();
return 1;
}
int List::print()
{
if(list==0)
{
cout<<"为空或没输入内容"<<endl;
return 0;
}
person *p=list;
while(p!=NULL)
{
coutname<<endl;
couttel<<endl;
p=p->next;
}
cout<<endl;
return 1;
}
int List::append()
{
person *p=new person;
cout<<"请输入姓名:"<<endl;
cin>>p->name;
cout<<"请输入电话号码:"<<endl;
cin>>p->tel;
char temp;
cout<<"是否继续输入(y/n)";
cin>>temp;
if(temp=='y'||temp=='Y')
this->append();
if(list==0)
list=p;
else
(end())->next=p;
return 1;
}
person *List::end()
{
person *p,*q;
for(q=p=list;p;q=p,p=p->next) ;
return q;
}
int List::revise()
{
person *p=list;
char temp[20];
cout<<"你选择了根据姓名、电话修改信息。"<<endl<<"请输入将要修改的姓名或电话:";
cin>>temp;
int i=0;
while(p!=NULL)
{
if(!strcmp(p->name,temp)||!strcmp(p->tel,temp))
{
i=1;
cout<<"请输入新的姓名:";
cin>>p->name;
cout<<"请输入新的电话号码:";
cin>>p->tel;
}
p=p->next;
}
if(i==1) cout<<"修改成功!"<<endl;
if(i!=1) cout<<"未能找到。"<<endl;
return 1;
}
int List::dele()
{
person *q,*p=list;
char temp[20];
cout<<"你选择了根据姓名、电话删除信息。"<<endl<<"请输入将要删除的姓名或电话:";
cin>>temp;
if(p==NULL)
cout<<"为空或没有输入信息。"<<endl;
if(!strcmp(p->name,temp)||!strcmp(p->tel,temp)) //要删除的结点是第一个时
{
list=p->next;
delete p;
cout<<"删除成功!"<<endl;
}
else
{
while(p!=NULL&&(strcmp(p->name,temp)||strcmp(p->tel,temp)))
{
q=p;
p=p->next;
}
if(p==NULL) return 0;
else if(q==NULL)
cout<<"没能找到。"<<endl;
else
{
q->next=p->next;
delete p;
cout<<"删除成功!"<<endl;
}
}
return 1;
}
void main()
{
List L;
L.gncd();
}
/*假设ha为A稀疏矩阵十字链表的头指针,hb为B稀疏矩阵十字链表的头指针*/
#include<stdio.h>
#define maxsize 100
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext
{ int v;
struct linknode *next;} k;
};
struct linknode creatlindmat( ) /*建立十字链表*/
{ int x, m, n, t, s, i, j, k;
struct linknode *p , *q, *cp[maxsize],*hm;
printf("请输入稀疏矩阵的行、列数及非零元个数\n");
scanf("%d%d%d",&m,&n,&t);
if (m>n) s=m; else s=n;
hm=(struct linknode*)malloc(sizeof(struct linknode)) ;
hm->i=m; hm->j=n;
cp[0]=hm;
for (i=1; i<=s;i++)
{ p=(struct linknode*)malloc(sizeof(struct linknode)) ;
p->i=0; p->j=0;
p->rptr=p; p->cptr=p;
cp[i]=p;
cp[i-1]->k.next=p;
}
cp[s]->k.next=hm;
for( x=1;x<=t;x++)
{ printf("请输入一个三元组(i,j,v)\n");
scanf("%d%d%d",&i,&j,&k);
p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=i; p->j=j; p->k.v=k;
/*以下是将p插入到第i行链表中 */
q=cp[i];
while ((q->rptr!=cp[i]) &&( q->rptr->j<j))
q=q->rptr;
p->rptr=q->rptr;
q->rptr=p;
/*以下是将P插入到第j列链表中*/
q=cp[j];
while((q->cptr!=cp[j]) &&( q->cptr->i<i))
q=q->cptr;
p->cptr=q->cptr;
q->cptr=p;
}
return hm;
}
/* ha和hb表示的两个稀疏矩阵相加,相加的结果放入ha中*/
struct linknode *matadd(struct linknode *ha, struct linknode *hb)
{ struct linknode *pa, *pb, *qa, *ca,*cb,*p,*q;
struct linknode *hl[maxsize];
int i , j, n;
if((ha->i!=hb->i)||(ha->j!=hb->j))
printf("矩阵不匹配,不能相加\n");
else
{ p=ha->k.next; n=ha->j;
for (i=1;i<=n; i++)
{ hl[i]=p;
p=p->k.next;
}
ca=ha->k.next; cb=hb->k.next;
while(ca->i==0)
{pa=ca->rptr; pb=cb->rptr;
qa=ca;
while(pb->j!=0)
{ if((pa->j<pb->j)&&(pa->j!=0))
{ qa=pa; pa=pa->rptr;}
else if ((pa->j>pb->j)||(pa->j==0)) /*插入一个结点*/
{ p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=pb->i; p->j=pb->j;
p->k.v=pb->k.v;
qa->rptr=p; p->rptr=pa;
qa=p; pb=pb->rptr;
j=p->j; q=hl[j]->cptr;
while((q->i<p->i)&&(q->i!=0))
{ hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=p; p->cptr=q;
hl[j]=p;
}
else
{pa->k.v=pa->k.v+pb->k.v;
if(pa->k.v==0) /*删除一个结点*/
{ qa->rptr=pa->rptr;
j=pa->j; q=hl[j]->cptr;
while (q->i<pa->i)
{hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=q->cptr;
pa=pa->rptr; pb=pb->rptr;
free(q);
}
else
{ qa=pa; pa=pa->rptr;
pb=pb->rptr;
}
}
}
ca=ca->k.next; cb=cb->k.next;
}
}
return ha;
}
void print(struct linknode *ha) /*输出十字链表*/
{ struct linknode *p,*q;
p=ha->k.next;
while(p->k.next!=ha)
{ q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
p=p->k.next;
}
q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
}
void main()
{
struct linknode *ha=NULL,*hb=NULL,*hc=NULL;
ha=creatlindmat( ); /*生成一个十字链表ha*/
hb=creatlindmat( ); /*生成另一个十字链表hb*/
printf("A:\n"); /*输出十字链表ha*/
print(ha);printf("\n");
printf("B:\n"); /*输出十字链表hb*/
print(hb);printf("\n");
hc=matadd(ha,hb); /*十字链表相加*/
printf("A+B:\n"); /*输出相加后的结果*/
print(hc);printf("\n");
}
P94 数据类型描述如下:
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
}
P95 数据类型描述如下:
struct node2
{ elemtype data;
struct node2 *link1,*link2;
}
P96 求广义表的深度depth(LS)
int depth(struct node1 *LS)
{
int max=0,dep;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
P96 广义表的建立creat(LS)
void creat(struct node1 *LS)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node*)malloc(sizeof(struct node));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node*)malloc(sizeof(struct node));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}
P97 输出广义表print(LS)
void print(struct node1 *LS)
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c ",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}
P98 该算法的时间复杂度为O(n)。整个完整程序如下:
#include<stdio.h>
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
};
void creat(struct node1 LS) /*建立广义表的单链表*/
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}
void print(struct node1 LS) /*输出广义单链表*/
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}
int depth(struct node1 LS) /*求广义表的深度*/
{
int max=0;
while(LS!=NULL)
{ if(LS->atom==0)
{ int dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
main()
{ int dep;
struct node1 *p=NULL;
creat(p); /*建立广义表的单链表*/
print(p); /*输出广义单链表*/
dep=depth(p); /*求广义表的深度*/
printf("%d\n",dep);
}
第六章 树
P109 二叉链表的结点类型定义如下:
typedef struct btnode
{ anytype data;
struct btnode *Lch,*Rch;
}tnodetype;
P109 三叉链表的结点类型定义如下:
typedef struct btnode3
{ anytype data;
struct btnode *Lch,*Rch,*Parent ;
}tnodetype3;
P112 C语言的先序遍历算法:
void preorder (tnodetype *t)
/*先序遍历二叉树算法,t为指向根结点的指针*/
{ if (t!=NULL)
{printf("%d ",t->data);
preorder(t->lch);
preorder(t->rch);
}
}
P113 C语言的中序遍历算法:
void inorder(tnodetype *t)
/*中序遍历二叉树算法,t为指向根结点的指针*/
{
if(t!=NULL)
{inorder(t->lch);
printf("%d ",t->data);
inorder(t->rch);
}
}
P113 C语言的后序遍历算法:
void postorder(tnodetype *t)
/*后序遍历二叉树算法,t为指向根结点的指针*/
{
if(t!=NULL)
{ postorder(t->lch);
postorder(t->rch);
printf("%d ",t->data);
}
}
P114 如果引入队列作为辅助存储工具,按层次遍历二叉树的算法可描述如下:
void levelorder(tnodetype *t)
/*按层次遍历二叉树算法,t为指向根结点的指针*/
{tnodetype q[20]; /*辅助队列*/
front=0;
rear=0; /*置空队列*/
if (t!=NULL)
{ rear++;
q[rear]=t; /*根结点入队*/
}
while (front!=rear)
{ front++;
t=q [front];
printf ("%c\n",t->data);
if (t->lch!=NULL) /*t的左孩子不空,则入队*/
{ rear++;
q [rear]=t->lch;
}
if (t->rch!=NULL) /*t的右孩子不空,则入队*/
{ rear++;
q [rear]=t->rch;
}
}
}
P115 以中序遍历的方法统计二叉树中的结点数和叶子结点数,算法描述为:
void inordercount (tnodetype *t)
/*中序遍历二叉树,统计树中的结点数和叶子结点数*/
{ if (t!=NULL)
{ inordercount (t->lch); /*中序遍历左子树*/
printf ("%c\n",t->data); /*访问根结点*/
countnode++; /*结点计数*/
if ((t->lch==NULL)&&(t->rch==NULL))
countleaf++; /*叶子结点计数*/
inordercount (t->rch); /*中序遍历右子树*/
}
}
P115 可按如下方法计算一棵二叉树的深度:
void preorderdeep (tnodetype *t,int j)
/*先序遍历二叉树,并计算二叉树的深度*/
{ if (t!=NULL)
{ printf ("%c\n",t->data); /*访问根结点*/
j++;
if (k<j) k=j;
preorderdeep (t->lch,j); /*先序遍历左子树*/
preorderdeep (t->rch,j); /*先序遍历右子树*/
}
}
P117 线索二叉树的结点类型定义如下:
struct nodexs
{anytype data;
struct nodexs *lch, *rch;
int ltag,rtag; /*左、右标志域*/
}
P117 中序次序线索化算法
void inorderxs (struct nodexs *t)
/*中序遍历t所指向的二叉树,并为结点建立线索*/
{ if (t!=NULL)
{ inorderxs (t->lch);
printf ("%c\n",t->data);
if (t->lch!=NULL)
t->ltag=0;
else { t->ltag=1;
t->lch=pr;
} /*建立t所指向结点的左线索,令其指向前驱结点pr*/
if (pr!=NULL)
{ if (pr->rch!=NULL)
pr->rtag=0;
else { pr->rtag=1;
pr->rch=p;
}
} /*建立pr所指向结点的右线索,令其指向后继结点p*/
pr=p;
inorderxs (t->rch);
}
}
P118 在中根线索树上检索某结点的前驱结点的算法描述如下:
struct nodexs * inpre (struct nodexs *q)
/*在中根线索树上检索q所指向的结点的前驱结点*/
{ if (q->ltag==1)
p=q->lch;
else { r=q->lch;
while (r->rtag!=1)
r=r->rch;
p=r;
}
return (p);
}
P119 在中根线索树上检索某结点的后继结点的算法描述如下:
struct nodexs * insucc (struct nodexs *q)
/*在中根线索树上检索q所指向的结点的后继结点*/
{ if (q->rtag==1)
p=q->rch;
else { r=q->rch;
while (r->ltag!=1)
r=r->lch;
p=r;
}
return (p);
}
P120 算法程序用C语言描述如下:
void sortBT(BT *t,BT *s) /*将指针s所指的结点插入到以t为根指针的二叉树中*/
{ if (t==NULL) t=s; /*若t所指为空树,s所指结点为根*/
else if (s->data < t->data)
sortBT(t->lch,s); /*s结点插入到t的左子树上去*/
else
sortBT(t->rch,s); /*s结点插入到t的右子树上去*/
}
P121 二叉排序树结点删除算法的C语言描述如下:
void delnode(bt,f,p)
/*bt为一棵二叉排序树的根指针,p指向被删除结点,f指向其双亲*/
/*当p=bt时f为NULL*/
{ fag=0; /*fag=0时需修改f指针信息,fag=1时不需修改*/
if (p->lch==NULL)
s=p->rch; /*被删除结点为叶子或其左子树为空*/
else if (p->rch==NULL)
s=p->lch;
else { q=p; /*被删除结点的左、右子树均非空*/
s=p->lch;
while (s->rch!=NULL)
{ q=s;
s=s->rch;
} /*寻找s结点*/
if (q=p)
q->lch=s->lch;
else q->rch=s->lch;
p->data=s->data; /*s所指向的结点代替被删除结点*/
DISPOSE(s);
Fag=1;
}
if (fag=0) /*需要修改双亲指针*/
{ if (f=NULL)
bt=s; /*被删除结点为根结点*/
else if (f->lch=p)
f->lch=s;
else f->rch=s;
DISPOSE(p); /*释放被删除结点*/
}
}
第七章 图
P134 用邻接矩阵表示法表示图,除了存储用于表示顶点间相邻关系的邻接矩阵外,通常还需要用一个顺序表来存储顶点信息。其形式说明如下:
# define n 6 /*图的顶点数*/
# define e 8 /*图的边(弧)数*/
typedef char vextype; /*顶点的数据类型*/
typedef float adjtype; /*权值类型*/
typedef struct
{vextype vexs[n];
adjtype arcs[n][n];
}graph;
P135 建立一个无向网络的算法。
CREATGRAPH(ga) /*建立无向网络*/
Graph * ga;
{
int i,j,k;
float w;
for(i=0;i<n;i++ )
ga ->vexs[i]=getchar(); /*读入顶点信息,建立顶点表*/
for(i=0;i<n;i++ )
for(j=0;j<n;j++)
ga ->arcs[i][j]=0; /*邻接矩阵初始化*/
for(k=0;k<e;k++) /*读入e条边*/
(scanf("%d%d%f",&I,&j,&w); /*读入边(vi,vj)上的权w */
ga ->arcs[i][j]=w;
ga - >arcs[j][i]=w;
}
} /*CREATGRAPH*/
P136 邻接表的形式说明及其建立算法:
typedef struct node
{int adjvex; /*邻接点域*/
struct node * next; /*链域*/
}edgenode; /*边表结点*/
typedef struct
{vextype vertex; /*顶点信息*/
edgenode link; /*边表头指针*/
}vexnode; /*顶点表结点*/
vexnode ga[n];
CREATADJLIST(ga) /*建立无向图的邻接表*/
Vexnode ga[ ];
{int i,j,k;
edgenode * s;
for(i=o;i<n;i++= /*读入顶点信息*/
(ga[i].vertex=getchar();
ga[i].1ink=NULL; /*边表头指针初始化*/
}
for(k=0;k<e;k++= /*建立边表*/
{scanf("%d%d",&i,&j); /*读入边(vi , vj)的顶点对序号*/
s=malloc(sizeof(edgenode)); /*生成邻接点序号为j的表结点*s */
s-> adjvex=j;
s- - >next:=ga[i].Link;
ga[i].1ink=s; /*将*s插入顶点vi的边表头部*/
s=malloc(size0f(edgende)); /*生成邻接点序号为i的边表结点*s */
s ->adjvex=i;
s ->next=ga[j].1ink;
ga[j].1ink=s; /*将*s插入顶点vj的边表头部*/
}
} /* CREATADJLIST */
P139 分别以邻接矩阵和邻接表作为图的存储结构给出具体算法,算法中g、g1和visited为全程量,visited的各分量初始值均为FALSE。
int visited[n] /*定义布尔向量visitd为全程量*/
Graph g; /*图g为全程量*/
DFS(i) /*从Vi+1出发深度优先搜索图g,g用邻接矩阵表示*/
int i;
{ int j;
printf("node:%c\n" , g.vexs[i]); /*访问出发点vi+1 */
Visited[i]=TRUE; /*标记vi+l已访问过*/
for (j=0;j<n;j++) /*依次搜索vi+1的邻接点*/
if((g.arcs[i][j]==1) &&(! visited[j]))
DFS(j); /*若Vi+l的邻接点vj+l未曾访问过,则从vj+l出发进行深度优先搜索*/
} /*DFS*/
vexnode gl[n] /*邻接表全程量*/
DFSL(i) /*从vi+l出发深度优先搜索图g1,g1用邻接表表示*/
int i;
{ int j;
edgenode * p;
printf("node:%C\n" ,g1[i].vertex);
vistited[i]=TRUE;
p=g1[i].1ink; /*取vi+1的边表头指针*/
while(p !=NULL) /*依次搜索vi+l的邻接点*/
{
if(! Vistited[p ->adjvex])
DFSL(p - >adjvex); /*从vi+1的未曾访问过的邻接点出发进行深度优先搜索*/
p=p - >next; /*找vi+l的下一个邻接点*/
}
} /* DFSL */
P142 以邻接矩阵和邻接表作为图的存储结构,分别给出宽度优先搜索算法。
BFS(k) /*从vk+l出发宽度优先搜索图g,g用邻接矩阵表示,visited为访问标志向量*/
int k;
{ int i,j;
SETNULL(Q); /*置空队Q */
printf("%c\n",g.vexs[k]); /*访问出发点vk+l*x/
visited[k]=TRUE; /*标记vk+l已访问过*/
ENQUEUE(Q,K); /*已访问过的顶点(序号)入队列*/
While(!EMPTY(Q)) /*队非空时执行*/
{i=DEQUEUE(Q); /*队头元素序号出队列*/
for(j=0;j<n;j++)
if((g.arcs[i][j]==1)&&(! visited[j]))
{printf("%c\n" , g.vexs[j]); /*访问vi+l的未曾访问的邻接点vj+l */
visited[j]=TRUE;
ENQUEUE(Q,j); /*访问过的顶点入队*/
}
}
} /* BFS */
BFSL(k) /*从vk+l出发宽度优先搜索图g1,g1用邻接表表示*/
int k
{ int i;
edgenode * p;
SETNULL(Q);
printf("%c\n" , g1[k].vertex);
visited[k]=TRUE;
ENQUEUE(Q,k);
while(! EMPTY(Q));
{ i=DEQUEUE(Q);
p=g1[i].1ink /*取vi+l的边表头指针*/
while(p !=NULL) /*依次搜索vi+l的邻接点*/
{ if( ! visited[p - >adjvex]) /*访问vi+l的未访问的邻接点*/
{ printf{"%c\n" , g1[p - >adjvex].vertex};
visited[p - >adjvex]=TRUE;
ENQUEUE(Q,p - >adjvex); /*访问过的顶点入队*/
}
p=p - >next; /*找vi+l的下一个邻接点*/
}
}
} /*BFSL*/
P148 在对算法Prim求精之前,先确定有关的存储结构如下:
typdef struct
{Int fromvex,endvex; /*边的起点和终点*/
float length; /*边的权值*/
} edge;
float dist[n][n]; /*连通网络的带权邻接矩阵*/
edgeT[n-1]; /*生成树*/
P149 抽象语句(1)可求精为:
for(j=1;j<n;j++) /*对n-1个蓝点构造候选紫边集*/
{T[j-1].fromvex=1}; /*紫边的起点为红点*/
T[j-1].endvex=j+1; /*紫边的终点为蓝点*/
T[j-1].1ength=dist[0][j]; /*紫边长度*/
}
P149 抽象语句(3)所求的第k条最短紫边可求精为:
min=max; /*znax大于任何边上的权值*/
for (j=k;j<n-1;j++) /*扫描当前候选紫边集T[k]到T[n-2],找最短紫边*/
if(T[j].1ength<min)
{min=T[j].1ength;m=j; /*记录当前最短紫边的位置*/
}
P149 抽象语句(4)的求精:
e=T[m];T[m]=T[k];T[k]=e, /* T[k]和T[m]交换*/
v=T[kl.Endvex]; /* v是刚被涂红色的顶点*/
P149 抽象语句(5)可求精为:
for(j=k+1;j<n-1;j++) /*调整候选紫边集T[k+1]到T[n-2]*/
{d=dist[v-1][T[j].endvex-1]; /*新紫边的长度*/
if(d<T[j].1ength) /*新紫边的长度小于原最短紫边*/
{T[j].1ength=d;
T[j].fromvex=v; /*新紫边取代原最短紫边*/
}
}
P150 完整的算法:
PRIM() /*从第一个顶点出发构造连通网络dist的最小生成树,结果放在T中*/
{int j , k , m , v , min , max=l0000;
float d;
edge e;
for(j=1;j<n;j++) /*构造初始候选紫边集*/
{T[j-1].formvex=1; /*顶点1是第一个加入树中的红点*/
T[j-1].endvex=j+1;
T[j-1].length=dist[o][j];
}
for(k=0;k<n-1;k++) /*求第k条边*/
{min=max;
for(j=k;j<n-1;j++) /*在候选紫边集中找最短紫边*/
if(T[j].1ength<min)
{min=T[j].1ength;
m=j;
} /*T[m]是当前最短紫边*/
}
e=T[m];T[m]=T[k];T[k]=e; /*T[k]和T[m]交换后,T[k]是第k条红色树边*/
v=T[k].endvex ; /* v是新红点*/
for(j=k+1;j<n-1;j++) /*调整候选紫边集*/
{d=dist[v-1][T[j].endvex-1];
if(d<T[j].1ength);
{T[j].1ength=d;
T[j].fromvex=v;
}
}
} /* PRIM */
P151 Kruskl算法的粗略描述:
T=(V,φ);
While(T中所含边数<n-1)
{从E中选取当前最短边(u,v);
从E中删去边(u,v);
if((u,v)并入T之后不产生回路,将边(u,v)并入T中;
}
P153 迪杰斯特拉算法实现。算法描述如下:
#define max 32767 /*max代表一个很大的数*/
void dijkstra (float cost[][n],int v)
/*求源点v到其余顶点的最短路径及其长度*/
{ v1=v-1;
for (i=0;i<n;i++)
{ dist[i]=cost[v1][i]; /*初始化dist*/
if (dist[i]<max)
pre[i]=v;
else pre[i]=0;
}
pre[v1]=0;
for (i=0;i<n;i++)
s[i]=0; /*s数组初始化为空*/
s[v1]=1; /*将源点v归入s集合*/
for (i=0;i<n;i++)
{ min=max;
for (j=0;j<n;j++)
if (!s[j] && (dist[j]<min))
{ min=dist[j];
k=j;
} /*选择dist值最小的顶点k+1*/
s[k]=1; /*将顶点k+1归入s集合中*/
for (j=0;j<n;j++)
if (!s[j]&&(dist[j]>dist[k]+cost[k][j]))
{ dist[j]=dist[k]+cost[k][j]; /*修改 V-S集合中各顶点的dist值*/
pre[j]=k+1; /*k+1顶点是j+1顶点的前驱*/
}
} /*所有顶点均已加入到S集合中*/
for (j=0;j<n;j++) /*打印结果*/
{ printf("%f\n%d",dist[j],j+1;);
p=pre[j];
while (p!=0)
{ printf("%d",p);
p=pre[p-1];
}
}
}
P155 弗洛伊德算法可以描述为:
A(0)[i][j]=cost[i][j]; //cost为图的邻接矩阵
A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]}
其中 k=1,2,…,n
P155 弗洛伊德算法实现。算法描述如下:
int path[n][n]; /*路径矩阵*/
void floyd (float A[][n],cost[][n])
{ for (i=0;i<n;i++) /*设置A和path的初值*/
for (j=0;j<n;j++)
{ if (cost[i][j]<max)
path[i][j]=j;
else { path[i][j]=0;
A[i][j]=cost[i][j];
}
}
for (k=0;k<n;k++)
/*做n次迭代,每次均试图将顶点k扩充到当前求得的从i到j的最短路径上*/
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (A[i][j]>(A[i][k]+A[k]
考考自己吧
人不能总能依靠别人.
这些代码都可以在知道里面直纯属体力劳动,重复的无意义工作我还是不要做了...
接搜到,无需再悬赏。
回答完你这些问题我要几个小时,你就给150分,太少了吧
这些代码都可以在知道里面直接搜到,无需再悬赏。
数据结构考研用什么辅导书
第二版是2007年最新出版的,对里面的题目进行了大量的更新,去掉了一些比较过时和重复的题,加上了很多名校最近几年的考研真题,总共大约1650题左右。真题就是训练的最好武器,相信当你复习完这本数据结构辅导书后,任何关于数据结构的考题都是小菜一碟。3、《数据结构C++版》。数据结构是计算机专业教学...
计算机专业考研科目有哪些?专业基础课是不是所有高校都一样呢?_百度知...
链接:提取码:7q4d 计算机科学与技术(Computer Science and Technology)是国家一级学科,下设信息安全、软件工程、计算机软件与理论、计算机系统结构、计算机应用技术、计算机技术等专业。
计算机专业考研 专业课 参考资料
为大家整理了一份考研学习资料,包括各大机构的语文,数学,英语以及各大专业课的学习资源,适合想自考的学生,后面会不断汇聚更多优秀学习资源,供大家交流分享学习,需要的可以先收藏转存,有时间慢慢看~考研资料实时更新 链接:https:\/\/pan.baidu.com\/s\/1oE-xAzF7lQZSvrr5dZPrdg ?pwd=2D72 提取...
北京科技大学计算机考研
《北京科技大学《871计算机综合一》考研全套教程》百度网盘资源免费下载 链接: https:\/\/pan.baidu.com\/s\/1ip0iOcOitTMq993yyDjJWQ ?pwd=kmk4 提取码: kmk4 北京科技大学《871计算机综合一》考研全套教程|北京科技大学《871计算机综合一》考研全套教程(晒图送)|8 . 《数据结构》、《组成原理》本科...
408统考科目包括什么内容?
举例来说,栈这种数据结构有两种实现方式(即存储方式):顺序栈和链式栈,经过一到两轮的复习之后,考生应该能够比较熟练地使用C语言(当然也可以用C++等高级语言)写出这两种方式下栈的定义以及初始化、进栈、出栈、返回栈顶元素等各种基本操作的算法实现,有条件的同学,可以上机调试算法。也就是说,对于每...
全国计算机二级vb考试具体考什么内容?
3.了解简单的数据结构和算法。 4.能够编写和调试简单的VisualBasic程序。 考试内容 一、VisualBasic程序开发环境 1.Visual Basic的特点和版本。 2.Visual Basic的启动与退出。 3.主窗口: (1)标题和菜单。 (2)工具栏。 全国计算机等级考试——VB考试200209~2009 4.其它窗口: (1)窗体设计器和工程资源管理器。
计算机一级考试试题
A:使用了先进的电子器件 B:事先编程并输入计算机 C:采用了高效的编程语言 D:开发了高级操作系统 答案: B 4、计算机的应用领域可大致分为几个方面,下列四组中,属于其应用范围的是 。 A:计算机辅助教学、专家系统、操作系统 B:工程计算、数据结构、文字处理 C:实时控制、科学计算、数据处理 D:数值处理、人工...
全国计算机等级考试二级C语言的考试题目都是从《C语言题库》里面抽取...
全国计算机等级考试二级C语言的考试题目的小题不是从《C语言题库》中抽取的,后面的大题即编程题全部是从最近的一年的《C语言题库》中抽取的。考题大部分是C语言,少部分是算法与数据结构里面的东西。就算不是《C语言题库》题库里的题,但是题型都差不多的。c语言是一门面向过程、抽象化的通用程序...
851数据结构怎么复习
数据结构的复习方法:1、以课本为本,以考纲为纲,把课本吃透。考题肯定是根据指定的教材出,不是根据某家出版社的教辅材料出。平常的考试题目,几乎百分之百都可以在课本中找到原型——当然经过多层的综合和深化。2、三遍读书法。第一遍应该以整体浏览为主,争取明白全书概要,不要求理解每个具体知识点...
考研计算机网络和数据库哪个难?
现在计算机专业考研,初试全国统一。有四门课:数据结构、计算机组成原理、操作系统、计算机网络。复试:各学校的情况不大一样。有的考这两门,有的不考。比如会考这些科目:数据库、计算机体系结构、编译原理、汇编语言…总体感觉,数据结构难于计算机网络。尤其是算法设计部分。PS:初试就是那四门。总分150...
苍梧明米诺:http://apps.hi.baidu.com/share/detail/19838161商品货架可以看成一个栈,栈顶商品的生产日期最早,栈底商品的生产日期最近. 上货时,需要倒货架,以保证生产日期较近的商品在较下的位置.#include#include#define size 4...
鄂尔多斯市19519629514: C语言版数据结构编程题 - ?
苍梧明米诺: //试编写一道在单链表中数据域值为a的结点之后,//插入一个新结点的算法.若原链表中无数据域值为a的结点,//则把新结点插入到表尾.设新结点数据域值为x.小弟初学,谢谢大家啦//定义结点 typedef struct node{ int data; struct node *next; }LNode...
鄂尔多斯市19519629514: 系列数据结构(C语言题),感激不尽 - ?
苍梧明米诺: 1、2342、*+A+BCDE*FG -+*A-BD/H+DE/S*NT *-AC+BD/-EF+GH3、1/(n-1)4、3.35、集合,线性,树形和图6、bceda15、 void SelectSort(int a[],int n) { int l=n,k,x; for(int i=1;i<=l-1;++i) {k=i; for(int j=i+1;j<=l;++j) { if(a[j]<a[k]) k=j; if(k!=j) { x=a[i];r[i]=r[k];r[k]=x; } } } }16、这个就不知道了 自己好好想想啊
鄂尔多斯市19519629514: 数据结构习题:编写判断一个字符序列是否是回文的函数.非常急,《数据结构 - 使用C语言》第四版,朱战立编的.84页习题3 - 18.编写判断一个字符序列是否是... - ?
苍梧明米诺:[答案] //首先我认为回文不一定是奇数个;也有可能是偶数个;只要这个字符串 //正读跟反读都一样 那它就是回文 所以不应该把字符串的个数当成是判断回文串的 //一个条件. #include #include #include bool huiWen(const char *p); int main() { char test[225]; ...
鄂尔多斯市19519629514: 数据结构题(C语言)?
苍梧明米诺: #include <stdio.h> #include <malloc.h> #include <string.h> typedef struct LNode { char stuID[10]; int data; struct LNode *next; }LNode,*LinkList; void CreateList_L(LNode* L) { LinkList p; char tmp[10]; scanf("%s",tmp); while(strcmp(tmp,"0") != 0)...
鄂尔多斯市19519629514: C语言数据结构试验 - ?
苍梧明米诺: Status Initlist_Sq(SqList &L) /*初始化顺序表*/ { L=(SqList *)malloc(sizeof(SqList)); l->length=0; } void Destroylist(SqList &L) /*销毁顺序表*/ { free(L); } void Clearlist_Sq(SqList &L) /*清空顺序表*/ { 同上} Status Listempty_Sq(SqList L) /*测试顺序表是...
鄂尔多斯市19519629514: 数据结构(C语言版)的一道题 - ?
苍梧明米诺: 楼主,你好,我前天恰好做了一道类似的题,代码如下,我都给你注释了 struct staff *reverse(struct staff *head) //struct staff是个结构体 { struct staff *p,*q,*temp,*o;q=head; //q指针始终保持在p的前一个结点处 p=head->next; //利用p指针从第2个...
鄂尔多斯市19519629514: 数据结构的习题(C语言版)?
苍梧明米诺: 第一个问题,分析下要求,可以知道要做的事情是合并两个数组到一个数组里去,数组C的长度是AB之和.表C的第一个字符不是A的第一个字符就是B的第一个字符.因此接下来要做的事情就是做一个长度为AB之和的循环,每一次找出A或B中...
鄂尔多斯市19519629514: 有关C语言(数据结构)程序设计题?
苍梧明米诺: struct Node; typedef struct Node *PNode; struct Node //节点类型; { DataType info; PNode link; }; typedef struct Node *LinkList; //单链表类型 int insert_link(LinkList llist,DataType y,DataType x) { PNode p,q; p=llist; while(p!=null&&y!=p-&...
鄂尔多斯市19519629514: 数据结构难题(C语言) - ?
苍梧明米诺: #include<stdio.h> #include<stdlib.h> #include<time.h> #define MAX 100 /* 快速排序算法的两个主要步骤,分割(Partition和QuickSort) */ int Partition(int A[],int p,int q); int QuickSort(int A[],int p,int q); int test(); int main() { test();return0; } /* 一个...