一、基本概念数据结构数据结构存储具有一种或多种特定关系的数据的集合如何组织和存储数据。程序设计 数据结构 算法数据与数据之间的关系逻辑结构 数据元素与元素之间的关系集合 数据元素与元素之间关系平等线性结构 数据元素与元素之间一对一的关系顺序表数组、链表、队列、栈树形结构 数据元素与元素之间一对多的关系二叉树图形结构 数据元素与元素之间多对多的关系网状结构物理结构 数据元素在计算机内存中的存储方式顺序存储选取内存中连续空间进行存储 代表顺序表数组1. 内存空间必须连续 1. 数据元素的插入和删除需要移动后续大量数据不方便 1. 访问元素效率高 1. 需要预分配把内存空间分配不合适可能造成内存空间浪费或者数组越界链式存储 可以选取非连续内存空间进行存储代表链式表内存空间可以不连续插入和删除数据元素方便访问数据元素必须要遍历不需要预分配内存空间可以根据数据动态存储索引存储将要存储的元素关键字和存储位置构建索引表数据查找是通过查询索引表获取数据的真正存储位置。散列存储哈希存储将要存储的元素的关键字和存储位置之间建立起对应关系这个关系称为哈希函数数据存储时按照哈希函数的映射进行存储数据查找时也按照哈希函数的映射进行查找。数据结构学习内容顺序表数组单向链式表双向链表循环链表队列栈二叉树哈希表4 . 知识储备 结构体 指针 动态内存分配二、单向链表API应用程序接口创建链表链表插入(头插、尾插)链表删除头删、尾删查找修改链表遍历链表销毁链表数据类型构造//链表结点类型 typedef struct node { int data; //数据域保存的数据 struct node *pnext; //指针域下一个结点的地址 }Node_t; //链表对象类型 typedef struct link { Node_t *phead; //链表头节点指针 int clen; //链表当前结点的个数 }Link_t;单向链表的创建Link_t *create_link() { Link_t *plink malloc(sizeof(Link_t)); if (NULL plink) { printf(malloc error\n); return NULL; } plink-phead NULL; plink-clen 0; return plink; }单向链表头插创建结点为结点赋值让要插入结点的指针域指向原来的头节点让phead指向新插入结点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;extern }单向链表尾插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_tail(Link_t *plink) { if (is_empty_link(plink)) { return -1; } else if (NULL plink-phead) { 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; }内存泄露用户自己申请的堆区空间使用完没有及时释放则造成内存泄露。检测程序有没有内存泄露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