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

线性表之链式表

article 2024/11/13 14:33:47

文章目录

主要内容

  1. 单链表
  2. 双链表和循环链表

链式表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链式表具有灵活的插入和删除操作，但访问元素的效率较低。

一.单链表

单链表是最简单的链表结构之一。它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。单链表的特点是只能从头节点开始依次访问每个节点，无法直接访问任意位置的节点。这使得单链表在插入和删除操作时效率较高，但在查找和访问特定节点时效率较低。

1.头插法建立单链表

代码如下（示例）:

C语言代码：

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createListByHeadInsert(int arr[], int n) {
    Node* head = (Node*)malloc(sizeof(Node));
    head->next = NULL;

    for (int i = 0; i < n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = head->next;
        head->next = newNode;
    }

    return head;
}

Python代码：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def create_list_by_head_insert(arr):
    head = Node(None)

    for data in arr:
        new_node = Node(data)
        new_node.next = head.next
        head.next = new_node

    return head

2.尾插法建立单链表

代码如下（示例）:

C语言代码：

Node* createListByTailInsert(int arr[], int n) {
    Node* head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    Node* tail = head;

    for (int i = 0; i < n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
    }

    return head;
}

Python代码：

def create_list_by_tail_insert(arr):
    head = Node(None)
    tail = head

    for data in arr:
        new_node = Node(data)
        tail.next = new_node
        tail = new_node

    return head

3.按序号查找结点值

代码如下（示例）:

C语言代码：

int getElemByIndex(Node* head, int index) {
    Node* p = head->next;
    int i = 1;

    while (p && i < index) {
        p = p->next;
        i++;
    }

    if (!p || i > index) {
        return -1;
    }

    return p->data;
}

Python代码：

def get_elem_by_index(head, index):
    p = head.next
    i = 1

    while p and i < index:
        p = p.next
        i += 1

    if not p or i > index:
        return -1

    return p.data

4.按值查找表结点

代码如下（示例）:

C语言代码：

Node* locateElem(Node* head, int value) {
    Node* p = head->next;

    while (p && p->data != value) {
        p = p->next;
    }

    return p;
}

Python代码：

def locate_elem(head, value):
    p = head.next

    while p and p.data != value:
        p = p.next

    return p

5.插入节点操作

代码如下（示例）:

C语言代码：

void insertElem(Node* head, int index, int value) {
    Node* p = head;
    int i = 0;

    while (p && i < index - 1) {
        p = p->next;
        i++;
    }

    if (!p || i > index - 1) {
        return;
    }

    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = p->next;
    p->next = newNode;
}

Python代码：

def insert_elem(head, index, value):
    p = head
    i = 0

    while p and i < index - 1:
        p = p.next
        i += 1

    if not p or i > index - 1:
        return

    new_node = Node(value)
    new_node.next = p.next
    p.next = new_node

6.删除结点操作

代码如下（示例）:

C语言代码：

void deleteElem(Node* head, int value) {
    Node* p = head;
    while (p->next && p->next->data != value) {
        p = p->next;
    }

    if (p->next) {
        Node* temp = p->next;
        p->next = temp->next;
        free(temp);
    }
}

Python代码：

def delete_elem(head, value):
    p = head
    while p.next and p.next.data != value:
        p = p.next

    if p.next:
        temp = p.next
        p.next = temp.next
        del temp

7.求表长操作

代码如下（示例）:

C语言代码：

int getLength(Node* head) {
    Node* p = head->next;
    int length = 0;
    while (p) {
        length++;
        p = p->next;
    }
    return length;
}

Python代码：

def get_length(head):
    p = head.next
    length = 0
    while p:
        length += 1
        p = p.next
    return length

二.双链表和循环链表

双链表在单链表的基础上增加了一个指向前一个节点的指针。这样一来，双链表可以双向遍历，即可以从头节点向后遍历，也可以从尾节点向前遍历。这种特性使得双链表在某些场景下具有更高的灵活性和效率。

1.双链表的插入操作

代码如下（示例）:

C语言实现：

void insertNode(struct Node* prevNode, int newData) {
    if (prevNode == NULL) {
        printf("The given previous node cannot be NULL");
        return;
    }
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
    newNode->prev = prevNode;
    if (newNode->next != NULL) {
        newNode->next->prev = newNode;
    }
}

Python实现：

def insertNode(prev_node, new_data):
    if prev_node is None:
        print("The given previous node cannot be NULL")
        return
    new_node = Node(new_data)
    new_node.next = prev_node.next
    prev_node.next = new_node
    new_node.prev = prev_node
    if new_node.next is not None:
        new_node.next.prev = new_node

2.双链表的删除操作

代码如下（示例）:

C语言实现：

void deleteNode(struct Node** head_ref, struct Node* del) {
    if (*head_ref == NULL || del == NULL) {
        return;
    }
    if (*head_ref == del) {
        *head_ref = del->next;
    }
    if (del->next != NULL) {
        del->next->prev = del->prev;
    }
    if (del->prev != NULL) {
        del->prev->next = del->next;
    }
    free(del);
}

Python实现：

def deleteNode(head_ref, del_node):
    if head_ref is None or del_node is None:
        return
    if head_ref == del_node:
        head_ref = del_node.next
    if del_node.next is not None:
        del_node.next.prev = del_node.prev
    if del_node.prev is not None:
        del_node.prev.next = del_node.next
    del_node = None

循环链表是一种特殊的链表结构，其尾节点指向头节点，形成一个闭环。循环链表可以用于模拟循环队列或循环缓冲区等场景，其特点是可以无限循环访问节点。

3.循环单链表

代码如下（示例）:

C语言实现：

struct Node {
    int data;
    struct Node* next;
};

void insertNode(struct Node** head_ref, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;
    newNode->data = newData;
    newNode->next = *head_ref;
    if (*head_ref == NULL) {
        newNode->next = newNode;
    } else {
        while (last->next != *head_ref) {
            last = last->next;
        }
        last->next = newNode;
    }
    *head_ref = newNode;
}

Python实现：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def insertNode(head_ref, new_data):
    new_node = Node(new_data)
    last = head_ref
    new_node.next = head_ref
    if head_ref is None:
        new_node.next = new_node
    else:
        while last.next != head_ref:
            last = last.next
        last.next = new_node
    head_ref = new_node

循环双链表是一种特殊的链式表，它的最后一个节点指向第一个节点，而第一个节点指向最后一个节点，形成一个循环。循环双链表可以在任意位置插入和删除节点。

4.循环双链表的插入操作

代码如下（示例）:

C语言实现：

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

void insert(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = head;
    newNode->next = head->next;
    head->next->prev = newNode;
    head->next = newNode;
}

Python实现：

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

def insert(head, data):
    new_node = Node(data)
    new_node.prev = head
    new_node.next = head.next
    head.next.prev = new_node
    head.next = new_node

5.循环双链表的删除操作

代码如下（示例）:

C语言实现：

void delete(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node);
}

Python实现：

def delete(node):
    node.prev.next = node.next
    node.next.prev = node.prev

静态链表是一种使用数组来模拟链表结构的数据结构。它的特点是在静态分配的数组中维护节点的关系，而不是使用指针。静态链表在某些特定场景下可以减少指针操作的开销，但也限制了链表的动态性和灵活性。

6.静态链表的基本操作

代码如下（示例）:

C语言实现：

#define MAX_SIZE 100
typedef struct {
    int data;
    int next;
} Node;

int allocate(Node* arr) {
    int i = arr[0].next;
    if (i != -1) {
        arr[0].next = arr[i].next;
    }
    return i;
}

void deallocate(Node* arr, int i) {
    arr[i].next = arr[0].next;
    arr[0].next = i;
}

Python实现：

MAX_SIZE = 100
class Node:
    def __init__(self, data, next):
        self.data = data
        self.next = next

def allocate(arr):
    i = arr[0].next
    if i != -1:
        arr[0].next = arr[i].next
    return i

def deallocate(arr, i):
    arr[i].next = arr[0].next
    arr[0].next = i

总结

以上是今天要讲的内容，学到了链式表中单链表、双链表、循环链表和静态链表的相关操作。
线性表–链式表-1


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

相关文章：

  • 计算机的错误计算（一百五十二）
  • go语言中的log 包详解
  • 用户裂变数据分析
  • Linux权限和开发工具(3)
  • Xshell 7 偏好设置
  • echarts-gl 3D柱状图配置
  • 网工内推 | 中高级网工，IE认证优先，带薪年假，五险一金
  • Windows如何启动MySQL
  • [Linux] linux防火墙
  • 科普 | 隧道代理IP，简化操作提升安全性
  • vue3+vite打包自动生成dist.zip文件
  • JVM
  • 智能合约安全漏洞与解决方案
  • Unity 关于Input类的使用
  • 惠威M200MKII音箱拆机
  • 手摸手Element-ui组件化开发
  • 【C/C++】常见模拟题题解
  • React 和 Vue 在技术层面有哪些区别？
  • JSON.stringify,JSON.parse
  • Linux下文件操作函数
  • 【Linux】 sudo命令使用
  • 每日一题(LeetCode)----哈希表--两数之和
  • ArkUI开发进阶—@Builder函数@BuilderParam装饰器的妙用与场景应用【鸿蒙专栏-05】
  • el-table合并行
  • SecureCRT -- 使用说明
  • 【Apifox】测试工具自动编写接口文档