数据结构——算法、程序设计
2022/1/16 14:04:50
本文主要是介绍数据结构——算法、程序设计，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
一、实验目的
- 理解和掌握线性表的类型定义方法。
- 掌握顺序表中的基本运算，包括顺序表的创建、元素的添加、删除，判空及判满等基本操作。
二、实验要求
【题目1 - C/C++语言中函数参数传递的三种方式】
C语言提供了两种函数参数传递的方式：传值和传地址。在C++中，又拓展了引用方式。通过本项目，确认是否已经掌握了这三种方式的原理，为后续学习做好准备。
两个变量的值的交换，请用三种方法来实现，分别完成主程序的编写：
//（1）传值
void myswap(int x, int y)
{
int t;
t=x;
x=y;
y=t;
}
//（2）传地址
void myswap(int *p1, int *p2) P1=&A
{
int t;
t=*p1;
*p1=*p2;
*p2=t;
}
//（3）引用作形参
void myswap(int &x, int &y)
{
int t;
t=x;
x=y;
y=t;
}
int main()
{
int a, b;
printf("请输入待交换的两个整数：");
scanf("%d %d", &a, &b);
__________________; //分三个程序，分别写上调用myswap的合适形式
printf("调用交换函数后的结果是：%d 和 %d\n", a, b);
return 0;
}
添加修改：
第一种交换:
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
void myswap1(int x, int y)
{
int t;
t=x;
x=y;
y=t;
}
//（2）传地址
void myswap2(int *p1, int *p2) //P1=&A
{
int t;
t=*p1;
*p1=*p2;
*p2=t;
}
//（3）引用作形参
void myswap3(int &x, int &y)
{
int t;
t=x;
x=y;
y=t;
}
int main()
{
int a, b;
printf("请输入待交换的两个整数：");
scanf("%d %d",&a,&b);
myswap1(a,b); //分三个程序，分别写上调用myswap的合适形式
printf("调用交换函数后的结果是：%d 和 %d\n", a, b);
return 0;
}
运行截图：
第二种交换：
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
void myswap1(int x, int y)
{
int t;
t=x;
x=y;
y=t;
}
//（2）传地址
void myswap2(int *p1, int *p2) //P1=&A
{
int t;
t=*p1;
*p1=*p2;
*p2=t;
}
//（3）引用作形参
void myswap3(int &x, int &y)
{
int t;
t=x;
x=y;
y=t;
}
int main()
{
int a, b;
printf("请输入待交换的两个整数：");
scanf("%d %d",&a,&b);
myswap2(&a,&b); //分三个程序，分别写上调用myswap的合适形式
printf("调用交换函数后的结果是：%d 和 %d\n", a, b);
return 0;
}
运行截图：
第三种交换：
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
void myswap1(int x, int y)
{
int t;
t=x;
x=y;
y=t;
}
//（2）传地址
void myswap2(int *p1, int *p2) //P1=&A
{
int t;
t=*p1;
*p1=*p2;
*p2=t;
}
//（3）引用作形参
void myswap3(int &x, int &y)
{
int t;
t=x;
x=y;
y=t;
}
int main()
{
int a, b;
printf("请输入待交换的两个整数：");
scanf("%d %d",&a,&b);
myswap3(a,b); //分三个程序，分别写上调用myswap的合适形式
printf("调用交换函数后的结果是：%d 和 %d\n", a, b);
return 0;
}
运行截图：
【项目2 - 程序的多文件组织】
学习数据结构，目标就是要编制出有相当规模的程序的。将所有的代码放在一个文件中的做法，不能适用现阶段的需求了。
通过这个项目，确认有能力用多文件组织程序。方便以后各章，我们就某一数据结构定义算法库，并能引用算法库进行实践。
最简单的多文件组织，一个项目中有3个文件：
(1) .h 头文件：定义数据类型、声明自定义函数、定义宏等
(2).cpp 源文件1：用于实现头文件中声明的自定义函数
(3).cpp 源文件2：定义main()函数，用于调用相关函数，实现问题求解目标。
如程序：
head.h:
#ifndef HEAD_H_INCLUDED
#define HEAD_H_INCLUDED
#define MaxStud 50
#define MaxCour 300
struct stud1
{
int no;
char name[10];
int bno;
};
struct stud2
{
int no;
int cno;
int deg;
};
double studavg(struct stud2 s2[],int m,int i);
double couravg(struct stud2 s2[],int m,int i);
void allavg(struct stud1 s1[],int n,struct stud2 s2[],int m);
#endif // HEAD_H_INCLUDED
sources.cpp:
#include "head.h"
#include <iostream>
#include <stdio.h>
using namespace std;
double studavg(struct stud2 s2[],int m,int i)
{
int j,n=0;
double sum=0;
for(j=0;j<m;j++)
if(s2[j].no==i)
{
n++;
sum+=s2[j].deg;
}
return (sum/n);
}
double couravg(struct stud2 s2[],int m,int i)
{
int j,n=0;
double sum=0;
for(j=0;j<m;j++)
if(s2[j].cno==i)
{
n++;
sum+=s2[j].deg;
}
return (sum/n);
}
void allavg(struct stud1 s1[],int n,struct stud2 s2[],int m)
{
int i,j;
printf("学生平均分：\n");
printf(" 学号 姓名 平均分\n");
i=0;
while(i<n)
{
j=s1[i].no;
printf("%4d%10s%g\n",s1[i].no,s1[i].name,studavg(s2,m,j));
i++;
}
printf("课程平均分：\n");
for(i=1;i<6;i++)
printf(" 课程%d:%g\n",i,couravg(s2,m,i));
}
main.cpp:
#include "head.h"
#include <iostream>
using namespace std;
int main()
{
int n=7;
int m=21;
struct stud1 s1[MaxStud]=
{
{1,"张斌",9901},
{8,"刘丽",9902},
{34,"李英",9901},
{20,"陈华",9902},
{12,"王奇",9901},
{26,"董强",9902},
{5,"王萍",9901},
};
struct stud2 s2[MaxCour]=
{
{1,1,67},
{1,2,98},
{1,4,65},
{8,1,98},
{8,3,90},
{8,6,67},
{34,2,56},
{34,4,65},
{34,6,77},
{20,1,68},
{20,2,92},
{20,3,64},
{12,4,76},
{12,5,75},
{12,6,78},
{26,1,67},
{26,5,78},
{26,6,62},
{5,1,94},
{5,2,92},
{5,6,89}
};
allavg(s1,n,s2,m);
return 0;
}
程序运行结果截图：
【项目3 - 体验复杂度】
（1）两种排序算法的运行时间
排序是计算机科学中的一个基本问题，产生了很多种适合不同情况下适用的算法，也一直作为算法研究的热点。本项目提供两种排序算法，复杂度为O(n2)的选择排序BubbleSort，和复杂度为O(nlogn)的快速排序quicksort，在main函数中加入了对运行时间的统计。
请阅读后附的程序1和程序2，利用一个将近10万条数据的文件作为输入数据运行程序，感受两种算法在运行时间上的差异。
代码：
head.h:
#ifndef HEAD_H_INCLUDED #define HEAD_H_INCLUDED #include<time.h> #include<stdlib.h> #define MAXNUM 100000 void BubbleSort(int a[],int n); void quicksort(int data[],int first,int last); #endif // HEAD_H_INCLUDED
sources.cpp:
#include "head.h"
#include <iostream>
using namespace std;
void BubbleSort(int a[],int n)
{
int i,j;
bool exchange;
for(i=0;i<n-1;i++)
{
exchange=false;
for(j=n-1;j>i;j--)
{
if(a[j]<a[j-1])
{
swap(a[j],a[j-1]);
exchange=true;
}
}
if(!exchange)
return;
}
}
void quicksort(int data[],int first,int last)
{
int i,j,t,base;
if(first>last)
return;
base=data[first];
i=first;
j=last;
while(i!=j)
{
while(data[j]>=base&&i<j)
j--;
while(data[i]<=base&&i<j)
i++;
if(i<j)
{
t=data[i];
data[i]=data[j];
data[j]=t;
}
}
data[first]=data[i];
data[i]=base;
quicksort(data,first,i-1);
quicksort(data,i+1,last);
}
main.cpp:
#include "head.h"
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int x[MAXNUM];
int n=0;
double t1,t2;
FILE *fp;
fp=fopen("numbers.txt","r");
if(fp==NULL)
{
printf("打开文件错！请下载文件，并将之复制到与源程序文件同一文件夹下。\n");
exit(1);
}
while(fscanf(fp,"%d",&x[n])!=EOF)
n++;
printf("数据量： %d,开始排序....",n);
t1=time(0);
BubbleSort(x,n);
// quicksort(x,0,n-1);
t2=time(0);
printf("用时 %d 秒",(int)(t2-t1));
fclose(fp);
return 0;
}
运行截图：
这篇关于数据结构——算法、程序设计的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-09-21订单系统资料入门教程：轻松管理你的订单
- 2024-09-21Java部署资料：新手入门教程
- 2024-09-21Java部署资料：新手入门教程
- 2024-09-21Java订单系统资料：新手入门教程与实战指南
- 2024-09-21Java管理系统资料入门教程
- 2024-09-21从零开始学习Java监控系统资料
- 2024-09-21Java就业项目资料：新手入门的必备教程
- 2024-09-21Java全端资料：初学者指南
- 2024-09-21Java全栈资料入门教程及资源汇总
- 2024-09-21Java日志系统资料入门教程
