动态链表我们就先讲到这里，实际上更让我感兴趣的是静态链表。这种无需指针而有能够实现链表功能的结构，对于那些不支持指针的高级语言来说，无疑是个巨大的福音。它既可以像数组一样随机存取数据---它本身就是一个数组，又具有链表方便地实现插入和删除结点的功能；由于它是模拟的“动态分配空间”，实际上它的存储空间是由系统一次性分配好了的，这样在“动态分配空间”的时候，不需要内存管理程序，如果运行的Find函数相对较少，它实现的速度比动态链表要快很多；此外，他很少出现因为内存空间不够的原因而导致程序不正常终止的情况，因为它的空间一早就分配好了，只要不超出链表的最大长度，空间就足够。因此它真可以称的上是一个“宝贝”。 在链表的指针实现（即动态链表）中，有两个重要的特点： 1.数据存储在一组结构体中,每个结构包含有数据以及指向下一个结构体的指针. 2.一个新的结构体可以通过调用malloc()而从系统全局内存(global memory)得到,并可以通过调用 free()而被释放. 静态链表必须能够模仿实现这两条特性.满足条件1的逻辑方法是要有一个全局的结构体数组.对于该数组中的任何单元(元素),其数组下标可以用来表示一个地址(结点).也就是说数组元素(结构体)包含有数据以及指向下一个结构体的游标---即下一个结点的数组下标.可以建立不同的链表，但实际上每一个链表都是结构体数组一部分元素的集合。 为了模拟条件2，我们需要建立一个“模拟空间分配站”，它是一个规模较大的结构体数组。我们可以建立不同的链表，实际上我们创造的每一个链表都来自这个“模拟空间分配站”，每一个结点都是该结构体数组的元素，每一个链表都是结构体数组一部分元素的集合。 它的类型声明和基本操作如下表所示： //-------------------线性表的静态单链表存储结构------------------------ #define MAXSIZE 1000//链表的最大长度 typedef int Position; typedef int SLink; typedef struct Node{     ElemType data;     Position next; } SLinkList[MAXSIZE]; //-------------------线性表的静态单链表基本操作------------------------ static void InitSpace_SL(SLinkList Space);//构造一个“模拟空间分配站”,为全局变量 //初始条件：“模拟空间分配站”已存在。操作结果："动态"分配空间 给结点P  static Position malloc_SL(void); //初始条件：“模拟空间分配站”已存在。操作结果：释放结点P 的空间 到“模拟空间分配站” static void free_SL(Position P); Position MakeEmpty(SLink L);//初始条件：线性表L已存在。 操作结果：将线性表L重置为空表。 Position InitList(void); //构造一个空的线性表 void DestroyList(SLink L);//初始条件：线性表L已存在。 操作结果：销毁线性表L。 int IsEmpty(SLink L);//初始条件：线性表L已存在。 操作结果：判断线性表是否为空表。 int SListLength(SLink L);//初始条件：线性表L已存在。 操作结果：返回线性表L结点的个数。 Position NewSLNode(ElemType X);//构造一个数据域为X的新结点 //初始条件：线性表L和结点P已存在。操作结果：判断P是否为链表L的结点 int LContaiP(SLink L, Position P); int IsLast(Position P); //初始条件：结点P已存在。 操作结果：判断P是否为尾结点 Position FindPrefious(ElemType X, SLink L); //初始条件：线性表L已存在。操作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。 void SListDelete(Position Pre);//初始条件：线性表L中结点P已找到。 操作结果：删除该结点。 void SListInsert(Position Pre, Position S); //初始条件：线性表L中结点P已找到，新结点S已构造。操作结果：在该结点之前插入新结点X。 //-------------------线性表的静态单链表基本操作的算法实现------------------------ static void InitSpace_SL(SLinkList Space)//构造一个“模拟空间分配站”,为全局变量 {     int i;         for(i=0; i<MAXSIZE-1; i++) //每个结点的游标值均表示其后继结点的数组下标     {         Space[i].next = i+1;         Space[i].data = i+1;     }     Space[MAXSIZE-1].next = 0;//尾结点的后继结点下标为0，即NULL } //初始条件：“模拟空间分配站”已存在。操作结果："动态"分配空间 给结点P  static Position malloc_SL(void) {     Position P;         P = Space[0].next;  //每一个结点的空间均从Space[0]这里取得，当前被取走的结点乃Space[0]的直接后继     Space[0].next = Space[P].next; //为P结点分配空间，实际上相当于出栈，Space[0]即栈顶     return P;   //把结点P从“模拟空间分配站”中取出来 ，并返回其值（实际上是一个数组下标） }   //初始条件：“模拟空间分配站”已存在。操作结果：释放结点P 的空间 到“模拟空间分配站” static void free_SL(Position P) {      Space[P].next = Space[0].next;      Space[0].next = P;//回收P结点的空间，实际上相当于入栈 ，Space[0]即栈顶 }   Position MakeEmpty(SLink L)//初始条件：线性表L已存在。 操作结果：将线性表L重置为空表。 {     Position P = Space[L].next;         while(P)     {         free_SL(L); //从头结点开始依次释放回收结点的空间         L = P;         P = Space[L].next;     }   //最后使  Space[L].next = 0; }   Position InitList(void) //构造一个空的线性表 {     SLink L;         L = malloc_SL(); //为链表的头结点分配空间     if(!L)     {         printf("Out of space!");         return 0;     }     Space[L].next = 0; //使头结点的直接后继为0,构造一个空的线性表     return L; }   void DestroyList(SLink L)//初始条件：线性表L已存在。 操作结果：销毁线性表L。 {     Position P = Space[L].next;         while(P)     {         free_SL(L); //从头结点开始依次释放回收结点的空间         L = P;         P = Space[L].next;     }       free_SL(L);//把头结点的空间也释放回收,彻底销毁线性表L }   int IsEmpty(SLink L)//初始条件：线性表L已存在。 操作结果：判断线性表是否为空表。 {     return Space[L].next == 0; }   int SListLength(SLink L)//初始条件：线性表L已存在。 操作结果：返回线性表L结点的个数。 {     Position P = Space[L].next;     int num = 0;           while(P) //累积线性表L结点的个数     {         num++;         P = Space[P].next;     }     return num;  //返回线性表L结点的个数 }   Position NewSLNode(ElemType X)//构造一个数据域为X的新结点 {     Position S;         S = malloc_SL(); //为新结点分配空间      if(!S)     {         printf("Out of space!");         return 0;     }     Space[S].data = X;     Space[S].next = 0;     return S;//返回新结点 }   //初始条件：线性表L和结点P已存在。操作结果：判断P是否为链表L的结点 int LContaiP(SLink L, Position P) {     Position R = Space[L].next;         while(R && R!=P) //遍历整个链表         R = Space[R].next;     return R;//返回R,若P不是链表L的结点,则R=0,否则R不为0 }   int IsLast(Position P) //初始条件：结点P已存在。 操作结果：判断P是否为尾结点 {     return  Space[P].next == 0; } //初始条件：线性表L已存在。操作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。 Position FindPrefious(ElemType X, SLink L) {     Position P = L;         while(Space[P].next && Space[Space[P].next].data != X)//遍历链表寻找值为X的结点         P = Space[P].next;     if(!Space[P].next)  //如果找不到值为X的结点,返回NULL         return 0;     else         //若找到则返回该结点的前驱P         return P;    }   void SListDelete(Position Pre)//初始条件：线性表L中结点P已找到。 操作结果：删除该结点。 {      Position P;            P = Space[Pre].next; //删除结点P      Space[Pre].next = Space[P].next;      free_SL(P);//释放回收结点P的空间 } //初始条件：线性表L中结点P已找到，新结点S已构造。操作结果：在该结点之前插入新结点X。 void SListInsert(Position Pre, Position S) {      Space[S].next = Space[Pre].next;      Space[Pre].next = S; }

评论