算法与数据结构

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

题目：集合运算问题；

排序算法比较问题；

方程求解问题；

图的基本操作与实现；

目录。摘要 3

一。集合运算问题 4

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

2.算法设计 5

3.函数的调用关系图 5

4.调试分析 5

5.测试结果 6

6.源程序（带注释） 8

二。排序算法比较问题 13

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

2.算法设计 14

3.函数的调用关系图 15

4.调试分析 16

5.测试结果 16

6.源程序（带注释） 18

三。方程求解问题 27

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

2.算法设计 27

3.函数的调用关系 27

4.调试分析 27

5.测试结果 28

6.源程序（带注释） 28

四。图的基本操作与实现 31

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

2.算法设计 32

3.函数调用关系图 33

4.调试分析 33

5.测试结果 33

6.源程序(带注释) 35

总结 46参考文献 47

致谢 48此文档关于各种算法问题的求解，包括以下四大部分。

集合运算问题。实现两个集合的并集、交集、差集、显示输出等，要求结果集合中的元素不重复，实现一个集合的幂集的求解的问题，此程序通过输入两个链表存储两个集合各自的元素，通过操作链表实现两集合交集、并集和差集，通过遍历链表获取集合元素。

排序算法比较问题。比较各类排序算法效率的程序，程序能够将产生的随机数据同时用不同的内部排序算法排序，并且在同一界面中同时输出数据结果，通过随机的数据测试，直观的比较各算法的关键字比较次数和关键字移动次数的问题。

方程求解问题。使得方程a5+b5+c5+d5+e5=f5刚好有一个满足0≤a≤b≤c≤d≤e≤f≤75的整数解的问题，通过开始建立数组，用来存储整型abcdef五次方的值，然后利用for嵌套循环，一次求abcdef五次方的值，接下来用if判断语句，若abcde次方之和与f五次方的差为零，输出abcdef的整数解。

图的基本操作与实现的问题。图的基本操作与实现通过采用邻接表来存储无向图，无向图中有n个顶点e条边，使得邻接表得需要n个头结点和2e个表结点，顶点vi的度恰好为第j个链表中的表结点数。深度优先的非递归算法需要借助栈实现，对所有节点做未访问标记后起始节点入栈，使用while循环栈不为空时，栈顶顶点v出栈，如果顶点v未标记为已访问标记v为已访问，遍历顶点v的邻接点，如果邻接点u未被标记为已访问，则u入栈，如此循环完成深度优先遍历。

同理借助借助队列完成图的广度遍历。通过遍历邻接表中的表结点，确定邻接矩阵中的相应元素。对图深度优先遍历后，如果存在未被标记的顶点，说明图不是连通图，否则是连通。

关键词：集合，排序，复杂度，方程求解，图的操作及实现。

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

typedef struct lnode

char data；

struct lnode*next

*pointer

定义结构体指针类型，*pointer为结构指针类型。

有序表的抽象诗句类型定义为：

read data（pointer head）

初始条件：head是以head为头节点的空链表。

操作结果：生成以head为头结点的非空链表。

pop（pointer head）

初始条件：head是以head为头节点的非空链表。

操作结果：将以head为头结点的链表中数据逐个输出。

and（pointer head1，pointer head2，pointer head3）

初始条件：链表head1，head2，head3已存在。

操作结果：生成一个由head1和head2的并集构成的集合head3。

or（pointer head1，pointer head2，pointer head3）

初始条件：链表head1，head2，head3已存在。

操作结果：生成一个由head1和head2的并集构成的集合head3。

输入两个链表存储两个集合各自的元素，通过操作链表实现两集合交集、并集和差集，通过遍历链表获取集合元素。对于交集，遍历链表1和遍历链表2，相同元素放入链表3，遍历链表3输出元素；对于并集，遍历链表1中的元素放入遍历链表3，再把遍历链表2中不等于遍历链表1的元素放入遍历链表3，遍历链表3输出元素；差集的实现，通过遍历链表，将遍历链表1中不等于2的元素放入遍历链表3，遍历链表3输出差集。

1 算法时间复杂度为o（n^2）

2输完一组数据，以enter键继续。输入数组包括字母，数都可以，差集，并集，交集都会在同一界面同时输出。

图1.1集合运算图。

图1.2集合运算图。

图1.3集合运算图。

#include<>

typedef struct lnode //定义结构体指针类型。

char data;

struct lnode*next;

*pointer;

void readdata(pointer head)//定义输入集合函数。

pointer p;

char tmp;

scanf("%c",&tmp);

while(tmp!='n')

void pop(pointer head)//定义输出集合函数。

pointer p;

p=head->next;

while(p!=null)

printf("");

void or(pointer head1,pointer head2,pointer head3)//定义集合交集函数。

pointer p1,p2,p3;

p1=head1->next;

while(p1!=null)

p1=p1->next;

void and(pointer head1,pointer head2,pointer head3)//定义集合并集函数。

pointer p1,p2,p3;

p1=head1->next;

while(p1!=null)

p2=head2->next;

while(p2!=null)

p2=p2->next;

void differ(pointer head1,pointer head2,pointer head3) /定义集合差集函数。

pointer p1,p2,p3;

p1=head1->next;

while(p1!=null)

p1=p1->next;

/主函数。void main()

int x;

pointer head1,head2,head3;

head1=(pointer)malloc(sizeof(struct lnode));

head1->next=null;

head2=(pointer)malloc(sizeof(struct lnode));

head2->next=null;

head3=(pointer)malloc(sizeof(struct lnode));

head3->next=null;

printf("请输入以下两个集合");

printf("请输入第一个集合：")

readdata(head1);

printf("请输入第二个集合：")

readdata(head2);

printf("交集集合为：")

or(head1,head2,head3);

pop(head3);

head3->next=null;

printf("并集集合为：")

and(head1,head2,head3);

pop(head3);

head3->next=null;

printf("差集集集合为：")

differ(head1,head2,head3);

pop(head3);

head3->next=null;

算法与数据结构

数据结构与算法

算法与数据结构

算法与数据结构

其他用户还读了