锐客网

  1. 首页 > 睿知 > it技术 > >

王道考研|笔记&补充线性表之顺序表

IT知识线性表线性

赋料扬雄敌，诗看子建亲。这篇文章主要讲述王道考研|笔记&补充线性表之顺序表相关的知识，希望能为你提供帮助。
定义：线性表是具有相同数据类型的n个数据元素（int，float，struct...）的有限序列
特点：除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继顺序表；用顺序存储的方式实现线性表--（逻辑相邻的元素物理位置相邻）
定义结构

#include< stdio.h>
#define MaxSize 10
typedef struct
int data[MaxSize];
int length;
SqList;

基本操作
  • 初始化（考虑数据元素里所有数据项）
void InitList(SqList & L)
for (int i = 0; i < MaxSize; i++)
L.data[i] = 0;
L.length = 0;

/*因为数据项里有length记录了存放了多少数据，操作的一般是存放的数据，而非整个开辟的空间，而存放的时候即给data[i]赋值了，因此对data[i]的初始化其实是可以省略掉的*/

void InitList(SqList & L)
L.length = 0;

  • 插入（插入位置之后的元素i~n-1都得后移一位，注意先移动最后的n-1到n，即从后往前移动需要后移的数据元素，否则会发生数据元素覆盖）（提高代码的健壮性：考虑空间不足时无法插入或者空间足够但插入位置不合法）
//在第i个位置（次序）上插入元素e
bool ListInsert(SqList & L, int i, int e)
if (L.length > = MaxSize) //存储空间已满
return false;
if (i< 1 || i> L.length + 1) //插入位置不合理
return false;
for (int j = L.length; j > = i; j--)
L.data[j] = L.data[j - 1]; //后移
L.data[i - 1] = e; //次序i,即下标i-1
L.length++;
return true;

  • 删除（删除位置之后的元素i~n-1都得前移一位，直接从前往后依次前移覆盖掉要删除的元素即可）
//将第i位元素删除，并获取被删除的这个元素
bool ListDelete(SqList & L, int i, int & e)
if (i< 1 || i> L.length)
return false;
e = L.data[i - 1];
for (int j = i; j < L.length; j++)
L.data[j - 1] = L.data[j]; //前移

L.length--;
return true;

  • 查找
  • 因为存储的是相同数据类型的元素，所有每个元素的大小是相同的，c语言提供sizeof()来计算一个数据元素的大小。**假设第一个元素的地址是loc，那么第n个元素的地址是loc+(n-1)*sizeof(ElemType)**
【王道考研|笔记&补充线性表之顺序表】

  • 按位查找：
//查找-按位查找第i个元素（次序）
int GetElem(SqList L, int i)
return L.data[i - 1];

  • 按值查找：
//查找-按值查找元素值为e的第一个出现的元素，返回其次序
int LocateElem(SqList L, int e)
for (int i = 0; i < L.length; i++)
if (L.data[i] == e)
return i + 1; //注意要求是返回次序

return -1; //查找失败，该元素不存在

完整代码
//构造数据元素
#define MaxSize 10
typedef struct
int data[MaxSize];
int length;
SqList;
//数据元素初始化
void InitList(SqList & L)
for (int i = 0; i < MaxSize; i++)
L.data[i] = 0;
L.length = 0;

//在第i个位置（次序）上插入元素e
bool ListInsert(SqList & L, int i, int e)
if (L.length > = MaxSize) //存储空间已满
return false;
if (i< 1 || i> L.length + 1) //插入位置不合理
return false;
for (int j = L.length; j > = i; j--)
L.data[j] = L.data[j - 1]; //后移
L.data[i - 1] = e; //次序i,即下标i-1
L.length++;
return true;

//将第i位元素删除，并获取被删除的这个元素
bool ListDelete(SqList & L, int i, int & e)
if (i< 1 || i> L.length)
return

    推荐阅读


    上一篇：K8S关于pod资源监控

    下一篇：python 包之 blinker 信号库教程