当前位置: 首页 > >

用C语言实现数据结构??顺序表(线性表)

发布时间:

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表。特点:地址连续。


介绍几个函数

1.:
(1) malloc() : 申请空间


Array *temp = (Array *)malloc(sizeof(Array));

(2) free() : 释放空间


/*
Function name : destroyArray
Description : 销毁顺序表
Parameter :
@arr:顺序表结构体
return : 1成功,其他失败
*/
int destroyArray(Array *arr)
{
if (arr != NULL)/*结构体有空间*/
{
if (arr->data != NULL)/*动态数组有空间*/
{
free(arr->data);
}
free(arr);
return 1;
}
return 0;
}

(3) realloc() : 重新申请空间(扩大空间),原理就是申请一段空间后,将原有数据赋值进去,并且扩大空间。


arr->data = (Type *)realloc(arr->data, (arr->size + 5)*sizeof(Type));/*增加5个空间*/

2.
assert() : 断言,如果括号中的参数为空,就报错,相当于一个if,如果有空间,不管,如果没空间,就报错。


assert(temp);/*若空间申请失败则报错*/

完整代码、注释和运行结果:

/*********************************************
@File name : MyArr.c
@Author : StudyCcYa
@Version : 1.0
@Date : 2020-11-06
@Description : 用c语言实现数据结构??顺序表
********************************************/
#include
#include
#include
#define MAX 20/*顺序表的大长度*/

typedef int Type;

/*顺序表的结构体*/
typedef struct Array
{
Type *data; /*动态数组*/
int length; /*顺序表当前的长度*/
int size; /*顺序表的最大长度*/
}Array;

/*函数声明*/
Array *creatArray();/*创建一个空的顺序表*/
int insertArray(Array *arr, int i, Type elem);/*指定位置插入数据*/
int deleteElem(Array *arr, int i);/*删除指定位置数据*/
Type getElem(Array *arr, int i);/*查找指定位置数据*/
int changeElem(Array *arr, int i, Type elem);/*修改指定位置数据*/
int isEmpty(Array *arr);/*判断是否为空表*/
int destroyArray(Array *arr);/*销毁顺序表*/
int printfArray(Array *arr);/*输出顺序表*/


/*
Function name : creatArray
Description : 创建一个空的顺序表
Parameter : 无
return : temp成功,其他失败
*/
Array *creatArray()
{
Array *temp = (Array *)malloc(sizeof(Array));/*给结构体申请空间*/
assert(temp);/*若空间申请失败则报错*/
temp->data = (Type *)malloc(sizeof(Type)*MAX);/*给动态数组申请空间*/
assert(temp->data);
temp->length = 0;/*当前长度为0*/
temp->size = MAX; /*最大长度为MAX*/
return temp;
}

/*
Function name : insertArray
Description : 给顺序表指定位置插入数据
Parameter :
@*arr:顺序表结构体
@i :要插入的位置
@elem:要插入的数据
return : 1插入成功 其他失败
*/
int insertArray(Array *arr, int i, Type elem)
{
if (i<0 || i>arr->length + 1) return 0;/*插入位置不合法*/
if (arr->length >= arr->size)/*空间不足*/
{
arr->data = (Type *)realloc(arr->data, (arr->size + 5)*sizeof(Type));/*增加5个空间*/
assert(arr->data);
arr->size += 5;/*最大空间相应要增加*/
}

for (int k = arr->length - 1; k >= i - 1; k--)
{
arr->data[k + 1] = arr->data[k];/*所有元素后移一位*/
}
arr->data[i-1] = elem;/*插入*/
arr->length++;/*长度+1*/
return 1;
}

/*
Function name : deleteElem
Description : 删除指定位置的数据
Parameter :
@arr : 顺序表结构体
@i : 删除的位置
return : 1删除成功,其他失败
*/
int deleteElem(Array *arr, int i)
{
if (i < 1 || i>arr->length) return 0;/*删除位置不合法*/
for (int k = i - 1; k < arr->length - 1; k++)
{
arr->data[k] = arr->data[k + 1];/*所有元素前移一位*/
}
arr->length--;/*长度-1*/
return 1;
}

/*
Function name : getElem
Description : 查找指定位置数据
Parameter :
@arr : 顺序表结构体
@i : 查找的位置
return : Type成功,其他失败
*/
Type getElem(Array *arr, int i)
{
if (i < 1 || i>arr->length) return 0;/*查找位置不合法*/
return arr->data[i - 1];
}

/*
Function name : changeElem
Description : 修改指定位置数据
Parameter :
@arr : 顺序表结构体
@i : 修改的位置
@elme: 改变成的数据
return : 1成功,其他失败
*/
int changeElem(Array *arr, int i,Type elem)
{
if (i<1 || i>arr->length) return 0;/*修改位置不合法*/
arr->data[i - 1] = elem;
return 1;
}

/*
Function name : isEmtpy
Description : 判断是否为空表
Parameter :
@arr : 顺序表结构体
return : 1是空表,0不是空表
*/
int isEmpty(Array *arr)
{
if (arr == NULL || arr->length == 0)
return 1;
return 0;
}

/*
Function name : destroyArray
Description : 销毁顺序表
Parameter :
@arr:顺序表结构体
return : 1成功,其他失败
*/
int destroyArray(Array *arr)
{
if (arr != NULL)/*结构体有空间*/
{
if (arr->data != NULL)/*动态数组有空间*/
{
free(arr->data);
}
free(arr);
return 1;
}
return 0;
}

/*
Function name : printfArray
Description : 输出顺序表
Parameter :
@arr:顺序表结构体
return : 1成功,其他失败
*/
int printfArray(Array *arr)
{
if (!isEmpty(arr))
{
for (int i = 0; i < arr->length; i++)
{
printf("%d ",arr->data[i]);
}
printf("
");
return 1;
}
return 0;
}

int main()
{
Array *arr = creatArray();
for (int i = 1; i <= 10; i++)
{
insertArray(arr, i, i);
}
printfArray(arr);

insertArray(arr, 3, 99);/*第3个位置插入99*/
printfArray(arr);

deleteElem(arr, 3);/*删掉第3个位置的数据*/
printfArray(arr);

printf("%d
", getElem(arr, 5));/*查找第5个位置的数据*/

changeElem(arr, 4, 55);/*第4个位置的数据修改为55*/
printfArray(arr);

return 0;
}


运行成功。实现的功能就是基本的增删查改。


笔者的话

由于顺序表这个数据结构很简单,没有什么要说的,说白了就是一个数组,只是这个数组的所有操作都要你通过代码来实现,注释标的很清晰,如果有任何不足或者不懂的地方,欢迎指正和讨论,这是笔者第一次写博客,后续会将所有的数据结构用c语言和java语言实现。



友情链接: