链表基本操作实验报告

实验实验 2 链表基本操作实验链表基本操作实验 一 实验目的一 实验目的 1 定义单链表的结点类型 2 熟悉对单链表的一些基本操作和具体的函数定义 3 通过单链表的定义掌握线性表的链式存储结构的特点 二 实验内容与要求二 实验内容与要求 该程序的功能是实现单链表的定义和主要操作 如 单链表建立 输出 如 单链表建立 输出 插入 删除 查找等操作插入 删除 查找等操作 该程序包括单链表结构类型以及对单链表操作的具 体的函数定义和主函数 程序中的单链表 带头结点 结点为结构类型 结点 值为整型 要求 同学们可参考指导书实验 2 程序 教材算法及其他资料编程实现单链表相 关操作 必须包括单链表创建 输出 插入 删除操作 其他操作根据个人情 况增减 三 三 算法分析与设计 算法分析与设计 1 创建单链表 LinkedList LinkedListCreat 创建链表函数 LinkedList L LinkedListInit p r 调用初始化链表函数 r L r 指向头结点 使用 malloc 函数动态分配存储空间 指针 p 指向新开辟的结点 并将元素存 放到新开辟结点的数据域 p LinkedList malloc sizeof LNode p data x r next p 将新的结点链接到头结点 r 之后 r p r 指向 p 结点 scanf d 满足条件循环输入链表元素 while x flag 当输入不为 1 时循环 r next NULL return L 将链表结尾赋空值 返回头结点 L 头结点 L L An A1 A2 2 单链表插入 p s s data x s next p next p next s 3 单链表的删除 p p next p next next void LinkedListInsert LinkedList L int i ElemType x 链表插入函数 L 头指针 i 插入位置 x 插入元素 LinkedList p s 定义结构体类型指针 p s j 1 p L 定义整型 j 计数 寻找插入位置 p 指针指向头结点 p p next j 满足条件时 p 指针后移 j 自加 1 while ps LNode malloc sizeof LNode 使用 malloc 函数动态分配存储空间 指针 s 指向新开辟的结点 并将插入元素 x 存放 到新开辟结点 s 的数据域 将结点 s 指向 i 1 结点位置 第 i 个结点指向 s 实现了 链表元素插入 a b x b c 四 四 运行结果运行结果 1 单链表初始化 2 创建单链表 3 求链表长度 4 检查链表是否为空 5 遍历链表 6 从链表中查找元素 7 从链表中查找与给定元素值相同的元素在顺序表中的位置 8 向链表中插入元素 插入元素之后的链表 9 从链表中删除元素 删除位置为 6 的元素 是 3 10 清空单链表 五 实验体会实验体会 经过这次单链表基本操作实验 自己的编程能力有了进一步的提高 认识到 自己以前在思考一个问题上思路不够开阔 不能灵活的表达出自己的想法 虽 然在打完源代码之后出现了一些错误 但是经过认真查找 修改 最终将错误 一一修正 主要是在写算法分析的时候出现了障碍 经过从网上查找资料 自 己也对程序做了仔细的分析 对单链表创建 插入 删除算法画了详细的 N S 流程图 六 C 语言版原代码 include include 定义 ElemType 为 int 类型 typedef int ElemType define TRUE 1 define FALSE 0 define NULL 0 define flag 1 单链表的结点类型 typedef struct LNode ElemType data struct LNode next LNode LinkedList 初始化单链表 LinkedList LinkedListInit LinkedList L L LinkedList malloc sizeof LNode L next NULL return L 清空单链表 void LinkedListClear LinkedList L L next NULL printf 链表已经清空 n 检查单链表是否为空 int LinkedListEmpty LinkedList L if L next NULL return TRUE else return FALSE 遍历单链表 void LinkedListTraverse LinkedList L LinkedList p p L next if p NULL printf 单链表为空表 n else printf 链表中的元素为 n while p NULL printf d p data p p next printf n int LinkedListLength LinkedList L LinkedList p int j p L next j 0 while p NULL j p p next return j LinkedList LinkedListGet LinkedList L int i LinkedList p int j p L next j 1 while p NULLj if j i return p else return NULL int LinkedListLocate LinkedList L ElemType x LinkedList p int j p L next j 1 while p NULLj if p return j else return 0 void LinkedListInsert LinkedList L int i ElemType x LinkedList p s int j j 1 p L while pj if p NULL j i printf 插入位置不正确 n else s LNode malloc sizeof LNode s data x s next p next p next s printf d 已插入到链表中 n x void LinkedListDel LinkedList L int i LinkedList p q int j j 1 p L while p nextj if p next NULL printf 删除位置不正确 n else q p next p next q next free q printf 第 d 个元素已从链表中删除 n i LinkedList LinkedListCreat LinkedList L LinkedListInit p r ElemType x r L printf 请依次输入链表中的元素 输入 1 结束 n scanf d while x flag p LinkedList malloc sizeof LNode p data x r next p r p scanf d r next NULL return L int scan int d printf 请选择要进行的操作 n printf n printf 1 初始化 2 清空 3 求链表长度 4 检查链表是否为空 n printf n printf 5 遍历链表 6 从链表中查找元素 n printf n printf 7 从链表中查找与给定元素值相同的元素在顺序表中的位置 n printf n printf 8 向链表中插入元素 9 从链表中删除元素 10 创建线性表 n printf n printf 其他键退出 n printf 输入 scanf d return d main int quit 0 int i locate ElemType e LinkedList L p while quit switch scan case 1 L LinkedListInit printf n break case 2 LinkedListClear L printf n break case 3 printf 链表长度为 d n LinkedListLength L break case 4 if LinkedListEmpty L printf 链表为空 n else printf 链表非空 n break case 5 LinkedListTraverse L break case 6 printf 请输入待查询元素在链表中的位置 scanf d p LinkedListGet L i if p printf 链表第 d 个元素的值为 d n i p data else printf 查询位置不正确 n break case 7 printf 请输入待查询元素的值 scanf d locate LinkedListLocate L e if locate printf d 在链表中的位置是 d n e locate else printf 链表中没有值为 d 的元素 n e break case 8 printf 请输入插入元素的位置和值 中间以空格或回车分隔 n