链式存储结构(一)——单向链表的有关操作

精品文档 1欢迎下载1欢迎下载1欢迎下载 链式存储结构链式存储结构 一一 单向链表的有关操作单向链表的有关操作 实验目的 实验目的 1 掌握单向链表的存储特点及其实现 2 掌握单向链表的插入 删除算法及其应用算法的程序实现 实验内容 实验内容 1 随机产生或键盘输入一组元素 建立一个带头结点的单向链表 无序 2 遍历单向链表 3 把单向链表中元素逆置 不允许申请新的结点空间 4 在单向链表中删除所有的偶数元素结点 5 编写在非递减有序链表中插入一个元素使链表元素仍有序的函数 并利用该函数建立 一个非递减有序单向链表 6 利用算法 5 建立两个非递减有序单向链表 然后合并成一个非递增链表 7 利用算法 5 建立两个非递减有序单向链表 然后合并成一个非递减链表 8 利用算法 1 建立的链表 实现将其分解成两个链表 其中一个全部为奇数 令一个全 部为偶数 尽量利用已知的存储空间 9 利用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果 10 在主函数中设计一个简单的菜单 分别调试上述算法 实现源代码 实现源代码 include stdio h include stdlib h typedef int ElemType 元素实际类型 typedef struct LNode Elemtype data struct LNode next LNode LinkList 定义结点 指针类型 名 头插法建立无序链表 void CreateList LinkList ElemType e L LinkList malloc sizeof LNode L next NULL printf 头插法建立链表 以 0 结束 n scanf d while e p LinkList malloc sizeof LNode p data e p next L next L next p scanf d 非递减有序单向链表 L 插入元素 e 序列 仍有序 void insert Sort LinkList s LinkList malloc sizeof LNode s data e p L while P next 查找插入位置 s next p next 插入语句 p 结点 插入 s 结点 p next s 建立递增有序单向链表 void Create Sort LinkList L LinkList malloc sizeof LNode L next NULL 精品文档 2欢迎下载2欢迎下载2欢迎下载 printf 建立有序表 输入任意个整 型数据以 0 结束 n scanf d while e Insert Sort L e scanf d 单向链表的遍历 void Traverse LinkList L LinkList p printf 遍历链表 for p L next p p p next printf 5d p data printf n 在单向链表中删除元素 e void Delete LinkList p L q L next while q q q next if q printf nnot deleted 未 找到元素 e else p next q next 找到删除 free q 单向链表的逆置 void exch LinkList p L next L next NULL while p s p p p next s next L next L next s 两个非递减有序单向链表合并后仍为非 递减序列 void MergeIncrease LinkList La LinkList Lb LinkList p La next q Lb next Lc rear La free Lb while pp p next else s q q q next rear next s 较小元素插入表 尾 rear rear next if p rear next p else rear next q 主函数 include LinkList h void main LinkList La Lb Lc ElemType e int select 精品文档 3欢迎下载3欢迎下载3欢迎下载 do printf 1 建立无序表 再删除 指定元素 n printf 2 建立递增有序表 再逆置 n printf 3 建立两个递增有序表 将它们合并为一个仍递增表 n printf 0 退出 请输入选项 0 3 n scanf d switch select case 0 break case 1 CreateList La Traverse La printf 请输入需删除的元素 n scanf d Delete La e Traverse La break case 2 Create Sort La Traverse La exch La printf The list that is exchaged n Traverse La break case 3 Create Sort La Traverse La Create Sort Lb Traverse Lb MergeIncrease La Lb Lc Traverse Lc break default printf 输入选项错误 请重新输入 n while select 运行结果 精品文档 4欢迎下载4