这篇资源是关于西南交通大学数据结构实验的一个练习,重点在于单向链表的算法操作,包括链表的创建、插入、删除、查找和特定条件下的元素重组。实验目的是让学生掌握单向链表的基本操作及其算法实现。
在实验中,首先需要从键盘输入一系列非零整数来构建单向链表,输入0作为终止标志。接着,通过一个字符界面菜单提供以下功能:
1. 插入元素:用户输入要插入的位置`i`和元素`e`,在链表的第`i`个元素前插入`e`。程序需处理无效的位置号(如超出链表长度或负数)和存储空间不足的情况。
2. 删除元素:用户输入要删除的位置`i`,删除该位置的元素。程序需处理无效的位置号和空表的情况。
3. 查找元素:用户输入要查找的元素`e`,程序返回`e`在线性表中的所有位置(位置号从0开始)。如果元素不在链表中,则提示查找失败。
4. 显示线性表长度:输出当前链表的长度。
5. 调整连接:将所有负整数结点移到正整数结点之后,但保持原链表中正负整数的相对顺序。
数据结构设计方面,实验采用带附加头结点的单向链表,每个结点包含一个整型数据域用于存储整数值,以及一个指针域指向下一个结点。链表的创建、插入、删除等操作通过特定的算法实现:
- 建立链表:采用顺序方法,按输入顺序添加结点。
- 插入元素:使用主从指针推进法,确保正确插入位置。
- 删除元素:同样利用主从指针,找到目标位置并进行删除。
- 查找元素:遍历链表,查找给定元素的位置。
- 调整连接:遍历链表,区分正负整数,重新连接。
输入/输出设计上,整数通过空格、回车或制表符分隔,输入0结束输入。输出时,整数间用空格分隔,并有文字提示。编程语言选用Visual C++,代码采用C语言编写。
主要的函数包括:
- `LinkList crt()`:创建带附加头结点的单向链表。
- `void prt(LinkList h)`:输出链表所有元素。
- `void insert(LinkList h)`:在指定位置插入元素。
- `void del(LinkList h)`:删除指定位置的元素。
- `void find(LinkList h)`:查找指定元素在链表中的位置。
这个实验提供了实践数据结构基础操作的机会,有助于加深对单向链表的理解和应用。