朝花夕拾 · 数据结构 | 链表篇

一.逻辑结构与存储结构1.数据的逻辑结构2.数据的存储结构顺序存储与链式存储的区别顺序存储1.需要占用内存相邻一块连续的空间若开辟空间较大时则可能挤占其余内存空间产生部分内存外部碎片。2.由于是顺序存储元素之间可连续读取适合查改效率高但不适合增删对顺序存储结构进行增删需遍历数组将部分元素进行移动。3.需要进行预分配内存由于先分配后使用所以申请空间可能大可能小造成内存浪费或数组越界。链式存储1.不要求逻辑上相邻的元素在物理上也相邻可借助元素的后继指针连接可以充分利用内存空间不会出现内存碎片现象。2.由于不要求物理上连续所以每个元素需要指针来指向后一个元素增加了内存的消耗。3.与顺序存储相反链式存储适合增删对于元素的位置只需修改前驱与后继的指针即可而不适合查改每次遍历都只能从头指针开始向后遍历整个链表也可采用双向链表或循环链表进行优化。4.不需要进行预分配内存每次使用时动态开辟空间即可即用即存不需要时可及时释放内存空间。注意线性表是一种逻辑结构表示元素之间一对一的相邻关系。顺序表和链表是指存储结构两者属于不同层面的概念因此不要将其混淆。二.链表1.链表的定义线性表的链式存储也称单链表它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系对每个链表结点除存放元素自身的信息外还需要存放一个指向其后继的指针。单链表结点结构如图2.3所示其中data为数据域存放数据元素;next为指针域存放其后继结点的地址。typedef struct Node //定义结点结构 { int data; struct Node *pnext; }Node; typedef struct //定义链表结构 { int len; Node *phead; }Link;2.基本功能通常用头指针来标识一个单链表指出链表的起始地址头指针为NULL时表示一个空表。此外为了操作上的方便在单链表第一个数据结点之前附加一个结点称为头结点。头结点的数据域可以不设任何信息但也可以记录表长等信息。单链表带头结点时头指针指向头结点如图(a)所示。单链表不带头结点时头指针L指向第一个数据结点如图(b)所示。表尾结点的指针域为NULL(用“^”表示)。带头结点的链表代码操作较为简单且规范故推荐定义链表时采用带头结点的方式。以下有三种链表结构的创建与初始化无Link容器的带头结点Node * create_link() { Node *phead malloc(sizeof(Node)); if(NULLphead) { printf(malloc error\n); return NULL; } phead-pnextNULL; phead-data0; //头结点data为无效值 return phead; }Link容器的带头结点Link * create_link() { Link *plink malloc(sizeof(Link)); if(NULLplink) { printf(malloc error\n); return NULL; } Node *head malloc(sizeof(Node)); if(NULL head) { printf(mallochead error\n); return NULL; } head-data0; //头结点可不赋值 head-pnextNULL; plink-len0; plink-pheadhead; return plink; }Link容器的不带头结点Link *create_link() //不带头结点通过Link管理链表是否带头结点主要看链表有无空结点 { Link *plink malloc(sizeof(Link)); if (NULL plink) { printf(malloc error\n); return NULL; } plink-phead NULL; plink-len 0; return plink; }头结点和头指针的关系:不管带不带头结点头指针都始终指向链表的第一个结点而头结点是带头结点的链表中的第一个结点结点内通常不存储信息。引入头结点后可以带来两个优点:1.第一个数据结点的位置被存放在头结点的指针域中因此在链表的第一个位置上的操作和在表的其他位置上的操作一致无须进行特殊处理。2.无论链表是否为空其头指针都是指向头结点的非空指针(空表中头结点的指针域为空)因此空表和非空表的处理也就得到了统一。内存布局以下为三种常见链表结构以下为不带头结点的链表相关基础功能int insert_link_head(Link_t *plink, int data) //头插 { Node_t *pinsert malloc(sizeof(Node_t)); if (NULL pinsert) { printf(malloc error\n); return -1; } pinsert-data data; pinsert-pnext NULL; pinsert-pnext plink-phead; plink-phead pinsert; plink-clen; return 0; } void show_link(Link_t *plink) //遍历 { Node_t *ptmp plink-phead; while (ptmp ! NULL) { printf(%d , ptmp-data); ptmp ptmp-pnext; } printf(\n); } int is_empty_link(Link_t *plink) //判空 { if (NULL plink-phead) { return 1; } return 0; } int insert_link_tail(Link_t *plink, int data) //尾插 { Node_t *pinsert malloc(sizeof(Node_t)); if (NULL pinsert) { printf(mallocc error\n); return -1; } pinsert-data data; pinsert-pnext NULL; if (is_empty_link(plink)) { plink-phead pinsert; } else { Node_t *ptmp plink-phead; while (ptmp-pnext ! NULL) { ptmp ptmp-pnext; } ptmp-pnext pinsert; } plink-clen; return 0; }int delete_link_head(Link_t *plink) //头删 { if (is_empty_link(plink)) { return -1; } Node_t *pfree plink-phead; plink-phead pfree-pnext; free(pfree); plink-clen--; return 0; } int delete_link_tail(Link_t *plink) //尾删 { if (is_empty_link(plink)) { return -1; } else if (NULL plink-phead-pnext) { free(plink-phead); plink-phead NULL; } else { Node_t *ptmp plink-phead; while (ptmp-pnext-pnext ! NULL) { ptmp ptmp-pnext; } free(ptmp-pnext); ptmp-pnext NULL; } plink-clen--; return 0; } void destroy_link(Link_t *plink) //销毁 { while (!is_empty_link(plink)) { delete_link_head(plink); } free(plink); }3.内存泄漏内存泄露用户自己申请的堆区空间使用完没有及时释放则造成内存泄露。检测程序有没有内存泄露valgrind内存错误检测工具GNU提供可以检测程序运行过程中的内存泄露情况以及野指针的使用情况等。使用方法安装valgrind工具sudo apt-get isntall valgrind 编译完程序后使用 valgrind ./a.out valgrind --leak-checkfull ./a.out 6742 HEAP SUMMARY: 6742 in use at exit: 112 bytes in 7 blocks 6742 total heap usage: 10 allocs, 3 frees, 1,168 bytes allocated 6742 6742 LEAK SUMMARY: 6742 definitely lost: 16 bytes in 1 blocks 6742 indirectly lost: 96 bytes in 6 blocks 6742 possibly lost: 0 bytes in 0 blocks 6742 still reachable: 0 bytes in 0 blocks 6742 suppressed: 0 bytes in 0 blocks 6742 Rerun with --leak-checkfull to see details of leaked memory