线性表

发表于 更新于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 7 分钟

定义

顾名思义，线性表中的数据是线性排列的，是包括零个或多个数据元素的有限序列。

线性表的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ADT 线性表(List)
Data
    线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType。其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

Operation
    InitList(*L):初始化操作，建立一个空的线性表。
    ListEmpty(L):若线性表为空，返回true，否则返回false。
    ClearList(*L):线性表清空。
    GetElem(L,i,*e):将线性表L中第i个位置元素返回给e。
    LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果查找成功,返回该元素在表中的序列号；否则，返回0表示失败。
    ListInsert(*L,i,e):在线性表的第i个位置插入元素e。
    ListDelete(*L,i,*e):删除线性表L中的第i个元素，并用e返回其值
    ListLength(L):返回线性表L的元素个数。
    PrintList(L):打印线性表

对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的。
对于实际问题中涉及的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。

线性表的顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

定义

1
2
3
4
5
6
7
8
# define  MAXSIZE   50  /*存储空间初始分配量*/
typedef int ElemType;   /*ElemType类型根据实际情况而定*/

typedef struct
{
    ElemType* data;     /*存储空间基地址*/
    int length;         /*线性表当前长度*/
}SqList;

元素获取

1
2
3
4
5
6
7
8
9
10
int GetElem(SqList L, int i)
{
    if (L.length == 0 || i<1 || i>L.length)
    {
        cout << "位置信息有误！" << endl;   /*位置不合法，返回-1*/
        return -1;
    }
    else
        return L.data[i - 1];       /*返回位置i的值*/
}

元素插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void InsertElem(SqList& L, int i, ElemType e)
{
    if (L.length == MAXSIZE)
        return;         /*空间已满*/
    else
    {
        if (i<1 || i>L.length + 1)
            return;     /*位置不合法*/
        elseyici
        {
            /*从最后元素到第i个元素依次后移一位*/
            for (int j = L.length - 1; j >= i - 1; j--)
                L.data[j + 1] = L.data[j];
            L.data[i - 1] = e;  /*第i的位置为值e*/
            L.length++;         /*长度加一*/
        }
    }
}

元素删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void DeleteElem(SqList& L, int i, ElemType& e)
{
    if (L.length == 0)
        return;         /*空表没有删除操作*/
    else
    {
        if (i<1 || i>L.length)
            return;     /*位置不合法*/
        else
        {
            e = L.data[i - 1];  /*删除元素存入e*/
            /*从第i+1元素到最后元素依次前移一位*/
            for (int j = i; j < L.length; j++)
                L.data[j - 1] = L.data[j];
            L.length--;     /*长度减一*/
        }
    }
}

优缺点

优点：

  • 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速地存取表中任意位置元素

缺点：

  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时，难以确定存储空间的容量
  • 造成存储空间的“碎片”

线性表的链式存储结构

线性表中元素不再是相邻排列，而是由“链”连接成。

头指针与头结点的异同

头指针： * 头指针是指链表指向的第一个结点的指针，若链表有头结点，则是指向头结点的指针 * 头指针具有标识作用，所有常用头指针冠以链表的名字 * 无论链表是否为空，头指针均不为空。头指针是链表的必要元素

头结点： * 头结点是为了操作的统一和方便而设计的，放在第一元素的结点之前，其数据域一般无意义（也存放链表的长度） * 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了 * 头结点不一定是链式必须要素

定义

1
2
3
4
5
6
7
typedef int ElemType;

typedef struct LNode
{
    ElemType   data;       /*数据域*/
    struct LNode* next;   /*指针域*/
} LNode, * LinkList;          /*LinkList为LNode类型的指针*/

元素获取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void GetElem(LinkList L, int i, ElemType& e)
{
    //当第i个元素存在时，其值赋给e
    LinkList p = L->next;
    int j = 1; //初始化
    while (p && j < i)
    {
        //向后扫描，直到p指向第i个元素或p为空
        p = p->next;
        ++j;
    }
    if (!p || j > i) 
    {
        cout << "第" << i << "个结点不存在\n"; //第i个元素不存在
        e = -1;
    }
    else
        e = p->data;
}

元素插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void ListInsert(LinkList& L, int i, ElemType e)
{
    LinkList p, s;
    int j = 1;
    p = L;
    while (p && j < i)
    {
        p = p->next;    //寻找第i−1个结点
        ++j;
    }
    if (!p || j > i) cout << "第" << i << "个结点不存在" << endl;	//i大于表长 + 1或者小于1
    else
    {
        s = new LNode;                    //生成新结点*s
        s->data = e;      		          //将结点*s的数据域置为e
        s->next = p->next;	   	          //将结点*s插入L中
        p->next = s;
    }
}

元素删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void ListDelete(LinkList& L, int i, ElemType& e)
{
    LinkList p, q;
    int j = 1;
    p = L;
    while (p->next && j < i) //寻找第i个结点，并令p指向其前驱
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j > i) cout << "第" << i << "个结点不存在" << endl; //删除位置不合理
    else
    {
        q = p->next; //临时保存被删结点的地址以备释放
        p->next = q->next; 	//改变删除结点前驱结点的指针域
        delete q;//释放结点
    }
}

单链表创建

头插法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void CreateList_H(LinkList& L, int n)
{
    LinkList p;
    L = new LNode;
    L->next = NULL; //先建立一个带头结点的单链表
    cout << "输入" << n << "个新值：";
    for (int i = 0; i < n; i++)
    {
        p = new LNode;//生成新结点
        cin >> p->data;
        p->next = L->next;
        L->next = p; //插入到表头
    }
}

尾插法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void CreateList_T(LinkList& L, int n)
{
    //正位序输入n个元素的值，建立带表头结点的单链表L
    LinkList p, r;
    L = new LNode;
    L->next = NULL;
    r = L; //尾指针r指向头结点
    cout << "输入" << n << "个新值：";
    for (int i = 0; i < n; i++)
    {
        p = new LNode; //生成新结点
        cin >> p->data;
        p->next = NULL;
        r->next = p; //插入到表尾
        r = p; //r指向新的尾结点
    }
}

单链表整表删除

1
2
3
4
5
6
7
8
9
10
11
12
13
void ClearList(LinkList& L)
{
    // 将L重置为空表
    LinkList p, q;
    p = L->next;   //p指向第一个结点
    while (p)       //没到表尾
    {
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;   //头结点指针域为空
}

静态链表

引用

循环链表

引用

双向链表

引用

单链表结构与顺序存储结构优缺点

存储结构 顺序表 链表
存储空间 预先分配，会导致空间闲置或溢出现象 动态分配，不会出现存储空间闲置或溢出现象
存储密度 不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1 需要借助指针来体现元素间的逻辑关系，存储密度小于1
存取元素 随机存取，按位置访问元素的时间复杂度为O(1) 顺序存取， 按位置访问元素时间复杂度为O(n)
插入、删除 平均移动约表中一半元素， 时间复杂度为O(n) 不需移动元素， 确定插入.删除位置后，时间复杂度为0(1)
使用情况 ①表长变化不大，且能事先确定变化的范围②很少进行插入或删除操作，经常按元素位置序号访问数据元素 ①长度变化较大②频繁进行插人或删除操作

---参考《大话数据结构》

详细