数据结构(二)线性表

线性表，也称为线性结构，是数据结构中的一种基本类型，其特点是数据元素之间存在一对一的线性关系。线性表通常可以用数组（顺序存储）或链表（链式存储）来实现。线性表的特点是数据元素的排列呈现线性，即元素之间是有序的，并且每个元素（除了第一个和最后一个）都有一个前驱和一个后继。

线性表的顺序存储

线性表的顺序存储是指使用一段连续的存储单元依次存储线性表的数据元素，这种存储方式通常通过数组来实现。在顺序存储结构中，线性表的元素按照逻辑顺序在物理位置上也是连续的，即每个元素都有一个唯一的序号，称为其在表中的位置或索引。

顺序存储基本操作

结构定义

#define MAX_SIZE 100  // 定义最大长度
typedef struct {
    int data[MAX_SIZE];  // 存储数据元素的数组
    int length;          // 线性表的当前长度
} SequentialList;

初始化线性表

void initList(SequentialList *list) {
    list->length = 0;  // 初始化线性表长度为0
}

插入元素

在顺序存储的线性表中插入元素需要移动元素

int insertElement(SequentialList *list, int position, int element) {
    if (list->length == MAX_SIZE || position < 1 || position > list->length + 1)
        return 0;  // 插入失败

    for (int i = list->length; i >= position; i--) {
        list->data[i] = list->data[i - 1];  // 向后移动元素
    }
    list->data[position - 1] = element;  // 插入新元素
    list->length++;  // 长度增加
    return 1;  // 插入成功
}

删除元素

int deleteElement(SequentialList *list, int position) {
    if (position < 1 || position > list->length)
        return 0;  // 删除失败

    for (int i = position; i < list->length; i++) {
        list->data[i - 1] = list->data[i];  // 向前移动元素
    }
    list->length--;  // 长度减少
    return 1;  // 删除成功
}

访问元素

int getElement(const SequentialList *list, int position) {
    if (position < 1 || position > list->length)
        return -1;  // 位置不合法

    return list->data[position - 1];  // 返回元素
}

获取线性表的长度

int getListLength(const SequentialList *list) {
    return list->length;  // 返回线性表长度
}

 查找元素

int findElement(const SequentialList *list, int element) {
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == element) {
            return i + 1;  // 返回元素的位置
        }
    }
    return 0;  // 元素不存在
}

线性表的链式存储

使用一组任意的存储单元来存储线性表的数据元素，这些存储单元可以是连续的，也可以是不连续的。在链式存储结构中，数据元素的逻辑顺序是通过每个节点中的指针来实现的，而不是通过它们在内存中的物理位置。链式存储结构通常通过链表来实现，链表中的每个元素称为节点，包含数据域和指针域。

链式存储基本操作

结构定义

typedef struct Node {
    int data;                 // 数据域，存储节点的数据
    struct Node* next;        // 指针域，指向下一个节点的指针
} Node;

初始化线性表

初始化线性表是创建一个空的线性表，设置头指针为NULL

Node* initList() {
    return NULL;  // 返回一个空链表的头指针
}

创建节点

创建一个新节点，通常需要提供数据。

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->next = NULL;
    }
    return newNode;
}

插入元素

在链式存储的线性表中插入元素，需要更新节点的指针。

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

删除元素

删除元素需要更新节点的指针。

void deleteNode(Node** head, Node* delNode) {
    if (*head == delNode) {
        *head = (*head)->next;
        free(delNode);
    } else {
        Node* temp = *head;
        while (temp->next != NULL && temp->next != delNode) {
            temp = temp->next;
        }
        if (temp->next == delNode) {
            temp->next = delNode->next;
            free(delNode);
        }
    }
}

访问元素

访问元素需要从头节点开始遍历链表。

int getElement(Node* head, int position) {
    Node* current = head;
    int index = 1;
    while (current != NULL && index < position) {
        current = current->next;
        index++;
    }
    if (current == NULL || index > position) {
        return -1;  // 位置不合法或元素不存在
    }
    return current->data;
}

获取线性表的长度

获取线性表的长度需要遍历链表。

int getListLength(Node* head) {
    int length = 0;
    Node* current = head;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

清空线性表

清空线性表需要释放所有节点。

void clearList(Node** head) {
    Node* current = *head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    *head = NULL;
}

查找元素

查找元素涉及遍历链表以查找具有特定值的元素。

Node* findElement(Node* head, int element) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == element) {
            return current;
        }
        current = current->next;
    }
    return NULL;  // 元素不存在
}