线性顺序表算法库
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语言, 直接freefree(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; //插入元素eL->length++; //顺序表插入增1return 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--; //顺序表长度减去1return true;
}list.h 算法库头文件
#ifndef LIST_H_INCLUDE
#define LIST_H_INCLUDE#define MaxSize 100typedef 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);#endifmain.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;
}
演示结果:
