数据结构课程设计报告

发表于 | 分类于

课题：排序算法、演示及飞机订票系统
姓名：陈实
学号：19130216
班级：191302
指导教师：陈波

#一、排序算法
任务描述：利用c++生成100W个随机数，并实现归并，快排，希尔以及堆排序，记录排序结果及时间等。

##1.1、生成随机数
利用c#中的种子生成器，通过文件流保存至相应文件夹。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void range()
      {
          string path = Directory.GetCurrentDirectory();//获取当前目录
          path += "/RawData.txt";//文件名

          Random example = new Random();//种子生成器

          //MessageBox.Show(path);//测试路径是否正确

          using (StreamWriter sw = File.CreateText(path))
          {
              for (int i = 0; i < number; i++)
              {
                  int tmp = example.Next(1, 65536);
                  sw.WriteLine(tmp);
              }
              MessageBox.Show("已生成" + number/10000 + "万个随机数");
          }
          ReadFile(filedata, path);
      }

##1.2、文件读取与存储
文件流读取文件与存储文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private void ReadFile(int[] f, String path)
{
    using (StreamReader sr = File.OpenText(path))
    {
        string s = "";
        int i = 0;
        while ((s = sr.ReadLine()) != null)
        {
            int tmp = int.Parse(s);
            f[i++] = tmp;
        }
    }

}

private void SaveFile(int[] f, String path)
{
    using (StreamWriter sw = File.CreateText(path))
    {
        for (int i = 0; i < f.Length; i++)
        {
            sw.WriteLine(f[i]);
        }
    }
}

##1.3、排序gui界面控件的代码设置
四个算法类似

  • 若未检测到生成随机数，则生成随机数
  • 利用跑表来测程序时间
  • 通过文件流拷贝文件数据
  • 排序程序
  • 显示结果
  • 其他几个类似
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    private void ShellSort_Click(object sender, EventArgs e)
          {
              if (filedata[1] == 0)
              {
                  range();
              }

              Stopwatch stopWatch = new Stopwatch();//跑表

              int[] shell_copy = new int[filedata.Length];//拷贝原始数据
              filedata.CopyTo(shell_copy, 0);

              stopWatch.Start();
              Shell(shell_copy);
              stopWatch.Stop();

              string path = Directory.GetCurrentDirectory();//获取当前目录
              path += "/" + DateTime.Now.ToString("yyyyMMdd"); ;
              Directory.CreateDirectory(path);

              String name = "ShellRes_runtime_";
              name += stopWatch.Elapsed.Milliseconds + "ms_";
              name += DateTime.Now.ToString("yyyyMMdd");
              name += DateTime.Now.ToString("HHmmss");//获取当前时间，用于创建文件夹
              name += ".txt";


              path += "/" + name;//获取写入目录

              SaveFile(shell_copy, path);//写入文件

              String res = "希尔排序执行完毕，执行时间：" + stopWatch.Elapsed.Milliseconds + "ms," + "结果保存至当前目录";
              hint h = new hint();
              h.setstr(res);
              h.Show();
          }

##1.4、排序过程

###1.4.1、希尔排序
间隔递减的插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void Shell(int[] r)
    {
        int n = r.Length;
        for (int d = n; d >= 1; d = d / 2)
        {
            for (int i = d; i < n; i++)
            {
                int j;
                int temp = r[i];				//暂存被插入记录
                for (j = i - d; j >= 0 && temp < r[j]; j = j - d)
                    r[j + d] = r[j];			//记录后移d个位置
                r[j + d] = temp;
            }
        }
    }

###1.4.2、快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private int Partition(int[] r, int i, int j)
{
    int temp = r[i];
    while (i < j)
    {
        while (i < j && r[j] >= temp)
            j--;
        if (i < j)
            r[i++] = r[j];
        while (i < j && r[i] <= temp)
            i++;
        if (i < j)
            r[j--] = r[i];
    }
    r[i] = temp;
    return i;
}
void Quick(int[] r, int i, int j)//快速排序算法QuickSort
{
    if (i < j)
    {
        int pivot = Partition(r, i, j);
        Quick(r, i, pivot - 1);
        Quick(r, pivot + 1, j);
    }
}

###1.4.3、堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
private void sift(int[] array, int target, int tail)
{
    int tmp;
    int child = target * 2;
    while (child <= tail)
    {
        if (child + 1 <= tail && array[child] < array[child + 1])
        {
            child++;
        }
        if (array[child] <= array[target])
        {
            break;
        }
        if (array[child] > array[target])
        {
            tmp = array[child];
            array[child] = array[target];
            array[target] = tmp;
            target = child;
            child = child * 2;
        }
    }
}

void Heap(int[] r)//堆排序Heap
{
    int len = r.Length;
    for (int i = len / 2; i >= 0; i--)
    {
        sift(r, i, len - 1);
    }
    //sorted and adjust
    int tmp, tail;
    for (int i = 0; i < len - 1; i++)
    {
        tail = len - 1 - i;
        tmp = r[tail];
        r[tail] = r[0];
        r[0] = tmp;
        sift(r, 0, tail - 1);
    }
}

###1.4.4、归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void merge(int[] array, int start, int mid, int end)
      {
          int[] tmpArray = new int[end - start + 1];
          int i = start;
          int j = mid + 1;
          int k = 0;
          while (i <= mid && j <= end)
          {
              if (array[i] <= array[j])
              {
                  tmpArray[k++] = array[i++];
              }
              else
              {
                  tmpArray[k++] = array[j++];
              }
          }
          while (i <= mid)
          {
              tmpArray[k++] = array[i++];
          }
          while (j <= end)
          {
              tmpArray[k++] = array[j++];
          }
          i = 0;
          while (start <= end)
          {
              array[start++] = tmpArray[i++];
          }
      }
      void Merge(int[] array, int start, int end)
      {
          if (start < end)
          {
              int mid = (start + end) / 2;
              Merge(array, start, mid);
              Merge(array, mid + 1, end);
              merge(array, start, mid, end);
          }
      }

##1.5、程序测试

###1.5.1、主界面展示
主界面展示

###1.5.2、生成随机数界面
生成随机数界面

###1.5.3、一万测试数据
（1）
一万测试数据1
（2）
一万测试数据2

###1.5.4、十万测试数据
（1）
十万测试数据1
（2）
十万测试数据2

###1.5.5、百万测试数据
（1）
百万测试数据1
（2）
百万测试数据2

##1.6、结果目录展示
此处输入图片的描述

###1.7、数据结果分析
万级别上，各排序速度相仿，均在几毫秒之内完成内存排序，
十万级别及百万级别上，随机数生成的测试文件，快速排序表现尤其好。
测试数据范围：1~65535

#二、飞机管理系统

##2.1、问题描述

1
2
3
4
5
6
7
8
9
任务：通过此系统可以实现如下功能：
录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）
查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；
可以输入起飞抵达城市，查询飞机航班情况；
订票：（订票情况可以存在一个数据文件中，结构自己设定）
可以订票，如果该航班已经无票，可以提供相关可选择航班；
退票： 可退票，退票后修改相关数据文件；
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
修改航班信息：当航班信息改变可以修改航班数据文件

##2.2、问题解析

  • 问题不难，即一个管理系统，本文采用c#做gui界面，数据结构是可变数组。
  • 文件操作，仿照数据库操作，即用即读，不再在加载界面时读入内存。
  • 本文主界面共提供了8个按钮,分三组为：航班管理，票务管理以及系统。

##2.3、航班管理

###2.3.1、录入航班

  • 通过人工键入值，追加保存到文件末尾

###2.3.2、删除航班

  • 从文件读取，并绑定到下拉列表框，提供显示与删除功能。并做了一定的安全测试。

###2.3.3、修改航班

  • 从文件读取，并绑定到下拉列表框，提供显示与修改功能。并做了一定的安全测试。

##2.3、票务管理

###2.3.1、航班号订票

  • 已知航班号，从文件读取数据，输入相关信息，订票并写回文件，并做了一定的安全测试。

###2.3.2、选择订票

  • 文件读取信息，绑定到控件，选择起始地与目的地订票，写回文件，并做了一定的安全测试。

###2.3.3、退票

  • 文件读取信息，绑定到控件，选择客户ID，退票。

##2.4、系统

###2.4.1、退出系统

  • 提供退出程序的功能。

###2.4.2、关于

  • 关于本软件的信息。

##2.5、数据格式设计

###2.5.1、航班数据
共9个字段，均为string型，方便操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Flight
   {
       public string FlightNumber;
       public string StartTime;
       public string EndTime;
       public string StartCity;
       public string EndCity;
       public string FlightTicket;
       public string TicketDisconut;
       public string MaxNumber;
       public string RestTicketNum;


       public Flight(string[] str)
       {
           if (str.Length != 9)
           {
               throw new Exception();
           }
           else
           {
               FlightNumber = str[0];
               StartTime = str[1];
               EndTime = str[2];
               StartCity = str[3];
               EndCity = str[4];
               FlightTicket = str[5];
               TicketDisconut = str[6];
               MaxNumber = str[7];
               RestTicketNum = str[8];

           }
       }
       public override string ToString()
       {
           string res = "";
           res +=
           FlightNumber +","+
           StartTime + "," +
           EndTime + "," +
           StartCity + "," +
           EndCity + "," +
           FlightTicket + "," +
           TicketDisconut + "," +
           MaxNumber + "," +
           RestTicketNum;
           return res;
       }
   }

###2.5.1、订单数据
共4个字段，均为string型，方便操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Order
{
    public string FlightNumber;
    public string Ordernum;
    public string name;
    public string Id;

    public Order(string[] str)
    {
        if (str.Length != 4)
        {
            throw new Exception();
        }
        else
        {
            Ordernum = str[0];
            FlightNumber = str[1];
            name = str[2];
            Id = str[3];
        }
    }
    public override string ToString()
    {
        string res = "";
        res +=
        Ordernum + "," +
        FlightNumber + "," +
        name + "," +
        Id;
        return res;
    }
}

##2.6、软件测试
测试繁多，不宜展示，在测试的时候修复许多bug，一定程度上增强了软件的安全性。

###2.6.1、软件主界面
软件主界面

###2.6.2、录入航班
录入航班

###2.6.3、删除航班
删除航班

###2.6.4、修改航班
修改航班

###2.6.5、航班号订票
航班号订票

###2.6.6、目的地订票
目的地订票

###2.6.7、退票
退票

#三、排序演示

  • 本程序是基于MFC编写的，原框架是来源于VC课程，再次做了重构，提取出了方法，便于加类以实现不同的排序演示，在这里，介绍一个demo。
  • 程序采用绘制view和时钟中断，实现了模拟排序的效果。

##3.1、csArray类

1
这是所有排序类的基类，其他排序类由此扩展，负责绘制一些基本的试图。

##3.2、CTestView

1
视图类，控制时钟中段，建立排序类实例，绘制排序类等功能。

##3.3、扩展排序类

目前实现了冒泡，插入，选择，希尔的演示

##3.4、程序测试

###3.4.1、程序主界面
程序主界面

###3.4.2、冒泡排序
冒泡排序

###3.4.3、插入排序
插入排序

###3.4.4、选择排序
选择排序

###3.4.5、希尔排序
希尔排序

#四、课设心得

  • 更好的掌握数据结构
  • 更严谨的测试程序
  • 通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法
  • 培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力
  • 严肃认真的心态