线性表的顺序储存结构

发表评论
6,440 views

A+

所属分类：Fly数据结构与算法原创文章

线性表：有零个或多个数据元素组成的有限序列

（a1,a2,......,ai-1,ai,ai+1,.......an）

其中ai-1是ai的直接前驱元素

ai+1是ai的直接后继元素

概念就不多说了

百度一大把

重点是实现

下面实现线性表的顺序储存结构

这里使用C#语言

class MyList<T>
{
    private T[] _data;
    private int _maxLength = 24;
    private int _currentLength = 0;

class MyList<T>

{

private T[] _data;

private int _maxLength = 24;

private int _currentLength = 0;

这里使用泛型来兼容多种数据类型

并规定了数据类型为值类型

_data是用来储存数据的数据域

使用数组来表达顺序储存结构

数组的元素之间的储存单元是连续的

_maxLength规定线性表可以储存元素的最大值

也就是数组的最大储存值

_currentLength是当前线性表元素的个数

//默认构造函数
public MyList() {
    this._data = new T[this._maxLength];
}

//自定义线性表的长度
public MyList(int length) {
    if (length <= 0) {
        this._data = new T[this._maxLength];
    }
    else
    {
        this._data = new T[length];
        this._maxLength = length;
    }
}

//默认构造函数

public MyList() {

this._data = new T[this._maxLength];

}

//自定义线性表的长度

public MyList(int length) {

if (length <= 0) {

this._data = new T[this._maxLength];

}

else

{

this._data = new T[length];

this._maxLength = length;

}

编写两个构造函数

一个使用默认的线性表长度

一个可以自定义数组的长度也就是线性表的长度

//添加元素
public bool Add(T element) {
    if (this._currentLength < this._maxLength) {
        this._data[this._currentLength] = element;
        this._currentLength++;
        return true;
    }

    Console.WriteLine("元素已满！！");
    return false;
}

//添加元素

public bool Add(T element) {

if (this._currentLength < this._maxLength) {

this._data[this._currentLength] = element;

this._currentLength++;

return true;

}

Console.WriteLine("元素已满！！");

return false;

}

为线性表中添加元素

这个很简单

①先判断一下线性表是否已满，满了给出提示

②如果没有满，则将元素放到最后

③将线性表当前元素长度自加

//插入元素
public bool Insert(int index, T element) {
    if (index < 1 || index > this._currentLength) {
        Console.WriteLine("索引非法！");
        return false;
    }

    if (this._currentLength < this._maxLength) {
        for (int i = this._currentLength-1; i >= index-1; i--) {
            this._data[i + 1] = this._data[i];
        }

        this._data[index - 1] = element;
        this._currentLength++;
        return true;
    }

    Console.WriteLine("不能向已满的表插入元素！");
    return false;
}

//插入元素

public bool Insert(int index, T element) {

if (index < 1 || index > this._currentLength) {

Console.WriteLine("索引非法！");

return false;

}

if (this._currentLength < this._maxLength) {

for (int i = this._currentLength-1; i >= index-1; i--) {

this._data[i + 1] = this._data[i];

}

this._data[index - 1] = element;

this._currentLength++;

return true;

}

Console.WriteLine("不能向已满的表插入元素！");

return false;

}

向线性表中插入元素

①检查索引是否合法，查看是否在已有元素的范围之内

②判断线性表是否已满，满了就给出提示

③如果没满，则从最后一个元素遍历到第i个元素，将它们分别向后移动一位

④向空出的第i位元素插入元素element

⑤线性表的长度+1

//通过索引删除元素
public T DeleteByIndex(int index) {
    if (index < 1 || index > this._currentLength) {
        Console.WriteLine("索引非法！");
        return default(T);
    }

    T deleteData = this._data[index - 1];

    for (int i = index - 1; i < this._currentLength - 1; i++) {
        this._data[i] = this._data[i + 1];
    }
    this._currentLength--;
    return deleteData;
}

//通过索引删除元素

public T DeleteByIndex(int index) {

if (index < 1 || index > this._currentLength) {

Console.WriteLine("索引非法！");

return default(T);

}

T deleteData = this._data[index - 1];

for (int i = index - 1; i < this._currentLength - 1; i++) {

this._data[i] = this._data[i + 1];

}

this._currentLength--;

return deleteData;

}

通过索引删除线性表中的元素

①先判断索引是否在线性表的数据区域内

②取出被删除的元素，在最后的时候返回

③从删除元素后一位遍历到最后一个，分别向前移动一位

④线性表的长度减1

//获取元素的索引，从后先前的第一个
public int GetIndexByElement(T element) {
    for (int i = this._currentLength - 1; i >= 0; i--) {
        if (element.Equals(this._data[i])) {
            return i + 1;
        }
    }

    return -1;
}

//获取元素的索引，从后先前的第一个

public int GetIndexByElement(T element) {

for (int i = this._currentLength - 1; i >= 0; i--) {

if (element.Equals(this._data[i])) {

return i + 1;

}

return -1;

}

通过元素，获取到它的索引

这个是从后面先前面遍历

只要找到一个合适的元素

就返回它的索引（只有一个）

否则找不到的话就返回-1

//删除元素
public bool DeleteElement(T element) {
    int index = this.GetIndexByElement(element);
    if (index != -1) {
        this.DeleteByIndex(index);
        return true;
    }

    return false;
}

//删除元素

public bool DeleteElement(T element) {

int index = this.GetIndexByElement(element);

if (index != -1) {

this.DeleteByIndex(index);

return true;

}

return false;

}

通过元素来删除元素

①先从后向前遍历元素，得到相应的索引

②若得到的索引合法，则通过索引删除线性表中的元素

//通过索引获取元素
public bool GetElement(int index, ref T element) {
    if (index < 1 || index > this._maxLength) {
        Console.WriteLine("索引非法！");
        return false;
    }
    element = this._data[index - 1];
    return true;
}

//通过索引获取元素

public bool GetElement(int index, ref T element) {

if (index < 1 || index > this._maxLength) {

Console.WriteLine("索引非法！");

return false;

}

element = this._data[index - 1];

return true;

}

通过索引取出元素的值

①向判断索引是否在已有数据域（数组）内

②如果是，取出相应的位置的值

//请空表
public void Clear() {

    for (int i = 0; i < this._currentLength; i++) {
        this._data[i] = default(T);
    }

    this._currentLength = 0;
}

//获取线性表元素的个数
public int GetListLength() {
    return this._currentLength;
}

//获取线性表元素的允许的最大个数
public int GeiListMaxLength() {
    return this._maxLength;
}

//请空表

public void Clear() {

for (int i = 0; i < this._currentLength; i++) {

this._data[i] = default(T);

}

this._currentLength = 0;

}

//获取线性表元素的个数

public int GetListLength() {

return this._currentLength;

}

//获取线性表元素的允许的最大个数

public int GeiListMaxLength() {

return this._maxLength;

}

这个就不说了

下面测试一下这个顺序储存结构的线性表

static void TestMyList() {

    //增加元素到最大值
    MyList<int> maxList = new MyList<int>(3);
    maxList.Add(2);
    maxList.Add(3);
    maxList.Add(6);
    PrintList(maxList, "添加过量元素前：");
    maxList.Add(8);
    PrintList(maxList, "添加过量的元素后：");
    Console.WriteLine();

    //插入元素
    MyList<int> myList = new MyList<int>();
    myList.Add(5);
    myList.Add(10);
    myList.Add(22);
    PrintList(myList, "插入元素前：");
    myList.Insert(2, 30);
    PrintList(myList, "在索引2插入元素30 ：");
    Console.WriteLine();

    //向已满线性表中插入元素
    PrintList(maxList, "已满线性表插入之前：");
    maxList.Insert(2, 30);
    PrintList(maxList, "向已满线性表索引2插入30：");
    Console.WriteLine();

    //通过索引删除元素
    PrintList(myList, "删除元素之前：");
    myList.DeleteByIndex(2);
    PrintList(myList, "删除索引2的元素后：");
    Console.WriteLine();

    //通过元素删除
    myList.Add(10);
    myList.Add(3);
    PrintList(myList, "通过元素删除之前：");
    myList.DeleteElement(10);
    PrintList(myList, "通过元素删除之后：");
    Console.WriteLine();

    //错误索引测试
    int someElement = 0;
    myList.GetElement(200, ref someElement);
    myList.GetElement(-20, ref someElement);
    myList.DeleteByIndex(100);
    myList.Insert(-2, 10);
}

static void PrintList(MyList<int> l, string text = "输出：") {
    int data = 0;

    Console.Write(text);
    for (int i = 0; i < l.GetListLength(); i++) {
        l.GetElement(i + 1, ref data);
        Console.Write(data.ToString() + " ");
    }
    Console.WriteLine();
}

static void TestMyList() {

//增加元素到最大值

MyList<int> maxList = new MyList<int>(3);

maxList.Add(2);

maxList.Add(3);

maxList.Add(6);

PrintList(maxList, "添加过量元素前：");

maxList.Add(8);

PrintList(maxList, "添加过量的元素后：");

Console.WriteLine();

//插入元素

MyList<int> myList = new MyList<int>();

myList.Add(5);

myList.Add(10);

myList.Add(22);

PrintList(myList, "插入元素前：");

myList.Insert(2, 30);

PrintList(myList, "在索引2插入元素30 ：");

Console.WriteLine();

//向已满线性表中插入元素

PrintList(maxList, "已满线性表插入之前：");

maxList.Insert(2, 30);

PrintList(maxList, "向已满线性表索引2插入30：");

Console.WriteLine();

//通过索引删除元素

PrintList(myList, "删除元素之前：");

myList.DeleteByIndex(2);

PrintList(myList, "删除索引2的元素后：");

Console.WriteLine();

//通过元素删除

myList.Add(10);

myList.Add(3);

PrintList(myList, "通过元素删除之前：");

myList.DeleteElement(10);

PrintList(myList, "通过元素删除之后：");

Console.WriteLine();

//错误索引测试

int someElement = 0;

myList.GetElement(200, ref someElement);

myList.GetElement(-20, ref someElement);

myList.DeleteByIndex(100);

myList.Insert(-2, 10);

}

static void PrintList(MyList<int> l, string text = "输出：") {

int data = 0;

Console.Write(text);

for (int i = 0; i < l.GetListLength(); i++) {

l.GetElement(i + 1, ref data);

Console.Write(data.ToString() + " ");

}

Console.WriteLine();

}

输出为

发表评论取消回复

登录 注册 找回密码

登录注册找回密码