重生之我在异世界学编程之算法与数据结构：深入动态顺序表篇

大家好，这里是小编的博客频道
小编的博客：就爱学编程

很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！

本文目录

引言

在C语言中，数据结构是编程的基础之一。顺序表（Sequence List）作为一种常见的数据结构，具有随机访问速度快、逻辑结构简单等特点。然而，传统的静态数组实现的顺序表存在空间固定的问题，一旦初始化后无法动态调整大小。为了解决这个问题，动态顺序表应运而生。本文将详细介绍C语言中动态顺序表的实现原理、基本操作以及应用示例那现在，一起来看看吧！！！

在这里插入图片描述

那接下来就让我们开始遨游在知识的海洋！

正文

一 动态顺序表的基本概念

（1）定义

  • 动态顺序表是一种基于动态内存分配的顺序存储结构的线性表。它允许在需要时自动调整存储空间的大小，从而克服了静态数组在实现顺序表时的局限性。

（2）特点

动态性：可以根据需要动态地增加或减少存储空间。
随机访问性：支持通过下标快速访问表中的元素。
连续性：表中元素在物理上连续存放。

（3）基本操作

初始化：创建一个空的动态顺序表。
插入：在指定位置插入一个或多个新元素。
删除：删除指定位置的元素或满足条件的元素。
查找：根据值查找元素的位置。
更新：修改指定位置的元素的值。
获取长度：返回当前动态顺序表的长度。
清空：清空动态顺序表中的所有元素。

接下来我们就一起看看具体如何实现？

二 动态顺序表的实现

（1）数据结构设计

为了实现动态顺序表，我们需要定义一个结构体来保存表的相关信息，包括指向数组的指针、数组的容量和当前已使用的长度等。以下是一个简单的动态顺序表的结构体定义：

#include 
#include 
#include 

#define INIT_CAPACITY 4 // 初始容量
#define INCREMENT 2    // 每次扩容的增量

typedef struct {
    int *data;         // 指向数组的指针
    int capacity;      // 数组的容量
    int length;        // 当前已使用的长度
} SeqList;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 在这个结构体中， data 是指向实际存储元素的数组的指针， capacity 表示数组的容量，即最多可以存储多少个元素，而length则表示当前已经存储了多少个元素。

（2）初始化函数

初始化函数用于创建一个空的动态顺序表，并为其分配初始容量的内存空间。以下是初始化函数的实现：

void InitSeqList(SeqList *list) {
   list->data = (int *)malloc(INIT_CAPACITY * sizeof(int));
   if (!list->data) {
       printf("Memory allocation failed!
");
       exit(EXIT_FAILURE);
   }
   list->capacity = INIT_CAPACITY;
   list->length = 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 这个函数首先为 data 成员分配了初始容量的内存空间，然后设置capacity为初始容量，并将 length 设置为0，表示当前为空表。如果内存分配失败，则打印错误信息并退出程序。

（3）插入操作

插入操作需要在指定位置插入一个新元素。如果当前容量不足以容纳新元素，则需要先扩容。以下是插入操作的实现：

 
bool InsertSeqList(SeqList *list, int index, int value) {
    if (index < 0 || index > list->length) {
        printf("Invalid index!
");
        return false;
    }

    if (list->length >= list->capacity) {
        int newCapacity = list->capacity + INCREMENT;
        int *newData = (int *)realloc(list->data, newCapacity * sizeof(int));
        if (!newData) {
            printf("Memory reallocation failed!
");
            return false;
        }
        list->data = newData;
        list->capacity = newCapacity;
    }

    for (int i = list->length; i > index; --i) {
        list->data[i] = list->data[i - 1];
    }
    list->data[index] = value;
    ++list->length;
    return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 这个函数首先检查插入位置是否有效，然后判断是否需要扩容。如果需要扩容，则使用 realloc 函数重新分配内存空间，并更新 data 指针和 capacity 值。接着，将插入位置之后的元素向后移动一位，为新元素腾出空间，最后将新元素插入到指定位置，并更新 length 值。

（4）删除操作

删除操作需要删除指定位置的元素。以下是删除操作的实现：

 
bool DeleteSeqList(SeqList *list, int index) {
    if (index < 0 || index >= list->length) {
        printf("Invalid index!
");
        return false;
    }

    for (int i = index; i < list->length - 1; ++i) {
        list->data[i] = list->data[i + 1];
    }
    --list->length;
    return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 这个函数首先检查删除位置是否有效，然后将删除位置之后的元素向前移动一位，以覆盖被删除的元素，最后更新 length 值。

（5）查找操作

查找操作需要根据给定的值查找元素的位置。以下是查找操作的实现：

int FindSeqList(const SeqList *list, int value) {
   for (int i = 0; i < list->length; ++i) {
       if (list->data[i] == value) {
           return i;
       }
   }
   return -1; // 未找到
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 这个函数遍历整个动态顺序表，比较每个元素与给定值是否相等。如果找到了相等的元素，则返回其位置索引；否则返回-1表示未找到。

（6）更新操作

更新操作需要修改指定位置的元素的值。以下是更新操作的实现：

bool UpdateSeqList(SeqList *list, int index, int newValue) {
   if (index < 0 || index >= list->length) {
       printf("Invalid index!
");
       return false;
   }
   list->data[index] = newValue;
   return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 这个函数首先检查更新位置是否有效，然后直接修改指定位置的元素的值。

（7）获取长度操作

获取长度操作需要返回当前动态顺序表的长度。以下是获取长度操作的实现：

 
int GetSeqListLength(const SeqList *list) {
    return list->length;
}
  • 1
  • 2
  • 3
  • 4
  • 这个函数直接返回 length 成员的值即可。

（8）清空操作

清空操作需要清空动态顺序表中的所有元素，但不需要释放内存空间。以下是清空操作的实现：

void ClearSeqList(SeqList *list) {
   list->length = 0;
}
  • 1
  • 2
  • 3
  • 这个函数直接将 length 成员设置为0即可。注意这里并没有释放 data 指针所指向的内存空间，因为在实际应用中可能还需要继续使用这块内存空间来存储新的元素。如果需要彻底销毁动态顺序表并释放所有资源，则可以在清空操作之后调用 free 函数来释放 data 指针所指向的内存空间。但是这样做会导致 data 指针变为野指针（dangling pointer），因此通常建议在销毁动态顺序表时将整个结构体也一起释放掉或者将其重置为一个空的状态以便后续重用。不过在本例中为了简化代码和实现逻辑上的清晰性小编并没有这样做而是保留了原有的内存空间供后续使用。当然在实际开发中应该根据具体需求和场景来选择合适的方式来处理这些问题以避免潜在的风险和问题发生。

（9）销毁操作

虽然在上文中我们没有实现一个专门的销毁操作来释放动态顺序表所占用的所有资源，但在实际应用中这是非常重要的一个步骤。为了避免内存泄漏等问题，我们应该在不再需要使用动态顺序表时及时释放其所占用的内存空间。以下是一个可能的销毁操作的实现方式：

void DestroySeqList(SeqList *list) {
   free(list->data); // 释放data指针所指向的内存空间
   list->data = NULL; // 将data指针置为空以防止野指针问题发生（可选步骤但推荐执行）
   list->capacity = 0; // 重置容量值（可选步骤但有助于保持数据结构状态的一致性）
   list->length = 0; // 重置长度值（同样可选但推荐执行以保持数据结构状态的清晰性和一致性）
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

请注意：

  • 在实际代码中宝子们可能需要根据具体的业务逻辑和需求来决定是否需要执行上述所有的重置操作以及是否需要将结构体本身也进行释放（例如如果该结构体是通过动态分配得到的并且之后不再需要使用了）。

三 源码

注意：这是小编自己写的，可能有不足之处，仅供参考！！！

（1）SL.h

#pragma once
#include 
#include 
#include 
#define INIT_CAPICITY  4         //初始化第一次开辟的空间

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 SeqListPopBack(SeqList* ps);

//尾插
void SeqListPushFront(SeqList* ps, SLDateType x);

//尾删
void SeqListPopFront(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);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

（2）SL.c

#include"SL.h"

//初始化顺序表
void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = (SLDateType*)malloc(sizeof(SLDateType) * INIT_CAPICITY);
	if (ps->a == NULL) {
		perror("SeqList->malloc fail");
		return;
	}
	ps->capacity = INIT_CAPICITY;
	ps->size = 0;
}

//打印顺序表内的的有效信息（指针指向的空间内的信息）
void SeqListPrint(SeqList* ps) {
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++) {
		printf("%d->", ps->a[i]);
	}
	printf("%d", ps->a[ps->size - 1]);
	printf("\n");
}

//销毁顺序表
void SeqListDestroy(SeqList* ps) {
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

//检查顺序表是否已经满了，满了就加
void Check_SeqList(SeqList* ps) {
	assert(ps);
	if (ps->capacity == ps->size) {
		SLDateType* temp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * 2 * (ps->capacity));
		if (temp == NULL) {
			perror("Check_SeqList->realloc fail");
			return;
		}
		ps->a = temp;
		ps->capacity = 2 * ps->capacity;
		printf("增容成功\n");
	}
}
//头插
void SeqListPushBack(SeqList* ps, SLDateType x) {
	assert(ps);
	Check_SeqList(ps);
	for (int i = ps->size - 1; i >= 0; i--) {
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[0] = x;
	ps->size++;
}

//头删
void SeqListPopBack(SeqList* ps) {
	assert(ps);
	for (int i = 0; i < ps->size - 1; i++) {
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

//尾插
void SeqListPushFront(SeqList* ps, SLDateType x) {
	assert(ps);
	Check_SeqList(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

//尾删
void SeqListPopFront(SeqList* ps) {
	assert(ps);
	ps->size--;
	assert(ps->size > 0);
}

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x) {
	assert(ps);
	for (int i = 0; i < ps->size; i++) {
		if (ps->a[i] == x) {
			return i + 1;
		}
	}
	return -1;
}

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x) {
	Check_SeqList(ps);
	for (int i = ps->size; i >= pos; i--) {
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos - 1] = x;
	ps->size++;
}

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos) {
	assert(ps);
	assert(pos > 0);
	for (int i = pos - 1; i < ps->size; i++) {
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113

（3）Test.c

#include"SL.h"
SeqList s;
void test5() {
	SeqListPushFront(&s, 4);
	SeqListPushFront(&s, 2);
	SeqListPushFront(&s, 7);
	SeqListPushFront(&s, 8);
	SeqListPushFront(&s, 5);
	SeqListPushFront(&s, 6);

	SeqListInsert(&s, 1, 1);

	SeqListPrint(&s);

	SeqListErase(&s, 1);

	SeqListPrint(&s);

}
void test4() {
	SeqListPushFront(&s, 4);
	SeqListPushFront(&s, 2);
	SeqListPushFront(&s, 7);
	SeqListPushFront(&s, 8);
	SeqListPushFront(&s, 5);
	SeqListPushFront(&s, 6);

	SeqListPrint(&s);

	int ret = SeqListFind(&s, 2);
	assert(ret > 0);
	printf("%d ", s.a[ret - 1]);
}

void test3() {
	SeqListPushFront(&s, 4);
	SeqListPushFront(&s, 2);
	SeqListPushFront(&s, 7);
	SeqListPushFront(&s, 8);
	SeqListPushFront(&s, 5);
	SeqListPushFront(&s, 6);

	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	/*SeqListPopFront(&s);
	SeqListPopFront(&s);*/

	SeqListPrint(&s);
}
void test2() {
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 5);
	SeqListPushBack(&s, 6);

	SeqListPrint(&s);

	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s); 
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);

	SeqListPrint(&s);
}
void test1() {
	SeqListInit(&s);

	SeqListPrint(&s);

	SeqListDestroy(&s);

}
int main() {
	test5();
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83

快乐的时光总是短暂，咱们下篇博文再见啦！！！在下一篇博文，小编将会带着宝子们学习如何使用动态顺序表写一个通讯录，敬请期待吧！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！

注：本文转载自blog.csdn.net的就爱学编程的文章"https://blog.csdn.net/z15879084549/article/details/144597364"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！