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