数据结构:线性表之顺序存储结构

线性表的数据对象集合为 {a1,a2,....an},每个元素的类型均为Datatype。其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

线性表的顺序存储结构的优缺点:

优点:无须为表示表中元素之间的逻辑关系而增加额外的存储空间;可以快速地存取表中任一位置的元素O(1)

缺点:插入和删除操作需要移动大量元素O(n);当线性表长度变化较大时,难以确定存储空间的容量;造成存储空间的“碎片”

示例程序如下(改编自《大话数据结构》):

#include<iostream>
using namespace std;

#define MAXSIZE 20

typedef int ElemType;

typedef struct
{
    ElemType data[MAXSIZE];
    int length;
} SqList;

/* 初始化顺序线性表 */
bool InitList(SqList *ptr)
{
    for (int i = 0 ; i < MAXSIZE; i++)
        ptr->data[i] = 0;
    ptr->length = 0;
    return true;
}

bool ListEmpty(SqList Sq)
{
    if (Sq.length == 0)
        return true;
    else
        return false;
}

bool ClearList(SqList *ptr)
{
    for (int i = 0 ; i < ptr->length; i++)
        ptr->data[i] = 0;
    ptr->length = 0;
    return true;
}
/*用ptr返回Sq中第pos个数据元素的值,注意pos是指位置,第1个位置的数组是从0开始 */
bool GetElem(SqList Sq, int pos, ElemType *ptr)
{
    if (Sq.length == 0 || pos < 1 || pos > Sq.length)
        return false;
    *ptr = Sq.data[pos - 1];
    return true;
}
/*返回Sq中第1个与Elem满足关系的数据元素的位序,若这样的数据元素不存在,则返回值为0 */
int Locate(SqList Sq, ElemType Elem)
{
    for (int i = 0; i < Sq.length; i++)
    {
        if (Sq.data[i] == Elem)
            return i + 1;
    }
    return 0;
}
/*在Sq中第pos个位置之前插入新的数据元素Elem,L的长度加1*/
bool ListInsert(SqList *ptr, int pos, ElemType Elem)
{
    if (ptr->length == MAXSIZE)/* 顺序线性表已经满 */
        return false;
    if (pos < 1 || pos > ptr->length + 1)
        return false;
    if (pos <= ptr->length)
    {
        /* 将要插入位置之后的数据元素向后移动一位 */
        for (int i = ptr->length - 1; i >= pos - 1; i--)
        {
            ptr->data[i + 1] = ptr->data[i];
        }
    }

    ptr->data[pos - 1] = Elem; /* 将新元素插入 */

    ptr->length++;
    return true;
}
/*删除ps的第pos个数据元素,并用pe返回其值,ps的长度减1*/
bool ListDelete(SqList *ps, int pos, ElemType *pe)
{
    if (pos < 1 || pos > ps->length)
        return false;
    *pe = ps->data[pos - 1];
    /* 将删除位置后继元素前移 */
    for (int i = pos; i < ps->length; i++)
        ps->data[i - 1] = ps->data[i];

    ps->length--;

    return true;

}

int ListLength(SqList Sq)
{
    return Sq.length;
}

/*将所有在线性表pb中但不在pa中的元素都插入到pa中*/
void UnionList(SqList *pa, SqList *pb)
{
    int lena = pa->length;
    int lenb = pb->length;
    int item;

    for (int i = 0; i < lenb; i++)
    {
        if (GetElem(*pb, i + 1, &item))
        {
            if (Locate(*pa, item) == 0)
                ListInsert(pa, ++lena, item);
        }
    }

}

int main(void)
{
    SqList Sq;
    InitList(&Sq);
    for (int i = 1 ; i < 5; i++)
        ListInsert(&Sq, i, i);

    if (!ListEmpty(Sq))
    {
        cout << "Sq: " << endl;
        for (int i = 0 ; i < ListLength(Sq); i++)
            cout << Sq.data[i] << ' ';
    }
    cout << endl;

    int pos = Locate(Sq, 2);
    if (pos != 0)
    {
        int result;
        ListDelete(&Sq, pos, &result);
        cout << "delete: " << result << endl;
    }

    if (!ListEmpty(Sq))
    {
        cout << "Sq: " << endl;
        for (int i = 0 ; i < ListLength(Sq); i++)
            cout << Sq.data[i] << ' ';
    }
    cout << endl;

    SqList Sq2;
    InitList(&Sq2);
    for (int i = 1 ; i < 4; i++)
        ListInsert(&Sq2, i, 6);
    ListInsert(&Sq2, 4, 7);
    if (!ListEmpty(Sq2))
    {
        cout << "Sq2: " << endl;
        for (int i = 0 ; i < ListLength(Sq2); i++)
            cout << Sq2.data[i] << ' ';
    }
    cout << endl;

    UnionList(&Sq, &Sq2);

    if (!ListEmpty(Sq))
    {
        cout << "Sq: " << endl;
        for (int i = 0 ; i < ListLength(Sq); i++)
            cout << Sq.data[i] << ' ';
    }
    cout << endl;

    return 0;
}

输出为:

注意:

1、程序中所说的位置pos应是序号加1,如第一个元素序号为0,位置为1。

2、程序中所举的函数是最基本的操作,涉及更复杂的操作可以使用基本操作的组合来完成,如上面的UnionList即求两个线性表集合A和B的并集。

3、初学者易混淆的点是:插入或删除并没有真正进行内存的操作,只是进行了元素的移动,覆盖等,由length成员来记录现在线性表的长度,但总长度是确定的即MAXSIZE,线性表的内存在栈上,函数返回时会被释放。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法与数据结构

PTA 循环单链表区间删除 (15 分)

本题要求实现带头结点的循环单链表的创建和单链表的区间删除。L是一个带头结点的循环单链表,函数ListCreate_CL用于创建一个循环单链表,函数ListDel...

1898
来自专栏苍云横渡学习笔记

【慕课-数据结构-C++语言】线性表篇

线性表是n个数据元素的有限序列。可应用与通讯录、一元多项式等等。 ? 顺序表 新建List.h和List.cpp #List.h #ifndef LIST_H ...

2676
来自专栏Java开发者杂谈

算法之逆序对

算法之逆序对 逆序对问题 ​ 假设A[1..n]是一个有n个不同数的数组。若iA[j],则对偶(i, j)称为A的一个逆序对(inversion)。 列出数组{...

3439
来自专栏JackeyGao的博客

Python eval安全案例

关于Python的eval函数, 大家一致的避免使用。 但有时候必须使用, 怎么保证安全呢? 下面我用一个案例来避免eval潜在的风险。 当然这只是其中的一种。

663
来自专栏从流域到海域

《数据结构》 单链表常用操作代码集合

Ps:每段代码中,添加了Solo署名的是博主自己写的,其余来自课本或老师。 //单链表存储结构 typedef struct Node //结点类型定义 ...

1956
来自专栏恰同学骚年

剑指Offer面试题:31.两个链表的第一个公共节点

  碰到这道题,很多人的第一反应就是蛮力法:在第一链表上顺序遍历每个结点,每遍历到一个结点的时候,在第二个链表上顺序遍历每个结点。如果在第二个链表上有一个结点和...

501
来自专栏软件开发 -- 分享 互助 成长

欧拉回路

一、定义 欧拉回路:图G,若存在一条路,经过G中每条边有且仅有一次,称这条路为欧拉路,如果存在一条回路经过G每条边有且仅有一次, 称这条回路为欧拉回路。具有欧拉...

1849
来自专栏数据结构与算法

1006. 捡石头

1006. 捡石头 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 憨厚的老农夫昨天捡到了3...

2735
来自专栏Python

python——内置函数和匿名函数

内置函数 接下来,我们就一起来看看python里的内置函数。截止到python版本3.6.2,现在python一共为我们提供了68个内置函数。它们就是pytho...

17910
来自专栏我是业余自学C/C++的

循环链表(测试代码,Qt5.1 for windows)

2004

扫码关注云+社区