稀疏矩阵十字链表的存储

电子信息学院 实验报告书 课 程 名 数据结构 题 目 稀疏矩阵十字链表的存储 实验类别 设计 班 级 BX1001 学 号 41 姓 名 赵艳 2011 年 10 月 24 日 算法设计与分析 实验报告 1 1 1 实验题目实验题目 1 掌握稀疏矩阵十字链表存储的方法 2 掌握稀疏矩阵的显示 查找等基本算法 2 2 实验内容实验内容 1 创建空的稀疏矩阵十字链表存储结构 2 稀疏矩阵十字链表的数据输入 3 稀疏矩阵十字链表的数据显示 4 稀疏矩阵十字链表的数据查找 3 3 实验要求实验要求 1 利用 C C 语言完成算法设计和程序设计 2 上机调试通过实验程序 3 输入右侧矩阵 A 检验程序运行结果 4 给出具体的算法分析 包括时间复杂度和空间复杂度等 5 撰写实验报告 4 4 实验步骤与源程序实验步骤与源程序 实验步骤 先定义各个需要的函数组成部分 然后依次构建四个子函数 分别是新建十字链表 显示 十字链表 输入链表元素 查找链表元素 然后是通过主函数对各个子函数的调用 来实现题 目的目的 整个程序中主要用到指针定位 for 循环 还有 switch 选择语句 其中对指针的运 用很难 很难定位指针 而且指针太多 繁杂 源代码 include include include include struct linknode int rows cols linknode down right union vnext 算法设计与分析 实验报告 2 int v linknode next node linknode CreateMatlind linknode InputMatlind linknode int void ShowMatlind linknode void SearchMatlind linknode hm int s linknode CreateMatlind int i j maxlin linknode hm cp 100 p printf n t t 请输入稀疏矩阵的行数 列数 用逗号隔开 scanf d d if i j maxlin i else maxlin j hm new linknode cp 0 hm for int l 1 lrows 0 p cols 0 p down p p right p cp l p cp l 1 node next p 算法设计与分析 实验报告 3 cp maxlin node next hm hm new linknode hm rows i hm cols j return hm linknode InputMatlind linknode hm int s linknode cp 100 p q int m n t int i j k maxlin i hm rows j hm cols if i j maxlin i else maxlin j cp 0 hm for int l 1 lrows 0 p cols 0 p down p p right p cp l p cp l 1 node next p cp maxlin node next hm 算法设计与分析 实验报告 4 for int x 0 xrows m p cols n p node v t k 1 q cp m while k if q right cp m q right cols n p right q right q right p k 0 else if q right cols n p right q right right q right p k 0 else if q right colsright k 1 k 1 算法设计与分析 实验报告 5 q cp n while k if q down cp n q down rows m p down q down q down p k 0 else if q down rows m p down q down down q down p k 0 else if q down rowsdown k 1 return hm void ShowMatlind linknode hm int m n linknode p q m hm rows n hm cols q p hm node next 算法设计与分析 实验报告 6 p p right cout endl endl printf n t t for int i 1 i m i for int j 1 jrows i else printf 8c 0 if j n else if p right q p p right printf n n t t p q q p p node next p p right void SearchMatlind linknode hm int s int m n k linknode p q m hm rows n hm cols q p hm node next p p right 算法设计与分析 实验报告 7 k 1 while k if p node v s printf n t t 行 列 值 n printf n t t 元素位置 第 2d 行第 2d 列 2d n p rows p cols p node v k 0 else if p right q p p right else p q q p p node next if p hm printf n t t 十字链表中无此元素 n k 0 p p right void main int s k ch 1 int choice linknode hm NULL while ch 算法设计与分析 实验报告 8 printf n printf n t t 稀疏矩阵的十字链表存储系统 n printf n t t printf n t t 1 新建十字链表 printf n t t 2 显示十字链表 printf n t t 3 查 找 元 素 printf n t t 0 退 出 printf n t t printf n n t t 请输入菜单号 scanf d switch choice case 1 hm CreateMatlind do printf n t t 请输入稀疏矩阵的非零元素个数 scanf d if s hm rows hm cols printf n t t 元素个数错误 应小于或等于 d 个 n hm rows hm cols k 1 else k 0 while k hm InputMatlind hm s break case 2 if hm NULL 算法设计与分析 实验报告 9 printf n t t 链表为空 n break else ShowMatlind hm break case 3 if hm NULL printf n t t 链表为空 n break else printf n t t 请输入您要查找的元素 scanf d SearchMatlind hm s break case 0 ch 0 break if choice 1 choice 2 choice 3 printf n t t system pause system cls 算法设计与分析 实验报告 10 5 5 测试数据与实验结果 可以抓图粘贴 测试数据与实验结果 可以抓图粘贴 算法设计与分析 实验报告 11 6 结果分析与实验体会 本次试验是稀疏矩阵十字链表的存储 通过这个实验 我们可以更好的掌握稀 疏矩阵十字链表存储的方法 以及稀疏矩阵的显示 查找等一些基本算法 在实验 中我们先定义对要定义的子函数进行声明 后建立新的存储结构 再后定义不同的 子函数来实现稀疏矩阵十字链表的建立 显示 输入数据