顺序表的基本操作
1顺序表的基本操作有
- 用于初始化顺序表,并为动态数组分配初始内存。
SLDestroy
: 用于销毁顺序表,释放动态数组占用的内存。SLPrint
: 打印顺序表中的所有元素,通常用于调试。SLPushBack
: 在顺序表的尾部插入一个元素。SLPushFront
: 在顺序表的头部插入一个元素。SLPopBack
: 删除顺序表的尾部元素。SLPopFront
: 删除顺序表的头部元素。SLInsert
: 在顺序表的指定位置插入一个元素。SLErase
: 删除顺序表中指定位置的元素。SLFind
: 在顺序表中查找某个元素,如果找到返回其下标,否则返回-1
。- 我将具体可以实现的代码分为三部分
1下面的头文件代码定义了一个动态顺序表(SeqList
)及其相关操作函数。动态顺序表使用动态内存分配来存储数据。
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>// 定义顺序表中存储的数据类型
typedef int SLDataType;// 动态顺序表的结构定义
typedef struct SeqList
{SLDataType* arr; // 指向动态数组的首地址int size; // 顺序表中有效数据的个数int capacity; // 顺序表的容量(总共可以容纳的元素个数)
} SL;// 顺序表的初始化函数,用于为顺序表分配初始内存
void SLInit(SL* ps);// 顺序表的销毁函数,用于释放顺序表占用的内存
void SLDestroy(SL* ps);// 打印顺序表中的元素(调试用)
void SLPrint(SL s);// 头部插入和尾部插入元素
void SLPushBack(SL* ps, SLDataType x); // 在顺序表的尾部插入元素
void SLPushFront(SL* ps, SLDataType x); // 在顺序表的头部插入元素// 头部删除和尾部删除元素
void SLPopBack(SL* ps); // 删除顺序表的尾部元素
void SLPopFront(SL* ps); // 删除顺序表的头部元素// 在指定位置插入或删除元素
void SLInsert(SL* ps, int pos, SLDataType x); // 在指定位置之前插入元素
void SLErase(SL* ps, int pos); // 删除指定位置的元素// 查找某个元素,返回其下标,如果找不到返回-1
int SLFind(SL* ps, SLDataType x);
2下面代码实现了一个动态顺序表的基本操作,包括初始化、销毁、插入、删除、查找等功能。是上面各项操作的函数的具体实现过程
#define _CRT_SECURE_NO_WARNINGS 1
#include"seqlist.h"// 顺序表的初始化函数,用于初始化顺序表
void SLInit(SL* ps)
{ps->arr = NULL; // 将数组指针初始化为NULLps->size = ps->capacity = 0; // 将有效数据个数和容量都初始化为0
}// 顺序表的销毁函数,用于释放顺序表占用的内存
void SLDestroy(SL* ps)
{if (ps->arr) // 如果数组指针不为空{free(ps->arr); // 释放数组占用的内存}ps->arr = NULL; // 将数组指针置为NULLps->size = ps->capacity = 0; // 将有效数据个数和容量都置为0
}// 检查并扩容顺序表,确保有足够的空间存储新数据
void SLCheckCapacity(SL* ps)
{// 如果当前容量等于有效数据个数,说明空间已满,需要扩容if (ps->capacity == ps->size){// 计算新的容量大小,如果是第一次扩容则设置为4,否则扩容为当前容量的2倍int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;// 使用realloc函数重新分配内存SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (tmp == NULL) // 如果内存分配失败{perror("realloc fail!"); // 输出错误信息exit(1); // 直接退出程序}// 内存分配成功,更新数组指针和容量ps->arr = tmp;ps->capacity = newCapacity;}
}// 尾插函数,在顺序表的尾部插入一个元素
void SLPushBack(SL* ps, SLDataType x)
{assert(ps); // 断言ps不为空SLCheckCapacity(ps); // 检查并扩容ps->arr[ps->size++] = x; // 在尾部插入元素,并将size加1
}// 头插函数,在顺序表的头部插入一个元素
void SLPushFront(SL* ps, SLDataType x)
{assert(ps); // 断言ps不为空SLCheckCapacity(ps); // 检查并扩容// 将已有数据整体向后移动一位,为新元素腾出空间for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x; // 在头部插入新元素ps->size++; // 增加有效数据个数
}// 打印顺序表中的元素
void SLPrint(SL s)
{for (int i = 0; i < s.size; i++){printf("%d ", s.arr[i]); // 打印每个元素}printf("\n"); // 换行
}// 尾删函数,删除顺序表的尾部元素
void SLPopBack(SL* ps)
{assert(ps); // 断言ps不为空assert(ps->size); // 断言顺序表不为空--ps->size; // 直接将size减1,相当于删除了最后一个元素
}// 头删函数,删除顺序表的头部元素
void SLPopFront(SL* ps)
{assert(ps); // 断言ps不为空assert(ps->size); // 断言顺序表不为空// 将已有数据整体向前移动一位,覆盖掉第一个元素for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--; // 减少有效数据个数
}// 在指定位置插入一个元素
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps); // 断言ps不为空assert(pos >= 0 && pos <= ps->size); // 断言插入位置合法SLCheckCapacity(ps); // 检查并扩容// 将pos及之后的数据整体向后移动一位,为新元素腾出空间for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x; // 在指定位置插入新元素ps->size++; // 增加有效数据个数
}// 删除指定位置的元素
void SLErase(SL* ps, int pos)
{assert(ps); // 断言ps不为空assert(pos >= 0 && pos <= ps->size); // 断言删除位置合法// 将pos之后的数据整体向前移动一位,覆盖掉指定位置的元素for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--; // 减少有效数据个数
}// 查找指定元素,返回其下标,如果找不到返回-1
int SLFind(SL* ps, SLDataType x)
{assert(ps); // 断言ps不为空for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x) // 如果找到元素{return i; // 返回元素下标}}return -1; // 没有找到元素,返回-1
}
3输入具体数值调用函数的过程
#define _CRT_SECURE_NO_WARNINGS 1
#include "seqlist.h"// 测试顺序表的基本操作
void SLtest01() {SL sl; // 定义一个顺序表SLInit(&sl); // 初始化顺序表// 在顺序表尾部插入元素SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl); // 输出当前顺序表: 1 2 3 4// 在顺序表头部插入元素SLPushFront(&sl, 6);SLPushFront(&sl, 7);SLPrint(sl); // 输出当前顺序表: 7 6 1 2 3 4// 从尾部删除元素SLPopBack(&sl);SLPrint(sl); // 输出当前顺序表: 7 6 1 2 3// 从头部删除元素SLPopFront(&sl);SLPrint(sl); // 输出当前顺序表: 6 1 2 3
}// 测试顺序表的其他操作
void SLTest02() {SL sl; // 定义一个顺序表SLInit(&sl); // 初始化顺序表// 在顺序表尾部插入元素SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl); // 输出当前顺序表: 1 2 3 4// 测试在指定位置之前插入数据SLInsert(&sl, 1, 99); // 在下标1的位置前插入99SLInsert(&sl, sl.size, 88); // 在顺序表最后插入88SLPrint(sl); // 输出当前顺序表: 99 1 2 3 4 88// 测试删除指定位置的数据SLErase(&sl, 0); // 删除下标为0的元素SLPrint(sl); // 输出当前顺序表: 1 2 3 4 88// 测试顺序表的查找int find = SLFind(&sl, 4); // 查找元素4的位置if (find < 0) {printf("没有找到!\n"); // 如果未找到,输出提示} else {printf("找到了!下标为%d\n", find); // 找到时输出下标}// 释放顺序表占用的资源SLDestroy(&sl);
}int main() {SLtest01(); SLTest02(); return 0;
}