数据结构与算法—线性表(数据结构与算法入门：线性表详解)

原创

ithorizon 7个月前 (10-20) 阅读数 22 #后端开发

数据结构与算法入门：线性表详解

一、线性表概述

线性表（Linear List）是数据结构中最基本的一种形式，它是由零个或多个数据元素组成的有限序列。线性表中的元素可以是基本的数据类型，如整数、浮点数、字符等，也可以是错综的结构体。线性表具有以下特点：

线性表中元素的个数称为线性表的长度。

线性表可以是空表，即不含任何元素。

线性表中的元素是有序的，即元素的位置是固定的。

二、线性表的分类

线性表结合存储方法的不同，可以分为以下几种类型：

顺序存储的线性表：使用一段连续的存储单元来存储数据元素，如数组。

链式存储的线性表：使用链表的形式来存储数据元素，如单向链表、双向链表和循环链表。

三、线性表的基本操作

线性表的基本操作包括：

初始化：创建一个空的线性表。

销毁：释放线性表所占用的存储空间。

插入：在线性表中插入一个元素。

删除：在线性表中删除一个元素。

查找：在线性表中查找某个元素。

遍历：访问线性表中的所有元素。

四、顺序存储的线性表

顺序存储的线性表通常使用数组来实现。下面是一个简洁的顺序表的定义和基本操作的实现：


#define MAXSIZE 100 // 定义线性表的最大长度
typedef struct {
    int data[MAXSIZE]; // 存储数据元素
    int length;        // 线性表当前长度
} SeqList;
// 初始化顺序表
void InitList(SeqList *L) {
    L->length = 0;
}
// 插入元素
bool ListInsert(SeqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1 || 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;
}
// 删除元素
bool ListDelete(SeqList *L, int i) {
    if (i < 1 || i > L->length) {
        return false;
    }
    for (int j = i; j < L->length; j++) {
        L->data[j - 1] = L->data[j];
    }
    L->length--;
    return true;
}
// 查找元素
int LocateElem(SeqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;
        }
    }
    return 0;
}

五、链式存储的线性表

链式存储的线性表通常使用链表来实现。下面是一个简洁的单向链表的定义和基本操作的实现：


typedef struct ListNode {
    int data;           // 数据域
    struct ListNode *next; // 指针域
} ListNode;
// 创建节点
ListNode* CreateNode(int e) {
    ListNode *node = (ListNode*)malloc(sizeof(ListNode));
    if (node != NULL) {
        node->data = e;
        node->next = NULL;
    }
    return node;
}
// 初始化链表
void InitList(ListNode **L) {
    *L = (ListNode*)malloc(sizeof(ListNode));
    if (*L != NULL) {
        (*L)->next = NULL;
    }
}
// 插入元素
bool ListInsert(ListNode *L, int i, int e) {
    if (i < 1) {
        return false;
    }
    ListNode *node = CreateNode(e);
    if (node == NULL) {
        return false;
    }
    ListNode *p = L;
    int j = 0;
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) {
        free(node);
        return false;
    }
    node->next = p->next;
    p->next = node;
    return true;
}
// 删除元素
bool ListDelete(ListNode *L, int i) {
    if (i < 1) {
        return false;
    }
    ListNode *p = L;
    int j = 0;
    while (p->next != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p->next == NULL) {
        return false;
    }
    ListNode *q = p->next;
    p->next = q->next;
    free(q);
    return true;
}