算法与数据结构课程设计说明书

目 录

摘 要 ........................................................... 3 一． 求素数问题 .................................................. 4 1.1 问题描述 ................................................... 4 1.2采用类语言定义相关的数据类型 ................................ 4 1.3算法设计 .................................................... 4 1.4函数的调用关系图 ............................................ 4 1.5调试分析 .................................................... 5 1.6测试结果 .................................................... 5 1.7源程序（带注释） ............................................ 7 二、数据删除问题 ................................................. 8 2.1 问题描述 ................................................... 8 2.2算法设计 .................................................... 8 2.3程序调试情况： ............................................. 10 2.4源程序 ..................................................... 10 三、通过课程选修问题 ............................................ 11 3.1数据结构设计 ............................................... 11 3.2算法设计 ................................................... 12 3.3调试分析 ................................................... 14 3.4测试结果 ................................................... 14 3.5源程序（带注释） ........................................... 15 四、排序重构问题 ................................................ 25 4.1问题说明 ................................................... 25 4.2数据结构设计 ............................................... 26 4.3算法设计 ................................................... 26 4.4流程图如下： ............................................... 27 4.5调试分析 ................................................... 27

4.6测试结果 ................................................... 27 4.7 源程序（带注释） .......................................... 28 总 结 .......................................................... 32 参考文献 ........................................................ 33 致 谢 .......................................................... 34

摘 要

第一个程序为求解素数问题在求解过程中运用埃拉托色尼筛法求所有小于N的素数的方法。从建立一个整数2~N的线性表寻找i?错误！未找到引用源。的整数 第二个程序为求解数据删除问题，编写删除具有N个数据项的数组A中所有重复项的程序，返回A中仍有的数据项。对于设计程序的思路，可以从数据类型入手，如果是整型（也包括但字符），可以使用排序法，然后，输出的重复的就删去，如果是正整数，可以直接构造一个数组：int a[]={0};//全部初始化为0，然后一个一个地读入，假设读入n，则令a[n]=1表示n存在，那么下一个读入的n则与a[n]判断，如果a[n]是1，则跳过。输出时，只需要挨个判断a[]中的a[n]了，如果是1，输出n。

课程选修问题。学生需要修一定数量的课程才能毕业，而这些课程会有一些必须遵循的选修顺序。假设每个学期都开所有课程，并且学生所修课程数量不限制。给出课程和先修课程的列表，求出一个满足最小学期数要求的时间表。以你的专业情况为背景设计。

第四道为排序重构问题。具体要求是由题目给出的一个顺序序列按照题目给定的相关计算方法得到新的序列，然后对计算方法进行逆推得到新的顺序序列，由于计算方法我们得到的序列并不唯一。

关键词： 素数 数据删除 排序重构 埃拉托色尼筛法 选修顺序

3

一． 求素数问题

1.1 问题描述

埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于N的素数的方法。从建立一个整数2~N的表着手，寻找i?错误！未找到引用源。的整数，编程实现此算法，并讨论运算时间。

1.2采用类语言定义相关的数据类型

定义一个线性表顺序存储结构，用来求所有小于N的素数 typedef int DataType;//数据类型 typedef struct{

DataType data[maxsize]; 定义一个一维数组 int length;//线性表中实际元素的个数 }Seqlist;

1.3算法设计

用一个循环结构判断是否为素数，如果是素数则返回1，否则返回0。 int sushu(DataType &i) { int m; if(i==1) return 0; for(m=2;m

if(i%m==0)

return 0; }return 1；}

1.4函数的调用关系图

4

主函数 sushu

图1.1调用关系图

1.5调试分析

1 当m的值大于maxsize的值是发生越界问题，在输入m时要确保m的值要小于maxsize的值。开始界面如图所示。

图1.2开始界面

2 算法的时间复杂度O(L.length-1)+O(m)。

1.6测试结果

1 图1为输出2~200内的数

图1.3 2~200内所有的数

5

2图2为当m=150时，输出1~150之间的素数，结果如图所示。

图1.4 1~150之间的素数运行结果

3 图3为m大于L.length时的图

图1.5大于L.lenggth

1.7源程序（带注释）

#include #include #define maxsize 200 #define FALSE 0 typedef int DataType; typedef struct { DataType data[maxsize]; int length; }Seqlist;//结点结构

int sushu(DataType i)//判断是否为素数 {

int m; f(i==1) return 0;

6

for(m=2;m

int main() { Seqlist L; int m,j; int i,k=0; L.length=maxsize; for(j=2;j<=L.length ;j++) { L.data[j-1]=j; printf(\ } printf(\ printf(\ scanf(\ if(m>L.length ) return FALSE; printf(\至m之间的素数从小到大分别为:\\n\ for(i=1;i<=m ;i++) L.data[i-1]=i; for(i=1;i<=m;i++) if(sushu(L.data[i-1])) { k++; printf(\符号\的作用是横向制表。 } printf(\总共%d个。\\n\ return 0; }

二、数据删除问题

2.1 问题描述

编写删除具有N个数据项的数组A中所有重复项的程序，返回A中仍有的数据项。要求运行时间在O（NlogN）。（例如：

数组a的初始数据为：2,5,2,4,20,0,4,-5,-5,16,2,-4,20。 升序排序后为： -5,-5,-4,0,2,2,2,4,4,5,16,20,20。

7

删除重复数据后为： -5,-4,0,2,4,5,16,20

2.2算法设计

(1)定义一个数组a[10],用循环实现排序 for(i=0;i<10;i++) {

for(j=i+1;j<10;j++) {

if(a[i]>a[j]) {

t=a[i]; a[i]=a[j]; a[j]=t;

用直接覆盖法删除重复数据 for(j=i+1;j<9;j++) a[j]=a[j+1];

(2)程序流程图

数据删除问题程序流程图 理的输入所要处 数组，进行编译预 处理 进行排序（冒泡排序） 8

利用正则遍历， 将数组中重复的 数据分离出来， 用于单独处理 在遍历过程中，将相 同的分别数据保留 一个，并继续遍历 输出处理后的新数组 若没有数据相同，则跳过此阶段 图2.1数据删除流程图

9

2.3程序调试情况：

1数据删除问题：当输入1 2 2 2 3 3 3 2 1 3 时，删除重复数据，输出结果如图所示。

图2.2数据删除图

2.4源程序

#include main()

{ int i,j,t; int a[10];

printf(\请输入10个数:\\n\

for(i=0;i<10;i++) //输入 scanf(\

printf(\输入的10个数是：\ for(i=0;i<10;i++) printf(\ printf(\

for(i=0;i<10;i++) //排序 {

for(j=i+1;j<10;j++) {

if(a[i]>a[j]) {

t=a[i]; a[i]=a[j]; a[j]=t; } }

10

}

printf(\个数排序后是：\ for(i=0;i<10;i++) {

printf(\ }

printf(\

for(i=0;i<9;i++) //删除重复数字 {

if(a[i]==a[i+1]) //如果后一个数等于前一个数，就把后一个数删掉（ps:这里已经排过序，所以可以这样做来删除重复数字） {

for(j=i+1;j<9;j++) //这里的删除用的直接覆盖 a[j]=a[j+1]; } }

printf(\删除重复数字后：\ for(i=0;i<10;i++) {

if(i>0&&a[i-1]==a[i]) //只输出前面不重复的数 break;

printf(\ }

printf(\}

三、通过课程选修问题

学生需要修一定数量的课程才能毕业，而这些课程会有一些必须遵循的选修顺序。假设每个学期都开所有课程，并且学生所修课程数量不限制。给出课程和先修课程的列表，求出一个满足最小学期数要求的时间表。以你的专业情况为背景设计。

3.1数据结构设计

typedef struct subjects {

int num; //课程编号 char name[20]; //课程名称 char kind[10]; //课程性质 int stime; //总学时 int ttime; //授课学时

11

int etime; //实验或上机学时 int score; //学分 int term; //开课学期 struct subjects *next; }SUB;

3.2算法设计

1.SUB *create_form() //创建链表 while(num!=0) {

p=(SUB *)malloc(size); p->num=num;

strcpy(p->name,name); strcpy(p->kind,kind); p->stime=stime; p->ttime=ttime; p->etime=etime; p->score=score; p->term=term; if(head==NULL) head=p; else

tail->next=p; if(fp==NULL)exit(0); tail=p;

void savefile() //保存文件

for(p=head;p;p=p->next)

fprintf(fp,\

p->num,p->name,p->kind,p->stime,p->ttime,p->etime,p->score,p->term); fclose(fp);

printf(\创建后的信息已放入'3.txt'文件中\\n\ system(\

void readfile() //阅读文件 while(!feof(fp)) {

newSub=(SUB*)malloc(sizeof(SUB));

fscanf(fp,\nd,

&newSub->stime,&newSub->ttime,&newSub->etime,&newSub->score,&newSub->term);

myInsert(newSub); }

fclose(fp)

12

void *insert()//插入课程信息 {

while(ch!='0') {

subj=(SUB *)malloc(size); ptr=subj;

void search() //课程信息查询for(ptr=head;ptr;ptr=ptr->next) if(ptr->score==num) {

printf(\

ptr->kind,ptr->stime,ptr->ttime,ptr->etime,ptr->score,ptr->term); t=0; }

if(t)

printf(\未找到!\\n\ t=1;

system(\ goto L1; case 3:break; }

2主函数main()函数设计地比较简洁，只是提供一个主菜单，switch语句将整个程序分为两个大的功能模块：

进入下一层 选择序号进行选课 进入选课系统

图3.1删除流程图

13

3.3调试分析

1 开始运行

图3.2开始运行界面

2 管理员菜单

图3.3菜单

按1进人录入课程模块

3.4测试结果

图3.4测试结果

14

图3.5运行结果

3.5源程序（带注释）

#include \#include \#include \#include \void prin1(); void choose();

typedef struct subjects {

int num; //课程编号 char name[20]; //课程名称 char kind[10]; //课程性质 int stime; //总学时 int ttime; //授课学时

int etime; //实验或上机学时 int score; //学分 int term; //开课学期 struct subjects *next; }SUB;

SUB *head=NULL;

SUB *create_form() //创建链表 {

SUB *head,*tail,*p; int num,stime,ttime; int etime,score,term; char name[20],kind[10]; int size=sizeof(SUB); head=tail=NULL;

printf(\输入选修课程信息:\\n\

scanf(\

15

&stime,&ttime,&etime,&score,&term); while(num!=0) {

p=(SUB *)malloc(size); p->num=num;

strcpy(p->name,name); strcpy(p->kind,kind); p->stime=stime; p->ttime=ttime; p->etime=etime; p->score=score; p->term=term; if(head==NULL) head=p; else

tail->next=p; tail=p;

scanf(\

kind,&stime,&ttime,&etime,&score,&term); }

tail->next=NULL; return head; }

void savefile() //保存文件 {

SUB *p; FILE *fp;

fp=fopen(\ if(fp==NULL)exit(0);

printf(\课程编号 课程名称 课程性质 总学时 授课学时 实验或上机学时 学分 开课学期\\n\ for(p=head;p;p=p->next)

fprintf(fp,\

p->num,p->name,p->kind,p->stime,p->ttime,p->etime,p->score,p->term); fclose(fp);

printf(\创建后的信息已放入'2.txt'文件中\\n\ system(\}

void savefile1() //保存文件 {

SUB *p; FILE *fp;

fp=fopen(\

16

if(fp==NULL)exit(0); for(p=head;p;p=p->next)

fprintf(fp,\

p->num,p->name,p->kind,p->stime,p->ttime,p->etime,p->score,p->term); fclose(fp);

printf(\创建后的信息已放入'3.txt'文件中\\n\ system(\}

void readfile() //阅读文件 {

void *myInsert(SUB*); SUB *newSub; //新课程 int num,stime,ttime,etime; int score,term;

char cname[20],kind[10],fname[20]; FILE *fp;

fp=fopen(\ while(!feof(fp)) {

newSub=(SUB*)malloc(sizeof(SUB));

fscanf(fp,\nd,

&newSub->stime,&newSub->ttime,&newSub->etime,&newSub->score,&newSub->term);

myInsert(newSub); }

fclose(fp); }

void prin() //浏览所有课程 {

SUB *ptr; head=NULL; readfile(); if(head==NULL) {

printf(\ return; }

printf(\课程编号 课程名称 课程性质 总学时 授课学时 实践或上机学时 学分 开课学期\\n\

for(ptr=head;ptr;ptr=ptr->next)

17

{

printf(\

ptr->kind,ptr->stime,ptr->ttime,ptr->etime,ptr->score,ptr->term); }

system(\}

void prin1() //浏览所有选修课程 {

SUB *ptr; FILE *fp;

if((fp=fopen(\ {

printf(\ choose(); }

printf(\课程编号 课程名称 课程性质 总学时 授课学时 实践或上机学时 学分 开课学期\ printf(\ while(!feof(fp)) {

ptr=(SUB*)malloc(sizeof(SUB));

fscanf(fp,\

&ptr->stime,&ptr->ttime,&ptr->etime,&ptr->score,&ptr->term);

printf(\

ptr->kind,ptr->stime,ptr->ttime,ptr->etime,ptr->score,ptr->term); }

fclose(fp);

system(\}

void *myInsert( SUB *subj) //链表插入操作 {

SUB *ptr,*ptr2; ptr=subj;

if(head==NULL) {

head=ptr;

head->next=NULL; } else {

for(ptr2=head;ptr2;ptr2=ptr2->next)

18

if(ptr2->next==NULL) {

ptr2->next=subj; subj->next=NULL; break; } }

return head; }

void *insert()//插入课程信息 {

SUB *ptr,*subj;

int size=sizeof(SUB); char ch,ch1; while(ch!='0') {

subj=(SUB *)malloc(size); ptr=subj;

printf(\输入要插入的课程信息:\\n\

printf(\请输入课程编号:\ printf(\请输入课程名称:\ printf(\请输入课程性质:\ printf(\请输入总学时:\ printf(\请输入授课学时:\

printf(\请输入实践或上机学时:\ printf(\请输入学分:\ printf(\请输入开课学期:\ myInsert(subj);

printf(\添加完毕,新信息存入文件中\\n\ printf(\继续插入请按回车\\n\

printf(\结束添加课程按 0: [ ]\\b\\b\

ch1=getchar(); //将回车键赋给CH1,否则subj->term输完后输入的回车键会赋给CH,因此用CH1填补。 ch=getchar(); }

return head; }

void *del() //删除课程 {

SUB *p1,*p2; char ch,ch1; int num;

while(ch!='0') {

19

printf(\输入想要删除的课程编号:[ ]\\b\\b\\b\\b\\b\ scanf(\ if(head->num==num) {

p2=head;

head=head->next; free(p2); }

if(head==NULL) return NULL; p1=head;

p2=head->next; while(p2) {

if(p2->num==num) {

p1->next=p2->next; free(p2); } else

p1=p2; p2=p1->next; }

printf(\继续删除请按回车\\n\

printf(\结束删除课程按 0: [ ]\\b\\b\

ch1=getchar(); //将回车键赋给CH1,否则num输完后再输入的回车键会赋给CH,因此用CH1填补。 ch=getchar();

printf(\删除完毕,新信息存入文件中\\n\ system(\ }

return head;

system(\}

void choose()//选新课程--学生选课函数 {

SUB *p,*q; int a[5];

int num,total=0,i=0,j;

printf(\输入要选修的课程的编号,编号之间以空格分开\\n\ scanf(\

printf(\如果确认输入完要选修的课程的编号,请输入0: [ ]\\b\\b\ while(num!=0) {

20

for(p=head;p;p=p->next) if(p->num==num) {

total=total+p->score; a[i]=num; i++; }

scanf(\ }

if(total<60) {

printf(\选修总学分为%d,未达到60,选修失败!\\n\ system(\ } else {

FILE *fp;

fp=fopen(\ for(j=0;j

for(q=head;q;q=q->next) if(q->num==a[j])

fprintf(fp,\

q->name,q->kind,q->stime,q->ttime,q->etime,q->score,q->term); fclose(fp);

printf(\选修成功!****\\n\

printf(\您选修的课程总学分为%d,课程分别为:\\n\ printf(\课程编号 课程名称 课程性质 总学时 授课学时 实践或上机学时 学分 开课学期\\n\ for(j=0;j

for(q=head;q;q=q->next) if(q->num==a[j])

printf(\

q->num,q->name,q->kind,q->stime,q->ttime,q->etime,q->score,q->term); printf(\以上信息全部保存在'3.txt'中\\n\ }

system(\}

void search() //课程信息查询 {

int a,num; int t=1;

char type[10];

21

SUB *ptr;

L1:system(\

printf(\请选择查询方式*************\\n\ printf(\按课程性质查找\\n\ printf(\按学分查找\\n\ printf(\退出查找\\n\

printf(\ printf(\ scanf(\ switch(a) {

case 1:printf(\请输入要查找的课程的性质:\ scanf(\

printf(\课程编号 课程名称 课程性质 总学时 授课学时 实践或上机学时 学分 开课学期\\n\

for(ptr=head;ptr;ptr=ptr->next) if(strcmp(type,ptr->kind)==0) {

printf(\

ptr->name,ptr->kind,ptr->stime,ptr->ttime,ptr->etime,ptr->score,ptr->term);

t=0; }

if(t)

printf(\未找到!\\n\ t=1;

system(\ goto L1;

case 2:printf(\输入要查找的课程的学分:\ scanf(\

printf(\课程编号 课程名称 课程性质 总学时 授课学时 实践或上机学时 学分 开课学期\\n\

for(ptr=head;ptr;ptr=ptr->next) if(ptr->score==num) {

printf(\

ptr->kind,ptr->stime,ptr->ttime,ptr->etime,ptr->score,ptr->term); t=0; }

if(t)

printf(\未找到!\\n\

22

t=1;

system(\ goto L1; case 3:break; } }

void Mangers() {

int n,w=1,flag=0,i=3; char s[8];

char password[7]=\ do {

printf(\ scanf(\

if(!strcmp(s,password)) // {

flag=1; break; } else {

printf(\You only again:\\n\ i--; } }

while(i>0); if(!flag) {

printf(\ exit(0); // } do {

system(\

puts(\*******************\\n\\n\

puts(\录入课程\\n\ puts(\浏览课程\\n\ puts(\查询课程\\n\ puts(\删除课程\\n\ puts(\返回主菜单\

23

进行密码匹配验证 have %d times! Enter 输入密码超过了3次！！自动退出 管理员菜单

puts(\);

printf(\ scanf(\ switch(n) {

case 1:insert();savefile();break; case 2:prin();break; case 3:search();break;

case 4:del();savefile();break; case 5:return; default:; } }

while(w==1); }

void Students() {

int n,w=1; do {

system(\

puts(\学生菜单*******************\\n\\n\

puts(\浏览所有课程\\n\ puts(\查询课程信息\\n\ puts(\选择选修课程\\n\ puts(\浏览我选修的课程\\n\ puts(\删除错选课程\\n\ puts(\返回主菜单\

puts(\ printf(\ scanf(\ switch(n) {

case 1:prin();break; case 2:search();break; case 3:choose();break; case 4:prin1();break;

case 5:del();savefile1();break; case 6:return; default:; }

24

}

while(w==1); }

int main() {

int n,w=1; do {

system(\

puts(\ puts(\以管理员身份登录(password 1)\\n\ puts(\以学生身份登录\\n\ puts(\退出\

puts(\ printf(\ scanf(\ switch(n) {

case 1:Mangers() ;break; case 2:Students();break; case 3:w=0;break; default:; } }

while(w==1); return 0; }

四、排序重构问题

4.1问题说明

A为一个由N个已特殊排序数组成的数列：A1，A2，…，AN，其中A1=0。令B为N（N-1）/2个数（定义为Dij=Ai-Aj(i>j)）组成的数列。例如，A=0，1，5，8，那么D=1，3，4，5，7，8。请完成：

编写程序，根据A构造D；

编写程序，构造与D相对应的某一个数列A，注意A不是唯一的。

25

4.2数据结构设计

数据结构：结构体。 typedef struct {

int data[MAX]; int flag[MAX]; int size;

}array；

4.3算法设计

if((fp=fopen(\数组B.c\

{

printf(\文件打开失败！\\n\ exit(0); }

while(!feof(fp)) {

fread(&b,1,sizeof(array),fp); }

for(i=0;isize;i++) {

x=a->data[i];

for(j=i+1;jsize;j++) {

y=a->data[j]; b.data[k]=y-x; k++; } }

b.size=k;

26

4.4流程图如下：

图4.1 程序流程图

生成A 生成D

开始 录入A 4.5调试分析

a．调试中遇到的问题及对问题的解决方法

第一次排序的时候忘了让对应的下标对应起来，结果导致排序结果失误。解决方法，检查到之后更正回来。 b．算法的时间复杂度和空间复杂度

由于采用了三重循环进行组合计算，所以时间复杂度为O（n^3）

4.6测试结果

1 当输入数组A的大小为4,{0,1,5,8},数组B为{1,3,4,5,7,8,}，输出结果如图所示。

图4.1 数组A,B排序重新组图

27

4.7 源程序（带注释）

部分源程序

# include # include # include # include # define MAX 100

typedef struct {

int data[MAX]; int flag[MAX]; int size; }array; int

CREAT_NEW_A() {

FILE *fp;

array b,a; //b原始数据存储.a,构造的用于判断的结构体

int i,j,z; char ch[MAX];

strcpy(ch,\数组c.c\

if((fp=fopen(\数组B.c\ {

printf(\文件打开失败！\\n\ exit(0); }

28

while(!feof(fp)) {

fread(&b,1,sizeof(array),fp); }

fclose(fp); a.data[0]=0; printf(\数组：\\n\ for(i=0;i

a.data[1]=b.data[i]; a.data[2]=b.data[j]; a.data[3]=b.data[z]; a.size=4; COMPARE(&a,ch); }

printf(\满足条件\\n\ return 0; } int max; int

COMPARE(array *a,char ch[MAX]) {

FILE *fp; array d; array b;

int i,j,k=0,n,x,y,z;

if((fp=fopen(ch,\ {

printf(\文件打开失败！\\n\

29

exit(0); }

for(i=0;isize;i++) {

x=a->data[i];

for(j=i+1;jsize;j++) {

y=a->data[j]; b.data[k]=y-x; k++; } }

b.size=k; sort(&b);

fwrite(&b,1,sizeof(array),fp); fclose(fp);

if((fp=fopen(\数组B.c\ {

printf(\文件打开失败！\\n\ exit(0); }

while(!feof(fp)) {

fread(&d,1,sizeof(array),fp); }

fclose(fp);

for(i=0;i

if(b.data[i]!=d.data[i]) break;

30

}

if(i==d.size) {

for(i=0;isize;i++) printf(\ printf(\ }

return 0; }

31

总 结

紧张的两周数据结构课设很快就过去了，通过这两周的实践学习，不仅使我们巩固了以前的知识并在此基础上还对数据结构的特点和算法有了更深的了解，使我们在这门课程的实际应用上也有了一个提高。

其次，它激发了我们创新意识，开发创造的能力和培养沟通能力。另外，让我们进一步熟悉了数据结构的设计应用。每一处编码都是在反复的熟悉数据结构的结构特性，及其语法、函数和程序设计思想的过程，对我们数据结构的学习和提高很有益处，并且使我们明白了程序设计过程。

同时通过本次课程设计也加深了我对C语言相关知识的理解与掌握。课程设我相信通过这次课程设计的锻炼，能为我以后处理程序设计打下坚实的基础。

32

参考文献

[1] 秦锋.数据结构（C语言版）.第一版.北京：清华大学出版社.2011.

[2] 秦锋.数据结构（C语言版）例题详解与课程设计指导.第一版.北京：清华大学出版社.2011.

[3] 严蔚敏,吴伟民.数据结构（C语言版）.第一版.北京：清华大学出版社.2007. [4] 李春葆等.数据结构教程.第三版.北京：清华大学出版社.2009.

33

致 谢

在这两周的课程设计中，我查阅了相关的资料，尽量把问题理解透彻。由于自己能力水平有限，在加之时间比较紧张，所以本次课设还是面临着极大的挑战。在做练习的过程中，老师给予了我很多的帮助，让我可以顺利的完成任务，在此表示衷心的感谢。另外，在完成课程设计的过程中，舍友也给我提了不少的建议，帮我解决了好多难题，同学也不厌烦的给我讲解示范，再此一并表示感谢。另外还得感谢以前向我传授知识的老师们，毕竟做课程设计会遇到以前的很多知识。感谢学校提供这次实践的机会，让我可以更好的完善自己，提高自己的知识应运能力。

34

本文来源：https://www.bwwdw.com/article/t65a.html