# Ch2 线性表

存储结构：顺序表（数组），链表

# 顺序表

逻辑顺序和物理顺序一致，都连续
按下标访问 O (1)，插入操作平均移动 n/2，删除操作平均移动 (n-1)/2

静态分配

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;

动态分配

#define InitSize 100
typedef struct{
    ElemType *data;
    int MaxSize, length;
}SqList;

初始动态分配：

1	L.data = (ElemType)malloc(sizeof(ElemType)InitSize);

c++

1	L.data = new ElemType[InitSize];

# 初始化

静态分配初始化

1
2
3

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

动态分配初始化

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

# 插入操作

在顺序表的第 i 个 位置 插入元素 e，注意是位置不是下标 (1<=i<=L.length+1)

插入操作

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

插入移动的平均次数为 n/2，插入算法的平均时间复杂度为 $O(n)$

# 删除操作

删除顺序表中第 i 个元素，返回删除的元素 e

删除操作

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;
}

删除操作的平均移动此时是 (n-1)/2，平均时间复杂度为 $O(n)$

# 按值查找

按值查找

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

平均需要访问 (n+1)/2 个元素，平均时间复杂度为 $O(n)$

# 单链表

# 链表结构

单链表结构

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

# 初始化

带头节点的初始化

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

不带头节点的初始化

1
2
3

bool InitList(LinkList &L){
    L = NULL;
}

# 求表长

从头开始遍历，每访问一个节点，长度加 1

求表长

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

# 按序号查找

从头开始遍历直到找到第 i 个节点

按序号查找

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

# 按值查找

从头开始遍历，如果找到则返回该节点

按值查找

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

# 插入操作

先把后继连到新节点的后继，再把前继节点的后继连到新节点

插入操作

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;
}

# 删除操作

先找到待删除节点的前一个节点，再把前一个节点的 next 指向待删除节点的 next，然后释放待删除节点

删除操作

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)$

采用头插法建立单链表

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

# 采用尾插法建立单链表

采用尾插法建立单链表

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;
}

# 双链表

# 双链表结构

双链表结构

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

# 双链表的插入

双链表的插入

s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;

# 双链表的删除

双链表的删除

1
2
3

p->next = q->next;
q-next->prior = p;
free(q);

# 循环链表

# 循环单链表

# 循环双链表

# 静态链表

用数组来表示线性表的链式存储结构

静态链表结构

#define MaxSize 50
typedef struct{
    ElemType data;
    int next;   //下一个元素的数组下标
} SlinkList[MaxSize];

next = -1 表示结束标志

# 顺序表和链表比较

存取
顺序表可以顺序存取 / 随机存取，链表只能顺序
逻辑结构和物理结构
顺序表和链表的逻辑结构相同，顺序表物理结构存储连续，链表物理结构存储不一定连续
删改查的复杂度
略
空间分配
链表的空间分配比较灵活，但存储密度低

难以估计线性表的长度时不宜采用顺序表
按序号访问多选顺序表，插入删除多选链表

线性表

# Ch2 线性表

# 顺序表

# 初始化

# 插入操作

# 删除操作

# 按值查找

# 单链表

# 链表结构

# 初始化

# 求表长

# 按序号查找

# 按值查找

# 插入操作

# 删除操作

# 采用头插法建立单链表

# 采用尾插法建立单链表

# 双链表

# 双链表结构

# 双链表的插入

# 双链表的删除

# 循环链表

# 循环单链表

# 循环双链表

# 静态链表

# 顺序表和链表比较

Amortized Analysis

ch1