《数据结构》

实验报告

题目:_顺序表的实现

学号:___________

姓名:___________

东南大学计算机系

实验题目

一、    实验目的

1.    掌握顺序表的基本操作，实现顺序表的插入、删除、查找等基本运算。

二、    实验内容

1.                       完善顺序表的定义，并运用其实现线性表的操作。

2.                       (课上任务)

     选题一：集合的交、并、差运算

【问题描述】

        编制一个能演示执行集合的交、并和差运算的程序。

【任务要求】

1) 集合元素用小写英文字母，执行各种操作应以对话方式执行。

2) 算法要点：利用顺序表表示集合；理解好三种运算的含义

【测试数据】

自行设定，注意边界等特殊情况。

选题二：文章编辑

功能：输入一页文字，程序可以统计出文字、数字、空格的个数。

静态存储一页文章，每行最多不超过80个字符，共N行；要求①分别统计出其中英文字母数和空格数及整篇文章总字数；②统计某一字符串在文章中出现的次数，并输出该次数；③删除某一子串，并将后面的字符前移。

存储结构使用顺序表，分别用几个子函数实现相应的功能；

输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。

输出形式：①分行输出用户输入的各行字符；②分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"；③输出删除某一字符串后的文章；

选题三：构造有序顺序表

要求：进一步完善SqList类模板，实现顺序表的按值插入元素，即顺序表为递增有序表，插入元素后仍递增有序。

方法：在sq_list.h中添加代码，在SqList类模板的定义中添加函数声明，在类模板实现部分实现该函数。

bool  CreateListOrder();

bool  InsertOrder(ElemType e);

三、    实验步骤

1.启动VC6.0：开始菜单→程序→Microsoft Visual Studio 6.0 →Microsoft Visual C++ 6.0

2.建立工程：文件（File）→新建（new）→在弹出的对话框中选择工程标签（Project）→选中选项：Win32 Console Application（不能选别的）→输入工程名（Project Name）→选择工程的存放位置（Location）→单击“确定”按钮（OK）→在弹出的对话框中选中选项：An Empty Project→单击“完成”按钮（Finish）→在弹出的对话框中单击“确定”按钮（ OK ）。

3.创建头文件：文件（File）→新建（new）→在弹出的对话框中选择文件标签（Files） →选中选项：C/C++ Header File→输入头文件名（此处定义为“sq_list.h”）→单击“确定”按钮（OK）。

sq_list.h内容如下：

#ifndef __SQ_LIST_H__

#define __SQ_LIST_H__

// 顺序表类模板

template <class ElemType>

class SqList 

{

protected:

// 顺序表实现的数据成员:

        int count;                 // 元素个数

        int maxSize;              // 顺序表最大元素个数

        ElemType *elems;          // 元素存储空间

public:

// 顺序表的方法声明：

     SqList(int size); // 初始化线性表

     virtual ~SqList()    // 销毁线性表

     bool CreateList(); //构建顺序表

     void Clear();             // 将线性表清空

     int Length() ;    // 求线性表长度                

     bool Empty() ;    // 判断线性表是否为空

     bool Full() ;     // 判断线性表是否已满

     bool SetElem(int position, ElemType e);// 设置指定位置的元素值

     bool GetElem(int position, ElemType &e) ;    // 求指定位置的元素

int Locate (ElemType  e); //元素定位

      bool Insert(int position,  ElemType e);// 插入元素

      bool Delete(int position, ElemType &e);// 删除元素     

void Traverse() ;                       // 遍历线性表

};

// 顺序表类模板的实现部分由学生自己完成

……

5. 创建源程序文件main.cpp：文件（File）→新建（new）→在弹出的对话框中选择文件标签（Files） →选中选项：C++ Source File→输入源程序文件名（main）→单击“确定”按钮（OK）。

main.cpp文件内容可参考下述代码：

#include "sq_list.h"   // 顺序表类

void main(void)

{

    int size=0;

cout<<”请输入顺序表最大长度：”;

cin>>size;

    SqList<int> sl(size);

    char c = ‘0‘;

    while (c != ‘13‘)

{

        cout << endl << "1. 输入线性表，创建顺序表";

        cout << endl << "2. 求线性表长度";

        cout << endl << "3. 判断线性表是否为空";

        cout << endl << "4. 判断线性表是否已满";

        cout << endl << "5. 修改线性表某元素值";

        cout << endl << "6. 求线性表某位置元素值";

        cout << endl << "7. 在线性表中查找元素";

        cout << endl << "8. 在线性表中插入元素";

        cout << endl << "9. 在线性表中删除元素";

        cout << endl << "10. 遍历线性表";

        cout << endl << "11. 清空线性表";

        cout << endl << "12. 销毁线性表";

        cout << endl << "13. 退出";

        cout << endl << "选择功能(1~13):";    

cin >> c;

        switch (c) e

        {

            case ‘1‘:sl.CreateList(); break;

             case ‘2‘:

             case ‘3‘:

        ................//剩余部分学生自己完成

         }

        }

}                                                    

注意：1.在编程过程中注意及时保存编写内容。

      2.对顺序表的各种操作在运行结果中体现出来。

四、    实验结果

1. sq_list.h的代码
2. main.cpp的代码
3. 运行结果截图（可以有多张）

顺序表实验2