一、基本概念1.数据结构数据结构存储具有一种或多种特定关系的数据的集合如何组织和存储数据。程序设计数据结构算法2.数据与数据之间的关系1逻辑结构数据元素与元素之间的关系集合 数据元素与元素之间关系平等线性结构 数据元素与元素之间一对一关系顺序表数组、链表、队列、栈树形结构 数据元素与元素之间一对多关系二叉树图形结构数据元素与元素之间多对多关系网状结构2物理结构数据元素在计算机内存中的存储方式顺序存储选取内存中连续空间存储顺序表数组特点1.内存空间连续2.数据元素的插入和删除需要移动后续大量数据不方便3.访问元素效率高时间复杂度O(1)4.需要预分配内存空间分配不合适可能造成内存空间浪费、或数组越界5.容易造成内存碎片链式存储可以选取非连续空间存储链表特点1.内存空间可以不连续2.插入和删除数据元素方便3.访问数据元素需要遍历4.不需要预分配内存空间可以根据数据动态存储5.有效利用内存碎片索引存储将要存储的元素关键字和存储位置构建索引表数据查找时通过索引表获取数据的真正存储位置散列存储哈希存储将要存储的元素的关键字和存储位置之间建立起对应关系这个关系称为散列函数哈希函数数据存储时按照哈希函数的映射进行存储数据查找时也按照哈希函数的映射查找3.数据结构学习内容顺序表数组 单向链表 双向链表 循环链表 队列 栈 二叉树 哈希表4.知识储备结构体 指针 动态内存分配API应用程序接口1.创建链表2.链表插入头插尾插3.链表删除头删尾删4.查找5.修改6.链表遍历7.链表销毁二、单向链表创建链表插入链表遍历链表尾插头删尾删valgrind测试内存泄漏内存泄漏用户自己申请的堆区空间使用完没有及时释放则造成内存泄漏。valgrind内存错误检测工具GNU提供可以检测程序运行过程中的内存泄漏情况以及野指针的使用情况。valgrind ./a.out