线性表是数据结构中的逻辑结构。线性表采用顺序存储的方式存储就称之为顺序表,数组是顺序表在实际编程中的具体实现方式之一,本篇主要介绍顺序表,顺序表的创建、添加元素、删除元素、遍历输出等操作。
1、创建顺序表
1.1定义顺序表结构体
结构体包含三个成员arr_base、cap、len。arr_base定义顺序表第一个元素的地址。Cap:定义顺序表可容纳元素的个数。Len:定义顺序表有效元素的个数。
typedef struct
{
int *arr_base; //定义顺序表的第一个元素的地址
int cap; //定义顺序表可容纳元素的个数
int len; //定义顺序表有效元素的个数
}Array,*PArray;
1.2 顺序表初始化函数
该函数需要输入最大容纳元素个数,初始化线性表指针、为顺序表数据段申请内存空间,定义结构体成员初始值,返回创建好线性表指针。
PArray Array_Init(int cap)
{
PArray parr = (PArray)malloc(sizeof(Array));
if(NULL == parr)
{
return NULL;
}
parr->arr_base = (int*)malloc(cap * sizeof(int));
if(NULL == parr->arr_base)
{
return NULL;
}
parr->cap = cap;
parr->len = 0;
return parr;
}
2、顺序表添加元素
2.1 顺序表追加元素
追加是在顺序表的最后添加元素,追加函数需要两个输入参数,线性表的指针(parr)和数据(data),主要完成两个功能,首先判断顺序表是否已满,如果没有满则添加元素,有效元素个数加1。
int Array_Append(PArray parr,int data)//最后添加元素
{
if(parr->len >= parr->cap)
{
return 0;
}
parr->arr_base[parr->len] = data;
parr->len++;
return 1;
}
2.2 顺序表插入元素
插入元素需要三个输入参数,线性表指针(parr)、插入的位置(pos)、数据(data),其中pos的范围为0<=pos<len。插入算法说明:
顺序表原始元素为 1,2,3此时len = 3,假设插入的位置pos = 0,data = 5;
首先将len (3)位置的元素替换为len-1(2)位置的元素:1,2,3,3
将len-1 (2)位置的元素替换为len-2(1)位置的元素:1,2,2,3
将len-2 (1)位置的元素替换为len-3(0)位置的元素:1,1,2,3
将pos位置的元素替换为data:5,1,2,3
最后有效元素个数加1。
int Array_Insert(PArray parr,int pos,int data)//pos范围是0到parr->len - 1
{
int i = 0;
if((pos < 0) || ((pos > parr->len - 1) && (parr->len > 0)) || (parr ->len == parr->cap))
{
return 0;
}
for(i = parr->len - 1;i >= pos;i--)
{
parr->arr_base[i + 1] = parr->arr_base[i];
}
parr->arr_base[pos] = data;
parr->len++;
return 1;
}
4、顺序表删除元素
删除元素需要两个输入参数,线性表指针(parr)、数据(data),首先根据数据查找数据的索引位置,最后根据索引位置删除元素。
4.1 查找数据返回元素所在的索引
循环遍历索引数据,如果查找到返回数据元素的索引值,如果没有查找返回-1,如果顺序表中有多个相同的数据,返回第一次找到数据元素的索引值。
int Array_Find(PArray parr,int data)//查找元素
{
int i = -1;
for(i = 0;i < parr->len;i++)
{
if(data == parr->arr_base[i])
{
break;
}
}
if(i == parr->len)
{
return -1;
}
return i;
}
4.2 删除元素
删除算法说明:
顺序表原始元素为 1,2,3此时len = 3,假设要删除的data = 1;
首先查找data返回元素所在的索引pos(0)
将pos (0)位置的元素替换为pos+1(1)位置的元素:2,2,3
将pos+1 (1)位置的元素替换为pos+2(2)位置的元素:2,3,3
最后有效元素个数减1:2,3
int Array_Delete(PArray parr,int data)
{
int i = 0;
int pos = Array_Find(parr,data);
if(pos < 0)
{
return 0;
}
if((pos < 0) || (pos > parr->len - 1) || (parr ->len == parr->cap))
{
return 0;
}
for(i = pos;i < parr->len - 1;i++)
{
parr->arr_base[i] = parr->arr_base[i + 1];
}
parr->len--;
return 1;
}
5、顺序表遍历输出
需要传入线性表的指针parr,从索引0开始一直到len-1,循环输出所有元素。
void Array_Print(PArray parr)
{
int i = 0;
for(;i < parr->len;i++)
{
printf("%d ",parr->arr_base[i]);
}
printf("\n");
}
6、全部代码
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int *arr_base; //定义顺序表的第一个元素的地址
int cap; //定义顺序表可容纳元素的个数
int len; //定义顺序表有效元素的个数
}Array,*PArray;
PArray Array_Init(int cap)
{
PArray parr = (PArray)malloc(sizeof(Array));
if(NULL == parr)
{
return NULL;
}
parr->arr_base = (int*)malloc(cap * sizeof(int));
if(NULL == parr->arr_base)
{
return NULL;
}
parr->cap = cap;
parr->len = 0;
return parr;
}
void Array_Print(PArray parr)
{
int i = 0;
for(;i < parr->len;i++)
{
printf("%d ",parr->arr_base[i]);
}
printf("\n");
}
int Array_Append(PArray parr,int data)//最后添加元素
{
if(parr->len >= parr->cap)
{
return 0;
}
parr->arr_base[parr->len] = data;
parr->len++;
return 1;
}
int Array_Insert(PArray parr,int pos,int data)//pos范围是0到parr->len - 1
{
int i = 0;
if((pos < 0) || ((pos > parr->len - 1) && (parr->len > 0)) || (parr ->len == parr->cap))
{
return 0;
}
for(i = parr->len - 1;i >= pos;i--)
{
parr->arr_base[i + 1] = parr->arr_base[i];
}
parr->arr_base[pos] = data;
parr->len++;
return 1;
}
int Array_Find(PArray parr,int data)//查找元素
{
int i = -1;
for(i = 0;i < parr->len;i++)
{
if(data == parr->arr_base[i])
{
break;
}
}
if(i == parr->len)
{
return -1;
}
return i;
}
int Array_Delete(PArray parr,int data)
{
int i = 0;
int pos = Array_Find(parr,data);
if(pos < 0)
{
return 0;
}
if((pos < 0) || (pos > parr->len - 1) || (parr ->len == parr->cap))
{
return 0;
}
for(i = pos;i < parr->len - 1;i++)
{
parr->arr_base[i] = parr->arr_base[i + 1];
}
parr->len--;
return 1;
}
int main()
{
PArray parr = NULL;
int cap = 20;
int i = 0;
parr = Array_Init(cap);
if(NULL == parr)
{
printf("内存分配失败\n");
}
for(i = 0;i < 10;i++)
Array_Append(parr,i);
Array_Print(parr);
Array_Insert(parr,0,-1);
Array_Print(parr);
Array_Delete(parr,-1);
Array_Print(parr);
return 0;
}
7、运行效果