本文共 3111 字，大约阅读时间需要 10 分钟。

前言

本篇讨论的均为带头结点的单链表。

一、单链表的初始化

先上结构体：

typedef struct Node{	int data;	Node* next;}Node,*LinkedList;

Node为struct Node的别名，

LinkedList为struct Node*，也就是链表指针的别名。

代码：

LinkedList LinkedListInit(){	Node* L;	L = (Node*)malloc(sizeof(Node));	if (L == NULL)	{		cout << "申请内存空间失败！" << endl;	}	return L;}

首先，这个函数的返回值是一个链表的指针。

创建第一个结点的指针，

为这个指针分配一块大小为8的内存空间；

如果分配后，L还是为NULL，

则说明分配失败。

最后把L返回。

初始化的这个L就是链表的头结点，其数据域不具有意义，指针域指向NULL。

我们来测试一下这个代码：

 

int main(){	LinkedList p;	p = LinkedListInit();	p->data = 5;	cout << p->data;	free(p);	return 0;}

 运行结果：

如果不进行初始化，

会报错：不允许使用未初始化的结构体。

二、单链表的建立——头插法

代码：

LinkedList LinkedListCreatH(){	Node* L =LinkedListInit();	L->next = NULL;	int x;	while (scanf("%d", &x) != EOF)	{		Node* p;		p = (Node*)malloc(sizeof(Node));		p->data = x;		p->next = L->next;		L->next = p;	}	return L;}

 首先，利用已经写好的链表初始化函数，为一个结点分配内存空间；

然后，将其指针域指向NULL，数据域不放任何东西。

这样，头结点就做好了。

然后，输入数据：

只要输入的不是EOF，就一直插入结点，直到程序读到一个EOF为止。

在循环体内部，创建一个结点p，

然后为其动态分配内存空间；

接下来赋值，

让新结点的指针域指向头结点指向的那个结点，

让头结点的指针域存放这个结点的地址。

最后返回头结点的地址，

这样，一个头插法链表就创建完毕。

图示：

三、单链表的建立——尾插法

代码：

LinkedList LinkedListCreatH(){	Node* L = LinkedListInit();	L->next = NULL;	Node* r;	r = L;	int x;	while (scanf("%d", &x) != EOF)	{		Node* p;		p = (Node*)malloc(sizeof(Node));		p->data = x;		r->next = p;		r = p;	}	r->next = NULL;	return L;}

还是先建立头结点。

和头插法不一样的是，这里创建了一个头指针r，指向头结点；

现在由指针r和指针L共同维护头结点；

然后，创建新结点p1。

让r的指针指向p1，

也就是让头结点指向p1,

再让r指向p1,

现在，头结点仅由L维护，

而第一个结点p1由p1和r共同维护。

接下来，一直插入结点，直到遇到EOF为止。

退出循环，然后将r->next指向NULL，也就是最后一个结点的指针域存放着NULL。

此时，头指针到达了尾部。

图示：

四、单链表的插入

代码：

LinkedList LinkedListInsert(LinkedList L, int i, int x){	Node* pre;	pre = L;	int tempi = 0;	for (tempi = 1; tempi < i; tempi++)	{		pre = pre->next;	}	Node* p;	p = (Node*)malloc(sizeof(Node));	p->data = x;	p->next = pre->next;	pre->next = p;	return L;}

对于单链表的插入，

我们需要找到要插位置的前一个结点。

然后进行如图所示的操作：

 这里首先创建一个Node* pre，表示要插入结点的前一个结点。

其实不必像王道书上写的，对第一个结点进行特殊处理，

只需要写一个for循环，

如果i = 1,

那么pre就是头结点；

如果i>1,

再进行找结点运算。

找到前一个结点后，我们开始创建新结点；

然后让新结点指向上一个结点的下一个结点，

让上一个结点指向新结点，

这样不会断链，

最后返回头结点即可。

五、单链表的删除

代码：

LinkedList LinkedListDelete(LinkedList L, int i){	if (i < 1)		cout << "请输入大于等于1的正整数！" << endl;	Node* pre;	pre = L;	int tempi = 0;	for(tempi = 1;tempi < i;tempi++)	{		pre = pre->next;	}	Node* p = pre->next;	pre->next = p->next;	free(p);	return L;}

这里还是先找到位序元素的前一个元素，

然后让前一个元素的指针指向位序元素的后一个元素，

再释放位序元素即可。

如图所示：

六、测试

先测头插法：

int main(){	cout << "请输入单链表的数据：";	LinkedList list,start;	list = LinkedListCreatH();	for (start = list->next; start != NULL; start = start->next)	{		cout << start->data<

结果：

再测尾插法：

 

测试成功。

这里要注意：

我们输入了三个CTRL+Z才完成了EOF。

原因在于：

跟着断点进去，第一次ctrl+z被whitespace判断吃掉了，第二次ctrl+z被parse_integer吃掉了（虽然后面有unget，但不知道具体作用）。第三次ctrl+z才是被用来触发eof的。 

 测试插入操作：

int main(){	cout << "请输入单链表的数据：";	LinkedList list,start;	list = LinkedListCreatT();	LinkedListInsert(list, 3, 5);	for (start = list->next; start != NULL; start = start->next)	{		cout << start->data<

测试删除操作：

int main(){	cout << "请输入单链表的数据：";	LinkedList list,start;	list = LinkedListCreatT();	LinkedListDelete(list, 3);	for (start = list->next; start != NULL; start = start->next)	{		cout << start->data<

测试完成。

链表的基本操作讲解到这里就完成了，接下来会更新双链表，循环链表以及链表反转等算法问题。

github地址：

转载地址：http://rjjz.baihongyu.com/