数据结构之顺序表的实现
2020-04-06 16:00:56来源:博客园 阅读 ()
数据结构之顺序表的实现
数据结构,顺序表数据结构之顺序表的实现
一、原理
1.定义
顺序表是在计算机中以数组形式保存的。
2.特点
-
在计算机中占用连续的一段内存
-
一旦声明,空间大小一般不变
二、初始化相关操作
包括:
- 结构体的定义
- 顺序表的创建
- 顺序表清空
- 判断顺序表是否为空
1.结构体定义
即定一个满足顺序表定义的结构体,其中包含 数组、存储长度、总长度。
typedef int ElemType; //将int抽象为ElemType,表明顺序表也可以存储其他类型(如将int改为char)
struct List
{
ElemType *list;
//声明数组用于给顺序表存储数据,等价于以下声明方式
//ElemType[] list;
int length; //用于记录顺序表存储的数据长度
int MaxSize; //用于记录顺序表最大长度(即最多存储数据)
}
2.初始化
对顺序表进行初始化,包括分配自定义长度的数组空间,设定存储长度为0,存储长度为规定值
//初始化,传入需要初始化的顺序表和初始化长度
void InitList(struct List *L,int maxSize){
//初始化长度合法性判断
if(maxSize<0){
printf("初始化长度非法!\n");
exit(1); //退出程序
}
//对顺序表长度进行赋值
L->MaxSize = maxSize;
//根据初始化长度和存储数据类型来动态分配数组
L->list = malloc(sizeof(maxSize*sizeof(ElemType)));
//分配成功判定
if(!L->list){
printf("动态分配存储失败\n");
exit(1);
}
//初始化存储数据为0个
L->length = 0;
}
3.清空
将顺序表内容清空,用于某些题目要求或节省空间
//清空,传入需要清空的顺序表
void ClearList(struct List *L){
//判断顺序表是否已经为空
if(L->list!=NULL){
free(L->list); //释放顺序表中数组内存
L->list = 0;
L->length = 0;
L->MaxSize = 0;
}
}
4. 判断是否为空
判断顺序表是否为空,在某些操作之前,先要判断顺序表是否为空,防止出错
int isEmpty(struct List *L){
return L->length==0?1:0; //顺序表最大长度为0则为空返回1,否则返回0
}
三、增加相关操作
包括:
- 向表头插入元素x
- 向表尾插入元素x
- 向第n个位置插入元素x
- 向递增的线性表中插入元素x,之后仍然保持有序
进行操作之前,还需要一个方法,当插入元素超过数组长度时,将数组容量扩大,即重新申请空间
Tip:将顺序表扩大一倍空间
void ReMalloc(struct List *L){
ElemType *p = realloc(L->list,2*L->MaxSize*sizeof(ElemType));
if(!p){
printf("空间分配失败\n");
exit(1);
}
L->list = p; //使list重新指向新生成的空间
L->MaxSize = 2*L->MaxSize;
printf("存储空间已经扩大为2倍\n");
}
1.向表头插入元素x
void insertElemToHead(struct List *L,ElemType x){
int i;
//判断存储空间是否已满
if(L->length==L->MaxSize){
printf("存储空间已满,重新分配中...");
ReMalloc(L);
}
//所有元素后移
for(i=L->length;i>0;i--){
L->list[i+1]=L->list[i];
}
L->list[i]=x;
L->length++;
}
2.向表尾插入元素x
void insertElemToTail(struct List *L,ElemType x){
//判断存储空间是否已满
if(L->length==L->MaxSize){
printf("存储空间已满,重新分配中...");
ReMalloc(L);
}
L->list[L->length++]=x;
}
3.向线性表L的第n个位置插入元素x
void insertElemSomewhere(struct List *L,ElemType x,int n){
//判断存储空间是否已满
if(L->length==L->MaxSize){
printf("存储空间已满,重新分配中...");
ReMalloc(L);
}
int i;
for(i=L->length;i>=n;i--){
L->list[i] = L->list[i-1];
}
L->list[i] = x;
L->length--;
}
四、删除相关操作
包括:
-
删除表头元素并返回被删除的值
-
删除第n个元素并返回被删除元素
-
从线性表L中删除值为X的第一个元素
1.删除表头元素并返回被删除的值
删除表头第一个元素,长度减少1,返回被删除的值
ElemType delHeadElem(struct List *L){
ElemType x = L->list[0];
//合法性判断
if(L->length==0){
printf("线性表为空,不能删除\n");
exit(1);
}
for(int i=0;i<L->length;i++){
L->list[i] = L->list[i+1];
}
L->length--;
return x;
}
2.删除第n个元素并返回被删除元素
ElemType delSomeElem(struct List *L,int n){
if(n<L->length){
printf("n位置越界,不能删除");
exit(1);
}
ElemType x = L->list[n-1];
for(int i=n;i<L->length;i++){
L->list[i]=L->list[i+1];
}
L->length--;
retur x;
}
3.从线性表L中删除值为X的第一个元素
从线性表L中删除值为X的第一个元素,若删除成功则返回1,否则返回0
int delElemKnown(struct List *L,ElemType x){
int i,j;
//先找出值为X的下标
for(i=0;i<L->length;i++){
if(L->list[i]==x){
break;
}
}
for(j=i;i<L->length;j++){
L->list[j]=L->list[j+1];
}
L->length--;
return 1;
}
五、修改相关操作
包括:
- 把线性表中第n个元素修改为x
1.把线性表中第n个元素修改为x
把线性表中第n个元素修改为x,若成功则返回1,失败返回0
int updateElemKnown(struct List *L,ElemType x,int n){
if(n>L->length||n<1){
return 0;
}
L->list[n]=x;
return 1;
}
六、查找相关操作
包括:
-
查找第n个位置的值
-
顺序遍历输出所有值
-
返回值等于x的下标
1.查找第n个位置的值
输入要查找的坐标,若合法则范围对应的值,若非法则提示并推出
int getElem(struct List *L,int n){
if(n<0||n>L->MaxSize){
printf("查找位置超出长度!\n");
exit(1);
}
return L->list[n-1]; //n-1的原因是查找的第n个是从1开始计数,而数组是从0开始计数
}
2.顺序遍历输出所有值
输出顺序表中的所有值
void getAll(struct List *L){
int i = 0;
while(i<L->length){
printf(L->list[i]+"\t");
i++;
}
printf("\n");
}
3.查找值为x的节点并返回其坐标
输入要查找的值x,若存在则范围首次出现的下标,否则返回0
void findElem(struct List *L,ElemType x){
int i;
for(i=0;i<L->length;i++){
if(L->list[i]==x){
return i;
}
}
}
七、总结
1.优点
- 查找方便
- 空间利用率高
2.缺点
- 删除和增加操作效率低
- 空间固定,不易扩展
八、完整代码
#include "stdio.h"
#include <stdlib.h>
/**
* =======顺序表的定义=========
*/
typedef int ElemType;
//结构体定义
struct List{
ElemType *list;//存储数据
int length;//存储长度
int MaxSize;//最大长度
};
//初始化
void initList(struct List *L,int maxSize){
//初始化长度合法性判断
if(maxSize<0){
printf("初始化长度非法!\n");
exit(1); //退出程序
}
L->MaxSize = maxSize;
L->list = malloc(sizeof(maxSize* sizeof(ElemType)));
//判断分配空间是否成功
if(!L->list){
printf("空间分配失败");
exit(1);
}
L->length=0;
}
//清空
void clearList(struct List *L){
if(L->list!=NULL){
free(L->list);
L->list=0;
L->MaxSize=0;
L->length=0;
}
}
//判空
int isEmpty(struct List *L){
return L->length==0?1:0;
}
/**
* =======增加操作=========
*/
//空间再分配
void reMalloc(struct List *L){
ElemType *p = realloc(L->list,2*L->MaxSize* sizeof(ElemType));
if(!p){
printf("空间分配失败");
exit(1);
}
L->list = p;
L->MaxSize = 2*L->MaxSize;
printf("空间已扩大两倍");
}
//向表头插入元素
void insertElemToHead(struct List *L,ElemType x){
if(L->length==L->MaxSize){
reMalloc(L);
printf("空间已满,重新分配中");
}
for(int i=L->length;i>0;i++){
L->list[i-1] = L->list[i];
}
L->list[0] = x;
L->length++;
}
//向表尾插入元素
void insertElemToTail(struct List *L,ElemType x){
if(L->length==L->MaxSize){
reMalloc(L);
printf("空间已满,重新分配中");
}
L->list[L->length++] = x;
}
//向线性表L的第n个位置插入元素x
void insertElemSomewhere(struct List *L,ElemType x,int n){
int i;
if(L->length==L->MaxSize){
reMalloc(L);
printf("空间已满,重新分配中");
}
for(i=L->length;i>=n;i--){
L->list[i]=L->list[i-1];
}
L->list[i]=x;
L->length++;
}
/**
* =======删除操作=========
*/
//删除表头元素并返回被删除的值
void delHeadElem(struct List *L){
ElemType x = L->list[0];
if(L->length==0){
printf("顺序表为空,删除失败!");
exit(1);
}
for(int i=1;i<L->length;i++){
L->list[i-1] = L->list[i];
}
L->length--;
}
//删除第n个元素并返回被删除元素
ElemType delSomeElem(struct List *L,int n){
ElemType x = L->list[n-1];
if(n>L->length){
printf("n位置越界,不能删除");
exit(1);
}
for(int i=n;i<L->length;i++){
L->list[i-1] = L->list[i];
}
L->length--;
return x;
}
//从线性表L中删除值为X的第一个元素
int delElemKnown(struct List *L,ElemType x){
int i,j;
for(i=0;i<L->length;i++){
if(L->list[i]==x){
break;
}
}
for(j=i;j<L->length;j++){
L->list[j]=L->list[j+1];
}
L->length--;
return 1;
}
/**
* =======修改操作=========
*/
//把线性表中第n个元素修改为x
int updateElemKnown(struct List *L,ElemType x,int n){
if(n>L->length||n<1){
return 0;
}
L->list[n]=x;
return 1;
}
/**
* =======查找操作=========
*/
//查找第n个位置的值
int getElem(struct List *L,int n){
if(n<0||n>L->MaxSize){
printf("查找位置超出长度!\n");
exit(1);
}
return L->list[n-1]; //n-1的原因是查找的第n个是从1开始计数,而数组是从0开始计数
}
//顺序遍历输出所有值
void getAll(struct List *L){
int i = 0;
while(i<L->length){
printf("%d\t",L->list[i]);
i++;
}
printf("\n");
}
//查找值为x的节点并返回其坐标
int findElem(struct List *L,ElemType x){
int i;
for(i=0;i<L->length;i++){
if(L->list[i]==x){
return i;
}
}
}
//主函数
int main()
{
//初始化操作测试
struct List L;
initList(&L,20);
//插入操作测试
insertElemToHead(&L,2);
insertElemSomewhere(&L,4,2);
insertElemToTail(&L,5);
printf("%d\n",L.list[0]);
printf("%d\n",L.list[1]);
//删除操作测试
delElemKnown(&L,2);
printf("%d\n",L.list[0]);
//修改操作测试
updateElemKnown(&L,8,1);
//查找操作测试
printf("%d\n",getElem(&L,2));
printf("%d\n",findElem(&L,8));
printf("%d\n",L.list[0]);
getAll(&L);
}
原文链接:https://www.cnblogs.com/Mayberichard/p/12642770.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- 数据结构—链表 2020-05-29
- opencv-12-高斯滤波-双边滤波(附C++代码实现) 2020-05-10
- 图 2020-05-02
- 二叉排序树 2020-05-02
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash