《数据结构》实验指导/实验五:数组的存储及操作 《数据结构》实验指导 实验五:数组的存储及操作 、实验目的 1、掌握数组的定义和存储结构 2、掌握特殊矩阵的压缩存储。 3、掌握稀疏矩阵的三元组顺序表存储及运算实现, 4、了解广义表的定义 实验学时 2学时 、实验类型 验证性实验 四、实验需求 1、硬件 每位学生配备计算机一台 2、软件 Windows XP/ Windows7操作系统;开发工具软件: Microsoft visual studio2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、稀疏矩阵的特点和基本运算 4、稀疏矩阵三元组顺序表存储及运算实现 六、实验任务 1、稀疏矩阵三元组顺序表抽象数据类型的代码实现 2、稀疏矩阵运算的代码实现 3、编写应用程序,用相关数据验证运算算法 管理科学与工程学科/共7页第1页
《数据结构》实验指导 / 实验五：数组的存储及操作 1 管理科学与工程学科 / 共7页,第1页 《数据结构》实验指导 实验五：数组的存储及操作 一、实验目的 1、 掌握数组的定义和存储结构。 2、 掌握特殊矩阵的压缩存储。 3、 掌握稀疏矩阵的三元组顺序表存储及运算实现。 4、 了解广义表的定义。 二、实验学时 2 学时 三、实验类型 验证性实验 四、实验需求 1、硬件 每位学生配备计算机一台； 2、软件 Windows XP/ Windows 7 操作系统；开发工具软件：Microsoft Visual Studio 2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、稀疏矩阵的特点和基本运算 4、稀疏矩阵三元组顺序表存储及运算实现 六、实验任务 1、稀疏矩阵三元组顺序表抽象数据类型的代码实现 2、稀疏矩阵运算的代码实现 3、编写应用程序，用相关数据验证运算算法
《数据结构》实验指导/实验五:数组的存储及操作 2 七、实验内容及步骤 1、任务一:代码实现稀疏矩阵三元组顺序表抽象数据类型:编写应用程序,用相关数据验证运 算算法 实验步骤 (1)启动 isual Studio2010,创建窗体应用程序。 (2)增加稀疏矩阵三元组顺序表类,代码参考如下: public struct TupNode ∥单个三元组的类型 public int r ∥行号 public int c, ∥0号 ∥元素值 public struct TSMatrix ∥三元组顺序表类型 public int rows, ∥行数 public int cols ∥列数 public int nums ∥零元素个数 public Tup] data public class SMatrixClass ∥稀疏矩阵三元组存储结构类 const int MaxSize =100 ∥三元组顺序表中最多元素个数 const int maXM=10 ∥稀疏矩阵最大行或列数 public int[ JA=new int[ MAXM, MAXM public int m; ∥稀疏矩阵的行数 public int n ∥稀疏矩阵的列数 public TSMatrix trip ∥稀疏矩阵对应的三元组顺序表 public SMatrix Class trip=new TSMatrixo trip data= new TupNode MaxSize public string Disp TSMatrixO ∥输出三元组表示 string my 管理科学与工程学科/共7页第2页
《数据结构》实验指导 / 实验五：数组的存储及操作 2 管理科学与工程学科 / 共7页,第2页 七、实验内容及步骤 1、任务一：代码实现稀疏矩阵三元组顺序表抽象数据类型；编写应用程序，用相关数据验证运 算算法。 实验步骤： （1） 启动 Visual Studio 2010，创建窗体应用程序。 （2） 增加稀疏矩阵三元组顺序表类，代码参考如下： public struct TupNode //单个三元组的类型 { public int r; //行号 public int c; //列号 public int d; //元素值 }; public struct TSMatrix //三元组顺序表类型 { public int rows; //行数 public int cols; //列数 public int nums; //非零元素个数 public TupNode[] data; } ; public class SMatrixClass //稀疏矩阵三元组存储结构类 { const int MaxSize = 100; //三元组顺序表中最多元素个数 const int MAXM = 10; //稀疏矩阵最大行或列数 public int[,] A = new int[MAXM, MAXM]; public int m; //稀疏矩阵的行数 public int n; //稀疏矩阵的列数 public TSMatrix trip; //稀疏矩阵对应的三元组顺序表 public SMatrixClass() { trip = new TSMatrix(); trip.data = new TupNode[MaxSize]; } public string DispTSMatrix() //输出三元组表示 { string mystr = ""; int i;
《数据结构》实验指导/实验五:数组的存储及操作 3 if( trip. nums=trip. rows j= trip. cols return false 下标错误时返回 false while(ktrip data(k] r) k++ ∥查找第i行的第一个非零元素 while(k trip. datal[k].c) k++ ∥在第i行中查找第j列的元素 if(trip data(k). r==i&& trip data[k].c==j ∥找到了这样的元素 trip data[k]. d ∥不存在这样的元素时插入一个元素 for(kl= trip. nums-1;k1>=k;k1-)∥后移元素以便插入 trip data[ kl +1]. r=trip data[ kl]r, trip data k1 +1.c= trip. datalklc 管理科学与工程学科/共7页第3页
《数据结构》实验指导 / 实验五：数组的存储及操作 3 管理科学与工程学科 / 共7页,第3页 if (trip.nums = trip.rows || j = trip.cols) return false; //下标错误时返回 false while (k trip.data[k].r) k++; //查找第 i 行的第一个非零元素 while (k trip.data[k].c) k++; //在第i行中查找第j列的元素 if (trip.data[k].r == i && trip.data[k].c == j) //找到了这样的元素 trip.data[k].d = x; else //不存在这样的元素时插入一个元素 { for (k1 = trip.nums - 1; k1 >= k; k1--) //后移元素以便插入 { trip.data[k1 + 1].r = trip.data[k1].r; trip.data[k1 + 1].c = trip.data[k1].c;
《数据结构》实验指导/实验五:数组的存储及操作 4 tr trip data[ k] r=I trip. datal k]. d ∥赋值成功时返回true public bool Get Value(int i, int j, ref int x) ink=0 if(1=trip. rows‖jtrip.cols) ∥下标错误时返回 while(k< trip. nums & trip data[ k]r<1) ∥查找第i行的第一个非零元素 while(k< trip. nums & trip data[k] r==i&& trip. datal[].c<j ∥在第ⅰ行中查找第j列的元素 f(trip. data(k).r=i&& trip. data(k]c=j)∥找到了这样的元素 x=trip data[ k].d; ∥在三元组中没有找到表示是零元素 ∥取值成功时返回true ---- (3)设计窗体,界面参考如下: 管理科学与工程学科/共7页第4页
《数据结构》实验指导 / 实验五：数组的存储及操作 4 管理科学与工程学科 / 共7页,第4页 trip.data[k1 + 1].d = trip.data[k1].d; } trip.data[k].r = i; trip.data[k].c = j; trip.data[k].d = x; trip.nums++; } return true; //赋值成功时返回 true } public bool GetValue(int i, int j, ref int x) { int k = 0; if (i = trip.rows || j = trip.cols) return false; //下标错误时返回 false while (k < trip.nums && trip.data[k].r < i) k++; //查找第 i 行的第一个非零元素 while (k < trip.nums && trip.data[k].r == i && trip.data[k].c < j) k++; //在第 i 行中查找第 j 列的元素 if (trip.data[k].r == i && trip.data[k].c == j) //找到了这样的元素 x = trip.data[k].d; else x = 0; //在三元组中没有找到表示是零元素 return true; //取值成功时返回 true } //-------------------------------------------------------- } （3） 设计窗体，界面参考如下：
《数据结构》实验指导/实验五:数组的存储及操作 5 操作步骤1一设置稀疏矩阵行数列数的信息 行数:6列数:7「设置稀碳矩阵行数 操作步骤2一元素赋值操作 赋值后的三元组表示如下: AL 2 2 0 元素赋值 3 d-123567 5 共有7个非零元素 操作步骤3-取元素值操作 x=A【5,5][取元素值 操作提示求得A[5,5]=7 (4)编写窗体中按钮等控件的代码,调用三元组顺序表类,参考如下 SMatrix Class tm=new SMatrixClassO private void button Click(object sender, EventArgs e) tm trip. rows=int Parse(text Boxl Text) trip private void button2 Click(object sender, EventArgs e) Int 1,1,X; j=Convert. Tolnt32(text Box4.Text) X=Convert. Tolnt32(text Box5. Text) 管理科学与工程学科/共7页第5页
《数据结构》实验指导 / 实验五：数组的存储及操作 5 管理科学与工程学科 / 共7页,第5页 （4） 编写窗体中按钮等控件的代码，调用三元组顺序表类，参考如下： SMatrixClass tm = new SMatrixClass(); private void button1_Click(object sender, EventArgs e) { tm.trip.rows = int.Parse(textBox1.Text); tm.trip.cols = int.Parse(textBox2.Text); } private void button2_Click(object sender, EventArgs e) { int i, j, x; try { i = Convert.ToInt32(textBox3.Text); j = Convert.ToInt32(textBox4.Text); x = Convert.ToInt32(textBox5.Text); }
《数据结构》实验指导/实验五:数组的存储及操作 6 infolabel.lext="操作提示:输入的行列号和元素值错误,请重新输入 if(tm Setvalue(i,j, x)) textBox6.Text=tm. DispTSMatrixO tm. TransArrayO ∥将三元组还原成稀疏矩阵 infolabel. Text="操作提示稀疏矩阵的三元组输出完毕 else infolabel, Text="操作提示:输入的行列号和元素值错误,请重新输入" return private void buttons Click(object sender, EventArgs e) 1= Convert. ToInt32(text Box7 Text); j=Convert. Tolnt32(text Box8 Text catch(Exception err) infolabel.lext="操作提示:输入的行号和列号错误请重新输入" if(tm Get Value(i, j,ref v)) nfolabel. Text="操作提示求得A"+i. ToString)+","+ jToString)+"]=”+ v ToString(; 管理科学与工程学科/共7页第6页
《数据结构》实验指导 / 实验五：数组的存储及操作 6 管理科学与工程学科 / 共7页,第6页 catch (Exception err) { infolabel.Text = "操作提示:输入的行列号和元素值错误,请重新输入"; return; } if (tm.Setvalue(i, j, x)) { textBox6.Text = tm.DispTSMatrix(); tm.TransArray(); //将三元组还原成稀疏矩阵 infolabel.Text = "操作提示:稀疏矩阵的三元组输出完毕"; } else { infolabel.Text = "操作提示:输入的行列号和元素值错误,请重新输入"; return; } } private void button3_Click(object sender, EventArgs e) { int i, j, v = 0; try { i = Convert.ToInt32(textBox7.Text); j = Convert.ToInt32(textBox8.Text); } catch (Exception err) { infolabel.Text = "操作提示:输入的行号和列号错误,请重新输入"; return; } if (tm.GetValue(i, j, ref v)) { textBox9.Text = v.ToString(); infolabel.Text = "操作提示:求得 A[" + i.ToString() + "," + j.ToString() + "]=" + v.ToString(); } else {
《数据结构》实验指导/实验五:数组的存储及操作 7 textBox. Text= nfolabel, Text="操作提示求得A["+i. ToString(+","+j. ToString0+"=0”; (5)使用下图稀疏矩阵调试运行程序,并观察运行情况。 0010000 0200000 3000000 0005000 0000600 0000074 (6)在三元组顺序表类中增加如下两个方法,编写方法代码: public void TransArrayO ∥将三元组顺序表还原成稀疏矩阵 blic string DispArrayO /输出稀疏矩阵 (7)在窗体中增加相应控件和代码,调用步骤(6)中的两个方法,调试运行并观察运行结果 八、实验分析 1、分析程序的运行过程,并将核心代码、错误提示及纠错内容记录至实验报告册 2、数组的存储和运算的代码实现 3、数据结构的应用特点。 九、课外自主实验 1、设计一个项目,用于上三角矩阵的压缩存储,并用相关数据进行测试。 2、设计通过三元组表示实现稀疏矩阵转置操作的算法,并用相关数据进行测试。 管理科学与工程学科/共7页第7页
《数据结构》实验指导 / 实验五：数组的存储及操作 7 管理科学与工程学科 / 共7页,第7页 textBox9.Text = ""; infolabel.Text = "操作提示:求得 A[" + i.ToString() + "," + j.ToString() + "]=0"; } } （5） 使用下图稀疏矩阵调试运行程序，并观察运行情况。 （6） 在三元组顺序表类中增加如下两个方法，编写方法代码： public void TransArray() //将三元组顺序表还原成稀疏矩阵 public string DispArray() //输出稀疏矩阵 （7）在窗体中增加相应控件和代码，调用步骤（6）中的两个方法，调试运行并观察运行结果。 八、实验分析 1、 分析程序的运行过程，并将核心代码、错误提示及纠错内容记录至实验报告册； 2、 数组的存储和运算的代码实现； 3、 数据结构的应用特点。 九、课外自主实验 1、设计一个项目，用于上三角矩阵的压缩存储，并用相关数据进行测试。 2、设计通过三元组表示实现稀疏矩阵转置操作的算法，并用相关数据进行测试
