长春哪里有做网站的,制作网站推广码,网页制作费用,电子商务网站建设规划论文顺序表 1. 线性表2. 顺序表2.1 静态顺序表2.2 动态顺序表2.2.1 动态数据表初始化和销毁2.2.2 动态数据表的尾插尾删2.2.3 动态数据表的头插头删2.2.4 动态数据表的中间部分插入删除2.2.5 动态数据表的查询数据位置 3. 总结 1. 线性表
线性表#xff08;linear list#xff0… 顺序表 1. 线性表2. 顺序表2.1 静态顺序表2.2 动态顺序表2.2.1 动态数据表初始化和销毁2.2.2 动态数据表的尾插尾删2.2.3 动态数据表的头插头删2.2.4 动态数据表的中间部分插入删除2.2.5 动态数据表的查询数据位置 3. 总结 1. 线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。
2. 顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表严格来说就是一个数组 要求数据连续存储 顺序表一般分为静态顺序表和动态顺序表。
2.1 静态顺序表
静态顺序表使用定长数组存储元素。
由于使用时无法增加内部容量所以静态顺序表只适用于确定知道需要存多少数据的场景。
静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小。
2.2 动态顺序表
动态顺序表使用动态开辟的数组存储。
typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{SLDataType* array; // 指向动态开辟的数组size_t size ; // 有效数据个数size_t capicity ; // 容量空间的大小
}SeqList;作为一个可以进行修改的顺序表所以动态顺序表必须要满足以下的条件 1.顺序表 初始化 2.顺序表 增加数据 3.顺序表 删除数据 4.顺序表 查找数据 5.顺序表 修改数据 6.顺序表 插入数据 7.顺序表 销毁 2.2.1 动态数据表初始化和销毁
//初始化
void SeqListInit(SeqList* ps)
{ps-a NULL;ps-size 0;ps-capacity 0;
}
//销毁
void SeqListDestroy(SeqList* ps)
{if(ps-a ! NULL){free(ps-a);ps-a NULL;ps-size ps-capacity 0;}
}2.2.2 动态数据表的尾插尾删
//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{//检查容量如果不够扩容if(ps-size ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;SLDataType* tmp (SLDataType*)realloc(ps-a, newCapacity * sizeof(SLDataType));//判断扩容是否成功if(tmp NULL){perror(realloc fail!);exit(-1);}ps - a tmp;ps-capacity newCapacity;}//将数据插入到顺序表中ps-a[size] x;ps-size;
}
//顺序表尾删
void SeqListPopBack(SeqList* ps)
{//暴力检查assert(ps-size 0);ps-size--;
}
2.2.3 动态数据表的头插头删
// 检查空间如果满了进行增容
void CheckCapacity(SeqList* ps)
{if(ps-size ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity*2;SLDataType* tmp (SLDataType*)realloc(ps-a, newCapacity * sizeof(SLDataType));if(tmp NULL){perror(realloc fail!);exit(-1);}ps-a tmp;ps-capacity newCapacity;}
}// 顺序表头插
void SeqListPushFront(SeqList* ps, SLDataType x)
{ assert(ps);//检查顺序表是否为空为空直接报错CheakCapacity(ps);//检查是否需要扩容 //由于多个地方都需要扩容为了避免重复代码选择复用代码//将前一个数据放到后面的空格中int end ps-size - 1; while(end 0){ps-a[end 1] ps-a[end]; --end;}ps-a[0] x;ps-size;
}
// 顺序表头删
void SeqListPopFront(SeqList* ps)
{assert(ps);assert(ps-size 0);//直接移动数据进行覆盖int begin 0;while(begin ps- size - 1){ps-a[begin] ps-a[begin1];begin;}ps-size--;
}写到这里仔细思考的话会发现头插的时间复杂度是O(N)尾插的时间复杂度是O(1)因此顺序表的数据插入一般会使用尾插。
2.2.4 动态数据表的中间部分插入删除
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x)
{assert(ps);assert(pos 0 );//相等就是头插尾插assert(pos ps-size);//检查扩容CheckCapacity(ps);//移动int end ps-size -1;while(end pos)//pos位置的数据也要移动{ps-a[end 1] ps-a[end]; end--;}ps-a[pos] x;ps-size;
}
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos)
{assert(ps);assert(pos 0);assert(pos ps-size);int begin pos1;while(begin ps-size){ps-a[begin] pos-a[begin - 1];begin;}ps-size--;
}2.2.5 动态数据表的查询数据位置
// 顺序表查找
int SeqListFind(SeqList* ps, SLDataType x)
{assert(ps);for(int i0;i ps-size; i){if(ps-a[i] x){return i;}}return -1;
}
3. 总结
首先顺序表是连续的存储空间不能断开。静态顺序表用的很少几乎都是动态顺序表。默认说的顺序表是动态顺序表。其次顺序表提供增删查改但是相对来说顺序表使用尾插最好时间复杂度最低。第三顺序表一旦提供在中间的增删后头插尾插和头删尾删都可以用中间的增删来进行复用。
