普及向——链表初步(C向)
开始便想到了洲哥奇葩的期中考试中的“给定常量M”……
链表出现的主要意义第一是满足元素个数没有明确上限的时候,使用动态内存分配来满足程序的需求。其次是因为数组对插入、删除、移动操作的时间复杂度较高,因此采用链表来实现。
数组 | 链表 | |
遍历 | O(n) | O(n) |
查找 | O(log n)(二分) | O(n) |
插入、删除、移动 | O(n) | O(1) |
可见,在查找次数比较多的时候使用数组,在插入、删除次数比较多的时候使用链表。
链表的实现主要依靠结点结构体(类)。
链表结点的结构一般为
Node
DataType Data
Node* Next
单链表中每个结点仅有一个指针,指向它的后继结点。
单链表操作主要分为插入、删除void append(Node* Node, Node* newNode)<span style="padding-left: 30px; color: #339966;">//append newNode to Node</span>
{
<span style="padding-left: 30px;">newNode->next=TargetNode->Next;</span>
<span style="padding-left: 30px;">TargetNode->Next=newNode;</span>
}
void delete(Node* TargetNode)<span style="padding-left: 30px; color: #339966;">//delete TargetNode->Next</span>
{
<span style="padding-left: 30px;"><code>Node* buf=TargetNode->Next;
TargetNode->Next=TargetNode->Next->Next;
free(buf);
}
有一个比较好玩的问题:单链表如何删除当前结点?(全选看答案)
答案:将下一个结点的Data拷贝到当前结点,然后把下个结点删掉⋯⋯
再来一个问题:将单链表逆序,即最后一个结点称为第一个结点etc(全选看答案)
答案:很明显的,我们对于任意一个结点来说,需要做如下事情:
- 如果自己有后继,将后面所有的的结点逆序,否则将头指针指向自己。
- 将自己的后继指针指向自己原来的前趋,如果自己没有前趋则将后继指针置为空。
由此可见逆序操作适合使用递归处理。
void reverse(Node* preNode) { <span style="padding-left: 30px;">if(preNode->Next->Next)</span> <span style="padding-left: 60px;">reverse(preNode->Next);</span> <span style="padding-left: 30px;">else</span> <span style="padding-left: 60px;">head.Next=preNode->Next;</span> <span style="padding-left: 30px;">if(preNode!=&head)</span> <span style="padding-left: 60px;">preNode->Next->Next=preNode;</span> <span style="padding-left: 30px;">else</span> <span style="padding-left: 60px;">preNode->Next->Next=NULL;</span> }
在这里的preNode->Next意思是当前结点。
主函数里面调用reverse(HeadNodePtr)
即可~
(这里使用的是有头结点的版本,没有头结点的版本需要对第一个结点进行特殊处理)。
由于单链表只能单向移动,所以同时还存在其他的一些链表来满足不同的需求,比如循环链表(尾结点的后继是头结点)、双向链表(每个结点有个指向前趋的指针)、十字链表(模拟矩阵,每个结点有两个或四个指针)。
在链表实现过程中,大家可能会发现,每次都要对链表是否非空进行判断,因为头指针一旦为空,对头指针指向内容进行操作就会内存越界。因此在实现链表有一种方法就是:设置一个没有数据或者数据为空的头结点来代替头指针。这样操作之后,向空链表中插入结点的操作也转化为向某个结点(头结点)后面插入一个新的结点,同时保证了链表非空时某特定结点之前之后一定有结点(循环链表、双向链表),因此代码量会大大减少。
At Last:链表的题目一定要形象化思维,脑子里想不清可以在纸上画,用一个箭头来代表指针之类的。