list.cpp 具体函数实现
#include <stdio.h>
#include "list.h"
#include <malloc.h>
/**************************************************
①函数名: CreateList
功 能: 用数组构建顺序表
参 数: ①SqList *&L:传入的线性表 ②ElemType a[]:使用的数组
③int n: 线性表的长度(n < Maxsize)
返回值: 无
**************************************************/
void CreateList(SqList *&L, ElemType a[],int n)
{
int i;
//分配空间
L = (SqList*)malloc(sizeof(SqList));
for(i = 0; i<n; i++)
{
L->data[i] = a[i];
}
L->length = n;
}
/**************************************************
②函数名: InitList
功 能: 初始化线性表,重新分配空间,长度清成零
参 数: ①SqList *&L:要进行初始化的线性表
返回值: 无
**************************************************/
void InitList(SqList *&L)
{
L = (SqList*)malloc(sizeof(SqList)); //既然初始化了,直接重新分配空间
L->length = 0;
}
/**************************************************
③函数名: DispalyList
功 能: 输出数组线性表到控制台
使用场景: 调试输出专用
参 数: ①SqList *L:所需展示的顺序表
返回值: void
**************************************************/
void DispalyList(SqList *L)
{
if(L->length == 0) return;
for(int i = 0; i< L->length; i++)
{
printf("%d ",L->data[i]);
}
printf("\n");
}
/**************************************************
④函数名: ListEmpty
功 能: 判断顺序表是否为空
参 数: ① SqList *L: 需要判断的顺序表
返回值: (bool类型) 是空表 ? 返回1 : 不是返回0
**************************************************/
bool ListEmpty(SqList *L)
{
return(L->length == 0);
}
/**************************************************
⑤函数名 : DestroyList
功 能: 释放顺序表空间
参 数: ① SqList *&L: 所需释放的线性表的指针地址
注 意: (1)
返回值: 无
**************************************************/
void DestroyList(SqList *&L) //(1)注意是指针地址
{
//c语言, 直接free
free(L);
}
/**************************************************
⑥函数名:ListLength
功 能: 返回顺序表长度
参 数: ① SqList *L:传入顺序表的名字
返回值: int: 线性表长度值
**************************************************/
int ListLength(SqList *L)
{
return (L->length);
}
/**************************************************
⑦函数名:GetElem
功 能: 取线性表数组内,某个序号的元素值,并返回
参 数: ①SqList *L: 要取的线性表 ②int i:要取的序号(逻辑需要 1-n)
③ElemType &e:返回到特定位置
注意:①合法性判断 ② 需要把逻辑(1~n)变成物理序号(0~n-1)
返回值: bool:是否获取成功
**************************************************/
bool GetElem(SqList *L,int i, ElemType &e)
{
if(i<1 || i>L->length)//①
{
return false;
}
e = L->data[i-1]; //②
return true;
}
/**************************************************
⑧函数名: LocateElement
功 能: 查找特定元素值,在线性表中的位置(1~n)
参 数: ①ElemType element: 特定元素值 ② SqList *L:被查的线性表
返回值: int: 位置信息 (0没找到, 1~n, 即为位置)
**************************************************/
int LocateElement(ElemType element, SqList *L)
{
int i = 0;
while(i < L->length && L->data[i] != element) i++;
//如果 i跳出后, i范围超过 L->length,则 没找到
if(i >= L->length) return 0;
else return i+1;
}
/**************************************************
函数名: ListInsert
功 能: 把 e 插到到线性表 L 的第 i(逻辑序号) 个位置
参 数: (1)SqList *&L: 线性表L (2)int i: 插入到的逻辑位置
(3) ElemType e:要插入的元素值
注意:① 可插入的位置逻辑序号为1~L->length+1
②得出 j最后是等于 i+1, 所以j的范围是 j>i
③从 j=L->length得出 , data[j] = data[j-1],从而确定整体范围
返回值: bool:是否插入完成
**************************************************/
bool ListInsert(SqList *&L,int i, ElemType e)
{
int j;
if(i<1 || i>L->length+1) //①
return false;
i--; //将顺序表的逻辑序号转化为物理序号
for(j = L->length; j > i; j--) //② data[i+1] = data[i] => j = i+1
{
//③ data[i]~data[L->length-1]整体后移到data[i+1]~data[L->length]
L->data[j] = L->data[j-1];
}
L->data[i] = e; //插入元素e
L->length++; //顺序表插入增1
return true; //成功插入返回true
}
/**************************************************
函数名: ListDelete
功 能: 删除顺序表特定位置的元素
参 数: (1)SqList *&L:被删的顺序表 (2)int i:位置
(3)ElemType &e:删掉的值
注 意: ① 思路是整体前移,所以确定初始值i,然后定公式,看临界定 范围
② 最后一个是 data[L->length-2] = data[L->length-1],
得出 j = L->length-2
返回值: bool:是否删除成功? true : false
**************************************************/
bool ListDelete(SqList *&L, int i, ElemType &e)
{
int j;
if(i < 1 || i > L->length) return false;
i--; //把逻辑序号转为物理序号
e = L->data[i]; //将要删除的元素存储
for(j = i;j < L->length-1; j++)//①将data[i...n-1]整体前移
{
//② data[i+1]~data[L->length-1] => data[i] ~ data[L->length-2]
L->data[j] = L->data[j+1];
}
L->length--; //顺序表长度减去1
return true;
}
list.h 算法库头文件
#ifndef LIST_H_INCLUDE
#define LIST_H_INCLUDE
#define MaxSize 100
typedef int ElemType; //自定义类型
typedef struct //自定义结构体
{
ElemType data[MaxSize];
int length;
}SqList;
//①用数组创建线性表
void CreateList(SqList *&L, ElemType a[],int n);
//②初始化线性表
void InitList(SqList *&L);
//③输出线性表
void DispalyList(SqList *L);
//④判断是否为空表
bool ListEmpty(SqList *L);
//⑤销毁线性表
void DestroyList(SqList *&L);
//⑥ 求线性表的长度
int ListLength(SqList *L);
//⑦求某个位置的数据元素值GetElem(L,i,e)
bool GetElem(SqList *L,int i, ElemType &e);
//⑧ 元素 e 在 L中的序号(逻辑序号 1~n)
int LocateElement(ElemType element, SqList *L);
//⑨ L中 第 i 位, 插入 e, ListInsert(L,i,e)
bool ListInsert(SqList *&L,int i, ElemType e);
//⑩ 删除 L 中特定位置 i 的元素 e, ListDelete(L,i,e)
bool ListDelete(SqList *&L, int i, ElemType &e);
#endif
main.cpp 测试函数
#include "list.h"
#include "stdio.h"
int main()
{
SqList *sq;
//②初始化线性表
InitList(sq);
//判断是否初始化后是空表
if(ListEmpty(sq))
{
printf("初始化过后是空表\n");
}
ElemType elem;
ElemType x[8] = {1,2,3,4,5,6,7,8};
ElemType y[8] = {9,8,7,6,5,4,3,2};
//①用数组创建线性表
CreateList(sq, x,8);
if(ListEmpty(sq) != 1)
{
printf("新建后不是空表\n");
}
//③输出线性表
DispalyList(sq);
④判断是否为空表
//bool ListEmpty(SqList *L);
//⑤销毁线性表
DestroyList(sq);
printf("空间释放后,输出看看啥情况\n");
DispalyList(sq);
CreateList(sq,y,8);
//⑥ 求线性表的长度
printf("新建一个y表,求一下长度是%d\n",ListLength(sq));
//⑦求某个位置的数据元素值GetElem(L,i,e)
if(GetElem(sq,1, elem))
{
printf("新y表第一个元素是%d\n",elem);
}
//⑧ 元素 e 在 L中的序号(逻辑序号 1~n)
elem = LocateElement(6, sq);
printf("6在y的第%d个位置\n",elem);
if(ListDelete(sq, 3, elem))
{
printf("删除y的第三个元素%d,然后再输出一下y:\n",elem);
DispalyList(sq);
}
//⑨ L中 第 i 位, 插入 e, ListInsert(L,i,e)
if(ListInsert(sq,3,elem))
{
printf("再插入,就是玩,展示:\n");
DispalyList(sq);
}
return 0;
}
演示结果:
