线性表

线性表抽象数据类型

定义

线性表是可以在任意位置插入和删除数据元素操作，由n(n>=0)个相同数据元素a0,a1,a3……an-1组成的线性结构

线性表抽象数据类型

• 数据集合:DataType
• 操作集合:
  1. ListInitiate(L)初始化
  2. ListInsert(L,i,x)插入
  3. ListLength(L)求当前数据元素个数
  4. ListDelete(L,i,x)删除
  5. ListGet(L,i,x)求数据元素

顺序表类

顺序表的存储结构

使用数组
数组把线性表的数据元素存储在一块连续空间地址的内存单元中

顺序表一般采用静态数组方法实现数据元素存储

顺序表类定义

类的成员变量用来表示抽象数据的数据集合，类的成员函数用来表示抽象数据类型的操作集合

[!NOTE]

类的定义包括两部分：类定义和类实现
类定义给出类的成员变量和成员函数的定义
类实现给出类成员函数的具体编码实现

顺序表类定义：

 class SeqList{
 protected:
     DataType *list;//数组
     int maxSize;//最大元素个数
     int size;//当前元素个数
 public:
     SeqList(int max = 0);//构造函数
     ~SeqList();//析构函数
     int Size()const;//取当前元素个数
     void Insert(const DataType& item, int i);//插入
     DataType Delete(const int i);//删除
     DataType GetData(int i) const;//取数据元素 
 }；

SeqList:类名

DataType:数组元素的数据类型

list:顺序表的数组成员变量

maxSize:数组的最大成员个数

size:顺序表中当前存储的数组成员个数成员变量，size <= maxSize

类是可以被重复使用的软件设计的基本模块

顺序表类实现

SeqList::SeqList(int max){
    maxSize = max;
    size = 0;
    list = new DataType[maxSize];
}

SeqList::~SeqList(void){
    delete []list;
}

SeqList::Size(void)const{
    return size;
}

void SeqList::Insert(const DataType& item, int i){
    for(int j = size; j > i; j--) list[j] = list[j-1];
    list[i] = item;
    size++;
}

DataType SeqList::Delete(const int i){
    DataType x = list[i];
  
    for(int j = i; j < size - 1; j++) list[j] = list[j + 1];
    size--;
    return x;
}

DataType SeqList::GetData(int i) const{
    return list[i];
}

单链表类

结构

单链表内构成链表的结点只有一个只想直接后继节点的指针域，其结构特点：逻辑上相邻的数据元素在物理上不一定相邻
节点结构包括数据域和指针域

数据域：存储元素数值数据
指针域：存储直接后继的存储位置

头指针：指向链表的第一个结点（头结点或首元结点）
头结点：链表的首元结点之前附设的一个结点，只存放空表信息和表长，不计入总长度
首元结点：指链表中存储线性表第一个数据元素a0的结点

结点类的定义和实现

template <class T> class LinList;
template <class T>
class LinNode
{
friend class LinList <T>;
private:
    ListNode <T> *next;//指向下一个结点的指针
    T data;
public:
  
    ListNode(ListNode<T> *ptrNext = NULL){
        next = ptrNext;
    }//构建头结点
  
    ListNode(const T& item,ListNode<T> *ptrNext=NULL){
        data = item;
        next = ptrNext;
    }//构建其他结点
  
    ~ListNode(void);
    //析构函数
  
};

单链表的定义和实现

template <class T>
class LinList
{
private:
	ListNode <T> *head;//头指针
    int size;//当前元素个数
    ListNode <T> *Index(int i); //定位函数
  
public:
    LinList(void); //构造函数
    ~LinList(void); //析构函数
  
    int Size(void) const; //取当前数据元素个数
    void Insert(const T& item, int i); //插入
  
    T Delete(int i); //删除
    T GetData(int i); //取数据元素
}

//所设计的单链表带头结点，所以构造函数要用new运算符

LinList <T>::LinList()
{
    head = new LinNode<T>();
    size = 0;
}

LinList<T> ::~LinList(void)
{
    LinNode<T> *p, *q;
    p = head;//p指向头指针
    while(p != NULL)
    {
        q = p;
        p = p->next;
        delete q;
    }
  
    size = 0;//节点个数重置
    head = NULL;
}

LinList<T> ::Insert(const T& item, int i)
{
    ListNode <T> *p = Index(i - 1);
    ListNode <T> *q = new LinNode <T> (item, p->next);
    //构建新结点q的data值域为item，next值域为p->next,此处建立连接
    p->next = q;
  
    size++;
}

LinList<T> ::Delete(int i)
{
    ListNode<T> *s, *p = Index(i - 1);
    s = p->next;
    p->next=p->next->next;
  
    T x = s->data;
    delete s;
    size--;
  
    return x;//返回第i个结点的data值域
}

循环单链表

循环单链表是单链表的另一种形式，特点是链表中的最后一个结点的指针域指向整个链表的第一个结点，从而使链表形成一个环。
优点是从链尾到链头比较方便。

也有带头结点和不带头结点两类。

双向链表

双向链表是每个结点除了后继指针外还有一个前驱指针，它带有头结点和不带头结点，循环和非循环结构，
双向链表是解决查找前驱结点问题的有效途径

静态链表

在数组中增加一个（或两个）指针域用来存放下一个（或上一个）数据元素在数组中的下标，从而构成用数组构造的单链表。
因为数组内存空间的申请方式是静态的，所以称为静态链表，增加的指针称为仿真指针。