C++数据结构01--顺序线性表实现

今天正好又是很闲，就简单实现一下数据结构里面的顺序线性表玩一下，后面有时间再慢慢把后面几种数据结构实现一下玩一下。

顺序线性表，就是在连续内存中元素按内存地址顺序排列的数据结构，本人用数组来实现的，因为数组就是连续分配的内存区域，所以比较好弄，加一个结构体。

现在上代码：

首先是头文件

#include "stdafx.h"
using namespace std;

#define MaxSize 255 //定义数组最大长度

typedef int datatype;

typedef struct{
  datatype data[MaxSize];
  int length; //保存线性表的长度
}SeqList;

//顺序线性表类
class Sequential{
public:
  Sequential();//构造函数
  ~Sequential();//析构函数

  //查询操作
  datatype GetElemByPos(SeqList *L,int pos); //根据位置，返回元素值
  int GetElemByData(SeqList *L,datatype data); //根据元素值，返回第一个找到的元素的位置

  //插入操作
  bool InsertData(SeqList *L,int pos,datatype data);  

  //删除操作
  bool DeleteDataByPos(SeqList *L,int pos);//根据位置删除元素

  //返回线性表长度
  int getLength(SeqList *L);

  //查看是否为空
  bool isEmptySeqList(SeqList *L);

  //清空线性表数据
  bool clearSeqList(SeqList *L);
};

其次是cpp实现的文件代码：

#include "stdafx.h"
#include "SeqLineList.h"

using namespace std;

Sequential::Sequential(){
cout << "初始化构造函数";
}

Sequential::~Sequential()
{
  cout << "delete 构造函数 "<<endl;
}

//查找元素
//@param[in]:L:需要查找的线性表
//@param[in]:pos:查找的位置
//return:找到的元素值
datatype  Sequential::GetElemByPos(SeqList *L,int pos)
{
  int length = L->length; 
  if (length == 0)
  {
    cout << "当前线性表大小为0，不存在元素" <<endl;
    return 0;
  }
  else
  {
    if (pos > length || pos <= 0)
    {
      cout << "pos值大于线性表的长度或pos值小于0,无法获取值元素"<<endl;
      return 0;
    }
    else
    {
      datatype cur_val = L->data[pos-1];
      return cur_val;
    }
  }
}

//查找元素
//@param[in]:L:需要查找的线性表
//@param[in]:data:需要查找的元素值
//return:元素位置
int Sequential::GetElemByData(SeqList *L,datatype data)
{
  int length = L->length; 
  if (length == 0)
  {
    cout << "当前线性表大小为0，不存在元素" <<endl;
    return 0;
  }

  //查找元素（默认第一个元素就终止寻找，返回位置）
  for (int i = 0; i < length-1; i++)
  {
    if (L->data[i] == data)
    {
      cout << "找到元素，元素位置是"  << i+1<< endl;
      return i+1;
    }
  }
  cout << "未找到元素" << endl;
  return 0;
}

//插入元素操作
//@param[in]:L:需要查找的线性表
//@param[in]:pos:需要插入的位置
//@param[in]:data:需要插入的元素值
//return:true:插入成功，false：插入失败
bool Sequential::InsertData(SeqList *L,int pos,datatype data)
{
  //先获取当前线性表的长度
  int length = L->length;
  if (length == MaxSize)
  {
    cout << "线性表已满，无法插入元素了！";
    return false;
  }
  if (pos > length || pos < 0)
  {
    cout << "位置超过长度，无法插入元素";
    return false;
  }
  //在pos元素末尾添加元素
  if (pos == length)
  {
    L->data[length] = data;
    L->length = length +1;
    cout << "元素插入成功！" << endl;
    return true;
  }
  else
  {
    for (int i = length-1; i >= pos; i--)
    {
      L->data[i+1] = L->data[i];
    }
    L->data[pos] = data;
    L->length  = length+1;
    cout << "元素插入成功！" << endl;
  }
  return true;
}

//删除操作
//param[in]:L:需要删除的线性表
//param[in]:pos:删除的位置
//return: false:删除失败，true:删除成功
bool Sequential::DeleteDataByPos(SeqList *L,int pos)
{
  int length = L->length;
  //避免本身线性表就为空，那也删不了
  if (pos > length || pos < 1 || length == 0 )
  {
    cout << "长度超过length或者小于1，无法删除元素"<< endl;
    return false;
  }

  //pos等于length 只要删除最后一个元素即可
  if (pos == length)
  {
    L->data[length-1] = L->data[length];
    L->length = length-1;
    cout << "删除元素成功" << endl;
    return true;
  }
  else
  {
    for (int i = pos-1; i< length; i++)
    {
      L->data[i] = L->data[i+1];  
    }
    cout << "删除元素成功" << endl;
    L->length = length -1;
  }
  return true;
}

//返回顺序线性表的长度
//@param[in]:L:需要查询的线性表
//return:线性表的长度
int Sequential::getLength(SeqList *L)
{
  return L->length;
}

//判断线性表是否为空
//@param[in]:需要的线性表
//return:true:空，false：非空
bool Sequential::isEmptySeqList(SeqList *L)
{
  return L->length?false:true;
}

//清空线性表
//@param[in]:L:需要清空的线性表
//return:true:清空成功，false：失败
bool Sequential::clearSeqList(SeqList *L)
{
  int length = L->length;
  if (length!=0)
  {
    for (int i = length-1; i >=0; i--)
    {
      L->data[i] = L->data[i+1];
    }
    L->length = 0;
  }
  return true;
}

然后用来测试这功能的代码：

// SequentialLinearList.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "SeqLineList.h"
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    SeqList *test = new SeqList;
    test->length = 0;
    test->data;
    Sequential *sq =new Sequential();
    sq->InsertData(test,0,1);
    sq->InsertData(test,1,2);
    datatype cur_pos = sq->GetElemByPos(test,1);
    sq->DeleteDataByPos(test,1);
    bool isEmpty_dd = sq->isEmptySeqList(test);
    sq->DeleteDataByPos(test,1);
    int cur_data_pos =sq->GetElemByData(test,4);
    bool isEmpty = sq->isEmptySeqList(test);
    cout << cur_pos;
    //释放内存
    delete test;
    delete sq;
    return 0;
}

希望大家可以学会就是了 数据结构还是比较重要的

源码放在github上：​​https://github.com/huifeng-kooboo/DataStructure​​

主要当复习或者面试的时候 感觉写在github上比较好，正好也可以展示出来自己有会这些东西哈哈哈哈哈