【数据结构】顺序表与单链表的增删查改

文章目录

前言
顺序表增删查改
- 顺序表的定义与初始化
- 增删查改操作
- 测试代码
- 完整代码
单链表的增删查改
- 数据结构定义
- 动态申请节点
- 单链表的尾插和头插
- 单链表的尾删和头删
- 单链表的查找
- 单链表的插入和删除
- 销毁链表
- 测试代码
- 完整代码
总结

前言

在计算机编程领域，数据结构是非常重要的基础知识之一。顺序表和单链表作为常见的线性数据结构，在实际的软件开发中被广泛应用。本文将介绍了C语言中顺序表和单链表的实现方式，并对其进行了增删查改操作的详细讲解。通过阅读本文，读者将能够深入了解顺序表和单链表的底层实现原理，掌握它们的基本操作及相关的代码编写技巧。

顺序表增删查改

当今计算机编程领域中最重要的数据结构之一是顺序表。顺序表是一种线性表，其中的元素在内存中按照顺序存储，可以通过下标来访问。本文将介绍一个简单的顺序表实现，并对其进行增删查改操作。

顺序表的定义与初始化

首先，我们需要定义一个结构体来表示顺序表，并声明一些相关的变量和函数。顺序表的结构体包含一个动态数组 a，用于存储数据；size 表示当前顺序表中元素的个数；capacity 表示顺序表的容量，即当前数组 a 的大小。

typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);
void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);
int SeqListFind(SeqList* ps, SLDateType x);
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
void SeqListErase(SeqList* ps, int pos);

在初始化顺序表之前，我们需要实现一个辅助函数 SLCheckCapacity，用于检查顺序表的容量，并在需要时进行扩容。

void SLCheckCapacity(SeqList* ps)
{assert(ps);if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDateType* tmp = realloc(ps->a, newCapacity * sizeof(SLDateType));if (tmp == NULL){printf("realloc fail!\n");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}
}

接下来，我们实现顺序表的初始化函数 SeqListInit 和销毁函数 SeqListDestroy。

void SeqListInit(SeqList* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->size = 0;
}void SeqListDestroy(SeqList* ps)
{assert(ps);if (ps->a){free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;}
}

增删查改操作

顺序表的增删查改操作是对数据进行管理的核心部分。我们实现了以下函数来完成这些操作：

SeqListPrint：打印顺序表中的所有元素。
SeqListPushBack：在顺序表的末尾插入一个元素。
SeqListPushFront：在顺序表的头部插入一个元素。
SeqListPopFront：从顺序表的头部删除一个元素。
SeqListPopBack：从顺序表的末尾删除一个元素。
SeqListFind：在顺序表中查找指定元素，并返回其索引位置。
SeqListInsert：在顺序表的指定位置插入一个元素。
SeqListErase：从顺序表的指定位置删除一个元素。

void SeqListPrint(SeqList* ps)
{assert(ps);for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}void SeqListPushBack(SeqList* ps, SLDateType x)
{SeqListInsert(ps, ps->size, x);
}void SeqListPushFront(SeqList* ps, SLDateType x)
{SeqListInsert(ps, 0, x);
}void SeqListPopFront(SeqList* ps)
{SeqListErase(ps, 0);
}void SeqListPopBack(SeqList* ps)
{SeqListErase(ps, ps->size - 1);
}int SeqListFind(SeqList* ps, SLDateType x)
{assert(ps);for (int i = 0; i < ps->size; ++i){if (ps->a[i] == x) return i;}return -1;
}void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);memmove(ps->a + pos + 1, ps->a + pos, (ps->size - pos) * sizeof(SLDateType));ps->a[pos] = x;ps->size++;
}void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);memmove(ps->a + pos, ps->a + pos + 1, (ps->size - pos - 1) * sizeof(SLDateType));ps->size--;
}

测试代码

为了验证顺序表的正确性，我们编写了一个简单的测试代码。在测试代码中，我们创建了一个顺序表，并进行了一系列的增删查改操作。

int main()
{SeqList sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPushBack(&sl, 6);SeqListPushBack(&sl, 7);SeqListPushBack(&sl, 8);printf("PushBack 测试(尾插8个数):\n");SeqListPrint(&sl);SeqListPushFront(&sl, 9);SeqListPushFront(&sl, 9);SeqListPushFront(&sl, 9);printf("PushFront 测试(头插三个9):\n");SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPopFront(&sl);SeqListPopFront(&sl);printf("PopFront 测试(头删三个数):\n");SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPopBack(&sl);printf("PopBack 测试(尾删两个数):\n");SeqListPrint(&sl);printf("Find 测试(找5和8):\n");int pos = SeqListFind(&sl, 5);if (pos != -1) printf("5 在下标为%d的位置\n", pos);else printf("%d没找到！\n", 5);pos = SeqListFind(&sl, 8);if (pos != -1) printf("8 在下标为%d的位置\n", pos);else printf("%d 没找到！\n", 8);SeqListDestroy(&sl);return 0;
}

在这里插入图片描述

完整代码

//SeqList.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;void SLCheckCapacity(SeqList* ps);// 对数据的管理:增删查改 
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

//Seqlist.c
#include "SeqList.h"void SLCheckCapacity(SeqList* ps)
{assert(ps);if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDateType* tmp = realloc(ps->a, newCapacity * sizeof(SLDateType));if (tmp == NULL){printf("realloc fail!\n");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}
}// 对数据的管理:增删查改 
void SeqListInit(SeqList* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->size = 0;
}
void SeqListDestroy(SeqList* ps)
{assert(ps);if (ps->a){free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;}
}void SeqListPrint(SeqList* ps)
{assert(ps);for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}
void SeqListPushBack(SeqList* ps, SLDateType x)
{SeqListInsert(ps, ps->size, x);
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{SeqListInsert(ps, 0, x);
}
void SeqListPopFront(SeqList* ps)
{SeqListErase(ps, 0);
}
void SeqListPopBack(SeqList* ps)
{SeqListErase(ps, ps->size);
}// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x)
{assert(ps);for (int i = 0; i < ps->size; ++i){if (ps->a[i] == x) return i;}return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);memmove(ps->a + pos + 1, ps->a + pos, (ps->size - pos) * sizeof(SLDateType));ps->a[pos] = x;ps->size++;
}
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(pos >= 0 && pos <= ps->size);memmove(ps->a + pos, ps->a + pos + 1, (ps->size - pos) * sizeof(SLDateType));ps->size--;
}

//test.c
#include"SeqList.h"int main()
{SeqList sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPushBack(&sl, 6);SeqListPushBack(&sl, 7);SeqListPushBack(&sl, 8);printf("PushBack 测试(尾插8个数):\n");SeqListPrint(&sl);SeqListPushFront(&sl, 9);SeqListPushFront(&sl, 9);SeqListPushFront(&sl, 9);printf("PushFront 测试(头插三个9):\n");SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPopFront(&sl);SeqListPopFront(&sl);printf("PopFront 测试(头删三个数):\n");SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPopBack(&sl);printf("PopBack 测试(尾删两个数):\n");SeqListPrint(&sl);printf("Find 测试(找5和8):\n");int pos = SeqListFind(&sl, 5);if (pos != -1) printf("5 在下标为%d的位置\n", pos);else printf("%d没找到！\n", 5);pos = SeqListFind(&sl, 8);if (pos != -1) printf("8 在下标为%d的位置\n", pos);else printf("%d 没找到！\n", 8);SeqListDestroy(&sl);return 0;
}

通过上述代码，我们实现了一个简单的顺序表，并对其进行了增删查改操作的测试。顺序表是一种非常常用的数据结构，能够高效地管理线性数据。

单链表的增删查改

单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和指向下一个节点的指针。我将介绍如何使用C语言实现单链表的增删查改操作。

数据结构定义

首先，我们需要定义单链表的数据结构。在给出的代码中，使用了SListNode结构体表示每个节点，其中包含一个整型数据 data 和一个指向下一个节点的指针 next。另外，定义了一个类型别名 SLTDateType 来表示节点数据的类型。

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

动态申请节点

为了创建一个新的节点，我们需要动态申请内存空间，并将数据和指针赋值。在给出的代码中，定义了一个 BuySListNode 函数来完成这个任务。

SListNode* BuySListNode(SLTDateType x)
{SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));if (newNode == NULL){printf("malloc fail!");exit(-1);}newNode->next = NULL;newNode->data = x;return newNode;
}

单链表的尾插和头插

尾插操作是将新节点插入到链表末尾。给出的代码中，定义了 SListPushBack 函数来实现尾插操作。它首先创建一个新节点，并找到链表的尾部，然后将新节点连接到尾节点的后面。

void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newNode = BuySListNode(x);SListNode* tail = *pplist;if (tail == NULL) {*pplist = newNode;return;}else {while (tail->next) {tail = tail->next;}}tail->next = newNode;
}

头插操作是将新节点插入到链表的头部。给出的代码中，定义了 SListPushFront 函数来实现头插操作。它首先创建一个新节点，并将新节点的指针指向原链表的头节点，然后更新链表的头节点为新节点。

void SListPushFront(SListNode** pplist, SLTDateType x) 
{assert(pplist);SListNode* newNode = BuySListNode(x);newNode->next = *pplist;*pplist = newNode;
}

单链表的尾删和头删

尾删操作是删除链表的最后一个节点。给出的代码中，定义了 SListPopBack 函数来实现尾删操作。它首先找到链表的倒数第二个节点，然后释放最后一个节点的内存，并将倒数第二个节点的 next 指针置空。

void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* tail = *pplist;SListNode* prev = NULL;if (tail->next == NULL) {*pplist = NULL;}else {while (tail->next) {prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}
}

头删操作是删除链表的第一个节点。给出的代码中，定义了 SListPopFront 函数来实现头删操作。它首先将链表的头节点保存起来，然后更新链表的头节点为原头节点的下一个节点，并释放保存的头节点的内存。

void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* front = *pplist;*pplist = (*pplist)->next;free(front);
}

单链表的查找

查找操作是在链表中寻找特定的数据。给出的代码中，定义了 SListFind 函数来实现查找操作。它遍历链表，直到找到数据等于目标值的节点，然后返回该节点的指针。

SListNode* SListFind(SListNode* plist, SLTDateType x)
{assert(plist);SListNode* cur = plist;while (cur->next && cur->data != x) {cur = cur->next;}if (cur->next) {return cur;}return NULL;
}

单链表的插入和删除

在给出的代码中，还定义了 SListInsertAfter、SListEraseAfter、SListInsert 和 SListErase 函数来实现在指定位置之后插入节点、删除指定位置之后的节点、在指定位置之前插入节点以及删除指定位置的节点。

//具体的实现细节请参考给出的代码。

销毁链表

为了释放链表占用的内存空间，给出的代码中，定义了 SListDestroy 函数来销毁链表。它遍历链表的每个节点，依次释放内存，并将链表的头节点置为NULL。

void SListDestroy(SListNode** pplist)
{assert(pplist);SListNode* cur = *pplist;while (cur){SListNode* next = cur->next;free(cur);cur = next;}*pplist = NULL;
}

测试代码

给出的代码还包括了一个 main 函数来测试上述函数的功能。它首先创建一个空链表，然后进行了一系列的增删查改操作，并输出每一步操作后的链表结果。

int main()
{SListNode* plist = NULL;// 测试代码return 0;
}

以上就是关于C语言实现单链表的增删查改的代码解析和使用方法。
在这里插入图片描述

完整代码

//slist.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 SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x);
// 删除pos位置
void SListErase(SListNode** pplist, SListNode* pos);
//销毁链表
void SListDestroy(SListNode** pplist);

//slist.c
#include "slist.h"// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));if (newNode == NULL){printf("malloc fail!");exit(-1);}newNode->next = NULL;newNode->data = x;
}
// 单链表打印
void SListPrint(SListNode* plist)
{SListNode* cur = plist;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newNode = BuySListNode(x);SListNode* tail = *pplist;//找尾if (tail == NULL) {*pplist = newNode;return;}else {while (tail->next) {tail = tail->next;}}tail->next = newNode;
}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x) 
{assert(pplist);SListNode* newNode = BuySListNode(x);newNode->next = *pplist;*pplist = newNode;
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* tail = *pplist;SListNode* prev = NULL; //尾的前一个//找尾if (tail->next == NULL) {*pplist = NULL;}else{while (tail->next) {prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* front = *pplist;*pplist = (*pplist)->next;free (front);
}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{assert(plist);SListNode* cur = plist;while (cur->next && cur->data != x) {cur = cur->next;}if (cur->next) {return cur;}return NULL;
}
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？如果在pos之前经行插入需要遍历一遍前面的链表,效率低
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newNode = BuySListNode(x);SListNode* tmp = pos->next;pos->next = newNode;newNode->next = tmp;
}
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？同上
void SListEraseAfter(SListNode* pos)
{assert(pos);SListNode* del = pos->next;pos->next = pos->next->next;free(del);
}// 在pos的前面插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x)
{assert(pplist);assert(pos);if (pos == *pplist){SListPushFront(pplist, x);return;}SListNode* newNode = BuySListNode(x);SListNode* prev = *pplist;while (prev->next != pos){prev = prev->next;}newNode->next = pos;prev->next = newNode;
}
// 删除pos位置
void SListErase(SListNode** pplist, SListNode* pos)
{assert(pplist);assert(*pplist);assert(pos);SListNode* prev = *pplist;SListNode* del = pos;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(del);
}
//销毁链表
void SListDestroy(SListNode** pplist)
{assert(pplist);SListNode* cur = *pplist;while (cur){SListNode* next = cur->next;free(cur);cur = next;}*pplist = NULL;
}

//test.c
#include"slist.h"int main()
{SListNode* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPushBack(&plist, 5);SListPushBack(&plist, 6);SListPushBack(&plist, 7);SListPushBack(&plist, 8);printf("PushBack 测试(尾插8个数):\n");SListPrint(plist);SListPushFront(&plist, 0);SListPushFront(&plist, 0);SListPushFront(&plist, 0);printf("PushFront 测试(头插三个0):\n");SListPrint(plist);SListPopBack(&plist);SListPopBack(&plist);printf("PopBack 测试(尾删两个数):\n");SListPrint(plist);SListPopFront(&plist);SListPopFront(&plist);SListPopFront(&plist);printf("PopFront 测试(头删三个数):\n");SListPrint(plist);printf("Find 测试(找4):\n");SListPrint(SListFind(plist, 4));printf("InsertAfter 测试(找4后插):\n");SListInsertAfter(SListFind(plist, 4), 999);SListPrint(plist);printf("EraseAfter 测试(找4后删):\n");SListEraseAfter(SListFind(plist, 4));SListPrint(plist);printf("Insert 测试(找4前插):\n");SListInsert(&plist, SListFind(plist, 4), 999);SListPrint(plist);printf("Erase 测试(找4删4):\n");SListErase(&plist, SListFind(plist, 4));SListPrint(plist);SListDestroy(&plist);printf("Destroy！\n");SListPrint(plist);return 0;
}

总结

本文首先介绍了顺序表的定义与初始化，包括动态数组的使用、容量检查和扩容操作等内容。然后详细讲解了顺序表的增删查改操作，并给出了相应的代码示例。接着，文章转向单链表的实现，包括节点的定义、动态申请节点、尾插和头插操作、尾删和头删操作、查找、插入和删除等操作的具体实现。最后，通过测试代码验证了顺序表和单链表的功能正常运行。

通过本文的学习，读者可以加深对顺序表和单链表的理解，掌握这两种数据结构的增删查改的具体实现方法。同时，对于初学者来说，也能够更好地理解数据结构和算法在实际编程中的应用，为日后的软件开发打下良好的基础。

希望本文能为您对顺序表和单链表的理解和应用提供帮助，欢迎大家在实践中不断探索和应用这些知识，提升自己的编程技能。