Java教程

数据结构——算法、程序设计

本文主要是介绍数据结构——算法、程序设计,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、实验目的

  1. 理解和掌握线性表的类型定义方法。
  2. 掌握顺序表中的基本运算,包括顺序表的创建、元素的添加、删除,判空及判满等基本操作。

二、实验要求

【题目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;
}

运行截图:
在这里插入图片描述
在这里插入图片描述

这篇关于数据结构——算法、程序设计的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!