数组和广义表学习

1、中南大学数据结构与算法数组与广义表学习报告学习报告数组与广义表学习报告a 数组1学习目标：进一步深刻的了解数组的定义与运算，对数组的顺序存储结构更深入的认知。也是对曾经学过的知识的进一步巩固。更重要的是学习特殊矩阵的压缩存储方法实现矩阵之间的加减运算，如三角矩阵，对称矩阵，以及稀疏矩阵的一些基本操作。2学习过程：数组是一种数据类型。从逻辑结构上看，数组可以看成是一般线性表的扩充。二维数组可以看成是线性表的线性表，应此可以利用线性表来存储多维数组。把多维数组尤其是二维数组转换为线性表尤为重要，二维数组可以作为一个矩阵看待我们还可以将数组am×n看成另外一个线性表:b=(b1，,b2,，

2、 ，bm)，其中bi（1i m）本身也是一个线性表，称为行向量，即： bi= （ai1，ai2， ，aij ，ain）。这样把二维数组转换为了一维数组就能很轻松的进行操作与运算了。数组的抽象数据类型定义（adt array）数据对象：d= aj1j2jn| n>0，称为数组的维数，ji是数组的第i维下标，1jibi，bi为数组第i维的长度， aj1j2jn elementset 基本操作：包括 initarray(), destoryarray(), getelement(), setelement() 1先实现了 一位动态数组的存储#include<iostream>usi

3、ng namespace std;void main()int *a ,n=10;int i;a=(int *)calloc(n,sizeof(int);for(i=0;i<n;i+)ai=i+1;for (i=0;i<n;i+)cout<<ai<<"t"free(a);通过实现了这个程序学到了更进一步的知道了如何动态申请内存空和释放动态深情的数组内存空间的calloc()函数，其函数原型为(void*)calloc(unsigned n ,sizeof(int)。知道了与malloc 函数的区别，更优于malloc；2实现二维动态数组的

4、存储与输出#include <stdlib.h>#include <iostream>using namespace std;int *creat(int row,int col)int *a,i;a=(int*)calloc(row,sizeof(int);for(i=0;i<row;i+)ai=(int*)calloc(col,sizeof(int);return (a);void destoyarray(int*a,int row)int i;for (i=0;i<row;i+) free(ai);free(a);void main()int i,j;

5、int row=3,col=4,*a;a=creat(row,col);int c=1;for (i=0;i<row;i+)for(j=0;j<col;j+)aij=c;c+;for(i=0;i<row;i+)for(j=0;j<col;j+)cout<<aij<<"t"cout<<endl; destoyarray(a,row);通过这个程序的实现后对二维数组的存储方法有了更深的理解和认识，更加深了对二维数组存储结构实现方法，同时也对数组的一些基本操作理解和应用。此程序主要运用双层循环实现对数组的输出格式的美观3

6、三阶对称矩阵的加法运算#include <iostream>using namespace std; void add(int a,int b,int c,int n) int i; for(i=0;i<=n*(n+1)/2-1;i+) ci=ai+bi; void print (int a,int n) int i,j,k; for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(i>=j) k=i*(i-1)/2+j-1; else k=j*(j-1)/2+i-1; cout<<ak<<"t"

7、 cout<<"n" void main () int n=3;int a6,b6,c6; cout<<"*"<<"n" cout<<"请输入你所求的两个对称矩阵，并按照先行后列的顺序"<<endl; for(int r=0;r<6;r+) cin>>ar; cout<<"请输入第二个" for(int s=0;s<6;s+) cin>>bs; add(a,b,c,n); print(c,

8、n); cout<<"*"<<endl; / int a=1,2,4,3,5,6 ,b=10,20,40,30,50,60,c6;这个程序虽然实现了，但是还有局限性，只能针对已经固定维数的矩阵的加法运算，在这个程序中运用了一个公式 k=i*(i-1)/2+j-1;(i>=j) k=j*(j-1)/2+i-1; (j<i)这个程序中输入的说明不太清除也是一个缺点4稀疏矩阵的输出与转置#include <iostream>using namespace std;const int maxsize=999;class matrixt

9、ypedef structint i,j, e;triple;triple datamaxsize;int m,n,t; public: matrix(int row,int col,int value); print();void transposs(matrix &tmatrix);void main()cout<<"*"<<endl;cout<<"请输入a矩阵的行数，列数和非零元的个数："<<endl;int row,col,value; /row，col，t分别用来表示行数列数和非零元的个数

10、cin>>row>>col>>value;matrix a(row,col,value); /创建三元组对象acout<<"*"<<endl;cout<<"a矩阵为:"<<endl;a.print(); /输出该矩阵cout<<"*"<<endl;cout<<"请再次"matrix b(row,col,value);cout<<"*"<<endl; co

11、ut<<"a的转置矩阵b为:"<<endl; a.transposs(b);b.print();cout<<"*"<<endl;matrix:matrix(int row,int col,int value) m=row;n=col;t=value;cout<<" 请输入数据为:"<<endl;for(int i=1 ;i<=t; i+)cin>>datai.i>>datai.j>>datai.e; matrix:prin

12、t() for(int i=1;i<=m;i+)for(int j=1; j<=n; j+) for(int k=1; k<=t; k+)if(i=datak.i && j=datak.j) cout<<datak.e<<" "break;if(k>t) cout<<0<<" "cout<<endl;void matrix:transposs(matrix &tmatrix) /矩阵的转置tmatrix.m=n;tmatrix.n=m;tmatri

13、x.t=t;if(tmatrix.t)int q=1; for(int col=1;col<=n;col+)for(int p=1; p<=t;p+)if(datap.j = col) tmatrix.dataq.i=datap.j; /对调i j 的值tmatrix.dataq.j=datap.i;tmatrix.dataq.e=datap.e;+q; 这个程序通过输入一组包含非0数的坐标与数值来进行一系列的操作但是这个程序中也有很多不足之处，例如要输入两次数值，暂时无法通过一次输入实现两种操作，即输出稀疏矩阵与输出转置后的矩阵3学习感受：通过自学习数组让我更加的了解到了学习方法

14、的重要性，认识到了作为一门动手为主的课程：数据结构中自己动手编程的重要性和自己实现程序的乐趣。在其中也不可避免的遇到很多错误，有语法上的，还有很多逻辑错误，不过通过查阅书籍和上网搜索都得到了解决。让我更加深了对自我学习的信心与认识。b广义表1学习目标：掌握广义表的类型定义广义表的存储表示和实现2 学习过程一般情况下，广义表写成 ls = ( a1,a2, . , an )其中：ai 或为原子或为广义表。 在线性表的定义中，只限于是单个元素。而在广义表的定义中，可以是单个元素，也可是广义表，分别称为广义表 ls 的原子和子表。 习惯上，用大写字母表示广义表的名称，用小写字母表示原子。 广义表是递

15、归定义的线性结构。 广义表的四个特点：1广义表中的数据元素有相对次序2广义表的长度为最外层包含的元素个数3广义表的深度为所含括弧的重数4广义表可以共享 广义表的基本操作1 initglist(&l);2 destroyglist(&l)3 createglist(&l, s)4 copyglist(&t, l)glistlength(l); glistdepth(l); glistempty(l); gethead(l); gettail(l)遍历 traverse_gl(l, visit() 操作结果：遍历广义表l，用函数visit处理每个元素 广义表的存储结点结构：typedef enum atom,list elemt