顺序表 订阅
顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系,采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。 [1] 展开全文
顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系,采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。 [1]
信息
结    构
存储结构
外文名
Contiguous List
中文名
顺序表
形    式
数组
顺序表简介
将表中元素一个接一个的存入一组连续的存储单元中,这种存储结构是顺序结构。采用顺序存储结构的线性表简称为“ 顺序表”。顺序表的存储特点是:只要确定了起始位置,表中任一元素的地址都通过下列公式得到:LOC(ai)=LOC(a1)+(i-1)*L  1≤i≤n 其中,L是元素占用存储单元的长度。顺序表的结构定义:#define maxlen 50 //定义顺序表中元素个数最多有几个 typedef struct{elementtype data[maxlen]; //elementtype是元素的类型 依具体情况而定int listlen; //便于时刻了解顺序表里元素的个数}seqlist; //顺序表的名称 不妨为seqlist声明顺序表类型变量:seqlist L,L1;如顺序表的每个结点占用len个内存单元,用location (ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系:location (ki+1) = location (ki) +lenlocation (ki) = location(k1) + (i-1)len存储结构要体现数据的逻辑结构,顺序表的存储结构中,内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。 [2] 
收起全文
精华内容
下载资源
问答
  • 顺序表
    千次阅读
    2021-11-15 16:02:21

    c++实现顺序表中的基本操作:

    1、顺序表的初始化
    2、顺序表的创建
    3、顺序表的插入
    4、顺序表的删除
    5、顺序表的查找
    6、顺序表的取值
    7、顺序表的清空
    8、顺序表的长度
    9、顺序表的判空
    10、顺序表的打印

    /*
    Project: sequence_list(数据结构-顺序表)
    Date: 2021/11/15
    InitList(SqList &L) 参数:顺序表L 功能:初始化 时间复杂度:O(1)
    CreateList(SqList &L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度为n的顺序表 时间复杂度:O(n)
    InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能:位置i处插入元素e 时间复杂度:O(n)
    DeleteList(SqList &L,int i) 参数:顺序表L,位置i 功能:删除位置i处元素 时间复杂度:O(n)
    LocateDate(SqList L,ElemType e) 参数:顺序表L,元素e 功能:返回第一个等于e的元素的位置 时间复杂度:O(n)
    GetData(SqList L, int i, ElemType &e) 参数:顺序表L,位置i,元素e 功能:取得i处的元素e 时间复杂度:O(1)
    ClearList(SqList &L) 参数:顺序表L 功能:清空顺序表
    GetLength(SqList L) 参数:顺序表L 功能:求顺序表的长度
    IsEmpty(SqList L) 参数:顺序表L 功能:判断顺序表是否为空
    PrintList(SqList L) 参数:顺序表L 功能:遍历并输出顺序表
    */
    
    #include<iostream>
    #define Maxsize 100
    #define ElemType char//ElemType 可根据需求自行定义
    using namespace std;
    
    //顺序表数据结构
    typedef struct
    {
    	/*ElemType是数据结构的书上为了说明问题而用的一个词。它是element type(“元素的类型”)的简化体。*/
    	ElemType *data;//顺序表元素
    	int length;//顺讯表当前长度
    }SqList;
    
    //*******************************基本操作函数******************************
    
    //顺序表的初始化,创建一个空的顺序表
    int Initlist(SqList &L)
    {
    	L.data = new ElemType[Maxsize];//为顺序表分配一个大小为Maxsize的数组空间
    	if (!L.data)
    		exit(OVERFLOW);//存储空间分配失败
    	L.length = 0;//空表长度为0
    	return 0;
    }
    
    //顺序表的创建,创建一个长度为n的顺序表
    bool CreateList(SqList& L, int n)
    {
    	if (n<0 || n>Maxsize)
    	{
    		return false;
    	}
    	else
    		for (int i = 0; i < n; i++)
    		{
    			cout << "请输入第" << i+1 << "个元素:" << endl;
    			cin >> L.data[i];
    			L.length++;
    		}
    	return true;
    }
    
    //顺序表的插入,第i个位置插入新元素e
    bool InsertList(SqList& L, int i, ElemType e)
    {
    	if (i<1 || i>L.length + 1)
    	{
    		return false;//插入位置不合法
    	}
    	if (L.length == Maxsize)
    	{
    		return false;//当前存储空间已满
    	}
    	for (int j = L.length; j >= i; j--)
    	{
    		L.data[j] = L.data[j - 1];
    	}
    	L.data[i - 1] = e;
    	L.length++;
    	return true;
    }
    
    //顺序表的删除,删除第i个元素
    bool DeleteList(SqList& L,int i)
    {
    	if (i<1 || i>L.length)
    	{
    		return false;//删除位置不合法
    	}
    	for (int j = i; j < L.length; j++)
    	{
    		L.data[j - 1] = L.data[j];
    	}
    	L.length--;
    	return true;
    }
    
    //顺序表的查找,按值查找
    int LocateData(SqList L, ElemType e)
    {
    	for (int i = 0; i < L.length; i++)
    	{
    		if (L.data[i] == e)
    		{
    			return i + 1;//查找成功,返回其序号
    		}
    	}
    	return 0;
    }
    
    //顺序表的取值,取得第i个元素的值
    bool GetData(SqList L, int i, ElemType &e)
    {
    	if (i<1 || i>L.length)
    	{
    		return false;
    	}
    	else
    	{
    		e = L.data[i - 1];
    		return true;
    	}
    }
    
    //*********************************功能函数********************************
    
    //1、 顺序表的创建函数
    void Create(SqList& L)
    {
    	int n;
    	bool flag;
    	cout << "请输入要创建的顺序表长度:" << endl;
    	while (1)
    	{
    		cin >> n;
    		flag = CreateList(L, n);
    		if (flag)
    		{
    			cout << "顺序表创建成功!" << endl;
    			break;
    		}
    		else
    		{
    			cout << "顺序表创建失败!" << endl;
    			cout << "请重新输入要创建数据表的长度:" << endl;
    		}
    	}
    	
    }
    
    //2、顺序表的插入函数
    void Insert(SqList& L)
    {
    	int place;
    	ElemType e;
    	bool flag;
    	cout << "请输入元素要插入的位置:" << endl;
    	cin >> place;
    	cout << "请输入元素要插入的元素:" << endl;
    	cin >> e;
    	flag = InsertList(L, place, e);
    	if (flag)
    	{
    		cout << "顺序表插入成功!" << endl;
    	}
    	else
    	{
    		cout << "顺序表插入失败!" << endl;
    	}
    }
    
    //3、顺序表的删除函数
    void Delete(SqList& L)
    {
    	int place;
    	bool flag;
    	cout << "请输入要删除元素的位置:" << endl;
    
    	cin >> place;
    	flag = DeleteList(L, place);
    	if (flag)
    	{
    		cout << "顺序表的元素删除成功!" << endl;
    	}
    	else
    	{
    		cout << "顺序表的元素删除失败!" << endl;
    	}
    }
    
    //4、顺序表的查找函数
    void Search(SqList L)
    {
    	ElemType e;
    	int place;
    	cout << "请输入要查找的值:" << endl;
    	cin >> e;
    	place = LocateData(L, e);
    	if (place)
    		cout << "该元素的位置为:" << place << endl;
    	else
    		cout << "没有找到该元素" << endl;
    }
    
    //5、顺序表的取值函数
    void Get(SqList L)
    {
    	int place;
    	ElemType e;
    	bool flag;
    	cout << "请输入要取元素的位置:" << endl;
    	cin >> place;
    	flag=GetData(L, place, e);
    	if (flag)
    	{
    		cout << "取得的元素为:" << e << endl;
    	}
    	else
    		cout << "取值失败!" << endl;
    }
    
    //6、顺序表的清空函数
    void ClearList(SqList& L)
    {
    	L.length = 0;
    }
    
    //7、顺序表的求长函数
    void GetLength(SqList L)
    {
    	cout << "顺序表的长度为:" << L.length << endl;
    }
    
    //8、顺序表的判空函数
    void IsEmpty(SqList L)
    {
    	if (L.length == 0)
    		cout << "顺序表为空" << endl;
    	else
    		cout << "顺序表不为空" << endl;
    }
    
    //9、打印输出当前顺序表的所有元素
    void PrintList(SqList L)
    {
    	cout << "当前顺序表的所有元素分别为:" << endl;
    	for (int i = 0; i < L.length; i++)
    	{
    		cout << "第" << i + 1 << "个元素为:" << L.data[i] << endl;
    	}
    }
    
    //菜单
    void menu()
    {
    	cout << "************************************************" << endl;
    	cout << "*********************1、创建********************" << endl;
    	cout << "*********************2、插入********************" << endl;
    	cout << "*********************3、删除********************" << endl;
    	cout << "*********************4、查找********************" << endl;
    	cout << "*********************5、取值********************" << endl;
    	cout << "*********************6、清空********************" << endl;
    	cout << "*********************7、求长********************" << endl;
    	cout << "*********************8、判空********************" << endl;
    	cout << "*********************9、打印********************" << endl;
    	cout << "*********************0、退出********************" << endl;
    	cout << "************************************************" << endl;
    }
    
    int main()
    {
    	SqList L;
    	Initlist(L);
    	int select;
    	while (1)
    	{
    		system("cls");//进行清屏操作
    		menu();
    		cout << "请输入菜单序号:" << endl;
    		cin >> select;
    		switch (select)
    		{
    		case 1:
    			Create(L);//创建
    			system("pause");//按任意键继续
    			break;
    		case 2:
    			Insert(L);//插入
    			system("pause");
    			break;
    		case 3:
    			Delete(L);//删除
    			system("pause");
    			break;
    		case 4:
    			Search(L);//查找
    			system("pause");
    			break;
    		case 5:
    			Get(L);//取值
    			system("pause");
    			break;
    		case 6:
    			ClearList(L);//清空
    			system("pause");
    			break;
    		case 7:
    			GetLength(L);//求长
    			system("pause");
    			break;
    		case 8:
    			IsEmpty(L);//判空
    			system("pause");
    			break;
    		case 9:
    			PrintList(L);//打印
    			system("pause");
    			break;
    		case 0:
    			cout << "欢迎下次使用!" << endl;//退出
    			system("pause");
    			return 0;
    			break;
    		default:
    			cout << "菜单序号输入有误!" << endl;
    			system("pause");
    			break;
    		}
    	}
    	system("pause");
    	return 0;
    }

    注意:ElemType 可根据需求自行定义,将其定义成合适的结构体形式,对以上代码稍作修改,便可以实现通讯录管理系统或图书信息管理系统的一些基本操作。
    例如:图书信息管理系统可对ElemType进行如下定义。

    typedef struct
    {
        string number;//图书编号
    	string name;//图书名字
    	float price;//图书价格
    }ElemType;

    参考资料:
    《数据结构》(C语言版)严蔚敏
    数据结构-顺序表基本操作的实现(含全部代码)_lady_killer9的博客-CSDN博客_数据结构顺序表代码

    更多相关内容
  • 顺序表

    千次阅读 多人点赞 2019-11-06 08:49:33
    顺序表是什么呢? 顾名思义,顺序表是物理地址连续的存储单元依次存储数据的线性结构,一般情况下采用数组存储,在数组上完成数据的增删查改。 顺序表和数组有什么区别呢? 顺序表比数组更约束,顺序表物理地址上...

    顺序表是什么呢?
    顾名思义,顺序表是物理地址连续的存储单元依次存储数据的线性结构,一般情况下采用数组存储,在数组上完成数据的增删查改。
    在这里插入图片描述
    顺序表和数组有什么区别呢?
    顺序表比数组更约束,顺序表物理地址上必须连续存储,数组是顺序表在实际编程中的具体实现方式。

    顺序表分为静态顺序表和静态顺序表(主要区别在于他们的容量是否可变)

    静态顺序表

    静态顺序表的概念

    顺序表的容量在静态时期(编译期间)确定,大小不可改变。

    静态顺序表的创建
    typedef struct SeqList{
    	int array[100];
    	int size;//顺序表中实际存储的数据个数
    }SeqList;//别名
    

    静态顺序表相对来比较简单,我们这里就不做深入的讨论,接下来主要了解一下动态顺序表。

    动态顺序表

    动态顺序表的概念

    顺序表的容量在动态时期(运行期间)确定,大小可改变。

    动态顺序表的创建
    typedef struct SeqList{
    	int* array;//动态从堆上申请
    	int capacity;//容量
    	int size;//有效数据的个数  尾插时,可用位置的下标
    }SeqList;
    
    动态顺序表的初始化

    Main.c
    初始化顺序表传参时应该传&seqlist,用结构体指针来接收 SeqList ✳ps,并且还应传顺序表的容量capacity。

    	SeqList seqlist;
     	SeqListInit(&seqlist,10);
    

    SeqList.h

    void SeqListInit(SeqList *ps,int capacity);
    

    SeqList.c

    void SeqListInit(SeqList *ps,int capacity){
    	ps->array = malloc(sizeof(int) * capacity);//申请空间大小
    	assert(ps->array != NULL);
    	ps->size = 0;
    	ps->capacity = capacity;
    }
    
    动态顺序表的销毁

    Main.c
    这里传参依旧是&seqlist,注意释放顺序表空间free(ps->array),销毁时传参不需要传顺序表的容量。

    SeqListDestroy(&seqlist);
    

    SeqList.h

    void SeqListDestroy(SeqList *ps);
    

    SeqList.c

    void SeqListDestroy(SeqList *ps){
    	//释放 array 的空间
    	free(ps->array);
    	//锦上添花
    	ps->array = NULL;
    	ps->size = 0;
    	ps->capacity = 0;
    
    }
    
    动态顺序表的扩容

    当顺序表的容量不够用时,我们应该怎么办呢?当然是扩大顺序表的容量。
    在这里插入图片描述
    具体步骤:
    1.当size(实际存储)>=capacity(顺序表容量)时,顺序表执行扩容。
    2.扩容一般是两倍增长,新顺序表是原顺序表容量的2倍大小。(缺陷:会造成空间的浪费)int newCapacity = ps->capacity * 2;
    3.注意:不是在原顺序表的基础上增加容量,而是新建一个顺序表。int *newArray = (int*)malloc(sizeof(int)*newCapacity);

    4.将原来顺序表的数据加载到新的顺序表中。
    for (int i = 0; i < ps->sz; i++){ newArray[i] = ps->array[i]; }
    5.扩容完成,释放原来顺序表的内存。
    free(ps->array);
    6.将array的关系指向新的顺序表。
    ps->array = newArray;
    7.改变capacity
    ps->capacity = newCapacity;

    static void CheckCapacity(SeqList *ps){
    	if (ps->size < ps->capacity){
    		return;
    	}
    	//需要扩容
    	int newCapacity = ps->capacity * 2;
    	int *newArray = (int*)malloc(sizeof(int)*newCapacity);
    	assert(newArray != NULL);
    
    	//搬移
    	for (int i = 0; i < ps->size; i++){
    		newArray[i] = ps->array[i];
    	}
    
    	//释放老空间
    	free(ps->array);
    	ps->array = newArray;
    	ps->capacity = newCapacity;
    }
    
    
    动态顺序表的插入(头插,尾插,根据pos下标插入)

    尾插
    在这里插入图片描述
    尾插时,顺序表有效数据的个数就是尾插时可用位置的下标。
    完成尾插之后,使有效数据个数size++。

    void SeqListPushBack(SeqList *ps, int v);
    
    void SeqListPushBack(SeqList *ps, int v){
    	CheckCapacity(ps);
    	ps->array[ps->size] = v;
    	ps->size++;
    }
    

    头插
    在这里插入图片描述
    头插可以直接将数据插到顺序表的首位吗?很显然是不行的,因为顺序表首位已经有了数据。
    头插时,应从后向前依次将数据向后搬移一位,将首位腾出给目标数据插入。

    void SeqListPushFront(SeqList *ps, int v);
    
    void SeqListPushFront(SeqList *ps, int v){
    	CheckCapacity(ps);
    	//i表示空间下标
    	for (int i = ps->size; i >= 1; i--){
    		ps->array[i] = ps->array[i - 1];
    	}
    	ps->array[0] = v;
    	ps->size++;
    }
    

    根据pos下标插入
    在这里插入图片描述
    将下标为pos及pos之后的数据向后移动一位,使ps->array[pos]=v。

    void SeqListInsert(SeqList *ps, int pos, int v);
    
    void SeqListInsert(SeqList *ps, int pos, int v){
    	CheckCapacity(ps);
    	//pos = 0为头插  pos = size为尾插
    	assert(pos >= 0 && pos <= ps->size);
    	//i代表数据的下标
    	for (int i = ps->size - 1; i >= pos; i--){
    		ps->array[i + 1] = ps->array[i];
    	}
    
    	ps->array[pos] = v;
    	ps->size++;
    }
    
    动态顺序表的删除(头删,尾删,根据pos下标删除)

    尾删
    在这里插入图片描述
    直接使顺序表size--

    void SeqListPopBack(SeqList *ps);
    
    
    void SeqListPopBack(SeqList *ps){
    	assert(ps->size > 0);
    	ps->size--;
    }
    

    头删
    在这里插入图片描述
    直接前移覆盖第一个数据

    void SeqListPopFront(SeqList *ps);
    
    void SeqListPopFront(SeqList *ps){
    	assert(ps->size > 0);
    	//i代表空间的下标
    	for (int i = 0; i <= ps->size - 2; i++){
    		ps->array[i] = ps->array[i + 1];
    	}
    	ps->size--;
    }
    

    根据pos下标删除
    在这里插入图片描述
    将pos+1及以后的数据依次前移

    void SeqListErase(SeqList *ps, int pos);
    
    void SeqListErase(SeqList *ps, int pos){
    	assert(ps->size > 0);
    	assert(pos >= 0 && pos < ps->size);
    	//i代表数据的下标
    	for (int i = pos + 1; i <= ps->size - 1; i++){
    		ps->array[i - 1] = ps->array[i];
    	}
    	ps->size--;
    }
    

    删除第一个遇到的目标元素
    调用查找和根据pos下标删除的函数即可

    int SeqListRemove(SeqList *ps, int v);
    
    int SeqListRemove(SeqList *ps, int v){
    	int pos = SeqListFind(ps, v);
    	if (pos = -1){
    		return;
    	}
    
    	SeqListErase(ps, pos);
    
    }
    

    删除所有的目标元素
    在这里插入图片描述
    定义i 和 j,若没有遇到目标元素,i++,j++,若遇到目标元素i++,j不动,直到i找到下一个不是目标元素的值,将值赋给j下标所在的数据,即可完成替换目标元素。

    int SeqListRemoveAll(SeqList *ps, int v);
    
    int SeqListRemoveAll(SeqList *ps, int v){
    	int i, j;
    	for (i = 0, j = 0; i < ps->size; i++){
    		if (ps->array[i] != v){
    			ps->array[j] = ps->array[i];
    			j++;
    		}
    	}
    	ps->size = j;
    }
    
    动态顺序表的查找

    遍历顺序表查找

    int SeqListFind(SeqList *ps, int v);
    
    int SeqListFind(SeqList *ps, int v){
    	for (int i = 0; i < ps->size; i++){
    		if (ps->array[i] = v){
    			return i;
    		}
    	}
    	return -1;
    }
    
    动态顺序表的更新

    目标数据直接替换pos下标所在数据

    void SeqListModify(SeqList *ps, int pos, int v);
    
    void SeqListModify(SeqList *ps, int pos, int v){
    	assert(pos >= 0 && pos < ps->size);
    	ps->array[pos] = v;
    }
    

    到这里顺序表的基本问题就解释完了,相信多多少少会解决大家心头的疑问,在数据结构的学习中应当善于思考,多画图,死磕代码,注意细节,将伪代码转换为代码,这样才能很好的掌握数据结构的有关知识。

    展开全文
  • 顺序表的实现

    千次阅读 多人点赞 2022-03-13 12:51:51
    1.顺序表的概念 2.静态顺序表 分析: 3.动态顺序表 分析: 4.顺序表初始化 5.顺序表尾部操作 5.1尾插 空间检查函数实现 分析: 5.2尾删 分析: 6.顺序表的头部操作 6.1头插 分析: 6.2头删 分析: ...

    目录

    1.顺序表的概念

    2.静态顺序表

    分析:

    3.动态顺序表

    分析:

    4.顺序表初始化

    5.顺序表尾部操作

    5.1尾插

     空间检查函数实现

    分析:

    5.2尾删

    分析:

    6.顺序表的头部操作

    6.1头插

    分析:

    6.2头删

    分析:

    7.固定位置操作

    7.1固定位置插入

    分析:

     7.2固定位置删除

    分析:

    8.查找及打印

    9.销毁顺序表

    10.我的菜单及主函数 

    直接上代码:


    1.顺序表的概念

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。

    顺序表一般可以分为:静态顺序表和动态顺序表

    2.静态顺序表

                  使用定长数组存储元素

    分析:

    3.动态顺序表

                 使用动态开辟的数组存储

    分析:


     

           函数接口基于动态顺序表来实现       

    4.顺序表初始化

    通过分析,我们知道顺序表中有起始地址,数据个数,及空间大小,一个顺序表刚开始当然应该为空,那么数据个数和空间大小应为0,起始地址应置空

    操作是对整个顺序表进行操作,函数参数应传顺序表地址,形参接收用指针。

    //初始化
    void SLInit(SL* p)
    {
    	assert(p);    //暴力判断,断言指针是否为空
    	p->a = NULL;
    	p->size = 0;
    	p->capacity = 0;
    }

    5.顺序表尾部操作

    5.1尾插

    顾名思义,从顺序表的末尾插入数据,顺序表空间是固定的,插入的时候我们要检查空间是否足够,不够则要进行扩容,足够则插入。

    void SLPushBack(SL* p, SLDataType x)
    {
    	assert(p);
    	//检查空间,是否扩容
    	SLcheckCapacity(p);
    
    	//插入
    	p->a[p->size] = x; //尾数的下一个位置插入数据
    	p->size++;          //有效数据个数加一
    }

     空间检查函数实现

    //检查空间
    void SLcheckCapacity(SL* p)
    {
    	assert(p);
    	//检查是否需要扩容
    	if (p->size == p->capacity)
    	{
    		size_t newCapacity = p->capacity == 0 ? 4 : p->capacity * 2;
    		SLDataType* tmp = realloc(p->a, sizeof(SLDataType)*newCapacity);
    		if (tmp == NULL)
    		{
    			printf("realloc fail\n");
    			exit(-1);
    		}
    		else
    		{
    			p->a = tmp;
    			p->capacity = newCapacity;
    		}
    	}
    }

    分析:

    我们要知道当数据个数=空间数时,空间已满,那么就要改变空间大小,这里我们设新的空间大小newCapacity为原capacity的二倍。

    接下来就是扩容空间为新空间大小,用realloc开辟空间,记着要判断是否开辟成功,详细用法: 动态内存管理分析理解_i跑跑的博客-CSDN博客

     开辟成功后,记得将令新空间指向原顺序表地址,空间大小=新空间大小。

    5.2尾删

    分析:

    删除的时候并不是将最后一个数给置为0,或者‘\n’,这些,不对数据进行任何需要将操作而是只有效个数减一就可以。注意不可以对要删除数得空间进行释放,这是不可取得,动态开辟出的空间是一起开辟,一起释放的,在这里不可以实现。

    //尾删
    void SLPopBack(SL* p)
    {
    	assert(p);
    	//size不能一直--
    	if (p->size > 0)
    	{
    		p->size--;
    	}
    }

     有效个数不能为负数,这里要进行判断。

    6.顺序表的头部操作

    6.1头插

    分析:

    从头部插入数据,那么就需要将原数据从最后一个数据开始向后移动一位,这里必然要进行空间检查。

    //头插
    void SLPushFront(SL* p, SLDataType x)
    {
    	assert(p);
    	SLcheckCapacity(p);
    	for (int i = p->size;i>0;i--)
    	{
    		p->a[i] = p->a[i-1];
    	}
    	p->a[0] = x;
    	p->size++;
    }

    记得插入后有效数据个数加一。

    6.2头删

    分析:

    与头插相反,头插是将从最后一个数开始向后覆盖,头删是不要第一个数,从第一个数开始,第一个=第二个;第二个=第三个 ... ... 这样覆盖,覆盖原有效数据-1次。

    //头删
    void SLPopFront(SL* p)
    {
    	assert(p);
    	if (p->size>0)
    	{
    		for (int j = 0; j<p->size - 1; j++)
    		{
    			p->a[j] = p->a[j + 1];
    		}
    	}
    	p->size--;
    }

    7.固定位置操作

    7.1固定位置插入

              固定位置为下标,从0开始

    分析:

    思想与头插相似,先要判断空间是否足够。再进行插入,例如从下标x的位置开始,那么从最后一个数向后挪动,挪动size-x次,在x位置插入数据。

    判断位置大小是否大于size,越界。 

    //在固定位置插入,pos为下标
    void SLInsert(SL* p, size_t pos, SLDataType x)
    {
    	assert(p);
    	//注意要判断pos的大小
    	if (pos>p->size)
    	{
    		printf("pos 越界:%d\n",pos);
    		return;
    	}
    	SLcheckCapacity(p);
    	for (int i = p->size;i>pos;i--)
    	{
    		p->a[i] = p->a[i - 1];
    	}
    	p->a[pos] = x;
    	p->size++;
    }

     7.2固定位置删除

    分析:

    操作与头删相似,从pos位置开始;第一个=第二个;第二个=第三个 ... ... ,覆盖到pos=尾数的上一个数,顺便也防了个越界。

    //在固定位置删除,pos为下标
    void SLErase(SL* p, size_t pos)
    {
    	assert(p);
    	if (pos<p->size)
    	{
    		for (int j = (int)pos; j<p->size-1; j++)
    		{
    			p->a[j] = p->a[j + 1];
    		}
    	}
    	p->size--;
    }

    8.查找及打印

    依次遍历,找到则返回位置下标,

    //查找
    int SLFind(SL* p,SLDataType x)
    {
    	assert(p);
    	for (int i = 0;i<p->size;i++)
    	{
    		if (p->a[i]==x)
    		{
    			return i;
    		}
    	}
    	return -1;
    }

    也是遍历,打印每一个数据。 

    //打印
    void SLPrintf(SL* p)
    {
    	assert(p);
    	for (int i = 0;i<p->size;i++)
    	{
    		printf("%d ",p->a[i]);
    	}
    	printf("\n");
    }

    9.销毁顺序表

              注意要释放掉内存 

    //销毁
    void SLDestory(SL* p)
    {
    	assert(p);
    	free(p->a);
    	p->a = NULL;
    	p->capacity = p->size = 0;
    }

    10.我的菜单及主函数 

    直接上代码:

    void menu()
    {
    	printf("******************************\n");
    	printf("** 1.尾插数据 ** 2.头插数据 **\n");
    	printf("** 3.尾删数据 ** 4.头删数据 **\n");
    	printf("** 5.固定插入 ** 6.固定删除 **\n");
    	printf("** 7.查找数据 ** 8.打印数据 **\n");
    	printf("**         0.退出           **\n");
    	printf("******************************\n");
    }
    int main()
    {
    	SL s;
    	SLInit(&s);
    	int input = 0;
    	do
    	{
    		int val = 0;
    		size_t pos = 0;
    		menu();
    		printf("请输入选项->:");
    		scanf("%d", &input);
    		switch (input)
    		{
    		case 1:
    			printf("请输入你要尾插的数据:");
    			scanf("%d",&val);
    			SLPushBack(&s,val);
    			break;
    		case 2:
    			printf("请输入你要头插的数据:");
    			scanf("%d", &val);
    			SLPushFront(&s, val);
    			break;
    		case 3:
    			SLPopBack(&s);
    			break;
    		case 4:
    			SLPopFront(&s);
    			break;
    		case 5:
    			printf("请输入你要插入的位置和数据:");
    			scanf("%d %d",&pos ,&val);
    			SLInsert(&s,pos,val);
    			break;
    		case 6:
    			printf("请输入你要删除的位置:");
    			scanf("%d", &pos);
    			SLErase(&s, pos);
    			break;
    		case 7:
    			printf("请输入要查找的数据:");
    			scanf("%d",&val);
    			int num=SLFind(&s,val);
    			printf("%d\n",num);
    			break;
    		case 8:
    			SLPrintf(&s);
    			break;
    		case 0:
    			SLDestory(&s);
    			break;
    		default:
    			printf("请重新输入\n");
    			break;
    		}
    	} while (input);
    	return 0;
    }

     这样一个顺序表的定义,函数及功能就建立完成了。

    看到这啦,点个赞呗,关注不迷路噢,欢迎大家评论指正。

    展开全文
  • 【数据结构功法】第3话 · 顺序表快速入门

    千次阅读 多人点赞 2022-03-29 22:07:53
    动态顺序表的定义 kiko:在学完静态顺序表定义的参数细节后,对于动态顺序表的定义,我希望大家可以先思考一下动态顺序表需要哪些参数,然后自己写一个结构体试试先。 Q1:定义一个动态顺序表需要哪些参数? A1:...

    🌕写在前面


    Hello🤗大家好啊,我是kikokingzz,名字太长不好记,大家可以叫我kiko哦~

    从今天开始,我将正式开启一个新的打卡专题——【数据结构·水滴计划】,没错!这是今年上半年的一整个系列计划!本专题目的是通过百天刷题计划,通过题目和知识点串联的方式刷够1000道题完成对数据结构相关知识的全方位复习和巩固;同时还配有专门的笔记总结和文档教程哦!想要搞定,搞透数据结构的同学

    🎉🎉欢迎订阅本专栏🎉🎉

    🍊博客主页:kikoking的江湖背景🍊


    🌟🌟往期必看🌟🌟

    【数据结构】第一话·数据结构入门竟如此简单?

    收藏量:471

    【数据结构】第二话·带你彻底吃透算法复杂度

    收藏量:1517

    目录

    🌕写在前面

    🍺知识点3:线性表

    🥝3.1 线性表的定义与操作

    🍊1.什么是线性表?

    🍊2.线性表的特点有哪些? 

    🍊3.线性表的基本操作有哪些?

    🍺知识点4:顺序表

    🥝4.1 顺序表的定义与特点

    🍊1.什么是顺序表?

    🍊2.顺序表的特点有哪些呢?

    🥝4.2 顺序表的静态分配

    🍊1.什么是顺序表的静态分配?

    🍊2.静态顺序表的定义

    🥝4.3 顺序表的动态分配

    🍊1.什么是顺序表的动态分配?

    🍊2.动态顺序表的定义

    🍊3.动态顺序表的功能定义

    🥝4.4 动态分配的代码实现 

    (1)初始化顺序表·SeqListInit

    (2)销毁顺序表·SeqListDestroy

    (3)动态监测与扩容·SeqCheckCapacity

    (4)尾插元素·SeqListPushBack

    (5)头插元素·SeqListPushFront

    (6)指定位置插入元素·SeqListInsert

    (7)尾删元素·SeqListPopBack

    (8)头删元素·SeqListPopFront

    (9)指定位置删除元素·SeqListErase

    (10)按值查找·SeqListFind

    (11)打印输出·SeqListPrint

    📝LeetCode之移除元素

    🌕写在最后

    热爱所热爱的, 学习伴随终生,kikokingzz与你同在!❥(^_-)

    🍺知识点3:线性表

    🥝3.1 线性表的定义与操作


    🍊1.什么是线性表?

    线性表是一种逻辑结构,它是具有相同数据类型的n(n>=0)个数据元素的有限集合,其中n为表长,当n=0时,线性表是一个空表。若用L命名线性表,则其一般表示为:

    如果采用更生动一点方式来描述线性表的话,我们可以看看下图呀:


    🍊2.线性表的特点有哪些? 

    (1)表中元素个数有限。

    (2)表中元素数据类型相同,因此每个元素占用相同大小的存储空间。

    (3)表中元素具有逻辑上的顺序性,各元素之间有先后次序。

    (4)表中元素具有抽象性,仅讨论元素间的逻辑关系,而不考虑元素究竟是什么内容。

    注意:线性表是一种逻辑结构,表示元素间一对一的相邻关系,而顺序表和链表是存储结构。

    02.以下( )是一个线性表。
    A.由n个实数组成的集合
    B.由100个字符组成的序列
    C.所有整数组成的序列
    D.邻接表
    

    kiko:A. 集合中的元素没有前后之间的逻辑关系;B. 是有限个数据元素组成的序列,序列具有逻辑关系,满足线性表的要求;C. 所有整数的个数是无限个,不满足线性表中元素个数有限的特点;D. 邻接表属于存储结构,而线性表是一种逻辑结构;因此正确答案:B

    03.线性表是一个( )。
    A.有限序列,可以为空
    B.有限序列,不能为空
    C.无限序列,可以为空
    D.无限序列,不能为空
    

    kiko:由线性表概念可得,线性表是n(n ≥0)个具有相同特性的数据元素的有限序列,因此线性表可以为空,但必须是有限序列,因此正确答案:A


    🍊3.线性表的基本操作有哪些?

    一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可以通过调用这些基本操作来实现,要注意之后学习的顺序表的基本操作,就是线性表在顺序存储的情况下的一些基本操作。

    • (创)初始化:构造一个空的线性表。
    • (销)销毁表:销毁操作,销毁线性表,并释放线性表所占用的空间。
    • (增)插入操作:在表中某位置插入指定元素。
    • (删)删除操作:删除表中某位置元素。
    • (查)按值查找:在表中查找具有给定关键字值的元素。
    • (查)按位查找:获取表中第i个位置的元素的值。
    • 输出操作:按照前后顺序输出线性表中的所有元素。
    • 求表长:返回线性表的长度,即线性表中元素的个数。
    • 判空操作:若为空表,返回true,否则返回false。

    对于上面这些基本操作,其实我们只需要记住一个口诀,就可以将上述最重要的一些基本功能囊括其中:线性表的基本操作有:创、销、增、删、改、查。

    PS:上述操作中并没有出现“改”,但是在实际执行运算过程中,“查”操作有一部分是为了“改”,比如:我需要将线性表中所有值为1的元素改为0,这时我需要先通过“按值查找”找到指定元素,然后才可以进行值的修改。

    🍺知识点4:顺序表

    🥝4.1 顺序表的定义与特点


    🍊1.什么是顺序表?

    线性表的顺序存储又称为顺序表,实际上就是一个数组;它用一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置,第i个元素的存储位置后面紧接着存储的是第i+1个元素,称 i 为元素a_{i}在线性表中的位序。


    🍊2.顺序表的特点有哪些呢?

    (1)双序相同:顺序表中元素的逻辑顺序与物理顺序相同。

    (2)随机存取:当你知道数组首地址后,可以在相同时间内读取任何一个位置的元素;如上图所示,假设a_{1}的内存地址为LOC(A),那么你可以在O(1)的时间找到元素a_{i},因为a_{i}在内存中的存储位置为LOC(A)+(i-1)*sizeof(ElemType),这个计算式对所有元素都是一样的计算时间,可以理解为,访问任何一个元素的时间都是相同的,也就是随机存取。

    PS:对于链表来说,假如要读取第a_{i}个,那么就需要依次从头挨个读取,一直读到第i个才能找到。

    01.下述( )是顺序存储结构的优点。
    A.存储密度大
    B.插入运算方便
    C.删除运算方便
    D.方便地运用于各种逻辑结构的存储表示

    kiko:顺序表不像链表那样要在结点中存放指针域,因此存储密度较大,A正确。B和C是链表的优点,对于顺序表来说是缺点。D是错误的,比如对于树形结构,顺序表显然不如链表表示起来方便;因此本题选A。

    04.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值,为了提高效率,应
    采用( )的存储方式。
    A.单链表        B.双向链表        C.单循环链表        D.顺序表

    kiko:题干实际要求能最快存取第i-1、i、i+1个元素值。A、B、C都只能从头结点依次顺序查找,时间复杂度为O(N),只有顺序表可以按序号随机存取,时间复杂度为O(1);因此本题选D。

    02.线性表的顺序存储结构是一种( )。
    A.随机存取的存储结构
    B.顺序存取的存储结构
    C.索引存取的存储结构
    D.散列存取的存储结构

    kiko:本题易误选B。注意,存取方式是指读写方式。顺序表是一种支持随机存取的存储结构,根据起始地址加上元素的序号,可以很方便地访问任意一个元素,这就是随机存取的概念。而顺序存取指的是可以从首元素开始遍历至需要存取的元素,因此链表与顺序表都可以是顺序存取的。通过比较二者,我们优先选A。这并不是一道好题目。

    02.(多选)一个顺序表占用存储空间的大小与( )有关。
    A.表长
    B.元素的数据类型
    C.表中元素数量
    D.元素的物理位置
    

    kiko:顺序表占用的空间大小等于表长\timessizeof(元素数据类型),这是因为顺序表的空间是提前申请好的,因此其存储空间的大小与表中的元素数量和位置无关。

     ✨✨✨我是分割线✨✨✨ 

    🥝4.2 顺序表的静态分配


    🍊1.什么是顺序表的静态分配?

    顺序表在静态分配时,使用“静态”的数组存放数据元素。静态的意思是:数组的大小和空间是事先预定好的,因此一旦空间占满,如果出现新的数据,就会产生溢出,最终导致程序崩溃。

    缺点:开小了不够用,开大了会存在浪费。


    🍊2.静态顺序表的定义

    Q1:定义一个静态顺序表需要哪些参数?

    A1:关于这个问题很多书上都没有提及,从个人角度认为,其参数细节主要有以下几点:

    1. 顺序表的最大长度:通俗来说,我们得知道顺序表能存放多少个元素,对于静态顺序表来说,我们通过采用宏定义的方式确定其最多可存100个元素;
    2. 顺序表中元素类型:我们要知道顺序表存放的是什么类型的数据元素,下例中我们通过定义 int a[N] 确定顺序表存放的元素类型为int型,且开辟了100个空间;
    3. 顺序表的当前长度:我们需要知道当前顺序表已经存了多少元素,进而在一些对顺序表插入、删除等操作时,方便我们处理元素。

    由于定义一个顺序表需要囊括以上三类参数,因此我们采用结构体的方式,将他们集合到一起,所以最终采用了结构体的方式。

    //静态的顺序表
    
    #define N 100 //定义顺序表的最大长度
    struct SeqList
    {
    	int a[N];//定义顺序表存储的元素类型和元素个数
    	int size;//定义顺序表的当前存储个数
    };

     ✨✨✨我是分割线✨✨✨

    🥝4.3 顺序表的动态分配


    🍊1.什么是顺序表的动态分配?

    采用动态分配时,存储数组的空间是在程序执行过程中通过动态存储分配语句分配的,一旦数据空间占满,就另外开辟一块更大的存储空间,用以替换原来的存储空间,从而达到扩充数组空间的目的,而不需要为线性表一次性地划分所有空间。


    🍊2.动态顺序表的定义

    kiko:在学完静态顺序表定义的参数细节后,对于动态顺序表的定义,我希望大家可以先思考一下动态顺序表需要哪些参数,然后自己写一个结构体试试先。

    Q1:定义一个动态顺序表需要哪些参数?

    A1:动态与静态顺序表的唯一区别就在于,动态顺序表是可以进行动态分配,遇到扩容时,元素是可以整体“搬家”的,“搬”到新的内存地址空间去,因此我们在这里将定义动态数组的指针(注意不是定义静态数组咯!),而其余参数和静态顺序表的需求是一样的,动态顺序表同样需要知道其当前情况下的最大容量capacity和当前元素个数size。

    typedef int DataType;//将int重定义为DataType
    //下次想更改数据类型的时候只需要更改前面的int就可以,无需改变整个程序
     
    typedef struct SeqList //定义一个顺序表的结构体
    {
    	DataType* a;//定义指示动态分配数组的指针
    	DataType size;//定义数组中有效数据的个数
    	DataType capacity;//定义数组的容量
    }SEQ;// 将SeqList这个结构体重定义为SEQ,为了后续方便写程序

    Q2:为什么上例要使用DataType而不直接使用int?

    A2:这里使用了 typedef 将int类型重定义为 DataType 型,目前动态顺序表存储的元素类型是int型,但如果下次该表改存float型数据元素时,我们只需要将上例第一行的int改为float就可以实现存储元素类型的变换;但如果不使用DataType而是整个程序都使用int,那么修改的时候就需要修改整个程序,太麻烦了!

    08.采用动态分配存储空间的顺序表,若已存放n个元素并存满存储空间,需要再存放m个元素,此时
    申请空间成功是说明线性表至少有( )个地址连续可分配的空闲空间。
    A. m
    B. m-n
    C. n+m
    D. n
    

    kiko:由于存储空间已满,因此额外存放m个元素则至少需要m+n个地址连续的空间。申请新空间成功后,将原本的n个元素复制到新空间并存放后续m个元素。因此本题选C。


    🍊3.动态顺序表的功能定义

    下面是一个动态顺序表的一些最核心、最基本的操作。其他较复杂的操作都可以通过调用以下操作的组合来实现。动态顺序表的主要操作有:

    void SeqListInit(SeqList *sl);//(1)初始化顺序表
    
    void SeqListDestroy(SeqList* sl);//(2)销毁顺序表
    
    void SeqListCheckCapacity(SeqList* sl);//(3)动态监测与扩容
    
    void SeqListPushBack(SeqList* sl, DataType x);//(4)尾插
    
    void SeqListPushFront(SeqList* sl, DataType x);//(5)头插
    
    void SeqListInsert(SeqList* sl, size_t pos, DataType x);//(6)指定位置插入
    
    void SeqListPopBack(SeqList* sl)//(7)尾删
    
    void SeqListPushPop(SeqList* sl);//(8)头删
    
    void SeqListErase(SeqList* sl, size_t pos)//(9)指定位置删除
    
    int SeqListFind(SeqList* sl, DataType x)//(10)按值查找
    
    void SeqListPrint(SEQ* sl);//(11)打印顺序表

    ✨✨✨我是分割线✨✨✨ 

    🥝4.4 动态分配的代码实现 


    (1)初始化顺序表·SeqListInit

    初始化一个顺序表,首先需要保证传入这个动态数组的指针不为空,因此这里使用assert进行断言操作,如果传入空指针,就会进行报错。由于是初始化操作,因此将该顺序表中所有参数置0,动态数组指针置NULL。

    PS:有些书籍在初始化时就为顺序表分配空间,但在本例中,将会统一在"动态监测与扩容"这一步进行,这是因为在初始化时为其分配空间的操作,也是扩容操作的一种情况,在这里我将它们集中在同一模块了。

    void SeqListInit(SeqList *sl)
    {
        assert(sl);//进行断言操作,防止空指针
    	sl->a = NULL;//将指向动态数组的指针置为空
    	sl->size = 0;//表中元素个数置为0
    	sl->capcity = 0;//表的容量置为0
    }

    (2)销毁顺序表·SeqListDestroy

    销毁顺序表比较简单,但是我们注意不要遗漏,我们可以从大到小进行销毁:

    • step1.释放整个顺序表的空间,即释放动态数组的空间
    • step2.将指向动态数组的指针置空
    • step3.将数组的容量和元素个数置0
    void SeqListDestroy(SeqList* sl)//销毁顺序表
    {
    	assert(sl);
    	free(sl->a);//释放动态数组空间
    	sl->a = NULL;//将动态数组的头指针置空
    	sl->capacity = sl->size = 0;//将数组容量和元素个数置0
    }

    (3)动态监测与扩容·SeqCheckCapacity

    该函数的主要操作是监测当前数组是否已满,如果元素已满将进行扩容操作;下例中是将数组的最大容量直接扩容2倍。

    void SeqListCheckCapacity(SeqList* sl)
    {
    	assert(sl);//声明sl,防止传入空指针
    	if (sl->size == sl->capacity)//如果相等,说明数组已满
    	{
    		DataType newcapacity = sl->capacity == 0 ? 4 : sl->capacity * 2;//扩容
    		DataType* tmp = realloc(sl->a, sizeof(DataType) * newcapacity);//动态申请空间
    		if (tmp == NULL)//判断动态申请空间操作是否成功
    		{
    			printf("realloc fail\n");
    			exit(-1);
    		}
    		else
    		{
    			sl->a = tmp;//将新申请的地址赋给动态数组指针
    			sl->capacity = newcapacity;//将新申请的空间赋予给capacity
    		}
    	}
    }

    Q1:初始化时未给动态数组分配空间,在这一步上是如何实现的?

    DataType newcapacity = sl->capacity == 0 ? 4 : sl->capacity * 2;//扩容
    DataType* tmp = realloc(sl->a, sizeof(DataType) * newcapacity);//动态申请空间

    A1:是通过上面两行程序实现的,在初始化时,我们将capacity赋值为0,因此当进入上述程序(三目操作符判断时),当capacity值为0时,将返回一个4赋值给newcapacity,相当于为其分配了4个初始空间。


    番外内容:realloc的细节

    realloc可以对给定的指针所指的空间进行扩大或者缩小,无论是扩张或是缩小,原有内存的中内容将保持不变。缩小时,被缩小的那一部分的内容会丢失;扩大时,realloc试图直接在现存的数据后面获得附加空间,当数据后面的空间不足时,就会重新寻找开辟一个足够的空间,将现存数据拷贝到新地址。(更多内容详见:malloc,realloc和calloc的区别

    • 原地扩容:如果现存数据后面附加空间够用,就原地扩容。
    • 异地扩容:如果现存数据后面附加空间不足,就异地扩容。

    Q2:为啥上例不使用malloc呢?

    A2:因为malloc是完全异地扩容,需要自己搬数据,释放旧空间,而realloc是有可能进行原地扩容的,消耗的代价可能会更低一些。


    (4)尾插元素·SeqListPushBack

    对于尾插元素,我们第一步先检测数组是否已经存满,如果存满了,我们就先对其进行扩容(使用SeqCheckCapacity来进行扩容),然后在数组尾元素后插入该元素,最后将size++即可。

    时间复杂度:O(1)

    void SeqListPushBack(SeqList* sl, DataType x)//尾插
    {
    	SeqListCheckCapacity(sl);//检测数组是否已满,满了就扩容
    	sl->a[sl->size] = x;     //尾插元素x
    	sl->size++;              //表中元素个数+1
    }

    (5)头插元素·SeqListPushFront

    对于头插,我们发现依然会有两种情况:1.数组有剩余空间、2.数组已经满了,因此第一步仍然是进行判断数组空间是否已满,如果满了就执行扩容操作;然后按元素从后往前的顺序,依次将元素向后移动一位,将数组的第一个头空间空出来。

    时间复杂度:O(N)

    void SeqListPushFront(SeqList* sl, DataType x)//头插
    {
    	assert(sl);//声明sl,防止传入空指针
    	SeqListCheckCapacity(sl);//检测数组是否已满,满了就扩容
    	int end = sl->size - 1;//将end指向数组中最后一个元素
    	while (end >= 0)//从后往前挨个后移
    	{
    		sl->a[end + 1] = sl->a[end];//end指向的元素后移
    		--end;//将end指向前一个元素
    	}
    	sl->a[0] = x;//头插元素x
    	sl->size++;//顺序表长度+1
    }

    (6)指定位置插入元素·SeqListInsert

    该操作程序类似于头插,只不过这里与头插的区别在于,它的头不再是数组的第一个位置了,而是pos指向的位置[pos](可以说是一种头插的变式啦~)。

    值得注意的是,在这里我们需要对pos的范围做一个规定,pos最前端可以达到数组的[0],此时相当于头插;pos最后端可以到达数组的 [size],此时相当于尾插。

    时间复杂度:O(N)

    void SeqListInsert(SeqList* sl, int pos, DataType x)//指定位置插入
    {
    	assert(sl);//声明sl,防止传入空指针
    	assert(pos >= 0&&pos<=sl->size);//规定pos允许插入的范围
    	SeqListCheckCapacity(sl);
    	int end = sl->size - 1;//将end指向数组中最后一个元素
    	while (end >= pos)//将pos位置及后面元素从后往前挨个后移
    	{
    		sl->a[end + 1] = sl->a[end];//将end指向的元素后移
    		--end;//将end指向前一个元素
    	}
    	sl->a[pos] = x;//在pos位置插入元素x
    	++sl->size;//顺序表长度+1
    }

    升级版本:使用 size_t 定义pos

    void SeqListInsert(SeqList* sl, size_t pos, DataType x)//改用无符号定义pos
    {
    	assert(sl);
    	assert(pos <= sl->size);
    	SeqListCheckCapacity(sl);
    	int end = sl->size - 1;//此处不可用size_t定义end
    	while (end >= (int)pos)//这边进行大小比较时一定要进行强转
    	{
    		sl->a[end + 1] = sl->a[end];
    		--end;
    	}
    	sl->a[pos] = x;
    	++sl->size;
    }

    此时我们需要注意,在while循环中进行end和pos的大小比较时,必须要将无符号的pos强制转换为int类型

    Q1:请问此处为什么不可用 size_t 定义end呢?

    A1:因为当原数组没有元素时,即size为0时,这时end的值计算为-1,但由于size_t 定义的是无符号数,因此end的值会从有符号数的-1变化为无符号数的4294967295,进而导致后续程序出错。

    Q2:为什么while循环中的判断语句要使用强转(int)呢?

    A2:这是因为当原数组没有元素时,即size为0时,这时end的值计算为有符号数的-1,如果不对pos进行强转,有符号数与无符号数比较时,有符号数会整型提升为无符号数,此时有符号数的-1将会变为无符号数的最大数,此时必然大于pos,进而进入while循环。此时由于end 的值为-1,sl->a[end]会出现访问越界错误。


    升级版本再改进

    kiko:当然我们不难发现,这边主要的核心问题在于,end出现了负数情况,我们有没有办法让end始终保持非负状态呢?这样我们就无需进行强转操作了,答案是有的。

    我们只需要将end更改指向为最后一个元素的后一个位置,这时就算原数组没有元素(size为0时),end的值也为0,是非负数,而pos的值最小为0,因此二者可以进行正常比较。

    void SeqListInsert(SeqList* sl, size_t pos, DataType x)//改用无符号定义pos
    {
    	assert(sl);
    	assert(pos <= sl->size);
    	SeqListCheckCapacity(sl);
    	size_t end = sl->size ;
    	while (end > pos)
    	{
    		sl->a[end] = sl->a[end-1];
    		--end;
    	}
    	sl->a[pos] = x;
    	++sl->size;
    }

    (7)尾删元素·SeqListPopBack

    在尾删元素过程中,我们一般只需要将顺序表中的size--即可,因为size的值代表的是顺序表中存储的有效元素长度,将其--,即将它的有效长度减1,相当于删除了最后一个元素;例如原本顺序表中有5个元素,这时使用size--后,该顺序表只有前4个元素有效,相当于尾删了一个元素。

    时间复杂度:O(1)

    PS:尾删时,我们不需要特意去清除最后一个元素的值,因为清除的物理本质是用一个值去替换原值,但我们无法确定新赋的值与原值是否相同,为了避免多此一举,因此直接size--,它不香吗?

    void SeqListPopBack(SeqList* sl)//尾删
    {
    	assert(sl);//声明sl,防止传入空指针
    	if (sl->size > 0)
    	{
    		sl->size--;//顺序表的有效数据是依赖于size的
    	}
    }

    (8)头删元素·SeqListPopFront

    对于头删元素,我们需要与头插做对比。头删时我们需要将头部元素之后的所有元素,按从前到后的顺序,将这些元素逐个前移,这样第二个元素的值就会覆盖掉第一个元素的值,换句话说也就实现了头删的功能。

    时间复杂度:O(N)

    值得注意的是,begin选取的位置不同,最终设计出来的程序也会不同,我们此处将begin指向头部后一个元素。

    void SeqListPopFront(SeqList* sl)//头删
    {
    	if (sl->size > 0)//当数组内有元素才可以头删
    	{
    		int begin = 1;
    		//当数组内只有一个元素时,直接跳过此步骤,直接--
    		while (begin < sl->size)
    		{
    			sl->a[begin - 1] = sl->a[begin];
    			++begin;
    		}
    		--sl->size;
    	}
    }

    (9)指定位置删除元素·SeqListErase

    该操作程序类似于头删,只不过这里与头删的区别在于,它的头不再是数组的第一个位置了,而是pos指向的位置[pos](同样可以说是一种头删的变式啦~)。

    因此,在这里我们也需要对pos的范围做一个规定,pos最前端可以达到数组的[0],此时相当于头删;pos最后端可以到达数组的 [size-1],此时相当于尾删,为了方便我们可以采用无符号 size_t 来定义pos。

    void SeqListErase(SeqList* sl, size_t pos)//指定位置删除
    {
    	assert(sl);
    	assert(pos < sl->size);
    	size_t begin = pos + 1;
    	while (begin < sl->size)
    	{
    		sl->a[begin - 1] = sl->a[begin];
    		++begin;
    	}
    	sl->size--;
    }

    (10)按值查找·SeqListFind

    该操作通常与其他操作组合使用,例如在某个具体数值的前后插入元素、删除数组中所有值为特定数的元素等。

    kiko:算是这么多操作里最简单的一个啦~

    int SeqListFind(SeqList* sl, DataType x)//该函数的返回值为int型
    {
    	assert(sl);
    	for (int i = 0; i < sl->size; ++i)
    	{
    		if (sl->a[i] == x)
    			return i;//返回这个元素的数组下标
    	}
    	return -1;
    }

    (11)打印输出·SeqListPrint

    该操作就是遍历输出一遍顺序表,比较简单!

    void SeqListPrint(SEQ* sl)
    {
    	assert(sl);
    	for (int i = 0; i < sl->size; i++)//遍历顺序表
    	{
    		printf("%d\t", sl->a[i]);
    	}
    }

     ✨✨✨我是分割线✨✨✨

    📝LeetCode之移除元素



    思路1-依次挪动数据覆盖

    思路:从前向后依次遍历找到数组中的元素,然后依次挪动后面的元素将其覆盖;重复此操作;用我们刚刚写的程序来描述就是,先使用SeqListFind找到对应元素,然后使用SeqListErase删除指定位置的元素,将此系列操作一直进行至遍历完整个数组。

    优点:简单易想。

    缺点:时间复杂度太大;最坏情况就是数组中所有元素都是需要删除的元素,此时时间复杂度达到了O(N^2)。


    思路2-拷贝到新数组

    思路:对原数组从前向后遍历,将不是val的值拷贝到新的数组中;最后再将新数组的元素拷贝回原数组,相当于对原数组进行了删除操作。

    优点:时间复杂度为O(N)。

    缺点:空间复杂度不符合要求,为O(N)。


    思路3-拷贝到新数组(双指针)

    思路:使用双指针,如果src指向的元素不为val,就将src指向的元素赋给dst,然后对src与dst同时++;当src指向的元素为val时,src++,dst不变;对上述2类操作一直重复至src遍历完整个数组,最终返回dst的值恰好就是有效数据的长度。

    例如下例中dst,表示数组下标[2],而有数据为[0,3]的长度也为2,因此返回dst的值就好比返回了有效数组的长度,进而相当于删除了原数组的后续元素。

    优点:时间复杂度为O(N);空间复杂度为O(1)。

    代码实现:

    int removeElement(int* nums, int numsSize, int val)
    {
        int src=0, dst=0;
        while(src<numsSize)
        {
            if(nums[src]!=val)
            {
                nums[dst]=nums[src];
                src++;
                dst++;
            }
            else
            {
                src++;
            }
        }
        return dst;
    }

    🌕写在最后


    数据结构的世界是相当丰富的,内容方向繁多,但只要一步一个脚印,跟随【水滴计划】水滴石穿吃透、搞懂、拿捏住数据结构是完全没有问题的!后期该系列还会有视频教程和经验分享,关于更多这方面的内容,请关注本专栏哦!

    热爱所热爱的, 学习伴随终生,kikokingzz与你同在!❥(^_-)

    展开全文
  • 图解顺序表+单链表

    千次阅读 2021-11-06 13:26:01
    文章目录一 图解顺序表顺序表的概念顺序表的实现1 抽象对应的类2 类的方法去实现顺序表2.1 顺序表的打印2.2 顺序表的新增元素2.3判定是否包含某个元素2.4 获取顺序表的长度2.5 查找某个元素对应的位置2.6 获取pos...
  • 顺序表各种接口实现
  • SqListDemo.c/* 线性表的顺序存储实现 */#include#include#include// 定义符号常量#define LIST_INIT_SIZE 50#define LISTINCREMENT 10#define OK 1#define ERROR 0#define OVERFLOW -2// ...// 定义顺序表类型type...
  • c语言实现顺序表的基本操作

    千次阅读 2021-05-23 11:53:27
    原作者:Step by Step经过三天的时间终于把顺序表的操作实现搞定了。(主要是在测试部分停留了太长时间)1;线性表顺序存储的概念:指的是在内存中用一段地址连续的存储单元依次存储线性表中的元素。2;采用的实现方式:...
  • 顺序表的常用操作实现及测试

    千次阅读 2021-10-24 00:58:36
    顺序表的常用操作实现及测试: 初始化并建立顺序表 顺序表初始值输入 按位置插入 按位置删除 按值查询 按位置修改 去除顺序表重复元素 顺序表排序 顺序表遍历及输出 合并两个有序顺序表 代码(C语言): /*动态...
  • Java实现顺序表及其常规操作

    千次阅读 2022-03-12 23:20:54
    打印顺序表 判断顺序表是是否已满 增加元素 指定位置插入元素 判断是否包含某个元素 按值查找元素 获取对应位置的元素 修改指定位置的值 删除元素 获取顺序表的长度 清空顺序表 完整代码 什么是顺序表...
  • 顺序表的基本操作(超详细)

    千次阅读 多人点赞 2021-10-15 20:52:22
    1.顺序表的定义 使用结构体来构造一个顺序表。 typedef struct { int length;//当前顺序表长度 int Maxsize;//顺序表最大长度 int* data;//定义顺序表中元素类型的数组指针 }SqList; 2.顺序表的初始化 顺序表的...
  • 数据结构初阶——顺序表

    千次阅读 多人点赞 2022-04-29 10:17:19
    博客写到这里,关于C语言的相关内容就告一段落了,从这篇开始,跟我一起进入一个全新的领域吧。把顺序表的代码放到了结尾。击鼓进军数据结构!!!
  • 线性表是一种在实际中广泛使用的数据结构,每个元素都有唯一的前去和唯一的后继,前一个元素没有前驱只有后继,最后一个元素没有后继只有前驱,常见的线性表:顺序表、链表、栈、队列、字符串。 数组不等于线性表,...
  • 数据结构-顺序表基本操作的实现(含全部代码)

    万次阅读 多人点赞 2018-09-13 22:14:57
    今天起开始编写数据结构中的各种数据结构及其算法的实现。 主要依据严蔚敏版数据结构教材以及王道数据结构...L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度为的顺序表 时间复杂度:O(n) InitList(SqList &...
  • 顺序表详解(C语言版)

    万次阅读 多人点赞 2020-09-27 22:44:24
    本文介绍了顺序表的定义和常见操作并使用C语言代码对其进行实现。
  • 超详细讲解数据结构之顺序表

    千次阅读 多人点赞 2022-03-14 19:32:42
    超详细讲解数据结构之顺序表顺序表概念静态顺序表动态顺序表动态循序表的概念及构造动态顺序表接口的实现检查顺序表的容量尾插与尾删头插与头删 顺序表 概念 顺序表是用一段物理地址连续的存储单元依次存储数据元素...
  • 顺序表的创建

    千次阅读 2021-04-25 19:34:54
    静态分配创建一个顺序表; 1.顺序表的定义: #define MaxSize 10 typedef struct { ElemType data[MaxSize]; int length; }SqlList; 这里我们用结构体的方式定义以一个顺序表;用静态数组存放数据元素;定义一个...
  • 顺序表和链表的区别

    千次阅读 2022-04-25 13:58:26
    顺序表 链表 存储空间 物理上一定连续 逻辑上连续,但物理上不一定连续 随机访问 支持O(1) 不支持:O(N) 任意位置插入或者删除元素 可能需要搬移元素,效率低O(N) 只需修改指针指向 ...
  • 一、顺序表(顺序存储) (一)、定义(如何用代码实现) 线性表是具有相同数据类型的n(n >= 0)个数据元素的有限序列。 顺序表:用顺序存储的方式实现线性表顺序存储。 把逻辑上相邻的元素存储在物理位置上也相邻...
  • 顺序表的基本操作(C语言实现,简单易懂!)

    万次阅读 多人点赞 2021-01-24 00:25:10
    一、学习内容:1、 创建顺序表 2、 按数值查找 3、 按位置查找 4、 插入一个数值 5、 删除一个数值 6、 销毁顺序表 7、 求前驱算法 8、 求后继算法
  • 数据结构--线性表与顺序表

    千次阅读 2020-12-08 11:24:31
    线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表指的是在逻辑上是线性结构,也就是指连续的一条直线。但在物理结构上并不一定是连续的,线性表在物理上存储时,...
  • 什么是顺序表

    万次阅读 2019-08-25 00:43:07
    顺序表 在程序中,经常需要将一组(通常是同为某个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等。一组数据中包含的元素个数可能发生变化(可以增加或删除元素)。 对于...
  • 文章目录(1)线性表(2)顺序表1)什么是顺序表2)顺序表的定义2)顺序表的接口实现1、初始化顺序表2、销毁(释放)顺序表3、检查顺序表容量是否满了,好进行增容3、顺序表尾插4、顺序表尾删5、顺序表头插6、顺序...
  • 将两个顺序表合并为一个新的顺序表

    千次阅读 多人点赞 2020-09-04 00:23:58
    问题描述:将两个有序顺序表合并为一个新的有序顺序表,并有函数返回结果顺序表。要求时间复杂度O(n) 算法设计思想:首先,按顺序取两个顺序表表头较小的结点存入新的线性表中直到某一个表遍历完;然后将还有剩余...
  • 顺序存储(顺序表)

    万次阅读 多人点赞 2018-08-25 11:56:23
    1.顺序存储方式 线性表的顺序存储结构,就是在内存中找到一块空间,通过占位的方式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空间中,既然线性表的每个数据元素的类型相同,所以C语言...
  • 目录一、数据结构1.1 算法与数据结构的区别二、顺序表2.1 顺序表的基本形式【重点】2.2 顺序表的两种基本实现方式【重点】1、一体式结构:2、分离式结构:2.3 元素存储区替换与扩充1. 元素存储区的替换2. 元素存储区...
  • 顺序表(C++实现)

    万次阅读 多人点赞 2019-04-07 14:15:02
    一、实现要求 ...(5)将顺序表L中的奇数项和偶数项结点分解开(元素值为奇数、偶数),分别放入新的顺序表中,然后原表和新表元素同时输出到屏幕上,以便对照求解结果。 (6)求两个递增有序...
  • 顺序表的操作实验(数据结构)

    千次阅读 2021-02-21 21:48:47
    顺序表的操作实验 一、实验名称和性质 二、实验目的 1.掌握线性表的顺序存储结构的表示和实现方法。 2.掌握顺序表基本操作的算法实现。 3.了解顺序表的应用。 三、实验内容 1.建立顺序表。 2.在顺序表上...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,673,653
精华内容 669,461
关键字:

顺序表