数据结构实验线性表基本操作.doc

学学 数据结构数据结构 课程课程 实验报告实验报告 实实 验验 名名 称 称 线性表基本操作的实现 实验室实验室 中心中心 学学 生生 信信 息 息 专专 业业 班班 级 级 指指 导导 教教 师师 实验完成时间 实验完成时间 2016 教师评阅意见 签名 年 月 日 实验成绩 章 线性表提升实验 2 实验一实验一 线性表基本操作的实现线性表基本操作的实现 一 实验目的一 实验目的 1 熟悉 C 语言的上机环境 进一步掌握 C 语言的结构特点 2 掌握线性表的顺序存储结构的定义及 C 语言实现 3 掌握线性表的链式存储结构 单链表的定义及 C 语言实现 4 掌握线性表在顺序存储结构即顺序表中的各种基本操作 5 掌握线性表在链式存储结构 单链表中的各种基本操作 二 实验内容及要求二 实验内容及要求 1 顺序线性表的建立 插入 删除及合并 2 链式线性表的建立 插入 删除及连接 三 实验设备及软件三 实验设备及软件 计算机 Microsoft Visual C 6 0 软件 四 设计方案 算法设计 四 设计方案 算法设计 采用的数据结构 本程序顺序表的数据逻辑结构为线性结构 存储结构为顺序存储 链表的 数据逻辑结构依然为线性结构 存储结构为链式结构 设计的主要思路 1 建立含 n 个数据元素的顺序表并输出该表中各元素的值及顺序表的长度 顺序 表的长度和元素由用户输入 2 利用前面建立的顺序表 对顺序表进行插入 删除及合并操作 3 建立一个带头结点的单链表 结点的值域为整型数据 链表的元素由用户输入 章 线性表提升实验 3 4 对前面建立的链表进行插入 删除及连个链表的连接操作 算法描述 1 顺序表 void Init sqlist 初始化顺序表 BOOL Inse sqlist 在线性表中插入元素 BOOL del sqlist 在线性表中删除元素 int Loc sqlist char 在线性表中定位元素 void print sqlist 输出顺序表 void combine sqlist 两个线性表的合并 2 链表 void CreaL LinkList 生成一个单链表 BOOL LInsert LinkList 在单链表中插入一个元素 BOOL LDele LinkList 在单链表中删除一个元素 BOOL LFind key LinkList char int 按关键字查找一个元素 BOOL LFind order LinkList char 按序号查找一个元素 void LPrint LinkList 显示单链表所有元素 void LUnion LinkList 两个链表的连接 五 程序代码五 程序代码 1 顺序表 include 章 线性表提升实验 4 include define Max 116 enum BOOL False True typedef struct char elem Max 线性表 int last last 指示当前线性表的长度 sqlist void Init sqlist BOOL Inse sqlist 在线性表中插入元素 BOOL del sqlist 在线性表中删除元素 int Loc sqlist char 在线性表中定位元素 void print sqlist void combine sqlist void main sqlist L1 sqlist L2 sqlist L3 int loc S 1 char j ch BOOL temp printf 本程序用来实现顺序结构的线性表 n printf 可以实现查找 插入 删除 两个线性表的合并等操作 n Init L1 章 线性表提升实验 5 while S printf n 请选择 n printf 1 显示所有元素 n printf 2 插入一个元素 n printf 3 删除一个元素 n printf 4 查找一个元素 n printf 5 线性表的合并 n printf 6 退出程序 n n scanf c switch j case 1 print L1 break case 2 printf 请输入要插入的元素 一个字符 和插入位置 n printf 格式 字符 位置 例如 a 2 n scanf c d temp Inse L1 loc ch if temp False printf 插入失败 n else printf 插入成功 n print L1 break case 3 printf 请输入要删除元素的位置 scanf d temp del L1 loc ch if temp True printf 删除了一个元素 c n ch 章 线性表提升实验 6 else printf 该元素不存在 n printf 删除该元素后的线性表为 print L1 break case 4 printf 请输入要查找的元素 scanf c loc Loc L1 ch if loc 1 printf 该元素所在位置 d n loc 1 else printf c 不存在 n ch break case 5 printf 请输入要进行合并的第二个线性表 Init L2 combine L1 L2 L3 printf 合并前的两个线性表如下 n print L1 print L2 printf 输出合并后的线性表如下 n print L3 break default S 0 printf 程序结束 按任意键退出 n getch 章 线性表提升实验 7 void Init sqlist printf 请输入初始线性表长度 n scanf d printf 请输入从 1 到 d 的各元素 字符 例如 abcdefg n v last getchar for i 0 i v last i scanf c BOOL Inse sqlist if locv last 1 printf 插入位置不合理 n return False else if v last Max printf 线性表已满 n return False else for i v last 1 i loc 1 i 章 线性表提升实验 8 v elem i 1 v elem i v elem loc 1 ch v last return True BOOL del sqlist if locv last return False else ch v elem loc 1 for j loc 1 j v last 1 j v elem j v elem j 1 v last return True int Loc sqlist v char ch 在线性表中查找 ch 的位置 成功返回其位置 失败 返回 1 int i 0 while i v last 章 线性表提升实验 9 if v elem i ch return i else return 1 void print sqlist v 显示当前线性表所有元素 int i for i 0 i v last i printf c v elem i printf n void combine sqlist int j 0 int k 0 while i s1 last i else 章 线性表提升实验 1 0 s3 elem k s2 elem j j k if i s1 last while j s2 last s3 elem k s2 elem j k j if j s2 last while i s1 last s3 elem k s1 elem i k s3 last k 章 线性表提升实验 1 1 2 链表的操作 include include include define LEN sizeof LNode enum BOOL False True typedef struct node char data struct node next LNode LinkList void CreaL LinkList 生成一个单链表 BOOL LInsert LinkList 在单链表中插入一个元素 BOOL LDele LinkList 在单链表中删除一个元素 BOOL LFind key LinkList char int 按关键字查找一个元素 BOOL LFind order LinkList char 按序号查找一个元素 void LPrint LinkList 显示单链表所有元素 void LUnion LinkList 两个链表的连接 void main LinkList L LinkList T 章 线性表提升实验 1 2 LinkList H BOOL temp int num num1 loc flag 1 char j ch printf 本程序实现链式结构的线性表的操作 n printf 可以进行插入 删除 定位 查找等操作 n printf 请输入初始时链表长度 scanf d CreaL L num LPrint L while flag printf 请选择 n printf 1 显示所有元素 n printf 2 插入一个元素 n printf 3 删除一个元素 n printf 4 按关键字查找元素 n printf 5 按序号查找元素 n printf 6 链表的连接 n printf 7 退出程序 n scanf c switch j case 1 LPrint L break case 2 printf 请输入元素 一个字符 和要插入的位置 n printf 格式 字符 位置 例如 a 3 n scanf c d 章 线性表提升实验 1 3 temp LInsert L loc ch if temp False printf 插入失败 n else printf 插入成功 n LPrint L break case 3 printf 请输入要删除的元素所在位置 scanf d temp LDele L loc ch if temp False printf 删除失败 n else printf 成功删除了一个元素 c n ch LPrint L break case 4 if L next NULL printf 链表为空 n else printf 请输入要查找的元素 一个字符 scanf c temp LFind key L ch loc if temp False printf 没有找到该元素 n else printf 该元素在链表的第 d 个位置 n loc break case 5 if L next NULL printf 链表为空 n 章 线性表提升实验 1 4 else printf 请输入要查找的位置 scanf d temp LFind order L ch loc if temp False printf 该位置不存在 n else printf 第 d 个元素是 c n loc ch break case 6 if L next NULL printf 链表为空 n else printf 请输入第二个链表的长度 scanf d CreaL T num1 if T next NULL printf 第二个链表为空 n LUnion L T H num num1 printf 输出连接后链表中的所有元素 printf n LPrint H break default flag 0 printf 程序结束 按任意键退出 n 章 线性表提升实验 1 5 getch void CreaL LinkList LinkList p v LinkList malloc LEN v next NULL printf 请输入 d 个字符 例如 abcdefg n n getchar for i n i 0 i p LinkList malloc LEN scanf c p next v next v next p BOOL LInsert LinkList int j 0 p v while p j 章 线性表提升实验 1 6 if p j i 1 return False s LinkList malloc LEN s data e s next p next p next s return True BOOL LDele LinkList int j 0 p v while p next j if p next j i 1 return False q p next p next q next e q data free q return True BOOL LFind key LinkList v char e int 章 线性表提升实验 1 7 LinkList p p v next while p data e i if p data e return False else return True BOOL LFind order LinkList v char int j 0 p v while p next j if j i return False else e p data return True void LPrint LinkList v 显示链表所有元素 LinkList q 章 线性表提升实验 1 8 q v next printf 链表所有元素 while q NULL printf c q data q q next printf n void LUnion LinkList LinkList p w LinkList malloc LEN 生成头结点 w next NULL for i n i 0 i p LinkList malloc LEN 生成新结点 if u NULL p data u data u u next else p data v data v v next p next w next w next p 章 线性表提升实验 1 9 六 测试结果及说明六 测试结果及说明 顺序表和链表基本操作的实现程序编译结果没错误和提醒 运行测试结果正 确 没有出现错误 1 顺序表 2 链表 章 线性表提升实验 2 0 七 实验体会七 实验体会 1 由于 C 语言的数组类型也有随机存取的特点 一维数组的机内表示就是顺序结 构 因此 可用 C 语言的一维数组实现线性表的顺序存储 2 注意如何取到第 i 个元素 在插入过程中注意溢出情况以及数组的下标与位序 顺序表中元素的次序 的区别 3 单链表的结点结构除数据域外 还含有一个指针域 章 线性表提升实验 2 1 线性表提升实验线性表提升实验 一 一 实现顺序表元素的就地逆置 实现顺序表元素的就地逆置 一 设计方案一 设计方案 采用的数据结构 本程序采用的数据逻辑结构为线性结构 存储结构为顺序结构 算法的总 体功能是实现顺序表中元素的逆置 设计的主要思路 由用户确定初始顺序表的长度并输入初始顺序表的元素 然后通过交换元 素的方法将初始表中的元素进行逆置处理 输出元素 算法描述 status Initlist Sq Sqlist L 对顺序表 A 进行初始化 void input Sqlist A 对一个线性表输入数据 是先输入长度 然后再输入数 据 void print Sqlist A 对一个线性表进行输出 void invert Sqlist A 实现一个顺序表的逆置 二 主要代码二 主要代码 include 章 线性表提升实验 2 2 include include define SIZE 100 define ListInc 10 define OK 1 typedef struct int elem int length int listsize Sqlist typedef int status status Initlist Sq Sqlist L L elem int malloc SIZE sizeof status if L elem printf voerflow else L length 0 L listsize SIZE return OK 对一个线性表输入数据 是先输入长度 然后再输入数据 void input Sqlist A int i 0 printf 本程序用于实现顺序表的逆置 n printf n 请输入长度 n 章 线性表提升实验 2 3 scanf d printf 请输入数 n for i 0 ilength i scanf d 对一个线性表进行输出 void print Sqlist A int i for i 0 ilength i printf d t A elem i printf n n void invert Sqlist A int n A length int m A length 2 i int temp for i 0 ielem i A elem i A elem n i 1 A elem n i 1 temp 章 线性表提升实验 2 4 void main Sqlist A 定义一个线性表 A Initlist Sq 对 A 进行初始化 input 输入数据 printf 输入的数据为 n print printf 逆序处理后为 n invert 对线性表 A 逆置 print 输出逆置以后的 A 三 测试结果及说明三 测试结果及说明 由用户输入初始顺序表的长度以及元素 然后通过程序实现初始顺序表的 逆置并输出结果 程序的测试结果完全正确 没有出现任何的错误 章 线性表提升实验 2 5 二 二 实现单循环链表的逆置 实现单循环链表的逆置 一 设计方案一 设计方案 采用的数据结构 本程序采用的数据逻辑结构为线性结构 存储结构为链式存储结构 算法 的总体功能是实现单循环链表中元素的逆置 设计的主要思路 由用户确定初始链表的长度并输入初始链表的元素 然后通过过交换指针 的方法将初始表中的元素进行逆置处理 输出元素 算法描述 void creatlinklist linklist struct lnode next lnode linklist 建立一个空表 初始化 并对其进行输入值 void creatlinklist linklist 章 线性表提升实验 2 6 if l exit OVERFLOW l next l 循环链表 linklist p q int i q l printf 请输入 d 个元素 n n for i 0 idata p next q next q next p q p 逆置函数 void invert linklist p l next q p next r q next while p l q next p 章 线性表提升实验 2 7 p q q r r r next int main printf 本程序用于实现单循环链表的逆置处理 n n linklist l p int length i printf 请输入元素的个数 n scanf d creatlinklist l length p l next printf 输入的链表为 n while p l printf d p data p p next printf n printf 逆置后的链表为 n invert l p l next i 0 while p l 章 线性表提升实验 2 8 printf d p data p p next printf n return 0 三 测试结果及说明三 测试结果及说明 由用户确定输入的元素个数为 6 个 依次输入 16 25 34 43 52 61 逆置处理后输出的结果为 61 52 43 32 21 16 程序运行的结果正确 没 有出现错误 三 三 解决约瑟夫环的出列问题 解决约瑟夫环的出列问题 一 设计方案一 设计方案 采用的数据结构 本程序采用的数据逻辑结构为线性结构 存储结构为链式存储结构 算法 的总体功能是实现约瑟夫环的出列问题 设计的主要思路 章 线性表提升实验 2 9 设编号为 1 2 3 n 的 n n 0 个人按顺时针方向围坐一圈 每个人 持有一个正整数密码 开始时任选一个正整数做为报数上限 m 从第一个人开 始顺时针方向自 1 起顺序报数 报到 m 是停止报数 报 m 的人出列 将他的密 码作为新的 m 值 从他的下一个人开始重新从 1 报数 如此下去 直到所有人 全部出列为止 令 n 最大值取 30 要求设计一个程序模拟此过程 求出出列编 号序列 算法描述 static void CreaL NodeType const int 运行 约瑟夫环 问题 static void PrintL const NodeType 得到一个结点 static NodeType GetNode const int const int 测试链表是否为空 空为 True 非空为 False static unsigned EmptyL const NodeType static void StatGame NodeType ppHead int iCipher 二 主要代码二 主要代码 include include define Max 30 define True 1 define False 0 typedef struct NodeType int Num int PassWord struct NodeType next NodeType static void CreaL NodeType const int 运行 约瑟夫环 问题 static void PrintL const NodeType 得到一个结点 章 线性表提升实验 3 0 static NodeType GetNode const int const int 测试链表是否为空 空为 True 非空为 False static unsigned EmptyL const NodeType static void StatGame NodeType ppHead int iCipher int main void printf 本程序用于实现约瑟夫环操作 n n int n m NodeType pHead NULL while 1 printf 输入总的人数 n Max printf 数字太大 请重新输入 n continue else break CreaL printf n 打印出原始每个结点的序列号和密码 n PrintL pHead printf n 最终每个结点退出的序列号和密码 n 章 线性表提升实验 3 1 StatGame return 0 static void CreaL NodeType ppHead const int n int i iCipher NodeType pNew pCur for i 1 inext ppHead else pNew ne