前言

线性表的含义：

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使

用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，

线性表在物理上存储时，通常以数组和链式结构的形式存储。

一、顺序表

1.1顺序表的概念

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

1.2顺序表的分类

静态的顺序表：使用定长数组存储元素

typedef int SLDatatype;
#define N 10
typedef int SLDatatype;
struct SeqList
{
  SLDatatype a[N];
  int size;
};

动态的顺序表：使用动态开辟的数组存储

typedef int SLDatatype;
typedef struct SeqList
{
  SLDatatype* a;
  int size;   //存储的有效数据个数
  int capacity; //容量
}SL;

1.3、顺序表的接口定义

1、顺序表的初始化

void SLInit(SL* psl)
{
  psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
  if (psl->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  psl->capacity = 4;
  psl->size = 0;
}

首先我们在内存中，动态开辟一块空间，并且把初始的存储容量设置为4个，psl->size其实就是下标的意思啦！

2、顺序表的销毁

void SLDestroy(SL* psl)
{
  free(psl->a);
  psl->a = NULL;
  psl->capacity = psl->size = 0;
}

首先开辟在堆上的数据，我们采用c语言中的free语句来释放，并且再让capacity和size都变为0，这样就算销毁成功啦！

3、顺序表的打印

void SLPrint(SL* psl)
{
  int i = 0;
  for (i = 0; i < psl->size; i++)
  {
    printf("%d ", psl->a[i]);
  }
  printf("\n");
}

首先顺序表的原理其实跟数组挺像的，其是物理地址连续的存储单元依次存储数据元素，所以在打印的时候我们可以想象数组的遍历，psl->size就是数组的元素个数，我们只需要利用一个for循环即可打印出来。

4、数组中的动态增容

void SLCheckCapacity(SL* psl)
{
  assert(psl);
  if (psl->capacity == psl->size)
  {
    SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * 2 * psl->capacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    psl->a = tmp;
    psl->capacity *= 2;
  }
}

首先，当元素个数与数组大小相同的时候，我们可以给psl->a realloc动态增容，首先realloc有两个参数，一个是要增容的地址处，一个是增容大小。我们增容完毕之后在把增容的值赋给原来的psl->a这块地址处，并且在让数组大小变成原来的两倍。

5、顺序表的尾插

void SLPushBack(SL* psl, SLDatatype x)
{
  SLCheckCapacity(psl);//检查是否需要扩容
  psl->a[psl->size] = x;
  psl->size++;
}

从图中我们可以看出，顺序表的尾插只需要找到psl->size中处于何位置时，在该位置上，我们把相应的数插入进去即可

6、顺序表的头插

void SLPushFront(SL* psl, SLDatatype x)
{
  assert(psl->size);
  SLCheckCapacity(psl);
  int end = psl->size - 1;
  while (end >= 0)
  {
    psl->a[end + 1] = psl->a[end];
    end--;
  }
  psl->a[0] = x;
  psl->size++;
}

首先，头插如果从前面开始往后移的话，就会覆盖后面的数，那么我们应该怎么办呢？我们应该从后向前挪动，这样就不会影响到各个位置的数了。我们先找到最后一个数的下标，然后从后往前挪动，就如下图所示，此时最前头的一个位置就是空着了，我们把想插入的数插入进去即可，记住我们数据加一之后，我们size也会随之加一，所以最后要psl->size++噢！

7、顺序表的尾删

void SLPopBack(SL* psl)
{
  assert(psl->size > 0);
  psl->size--;
}

尾删的话，我们直接暴力一点直接删除psl->size就行啦！

8、顺序表的头删

void SLPopFront(SL* psl)
{
  assert(psl->size > 0);
  int start = 0;
  while (start < psl->size - 1)
  {
    psl->a[start] = psl->a[start + 1];
    start++;
  }
  psl->size--;
}

头删的话我们就从头开始往前挪动，最后记得我们已经少了一个数据了，记得psl->size–噢！

9、顺序表的插入

void SLInsert(SL* psl, int pos, SLDatatype x)
{
  assert(pos >= 0 && pos <= psl->size);
  SLCheckCapacity(psl);
  int cur = psl->size - 1;
  while (pos <= cur)
  {
    psl->a[cur + 1] = psl->a[cur];
    cur--;
  }
  psl->a[pos] = x;
  psl->size++;
}

10、顺序表的删除

void SLErase(SL* psl, int  pos)
{
  assert(pos >= 0 && pos < psl->size);
  int end = pos + 1;
  while (pos <= psl->size)
  {
    psl->a[pos] = psl->a[pos + 1];
    pos++;
  }
  psl->size--;
}

11、顺序表的查找

int SLFind(SL* psl, SLDatatype x)
{
  assert(psl);
  for (int i = 0; i < psl->size; i++)
  {
    if (psl->a[i] == x)
      return i;
  }
  return -1;
}

12、顺序表的修改

void Modify(SL* psl, int pos, SLDatatype x)
{
  assert(psl);
  psl->a[pos] = x;
}

二.顺序表的完整实现

2.1代码的完成实现

seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"
//void SLInit(SL* psl)
//{
//  psl->a = NULL;
//  psl->capacity = 0;
//  psl->size = 0;
//}
void SLInit(SL* psl)
{
  psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
  if (psl->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  psl->capacity = 4;
  psl->size = 0;
}
void SLDestroy(SL* psl)
{
  free(psl->a);
  psl->a = NULL;
  psl->capacity = psl->size = 0;
}
void SLCheckCapacity(SL* psl)
{
  assert(psl);
  if (psl->capacity == psl->size)
  {
    SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * 2 * psl->capacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    psl->a = tmp;
    psl->capacity *= 2;
  }
}
void SLPrint(SL* psl)
{
  int i = 0;
  for (i = 0; i < psl->size; i++)
  {
    printf("%d ", psl->a[i]);
  }
  printf("\n");
}
void SLPushBack(SL* psl, SLDatatype x)
{
  SLCheckCapacity(psl);
  psl->a[psl->size] = x;
  psl->size++;
}
void SLPushFront(SL* psl, SLDatatype x)
{
  assert(psl->size);
  SLCheckCapacity(psl);
  int end = psl->size - 1;
  while (end >= 0)
  {
    psl->a[end + 1] = psl->a[end];
    end--;
  }
  psl->a[0] = x;
  psl->size++;
}
void SLPopBack(SL* psl)
{
  assert(psl->size > 0);
  psl->size--;
}
void SLPopFront(SL* psl)
{
  assert(psl->size > 0);
  int start = 0;
  while (start < psl->size - 1)
  {
    psl->a[start] = psl->a[start + 1];
    start++;
  }
  psl->size--;
}
void SLInsert(SL* psl, int pos, SLDatatype x)
{
  assert(pos >= 0 && pos <= psl->size);
  SLCheckCapacity(psl);
  int cur = psl->size - 1;
  while (pos <= cur)
  {
    psl->a[cur + 1] = psl->a[cur];
    cur--;
  }
  psl->a[pos] = x;
  psl->size++;
}
void SLErase(SL* psl, int  pos)
{
  assert(pos >= 0 && pos < psl->size);
  int end = pos + 1;
  while (pos <= psl->size)
  {
    psl->a[pos] = psl->a[pos + 1];
    pos++;
  }
  psl->size--;
}
int SLFind(SL* psl, SLDatatype x)
{
  assert(psl);
  for (int i = 0; i < psl->size; i++)
  {
    if (psl->a[i] == x)
      return i;
  }
  return -1;
}
void Modify(SL* psl, int pos, SLDatatype x)
{
  assert(psl);
  psl->a[pos] = x;
}

seqlist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//#define N 10
//typedef int SLDatatype;
//struct SeqList
//{
//  SLDatatype a[N];
//  int size;
//};
typedef int SLDatatype;
typedef struct SeqList
{
  SLDatatype* a;
  int size;   //存储的有效数据个数
  int capacity; //容量
}SL;
void SLInit(SL* psl);
void SLDestroy(SL* psl);
void SLPrint(SL* psl);
void SLPushBack(SL* psl, SLDatatype x);
void SLPushFront(SL* psl, SLDatatype x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);
void SLInsert(SL* psl, int pos, SLDatatype x);
void SLErase(SL* psl, int  pos);
int SLFind(SL* psl, SLDatatype x);
void Modify(SL * psl, int pos, SLDatatype x);

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//#define INT_PTR int*
//typedef int* int_ptr;
//
//#define N 4
//#define Y(n) ((N+2)*n) ((6) * 5 + 1)
//
//INT_PTR a, b;
//int_ptr c, d;
//int main()
//{
//  int z = 2 * (N + Y(5 + 1));
//  return 0;
//}
//
//#include<stddef.h>
struct S
{
  int a;
  char c;
  double d;
};
#define OFFSETOF(type,name)   (size_t)&(((type*)0)->name) 
int main()
{
  struct S s;
  printf("%d\n", OFFSETOF(struct S, a));
  printf("%d\n", OFFSETOF(struct S, c));
  printf("%d\n", OFFSETOF(struct S, d));
  return 0;
}
//
#define SWAP_BIT(x)  (x = (((x & 0x55555555) << 1) + ((x & 0xaaaaaaaa) >> 1)))
int main()
{
  int a = 5;
  SWAP_BIT(a);
  printf("%d", a);
  return 0;
}
//
//void Func1()
//{
//  int a = 0;
//  printf("%p\n", &a);
//}
//
//void Func2()
//{
//  int b = 0;
//  printf("%p\n", &b);
//}
//
//int main()
//{
//  Func1();
//  Func2();
//
//
//  return 0;
//}
#include"Seqlist.h"
void test1()
{
  SL s;
  SLInit(&s);
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPrint(&s);
  SLPushFront(&s, 5);
  SLPushFront(&s, 4);
  SLPushFront(&s, 3);
  SLPushFront(&s, 2);
  SLPrint(&s);
  SLDestroy(&s);
}
void test2()
{
  SL s;
  SLInit(&s);
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPrint(&s);
  SLInsert(&s, 3, 6);
  SLInsert(&s, 2, 4);
  SLPrint(&s);
  SLErase(&s, 2);
  SLPrint(&s);
  SLDestroy(&s);
}
void test3()
{
  SL s;
  SLInit(&s);
  SLPushBack(&s, 1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  /*int pos = SLFind(&s, 2);
  printf("%d\n", pos);*/
  Modify(&s, 1, 5);
  SLPrint(&s);
  SLDestroy(&s);
}
int main()
{
  test3();
  return 0;
}

总结

本次的顺序表实现就到此为止啦，这是刚开始的分享哦！请大家持续关注我！

初阶数据结构之顺序表的增删查改（二）

前言

一、顺序表

1.1顺序表的概念

1.2顺序表的分类

1.3、顺序表的接口定义

二.顺序表的完整实现

2.1代码的完成实现

总结

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

初阶数据结构之顺序表的增删查改（二）

前言

一、顺序表

1.1顺序表的概念

1.2顺序表的分类

1.3、顺序表的接口定义

二.顺序表的完整实现

2.1代码的完成实现

总结

热门文章

最新文章

相关课程

相关电子书