#include "SeqList.h"
//尾插测试
void TestSeqList1()
{ 
  //尾插
  SeqList s;
  SeqListInit(&s); //这里&是取地址
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPushBack(&s, 5);
  SeqListPushBack(&s, 0);
  SeqListPrint(&s);
  SeqListPushBack(&s, 10);
  SeqListPushBack(&s, 20);
  SeqListPrint(&s);
  //如果不小心传了空指针，须使用断言进行报错查找
  //SeqListPrint(NULL);
  //测试越界
  //int a[10];
  ////a[10] = 1;
  ////a[11] = 1;
  //a[12] = 1;
  ////a[100] = 1;
}
//尾删测试
void TestSeqList2()
{
  //尾插
  SeqList s;
  SeqListInit(&s); //这里&是取地址
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPushBack(&s, 5);
  SeqListPushBack(&s, 0);
  SeqListPrint(&s);
  //尾删，删除最后两个数据
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPrint(&s);
  //删除完毕，且删多了
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPrint(&s);
  //再次尾插数据
  SeqListPushBack(&s, 10);
  SeqListPushBack(&s, 20);
  SeqListPrint(&s);
}
//头插测试
void TestSeqList3()
{   //扩容测试
  /*int* p = (int*)malloc(sizeof(int) * 10);
  printf("%p\n", p);
  int* p1 = (int*)realloc(p, sizeof(int) * 100);
  printf("%p\n", p1);*/
  SeqList s;
  SeqListInit(&s);
  //尾插
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPrint(&s);
  //头插
  SeqListPushFront(&s, 0);
  SeqListPushFront(&s, -1);
  SeqListPrint(&s);
}
//头删测试
void TestSeqList4()
{
  SeqList s;
  SeqListInit(&s);
  //尾插
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPrint(&s);
  //头插
  SeqListPushFront(&s, 0);
  SeqListPushFront(&s, -1);
  SeqListPrint(&s);
  //头删
  SeqListPopFront(&s);
  SeqListPopFront(&s);
  SeqListPopFront(&s);
  SeqListPopFront(&s);
  SeqListPopFront(&s);
  SeqListPrint(&s);
  SeqListPopFront(&s);
  SeqListPrint(&s);
  //再次头删，删多了
  SeqListPopFront(&s);
  SeqListPopFront(&s);
  SeqListPrint(&s);
  //再次头插
  SeqListPushFront(&s, 0);
  SeqListPushFront(&s, -1);
  SeqListPrint(&s);
}
//pos指定位置插入测试
void TestSeqList5()
{
  SeqList s;
  SeqListInit(&s);
  //尾插
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPrint(&s);
  //pos指定位置插入数据
  SeqListInsert(&s, 10, 100);
  SeqListInsert(&s, 1, 20);
  SeqListInsert(&s, 5, 50);
  SeqListInsert(&s, 0, 50);
  SeqListPrint(&s);
  //销毁释放内存
  SeqListDestroy(&s);
}
//pos指定位置删除测试
void TestSeqList6()
{
  SeqList s;
  SeqListInit(&s);
  //尾插
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPrint(&s);
  //头插
  SeqListPushFront(&s, 0);
  SeqListPushFront(&s, -1);
  SeqListPrint(&s);
  //pos指定位置删除
  SeqListErase(&s, 4);
  SeqListPrint(&s);
  SeqListErase(&s, 0);
  SeqListPrint(&s);
  SeqListErase(&s, 1);
  SeqListPrint(&s);
}
//顺序表修改测试
void TestSeqList7()
{
  SeqList s;
  SeqListInit(&s);
  //尾插
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPushBack(&s, 5);
  SeqListPushBack(&s, 6);
  SeqListPrint(&s);
  //1.直接修改
  SeqListModify(&s, 3, 1000);
  SeqListPrint(&s);
  //2.按值查找后修改
  int pos = SeqListFind(&s, 6);//括号第二个数是确定的值，不是下标
  if (pos != -1)
  {
    SeqListModify(&s, pos, 90);
  }
  SeqListPrint(&s);
}
int main()
{
  SeqList s;
  SeqListInit(&s); //这里&是取地址
  TestSeqList1();
  TestSeqList2();
  TestSeqList3();
  TestSeqList4();
  TestSeqList5();
  TestSeqList6();
    TestSeqList7();
  return 0;
}

SeqList.c：

#include "SeqList.h"
//打印顺序表
void SeqListPrint(SeqList* psl)
{   //Print可以不传指针，因为它不需要修改结构体的内容，但结构体较大，传指针可以减少拷贝
  assert(psl);
  for (int i = 0; i < psl->size; ++i)
  {
    printf("%d ", psl->a[i]);
  }
  printf("\n");
}
//顺序表初始化
void SeqListInit(SeqList* psl)
{
  assert(psl);
  psl->a = NULL;
  psl->size = 0;
  psl->capacity = 0;
}
//顺序表销毁、释放内存
void SeqListDestroy(SeqList* psl)
{
  assert(psl);
  free(psl->a);
  psl->a = NULL;
  psl->capacity = psl->size = 0;
}
//检查容量，降低冗余度
void SeqListCheckCapacity(SeqList* psl)
{
  // ˣҪ
  if (psl->size == psl->capacity)
  {   //relloc扩容
    size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
    //因为最初是0，*2也是0.所以最初为0就给4个(4没有特定含义，只要不是太大就行），若不是0就 psl->capacity * 2（折中）*3或*4均可
    SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    else
    {
      psl->a = tmp;
      psl->capacity = newCapacity;
    }
  }
}
//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
  assert(psl);
  SeqListCheckCapacity(psl);
  psl->a[psl->size] = x;
  psl->size++;
}
//顺序表尾删
void SeqListPopBack(SeqList* psl)
{
  assert(psl);
  //psl->a[psl->size - 1] = 0;  
  //此语句是将删除后的覆盖为0，但这样做不太好
  //原因：1.若原有最后一个为0，意义不大  2.若类型不为int，而是double或char，覆盖为0有误
  //因为size标识有效数据，因此即使删除，数据还在capacity，即使删除后没有被覆盖，但不会访问
  if (psl->size > 0)
  {
    psl->size--;
  }
}
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
    assert(psl);
    SeqListCheckCapacity(psl);
    // 挪动数据，腾出头部空间
    int end = psl->size - 1;
    while (end >= 0)
    {
      psl->a[end + 1] = psl->a[end];
      --end;
    }
    psl->a[0] = x;
    psl->size++;
    //SeqListInsert(psl, 0, x);
}
//顺序表头删
void SeqListPopFront(SeqList* psl)
{
    assert(psl);
    if (psl->size > 0)
    {
      //挪动数据覆盖删除
      int begin = 1;
      while (begin < psl->size)
      {
        psl->a[begin - 1] = psl->a[begin];
        ++begin;
      }
      --psl->size;
    }
}
// 在pos(指定位置）插入x
//void SeqListInsert(SeqList* psl, int pos, SLDataType x)    //解决整型提升形成的死循环,解决1
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
  // 暴力检查
  assert(psl);
  // 温和检查
  if (pos > psl->size)
  {
    printf("pos 越界：%d\n", pos);
    return;
    //exit(-1);  //直接终止程序，没必要
  }
  // 暴力检查
  //assert(pos <= psl->size);
  //检查后，根据需要是否增容
  SeqListCheckCapacity(psl);
  //解决整型提升形成的死循环,解决2
  //int end = psl->size-1;
  //while (end >=(int)pos)
  //{
  //  psl->a[end+1] = psl->a[end];
  //  --end;
  //}
  //解决整型提升形成的死循环,解决3
  size_t end = psl->size;
  while (end > pos)
  {
    psl->a[end] = psl->a[end - 1];
    --end;
  }
  psl->a[pos] = x;
  psl->size++;
}
// 删除pos(指定位置）的数据
void SeqListErase(SeqList* psl, size_t pos)
{
  assert(psl);
  assert(pos < psl->size);
  size_t begin = pos + 1;
  while (begin < psl->size)
  {
    psl->a[begin - 1] = psl->a[begin];
    ++begin;
  }
  psl->size--;
}
//按值查找
int SeqListFind(SeqList* psl, SLDataType x)
{
  assert(psl);
  for (int i = 0; i < psl->size; ++i)
  {
    if (psl->a[i] == x)
    {
      return i;
    }
  }
  return -1;
}
//顺序表修改
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
  assert(psl);
  assert(pos < psl->size);
  psl->a[pos] = x;
}

SeqList.h：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 要求：存储的数据从0开始，依次连续存储
// 静态的顺序表
// 问题：开小了，不够用。开大了，存在浪费。
//#define N 10000
//struct SeqList
//{
//  int a[N];
//  int size; // 记录存储了多少个数据
//};
typedef int SLDataType;
// 动态的顺序表
typedef struct SeqList
{
  SLDataType* a;
  int size;     // 存储数据个数
  int capacity; // 存储空间大小
}SL, SeqList;
//void SLInit(SeqList* psl);
//顺序表初始化
void SeqListInit(SeqList* psl);
//顺序表销毁
void SeqListDestroy(SeqList* psl);
//打印顺序表
void SeqListPrint(SeqList* psl);
//检查容量，降低冗余度
void SeqListCheckCapacity(SeqList* psl);
// 时间复杂度是O(1)
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
//尾删
void SeqListPopBack(SeqList* psl);
// 时间复杂度是O(N)
//头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//头删
void SeqListPopFront(SeqList* psl);
// 在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 删除pos位置的数据
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
//顺序表修改
void SeqListModify(SeqList* psl, size_t pos, SLDataType x);

版本2：

附用SeqListInsert、SeqListErase版

附用SeqListInsert、SeqListErase测试示例： 编辑

Test.c：

#include "SeqList.h"
//附用SeqListInsert、SeqListErase版测试
void TestSeqList7()
{
  SeqList s;
  SeqListInit(&s);
  //尾插
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPushBack(&s, 5);
    SeqListPushBack(&s, 6);
  SeqListPrint(&s);
  //头插
  SeqListPushFront(&s, -1);
  SeqListPushFront(&s, -2);
  SeqListPrint(&s);
  //头删
  SeqListPopFront(&s);
  SeqListPopFront(&s);
  SeqListPrint(&s);
  //尾删
  SeqListPopBack(&s);
  SeqListPopBack(&s);
  SeqListPrint(&s);
    //1.直接修改
  SeqListModify(&s, 3, 1000);
  SeqListPrint(&s);
  //2.按值查找后修改
  int pos = SeqListFind(&s, 6);//括号第二个数是确定的值，不是下标
  if (pos != -1)
  {
    SeqListModify(&s, pos, 90);
  }
  SeqListPrint(&s);
}
int main()
{
  SeqList s;
  SeqListInit(&s); //这里&是取地址
  TestSeqList7();
  return 0;
}

SeqList.c:

#include "SeqList.h"
//打印顺序表
void SeqListPrint(SeqList* psl)
{   //Print可以不传指针，因为它不需要修改结构体的内容，但结构体较大，传指针可以减少拷贝
  assert(psl);
  for (int i = 0; i < psl->size; ++i)
  {
    printf("%d ", psl->a[i]);
  }
  printf("\n");
}
//顺序表初始化
void SeqListInit(SeqList* psl)
{
  assert(psl);
  psl->a = NULL;
  psl->size = 0;
  psl->capacity = 0;
}
//顺序表销毁、释放内存
void SeqListDestroy(SeqList* psl)
{
  assert(psl);
  free(psl->a);
  psl->a = NULL;
  psl->capacity = psl->size = 0;
}
//检查容量，降低冗余度
void SeqListCheckCapacity(SeqList* psl)
{
  // ˣҪ
  if (psl->size == psl->capacity)
  {   //relloc扩容
    size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
    //因为最初是0，*2也是0.所以最初为0就给4个(4没有特定含义，只要不是太大就行），若不是0就 psl->capacity * 2（折中）*3或*4均可
    SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    else
    {
      psl->a = tmp;
      psl->capacity = newCapacity;
    }
  }
}
//顺序表尾插--附用SeqListInsert版
void SeqListPushBack(SeqList* psl, SLDataType x)
{
  assert(psl);
  SeqListInsert(psl, psl->size, x);
}
//顺序表尾删—附用SeqListErase版
void SeqListPopBack(SeqList* psl)
{
  assert(psl);
  SeqListErase(psl, psl->size - 1);
}
//顺序表头插--附用SeqListInsert版
void SeqListPushFront(SeqList* psl, SLDataType x)
{
  assert(psl);
  SeqListInsert(psl, 0, x);
}
//顺序表尾头删—附用SeqListErase版
void SeqListPopFront(SeqList* psl)
{
  assert(psl);
  SeqListErase(psl, 0);
}
// 在pos(指定位置）插入x
//void SeqListInsert(SeqList* psl, int pos, SLDataType x)    //解决整型提升形成的死循环,解决1
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
  // 暴力检查
  assert(psl);
  // 温和检查
  if (pos > psl->size)
  {
    printf("pos 越界：%d\n", pos);
    return;
    //exit(-1);  //直接终止程序，没必要
  }
  // 暴力检查
  //assert(pos <= psl->size);
  //检查后，根据需要是否增容
  SeqListCheckCapacity(psl);
  //解决整型提升形成的死循环,解决2
  //int end = psl->size-1;
  //while (end >=(int)pos)
  //{
  //  psl->a[end+1] = psl->a[end];
  //  --end;
  //}
  //解决整型提升形成的死循环,解决3
  size_t end = psl->size;
  while (end > pos)
  {
    psl->a[end] = psl->a[end - 1];
    --end;
  }
  psl->a[pos] = x;
  psl->size++;
}
// 删除pos(指定位置）的数据
void SeqListErase(SeqList* psl, size_t pos)
{
  assert(psl);
  assert(pos < psl->size);
  size_t begin = pos + 1;
  while (begin < psl->size)
  {
    psl->a[begin - 1] = psl->a[begin];
    ++begin;
  }
  psl->size--;
}
//按值查找
int SeqListFind(SeqList* psl, SLDataType x)
{
  assert(psl);
  for (int i = 0; i < psl->size; ++i)
  {
    if (psl->a[i] == x)
    {
      return i;
    }
  }
  return -1;
}
//顺序表修改
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
  assert(psl);
  assert(pos < psl->size);
  psl->a[pos] = x;
}

SeqList.h:

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 要求：存储的数据从0开始，依次连续存储
// 静态的顺序表
// 问题：开小了，不够用。开大了，存在浪费。
//#define N 10000
//struct SeqList
//{
//  int a[N];
//  int size; // 记录存储了多少个数据
//};
typedef int SLDataType;
// 动态的顺序表
typedef struct SeqList
{
  SLDataType* a;
  int size;     // 存储数据个数
  int capacity; // 存储空间大小
}SL, SeqList;
//void SLInit(SeqList* psl);
//顺序表初始化
void SeqListInit(SeqList* psl);
//顺序表销毁
void SeqListDestroy(SeqList* psl);
//打印顺序表
void SeqListPrint(SeqList* psl);
//检查容量，降低冗余度
void SeqListCheckCapacity(SeqList* psl);
// 时间复杂度是O(1)
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
//尾删
void SeqListPopBack(SeqList* psl);
// 时间复杂度是O(N)
//头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//头删
void SeqListPopFront(SeqList* psl);
// 在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 删除pos位置的数据
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
//顺序表修改
void SeqListModify(SeqList* psl, size_t pos, SLDataType x);

顺序表修改功能：

编辑顺序表按值查找功能：

编辑

顺序表功能实现（增删查改）《数据结构(C语言版)》

博文内容：

数据结构（C语言版）之顺序表及其功能实现（增删查改）

博文作者：

新晓·故知

注：

★博文转载请注明出处。

★博文仅供学习交流，禁止用于商业用途。

《数据结构(C语言版)》实战项目之顺序表（增删查改）功能实现：

问题导引：

实现步骤：

P2—＜顺序表＞《数据结构(C语言版)》

源码如下，欢迎复制测试指正！

版本1：

源代码：

Test.c：

SeqList.c：

SeqList.h：

版本2：

附用SeqListInsert、SeqListErase版

Test.c：

SeqList.c:

SeqList.h:

顺序表修改功能：

编辑顺序表按值查找功能：

后记：

●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

——By 作者：新晓·故知

热门文章

最新文章

相关课程

相关电子书

顺序表功能实现（增删查改）《数据结构(C语言版)》

博文内容：

数据结构（C语言版）之顺序表及其功能实现（增删查改）

博文作者：

新晓·故知

注：

★博文转载请注明出处。

★博文仅供学习交流，禁止用于商业用途。

《数据结构(C语言版)》实战项目之顺序表（增删查改）功能实现：

问题导引：

实现步骤：

P2—＜顺序表＞《数据结构(C语言版)》

源码如下，欢迎复制测试指正！

版本1：

源代码：

Test.c：

SeqList.c：

SeqList.h：

版本2：

附用SeqListInsert、SeqListErase版

Test.c：

SeqList.c:

SeqList.h:

顺序表修改功能：

编辑 顺序表按值查找功能：

后记：

●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

——By 作者：新晓·故知

热门文章

最新文章

相关课程

相关电子书

编辑顺序表按值查找功能：