数据结构（C语言）类C代码的代码实现（二）——线性表的顺序表示和实现

目录

前期准备

代码的主要参考

源码形式

源代码

头文件

源文件1.SqList.cpp

构造顺序表

销毁顺序表

清空顺序表

判断空表

求表长

按位查找

按值查找

寻找前驱

寻找后继

插入元素

删除元素

遍历顺序表

顺序表合并

源文件2.测试函数.test.cpp

最终测试结果

收获

---

前期准备

下面的代码有些部分是C++的功能，如引用，所以.cpp可以实现。代码是基于VS的C++写的，不过这个C++基本可以兼容C语言（scanf函数要换成scanf_s函数）。

如何用Visual Studio 2022 编写C语言_visualstudio2022怎么写c语言-CSDN博客

代码的主要参考

参考原因：1、和我写的东西意义一致。2、纯用C实现。3、主函数（测试函数）基本改编自这篇博客。

数据结构c语言版 严蔚敏 顺序线性表12个基本操作及算法的实现_编程实现线性链表的基本操作(12个)-CSDN博客

源码形式

头文件用来放调用的库和函数声明。SqList.cpp是函数实现，test.cpp是主函数（测试函数）。

源代码

头文件

#pragma once
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;//Status是函数的类型，其值是函数结果状态代码
typedef int ElemType;

//-----线性表的动态分配顺序存储结构-----
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef struct SqList {
	ElemType* elem;//存储空间基址
	int length;//当前长度
	int listsize;//当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;

Status InitList_Sq(SqList& L);
//操作结果：构造一个空的线性表L。
void DestroyList_Sq(SqList& L);
//初始条件：线性表L已存在。
//操作结果：销毁线性表L。
Status ClearList_Sq(SqList& L);
//初始条件：线性表L已存在。
//操作结果：将L重置为空表。
Status ListEmpty_Sq(SqList L);
//初始条件：线性表L已存在。
//操作结果：若L为空表，则返回TRUE,否则返回FALSE。
int ListLength_Sq(SqList L);
//初始条件：线性表L已存在。
//操作结果：返回L中数据元素个数。
Status GetElem_Sq(SqList L, int i, ElemType& e);
//初始条件：线性表L已存在，1<=i<=ListLength(L)。
//操作结果：用e返回L中第i个数据元素的值。
int LocateElem_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType));
//初始条件：线性表L已存在，compare()是数据元素判定函数。
//操作结果：返回L中第1个满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。
Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType& pre_e);
//初始条件：线性表L已存在。
//操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回他的前驱，否则操作失败，pre_e无定义。
Status NextElem_Sq(SqList L, ElemType cur_e, ElemType& next_e);
//初始条件：线性表L已存在。
//操作结果：若cur_e是L的数据元素，且不是第一个，则用next_e返回他的后继，否则操作失败，pre_e无定义。
Status ListInsert_Sq(SqList& L, int i, ElemType e);
//初始条件：线性表L已存在，1<=i<=ListLength(L)+1。
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。
Status ListDelete_Sq(SqList& L, int i, ElemType& e);
//初始条件：线性表L已存在且非空，1<=i<=ListLength(L)。
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。
Status ListTraverse_Sq(SqList L, void (*visit)(ElemType*));
//初始条件：线性表L已存在。
//操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
void MergeList_Sq(SqList La, SqList Lb, SqList& Lc);
//合并有序非递减顺序表。//这个操作不是课本中12个基本操作的一个。
//归并La,Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列。
void union_Sq(SqList& La, SqList Lb);
//将所有在线性表Lb中但不在La中的数据元素插入到La中
Status equal(ElemType c1, ElemType c2); /* 数据元素判定函数(相等关系) */

源文件1.SqList.cpp

#include "head.h"

构造顺序表

Status InitList_Sq(SqList& L) {
	//构造一个空的线性表L。
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if (!L.elem)exit(OVERFLOW);//存储分配失败
	L.length = 0;//空表长度为0
	L.listsize = LIST_INIT_SIZE;//初始存储容量
	return OK;
}//构造

销毁顺序表

void DestroyList_Sq(SqList& L) {
	free(L.elem);
	L.elem = NULL;
	L.length = 0;
	L.listsize = 0;
	//对非动态开辟内存不能使用free释放，所以free(&L)不可以
}//销毁

参考博客

【C语言】free()函数详解(动态内存释放函数)_free函数-CSDN博客

清空顺序表

Status ClearList_Sq(SqList& L) {
	if (!L.elem)exit(OVERFLOW);
	else {//傻了，思考两个小时在想销毁和清空有什么区别，原来清空是保留空间啊
		L.length = 0;
		L.listsize = LIST_INIT_SIZE;//空间位置数
		return OK;
	}
}//清空

判断空表

Status ListEmpty_Sq(SqList L) {
	if (L.length == 0 && L.listsize == LIST_INIT_SIZE)
		return TRUE;
	else
		return FALSE;
}//确定表是否为空

求表长

int ListLength_Sq(SqList L) {
	return L.length;
}//返回表中元素个数

按位查找

Status GetElem_Sq(SqList L, int i, ElemType& e) {
	if ((i < 1) || (i > L.length))return ERROR;//i值不合法
	e = L.elem[i - 1];
	return OK;
}//按位查找

按值查找

int LocateElem_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
	//在顺序线性表L中查找第1个值与e满足compare()的元素的位序
	//若找到，则返回其在L中的位序，否则返回0
	int i;ElemType* p;
	i = 1;//i的初值为第1个元素的位序
	p = L.elem;//p的初值为第1个元素的存储位置
	while (i <= L.length && !(*compare)(*p++, e))++i;
	if (i <= L.length)return i;
	else return 0;
}//按值查找

一开始我以为compare是一个特殊的函数，但这里是一个函数指针。包括下面的visit也是。可以参见博客：函数指针和指针函数用法和区别-CSDN博客

test.cpp源文件中有函数指针用法的示例。

当然C++中有compare函数，类似于C语言中的strcmp函数吧。

请问C语言的库函数里有compare函数么？-CSDN社区

C 语言标准库速查手册-CSDN社区

第二个在C技能树-参考手册

寻找前驱

Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType& pre_e) {
	int i = 2;//从第2个元素开始，因为第一个元素一定没有前驱
	for (;i <= L.length;i++) {
		if (L.elem[i - 1] == cur_e)break;//elem[0]是第1个元素
	}
	if (i > L.length)return ERROR;//无前驱
	pre_e = L.elem[i - 2];//i-1的前驱是i-2
	return OK;//一定要有return OK。若没有上一次为ERROR，下一次无论合不合理返回值仍为ERROR；若第一次正常，返回值系统随意赋值。
}//寻找前驱

寻找后继

Status NextElem_Sq(SqList L, ElemType cur_e, ElemType& next_e) {
	int i = 1;//从第1个元素开始
	for (;i <= L.length;i++) {
		if (L.elem[i - 1] == cur_e)break;//elem[0]是第1个元素
	}
	if (i >= L.length)return ERROR;//无后继
	next_e = L.elem[i];//i-1的前驱是i
	return OK;
}//寻找后继

插入元素

Status ListInsert_Sq(SqList& L, int i, ElemType e) {
	//在顺序表中L中第i个位置之前插入新的元素e。
	//i的合法值为1<=i<=ListLength_Sq(L)
	ElemType* newbase = NULL, * q, * p;//辅助指针
	if ((i < 1) || (i > L.length + 1))return ERROR;//i值不合法
	if (L.length >= L.listsize) {//当前存储空间已满，增加分配
		newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
		if (!newbase)exit(OVERFLOW);//存储分配失败
		L.elem = newbase;//新基址
		L.listsize += LISTINCREMENT;//增加存储容量
	}
	q = &(L.elem[i - 1]);//q为插入位置
	for (p = &(L.elem[L.length - 1]);p >= q;--p)
		*(p + 1) = *p;//插入位置及之后的位置右移
	*q = e;//插入e
	++L.length;//表长增1
	return OK;
}//插入

删除元素

Status ListDelete_Sq(SqList& L, int i, ElemType& e) {
	//在顺序线性表L中删除第i个元素，并用e返回其值
	//i的合法值为1<=i<=ListLength_Sq(L)
	ElemType* p, * q;//辅助指针
	if ((i < 1) || (i > L.length))return ERROR;//i值不合法
	p = &(L.elem[i - 1]);//p为删除位置
	e = *p;//被删除元素的值赋给e
	q = L.elem + L.length - 1;//表尾元素的位置
	for (++p;p <= q;++p)//被删除元素之后的元素左移
		*(p - 1) = *p;
	--L.length;//表长减1
	return OK;
}//删除

遍历顺序表

Status ListTraverse_Sq(SqList L, void(*visit)(ElemType*))
{ /* 初始条件：顺序线性表L已存在 */
  /* 操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败 */
  /*           visit()的形参加'&'，表明可通过调用visit()改变元素的值 */
	ElemType* p;
	int i;
	p = L.elem;
	for (i = 1;i <= L.length;i++)
		visit(p++);
	printf("\n");
	return OK;
}

前面12个函数就是线性表的12个基本操作

无序顺序表合并（例2-1）

void union_Sq(SqList& La, SqList Lb) {
	//将所有在线性表Lb中但不在La中的数据元素插入到La中
	int La_len = ListLength_Sq(La);
	int Lb_len = ListLength_Sq(Lb);//求线性表的长度
	ElemType e;
	for (int i = 1;i <= Lb_len;i++) {
		GetElem_Sq(Lb, i, e);//取Lb中第i个数据元素赋给e
		if (!LocateElem_Sq(La, e, equal))ListInsert_Sq(La, ++La_len, e);
	}
}//无序归并
Status equal(ElemType c1, ElemType c2) /* 数据元素判定函数(相等关系) */
{
	if (c1 == c2)
		return TRUE;
	else
		return FALSE;
}

非递减顺序表合并（例2-2）

void MergeList_Sq(SqList La, SqList Lb, SqList& Lc) {
	//已知顺序线性表La和Lb的元素按值非递减排列
	//归并La和Lb得到的新的顺序线性表Lc,Lc的元素也按值非递减排列
	ElemType* pa, * pb, * pc, * pa_last, * pb_last;
	pa = La.elem;pb = Lb.elem;
	Lc.listsize = Lc.length = La.length + Lb.length;
	pc = Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));
	if (!Lc.elem)exit(OVERFLOW);//存储分配失败
	pa_last = La.elem + La.length - 1;
	pb_last = Lb.elem + Lb.length - 1;
	while (pa <= pa_last && pb <= pb_last) {//归并
		if (*pa <= *pb)*pc++ = *pa++;
		else *pc++ = *pb++;
	}
	while (pa <= pa_last)*pc++ = *pa++;//插入La的剩余元素
	while (pb <= pb_last)*pc++ = *pb++;//插入Lb的剩余元素
}//归并

源文件2.测试函数.test.cpp

测试成功

#include"head.h"
typedef int ElemType;

Status comp(ElemType c1, ElemType c2) /* 数据元素判定函数(平方关系) */
{
    if (c1 == c2 * c2)
        return TRUE;
    else
        return FALSE;
}

void visit(ElemType* c) /* ListTraverse()调用的函数(类型要一致) */
{
    printf("%d ", *c);
}

void dbl(ElemType* c) /* ListTraverse()调用的另一函数(元素值加倍) */
{
    *c *= 2;
}

void main()
{
    SqList L,L1,L2;
    ElemType e, e0;
    Status i;
    int j, k;
    i = InitList_Sq(L);
    printf("初始化L后：L.elem=%u L.length=%d L.listsize=%d\n", L.elem, L.length, L.listsize);
    for (j = 1;j <= 5;j++)
        i = ListInsert_Sq(L, 1, j);
    printf("在L的表头依次插入1～5后：*L.elem=");
    for (j = 1;j <= 5;j++)
        printf("%d ", *(L.elem + j - 1));
    printf("\n");
    printf("L.elem=%u L.length=%d L.listsize=%d\n", L.elem, L.length, L.listsize);
    i = ListEmpty_Sq(L);
    printf("L是否空：i=%d(1:是 0:否)\n", i);
    i = ClearList_Sq(L);
    printf("清空L后：L.elem=%u L.length=%d L.listsize=%d\n", L.elem, L.length, L.listsize);
    i = ListEmpty_Sq(L);
    printf("L是否空：i=%d(1:是 0:否)\n", i);
    for (j = 1;j <= 10;j++)
        ListInsert_Sq(L, j, j);
    printf("在L的表尾依次插入1～10后：L.elem=");
    for (j = 1;j <= 10;j++)
        printf("%d ", *(L.elem + j - 1));
    printf("\n");
    printf("L.elem=%u L.length=%d L.listsize=%d\n", L.elem, L.length, L.listsize);
    ListInsert_Sq(L, 1, 0);
    printf("在L的表头插入0后：L.elem=");
    for (j = 1;j <= ListLength_Sq(L);j++) /* ListLength(L)为元素个数 */
        printf("%d ", *(L.elem + j - 1));
    printf("\n");
    printf("L.elem=%u(有可能改变) L.length=%d(改变) L.listsize=%d(改变)\n", L.elem, L.length, L.listsize);
    GetElem_Sq(L, 5, e);
    printf("第5个元素的值为：%d\n", e);
    for (j = 3;j <= 4;j++)
    {
        k = LocateElem_Sq(L, j, comp);
        if (k)
            printf("第%d个元素的值为%d的平方\n", k, j);
        else
            printf("没有值为%d的平方的元素\n", j);
    }
    for (j = 1;j <= 2;j++) /* 测试头两个数据 */
    {
        GetElem_Sq(L, j, e0); /* 把第j个数据赋给e0 */
        i = PriorElem_Sq(L, e0, e); /* 求e0的前驱 */
        if (i == ERROR)
            printf("元素%d无前驱\n", e0);
        else
            printf("元素%d的前驱为：%d\n", e0, e);
    }
    for (j = ListLength_Sq(L) - 1;j <= ListLength_Sq(L);j++) /* 最后两个数据 */
    {
        GetElem_Sq(L, j, e0); /* 把第j个数据赋给e0 */
        i = NextElem_Sq(L, e0, e); /* 求e0的后继 */
        if (i == ERROR)
            printf("元素%d无后继\n", e0);
        else
            printf("元素%d的后继为：%d\n", e0, e);
    }
    k = ListLength_Sq(L); /* k为表长 */
    for (j = k + 1;j >= k;j--)
    {
        i = ListDelete_Sq(L, j, e); /* 删除第j个数据 */
        if (i == ERROR)
            printf("删除第%d个数据失败\n", j);
        else
            printf("删除的元素值为：%d\n", e);
    }
    printf("依次输出L的元素：");
    ListTraverse_Sq(L, visit); /* 依次对元素调用visit()，输出元素的值 */
    printf("L的元素值加倍后：");
    ListTraverse_Sq(L, dbl); /* 依次对元素调用dbl()，元素值乘2 */
    ListTraverse_Sq(L, visit);
    i = InitList_Sq(L1);//L1必须初始化，L2可以不初始化
    printf("初始化L1后：L1.elem=%u L1.length=%d L1.listsize=%d\n", L1.elem, L1.length, L1.listsize);
    for (j = 1;j <= 6;j++)
        ListInsert_Sq(L1, j, j);
    printf("在L1的表尾依次插入1～6后：L1.elem=");
    for (j = 1;j <= 6;j++)
        printf("%d ", *(L1.elem + j - 1));
    printf("\n");
    MergeList_Sq(L, L1, L2);
    printf("依次输出L2的元素：");
    ListTraverse_Sq(L2,visit);
    union_Sq(L, L1);
    printf("依次输出L的元素：");
    ListTraverse_Sq(L, visit);
    DestroyList_Sq(L);
    DestroyList_Sq(L1);
    DestroyList_Sq(L2);
    printf("销毁L后：L.elem=%u L.length=%d L.listsize=%d\n", L.elem, L.length, L.listsize);
}

中间一次ctrl+C只点了C，导致测试主函数代码全删，最后被迫上了初始版，只有12个函数的版本。中间我又凭印象加上了顺序表合并这个函数的测试，但L1没初始化，结果出现了以下局面。

最终测试结果

收获

1、弥补了关于函数指针的一些知识缺陷

2、解决了相关问题