赞
踩
线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串。
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为:
1. 静态顺序表:使用定长数组存储元素。
2. 动态顺序表:使用动态开辟的数组存储。
基本操作及其实现:
- typedef int SLDataType; // 顺序表的动态存储
-
- typedef struct SeqList
-
- {
-
- SLDataType* array; // 指向动态开辟的数组
-
- size_t size ; // 有效数据个数
-
- size_t capicity ; // 容量空间的大小
-
- }SeqList;
//1. 顺序表初始化
void SeqListInit(SeqList* psl, size_t capacity);
- // 对顺序表进行初始化
- void SeqListInit(SeqList* ps, int initCapacity)
- {
- assert(ps);
- initCapacity = initCapacity <= 0 ? 3 : initCapacity;
- ps->array = (int*)malloc(initCapacity*sizeof(DataType));
- if (NULL == ps->array)
- {
- assert(0);
- return;
- }
-
- ps->capacity = initCapacity;
- ps->size = 0;
- }
// 2.检查空间,如果满了,进行增容
void CheckCapacity(SeqList* psl);
- void CheckCapacity(SeqList* ps)
- {
- assert(ps);
- if (ps->size == ps->capacity)
- {
- // 1. 计算新空间的大小
- int newCapacity = ps->capacity * 2;
-
- // 2. 扩容
- int* temp = (int*)malloc(sizeof(DataType)*newCapacity);
- if (NULL == temp)
- {
- assert(0);
- return;
- }
-
- memcpy(temp, ps->array, ps->size*sizeof(DataType));
- free(ps->array);
- ps->array = temp;
- ps->capacity = newCapacity;
-
-
- //或用realloc函数
- /*
- ps->array = (int*)realloc(ps->array, sizeof(DataType)*newCapacity);
- if (NULL == ps->array)
- {
- assert(0);
- return;
- }
- ps->capacity = newCapacity;
- */
- }
- }
// 3.顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
- void SeqListPushBack(SeqList* ps, DataType data)
- {
- assert(ps);
-
- // 0. 必须要保证顺序表中有足够的空间才可以插入,否则就需要扩容 (第二个函数)
- CheckCapacity(ps);
-
- // 1. 将data插入到最后一个元素的下一个位置---size的位置
- ps->array[ps->size] = data;
- ps->size++;
- }
// 4.顺序表尾删
void SeqListPopBack(SeqList* psl);
- void SeqListPopBack(SeqList* ps)
- {
- if (SeqListEmpty(ps))
- {
- return;
- }
-
- ps->size--;
- }
// 5.顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
- void SeqListPushFront(SeqList* ps, DataType data)
- {
- assert(ps);
-
- // 0. 检测空间是否足够 (第二个函数)
- CheckCapacity(ps);
-
- // 1. 将顺序表中所有的元素整体往后搬移一个位置(注意:从后往前来搬移)
- for (int pos = ps->size - 1; pos >= 0; --pos)
- {
- ps->array[pos+1] = ps->array[pos];
- }
-
- // 2. 将data插入到顺序表的0号位置
- ps->array[0] = data;
-
- // 3. 有效元素个数增加一个
- ps->size++;
- }
// 6.顺序表头删
void SeqListPopFront(SeqList* psl);
- void SeqListPopFront(SeqList* ps)
- {
- if (SeqListEmpty(ps))
- {
- return;
- }
-
- for (int pos = 1; pos < ps->size; pos++)
- {
- ps->array[pos-1] = ps->array[pos];
- }
-
- ps->size--;
- }
// 7.顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
- int SeqListFind(SeqList* ps, DataType data)
- {
- assert(ps);
- for (int i = 0; i < ps->size; ++i)
- {
- if (ps->array[i] == data)
- return i;
- }
-
- return -1;
- }
// 8.顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
- void SeqListInsert(SeqList* ps, int pos, DataType data)
- {
- assert(ps);
- if (pos < 0 || pos > ps->size)
- {
- printf("pos位置非法!!!");
- return;
- }
-
- CheckCapacity(ps);
-
- for (int i = ps->size - 1; i >= pos; i--)
- {
- ps->array[i+1] = ps->array[i];
- }
-
- ps->array[pos] = data;
-
- ps->size++;
- }
//9. 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
- void SeqListErase(SeqList* ps, int pos)
- {
- assert(ps);
- if (pos < 0 || pos >= ps->size)
- {
- printf("pos位置非法!!!");
- return;
- }
-
- for (int i = pos + 1; i < ps->size; i++)
- {
- ps->array[i-1] = ps->array[i];
- }
-
- ps->size--;
- }
// 10.顺序表销毁
void SeqListDestory(SeqList* psl);
- void SeqListDestory(SeqList* ps)
- {
- assert(ps);
- if (ps->array)
- {
- free(ps->array);
- ps->array = NULL;
- ps->capacity = 0;
- ps->size = 0;
- }
- }
// 11.顺序表打印
void SeqListPrint(SeqList* psl);
- void PrintSeqList(SeqList* ps)
- {
- assert(ps);
- for (int i = 0; i < ps->size; ++i)
- {
- printf("%d ", ps->array[i]);
- }
- printf("\n");
- }
// 12.检测顺序表是否为空
int SeqListEmpty(SeqList* ps)
- int SeqListEmpty(SeqList* ps)
- {
- return 0 == ps->size;
- }
// 13.获取顺序表中有效元素个数
int SeqListSize(SeqList* ps)
- int SeqListSize(SeqList* ps)
- {
- return ps->size;
- }
// 14.获取顺序表的容量
int SeqListCapacity(SeqList* ps)
- int SeqListCapacity(SeqList* ps)
- {
- return ps->capacity;
- }
顺序表存在的一些问题:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。