数据结构:顺序表-尧图网站建设

一.数据结构的定义:

数据结构是计算机存储,组织数据的方式

二.顺序表的概念和结构:

1.线性表

线性表是n个具有相同特性的数据元素的有限序列

线性表在逻辑上是线性结构,但是在物理结构上不一定是连续的,线性表在物理上存储的时候,通常以数组和链式结构的形式存储

2.顺序表的分类

顺序表的逻辑结构是线性的,物理结构是连续的

顺序表的底层结构是数组,对数组的封装,实现了对常用的增删改查等接口

(1)静态顺序表

使用定长数组存储元素

结构体包括申请空间的大小和实际有效空间的大小(实际存储了数据的空间)

#define N 10
typedef int SLDateType;
struct Seqlist
{SLDateType a[N];//实际申请空间int size;//有效空间
};

缺陷:空间给少了不够用,导致数据丢失,给多了会造成空间浪费

(2)动态顺序表

typedef int SLDateType;
typedef struct SeqList
{SLDateType* arr;//存储数据的底层结构int capacity;//记录顺序表的空间大小int size;//记录顺序表当前有效的数据个数
}SL;//使用typedef重命名结构体可以方便使用

3.动态顺序表的实现

typedef int SLDateType;
typedef struct SeqList
{SLDateType* arr;int capacity;int size;
}SL;

(1)顺序表初始化:

void SLInit(SL *sl)
{sl->arr = NULL;sl->size = sl->capacity = 0;
}

(2)顺序表尾部插入:

void SLOPushBack(SL *sl,SLDateType x)
{if(sl == NULL)return;//空间不够,扩容SLCheckCapacity(sl);//空间足够,直接插入sl->arr[sl->size] = x;sl->size++;}

(3)顺序表扩容:

扩容的方法:1.一次扩充一个空间,防止造成空间的浪费
2.一次扩容固定大小的空间

3.成倍数增加(扩容效率最高)

void SLCheckCapacity(SL *sl)
{if(sl->size == sl->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps ->capacity;SLDateType *tmp = (SLDateType *)realloc(ps->arr,newCapacity*sizeof(SLDateType));if(tmp == NULL){perror("realloc fail");exit(1);//扩容失败直接中断程序}//扩容成功ps->arr = tmp;ps->capacity = newCapacity;}
}

(4)打印顺序表

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

(5)顺序表头部插入

如果直接经数据放在头部,则原本的头部数据会丢失,因此需要将数据集体后移

为防止数据丢失,因该采取从尾部开始后移的策略

void SLOPushFront(SL *sl,SLDateType X)
{if(sl == NULL)return;//空间不够,扩容SLCheckCapacity(sl);//空间足够,旧数据后移一位for(int i = sl->size;i > 0;i--){sl->arr[i] = ps->arr[i - 1];}sl->arr[0] = x;sl->size++;
}

(6)顺序表尾部删除

void SLPopBack(SL *sl)
{//顺序表为空if(ps == 0)return;if(ps->size == 0)return;//顺序表不为空ps->size--;}

注意:因为size是指有效空间,因此只要令size--,就可以实现尾部的删除,位于size外的数据无法被访问

(7)顺序表头部删除

void SLPopFront(SL *sl)
{//顺序表为空if(ps == 0)return;if(ps->size == 0)return;//顺序表不为空for(int i = 0;i < sl->size - 1;i++)sl->a[i] = sl->a[i+1];sl->size--;
}

(8)任意位置插入数据

void SLInsert(SL *sl,int pos,SLDateType x)
{if(sl == NULL)return;if(pos < 0 || pos > sl->size)return;SLCheckCapacity(sl);//pos及以后的数据后移一位,pos空出for(int i = sl->size;i > pos;i--){sl->arr[i] = sl->arr[i - 1];}sl->arr[pos] = x;ps->size++;
}

(9)任意位置删除数据

void SLDestory(SL *sl,int pos)
{//判断是否为空if(sl == NULL)return;if(pos < 0 || pos < sl->size)return;//向前移for(int i = pos+1;i < sl->size - 1;i++){sl->arr[i] = sl->arr[i + 1];}sl->size--;
}

(10)在顺序表中查找

int SLFind(SL *sl,SLDateType x)
{if(sl == NULL)return;for(int i = 0; i < sl->size,i++){if(sl->arr[i] == x)return i;}return -1;//表示没有找到
}

(10)顺序表的销毁

void SLDestory(SL *sl)
{if(sl == NULL)return;if(sl->arr != NULL)free(sl->arr);sl->arr = NULL;sl->size = sl->capacity = 0;
}

资讯详情

数据结构:顺序表