一.逻辑结构与存储结构

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(NULL==phead) { printf("malloc error\n"); return NULL; } phead->pnext=NULL; phead->data=0; //头结点data为无效值 return phead; }

Link容器的带头结点：

Link * create_link() { Link *plink = malloc(sizeof(Link)); if(NULL==plink) { printf("malloc error\n"); return NULL; } Node *head = malloc(sizeof(Node)); if(NULL == head) { printf("mallochead error\n"); return NULL; } head->data=0; //头结点可不赋值 head->pnext=NULL; plink->len=0; plink->phead=head; 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-check=full ./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-check=full to see details of leaked memory