普及向——链表初步(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-&gt;next=TargetNode-&gt;Next;</span> <span style="padding-left: 30px;">TargetNode-&gt;Next=newNode;</span> }

void delete(Node* TargetNode)<span style="padding-left: 30px; color: #339966;">//delete TargetNode-&gt;Next</span> { <span style="padding-left: 30px;"><code>Node* buf=TargetNode-&gt;Next;
TargetNode->Next=TargetNode->Next->Next;
free(buf);
}

有一个比较好玩的问题:单链表如何删除当前结点?(全选看答案)

答案:将下一个结点的Data拷贝到当前结点,然后把下个结点删掉⋯⋯

再来一个问题:将单链表逆序,即最后一个结点称为第一个结点etc(全选看答案)

答案:很明显的,我们对于任意一个结点来说,需要做如下事情:

  1. 如果自己有后继,将后面所有的的结点逆序,否则将头指针指向自己。
  2. 将自己的后继指针指向自己原来的前趋,如果自己没有前趋则将后继指针置为空。
    由此可见逆序操作适合使用递归处理。
    void reverse(Node* preNode) { <span style="padding-left: 30px;">if(preNode-&gt;Next-&gt;Next)</span> <span style="padding-left: 60px;">reverse(preNode-&gt;Next);</span> <span style="padding-left: 30px;">else</span> <span style="padding-left: 60px;">head.Next=preNode-&gt;Next;</span> <span style="padding-left: 30px;">if(preNode!=&amp;head)</span> <span style="padding-left: 60px;">preNode-&gt;Next-&gt;Next=preNode;</span> <span style="padding-left: 30px;">else</span> <span style="padding-left: 60px;">preNode-&gt;Next-&gt;Next=NULL;</span> }

在这里的preNode->Next意思是当前结点。

主函数里面调用reverse(HeadNodePtr)即可~

(这里使用的是有头结点的版本,没有头结点的版本需要对第一个结点进行特殊处理)。

由于单链表只能单向移动,所以同时还存在其他的一些链表来满足不同的需求,比如循环链表(尾结点的后继是头结点)、双向链表(每个结点有个指向前趋的指针)、十字链表(模拟矩阵,每个结点有两个或四个指针)。

在链表实现过程中,大家可能会发现,每次都要对链表是否非空进行判断,因为头指针一旦为空,对头指针指向内容进行操作就会内存越界。因此在实现链表有一种方法就是:设置一个没有数据或者数据为空的头结点来代替头指针。这样操作之后,向空链表中插入结点的操作也转化为向某个结点(头结点)后面插入一个新的结点,同时保证了链表非空时某特定结点之前之后一定有结点(循环链表、双向链表),因此代码量会大大减少。

At Last:链表的题目一定要形象化思维,脑子里想不清可以在纸上画,用一个箭头来代表指针之类的。

更多关于链表的知识请看这里,如果你认为英文足够好,请看这里。感觉上比前面的好很多。