线性表之顺序表

2019-03-09 本文已影响0人此间不留白

基本概念

线性表(Liner List)是最常用，最简单的一组数据结构，线性表表示的是有n个相同特性的数据元素a[1],a[2],a[3]……a[n-1],a[n]所构成的有限序列。线性表具有如下特点：
线性表的相邻元素之间存在着序偶关系，存在着一个唯一没有前驱(头的的数据元素，存在着一个唯一没有后继(尾)的数据元素，除此之外，每个元素都存在唯一的直接前驱和直接后继元素。
这种所谓的线性和非线性只是按照其存储的逻辑层次讨论的，而不是物理存储层次。就其逻辑存储结构上可以有以下分类：

一般线性表：所谓一般线性表是指可以自由的增加或者删除结点，比如数组，链表。
受限线性表：而受限线性表表示只能按照一定规则对结点数据进行操作，比如栈和队列。

线性表的顺序表示和实现

线性表的顺序表示是指将所有数据存储到物理地址连续的存储单元中，以物理地址的相邻表示数据元素之间的逻辑关系，可以随机存取任一元素，比如C语言中的数组。

接口定义

顺序表的接口定义如下代码所示：


#define bool int
#define false 0
#define true 1
# define LIST_INIT_SIZE 100 //初始空间
typedef struct {
    int *elem; //存储空间基址
    int length; //当前长度
    int listSize; //当前分配的存储容量
}SqList;

SqList initList(); //初始化顺序表
void display(SqList list); //显示所有元素
SqList insertList(SqList list, int i, int e); //在第i个位置插入一个元素e
SqList removeList(SqList list, int i, int e);//删除第i个位置的元素
int locateList(SqList list, int e,int low,int high); //查找元素，返回其索引
SqList updateList(SqList list, int i, int e,int newE);//将e修改为newE
void sortList(SqList list); //插入排序

接口实现

根据以上接口，则有则有如下实现

初始化
初始化代码如下所示，根据要求，需要对整个结构体的初始值进行设置，如下代码所示;

SqList initList()
{
    SqList list;
    list.elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int));
    if (!list.elem)
    {
        exit(0);
    }
    else
    {
        list.length = 0;
        list.listSize = LIST_INIT_SIZE;
        return list;
    }
}

插入元素
顺序表在其指定位置需入一个元素，因为其顺序存储的特点，相邻的数据元素在物理位置上也是相邻的，因此，必须通过移动元素才能反映这个逻辑关系的变化，为了在顺序表的特定位置插入一个元素，需要将顺序表这个特定位置之后的所有元素都向后移动一个位置。具体实现如下代码所示;

SqList insertList(SqList list, int i, int e)
{
    if (i<1 || i>list.length + 1)
        exit(0);
    if (list.length >= list.listSize)  //重新分配一次空间
    {
        int *newBase = (int *)realloc(list.elem, (list.listSize * 2) * sizeof(int));
        if (!newBase)
        {
            exit(0);
        }
        list.elem = newBase;
        list.listSize = list.listSize * 2;
    }
    for (int j = list.length - 1; j >= i - 1; j--)
    {
        list.elem[j + 1] = list.elem[j];

    }
    list.elem[i - 1] = e;
    list.length++;
    return list;
}

注意：如以上代码所示，连续插入元素，可能会导致存储空间不足的问题，因此，每次插入前，我们需要判断存储空间是否足够，如果不足，需要，重新增加新的空间大小，从算法的时间复杂度的角度考虑，我们可以将其在原来大小的基础上扩大2倍。

删除元素
删除元素与增加一个元素很相似，也要注意顺序表的长度会发生变化，同样需要移动元素，与增加元素相比，删除元素需要将所删除元素位置之后的所有元素都要向前移动一个位置。具体算法实现，如下代码所示：

SqList removeList(SqList list, int i)
{
    if (i > list.length || i < 1)
    {
        printf("位置不存在");
        exit(0);
    }
    
    for (int j = i; j < list.length; j++)
    {
        list.elem[j-1] = list.elem[j];
    }
    list.length--;
    return list;

元素排序
排序算法应用十分广泛，排序算法能够使得在处理数据时更加高效，快捷。顺序表的排序算法如下所示：

void sortList(SqList list)
{
    for (int j = 1; j < list.length; j++)
    {
        int key = list.elem[j];
        int i = j - 1;
        while (i >= 0 && list.elem[i] > key)
        {
            list.elem[i + 1] = list.elem[i];
            i = i - 1;
        }
        list.elem[i + 1] = key;
    }

}

以上代码中的算法是插入排序法，常见的排序算法还有冒泡排序，选择排序，归并排序等，之所以采用插入排序是因为插入排序是【算法导论】中的第一个算法，印象深刻！

插入排序基本思想如下所示：

将第一个元素标记为已排序；
遍历每个没有排序过的元素；
“提取” 元素 key；
i = 最后排序过元素的指数到 0 的遍历
如果现在排序过的元素 > 提取的元素，将排序过的元素向右移一格；否则，插入提取的元素。
实现过程可以用如下动态图表示：

插入排序示意图

查找元素
在顺序表中，需要给出一个指定元素，返回该元素的位置。本次实现过程采用的是二分查找方法，二分查找法有两种方法实现，一种是循环方法，一种是递归法，本次算法实现采用的是递归方法，具体实现过程如下所示：

int locateList(SqList list, int e,int low,int high)
{
    sortList(list);
    if (low > high)
    {
        printf("元素不存在\n");
    }
    int mid = (low + high) / 2;
    if (e == list.elem[mid])
    {
        return mid;
    }
    else if (e < list.elem[mid])
        return locateList(list, e, low, high = mid - 1);
    else
        return locateList(list, e, low = mid + 1, high);

}

修改指定位置的元素
根据需求，需要修改指定位置的元素，其算法原理是先通过二分查找方法寻得指定元素的索引，再通过索引的取修改指定元素吗，具体实现方法如下所示：

SqList updateList(SqList list, int e, int newE)
{
    int locate = locateList(list, e, 0, list.length-1);
    list.elem[locate - 1] = newE;
    return list;

}

参考教材：
数据结构（C语言版）清华大学出版社
算法导论机械工业出版社
数据结构学习网站：https://visualgo.net

线性表之顺序表

基本概念

线性表的顺序表示和实现

接口定义

接口实现

猜你喜欢

热点阅读