数据结构课程设计报告

课程设计

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

一、排序算法

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

1.1、生成随机数

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

  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、文件读取与存储

文件流读取文件与存储文件

        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界面控件的代码设置

四个算法类似

• 若未检测到生成随机数，则生成随机数
• 利用跑表来测程序时间
• 通过文件流拷贝文件数据
• 排序程序
• 显示结果
• 其他几个类似

  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、希尔排序

间隔递减的插入排序

    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、快速排序

        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、堆排序

        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、归并排序

  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）

（2）

1.5.4、十万测试数据

（1）

（2）

1.5.5、百万测试数据

（1）

（2）

1.6、结果目录展示

1.7、数据结果分析

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

二、飞机管理系统

2.1、问题描述

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

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型，方便操作。

 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型，方便操作。

    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类

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

3.2、CTestView

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

3.3、扩展排序类

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

3.4、程序测试

3.4.1、程序主界面

3.4.2、冒泡排序

3.4.3、插入排序

3.4.4、选择排序

3.4.5、希尔排序

四、课设心得

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