1.课程设计的目的
(1) 熟练使用 C ++语言编写程序，解决实际问题;
(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和
设计能力;
(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试
等基本方法和技能;
(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能
力;
2.需求分析
问题描述：对于特殊矩阵可以通过压缩存储减少存储空间。
基本要求：
1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值。
2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值。
特殊矩阵：具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。最常见的特殊矩阵有对称矩阵、上(下)三角矩阵、对角矩阵等。
特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的
分布规律，把那些呈现规律性分布的值相同的多个矩阵元素压缩存储到一个存储空间中。
3.矩阵的压缩与解压缩问题的设计
图1-1
4.调试分析
图1-2程序运行界面
图1-3 程序运行界面
5.小结
经过矩阵的压缩与解压缩的实验，让我了解到计算机是怎么为了减少承储空间的，存储矩阵的。以及特殊矩阵式在计算机中存储，以及把这些矩阵的压缩后怎么解压出来，恢复原来的样子！我觉得像这样的课程设计，一定要先想好有哪些板块，以及那些板块之间的关系这么样！谁调谁！
6、参考文献
[1] 严蔚敏，吴伟民编著. 数据结构(C 语言版)--北京: 清华大学出版社，2007.2
[2]严蔚敏，吴伟民米宁编著. 数据结构题集(C 语言版)--北京: 清华大学出版社，2007.3
[3]网上搜索相关程序作为参考
附录：
#include
#include
using namespace std;
int SymmetricMatrix()
{
int colm;//行
int row;//列
fstream file("SymmetricMatrix.txt");
ofstream fout("SymmetricMatrix1.txt");
file>>colm>>row;
int **matrix;
//bool flag=true;
matrix=new int *[colm];
for(int i=0;i { matrix[i]=new int[row]; } for (int i=0;i { for(int j=0;j { file>>matrix[i][j]; //cout< } } for (int i=0;i { for(int j=i;j { if(!(matrix[i][j]==matrix[j][i])) { cout<<"输入的不是对称矩阵"< return 0; } } } cout<<"对称矩阵如下"< for (int i=0;i { for(int j=0;j { //fin>>matrix[i][j]; cout< } cout< } int *array=new int[colm*(colm+1)/2]; int k=0; for (int i=0;i { for(int j=i;j { array[k]=matrix[i][j]; file<<3433; //file< cout< ++k; } } cout< return 0; } int UpperTriangularMatrix() { int colm;//行 int row;//列 fstream file("UpperTriangularMatrix.txt"); //ofstream fout("UpperTriangularMatrix.txt"); file>>colm>>row; int **matrix; //bool flag=true; matrix=new int *[colm]; for(int i=0;i { matrix[i]=new int[row]; } for (int i=0;i { for(int j=0;j { file>>matrix[i][j]; //cout< } } for (int i=0;i { for(int j=0;j { if(!(matrix[i][j]==0)) { cout<<"输入的不是上三角矩阵"< return 0; } } } cout<<"上三角矩阵如下"< for (int i=0;i { for(int j=0;j { //fin>>matrix[i][j]; cout< } cout< } int *array=new int[colm*(colm+1)/2]; int k=0; for (int i=0;i { for(int j=i;j { array[k]=matrix[i][j]; file<<3433; //file< cout< ++k; } } cout< return 0; } int LowerTriangularMatrix() { int colm;//行 int row;//列 fstream file("LowerTriangularMatrix.txt"); //ofstream fout("UpperTriangularMatrix.txt"); file>>colm>>row; int **matrix; //bool flag=true; matrix=new int *[colm]; for(int i=0;i { matrix[i]=new int[row]; } for (int i=0;i { for(int j=0;j { file>>matrix[i][j]; //cout< } } for (int i=0;i { for(int j=i+1;j { if(!(matrix[i][j]==0)) { cout<<"输入的不是下三角矩阵"< return 0; } } } cout<<"下三角矩阵如下"< for (int i=0;i { for(int j=0;j { //fin>>matrix[i][j]; cout< } cout< } int *array=new int[colm*(colm+1)/2]; int k=0; for (int i=0;i { for(int j=0;j<=i;j++) { array[k]=matrix[i][j]; //file<<3433; //file< cout< ++k; } } cout< return 0; } int SymmetricMatrixuncompress() { int colm;//行 int row;//列 fstream file("SymmetricMatrixuncompress.txt"); //ofstream fout("UpperTriangularMatrix.txt"); file>>colm>>row; int **matrix; //bool flag=true; matrix=new int *[colm]; for(int i=0;i { matrix[i]=new int[row]; } int *array=new int[colm*(colm+1)/2]; int k=0; for (int i=0;i { for(int j=0;j<=i;j++) { file>>matrix[i][j]; } } for (int i=0;i { for(int j=0;j<=i;j++) { matrix[j][i]=matrix[i][j]; } } cout<<"解压缩对称矩阵"< for (int i=0;i { for(int j=0;j { cout< } cout< } return 0; } int UpperTriangularMatrixuncompress() { int colm;//行 int row;//列 fstream file("UpperTriangularMatrixuncompress.txt"); //ofstream fout("UpperTriangularMatrix.txt"); file>>colm>>row; int **matrix; //bool flag=true; matrix=new int *[colm]; for(int i=0;i { matrix[i]=new int[row]; } int *array=new int[colm*(colm+1)/2]; int k=0; for (int i=0;i { for(int j=i;j { file>>matrix[i][j]; } } for (int i=0;i { for(int j=0;j<=i;j++) { matrix[i][j]=0; } } cout<<"解压缩上三角矩阵"< for (int i=0;i { for(int j=0;j { cout< } cout< } return 0; } int LowerTriangularMatrixuncompress() { int colm;//行 int row;//列 fstream file("LowerTriangularMatrixuncompress.txt"); //ofstream fout("UpperTriangularMatrix.txt"); file>>colm>>row; int **matrix; //bool flag=true; matrix=new int *[colm]; for(int i=0;i { matrix[i]=new int[row]; } int *array=new int[colm*(colm+1)/2]; int k=0; for (int i=0;i { for(int j=0;j<=i;j++) { file>>matrix[i][j]; } } for (int i=0;i { for(int j=i+1;j { matrix[i][j]=0; } } cout<<"解压缩上三角矩阵"< for (int i=0;i { for(int j=0;j { cout< } cout< } return 0; } int main() { char c; do { printf("\t 1.对称矩阵的压缩\n"); printf("\t 2.上三角矩阵的压缩\n"); printf("\t 3.下三角矩阵的压缩\n"); printf("\t 4.对称矩阵的解压缩\n"); printf("\t 5.上三角矩阵的解压缩\n"); printf("\t 6.下三角矩阵的解压缩\n"); printf("\t 7.!\n"); printf("Please Input choose (1-7):"); scanf("%s",&c); switch(c) { case '1': printf("\t 1.\n"); SymmetricMatrix(); break; case '2': printf("\t 2.");UpperTriangularMatrix(); break; case '3': printf("\t 3."); LowerTriangularMatrix(); break; case '4': printf("\t 4."); SymmetricMatrixuncompress(); break; case '5': printf("\t 5."); UpperTriangularMatrixuncompress(); break; case '6': printf("\t 6."); LowerTriangularMatrixuncompress(); break; case '7': exit(0); default : break; } }while(c!='4'); cin.get(); return 0;} 数据结构实验五矩阵的压缩存储与运算 第五章矩阵的压缩存储与运算 【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。 第一节知识准备 矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。 一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵 若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。 问题已经转化为：已知二维矩阵A[i，j]，如图5-1， 我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。 任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1 k= 0 1 2 3 …n(n- 1)/2 …n(n+1)/2-1 图5-2下三角矩阵的压缩存储 反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵 在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。 图5-3 三对角矩阵A 与下三角矩阵的存储一样，我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A，其对应关系见图5-4。 a00 a01 a10 a11 a12 … an-1,n-2 an-1,n-1 k= 0 1 2 3 4 … 3n-3 3n-2 图5-4下三角矩阵的压缩存储 A中的一对下标(i,j)与ma中的下标k之间有如下的关系： 公式中采用了C语言的符号，int()表示取整，‘%’表示求余。 课程设计 课程：数据结构 题目：稀疏矩阵4 三元组单链表结构体(行数、列数、头) 矩阵运算重载运算符优 班级： 姓名： 学号： 设计时间：2010年1月17日——2010年5月XX日 成绩： 指导教师：楼建华 一、题目 二、概要设计 1.存储结构 typedef struct{ int row,col;//行，列 datatype v;//非0数值 }Node; typedef struct{ Node data[max];//稀疏矩阵 int m,n,t;//m 行，n 列，t 非0数个数 … … 2.基本操作 ⑴istream& operator >>(istream& input,Matrix *A)//输入 ⑵ostream& operator <<(ostream& output,Matrix *A){//输出 ⑶Matrix operator ~(Matrix a,Matrix b)//转置 ⑷Matrix operator +(Matrix a,Matrix b)//加法 ⑸Matrix operator -(Matrix a,Matrix b)//减法 ⑹Matrix operator *(Matrix a,Matrix b)//乘法 ⑺Matrix operator !(Matrix a,Matrix b)//求逆 三、详细设计 （1）存储要点 position[col]=position[col-1]+num[col-1]; 三元组表(row ，col ，v) 稀疏矩阵（（行数m ，列数n ，非零元素个数t ），三元组，...，三元组） 1 2 3 4 max-1 《数据结构与算法设计》实验大纲及实验内 容详细要求 一、课程编号： 二、课程类型：必修 适用专业：通信工程 实验学时：32学时 三、本课程的地位、作用与任务 数据结构课程的目标是使学生掌握数据的基本的逻辑结构和存储结构、一些典型的数据结构算法及程序设计方法，要求学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，为数据选择适当的逻辑结构、存储结构以及相应的处理算法，要求具备算法分析的基本技术和能力，并培养良好的程序设计风格，掌握开发复杂、高效程序的技能。 在实验前要预习或者自行补充部分学时，同时进行部分代码准备，实验后要认真完成实验报告。 四、课程基本要求 1.学生应根据每个实验的任务和教师所提的要求，带C语言教材和课程教材。 2.完成指定的实验任务，保存源代码并输出、记录实验结果。 3.实验结束后按时提交实验报告，对于未完成部分，应该利用课余时间补充完成。 五、实验安排 本实验课程共32学时，五个实验(单元)，分16次实验，每次2学时。 实验一：C程序编程、调试实验 1、实验学时：4学时（学生堂下自行加4学时） 2、实验目的： 1)巩固复习前期所学C语言的基本数据类型和自定义数据类型等知识点，强化 学习数据结构语言和编程基础。 2)巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学 习数据结构语言基础。 3)能够较熟练调试程序 3、实验内容： 1)学生信息的显示。具体要求如下： ●定义一个结构体描述学生信息(学号，姓名，性别，年龄，住址)； ●设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构 体类型； ●设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数 进行显示（学生人数不少于5人）。 2)输入若干个整数存储到数组元素值，然后按输入顺序进行逆置存储，最后打 印出逆置后的元素值。要求用指针和动态内存分配方法实现。例如输入：1023045，逆置后显示为：5430210。 3)编写扑克牌发牌程序。在VC++的调试环境下观察数据存储位置、存储数据的 变化、数据之间的逻辑次序、物理存储位置次序。 4)对上述C程序进行调试，运行，从中理解数据和算法的概念，总结调试方法。 实验二：线性表的存储及基本操作、综合应用 1、实验学时：6学时 2、实验目的： 1)掌握线性表的逻辑特征 2)熟练掌握线性表的链式存储结构定义及基本操作 3)理解循环链表和双链表的特点和基本运算 4)加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实 际问题的编程能力。 5)掌握顺序表和链表的概念，学会对问题进行分析，选择恰当的逻辑结构和物理 结构 6)和实验一一起撰写一份实验报告，总结学习效果 3、实验内容： 使用顺序表和链表两种存储结构（linked list），存储输入的一组数据整数，能够进 特殊矩阵计算器 1、特殊矩阵计算器 问题描述：创建两个特殊矩阵 A 和 B，计算 A+B、A-B、A*B、B*A、A（或 B）的逆、A（或 B）的转置、A（或 B）的行列式等，具体要求如下：① A、B 均是压缩存储的特殊矩阵，如上/下三角矩阵、对称矩阵、对角矩阵、单位矩阵等。 ② A、B 的矩阵类型、行列数、各位置的元素值等信息均在运行时指定（对于不同类型的矩阵，要求输入的数据也不尽相同）。③各运算若可行，则打印结果；若不可行，则给出提示信息。④各运算需自己实现，禁止调用语言内建或第三方类库的矩阵 API。 涉及算法及知识：特殊矩阵的压缩存储、矩阵相关运算。 #include<> #include<> #define max 100 typedef struct{ int row,col;//定义矩阵行数、列数 int a[max][max]; }Matrix; //存储结构 typedef struct{ int array[max]; int n; //定义矩阵的阶 }M; Matrix A,B,C,D; M p; //*************矩阵的压缩存储*********************// int CompressMatrix(int m,int i,int j,int n){ int k; if(m==1){ if(i<=j) k=(2*n-i+1)*i/2+(j-i)+1; else k=0; return k; } if(m==2){ if(i>=j) k=i*(i+1)/2+j+1; else k=0; return k; } if(m==3){ if(i>=j) k=i*(i+1)/2+j; else k=j*(j+1)/2+i; return k; } if(m==4){ if(i!=j) k=0; else k=i+1; 常熟理工学院 《数据结构与算法》实验指导与报告书 _2017-2018_____学年第__1__ 学期 专业：物联网工程 实验名称：特殊矩阵和稀疏矩阵 实验地点： N6-210 指导教师：聂盼红 计算机科学与工程学院 2017 实验五特殊矩阵和稀疏矩阵 【实验目的】 1、掌握数组的结构类型（静态的内存空间配置）；通过数组的引用下标转换成该数据在内存中的地址； 2、掌握对称矩阵的压缩存储表示； 3、掌握稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。 【实验学时】 2学时 【实验预习】 回答以下问题： 1、什么是对称矩阵？写出对称矩阵压缩存储sa[k]与aij之间的对应关系。 若n阶矩阵A中的元素满足下述性质：a ij=a ji，则称为n阶对称矩阵。 sa[k]与矩阵元素a ij之间存在着一一对应的关系： 若i>=j，k=i*(i+1)/2+j; 若i 的关系。（注意C程序中，i，j，k均从0开始） （2）调试程序与运行。对称矩阵存储下三角部分即i>=j。 对称矩阵为3,9,1,4,7 9,5,2,5,8 1,2,5,2,4 4,5,2,1,7 7,8,4,7,9 参考程序如下： #include<> #define N 5 int main() { int upper[N][N]= {{3,9,1,4,7}, {9,5,2,5,8}, {1,2,5,2,4}, {4,5,2,1,7}, {7,8,4,7,9} }; /*对称矩阵*/ int rowMajor[15]; /*存储转换数据后以行为主的数组*/ int Index; /*数组的索引值*/ int i,j; printf("Two dimensional upper triangular array:\n"); for (i=0; i 禁止抄袭，否则一律不及格。机会仅有一次！！！！！ 《数据结构课程设计》 一、基本要求 （1）选择一个与线性表、堆栈和队列、数组、树、图、排序、查找等相关的专题，利用C语言或java来实现，解决具有一定规模的、具有实际意义的应用题目。 （2）论文内容主要包括封面、正文、参考文献等，其中正文内容主要引言、系统分析设计、系统实现和小结几部分组成。 （3）论文格式参考下面文档《模板》撰写课程报告。 （4）特别要求自己独立完成。 （5）第15周周一提交课程设计论文、电子版、源代码。 二、创新要求 在基本要求达到后，可进行创新设计，如改善算法性能、友好的人机界面。 可选题目列表： 1.运动会分数统计 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 功能要求： 1)可以输入各个项目的前三名或前五名的成绩； 2)能统计各学校总分， 3)可以按学校编号或名称、学校总分、男女团体总分排序输出； 4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 5)数据存入文件并能随时查询 6)规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有合理的提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指 稀疏矩阵 一、问题描述 假若在n m ?阶中，有t 个元素不为零，令n m t ?=δ称为矩阵的稀疏因子。通常认为≤δ0.05时称为稀疏矩阵。稀疏矩阵的研究大大的减少了数据在计算机中存储所需的空间，然而，它们的运算却与普通矩阵有所差异。通过本次实验实现稀疏矩阵的转置、加法和乘法等多种运算。 二、基本要求 1、稀疏矩阵采用三元组表示，建立稀疏矩阵，并能按矩阵和三元组方式输出; 2、编写算法，完成稀疏矩阵的转置操作； 3、编写算法，完成对两个具有相同行列数的稀疏矩阵进行求和操作； 4、编写算法，对前一矩阵行数与后一矩阵列数相等的两个矩阵,完成两个稀疏矩阵的相乘操作。 三、测试数据 1、转置操作的测试数据： ??????? ? ?00200013000010020100 2、相加操作的测试数据： ??????? ? ?002000130000100 20100 ??????? ??00200010000210030300 3、相乘操作的测试数据： ?????? ? ??000000030040 0021 ??????? ??001002000021 四、算法思想 1、三元组结构类型为Triple ，用i 表示元素的行，j 表示元素的列，e 表示元素值。稀疏矩阵的结构类型为TSMatrix ，用数组data[]表示三元组，mu 表示行数，nu 表示列数，tu 表示非零元个数。 2、稀疏矩阵转置的算法思想 将需要转置的矩阵a 所有元素存储在三元组表a.data 中，按照矩阵a 的列序来转置。 为了找到a的每一列中所有非零元素，需要对其三元组表a.data扫描一遍，由于a.data 是以a的行需序为主序来存放每个非零元的，由此得到的就是a的转置矩阵的三元组表，将其储存在b.data中。 3、稀疏矩阵相加的算法思想 比较满足条件(行数及列数都相同的两个矩阵)的两个稀疏矩阵中不为0的元素的行数及列数（即i与j），将i与j都相等的前后两个元素值e相加，保持i,j不变储存在新的三元组中，不等的则分别储存在此新三元组中。最后得到的这个新三元组表就是两个矩阵的和矩阵的三元组表。 4、稀疏矩阵相乘的算法思想 两个相乘的矩阵为M与N，对M中每个元素M.data[p](p=1,2,…,M.tu),找到N中所有满足条件M.data[p].j=N.data[q].i的元素N.data[q]，求得M.data[p].v和N.data[q].v 的乘积，又T(i,j)=∑M(i,k)×N(k,j),乘积矩阵T中每个元素的值是个累计和，这个乘积M.data[p].v×N.data[q].v只是T[i][j]中的一部分。为便于操作，应对每个元素设一累计和的变量，其初值是零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。由于T中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对T进行逐行处理，先求得累计求和的中间结果（T的一行），然后再压缩存储到Q.data中去。 五、模块划分 1、Status CreateM(TSMatrix *M, int a[],int row, int col)，创立三元组； 2、void PrintM(TSMatrix M)，按数组方式输出； 3、void PrintM3(TSMatrix M)，按三元组方式输出； 4、Status TransposeSMatrix(TSMatrix M, TSMatrix *T)，稀疏矩阵的转置； 5、Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)，稀疏矩阵加法； 6、Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)，稀疏矩阵相乘； 7、main(),主函数。 六、数据结构//(ADT) 1、三元组结构类型 typedef struct { int i,j; ElemType e; } Triple; 2、稀疏矩阵 typedef struct { Triple data[MAXSIZE+1]; 实验一~实验四任选一题；实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的： （1）熟练掌握线性表的两种存储方式 （2）掌握链表的操作和应用。 （3）掌握指针、结构体的应用 （4）按照不同的学校，不同项目和不同的名次要求，产生各学校的成绩单、团体总分报表。 二、实验内容： 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m＋1~m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n＝4，m＝3，w＝2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】 可以假设m≤20，m≤30，w≤20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。 【选作内容】 允许用户指定某些项目可采取其他名次取法。 实验二停车场管理 一、实验目的： （1）熟练掌握栈顺存和链存两种存储方式。 （2）掌握栈的基本操作及应用。 （3）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。 二、实验内容： 【问题描述】 设停车场是一个可停放n辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设n=2，输入数据为：(A，1，5)，（A，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。 【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 【选作内容】 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占地面积不同收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。 /* c1.h (程序名) */ #include 数据结构课后习题及解析第五章 第五章习题 5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为 1000，计算： 数组A共占用多少字节； 数组A的最后一个元素的地址； 按行存储时元素A 36 的地址； 按列存储时元素A 36 的地址； 5.2 设有三对角矩阵A n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= a ij ， 求： （1）用i,j表示k的下标变换公式； （2）用k表示i,j的下标变换公式。 5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放 结果矩阵。 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个 辅助向量空间。 5.5写一个在十字链表中删除非零元素a ij 的算法。 5.6画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 5.7求下列广义表运算的结果： （1）HEAD[((a,b),(c,d))]; （2）TAIL[((a,b),(c,d))]; （3）TAIL[HEAD[((a,b),(c,d))]]; （4）HEAD[TAIL[HEAD[((a,b),(c,d))]]]; （5）TAIL[HEAD[TAIL[((a,b),(c,d))]]]; 实习题 若矩阵A m×n 中的某个元素a ij 是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该 矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。 第五章答案 5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得B[k]=a ij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。 【解答】（1）k=2(i-1)+j (2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余） 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 【解答】算法（一） FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/ int col,t,p,q; int position[MAXSIZE]; B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { position[1]=1; for(t=1;t<=A.len;t++) position[A.data[t].col+1]++; /*position[col]存放第col-1列非零元素的个数, 即利用pos[col]来记录第col-1列中非零元素的个数*/ /*求col列中第一个非零元素在B.data[ ]的位置，存放在position[col]中*/ for(col=2;col<=A.n;col++) position[col]=position[col]+position[col-1]; for(p=1;p 压缩感知理论综述 摘要：信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来，指导信号采样的理论基础一直是著名的Nyquist采样定理，但其产生的大量数据造成了存储空间的浪费。压缩感知（Compressed Sensing）提出一种新的采样理论，它能够以远低于Nyquist采样速率采样信号。本文详述了压缩感知的基本理论，着重介绍了信号稀疏变换、观测矩阵设计和重构算法三个方面的最新进展，并介绍了压缩感知的应用及仿真，举例说明基于压缩感知理论的编解码理论在一维信号、二维图像处理上的应用。 关键词：压缩感知；稀疏表示；观测矩阵；编码；解码 一、引言 Nyquist采样定理指出，采样速率达到信号带宽的两倍以上时，才能由采样信号精确重建原始信号。可见，带宽是Nyquist采样定理对采样的本质要求。然而随着人们对信息需求量的增加，携带信息的信号带宽越来越宽，以此为基础的信号处理框架要求的采样速率和处理速度也越来越高。解决这些压力常见的方案是信号压缩。但是，信号压缩实际上是一种资源浪费，因为大量的不重要的或者只是冗余信息在压缩过程中被丢弃。从这个意义而言，我们得到以下结论：带宽不能本质地表达信号的信息，基于信号带宽的Nyquist采样机制是冗余的或者说是非信息的。 于是很自然地引出一个问题：能否利用其它变换空间描述信号，建立新的信号描述和处理的理论框架，使得在保证信息不损失的情况下，用远低于Nyquist 采样定理要求的速率采样信号，同时又可以完全恢复信号。与信号带宽相比，稀疏性能够直观地而且相对本质地表达信号的信息。事实上，稀疏性在现代信号处理领域起着至关重要的作用。近年来基于信号稀疏性提出一种称为压缩感知或压缩采样的新兴采样理论，成功实现了信号的同时采样与压缩。 简单地说，压缩感知理论指出：只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。在该理论框架 typedef int ElemType; // 稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE 100 // 非零元个数的最大值 typedef struct { int i,j; // 行下标,列下标 ElemType e; // 非零元素值 }Triple; typedef struct { Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用 int mu,nu,tu; // 矩阵的行数、列数和非零元个数 }TSMatrix; // 创建稀疏矩阵M int CreateSMatrix(TSMatrix *M) { int i,m,n; ElemType e; int k; printf("请输入矩阵的行数,列数,非零元素个数：（逗号）\n"); scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu); (*M).data[0].i=0; // 为以下比较顺序做准备 for(i = 1; i <= (*M).tu; i++) { do { printf("请按行序顺序输入第%d个非零元素所在的行(1～%d)," "列(1～%d),元素值：(逗号)\n", i,(*M).mu,(*M).nu); scanf("%d,%d,%d",&m,&n,&e); k=0; // 行或列超出范围 if(m < 1 || m > (*M).mu || n < 1 || n > (*M).nu) k=1; if(m < (*M).data[i-1].i || m == (*M).data[i-1].i && n <= (*M).data[i-1].j) // 行或列的顺序有错 k=1; }while(k); 数据结构实验课程大纲 本大纲是针对计算机科学与技术专业本科对数据结构的基本要求而编写的。 一、目的与任务 数据结构是一门实践性很强的课程，每个学生必须完成一定数量的上机作业。通过上机作业，要求在数据结构的逻辑特性和存贮表示、基本数据结构的选择和应用、算法设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法、程序设计风格及上机操作等基本技能和科学作风方面受到比较系统的、严格的训练。提高分析问题和用计算机解决实际问题的能力。为后续课程的学习以及为应用软件特别是非数值软件的开发打下良好的理论基础和实践基础。 二、课程内容 1.顺序表的表示和运算（0-2学时） 2.链表的表示和运算（2学时） 3.栈的应用（2-3学时） 4.队列的应用（2-3学时） 5.二叉树的基本操作和应用（2-6学时） 6.图及其应用（2-6学时） 7.排序（4-6学时） 8.查找（2-4学时） 三、基本要求 1.逐步理解和掌握程序设计和上机操作的基本方法和技能。 2.理解并实现各种基本数据结构的存贮表示、运算方法及其典型应用；学会根据实际问题的要求设计算法的 数据结构，并具有一定的比较和选用数据结构及算法的能力。 3.理解并实现常用的查找和排序的基本方法。 四、学时分配 五、实验内容 注：带*的内容以及练习与思考题，可根据实际学时、专业方向特点等具体要求，做相应调整或从略。 实验一、顺序表 实验目的： 熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。 实验要求： 了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。 实验内容： 编写程序实现下列的要求： (1) 设数据元素为整数，实现这样的线性表的顺序存储表示。 (2) 键盘输入10个数据元素，利用顺序表的基本操作，建立该表。 (3) 利用顺序表的基本操作，找出表中的最大的和最小的数据元素（用于比较的数据元素为整数）。 (4) * 若数据元素为学生成绩（含姓名、成绩等字段），重新编程，实现上面的要求。要求尽可能少地修改前面的程序来得到新程序。（这里用于比较的字段为分数） 练习及思考题： （1）不同类型的数据元素所对应的顺序表在类型定义和操作实现上有什么异同？ （2）顺序表的操作上有什么特点？ （3）不固定数据元素的个数，而通过特殊数据来标记输入数据的结束，实现这样的输入操作。 实验二、链表 实验目的： 熟悉链式表的逻辑特性、存储表示方法的特点和链式表的基本操作。 实验要求： 了解并熟悉链式表的逻辑特性、存储表示方法和链式表的基本操作的实现和应用。 实验内容： 编写程序实现下列的要求： (1) 设学生成绩表中的数据元素为学生成绩（含姓名、成绩字段），实现这样的线性表的链式存储表示。 (2) 键盘输入若干个数据元素（用特殊数据来标记输入数据的结束），利用链表的基本操作（前插或后插算法），建立学生成绩单链表。 (3) 键盘输入关键字值x，打印出表中所有关键字值<=x的结点数据。（用于比较的关键字字段为分数）。 (4) 输入关键字值x，删除表中所有关键字值<=x的结点。（用于比较的关键字字段为分数）。 (5) * 释放该链表（删除所有结点）。 (6) * 若要求建立的学生成绩单链表为有序表，重新编写算法和程序实现前面的要求（3）。（用于比较的字段为分数）。 练习及思考题： （1）不同类型的数据元素所对应的链式表在类型定义和操作实现上有什么异同？ （2）有头结点的链式表，有什么特点？ #include 压缩感知理论 一、压缩感知理论简介 压缩感知，又称压缩采样，压缩传感。它作为一个新的采样理论，它通过开发信号的稀疏特性，在远小于Nyquist 采样率的条件下，用随机采样获取信号的离散样本，然后通过非线性重建算法完美的重建信号。压缩感知理论一经提出，就引起学术界和工业界的广泛关注。它在信息论、图像处理、地球科学、光学、微波成像、模式识别、无线通信、大气、地质等领域受到高度关注，并被美国科技评论评为2007年度十大科技进展。 二、压缩感知产生背景 信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来，指导信号采样的理论基础一直是著名的Nyquist 采样定理。定理指出，只有当采样速率达到信号带宽的两倍以上时，才能由采样信号精确重建原始信号。可见，带宽是Nyquist 采样定理对采样的本质要求。但是，对于超宽带通信和信号处理、核磁共振成像、雷达遥感成像、传感器网络等实际应用，信号的带宽变得越来越大，人们对信号的采样速率、传输速度和存储空间的要求也变得越来越高。为了缓解对信号传输速度和存储空间的压力，当前常见的解决方案是信号压缩但是，信号压缩实际上是一种严重的资源浪费，因为大量采样数据在压缩过程中被丢弃了，它们对于信号来说是不重要的或者只是冗余信息。故而就有人研究如何很好地利用采集到的信号，压缩感知是由 E. J. Candes 、J. Romberg 、T. T ao 和D. L. Donoho 等科学家于2004 年提出，压缩感知方法抛弃了当前信号采样中的冗余信息。它直接从连续时间信号变换得到压缩样本，然后在数字信号处理中采用优化方法处理压缩样本。这里恢复信号所需的优化算法常常是一个已知信号稀疏的欠定线性逆问题。 三、压缩感知理论 压缩感知理论主要涉及到三个方面，即信号的稀疏表示、测量矩阵的设计和重构算法的构造。稀疏信号广义上可理解为信号中只有少数元素是非零的，或者信号在某一变换域内少数元素是非零的。那么在我们如果只保留这些非零数据，丢弃其他的系数，则可以减小储存该信号需要的空间，达到了压缩(有损压缩）的目的，同时，这些系数可以重构原始信号，不过一般而言得到的是X 的一个逼近。在实际生活中有很多数字信号都是稀疏信号或者在某一变换域内是稀疏的，这样压缩感知理论的第一个方面就可以得到满足。如果信号N x R ∈在某变换域内是稀疏的，可以用一组正交基12[,,,]N ψψψψ= 线性组合表示：1 N i i i x s s ψ===ψ∑，其中式中，是对应于正交基的投影系数。由稀疏性可知其内只含有少数不为零的数，感知信号y 可表示为：y x s s =Φ=Φψ=Θ，Φ就为测量矩阵，Ψ为稀疏表示矩阵，当测量矩阵与稀疏表示矩阵不相关时就可以从s 中不失真的恢复出原始信号x ，常用的测量矩阵有高斯随机阵等。接下来是算法的重构，由于用少数信号恢复原来的大信号，这是一个欠定问题，一般用最优化方法来求解。这就是压缩感知理论体系的基本理论。 四、对这一创新案例的分析 《数据结构与算法》课程实验内容与要求 一、课程简介 本课程着重讲述①线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应的基本算法。②各种查找算法③典型内部排序算法。 二、实验的作用、地位和目的 数据结构是一门技术基础课，通过实验深刻理解各种逻辑结构、存储结构的特性，培养为实际问题分析其数据对象、基本操作，选择逻辑结构、存储结构灵活应用基本算法，设计出具有专业水准的应用程序的能力。 三、实验方式与要求 ①首先要求学生在课下完成问题分析、算法设计，基本完成程序设计。 ②实验时，每位学生使用一台微机，独立调试，完成程序。 ③程序调试好后，由指导教师检测运行结果，并要求学生回答相关的问题。教师评出检查成绩。 ④学生记录程序的输入数据，运行结果及源程序。 ⑤在一周内完成实验报告。 四、考核方式与实验报告要求 实验成绩由指导教师根据学生的实验完成情况、源程序质量、回答问题情况、实验报告质量、实验纪律等方面给分。 学生在实验后的一周内提交实验报告。实验报告按照首页附件中实验报告模版书写。实验报告中应包括如下内容： ?实验内容按任课教师下达的实验任务填写（具体实验题目和要求）； ?实验过程与实验结果应包括如下主要内容： 算法设计思路简介 算法描述：可以用自然语言、伪代码或流程图等方式 算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等 ?源程序清单与实验结果或其它说明可打印，并装订在实验报告首页之后。 ?实验报告雷同者，本次实验成绩为0分或雷同实验报告平分得分 五、实验的软硬件环境 硬件环境：PⅡ以上微型计算机 软件环境：Windows98/2000, VC++6.0或turbo C 六、实验内容安排 实验一线性表应用 实验时间：2016年3月14日1-4节（地点：7-215） 实验目的：理解线性表的逻辑特点；掌握顺序表、链表存储结构，以及线性表的基本操作，如插入、删除、查找，以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法，并能够在实际问题背景下的灵活运用线性表来解决问题，实现相应算法。 具体实验题目与要求：（任课教师根据实验大纲自己指定） 每位同学可从下面题目中选择1-2题实现： 1．一元稀疏多项式简单的计算器 1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器 2）要求: （1）采用单链表存储结构一元稀疏多项式 （2）输入并建立多项式 （3）输出多项式 （4）实现多项式加、减运算 2．单链表基本操作练习 1）问题描述：在主程序中提供下列菜单： 1…建立链表 2…连接链表 3…输出链表 0…结束 2）实验要求：算法中包含下列过程，分别完成相应的功能： CreateLinklist(): 从键盘输入数据，创建单链表 ContLinklist()：将前面建立的两个单链表首尾相连 OutputLinklist()：输出显示单链表 3．约瑟夫环问题 1）问题描述：有编号为1, 2…n 的n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。 2）要求: 采用顺序和链式两种存储结构实现 实验报告格式及要求：按附件中实验报告模版书写。（具体要求见四）数据结构实验五矩阵的压缩存储与运算学习资料
数据结构稀疏矩阵基本运算实验报告
《数据结构与算法设计》实验大纲及实验内容详细要求
数据结构课程设计-特殊矩阵计算器
数据结构与算法 特殊矩阵和稀疏矩阵
《数据结构设计》内容要求要点
稀疏矩阵(算法与数据结构课程设计)
数据结构课程设计题目及要求
数据结构矩阵的转置
数据结构课后习题及解
压缩感知理论综述(原创)
数据结构C语言版-稀疏矩阵的三元组顺序表存储表示和实现
《数据结构》实验指导书
数据结构 稀疏矩阵相乘问题
压缩感知理论
《数据结构与算法》上机实验要求
相关主题
文本预览