《数据结构课程设计》报告

题目集合运算

专业计算机科学与技术

班级。学生。

题目。集合运算。

题目内容。问题一：子集求和问题。

有一集合中有 n 个元素，每个元素均为自然数。给定任意一个 m，求满足子集中各元素之和等于m的所有子集。

问题二：求最小元素。

问题描述：1 1 是集合的元素；

若 p 是集合的元素，则 2*p+1，4*p+5 也是集合的元素。

求：此集合中最小的 k 个元素。

1 本人完成的工作

1．编写集合输出函数out。

2．编写一个集合创建函数great_set，自行输入元素，没有重复元素，并输出集合元素。

3．编写函数output输出满足集合中各元素之和为m的集合的所有子集。

4．编写函数all_subset，输出集合中所有小于m的元素所组成的所有子集。

5．编写函数select_element，筛选集合中小于或等于m的元素，并输出。

6．编写gather函数，输出集合中满足条件的k个元素。

7．编写函数disy()，调用gather实现第二问的功能。

8．编写主函数main，并通过函数调用，实现所有功能。

2 所采用的数据结构单链表。

typedef struct stud

int a集合元素。

struct stud *next; /指向下一个结点的指针。

stud;

3 所设计的函数。

1.集合输出函数。

算法思想：从单链表的头指针之后的第一个结点开始取数据并输出，若第一个结点为空，输出集合为空集。

2、集合创建函数。

算法思想：开始输入ｎ作为生成的集合的元素个数，当ｎ＞１时，输入数据过大，重新输入。当n≤100时，开始输入集合元素，第一个数据元素存入链表，当新输入的数据和刚刚输入的数据相等时显示已经输入，重新输入；不相等时，存入链表，当输入元素个数为n时，结束输入，调用out（），输出你刚刚输入的集合。

3.输出满足集合中各元素之和为m的集合的函数。

算法思想：当used[j]=1时相加，求出子集所以元素之和count，然后再与输入的和m比较，如果count=m，就把子集的元素输出，如果count！=m，此次循环结束。

4.函数all_subset，输出集合中所有小于m的元素所组成的所有子集。

算法思想：n个数，每个数取或不取，f(判断第j个数)

若n个数都判断完(j>=n)，输出刚才所取的数，返回。

否则：不取第j个数，f(判断第j+1个数)

取第i个数，f(判断第j+1个数)

5.编写函数select_element，筛选集合中小于或等于m的元素，并输出。

算法思想：先判断ｐ是不是尾结点，若不是的再比较ｐ－＞与ｍ的大小，把比ｍ小的元素存到数组ａ［i］中，当p=null是，输出比m小的元素组成的集合ｑ，再调用all_subset函数，求ｑ的子集。

6.编写gather函数，输出集合中满足条件的k个元素。

算法思想：因为这是个无穷集，不可能将所有结果都表示出来，但通过观察我们知道，想要得到最小的k个元素，只要知道最多2的k次方减去1个元素就行了。在这个部分集里，我们就可以找到符合条件的元素。

初始时i=0，j=0，当j小于k时，j++。由1开始生成集合，集合的个数为2的k次方。当j=k时，说明已经将k层的每个元素都放到了数组中，在这个for循环里，就是将已经建立的数组进行排序，便于输出。

7.编写函数disy()，调用gather实现第二小题的功能。

算法思想：首先输入一个k值，就是要输出的元素个数，调用malloc，根据k值开辟空间，调用gather（），输出集合k个最小元素。

8.编写主函数main，并通过函数调用，实现所有功能。

算法思想：调用函数creat，创建集合，并输出。输入给定的和m，调用select_element（），计算并输出所有满足条件的自己的元素。

运行结果：第一小题。

第二小题。问题与总结。

问题：1、在做第一问时，求n个元素的集合中小于给定的m的元素所组成的集合的全部子集，时算法一时间没有想出来。问了同学才能写出算法。

2、第二问时，由于由1生成元素所组成的集合元素个数是无限，要取其中一部分就可以了，前面k个最小的元素，最多用到第k层，就可以了。

总结：通过这次数据结构课程设计，使我对函数的调用比较深刻的了解，对集合数组和链表的使用有了清晰的认识，使我感觉到到，一个优秀的软件，不仅仅是可以运行的，协调的布局，合理的结构，良好的性能和一定的容错性。一个人要完成所有的工作是非常困难和耗时的。

源程序：#include<>

#include<>

#define max_size 100

int * list,i=0,j=0,k=0,s=0;

typedef struct stud

int a集合元素。

struct stud *next; /指向下一个结点的指针。

stud;

问题一集合结点的定义。

int a[max_size用来存放小于m的元素。

int used[max_size]; 存放标志位的数组。

void out(stud *g集合的输出。

stud *p;

p=g->next;

while(p!=null)

printf("");

void great_set(stud *g) /集合的创建。

stud *p,*q,*pr;

int n,i,k;

p=g;int a=1;

while(a=1)

for(i=1;i<=n;i++)

if(pr==null如果输入的自然数与集合中原有数据不相同。

out(g);

void output(int a[max_size],int i,int m) /满足集合中各元素之和为m的所有子集。

int j,count=0;

for(j=0;j

if(count==m) /满足和为m的子集输出。

printf("");

void all_subset(int a[max_size],int j,int i,int m)//所有小于m的元素组成的子集。

if(j>=i)

output(a,i,m);

elsevoid select_element(stud *g,int m) /筛选出不大于m的元素。

stud *p;

int i=0,k,j=0;

p=g->next;

while(p!=null)

p=p->next;

printf("小于等于%d的数的集合",m);

for(k=0;k printf("%d,",a[k]);

printf("");

printf("满足集合各元素之和为%d的子集如下：",m);

all_subset(a,j,i,m);

void gather(){

i+=(int)pow(2,j);/pow(x,y)是一个数学函数，结果是x的y次方。

j++;if(j==k){

int temp=0;

for(i=0;i {

for(j=i;j

if(list[i]>list[j])

《数据结构课程设计》报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了