本文介绍: 详细介绍了静态顺序表和动态顺序表,包括应用上述程序实现了一个简单的静态顺序表,包括初始化、插入、删除和打印操作。大家可以自己修改插入,删除数据,体会其中的奥秘。效果
顺序表的定义
顺序表是一种线性数据结构,它由一组连续的存储单元组成,用来存储具有相同数据类型的元素。顺序表中的元素按照逻辑顺序依次存放,并且可以通过索引来访问和修改元素。
顺序表的实现方式
两种:静态顺序表和动态顺序表。
- 静态顺序表:
静态顺序表使用静态数组来实现,需要在创建顺序表时提前确定顺序表的大小。静态顺序表的大小是固定的,一旦分配了固定大小的存储空间,就不能动态地改变大小。因此,静态顺序表的容量是有限的,如果插入的元素超过了容量,就会导致溢出。 - 优点:可以直接通过下标直接访问元素,访问元素速度快,时间复杂度是O(1)。
- 缺点:插入与删除元素的操作比较耗时,需要移动其他元素,时间复杂度位O(n)。
- 动态顺序表:
- 动态顺序表使用动态数组来实现,可以根据需要动态调整顺序表的大小。动态顺序表的大小是可变的,当插入的元素超过当前容量时,会自动扩容,当删除元素后,如果剩余容量过多,可以缩小容量,以节省内存空间。
- 优点:可以根据动态调整大小,灵活性较高。
- 缺点:在插入和删除元素时,可能需要重新分配存储空间,导致一定的时间开销。
静态顺序表的例子
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
// 定义静态顺序表的最大长度
#define MAX_SIZE 100
// 定义结构体,表示静态顺序表
struct SeqList
{
int data[MAX_SIZE]; // 数据数组
int length; // 当前表长
};
// 初始化顺序表
void initSeqList(struct SeqList* list)
{
list->length = 0; // 初始化表长为0
}
// 插入元素到顺序表
int insertElement(struct SeqList* list, int position, int value)
{
// 检查插入位置的有效性
if (position < 1 || position > list->length + 1 || list->length >= MAX_SIZE)
{
printf("插入位置无效或表满,插入失败n");
return 0; // 插入失败
}
// 将插入位置及之后的元素后移
for (int i = list->length; i >= position; i--)
{
list->data[i] = list->data[i - 1];
}
// 在插入位置处插入新元素
list->data[position - 1] = value;
// 表长加1
list->length++;
printf("插入成功n");
return 1; // 插入成功
}
// 删除顺序表中指定位置的元素
int deleteElement(struct SeqList* list, int position)
{
// 检查删除位置的有效性
if (position < 1 || position > list->length)
{
printf("删除位置无效,删除失败n");
return 0; // 删除失败
}
// 将删除位置之后的元素前移
for (int i = position; i < list->length; i++)
{
list->data[i - 1] = list->data[i];
}
// 表长减1
list->length--;
printf("删除成功n");
return 1; // 删除成功
}
// 打印顺序表中的元素
void printSeqList(struct SeqList* list)
{
printf("顺序表元素:");
for (int i = 0; i < list->length; i++)
{
printf("%d ", list->data[i]);
}
printf("n");
}
int main()
{
// 声明并初始化顺序表
struct SeqList myList;
initSeqList(&myList);
// 在顺序表中插入元素
insertElement(&myList, 1, 10);
insertElement(&myList, 1, 20);
insertElement(&myList, 1, 5);
insertElement(&myList, 1, 6);
// 打印顺序表
printSeqList(&myList);
// 删除顺序表中的元素
deleteElement(&myList, 1);
// 打印删除后的顺序表
printSeqList(&myList);
return 0;
}
上述程序实现了一个简单的静态顺序表,包括初始化、插入、删除和打印操作。大家可以自己修改插入,删除数据,体会其中的奥秘。
效果
动态顺序表的例子
#include <stdio.h>
#include <stdlib.h>
// 定义动态顺序表的初始容量和增量
#define INIT_CAPACITY 10
#define INCREMENT 5
// 定义结构体,表示动态顺序表
struct SeqList
{
int* data; // 数据指针
int length; // 当前表长
int capacity; // 当前容量
};
// 初始化顺序表
void initSeqList(struct SeqList* list)
{
list->data = (int*)malloc(INIT_CAPACITY * sizeof(int)); // 分配初始容量的内存
list->length = 0; // 初始化表长为0
list->capacity = INIT_CAPACITY; // 初始化容量为初始容量
}
// 销毁顺序表
void destroySeqList(struct SeqList* list)
{
free(list->data); // 释放动态分配的内存
list->data = NULL; // 将指针置为空
list->length = 0; // 表长置为0
list->capacity = 0; // 容量置为0
}
// 打印顺序表中的元素
void printSeqList(struct SeqList* list)
{
printf("顺序表元素:");
for (int i = 0; i < list->length; i++)
{
printf("%d ", list->data[i]);
}
printf("n");
}
// 自动增容
void increaseCapacity(struct SeqList* list)
{
int* newData = (int*)realloc(list->data, (list->capacity + INCREMENT) * sizeof(int)); // 重新分配内存
if (newData != NULL)
{ // 分配成功
list->data = newData; // 将指针指向新的内存
list->capacity += INCREMENT; // 容量增加
printf("自动增容成功,容量增加到%dn", list->capacity);
}
else
{ // 分配失败
printf("自动增容失败n");
}
}
// 插入元素到顺序表
int insertElement(struct SeqList* list, int position, int value)
{
// 检查插入位置的有效性
if (position < 1 || position > list->length + 1)
{
printf("插入位置无效,插入失败n");
return 0; // 插入失败
}
// 如果表满,自动增容
if (list->length >= list->capacity)
{
increaseCapacity(list);
}
// 将插入位置及之后的元素后移
for (int i = list->length; i >= position; i--)
{
list->data[i] = list->data[i - 1];
}
// 在插入位置处插入新元素
list->data[position - 1] = value;
// 表长加1
list->length++;
printf("插入成功n");
return 1; // 插入成功
}
// 删除顺序表中指定位置的元素
int deleteElement(struct SeqList* list, int position)
{
// 检查删除位置的有效性
if (position < 1 || position > list->length)
{
printf("删除位置无效,删除失败n");
return 0; // 删除失败
}
// 将删除位置之后的元素前移
for (int i = position; i < list->length; i++)
{
list->data[i - 1] = list->data[i];
}
// 表长减1
list->length--;
printf("删除成功n");
return 1; // 删除成功
}
// 查找元素在顺序表中的位置
int searchElement(struct SeqList* list, int value)
{
for (int i = 0; i < list->length; i++)
{
if (list->data[i] == value)
{
printf("元素%d在顺序表中的位置是%dn", value, i + 1);
return i + 1; // 返回位置
}
}
printf("元素%d不在顺序表中n", value);
return 0; // 查找失败
}
int main()
{
// 声明并初始化顺序表
struct SeqList myList;
initSeqList(&myList);
// 在顺序表中插入元素
insertElement(&myList, 1, 10);
insertElement(&myList, 2, 20);
insertElement(&myList, 1, 5);
// 打印顺序表
printSeqList(&myList);
// 删除顺序表中的元素
deleteElement(&myList, 2);
// 打印删除后的顺序表
printSeqList(&myList);
// 查找元素在顺序表中的位置
searchElement(&myList, 20);
searchElement(&myList, 30);
// 销毁顺序表
destroySeqList(&myList);
return 0;
}
效果
原文地址:https://blog.csdn.net/2303_80025768/article/details/135438524
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_54677.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。