数据结构实验报告

江 西 科 技 师 范 学 院 实 验 报 告 课 程 数据结构B 系 别 通信与电子学院 班 级 电气信息类二班 学 号 20092118 姓 名 徐车生 报告规格 一 实验目的 二 实验原理 三 实验仪器 四 实验方法及步骤 五 实验记录及数据处理 六 误差分析及问题讨论 目 录 1 实验一 C 语言编程 3 2 实验二 顺序存储 4 3 实验三 链式存储 5 4 实验四 模式匹配算法应用 6 5 实验五 特殊矩阵 7 6 实验六 内排序 8 7 实验七 树与二叉树 9 8 实验八 图的遍历 11 9 实验九 检索 15 每次实验课必须带上此本子 以便教师检查预习情况和记录实验原始数据 实验时必须遵守实验规则 用正确的理论指导实践袁必须人人亲自动手实验 但反 对盲目乱动 更不能无故损坏仪器设备 这是一份重要的不可多得的自我学习资料袁它将记录着你在大学生涯中的学习和学 习成果 请你保留下来 若干年后再翻阅仍将感到十分新鲜 记忆犹新 它将推动你在人生 奋斗的道路上永往直前 实验一实验一 C语言编程语言编程 实验名称 实验一 C 语言编程 实验目的 复习 C 语言程序设计 回顾 C 语言结构数据及指针数据的应用 实验原理 C 语言结构化程序设计思想 结构数据类型 指针数据类型 实验设备 电脑 TURBO C2 0 WIN TC VISUAL C 实验内容 1 某组有 10 个人 每个人有 3 门课的考试成绩 求该组单科的平均成绩和 各科总平均成绩 2 用指针变量输出结构数组 结构数组存放了 5 个学生的信息 学生的信 息包括学号 姓名 性别和入学分数 1 实验代码 include void main float a 11 4 sum 0 int i j for i 0 i 10 i printf 请输入第 d 个学生的 3 门课成绩 i 1 for j 0 j 3 j scanf f printf 各门课的平均成绩 n for j 0 j 3 j sum 0 for i 0 i 10 i sum sum a i j a 10 j sum 10 0 printf 第 d 门课的平均成绩是 6 2f n j 1 a 10 j for i 0 i 3 i sum 0 for j 0 j 10 j sum a i j a i 3 sum 3 0 printf 第 d 个学生各科总平均成绩 6 2f n i 1 a i 4 实验结果 2 实验代码 include struct student int num char name 20 char sex float score struct student stu 5 001 zhang san M 98 002 li shi F 72 003 wang wu F 99 004 li lin M 79 005 wang ming M 80 void main struct student p printf No Name sex score n for p stu pnum p name p sex p score 实验结果 实验心得 本次试验 利用数据结构及指针计算十个学生的单科平均成绩和总的平均成绩 试验中定义二维变量 a 11 4 输入十个学生的成绩 分别存储在数组变量 a 中 通 过语句 sum 0 for i 0 isize 0 void append list s datatype x if s size MAXSIZE printf overflow n else s a s size x s size void display list s int i if s size 0 for i 0 isize i printf 5d s a i else printf list is null n void merge list la list lb list lc int i 0 j 0 k 0 while isize else lc a k lb a j while isize lc a k la a i while jsize lc a k lb a j lc size la size lb size void main list s h k d datatype x init k init init k printf 请输入表 S 的内容 n scanf d while x 0 append scanf d printf 请输入表 h 的内容 n scanf d while x 0 append 原该处 h 表写成了 s 表 scanf d merge display k printf n 实验结果 实验心得 本次实验很好的体现了函数调用技术 先通过函数 init 初始化 然后利用 merge list la list lb list lc 进行排列 最后 display 函数显示输出结果 通过本次实验了解 了顺序存储的方式以及如何实现数据的大小排列 很好掌握了函数调用的技巧 实验三 链式存储 实验名称 实验三 链式存储 实验目的 掌握线性表链式存储结构的描述 学会针对链式存储线性表的基本操作 实验原理 C 语言结构化程序设计思想 结构体及指针的应用 实验设备 电脑 TURBO C2 0 WIN TC VISUAL C 实验内容 1 已知两个依元素值递增有序排列的链表 A 和 B 且同一表中的元素值各 不相同 构造一个单链表 C 其元素为 A 和 B 中元素的交集 且表 C 中的元 素也依值递增有序排列 实验代码 include include malloc h define MAXSIZE 100 typedef int datatype typedef struct lindnode datatype info struct lindnode next node node init return NULL void creat node head node r s datatype x head r node malloc sizeof node printf n 创建链表 n scanf d while x s node malloc sizeof node s info x r next s r s scanf d r next NULL void display node head node p p head next if p printf kong n else while p printf 5d p info p p next void inter node A node B node C node pa A next pb B next s r C node malloc sizeof node C next NULL r C while pa NULL else if pa info pb info pb pb next else s node malloc sizeof node s info pa info s next NULL r next s r s pa pa next pb pb next r next NULL void main node head p q head init p init q init creat creat inter head p display q 实验结果 实验心得 本次实验很好的体现了链式排列的方式 通过本次实验 很好的掌握了链式排 列的方法 并且加深了指针变量的使用方法 实验四 模式匹配算法应用 实验名称 实验四 模式匹配算法应用 实验目的 掌握字符串存储结构的描述 学会字符串的模式匹配算法的应用 实验原理 C 语言结构化程序设计思想 结构体及指针和字符数组的应用 实验设备 电脑 TURBO C2 0 WIN TC VISUAL C 实验内容 1 朴素模式匹配算法 2 快速模式匹配算法 实验代码 1 朴素模式匹配算法 include stdio h define MAXSIZE 100 typedef struct char data MAXSIZE int length string void init string s s length 0 void input string s char c int i i 0 scanf c while c n s data i c scanf c s length i int pipei string s string t int i j i 0 j 0 while i s length else return 1 void main string s t init init printf please input string s input printf please input string t input int k pipei s t if k 1 printf string t is not in string s n else printf string t is in string s d n k 2 快速模式匹配算法 include stdio h define MAXSIZE 100 typedef struct char data MAXSIZE int length string void init string s s length 0 void input string s char c int i i 1 scanf c while c n s data i c scanf c s length i 1 void get next string T int next int i j i 1 j 0 next 1 0 while i T length if j 0 T data i T data j i j next i j 2 else j next j int Index KMP string S string T int next int i j i 0 j 1 这里的串的第 1 个元素下标是 1 while i S length 匹配成功 else return 0 void main string s t int next MAXSIZE init init printf please input string s input printf please input string t input get next t next int k Index KMP s t next if k 0 printf string t is not in string s n else printf string t is in string s d n k 实验结果 实验心得 实验中程序一为朴素模式匹配算法 程序二为快速模式匹配算法 两者都使用 了指针变量以及数组变量 利用字符串方式实现功能 朴素模式匹配算法和快速模式匹配 算法各有自己的特点 在本次实验中充分体现里两者不同之处 通过本次实验较好的掌握 了两种匹配算法的方法 加深了数组变量的应用 实验五 特殊矩阵 实验名称 实验五 特殊矩阵 实验目的 掌握特殊矩阵存储结构的描述 学会针对特殊矩阵的基本操作 实验原理 C 语言结构化程序设计思想 结构体及数组的应用 实验设备 电脑 TURBO C2 0 WIN TC VISUAL C 实验内容 1 稀疏矩阵的存储及转置运算 实验代码 稀疏矩阵的三元组顺序表存储表示及其转置算法 cpp include define ERROR 0 define OK 1 typedef int status typedef int ElemType 稀疏矩阵的三元组顺序表存储表示 define MAXSIZE 100 非零元个数最大为 100 typedef struct int i j 非零元的行下标和列下标 ElemType e 非零元 Triple typedef struct Triple data MAXSIZE 1 非零元三元组表 data 0 不用 int mu nu tu 矩阵的总行数 总列数 非零元总个数 TSMatrix status CreateTriplTable TSMatrix printf 请输入稀疏矩阵行数 列数 非零元个数 scanf d d d if M tuMAXSIZE return ERROR printf 行 列 非零元 n for k 1 k M tu k scanf d d d return OK void OutputTripleTable TSMatrix M 输出三元组表 int k printf 行数 列数 非零元个数 printf d d d n M mu M nu M tu printf 行 列 非零元 n for k 1 k M tu k printf 2d 3d 5d n M data k i M data k j M data k e void outputMatrix TSMatrix M 将三元组表 M 转换为对应的 mu nu 阶稀疏矩阵并输出 int i j k 1 printf 三元组表对应的稀疏矩阵 n for i 0 i M mu i for j 0 j M nu j if i M data k i 1 k else printf 5d 0 printf n status TransposeSMatrix TSMatrix M TSMatrix T mu M nu T nu M mu T tu M tu if T tu q 1 首先置目标结点 即 T 的序号为 1 即 q 1 for col 1 col M nu col 按 M 的列序 col 转置 col 从 1 至 M 的列数 M tu for p 1 p M tu p 每次对 M 的结点进行扫描 p 从 1 至 M 的非零元个数 M tu if M data p j col 若在 M 中找到 M data p j col 的结点 p T data q i M data p j 则将 M 中序号为 p 的结点赋给 T 中序号为 q 的结点 T data q j M data p i T data q e M data p e q 且将目标结点 q 往下移即 q return OK define MAXCOL 50 status FastTransposeSMatrix TSMatrix M TSMatrix T mu M nu T nu M mu T tu M tu if T tu for col 1 col M nu col num col 0 for t 1 t M tu t num M data t j 求 M 中每一列含非零元个数 cpot 1 1 求第 col 列中第一个非零元在 T data 中的序号 for col 2 col M nu col 后一列第一个非零元在 T data 中的序号等于 cpot col cpot col 1 num col 1 前一列的序号 前一列非零元个数 for p 1 p M tu p col M data p j M 中第 p 行的列号域值赋给 col q cpot col M 中的第 col 列非零元在 T data 中的恰当位置赋给 q T data q i M data p j M 中的第 p 行复制到 T 中的第 q 行 T data q j M data p i T data q e M data p e cpot col M 中第 col 列下一个非零元在 T data 中的位置应增 1 return OK void main TSMatrix a b CreateTriplTable a outputMatrix a TransposeSMatrix a b printf 转置矩阵 OutputTripleTable b outputMatrix b FastTransposeSMatrix a b printf 快速 转置矩阵 OutputTripleTable b 实验结果 实验心得 熟悉了特殊矩阵存储结构的描述 掌握了针对特殊矩阵的基本操作 对计算机 的操作更加熟练 加强了自己的实践动手能力 所有理论都必须经过实验的论 证来检验它的正确性 实验六 内排序 实验名称 实验六 内排序 实验目的 通过本次实验 掌握线性表的排序方法 并分析时间复杂度 实验原理 C 语言结构化程序设计思想 数组的应用 实验设备 电脑 TURBO C2 0 WIN TC VISUAL C 实验内容 1 将快速排序算法写成完整的程序上机通过 并统计递归深度 实验代码 include typedef int node node afile 20 node x int d dl n int l r i j void q int l int r int p d if dl d dl d printf dl d dl printf d d n d if lx if i j afile i afile j while afile i i i if i j afile j afile i afile i x for p 1 p n p printf d afile p printf n q l i 1 q i 1 r d printf d n d void main int p printf nPlease inputn n scanf d printf Please input astring for p 1 p n p scanf d d 0 dl 0 l 1 r n q l r for p 1 pdata ch T lchild Create T lchild T rchild Create T rchild return T void Preorder BiTree T if T printf c T data Preorder T lchild Preorder T rchild int Sumleaf BiTree T int sum 0 m n if T if T lchild m Sumleaf T lchild sum m n Sumleaf T rchild sum n return sum void zhongxu BiTree T if T zhongxu T lchild printf c T data zhongxu T rchild void houxu BiTree T if T houxu T lchild houxu T rchild printf c T data int Depth BiTree T int dep 0 depl depr if T dep 0 else depl Depth T lchild depr Depth T rchild dep 1 depl depr depl depr return dep main BiTree T int sum dep T Create T Preorder T printf n zhongxu T printf n houxu T printf n sum Sumleaf T printf d sum dep Depth T printf n d dep 实验结果 实验心得 了解了树与二叉树的建立 三种遍历方法及用广义表进行输入与输出 进一步 了解树的结构及非线性特点 递归特点和动态性 了解了树与二叉树与线性表的区别 实验八 图的遍历 实验名称 实验八 图的遍历 实验目的 熟悉图的存储结构 掌握有关算法的实现 了解图在计算机科学及其他工程技 术中的应用 实验原理 C 语言结构化程序设计思想 图的应用 实验设备 电脑 TURBO C2 0 WIN TC VISUAL C 实验内容 1 给定一个图 设计一个程序 找出一条从某一顶点 A 到另一顶点 B 边数 最少的一条路径 实验代码 include int number typedef struct int q 20 int f r queue int nodelist 20 20 queue Q int z 20 int a b n i j x y int finished void enq queue Q int x Q q Q r x if Q r 19 Q r 0 else Q r if Q r Q f printf Overflow n front queue Q if Q r Q f printf Underflow n else return Q q Q f void deq queue Q if Q r Q f printf Underflow n else if Q f 19 Q f 0 else Q f int qempty queue Q if Q f Q r return 1 else return 0 void readgraph printf nPlease input n scanf d printf Please input nodelist i j n for i 1