数据结构-线性表|顺序表|链表(中)

本节纲要

• 预备知识
• 顺序表(Sequential List)
• 单链表(Singly Linked List )
• 静态链表(Static list )
• 循环链表(circular linked list)
• 双向链表(doubly linked list)

03 单链表(Singly Linked List )

3.1 什么是单链表？

单链表是一种链式存储的结构。它动态的为节点分配存储单元。当有节点插入时，系统动态的为结点分配空间。在结点删除时，应该及时释放相应的存储单元，以防止内存泄露。由于是链式存储，所以操作单链表时，必须知道头结点或者头指针的位置。并且，在查找第i个节点时，必须找到第i-1个节点。

3.2 单链表的存储结构代码描述

对于链式存储，通过上一节的讲解相信大家已经了解得够清楚了。如下图所示：

下面我们来看看单链表存储是如何用代码来实现的。

//单链表的存储结构C语言代码
typedef struct SListNode
{
    datatype data;    //数据域
    struct SListNode * pnext;//指针域
}SLinkList;

由上面的结构我们可以看出，一个节点由存放数据的数据域和存放地址的指针域组成。假如p指向了第i个节点，那么p->data就是该节点存放的数据，而p->pnext自然就是指向下一个节点的指针。如下图所示：

那么接下来我们看看单链表的各个操作具体实现吧。(只讲几个关键步骤)
备注：下面的代码基于这样的一个单链表：

• 有一个头指针phead
• 有一个头结点node
• 头指针指向头结点，头结点位置记为0

  3.3 单链表的读取

  在拿到头指针以后，单链表的读取也并非一件难事。一开始设置一个计数变量，不断遍历链表，让计数器自增。找到合适的位置将数据读取出来。具体代码实现如下：

  #define status bool
  #define ERROR false
  #define OK true
  /*
   * 函数功能：获取位置index节点的数据
   * 参数说明：phead链表头结点，e用来获取的变量，index索引
  */
  
  status GetSListIndexNode(Node * phead,DType *e, int index)
  {
  	int icount = 0; //计数器
      //注：0号位为头结点，头结点不存放任何数据
  	if (phead->pnext == nullptr || index < 1 || index > GetSListLength()/*此处为链表长度*/)
  	{
  		return ERROR; //异常 处理
  	}
  	while (phead->pnext != nullptr)
  	{
  		icount++;
  		phead = phead->pnext;
  		if (icount == index)
  		{
  			*e = phead->data;
  			return OK;
  		}
  	}
  	return ERROR;
  }

3.4 单链表的插入

3.4.1 指定位置后插

其实链表的插入和删除都是很简单的操作，初学者只要抓住指针指向的节点，并加以区分开来，就很easy了。如下图：

图中，假如此时p指向了我们要插入的节点的位置。那么，怎样把我们的S节点给插入到p指向的节点之后？在这里我们先不要惊动p以及p后面的节点：

1. 我们先让S节点指向p之后的节点(步骤①)
2. 之后我们切断p和p后面那个节点的关系(步骤②)
3. 最后让p节点的指针域指向s节点(步骤③)，搞定

算法描述：

1. 声明一个指针p指向链表头结点，向后遍历p=p->next，找到正确的位置。
2. 新建一个结点s。
3. s->next = p->next ①
4. p->next = s ②③
   具体代码如下：

   #define status bool
   #define ERROR false
   #define OK true
   /*
    * 函数功能：指定位置后插
    * 参数说明：phead链表头结点，IData插入的数据，index索引
   */
   status InsertSListNodeFront(Node * phead, DType IData, int index)
   {
   	if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
   	{
   		return ERROR; //异常 处理
   	}
   	int iCount = 0; //计数器
   	Node<DType> * q = nullptr; //备用
   	while (phead->pnext != nullptr)
   	{
   		iCount++;
   		q = phead;
   		phead = phead->pnext;
   		if ( iCount == index )
   		{
   			Node<DType> * p = new Node<DType>;
   			p->data = IData;
   			p->pnext = phead;
   			q->pnext = p;   //前插
   			return OK;
   		}
   	}
   	return ERROR;
   }

3.4.1 指定位置前插

咳咳，聪明的小伙伴，用脑子想想。指定位置前插 == 指定位置的前一个位置进行后插。懂了吧？直接看具体代码：

/*
 * 函数功能：指定位置后插
 * 参数说明：phead链表头结点，IData插入的数据，index索引
*/
status InsertSListNodeBack(Node * phead, DType IData, int index)
{
	if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
	{
		return ERROR; //异常 处理
	}
	int iCount = 0; //计数器
	Node<DType> * q = nullptr; //备用
	while (phead->pnext != nullptr)
	{
		iCount++;
		q = phead;
		phead = phead->pnext;
		if (iCount == index)
		{
			Node<DType> * p = new Node<DType>;
			q = phead;
			phead = phead->pnext; //后插就是后一个节点的前插咯
			p->data = IData;
			p->pnext = phead;
			q->pnext = p;   
			return OK;
		}
	}
	return ERROR;
}

3.5 单链表的删除

单链表的删除其实也是很简单。只要比如要删除p指向的节点，只需要让p之前的节点的指针域直接指向p之后的节点，再把p给free就OK了。如下图：

算法描述:

1. 声明一个指针p指向链表头结点，向后遍历p=p->next，找到要删除的节点位置。
2. q = p->next
3. p->next = q->next ①②
4. free(q) ③④

具体代码如下:

/*
 * 函数功能：指定位置后插
 * 参数说明：phead链表头结点，IData获取删除的数据，index索引
*/
//删除指定位置节点(e获取删除元素)
template <typename DType>
status DeleteSListIndexNode(Node * phead, DType *e, int index)
{
	int i = 0; //计数器
	Node<DType> * q = nullptr;
	if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
	{
		return ERROR; //异常 处理
	}
	while (phead->pnext != nullptr)
	{
		i++;
		q = phead; //保存备用
		phead = phead->pnext;
		if (i == index)
		{
			*e = phead->data;
			q->pnext = phead->pnext; //删除出局
			return OK;
		}
	}
	return ERROR;
}

代码应该不难，相信大家都能很容易看懂。

3.6 单链表的完整代码

好了，前面介绍了几个重要的操作，接下来请大家看看完整的代码吧。小编为了使用方便，就用C++的class和template将整个链表封装到了一个类里面，通过模板实现泛型编程。

/*
 * 文件名:SingleLinkList.h
 * 说明 ：类的各种声明
 */
#pragma once //VC编译器防止头文件被重复包含的一条预编译指令

#define status bool
#define OK true
#define ERROR false
#define YES true
#define NO false

template <typename DType>
class Node
{
public:
	DType data;
	Node * pnext;
};

template <typename DType>
class CSingleLinkList
{
private:
	Node<DType> *phead; //链表头指针
public:
	CSingleLinkList();//构造，类被创建时调用
	~CSingleLinkList();//析构，类被销毁时调用
public:
	//初始化链表
	status InitSList();
	//获取链表长度
	int GetSListLength();
	//增加一个节点 前插法
	status AddSListNodeFront(DType idata);
	//增加一个节点 后插法
	status AddSListNodeBack( DType idata);
	//判断链表是否为空
	status IsSListEmpty();
	//获取指定位置节点值(注意，本程序规定0号为头节点，e获取删除元素)
	status GetSListIndexNode(DType *e, int index);
	//删除指定位置节点(e获取删除元素)
	status DeleteSListIndexNode(DType *e, int index);
	//查找链表中指定值(pindex获取位置0==>not found)
	status SearchSListNode(DType SData, int *pindex);
	//指定位置前插
	status InsertSListNodeFront(DType IData, int index);
	//指定位置后插
	status InsertSListNodeBack(DType IData, int index);
	//清空链表(保留根节点)
	status ClearSList();
	//销毁链表(all delete)
	status DestorySList();
	//尾部删除一个元素
	status DeleteSListNodeBack();
	//打印链表   此函数根据实际情况而定
	void PrintSList();
};

/*
 * 文件名:SingleLinkList.cpp
 * 说明 ：类的各种方法的实现
 */

#include "SingleLinkList.h"
#include <stdio.h>

template <typename DType>
CSingleLinkList<DType>::CSingleLinkList()
{
	cout << "链表创建" << endl;
	InitSList();
}
template <typename DType>
CSingleLinkList<DType>::~CSingleLinkList()
{
	cout << "链表销毁" << endl;
	DestorySList();
}
//初始化链表
template <typename DType>
status CSingleLinkList<DType>::InitSList()
{
	Node<DType> * ph = new Node<DType>;
	if (ph != NULL)
	{
		ph->pnext = nullptr;
		this->phead = ph; //头结点
		return OK;
	}
	return ERROR;
}
//获取链表长度(head_node is not included)
template <typename DType>
int CSingleLinkList<DType>::GetSListLength()
{
	int length = 0;
	Node<DType> * phead = this->phead;
	while (phead->pnext != nullptr)
	{
		length++;
		phead = phead->pnext;
	}
	return length;
}
//增加一个节点 前插法
template <typename DType>
status CSingleLinkList<DType>::AddSListNodeFront( DType idata)
{
	Node<DType> * pnode = new Node<DType>;
	if (pnode != NULL)
	{
		pnode->data = idata;
		pnode->pnext = this->phead->pnext;
		this->phead->pnext = pnode; //挂载
		
		//printf("pnode = %p  pnode->pnext = %p this->phead->pnext = %p this->phead = %p\n", pnode, pnode->pnext, this->phead->pnext, this->phead);
		return OK;
	}
	return ERROR;
}


//增加一个节点 尾插法
template <typename DType>
status CSingleLinkList<DType>::AddSListNodeBack(DType idata)
{
	Node<DType> * pnode = new Node<DType>;
	Node<DType> * phead = this->phead;
	if (pnode != NULL)
	{
		while (phead->pnext != nullptr)
		{
			phead = phead->pnext;
		}
		pnode->data = idata;
		pnode->pnext = nullptr;
		phead->pnext = pnode; //挂载
		return OK;
	}
	return ERROR;
}
//判断链表是否为空
template <typename DType>
status CSingleLinkList<DType>::IsSListEmpty()
{
	if (this->phead->pnext == nullptr)
	{
		return YES;
	}
	return NO;
}
//获取指定位置节点值(注意，本程序规定0号为头节点，e获取节点的值)
template <typename DType>
status CSingleLinkList<DType>::GetSListIndexNode(DType *e, int index)
{
	Node<DType> * phead = this->phead;
	int i = 0; //计数器
	if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
	{
		return ERROR; //异常 处理
	}
	while (phead->pnext != nullptr)
	{
		i++;
		phead = phead->pnext;
		if (i == index)
		{
			*e = phead->data;
			return OK;
		}
	}
	return ERROR;
}
//删除指定位置节点(e获取删除元素)
template <typename DType>
status CSingleLinkList<DType>::DeleteSListIndexNode( DType *e, int index)
{
	Node<DType> * phead = this->phead;
	int i = 0; //计数器
	Node<DType> * q = nullptr;
	if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
	{
		return ERROR; //异常 处理
	}
	while (phead->pnext != nullptr)
	{
		i++;
		q = phead; //保存备用
		phead = phead->pnext;
		if (i == index)
		{
			*e = phead->data;
			q->pnext = phead->pnext; //删除出局
			return OK;
		}
	}
	return ERROR;
}
//查找链表中指定值(pindex获取位置   0==>not found)
template <typename DType>
status CSingleLinkList<DType>::SearchSListNode( DType SData, int *pindex)
{
	Node<DType> * phead = this->phead;
	int iCount = 0;//计数器
	while (phead->pnext != nullptr)
	{
		iCount++;
		phead = phead->pnext;
		if (phead->data == SData)
		{
			*pindex = iCount;
			return YES;
		}
	}
	*pindex = 0;
	return NO;
}
//指定位置前插
template <typename DType>
status CSingleLinkList<DType>::InsertSListNodeFront(DType IData, int index)
{
	Node<DType> * phead = this->phead;
	if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
	{
		return ERROR; //异常 处理
	}
	int iCount = 0; //计数器
	Node<DType> * q = nullptr; //备用
	while (phead->pnext != nullptr)
	{
		iCount++;
		q = phead;
		phead = phead->pnext;
		if ( iCount == index )
		{
			Node<DType> * p = new Node<DType>;
			p->data = IData;
			p->pnext = phead;
			q->pnext = p;   //前插
			return OK;
		}
	}
	return ERROR;
}
//指定位置后插
template <typename DType>
status CSingleLinkList<DType>::InsertSListNodeBack( DType IData, int index)
{
	Node<DType> * phead = this->phead;
	if (phead->pnext == nullptr || index < 1 || index > GetSListLength())
	{
		return ERROR; //异常 处理
	}
	int iCount = 0; //计数器
	Node<DType> * q = nullptr; //备用
	while (phead->pnext != nullptr)
	{
		iCount++;
		q = phead;
		phead = phead->pnext;
		if (iCount == index)
		{
			Node<DType> * p = new Node<DType>;
			q = phead;
			phead = phead->pnext; //后插就是后一个节点的前插咯
			p->data = IData;
			p->pnext = phead;
			q->pnext = p;   
			return OK;
		}
	}
	return ERROR;
}
//清空链表(保留根节点)
template <typename DType>
status CSingleLinkList<DType>::ClearSList()
{
	Node<DType> * phead = this->phead;
	Node<DType> * q = nullptr; //防止那啥，野指针
	phead = phead->pnext;//保留头节点
	while (phead != nullptr)
	{
		q = phead;
		phead = phead->pnext;
		delete q; //释放
	}
	this->phead->pnext = nullptr;
	return OK;
}
//销毁链表(all delete)
template <typename DType>
status CSingleLinkList<DType>::DestorySList()
{
	ClearSList();
	delete this->phead;//释放头结点 
	return OK;
}

template <typename DType>
status CSingleLinkList<DType>::DeleteSListNodeBack()
{
	Node<DType> * phead = this->phead;
	Node<DType> * q = nullptr; //备用
	if (phead->pnext == nullptr)
	{
		return ERROR; //链表都空了还删鸡毛
	}
	while (phead->pnext != nullptr)
	{
		q = phead;
		phead = phead->pnext;
	}
	q->pnext = nullptr;
	delete phead;

	return OK;
	
}
template <typename DType>
void CSingleLinkList<DType>::PrintSList()
{
	Node<DType> * phead = this->phead;
	if (phead->pnext == nullptr || phead == nullptr)
	{
		cout << "链表为空，打印鸡毛" << endl;
		return;
	}
	int i = 1;
	cout << "===============print list================" << endl;
	while (phead->pnext != nullptr)
	{
		phead = phead->pnext;
		cout <<"node[" << i++ << "] = " << phead->data<<endl;
	}
}

/*
 * 文件名:SingleLinkListTest.cpp
 * 说明 ：测试代码
 */

 #include <iostream>
#include "SingleLinkList.h"
#include "SingleLinkList.cpp"

using namespace std;

int main()
{
	CSingleLinkList<int> * pMySList = new CSingleLinkList<int>;
	cout << pMySList->IsSListEmpty() << endl;
	pMySList->AddSListNodeFront(111);
	pMySList->AddSListNodeFront(222);
	pMySList->AddSListNodeFront(333);

	cout << "链表长度" << pMySList->GetSListLength() << endl;

	pMySList->PrintSList();

	pMySList->AddSListNodeBack(444);
	pMySList->AddSListNodeBack(555);
	pMySList->AddSListNodeBack(666);

	pMySList->PrintSList();

	cout << pMySList->IsSListEmpty() << endl;
	cout << "链表长度" << pMySList->GetSListLength() << endl;

	int GetElem, GetIndex;
	pMySList->GetSListIndexNode(&GetElem, 2);
	cout << "Got Elem = " << GetElem << endl;

	pMySList->GetSListIndexNode(&GetElem, 6);
	cout << "Got Elem = " << GetElem << endl;

	pMySList->GetSListIndexNode(&GetElem, 4);
	cout << "Got Elem = " << GetElem << endl;

	pMySList->DeleteSListIndexNode(&GetElem, 1);
	cout << "del Elem = " << GetElem << endl;
	pMySList->DeleteSListIndexNode(&GetElem, 3);
	cout << "del Elem = " << GetElem << endl;
	

	pMySList->PrintSList();

	pMySList->SearchSListNode(555, &GetIndex);
	cout << "Search Index = " << GetIndex << endl;
	pMySList->SearchSListNode(111, &GetIndex);
	cout << "Search Index = " << GetIndex << endl;
	pMySList->SearchSListNode(666, &GetIndex);
	cout << "Search Index = " << GetIndex << endl;

	pMySList->InsertSListNodeFront(333, 1);
	pMySList->InsertSListNodeFront(444, 4);

	pMySList->PrintSList();

	pMySList->InsertSListNodeBack(777, 3);
	pMySList->InsertSListNodeBack(888, 5);

	pMySList->PrintSList();

	pMySList->DeleteSListNodeBack();
	pMySList->PrintSList();
	pMySList->DeleteSListNodeBack();
	pMySList->PrintSList();
	pMySList->DeleteSListNodeBack();
	pMySList->PrintSList();

	return 0;
}

代码如果有不正确的地方，欢迎大家来指正哈。

04 静态链表(circular linked list)

4.1 什么是静态链表？

我们把线性表的元素存放在数组中，这些元素由两个域组成：

• 数据域data
• 指针域cur

数据域是存放数据的，而指针域，这里和链表不同是，它存的不再是指向下一个节点的内存地址。而是下一个节点在数组中的下标。我们就把这种用数组描述的链表称为静态表，该方法也称之为游标实现法。如下图所示：

由上图我们需要注意以下几点：

• 我们对数组的第一个元素和最后一个元素做特殊处理，不存放数据。
• 把未使用的数组元素称为备用链表。
• 数组的第一个元素(下标为0)的cur域存放备用链表第一个节点的下标。
• 数组的最后一个元素的cur域存放第一个有数据的节点的下标，相当于链表中头结点的存在。链表为空时，其值为0。

如下图：

引出的问题：数组的长度定义的问题，无法预支。所以，为了防止溢出，我们一般将静态表开得大一点。

4.2 静态链表存储的代码描述

基于上面的讲解，我们来看看代码是怎么描述这种存储结构的。

//---------线性表的静态单链表存储结构--------
#define MAXSIZE 1000 /*假设链表最大长度为1000*/
typedef struct
{
    datatype data;
    int cur;   //为0时表示无指向
}SLinkList[MAXSIZE];

接下来我们讲解几个重要的操作实现。

4.3 静态链表的插入操作

前面我们讲动态链表的时候说过，增加和删除一个节点我们可以用malloc()和free()函数(C++可用new和delete)来实现。但是现在由于我们操作的是静态表，它可是用数组存的，可没有这种操作了。因此我们首先来自己实现一个静态表的malloc和free。

那么怎么辨别数组中哪些空间没有被使用呢？一个好的解决办法是，将所有未使用或者被删除的空间串成一个备用链表。插入节点时便可以从备用链表获取第一个未使用的空间的下标。因此我们在初始化的时候会做这样的工作：

void SListInit(SLinkList space)
{
    int i;
    for(i = 0; i < MAXSIZE; i++)
        space[i].cur = i+1; //将所有结点链入备用链表
    //备用链表头指针链像第二个结点
    space[0].cur = space[1].cur; 
    //第一个结点作为链表的头结点  
    space[1].cur = 0;              
}

分配内存

/分配备用链表的一个结点,返回下标
//若为0，则说明备用链表用完
int Malloc_SL(SLinkList space)
{
    int i = space[0].cur;
    //判断备用链表是否非空
    if(space[0].cur)    
        //备用链表头指针指向第二个空结点
        space[0].cur = space[i].cur; 

    return i;    //返回第一个空结点
}

上面的代码应该是没有难度的。写完了这个函数，我们来看看静态表中具体如何插入：

//在链表的第i个位置插入元素e
void SlistInsert(SLinkList space, int i, ElemType e)
{
    //超出范围
    if(i < 1 || i > SListLength(space)+1) 
        return;
    int k = 1, j;
    //使k指示要插入的结点的前一个结点
    for(j = 0; j <i-1; j++) 
        k = space[k].cur;

    int v = Malloc_SL(space);
    if(v)     //如果有空间
    {
        space[v].data = e;
        space[v].cur = space[k].cur;
        space[k].cur = v;  //链入链表
    }
}

注意几点：

• 首先我们让k指向了要插入节点(记为X)的前一个位置(记为Y节点)，前插法。
• 然后我们在静态表内申请空间，存放新的节点(记为N)。
• 把数据放进新申请的节点里面。
• 新节点N的cur域指向X节点，然后让Y节点指向N节点。

该过程不难理解。就不上图了……

4.4 静态链表的删除操作

删除同样需要自己实现free函数，我们来看看代码：

回收内存

//将下标为k的空闲结点回收到备用链表
void Free_SL(SLinkList space, int k)
{
    //将备用链表链到k之后
    space[k].cur = space[0].cur;  
    //将k链到备用链表头之后
    space[0].cur = k;               
}

删除以后记得把空间重新挂载到备用链表上以便下一次使用。下面我们实现删除的代码：

//删除第i个位置的元素
void SListDelete(SLinkList space, int i)
{   //超出范围退出
    if(i < 1 || i > SListLength(space))  
        return ;
    int k = 1, j;
     //使k指示要删除的结点的前一个结点
    for(j = 0; j <i-1; j++)  
        k = space[k].cur;

    int temp = space[k].cur;
    space[k].cur = space[temp].cur;
    Free_SL(space, temp);
}

其实代码也很好理解了。假如X、Y、Z……等等排列，我们要删除Y。无非就是告诉X，你不要指向Y了，你直接指向Z，然后我们再把Y给free了。就直接变成了X、Z……简单吧。

4.5 静态链表的完整代码

/*************************************
                静态链表
数据结构：每个数组节点都有值和游标.
游标表示下一个节点，节点分为已用节点和备用节点
第一个节点和最后节点保留：
第一个节点游标表示备用节点起始位置
最后一个节点游标表示已用节点的起始位置
已用节点的最后一个元素的游标指向0，表示末尾。
*************************************/
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#define ERROR 0
#define OK 1
#define MAX 100     //声明数组的最大长度

typedef int Status,ElemType;
typedef struct{
   int data;    //数据
   int cur;     //游标
}component,staticlink[MAX]; //定义结构体数组

/**********************************
         初始化链表
输入值：链表的指针
输出值：状态码
功能：  将所以节点的游标指向后一个节点
 ***********************************/
Status initLink(staticlink space)
{
  int i;
  for(i=0;i<(MAX-1);i++){  //遍历所有节点
    space[i].cur = i+1;　//将节点的游标指向下个节点
  }
  space[MAX-1].cur = 0; //最后一个节点的游标指向第一个节点
  return OK;
}

/*********************************
         分配备用空间
输入值：链表的指针
输出值：备用节点的下标
功能：  将备用节点的分配出来使用
 *********************************/
int mallocSpace(staticlink space)
{
  int i;
  i = space[0].cur;　//取出第一个备用节点
  if(space[0].cur)　　　　 //如果取出成功
    space[0].cur = space[i].cur; //第一个节点的指针往后移动
  return i;
}

/********************************
         获取长度
输入值：链表的指针
输出值：长度值
功能：  将链表中已用的节点个数返回
 ********************************/
int getLength(staticlink space)
{
  int mov = MAX-1;
  int j=0;
  while(space[mov].cur)
  {　//遍历所有已用节点
    mov = space[mov].cur;
    j++;
  }
  return j;
}
/*********************************
          创建值
输入值：链表的指针，初始值个数
输出值：状态码
功能：  为链表初始指定个数的随机值
 *********************************/
Status createValue(staticlink space,int num)
{
  srand(time(0));
  int i,mov = MAX-1;
  space[mov].cur = 1;
  for(i=0;i<num;i++)
  {
    mov = space[mov].cur;　　　　//移动游标
    space[mov].data = rand()%100+1;　　//初始化随机值
  }
  space[0].cur = space[mov].cur;//第一节点游标指向备用节点
  space[mov].cur = 0;　 //最后一个已用节点指向第一个节点
  return OK;
}

/*********************************
          插入节点
输入值：链表的指针，插入位置(从1开始)，插入位置
输出值：状态码
功能：  在指定的位置插入指定的值
 *********************************/
Status insertNode(staticlink space,int index,ElemType e)
{
  int new,mov,i;
  if(index<1 || index>getLength(space))return ERROR;  //不可以超过已用节点个数

  mov = MAX-1;
  new = mallocSpace(space);

  if(new){
    space[new].data=e;　//创建新节点
    for(i=1;i<index;i++)//定位插入节点的前一节点
      mov = space[mov].cur;

    space[new].cur = space[mov].cur;　//连后
    space[mov].cur = new;　　//接前
    return OK;
  }
  return ERROR;
}

/************************************
          删除节点
输入值：链表的指针，删除位置(从1开始)
输出值：状态码
功能：  删除指定的节点
 ************************************/
Status deleteNode(staticlink space,int index)
{
  if(index<1 || index>getLength(space))return ERROR;
  int mov,next,i;

  mov = MAX-1;
  for(i=1;i<index;i++)　//定位删除节点的前一节点
    mov = space[mov].cur;

  next = space[mov].cur;//获取被删节点
  space[mov].cur = space[next].cur; //前一节点连接被删节点的游标
  freeNode(space,next);//释放被删节点
  return OK;
}

/***********************************
          释放节点
输入值：链表的指针，释放节点的位置
输出值：状态码
功能:   将已用节点释放成备用节点
 ***********************************/
Status freeNode(staticlink space,int target)
{
  space[target].cur = space[0].cur;//释放节点连接第一备用节点
  space[0].cur = target;//第一节点连接释放节点
  return OK;
}

/**********************************
          输出链表
输入值：链表的指针
输出值：状态码
功能：  将链表的值一一输出
 **********************************/
Status printLink(staticlink space)
{
  int mov = MAX-1;
  while(space[mov].cur)
  {
    mov = space[mov].cur;
    printf("[%d] ",space[mov].data);
  }
  printf("\n");
  return OK;
}

int main()
{
  int num,value,index;
  staticlink L;
  initLink(L);

  printf("[create]enter num:");
  scanf("%d",&num);
  createValue(L,num);
  printLink(L);

  printf("[insert]enter index:");
  scanf("%d",&index);
  printf("[insert]enter value:");
  scanf("%d",&value);
  insertNode(L,index,value);
  printLink(L);

  printf("[delete]enter index:");
  scanf("%d",&index);
  deleteNode(L,index);
  printLink(L);
  return 0;

这次就先到这里吧。更多精彩内容，请期待下回分解。

另外：部分资料参考自网络，来源和作者实在无法考证，如果有侵犯到您的劳动成果，请速与我联系。

========================END=======================