数据结构: 线性表(顺序表实现)

news/2024/4/25 23:21:20/文章来源:https://blog.csdn.net/Kuzuba/article/details/132001895

文章目录

  • 1. 线性表的定义
  • 2. 线性表的顺序表示:顺序表
    • 2.1 概念及结构
    • 2.2 接口实现
      • 2.2.1 顺序表初始化 (SeqListInit)
      • 2.2.2 顺序表尾插 (SeqListPushBack)
      • 2.2.3 顺序表打印 (SeqListPrint)
      • 2.2.6 顺序表销毁 (SeqListDestroy)
      • 2.2.5 顺序表尾删 (SeqListPopBack)
      • 2.2.6 顺序表头插 (SeqListPushFront)
      • 2.2.7 顺序表头删 (SeqListPopFront)
      • 2.2.8 顺序表查找元素 (SeqListFind)
      • 2.2.9 顺序表指定位置插入 (SeqListInsert)
      • 2.2.10 顺序表指定位置删除 (SeqListErase)
    • 2.3 完整代码

1. 线性表的定义

线性表(linear list)是 n 个具有相同特性的数据元素的有序序列.
线性表是一种在实际中广泛使用的数据结构,常见的线性表: 顺序表,链表,栈,队列,字符串…

在这里插入图片描述

在这里插入图片描述

2. 线性表的顺序表示:顺序表

2.1 概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删查改.

顺序表一般可以分为:

  1. 静态顺序表: 使用定长数组存储元素
//顺序表的静态存储
#define N 7
typedef int SLDatatype;
typedef struct SeqList
{SLDatatype array[N];    //定长数组size_t size;            //有效元素的个数
}SeqList;

在这里插入图片描述

静态顺序表的特点: 容量创建时就已经确定
静态顺序表的缺点: 不能确定是具体给多少容量,给过大过小都不合适

  1. 动态顺序表: 使用动态开辟的数组存储
typedef int SLDataType;
typedef struct SeqList
{SLDataType *array;      //指向动态开辟的数组size_t size;            //有效元素的个数size_t capacity;        //容量空间的大小
}SeqList;

在这里插入图片描述

2.2 接口实现

静态顺序表只适用于确定直到需要存多少数据的场景.静态顺序表的定长数组导致了N定大了.空间开多了浪费,空间开小了不够用.

所以现实中基本上是使用动态顺序表,根据需要的动态的分配空间大小.

typedef int SLDataType;//顺序表的动态存储
typedef struct SeqList
{SLDataType* a;      //指向动态开辟的数组size_t size;        //有效数据的个数size_t capacity;    //容量空间的大小
}SeqList;//基本增删查改接口//顺序表初始化
void SeqListInit(SeqList* ps);
//顺序表销毁
void SeqListDestroy(SeqList* ps);
//顺序表打印
void SeqListPrint(const SeqList* ps);
//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x);
//顺序表头插
void SeqListPushFront(SeqList* ps, SLDataType x);
//顺序表尾删
void SeqListPopBack(SeqList* ps);
//顺序表头删
void SeqListPopFront(SeqList* ps);	
//顺序表查找
int SeqListFind(const SeqList* ps, SLDataType x);
//顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDataType x);
//顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

2.2.1 顺序表初始化 (SeqListInit)

  • Seqlist.h
#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;//顺序表的动态存储
typedef struct SeqList
{SLDataType* a;      //指向动态开辟的数组size_t size;        //有效数据的个数size_t capacity;    //容量空间的大小
}SeqList;//顺序表初始化
void SeqListInit(SeqList* ps);
  1. 使用#pragma once确保头文件不会倍重复包含
  1. 使用typedef将类型命名为SLDatatype,确保后续修改数组元素类型
  1. 使用typedef将动态顺序表结构体类型命名为SeqList,方便后续使用结构体类型
  1. 最后定义初始化接口函数void SeqListInit(SeqList* ps).这里使用了传址调用,初始化对结构体内容进行修改,要作用到主程序实参上面,就需要传递地址.
  • Seqlist.c
//顺序表初始化
void SeqListInit(SeqList* ps)
{assert(ps);ps->a = (SLDataType*)malloc(4*sizeof(SLDataType));if (ps->a == NULL){perror("SeqListInit");exit(-1);}ps->size = 0;ps->capacity = 4;
}
  1. assert(ps)确保传入的地址是有效地址
  1. ps->a = (SLDataType*)malloc(4*sizeof(SLDataType));动态开辟了能存放 4 个数据的数组空间
  1. ps->size = 0;ps->capacity = 4;对有效个数和容量空间进行初始化.
  • Test.c
#include "SeqList.h"voit SeqListTest1()
{SeqList sl;SeqListInit(&sl);
}int main(void)
{SeqList sl;return 0;
}
  1. 将测试代码放入函数中,可以方便进行选择性调试信息
  1. 程序运行结束后,通过调试得到以下信息:
    在这里插入图片描述

sl的成员都通过调用初始化程序创建成功了

2.2.2 顺序表尾插 (SeqListPushBack)

顺序表尾插,就是在数组末尾添加元素,可能会出现如下情况:
在这里插入图片描述

在这里插入图片描述

  • SeqList.h
void SeqListPushBack(SeqList* ps, SLDataType x);
  1. 要修改顺序表的内容,同样是传址调用.
  1. x为要插入的数据,类型为SLDataType
  • SeqList.c
//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{assert(ps);//若容量不够且扩容失败, 直接结束程序if (SeqListCheckCapacity(ps) == 0){exit(-1);}ps->a[ps->size] = x;ps->size++;
}
  1. 首先先判断容量是否足够,因为其他插入方式也需要使用到这个功能,所以我将其封装成了一个函数SeqListCheckCapacity,具体如下:
//检查容量是否满,若满则扩容,失败返回0,成功或容量未满返回1
static int SeqListCheckCapacity(SeqList* ps)
{//如果容量已满,则进行尝试扩容if (ps->size == ps->capacity){//使用realloc将原空间扩大为 2 倍SLDataType* tmp = (SLDataType*)realloc(ps->a, 2 * ps->capacity * sizeof(SLDataType));//如果开辟失败,则提示后返回 0if (tmp == NULL){printf("realloc 扩容失败.\n");return 0;}//如果开辟成功,则更新容量ps->a = tmp;ps->capacity *= 2;}return 1;
}

若容量已满,则使用realloc()函数进行扩容,每次将空间扩大为2倍.如果扩容失败,直接返回 0;如果扩容成功,则返回 1.

同时开辟成功的话,更新容量.并且和空间容量足够的情况下一样,返回 1

  1. 确保容量足够的情况下,将要插入的值直接赋值到 size 位置上,同时 size++
  • “Test.c”
void SeqListTest1()
{SeqList sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);
}
  1. 第一次插入,容量足够,if判断容量足够,直接插入:
    在这里插入图片描述
  1. 因为初始化的时候赋予了顺序表容量为4,第2,3,4次插入都不需要扩容,直接插入
  1. 第5次插入,容量不够,扩充完容量后才插入数据:
    在这里插入图片描述
  1. 同时,这个时候观察顺序表成员,容量已经扩容了两倍,size 已经变成了 5
    在这里插入图片描述

2.2.3 顺序表打印 (SeqListPrint)

顺序表打印,之间遍历数组元素并且打印出来就行了,注意这里只是适用于int类型的数据

  • SeqList.h
void SeqListPrint(const SeqList* ps);

使用const修饰形参常变量,保护ps所指向的数据,因为这里只需要打印操作,并不需要进行修改.

  • SeqList.c
//顺序表打印
void SeqListPrint(const SeqList* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}

遍历整个顺序表,简单使用for循环就可以了

  • Test.c
void SeqListTest1()
{SeqList sl;SeqListInit(&sl);SeqListPrint(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);
}

程序运行结果打印正确:
在这里插入图片描述

2.2.6 顺序表销毁 (SeqListDestroy)

动态顺序表是通过动态申请内存空间来存储数据的,在不需要该顺序表,需要将这块空间归还过去,否则会出现内存泄漏

  • SeqList.h
void SeqListDestroy(SeqList* ps);
  • SeqList.c
//顺序表销毁
void SeqListDestroy(SeqList* ps)
{assert(ps);free(ps->a);		//将空间还给操作系统ps->a = NULL;		//置空防止野指针ps->size = 0;		//空间置零ps->capacity = 0;
}

由于只有数组空间是动态申请的,只需要free(ps->a),归还后将有效个数和容量置为 0

  • Test.c
void SeqListTest1()
{SeqList sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListDestroy(&sl);
}

2.2.5 顺序表尾删 (SeqListPopBack)

顺序表尾删,不需要移动元素,直接将 size–.

并不需要将这块空间真正归还给操作系统:使用free()函数

在这里插入图片描述

  • SeqList.h
void SeqListPopBack(SeqList* ps, SLDataType x);
  • SeqList.c
//顺序表尾删
void SeqListPopBack(SeqList* ps)
{assert(ps);//确保顺序表有数据可删assert(ps->size > 0);//进行删除操作ps->size--;
}

在确保顺序表有数据可删的情况下, 直接size减1就行

  • test.c
	SeqList sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPopBack(&sl);SeqListPrint(&sl);SeqListDestroy(&sl);

测试运行结果如下:
在这里插入图片描述

通过调试可以看出, 顺序表删除元素仅仅是将 size 减一, 而不需要修改容量, 甚至试图 free 删去元素所在的空间(释放非动态申请空间时指向的空间,这是会造成内存泄露的!):
在这里插入图片描述

2.2.6 顺序表头插 (SeqListPushFront)

顺序表头插, 需要先将下标 0 - ps->size - 1 的元素全都向后移动一个元素的位置, 再将需要插入的数据插入到顺序表头部位置
在这里插入图片描述

  • SeqList.h
void SeqListPushFront(SeqList* ps, SLDataType x);
  • SeqList.c
//顺序表头插
void SeqListPushFront(SeqList* ps, SLDataType x)
{assert(ps);	//若容量不够且扩容失败, 直接结束程序if (SeqListCheckCapacity(ps) == 0){exit(-1);}//从后开始将每个元素向后移动一个位置,直到下标到0int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}//第一个位置放入对应元素ps->a[0] = x;ps->size++;
}
  1. 首先进行容量判断, 使用SeqListCheckCapacity()函数进行判断, 并扩容
  1. 容量足够时, 一次向后移动元素, 需要从后往前移动才能不覆盖已有的元素. 首先定义一个 end 变量,记录最后一个元素的下标.
  1. 随后不断将元素后移, 直至 end指向了第一个元素.
  1. 所有的元素移动完毕后, 顺序表第一个空间是空出来的, 这时候将要插入的数据头插到第一个空间内.并且更新有效元素个数.
  • Test.c
	SeqList sl;SeqListInit(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPrint(&sl);SeqListPushFront(&sl, -1);SeqListPushFront(&sl, -2);SeqListPushFront(&sl, -3);SeqListPushFront(&sl, -4);SeqListPushFront(&sl, -5);SeqListPrint(&sl);SeqListDestroy(&sl);

在头插元素之前, 顺序表中已经有了 5 个元素, 随后进行头插, 测试结果如下:
在这里插入图片描述

2.2.7 顺序表头删 (SeqListPopFront)

顺序表头删和顺序表头插相反, 将第二个元素至最后一个元素全部前移一个元素空间就可以了.

在这里插入图片描述

  • SeqList.h
void SeqListPopFront(SeqList* ps);
  • SeqList.c
//顺序表头删
void SeqListPopFront(SeqList* ps)
{assert(ps);//确保顺序表有数据可删assert(ps->size > 0);//从前向后将每个元素向前移动一个位置,直到下标为size-1int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}
  1. 和顺序表尾删一样, 也需要断言表中有数据存在, 否则直接结束程序.
  1. 直接定义一个 begin 第二个元素, 将该元素向前移动一个元素空间后, begin++,直到第三个元素, 直至将所有的元素(除了要删除的第一个元素)都前移一个元素空间.
  1. 最后 size 减一表示删除成功
  • Test.c
	SeqList sl;SeqListInit(&sl);SeqListPushFront(&sl, -1);SeqListPushFront(&sl, -2);SeqListPushFront(&sl, -3);SeqListPushFront(&sl, -4);SeqListPushFront(&sl, -5);SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPopFront(&sl);SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPopFront(&sl);SeqListPrint(&sl);SeqListDestroy(&sl);

测试结果如下:
在这里插入图片描述

2.2.8 顺序表查找元素 (SeqListFind)

思路就是遍历顺序表, 并且判断是否有符合要求的元素, 如果有返回该元素下标, 如果没有返回 -1

  • SeqList.h
int SeqListFind(const SeqList* ps, SLDataType x);
  • SeqList.c
//顺序表查找
int SeqListFind(const SeqList* ps, SLDataType x)
{	assert(ps);int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}
  • Test.c
	SeqList sl;SeqListInit(&sl);SeqListPushBack(&sl, 0);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPushBack(&sl, 6);SeqListPushBack(&sl, 7);SeqListPushBack(&sl, 8);SeqListPushBack(&sl, 9);SeqListPushBack(&sl, 10);int pos = 0;pos = SeqListFind(&sl, 2);printf("%d\n", pos);pos = SeqListFind(&sl, 10);printf("%d\n", pos);pos = SeqListFind(&sl, 11);printf("%d\n", pos);
  1. 首先我插入了从 0 - 10 的 11 个元素,接着使用SeqListFind()分别查找 2, 10, 11, 并将结果打印出来
  2. 测试运行结果如下:
    在这里插入图片描述
    查找到的元素返回下标, 未查找到的元素返回 -1

2.2.9 顺序表指定位置插入 (SeqListInsert)

实现方式和头插差不多, 只是添加了个 pos 参数.
注意 pos 的合法性

在这里插入图片描述

  • SeqList.h
void SeqListInsert(SeqList* ps, int pos, SLDataType x);
  • SeqList.c
//在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{assert(ps);//确保插入在合法位置assert(pos >= 0 && pos <= ps->size);//若空间不够则进行扩容if (SeqListCheckCapacity(ps) == 0){exit(-1);}//从后向前将pos后面的元素都移动一次int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}//将pos位置的值设置ps->a[pos] = x;ps->size++;
}
  1. 第一步先判断pos的合法性, 如果插入位置不合法, 直接结束程序
  1. 接着使用 SeqListCheckCapacity() 函数判断容量是否充足, 不充足则扩充容量
  1. 随后定义一个 end 变量指向顺序表最后一个元素位置, 将该元素后移一个元素空间, 同时end--, end指向顺序表倒数第二个元素位置
  1. 重复操作直至end指向pos处的位置, 并将pos处的元素后移一个元素空间
  1. 这时pos处的空间已经空闲, 将需要插入的元素插入到空闲空间, 同时size++, 有效个数加一
  • Test.c
	SeqList sl;SeqListInit(&sl);SeqListPushBack(&sl, 0);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPushBack(&sl, 6);SeqListPushBack(&sl, 7);SeqListPushBack(&sl, 8);SeqListPushBack(&sl, 9);SeqListPushBack(&sl, 10);pos = 2;SeqListInsert(&sl, pos, 100);SeqListPrint(&sl);pos = 10;SeqListInsert(&sl, pos, 100);SeqListPrint(&sl);pos = sl.size + 1;SeqListInsert(&sl, pos, 100);SeqListPrint(&sl);SeqListDestroy(&sl);
  1. 这里我插入了三次, 位置分别为 2, 10, sl.size + 1
  1. 测试结果如下:
    在这里插入图片描述
    前两次 pos 合法,插入成功; 最后一次 pos 值不合法, 程序直接退出

这样头插和尾插的功能可以直接复用SeqListInsert():

//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{assert(ps);//若容量不够且扩容失败, 直接结束程序if (SeqListCheckCapacity(ps) == 0){exit(-1);}SeqListInsert(ps, ps->size, x);
}	   //顺序表头插
void SeqListPushFront(SeqList* ps, SLDataType x)
{assert(ps);	//若容量不够且扩容失败, 直接结束程序if (SeqListCheckCapacity(ps) == 0){exit(-1);}SeqListInsert(ps, 0, x);
}

2.2.10 顺序表指定位置删除 (SeqListErase)

实现方式和顺序表头删差不多, 只是多了个 pos 参数

要注意pos的合法性: pos >=0 && pos < ps->size

  • SeqList.h
void SeqListErase(SeqList* ps, int pos, SLDataType x);
  • SeqList.c
//删除pos位置上的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);//确保pos值合法assert(pos >= 0 && pos < ps->size);//确保有空间可删assert(ps->size > 0);//从前将从pos+1的元素向前移动一次int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}
  • Test.c
	SeqList sl;SeqListInit(&sl);SeqListPushBack(&sl, 0);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPushBack(&sl, 6);SeqListPushBack(&sl, 7);SeqListPushBack(&sl, 8);SeqListPushBack(&sl, 9);SeqListPushBack(&sl, 10);int pos;pos = 1;SeqListErase(&sl, pos);SeqListPrint(&sl);pos = 3;SeqListErase(&sl, pos);SeqListPrint(&sl);SeqListDestroy(&sl);

测试运行结果如下:
在这里插入图片描述

同样这样头删和尾删的功能可以直接复用SeqListErase():

//顺序表尾删
void SeqListPopBack(SeqList* ps, SLDataType x)
{assert(ps);//确保顺序表有数据可删assert(ps->size > 0);SeqListErase(ps, ps->size - 1);
}	   //顺序表头删
void SeqListPopFront(SeqList* ps, SLDataType x)
{assert(ps);	//确保顺序表有数据可删assert(ps->size > 0);SeqListErase(ps, 0);
}

2.3 完整代码

  • SeqList.h: 头文件以及函数申明
#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
typedef struct SeqList
{SLDataType* a;size_t size;size_t capacity;
}SeqList;// 对数据的管理:增删查改
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);void SeqListPrint(const SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDataType x);
void SeqListPushFront(SeqList* ps, SLDataType x);
void SeqListPopBack(SeqList* ps);
void SeqListPopFront(SeqList* ps);	// 顺序表查找
int SeqListFind(const SeqList* ps, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);
  • SeqList.c: 接口实现
#include "SeqList.h"//检查容量是否满,若满则扩容,失败返回0,成功或容量未满返回1
static int SeqListCheckCapacity(SeqList* ps)
{//如果容量已满,则进行尝试扩容if (ps->size == ps->capacity){//使用realloc将原空间扩大为 2 倍SLDataType* tmp = (SLDataType*)realloc(ps->a, 2 * ps->capacity * sizeof(SLDataType));//如果开辟失败,则提示后返回 0if (tmp == NULL){printf("realloc 扩容失败.\n");return 0;}//如果开辟成功,则更新容量ps->a = tmp;ps->capacity *= 2;}return 1;
}//顺序表初始化
void SeqListInit(SeqList* ps)
{assert(ps);ps->a = (SLDataType*)malloc(4*sizeof(SLDataType));if (ps->a == NULL){perror("SeqListInit");exit(-1);}ps->size = 0;ps->capacity = 4;
}//顺序表销毁
void SeqListDestroy(SeqList* ps)
{assert(ps);free(ps->a);		//将空间还给操作系统ps->a = NULL;		//置空防止野指针ps->size = 0;		//空间置零ps->capacity = 0;
}//顺序表打印
void SeqListPrint(const SeqList* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{assert(ps);//若容量不够且扩容失败, 直接结束程序if (SeqListCheckCapacity(ps) == 0){exit(-1);}ps->a[ps->size] = x;ps->size++;
}	   //顺序表尾删
void SeqListPopBack(SeqList* ps)
{assert(ps);//确保顺序表有数据可删assert(ps->size > 0);//进行删除操作ps->size--;
}//顺序表头插
void SeqListPushFront(SeqList* ps, SLDataType x)
{assert(ps);	//若容量不够且扩容失败, 直接结束程序if (SeqListCheckCapacity(ps) == 0){exit(-1);}//从后开始将每个元素向后移动一个位置,直到下标到0int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}//第一个位置放入对应元素ps->a[0] = x;ps->size++;
}//顺序表头删
void SeqListPopFront(SeqList* ps)
{assert(ps);//确保顺序表有数据可删assert(ps->size > 0);//从前向后将每个元素向前移动一个位置,直到下标为size-1int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}//顺序表查找
int SeqListFind(const SeqList* ps, SLDataType x)
{	assert(ps);int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}//在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{assert(ps);//确保插入在合法位置assert(pos >= 0 && pos <= ps->size);//若空间不够则进行扩容if (SeqListCheckCapacity(ps) == 0){exit(-1);}//从后向前将pos后面的元素都移动一次int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}//将pos位置的值设置ps->a[pos] = x;ps->size++;
}//删除pos位置上的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);//确保pos值合法assert(pos >= 0 && pos < ps->size);//确保有空间可删assert(ps->size > 0);//从前将从pos+1的元素向前移动一次int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}
  • Test.c: 测试用例
#include "SeqList.h"void SeqListTest1()
{SeqList sl;SeqListInit(&sl);SeqListPrint(&sl);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPopBack(&sl);	SeqListPopBack(&sl);	SeqListPopBack(&sl);	SeqListPopBack(&sl);	SeqListPopBack(&sl);	SeqListPopBack(&sl);	SeqListPopBack(&sl);	SeqListPrint(&sl);SeqListDestroy(&sl);
}void SeqListTest2()
{SeqList sl;SeqListInit(&sl);SeqListPushFront(&sl, 1);SeqListPushFront(&sl, 2);SeqListPushFront(&sl, 3);SeqListPushFront(&sl, 4);SeqListPushFront(&sl, 5);SeqListPopFront(&sl);SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPrint(&sl);SeqListDestroy(&sl);
}void SeqListTest3()
{SeqList sl;SeqListInit(&sl);SeqListPushBack(&sl, 0);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPushBack(&sl, 6);SeqListPushBack(&sl, 7);SeqListPushBack(&sl, 8);SeqListPushBack(&sl, 9);SeqListPushBack(&sl, 10);int pos = 0;pos = SeqListFind(&sl, 2);printf("%d\n", pos);pos = SeqListFind(&sl, 10);printf("%d\n", pos);pos = SeqListFind(&sl, 11);printf("%d\n", pos);pos = 2;SeqListPrint(&sl);SeqListInsert(&sl, pos, 100);SeqListPrint(&sl);pos = 10;SeqListPrint(&sl);SeqListInsert(&sl, pos, 100);SeqListPrint(&sl);pos = sl.size + 1;SeqListInsert(&sl, pos, 100);SeqListDestroy(&sl);
}void SeqListTest4()
{SeqList sl;SeqListInit(&sl);SeqListPushBack(&sl, 0);SeqListPushBack(&sl, 1);SeqListPushBack(&sl, 2);SeqListPushBack(&sl, 3);SeqListPushBack(&sl, 4);SeqListPushBack(&sl, 5);SeqListPushBack(&sl, 6);SeqListPushBack(&sl, 7);SeqListPushBack(&sl, 8);SeqListPushBack(&sl, 9);SeqListPushBack(&sl, 10);int pos;pos = 1;SeqListErase(&sl, pos);SeqListPrint(&sl);pos = 3;SeqListErase(&sl, pos);SeqListPrint(&sl);SeqListDestroy(&sl);	}
int main(void)
{//SeqListTest1();//SeqListTest2();//SeqListTest3();SeqListTest4();return 0;
}

本章完.

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.luyixian.cn/news_show_337427.aspx

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Python 进阶（二）：操作字符串的常用方法

Python 进阶（二）：操作字符串的常用方法

❤️ 博客主页&#xff1a;水滴技术 &#x1f338; 订阅专栏&#xff1a;Python 入门核心技术 &#x1f680; 支持水滴&#xff1a;点赞&#x1f44d; 收藏⭐ 留言&#x1f4ac; 文章目录 一、索引和切片二、字符串长度三、查找和替换四、大小写转换五、分割和连接六、去除空…
阅读更多...
《JavaSE-第二十章》之线程 的创建与Thread类

《JavaSE-第二十章》之线程 的创建与Thread类

文章目录 什么是进程&#xff1f;什么是线程&#xff1f;为什么需要线程&#xff1f; 基本的线程机制创建线程1.实现 Runnable 接口2.继承 Thread 类3.其他变形 Thread常见构造方法1. Thread()2. Thread(Runnable target)3. Thread(String name)4. Thread(Runnable target, Str…
阅读更多...
C语言每天一练----输出水仙花数

C语言每天一练----输出水仙花数

题目&#xff1a;请输出所有的"水仙花数" 题解&#xff1a;所谓"水仙花数"是指一个3位数,其各位数字立方和等于该数本身。 例如, 153是水仙花数, 因为153 1 * 1 * 1 5 * 5 * 5 3 * 3 * 3" #define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h&g…
阅读更多...
Segmentation fault 利用 core.xxx文件帮助你debug

Segmentation fault 利用 core.xxx文件帮助你debug

在没有get到本文介绍的技能之前的时候&#xff0c;以前遇到程序发生了 Segmentation fault 时&#xff0c;也是一筹莫展&#xff0c;看到伴随程序崩溃而生成的 core.xxxx 文件时&#xff08;有时会生成&#xff0c;有时不会生成&#xff0c;留着下面介绍&#xff09;&#xff0…
阅读更多...
windows系统之WSL 安装 Ubuntu

windows系统之WSL 安装 Ubuntu

WSL windows10 以上才有这个wsl功能 WSL&#xff1a; windows Subsystem for Linux 是应用于Windows系统之上的Linux子系统 作用很简单&#xff0c;可以在Windows系统中获取Linux系统环境&#xff0c;并完全直连计算机硬件&#xff0c;无需要通过虚拟机虚拟硬件 Windows10的W…
阅读更多...
TCP网络通信编程之字符流

TCP网络通信编程之字符流

【案例1】 【题目描述】 【 注意事项】 (3条消息) 节点流和处理流 字符处理流BufferedReader、BufferedWriter&#xff0c;字节处理流-BufferedInputStream和BufferedOutputStream (代码均正确且可运行_Studying~的博客-CSDN博客 1。这里需要使用字符处理流&#xff0c;来将…
阅读更多...
C++代码格式化工具clang-format详细介绍

C++代码格式化工具clang-format详细介绍

文章目录 clang-format思考代码风格指南生成您的配置运行 clang-format禁用一段代码的格式设置clang-format的设置预览 clang-format 我曾在许多编程团队工作过&#xff0c;这些团队名义上都有“编程风格指南”。该指南经常被写下来并放置在开发人员很少查看的地方。几乎在每种…
阅读更多...
MQTT服务器详细介绍：连接物联网的通信枢纽

MQTT服务器详细介绍：连接物联网的通信枢纽

随着物联网技术的不断发展&#xff0c;MQTT&#xff08;Message Queuing Telemetry Transport&#xff09;协议作为一种轻量级、可靠、灵活的通信协议&#xff0c;被广泛应用于物联网领域。在MQTT系统中&#xff0c;MQTT服务器扮演着重要的角色&#xff0c;作为连接物联网设备和…
阅读更多...
常见网关对比

常见网关对比

常见网关对比 目前常见的开源网关大致上按照语言分类有如下几类&#xff1a; Nginxlua &#xff1a;OpenResty、Kong、Orange、Abtesting gateway 等 Java &#xff1a;Zuul/Zuul2、Spring Cloud Gateway、Kaazing KWG、gravitee、Dromara soul 等 Go &#xff1a;Janus、fa…
阅读更多...
计算机里基本硬件的组成以及硬件协同

计算机里基本硬件的组成以及硬件协同

文章目录 冯诺依曼体系输入设备输出设备存储器运算器控制器协同工作的流程 冯诺依曼体系 世界上第一台通用计算机&#xff0c;ENIAC&#xff0c;于1946年诞生于美国一所大学。 ENIAC研发的前期&#xff0c;需要工作人员根据提前设计好的指令手动接线&#xff0c;以这种方式输入…
阅读更多...
【HDFS】Block、BlockInfo、BlockInfoContiguous、BlockInfoStriped的分析记录

【HDFS】Block、BlockInfo、BlockInfoContiguous、BlockInfoStriped的分析记录

本文主要介绍如下内容： 关于几个Block类之间的继承、实现关系；针对文章标题中的每个类，细化到每个成员去注释分析列出、并详细分析BlockInfo抽象类提供的抽象方法、非抽象方法的功能针对几个跟块组织结构的方法再进行分析。moveBlockToHead、listInsert、listRemove等。一、…
阅读更多...
spring5源码篇(13)——spring mvc无xml整合tomcat与父子容器的启动

spring5源码篇(13)——spring mvc无xml整合tomcat与父子容器的启动

spring-framework 版本&#xff1a;v5.3.19 文章目录 整合步骤实现原理ServletContainerInitializer与WebApplicationInitializer父容器的启动子容器的启动 相关面试题 整合步骤 试想这么一个场景。只用 spring mvc&#xff08;确切来说是spring-framework&#xff09;&#x…
阅读更多...
MySQL 实现分库和分表的备份 2023.7.29

MySQL 实现分库和分表的备份 2023.7.29

1、分库备份 [rootlocalhost mysql-backup]# cat db_bak.sh #!/bin/bash k_userroot bak_password123456 bak_path/root/mysql-backup/ bak_cmd"-u$bak_user -p$bak_password" exc_db"Database|information_schema|mysql|performance_schema|sys" dbname…
阅读更多...
C#，数值计算——对数正态分布（logarithmic normal distribution）的计算方法与源程序

C#，数值计算——对数正态分布（logarithmic normal distribution）的计算方法与源程序

对数正态分布&#xff08;logarithmic normal distribution&#xff09;是指一个随机变量的对数服从正态分布&#xff0c;则该随机变量服从对数正态分布。对数正态分布从短期来看&#xff0c;与正态分布非常接近。但长期来看&#xff0c;对数正态分布向上分布的数值更多一些。 …
阅读更多...
基于minio的dababend部署总结

基于minio的dababend部署总结

Databend 是一款开源、弹性、低成本&#xff0c;基于对象存储也可以做实时分析的新式数仓。期待您的关注&#xff0c;一起探索云原生数仓解决方案&#xff0c;打造新一代开源 Data Cloud。 Minio搭建 minio 192.168.10.159 cd /data mkdir minio cd minio wget https://dl…
阅读更多...
word2vec原理总结

word2vec原理总结

参考文章&#xff1a;https://www.cnblogs.com/pinard/p/7160330.html word2vec是google在2013年推出的一个NLP工具&#xff0c;它的特点是将所有的词向量化&#xff0c;这样词与词之间就可以定量的去度量他们之间的关系&#xff0c;挖掘词之间的联系。 1 词向量编码 1.1 one…
阅读更多...
Unity源码分享-黄金矿工游戏完整版

Unity源码分享-黄金矿工游戏完整版

Unity源码分享-黄金矿工游戏完整版 项目地址&#xff1a;https://download.csdn.net/download/Highning0007/88118933
阅读更多...
Python-Python基础综合案例--数据可视化 - 地图可视化

Python-Python基础综合案例--数据可视化 - 地图可视化

版本说明 当前版本号[20230729]。 版本修改说明20230729初版 目录 文章目录 版本说明目录知识总览图Python基础综合案例--数据可视化 - 地图可视化基础地图使用案例效果视觉映射器 疫情地图-国内疫情地图案例效果实操设置全局配置选项 疫情地图-省级疫情地图案例效果实操 知…
阅读更多...
如何做好IT类的技术面试

如何做好IT类的技术面试

目录 一、IT行业的招聘渠道 二、如何做好技术面试官 三、谈谈IT行业如何做好招聘工作 四、面试IT公司的小技巧 五、面试有哪些常见的问题 六、关于面试的一些建议 面试可能是我们每个人都必须会遇到的事情&#xff0c;而技术面试更具有专业性&#xff0c;以下会从几个方面…
阅读更多...
IDEA将本地项目上传到码云

IDEA将本地项目上传到码云

一、创建本地仓库并关联 用IDEA打开项目&#xff0c;在菜单栏点击vcs->create git repository创建本地仓库&#xff0c; 选择当前项目所在的文件夹当作仓库目录。 二、将项目提交本地仓库 项目名右键就会出现“GIT”这个选项->Add->Commit Directory, 先将项目add…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业