外卖网站建设价钱,建设工程信息化平台,ui设计培训学校哪里好,宁波百度seo代理目录
1.什么是顺序表 顺序表的优势和缺点
顺序表预备知识
顺序表的代码实现
顺序表头部插入
顺序表的销毁
顺序表的头删
顺序表的尾删
顺序表的尾插
顺序表的任意位置插入
顺序表的查找
顺序表的打印 1.什么是顺序表
这篇文章我们来讲一下基础数据结构的顺序表相信大家在学习C语言的时候接触过数组这种数据结构但是它又跟顺序表又有什么关系呢 我们知道数组的内存是连续的一个下标对应着一片内存而且支持随机访问。这就叫做顺序结构而数组就是这种结构。果不其然我们的顺序表也是这种结构但是顺序表就是数组吗答案是是的只是其描述角度不同。
线性表是数据结构中的逻辑结构。线性表采用顺序存储的方式存储就称之为顺序表。数组是顺序表在实际编程中的具体实现方式之一。顺序表的优势和缺点
前面介绍完了顺序表的定义我们说说它的优势和不足的地方
我们知道顺序表的优势如下 支持随机访问查找速度O(1) 空间利用率高 那缺点就显而易见了
增加和删除的速度较慢如果要在中间插入一个元素则需要挪动后面的所有的元素造成多余的时间开销删除同理。 时间复杂度是On, 如果不经常删除和改动元素则不推荐使用顺序表这种顺序结构而用链表则效率更高。 顺序表的长度需要提前指定长度受到限制。 有同学说我可以进行动态内存分配啊这样不就行了其实动态内存分配是解决了长度受限的问题但存在一个潜在的问题顺序表扩容我们一般一次就扩充两倍但是用的可能没有这么多那多出来的内存空间不就浪费了吗这是我们说的多余的内存开销问题。
顺序表预备知识
动态内存分配(malloc)
结构体(struct)
顺序表的代码实现
以下为所有的代码实现
函数接口
void Sequential_table_deletion(SL*ps,int pos);
void Sequential_table_lookup(SL*ps,int pos,int x); //顺序表中插入数据
int Seqlistwo(SL*ps,int n);//顺序表中查找元素
void SeqlistPopBack(SL*ps,int n);//尾插函数
void Array_expansion(SL*ps); //扩容
void Seqlistfis(SL*ps);//(3) //头删
void Seqlistpuch(SL*ps,int n); // 头插法
void Array_expansion(SL*ps) //扩容
结构体定义
typedef struct Seqlist
{int *a;int size; //表示数组中存储了多少个数据int ciap;// 数组能实际存储的容量大小
}SL;
顺序表头部插入
顺序表的头部插入就是先把顺序表的第一个元素空出来然后把所有的数据往后挪动达到头插的目的
void Seqlistpuch(SL*ps,int n) // 头插法
{Array_expansion(ps); //检查增容int end ps-size-1;while(end0){ps-a[end1]ps-a[end];end--;} ps-a[0] n;ps-size;
}
顺序表的销毁
顺序表的销毁就简单了只要当前表不为空指针一直释放就可以了
void SeqListDestroy(SeqList* ps)
{//断言assert(ps);//释放空间if (ps-a ! NULL){free(ps-a);ps-a NULL;ps-capacity 0;ps-size 0;}}
顺序表的头插
在使用头插函数前我们需要检查当前顺序表的空间是否足够我们使用然后再对顺序表进行操作当然我们传进来的参数不能为空指针我们把长度定义为end,让它后一个数等于前一个数同时长度-1.我们的头插就完成了。
void SeqListPushFront(SeqList*ps,SLDateType x)
{断言//assert(ps);检查扩容//SeqListCheck(ps);//int end ps-size-1;挪动数据//while (end 0)//{// ps-a[end 1] ps-a[end];// end--;//}在头部插入数据//ps-a[0] x;//ps-size;SeqListInsert(ps, 0, x);
}
顺序表的尾删
当前下标大于0 长度-1
void SeqListPopBack(SeqList* ps)
{//断言assert(ps-size0);ps-size--;
} 顺序表的尾插
所有元素向前挪动一个位置长度1
void SeqListPushBack(SeqList* ps, SLDateType x)
{//断言assert(ps);//检查扩容SeqListCheck(ps);//插入数据ps-a[ps-size] x;ps-size;
}
顺序表的任意位置插入 顺序表的任意插入这个比头部或尾部插入有点麻烦不过实现起来也不难。我们先要断言一下要插入的下标的有效性。
void removeElem(STL*ps,substitute pos,substitute elem)//在指定位置插入元素
{ assert(pos0posps-size);int i 0;for(i 0;ips-size;i){ps-a[i]ps-a[i-1];}ps-a[pos]elem;ps-size;
}
顺序表的查找
顺序表的查找和数组是一样的如果当前顺序表的元素等于要查找的值则立即返回该数据的下标。否则返回空。
int SeqListFind(SeqList* ps, SLDateType x,int begain)
{assert(ps);int i 0;//遍历数组进行查找for (i begain; i ps-size; i){if (ps-a[i] x){return i;}}//查找不到返回-1return -1;
}
顺序表的打印 void Sequential_table_printing(STL*ps)
{ int i 0;for(i 0;ips-size;i)//打印顺序表的元素{printf(%d ,ps-a[i]);}
} 顺序表的打印和数组是一样的通过访问其下标。
