【数据结构】线性表之顺序表（模板类）

wander

建立一个线性表，首先依次输入数据元素1，2，3，…，10这10个数并输出线性表和线性表个数，然后删除第5个数据元素后输出线性表和线性表个数，最后在线性表的第6个位置输入20并输出线性表和线性表个数。实现方法要求如下：

1）采用直接编写一个主函数实现。

2）顺序表类的定义和实现代码存放在文件SeqList.h中

步骤1：使用VC++6.0创建项目；

打开VC++6.0，选择“文件|新建”，打开新建项目对话框，在打开的新建对话框中选择“工程”选项卡，在该选项卡下选择“Win32 Console Application”，在右边的“工程名称”中输入工程名（如：list、test2等）----注意：不能用中文名称，也不能以数字开头，在“位置”处修改保存路径（如：D:\）；然后点击“确定”后进入下一窗口，选择“一个‘HelloWorld’程序”，点击“完成”，在弹出的对话框中选择“确定”。新建项目完成。

步骤2：新建类Seqlist，并编辑：

单击菜单栏上的“插入|类”，在弹出的对话框中的“名称”文本框中输入“SeqList”，单击“确定”添加类。在VC++6.0的左侧编辑面板的属性菜单中双击新建的类“SeqList”，打开编辑窗口编辑类。

SeqList类的部分代码如下：

#include <iostream>

using namespace std;         //注意：在vs2010中cout的输出要使用：std::cout<<temp<<" "，可以在预编译命令中添加;

const int MaxSize = 100;          //100只是示例性的数据，可以根据实际问题具体定义

template <class DataType>        //定义模板类SeqList

class SeqList  

{

public:

    SeqList(){length=0;}//无参构造函数，建立一个空的顺序表

    ~SeqList(){}//析构函数为空

  SeqList(DataType a[ ], int n);      //有参构造函数，建立一个长度为n的顺序表

int Length( ) {return length;}       //求线性表的长度

  DataType Get(int i);              //按位查找，在线性表中查找第i个元素

  int Locate(DataType x );          //按值查找，在线性表中查找值为x的元素序号

  void Insert(int i,DataType x);      //插入操作，在线性表中第i个位置插入值为x的元素

  DataType Delete(int i);             //删除操作，删除线性表的第i个元素

  void PrintList( );                    //遍历操作，按序号依次输出各元素

private:

  DataType data[MaxSize];          //存放数据元素的数组

  int length;                       //线性表的长度,即当前数组个数

};                 //注意：此处分号不能省略

//实现顺序表有参构造函数

template<class DataType>

SeqList<DataType>::SeqList(DataTypea[ ], int n)

{

    if(n > MaxSize)

    {

       throw"传入的顺序表长度过长";

    }

//给顺序表的存储元素的数组赋值

    for(int i = 0; i < n; i++)

    {

       data= a;

    }

//给顺序表的长度赋值

    length= n;

}

//实现顺序表按位查找

template<class DataType>

DataTypeSeqList<DataType>::Get(int i)            

{

    if(i>0&&i<length)

    returndata[i-1];

    else

       throw"位置错误";

}

//按值查找，在线性表中查找值为x的元素序号.未找到返回0；

template <class DataType>

int SeqList<DataType> ::  Locate(DataType x )         

{

    for(inti=0;i<length;i++)

       if(x==data)return(i+1);

    return0;

}

template <class DataType>

void SeqList<DataType> ::Insert(int i,DataType x)       //插入操作，在线性表中第i个位置插入值为x的元素

{

    if(i>=1&&i<=length)

    {

        for(int j=length;j>=i;j--)

           data[j]=data[j-1];

        data[i-1]=x;

        length++;

    }

    else

       throw"插入位置错误！";

}

template <class DataType>

DataType SeqList<DataType> :elete(int i)             //删除操作，删除线性表的第i个元素

{

if (length==0) throw "下溢";

if (i<1 || i>length) throw"位置非法";

DataType x=data[i-1];                   //先保存要删除的数据元素，以备返回。

for (int j=i; j<length; j++)      //循环移位

    data[j-1]=data[j];   //注意此处j已经是元素所在的数组下标

length--;

return x;

}

template <class DataType>

void SeqList<DataType> :rintList( )                    //遍历操作，按序号依次输出各元素

{

    if(length < 1)

    {

       throw"顺序表中没有元素";

    }

    else

    {

       //顺序输出顺序表元素

       for(int i = 0; i < length; i++)

       {

           cout<<data<<"";

       }

       cout<<endl;

    }

}

保存文件；

步骤3：编写主程序

#include <iostream.h>      //vs2010中使用：#include <iostream>

#include "stdafx.h"

#include<iostream>

#include "SeqList.h"

int main(int argc, char* argv[])

{

inta[]={1,2,3,4,5，6,7,8,9,10};

    SeqList<int> seql=SeqList<int>(a,10);

cout<<"顺序表为：";

seql.PrintList();

printf("顺序表长度为：%d\n",seql.Length());

cout<<"第2个位置的元素是："<<seql.Get(2)<<endl;

cout<<"元素值3的位置是："<<seql.Locate(3)<<endl;

cout<< "---------------------------------------" << endl；

cout<<"删除第5个数后";

seql.Delete(5);

cout<<"顺序表为：";

seql.PrintList();

printf("顺序表长度为：%d\n",seql.Length());

cout<< "---------------------------------------" << endl;

cout<<"在第6位置插入20后，";

seql.Insert(6,20);

cout<<"顺序表为：";

seql.PrintList();

printf("顺序表长度为：%d\n",seql.Length());

cout<< "---------------------------------------" << endl;

printf("\nHelloWorld!\n");

getchar();

//cin.get();//暂停，等待输入

return0;

};