C语言线性链表时间分享

原创

Jack20

发布于 2025-07-17 15:42:53

10000

代码可运行

运行总次数：0

代码可运行

线性链表的概念

线性链表是一种数据结构，它由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域存储实际数据，而指针域存储指向下一个节点的地址，也称为后继节点。线性链表中的节点在内存中并不需要连续存储，而是通过指针相互连接形成一个逻辑上的连续序列

线性链表的特点

线性链表的主要特点包括：

动态性：线性链表的存储空间可以根据需要动态地分配和释放，这使得链表的长度可以随时改变。
非连续性：线性链表中的节点在内存中可以分散存储，不需要像数组那样连续排列。
访问特性：在链表中访问特定元素通常需要从头节点开始遍历，因此访问效率不如数组。
插入和删除效率：在链表中插入或删除元素通常只需要修改相应的指针，而不需要移动其他元素，因此在某些情况下比数组更高效。

线性链表的实现

线性链表可以通过编程语言提供的各种数据类型和结构来实现。例如，在C++中，可以通过结构体和指针来实现链表节点和链表本身。链表节点通常定义为一个结构体，其中包含了数据和指向下一个节点的指针。链表本身则可以通过一个指向头节点的指针来实现

线性链表的应用

线性链表广泛应用于各种场景，尤其是在需要频繁插入和删除操作的数据结构中。例如，它可以用来实现动态数组、栈、队列等数据结构。在这些应用中，链表的动态性和灵活性使其能够有效地管理数据元素的增删操作。

注意事项

在使用线性链表时，需要注意内存管理和指针操作的正确性。错误的指针操作可能会导致内存泄漏或程序崩溃。此外，由于链表不支持随机访问，访问特定元素通常需要从头节点开始遍历，这可能影响性能。

综上所述，线性链表是一种基本且重要的数据结构，它在许多编程问题中都有应用。了解其特性和实现方法对于掌握数据结构和算法的基础知识至关重要。

已知非空线性链表第1个链结点指针为list，链结点构造为

struct node{
datatype data;
node *link;
};

请写一算法，将该链表中数据域值最大的那个点移到链表的最后面。(假设链表中数据域值最大的链结点惟一）

【输入形式】

输入为一个整数序列，整数之间以空格隔开,序列以回车结尾。

【输出形式】

输出为移动后的整数序列,整数之间以空格隔开,序列以回车结尾。

【样例输入】

3 12 4 9 5 1

【样例输出】

3495112

【样例说明】

将序列中最大的数字12移动到序列最后。

我的算法解题思路

要实现单链表里面数据域值最大的节点移动到链表末尾，需解决

定位最大值的节点：遍历链表，找到数据域最大的节点及其前驱节点（便于后续删除操作）。
处理边界的情况：
- 若最大值节点已是尾节点，无需移动。
- 若最大值节点是头节点，需更新头指针。
节点的移动：
- 将最大值节点从原位置移除（断开与前驱节点的连接）。
- 将其插入到尾节点之后，并置其next指针为NULL。
遍历的优化：在一次遍历中同时记录最大值节点、其前驱节点及尾节点，避免多次遍历。

实现

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

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

// 将最大值节点移动到链表末尾
void moveMaxToTail(Node** head) {
    if (*head == NULL || (*head)->next == NULL) return; // 空链表或单节点无需处理

    Node *prev = NULL, *cur = *head;
    Node *prevMax = NULL, *maxNode = *head; // 最大值节点及其前驱
    Node *tail = *head; // 尾节点

    // 遍历链表，定位最大值节点和尾节点
    while (cur != NULL) {
        if (cur->next == NULL) tail = cur; // 更新尾节点
        if (cur->data > maxNode->data) {   // 更新最大值节点
            maxNode = cur;
            prevMax = prev;
        }
        prev = cur;
        cur = cur->next;
    }

    if (maxNode == tail) return; // 最大值已在末尾

    // 移除最大值节点
    if (prevMax == NULL) *head = (*head)->next; // 最大值是头节点
    else prevMax->next = maxNode->next;        // 最大值是中间节点

    // 插入到尾节点后
    tail->next = maxNode;
    maxNode->next = NULL;
}

// 创建链表（尾插法）
Node* createList(int arr[], int n) {
    Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        if (head == NULL) head = tail = newNode;
        else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

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

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

int main() {
    char input[1000];
    fgets(input, sizeof(input), stdin); // 读取输入行
    int arr[1000], n = 0;
    char* token = strtok(input, " \n"); // 分割空格和换行符

    // 解析整数序列
    while (token != NULL) {
        arr[n++] = atoi(token);
        token = strtok(NULL, " \n");
    }

    Node* head = createList(arr, n);
    moveMaxToTail(&head); // 移动最大值节点
    printList(head);      // 输出结果
    freeList(head);       // 释放内存
    return 0;
}

测试一下

我在程序里面输入：3 12 4 9 5 1
执行过程：

定位最大值节点 12（非尾节点），其前驱为 3。
移除 12：3->next指向 4。
插入末尾：尾节点 1的 next指向 12，链表变为 3→4→9→5→1→12。

于是输出：3 4 9 5 1 12

换一个方法试试

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

struct Node {
 int data;
 struct Node* next;
};
int main()
{
 struct Node* head, *tempHead;
 int data;
 char flag;
 head = (struct Node*)malloc(sizeof(struct Node));

 scanf("%d", &data);
 head->data = data;
 flag = getchar();
 head->next = NULL;
 tempHead = head;

 while (flag != '\n')
 {
  scanf("%d", &data);
  flag = getchar();

  tempHead->next = (struct Node*)malloc(sizeof(struct Node));
  tempHead = tempHead->next;
  tempHead->data = data;
  tempHead->next = NULL;
 }

 struct Node* maxPtr, *endPtr;
 int maxData = head->data;
 maxPtr = endPtr = head;
 while (endPtr->next != NULL)
 {
  endPtr = endPtr->next;
  if (endPtr->data > maxData)
  {
   maxData = endPtr->data;
   maxPtr = endPtr;
  }
 }
 data = maxPtr->data;
 maxPtr->data = endPtr->data;
 endPtr->data = data;


 tempHead = head;
 while (tempHead != NULL)
 {
  printf("%d ", tempHead->data);
  tempHead = tempHead->next;
 }

 return 0;
}

输入的处理：

使用fgets读取整行输入，通过strtok分割空格和换行符解析整数序列。
输入 3 12 4 9 5 1被解析为数组 [3, 12, 4, 9, 5, 1]。

链表的构建：采用尾插法创建链表，确保节点顺序与输入一致。

最大值移动：

定位：遍历时同步记录最大值节点 (maxNode)、其前驱 (prevMax) 和尾节点 (tail)。
移除：
- 若maxNode是头节点，直接更新头指针（如示例中 12被移除后头节点变为 3）。
- 否则，前驱节点跳过maxNode（如 prevMax->next = maxNode->next）。
插入：将maxNode链接到尾节点后（tail->next = maxNode），并置其next为NULL。

输出：按格式打印移动后的链表。

写的这个算法时间复杂度为 O(n)（一次遍历解决），空间复杂度 O(1)（仅需额外指针）。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

数据结构

腾讯技术创作特训营S14#补给站

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

数据结构

腾讯技术创作特训营S14#补给站

#数据结构

登录后参与评论

0 条评论

热度