数据结构单链表

实验一 单链表 一 实验目的 1 掌握用Vc 上机调试程序的基本方法 2 掌握单链表的建立 插入 删除以及相关操作 二 实验内容 1 单链表的插入算法 2 单链表的删除算法 3 两个有序单链表合并成一个有序单链表的算法 三 实验要求 1 学生用C C完成算法设计和程序设计并上机调试通过 2 撰写实验报告 提供实验测试数据和实验结果 3 分析算法 要求给出具体的算法分析结果 包括时间复杂度和空间复杂度 并简要给出算法设计小结和心得 四 实验准备 1 复习C 语言中指针的用法 特别是结构体的指针的用法 2 了解单链表的概念 单链表的定义方法 3 掌握线性表在链式存储结构上实现基本操作 查找 插入 删除的算法 在实现这些算法的时候 要注意判断输入数据的合法性 除此之外还要注意以 下内容 在实现查找的时候 首先要判断该单链表是否为空 其次要判断查找后的结果 查到时输出查到的数据 未查到时给出错误提示 在实现插入的时候 由于是链式存储 它可以随机产生和回收存储空间 所以 它不要判断线性表是否为满 但仍需判断要插入的位置是否合法 其次要注意 插 入的时候语句的顺序不可颠倒 否则出错 在实现删除的时候 首先要判断线性表是否为空 为空则不能删除 其次在删 除后要回收空间 五 实验步骤 1 编程实现建立一个单链表 并在此表中插入一个元素和删除一个元素 5 1 通过键盘读取元素建立单链表 2 指定一个位置 在此位置之前插入一个新元素 3 指定一个位置 删除此位置元素 2 两个有序单链表合并成一个有序单链表的算法 1 通过键盘读取元素建立2 个有序单链表 2 将二两个有序单链表合并成一个有序单链表 3 输出合并后的单链表 六 实验参考代码 1 编程实现建立一个单链表 并在此表中插入一个元素和删除一个元素 include stdio h include stdlib h define OK 1 define ERROR 0 typedef int ElemType typedef int Status typedef struct Lnode ElemType data struct Lnode next Lnode LinkList 以下是建立单链表 void CreatList L LinkList int n i p Lnode malloc sizeof Lnode head tail p head next NULL printf Please input length to creat a list n scanf d printf Please input a group of values of the list n for i 1 idata p next NULL tail next p tail p printf A list has been created successfully n 以下是输出单链表 void OutputList L LinkList L LinkList p L next if p NULL printf n No list n return printf The list is n while p printf 4d p data p p next printf n 在第i个元素之前插入一个元素 Status ListInsert L LinkList L int i ElemType e LinkList p s p L int j 0 while p j if p j i 1 return ERROR s LinkList malloc sizeof Lnode s data e s next p next p next s return OK 删除第 i 个元素 Status ListDelete L LinkList L int i ElemType p L int j 0 while p next j if p next j i 1 return ERROR q p next p next q next e q data free q return OK void main LinkList L int choice i ElemType e choice 1 printf We should create a list first CreatList L L OutputList L L while choice 0 printf n menu n printf 1 insert a elem printf 2 delete a elem printf 3 output a list printf 4 exit printf n n printf please choice 1 2 3 4 scanf d if choice 0 break else if choice 1 printf Please input a pos and a value what you want to insert n scanf d d if ListInsert L L i e printf The inserting action has been done n OutputList L L else printf The inserting pos is error please do again n else if choice 2 printf Please input a pos what you want to delete n scanf d if ListDelete L L i e printf The deleting action has been done the deleted value is d n e OutputList L L else printf The pos what you want to delete is error please do again n else if choice 3 OutputList L L else if choice 0 printf choice error n 2 两个有序单链表合并成一个有序单链表的算法 实现提示 实现提示 程序需要3 个指针 pa pb pc 其中pa pb 分别指向La表 Lb 表的首结点 用pa 遍历La 表 pb 遍历Lb 表 pc指向合并后的新表的最后一个结点 即尾结点 pc的初值指向La 表的头 8 结点 合并的思想是 先建立好两个链表La表和Lb 表 然后依次扫描La 和Lb 中的元素 比较 当 前元素的值 将较小者链到 pc之后 如此重复直到La 或Lb 结束为止 再将另一个链表 余下的内 容链到pc所指的结点之后 include stdio h include stdlib h typedef int ElemType typedef struct Lnode ElemType data struct Lnode next Lnode LinkList 以下是建立单链表 void CreatList L LinkList int n i p Lnode malloc sizeof Lnode head tail p head next NULL printf Please input length to creat a list n scanf d printf Please input a group of values of the list n for i 1 idata p next NULL tail next p tail p printf A list has been created successfully n 以下是输出单链表 void OutputList L LinkList L LinkList p L next if p NULL printf n No list n return printf The list is n while p printf 4d p data p p next printf n 以下将La 和Lb 表合并为Lc 表 void MergeList LinkList pa La next pb Lb next Lc pc La while papc pa pa pa next else pc next pb pc pb pb pb next pc next pa pa pb free Lb 以下是主程序 void main LinkList La Lb Lc printf We should create two incremental and orderly lists first n printf please creat a incremental and orderly list A n