devbox
2023面试高手
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

通过代码快速上手C语言数据结构-数组和广义表_广义表数据结构代码

作者：2023面试高手 | 2024-06-05 06:03:36

赞

踩

广义表数据结构代码

5.1稀疏矩阵转置经典

5.2稀疏矩阵列序递增转置

  1.  
  2.  
  3. #include <malloc.h>
  4. #include <stdio.h>
  5. //#include "array.h"
  6. #define MAXSIZE 1000  /*非零元素的个数最多为1000*/
  7. #define ElementType int
  8. /*稀疏矩阵三元组表的类型定义*/	
  9.  
  10. #define MAXSIZE 1000  /*非零元素的个数最多为1000*/
  11. #define ElementType int
  12. /*稀疏矩阵三元组表的类型定义*/	
  13. typedef struct
  14. {   
  15. 	int row,col;  /*该非零元素的行下标和列下标*/
  16.     ElementType e; /*该非零元素的值*/
  17. }Triple;
  18.  
  19. typedef struct
  20. {  
  21. 	Triple data[MAXSIZE+1];   /* 非零元素的三元组表。data[0]未用*/
  22. 	int m,n,len;          /*矩阵的行数、列数和非零元素的个数*/
  23. }TSMatrix;
  24.  
  25. /*矩阵转置的经典算法*/
  26.  
  27. /*"列序"递增转置法*/
  28.  
  29. void TransposeTSMatrix(TSMatrix A,TSMatrix *B)
  30. { /*把矩阵A转置到B所指向的矩阵中去。矩阵用三元组表表示*/
  31. 	int i,j,k;
  32. 	B->m=A.n; 
  33. 	B->n=A.m; 
  34. 	B->len=A.len;
  35. 	if(B->len>0)
  36. 	{
  37. 		j=1;				/*j为辅助计数器，记录转置后的三元组在三元组表B中的下标值*/
  38. 		for(k=1; k<=A.n; k++) /*扫描三元组表A 共k次，每次寻找列值为k的三元组进行转置*/
  39. 			for(i=1; i<=A.len; i++)
  40. 				if(A.data[i].col==k)
  41. 				{
  42. 					B->data[j].row=A.data[i].col;/*从头至尾扫描三元组表A,寻找col值为k的三元组进行转置*/
  43. 					B->data[j].col=A.data[i].row;
  44. 					B->data[j].e=A.data[i].e;
  45. 					j++;		/*计数器j自加，指向下一个存放转置后三元组的下标*/
  46. 				}/*内循环中if的结束*/
  47. 	}/* if(B->len>0)的结束*/
  48. }/* end of TransposeTSMatrix */
  49.  
  50. /*"按位快速转置"法*/
  51.  
  52. void FastTransposeTSMatrix(TSMatrix A,TSMatrix *B)
  53. { 
  54. 	/*基于矩阵的三元组表示，采用"按位快速转置"法，将矩阵A转置为矩阵B*/
  55. 	int col,t,p,q;
  56. 	int num[MAXSIZE], position[MAXSIZE];
  57. 	B->len=A.len; 
  58. 	B->n=A.m; 
  59. 	B->m=A.n;
  60. 	if(B->len)
  61. 	{
  62. 		for(col=1;col<=A.n;col++)
  63. 			num[col]=0;  
  64. 		for(t=1;t<=A.len;t++)
  65. 			num[A.data[t].col]++; /*计算每一列的非零元素的个数*/	
  66. 		position[1]=1;
  67. 		for(col=2;col<=A.n;col++)  /*求col列中第一个非零元素在B.data[ ]中的正确位置*/
  68. 			position[col]=position[col-1]+num[col-1]; 
  69. 		for(p=1;p<=A.len;p++)/*将被转置矩阵的三元组表A从头至尾扫描一次，实现矩阵转置*/
  70. 		{  
  71. 			col=A.data[p].col;  
  72. 			q=position[col];
  73. 			B->data[q].row=A.data[p].col;
  74. 			B->data[q].col=A.data[p].row;
  75. 			B->data[q].e=A.data[p].e;
  76. 			position[col]++;/* position[col]加1，指向下一个列号为col的非零元素在三元组表B中的下标值*/
  77. 		}/*end of for*/
  78. 	}
  79. }
  80.  
  81.  
  82. #include <malloc.h>
  83. #include <stdio.h>
  84. //#include "array.h"
  85. #define MAXSIZE 1000  /*非零元素的个数最多为1000*/
  86. #define ElementType int
  87. /*稀疏矩阵三元组表的类型定义*/	
  88.  
  89.  
  90.  
  91. void main()
  92. {
  93. 	int i;
  94. 	int a[8]={1,1,3,3,4,5,6,6};
  95. 	int b[8]={2,3,1,6,3,2,1,4};
  96. 	int c[8]={12,9,-3,14,24,18,15,-7};	
  97. 	TSMatrix A;
  98. 	TSMatrix *B;
  99. 	A.n=8; 
  100. 	A.m=1; 
  101. 	A.len=8;
  102. 	B=(TSMatrix *)malloc(sizeof(TSMatrix));
  103. 	for(i=0;i<8;i++)
  104. 	{
  105. 		A.data[i+1].row=a[i];	
  106. 		A.data[i+1].col=b[i];
  107. 		A.data[i+1].e=c[i];
  108. 	}
  109. 	TransposeTSMatrix(A,B);	
  110. 	for(i=1;i<=8;i++)
  111. 	{
  112. 		printf("%3d",B->data[i].row);	
  113. 	}
  114. 	printf("\n");
  115. 	for(i=1;i<=8;i++)
  116. 	{	
  117. 		printf("%3d",B->data[i].col);
  118. 	}
  119. 	printf("\n");
  120. 	for(i=1;i<=8;i++)
  121. 	{
  122. 		printf("%3d",B->data[i].e);
  123. 	}
  124. 	printf("\n");
  125. 	getchar();
  126. }
  127.  
  128. void main()
  129. {
  130. 	int i;
  131. 	int a[8]={1,1,3,3,4,5,6,6};
  132. 	int b[8]={2,3,1,6,3,2,1,4};
  133. 	int c[8]={12,9,-3,14,24,18,15,-7};	
  134. 	TSMatrix A;
  135. 	TSMatrix *B;
  136. 	A.n=8; 
  137. 	A.m=1; 
  138. 	A.len=8;
  139. 	B=(TSMatrix *)malloc(sizeof(TSMatrix));
  140. 	for(i=0;i<8;i++)
  141. 	{
  142. 		A.data[i+1].row=a[i];	
  143. 		A.data[i+1].col=b[i];
  144. 		A.data[i+1].e=c[i];
  145. 	}
  146. 	TransposeTSMatrix(A,B);	
  147. 	for(i=1;i<=8;i++)
  148. 	{
  149. 		printf("%3d",B->data[i].row);	
  150. 	}
  151. 	printf("\n");
  152. 	for(i=1;i<=8;i++)
  153. 	{	
  154. 		printf("%3d",B->data[i].col);
  155. 	}
  156. 	printf("\n");
  157. 	for(i=1;i<=8;i++)
  158. 	{
  159. 		printf("%3d",B->data[i].e);
  160. 	}
  161. 	printf("\n");
  162. 	getchar();
  163. }

 

5.3稀疏矩阵—次定位快速转置

  1. #include <malloc.h>
  2. #include <stdio.h>
  3. //#include "array.h"
  4. #define MAXSIZE 1000  /*非零元素的个数最多为1000*/
  5. #define ElementType int
  6. /*稀疏矩阵三元组表的类型定义*/	
  7.  
  8. #define MAXSIZE 1000  /*非零元素的个数最多为1000*/
  9. #define ElementType int
  10. /*稀疏矩阵三元组表的类型定义*/	
  11. typedef struct
  12. {   
  13. 	int row,col;  /*该非零元素的行下标和列下标*/
  14.     ElementType e; /*该非零元素的值*/
  15. }Triple;
  16.  
  17. typedef struct
  18. {  
  19. 	Triple data[MAXSIZE+1];   /* 非零元素的三元组表。data[0]未用*/
  20. 	int m,n,len;          /*矩阵的行数、列数和非零元素的个数*/
  21. }TSMatrix;
  22.  
  23. /*矩阵转置的经典算法*/
  24.  
  25. /*"列序"递增转置法*/
  26.  
  27. void TransposeTSMatrix(TSMatrix A,TSMatrix *B)
  28. { /*把矩阵A转置到B所指向的矩阵中去。矩阵用三元组表表示*/
  29. 	int i,j,k;
  30. 	B->m=A.n; 
  31. 	B->n=A.m; 
  32. 	B->len=A.len;
  33. 	if(B->len>0)
  34. 	{
  35. 		j=1;				/*j为辅助计数器，记录转置后的三元组在三元组表B中的下标值*/
  36. 		for(k=1; k<=A.n; k++) /*扫描三元组表A 共k次，每次寻找列值为k的三元组进行转置*/
  37. 			for(i=1; i<=A.len; i++)
  38. 				if(A.data[i].col==k)
  39. 				{
  40. 					B->data[j].row=A.data[i].col;/*从头至尾扫描三元组表A,寻找col值为k的三元组进行转置*/
  41. 					B->data[j].col=A.data[i].row;
  42. 					B->data[j].e=A.data[i].e;
  43. 					j++;		/*计数器j自加，指向下一个存放转置后三元组的下标*/
  44. 				}/*内循环中if的结束*/
  45. 	}/* if(B->len>0)的结束*/
  46. }/* end of TransposeTSMatrix */
  47.  
  48. /*"按位快速转置"法*/
  49.  
  50. void FastTransposeTSMatrix(TSMatrix A,TSMatrix *B)
  51. { 
  52. 	/*基于矩阵的三元组表示，采用"按位快速转置"法，将矩阵A转置为矩阵B*/
  53. 	int col,t,p,q;
  54. 	int num[MAXSIZE], position[MAXSIZE];
  55. 	B->len=A.len; 
  56. 	B->n=A.m; 
  57. 	B->m=A.n;
  58. 	if(B->len)
  59. 	{
  60. 		for(col=1;col<=A.n;col++)
  61. 			num[col]=0;  
  62. 		for(t=1;t<=A.len;t++)
  63. 			num[A.data[t].col]++; /*计算每一列的非零元素的个数*/	
  64. 		position[1]=1;
  65. 		for(col=2;col<=A.n;col++)  /*求col列中第一个非零元素在B.data[ ]中的正确位置*/
  66. 			position[col]=position[col-1]+num[col-1]; 
  67. 		for(p=1;p<=A.len;p++)/*将被转置矩阵的三元组表A从头至尾扫描一次，实现矩阵转置*/
  68. 		{  
  69. 			col=A.data[p].col;  
  70. 			q=position[col];
  71. 			B->data[q].row=A.data[p].col;
  72. 			B->data[q].col=A.data[p].row;
  73. 			B->data[q].e=A.data[p].e;
  74. 			position[col]++;/* position[col]加1，指向下一个列号为col的非零元素在三元组表B中的下标值*/
  75. 		}/*end of for*/
  76. 	}
  77. }
  78.  
  79.  
  80. void main()
  81. {
  82. 	int i;
  83. 	int a[8]={1,1,3,3,4,5,6,6};
  84. 	int b[8]={2,3,1,6,3,2,1,4};
  85. 	int c[8]={12,9,-3,14,24,18,15,-7};	
  86. 	TSMatrix A;
  87. 	TSMatrix *B;
  88. 	A.n=8; 
  89. 	A.m=1; 
  90. 	A.len=8;
  91. 	B=(TSMatrix *)malloc(sizeof(TSMatrix));
  92. 	for(i=0;i<8;i++)
  93. 	{
  94. 		A.data[i+1].row=a[i];	
  95. 		A.data[i+1].col=b[i];
  96. 		A.data[i+1].e=c[i];
  97. 	}
  98. 	FastTransposeTSMatrix(A,B);	
  99. 	for(i=1;i<=8;i++)
  100. 	{
  101. 		printf("%3d",B->data[i].row);	
  102. 	}
  103. 	printf("\n");
  104. 	for(i=1;i<=8;i++)
  105. 	{	
  106. 		printf("%3d",B->data[i].col);
  107. 	}
  108. 	printf("\n");
  109. 	for(i=1;i<=8;i++)
  110. 	{
  111. 		printf("%3d",B->data[i].e);
  112. 	}
  113. 	getchar();
  114. }

 

5.4建立稀疏矩阵的十字链表

  1. /*建立稀疏矩阵的十字链表的算法*/
  2.  
  3. //#include "crosslistarray.h"
  4. #include <malloc.h>
  5. #include <stdio.h>
  6. #define NULL 0;
  7. /*十字链表的结构类型定义如下：*/
  8. typedef struct OLNode
  9. {	
  10. 	int row,col;        /*非零元素的行和列下标*/
  11. 	int value;
  12. 	struct OLNode *right;  /*非零元素所在行表、列表的后继链域*/
  13. 	struct OLNode *down; 
  14. }OLNode,* OLink;
  15.  
  16. typedef struct 
  17. {	
  18. 	OLink *row_head;  /*行、列链表的头指针向量*/
  19. 	OLink *col_head;
  20. 	int m,n,len;               /*稀疏矩阵的行数、列数、非零元素的个数*/
  21. }CrossList;
  22.  
  23.  
  24.  
  25. void CreateCrossList(CrossList *M)
  26. {
  27. 	int m,n,t;
  28. 	OLNode *p,*q;
  29. 	int i,j,e;
  30. 	/*采用十字链表存储结构，创建稀疏矩阵M*/
  31. 	printf("输入M的行数,列数和非零元素的个数\n");
  32. 	scanf("%d,%d,%d",&m,&n,&t);  /*输入M的行数,列数和非零元素的个数*/
  33. 	M->m=m;
  34. 	M->n=n;
  35. 	M->len=t;
  36. 	if(!(M->row_head=(OLink *)malloc((m+1)*sizeof(OLink)))) 
  37. 		printf("error");
  38. 	if(!(M->col_head=(OLink *)malloc((n+1)*sizeof(OLink)))) 
  39. 		printf("error");
  40. 	M->row_head=M->col_head=NULL;   /*初始化行、列头指针向量，各行、列链表为空的链表*/
  41.  
  42. 	printf("输入\n");
  43. 	for(scanf("%d,%d,%d",&i,&j,&e);i!=0;scanf("%d,%d,%d",&i,&j,&e))
  44. 	{
  45. 		if(!(p=(OLNode *)malloc(sizeof(OLNode)))) 
  46. 			printf("error");
  47. 		p->row=i;
  48. 		p->col=j;
  49. 		p->value=e;  /*生成结点*/
  50. 		if(M->row_head[i]==NULL)   
  51. 			M->row_head[i]=p;
  52. 		else
  53. 		{  
  54. 			/*寻找行表中的插入位置*/
  55. 			for(q=M->row_head[i];q->right&&q->right->col<j;q=q->right);  /*空循环体*/
  56. 			p->right=q->right; 
  57. 			q->right=p;  /*完成插入*/
  58. 		}
  59. 		if(M->col_head[j]==NULL)   
  60. 			M->col_head[j]=p;
  61. 		else
  62. 		{  
  63. 			/*寻找列表中的插入位置*/
  64. 			for(q=M->col_head[j];q->down&&q->down->row<i;q=q->down);  /*空循环体*/
  65. 			p->down=q->down; 
  66. 			q->down=p;   /*完成插入*/
  67. 		}
  68. 	}
  69. }
  70.  
  71. void main()
  72. {
  73. 	CrossList M;
  74.  
  75. 	CreateCrossList(&M);
  76. }

 

5.5求广义表的表头

  1. /*求广义表的表头*/
  2. GList Head(GList L)
  3. {
  4. 	if(L==NULL) 
  5. 		return(NULL);    /* 空表无表头 */
  6. 	if(L->tag==ATOM) 
  7. 		exit(0);    /* 原子不是表 */
  8. 	else 
  9. 		return(L->atom_htp.htp.hp);
  10. }

5.6求广义表的表尾

  1. /*求广义表的表尾*/
  2. GList Tail(GList L)
  3. {
  4. 	if(L==NULL) 
  5. 		return(NULL);    /* 空表无表尾 */
  6. 	if(L->tag==ATOM) 
  7. 		exit(0);    /* 原子不是表*/
  8. 	else 
  9. 		return(L->atom_htp.htp.tp);
  10. }

5.7求广义表的长度

  1. int Length(GList L)
  2. { 
  3. 	int n=0;
  4. 	GLNode *s;
  5. 	if(L==NULL) 
  6. 		return(0);    /* 空表长度为0 */
  7. 	if(L->tag==ATOM) 
  8. 		exit(0);    /* 原子不是表 */
  9. 	s=L;
  10. 	while(s!=NULL)    /* 统计最上层表的长度 */
  11.   	{ 
  12.   		k++;
  13. 		s=s->atom_htp.htp.tp;
  14. 	}
  15. 	return(k);
  16. }

5.8求广义表的深度

  1. int Depth(GList L)
  2. { 
  3. 	int d, max;
  4. 	GLNode *s;
  5. 	if(L==NULL) 
  6. 		return(1);    /* 空表深度为1 */
  7. 	if(L->tag==ATOM) 
  8. 		return(0);    /* 原子深度为0 */
  9. 	s=L;
  10. 	while(s!=NULL)    /* 求每个子表的深度的最大值 */
  11. 	{ 
  12. 		d=Depth(s->atom_htp.htp.hp);
  13. 		if(d>max) max=d;
  14.     		s=s->atom_htp.htp.tp;
  15.    	}
  16. 	return(max+1);    /* 表的深度等于最深子表的深度加1 */
  17. }

5.9-1统计广义表中原子数目方法

  1. int CountAtom(GList L)
  2. { /*求广义表L中原子结点数目，并返回原子结点数目值*/
  3. 	int n;
  4. 	GLNode *s;
  5. 	if(L==NULL) 
  6. 		return(0);    /* 空表中没有原子 */
  7. 	if(L->tag==ATOM) 
  8. 		return(1);    /* L指向单个原子 */
  9. 	s=L; 
  10. 	n=0;
  11. 	while(s!=NULL)    /* 求每个子表的原子数目之和 */
  12.   	{ 
  13.   		n=n+CountAtom(s->atom_htp.htp.hp);
  14. 		s=s->atom_htp.htp.tp;
  15. 	}
  16. 	return(n);
  17. }

5.9-2统计广义表中原子数目方法

  1. int CountAtom(GList L)
  2. { 
  3. 	int n1, n2;
  4. 	if(L==NULL) 
  5. 		return(0);    /* 空表中没有原子 */
  6. 	if(L->tag==ATOM) 
  7. 		return(1);    /* L指向单个原子 */
  8. 	n1=CountAtom(L->atom_htp.htp.hp);    /* 求表头中的原子数目 */
  9. 	n2=CountAtom(L->atom_htp.htp.tp);    /* 求表尾中的原子数目 */
  10. 	return(n1+n2);
  11. }

5.10复制广义表

  1. int CopyGList(GList S, GList *T)
  2. { 
  3. 	if(S==NULL) 
  4. 	{ 
  5. 		*T=NULL; 
  6. 		return(OK); 
  7. 	}    /* 复制空表 */
  8. 	*T=(GLNode *)malloc(sizeof(GLNode));
  9. 	if(*T==NULL) 
  10. 		return(ERROR);
  11. 	(*T)->tag=S->tag;
  12. 	if(S->tag==ATOM) 
  13. 		(*T)->atom=S->atom;    /* 复制单个原子 */
  14. 	else
  15. 	{
  16. 		CopyGList(S->atom_htp.htp.hp, &((*T)->atom_htp.htp.hp));    /* 复制表头 */
  17. 		CopyGList(S->atom_htp.htp.tp, &((*T)->atom_htp.htp.tp));    /* 复制表尾 */
  18.   	}
  19. 	return(OK);
  20. }

 5.5-5.10

  1.  
  2. //#include "seqstack.h"
  3. #define TRUE 1
  4. #define FALSE 0
  5. #define Stack_Size 50
  6.  
  7.  
  8. /*顺序栈-整型*/
  9. typedef struct
  10. {
  11. 	int elem[Stack_Size];  /*用来存放栈中元素的一维数组*/
  12. 	int  top;          /*用来存放栈顶元素的下标，top为-1表示栈是空栈*/
  13. }nStack;
  14.  
  15. /*初始化*/
  16. void  nInitStack(nStack *S)
  17. {
  18. /*构造一个空栈S*/
  19.   	S->top=-1;
  20. }
  21.  
  22. /*判栈空*/
  23. int nIsEmpty(nStack *S)	/*判断栈S为空栈时返回值为真，反之为假*/
  24. {
  25. 	return(S->top==-1?TRUE:FALSE);
  26. }
  27.  
  28. /*判栈满*/
  29. int nIsFull(nStack *S)	/*判断栈S为满栈时返回值为真，反之为假*/
  30. {
  31. 	return(S->top==Stack_Size-1?TRUE:FALSE);
  32. }
  33.  
  34. int nPush(nStack * S, int x)
  35. {
  36. 	if(S->top== Stack_Size-1)  return(FALSE);  /*栈已满*/
  37. 	S->top++;
  38. 	S->elem[S->top]=x;
  39. 	return(TRUE);
  40. }
  41.  
  42. int nPop(nStack * S, int *x)
  43. {  /* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */
  44. 	if(S->top==-1)  /*栈为空*/
  45. 		return(FALSE);
  46. 	else
  47. 	{
  48.   		*x= S->elem[S->top];
  49. 		S->top--;    /* 修改栈顶指针 */
  50.   		return(TRUE);
  51. 	}
  52. }
  53.  
  54. int nGetTop(nStack *S, int *x)
  55. {  /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */
  56. 	if(S->top==-1)  /*栈为空*/
  57. 		return(FALSE);
  58. 	else
  59. 	{
  60.   		*x = S->elem[S->top];
  61.   		return(TRUE);
  62. 	}
  63. }
  64.  
  65.  
  66. /*顺序栈-字符型*/
  67. typedef struct
  68. {
  69. 	char elem[Stack_Size];  /*用来存放栈中元素的一维数组*/
  70. 	int  top;          /*用来存放栈顶元素的下标，top为-1表示栈是空栈*/
  71. }strStack;
  72.  
  73. /*初始化*/
  74. void strInitStack(strStack *S)
  75. {
  76. /*构造一个空栈S*/
  77.   	S->top=-1;
  78. }
  79.  
  80. /*判栈空*/
  81. int strIsEmpty(strStack *S)	/*判断栈S为空栈时返回值为真，反之为假*/
  82. {
  83. 	return(S->top==-1?TRUE:FALSE);
  84. }
  85.  
  86. /*判栈满*/
  87. int strIsFull(strStack *S)	/*判断栈S为满栈时返回值为真，反之为假*/
  88. {
  89. 	return(S->top==Stack_Size-1?TRUE:FALSE);
  90. }
  91.  
  92. char strPush(strStack * S, char x)
  93. {
  94. 	if(S->top== Stack_Size-1)  return(FALSE);  /*栈已满*/
  95. 	S->top++;
  96. 	S->elem[S->top]=x;
  97. 	return(TRUE);
  98. }
  99.  
  100. char strPop(strStack * S, char *x)
  101. {  /* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */
  102. 	if(S->top==-1)  /*栈为空*/
  103. 		return(FALSE);
  104. 	else
  105. 	{
  106.   		*x= S->elem[S->top];
  107. 		S->top--;    /* 修改栈顶指针 */
  108.   		return(TRUE);
  109. 	}
  110. }
  111.  
  112. int strGetTop(strStack *S, char *x)
  113. {  /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */
  114. 	if(S->top==-1)  /*栈为空*/
  115. 		return(FALSE);
  116. 	else
  117. 	{
  118.   		*x = S->elem[S->top];
  119.   		return(TRUE);
  120. 	}
  121. }
  122.  
  123. /*功能函数*/
  124. int Match(char ch,char str)
  125. {		
  126. 	if(ch=='('&&str==')')
  127. 	{
  128. 		return TRUE;
  129. 	}
  130. 	else if(ch=='['&&str==']')
  131. 	{
  132. 		return TRUE;
  133. 	}
  134. 	else if(ch=='{'&&str=='}')
  135. 	{
  136. 		return TRUE;
  137. 	}
  138. 	else return FALSE;
  139. }
  140.  
  141. int In(char ch)
  142. {
  143. 	if(ch=='+')
  144. 	{
  145. 		return TRUE;	
  146. 	}
  147. 	else if(ch=='-') 
  148. 	{
  149. 		return TRUE;	
  150. 	}
  151. 	else if(ch=='*')
  152. 	{
  153. 		return TRUE;	
  154. 	}
  155. 	else if(ch=='/')
  156. 	{
  157. 		return TRUE;	
  158. 	}
  159. 	else if(ch=='(')
  160. 	{
  161. 		return TRUE;	
  162. 	}
  163. 	else if(ch==')')
  164. 	{
  165. 		return TRUE;	
  166. 	}
  167. 	else if(ch=='#')
  168. 	{
  169. 		return TRUE;	
  170. 	}
  171. 	else return FALSE;
  172. }
  173.  
  174. char Compare(char x,char ch)
  175. {
  176. 	switch(x)
  177. 	{
  178. 	case '+':
  179. 		if(ch=='+'||ch=='-'||ch==')'||ch=='#')
  180. 			return '>';	
  181. 		else if(ch=='*'||ch=='/'||ch=='(')
  182. 				return '<';	
  183. 		break;
  184. 	case '-':
  185. 		if(ch=='+'||ch=='-'||ch==')'||ch=='#')
  186. 			return '>';	
  187. 		else if(ch=='*'||ch=='/'||ch=='(')
  188. 			return '<';	
  189. 		break;
  190. 	case '*':
  191. 		if(ch=='(')
  192. 		{
  193. 			return '<';
  194. 		}
  195. 		else
  196. 		{
  197. 			return '>';
  198. 		}
  199. 		break;
  200. 	case '/':
  201. 		if(ch=='(')
  202. 				return '<';	
  203. 		else
  204. 				return '>';	
  205. 		break;
  206. 	case '(':
  207. 		if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='(')
  208. 			return '<';	
  209. 		else if(ch==')')
  210. 			return '=';	
  211. 		else if(ch=='#')
  212. 			return '0';	
  213. 		break;
  214. 	case ')':
  215. 		if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch==')'||ch=='#')
  216. 			return '>';	
  217. 		else if(ch=='(')
  218. 			return '0';	
  219. 		break;
  220. 	case '#':
  221. 		if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='(')
  222. 			return '<';	
  223. 		else if(ch=='#')
  224. 			return '=';	
  225. 		else if(ch==')')
  226. 			return '0';	
  227. 		break;	
  228. 	default:
  229. 		return '0';
  230. 		break;
  231. 	}
  232.  
  233. }	
  234.  
  235. int Execute(int a,char op,int b)
  236. {
  237. 	switch(op)
  238. 	{
  239. 	case '+':
  240. 		return (a+b);
  241. 		break;
  242. 	case '-':
  243. 		return (a-b);
  244. 		break;
  245. 	case '*':
  246. 		return (a*b);
  247. 		break;
  248. 	case '/':
  249. 		return (a/b);
  250. 		break;
  251. 	}
  252. }
  253. #include "stdio.h"
  254. #include <conio.h>
  255.  
  256.  
  257. /*求广义表的表头*/
  258. GList Head(GList L)
  259. {
  260. 	if(L==NULL) 
  261. 		return(NULL);    /* 空表无表头 */
  262. 	if(L->tag==ATOM) 
  263. 		exit(0);    /* 原子不是表 */
  264. 	else 
  265. 		return(L->atom_htp.htp.hp);
  266. }
  267.  
  268.  
  269. /*求广义表的表尾*/
  270. GList Tail(GList L)
  271. {
  272. 	if(L==NULL) 
  273. 		return(NULL);    /* 空表无表尾 */
  274. 	if(L->tag==ATOM) 
  275. 		exit(0);    /* 原子不是表*/
  276. 	else 
  277. 		return(L->atom_htp.htp.tp);
  278. }
  279.  
  280. int Length(GList L)
  281. { 
  282. 	int n=0;
  283. 	GLNode *s;
  284. 	if(L==NULL) 
  285. 		return(0);    /* 空表长度为0 */
  286. 	if(L->tag==ATOM) 
  287. 		exit(0);    /* 原子不是表 */
  288. 	s=L;
  289. 	while(s!=NULL)    /* 统计最上层表的长度 */
  290.   	{ 
  291.   		k++;
  292. 		s=s->atom_htp.htp.tp;
  293. 	}
  294. 	return(k);
  295. }
  296.  
  297. int Depth(GList L)
  298. { 
  299. 	int d, max;
  300. 	GLNode *s;
  301. 	if(L==NULL) 
  302. 		return(1);    /* 空表深度为1 */
  303. 	if(L->tag==ATOM) 
  304. 		return(0);    /* 原子深度为0 */
  305. 	s=L;
  306. 	while(s!=NULL)    /* 求每个子表的深度的最大值 */
  307. 	{ 
  308. 		d=Depth(s->atom_htp.htp.hp);
  309. 		if(d>max) max=d;
  310.     		s=s->atom_htp.htp.tp;
  311.    	}
  312. 	return(max+1);    /* 表的深度等于最深子表的深度加1 */
  313. }
  314.  
  315. int CountAtom(GList L)
  316. { /*求广义表L中原子结点数目，并返回原子结点数目值*/
  317. 	int n;
  318. 	GLNode *s;
  319. 	if(L==NULL) 
  320. 		return(0);    /* 空表中没有原子 */
  321. 	if(L->tag==ATOM) 
  322. 		return(1);    /* L指向单个原子 */
  323. 	s=L; 
  324. 	n=0;
  325. 	while(s!=NULL)    /* 求每个子表的原子数目之和 */
  326.   	{ 
  327.   		n=n+CountAtom(s->atom_htp.htp.hp);
  328. 		s=s->atom_htp.htp.tp;
  329. 	}
  330. 	return(n);
  331. }
  332.  
  333. int CountAtom(GList L)
  334. { 
  335. 	int n1, n2;
  336. 	if(L==NULL) 
  337. 		return(0);    /* 空表中没有原子 */
  338. 	if(L->tag==ATOM) 
  339. 		return(1);    /* L指向单个原子 */
  340. 	n1=CountAtom(L->atom_htp.htp.hp);    /* 求表头中的原子数目 */
  341. 	n2=CountAtom(L->atom_htp.htp.tp);    /* 求表尾中的原子数目 */
  342. 	return(n1+n2);
  343. }

马鞍点

  1. /*如果矩阵A中存在这样的一个元素A[i][j]满足条件:A[i][j]是第i行中值最小的元素,且又是第j列中值最大的
  2. 元素,则称之为该矩阵的一个马鞍点。编写一个函数计算出1×n的矩阵A的所有马鞍点。
  3. 算法思想：依题意,先求出每行的最小值元素,放入min[m]之中,再求出每列的最大值元素,放入max[n]之中,若某
  4. 元素既在min[i]中,又在max[j]中,则该元素A[i][j]便是马鞍点,找出所有这样的元素,即找到了所有马鞍点。因此,
  5. 实现本题功能的程序如下:*/
  6. #include <stdio.h>
  7. #define m 3
  8. #define n 3
  9.  
  10. void minmax(int a[m][n])
  11. {
  12. 	int i1,j,have=0;
  13. 	int min[m],max[n];
  14. 	for(i1=0;i1<m;i1++)/*计算出每行的最小值元素,放入min[m]之中*/
  15. 	{
  16. 		min[i1]=a[i1][0];
  17. 		for(j=1;j<n;j++)
  18. 			if(a[i1][j]<min[i1]) min[i1]=a[i1][j];
  19. 	}
  20. 	for(j=0;j<n;j++)/*计算出每列的最大值元素,放入max[n]之中*/
  21. 	{
  22. 		max[j]=a[0][j];
  23. 		for(i1=1;i1<m;i1++)
  24. 			if(a[i1][j]>max [j]) max[j]=a[i1][j];
  25. 	}
  26. 	for(i1=0;i1<m;i1++)
  27. 		for(j=0;j<n;j++)
  28. 			if(min[i1]==max[j])
  29. 			{
  30. 				printf("(%d,%d):%d\n",i1,j,a[i1][j]);
  31. 				have=1; 
  32. 			}
  33. 			if(!have) printf("没有鞍点＼n");
  34. } 
  35.  
  36. void main()
  37. {
  38. 	int a[m][n];
  39. 	int i,j; 
  40. 	printf("请输入一个数组\n"); 
  41. 	for(i=0;i<m;i++) 
  42. 		for(j=0;j<n;j++) 
  43. 			scanf("%d",&a[i][j]); 
  44. 	minmax(a);
  45. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/675133
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号