线性表的应用 —— 单链表

线性表的应用 —— 单链表

链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，可以给每个元素都附加一个指针域，指向下一个元素的存储位置。

像这样：

从图中可以看出，每个节点都包含两个域：数据域和指针域。

数据域存储数据元素，指针域存储下一个节点的地址，因此指针指向的类型也是节点类型。
链表中的每个指针都指向下一个节点，都朝向一个方向，这样的链表被称为单向链表或单链表。

【单链表的节点结构体定义】

定义了节点结构体之后，就可以把若干节点连接在一起，形成一个单链表了。

不管这个单链表有多长，只要找到它的头，就可以拉起整个单链表，因此如果给这个单链表设置一个头指针，则这个单链表中的每个节点就都可以找到了。

有时为了操作方便，还会给单链表增加一个不存放数据的头节点（也可以存放表长等信息）。

若想在顺序表中找第i 个元素，则可以立即通过L .elem[i -1]找到，想找哪个就找哪个，被称为随机存取。
在单链表中找第i 个元素必须从头开始，按顺序一个一个地找，一直数到第i个元素，被称为顺序存取。

【插入】

在第i个节点之前插入元素e ，相当于在第i -1个节点之后插入元素e 。假设已找到第i -1个节点，并用p 指针指向该节点，s 指向待插入的新节点。
插入操作如下图所示。

其中，“s ->next=p ->next”指将节点p 后面的节点地址赋值给节点s 的指针域，即节点s 的next指针指向p 后面的节点；“p ->next=s”指将节点s 的地址赋值给节点p 的指针域，即节点p 的next指针指向节点s 。

[算法实现]

bool ListInsert_L(LinkList &L , int i , int e){ //单链表的插入，在第i个节点之前插入元素e
	// 在带头节点的 单链表 L 中第 i 个位置之前插入值为 e 的新节点
	int j;
	LinkList p , s;
	p = L;
	j = 0;
	while(p && j < i - 1){ // 查找第 i - 1 个节点，p 指向该节点
		p = p -> next;
		j ++;
	}
	if(!p || j > i - 1){  // i > n + 1 或者 i < 1
		return false;  // 没找到
	}
	s = new Lnode; //生成新节点
	s->data = e;  //将数据元素e 放入新节点的数据域中
	s->next = p->next;  //将新节点的指针域指向第 i 个节点
	p->next = s;  //将节点p 的指针域指向节点s
	return true;  //插入成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

【删除】

删除一个节点，实际上是把这个节点跳过去。根据单向链表向后操作的特性，要想跳过第i 个节点，就必须先找到第i -1个节点，否则跳不过去，如下图所示。

其中，“p ->next=q ->next”指将节点q 的下一个节点地址赋值给节点p 的指针域。

在这些有关指针的赋值语句中，等号的右侧是节点的地址，等号的左侧是节点的指针域

假设节点q 的下一个节点地址为1013，该地址被存储在q ->next里面，因此等号右侧q ->next的值为1013。把该地址赋值给节点p 的next指针域，把原来的值2046覆盖，这样，p ->next的值也为1013，相当于把节点q 跳过去了。

[算法实现]

bool ListDelete_L(LinkList &L , int i){ //在带头结点的单链表L中删除第i个元素
	LinkList p , q;
	int j;
	p = L;
	j = 0;
	while((p->next) && (j < i - 1)){ //查找第 i - 1个节点，p指向该节点
		p = p->next;
		j ++;
	}
	if(!(p->next) || (j > i - 1)){ //删除位置不合理
		return false; //删除失败
	}
	q = p->next; //临时保存被删除节点的地址以备释放空间
	p->next = q->next; //将节点q的下一个节点地址赋值给节点p的指针域
	delete q;  //释放被删除节点的空间
	return true;  //删除成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在单链表中，每个节点除了存储自身数据，还存储下一个节点的地址，因此可以轻松访问下一个节点，以及后面的所有后继节点，但是如果想访问前面的节点就不行了，再也回不去了。

例如删除节点q 时，要先找到它的前一个节点p ，然后才能删掉节点q ，单链表只能向后操作，不能向前操作。