[数据结构与算法]静态单链表、静态单循环链表、静态双循环链表

目录

（一）需求和规格说明

（二）设计

静态单链表：?

?单循环静态链表：

双循环静态链表：

（三）源代码

静态链表.cpp

StaticLinkList.h

静态单循环链表.cpp

CStaticLinkList.h

静态双循环链表.cpp

DCStaticLinkList.h

新手小白，欢迎指正批评！?

（一）需求和规格说明

【问题描述】

静态链表（Static Linked List）指利用数组实现链表的功能，免去了顺序表插入和删除操作时耗时的移动元素操作。是一个空间换时间的实例。在像JAVA、C#等没有指针的程序设计语言中，要实现链表就必须采用这种方式。下面以静态单链表为例来解释静态链表的实现：

申请一个较大的一维数组SL[n]。数组的元素由2个成员构成：一个成员data保存链表的数据元素；另一个成员next是指向链表中下一个元素的指针，事实上这里的next是存储下一个元素的数组下标。通过next，形成链式结构。当链表结束，最后一个结点的next域赋给一个特殊的值，比如：-1，表示链表结束。

与动态链表不同的是，插入新结点时，首先要判断表空间（数组）是否已满。如果表空间未满，则要获取一个空的单元，即取得空单元的指针（数组下标），那么如何取得空单元的指针呢？一般我们把所有空单元也组成一个链表，根据空单元链表的头指针很容易就能获取一个空单元。删除结点时，则需要把删除元素的单元回收到空单元链表中。所以，静态链表中事实上存储有2条链表，一条是保存数据的链表，另一条是空单元的链表。

静态链表也可以带有头结点，一般用数组SL[]头尾2个单元分别作为两条链表的头结点。比如，我们可以SL[0]为单链表头结点，头指针为0；以SL[n-1]为空单元链表的头结点，头指针为n-1，反之亦可。

下图所示为一个静态单链表，数据链表头结点为SL[0]，保存数据值a、b、c、d、e。空单元头结点为SL[11]。

【功能要求—基本】

1. 单链表初始化
2. 求链表长度
3. 按序号定位元素
4. 按给定值查找元素
5. 插入元素
6. 删除元素
7. 尾插法创建链表
8. 头插法创建链表
9. 打印数据链表
10. 打印空单元下标

【功能要求—扩展1】

实现静态单循环链表，功能参照基本功能要求。

【功能要求—扩展2】

实现静态双循环链表，功能参照基本功能要求。

（二）设计

• 静态单链表：?

??存储结构：

typedef struct{
????????ElemType data;
????????int cur;//索引后继节点
}Component, StaticLinkList[MAX_SIZE];?

1. 单链表初始化：首先，将静态链表中每一个元素的游标都指向与其相连的下一个元素。再对数据链表和空单元链表的头指针单独处理。数据链表的头指针指向MAX_SIZE，空单元链表的头指针指向0。

   ---

2. 求链表长度：定义一个变量n用于计算数据元素个数。从头节点开始，根据元素的游标找到元素的后继节点。每找到一个节点，n加一。直到找到数据链表的最后一个元素（即游标指向MAX_SIZE的元素），退出循环，返回元素个数n。
3. 按序号定位元素：（1）判断链表是否为空。若为空，给出提示并退出。（2）判断给定的序号是否合法（即不超过链表长度，且大于0），若不合法，给出提示并退出。（3）当链表不为空且序号合法时，进行查找。定义一个变量l（初始化为0），用于记录当前指针所指元素的序号。从数据链表的头节点开始遍历数据链表，直到找到给定序号的元素。将该元素的数据通过变量e传出函数，再给出提示信息。?
4. 按给定值查找元素：首先，判断数据链表是否为空。若为空，给出提示信息并退出。其次，在数据链表中查找给定元素。利用循环体遍历数据链表，当找到给定元素或者遍历完整个数据链表时，退出循环。最后，判断当前指针所指元素的数据是否为给定数据。若为给定元素，则查找成功，给出提示并传出该元素下标。若不是给定元素，则查找失败，给出提示。
5. 插入元素：?（1）判断插入位置是否合法。当插入位置大于数据链表长度或者小于1时不合法，给出提示，返回false。（2）获取一个空单元的下标，并判断数组是否已满。调用New（）函数（返回空单元头指针的游标，算法思想在下文给出）获取一个空单元的下标。当获取的空单元下标为0时，说明空单元链表中没有空单元，即数组已满。给出提示信息，并返回false。若不为0，说明获取空单元成功，将待插入元素的值赋给空单元。（3）插入位置合法且数组未满时，开始插入元素。首先找到插入位置的前驱节点。从头节点开始依次向后遍历数据链表直到找到插入位置的前驱节点。其次，将新单元的游标指向插入位置的当前节点。最后，让插入位置的前驱节点指向新单元。（4）插入成功后，返回true。
6. 删除元素：（1）判断数据链表是否为空。为空给出提示并退出.（2）判断待删除位置是否合法。不合法给出提示并退出。（2）数据链表不空且删除位置合法时，开始删除元素。（3）从数据链表中删除元素。首先找到删除位置的前驱节点，并且用变量j暂存删除位置的下标。让前驱节点的游标指向删除位置的后继节点。（4）将删除元素链接到空单元链表中。通过变量j找到已删除的节点，让该节点的游标指向空单元链表的第一个空单元，再让空单元链表的头指针指向该节点。此时，该节点已链接到空单元链表中，变成空单元链表的第一个节点。（5）删除成功后给出提示。
7. 尾插法创建链表：（1）读入第一个字符。（2）获取一个空单元，并赋值。利用New()函数获取第一个空单元的下标，将刚刚读入的字符存入获取的空单元中。如果获取新单元失败，给出提示并退出。（3）将新节点链接到数据链表尾部。定义一个整型变量k，指向当前节点。让当前节点（初始时当前节点为数据链表的头节点）的游标指向新节点。（4）更新当前节点。让k指向新节点，即使新节点变为当前节点。（5）再读取一个新的字符。（6）重复步骤2、3、4、5，直到读取到标志结束的字符‘#’。（7）单独处理最后一个节点的指向，令最后一个节点指向MAX_SIZE。（8）创建成功后给出提示。
8. 头插法创建链表：（1）读入一个字符。（2）调用插入函数，插入位置为1，插入元素即刚读入的元素。（3）再读取一个字符。（4）重复步骤1、2，直到读取到标志结束的字符‘#’。（5）创建成功，给出提示。
9. 打印数据链表：首先，判断数据表是否为空。若为空，给出提示并退出。不为空时，遍历数据链表。遍历的同时，输出每个节点的下标以及存储的数据。遍历完数据链表输出‘end’提示用户。
10. 打印空单元下标：首先，判断空单元链表是否为空。若为空，给出提示并退出。不为空时，遍历空单元链表。遍历的同时，打印空单元下标。遍历完空单元链表输出‘end’提示用户。
11. 获得静态链表第一个空闲单元的下标（New(StaticLinkList &space)）：定义一个变量i存储空单元链表的头指针的游标。若i不为0，将空单元链表中的第一个空单元从空单元链表中删除，然后返回i（即第一个空单元的下标）。若i为0，直接返回i。

• ?单循环静态链表：

? ? ? ? 存储结构请参考静态单链表。

1. 单链表初始化：请参考静态单链表。

2. 求链表长度：定义一个变量n（初始化为0）用于计算数据元素个数。先判断数据链表是否为空。若为空，直接返回n。若不为空，从头节点开始，根据元素的游标找到元素的后继节点。每找到一个节点，n加一。直到找到数据链表的最后一个节点（即该节点的游标指向数据链表第一个节点的下标L[MAX_SIZE-1].cur的元素），退出循环，返回元素个数n。

3. 按序号定位元素：参考静态单链表。

4. 按给定值查找元素：参考静态单链表。

5. 插入元素：（1）判断插入位置是否合法。当插入位置大于数据链表长度或者小于1时不合法，给出提示，返回false。（2）获取一个空单元的下标，并判断数组是否已满。调用New（）函数（返回空单元头指针的游标，算法思想在下文给出）获取一个空单元的下标。当获取的空单元下标为0时，说明空单元链表中没有空单元，即数组已满。给出提示信息，并返回false。若不为0，说明获取空单元成功，将待插入元素的值赋给空单元。（3）插入位置合法且数组未满时，开始插入元素。首先找到插入位置的前驱节点。从头节点开始依次向后遍历数据链表直到找到插入位置的前驱节点。其次，将新单元的游标指向插入位置的当前节点。最后，让插入位置的前驱节点指向新单元。（4）若插入位置为第一个节点，则还需更新数据链表最后一个节点的指向，以保证循环秩序的正确。先找到数据链表的最后一个节点，让他指向当前数据链表的第一个节点。（5）插入成功后，返回true。

6. 删除元素：（1）判断数据链表是否为空。为空给出提示并退出。（2）判断待删除位置是否合法。不合法给出提示并退出。（3）数据链表不空且删除位置合法时，开始删除元素。（4）从数据链表中删除元素。首先找到删除位置的前驱节点，并且用变量j暂存删除位置的下标。让前驱节点的游标指向删除位置的后继节点。（5）将删除元素链接到空单元链表中。通过变量j找到已删除的节点，让该节点的游标指向空单元链表的第一个空单元，再让空单元链表的头指针指向该节点。此时，该节点已链接到空单元链表中，变成空单元链表的第一个节点。（6）若删除元素为第一个节点时，还要更新最后一个节点的指向。先找到数据链表的最后一个节点，让他指向当前数据链表的第一个节点。（7）删除成功后给出提示。

7. 尾插法创建链表：（1）读入第一个字符。（2）获取一个空单元，并赋值。利用New()函数获取第一个空单元的下标，将刚刚读入的字符存入获取的空单元中。如果获取新单元失败，给出提示并退出。（3）将新节点链接到数据链表尾部。定义一个整型变量k，指向当前节点。让当前节点（初始时当前节点为数据链表的头节点）的游标指向新节点。（4）更新当前节点。让k指向新节点，即使新节点变为当前节点。（5）再读取一个新的字符。（6）重复步骤2、3、4、5，直到读取到标志结束的字符‘#’。（7）单独处理最后一个节点的指向，令最后一个节点指向第一个节点的下标。（8）创建成功后给出提示。

8. 头插法创建链表：（1）读入第一个字符。（2）获取一个空单元，并赋值。利用New()函数获取第一个空单元的下标，将刚刚读入的字符存入获取的空单元中。如果获取新单元失败，给出提示并退出。（3）定义一个变量k，暂存最后一个节点，也就是第一个插入数据链表的指针。（4）让新节点指向当前数据链表的第一个节点。再让数据链表的头节点指向新节点。（5）再读取一个新的字符。（6）重复步骤2、4、5，直到读取到标志结束的字符‘#’。（7）单独处理最后一个节点的指向，令最后一个节点指向第一个节点的下标。（8）创建成功后给出提示。

9. 打印数据链表：参考静态单链表。

10. 打印空单元下标：参考静态单链表。

11. 获得静态链表第一个空闲单元的下标（New(StaticLinkList &space)）：参考静态单链表。

• 双循环静态链表：

? ? ? ?存储结构有三部分：数据（data），前驱游标(rear)，后继游标（cur）。

typedef struct{

????????ElemType data;

??????? int cur;// 后继游标

??????? int rear;//前驱游标

}Component, StaticLinkList[MAX_SIZE];

1. 单链表初始化：参考静态单链表。
2. 求链表长度：定义一个变量n（初始化为0）用于计算数据元素个数。先判断数据链表是否为空。若为空，直接返回n。若不为空，从头节点开始，根据元素的后继游标找到元素的后继节点。每找到一个节点，n加1。直到找到数据链表的最后一个节点（即该节点的后继游标指向数据链表第一个节点的下标L[MAX_SIZE-1].cur的元素），退出循环，返回元素个数n。
3. 按序号定位元素：参考静态单链表。
4. 按给定值查找元素：参考静态单链表。
5. 插入元素：（1）判断插入位置是否合法。若不合法，给出提示，返回false。（2）获取一个空单元的下标，并判断数组是否已满。若已满，给出提示，返回false。（3）插入位置合法且数组未满时，开始插入元素。（4）插入元素时分三种情况：a.插入之前，数据链表为空。这种情况下，新节点插入数据表后既是首节点，也是尾节点。所以，只需要让头指针、新节点的前驱指针、新节点的后继指针都指向新节点即可。b.插入后，新节点不是首节点。此种情况下要先找到插入位置。找到后先对新节点的前驱、后继指针赋值。新节点的后继指针指向插入位置，新节点的前驱指针指向插入位置的前驱节点。再对涉及到的另两个节点做处理。让插入位置的前驱节点的后继指针指向新节点，插入位置的前驱指针指向新节点。c.插入后，新节点为首节点。此种情况下，只需在执行了情况2的基础上，让头指针指向新节点。（5）插入成功后，返回true。
6. 删除元素：（1）判断数据链表是否为空。为空给出提示并退出。（2）判断待删除位置是否合法。不合法给出提示并退出。（3）数据链表不空且删除位置合法时，开始删除元素。（4）删除元素分三种情况：a.数据链表中只有一个节点。这种情况先将唯一的节点链接到空单元链表中。再将头指针初始化，即指向MAX_SIZE。b.删除节点不是首节点。这种情况要先找到删除位置，定义一个指针指向即将被删除的节点。再让待删除节点的前驱节点与待删除节点的后继节点链接到一起。即让待删除节点的前驱节点的后继指针指向待删除节点的后继节点，再让待删除节点的后继节点的前驱指针指向待删除节点的前驱节点。最后将待删除节点链接到空单元链表中。c.删除节点是首节点。这种情况，只要在第二种情况的基础上将头指针指向待删除节点的后继节点即可。要注意，更新头指针指向，最好在将待删除节点链接到空单元链表之前进行操作，否则找待删除节点的后继节点会比较麻烦。(5)删除成功后给出提示。
7. 尾插法创建链表：(1)读入第一个字符。(2)获取一个空单元，并赋值。利用New()函数获取第一个空单元的下标，将刚刚读入的字符存入获取的空单元中。如果获取新单元失败，给出提示并退出。(3)插入第一个节点时单独处理。当插入节点为第一个时，只需让头指针指向新节点，再更新当前节点指针指向（指向新节点）就可以了。(4)将第二个即以后的新节点链接到数据链表尾部。让新节点的前驱指针指向当前节点，让当前节点的后继指针指向新节点。最后更新当前节点指针指向，使新节点变为当前节点。(5)再读取一个新的字符。(6)重复步骤2、4、5，直到读取到标志结束的字符‘#’。(7)创建成功后给出提示。
8. 头插法创建链表：(1)读入第一个字符。(2)获取一个空单元，并赋值。利用New()函数获取第一个空单元的下标，将刚刚读入的字符存入获取的空单元中。如果获取新单元失败，给出提示并退出。(3)插入第一个节点时单独处理。定义一个整型k，暂存第一个节点（未来数据链表的尾节点）的位置，再让头节点指向新节点。(4)插入第二个及以后的节点时，让新节点的后继指针指向当前数据链表的首节点，让首节点的前驱指针指向新节点。最后，再让数据链表的头节点指向新节点。(5)再读取一个新的字符。(6)重复步骤2、4、5，直到读取到标志结束的字符‘#’。(7)创建成功后给出提示。
9. 打印数据链表：参考静态单链表。
10. 打印空单元下标：参考静态单链表。
11. 获得静态链表第一个空闲单元的下标（New(StaticLinkList &space)）：参考静态单链表。

（三）源代码

• 静态链表.cpp

  #include<iostream>
  #include"StaticLinkList.h"
  
  int main(void){
  	StaticLinkList L;
  	ElemType e;
  	int i;
  	int n;
  	int j, k, l;
  	
  	menu();
  	while(1){
  		cout<<"--请输入指令："<<endl;
  		cin>>i;
  		
  		switch(i){
  			case 0:
  				cout<<"感谢使用！"<<endl; 
  				exit(1);
  			case 1:
  				InitialList(L);
  				cout<<"初始化完成！"<<endl;
  				break;
  			case 2:
  				n = ListLength(L);
  				cout<<"链表长度为："<<n<<endl;
  				break;
  			case 3:
  				cout<<"请输入位置："<<endl;
  				cin>>j;
  				Locate(L, j, e);
  				break;
  			case 4:
  				cout<<"请输入需要查找的元素："<<endl;
  				cin>>e;
  				Search(L, e, j);
  				break;
  			case 5:
  				cout<<"请输入插入位置："<<endl;
  				cin>>j;
  				cout<<"请输入插入元素："<<endl;
  				cin>>e; 
  				if(InsertList(L, j, e) == true){
  					cout<<"插入成功！"<<endl; 
  				}
  				break;
  			case 6:
  				cout<<"请输入需要删除的元素的位置：" ;
  				cin>>j;
  				Delecte(L, j);
  				break;
  			case 7:
  				TCreate(L);
  				break;
  			case 8:
  				HCreate(L);
  				break;
  			case 9:
  				PrintData(L);
  				break;
  			case 10:
  				PrintNull(L);
  				break;
  			default:
  				cout<<"请输入合法指令！"<<endl; 
  		}	
  	}
  	system("pause");
  	return 0;
  }

• StaticLinkList.h

  #include<iostream>
  
  #define MAX_SIZE 10
  #define ElemType char
  
  using namespace std;
  
  typedef struct{
  	ElemType data;
  	int cur;//静态链表中的游标 
  }Component, StaticLinkList[MAX_SIZE];
  
  //菜单 
  void menu(){
  	cout<<"*******************************************"<<endl;
  	cout<<"0.退出程序"<<endl;
  	cout<<"1.单链表初始化"<<endl;
  	cout<<"2.求链表长度"<<endl;
  	cout<<"3.按序号定位元素"<<endl;
  	cout<<"4.按给定值查找元素"<<endl;
  	cout<<"5.插入元素"<<endl;
  	cout<<"6.删除元素"<<endl;
  	cout<<"7.尾插法创建链表"<<endl;
  	cout<<"8.头插法创建链表"<<endl;
  	cout<<"9.打印数据链表"<<endl;
  	cout<<"10.打印空单元下表"<<endl;
  	cout<<"*******************************************"<<endl; 
  }
  
  //获得静态链表第一个空闲单元的下标
  int New(StaticLinkList &space){
  	int i = space[0].cur;
  	
  	if(space[0].cur != 0){//将第一个空闲单元从空链表中删除 
  		space[0].cur = space[i].cur;
  	}
  	
  	return i;
  } 
  
  //1.初始化静态链表 
  void InitialList(StaticLinkList &space){
  	int i;
  	for(i=0; i<MAX_SIZE; i++){//每一个元素指向数组的下一个元素 
  		space[i].cur = i+1;
  	}
  	space[MAX_SIZE-2].cur = 0;//空链表最后一个元素指向0 
  	space[MAX_SIZE-1].cur = MAX_SIZE;//数据链表最后一个指向MAX_SIZE 
  }
  
  
  //2.求链表长度
  int  ListLength(StaticLinkList &space){
  	int i=MAX_SIZE-1;//用于遍历链表 
  	int n=0;//记录链表长度 
  	while(space[i].cur != MAX_SIZE){//数据链表最后一个单元的游标为MAX_SIZE 
  		i = space[i].cur;
  		n++;
  	}
  	return n;
  }
  
  //3.按序号定位元素
  void Locate(StaticLinkList &L, int &i, ElemType &e){
  	int k, l=0; 
  	k = MAX_SIZE-1;//k指向数据链表的头节点 
  	
  	if(ListLength(L) == 0){//判断是否为空表 
  		cout<<"静态链表为空！"<<endl;
  		return;
  	}
  	 
  	if(i<1 || i>ListLength(L)){//判断查找位置是否合法 
  		cout<<"查找位置不合法！"<<endl;
  		return;
  	}
  	
  	while(l<=i-1){//找到查找位置 
  		k = L[k].cur;
  		l++;
  	}
  	e = L[k].data;//将查找元素的位置赋值给e 
  	cout<<"定位成功，该位置元素为"<<e<<endl; 
  	return;
  } 
  
  //4.按给定值查找元素
  void Search(StaticLinkList &L, ElemType &e, int &i){
  	int j;
  	j = L[MAX_SIZE-1].cur;//j指向第一个元素 
  	
  	if(ListLength(L) == 0){//判断是否为空表 
  		cout<<"静态链表为空！"<<endl;
  		return;
  	}
  	while(L[j].data != e && L[j].cur != MAX_SIZE){//遍历查找元素。找到或遍历完链表时退出。 
  		j = L[j].cur;
  	}
  	
  	if(L[j].data == e){ //找到，给出提示并传出位置 
  		i = j;
  		cout<<"查找成功,该元素的位置下标为"<<i<<endl; 
  	}
  	else{//找不到，给出提示 
  		cout<<"查找失败！"<<endl;
  	}
  	return;
  }
  
  
  //5.插入元素
  bool InsertList(StaticLinkList &L, int &i, ElemType &e){//i为插入位置，e为插入元素 
  	int j, k, l=1; 
  	k = MAX_SIZE-1;//k指向数组的最后一个元素
  	 
  	if(i<1 || i>ListLength(L)+1){//判断插入位置是否合法 
  		cout<<"插入位置不合法！"<<endl;
  		return false;
  	}
  	
  	j = New(L);//j为第一个空闲单元下标 
  	if(j == 0){//判断数组是否已满 
  		cout<<"内存已满，无法插入元素！"<<endl;
  		return false;
  	}
  	else{
  		L[j].data = e;
  		while(l<=i-1){//找到插入位置 
  			k = L[k].cur;
  			l++;
  		}
  		//将新单元插入到元素链表 
  		L[j].cur = L[k].cur;
  		L[k].cur = j;
  	}
  	return true;
  }
  
  //6.删除元素
  void Delecte(StaticLinkList &L, int &i){
  	int k, l=1; 
  	int j; 
  	k = MAX_SIZE-1;//k指向数据链表的头节点 
  	
  	if(ListLength(L) == 0){//判断是否为空表 
  		cout<<"静态链表为空！"<<endl;
  		return;
  	}
  	 
  	if(i<1 || i>ListLength(L)){//判断删除位置是否合法 
  		cout<<"删除位置不合法！"<<endl;
  		return;
  	}
  	
  	while(l<=i-1){//找到删除位置的前一个元素 
  		k = L[k].cur;
  		l++;
  	}
  	
  	//从数据链表中删除该元素
  	j = L[k].cur;//暂存删除元素位置
  	L[k].cur = L[j].cur;//删除元素的前一个元素指向删除元素的后一个元素 
  	
  	//将删除元素链接到空链表中 
  	L[j].cur = L[0].cur;//删除元素指向第一个空单元
  	L[0].cur = j;//空链表头指针指向删除元素 
  	cout<<"删除成功!"<<endl;
  	
  }
  
  
  //7.尾插法创建链表
  void TCreate(StaticLinkList &L){
  	int j;
  	int k;
  	ElemType e;
  	k = MAX_SIZE-1;
  	cout<<"请输入字符（以#结束）："<<endl;
  	cin>>e; 
  	while(e != '#'){
  		j = New(L);//获取一个空单元
  		if(j == 0){
  			cout<<"链表已满！"<<endl;
  			return;
  		}
  		L[j].data = e;//赋值
  		L[k].cur = j;//链接到链表尾部
  		k = j;//更新指针
  		cin>>e;
  	}
  	L[k].cur = MAX_SIZE;//最后一个元素指向MAX_SIZE
  	cout<<"创建成功！"<<endl; 
  } 
  
  //8.头插法创建链表
  void HCreate(StaticLinkList &L){
  	int i=1;
  	ElemType e;
  	cout<<"请输入字符（以#结束）："<<endl;
  	cin>>e;
  	do{
  		if(InsertList(L, i, e) == false){
  			return;
  		}
  		cin>>e;
  	}while(e != '#');
  	cout<<"创建成功！"<<endl;
  } 
  
  //9.打印数据链表
  void PrintData(StaticLinkList &L){
  	int i=MAX_SIZE-1;//用于遍历链表 
  	if(L[i].cur == MAX_SIZE){
  		cout<<"数据链表为空！"<<endl;
  		return;
  	}
  	cout<<"数据链表："; 
  	while(L[i].cur != MAX_SIZE){//数据链表最后一个单元的游标为MAX_SIZE 
  		i = L[i].cur;
  		cout<<"["<<i<<"]"<<L[i].data<<"-";
  	}
  	cout<<"end"<<endl;
  }
  //10.打印空单元下标 
  void PrintNull(StaticLinkList &L){
  	int i=0;//用于遍历链表
  	if(L[i].cur == 0){
  		cout<<"空单元链表为空！"<<endl;
  		return;
  	}
  	cout<<"空链表";
  	while(L[i].cur != 0) {
  		cout<<"["<<L[i].cur<<"]"<<"-";
  		i = L[i].cur;
  	}
  	cout<<"end"<<endl;
  }
  

• 静态单循环链表.cpp

  #include<iostream>
  #include"CStaticLinkList.h"
  
  int main(void){
  	StaticLinkList L;
  	ElemType e;
  	int i;
  	int n;
  	int j, k, l;
  	
  	menu();
  	while(1){
  		cout<<"--请输入指令："<<endl;
  		cin>>i;
  		
  		switch(i){
  			case 0:
  				cout<<"感谢使用！"<<endl; 
  				exit(1);
  			case 1:
  				InitialList(L);
  				cout<<"初始化完成！"<<endl;
  				break;
  			case 2:
  				n = ListLength(L);
  				cout<<"链表长度为："<<n<<endl;
  				break;
  			case 3:
  				cout<<"请输入位置："<<endl;
  				cin>>j;
  				Locate(L, j, e);
  				break;
  			case 4:
  				cout<<"请输入需要查找的元素："<<endl;
  				cin>>e;
  				Search(L, e, j);
  				break;
  			case 5:
  				cout<<"请输入插入位置："<<endl;
  				cin>>j;
  				cout<<"请输入插入元素："<<endl;
  				cin>>e; 
  				if(InsertList(L, j, e) == true){
  					cout<<"插入成功！"<<endl; 
  				}
  				break;
  			case 6:
  				cout<<"请输入需要删除的元素的位置：" ;
  				cin>>j;
  				Delecte(L, j);
  				break;
  			case 7:
  				TCreate(L);
  				break;
  			case 8:
  				HCreate(L);
  				break;
  			case 9:
  				PrintData(L);
  				break;
  			case 10:
  				PrintNull(L);
  				break;
  			default:
  				cout<<"请输入合法指令！"<<endl; 
  		}	
  	}
  	system("pause");
  	return 0;
  }

• CStaticLinkList.h

  #include<iostream>
  
  #define MAX_SIZE 10
  #define ElemType char
  
  using namespace std;
  
  typedef struct{
  	ElemType data;
  	int cur;//静态链表中的游标 
  }Component, StaticLinkList[MAX_SIZE];
  
  //菜单 
  void menu(){
  	cout<<"*******************************************"<<endl;
  	cout<<"0.退出程序"<<endl;
  	cout<<"1.单链表初始化"<<endl;
  	cout<<"2.求链表长度"<<endl;
  	cout<<"3.按序号定位元素"<<endl;
  	cout<<"4.按给定值查找元素"<<endl;
  	cout<<"5.插入元素"<<endl;
  	cout<<"6.删除元素"<<endl;
  	cout<<"7.尾插法创建链表"<<endl;
  	cout<<"8.头插法创建链表"<<endl;
  	cout<<"9.打印数据链表"<<endl;
  	cout<<"10.打印空单元下表"<<endl;
  	cout<<"*******************************************"<<endl; 
  }
  
  //获得静态链表第一个空闲单元的下标
  int New(StaticLinkList &space){
  	int i = space[0].cur;
  	
  	if(space[0].cur != 0){//将第一个空闲单元从空链表中删除 
  		space[0].cur = space[i].cur;
  	}
  	
  	return i;
  } 
  
  //1.初始化静态链表 
  void InitialList(StaticLinkList &space){
  	int i;
  	for(i=0; i<MAX_SIZE; i++){//每一个元素指向数组的下一个元素 
  		space[i].cur = i+1;
  	}
  	space[MAX_SIZE-2].cur = 0;//空链表最后一个元素指向0 
  	space[MAX_SIZE-1].cur = MAX_SIZE;//数据链表最后一个指向MAX_SIZE 
  }
  
  
  //2.求链表长度
  int  ListLength(StaticLinkList &space){
  	int i=MAX_SIZE-1;//用于遍历链表 
  	int n=0;//记录链表长度 
  	if(space[i].cur == MAX_SIZE){//p判断是否为空表 
  		return n;
  	}
  	i = space[i].cur;
  	n++; 
  	while(space[i].cur != space[MAX_SIZE-1].cur){//数据链表最后一个单元的游标为space[MAX_SIZE].cur
  		i = space[i].cur;
  		n++;
  	}
  	return n;
  }
  
  //3.按序号定位元素
  void Locate(StaticLinkList &L, int &i, ElemType &e){
  	int k, l=0; 
  	k = MAX_SIZE-1;//k指向数据链表的头节点 
  	
  	if(ListLength(L) == 0){//判断是否为空表 
  		cout<<"静态链表为空！"<<endl;
  		return;
  	}
  	 
  	if(i<1 || i>ListLength(L)){//判断查找位置是否合法 
  		cout<<"查找位置不合法！"<<endl;
  		return;
  	}
  	
  	while(l<=i-1){//找到查找位置 
  		k = L[k].cur;
  		l++;
  	}
  	e = L[k].data;//将查找元素的位置赋值给e 
  	cout<<"定位成功，该位置元素为"<<e<<endl; 
  	return;
  } 
  
  //4.按给定值查找元素
  void Search(StaticLinkList &L, ElemType &e, int &i){
  	int j;
  	j = L[MAX_SIZE-1].cur;//j指向第一个元素 
  	
  	if(ListLength(L) == 0){//判断是否为空表 
  		cout<<"静态链表为空！"<<endl;
  		return;
  	}
  	while(L[j].data != e && L[j].cur != MAX_SIZE){//遍历查找元素。找到或遍历完链表时退出。 
  		j = L[j].cur;
  	}
  	
  	if(L[j].data == e){ //找到，给出提示并传出位置 
  		i = j;
  		cout<<"查找成功,该元素的位置下标为"<<i<<endl; 
  	}
  	else{//找不到，给出提示 
  		cout<<"查找失败！"<<endl;
  	}
  	return;
  }
  
  
  //5.插入元素
  bool InsertList(StaticLinkList &L, int &i, ElemType &e){//i为插入位置，e为插入元素 
  	int j, k, l=1; 
  	int length = ListLength(L); 
  	k = MAX_SIZE-1;//k指向数组的最后一个元素
  	 
  	if(i<1 || i>ListLength(L)+1){//判断插入位置是否合法 
  		cout<<"插入位置不合法！"<<endl;
  		return false;
  	}
  	
  	j = New(L);//j为第一个空闲单元下标 
  	if(j == 0){//判断数组是否已满 
  		cout<<"内存已满，无法插入元素！"<<endl;
  		return false;
  	}
  	else{
  		L[j].data = e;
  		while(l<=i-1){//找到插入位置 
  			k = L[k].cur;
  			l++;
  		}
  		//将新单元插入到元素链表 
  		L[j].cur = L[k].cur;
  		L[k].cur = j;
  		//如果插入位置为第一个位置，则需要更新数据链表最后一个节点的指向 
  		if(i == 1){ 
  			l = 0;
  			k =  MAX_SIZE-1;
  			while(l<length+1){
  				k = L[k].cur;
  				l++;
  			}
  			L[k].cur = j;
  		} 
  	}
  	return true;
  }
  
  //6.删除元素
  void Delecte(StaticLinkList &L, int &i){
  	int k, l=1; 
  	int j; 
  	int length = ListLength(L);
  	k = MAX_SIZE-1;//k指向数据链表的头节点 
  	
  	if(ListLength(L) == 0){//判断是否为空表 
  		cout<<"静态链表为空！"<<endl;
  		return;
  	}
  	
  	if(i<1 || i>ListLength(L)){//判断删除位置是否合法 
  		cout<<"删除位置不合法！"<<endl;
  		return;
  	}
  	
  	while(l<=i-1){//找到删除位置的前一个元素 
  		k = L[k].cur;
  		l++;
  	}
  	
  	//从数据链表中删除该元素
  	j = L[k].cur;//暂存删除元素位置
  	L[k].cur = L[j].cur;//删除元素的前一个元素指向删除元素的后一个元素 
  	
  	//将删除元素链接到空链表中 
  	L[j].cur = L[0].cur;//删除元素指向第一个空单元
  	L[0].cur = j;//空链表头指针指向删除元素
  	
  	//若删除元素为第一个节点时，还要更新最后一个节点的指向
  	if(i == 1){
  		l = 0;
  		k =  MAX_SIZE-1;
  		while(l < length-1){
  			k = L[k].cur;
  			l++;
  		}
  		L[k].cur = L[MAX_SIZE-1].cur;
  	} 
  	
  	cout<<"删除成功!"<<endl;
  }
  
  
  //7.尾插法创建链表
  void TCreate(StaticLinkList &L){
  	int j;
  	int k;
  	ElemType e;
  	k = MAX_SIZE-1;
  	cout<<"请输入字符（以#结束）："<<endl;
  	cin>>e; 
  	while(e != '#'){
  		j = New(L);//获取一个空单元
  		if(j == 0){
  			cout<<"链表已满！"<<endl;
  			return;
  		}
  		L[j].data = e;//赋值
  		L[k].cur = j;//链接到链表尾部
  		k = j;//更新指针
  		cin>>e;
  	}
  	L[k].cur = L[MAX_SIZE-1].cur;//最后一个节点指向第一个节点 
  	cout<<"创建成功！"<<endl; 
  } 
  
  //8.头插法创建链表
  void HCreate(StaticLinkList &L){
  	int i=1;
  	int j;
  	int k=MAX_SIZE; //暂存最后一个节点下标 
  	ElemType e;
  	cout<<"请输入字符（以#结束）："<<endl;
  	cin>>e;
  	do{
  		j = New(L);//获取一个空单元
  		if(j == 0){
  			cout<<"链表已满！"<<endl;
  			return;
  		}
  		if(k == MAX_SIZE){//记录最后一个节点的下标 
  			k = j;
  		} 
  		L[j].data = e;//赋值
  		L[j].cur = L[MAX_SIZE-1].cur;//新节点指向当前第一个节点 
  		L[MAX_SIZE-1].cur = j;//新节点链接到链表头部  
  		cin>>e;
  	}while(e != '#');
  	L[k].cur = L[MAX_SIZE-1].cur;
  	cout<<"创建成功！"<<endl;
  } 
  
  //9.打印数据链表
  void PrintData(StaticLinkList &L){
  	int i=MAX_SIZE-1;//用于遍历链表 
  	if(L[i].cur == MAX_SIZE){
  		cout<<"数据链表为空！"<<endl;
  		return;
  	}
  	cout<<"数据链表：";
  	i = L[i].cur;
  	while(L[i].cur != L[MAX_SIZE-1].cur){//数据链表最后一个单节点指向第一个节点 
  		cout<<"["<<i<<"]"<<L[i].data<<"-";
  		i = L[i].cur;
  	}
  	cout<<"["<<i<<"]"<<L[i].data<<"-";
  	cout<<"end"<<endl;
  }
  //10.打印空单元下标 
  void PrintNull(StaticLinkList &L){
  	int i=0;//用于遍历链表
  	if(L[i].cur == 0){
  		cout<<"空单元链表为空！"<<endl;
  		return;
  	}
  	cout<<"空链表";
  	while(L[i].cur != 0) {
  		cout<<"["<<L[i].cur<<"]"<<"-";
  		i = L[i].cur;
  	}
  	cout<<"end"<<endl;
  }
  

• 静态双循环链表.cpp

  #include<iostream>
  #include"DCStaticLinkList.h"
  
  int main(void){
  	StaticLinkList L;
  	ElemType e;
  	int i;
  	int n;
  	int j, k, l;
  	
  	menu();
  	while(1){
  		cout<<"--请输入指令："<<endl;
  		cin>>i;
  		
  		switch(i){
  			case 0:
  				cout<<"感谢使用！"<<endl; 
  				exit(1);
  			case 1:
  				InitialList(L);
  				cout<<"初始化完成！"<<endl;
  				break;
  			case 2:
  				n = ListLength(L);
  				cout<<"链表长度为："<<n<<endl;
  				break;
  			case 3:
  				cout<<"请输入位置："<<endl;
  				cin>>j;
  				Locate(L, j, e);
  				break;
  			case 4:
  				cout<<"请输入需要查找的元素："<<endl;
  				cin>>e;
  				Search(L, e, j);
  				break;
  			case 5:
  				cout<<"请输入插入位置："<<endl;
  				cin>>j;
  				cout<<"请输入插入元素："<<endl;
  				cin>>e; 
  				if(InsertList(L, j, e) == true){
  					cout<<"插入成功！"<<endl; 
  				}
  				break;
  			case 6:
  				cout<<"请输入需要删除的元素的位置：" ;
  				cin>>j;
  				Delecte(L, j);
  				break;
  			case 7:
  				TCreate(L);
  				break;
  			case 8:
  				HCreate(L);
  				break;
  			case 9:
  				PrintData(L);
  				break;
  			case 10:
  				PrintNull(L);
  				break;
  			default:
  				cout<<"请输入合法指令！"<<endl; 
  		}	
  	}
  	system("pause");
  	return 0;
  }

• DCStaticLinkList.h

  #include<iostream>
  
  #define MAX_SIZE 10
  #define ElemType char
  
  using namespace std;
  
  typedef struct{
  	ElemType data;
  	int cur;// 后继游标 
  	int rear;//前驱游标
  }Component, StaticLinkList[MAX_SIZE];
  
  //菜单 
  void menu(){
  	cout<<"*******************************************"<<endl;
  	cout<<"0.退出程序"<<endl;
  	cout<<"1.单链表初始化"<<endl;
  	cout<<"2.求链表长度"<<endl;
  	cout<<"3.按序号定位元素"<<endl;
  	cout<<"4.按给定值查找元素"<<endl;
  	cout<<"5.插入元素"<<endl;
  	cout<<"6.删除元素"<<endl;
  	cout<<"7.尾插法创建链表"<<endl;
  	cout<<"8.头插法创建链表"<<endl;
  	cout<<"9.打印数据链表"<<endl;
  	cout<<"10.打印空单元下表"<<endl;
  	cout<<"*******************************************"<<endl; 
  }
  
  //获得静态链表第一个空闲单元的下标
  int New(StaticLinkList &space){
  	int i = space[0].cur;
  	
  	if(space[0].cur != 0){//将第一个空闲单元从空链表中删除 
  		space[0].cur = space[i].cur;
  	}
  	
  	return i;
  } 
  
  //1.初始化静态链表 
  void InitialList(StaticLinkList &space){
  	int i;
  	for(i=0; i<MAX_SIZE; i++){//每一个元素指向数组的下一个元素 
  		space[i].cur = i+1;
  	}
  	space[MAX_SIZE-2].cur = 0;//空链表最后一个元素指向0 
  	space[MAX_SIZE-1].cur = MAX_SIZE;//数据链表最后一个指向MAX_SIZE 
  }
  
  
  //2.求链表长度
  int  ListLength(StaticLinkList &space){
  	int i=MAX_SIZE-1;//用于遍历链表 
  	int n=0;//记录链表长度 
  	if(space[i].cur == MAX_SIZE){//p判断是否为空表 
  		return n;
  	}
  	i = space[i].cur;
  	n++; 
  	while(space[i].cur != space[MAX_SIZE-1].cur){//数据链表最后一个单元的游标为space[MAX_SIZE].cur
  		i = space[i].cur;
  		n++;
  	}
  	return n;
  }
  
  //3.按序号定位元素
  void Locate(StaticLinkList &L, int &i, ElemType &e){
  	int k, l=0; 
  	k = MAX_SIZE-1;//k指向数据链表的头节点 
  	
  	if(ListLength(L) == 0){//判断是否为空表 
  		cout<<"静态链表为空！"<<endl;
  		return;
  	}
  	 
  	if(i<1 || i>ListLength(L)){//判断查找位置是否合法 
  		cout<<"查找位置不合法！"<<endl;
  		return;
  	}
  	
  	while(l<=i-1){//找到查找位置 
  		k = L[k].cur;
  		l++;
  	}
  	e = L[k].data;//将查找元素的位置赋值给e 
  	cout<<"定位成功，该位置元素为"<<e<<endl; 
  	return;
  } 
  
  //4.按给定值查找元素
  void Search(StaticLinkList &L, ElemType &e, int &i){
  	int j;
  	j = L[MAX_SIZE-1].cur;//j指向第一个元素 
  	
  	if(ListLength(L) == 0){//判断是否为空表 
  		cout<<"静态链表为空！"<<endl;
  		return;
  	}
  	while(L[j].data != e && L[j].cur != MAX_SIZE){//遍历查找元素。找到或遍历完链表时退出。 
  		j = L[j].cur;
  	}
  	
  	if(L[j].data == e){ //找到，给出提示并传出位置 
  		i = j;
  		cout<<"查找成功,该元素的位置下标为"<<i<<endl; 
  	}
  	else{//找不到，给出提示 
  		cout<<"查找失败！"<<endl;
  	}
  	return;
  }
  
  
  //5.插入元素
  bool InsertList(StaticLinkList &L, int &i, ElemType &e){//i为插入位置，e为插入元素 
  	int j, k, l=0; 
  	int length = ListLength(L); 
  	k = MAX_SIZE-1;//k指向数组的最后一个元素
  	 
  	if(i<1 || i>ListLength(L)+1){//判断插入位置是否合法 
  		cout<<"插入位置不合法！"<<endl;
  		return false;
  	}
  	
  	j = New(L);//j为第一个空闲单元下标 
  	if(j == 0){//判断数组是否已满 
  		cout<<"内存已满，无法插入元素！"<<endl;
  		return false;
  	}
  	else{
  		L[j].data = e;
  		//当数据表为空表时,插入节点既是首节点又是尾节点
  		if(L[k].cur == MAX_SIZE){
  			L[k].cur = j;//头指针指向首节点
  			L[j].cur = j;//尾节点指向首节点 
  			L[j].rear = j; //首节点指向尾节点 
  		}
  		else{
  			while(l<=i-1){//找到插入位置 
  			k = L[k].cur;//指针后移 
  			l++;//计数序号加1 
  			}
  			//将新单元插入到元素链表 
  			L[j].cur = k;//新节点前驱指针指向插入位置的节点 
  			L[j].rear = L[k].rear;//新节点的后继指针指向插入位置的前驱节点 
  			L[L[j].rear].cur = j;//插入位置的前驱节点的后继指针指向新节点 
  			L[k].rear = j;//插入位置的前驱节点更新为新节点 
  			if(i == 1){//当插入位置为1时，还需将头指针指向首节点 
  				L[MAX_SIZE-1].cur = j;
  			} 
  		}
  	}
  	return true;
  }
  
  //6.删除元素
  void Delecte(StaticLinkList &L, int &i){
  	int k, l=0; 
  	int j; 
  	int length = ListLength(L);
  	k = MAX_SIZE-1;//k指向数据链表的头节点 
  	
  	if(ListLength(L) == 0){//判断是否为空表 
  		cout<<"静态链表为空！"<<endl;
  		return;
  	}
  	
  	if(i<1 || i>ListLength(L)){//判断删除位置是否合法 
  		cout<<"删除位置不合法！"<<endl;
  		return;
  	}
  	
  	
  	if(ListLength(L) == 1){//当链表中只有一个节点时单独处理 
  		L[k].cur = L[0].cur;
  		L[0].cur = k;
  		L[MAX_SIZE-1].cur = MAX_SIZE;
  	}
  	else{
  		//找到删除位置
  		while(l<=i-1){ 
  			k = L[k].cur;
  			l++;
  		}
  		//从数据链表中删除该元素
  		L[L[k].rear].cur = L[k].cur;
  		L[L[k].cur].rear = L[k].rear;
  		if(i == 1){//如果删除的是首节点，需要让头节点指向首节点 
  			L[MAX_SIZE-1].cur = L[k].cur;
  		}
  		//将删除元素链接到空链表中
  		L[k].cur = L[0].cur;
  		L[0].cur = k;
  		
  	}
  	
  	cout<<"删除成功!"<<endl;
  }
  
  
  //7.尾插法创建链表
  void TCreate(StaticLinkList &L){
  	int j;
  	int k;
  	int flag=1;
  	ElemType e;
  	k = MAX_SIZE-1;
  	cout<<"请输入字符（以#结束）："<<endl;
  	cin>>e; 
  	while(e != '#'){
  		j = New(L);//获取一个空单元
  		if(j == 0){
  			cout<<"链表已满！"<<endl;
  			return;
  		}
  		L[j].data = e;//赋值
  		
  		if(flag == 1){//插入第一个节点时单独处理 
  			L[k].cur = j;//头指针指向第一个节点 
  			k = j;//更新指针 
  			flag++;//更改标识 
  		}
  		else{//新节点链接到链表尾部
  			L[j].rear = k;
  			L[k].cur = j;
  			k = j;//更新指针
  		}
  		cin>>e;
  	}
  	L[k].cur = L[MAX_SIZE-1].cur;//最后一个节点的后继指针指向第一个节点
  	L[L[MAX_SIZE-1].cur] .rear= k;//首节点的前驱指针指向尾节点
  	 
  	cout<<"创建成功！"<<endl; 
  } 
  
  //8.头插法创建链表
  void HCreate(StaticLinkList &L){
  	int i=1;
  	int j;
  	int flag=1; 
  	int k=MAX_SIZE-1; //暂存最后一个节点下标 
  	ElemType e;
  	cout<<"请输入字符（以#结束）："<<endl;
  	cin>>e;
  	do{
  		j = New(L);//获取一个空单元
  		if(j == 0){
  			cout<<"链表已满！"<<endl;
  			return;
  		}
  		L[j].data = e;//赋值
  		
  		if(flag == 1){//第一次插入元素时单独处理 
  			k = j;//暂存最后一个节点 
  			flag++; //更改标识 
  		}
  		else{
  			L[j].cur = L[MAX_SIZE-1].cur;//新节点的前驱指针指向当前第一个节点 
  			L[MAX_SIZE-1].rear = j;//上一个节点的后继指针指向新节点
  		}
  		
  		L[MAX_SIZE-1].cur = j;//头指针指向新节点   
  		cin>>e;
  	}while(e != '#');
  	
  	L[k].cur = j;//尾节点的后继指针指向首节点
  	L[j].rear = k;//首节点的前驱指针指向尾节点
  	
  	cout<<"创建成功！"<<endl;
  } 
  
  //9.打印数据链表
  void PrintData(StaticLinkList &L){
  	int i=MAX_SIZE-1;//用于遍历链表 
  	if(L[i].cur == MAX_SIZE){
  		cout<<"数据链表为空！"<<endl;
  		return;
  	}
  	cout<<"数据链表：";
  	i = L[i].cur;
  	while(L[i].cur != L[MAX_SIZE-1].cur){//数据链表最后一个单节点指向第一个节点 
  		cout<<"["<<i<<"]"<<L[i].data<<"-";
  		i = L[i].cur;
  	}
  	cout<<"["<<i<<"]"<<L[i].data<<"-";
  	cout<<"end"<<endl;
  }
  //10.打印空单元下标 
  void PrintNull(StaticLinkList &L){
  	int i=0;//用于遍历链表
  	if(L[i].cur == 0){
  		cout<<"空单元链表为空！"<<endl;
  		return;
  	}
  	cout<<"空链表";
  	while(L[i].cur != 0) {
  		cout<<"["<<L[i].cur<<"]"<<"-";
  		i = L[i].cur;
  	}
  	cout<<"end"<<endl;
  }
  

  ---

  感谢您的阅读！?

  ---