C 语言数据结构——链表
|
181
|
0
|
Linux C / C++,计算机基础

3884 字
|
25 分钟

单链表的基本概念

  1. 结点（Node）：
    • 结点是单链表中用于存储数据的基本单元。每个结点通常包含两个部分：数据域和指针域。数据域用于存储数据，而指针域则用于存储指向下一个结点的指针。
  2. 头结点（Head Node）：
    • 头结点是一种特殊的结点，也称为虚拟结点或哨兵结点。它通常不存储数据，或者可以存储链表的元数据，如链表长度。
    • 在带有头结点的链表中，头结点是链表的第一个结点，它的存在可以简化链表操作的逻辑。
  3. 尾结点（Tail Node）：
    • 尾结点是链表中的最后一个结点。它仍然包含数据域，但指针域指向 NULL，表示链表的结束。
  4. 头指针（Head Pointer）：
    • 头指针是指向单链表第一个结点的指针。它是链表操作的起点，对于单链表来说至关重要。
    • 如果链表的头指针是 NULL，则表示链表为空。如果链表带有头结点，头指针指向头结点；否则，它指向第一个带有数据的结点。
  5. 尾指针（Tail Pointer）：
    • 尾指针是指向单链表最后一个结点（尾结点）的指针。虽然尾指针不是必需的，但它的存在可以使得链表尾部的操作更加方便和高效。
  6. 构建单链表的方法：
    • 头插法（Head Insertion）：在链表的头部插入一个结点，使得新结点成为新的头结点。这需要更新头指针。
    • 尾插法（Tail Insertion）：在链表的尾部插入一个结点，使得新结点成为新的尾结点。这需要更新尾指针（如果存在）。

常见的链表主要可以分为以下几种类型：

202311152050220.png

单链表的基本/核心操作

  1. 创建单链表：创建单链表通常从创建头结点开始，然后根据需要添加数据结点。
  2. 销毁单链表：销毁单链表需要释放链表中所有结点的内存。这通常通过遍历链表并逐个释放结点来完成。
  3. 插入新结点：插入操作可以在链表的头部或尾部进行： a. 头插法：在链表头部插入新结点，新结点成为链表的第一个结点。 b. 尾插法：在链表尾部插入新结点，新结点成为链表的最后一个结点。
  4. 根据索引插入结点：在链表的指定位置插入新结点，需要先遍历链表找到插入点，然后调整指针。
  5. 删除结点：删除操作可以基于元素的值或索引：
    1. 根据元素值删除：遍历链表，找到具有特定值的结点，并从链表中移除。
    2. 根据索引删除：遍历链表，找到特定索引的结点，并从链表中移除。
  6. 查询结点：查询操作可以基于数据域的值或索引：
    1. 根据值查询：遍历链表，查找具有特定值的第一个结点。
    2. 根据索引查询：遍历链表，查找特定索引的结点。
  7. 遍历单链表：遍历单链表是最基本的操作之一，通常用于访问链表中的每个结点，进行打印或其他处理。

202311161556943.png

单链表的创建和销毁

创建单链表

LinkedList *create_linked_list() {
    return calloc(1, sizeof(LinkedList));
}

销毁单链表

  1. 释放链表结点：从链表的头部开始，逐个结点释放内存。在释放当前结点之前，需要先保存下一个结点的地址。
  2. 释放链表结构：在所有结点都被释放之后，释放整个链表结构的内存。

遍历链表的标准做法：

遍历单链表是许多链表操作的基础，以下是一般的步骤：

  1. 初始化当前结点：创建一个指针 current，通常指向链表的头结点 list->head。
  2. 使用 while 循环：使用 while 循环来遍历链表，条件通常是 (current != NULL)。
  3. 处理逻辑：在循环体内部，执行需要的操作，例如打印结点数据或销毁结点。
  4. 移动到下一个结点：在循环的每次迭代结束时，更新 current 指针以指向下一个结点，通常使用 current = current->next;。
  5. 循环结束条件：循环继续进行，直到 current 为 NULL，表示已经到达链表的末尾。
void destroy_linked_list(LinkedList *list) {
    Node *curr = list->head;
    while (curr != NULL) {
        Node *next = curr->next; // 保存下一个结点
        free(curr);              // 释放当前结点
        curr = next;             // 移动到下一个结点
    }
    // 链表的所有结点都已释放，现在可以释放链表结构本身
    free(list);
}

打印链表

  1. 初始化当前结点：使用一个指针 curr 初始化为链表的头结点 list->head。
  2. 遍历链表：使用 while 循环遍历链表，直到 curr 为 NULL。
  3. 打印当前结点数据：在循环内部，打印当前结点 curr 的数据域 curr->data。
  4. 添加箭头指示：如果当前结点不是链表的最后一个结点（即 curr->next 不为 NULL），则打印一个箭头 -> 作为分隔。
  5. 移动到下一个结点：在循环的每次迭代结束时，将 curr 更新为下一个结点 curr->next。
  6. 完成打印：在所有结点都被打印后，打印一个换行符 \n。
void print_list(LinkedList *list) {
    Node *curr = list->head;
    while (curr != NULL) {
        printf("%d ->", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

插入节点

头插法插入结点

202401072127493.png

202401072135870.png

  1. 创建新结点：分配内存给新结点。
  2. 初始化新结点：
    • 给新结点的数据域赋值。
    • 将新结点的指针域指向原本的第一个结点。
  3. 更新链表结构信息：
    • 头指针指向新结点，使其成为链表的第一个结点。
    • 如果尾结点指针为 NULL（意味着以前的链表是空的），则更新尾结点指针指向新结点。
    • 链表长度增加 1。
bool add_before_head(LinkedList *list, DataType new_data) {
    Node *new_node = malloc(sizeof(Node));

    if (new_node == NULL) {
        printf("错误：malloc 在 add_before_head 中失败。\n");
        return false;
    }
    new_node->data = new_data;
    new_node->next = list->head; // 新结点指向原本的第一个结点

    list->head = new_node; // 新结点成为第一个结点
    if (list->tail == NULL) {
        list->tail = new_node; // 如果链表为空，更新尾结点指针
    }
    list->size++;
    return true;
}

尾插法插入结点

  1. 创建新结点：分配内存给新结点。
  2. 初始化新结点：
    • 给新结点的数据域赋值。
    • 将新结点的指针域指向 NULL，因为新结点要成为新的尾结点。
  3. 更新链表结构信息：
    • 如果以前的链表为空（尾结点指针为 NULL），则头指针也应该指向新结点。
    • 如果以前的链表非空，则头指针不用更新。只需要将以前的尾结点指针指向的新结点，指向新创建的结点（即更新前一个尾结点的 next 指针）。需要注意的是，这步需要保证单链表非空才能够执行否则链表没有结点，只有 NULL，将导致空指针操作的问题。
    • 将链表的尾结点指针指向新结点。
    • 链表长度增加 1。
bool add_behind_tail(LinkedList *list, DataType new_data) {
    // 分配新结点, 并初始化数据域和指针域
    Node *new_node = malloc(sizeof(Node));
    if (new_node == NULL) {
        printf("错误：malloc 在 add_behind_tail 中失败");
        return false;
    }

    new_node->data = new_data;
    new_node->next = NULL;

    if (list->tail == NULL) {
        // 链表为空
        list->head = new_node;
        list->tail = new_node; // 旧尾结点指向新结点
    } else {
        // 链表非空，将新结点链接到当前尾结点
        list->tail->next = new_node;
    }
    list->tail = new_node; // 更新尾结点指针
    list->size++;
    return true;
}

根据索引插入结点

  1. 参数校验：确保提供的索引 idx 在合法范围内，即 [0, 链表长度]。
  2. 边界值处理：
    • 如果索引为 0，则执行头插法。
    • 如果索引等于链表长度，则执行尾插法。
  3. 中间插入结点：
    • 创建一个新结点，并将其数据部分设置为要插入的数据。
    • 使用一个 current 结点指针遍历链表，找到目标索引的前一个结点。
    • 将新结点的指针指向 current 结点的下一个结点。
    • 将 current 结点的指针指向新结点。
    • 更新链表长度。
bool add_by_idx(LinkedList *list, int idx, DataType new_data) {
    if (idx < 0 || idx > list->size) {
        printf("错误：非法的传参 idx：%d！\n", idx);
        return false;
    }

    if (idx == 0) {
        return add_before_head(list, new_data);
    }

    if (idx == list->size) {
        return add_behind_tail(list, new_data);
    }

    Node *new_node = malloc(sizeof(Node));
    if (new_node == NULL) {
        printf("错误：malloc 在 add_by_idx 中失败！\n");
        return false;
    }

    new_node->data = new_data;
    Node *prev = list->head;
    for (int i = 0; i < idx - 1; ++i) {
        prev = prev->next;
    } // for 循环结束时, prev 指针指向 idx - 1 位置的结点
    new_node->next = prev->next;
    prev->next = new_node;
    list->size++;

    return true;
}

查找与删除结点

根据索引查找结点

  1. 参数校验：确保提供的索引 idx 在合法范围内，即 [0, 链表长度 - 1]。
  2. 遍历链表：使用一个指针 current 从链表的头结点开始遍历链表。
  3. 查找目标索引的结点：在遍历过程中，通过索引计数来查找目标索引的结点。当索引计数等于提供的索引 idx 时，停止遍历。
  4. 返回结点：如果找到了目标索引的结点，则返回该结点的指针。如果没有找到（索引超出范围），则返回 NULL。
Node *search_by_data(LinkedList *list, DataType data) {
    Node *curr = list->head;

    while (curr != NULL) {
        if (data == curr->data) {
            return curr;
        }
        curr = curr->next;
    }
    return NULL;
}

根据索引删除结点

  1. 参数校验：确保链表不为空，并且提供的索引 idx 在合法范围内，即 [0, 链表长度 - 1]。
  2. 删除第一个结点：如果索引为 0，则删除头结点。更新头指针指向下一个结点，并处理尾指针。
  3. 删除非第一个结点：如果索引不为 0，则需要遍历链表找到待删除结点的前一个结点。
  4. 更新指针：将前一个结点的 next 指针指向待删除结点的下一个结点，从而绕过待删除结点。
  5. 更新尾指针：如果删除的是尾结点，需要更新尾指针指向新的最后一个结点。
  6. 释放内存：释放待删除结点的内存。
  7. 更新链表长度。
bool delete_by_idx(LinkedList *list, int idx) {
    if (idx < 0 || idx > list->size) {
        printf("错误：非法的传参 idx：%d！\n", idx);
        return false;
    }

    Node *curr = list->head;
    Node *prev = NULL;

    if (idx == 0) {
        list->head = curr->next;
        if (list->size == 1) {
            list->tail = NULL;
        }
        free(curr);
        list->size--;
        return true;
    }

    curr = curr->next;
    for (int i = 0; i < idx - 1; ++i) {
        prev = curr;
        curr = curr->next;
    }
    prev->next = curr->next;
    if (idx == list->size - 1) {
        list->tail = NULL;
    }
    free(curr);
    list->size--;
    return true;
}

根据数据删除一个结点

202311201732619.png

202311202132276.png

  1. 处理头结点情况：如果头结点包含要删除的数据，更新头指针指向下一个结点，并释放原头结点的内存。
  2. 处理非头结点情况：使用两个指针 prev 和 curr 遍历链表，prev 指向当前结点的前一个结点，curr 指向当前结点。
  3. 查找并删除结点：在遍历过程中，找到包含要删除数据的结点，更新 prev 结点的 next 指针指向 curr 结点的下一个结点。
  4. 更新尾指针：如果删除的是尾结点，更新尾指针指向 prev 结点。
  5. 释放内存：释放被删除结点的内存。
  6. 更新链表长度。
bool delete_by_data(LinkedList *list, DataType data) {
    Node *curr = list->head;
    Node *prev = NULL;

    // 如果要删除的结点是第一个结点
    if (curr->data == data) {
        list->head = curr->next;
        if (list->head == NULL) {
            list->tail = NULL;
        }
        free(curr);
    } else {
        // 从第二个结点开始遍历查找待删除目标结点
        while (curr != NULL && curr->data != data) {
            prev = curr;
            curr = curr->next;
        }

        // 如果找到了目标结点
        if (curr != NULL) {
            prev->next = curr->next;
            if (prev->next == NULL) {
                list->tail = prev;
            }
            free(curr);
        } else {
            // 未找到目标结点
            return false;
        }
    }
    list->size--;
    return true;
}

相关题目：203. 移除链表元素

单链表总结

  1. 头部操作的时间复杂度：由于头部操作通常只涉及更新头指针，因此大多数头部操作（如头插、删除头部结点、访问头部结点）具有 O(1) 的时间复杂度。
  2. 尾部操作的时间复杂度：尾指针的存在使得在链表尾部新增结点（尾插）的操作也具有 O(1) 的时间复杂度。
  3. 结点操作的限制：单链表只能在一个确定的结点后面执行操作，如新增、删除、访问，因为单链表的每个结点只有一个指向后继结点的指针。
  4. 前驱结点的操作：任何在结点前面的操作都需要先遍历链表找到前驱结点，然后在结点的后面执行操作，此时时间复杂度为 O(n)。
  5. 双向链表的优势：双向链表在每个结点上增加了一个指向前驱结点的指针，这使得在任意结点附近（前后）都可以直接进行 O(1) 时间复杂度的操作。

结论：

  • 单链表在头部和尾部操作具有时间复杂度的优势，但在中间结点的操作受到限制。
  • 双向链表提供了更高的灵活性和效率，特别是在需要频繁访问和修改链表中间结点的场景中，因此它是更普遍的选择。

快慢指针

快慢指针法的基本原理：

  1. 初始化指针：同时初始化两个指针 slow 和 fast，它们都指向链表的头部。
  2. 遍历链表：在链表中进行遍历，每次遍历时，将 fast 指针向前移动两步，而 slow 指针只向前移动一步。
  3. 结束条件：当 fast 指针到达链表末尾或其下一个节点为 NULL 时，遍历结束。
  4. 中间节点：在遍历结束时，slow 指针将指向链表的中间节点。

相关题目：141. 环形链表

bool hasCycle(struct ListNode *head) {
    struct ListNode *fast = head;
    struct ListNode *slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) {
            return true;
        }
    }
    return false;
}

单链表的反转

循环解法

  1. 初始化指针：
    • 需要三个指针：curr、prev 和 next。
    • curr 用于遍历链表，初始时指向链表的第一个结点。
    • prev 用于指向 curr 的前驱结点，初始时指向 NULL。
    • next 用于临时存储 curr 的后继结点。
  2. 遍历链表：
    • 从链表的头结点开始，使用 curr 指针遍历链表。
    • 当 curr 指向 NULL 时，遍历结束，反转完成。
  3. 反转指针：
    • 在遍历的过程中，首先使用 next 指针存储 curr 的后继结点（curr->next）。
    • 然后，将 curr 结点的 next 指针指向 prev，完成当前结点的反转。
  4. 更新指针：在每次遍历后，更新 prev 为 curr，然后将 curr 移动到 next 指向的位置。
  5. 循环结束：当 curr 指向 NULL 时，prev 将指向原本的尾结点，即反转后链表的第一个结点。
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* curr = head;
    struct ListNode* prev = NULL;
    while(curr) {
        struct ListNode* succ = curr->next;
        curr->next = prev;
        prev = curr;
        curr = succ;
    }
    return prev;
}

递归解法

  1. 递归体：递归体是递归函数中自我调用的部分，它负责将问题分解为更小的子问题。
  2. 分解思路：对于一个有 n 个结点的单链表，我们可以将其分解为：反转第一个结点和剩余的 n-1 个结点的单链表。
  3. 递归出口：当链表为空（head == NULL）或只有一个结点（head->next == NULL）时，递归结束。
  4. 递归逻辑：
    • 在递归中，首先处理第一个结点的反转，即将其 next 指针指向之前已经反转的部分。
    • 然后，递归调用处理剩余链表的反转。
    • 首先，递归调用反转函数，以处理链表剩余的 n-1 个结点。这一步是递归的主体，它将问题分解为更小的子问题。
    • 在递归调用返回后，处理反转后的 n-1 个结点中的尾结点，使其指向原本的第一个结点（head）。这一步是递归过程中的关键操作，它将反转后的子链表与原链表连接起来。
    • 最后，更新 head 指针指向递归调用返回的新头指针。这一步是递归出口的一部分，它确保了整个链表的反转。

msedge_pACh186f6Y.png

struct ListNode* reverse(struct ListNode* pre, struct ListNode* cur) {
    if(!cur)
        return pre;
    struct ListNode* temp = cur->next;
    cur->next = pre;
    return reverse(cur, temp);
}

struct ListNode* reverseList(struct ListNode* head){
    return reverse(NULL, head);
}
C数据结构
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇