建设通是个什么网站,美团网站建设,聊城网站空间公司,核桃少儿编程加盟#x1f307;个人主页#xff1a;平凡的小苏 #x1f4da;学习格言#xff1a;别人可以拷贝我的模式#xff0c;但不能拷贝我不断往前的激情 #x1f6f8;C语言专栏#xff1a;https://blog.csdn.net/vhhhbb/category_12174730.html #x1f680;数据结构专栏#xff… 个人主页平凡的小苏 学习格言别人可以拷贝我的模式但不能拷贝我不断往前的激情 C语言专栏https://blog.csdn.net/vhhhbb/category_12174730.html 数据结构专栏https://blog.csdn.net/vhhhbb/category_12211053.html 家人们更新不易你们的点赞和⭐关注⭐真的对我真重要各位路过的友友麻烦多多点赞关注欢迎你们的私信提问感谢你们的转发 关注我关注我关注我你们将会看到更多的优质内容 目录
1、顺序表概念
2、函数接口的实现
2.1、顺序表的初始化
2.2、顺序表的插入操作
2.3、顺序表的删除操作
2.4、顺序表的插入和删除的时间复杂度
2.5、线性表的顺序存储结构的优缺点
2.6、顺序表的查找
2.7、顺序表的销毁
3、顺序表源码
SList.c
SList.h
Test.c 1、顺序表概念 线性表的顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素 线性表的存储结构说白了就是在内存中找块地儿通过占位的形式把一块内存空间给占了然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据都相同所以可以用C语言其他语言也相同的一维数组来实现顺序存储结构即把第一个数据元素存到数组下标为0的位置中接着把线性表相邻的元素存储在数组中相邻的位置。
2、函数接口的实现 来看线性表顺序存储的结构代码。
#include stdio.h
#include assert.h
#include stdlib.h
#define InitCapa 4;//初始容量
typedef int SLDateType;
typedef struct SeqList
{SLDateType* a; //动态分配数组存储数据元素int size;//数组元素个数int capacity;//数组容量的大小
}SeqList;
2.1、顺序表的初始化
void SeqListInit(SeqList* ps)
{assert(ps);ps-a (SLDateType*)malloc(sizeof(SLDateType) * 4);ps-size 0;ps-capacity InitCapa;
} 注顺序表的初始化首先要动态分配容量为4的数组。数组元素的个数初始化为0. 2.2、顺序表的插入操作 我们现在来考虑如果要实现线性的插入操作即在顺序表的第i个位置插入新元素e应该如何操作 举个栗子本来我们在春运时去买火车票大家都排队排的好好的。这时来了一个抱着孩子的年轻妈妈对着队伍中排在第三位的你说“大哥求求你帮帮忙我家里母亲有病我得急着回去看她你看我还抱着孩子这队伍这么长你可否让我排在你的前面你心一软就同意了。这时你必须得退后一步。骂声四起。但后面得人不清楚这加塞是怎么回事没什么办法。 这个例子已经说明了线性表得顺序存储结构在插入数据时得实现过程如下图所示 实现代码如下
void CheckCapacity(SeqList* ps)
{if (ps-size ps-capacity){SLDateType* tmp (SLDateType*)realloc(ps-a,sizeof(SLDateType) * ps-capacity * 2);if (tmp NULL){perror(realloc fail:);exit(-1);}ps-capacity * 2;ps-a tmp;}
}
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{assert(ps);CheckCapacity(ps);//检查容量函数只要是插入元素得操作都应该检查容量int end ps-size-1;while (end pos)//每个元素往后移动{ps-a[end 1] ps-a[end];end--;}ps-a[pos] x;ps-size;
} 插入算法得思路 1如果顺序表得长度大于等于数组长度则动态增加容量 2从最后一个元素开始向前遍历到第i个位置分别将它们都向后移动一个位置 3将要插入得元素填入位置i处 4表长加1 2.3、顺序表的删除操作 接着刚才的栗子。此时后面的人群意见都很大都说怎么可以这样不管什么原因插队就是不行有本事找火车站开后门去。就在这时远处跑来一胖子对着这个美女喊可找到你了你这个骗子还我钱。只见女子二话不说突然就冲出了队伍胖子追在其后。哦原来她是倒卖火车票的黄牛刚才还在装可怜。于是排队的人群又像蠕虫一样都向前移动了一步骂声渐息队伍又恢复了平静。 这就是顺序表的顺序存储结构的删除元素的过程实现如下图所示 实现代码如下
void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(ps-size);//如果容量为0就抛出异常不可以再删除int begin pos;while (begin ps-size-1){ps-a[begin] ps-a[begin 1];begin;}ps-size--;
} 删除算法的思路 1从删除元素位置开始遍历到最后一个元素位置分别将它们都向前移动一个位置 2表长减1 2.4、顺序表的插入和删除的时间复杂度 先看最好的情况如果元素要插入到最后一个位置或者删除最后一个元素时的时间复杂度为O(1)因为不需要移动元素。最坏的情况呢如果元素要插入到第一个位置或者删除第一个元素此时的时间复杂度是多少呢这就意味着要移动所有的元素向后或者向前所以这个时间复杂度为O(n).
2.5、线性表的顺序存储结构的优缺点
优点
无需为表示表中的元素之间的逻辑关系而增加额外的存储空间可以快速地存取表中任意位置的元素
缺点
插入和删除的操作需要移动大量的元素
2.6、顺序表的查找
实现代码如下
int SeqListFind(SeqList* ps, SLDateType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-a[i] x){return i;}}return -1;
} 注就是遍历查找的过程 2.7、顺序表的销毁 实现代码如下
void SeqListDestroy(SeqList* ps)
{assert(ps);free(ps-a);ps-size ps-capacity 0;ps-a NULL;
}
3、顺序表源码
SList.c
//SList.c
#includeSList.h
void SeqListInit(SeqList* ps)
{assert(ps);ps-a (SLDateType*)malloc(sizeof(SLDateType) * 4);ps-size 0;ps-capacity InitCapa;
}void CheckCapacity(SeqList* ps)
{if (ps-size ps-capacity){SLDateType* tmp (SLDateType*)realloc(ps-a,sizeof(SLDateType) * ps-capacity * 2);if (tmp NULL){perror(realloc fail:);exit(-1);}ps-capacity * 2;ps-a tmp;}
}
void SeqListPushBack(SeqList* ps, SLDateType x)
{assert(ps);CheckCapacity(ps);ps-a[ps-size] x;ps-size;
}
void SeqListPopBack(SeqList* ps)
{assert(ps-size);ps-size--;
}
void SeqListPopFront(SeqList* ps)
{//assert(ps);//assert(ps-size);//int begin 0;//int end 1;//while (end ps-size)//{// ps-a[begin] ps-a[end];// begin;// end;//}//ps-size--;SeqListErase(ps, 0);
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{//assert(ps);//CheckCapacity(ps);//int end ps-size;//int begin ps-size - 1;//while (begin 0)//{// ps-a[end] ps-a[begin];// begin--;// end--;//}//ps-a[0] x;//ps-size;SeqListInsert(ps, 0, x);
}
int SeqListFind(SeqList* ps, SLDateType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-a[i] x){return i;}}return -1;
}
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{assert(ps);CheckCapacity(ps);int end ps-size-1;while (end pos){ps-a[end 1] ps-a[end];end--;}ps-a[pos] x;ps-size;
}
void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(ps-size);int begin pos;while (begin ps-size-1){ps-a[begin] ps-a[begin 1];begin;}ps-size--;
}
void SeqListPrint(SeqList* ps)
{for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}void SeqListDestroy(SeqList* ps)
{assert(ps);free(ps-a);ps-size ps-capacity 0;ps-a NULL;
}
SList.h
#pragma once
#include stdio.h
#include assert.h
#include stdlib.h
#define InitCapa 4;
typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;// 对数据的管理:增删查改
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos); 注这里的尾插、头插、尾删、头删都是插入删除函数的复用 Test.c #includeSList.h
void TestSList()
{SeqList SL;SeqListInit(SL);SeqListPushBack(SL, 1);SeqListPushBack(SL, 2);SeqListPushBack(SL, 3);SeqListPushBack(SL, 4);SeqListPrint(SL);SeqListInsert(SL, 1, 5);SeqListInsert(SL, 1, 6);SeqListPrint(SL);SeqListDestroy(SL);
}
int main()
{TestSList();return 0;
} 好了小编的分享到这里就结束了想要继续了解数据结构的知识的敬请期待博主的更新有什么不足的地方请各位大佬多多指教
