数据结构c语言版源代码（数据结构C语言版）

今天给各位分享数据结构c语言版源代码的知识，其中也会对数据结构C语言版进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、数据结构 冒泡排序 c语言 源代码 急用啊
• 2、数据结构c语言版的一段代码求高手帮忙调试
• 3、c语言数据结构（考题，测试你的能力）－－编写源代码
• 4、求数据结构（c语言版）程序源代码

数据结构 冒泡排序 c语言 源代码 急用啊

void bubble_sort(int *x, int n)

{

int j, k, h, t;

for (h=n-1,h=k; h0; h--) /*循环到没有比较范围*/

{

for (j=0, k=0; jh; j++) /*每次预置k=0，循环扫描后更新k*/

{

if (*(x+j) *(x+j+1)) /*大的放在后面，小的放到前面*/

{

t = *(x+j);

*(x+j) = *(x+j+1);

*(x+j+1) = t; /*完成交换*/

k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/

}

}

}

}

数据结构c语言版的一段代码求高手帮忙调试

发完整的程序吧，我调试下cenjoy@qq.com

=======================================================

程序修改好了，使用了两种方法排序，一种类似快速排序、一种使用冒泡排序。

给楼主个建议啊，函数体后面是没有必要加分号的。

=======================================================

#include STDIO.H

#include MALLOC.H

#define NULL 0

typedef struct linknode

{

int data;

struct linknode *next;

}node;

node *head;

int length()

{

node *currnode;

int i=0;

currnode=head;

while(currnode)

{

currnode=currnode-next;

i++;

};

return i;

}

node *creat(node *head)

{

node *currnode,*newnode;

int x;

head=(node*)malloc(sizeof(node));

currnode=head;

do{

scanf("%d",x);

newnode=(node*)malloc(sizeof(node));

newnode-data=x;

currnode-next=newnode;

currnode=newnode;

}while(x!=NULL);

head=head-next;

currnode-next=NULL;

return head;

}

void print()

{

node *currnode;

currnode = head;

printf("链表如下....linklist:");

while(currnode-data != 0)

{

printf("%d--",currnode-data);

currnode = currnode-next;

};

printf("NULL\n");

printf("链表长度为........linklist length%d\n",length());

}

void Delete()

{

int x;

node *delnode,*currnode;

printf("输入要删除数据.......input delete data：");

scanf("%d",x);

if(head-data==NULL) printf("此链表为空无法删除......this linklist empty！\n");

if(head-data==x)

{

delnode=head;

head=head-next;

free(delnode);

if(head==NULL) printf("此链表为空........this linklist enpty！");

}

else

{

currnode=head;

delnode=currnode-next;

while(delnode-data!=xdelnode!=NULL)

{

currnode=currnode-next;

delnode=currnode-next;

};

if(delnode==NULL)

printf("无此数据.......no this data！\n");

else

{

currnode-next=delnode-next;

free(delnode);

}

}

}

void find()

{

node *currnode;

int count=1,x;

currnode=head;

printf("输入要查找数据........input search data:");

scanf("%d",x);

while(currnode-data!=NULLcurrnode-data!=x)

{

currnode=currnode-next;

count++;

}

if(currnode-data!=NULL)

{

printf("\n%d为第.........is no.",currnode-data);

printf("%d个数据.........data。\n",count);

}

else

printf("\n无此数据........not this data!\n");

}

void insert()

{

int x,w,i;

node *insertnode, *afternode,*currnode;

printf("输入要插入数据.........input inserte data：");

scanf("%d",x);

printf("插入n结点后..........inserta after no. data n=:(0，1，…)");

scanf("%d",w);

insertnode=(node*)malloc(sizeof(node));

insertnode-data=x;

if(w==0)

{

insertnode-next=head;

head=insertnode;

}

else

if(wlength()){ printf("超出范围.........overflow!\n");}

else

{

currnode=head;afternode=currnode-next;

for(i=1;iw;i++)

{

afternode=afternode-next;

currnode=currnode-next;

}

currnode-next=insertnode;

insertnode-next=afternode;

}

}

void Sort(node *h)//类似快速排序

{

node *p,*q,*minp;

int min,temp;

for(p = h; p != NULL p-data != 0; p = p-next)

{

min = p-data;

minp = p;

q = p-next;

while(q != NULL q-data != 0)

{

if(q-data min)

{

min = q-data;

minp = q;

q = q-next;

}

else

{

q = q-next;

}

}

temp = p-data;

p-data = minp-data;

minp-data = temp;

}

}

void Sort2(node *h)/*冒泡排序*/

{

node *p,*q;

node *L = (node *)malloc(sizeof(node));

L-next = h;

int temp;

for(p = L; p != NULL p-data != 0; p = p-next)

{

for(q = p-next; q != NULL q-data != 0; q = q-next)

{

if(p-data q-data)

{

temp = q-data;

q-data = p-data;

p-data = temp;

}

}

}

free(L);

}

void operation()

{

printf("\n\n删除数据输入........delete: 1\n");

printf("\n查找数据输入........search: 2\n");

printf("\n插入数据输入........insert: 3\n");

printf("\n排序A请输入..........sort: 4\n");

printf("\n排序B请输入..........sort: 5\n");

printf("\n结束操作............end: 6\n");

printf("\n?:");

}

void main()

{

int choic;

printf("\n输入数据以0结束..........input data 0 end:\n");

head=creat(head);

print();

operation();

do{

scanf("%d",choic);

switch(choic)

{

case 1:

Delete();

print();

operation();

break;

case 2: find();

operation();

break;

case 3:insert();

print();

operation();

break;

case 4:

Sort(head);

print();

operation();

break;

case 5:

Sort2(head);

print();

operation();

break;

default:printf("操作结束........operate end!");

break;

}

}while(choic!=6);

}

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语言版）程序源代码

1 #include string.h

2 #include stdio.h

3 #include stdlib.h

4

5 #define MAX_POS_NUM 100

6 #define MAX_STR_LEN 1024

7

8

9 //1. get all position of str_z in str_x

10 int get_sub_str_pos(const char * str_x, const char * str_z, int sub_str_pos[])

11 {

12 if (NULL == str_x || NULL == str_z)

13 {

14 printf("in error!\n");

15 return -1;

16 }

17

18 const char * pos_ptr = NULL;

19

20 pos_ptr = strstr(str_x,str_z);

21

22 int i=0;

23 while(pos_ptr)

24 {

25 printf("substring positon:%d\n",pos_ptr-str_x+1);

26 sub_str_pos[i] = pos_ptr - str_x + 1;

27 pos_ptr = strstr(pos_ptr+strlen(str_z),str_z);

28 i++;

29 }

30

31 return 0;

32 }

33

34 //2. get max length common string of str_x and str_y

35 char * get_max_com_str(const char * str_x, const char * str_y)

36 {

37 int x_len = strlen(str_x);

38 int y_len = strlen(str_y);

39

40 char * tmp_str = new char[y_len+1];

41

42 for(int i=y_len; i0; i--) // i is substring length

43 {

44 if (ix_len)

45 continue;

46 for(int j=0;j=y_len-i; j++) // j is substring start postion

47 {

48 snprintf(tmp_str,i+1,"%s",str_y);

49 if (strstr(str_x,tmp_str))

50 {

51 printf("%s\n",tmp_str);

52 printf("max common substring length:%d\n",i);

53 return tmp_str;

54 }

55 }

56 }

57

58 return NULL;

59 }

60

61 //3. replace all substring in question 1

62 char * replace_sub_str(const char * str_x, char * max_com_str, int sub_str_pos[], int sub_str_len)

63 {

64 char * replaced_str = new char[MAX_STR_LEN];

65

66 int sub_pos = sub_str_pos[0];

67 int l=0; // l is sub_str_pos index

68 int i=0,j=0; //i is str_x pos, j is replaced_str pos

69

70 while(*str_x)

71 {

72 if (i==sub_pos-1) // replace from this position

73 {

74 // printf ("i:%d,\n",i);

75 for (int k=0; kstrlen(max_com_str); k++)

76 {

77 *(replaced_str + j) = * (max_com_str + k);

78 j++;

79 }

80 i += sub_str_len;

81 str_x += sub_str_len;

82 l++;

83 sub_pos = sub_str_pos[l];

84 continue;

85 }

86 *(replaced_str+j) = *str_x++;

87 i++;

88 j++;

89 }

90

91 * (replaced_str + j) = '\0';

92

93 return replaced_str;

94 }

95

96 int main()

97 {

98 const char * str_x = "abcabcabc";

99 const char * str_y = "cabcd";

100 const char * str_z = "abc";

101

102 int sub_str_pos [MAX_POS_NUM] = {0};

103

104 char * max_com_str = NULL;

105

106 char * replaced_str = NULL;

107

108 get_sub_str_pos(str_x,str_z,sub_str_pos);

109 max_com_str = get_max_com_str(str_x,str_y);

110

111 printf("max common str: %s\n",max_com_str);

112

113 replaced_str = replace_sub_str(str_x, max_com_str, sub_str_pos, strlen(str_z));

114 printf("repalced str: %s\n",replaced_str);

115

116 return 0;

117 }

关于数据结构c语言版源代码和数据结构C语言版的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。