郑杭的数据结构课程设计论文.docx

郑杭的数据结构课程设计论文.docx

《郑杭的数据结构课程设计论文.docx》由会员分享，可在线阅读，更多相关《郑杭的数据结构课程设计论文.docx（19页珍藏版）》请在冰点文库上搜索。

郑杭的数据结构课程设计论文

辽宁工业大学

数据结构课程设计（论文）

院（系）：

电子与信息工程学院

专业班级：

计算机101

学号：

100401018

学生姓名：

郑杭

指导教师：

罗颖

教师职称：

讲师

起止时间：

2012.1.2—2012.1.6

课程设计（论文）任务及评语

院（系）：

电子与信息工程学院教研室：

软件工程

学号

100401018

学生姓名

郑杭

专业班级

计算机101

课程设计（论文）题目

课程设计（论文）任务

1.了解并掌握数据结构的设计方法,具备初步的独立分析和设计能力；

共五类题目，要求从前四类题目中任选其一，共计完成四个题目。

或选择第五类题目中的一个即可。

2.每个题目编写源程序时，每个子功能定义为相应的子函数，在主函数中调用各子函数，要求程序结构清晰。

3.数据的存储结构根据需要自行定义。

4.测试数据：

包括正确的输入及其输出结果和含有错误的输入及其输出结果。

5.分析算法的时间复杂度，要求算法的效率尽可能高。

6.将所选题目封装在一个主函数中。

指导教师评语及成绩

成绩：

指导教师签字：

学生签字：

郑杭

年月日

目录

第一章．程序设计0

1.1求最短路径1

1.2求最小生成树2

1.3快速排序5

1.4顺序栈实现基本操作9

．参考文献12

第一章．程序设计

1.1求最短路径

设G=（V,E）是一个每条边都有非负长度的有向图，有一个特异的顶点s称为缘。

单源最短路径问题，或者称为最短路径问题，是要确定从s到V中没一个其他

顶点的距离，这里从顶点s到x的距离定义为从s到x的最短路径问题。

这个问题

可以用Dijkstra算法解决。

#include

voidmain（）

{

intinfinity=100,j,i,n,k,t,**w,*s,*p,*d;

cout<<"inputthevalueofn:

";

cin>>n;

cout<

d=newint[n];

s=newint[n];

p=newint[n];

w=newint*[n];

for（i=0;i

for（i=0;i

for（j=0;j

cin>>w[i][j];

for（s[0]=1,i=1;i

{

s[i]=0;d[i]=w[0][i];

if（d[i]

elsep[i]=-1;

}

for（i=1;i

{

t=infinity;k=1;

for（j=1;j

if（（!

s[j]）&&（d[j]

s[k]=1;//pointkjointheS

for（j=1;j

if（（!

s[j]）&&（d[j]>d[k]+w[k][j]））

{d[j]=d[k]+w[k][j];p[j]=k;}

}

cout<<"从源点到其它顶点的最短距离依次如下：

";

for（i=1;i

}

/*********

顶点个数用n表示，这里给出的例子n=6

100112100100100

10010093100100

1001001001005100

10010041001315

1001001001001004

100100100100100100

结果：

1.2求最小生成树

1、基本思想：

设无向连通网为G＝（V,E），令G的最小生成树为T＝（U,TE），其初态为U＝V，TE＝{}，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。

若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。

2、示例：

3、代码实现如下：

viewplain

·········10········20········30········40········50········60········70········80········90········100·······110·······120·······130·······140·······150

程序如下

#include"stdio.h"

#include"stdlib.h"

structedge

{

intm;

intn;

intd;

}a[5010];

intcmp（constvoid*a,constvoid*b）//按升序排列

{

return（（structedge*）a）->d>（（structedge*）b）->d;}

intmain（void）

{

inti,n,t,num,min,k,g,x[100];

printf（"请输入顶点的个数：

"）;

scanf（"%d",&n）;

t=n*（n-1）/2;

for（i=1;i<=n;i++）

x[i]=i;

printf（"请输入每条边的起始端点、权值：

/n"）;

for（i=0;i

scanf（"%d%d%d",&a[i].m,&a[i].n,&a[i].d）;//输入每条边的权值

qsort（a,t,sizeof（a[0]）,cmp）;

min=num=0;

for（i=0;i

{

for（k=a[i].m;x[k]!

=k;k=x[k]）//判断线段的起始点所在的集合

x[k]=x[x[k]];

for（g=a[i].n;x[g]!

=g;g=x[g]）//判断线段的终点所在的集合

x[g]=x[x[g]];

if（k!

=g）//如果线段的两个端点所在的集合不一样

{

x[g]=k;

min+=a[i].d;

num++;

printf（"最小生成树中加入边：

%d%d/n",a[i].m,a[i].n）;

}

}

printf（"最小生成树的权值为：

%d/n",min）;

system（"pause"）;

return0;

}

结果：

1.3快速排序

流程图

#include

#defineMAX100

#defineOK1

#defineERROR0

#defineElemtypeint

#defineStatusint

typedefstruct{

Elemtypem[MAX];

intlength;

}sqlist;

Statuscreate（sqlist&L,intn）

{

for（inti=1;i<=n;i++）

cin>>L.m[i];

L.length=n;

returnOK;

}

StatusPartition（sqlist&L,intlow,inthigh）

{

intpivotkey=L.m[low];

L.m[0]=L.m[low];

while（low

{

while（low=pivotkey）

--high;

L.m[low]=L.m[high];

while（low

++low;

L.m[high]=L.m[low];

}

L.m[low]=L.m[0];

returnlow;

}

Statusquicksort（sqlist&L,intlow,inthigh）

{

if（low

{intpivotloc;

pivotloc=Partition（L,low,high）;

quicksort（L,low,pivotloc-1）;

quicksort（L,pivotloc+1,high）;

}

returnOK;

}//quicksort

voidprintlist（sqlistL）

{

for（intk=1;k<=L.length;k++）

cout<

cout<

}

intmain（）

{

sqlistS;

intx;

inttag=1;

cout<<"请输入表长:

"<

cin>>x;

cout<<"请输入表元:

"<

create（S,x）;

cout<<"输入序列为:

"<

printlist（S）;

quicksort（S,1,S.length）;

cout<<"排序后:

"<

printlist（S）;

returnOK;

}

结果：

1.4顺序栈实现基本操作

#include

usingnamespacestd;

#defineSTACK_INIT_SIZE100

#defineSTACKINCREMENT10

template

classStack

{

public:

Stack（）;

~Stack（）;

voidPush（Te）;

voidPop（）;

TGetTop（）;

intStackLength（）;

voidClearStack（）;

boolIsEmpty（）;

private:

T*base;

T*top;

intstacksize;

};

//Constructor

template

Stack:

:

Stack（）

{

base=newT[STACK_INIT_SIZE*sizeof（T）];

//base=（T*）malloc（STACK_INIT_SIZE*sizeof（T））;

if（!

base）//Memoryallocationfailed

{

exit

（1）;

}

top=base;

stacksize=STACK_INIT_SIZE;

}

//Destructor

template

Stack:

:

~Stack（）

{

deletebase;

//free（S->base）;//释放内存-与malloc成对

base=NULL;//释放指针变量

top=NULL;

stacksize=0;

}

//PushStack

template

voidStack:

:

Push（Te）//Insertelementeasthenewtopelement

{

//Stackisfullandreallocmemory

if（top-base>=stacksize）

{

base=（T*）realloc（base,（stacksize+STACKINCREMENT）*sizeof（T））;

if（!

base）

{

exit

（1）;

}

top=base+stacksize;

stacksize+=STACKINCREMENT;

}

*top++=e;

}

//PopStack

template

voidStack:

:

Pop（）

{

if（base==top）

{

exit

（1）;

}

Te=*--top;

}

//GetthetopelementofStackS

template

TStack:

:

GetTop（）

{

if（base==top）

{

exit

（1）;

}

Te=*（top-1）;

returne;

}

//Getthestacklength

template

intStack:

:

StackLength（）

{

/*inti=0;

T*t=top;

while（t!

=base）

{

t--;

i++;

}

returni;*/

returntop-base;

}

//ClearStack

template

voidStack:

:

ClearStack（）

{

top=base;

}

//JudgestackEmptyornot

template

boolStack:

:

IsEmpty（）

{

if（base==top）

{

returntrue;

}

else

{

returnfalse;

}

}

intmain（）

{

Stackstack;

for（inti=0;i<9;i++）

{

stack.Push（i）;

}

cout<

cout<

stack.Pop（）;

cout<

cout<

return0;

}

结果：

．参考文献

[1]《C++程序设计》，清华大学出版社

[2]数据结构（用面向对象方法与C++语言描述）（第二版）清华大学出版社

[3]数据结构（C++版）--习题解答及实习指导中国水利水电出版社