数据结构-链表

一.数据结构1.1 什么叫数据结构数据结构一组用来保存一种或多种特定关系的数据集合组织和存储数据。程序设计 数据结构 算法1.2 数据与数据之间的关系1.2.1逻辑结构数据元素与元素之间的关系1、集合平等关系2、线性结构元素与元素之间一对一的关系(顺序表链表队列、栈)3、树形结构元素与元素之间一对多的关系(二叉树)4、图形结构元素与元素之间多对多的关系(图)1.2.2 物理结构数据元素在计算机内存中的存储方式1、顺序结构选用一段连续的内存空间比如数组1. 数据访问方便O12. 元素插入和删除需要移动大量数据效率低3. 预分配内存空间2、链式结构选用非连续的内存空间比如链表1. 数据访问需要遍历On2. 插入和删除元素方便3. 不需要预分配可以动态存储4.可以有效利用内存碎片(内存碎片一些游离的小的内存空间)3、散列结构哈希结构将要存储的数据的关键字和存储位置之间构建映射关系哈希函数存储和查找都根据映射关系查找为了提高数据的查找效率。4、索引存储通关索引表寻找数据的存储位置为了提高数据的查找效率。二. 单向链表2.1 单向链表结构2.2 单向链表实现//链表节点结构体 typedef struct linknode{ DATATYPE_T data;//数据域 struct linknode *pnext;//指针域 }Node_t; //链表对象结构体 typedef struct link{ Node_t *phead;//存储头节点 int clen;//链表节点个数 }Link_t;这里Node_t 与 Link_t 中 _t 的含义_t是type的缩写意思是这是一个通过typedef定义的【类型别名】不是原生类型。2.3 创建链表对象//创建链表对象 Link_t *creat_link() { Link_t *plink malloc(sizeof(Link_t)); if(plink NULL) { printf(malloc error!\n); return NULL; } plink-phead NULL; plink-clen 0; return plink; }2.4 创建链表新节点//创建链表新节点 Node_t *creat_node(DATATYPE_T x) { Node_t *pnode malloc(sizeof(Node_t)); if(pnode NULL) { printf(malloc error!\n); return NULL; } pnode-data x; pnode-pnext NULL; return pnode; }2.5 链表判空bool is_empty_link(Link_t *plink) { return plink-clen 0; }2.6 链表头插//链表头插 int insert_link_head(Link_t *plink, DATATYPE_T data) { Node_t *pnewnode creat_node(data); if(pnewnode NULL) return -1; pnewnode-pnext plink-phead; plink-phead pnewnode; plink-clen; return 0; }2.7 链表头删保存原头节点//链表头删 int delete_link_head(Link_t *plink) { if(is_empty_link(plink)) return 0; else { Node_t *pfree plink-phead;//保存原头节点 plink-phead pfree-pnext; plink-clen--; free(pfree); pfree NULL; return 0; } }2.8 链表尾插注意这里找尾节点是对ptail-pnext进行循环判断//链表尾插 int insert_link_tail(Link_t *plink, DATATYPE_T data) { Node_t *pnewnode creat_node(data);//创建新节点 if(pnewnode NULL) return -1; Node_t *ptail plink-phead; if(is_empty_link(plink))//表示链表为空 { plink-phead pnewnode; plink-clen; return 0; } while(ptail-pnext)//开始找尾节点 { ptail ptail-pnext; } ptail-pnext pnewnode;//连接新节点 plink-clen; return 0; }2.9 链表尾删注意链表尾删要分三种情况空链表只有一个节点一个以上节点。//链表尾删 int delete_link_tail(Link_t *plink) { if(is_empty_link(plink))//链表为空 return 0; else if(plink-phead-pnext NULL)//链表只有一个节点 { delete_link_head(plink); return 0; } //一个以上节点 else { Node_t *ptail plink-phead, *prev NULL; while(ptail-pnext) { prev ptail; ptail ptail-pnext; } prev-pnext NULL; free(ptail); ptail NULL; plink-clen--; return 0; } }2.10 链表打印//打印链表 void print_link(Link_t *plink) { Node_t *cur plink-phead; while(cur) { printf(%d-,cur-data); cur cur-pnext; } printf(NULL\n); }2.11 链表销毁//销毁链表 void destroy_link(Link_t *plink) { while(!is_empty_link(plink)) { delete_link_head(plink); } free(plink); }三. valgrind工具3.1 简介Valgrind 是 Linux GNU提供的一个内存错误检查软件核心用途是内存调试、内存泄漏检测、线程错误检测、性能分析。在程序运行过程中检查内存错误。3.2 安装方法使用命令sudo apt-get install valgrind3.3 使用方法valgrind ./可执行程序执行结果3101 3101 HEAP SUMMARY: //堆内存使用总结 3101 in use at exit: 96 bytes in 6 blocks //程序退出时还有96字节6块内存没释放 3101 total heap usage: 7 allocs, 1 frees, 1,120 bytes allocated //总共7次malloc但是只释放了1次1120字节被申请 3101 3101 LEAK SUMMARY: //泄漏总结 3101 definitely lost: 16 bytes in 1 blocks //明确泄漏 3101 indirectly lost: 80 bytes in 5 blocks //间接泄漏 3101 possibly lost: 0 bytes in 0 blocks //可疑泄漏 3101 still reachable: 0 bytes in 0 blocks //可回收但没回收 3101 suppressed: 0 bytes in 0 blocks //系统忽略的内存 3101 Rerun with --leak-checkfull to see details of leaked memory 3101 3101 For counts of detected and suppressed errors, rerun with: -v 3101 ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) //崩溃、越界、野指针的情况