数据结构笔记：线性表(顺序存储结构&链式存储结构）（待填坑

线性表的抽象数据类型

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

线性表的顺序存储结构

将所有的在线性表Lb中但不在La中的数据元素插入到La中

 1 void unionL(SqList *La, SqList Lb) {
 2     int La_len, Lb_len;
 3     ElemType e; // 声明与La和Lb相同的数据元素e
 4     La_len = ListLength(*La); // 求线性表的长度
 5     Lb_len = ListLength(Lb);
 6     for (int i = 1; i <= Lb_len; i++) {
 7         GetElem(Lb, i, &e); // 取Lb中第i个数据元素赋给e
 8         if (!LocateElem(*La, e)) // *La中不存在和e相同数据元素
 9             ListInsert(La, ++La_len, e); // 插入
10     }
11 }

顺序存储的结构代码

1 #define MAXSIZE 20 // 储存空间初始分配量
2 typedef int ElemType; // ElemType类型根据实际情况而定，这里假设为int*
3 typedef struct {
4     ElemType data[MAXSIZE]; // 数组储存数据结构，最大值为MAXSIZE
5     int length; // 线性表当前长度
6 }SqList;

获得元素

 1 #define OK 1
 2 #define ERROR 0
 3 #define TRUE 1
 4 #define FALSE 0
 5 typedef int Status;
 6 // Status是函数的类型，其值是函数结果状态代码，如OK等
 7 // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 8 // 操作结果：用e返回L中第i个数据元素的值
 9 Status GetElem(SqList L, int i, ElemType *e) {
10     if (L.length == 0 || i < 1 || i > L.length)
11         return ERROR;
12     *e = L.data[i-1];
13 }

插入元素

 1 // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 2 // 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
 3 Status ListInsert(SqList *L,int i, ElemType e) {
 4     int k;
 5     if (L->length == MAXSIZE)
 6         return ERROR;
 7     if (i < 1 || i > L->length+1)
 8         return ERROR;
 9     if (i <= L->length) {
10         for (k = L->length-1; k >= i-1; k--)
11             L->data[k+1] = L->data[k];
12     }
13     L->data[i-1] = e;
14     L->length++;
15     return OK;
16 }

删除元素

 1 // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 2 // 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
 3 Status ListDelete(SqList *L, int i, ElemType *e) {
 4     if (L->length == 0) // 线性表为空
 5         return ERROR;
 6     if (i < 1 || i > L->length) // 删除位置不正确
 7         return ERROR;
 8     *e = L->data[i-1];
 9     if (i < L->length) {
10         for (int k = i; k < L->length; k++)
11             L->data[k-1] = L->data[k];
12     }
13     L->length--;
14     return OK;
15 }

线性表顺序存储结构的优缺点

优点：
    0.无须为表示表中元素之外的逻辑关系而增加额外的存储空间
    1.可以快速地存取表中任一位置的元素
缺点：
    0.插入和删除操作需要移动大量元素
    1.当线性表长度变化较大时，难以确定存储空间的容量
    2.造成存储空间的“碎片”

线性表的链式存储结构

头指针与头结点的异同

线性表的单链表存储结构

1 typedef struct Node {
2     ElemType data;
3     struct Node *next;
4 } Node;
5 typedef struct Node *Linklist; // 定义Linklist

单链表的读取

 1 // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 2 // 操作结果：用e返回L中第i个数据元素的值
 3 Status GetElem(LinkList L, int i, ElemType *e) {
 4     int j;
 5     LinkList p; // 声明一结点p
 6     p = L->next; // 让p指向链表L的第一个结点
 7     j = 1; // j为计数器
 8     while (p && j < i) { // p不为空或者计数器j不等于i时，循环
 9         p = p->next; // 让p指向下一个结点
10         ++j;
11     }
12     if (!p || j > i)
13         return ERROR; // 第i个元素不存在
14     *e = p->data; // 取第i个元素的数据
15     return OK;
16 }

单链表的插入

 1 // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 2 // 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
 3 Status ListInsert(LinkList *L, int i, ElemType e) {
 4     int j;
 5     LinkList p, s;
 6     p = *L;
 7     j = 1;
 8     while (p && j < i) { // 寻找第i个结点
 9         p = p->next;
10         ++j;
11     }
12     if (!p || j > i)
13         return ERROR; // 第i个元素不存在
14     s = (LinkList)malloc(sizeof(Node)); // 生成新结点(C标准函数)
15     s->data = e;
16     s->next = p->next; // 将p的后继结点赋值给s的后继
17     p->next = s; // 将s赋值给p的后继
18     return OK;
19 }

单链表的删除

 1 // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 2 // 操作条件：删除L的第i个数据元素，并用e返回其值，L的长度减1
 3 Status ListDelete(LinkList *L, int i, ElemType *e) {
 4     int j;
 5     LinkList p, q;
 6     p = *L;
 7     j = 1;
 8     while (p->next && j < i) { // 遍历寻找第i个元素
 9         p = p->next;
10         ++j;
11     }
12     if (!(p->next) || j > i)
13         return ERROR; // 第i个元素不存在
14     q = p->next;
15     p->next = q->next; // 将q的后继赋值给p的后继
16     *e = q->data; // 将q结点中的数据给e
17     free(q); // 让系统回收此节点，释放内存
18     return OK;
19 }

单链表的整表创建

随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）

 1 void CreateListHead(LinkList *L, int n) {
 2     LinkList p;
 3     srand(time(0)); // 初始化随机数种子
 4     *L = (LinkList)malloc(sizeof(Node));
 5     (*L)->next = NULL; // 先建立一个带头结点的单链表
 6     for (int i = 0; i < n; i++) {
 7         p = (LinkList)malloc(sizeof(Node)); // 生成新结点
 8         p->data = rand()%100 + 1; // 随机生成100以内的数字
 9         p->next = (*L)->next;
10         (*L)->next = p; // 插入到表头
11     }
12 }

随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）

 1 void CreateListTail(LinkList *L, int n) {
 2     LinkList p, r; 3     srand(time(0)); // 初始化随机数种子
 4     *L = (LinkList)malloc(sizeof(Node)); // 为整个线性表
 5     r = *L; // r为指向尾部的结点
 6     for (int i = 0; i < n; i++) {
 7         p = (Node *)malloc(sizeof(Node)); // 生成新结点
 8         p->data = rand()%100+1; // 随机生成100以内的数字
 9         r->next = p; // 将表尾终端结点的指针指向新结点
10         r = p; // 将当前的新结点定义为表尾终端结点
11     }
12     r->next = NULL; // 表示当前链表结束
13 }

单链表的整表删除

 1 // 初始条件：顺序线性表L已存在，操作结果：将L重置为空表
 2 Status ClearList(LinkList *L) {
 3     LinkList p, q;
 4     p = (*L)->next; // p指向第一个结点
 5     while (p) { // 没到表尾
 6         q = p->next;
 7         free(p);
 8         p = q;
 9     }
10     (*L)->next = NULL; // 头结点指针域为空
11     return OK;
12 }

顺序存储结构和单链表结构的对比
静态链表

线性表的静态链表存储结构

1 #define MAXSIZE 1000 // 假设链表的最大长度是1000
2 typedef struct {
3     ElemType data;
4     int cur; // 游标（Cursor），为0时表示无指向
5 } Component, StaticLinkList[MAXSIZE];
6 --------------------------------
7 // 将一维数组space中各分量链成一备用链表
8 // space[0],cur为头指针，“0”表示空指针

初始化

1 // 将一维数组space中各分量链成一备用链表
2 // space[0],cur为头指针，“0”表示空指针
3 Status InitList(StaticLinkList space) {4     for (int i = 0; i < MAXSIZE-1; i++)
5         space[i].cur = i + 1;
6     space[MAXSIZE-1].cur = 0; // 目前静态链表为空，最后一个元素的cur为0
7     return OK;
8 }

（待填）