数据结构与算法源代码(数据结构与算法分析c语言版)
admin 发布:2022-12-19 20:15 135
本篇文章给大家谈谈数据结构与算法源代码,以及数据结构与算法分析c语言版对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。
本文目录一览:
- 1、【数据结构】线性表(包括有序表)在顺序表和链表上的插入、删除、逆置操作算法
- 2、《数据结构》算法实现与分析高一凡中的源代码要怎么用
- 3、c语言数据结构(考题,测试你的能力)--编写源代码
- 4、如何理解编程中最没用的东西是源代码,最有用的东西是算法和数据结构
- 5、数据结构与算法演示系统完整简单的c++源代码,包哈内容有:线性表、二叉树、图、排序,急用!谢谢!
【数据结构】线性表(包括有序表)在顺序表和链表上的插入、删除、逆置操作算法
1)初始化指针p和q,分别指向链表中相邻的两个元素;
2)当p-next不为空时,做如下处理:
①若相邻两元素不相等时,p和q都向后推一步;
②否则,当相邻元素相等时,删除多余元素。
【算法源代码】
void Delete_Equal(LinkList *L)
{ p=(*L)-next;q=p-next; /*p和q指向相邻的两个元素*/
while(p-next)
{ if(p-data!=q-data) /*若相邻两元素不相等时,p和q都向后推一步*/
{ p=p-next; q=p-next; }
else
{ while(q-data==p-data) /*当相邻元素相等时删除多余元素*/
{ r=q;
q=q-next;
free(r);
}
p-next=q;p=q;q=p-next;
}/*else*/
}/*while*/
}/*Delete_Equal */
试设计一个算法,对带头结点的单链表实现就地逆置。
【算法分析】
1)空表或长度为1的表,不做任何处理;
2)表长大于2时,做如下处理:
①首先将整个链表一分为二,即从链表的第一元素结点处断开;
②逐个地把剩余链表的当前元素q插入到链表的头部。
【算法源代码】
void LinkList_reverse(LinkList L)
{ if(!L-next||!L-next-next) return;
p=L-next; q=p-next; s=q-next; p-next=NULL; /*从链表的第一元素结点处断开*/
while(s-next)
{q-next=p;p=q;
q=s;s=s-next; /*把L的元素逐个插入新表表头*/
}
q-next=p;s-next=q;L-next=s;
}/*LinkList_reverse*/
《数据结构》算法实现与分析高一凡中的源代码要怎么用
这个代码可以直接用。用的时候必须把include中的文件也保存好。
c语言数据结构(考题,测试你的能力)--编写源代码
P88 稀疏矩阵十字链表相加算法如下:
/*假设ha为A稀疏矩阵十字链表的头指针,hb为B稀疏矩阵十字链表的头指针*/
#includestdio.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 (mn) 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-jj))
q=q-rptr;
p-rptr=q-rptr;
q-rptr=p;
/*以下是将P插入到第j列链表中*/
q=cp[j];
while((q-cptr!=cp[j]) ( q-cptr-ii))
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-jpb-j)(pa-j!=0))
{ qa=pa; pa=pa-rptr;}
else if ((pa-jpb-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-ip-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-ipa-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(depmax) 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)。整个完整程序如下:
#includestdio.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(depmax) 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 (kj) 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;in;i++ )
ga -vexs[i]=getchar(); /*读入顶点信息,建立顶点表*/
for(i=0;in;i++ )
for(j=0;jn;j++)
ga -arcs[i][j]=0; /*邻接矩阵初始化*/
for(k=0;ke;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;in;i++= /*读入顶点信息*/
(ga[i].vertex=getchar();
ga[i].1ink=NULL; /*边表头指针初始化*/
}
for(k=0;ke;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;jn;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;jn;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;jn;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;jn-1;j++) /*扫描当前候选紫边集T[k]到T[n-2],找最短紫边*/
if(T[j].1engthmin)
{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;jn-1;j++) /*调整候选紫边集T[k+1]到T[n-2]*/
{d=dist[v-1][T[j].endvex-1]; /*新紫边的长度*/
if(dT[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;jn;j++) /*构造初始候选紫边集*/
{T[j-1].formvex=1; /*顶点1是第一个加入树中的红点*/
T[j-1].endvex=j+1;
T[j-1].length=dist[o][j];
}
for(k=0;kn-1;k++) /*求第k条边*/
{min=max;
for(j=k;jn-1;j++) /*在候选紫边集中找最短紫边*/
if(T[j].1engthmin)
{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;jn-1;j++) /*调整候选紫边集*/
{d=dist[v-1][T[j].endvex-1];
if(dT[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;in;i++)
{ dist[i]=cost[v1][i]; /*初始化dist*/
if (dist[i]max)
pre[i]=v;
else pre[i]=0;
}
pre[v1]=0;
for (i=0;in;i++)
s[i]=0; /*s数组初始化为空*/
s[v1]=1; /*将源点v归入s集合*/
for (i=0;in;i++)
{ min=max;
for (j=0;jn;j++)
if (!s[j] (dist[j]min))
{ min=dist[j];
k=j;
} /*选择dist值最小的顶点k+1*/
s[k]=1; /*将顶点k+1归入s集合中*/
for (j=0;jn;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;jn;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;in;i++) /*设置A和path的初值*/
for (j=0;jn;j++)
{ if (cost[i][j]max)
path[i][j]=j;
else { path[i][j]=0;
A[i][j]=cost[i][j];
}
}
for (k=0;kn;k++)
/*做n次迭代,每次均试图将顶点k扩充到当前求得的从i到j的最短路径上*/
for (i=0;in;i++)
for (j=0;jn;j++)
if (A[i][j](A[i][k]+A[k]
如何理解编程中最没用的东西是源代码,最有用的东西是算法和数据结构
了解和熟悉基础的算法和数据结构是必要的,所有开发平台和开发工具的设计趋向于简单化,人性化。也就更希望开发者多专注在业务逻辑上,而不必纠结于复杂的底层实现。当然很多所谓的高精尖端的地方需要实现各种高难度算法和数据结构,但是那毕竟是少数。工具类的知识只要你肯花时间,总是能够学会的,而思想你却不一定能学得会。偏偏越底层越基础的东西,才是最有价值的。上层的东西总是会死的,无论他现在多么牛逼。
数据结构与算法演示系统完整简单的c++源代码,包哈内容有:线性表、二叉树、图、排序,急用!谢谢!
我有表和二叉树的,图和排序没有!那玩意不能简单的,一个就得100多行!而且只是。h文件。先给你2个吧!
#ifndef SQLIST_H
#define SQLIST_H
using namespace std;
templateclass elemtype
class sqlist
{
public:
sqlist(){head=NULL; n=0;}
virtual ~sqlist(){head=NULL;}
bool insert(const elemtype ,int);
elemtype find(int );
void clear();
int length()const {return n;}
bool Delete(int );
protected:
int n;
struct node{
node *next;
elemtype data;
};
node *head;
};
templateclass elemtype
void sqlistelemtype::clear()
{
node *p,*q;
int i=1;
p=head;
while(i!=n)
{
q=p;
delete q;
p=p-next;
i++;
}
}
templateclass elemtype
bool sqlistelemtype::insert(const elemtype e,int i)
{
node *p,*q;
int j=1;
if(head==NULL)
head=new node;
p=head;
if(i==1in)//表头赋值
{head-data=e;
n++;
return true;}
else if(i==1i=n)//表头插入
{
head=new node;
head-data=e;
head-next=p;
n++;
return true;
}
else if(i=n) //表中插入
{
q=new node;
q-data=e;
while(ji-1){
p=p-next;
j++;
}
q-next=p-next;
p-next=q;
n++;
return true;}
else if(i==n+1i!=1)//表尾插入
{
q=new node;
q-data=e;
while (jn)
{
p=p-next;
j++;
}
p-next=q;
q-next=NULL;
n++;
return true;}
else
return false;
}
templateclass elemtype
elemtype sqlistelemtype::find(int i)
{
int j=1;
node *p;
p=head;
while(ji){
p=p-next;
j++;
}
return p-data;
}
templateclass elemtype
bool sqlistelemtype::Delete(int i)
{
int j=1;
node *p,*q;
p=head;
if(i!=1)//表中及表尾删除
{
while(ji)
{
q=p;
p=p-next;
j++;
}
q-next=p-next;
delete p;
n--;
return true;}
else//表头删除
head=p-next;
delete p;
n--;
return true;
}
#endif // SQLIST_H
#ifndef binarytree_H
#define binarytree_H
#include"stack.h"
#include"queue.h"
using namespace std;
templateclass elemtype
class binarytree{
public:
binarytree(){root=NULL;}
~binarytree(){}
int height(){return height(root);}
int size(){return size(root);}
void createtree(elemtype flag);
void preorder() const ;
void midorder() const ;
void postorder() const ;
bool isempty(){return root==NULL;}
void clear(){if (root!=NULL) clear(root);}
void delleft(){ clear(root-left);}
int height()const{return height(root );}
void delright(){return clear(root-right);}
private:
struct node{
node *left,*right;
elemtype data;
node():left(NULL),right(NULL){}
node(elemtype it,node*l=NULL,node*r=NULL):data(it),left(l),right(r){}
};
node *root;
struct stnode{
node *t;
int step;
stnode(node *tc=NULL):t(tc),step(0){}
};
void clear(node *);
int size(node* );
int height(node*);
};
templateclass elemtype
void binarytreeelemtype:: clear(node *t)
{
queuenode la;
node *tem,*q,*p;
la.append(t);
while(!la.empty()){
tem=la.putelem();
if(tem-left!=NULL)
{ p=t-left;
la.append(p);}
if(tem-right!=NULL)
{ q=tem-right;
la.append(q);}
delete tem;
}
}
templateclass elemtype
void binarytreeelemtype::createtree(elemtype flag)
{
queuenode* la;
node *tem;
elemtype x,ldata,rdata;
cout"根节点:";
cinx;
root=new node(x);
la.append(root);
while(!la.isempty()){
tem=la.putelem();
cout"输入"tem-data"的两节点值:";
cinldatardata;
if(ldata!=flag) la.append(tem-left=new node(ldata));
if(rdata!=flag) la.append(tem-right=new node(rdata));
}
}
templateclass elemtype
void binarytreeelemtype::preorder( )const
{
stacknode* la;
node *tem;
cout"前序遍历为:";
la.push(root);
while(!la.empty()){
tem=la.pop();
couttem-data" ";
if(tem-right!=NULL)
la.push(tem-right);
if(tem-left!=NULL)
la.push(tem-left);
}
}
templateclass elemtype
void binarytreeelemtype::midorder() const
{
stackstnode la;
stnode tem(root);
cout"中序遍历:";
la.push(tem);
while(!la.empty()){
tem=la.pop();
if(++tem.step==2){
couttem.t-data" ";
if(tem.t-right!=NULL)
la.push(stnode(tem.t-right));}
else{
la.push(tem);
if(tem.t-left!=NULL)
la.push(stnode(tem.t-left));
}
}
}
templateclass elemtype
void binarytreeelemtype::postorder() const
{
stackstnode la;
stnode tem(root);
cout"后序遍历:";
la.push(tem);
while(!la.empty()){
tem=la.pop();
if(++tem.step==3)
{couttem.t-data" ";continue;}
la.push(tem);
if(tem.step==1)
{
if(tem.t-left!=NULL)
la.push(stnode(tem.t-left));
}
else{
if(tem.t-right!=NULL)
la.push(stnode(tem.t-right));
}
}
}
templateclass elemtype
int binarytreeelemtype::size(node *t)
{
queuenode* la;
node *tem;
int a=0;
la.append(t);
while(!la.isempty()){
tem=la.putelem();
a++;
if(tem-left!=NULL)
la.append(tem-left);
if(tem-right!=NULL)
la.append(tem-right);
}
return a;
}
templateclass elemtype
int binarytreeelemtype::height(node* t)const
{
queuenode* la;
atacknode* lb;
node *tmp;
la.append(t);
while(!la.isempty())
{
tmp=la.putelem();
if(tmp-left)
}
/*if(t==NULL) return 0;
else
{
int l=height(t-left),r=height(t-right);
return 1+((lr)?l:r);
}*/
}
}
你还不如用stl!而且你要这玩意干什么?c++书里都有的,实在不行自己抄书不也行吗?c++的表分单链表,循环单链表,循环双链表(我给的只是单链表)。二叉树我自己用的非递归实现,除了求高度。但要用到栈和队列,你自己写吧,太多了!发着麻烦。
数据结构与算法源代码的介绍就聊到这里吧,感谢你花时间阅读本站内容,更多关于数据结构与算法分析c语言版、数据结构与算法源代码的信息别忘了在本站进行查找喔。
版权说明:如非注明,本站文章均为 AH站长 原创,转载请注明出处和附带本文链接;
- 上一篇:加载更多的代码(加载更多的代码是什么)
- 下一篇:包含回帖奖励代码的词条
相关推荐
- 05-18软文发布平台,软文发布平台分析
- 05-18网络营销案例具体分析,网络营销案例具体分析模板
- 05-15seo分析报告,做seo的分析工具有哪些
- 05-12网页设计需要学什么,网页设计学什么语言
- 05-07aso优化分析,aso优化方法
- 05-07pb超级报表源代码(pb报表工具)[20240507更新]
- 05-07简历源代码可以上传照片的简单介绍[20240507更新]
- 05-07广告切换源代码免费下载(广告切换源代码免费下载安装)[20240507更新]
- 05-06阁楼网源代码(阁楼是什么网站)[20240506更新]
- 05-06源代码管理资源管理器(资源管理器运行代码)[20240506更新]
取消回复欢迎 你 发表评论:
- 标签列表
- 最近发表
- 友情链接