算法与数据结构

数据结构与算法课程设计。

题目：集合运算问题；排序算法比较问题；跳马问题；构造可以使n个城市连接的最小生成树

目录。摘要 4

一．集合运算问题 5

1.采用类语言定义相关的数据类型 5

2.算法设计 5

3.函数的调用关系图 6

4.调试分析 6

5.测试结果 7

6. 源程序（带注释） 7

二．算法排序比较问题 13

1.采用类语言定义相关的数据类型 13

2.算法设计 13

3.函数的调用关系图 15

4.调试分析 16

5.测试结果 16

6.源程序（带注释） 18

三．跳马问题 23

1.数据结构设计 23

2.算法设计 23

3．函数的调用关系图 25

4.调试分析 26

6.源程序（带注释） 27

四．构造可以使n个城市连接的最小生成树 30

1.数据结构设计 30

2.算法设计 30

3.函数的调用关系图 32

4.调试分析 32

5.测试结果 33

6.源程序（带注释） 34

总结 46参考文献 47

致谢 47设计一个程序，实现两个集合的并集、交集、差集、显示输出等，要求结果集合中的元素不重复；实现一个集合的幂集的求解。用线性表对两个集合进行存储，然后进行比较，判断两个线性表中的元素，对其进行交集，并集，补集的运算，将其保存到第三个线性表中并进行输出以达到算法的目的。排序算法比较问题。

设计各类排序算法的程序，通过随机的数据测试，比较各算法的关键字比较次数和关键字移动次数。写出各种常见算法，用一组随机数进行测试比较。跳马问题是要求在64个国际象棋格子，任意位置放一个马，如何不重复地把格子走完。

能够想到的思路是用回溯，马在每一个点最多有8种跳法，遍历所有这8种可能的跳法即可得到结果。本设计的主要工作是用c语言来实现跳马问题。给定一个地区的n个城市间的距离网，用prim算法或kruskal算法建立最小生成树，并计算得到的最小生成树的代价。

其要求是，城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价；表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)；最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。对这些问题都进行相关的算法设计来解决这些问题。

关键词：集合运算，栈，队列，跳马，最小生成树，算法。

一．集合运算问题。

设计一个程序，实现两个集合的并集、交集、差集、显示输出等，要求结果集合中的元素不重复；实现一个集合的幂集的求解。

定义一个结构体存储结构，用来生成求幂集的二叉树只在求幂集函数内使用。

typedef struct根节点结构体（幂集使用）

int data[max];

int length;

root;

定义一个二维数组，用来存储节点选择情况，其第一个下标表示是左孩子还是右孩子，第二个表示节点当前所处的层数。

int c[2][maxc构造数据池。

程序执行的命令包括：

定义单链表结点类型typedef struct lnode

2)运用尾插法建立单链表void creatlistr（linklist *&l,elemtype a,int n）

3)创建头结点，为头结点分配空间

4)创建新结点。

5)建立有序链表void sort（linklist *&head）

6)将两个集合的元素进行比较 while语句

7)删除有序链表中的重复元素void shanchu(linklist *&head)

8)求交集void jiao（struct lnode **l1，struct lnode **l2，struct lnode **l3）

9)求并集void bing（struct lnode **l1，struct lnode **l2， struct lnode **l3）

10)输出单链表void display（linklist *l）

a、输入集合数据的时候必须要一个一个输，不能依次输入很多，否则会引起错误。

b、算法的时间复杂度o(n^2）。

图(1)集合运算。

#include<>

typedef struct node

char data; /定义了数据域，这里存储的是char类型*/

struct node*next; /定义了指针域*/

*linklist;

/创建链表。

void readdata(linklist head)

linklist p;

char a;

scanf("%c",&a);

while(a!='n')

p=(linklist)malloc(sizeof(struct node));

p->data=a;

p->next=head->next;

head->next=p;

scanf("%c",&a);

/遍历链表。

void pop(linklist head)

linklist p;

p=head->next;

while(p!=null)

printf("%c",p->data);

p=p->next;

printf("");

***求两个链表的并集***

void bingji(linklist head1,linklist head2,linklist head3)

linklist p1,p2,p3;

p1=head1->next;

while(p1!=null)

p2=head2->next;

while((p2!=null)&&p2->data!=p1->data))

p2=p2->nextp1！=p2 链表2后移。

if((p2!=null)&&p2->data==p1->data))

p3=(linklist)malloc(sizeof(struct node));

p3->data=p1->datap1=p2的值赋给p3

p3->next=head3->next;

head3->next=p3p3链表连接到head3

p1=p1->next; }

***求两个链表的交集***

void jiaoji(linklist head1,linklist head2,linklist head3)

linklist p1,p2,p3;

p1=head1->next;

/链表1中的数放入链3

while(p1!=null)

p3=(linklist)malloc(sizeof(struct node));

p3->data=p1->data;

p3->next=head3->next;

head3->next=p3;

p1=p1->next;

/链2的！=链1时，此链2节点加入链3

p2=head2->next;

while(p2!=null)

p1=head1->next;

while((p1!=null)&&p1->data!=p2->data))

p1=p1->next;

if (p1==null)

p3=(linklist)malloc(sizeof(struct node));

p3->data=p2->data;

p3->next=head3->next;

head3->next=p3; }

p2=p2->next;

***求两个链表的差集。

void chaji(linklist head1,linklist head2,linklist head3)

linklist p1,p2,p3;

p1=head1->next;

while(p1!=null) /循环语句执行链表的差集运算。

p2=head2->next;

while((p2!=null)&&p2->data!=p1->data))

p2=p2->next;

if(p2==null)

p3=(linklist)malloc(sizeof(struct node));

p3->data=p1->data;

p3->next=head3->next;

head3->next=p3;

p1=p1->next;

void main(linklist head1,linklist head2,linklist head3)

int x;

printf("input values and end up with ‘enter’ ");

算法与数据结构

数据结构与算法

算法与数据结构

算法与数据结构

其他用户还读了