线性表

发表于 2024-02-23 分类于数据结构本文字数： 8.7k

线性表中的顺序表和链表

线性表的特点：

存在唯一的一个被称作“第一个”的数据元素；
存在唯一的一个被称作“最后一个”的数据元素；
除第一个之外，结构中的每个数据元素均只有一个前驱；
除最后一个之外，结构中的每个数据元素均只有一个后继。

顺序表

线性表的顺序表示是指，用一组地址连续的存储单元，依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常称这种存储结构的线性表为顺序表

静态顺序表

数据元素储存空间大小固定的顺序表，称为静态顺序表，其储存空间一旦被确定就无法修改。下面是静态顺序表的实现

定义数据元素的结构体和顺序表的结构体

// 数据表允许储存的元素上限个数
#define MAX_LENGTH 100

// 顺序表中的数据元素
typedef int ElemType;

// 代表数据表
typedef struct List{
    ElemType data[MAX_LENGTH];  // 数据表中储存数据元素的数组
    int length;                 // 数据表中数据元素的长度
} List;

初始化表

/**
 * 静态顺序表的初始化
 */
void initList(List *list) {
    list->length = 0;
}

输出表中所有数据

/**
 * 输出数据表中的所有数据元素
 */
void printList(List list) {
    for (int i = 0; i < list.length; i++) {
        ElemType elem = list.data[i];
        printf("data = %d\n", elem);
    }
}

插入数据元素到指定位置

/**
 * 插入数据
 * @param list 
 * @param index     要插入的位置，以1为起始
 * @param elem      要插入的数据元素
 * @return 是否插入成功
 */
bool listInsert(List *list, int index, ElemType elem) {
    // 检查插入的位置是否有效
    if (index < 0 || index > list->length + 1)
        return false;
    // 检查储存空间是否已满
    if (list->length >= MAX_LENGTH)
        return false;
    // 将index及之后的元素全部后移一位
    for (int i = list->length; i >= index; i--)
        list->data[i] = list->data[i - 1];
    // 数据插入
    list->data[index - 1] = elem;
    // 长度+1
    list->length++;
    return true;
}

删除指定位置的数据元素

/**
 * 删除数据
 * @param list
 * @param index     要删除的位置，以1为起始
 * @param elem      被删除的数据元素
 * @return
 */
bool listDelete(List *list, int index, ElemType *elem) {
    // 检查插入的位置是否有效
    if (index < 1 || index >= list->length)
        return false;
    // 把需要被删除返回出去
    *elem = list->data[index - 1];
    // 将index之后的元素全部前移一位，用以覆盖index处的数据元素
    for (int i = index; i < list->length; i++)
        list->data[i - 1] = list->data[i];
    // 长度-1
    list->length--;
    return true;
}

按值查找数据元素

/**
 * 查找指定的数据元素，返回其在数据表中位置（以1为起始）
 * @param list 
 * @param elem 指定的数据元素
 * @return 若查找失败，返回0
 */
int locateElem(List list, ElemType elem) {
    for (int i = 0; i < list.length; i++)
        // 对比数据元素的id
        if (list.data[i] == elem)
            return i + 1;
    return 0;
}

动态顺序表

数据元素储存空间大小可以修改的顺序表，称为动态顺序表，其储存空间可以动态增加。下面是动态顺序表的实现

修改上面静态顺序表结构体，使用指针代替固定长度的数组，并添加一个size参数，用于记录当前数据表中的储存空间占用的内存大小

如下代码，仅列出与静态顺序表的不同之处。相同之处不提

// 数据表允许储存的元素的初始个数
#define INIT_LENGTH 100

// 顺序表中的数据元素
typedef int ElemType;

// 代表数据表
typedef struct List {
    ElemType *data; // 数据表中储存数据元素的首地址指针
    int length;     // 数据表中数据元素的长度
    int MaxLength;  // 数据表当前允许储存的数据元素最大个数
} List;

初始化表

/**
 * 动态顺序表的初始化
 */
void initList(List *list) {
    list->length = 0;
    list->MaxLength = INIT_LENGTH;
    list->data = (ElemType*) malloc(sizeof(ElemType) * INIT_LENGTH);
}

动态增加数据表储存空间

/**
 * 动态增加数据表储存空间
 */
void expandList(List *list) {
    list->MaxLength += INIT_LENGTH;
    ElemType *newData = (ElemType*) realloc(list->data, sizeof(ElemType) * list->MaxLength);
    if (newData != NULL)
        list->data = newData;
}

在插入数据时，检查储存空间是否已满，若已满则动态增加空间

/**
 * 插入数据
 * @param list
 * @param index     要插入的位置，以1为起始
 * @param elemType  要插入的数据元素
 * @return 是否插入成功
 */
bool listInsert(List *list, int index, ElemType elemType) {
    // 检查插入的位置是否有效
    if (index < 1 || index > list->length + 1)
        return false;
    // 检查储存空间是否已满，若已满则动态增加空间
    if (list->length >= list->MaxLength)
        expandList(list);
    // 将index及之后的元素全部后移一位
    for (int i = list->length; i >= index; i--)
        list->data[i] = list->data[i - 1];
    // 数据插入
    list->data[index - 1] = elemType;
    // 长度+1
    list->length++;
    return true;
}

链表

用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这种储存单元称为结点，每个结点包括两个域，其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域，指针域中存储的信息称作指针或链，n个结点通过指针链结成一个链表，即为线性表

根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等

单链表

对首元结点、头结点、头指针三个容易混淆的概念加以说明

首元结点是指链表中存储第一个数据元素结点。
头结点是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可存储与数据元素类型相同的其他附加信息。
头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。

定义结点和结点中数据的结构体

// 数据表允许储存的元素的初始个数
#define INIT_LENGTH 100

// 顺序表中的数据元素
typedef int ElemType;

// Node代表数据结点
// LinkList代表数据表
typedef struct Node {
    ElemType data;          // 当前结点中的数据
    struct Node *nextNode;  // 指向下个结点的指针
} Node, *LinkList;

使用头结点

使用头结点时，LinkList本身作为指针将指向头结点，其指针域指向首元结点，数据域不储存数据

输出链表中的数据

/**
 * 输出链表数据
 */
void printList(LinkList linkList) {
    Node *p = linkList;
    while (p->nextNode != NULL) {
        ElemType elemType = p->nextNode->data;
        printf("data = %d\n", elemType);
        p = p->nextNode;
    }
}

初始化链表

/**
 * 初始化链表
 * @param linkList
 */
void initList(LinkList *linkList) {
    // 给头结点分配内存地址
    (*linkList) = (Node*)malloc(sizeof(Node));
    (*linkList)->nextNode = NULL;
}

求链表的表长

/**
 * 求链表的表长，头结点的长度不包括在内
 * @param linkList
 * @return
 */
int Length(LinkList linkList) {
    int length = 0;
    Node *p = linkList;
    // 遍历链表，得到长度，该长度不包括头结点
    while (p->nextNode != NULL) {
        length++;
        p = p->nextNode;
    }
    return length;
}

查找链表中指定序号代表的结点

/**
 * 按序号查找结点，头结点不包括在内
 * @param linkList
 * @param i 链表的首个数据结点序号为1，头结点不包括在内
 * @return
 */
Node* getElement(LinkList linkList, int i) {
    int j = 0;
    Node *p = linkList;
    // 依次向下寻找，直到得到目标结点
    while (p != NULL && j < i) {
        j++;
        p = p->nextNode;
    }
    return p;
}

查找对应值的结点

/**
 * 按值查找结点
 * @param linkList
 * @param elemType
 * @return
 */
Node* locateElement(LinkList linkList, ElemType elemType) {
    Node *p = linkList->nextNode;
    while (p != NULL && p->data != elemType)
        p = p->nextNode;
    return NULL;
}

向链表中插入结点

/**
 * 插入数据
 * @param linkList
 * @param index     链表中首个数据结点的序号为1
 * @param elemType
 * @return
 */
bool listInsert(LinkList linkList, int index, ElemType elemType) {
    int j = 0;
    Node *p = linkList;
    // 找到要插入的位置的前驱结点
    while (p != NULL && j < index - 1) {
        j++;
        p = p->nextNode;
    }
    // 如果前驱结点不存在
    if (p == NULL)
        return false;
    // 插入新结点
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->nextNode = p->nextNode;
    newNode->data = elemType;
    // 连接后继结点
    p->nextNode = newNode;

    return true;
}

从链表中删除结点

/**
 * 删除数据
 * @param linkList
 * @param index         链表的首个数据结点序号为1
 * @param elemType
 * @return
 */
bool listDelete(LinkList linkList, int index, ElemType *elemType) {

    Node *p = linkList;
    int j = 0;

    // 找到要删除的结点的前驱结点
    while (p != NULL && j < index - 1) {
        j++;
        p = p->nextNode;
    }

    if (p ==NULL || p->nextNode == NULL)
        return false;

    // 返回被删除的结点的值
    (*elemType) = p->nextNode->data;

    // 删除结点
    Node *temp = p->nextNode;
    p->nextNode = p->nextNode->nextNode;

    // 释放被删除的结点
    free(temp);

    return true;
}

不使用头结点

在上面的代码中，Node代表结点，LinkList代表单链表；若使用头结点，则LinkList本身作为指针将指向头结点，否则指向首元结点