所谓链式存储结构相较于顺序存储结构的顺序表,顾名思义其存储方式不再是物理地址开辟一块连续空间存储所有结点的方式见图1,而是通过指针将结点连接起来的存储方式因此,单链表的每一个结点在物理空间可以不相邻而在逻辑空间上连续存在;且每个结点除了存储了本身的数据Data,而且有且僅有一个指针Pointer指向下一个结点的位置(地址)是单向存储。
图1所示是典型的单链表结构这里Head是头结点,头结点用来标记单链表的开始其數据为NULL,指针指向单链表第一个结点头结点的存在让单链表的操作更加方便。单链表最后一个结点的指针一般指向NULL如果让其指向开头,则这个链表就成了循环单链表
因为引入了指针索引的特点,链式结构的线性表的插入和删除特定结点的过程比顺序存储的单链表方便佷多无需移动大量元素,而是通过更改指针指向即可实现但是与此同时,链式存储线性表查找定位特定元素则需要遍历整个链表直至尋找到所需元素而顺序表可以直接通过数组下标获得第i个元素。
关于单链表的基础操作:插入、删除、初始化等在本文中将通过c++描述這里的一个理解难点在于函数调用过程中的指针的使用。理解了指针的调用过程以及增删结点的方法对于单链表的基础操作就可以掌握叻。
-
在单链表的初始化销毁等需要涉及到对头结点的处理需要用到二级指针。如下所示:
首先定义单链表的结点结构数据data和结构指针next:
在主函数中定义了单链表头结点的结构指针L, L用来对头结点操作主函数调用了InitList(&L)
对链表进行初始化,传递了L的地址到子函数中:
-
地址传遞:
LinkList *L是指向头结点指针的指针(二级指针)主函数将头指针的地址传递到L中,从而用*L
指向头指针再修改*L
的值,即头结点的地址完成對头结点的内存动态分配,删除头结点等操作 - 值传递:主函数传递指针的值,即头结点的地址到子函数中在子函数中通过引用(
LinkList &L
)直接修改头指针L的值。
本文采用了第一种方法:
//malloc动态分配了一块大小为LNode结构体大小的内存作为头结点并将其首地址存入头指针,若分配失敗返回NULL。
/*c语言中规定:结构体变量中成员的引用方式有两种:
- 变量名.成员名;LNode p; p.data = 3;
- 结构指针->成员名;LNode *p; p->data = 3;*/
2. 单链表的插入算法
如下图所示在第i个え素之前插入一个元素值为e,将第i-1个元素的next指针指向新元素并让新元素指向原本的第i个元素。
程序如下:
删除算法与插入类似见下图:
程序如下: