《大话数据结构》读书笔记之线性表基本操作（静态单链表实现）

dummy@example.com (batsom) — Fri, 09 Dec 2022 09:12:26 +0000

/*
Name: 线性表抽象数据类型（使用静态单链表实现）
Copyright:
Author: 巧若拙
Date:06-10-14 14:16
Description:
近一个月前我总结了线性表抽象数据类型（使用动态单链表实现），实际上更让我感兴趣的是静态链表。这种无需指针而有能够实现链表功能的结构，
对于那些不支持指针的高级语言来说，无疑是个巨大的福音。既可以像数组一样随机存取数据---它本身就是一个数组，又具有链表方便地实现插入和删除结点的功能；
由于它是模拟的"动态分配空间"，实际上它的存储空间是由系统一次性分配好了的，这样在"动态分配空间"的时候，不需要内存管理程序，如果运行的Find函数相对较少，
它实现的速度比动态链表要快很多；此外，他很少出现因为内存空间不够的原因而导致程序不正常终止的情况，因为它的空间一早就分配好了，只要不超出链表的最大长度，
空间就足够。因此它真可以称的上是一个"宝贝"。
在链表的指针实现（即动态链表）中，有两个重要的特点：
1.数据存储在一组结构体中,每个结构包含有数据以及指向下一个结构体的指针。
2.一个新的结构体可以通过调用malloc()而从系统全局内存(global memory)得到,并可以通过调用free()而被释放.
静态链表必须能够模仿实现这两条特性。满足条件1的逻辑方法是要有一个全局的结构体数组，对于该数组中的任何单元(元素)，其数组下标可以用来表示一个地址(结点)。
也就是说数组元素(结构体)包含有数据以及指向下一个结构体的游标---即下一个结点的数组下标.可以建立不同的链表，但实际上每一个链表都是结构体数组一部分元素的集合。
为了模拟条件2，我们需要建立一个"模拟空间分配站"，它是一个规模较大的结构体数组。我们可以建立不同的链表，实际上我们创造的每一个链表都来自这个"模拟空间分配站"，
每一个结点都是该结构体数组的元素，每一个链表都是结构体数组一部分元素的集合。
如果你曾经阅读过《线性表抽象数据类型（使用单链表实现）》中的代码，你会发现动态链表和静态链表的基本操作的实现算法很相似，所有函数的接口都是一样的，主函数是一模一样的。
静态链表可以代替动态链表实现线性表的所有功能，而且速度更快。
*/

#include
#include
#include
#include

#define MAXSIZE 1000 //链表的最大长度
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;
typedef int Status; //函数类型，其值是函数结果状态代码，如OK等
typedef int Position;
typedef int LinkList;

struct Node{
ElemType data; //数据域
Position next;//指针域（游标）
} List[MAXSIZE]; //全局变量，静态链表的存储空间

void InitSpaceSL(void);//构造一个"模拟空间分配站",为全局变量
Position MallocSL(void); //"动态"分配空间给结点P
void FreeSL(Position P);//释放结点P的空间到"模拟空间分配站"
Status InitList(LinkList *L);//建立一个带头结点的空线性表L
Status ListEmpty(LinkList L);//判断线性表是否为空，若线性表为空，返回TRUE，否则返回FALSE
void DestroyList(LinkList *L);//销毁线性表L
Status ClearList(LinkList *L);//将线性表清空（只留下头结点）
int ListLength(LinkList L);//返回线性表L的元素个数
Status DisplayList(LinkList L);//输出线性表L的所有元素
Status GetElem(LinkList L, int i, ElemType *e);//将线性表L中第i个位置元素值赋给e
Status LocateElem(LinkList L, ElemType e);//在线性表L中查找是否存在与给定值e相等的元素
Status ListInsert(LinkList *L, int i, ElemType e);//在线性表L中的第i个位置之前插入新元素e
Status ListDelete(LinkList *L, int i, ElemType *e);//删除线性表L中的第i个位置，并将该元素值赋给e

int main(void)
{
LinkList a = NULL;
ElemType *p, e = 0;
int i;

InitSpaceSL(); //构造一个"模拟空间分配站",为全局变量

InitList(&a);//建立一个空的线性表

ListInsert(&a, 1, 1);
for (i=1; i<10; i++)
{
ListInsert(&a, i, i+100);
}

DisplayList(a);

printf("len = %d\n", ListLength(a));
for (i=1; i {
ListDelete(&a, i, &e);//删除线性表L中的第i个位置，并将该元素值赋给e
}
printf("len = %d\n", ListLength(a));
printf("e = %d\n", e);

DisplayList(a);

i = 5;
e = 1050;
if (LocateElem(a, e))//在线性表L中查找是否存在与给定值e相等的元素
{
printf("存在%d\n", e);
}
else
{
printf("不存在%d\n", e);
ListInsert(&a, i, e);
}

DisplayList(a);

ListDelete(&a, ListLength(a), &e);//删除线性表L中的最后一个元素
DisplayList(a);

ListDelete(&a, 1, &e);//删除线性表L中的第一个元素
DisplayList(a);

ClearList(&a);//将线性表清空（只留下头结点）
DisplayList(a);

return 0;
}

/*
函数名称：InitSpaceSL
函数功能：构造一个"模拟空间分配站",作为静态链表的存储空间.
初始化各结点的游标值，每个结点的游标值均表示其后继结点的数组下标
输入变量：无
输出变量；无
*/
void InitSpaceSL(void)
{
Position i;

for (i=0; i {
List[i ].next = i + 1;
}

List[MAXSIZE-1].next = 0;//尾结点的后继结点下标为0，即NULL
}

Position MallocSL(void) //"动态"分配空间给结点P
{
Position P = 0;

if (List[0].next != 0) //还有空间
{
P = List[0].next;
List[0].next = List[P].next;
}

return P;
}

void FreeSL(Position P)//释放结点P的空间到"模拟空间分配站"
{
List[P].next = List[0].next;
List[0].next = P; //回收P结点的空间，实际上相当于入栈，List[0]即栈顶
}

Status InitList(LinkList *L)//建立一个带头结点的空线性表L
{
*L = MallocSL(); //为链表的头结点分配空间
if (!*L)
{
printf("Out of space!");
return ERROR;
}

List[*L].next = 0;

return OK;
}

Status ListEmpty(LinkList L)//判断线性表是否为空，若线性表为空，返回TRUE，否则返回FALSE
{
return (List[L].next == 0) ? TRUE : FALSE;
}

void DestroyList(LinkList *L)//销毁线性表L
{
Position s;

while (*L != 0)
{
s = List[*L].next;
FreeSL(*L);
*L = s;
}
}

Status ClearList(LinkList *L)//将线性表清空（只留下头结点）
{
Position q, s = List[*L].next;

while (s != 0)
{
q = List[s ].next;
FreeSL(s);
s = q;
}

List[*L].next = 0;
}

int ListLength(LinkList L)//返回线性表L的元素个数
{
Position s = List[L].next;
int count = 0;

while (s != 0)
{
count++;
s = List[s ].next;
}

return count;
}

Status DisplayList(LinkList L)//输出线性表L的所有元素
{
Position s = List[L].next;
int i = 0;

if (s == 0)
{
printf("none!\n");
return ERROR;
}

while (s != 0)
{
printf("data[%d] = %d, ", i++, List[s ].data);
s = List[s ].next;
}
printf("\n");

return OK;
}

Status GetElem(LinkList L, int i, ElemType *e)//将线性表L中第i个位置元素值赋给e
{
int j = 1;
Position s = List[L].next; //p指向第一个结点（非头结点）

while (s != 0 && j < i) //寻找第i个结点
{
j++;
s = List[s ].next;
}

if (s == 0 || j > i) //第i个元素不存在
{
return ERROR;
}

*e = List[s ].data;

return OK;
}

Status LocateElem(LinkList L, ElemType e)//在线性表L中查找是否存在与给定值e相等的元素
{
Position s = List[L].next;

while (s != 0)
{
if (List[s ].data == e)
return TRUE;
s = List[s ].next;
}

return FALSE;
}

Status ListInsert(LinkList *L, int i, ElemType e)//在线性表L中的第i个位置之前插入新元素e
{
int j = 1;
Position s, p = *L; //p指向头结点

while (p != 0 && j < i) //寻找第i-1个结点
{
j++;
p = List[p].next;
}

if (p == 0 || j > i) //第i-1个结点不存在
{
return ERROR;
}

s = MallocSL(); //为新结点分配空间
if (!s)
{
printf("Out of space!");
return ERROR;
}

List[s ].data = e;
List[s ].next = List[p].next;
List[p].next = s;

return OK;
}

Status ListDelete(LinkList *L, int i, ElemType *e)//删除线性表L中的第i个位置，并将该元素值赋给e
{
int j = 1;
Position q, p = *L; //p指向头结点

while (p != 0 && j < i) //寻找第i-1个结点
{
j++;
p = List[p].next;
}

if (List[p].next == 0 || j > i) //第i个结点不存在
{
return ERROR;
}

q = List[p].next; //q指向第i个结点
*e = List[q].data;
List[p].next = List[q].next;
FreeSL(q);

return OK;
}

Gentoo-zh / 《大话数据结构》读书笔记之线性表基本操作（静态单链表实现）

《大话数据结构》读书笔记之线性表基本操作（静态单链表实现）