线性顺序表算法库

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;
}

演示结果: