\数据结构与算法实验报告**
\实验项目：线性表的基本操作**
一、 \实验目的**
\1. 理解线性表的类型定义；
\2. 掌握理解线性表的顺序表示何实现；
\3. 掌握理解线性表的链式表示和实现；
二、 \实验任务**
\1. 创建线性表结构；
\2. 完成线性表的顺序操作（初始化、插入、删除）；
\3. 完成线性表的链式操作（初始化、插入、删除、遍历、等）；
\4. 利用约瑟夫循环单链表解决排队报数问题；
三、 \实验仪器设备**
| 工作任务 | 所用工具或设备 | 套数 | 操作要领和注意事项 |
|---|---|---|---|
| 使用软件 | Visual Studio Code | 1 | 注意C程序的运行及保存 |
| 使用系统 | Windows7 | 1 | 使用完后拷贝源码并关机 |
四、 \实验主要内容**
1. \创建线性表结构**
1.1 线性表是最常用且简单的一种数据结构。线性表是N个数据元素的有限序列如图4.1.1所示。
图4.1.1
1.2 顺序线性表则是按照一定的地址顺序分配对应的地址空间如图4.1.2.1所示具体创建结构如图4.1.2.2所示。
图4.1.2.1
顺序线性表结构
图4.1.2.2
1.3 链式线性表则是用一组任意的储存单元储存下一个数据元素的地址如图4.1.3.1所示具体创建结构如图4.1.3.2所示。
链式线性表
图4.1.3.1
链式线性表结构
图4.1.3.2
2. \顺序线性表操作**
2.1 \初始化操作**
初始化需要在在内存中分配一个数据元素空间设置默认空间大小
和其实际存储的长度如图2.1.1所示。
图2.1.1
2.2 \插入数据元素操作**
需要判断其插入位置的前后是否已经存在数据表，如果存在需要进行数据移动等操作如图2.2.1所示。
图2.2.1
2.3 \删除数据元素**
需要判断删除位置是否存在数据，如果存在，在找到该位置然后
后面的数据向前赋值，并改变线性表的实际数据长度（在其基础上减一）如图2.3.1所示。
图2.3.1
3. \链式线性表操作**
3.1 \初始化操作**
初始化链表，需要在内存中分配一个空间作为线性表的头指针，
并将头指针的地址（L.next）设置为NULL，并通过返回操作状态，1成功；0失败来作为判定条件。如图3.1.1所示。
图3.1.1
3.2 \遍历打印线性表**
遍历打印，需要判断线性表中的元素的地址储存区域中是否包含下一个数据元素，如果不存在就结束遍历如图3.2.1所示。
图3.2.1
3.3 \插入数据元素**
插入数据元素时，需要判断是否存在该位置，如果可以下面就需要找到对应位置；判断该位置是否（Ln.next）指向下一个数据元素，没有则需要进行两个数据元素的位置指向如图3.3.1所示。
图3.3.1
3.4 \删除数据元素**
删除数据元素时也需要判断是否该位置有数据；删除数据元素就重要就是找到指定位置的数据元素，然后将需要删除的数据元素的地址指向重新指向，前元素指向删除元素的next如图3.4.1所示。
图3.4.1
3.5 \判断链表是否为空**
直接判断头指针是否指向下一个元素，没有则为空如图3.5.1所示。
图3.5.1
3.6 \返回****指定****数据在链表中的位置****
需要将查询值与链表线性表中的每一位数据元素中的数据进行比对，发现相同就返回对应的位置；可是设置一个计数器，将最先找的元素位置返回如图3.6.1所示。
图3.6.1
3.7 \销毁数据链表**
销毁链表线性表，需要通过循环将链表中的所有数据元素节点都销毁（free）并且还要销毁头节点如图3.7.1所示。
图3.7.1
3.8 \清空链表**
清空链表，需要将头节点后面的所有结点销毁，但是保留头节点，如图3.8.1所示。
图3.8.1
3.9 \判断返回数据链表长度**
需要判断长度，通过循环与计数器结合，来判断线性表链表的实际长度，不包括头指针如图3.9.1所示。
图3.9.1
3.10 \获取链表指定位置的数据**
先通过循环计数器找到指定数据节点，然后将该节点的对于的数据返回如图3.10.1所示。
图3.10.1
3.11 \查找指定元素的的前驱元素**
通过两个交替变量循环，再返回前驱的地址如图3.11.1所示。
图3.11.1
3.12 \查找指定元素的的后置元素**
通过两个交替变量循环，再返回后置的地址如图3.11.1所示
图3.12.1
4. \利用约瑟夫循环单链表解决排队报数问题**
4.1 \思路分析**
有n个人，编号为1，2，3…counts围成一个圆圈，按照顺时针方向从编号为key的人
开始报数，报数为number的人出列，她的下一个人重新开始报数，数到number的人出列，如此重复下去，知道所有人都出列，编写一个算法，要求输入counts,number,key按照出列的顺序输出对应的值
example:
8,1,2,3,4,5,6,7 counts=8,key=2,number=3
则按照输出的数值及编号为：4 7 2 6 3 1 5
五、 \实验结果**
1. \顺序线性表操作实验结果**
1.1 \初始化、插入、遍历**
1.2 \删除指定位置的数据**
2. \链式线性表操作实验结果**
2.1 \初始化、插入、遍历**
2.2 \删除操作**
2.3 \获取链表的长度**
2.4 \清空销毁链式线性表**
2.5 \获取指定数据的前驱节点**
2.6 \获取指定数据的后置节点**
2.7 \获取指定节点的数据**
3. \排队报数实验结果**
六、 \实验总结**
\1. 初步简单的认识了什么是线性表，及线性表的储存方式的表示与具体操作。
\2. 面对实际问题需要通过可视化数据分析，从而理解问题并通过算法解决问题。
\3. 线性表的两种存储方式顺序、链式都有对应的特点，缺点，常常需要争对不同的问题来选择。
\4. 顺序线性表的特点，插入、删除操作比较耗时（相对）；查询快等。
\5. 链式线性表的特点，插入、删除快（相对）；查询慢需要循环等。
\6. 通过结合两者的特点就出现了双向循环链式线性表等。
\7. 需要在后面的学习中完善去理解线性表。
