就爱学编程

就爱学编程

关注
发信
关注(28)粉丝(399)

重生之我在异世界学编程之数据结构与算法：单链表篇

引言

在C语言中，数据结构的掌握对于高效编程至关重要。其中，单链表作为一种基础且常用的数据结构，具有独特的优势和应用场景。下面将对单链表进行详细介绍，并概述其实现方法。一起来看看吧！！！
重生之我在异世界学编程之数据结构与算法：单链表篇-LMLPHP

正文

一、单链表的概念与结构

具体来说，单链表的结构可以定义如下：

 
typedef int SLLDataType; // 单链表存贮的数据类型

typedef struct SLLNode {
    SLLDataType data;      // 数据域
    struct SLLNode* next;  // 指针域，指向下一个节点的地址
} Node;

二、单链表的优势与应用

相较于顺序表（即数组），单链表具有以下优势：

  • 单链表广泛应用于各种数据处理场景中，如实现队列、栈等抽象数据类型，以及解决图论、排序等问题。

三、单链表的实现概述

单链表的实现主要包括以下几个关键步骤：

在C语言中，单链表是一种常见的数据结构，它由一系列节点（Node）组成，每个节点包含数据部分和指向下一个节点的指针。下面我将详细讲解如何用C语言实现单链表的关键部分，包括节点定义、创建链表、插入节点、删除节点以及遍历链表等操作。

1. 定义节点结构

首先，我们需要定义一个结构体来表示链表的节点：

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

// 定义节点结构
typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域，指向下一个节点
} Node;

2. 创建链表

创建一个空链表通常意味着初始化一个头指针为NULL：

Node* createList() {
    return NULL;  // 空链表的头指针为NULL
}

3. 在链表头部插入节点

在链表头部插入一个新节点是一个常见的操作。我们首先需要为新节点分配内存，然后设置其数据和指针，最后更新头指针。

void insertAtHead(Node** head, int newData) {
    // 为新节点分配内存
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation error
");
        return;
    }

    // 设置新节点的数据
    newNode->data = newData;

    // 将新节点的next指针指向当前的头节点
    newNode->next = *head;

    // 更新头指针
    *head = newNode;
}

4. 删除指定值的节点

删除指定值的节点需要遍历链表并找到目标节点的前一个节点，然后修改前一个节点的next指针以跳过目标节点。同时，别忘了释放被删除节点的内存。

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);
}

5. 遍历链表

遍历链表意味着从头节点开始，依次访问每一个节点直到遇到NULL指针。

void printList(Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL
");
}

6. 主函数示例

以下是一个简单的主函数示例，展示了如何使用上述函数来操作单链表：

int main() {
    Node* head = createList();

    insertAtHead(&head, 1);
    insertAtHead(&head, 2);
    insertAtHead(&head, 3);

    printf("Created linked list: ");
    printList(head);

    deleteNode(&head, 2);
    printf("
Linked list after deleting 2: ");
    printList(head);

    return 0;
}

总结

  • 以上代码展示了如何在C语言中实现和操作一个简单的单链表。关键部分包括节点结构的定义、链表的创建、节点的插入与删除以及链表的遍历。这些基本操作是单链表实现的基础，也是理解和扩展更复杂数据结构的重要步骤。

四、源码

（1）SLT.h

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

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);

// 单链表打印
void SListPrint(SListNode* plist);

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);

// 单链表的尾删
void SListPopBack(SListNode** pplist);

// 单链表头删
void SListPopFront(SListNode** pplist);

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);

// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);

// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);

// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);

//销毁链表
void SLTDestroy(SListNode** pphead);

（2）SLT.c

#include"SLT.h"

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x) {
	SListNode* ptr = (SListNode*)malloc(sizeof(SListNode));
	if (ptr == NULL) {
		return NULL;
	}
	ptr->data = x;
	ptr->next = NULL;
	return ptr;
}

// 单链表打印
void SListPrint(SListNode* plist) {
	SListNode* cur = plist;
	while (cur) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");
	printf("\n");
}

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x) {
	assert(pplist);
	if (NULL == *pplist) {
		SListPushFront(pplist, x);
		return;
	}
	SListNode* newnode = BuySListNode(x);
	SListNode* fail = *pplist;
	while (fail->next) {
		fail = fail->next;
	}
	fail->next = newnode;
}

// 单链表的尾删
void SListPopBack(SListNode** pplist) {
	//一个节点和多个节点
	assert(pplist && *pplist);
	//一个节点
	if ((*pplist)->next == NULL) {
		free(*pplist);
		*pplist = NULL;
	}
	//多个节点
	SListNode* fail = *pplist;
	SListNode* perv = *pplist;
	while (fail->next) {
		perv = fail;
		fail = fail->next;
	}
	free(fail);
	//fail = NULL;               //这一步不会把删除后的最后一个节点的next指针改为NULL，这就要对于变量赋值和改值要有理解。
	perv->next = NULL;
}

// 单链表头删
void SListPopFront(SListNode** pplist) {
	assert(pplist && *pplist);
	SListNode* cur = *pplist;
	*pplist = cur->next;
	free(cur);
}

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x) {
	assert(plist);
	SListNode* cur = plist;
	while (cur) {
		if (cur->data == x)
			return cur;
	}
	printf("找不到\n");
	return NULL;
}

// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x) {
	assert(pos);
	SListNode* cur = BuySListNode(x);
	cur->next = pos->next;
	pos->next = cur;
}

// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos) {
	assert(pos && pos->next);
	SListNode* temp = pos->next->next;
	free(pos->next);
	pos->next = temp;
}

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x) {
	assert(pphead && *pphead);
	SListNode* ptr = BuySListNode(x);
	SListNode* cur = *pphead;
	if (cur == pos) {
		SListPushFront(pphead, x);
		return;
	}
	while (cur->next != pos && cur->next) {
		cur = cur->next;
	}
	if(cur->next == pos){
		cur->next = ptr;
		ptr->next = pos;
		return;
	}
	else assert(cur->next);
}
	
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos) {
	assert(pphead && *pphead);
	if (*pphead == pos) {
		SListPopFront(pphead);
		return;
	}
	SListNode* cur = *pphead;
	while (cur->next != pos && cur->next) {
		cur = cur->next;
	}
	assert(cur->next);
	cur->next = pos->next;
	free(pos);
}

//销毁链表
void SLTDestroy(SListNode** pphead) {
	SListNode* cur = *pphead;
	while (cur) {
		SListNode* temp = cur->next;
		free(cur);
		cur = temp;
	}
	*pphead = NULL;
}

（3）Test.c

#include"SLT.h"
void test3() {
	SListNode* n1 = BuySListNode(1);
	SListNode* n2 = BuySListNode(2);
	n1->next = n2;
	n2->next = NULL;

	SListInsertAfter(n1, 3);
	SListInsertAfter(n2, 4);

	SListPrint(n1);

	SListEraseAfter(n1);
	SListEraseAfter(n2);

	SListPrint(n1);

	SLTInsert(&n1, n2, 5);

	SListPrint(n1);

	SLTErase(&n1, n2);

	SListPrint(n1);

	/*SLTErase(&n1, n1);
	SListPrint(n1);*/

	SLTDestroy(&n1);
}


void test2() {
	SListNode* n1 = BuySListNode(1);
	SListNode* n2 = BuySListNode(2);
	n1->next = n2;
	n2->next = NULL;

	SListPushBack(&n1, 3);
	SListPushBack(&n1, 4);

	SListPrint(n1);

	SListPopBack(&n1);
	SListPopBack(&n1);

	SListPrint(n1);

	SListPopFront(&n1);

	SListPrint(n1);

	SLTDestroy(&n1);
}
void test1() {
	SListNode* n1  = BuySListNode(1);
	SListNode* n2  = BuySListNode(2);
	n1->next = n2;
	n2->next = NULL;

	SListPrint(n1);

	SLTDestroy(&n1);
}

int main() {
	test3();
	return 0;
}

快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！

12-27 09:19
Powered by LMLPHP ©2024 就爱学编程 0.005841