关于单链表的操作

《关于单链表的操作》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关于单链表的操作单向链表结构描述示例：structlinklist{intdata；structlinklist*next；}；structlinklist*head；单链表的建立在链表的操作中用到的几个函数：(1)malloc（size）在内存的动态存储区申请一个长度为size字节的连续空间。并将此存储空间的起始地址作为函数值返回。malloc函数的原型为：void*malloc(unsignedintsize)函数值为指针（地址），这个指针是指向void类型的，也就是不规定指向任何具体的类型。如

2、果内存缺乏足够大的空间进行分配，则malloc的函数值为“空指针”。(2)calloc（n，size）在内存的动态存储区申请n个长度为size字节的连续空间，函数返回值为分配空间的首地址。若此函数未被成功执行，函数返回值为0。函数返回值为该空间的首地址。其函数原型为：void*calloc(unsignedintn，unsignedintsize)(3)free（p）释放由指针p所指向的存储单元，而所释放的存储单元的大小是最近一次调用malloc（）函数或calloc（）函数时所申请的存储空间。fr

3、ee函数的原型为：voidfree(void*ptr)系统可以回收所释放的空间，另行分配作为它用。(4)realloc函数。其函数的原型为：voidrealloc(void*ptr，unsignedintsize)其作用是将ptr所指向的存储区（原先用malloc函数分配的）的大小改为size个字节。可以使原先分配区扩大和缩小。它的函数返回值是一个指针，即新的存储区的首地址。例1　使用表首插入法建立链表。表首插入法建立链表，这种方法的特点是：新产生的结点作为新的表头插入链表。#include

4、io.h>voidmain(）{structlinklist{intdata；structlinklist*next；}；structlinklist*head，*p；/*head头指针，p申请单元指针*/head=NULL；/*空链表*//*申请空间，并将指针p强制转换成所指向的结构体类型*/p=(structlinklist*)malloc(sizeof(structlinklist))；scanf("%d"，&p−>data)；/*得到数据，放结点数据域*/while(p−>data>0

5、)/*假设所给数据都大于0*/{p−>next=head；/*建立链接，当前结点指针域存放下一结点地址*/head=p；/*用头指针保存当前结点*//*为下一个结点申请空间*/p=(structlinklist*)malloc(sizeof(structlinklist))；scanf("%d"，&p−>data)；/*得到新结点数据*/}}运行该程序，输入准备建立链表的各数据，以0结束数据的输入，即可得到一个链表。由于是表首添加法，最后输出链表中的数据的输入顺序正好与输入顺序相反。例2　表尾插入法

6、建立链表若将链表的左端固定，链表不断向右延伸，这种建立链表的方法称为表尾插入法。表尾插入法建立链表时，头指针固定不动，故必须设立一个搜索指针，向链表右边延伸，则整个算法中应设立三个链表指针，即头指针head、搜索指针p2、申请单元指针p1。表尾插入法最先得到的是头结点。#includevoidmain(){structlinklist{intdata；structlinklist*next；}；structlinklist*head，*p1，*p2；head=NULL；/*空链表*

7、/p1=（structlinklist*）malloc（sizeof（structlinklist））；/*申请空间*/p2=p1;scanf（"%d"，&p1->data）；/*得到数据*/while（p1->data>0）{if（head==NULL）head=p1；elsep2->next=p1；/*建立连接*/p2=p1；/*保存当前结点*//*为下一个结点申请空间*/p1=(structlinklist*)malloc(sizeof(structlinklist))；scan

8、f("%d"，&p1−>data)；/*得到下一个结点数据*/}p2−>next=NULL；/*最后的尾结点指针域为空指针*/}运行该程序，输入准备建立链表的各数据，以0作为结束数据的输入，即可得到一个链表，该链表的输出顺序与输入顺序一致。单链表的有关操作链表的基本操作包括建立链表、链表结点的插入、删除、输出和查找等。下面介绍完成单链表的基本操作的函数。1.输出链表中所有结点要依次输出链表中各结点的数据比较容易。首先要知道表头结点的地址，即要知道head的值，然后设一