【数据结构】线性表

【数据结构】线性表

Turbo 308 2022-10-01

【数据结构】线性表

前言

线性表是一种简单的，也是最基本的线性结构。线性表的特点是数据元素之间仅具有单一前驱和后继关系，在一个线性表中数据元素的类型必须是相同的。

一、线性表的基本概念

  • 线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为：L = (a1, a2, a3, …,ai, …, an)。其中ai是序号为i的数据元素(i=1,2,…,n)。a1称为表头元素，an是表尾元素；
  • 线性表中所含数据元素的个数n称为线性表的长度，n=0时称为该线性表为空表；
  • 线性表中相邻元素之间存在着顺序关系，ai-1称为ai的直接前驱(简称为前驱)，ai+1称为ai的直接后继(简称为后继)。
  • 非空线性表的特点如下：
    1. 有且仅有一个表头结点a1，它没有前驱，而仅有一个后继a2。
    2. 有且仅有一个表尾结点a2，它没有后继，而仅有一个前驱an-1。
    3. 其余的结点ai(2<=i<=n-1)都有且仅有一个前驱ai-1和一个后继ai+1。
  • 线性表的长度可以根据需要加长或缩短，即对线性表的数据元素不仅可以访问，还可以进行插入和删除等操作。

二、线性表的存储结构

线性表有两种存储结构：顺序存储和链式存储。

2.1 顺序存储结构

线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这个存储形式存储的线性表又称为顺序表。
设顺序表第一个元素的存储地址为Loc(a1)，每个数据元素占d个存储单位，则第i个数据元素的地址为：Loc(ai)=Loc(a1)+(i-1)*d 1<=i<=n

2.2 顺序表的类模板：

template <class T, int MaxSize>
class SeqList
{
    T data[MaxSize];                         // 用于存放数据元素的数组
    int length;                              // 顺序表中元素的个数
public :
    SeqList();                               // 无参构造函数
    SeqList(T a[], int n);                   // 有参构造函数 
    int ListLength();                        // 求线性表的长度
    T Get(int pos);                          // 按位查找，取顺序表的第pos个元素
    int Locate(T item);                      // 按值查找，求顺序表中值为item的元素序号
    void PrintSeqList();                     // 遍历顺序表，按序号依次输出各元素
    void Insert(int i, T item);              // 在顺序表中的第i个位置插入值为item的元素
    T Delete(int i);                         // 删除顺序表的第i个元素
}

注 其中MaxSize表示数组的最大容量。同时由于顺序表要进行插入、删除等操作，因此顺序表的长度是可变的，可用一个变量length来记录当前顺序表中元素的个数。

2.3 顺序表的操作算法

2.3.1 无参构造函数

template<class T, int MaxSize>
SeqList<T, Maxsize>:: SeqList()
{
    length = 0;
}

2.3.2 有参构造函数

template<class T, int MaxSize>
SeqList<T, MaxSize>::SeqList(T a[], int n)
{
    if(n>MaxSize)
    {
        cerr<<"参数非法";
        exit(1);
    }
    for(i=0;i<n;i++)
        data[i] = a[i];
    length = n;
}

2.3.3 求顺序表的长度

template <class T, int MaxSize>
int SeqList<T, MaxSize>::ListLength()
{
    return length;
}

2.3.4 按位查找

template <class T, int MaxSize>
T SeqList<T, MaxSize>::Get(int pos)
{
    if(pos<1 || pos>length)
    {
        cerr<<"查找位置非法";
        exit(1);
    }
    return data[pos-1];
}

2.3.5 按值查找

template <class T, int MaxSize>
int SeqList<T, MaxSize>::Locate(T item)
{
    for(i=0;i<length;i++) 
    {
        if(data[i] == item)
            return i+1;
        return 0;
    }
}

2.3.6 遍历顺序表

template <class T, int MaxSize>
void SeqList<T, MaxSize>::PrintSeqList()
{
    for(i=0;i<length;i++)
        cout<<data[i]<<endl;
}

2.3.7 插入元素

  • 检查顺序表的存储空间是否已到最大值，若是则停止插入，抛出上溢异常；否则执行下一步
  • 检查插入位置i是否合法，若不合法，则停止插入，抛出插入异常；否则执行下一步
  • 从最后一个元素向前直至第i个元素为止，将每一个元素均后移一个存储单元，将第i个元素的存储位置空出
  • 将新元素item写入到第i个元素处，即下标为i-1的位置
  • 将顺序表的长度+1
template <class T, int MaxSize>
void SeqList<T, MaxSize>:: Insert(int i, T item)
{
    if(length>=MaxSize)
    {
        cerr<<"上溢";
        exit(1);
    }
    if(i<1 || i>length +1)
    {
        cerr<< "插入位置非法";
        exit(1);
    }
    for(j=length-1;j>=i-1;j--)
        data[j+1] = data[j];
    data[i-1] = item;
    length++;
}

2.3.8 删除元素

  • 检查顺序表是否为空，若是则抛出下溢异常；否则执行下一步
  • 检查删除位置i是否合法，若不合法，则抛出删除位置异常；否则执行下一步
  • 取出被删除元素
  • 从第i+1个元素向后直至最后一个元素为止，将每个元素均前移一个存储位置
  • 将顺序表的长度-1
  • 返回被删除元素的值
template <class T, int MaxSize>
T SeqList<T, MaxSize>:: Delete(int i)
{
    if(length==0)
    {
        cerr<<"下溢";
        exit(1);
    }
    if(i<1 || i>length)
    {
        cerr<< "删除位置非法";
        exit(1);
    }
    x = data[i-1];
    for(j=i;j<length;j++)
        data[j-1] = data[j];
    length--;
    return x;
}

2.4 链式存储结构

线性表的链式存储结构又称为链表，它用一个物理上不一定相邻的存储单元来存储线性表中的数据元素。
为了建立起数据元素之间的逻辑关系，对线性表中的每个数据元素ai，除了存放数据元素的自身信息外，还需要存储其后继元素所在的地址信息，这个地址信息称为指针。数据元素自身信息和指针这两部分组成了数据元素的存储映像，称为结点。一个结点可以包含一个或多个指针。含有一个指针使其指向后继的称为单链表，含有两个指针分别指向前驱和后继的称为双向链表。

2.4.1 单链表

在单链表中，每个数据元素由一个结点表示，该结点包含两部分信息：数据元素自身的信息和该元素后继的存储地址。数据域存放数据元素信息，指针域存放其后继地址如下图所示：

data next

结点定义如下：

template<class T>
struct Node
{
    T data;
    Node<T> * next;
}

单链表的类模板

template<class T>
class LinkList
{
    Node<T> *head;                      // 单链表的头指针
public:
    LinkList();                         // 建立带头结点的空链表
    LinkList(T a[], int n);             // 建立有n个元素的单链表
    ~LinkList();                        // 析构函数
    int ListLength();                   // 求单链表的长度
    T Get(int pos);                     // 按位查找，取单链表中第pos个结点的元素值
    int Locate(T item);                 // 按值查找，求单链表中值为item的元素序号
    void PringLinkList();               // 遍历单链表，按序号依次输出各元素
    void Insert(int i, T item);         // 在单链表中第i个位置插入元素值为item的结点
    T Delete(int i);                    // 在单链表中删除第i个结点
}

2.4.2 循环链表

将单链表最后一个节点的指针域指向头结点，称为单循环链表，简称循环链表。
循环链表的操作与单链表类似，区别仅在于判断单链表的条件是指针是否为空，而判断循环链表结束的条件是指针是否指向头结点。
在单链表中只能从头结点开始遍历(依次访问)整个链表，但在循环链表中则可以从任意结点开始遍历整个链表。不仅如此，如果需要对链表常做的操作是在表尾进行，那么可以改变一下链表的标识方法，不用头指针而用一个指向表尾结点的指针来标识，这有助于提高操作效率。

2.4.3 双向链表

双向链表通常也是用头指针标识，增加头结点同样可以简化双向链表的操作。如果已知某结点的指针为p，则其后继结点的指针是p->next，其前驱结点的指针是p->prior。

2.4.4 链表的操作方法

单链表的初始化——构造函数
单链表的无参构造函数

template <class T>
LinkList<T>::LinkList()
{
    head = new Node<T>;
    head->next = NULL;
}

单链表的有参构造函数

template<class T>
LinkList<T>::LinkList(T a[], int n)
{
    head = new Node<T>;           // 生成头结点
    rear = head;                  // 指针rear用于指向当前单链表的最后一个结点
    for( i=0;i<n;i++ )            // 为每个数组元素生成一个新结点，并插入到链表尾部
    {
        s = new Node<T>;
        s->data = a[i];           // 指针s用于指向新结点
        rear->next = s;
        rear = s;
    }
    rear->next = NULL;            // 单链表建立完毕，将最后一个结点的指针域置空
}

上述算法采用了尾部插入法，即每次生成的新结点均插入在链表的尾部。
求单链表的长度
设置一个指针，从单链表第一个数据结点开始向后扫描，直至单链表结束，在扫描过程中，利用计数器同步计数。

template <class T>
int LinkList <T>:: ListLength()
{
    num = 0;
    p = head->next;
    while( p )
    {
        p = p->next;
        num ++;
    }
    return num;
}

单链表的按位查找
由于单链表不能像顺序表那样随机访问，而是必须从头指针开始依次访问，因此按位查找算法步骤如下：

  1. 初始化指针p和计数器j；
  2. 当p不为空或j不等于pos时，p后移指向下一个结点，同时j+1；
  3. 若p为空，则抛出查找位置非法异常；否则p指向需要查找的元素，返回p所指向结点的数据；
template <class T>
T LinkList <T>::Get( int pos )
{
    p = head->next;
    j = 1;           // p初始化为第一个数据结点的地址，j初始化为1
    while( p&&j<pos )
    {
        p = p->next;
        j++;
    }
    if( !p || j>pos )
    {
        cerr<<"查找位置非法";
        exit(1);
    }
    else
    {
        return p->data;
    }
}

单链表的按值查找
按值查找将待查找的值item与单链表中的每个结点元素依次进行比较，如果查找到具有item值的元素时，则返回该元素的序号，否则返回值0，表明查找失败。

tempate <class T>
int LinkList <T>::Locate(T item)
{
    p = head->next;
    j = 1;
    while( p && p->data!=item )
    {
        p = p->next;
        j++;
    }
    if( p )
        return j;
    else
        return 0;
}

遍历单链表
遍历单链表依次输出单链表中除头结点外的每个结点的数据域即可。

template <class T>
void LinkList <T>::PrintLinkList()
{
    p = head->next;
    while( p )
    {
        cout<<p->data<<endl;
        p = p->next;
    }
}

单链表的插入
插入操作是指将值为item的新结点插入到单链表第i个位置上。根据插入的方法，可以分为后插和前插两种。
4.6.1 后插法
设p指向单链表中的某个结点，s指向待插入的值为item的新结点，将结点s插入到结点p的后面。

  1. s->next = p->next;
  2. p->next = s;
    注：两个指针的操作顺序不能交换。
    4.6.2 前插法
    设p指向链表中某结点，s指向待插入的值为item的新结点，将结点s插入到结点p的前面；与后插法不同的是，前插法首先要找到结点p的前驱结点q，然后再完成在结点q之后插入结点s。
  3. q = head;
    while( q->next != p )
    q = q->next;
  4. s->next = q->next;
  5. q->next = s;

可以看出，后插的效率比前插的效率高，后插操作的时间复杂度为O(1)，前插操作的时间复杂度为O(n)。

template <class T>
void LinkList <T>::Insert(int i, T item)
{
    p = head;
    j = 0;
    while( p && j<i-1 )           // 找到第i-1个结点的位置
    {
        p = p->next;
        j++
    }
    if( !p )
    {
        cerr<<"插入位置非法";
        exit(1);
    }
    else
    {
        s = new Node<T>;           // 生成元素值为item的新结点s
        s->data = item;
        s->next = p->next;         // 用后插法将s插入到结点p的后面
        p->next = s;
    }
}

单链表删除操作
设q指向单链表中某个结点，要删除结点q，首先要找到结点q的前驱结点p，然后再完成指针的操作即可。

  1. 工作指针p初始化，累加器j清零；
  2. 查找第i-1个结点，并将指针p指向该结点；
  3. 若p为空或p不存在后继结点，则抛出删除位置非法异常；否则删除结点p的后一个结点；
template <class T>
T LinkList <T>::Delete( int i )
{
    p = head;
    j = 0;
    while( p && j<i-1 )           // 查找第i-1个结点
    {
        p = p->next;
        j++;
    }
    if( !p || p->next )
    {
        cerr<<"删除位置非法";
        exit(1);
    }
    else
    {
        q = p->next;
        x = q->next;
        p->next = q->next;
        delete p;
        return x;
    }
}

单链表的析构函数
由于单链表类中由new运算符生成的结点空间无法自动释放，因此需要利用析构函数将单链表的存储空间加以释放。

template <class T>
LinkList <T>:: ~LinkList()
{
    p = head;
    while( p )
    {
        q = p;
        p = p->next;
        delete q;
    }
    head = NULL;
}

单链表的其他操作
逆置单链表

  1. 将逆置后的单链表初始化为一个空表；
  2. 依次删除原单链表中的结点，并将其插入到逆置后单链表的表头，直至原链表为空；
template <class T>
void LinkList <T>::Invert()
{
    p=head->next;
    head->next = NULL;               // 将逆置后的单链表初始化为空表
    while( p!=null )                 // 遍历原单链表的中结点
    {
        q = p;
        p = p->next;
        q->next = head->next;        // 将结点插入到逆置后单链表的表头
        head->next = q;
    }
}

合并有序单链表
已知递增有序的两个单链表L1和L2,要求将L2合并到L1中，且合并后的L1依然保持递增有序。

  1. 初始化指针，使指针p1指向单链表L1的第一个数据结点，p2指向单链表L2的第一个数据结点，指针P3指向单链表L1的头结点；
  2. 当p1和p2都不为空时，如果p1->data小于p2->data，则将p1所指向的结点链入结果有序单链表的表尾，并将指针p1和p3后移；否则，将p2指向的结果链入结果有序单链表的表尾，并将指针p2和p3后移；
  3. 如果p1不为空，则将p1所指向的剩余结点链入结果有序单链表的表尾；如果p2不为空，则将p2所指向的剩余结点链入结果有序单链表的表尾；
void Merge( LinkList &L1, LinkList &L2 )
{
    p1 = L1.head->next;
    p2 = L2.head->next;
    p3 = L1.head;
    while( (p1!=NULL)&&(p2!=NULL) )
    {
        // 处理两个表非空时的情况，p1，p2指向当前需比较的结点
        // p3指向结果有序单链表的表尾
        if( (p1->data) < (p2->data) )
        {
            p3->next = p1;
            p1 = p1->next;
            p3 = p3->next;
        }
        else
        {
            p3->next = p2;
            p2 = p2->next;
            p3 = p3->next;
        }
    }
    if( p1 != NULL )
    {
        p3->next = p1;
    }
    if( p2 != NULL )
    {
        p3->next = p2;
    }
    delete L2.head;
    L2.head = NULL;
}

完结

Data Structure