嵌入式开发学习日志（数据结构--顺序结构单链表）Day19

一、顺序结构

安装软件命令： sudo apt-get install  (软件名)
安装格式化对齐：sudo apt-get install clang-format
内存泄漏检测工具： sudo apt-get install valgrind
 编译后，使用命令         valgrind ./a.out        即可看内存是否泄露

 1、顺序表的基本操作

        表头结构是可选项，但最好在使用中加上；

2、创建顺序

【.h】中

【.c】 中

 

【主函数中】 

 3、判断数据列表是否满了

 【.c】中

 

 

 4、尾部插入

【主函数中】 

5、遍历成员 

 

 

 6、计算装了几个元素

 

7、判断是不是空数组 

 

8、 查找元素

【.c】中

 【主函数】中

 9、指定位置插入元素；

【.c】中

【主函数中】

 

 10、删除一个元素；

 11、清空列表，结构还在

12、 修改列表中文件；

13、 全部销毁

二、线性表顺序存储的优点，缺点 

1、优点

（1）无需为表中的逻辑关系增加额外的存储空间
（2）可以快速随机访问元素O(1)/

2、缺点

（1）插入，删除元素需要移动元素o(n)
（2）无法动态存储。

 

三、链表（线性表的链式存储）

1、目的：

        解决顺序存储的缺点，插入和删除，动态存储问题；

2、 特点：

       （1） 线性表链式存储结构的特点是一组任意的存储单位存储线性表的数据元素，存储单元可以是连续的，也可以不连续;
       （2）可以被存储在任意内存未被占用的位置上,所以前面的顺序表只需要存储数据元素信息就可以了。在链式结构中还需要一个元素存储下一个元素的地址
        （3）为了表示每个数据元素，a[i]与其直接后继数据元素a[i+1]之间的逻辑关系，                                    对a[i]来说，除了存储其本身的信息外，还需要存一个指示器直接后续的信息。
        （4）我们把存储元素信息的域叫数据域，把存储直接后继位置的域叫指针域。这两部分信息组成数据元素ai的存储映像，叫结点(Node);

3、单向链表 

 

 

• next指针指向整个结点开始位置
• 自定义类型不支持嵌套定义，因为不知道分配多大的内存空间；即在typedef srtuct node中，struct node next;不可取                    但*next可取
• 内存中开辟空间，用指针去接表头结构

 3.1.1创建链表

【.h】中

 

 

 【.c】中

】

 【主函数中】

 3.1.2判断是否为空链表

3.1.3 头部插入

（1）链表为空(直接将head指向newnode)

 （2） 链表非空

 

【主函数】 

3.1.4获取有效元素的个数

 3.1.5 遍历表中元素

• 使tmp->next来进行遍历，借助循环 

 

 

3.1.6 查找成员

3.1.7删除成员

 

• 通过比较tmp下一个的内容来控制，使tmp停于待删结点的前一个结点 

 

 3.1.8尾部插入

【主函数】 

 3.1.9指定位置插入