河南中医药大学：《数据结构》课程教学资源（实验指导）实验五 数组的存储及操作

《数据结构》实验指导/实验五:数组的存储及操作 《数据结构》实验指导 实验五:数组的存储及操作 、实验目的 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<=0) /没有非零元素时返回 mystr +=itj\td\r\n mystr += Arin' for(i=0; 1< trip mystr + trip data[i] rToString(+ "It"+ trip data[i]. cTo String +"It"+ rip data[i d ToString(+"rIn mystr+="共有”+ trip.nums, aStringe+"个非零元素"; return mysti public void TransArrayo ∥将三元组顺序表还原成稀疏矩阵 m=trip. rows for(i=0; i<m; 1++) for(=0; j<n;j++) A[j=0, for(k=0; k< trip. nums; k++) A[trip. data[ k] r, trip data( k). c]=trip. data( k].d; public bool Setvalue( int i, int j, int x) ∥通过三元组给稀疏矩阵元素赋值 ink=0.kI if (i<0 ll i >=trip. rows j<0 j>= trip. cols return false 下标错误时返回 false while(k< trip. nums && i>trip data(k] r) k++ ∥查找第i行的第一个非零元素 while(k< trip. nums &&i== trip data( k] r &&j> 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 <= 0) //没有非零元素时返回 return mystr; mystr += "i\tj\td\r\n"; mystr += "---------------------------------\r\n"; for (i = 0; i < trip.nums; i++) mystr += trip.data[i].r.ToString() + "\t" + trip.data[i].c.ToString() + "\t" + trip.data[i].d.ToString() + "\r\n"; mystr += "共有" + trip.nums.ToString() + "个非零元素"; return mystr; } public void TransArray() //将三元组顺序表还原成稀疏矩阵 { int i, j, k; m = trip.rows; n = trip.cols; for (i = 0; i < m; i++) for (j = 0; j < n; j++) A[i, j] = 0; for (k = 0; k < trip.nums; k++) A[trip.data[k].r, trip.data[k].c] = trip.data[k].d; } public bool Setvalue(int i, int j, int x) //通过三元组给稀疏矩阵元素赋值 { int k = 0, k1; if (i < 0 || i >= trip.rows || j < 0 || j >= trip.cols) return false; //下标错误时返回 false while (k < trip.nums && i > trip.data[k].r) k++; //查找第 i 行的第一个非零元素 while (k < trip.nums && i == trip.data[k].r && j > 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<o‖i>=trip. rows‖j<0‖j>trip.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 < 0 || i >= trip.rows || j < 0 || 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); }