课程实验报告1线性表

课课 程程 实实 验验 报报 告告 专专 业业 年年 级级 2012 级软件工程级软件工程 课课 程程 名名 称称 数据结构数据结构 C 语言描述语言描述 指指 导导 教教 师师 申红婷申红婷 学学 生生 姓姓 名名 王晓霞王晓霞 学学 号号 20122205041002 实实 验验 日日 期期 2012 10 31 实实 验验 地地 点点 A3 笃行楼笃行楼 A 栋栋 306 实实 验验 成成 绩绩 教务处制教务处制 2013 年年 10 月月 31 日日 实验项目实验项目 名称名称 线性表实验 实验实验 目的及要求目的及要求 一 目的 1 使学生对线性表的顺序存储结构 基本操作和应用 能通过实验达到掌握和应 用的目的 2 使学生对线性表的线性表的链式结构 基本操作和应用 能通过实验达到掌握 和应用的目的 二 要求 实验前认真预习实验内容 实验时自觉遵守课堂纪律 严格按操作规程操作 既 要独立操作又要与其他同学配合 在实验过程中必须按照实验内容认真做完实验 并 认真填写相关实验报告 实验实验 内容内容 线性表的顺序存储结构和线性表的链式结构 基本操和应用 实验步骤实验步骤 1 阅读下面程序 在横线处填写函数的基本功能 并运行程序 写出结果 include include define ERROR 0 define OK 1 define INIT SIZE 5 初始分配的顺序表长度 define INCREM 5 溢出时 顺序表长度的增量 typedef int ElemType 定义表元素的类型 typedef struct Sqlist ElemType slist 存储空间的基地址 int length 顺序表的当前长度 int listsize 当前分配的存储空间 Sqlist int InitList sq Sqlist L 初始化顺序表 为其分配存储空间 int CreateList sq Sqlist L int n 创建一个顺序表 int ListInsert sq Sqlist L int i ElemType e 将新元素 e 插入到顺序表第 i 个位置 int PrintList sq Sqlist L 输出顺序表的元素 int ListDelete sq Sqlist L int i 删除第 i 个元素 int ListLocate Sqlist L ElemType e 查找值为 e 的元素 int InitList sq Sqlist L L slist ElemType malloc INIT SIZE sizeof ElemType if L slist return ERROR L length 0 L listsize INIT SIZE return OK InitList int CreateList sq Sqlist L int n ElemType e int i for i 0 i n i printf input data d i 1 scanf d if ListInsert sq L i 1 e return ERROR return OK CreateList 输出顺序表中的元素 int PrintList sq Sqlist L int i for i 1 ilength i printf 5d L slist i 1 return OK PrintList int ListInsert sq Sqlist L int i ElemType e int k if iL length 1 return ERROR if L length L listsize L slist ElemType realloc L slist INIT SIZE INCREM sizeof ElemType if L slist return ERROR L listsize INCREM for k L length 1 k i 1 k L slist k 1 L slist k L slist i 1 e L length return OK ListInsert 在顺序表中删除第 i 个元素 int ListDelete sq Sqlist L int i if L length 0 return 0 if iL length return 0 for int j jlength j L slist j 1 L slist j L length return 1 在顺序表中查找指定值元素 返回其序号 int ListLocate Sqlist L ElemType e for int i 1 ilength i if L slist i 1 e return i return 0 int main Sqlist sl int n m k printf please input n 输入顺序表的元素个数 scanf d if n 0 printf n1 Create Sqlist n InitList sq CreateList sq printf n2 Print Sqlist n PrintList sq printf nplease input insert location and data location data n scanf d d ListInsert sq printf n3 Print Sqlist n PrintList sq printf nplease input delete location location n scanf d ListDelete sq printf n4 Print Sqlist n PrintList sq printf nplease input data data n scanf d ListLocate printf n5 Print Sqlist n PrintList sq printf n else printf ERROR return 0 运行结果 算法分析 首先应该选择顺序表的动态存储方式进行顺序表结构的定义 然后在程序的开头 进行顺序表各种操作函数的声明以及预定义命令 接着编写各种操作函数的函数体 而在主函数中要首先调用 InitList sq if iL length return 0 for int j i jlength j L slist j 1 L slist j L length return 1 运行结果 算法分析 当在主函数里面调用删除功能函数并传参数进去时 程序将自动跳到函数体里面 利用所传参数一步步执行 在该函数里面 当把顺序表和序号 i 传值进去时 程序可 以先判断所传值是否满足条件 若满足 则开始从顺序表第一个元素开始依次遍历 直到找到第 i 个位置的元素 并将其删除 后面的元素依次前移 填补 而表的长度 则减一 删除成功 若不满足 则返回 0 表示删除失败 查找算法代码 int ListLocate Sqlist L ElemType e for int i 1 ilength i if L slist i 1 e return i return 0 运行结果 算法分析 当在主函数里面调用查找功能函数并传参数进去时 程序将自动跳到函数体里面 利用所传参数一步步执行 在该函数里面 当把顺序表和要查找的值 e 传值进去时 程序开始从顺序表第一个元素开始依次遍历 直到找到值为 e 的元素 并返回其位置 序号 查找成功 若遍历了顺序表所有元素依然没有符合条件的 e 的值 则返回 0 表示查找失败 3 阅读下面程序 在横线处填写函数的基本功能 并运行程序 写出结果 include include define ERROR 0 define OK 1 typedef int ElemType 定义表元素的类型 typedef struct LNode 线性表的单链表存储 ElemType data struct LNode next LNode LinkList LinkList CreateList int n 建立带表头节点的单链表 void PrintList LinkList L 输出带头结点单链表的所有元素 int GetElem LinkList L int i ElemType e 在单链表中查找第 i 个 节点的值 LinkList CreateList int n LNode p q head int i head LinkList malloc sizeof LNode head next NULL p head for i 0 idata 输入元素值 q next NULL 结点指针域置空 p next q 新结点连在表末尾 p q return head CreateList void PrintList LinkList L LNode p p L next p 指向单链表的第 1 个元素 while p NULL printf 5d p data p p next PrintList int GetElem LinkList L int i ElemType e LNode p int j 1 p L next while pj if p j i return ERROR e p data return OK GetElem int InsertList LinkList L int i ElemType e int j 1 LNode p q p L next while pj if p return ERROR q LNode malloc sizeof LNode q data e q next p next p next q return OK int DeleteList LinkList L ElemType e LNode p q p L next while pp p next if p return ERROR else q next p next free p return OK int main int n i ElemType e LinkList L NULL 定义指向单链表的指针 printf please input n 输入单链表的元素个数 scanf d if n 0 printf n1 Create LinkList n L CreateList n printf n2 Print LinkList n PrintList L printf n3 GetElem from LinkList n printf input i scanf d if GetElem L i else printf not exists printf n4 Insert from LinkList n 调用插入函数 printf input i scanf d 指定插入位置 printf input e scanf d 输入欲插入元素的值 InsertList L i e PrintList L 输出调用后的结果 printf n5 Delete from LinkList n 调用删除函数 printf input e scanf d 输入欲删除元素的值 DeleteList L e PrintList L 输出调用后的结果 printf n else printf ERROR return 0 运行结果 算法分析 首先应该进行单链表结构的定义 然后在程序的开头进行顺序表各种操作函数的 声明以及预定义命令 接着编写各种操作函数的函数体 而在主函数中要首先调用 LinkList CreateList int n 创建带头结点的单链表 输入结点数 然后依次输入各 个结点的值 接着调用打印单链表功能函数输出单链表中的值 再调用查找功能函数 输入查找元素的位置 输出对应元素的值 然后调用插入功能函数 输入要插入的位 置和元素 打印输出插入后的新链表 同理调用删除功能函数 输入要删除的元素值 最后打印输出删除后的单链表 4 为第 3 题补充插入功能函数和删除功能函数 并在主函数中补充代码验证算法的正 确性 插入算法代码 int InsertList LinkList L int i ElemType e int j 1 LNode p q p L next while pj if p return ERROR q LNode malloc sizeof LNode q data e q next p next p next q return OK 运行结果 算法分析 当在主函数里面调用查找功能函数并传参数进去时 程序将自动跳到函数体里面 利用所传参数一步步执行 在该函数里面 当把单链表 要插入的位置序号和元素内 容传值进去时 程序开始从单链表第一个元素开始依次遍历 直到找到插入位置的前 一个节点 用指针 p 指向它 然后创建一个以 e 为值的新节点指针 q 修改节点 q 的 next 域指向节点 p 的下一个节点 再将节点 p 的 next 域修改为指向新节点 s 返回 ok 表示插入成功 最后打印输出插入后的新链表 删除算法代码 int DeleteList LinkList L ElemType e LNode p q p L next while pp p next if p return ERROR else q next p next free p return OK 运行结果 算法分析 当在主函数里面调用删除功能函数并传参数进去时 程序将自动跳到函数体里面 利用所传参数一步步执行 在该函数里面 当把单链表 要删除的元素内容传值进去 时 程序开始从单链表第一个元素开始依次遍历 直