SeqList InitList(); // 初始化线性表
void DestroyList(); // 销毁线性表
void ClearList(); // 清空线性表
int ListEmpty(); // 判断线性表是否为空
int ListLength(); // 求线性表的长度
void Travel(); // 遍历线性表
int ListInsert(); // 向线性表插入元素
int ListDelete(); // 从线性表删除元素
int GetElem(); // 找到线性表指定位置的元素值
int LocateElem(); // 找到线性表指定元素值的位置
顺序表是有插入和删除操作的,所以顺序表的长度是变化的,而 C语言中的数组是定长 的,那么该如何用数组实现顺序表呢? 我们可以定义一个变量来表示顺序表的长度,当顺序表长度变化时,只需相应地更改该变量即可。
#include "stdio.h"
#include "malloc.h"
#define MAXSIZE 100 // 顺序表的最大存储量
#define TRUE 1
#define FALSE 0
typedef int ElemType; // 顺序表存储元素的数据类型
// 定义顺序表结构体
typedef struct SeqList{
ElemType elems[MAXSIZE];
int len; // 当前顺序表的长度
}*SeqList;
*SeqList
是结构体类型指针,这里指的就是顺序表的地址。
#define MAXSIZE 100
宏定义顺序表的最大存储量,更方便改顺序表的存储大小,耦合性低。
typedef int ElemType;
自定义顺序表元素类型的,看起来 ElemType 和 int 是一样的,为什么不直接用 int,要用 ElemType。
Because:
定义不同的数据类型名称是为了提高程序的 高内聚,低耦合 ,而且一旦你需要将数据类型变换其他类型比如使用char类型的了,
只要写:typedef char ElemType;
一下子就全改了,如果没有定义的话就要一个个的把 int 改成 char,你不嫌麻烦么。
// 初始化顺序表
SeqList InitList(){
SeqList list = (SeqList)malloc(sizeof(struct SeqList)); // 分配顺序表内存大小
list -> len = 0; // 顺序表的初始长度
return list;
}
有初始化操作肯定就会有销毁,销毁无用的资源是一个好习惯。 如果使用静态数组实现的顺序表,我们无需手动释放资源,因为程序结束后系统会自动释放内存;而如果使用动态内存分配实现的顺序表,就需要我们手动释放内存,实现如下:
#include "stdio.h"
#include "malloc.h"
#define MAXSIZE 100 // 顺序表的最大存储量
#define TRUE 1
#define FALSE 0
typedef int ElemType; // 顺序表存储元素的数据类型
// 定义顺序表结构体
typedef struct SeqList{
ElemType *elems;
int len; // 当前顺序表的长度
}*SeqList;
// 初始化顺序表
SeqList InitList(){
SeqList list;
list -> elems = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE); // 分配顺序表内存大小
list -> len = 0; // 顺序表的初始长度
return list;
}
// 销毁顺序表
void DestroyList(SeqList list){
if(list -> elems != NULL){
free(list -> elems); //释放动态数组内存
}
list -> elems = NULL;
printf("释放动态数组内存\n");
}
int main(int argc, char const *argv[])
{
SeqList list = InitList();
printf("list -> len:%d\n", list -> len);
DestroyList(list);
printf("list -> elems地址:%p\n", list -> elems);
return 0;
}
程序运行结果
list -> len:0
释放动态数组内存
list -> elems地址:00000000
请按任意键继续. . .
// 清空顺序表
void ClearList(SeqList list){
list -> len = 0; // 将顺序表的长度置为 0
}
// 顺序表判空
int ListEmpty(SeqList list){
if(list == NULL) return FALSE;
return list -> len == 0;
}
只需要判断顺序表的长度是否为0, 0则空反之有元素。
// 获取顺序表的长度
int GetLen(SeqList list){
return list -> len;
}
// 遍历顺序表
void Travel(SeqList list){
for(int i=0;i<list -> len;i++){
printf("%d\t", list -> elems[i]);
}
printf("\n");
}
顺序表的插入算法思想如下:
/*
* 指定位置在顺序表插入元素
* pos 逻辑下标 (1, 2, 3, ...)
* elem 要插入顺序表的元素
*/
int ListInsert(SeqList list, int pos, ElemType elem){
// 判断插入位置是否合理
if(pos <= 0 || pos > list -> len + 1){
return FALSE;
}
// 判断顺序表是否已满
if(list -> len == MAXSIZE){
return FALSE;
}
// 元素后移
for(int i=list -> len;i>= pos;i--){
// 1 [2] 3 4 5
list -> elems[i] = list -> elems[i-1];
}
// 元素插入
list -> elems[pos - 1] = elem;
list -> len ++; // 记得更新顺序表长度
return TRUE;
}
注意:元素后移是从顺序表最后一个元素开始移动
假设顺序表容量为6,MAXSIZE = 6
顺序表的长度为4,len = 4
在顺序表第5个位置插入元素5,pos = 5 、elem = 5
由于len < pos --> 4 < 5
所以for循环条件不满足
直接插入elems[pos - 1] = elem; --> elems[4] = 5
假设顺序表容量为6,MAXSIZE = 6
顺序表的长度为4,len = 4
在顺序表第2个位置插入元素5,pos = 2 、elem = 5
从顺序表最后一个元素开始移动后
移动过程
1、elems[4] = elems[4 - 1]; --> elems[4] = elems[3]
2、elems[3] = elems[3 - 1]; --> elems[3] = elems[2]
3、elems[2] = elems[2 - 1]; --> elems[2] = elems[1]
元素插入后
elems[pos - 1] = elem; --> elems[1] = 5
顺序表的删除算法思想如下:
/*
* 指定位置在顺序表删除元素
* pos 逻辑下标 (1, 2, 3, ...)
* val 用来保存删除元素的值
*/
int ListDelete(SeqList list, int pos, ElemType *val){
// 判断删除位置是否合法
if(pos <= 0 || pos > list -> len){
return FALSE;
}
*val = list -> elems[pos - 1]; // 先保存要删除元素的值
// 元素前移
for(int i=pos - 1;i<list -> len;i++){
list -> elems[i] = list -> elems[i + 1];
}
list -> len --; // 记得更新顺序表长度
return FALSE;
}
假设顺序表容量为6,MAXSIZE = 6
顺序表的长度为4,len = 5
删除顺序表第2个位置的元素,pos = 2
元素向前移动过程
1、elems[1] = elems[1 + 1]; --> elems[1] = elems[2];
2、elems[2] = elems[2 + 1]; --> elems[2] = elems[3];
3、elems[3] = elems[3 + 1]; --> elems[3] = elems[4];
/*
* 查找指定位置的顺序表元素
* pos 逻辑下标 (1, 2, 3, ...)查找的位置
* val 用来保存元素的值
*/
int GetElem(SeqList list, int pos, ElemType *val){
// 判断位置是否合理
if(pos <= 0 || pos > list -> len){
return FALSE;
}
*val = list -> elems[pos - 1];
return TRUE;
}
/*
* 查找顺序表指定元素的位置(第一个匹配成功的元素位置)
* elem 要查找的元素
* pos 逻辑下标 (1, 2, 3, ...)用来保存元素的位置
*/
int LocateElem(SeqList list, ElemType elem, int *pos){
for(int i=0;i<list -> len;i++){
if(list -> elems[i] == elem){ // 判断元素是否相等
*pos = i + 1; // 通过指针把逻辑下标返回
return TRUE;
}
}
return FALSE; // 没找到返回FAlSE
}
源代码已上传到 GitHub Data-Structure-of-C,欢迎大家下载 C语言实现数据结构