单链表及其基本方法的实现

定义：线性表的链式存储结构使用一组任意的存储单元（可以连续，也可以不连续）存储线性表的数据元素。每个结点包含两个域：指针域（用来存储直接后继的存储位置）和数据域（用来存储数据元素信息）。

特点：由于链表不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序表随机存取的优点，每个元素的在内存中的位置是包含在该元素的直接前趋的指针域中。但是，链式存储结构在插入和删除元素上效率非常高，不需要元素移动的代价。

//单链表的实现和基本方法

#include<iostream>
#include<iomanip>
#include<stdlib.h>
#include<string.h>
using namespace std;

//结点结构
typedef int ElemType;
typedef struct LNode{
	ElemType data;				//数据域
	struct LNode *next;		//指针域
}LNode, *LinkList;

//逆序建立单链表
void CreateList(LinkList &L, int n){
	L = (LinkList) malloc(sizeof(LNode));	//头结点
	L->data = 0;
	L->next = NULL;
	LinkList p;
	for(int i=n; i>0; --i){
		p = (LinkList) malloc(sizeof(LNode));
		p->next = L->next;
		L->next = p;
		p->data = i;
	}
}

//销毁链表
void DestroyList(LinkList &L){
	LinkList p = L->next, q;
	while(p){
		q = p;
		p = p->next;
		free(q);
	}
	free(L);
	L = NULL;
}

//遍历链表
void TraverseList(LinkList &L){
	LinkList p = L;
	while(p){
		cout<<setw(5)<<(p->data);
		p = p->next;
	}
	cout<<endl;
}

//访问第i个元素
bool GetElem(LinkList &L, int i, ElemType &e){
	LinkList p = L->next;	//p指向第一个元素
	int j = 1;
	while(p && j<i){
		p = p->next;
		++j;
	}
	if(!p||j>i)return false;	//元素不存在
	e = p->data;
	return true;
}

//在第i个位置前插入元素
bool ListInsert(LinkList &L, int i, ElemType e){
	LinkList p = L;
	int j = 0;
	while(p && j<i-1){
		p = p->next;
		++j;
	}
	if(!p||j>i-1)return false;
	LinkList s = (LinkList) malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

//删除第i个元素
bool ListDelete(LinkList &L,int i, ElemType &e){
	LinkList p = L;
	int j = 0;
	while(p->next && j<i-1){
		p = p->next;
		++j;
	}
	if(!(p->next) || j>i-1)return false;
	e = p->next->data;
	p->next = p->next->next;
	return true;
}

//归并排序
void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc){
	LinkList pa = La->next;
	LinkList pb = Lb->next;
	LinkList pc = Lc = La;
	while(pa && pb){
		if(pa->data <= pb->data){
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else{
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa? pa : pb;	//插入剩余段
	free(Lb);
}

//反转单链表
void ReverseList(LinkList &L){
	if(L==NULL || L->next==NULL)return;	//边界检测
	LinkList pNext = NULL;	//下一个结点
	LinkList pPrev = L;		//上一个节点
	LinkList pCur = L->next;//当前节点

       //遍历链表，将前节点设置为当前节点的下一结点
	while(pCur != NULL){
		pNext = pCur->next;
		pCur->next = pPrev;
		pPrev = pCur;
		pCur = pNext;
	}
	L->next = NULL;	//原来的头结点变成最后一个结点
	L = pPrev;		//重新设置头指针
}

int main(){
	//演示
	cout<<"建立链表"<<endl;
	LinkList L;
	CreateList(L, 10);
	TraverseList(L);

	cout<<"查找操作"<<endl;
	ElemType e;
	GetElem(L,4,e);
	cout<<e<<endl;

	cout<<"插入操作"<<endl;
	ListInsert(L,4,99);
	TraverseList(L);
	cout<<"删除操作"<<endl;
	ListDelete(L,4,e);
	TraverseList(L);

	cout<<"反转链表"<<endl;
	ReverseList(L);
	TraverseList(L);
	DestroyList(L);
	return 0;
}

结果：

建立链表
    0    1    2    3    4    5    6    7    8    9   10
查找操作
4
插入操作
    0    1    2    3   99    4    5    6    7    8    9   10
删除操作
    0    1    2    3    4    5    6    7    8    9   10
反转链表
   10    9    8    7    6    5    4    3    2    1    0

注意：上面的查找操作GetElem、插入操作ListInsert、删除操作ListDelete的时间复杂度均为O(n)。

这里，单链表的归并排序算法的时间复杂度和顺序表相同，但空间复杂度不同。在归并两个链表为一个链表时，不需要另外新建表的结点空间，只需要将原来两个链表中结点之间的关系解除，重新按元素值非递减的关系将所有结点链接成一个新表即可。

by chenqi / 20110914