C/C++线性表实现(顺序存储与链式存储)

Miracle • 2023-04-16 • C++, 数据结构与算法 • 608 阅读

概述

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。常采用顺序存储和链式存储。

存储结构

顺序存储

顺序存储结构的线性表也称顺序表。

一般地，以LOC(a1)表示线性表中第一个元素的存储位置，在顺序存储结构中，第i个元素ai的存储位置为：

LOC(ai)=LOC(a1)+(i-1)*L        （ L表示单个数据元素所占的字节数。）

线性表采用顺序存储结构的优点是可以随机存取表中的元素，不用通过遍历来获取指定位置。缺点是插入和删除元素需要移动元素。

在表长为n的线性表进行插入操作时，共有n+1个插入位置。在位置1插入元素时，（将新元素插入到位置i前，即插入到ai前。）需要移动包括a1之后的所有元素，即表中的n个元素都需要移动。在位置n+1插入元素时，不需要移动任何元素。

等概率情况下，插入新元素需要移动元素个数的期望值为  ∑ p1*(n-i+1)=n/2   (i∈[1,n])

同理，等概率情况下，删除元素需要移动元素个数的期望值为  ∑ q1*(n-i)=(n-1)/2   (i∈[1,n])

代码

顺序表结构声明

#define MAXCapacity 100
template<class ElementType>
class seqlist
{
private:
    /* data */
    ElementType* first;
    int length;
public:
    seqlist(/* args */);
    ~seqlist();
    int GetLength()
    {
        return length;
    }
    bool ADD(ElementType value);
    bool RemoveAt(int index);
    bool Remove(ElementType value);
    bool Insert(int index, ElementType value);
    bool IsOverBound(int index);
    bool IsEmpty();
    ElementType get(int index);
    bool modify(int index,ElementType new_value);
};
template<typename ElementType>
seqlist<ElementType>::seqlist(/* args */)
{
    length=0;
    first=NULL;
}

template<typename ElementType>
seqlist<ElementType>::~seqlist()
{
}

添加元素：

 

template<typename ElementType>
bool seqlist<ElementType>::ADD(ElementType value)
{
    if (length>=MAXCapacity)
    {
        return 0;
    }
    if (first==NULL)
    {
        //如果数组指针为空，即没有分配内存。则动态分配内存。
        first=(ElementType*)malloc(sizeof(ElementType)*MAXCapacity);
        *first=value;
        //使用length计数 表长
        length+=1;
        return 1;
    }
    ElementType *p;
    //指针后移 指向第length位置的内存空间
    p=first+length;
    *p=value;
    length+=1;
    return 1;
}
  • 如果数组指针为空，即没有分配内存。则动态分配内存。
  • 新元素进入，指针后移 指向第length位置的内存空间。
删除元素：
template<typename ElementType>
bool seqlist<ElementType>::RemoveAt(int index)
{
    if (IsOverBound(index))
    {
        throw "发生边界错误";
    }
    for (size_t i = index+1; i < length; i++)
    {
        *(first+i-1)=*(first+i);
    }
    length-=1;
    *(first+length)=NULL;
}

template<typename ElementType>
bool seqlist<ElementType>::Remove(ElementType value)
{
    //FIND Return Index and del
}

插入新元素：

template<typename ElementType>
bool seqlist<ElementType>::Insert(int index,ElementType value)
{
    if (IsOverBound(index))
    {
        throw "发生边界错误";
    }
    if (length>=MAXCapacity)
    {
        throw "溢出";
    }
    ElementType *p;
    for (int i = length-1; i >=index; i--)
    {
        p=first+i+1;
        *p=*(first+i);
    }
    *(first+index)=value;
    length+=1;
}

修改元素：

template<typename ElementType>
bool seqlist<ElementType>::modify(int index,ElementType new_value)
{
    if (IsOverBound(index))
    {
        throw;
    }
    *(first+index)=new_value;
    return 1;
}

主程序入口测试：

/*
 * @Author       : unity-mircale 9944586+unity-mircale@user.noreply.gitee.com
 * @Date         : 2023-04-06 18:15:07
 * @LastEditors: unity-mircale 9944586+unity-mircale@user.noreply.gitee.com
 * @LastEditTime: 2023-04-16 14:52:03
 * @FilePath     : \DS1\source\Program.cpp
 * @Description  : 
 * 
 * Copyright (c) 2023 by ${git_name_email}, All Rights Reserved. 
 */
#include<stdio.h>
#include <stdlib.h>
#include <iostream>
#include "seqlist.h"
using namespace std;
template<class T>
void PRINTF_SEQUENCE(seqlist<T> seq);
int main()
{
    seqlist<int> seq;
    seq.ADD(10);
    seq.ADD(11);
    seq.ADD(12);
    PRINTF_SEQUENCE(seq);
    printf("MODIFY SEQUENCELIST:\n");
    seq.modify(1,12);
    PRINTF_SEQUENCE(seq);
    printf("Insert SEQUENCELIST:\n");
    seq.Insert(1, 11);
    PRINTF_SEQUENCE(seq);
    printf("Remove SEQUENCELIST:\n");
    seq.RemoveAt(1);
    PRINTF_SEQUENCE(seq);
    system("pause");
    return 0;
}
template<class T>
void PRINTF_SEQUENCE(seqlist<T> seq)
{
    for (int i = 0; i < seq.GetLength(); i++)
    {
        cout<<seq.get(i)<<endl;
    }
}

 

链式存储

链式存储结构的线性表也称链表。

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，因此存储数据元素的同时必须存储元素之间的逻辑关系。对数据元素ai来说，除存储其本身的信息之外，还需要存储一个指示它直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素ai的存储结构，称为结点（node）。结点之间通过指针域构成链表，若结点中只有一个指针域，则称线性链表或单链表。
结点：包含数据域与指针域。

当线性表采用链表存储结构时，不能对数据元素进行随机访问，但是有插入和删除操作不需要移动元素的优点。

链表结构还分双向链表、循环链表、静态链表。

  • 双向链表：每个结点包含它的直接前驱结点指针与直接后续结点指针。
  • 循环链表：表尾结点的指针指向链表中的第一个结点，构成循环链表。
  • 静态链表：借助数组来描述线性表的链式存储结构。

为方便存取，示例增加了一个表尾指针，指向表尾的最后一个结点。并连接头结点。（循环链表）

代码

结点结构定义：

struct LinkNode
    {
        ElementType data;
        LinkNode* next=nullptr;
    };

链表结构声明：

 

template<typename ElementType>
class seq_LinkList
{
protected:
    struct LinkNode
    {
        ElementType data;
        LinkNode* next=nullptr;
    };
    LinkNode* head;
    LinkNode* last;
    int length=0;
    LinkNode* GetLastNode()
    {
        return last;
    }
    LinkNode* FindIndex(int index)
    {
        if (isOverBound(index))
        {
            throw;
        }
        if (index == 0)
        {
            return head->next;
        }
        if (index == length - 1)
        {
            return last->next;
        }
        LinkNode *p;
        p = head->next;
        for (int i = 1; i <= index; i++)
        {
            p = p->next;
        }
        return p;
    }

public:

    seq_LinkList(/* args */);
    ~seq_LinkList();
    int ADD(ElementType value);
    bool REMOVEAT(int index);
    bool INSERT(int index,ElementType value);
    ElementType get(int index);
    int getlength();
    bool isEmpty();
    bool isOverBound(int index);
    
};



template<typename ElementType>
seq_LinkList<ElementType>::seq_LinkList(/* args */)
{
    // head=(LinkNode*)malloc(sizeof(LinkNode)); //malloc不会自动初始化类中成员
    head=new LinkNode();
    last=new LinkNode();
    // last=(LinkNode*)malloc(sizeof(LinkNode));
}

template<typename ElementType>
seq_LinkList<ElementType>::~seq_LinkList()
{
}

添加元素：

template<typename ElementType>
int seq_LinkList<ElementType>::ADD(ElementType value)
{
    LinkNode* node=(LinkNode*)malloc(sizeof(LinkNode));
    node->data=value;
    length+=1;
    if (isEmpty())
    {
        //head和last指针的next指向头结点
        head->next=node;
        node->next=head->next;
        last->next=node;
        return 0;
    }
    //最后一个结点的直接后续指向新的结点
    last->next->next=node;
    //新节点直接后续指向头结点。
    node->next=head->next;
    //last指针的next指向新结点
    last->next=node;
    return length-1;
}
  • 链表为空时，head和last指针的next指向头结点
  • 非空时，最后一个结点的直接后续指向新的结点。新节点直接后续指向头结点。更新last指针指向

删除结点：

template<typename ElementType>
bool seq_LinkList<ElementType>::REMOVEAT(int index)
{
    LinkNode *front;
    LinkNode *node;
    if (index==0)
    {
        front=head;
    }
    else
    {
        //查找索引i的结点的前一个结点。
        front = FindIndex(index-1);
    }
    //得到索引i的结点
    node = front->next;
    //更新前一个结点的直接后续为要删除结点的直接后续。
    front->next=node->next;
    //如果要删除的结点是表尾结点，则更新last指向前一个结点。
    if (node==last->next)
    {
        last->next=front;
    }
    
    length-=1;
    free(node);
    
}
  • 先查找索引i的结点的前一个结点，根据链式的逻辑关系也得到了索引i的结点。
  • 更新前一个结点的直接后续为要删除结点的直接后续。
  • 如果要删除的结点是表尾结点，则更新last指向前一个结点。

 

插入新元素：

template<typename ElementType>
bool seq_LinkList<ElementType>::INSERT(int index,ElementType value)
{
    LinkNode *front;
    LinkNode* node=(LinkNode*)malloc(sizeof(LinkNode));
    node->data=value;
    if (index==0)
    {
        front=head;
    }
    else
    {
        //查找索引i的结点的前一个结点。
        front = FindIndex(index-1);
    }
    //新节点的直接后续先指向前一个节点的直接后续，即索引i对应的结点。
    node->next=front->next;
    //索引i结点的前一个结点的直接后续更新为新节点。
    front->next=node;
    length+=1;
}
  • 先查找索引i的结点的前一个结点。
  • 新节点的直接后续先指向前一个节点的直接后续，即索引i对应的结点。
  • 索引i结点的前一个结点的直接后续更新为新节点。
主程序入口测试：
/*
 * @Author       : unity-mircale 9944586+unity-mircale@user.noreply.gitee.com
 * @Date         : 2023-04-06 20:25:10
 * @LastEditors  : unity-mircale 9944586+unity-mircale@user.noreply.gitee.com
 * @LastEditTime : 2023-04-07 22:12:12
 * @FilePath     : \DS2\source\Program.cpp
 * @Description  : 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <stdlib.h>
#include <iostream>
#include "seq_LinkList.h"
#include "seq_IntegerLinkList.h"
#include "stdio.h"
using namespace std;
template<class T>
void PRINTF_SEQUENCE(seq_LinkList<T> seq);
void Test01();
void Test02();
int main()
{
Test02();
system("pause");
}
template<class T>
void PRINTF_SEQUENCE(seq_LinkList<T> seq)
{
    int length=seq.getlength();
    for (int i = 0; i < length; i++)
    {
        cout<<seq.get(i)<<endl;
    }
}
void Test01()
{
    seq_LinkList<int> seq;
seq.ADD(11);
seq.ADD(12);
seq.ADD(13);

PRINTF_SEQUENCE(seq);
seq.INSERT(1,22);
cout<<"INSERT:"<<endl;
PRINTF_SEQUENCE(seq);
seq.REMOVEAT(2);
cout<<"REMOVEAT:"<<endl;
PRINTF_SEQUENCE(seq);
}
void Test02()
{
seq_IntegerLinkList seqIntegerList;
seqIntegerList.ADD(15);
seqIntegerList.ADD(11);
seqIntegerList.ADD(13);
PRINTF_SEQUENCE(seqIntegerList);
cout<<"Sorted:"<<endl;
seqIntegerList.Sorted();
PRINTF_SEQUENCE(seqIntegerList);
seqIntegerList.INSERT(1,22);
seqIntegerList.INSERT(1,1);
seqIntegerList.INSERT(1,14);
cout<<"INSERT:"<<endl;
PRINTF_SEQUENCE(seqIntegerList);
cout<<"Sorted:"<<endl;
seqIntegerList.Sorted();
PRINTF_SEQUENCE(seqIntegerList);
seqIntegerList.REMOVEAT(2);
cout<<"REMOVEAT:"<<endl;
PRINTF_SEQUENCE(seqIntegerList);
}

测试结果：

示例文件

]DS1.线性表-顺序表.zip
来源：诚通网盘 | 提取码：unitymake
作者：Miracle
来源：麦瑞克博客
链接：https://www.playcreator.cn/archives/programming-life/datastruct/2993/
本博客所有文章除特别声明外，均采用CC BY-NC-SA 4.0许可协议，转载请注明！
THE END
分享
打赏
海报
C/C++线性表实现(顺序存储与链式存储)
概述 线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。常采……
<<上一篇
下一篇>>
文章目录
关闭
目 录