data structure——数组、矩阵与广义表

数组：

1.两种逻辑结构

  • 一维数组
    dataType a[n];
  • 二维数组
    dataType a[m][n];
    元素为一维数组的数组

2.行优先和列优先储存
这里要区分数组在定义的时候例如：int a[2][3]中2和3就是又两行，有三列的意思，
而在说数组中的某一个元素是例如a[2][1]这里的2和1编号，是不一样的，因为编号是从0开始编号的。

矩阵:

1.概念
矩阵可以理解为二维数组。

2.操作

  • 矩阵转置

    1
    2
    3
    4
    5
    6
    7
    8
    void trsmat(int A[][maxsize],int B[][maxsize],int m, int n)  /*这里二维数组声明时省略了行的个数，
                                                                   但是列数是不可以省略的*/
    {
    	for(int i=0;i<m;i++)
    		for(int j=0;j<n;j++)
    			b[j][i]=A[i][j];
    }

  • 矩阵相加

    1
    2
    3
    4
    5
    6
    void addmat(int A[][maxsize],int B[][maxsize],C[][maxsize],int m ,int n)
    {
    	for (int i=0;i<m;i++)
    		for(int j=0;j<n;j++)
    			C[i][j]=A[i][j]+B[i][j];
    }

  • 矩阵相乘
    假设A[][]和B[][]分别为m*n，n*k。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void mutmat(int C[][maxsize],int B[][maxsize],int A[][maxsize],int m ,int n ,int k)
    {
    	for (int i=0;i<m;++i)
    		for(int j=0;j<k;++j)
    		{
    			C[0][0]=0;
    			for(h=0;h<n;++h)
    				C[i][j]+=A[i][h]*B[h][j];
    		}
    }


特殊矩阵和稀疏矩阵：

1.特殊矩阵

  • 对称矩阵

  • 三角阵
    只需要将那些相同的元素的值加在一维数组的后面一位就可以了。
  • 对角矩阵
    同上

2.稀疏矩阵

稀疏矩阵有两种表示方法：

  • 三元组表示法
    1
    2
    3
    4
    5
    6
    typedef struct
    {
    	int val;  //值
    	int i,j;  //行标和下标
    }Trimat;

    定义一个含有maxterm个元素的稀疏矩阵：
    Trimat trimat[maxterm];
    所以可以理解为，三元组表示法，是将稀疏矩阵以每个元素有三个分量的线性表形式将其进行存储。

当然，也可以这样存储：
int trimat[maxterms+1][3];
此时：
tirmat[k][0]表示原矩阵中的元素按行优先顺序的第k个元素的值
trimat[k][1]，tirmat[k][2]表示第k值在矩阵中的位置。
所以可以看出这是一个有maxterms行3列的数组，每行的第一列是值，第二列和第三列为这个元素的位置。
还有，我们默认的将第一行：
trimat[0][0]，trimat[0][1]，trimat[0][2]存储为非零元素的个数，矩阵行数，矩阵个数。

例题：
给定一个稀疏矩阵A（float型），其尺寸为m*n，建立其对应的三元组存储，并通过三元组打印输出矩阵A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void createtrimat(float A[][maxsize],int m ,int n, float B[][3]) //建立三元组
{
	int k=1;
	for(int i=0;i<m;++i)
		for(int j=0;j<n;++j)
			if(A[i][j]!=0)
			{
				B[k][0]=A[i][j];
				B[k][1]=i;
				B[k][2]=j;
				++k;
			}
		B[0][0]=k-1;
		B[0][1]=i;
		B[0][2]=j;
}
void print(float[][3])  //通过三元组打印矩阵A
{
	void k=1;
	for(int i=0;i<B[0][1];++i)
	{
		for(int j=0;j<B[0][2];++j)
		{
			if(i==(int)B[k][1]&&j==(int)B[k][2])
			{
				cout<<B[k][0]<<" ";
				++k;
			}
			else
				cout<<"0 ";
		}
		cout<<endl;
	}
}


  • 伪地址表示法

1.邻接表表示法

2.十字链表表示法

两种结点的结构定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct OLNode  //普通结点定义
{
	int row,col;
	struct OLNode *right ,*down;
	float val;
}OLNode;


typedef struct  //头结点定义
{
	OLNode *rhead,*chead;
	int m,n,k;  //矩阵的行数，列数，非零结点个数
}Crosslist;

例题：
给定一个稀疏矩阵A，其尺寸是m*n。非零元素个数是k，建立其对应的十字链表存储结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int creatcrossListmat(float A[][maxsize],int m,int n,int k,Crosslist &M)
{
	if(M.rhead)
		free(M.rhead);
	if(M.chead)
		free(M.chead);
	M.m=m;
	M.n=n;
	M.k=k;
	/*申请头结点数组空间*/
	if(!(M.rhead=(OLNode*)malloc(sizeof(OLNode)*m)))
		return 0;
	if(!M.chead=(OLNode*)malloc(sizeof(OLNode)*n))
		return 0;
	/*头结点数组right和down指针置空*/
	fot(int i=0;i<m;++i)
	{
		M.rhead[i].right=NULL;
		M.rhead[i].down=NULL;

	}
	for(j=0;j<n;++j)
	{
		M.chead[j].right=NULL;
		M.chead[j].down=NULL;
	}
	OLNode *temp_r[maxsize];  //建立列链表的辅助指针数组
	for(int j=0;j<n;++j)
		temp_r[j]=&(M.chead[j]);
	for(int i=0;i<m;++i)
	{
		OLNode *c=&(M.rhead[i]);
		for (int j=0;j<n;++j)
		{
			if(A[i][j]!=0)
			{
				OLNode *p=(OLNode*)malloc(sizeof(OLNode));
				p->row=i;
				p->col=j;
				p->val=A[i][j];
				p->down=NULL;
				p->right=NULL;
				c->right=p;
				c=p;
				temp_r[j]->down=p;
				temp_r[j]=p;
			}
		}
	}
	return 1;

}

广义表：

  • 广义表头尾链表存储结构

    A( )
    B(e)
    C(a,(b,c,d))
    D((),B,C)
    E(a,E)
    F(())
    其中有两种结点：原子结点，广义表结点。
    原子结点有两个域：标记域和数据域
    广义表结点有三个域：标记域，头指针和尾指针。
    当广义表非空时，第一个元素为广义表的表头，其余元素为广义表的表尾，这也是这个存储结构的名字的由来。

  • 广义表的扩展线性表存储结构

    其中也有两种结点：原子结点，广义表结点。
    不同的是：原子结点有三个域：标记域，头指针和尾指针。
    广义表结点有三个域：标记域，头指针和尾指针。

  • 特点
    广义表头尾链表存储结构类似于不带头结点的单链表存储结构，而广义表的扩展线性表存储结构类似于带头结点的单链表存储结构。

下面是例题：
1.设数组A[0,...,n-1]的n个元素中有多个零元素，设计一个算法，将A数组中的所有非零元素依次移动到A数组的前端。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void movelement(int A[],int n)  
{
	int i =-1,temp;  //i用来指最远离A[j]的为零的元素
	for(j=0,j<n;++j)
	{
		if(A[j]!=0)
		{
			++i;
			if(i!=j)
			{
				temp=A[i];  //用当前不是0的A[j]通过temp，
				A[i]=A[j];  //与最远离他的0元素进行交换
				A[j]=temp;
			}
		}
	}
}

2.关于浮点型数组A[0,...,n-1]，试设计一个实现下列运算的算法。
（1）求数组A中的最大值。
（2）求数组中n个数之和。
（3）求数组中n个数的平均值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
float findmax(float A[],int i ,int j)  //求最大值，递归
{
	float max;
	if(i=j)
		return A[i];
	else
	{
		max=findmax(A[],i+1,j);
		if(A[i]=max)
			return A[i];
		else
			return max；
	}
}

float arraysum(float A[],int i ,int j)  //求和
{
	if(i=j)
		return A[i];
	else
		return A[i]+arraysum(A[],i+1,j);
}

float arrayavg(float A[],int i,int j)  //求平均数
{
	if (i==j)
		return A[i];
	else
		return(A[i]+(j-i)*arrayavg(A,i+1,j))/(j-i+1);
}

3.设计一个算法，将数组A[0,...,n-1]中所有奇数移到偶数之前。要求不增加存储空间，且时间复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void divide(int A[],int n)
{
	int i=0,j=n-1,temp;
	while(i<j)
	{
		while(A[i]%2==1&&i<j)  //将i停在偶数上
			++i;
		while(A[i]%2==0&&i<j)  //将j停在奇数上
			--j;
		if(i<j)
		{
			temp=A[i];
			A[i]=A[j];
			A[j]=temp;
			++i;
			--j;
			
		}
	}
}


4.设有一元素为整数的线性表L，存放在一维数组A[0,...,n-1]中，设计一个算法，以A[n-1]为参考量，将该数组分为左右两个部分，其中左半部分的元素均小于等于A[n-1]，右半部分的元素值均大于A[n-1]，A[n-1]则位于这两个部分之间。要求结果仍存放在数组A中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void divide(int A[],int n)
{
	int temp;
	int  i=0;
	int j=n-1;
	temp=A[i];
	A[i]=A[j];
	A[j]=temp;
	temp=A[i];
	while(i!=j)
	{
		while (j>i&&A[j]>temp)
			--j;  //找到右边第一个小于temp的数
		if(i<j)
		{
			A[i]=A[j];
			++i;
		}
		while(i<j&&A[i]<temp)
			++i;  //找到左边第一个大于temp的数
		if(i<j)
		{
			A[j]=A[i];
			--j;
		}
		A[i]=temp；
	}
}

5.设计一个算法，对给定的一个整形m*n矩阵A,统计这个矩阵中具有下列特特征的元素并输出他们的坐标及数值：他们既是所在行中的最小值，又是所在列中的最小值：或者他们既是所在行中的最大值，又是所在列中的最大值。假设矩阵中元素各不相同，要求结果在处理过程中用输出语句输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
void printmin(int A[][maxsize],int m,int n)  //求最小，m是行号，n是列号
{
	int i,j,k,min,minj;  //minj是记录第i行上最小值的列号
	int flag;
	for(i=0;i<m;++i)
	{
		min=A[i][0];
		minj=0;
		for(j=1;j<n;++j)
		if (A[i][j]<min)  //找出第i行上的最小值，列号为minj
		{
			min=A[i][j];
			minj=j;
		}
		flag=1;
		for(k=0;k<m;++k)
		{
			if(min>A[k][minj])
			{
				flag=0;
				break;
			}
			
		}
		if(flag)
			cout<<min<<",["<<i<<","<<j<<",]"<<" ";
	}
	cou <<endl;
}

void printmax(int A[][maxsize],int m,int n)  //最大
{
	int i,j,k,max,maxj;
	int flag=0;
	for(i=0;i<m;++i)
	{
		max=A[i][0];
		maxj=0;
		for(j=1;j<n;++j)
		{
			if(A[i][j]>max)
			{
				max=A[i][j];
				maxj=j;
			}
			flag=1;
			for(k=0;k<m;++k)
			{
				if(max<A[i][maxj])
				{
					flag=0;
					break;
				}
			}
			if(flag)
				cout<<max<<",["<<i<<","<<maxj<<",]"<<" ";
		}
	}
	cout<<endl;
}

此题是一行一行的循环，首先是由第5行的循环，然后再通过第10行的循环，找出这一行中的最小值，然后，再在第16行的循环比较，这一行的这个最小值是不是又是他所在列的最小值，如果不是就将flag值为0，并退出，如果是，就以min,[i,minj]的格式将其输出。求最大的值的思路一样。

6.给定稀疏矩阵A（int型），创建其三元组存储结构B;查找给定元素x是否在矩阵中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void create(int A[][maxsize],int m,int n,int B[][3])
{
	int i,j,k=1;
	for(i=0;i<m;++i)
		for(j=0;j<n;++i)
			if(A[i][j]!=0)
			{
				B[k][0]=A[i][j];
				B[k][1]=i;
				B[k][2]=j;
				++k;
			}
	B[0][0]=k-1;
	B[0][1]=m;
	B[0][2]=n;
}

int search(int B[][3],int x)  //查找元素
{
	int i,t;
	t=B[0][0];
	i=1;
	while(i<=t&&B[i][0]!=x)
		i++;
	if(i<=t)  //这里有疑问
		return 1;
	else
		return 0;
}

7.假设稀疏矩阵A采用三元组表示，编写一个函数，计算其转置矩阵B,要求B也采用三元组表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void transpose(int A[][3],int B[][3])
{
	int p,q,col;
	B[0][0]=A[0][0];
	B[0][1]=A[0][2];
	B[0][2]=A[0][1];
	if(B[0][0]>0)
	{
		q=1;
		for(col=0;col<B[0][1];++col)
			for(p=1;p<=B[0][0];++p)
				if(A[p][2]==col)
				{
					B[q][0]=A[p][0];
					B[q][1]=A[p][2];
					B[q][2]=A[p][1];
					++q;
				}
	}
}

8.假设稀疏矩阵A和B（两矩阵行列数对应相等）都采用三元组表示，编写一个函数，计算C=A+B，要求C也采用三元组表示，所有矩阵均为int型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
void add(int A[][3],int B[][3],int C[][3])
 {
 	int i=1,j=1,k=1,m;
 	while(i<=A[0][0]&&j<=B[0][0])  
 	if(A[i][1]==B[i][1])  //如果a中的元素的行号等于b的元素的行号，说明，这两个元素在原来的稀疏矩阵中的同一行，
 	{
 		if (A[i][2]<B[i][2])      /*接着再比较这个元素的列号，若果a的列号小于b,那么就说明，
                                    a这个非零元素在稀疏矩阵中的位置，
                                    对应于b的这个相同行号的元素在其稀疏矩阵中的位置的那个元素是0*/
 		{
 			C[k][0]=A[i][0];  /*所以，a的元素加上0，就相当于将a当前的元素直接赋值给三元组c，下面的思路是一个意思*/
 			C[k][1]=A[i][1];
 			C[k][2]=A[i][2];
 			++k;
 			++i;
 		}
 		else if (A[i][2]>B[1][2])
 		{
 			C[k][0]=B[j][0];
 			C[k][1]=B[j][1];
 			C[k][2]=B[j][2];
 			++k;
 			++j;
 		}
 		else (A[i][2]==B[j][2])
 		{
 			m=A[i][0]+B[j][0];
 			if(m!=0)
 			{
 				C[k][0]=B[j][0];
 				C[k][1]=B[j][1];
 				C[k][2]=B[j][2];
 				++k;
 			}
 			++j;
 			++i;
 		}

 	}
 	else if(A[i][1]<B[j][1])  //如果a三元组的这个元素的行号小于b三元组的行号时
 	{
 		C[k][0]=A[i][0];
 		C[k][1]=A[i][1];
 		C[k][2]=A[i][2];
 		++k;
 		++i;
 	}
 	else(A[i][1]>B[j][1])
 	{
 		C[k][0]=B[j][0];
 		C[k][1]=B[j][1];
 		C[k][2]=B[j][2];
 		++k;
 		++i;
 	}
 	while(i<=A[0][0])  //如果a三元组中有多余的元素，将多余的元素直接赋值给c
 	{
 		C[k][0]=A[i][0];
 		C[k][1]=A[i][1];
 		C[k][2]=A[i][2];
 		++k;
 		++i;
 	} 
 	while (i<B[0][0])  //如果b三元组有多余
 	{
 		C[k][0]=B[j][0];
 		C[k][1]=B[j][1];
 		C[k][2]=B[j][2];
 		++k;
 		++j;
 	}
 	C[0][0]=k-1;
 	C[0][1]=A[0][1];
 	C[0][2]=A[0][2];
 }

由稀疏矩阵而来的三元组中，其实已经存储的是稀疏矩阵中非零的元素了，切记。

9.假设稀疏矩阵A,B（分别为m*n,n*k矩阵）采用三元组表示，编写一个函数计算C=A*B，要求C也是采用三元组表示的稀疏矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int getvalue(int D[][maxsize],int i,int j)  //返回三元组中的元素对应于他在稀疏矩阵中的值
{
	int k=1;
	while(k<=D[0][0] && (D[k][1]!=i||D[k][2]!=j))  //不相同的是0元素
		k++;  //所以就跳过
	if (k<=D[0][0])
		return D[k][0];
	else
		return 0;
}
void mul(int A[][3],int B[][3],int C[][3],int m,int n,int k)
{
	int i,j,l,p=1,s;
	for(i=0;i<m;++i)
		for(j=0;j<n;++j)
		{
			s=0;
			for(l=0;l<n;++l)  //主要是这个l要注意一下
				s+=getvalue(A,i,l)*getvalue(B,l,j);
			if(s!=0)
			{
				C[p][1]=i;
				C[p][2]=j;
				C[p][0]=s;
				++p;
			}
		}
		C[0][1]=m;
		C[0][2]=n;
		C[0][0]=p-1;
}

-..—.–..-.-./-.–..-..-.-..-/-.-.–.—…../-..—…—.-./–…-….-…-/-…-.——.-../-..—.-….–./-..—………/-.-..—–..-.-/-..-.-.-…–..-/-…-.—-.—.-/——–….–../-…-.—.-.-..-/-..—-.–…../–..—….-..-/—….-.—..-/-.—……—-/-..—…..–.-/-..–.-.–.–…/-.-…-.—.-../-..—.-….–./——–….–../-…——.–…/-..—………/-..—…-.-.-./-.-..-.-.–..-./—.–.-….-../-..—…..–.-/—.-…….–./–…-….-…-/——–….–../-….–..—–.-/—…-..–.–./–…-….-…-/—.——..-.-/-..-…..-.-..–/-.-..—–.-.-./–..–…-.—-/-..—-.–…../-.-.-..-…–../–…-….-…-/—.-.-…—–/—.–.-….-../-.—……—-/-..—…..–.-/-.—–……../-.——-….–/——–….–../-.-..—–.—-/–..–…-.—-/–..-.—–.–./-..-.-.—–.-../-..—………/-..-.-.-.——-/–…-….-…-/-…——.–…/–..–…-.—-/–..—….-..-/-..—………/—….-.—..-/-.—……—-/-.–..-..–…-/-….-….—-.-/-.-.-…–…-./–……….-./—..—.–…./-.-.—..-.-…/-..—-.–…../-.-.—..-.-…/-.-.–.——-./-..—..–..–./-..–..–….–./-..-…—..–../——–….–../-.-.—..-.-…/–…-….-…-/—.–.-….-../-.–.——-..-/-..-.—.–…-./—.—.–….-/—.—.-……/-..—.-….–./——–….–../–…-….-…-/–…-..-.-..–/-.—–……../-..-.——-..–/-..—..-.-…./——–….–../-.-..—-..-…/——.–.–..-/–…-….-…-/–…—.-.-…/-..-………..-/-..—.-….–./-..—………/-..—…-.-.-./-..—………/-..–..–..-.–./-.-..–.–….-/-.-…–..—../——–….–../-.——.-.—./-..–…–..—./-…—-.—-.–/–…-.–….-./—.—.-……/-..—-.–…../——–….–../–…-….-…-/—.—….-.–/—.—.-……/-..—-.–…../——–….–../-….–..—–.-/—…-..–.–./–.–..-.-….-/–..—….-..-/-.–..-..-.-.-./-..-.–…–..–/——–….–../-.-..–.—.-../-…——.–…/–..–…-.—-/-…-..—..-..-/—.–.-….-../-.-.-..-…–../-..—-.–…../-.-.—..-.-…/-..—………/-…–.-.—.—/—.—…—–/-.–..-.—–.-/–……….-.