学步园

  链表属于线性结构之一，主要功能是提供可动态扩展的线性结构，可使用不连续的的内存空间，为程序的动态特性提供支持。逻辑结构如下（图片引用自CSDN博客）

一般的定义如下

/*The Data Structure of Link List*/
typedef int DataType;
typedef struct LinkNode 
{
	DataType         data;
	struct LinkNode *next;
}*LinkList;

其中data用于存放数据，*next指向下一个结点，注意这个定义有递归的含义，因为*next的类型是LinkNode，这是在用自己定义自己，初学时也许会有点儿费解，但只要明白编译器仍然将其理解为一个指针就会清晰许多。下面给出链表的基本算法：（默认带头结点）

/*尾插法建立链表，链表元素顺序和数组一致*/
void CreateList(LinkList &L,DataType A[],int n)
{
	LinkNode *rear;
	L = rear = new LinkNode;
	for(int i=0; i<n; ++i)
	{
		rear->next =  new LinkNode;
		rear       =  rear->next;
		rear->data = A[i];
	}
	rear->next = NULL;
}

/*头插法建立链表，链表元素顺序和数组相反*/
void CreateList_reverse(LinkList &L,DataType A[], int n)
{
	L = new LinkNode;
	L->next = NULL;

	for( int i=0; i<n; ++i)
	{
		LinkNode *p = new LinkNode;
		p->data = A[i];
		p->next = L->next;
		L->next = p;
	}
}

/*链表逆置算法*/
void ReverseList(LinkList &L)
{
	LinkNode *pre = NULL;    /*two temporary node is needed to traverse the LinkList*/
	LinkNode * p  = L->next;

	while( p != NULL)
	{
		L->next = p->next;   /* p->next will change,so store it in the head node*/
		p->next = pre;        
		
		pre = p;             /* pre point to the new head */
		p   = L->next;       /* p point to the next position */
	}
	L->next = pre;           /* L-next point to the head of the reversed list*/
}

/*删除链表中的元素x*/
void DeleteList(LinkList &L,DataType x)
{
	for(LinkNode *pre=L,*p=L->next;  p!=NULL; pre=p,p=p->next )
		if( p->data == x)
		{
			pre->next = p->next; 
			delete p;
			return;
		}
}

/*插入链表元素x*/
void InsertList(LinkList &L ,DataType x)
{
	LinkNode *p = new LinkNode;
	p->data = x;
	p->next = L->next;
	L->next = p;	
}

/*显示链表所有元素，测试时比较有用*/
void DisplayList(LinkList &L)
{	
	cout<<endl;
	for( LinkNode *p = L->next;  p != NULL;  p = p->next )
	{ 	 cout<< p->data<<" ";	}
	cout<<endl;
}

/*链表的排序算法*/
void InsertSortList(LinkList &L)
{
	LinkNode *p     = L->next;        /*指向 待插入  结点 */
	LinkNode *nextp = NULL;           /*指向 p的后继 结点 */

	LinkNode *q     = L;              /*指向有序链表的头部*/
	q->next         = NULL;            

	while( p != NULL )
	{
		q = L;
		while(q->next!=NULL && p->data >= q->next->data) /*寻找插入位置，循环停止时，p应插入到q的后面*/
		{	q = q->next;		}

		nextp = p->next;  
		p->next = q->next;    /* p 的后继应是 q */
		q->next = p;
		p = nextp;	
	}
}

/*链表查找算法*/
LinkNode *SearchList(LinkList &L,DataType x)
{
	LinkNode *p = L->next;
	while( p!=NULL && p->data!=x )
	{	p = p->next;	}
	return p;	
}

/*链表销毁算法*/
void DestroyList(LinkList &L)
{
	if(L->next==NULL)
	{	
		cout<<"delete"<<L->data<<endl;
		delete L;	}
	else
	{	
		DestroyList(L->next);
		cout<<"delete"<<L->data<<endl;
		delete L;	
	}
}

上面给出了链表的的“创建”、“销毁”、 “插入”、“删除”、“查找”、 “逆置”、“遍历”、“排序”算法，这些基本算法可以构建起链表的几乎所有操作，下面给出基本测试代码：

int main()
{

	int A[6]={1,2,3,4,5,6};
	LinkList L;

	CreateList (L,A,6);
	DisplayList(L);

	ReverseList(L);
	DisplayList(L);

	InsertList (L,9);
	DisplayList(L);

	DeleteList (L,5);
	DisplayList(L);

	cout<<"after sort:";
	InsertSortList(L);
	DisplayList   (L);
	cout<<endl;

	LinkNode *p = SearchList(L,6);
	cout<<"search result:"<<p->data<<endl;

	cout<<"delete processing:"<<endl;
	DestroyList(L);

	system("pause");
	return 0;
}

其实链表算法的核心是两点：

（1）熟悉辅助结点的使用，我们访问链表必须通过辅助结点， for( LinkNode *p=L; p!=NULL ; p=p->next ) 与 for( int i=0 ; i<length ; ++i )  并没有本质的区别。

（2）熟悉操作通过前驱结点的方式，链表的操作往往需要找到或者记录当前结点的前驱，这也许是陌生感的真正原由。 所以链表算法中经常看到nextp,nextq,prep,preq这样的辅助结点和p,q一起使用。