《数据结构》第二章线性表

Article

数据结构

2.1 线性表的定义和基本操作

2.1.1 线性表的定义

线性表是具有相同数据类型的 n(N>=0)个数据元素的有限序列。

2.1.2 线性表的基本操作

“创销、增删改查”

InitList(&L): 初始化列表。
Length(L): 求表长。
LocateElem(L, e): 按值查找。
GetElem(L, i): 按位查找。
ListInsert(&L, i, e): 插入操作。
ListDelete(&L, i, &e): 删除操作。
PrintList(L): 输出操作。
Empty(L): 判断是否空表。
DestroyList(&L): 销毁操作。

2.2 线性表的顺序表示

2.2.1 顺序表的定义

线性表的顺序存储结构是一种随机存取的存储结构。

静态分配：

♾️ C 代码:

#define MaxSize 10            //定义线性表的最大长度
typedef struct {
    ElemType data[MaxSize];    //顺序表的元素
    int length;                //顺序表当前长度
}SqList;                    //顺序表的类型定义

动态分配：

♾️ C 代码:

#define InitSize 10            //表长度的初始定义
typedef struct {
    ElemType *data;            //指示动态分配数组的指针
    int MaxSize,length;        //数组的最大容量和当前长度
}SeqList;                    //顺序表的类型定义

//C的初始动态分配与释放
L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
free(L);
//C++的初始动态分配
L.data = new ElemType[InitSize];
delete[] L.data;

“动态分配的缺点：时间复杂度会高”

顺序表的优缺点：

优点：
- 可进行随机访问
- 存储密度高
缺点：
- 元素的插入删除需要移动大量的元素
- 需要一段连续的存储空间，不够灵活

2.2.2 顺序表上基本操作的实现

1. 初始化

静态分配

♾️ C 代码:

void InitList(SqList &L) {
    L.length = 0;
}

动态分配

♾️ C 代码:

void InitList(SeqList &L) {
    L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
    L.length = 0;
    L.MaxSize = InitSize;
}

2. 插入操作

♾️ C 代码:

bool ListInsert(SqList &L, int i, ElemType e) {
    if(i<1 || i>L.length+1)
        return false;
    if(L.length >= MaxSize)
        return false;
    for(int j = L.length; j>=i; j--) {
        L.data[j] = L.data[j-1]
    }
    L.data[i-1] = e;
    L.length++;
    return true;
}

时间复杂度：$O(n)$

3. 删除操作

♾️ C 代码:

bool ListDelete(SqList &L, int i, ElemType &e) {
    if(i<1 || i>L.length)
        return false;
    e = L.data[i-1];
    for(int j=i; j<=L.length; j++)
    {
        L.data[j-1] = L.data[j];
    }
    L.length--;
    return true;
}

时间复杂度：$O(n)$

4. 查找操作

按位查找

♾️ C 代码:

ElemType GetElem(SqList &L, int i) {
    return L.data[i-1];
}

时间复杂度：$O(1)$

按值查找

♾️ c 代码:

int LocateElem(SqList &L, ElemType e) {
    for(int i=0; i<L.length; i++)
    {
        if(L.data[i] == e)
            return i+1;
    }
    return 0;
}

时间复杂度：$O(n)$

2.3 线性表的链式表示

2.3.1 单链表的定义

线性表的链式存储也称单链表，包括数据域data，指针域next。

单链表的元素离散分布在存储空间，是非随机存取的存储结构。

♾️ C 代码:

typedef struct LNode {
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

2.3.2 单链表上基本操作的实现

1. 初始化

带头节点

♾️ c 代码:

bool InitList (LinkList L) {
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    return true;
}

不带头节点

♾️ C 代码:

bool InitList (LinkList L) {
    L->next = NULL;
    return true;
}

2. 求表长操作

♾️ C 代码:

int Length(LinkList L) {
    int len = 0;
    LNode *p = L;
    while(p->next != NULL) {
        p=p->next;
        len++;
    }
    return len;
}

时间复杂度：$O(n)$

3. 查找操作

按位查找

♾️ C 代码:

LNode *GetElem(LinkList L, int i) {
    LNode *P = L;
    int j = 0;
    while(p != NULL && j<i) {
        p = p->next;
        j++;
    }
    return p;
}

时间复杂度：$O(n)$

按值查找

♾️ C 代码:

LNode *LocateElem(LinkList L, ElemType e) {
    LNode *p = L;
    while(p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}

时间复杂度：$O(n)$

4. 插入操作

带头节点

♾️ C 代码:

bool ListInsert(LinkList L, int i, ElemType e) {
    LNode *p = L;
    int j = 0;
    while(p != NULL && j<i-1) {
        p = p->next
        j++;
    }
    if(p == NULL)
        return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

时间复杂度：$O(n)$

不带头节点（需单独考虑第 1 结点插入情况）

♾️ C 代码:

bool ListInert(LinkList L, int i, ElemType e) {
    LNode *p = L;
    int j = 0;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    
    //需单独考虑第 1 结点插入情况
    if(i == 1) {
        s->next = p;
        p = s;
    }        
    
    while(p != NULL && j<i-1) {
        p = p->next
        j++;
    }
    if(p == NULL)
        return false;
    s->next = p->next;
    p->next = s;
    return true;
}

时间复杂度：$O(n)$

5. 删除操作

♾️ C 代码:

bool ListDelete(LinkList L, int i, ElemType &e) {
    LNode *p = L;
    int j = 0;
    while(p != NULL && j<i-1) {
        p = p->next;
        j++;
    }
    if(p->next == NULL || j>i-1)
        return false;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

时间复杂度：$O(n)$

ps：对于要求删除定结点*p，可以找到*p的后继结点*q，将*q的data赋予到*p，再将*q断开并释放：

♾️ C 代码:

...
q = p->next;
p->data = q->data;
p->next = q->next;
free(q);

6. 头插法建立单链表

头插法的重要作用：链表的逆置

带头节点

♾️ C 代码:

LinkList List_HeadInsert(LinkList L) {
    LNode *s;
    int x;
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d",&x);
    while(x!=9999) {    //输入9999结束输入
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }        
    return L;
}

时间复杂度：$O(n)$

不带头节点
参考本小节的插入操作中的不带头节点插入第 1 个结点思路

7. 尾插法建立单链表

♾️ C 代码:

LinkList List_TailInsert(LinkList L) {
    int x;
    L = (LNode*)malloc(sizeof(LNode));
    LNode *s, *r = L;
    scanf("%d",&x);
    while(x!=9999) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return L;
}

时间复杂度：$O(n)$

2.3.3 双链表

双链表由两个指针域（指向前驱的prior和指向后继的next）和数据域组成。

♾️ C 代码:

typedef struct DNode {
    ElemType data;
    struct DNode *prior,*next;
}DNode, *DLinkList;

插入操作片段

♾️ C 代码:

//需要考虑 p结点的后继是否为空，这里是将 s结点插入到 p结点之后（p结点后继不为空）
s->next = p->next;
p->next-prior = s;
s->prior = p;
p->next = s;

删除操作片段

♾️ C 代码:

//需要考虑 q结点的后继是否为空，这里是将 p结点之后的 q结点删除（q结点后继不为空）
p->next = q->next;
q->next->prior = p;
free(q);

2.3.4 循环链表

循环单链表
- 当表为空时，L->next == L。
- 可以通过尾指针查找到表头，但若只有尾指针，当进行删除最后一个结点时，其需要遍历整张表，其时间复杂度为$O(n)$，并未达到高效率目的。
循环双链表
当表为空时，L->next == L->prior == L。

2.3.5 静态链表

和顺序表一样，静态链表也要预先分配一块连续的内存空间。

♾️ C 代码:

#define MaxSize 50
typedef struct {
    ElemType data;
    int next;
}SLinkList[MaxSize];

优点：只需要修改指针，而不需要移动元素
缺点：容量固定

2.3.6 顺序表和链表的比较

	顺序表	链表
弹性（可扩容）	😀	😀
增、删	😡	😀
查	😀	😡

现在已有 114 次阅读，0 条评论，0 人点赞

日	一	二	三	四	五	六
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

《数据结构》第二章 线性表

2.1 线性表的定义和基本操作

2.1.1 线性表的定义

2.1.2 线性表的基本操作

2.2 线性表的顺序表示

2.2.1 顺序表的定义

2.2.2 顺序表上基本操作的实现

1. 初始化

2. 插入操作

3. 删除操作

4. 查找操作

2.3 线性表的链式表示

2.3.1 单链表的定义

2.3.2 单链表上基本操作的实现

1. 初始化

2. 求表长操作

3. 查找操作

4. 插入操作

5. 删除操作

6. 头插法建立单链表

7. 尾插法建立单链表

2.3.3 双链表

2.3.4 循环链表

2.3.5 静态链表

2.3.6 顺序表和链表的比较

《数据结构》第二章线性表