链表学习实例-创建、插入、删除、排序

时间:11-10-28 栏目:技术 作者:liva 评论:0 点击: 2,267 次

链表概述
链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量,以head表示,它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”,每个结点都应包括两个部分:一为用户需要用的实际数据,二为下一个结点的地址。因此,head指向第一个元素:第一个元素又指向第二个元素;……,直到最后一个元素,该元素不再指向其它元素,它称为“表尾”,它的地址部分放一个“NULL”(表示“空地址”),链表到此结束。
链表的各类操作包括:学习单向链表的创建、删除、 插入(无序、有序)、输出、 排序(选择、插入、冒泡)、反序等等。

单向链表的图示:
---->[NULL]
head

图1:空链表

---->[p1]---->[p2]...---->[pn]---->[NULL]
head p1->next p2->next pn->next

图2:有N个节点的链表

创建n个节点的链表的函数为:

 

 

 

 

输出链表中节点的函数为:
view plain

单向链表的删除图示:
---->[NULL]
head

图3:空链表

从图3可知,空链表显然不能删除

---->[1]---->[2]...---->[n]---->[NULL](原链表)
head 1->next 2->next n->next

---->[2]...---->[n]---->[NULL](删除后链表)
head 2->next n->next

图4:有N个节点的链表,删除第一个节点
结合原链表和删除后的链表,就很容易写出相应的代码。操作方法如下:
1、你要明白head就是第1个节点,head->next就是第2个节点;
2、删除后head指向第2个节点,就是让head=head->next,OK这样就行了。
---->[1]---->[2]---->[3]...---->[n]---->[NULL](原链表)
head 1->next 2->next 3->next n->next

---->[1]---->[3]...---->[n]---->[NULL](删除后链表)
head 1->next 3->next n->next

图5:有N个节点的链表,删除中间一个(这里图示删除第2个)
结合原链表和删除后的链表,就很容易写出相应的代码。操作方法如下:
1、你要明白head就是第1个节点,1->next就是第2个节点,2->next就是第3个节点;
2、删除后2,1指向第3个节点,就是让1->next=2->next。

删除指定学号的节点的函数为:

单向链表的插入图示:
---->[NULL](原链表)
head

---->[1]---->[NULL](插入后的链表)
head 1->next

图7 空链表插入一个节点
结合原链表和插入后的链表,就很容易写出相应的代码。操作方法如下:
1、你要明白空链表head指向NULL就是head=NULL;
2、插入后head指向第1个节点,就是让head=1,1->next=NULL,OK这样就行了。

---->[1]---->[2]---->[3]...---->[n]---->[NULL](原链表)
head 1->next 2->next 3->next n->next

---->[1]---->[2]---->[x]---->[3]...---->[n]---->[NULL](插入后的链表)
head 1->next 2->next x->next 3->next n->next

图8:有N个节点的链表,插入一个节点(这里图示插入第2个后面)
结合原链表和插入后的链表,就很容易写出相应的代码。操作方法如下:
1、你要明白原1->next就是节点2,2->next就是节点3;
2、插入后x指向第3个节点,2指向x,就是让x->next=2->next,1->next=x。

插入指定节点的后面的函数为:
view plain

 

单向链表的反序图示:
---->[1]---->[2]---->[3]...---->[n]---->[NULL](原链表)
head 1->next 2->next 3->next n->next

[NULL]next 2->next 3->next n->next head

图9:有N个节点的链表反序
结合原链表和插入后的链表,就很容易写出相应的代码。操作方法如下:
1、我们需要一个读原链表的指针p2,存反序链表的p1=NULL(刚好最后一个节点的next为NULL),还有一个临时存储变量p;
2、p2在原链表中读出一个节点,我们就把它放到p1中,p就是用来处理节点放置顺序的问题;
3、比如,现在我们取得一个2,为了我们继续往下取节点,我们必须保存它的next值,由原链表可知p=2->next;
4、然后由反序后的链表可知,反序后2->next要指向1,则2->next=1;
5、好了,现在已经反序一个节点,接着处理下一个节点就需要保存此时的信息:
p1变成刚刚加入的2,即p1=2;p2要变成它的下一节点,就是上面我们保存的p,即p2=p。

反序链表的函数为:

对链表进行选择排序的基本思想就是反复从还未排好序的那些节点中,选出键值(就是用它排序的字段,我们取学号num为键值)最小的节点,依次重新组合成一个链表。

我认为写链表这类程序,关键是理解:head存储的是第一个节点的地址,head->next存储的是第二个节点的地址;任意一个节点p的地址,只能通过它前一个节点的next来求得。

单向链表的选择排序图示:
---->[1]---->[3]---->[2]...---->[n]---->[NULL](原链表)
head 1->next 3->next 2->next n->next

---->[NULL](空链表)
first
tail

---->[1]---->[2]---->[3]...---->[n]---->[NULL](排序后链表)
first 1->next 2->next 3->next tail->next

图10:有N个节点的链表选择排序

1、先在原链表中找最小的,找到一个后就把它放到另一个空的链表中;
2、空链表中安放第一个进来的节点,产生一个有序链表,并且让它在原链表中分离出来(此时要注意原链表中出来的是第一个节点还是中间其它节点);
3、继续在原链表中找下一个最小的,找到后把它放入有序链表的尾指针的next,然后它变成其尾指针;

对链表进行选择排序的函数为:

对链表进行直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值(就是用它排序的字段,我们取学号num为键值)排好序的,对于节点n在这个序列中找插入位置,使得n插入后新序列仍然有序。按照这种思想,依次对链表从头到尾执行一遍,就可以使无序链表变为有序链表。

单向链表的直接插入排序图示:
---->[1]---->[3]---->[2]...---->[n]---->[NULL](原链表)
head 1->next 3->next 2->next n->next

---->[1]---->[NULL](从原链表中取第1个节点作为只有一个节点的有序链表)
head
图11

---->[3]---->[2]...---->[n]---->[NULL](原链表剩下用于直接插入排序的节点)
first 3->next 2->next n->next
图12

---->[1]---->[2]---->[3]...---->[n]---->[NULL](排序后链表)
head 1->next 2->next 3->next n->next

图13:有N个节点的链表直接插入排序

1、先在原链表中以第一个节点为一个有序链表,其余节点为待定节点。
2、从图12链表中取节点,到图11链表中定位插入。
3、上面图示虽说画了两条链表,其实只有一条链表。在排序中,实质只增加了一个用于指向剩下需要排序节点的头指针first罢了。
这一点请读者务必搞清楚,要不然就可能认为它和上面的选择排序法一样了。

对链表进行直接插入排序的函数为:

对链表进行冒泡排序的基本思想就是对当前还未排好序的范围内的全部节点,自上而下对相邻的两个节点依次进行比较和调整,让键值(就是用它排 序的字段,我们取学号num为键值)较大的节点往下沉,键值较小的往上冒。即:每当两相邻的节点比较后发现它们的排序与排序要求相反时,就将它们互换。

单向链表的冒泡排序图示:
---->[1]---->[3]---->[2]...---->[n]---->[NULL](原链表)
head 1->next 3->next 2->next n->next

---->[1]---->[2]---->[3]...---->[n]---->[NULL](排序后链表)
head 1->next 2->next 3->next n->next

图14:有N个节点的链表冒泡排序

任意两个相邻节点p、q位置互换图示:
假设p1->next指向p,那么显然p1->next->next就指向q,
p1->next->next->next就指向q的后继节点,我们用p2保存
p1->next->next指针。即:p2=p1->next->next,则有:
[ ]---->[p]---------->[q]---->[ ](排序前)
p1->next p1->next->next p2->next
图15

[ ]---->[q]---------->[p]---->[ ](排序后)

图16

1、排序后q节点指向p节点,在调整指向之前,我们要保存原p的指向节点地址,即:p2=p1->next->next;
2、顺着这一步一步往下推,排序后图16中p1->next->next要指的是p2->next,所以p1->next->next=p2->next;
3、在图15中p2->next原是q发出来的指向,排序后图16中q的指向要变为指向p的,而原来p1->next是指向p的,所以p2->next=p1->next;
4、在图15中p1->next原是指向p的,排序后图16中p1->next要指向q,原来p1->next->next(即p2)是指向q的,所以p1->next=p2;
5、至此,我们完成了相邻两节点的顺序交换。
6、下面的程序描述改进了一点就是记录了每次最后一次节点下沉的位置,这样我们不必每次都从头到尾的扫描,只需要扫描到记录点为止。 因为后面的都已经是排好序的了。

对链表进行冒泡排序的函数为:

有序链表插入节点示意图:

---->[NULL](空有序链表)
head

图18:空有序链表(空有序链表好解决,直接让head指向它就是了。)

以下讨论不为空的有序链表。
---->[1]---->[2]---->[3]...---->[n]---->[NULL](有序链表)
head 1->next 2->next 3->next n->next

图18:有N个节点的有序链表

插入node节点的位置有两种情况:一是第一个节点前,二是其它节点前或后。

---->[node]---->[1]---->[2]---->[3]...---->[n]---->[NULL]
head node->next 1->next 2->next 3->next n->next

图19:node节点插在第一个节点前

---->[1]---->[2]---->[3]...---->[node]...---->[n]---->[NULL]
head 1->next 2->next 3->next node->next n->next

插入有序链表的函数为:

综上所述,链表的各类操作函数的完整代码如下:

声明: 本文由( liva )原创编译,转载请保留链接: 链表学习实例-创建、插入、删除、排序

链表学习实例-创建、插入、删除、排序:等您坐沙发呢!

发表评论


购物推荐

赞助商

© 2013 enjoydiy.com. Design by zijiao. 60 queries in 0.559 seconds, using 21.86MB memory