🎄顺序表C实现
🔮头文件结构声明
//
// Created by Liu Xianmeng on 2023/9/30 23:00
//
// 基于数组的线性表的实现 头文件
//
#include <stdio.h>
#include <stdlib.h>
#ifndef CDATASTRCUTRUES_20230930_SEQUENCELIST_H
#define CDATASTRCUTRUES_20230930_SEQUENCELIST_H
#define INIT_SIZE 100 // 线性表存储空间的初始化分配
#define INCREMENT 50 // 线性表存储空间的增量分配
// 静态分配方式(❌实际顺序表的实现不使用静态内存分配)
typedef struct {
// 一次性分配存储空间
int data[INIT_SIZE]; // 存储空间 取数组
int size; // 线性表的实际存储元素的数目
int capacity; // 线性表的容量（实际声明的内存容量）
}StaticSequenceList; // 静态分配方式
// 动态分配方式(✅其他的函数都将使用动态内存分配的方式来进行)
typedef struct {
int *data;
int size; // 实际存储大小
int capacity; // 声明的空间大小
}DynamicSequenceList; // 动态分配方式
// 打印绿色的success信息
void printf_green(const char *s){
printf("\033[0m\033[1;32m%s\033[0m", s);
}
/**
* 初始化线性表
* @param L 传入一个空新创建的动态线性表
* @return 初始化成功返回 1 失败返回 0
*/
int initList(DynamicSequenceList *L) {
...
}
/**
* 向指定位置插入一个元素
* @param L 要操作的顺序表对象
* @param pos 指定插入数据的下标位置（注意是下标位置）
* @param elem 要插入的元素
* @return 1表示插入成功 0表示插入失败
*/
int insertOne(DynamicSequenceList *L, int pos, int elem) {
...
}
/**
* 删除指定的pos位置的元素 用deletedElem指针接收被删除元素的值
* @param L
* @param pos
* @param deletedElem
* @return 1表示删除成功 0表示删除失败
*/
int deleteOne(DynamicSequenceList *L, int pos, int *deletedElem) {
...
}
#endif //CDATASTRCUTRUES_20230930_SEQUENCELIST_H
🔮初始化&&插入数据
/**
* 初始化线性表
* @param L 传入一个空新创建的动态线性表
* @return 初始化成功返回 1 失败返回 0
*/
int initList(DynamicSequenceList *L) {
// 声明一个不包含实际数据的存储区域
L->data = (int*) malloc(INIT_SIZE * sizeof(int));
L->size = 0; // 初始化的时候存储的元素个数为0
L->capacity = INIT_SIZE; // 初始化的时候存储容量为INIT_SIZE
if(!L->data) {
perror("S DynamicSequenceList M initList() -> 分配失败 程序退出\n");
return -1; // 如果分配失败 则直接返回-1 程序结束
}
printf_green("S DynamicSequenceList M initList() -> 分配成功 程序退出\n");
return 1; // 分配成功返回
}
/**
* 向指定位置插入一个元素
* @param L 要操作的顺序表对象
* @param pos 指定插入数据的下标位置（注意是下标位置）
* @param elem 要插入的元素
* @return
*/
int insertOne(DynamicSequenceList *L, int pos, int elem) {
// pos最小是0（当线性表的size本身就等于0的情况）
// pos最大是size（插入到线性表的尾部）
if(pos < 0 || pos > L->size) {
perror("传入的下标不合法");
}
/***** 其他位置则合法 这个时候又需要判断一个东西 那就是L的容量是否已经满了 *****/
// 如果L的capacity===size则说明容量已经满了 需要进行扩容
if(L->size == L->capacity) {
// 使用realloc函数进行扩容 第1个参数为原来的数据指针 第2个参数为扩容后的大小
int *p = (int *) realloc(L->data, (L->size + INCREMENT)*sizeof(int));
if(!p) {
perror("S DynamicSequenceList M insertOne() -> 扩容失败");
return -1;
} else {
// 扩容成功
L->data = p;
// 更新容量
L->capacity = L->size + INCREMENT;
}
}
// 执行插入操作 需要把后面的 L.size - pos 个元素向后移动一位
int count = 1;
while(count <= L->size - pos) {
*(L->data + L->size - count + 1) = *(L->data + L->size - count);
++count;
}
// 移动结束之后 把elem插入到当前的位置
*(L->data + pos) = elem;
printf("在%d位置插入数字%d\n", pos, elem);
++L->size;
return -1;
}
⚡测试初始化&&插入数据
//
// Created by Liu Xianmeng on 2023/9/30 23:44
//
#include <stdio.h>
#include "SequenceList.h" // ⚡⚡⚡包含顺序表的头文件
int main() {
printf_green("main() -> program start..\n");
DynamicSequenceList L;
initList(&L);
insertOne(&L, 0, 1);
insertOne(&L, 0, 2);
insertOne(&L, 0, 3);
insertOne(&L, 3, 4);
int *p = L.data;
int count = 1;
while(count != L.size + 1) {
printf("遍历DynamicSequenceList -> *p = %d\n", *p);
++p; // 指向下一个元素所在的位置
++count;
}
return 0;
}
🔮删除指定元素
/**
* 删除指定的pos位置的元素 并返回已经删除的元素
* @param L
* @param pos
* @param deletedElem
* @return 1表示删除成功 0表示删除失败
*/
int deleteOne(DynamicSequenceList *L, int pos, int *deletedElem) {
// 1 判断删除pos的边界
if(pos < 0 || pos >= L->size) {
//perror("S DynamicSequenceList M deleteOne() -> pos超出边界");
return 0; // 删除失败
}
// 2 执行删除操作
*deletedElem = *(L->data + pos); // deletedElem指针指向被删除的数
for(int i = pos + 1; i <= L->size - 1; ++i) {
// [pos + 1, L->size - 1] 范围的元素向前移动一位
*(L->data + i - 1) = *(L->data + i);
}
--L->size; // size减1
// 3 删除成功 返回
return 1;
}
⚡执行测试
//
// Created by Liu Xianmeng on 2023/9/30 23:44
//
#include <stdio.h>
#include "SequenceList.h"
int main() {
printf_green("main() -> program start..\n");
DynamicSequenceList L;
initList(&L);
insertOne(&L, 0, 1);
insertOne(&L, 0, 2);
insertOne(&L, 0, 3);
int e;
int rst = deleteOne(&L, 0, &e);
if(rst == 1) printf("deleteOne(&L, 0, e) -> 被删除的元素是%d\n", e);
else printf("deleteOne(&L, 0, e) -> 下标越界 删除失败\n");
int rst2 = insertOne(&L, 3, 4);
if(rst2 == 1) printf("insertOne(&L, 3, 4) -> 被插入的元素是%d\n", e);
else printf("insertOne(&L, 3, 4) -> 下标越界 插入失败\n");
int *p = L.data;
int count = 1;
while(count != L.size + 1) {
printf("遍历DynamicSequenceList -> *p = %d\n", *p);
++p;
++count;
}
return 0;
}
测试结果
🔮合并两个顺序表
/**
* 假设L1和L2是非递减的顺序 这个函数将L1和L2合并到L3
* @param L1
* @param L2
* @param L3
*/
void mergeTwoList(DynamicSequenceList L1, DynamicSequenceList L2, DynamicSequenceList *L3) {
int len1 = L1.size;
int len2 = L2.size;
int i = 0, j = 0, k = 0;
while(i < len1 && j < len2) {
if(*(L1.data + i) <= *(L2.data + j)) {
*(L3->data + k++) = *(L1.data + i++);
} else {
*(L3->data + k++) = *(L2.data + j++);
}
++L3->size; // 注意要更新L3的size大小！
}
while(i < len1) {
*(L3->data + k++) = *(L1.data + i++);
++L3->size; // 注意要更新L3的size大小！
}
while(j < len2) {
*(L3->data + k++) = *(L2.data + j++);
++L3->size; // 注意要更新L3的size大小！
}
////////////////// 合并完成 //////////////////
}
⚡执行测试
//
// Created by Liu Xianmeng on 2023/9/30 23:44
//
#include <stdio.h>
#include "SequenceList.h"
int main() {
printf_green("main() -> program start..\n");
DynamicSequenceList L1;
initList(&L1);
insertOne(&L1, 0, 1);
insertOne(&L1, 1, 2);
insertOne(&L1, 2, 3);
DynamicSequenceList L2;
initList(&L2);
insertOne(&L2, 0, 1);
insertOne(&L2, 1, 2);
insertOne(&L2, 2, 3);
DynamicSequenceList L3;
initList(&L3);
mergeTwoList(L1, L2, &L3);
int lenL3 = L3.size;
int count = 0;
printf("合并后的顺序表 = [");
while(count < lenL3) {
// 不换行遍历打印
printf("%d,", *(L3.data + count++));
}
printf("]");
return 0;
}
测试结果
🎄顺序表java实现
package bigbigmeng.datastructures.array;
/**
@author Liu Xianmeng
@createTime 2023/5/1 9:18
@instruction 实现动态数组
*/
@SuppressWarnings({"all"})
public class DynamicArray {
private int size = 0; // 数组的实际大小
private int capacity = 8; // 数组的容量
private int[] array = {}; // 数组本身
/**
* 检查扩容 如果当前容量不够 则进行扩容
*/
private void checkAndGrow() {
// 如果实际容量已满 则进行下面的扩容判断
if(size == capacity) {
// 扩容为原来的1.5倍
capacity += capacity >> 1;
int[] newArray = new int[capacity];
// 把原数组的内容从下标0开始拷贝size个元素到newArray
System.arraycopy(array, 0, newArray, 0, size);
array = newArray;
return;
}
// 如果实际容量为0 则初始化数组
if(size == 0) {
array = new int[capacity];
return;
}
// 如果实际容量未满 则什么也不做
}
/**
* 如果不指定插入位置 则在数组的最后追加元素
*/
public void addLast(int e) {
add(size, e);
}
/**
* 向 [0 .. size] 位置添加元素
*/
public void add(int index, int e) {
// 扩容检查
checkAndGrow();
// 下标要合法
if(index >= 0 && index < size) {
System.arraycopy(array, index, array, index + 1, size - index);
} else {
throw new IndexOutOfBoundsException("下标越界/错误");
}
array[index] = e;
++size;
}
/**
* 从 [0 .. size] 位置删除元素
*/
public int remove(int index) {
if(index >= 0 && index < size) {
int removed = array[index];
System.arraycopy(array, index + 1, array, index, size - index - 1);
--size;
return removed;
}
throw new IndexOutOfBoundsException("下标错误");
}
/**
* 获取 [0 .. size] 位置元素
*/
public int get(int index) {
return array[index];
}
}
🎄总结
C的实现涉及到内存的实际操作 而Java的实现封装了内存的操作 因为使用Java实现动态顺序表会相对简单 但是使用C可以更好地体会程序对内存的实际掌控