当前位置： 首页 > article >正文

数据结构---线性表

article 2025/2/3 23:20:41

线性表

顺序表

线性表的顺序存储结构是一种随机存取的存储结构，即通过首地址和元素序号可以在O(1)时间内找到指定的元素。由于线性表的长度可变，且所需最大存储空间随问题的不同而不同，在C/C++中常用动态分配的一维数组(vector)表示线性表
在这里插入图片描述
代码示例如下：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100  // 定义顺序表的最大长度

// 定义顺序表结构
typedef struct {
    int data[MAX_SIZE];  // 存储数据元素的数组
    int length;          // 当前顺序表的长度
} SeqList;

// 初始化顺序表
void InitList(SeqList *L) {
    L->length = 0;  // 初始化长度为 0
}

// 插入操作
int InsertList(SeqList *L, int i, int e) {
    // 判断插入位置是否合法
    if (i < 1 || i > L->length + 1) {
        printf("插入位置不合法！\n");
        return 0;  // 插入失败
    }
    // 判断顺序表是否已满
    if (L->length >= MAX_SIZE) {
        printf("顺序表已满，无法插入！\n");
        return 0;  // 插入失败
    }
    // 将第 i 个位置及之后的元素后移
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j - 1];
    }
    // 插入新元素
    L->data[i - 1] = e;
    L->length++;  // 长度加 1
    return 1;     // 插入成功
}

// 删除操作
int DeleteList(SeqList *L, int i, int *e) {
    // 判断删除位置是否合法
    if (i < 1 || i > L->length) {
        printf("删除位置不合法！\n");
        return 0;  // 删除失败
    }
    // 返回被删除的元素
    *e = L->data[i - 1];
    // 将第 i 个位置之后的元素前移
    for (int j = i; j < L->length; j++) {
        L->data[j - 1] = L->data[j];
    }
    L->length--;  // 长度减 1
    return 1;     // 删除成功
}

// 查找操作
int LocateElem(SeqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;  // 返回元素位置（从 1 开始）
        }
    }
    return 0;  // 未找到
}

// 获取元素操作
int GetElem(SeqList L, int i, int *e) {
    // 判断位置是否合法
    if (i < 1 || i > L.length) {
        printf("位置不合法！\n");
        return 0;  // 获取失败
    }
    *e = L.data[i - 1];  // 返回元素值
    return 1;            // 获取成功
}

// 打印顺序表
void PrintList(SeqList L) {
    printf("顺序表中的元素为：");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
}

// 主函数测试
int main() {
    SeqList L;
    InitList(&L);  // 初始化顺序表

    // 插入元素
    InsertList(&L, 1, 10);
    InsertList(&L, 2, 20);
    InsertList(&L, 3, 30);
    PrintList(L);  // 打印顺序表

    // 查找元素
    int pos = LocateElem(L, 20);
    if (pos) {
        printf("元素 20 的位置是：%d\n", pos);
    } else {
        printf("未找到元素 20\n");
    }

    // 删除元素
    int e;
    if (DeleteList(&L, 2, &e)) {
        printf("删除的元素是：%d\n", e);
    }
    PrintList(L);  // 打印顺序表

    // 获取元素
    int value;
    if (GetElem(L, 1, &value)) {
        printf("第 1 个元素是：%d\n", value);
    }

    return 0;
}

链表

链式存储是一种用一组任意的存储单元来存储线性表中数据元素的方法。采用这种方式存储的线性表简称为线性链表。这些存储单元可以是连续的，也可以是不连续的，甚至可以零散分布在内存中的任意位置。因此，链表中结点的逻辑顺序和物理顺序不一定相同。

为了正确表示结点之间的逻辑关系，在存储每个结点数据的同时，还必须存储其直接后继结点的地址（或位置），这部分信息称为指针（pointer）或链（link）。数据域和指针域共同组成了链表中的结点结构。

单链表：

链表通过每个结点的指针域，将线性表的 n 个结点按照逻辑次序链接在一起。如果每个结点只包含一个指针域，则称为单链表。单链表的指针域指向其后继结点，从而形成一种单向的逻辑链接关系

首元结点：链表中存储第一个数据元素的结点
头指针：通常使用“头指针”来标识一个链表，如单链表L，头指针为NULL的时表示一个空链表。链表非空时，头指针指向的是第一个结点的存储位置。

L->next==NULL;//带头结点的单链表为空时
L=NULL;//不带头结点的单链表为空时

头结点：在单链表的第一个结点之前附加一个结点，称为头结点。头结点的Data域可以不设任何信息，也可以记录表长等相关信息。若链表是带有头结点的，则头指针指向头结点的存储位置。
（无论是否有头结点，头指针始终指向链表的第一个结点。如果有头结点，头指针就指向头结点（只不过头结点的数据域可能为空而已）。）在这里插入图片描述
链表的基本操作示意图
在这里插入图片描述
在这里插入图片描述

//链表
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// 在链表尾部插入节点
void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// 删除指定值的节点
void deleteNode(Node** head, int key) {
    Node* temp = *head;
    Node* prev = NULL;

    // 如果头节点就是要删除的节点
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    // 查找要删除的节点
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // 如果没有找到要删除的节点
    if (temp == NULL) return;

    // 从链表中移除节点
    prev->next = temp->next;
    free(temp);
}

// 打印链表
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 释放链表内存
void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    Node* head = NULL;

    insertAtHead(&head, 3);
    insertAtHead(&head, 2);
    insertAtHead(&head, 1);
    insertAtTail(&head, 4);
    insertAtTail(&head, 5);

    printf("Initial list: ");
    printList(head);

    deleteNode(&head, 3);
    printf("After deleting node with value 3: ");
    printList(head);

    freeList(head);
    return 0;
}

循环链表

循环链表（Circular Linked List）：是一种头尾相接的链表。其特点是最后一个节点的指针域指向链表的头结点，整个链表的指针域连接成一个环。
从循环链表的任意一个节点出发都可以找到链表中的其他节点，使得表处理更加方便灵活。
在这里插入图片描述
1.判断是否是空链表：head->next==head

2.判断是否是表尾节点：p->next==head

#include <stdio.h>
#include <stdlib.h>

// 定义循环链表的结点结构
typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域，指向下一个结点
} Node, *CircularLinkedList;

// 初始化循环链表
void InitList(CircularLinkedList *L) {
    *L = (CircularLinkedList)malloc(sizeof(Node));  // 创建头结点
    (*L)->next = *L;  // 头结点的指针域指向自身，形成循环
}

// 插入操作：在循环链表的第 i 个位置插入元素 e
int InsertList(CircularLinkedList L, int i, int e) {
    Node *p = L;
    int j = 0;

    // 找到第 i-1 个结点
    while (p->next != L && j < i - 1) {
        p = p->next;
        j++;
    }

    // 判断插入位置是否合法
    if (j != i - 1) {
        printf("插入位置不合法！\n");
        return 0;  // 插入失败
    }

    // 创建新结点
    Node *s = (Node *)malloc(sizeof(Node));
    s->data = e;

    // 插入新结点
    s->next = p->next;
    p->next = s;
    return 1;  // 插入成功
}

// 删除操作：删除循环链表中第 i 个位置的元素，并将其值返回
int DeleteList(CircularLinkedList L, int i, int *e) {
    Node *p = L;
    int j = 0;

    // 找到第 i-1 个结点
    while (p->next != L && j < i - 1) {
        p = p->next;
        j++;
    }

    // 判断删除位置是否合法
    if (p->next == L || j != i - 1) {
        printf("删除位置不合法！\n");
        return 0;  // 删除失败
    }

    // 删除结点
    Node *q = p->next;
    *e = q->data;
    p->next = q->next;
    free(q);  // 释放被删除结点的内存
    return 1;  // 删除成功
}

// 查找操作：查找循环链表中第一个值为 e 的元素的位置
int LocateElem(CircularLinkedList L, int e) {
    Node *p = L->next;
    int pos = 1;

    // 遍历链表
    while (p != L) {
        if (p->data == e) {
            return pos;  // 返回元素位置
        }
        p = p->next;
        pos++;
    }
    return 0;  // 未找到
}

// 获取元素操作：获取循环链表中第 i 个位置的元素
int GetElem(CircularLinkedList L, int i, int *e) {
    Node *p = L->next;
    int j = 1;

    // 遍历链表
    while (p != L && j < i) {
        p = p->next;
        j++;
    }

    // 判断位置是否合法
    if (p == L || j > i) {
        printf("位置不合法！\n");
        return 0;  // 获取失败
    }

    *e = p->data;  // 返回元素值
    return 1;      // 获取成功
}

// 打印循环链表
void PrintList(CircularLinkedList L) {
    Node *p = L->next;
    printf("循环链表中的元素为：");
    while (p != L) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 主函数测试
int main() {
    CircularLinkedList L;
    InitList(&L);  // 初始化循环链表

    // 插入元素
    InsertList(L, 1, 10);
    InsertList(L, 2, 20);
    InsertList(L, 3, 30);
    PrintList(L);  // 打印循环链表

    // 查找元素
    int pos = LocateElem(L, 20);
    if (pos) {
        printf("元素 20 的位置是：%d\n", pos);
    } else {
        printf("未找到元素 20\n");
    }

    // 删除元素
    int e;
    if (DeleteList(L, 2, &e)) {
        printf("删除的元素是：%d\n", e);
    }
    PrintList(L);  // 打印循环链表

    // 获取元素
    int value;
    if (GetElem(L, 1, &value)) {
        printf("第 1 个元素是：%d\n", value);
    }

    return 0;
}

双向链表

双向链表（Double Linkedd List）:指的是构成链表的每个节点中设立两个指针域：一个指向其直接前驱的指针域prior，一个指向其直接后继的指针域next。这样形成的链表中有两个方向不同的链，故称为双向链表。
将头结点和尾节点连接起来也能构成循环链表，并称之为双向循环链表。
在这里插入图片描述
在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>

// 定义双向链表的结点结构
typedef struct Node {
    int data;               // 数据域
    struct Node *prev;      // 前驱指针
    struct Node *next;      // 后继指针
} Node, *DoublyLinkedList;

// 初始化双向链表
void InitList(DoublyLinkedList *L) {
    *L = (DoublyLinkedList)malloc(sizeof(Node));  // 创建头结点
    (*L)->prev = *L;  // 头结点的前驱指向自身
    (*L)->next = *L;  // 头结点的后继指向自身
}

// 插入操作：在双向链表的第 i 个位置插入元素 e
int InsertList(DoublyLinkedList L, int i, int e) {
    Node *p = L;
    int j = 0;

    // 找到第 i-1 个结点
    while (p->next != L && j < i - 1) {
        p = p->next;
        j++;
    }

    // 判断插入位置是否合法
    if (j != i - 1) {
        printf("插入位置不合法！\n");
        return 0;  // 插入失败
    }

    // 创建新结点
    Node *s = (Node *)malloc(sizeof(Node));
    s->data = e;

    // 插入新结点
    s->next = p->next;
    s->prev = p;
    p->next->prev = s;
    p->next = s;
    return 1;  // 插入成功
}

// 删除操作：删除双向链表中第 i 个位置的元素，并将其值返回
int DeleteList(DoublyLinkedList L, int i, int *e) {
    Node *p = L->next;
    int j = 1;

    // 找到第 i 个结点
    while (p != L && j < i) {
        p = p->next;
        j++;
    }

    // 判断删除位置是否合法
    if (p == L || j > i) {
        printf("删除位置不合法！\n");
        return 0;  // 删除失败
    }

    // 删除结点
    *e = p->data;
    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p);  // 释放被删除结点的内存
    return 1;  // 删除成功
}

// 查找操作：查找双向链表中第一个值为 e 的元素的位置
int LocateElem(DoublyLinkedList L, int e) {
    Node *p = L->next;
    int pos = 1;

    // 遍历链表
    while (p != L) {
        if (p->data == e) {
            return pos;  // 返回元素位置
        }
        p = p->next;
        pos++;
    }
    return 0;  // 未找到
}

// 获取元素操作：获取双向链表中第 i 个位置的元素
int GetElem(DoublyLinkedList L, int i, int *e) {
    Node *p = L->next;
    int j = 1;

    // 遍历链表
    while (p != L && j < i) {
        p = p->next;
        j++;
    }

    // 判断位置是否合法
    if (p == L || j > i) {
        printf("位置不合法！\n");
        return 0;  // 获取失败
    }

    *e = p->data;  // 返回元素值
    return 1;      // 获取成功
}

// 打印双向链表
void PrintList(DoublyLinkedList L) {
    Node *p = L->next;
    printf("双向链表中的元素为：");
    while (p != L) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 主函数测试
int main() {
    DoublyLinkedList L;
    InitList(&L);  // 初始化双向链表

    // 插入元素
    InsertList(L, 1, 10);
    InsertList(L, 2, 20);
    InsertList(L, 3, 30);
    PrintList(L);  // 打印双向链表

    // 查找元素
    int pos = LocateElem(L, 20);
    if (pos) {
        printf("元素 20 的位置是：%d\n", pos);
    } else {
        printf("未找到元素 20\n");
    }

    // 删除元素
    int e;
    if (DeleteList(L, 2, &e)) {
        printf("删除的元素是：%d\n", e);
    }
    PrintList(L);  // 打印双向链表

    // 获取元素
    int value;
    if (GetElem(L, 1, &value)) {
        printf("第 1 个元素是：%d\n", value);
    }

    return 0;
}

有时候，白纸一张更能呈现无尽可能。 —《帕特森》


http://www.kler.cn/a/530346.html

相关文章：

  • RDP协议详解
  • 【Elasticsearch】_all 查询
  • sysbench压力测试工具mysql以及postgresql
  • Workbench 中的热源仿真
  • LeetCode：300.最长递增子序列
  • Node.js 和 npm 安装教程
  • Linux网络 | 理解运营商与网段划分、理解NAT技术和分片
  • 开源智慧园区管理系统对比其他十种管理软件的优势与应用前景分析
  • 专业的定制版软件，一键操作，无限使用
  • 在React中使用redux
  • 从零开始玩转 Docker：用 Node.js 打印“Hello World”
  • MySQL的GROUP BY与COUNT()函数的使用问题
  • Skewer v0.2.2安装与使用-生信工具43
  • AlexNet论文代码阅读
  • OpenAI发布最新推理模型o3-mini
  • 1. 【.NET 8 实战--孢子记账--从单体到微服务--转向微服务】--前言
  • Nginx开发01：基础配置
  • AI模型平台之——ModelScope(魔搭)
  • 面试题-消失的数字-异或
  • 线性回归的损失和优化02
  • 小红的合数寻找
  • DeepSeek 详细使用教程
  • 笔灵ai写作技术浅析（三）：深度学习
  • 携程Java开发面试题及参考答案 （200道-上）
  • 深度学习 DAY3：NLP发展史（全网最全）
  • 【Windows7和Windows10下从零搭建Qt+Leaflet开发环境】