数据结构与算法笔记cp2：线性表

1. 线性表

1.1 定义：

List，由 零个或多个 数据特性相同的元素构成的 有限 序列。个数 n 称为线性表的长度，n=0 的时候称为空表。比如说，十二星座就是一个线性表，它的“第一个”和“最后一个”元素都是唯一的，并且中间的元素均只有一个前驱、一个后继。

1.2 抽象数据类型

ADT List{
    Data:.......
    Operation:
        InitList(&L): 初始化，建立一个空的线性表L
        ClearList(&L): 清空线性表L
        GetElem(L,i,&e): 将L中第i个位置元素值返回给e
        LocateElem(L,e): 在L中查找与e相等的元素
        ListInsert(&L,i,e): 在L中第i个位置插入新元素e
        ListDelete(&L,i,&e): 删除L中第i个位置元素，并用e返回其值
        ListLength(L): 返回L长度
} ADT List

2. 线性表的顺序存储结构

2.1 定义：

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

各个元素的地址之间构成等差数列，因此，知道了某一个元素的地址，就可以随时推导出其它元素的地址，也就是说不管取出还是存入哪一个元素，花费的时间都一样，是一个常数(O(1))，这种特性的存储结构就叫 随机存取结构 。

一维数组可以实现线性表的顺序存储结构，不过要注意数组下标从0开始，而说线性表的时候说的是位序，是从1开始的。

2.2 基本操作

(1) 初始化：

首先定义线性表顺序存储结构：

typedef struct Table{
    int * head;//声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length;//记录当前顺序表的长度
    int size;//记录顺序表分配的存储容量
}table;

第一个操作是初始化，包括：给head申请足够大小的物理空间；给size和length赋初值：

#define Size 5 //对Size进行宏定义，表示顺序表申请空间的大小
table initTable(){
    table t;
    t.head=(int*)malloc(Size*sizeof(int));//构造一个空的顺序表，动态申请存储空间
    if (!t.head) //如果申请失败，作出提示并直接退出程序
    {
        printf("初始化失败");
        exit(0);
    }
    t.length=0;//空表的长度初始化为0
    t.size=Size;//空表的初始存储空间为Size
    return t;
}

(2) 取值：

找某一个位序的元素，只需要判断位序的合法性，之后返回数组[位序-1]即可。

(3) 查找/修改：

遍历数组元素，与目标元素比较，相等则返回。如果要修改，重新赋值即可。

(4) 删除：

找到目标元素，让后续元素整体前移一个位置，之后长度减一即可。

table delTable(table t,int add){
    if (add>t.length || add<1) {
        printf("被删除元素的位置有误");
        exit(0);
    }
    //删除操作
    for (int i=add; i<t.length; i++) {
        t.head[i-1]=t.head[i];
    }
    t.length--;
    return t;
}

比如说要删除5个元素中的第三个，那么 add 就是 3，而 t.head[3] 就是第四个元素，从这个元素开始依次向前移动并覆盖前面的元素。

(5) 插入：

找到目标位置，将该位置对应元素以及后续元素整体后移一个位置，之后长度加一即可。

//插入函数，其中，elem为插入的元素，add为插入到顺序表的位置
table addTable(table t,int elem,int add)
{
    //判断插入本身是否存在问题
    if (add>t.length+1||add=add-1; i--) {
        t.head[i+1]=t.head[i];
    }
    t.head[add-1]=elem;
    t.length++;
    return t;
}

• 首先要注意范围的判断，add 作为目标位置，至少也得等于1，此时是插在最前面；同时，add 可以等于 length+1，此时是插在最后面，但不能比 length+1 更大了，否则会出现空隙。
• 接着要注意是从后往前遍历的，因为如果是从前往后的话就会发生覆盖。
• 可以不做“目标位置是否在表尾”的判断，这样会直接绕过for循环，执行赋值。

这里可以发现，线性表的插入和删除元素操作往往需要移动大量的元素。

3. 线性表的链式存储结构

2.1 定义：

线性表的链式存储结构不限制数据元素的物理存储状态，也就是说，其数据元素的物理位置是随机的。

对于每一个元素来说，它需要存储自身信息在 数据域 中，还需要存储直接后继的位置信息在 指针域 中，这两部分信息共同构成一个结点（Node）。n 个结点就

链结成一个 链表 ，如果每一个结点只有一个指针域，那么它就是单链表。

头指针：头指针保存第一个结点（首元结点）的存储位置，因为最后一个结点没有后继结点，所以它的指针域为空( NULL / ^ )。

头结点：有时候，首元结点前还会设置一个头结点，有头结点的时候，头指针保存的是头结点的存储位置。对于头结点，其数据域不一定要包含信息，其指针域则保存的是首元结点的存储位置。如下图所示：

Tip: 设计头结点是为了操作的统一。

链表并不是 随机存取结构 ，并不能根据一个给定元素就能马上找到另一个目标元素，而是只能从头指针开始顺链查找，这称为 顺序存取结构 。

2.2 单链表：

在开始之前，我们还是先定义单链表中每个结点的结构：

typedef struct Link{
    char elem; // 数据域
    struct Link * next; // 指针域
}link; // link为结点名，每个结点都是一个 link 结构体

Tip：因为指针也是指向一个结点，这里尤其要注意将指针类型声明为 struct Link

(1) 初始化空表：

link * initLink(){
    link * p=(link*)malloc(sizeof(link));// 创建一个头结点
    link * temp=p;// 声明头指针并指向头结点
    temp->next=NULL; // 头结点的指针域置空
    return p;
}

(2) 整表创建：

例如，创建一个存储 {1,2,3,4} 且无头结点的链表：

link * initLink(){
    link * temp = (link*)malloc(sizeof(link));// 创建首元结点
    link * p = temp;// 创建头指针并指向首元结点

    // 首元节点先初始化
    temp->elem = 1;
    temp->next = NULL;

    // 从第二个节点开始创建
    for (int i=2; ielem=i;
        a->next=NULL;
        // 将temp节点与新建立的a节点建立逻辑关系
        temp->next=a;
        // 指针temp每次都指向新链表的最后一个节点
        temp=temp->next;
    }
    //返回建立的节点，只返回头指针 p 即可，通过头指针即可找到整个链表
    return p;
}

(3) 查找元素：

p 为原链表，elem 表示被查找的元素
int selectElem(link * p,int elem){
    // 新建一个指针，直接指向首元结点
    link * t = p->next;
    while(t && t->elem!= elem){
        t=t->next;
    }
    return p;
}

因为存在头结点，所以这里首先获取首元结点，然后从首元结点开始依次往后面遍历，查找是否有符合的元素。如果查找成功，返回的 p 是元素的地址，查找失败则返回 NULL。

(4) 修改元素：

// add 表示更改结点在链表中的位置，newElem 为新的数据域的值
link *amendElem(link * p,int add,int newElem){
    link * temp=p->next;
    // 遍历到被删除结点
    for (int i=1; inext;
    }
    temp->elem=newElem;
    return p;
}

(5) 删除元素：

包括两步，一个是摘除结点并改变连接，一个是释放被摘除结点的内存。关键代码是：

temp->next=temp->next->next;

如下图所示：

具体实现代码是：

//p为原链表，add为要删除元素的值
link * delElem(link * p,int add){
    // temp 首先指向首元结点
    link * temp=p;
    // 先寻找被删除结点的上一个结点
    for (int i=1; inext;
    }
    link * del=temp->next;// 单独设置一个指针指向被删除结点，后面方便释放其内存
    temp->next=temp->next->next;
    free(del);// 手动释放该结点，防止内存泄漏
    return p;
}

注意这是没有头结点的情况，如果有头结点，循环判断应该是 i<add，因为这时候的 temp 指向的是头结点。

(6) 插入元素：

包括两步，一个是将插入位置后的结点作为新结点的 next，一个是将新结点作为插入位置前的结点的 next，也就是关键代码：

new->next=temp->next;
temp->next=new;

如下图所示：

注意：这里顺序不能颠倒，如果是先确定插入位置前结点和新结点的连接，那么插入位置后结点将无法获取，因为其获取是依赖于插入位置前结点的next的，而这个next已经被覆盖。

具体代码为：

// p为原链表，elem表示新数据元素，add表示新元素插入的位置
link * insertElem(link * p,int elem,int add){
    link * temp=p;// 创建指向头结点的指针
    // 遍历寻找插入位置前的结点
    for(int i=1;inext;
    }
    // 创建新结点并初始化
    link * c=(link*)malloc(sizeof(link));
    c->elem=elem;
    // 改变连接关系
    c->next=temp->next;
    temp->next=c;
    return p;
}

if 语句用来判断 add 是否合法，因为如果 add 过大，那么一直遍历下去会得到一个 next 为 NULL 的temp，之后报错。