数据结构-稀疏矩阵与广义表
稀疏矩阵
/*
设矩阵 A 中有 s 个非零元素，若 s 远远小于矩阵元素的总数，则称 A 为稀疏矩阵。
这里以一维数组顺序存放非零元素的行号、列号和数值，行号 -1 作为结束标志。
*/
#include<stdio.h>
#define m 6 //用户可根据需要定义原始矩阵行数
#define n 8 //定义原始矩阵列数
#define max 50
/*********************************************/
/* 转储稀疏矩阵的算法 */
/*********************************************/
void CreateMatrix(int A[m][n],int B[50])
{
int i,j,k=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(A[i][j]!=0)
{
B[k]=i;k++;
B[k]=j;k++;
B[k]=A[i][j];k++;
}
B[k]=-1; //非零元素存储的结束
}
/*********************************************/
/* 转储稀疏矩阵的算法 */
/*********************************************/
void MatrixAdd(int A[max],int B[max],int C[max])
{
int i=0,j=0,k=0;
while(A[i]!=-1 && B[j]!=-1)
{
if(A[i]==B[j]) //行相等
{
if(A[i+1]==B[j+1]) //且列相等
{
C[k]=A[i];
C[k+1]=A[i+1];
C[k+2]=A[i+2]+B[j+2];
k=k+3;
i=i+3;
j=j+3;
}
else if(A[i+1]<B[j+1]) //A的列小于B的列，将 A 的三个元素直接存入 C 中
{
C[k]=A[i];
C[k+1]=A[i+1];
C[k+2]=A[i+2];
k=k+3;
i=i+3;
}
else //B的列小于A的列，将B的三个元素直接存入C中
{
C[k]=B[j];
C[k+1]=B[j+1];
C[k+2]=B[j+2];
k=k+3;
j=j+3;
}
}
else if(A[i]<B[j]) //A的行小于B的行，将A的三个元素直接存入C中
{
C[k]=A[i];
C[k+1]=A[i+1];
C[k+2]=A[i+2];
k=k+3;
i=i+3;
}
else //B的行小于A的行，将B的三个元素直接存入C中
{
C[k]=B[j];
C[k+1]=B[j+1];
C[k+2]=B[j+2];
k=k+3;
j=j+3;
}
} //循环结束
if(A[i]==-1)
while(B[j]!=-1) //A结束B还有元素，将B的所有元素直接存入C中
{
C[k]=B[j];
C[k+1]=B[j+1];
C[k+2]=B[j+2];
k=k+3;
j=j+3;
}
else
while(A[i]!=-1) //B结束，A还有元素，将A的所有元素直接存入C中
{
C[k]=A[i];
C[k+1]=A[i+1];
C[k+2]=A[i+2];
k=k+3;
i=i+3;
}
C[k]=-1;
}
/*********************************************/
/* 主函数 */
/*********************************************/
void main()
{
int E[m][n],F[m][n],A[max],B[max],C[max];
int i,j,k;
printf("输入E矩阵：\n");
for(i=0;i<m;i++) //输入E矩阵所有元素值
for(j=0;j<n;j++)
scanf("%d",&E[i][j]);
printf("输入F矩阵：\n");
for(i=0;i<m;i++) //输入F矩阵所有元素值
for(j=0;j<n;j++)
scanf("%d",&F[i][j]);
CreateMatrix(E,A); //E矩阵的非零元素存储到一维数组A中
CreateMatrix(F,B); //F矩阵的非零元素存储到一维数组B中
MatrixAdd(A,B,C); //A,B相加存入C
i=0;
j=0;
k=0;
printf("A数组内容如下:\n");
while(A[i]!=-1) //输出A中内容
{
printf("%5d,%5d,%5d\n",A[i],A[i+1],A[i+2]);
i=i+3;
}
printf("B数组内容如下;\n");
while(B[j]!=-1)
{
printf("%5d,%5d,%5d\n",B[j],B[j+1],B[j+2]);
j=j+3;
}
printf("C数组内容如下;\n");
while(C[k]!=-1)
{
printf("%5d,%5d,%5d\n",C[k],C[k+1],C[k+2]);
k=k+3;
}
}
/*
测试输入：
E矩阵：
0 0 3 0 0 0 0 0
0 0 0 0 0 0 5 0
0 0 0 0 0 0 0 0
0 0 0 0 7 0 0 0
0 0 0 0 0 0 0 0
0 9 0 0 0 0 0 0
F矩阵：
0 2 0 0 0 0 0 0
0 0 0 4 0 0 0 0
0 0 0 0 0 6 0 0
0 0 0 0 8 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0
*/
广义表运算
#include<stdio.h>
#include<stdlib.h>
/*************************/
/* 广义表的存储结构 */
/*************************/
typedef char DataType;
enum{fasle,true};
typedef enum{atom,list}NodeTag; //atom=0,表示原子;list=1,表示子表
typedef struct GLnode
{
NodeTag tag; //用以区分原子结点和表结点
union
{
DataType data; //用以存放原子结点值，其类型由用户自定义
struct GLnode * slink; //指向子表的指针
};
struct GLnode * link; //指向下一个表结点
}GLNode,*Glist; //广义表结点及广义表类型
/*************************/
/* 建立广义表函数 */
/*************************/
//注：C语言中&(如&a)是取变量a的地址;而C++中&(&a)是变量a的引用(即表示变量a的地址),仅仅只是一个标识而已。
void CreatGList(Glist GL)
{
char ch;
scanf("%c",&ch);
if(ch!=10) //如果广义表未结束(10是回车的ASCII码)
{
if(ch=='(')
{
GL->tag=list;
GL->slink=(GLNode *)malloc(sizeof(GLNode));
CreatGList(GL->slink); //递归调用构造子表
}
else if (ch == ')')
GL = NULL;
else
{
//GL=(GLNode *)malloc(sizeof(GLNode));
//构造原子结点
GL->tag=atom;
GL->data=ch;
}
} //结束
else
GL=NULL;
scanf("%c",&ch);
if(GL!=NULL)
if(ch!=10)
{
if(ch==',')
{
GL->link=(GLNode *)malloc(sizeof(GLNode));
CreatGList(GL->link); //递归构造后续广义表
}
else
GL->link=NULL; //表示遇到 ')'或结束符 ';'时无后续表
}
else
GL->link=NULL;
}
/*************************************/
/* 输出广义表函数 */
/*************************************/
void PrintGList(Glist GL)
{
if(GL!=NULL)
{
if(GL->tag==list)
{
printf("(");
if(GL->slink==NULL)
printf(" ");
else PrintGList(GL->slink); //递归调用输出子表
}
else
printf("%c",GL->data); //输出结点数据域值
if(GL->tag==list)
printf(")");
if(GL->link!=NULL)
{
printf(",");
PrintGList(GL->link); //递归调用输出下一个结点
}
}
}
/*************************************/
/* 广义表查找函数 */
/*************************************/
Glist FindGlistX(Glist GL,DataType x,int *mark)
{ //调用广义表GL所指向的广义表，mark=false,x为查找的元素，
//若查找成功，mark=true,p为指向数据域为x的结点
if(GL!=NULL)
{
if(GL->tag==0 && GL->data==x)
{
*mark=true;
return GL;
}
else
if(GL->tag==1)
FindGlistX(GL->slink,x,mark);
FindGlistX(GL->link,x,mark);
}
return NULL;
}
/*************************************/
/* 求广义表表头函数 */
/*************************************/
Glist head(Glist GL)
{
Glist p;
if(GL!=NULL && GL->tag!=0) //不为空并且不是原子
{
p=GL->slink;
p->link=NULL;
return p; //返回GL中指向子表的指针
}
else
return NULL;
}
/*************************************/
/* 求广义表表尾函数 */
/*************************************/
Glist tail(Glist GL)
{
Glist p;
if(GL!=NULL && GL->tag!=0) //表不为空表并且有表尾
{
p=GL->slink;
p=p->link; //p指向第二个元素
GL->slink=p; //删除广义表第一个元素
}
return p;
}
/*************************************/
/* 求广义表深度 */
/*************************************/
void depth(Glist GL,int *maxdh)
{
int h;
if(GL->tag==0)
maxdh=0; //说明广义表为单个元素
else
if(GL->tag==1 && GL->slink==NULL)
*maxdh=1; //广义表为空表
else //进行递归求解
{
GL=GL->slink; //进入第一层
*maxdh=0;
do //循环扫描表的第一层的每个结点，对每个结点求其子表深度
{
depth(GL,&h);
if(h>*maxdh)
*maxdh=h; //取最大的子表深度
GL=GL->link;
}while(GL!=NULL);
*maxdh=*maxdh+1; //子表最大深度加1
}
}
/*************************************/
/* 求广义表的长度(即元素的个数 */
/*************************************/
//注：GL->slink=NULL 和没有指定空间是不同的。
int GListLength(Glist GL)
{
if (GL != NULL)
return 1+GListLength(GL->link);
else
return 0;
}
/*************************************/
/* 复制广义表 */
/*************************************/
void CopyGList(Glist NList,Glist GList)
{//复制广义表要
//将广义表的标记、原子、子表和下一结点复制
if (!GList)//原广义表为空
NList = NULL;
else
{
NList->tag = GList->tag;
if (GList->tag == 0)
NList->data = GList->data;//复制广义表的原子结点
else if (GList->tag == 1)
{
if (!(NList->slink = (GLNode *)malloc(sizeof(GLNode))))
printf("存储空间分配失败\n");
CopyGList(NList->slink,GList->slink);//复制广义表的子表
}
if (!(NList->link = (GLNode *)malloc(sizeof(GLNode))))
printf("存储空间分配失败\n");
CopyGList(NList->link,GList->link);//复制广义表的下一结点
}
}
/*************************************/
/* 主函数:广义表基本运算的实现 */
/*************************************/
int main()
{
int xz=1,mark;
char x;
Glist GL=(GLNode *)malloc(sizeof(GLNode));
Glist GL1,NList;
//void CreatGList(Glist GL),PrintGList(Glist GL),depth(Glist GL,int *maxdh);
//Glist FindGlistX(Glist GL,DataType x,int *mark),head(Glist GL),tail(Glist GL);
while(xz)
{
printf("*===============================*\n");
printf("* 广义表的运算 *\n");
printf("*===============================*\n");
printf("**********1.建立广义表***********\n");
printf("**********2.广义表查找***********\n");
printf("**********3.求广义表头***********\n");
printf("**********4.求广义表尾***********\n");
printf("**********5.求广义表深度*********\n");
printf("**********6.求广义表长度*********\n");
printf("**********7.输出复制广义表********\n");
printf("**********0.退出表的运算*********\n");
printf("*===============================*\n");
printf(" 请 选 择：0-5 \n");
scanf("%d",&xz);
getchar();
switch(xz)
{
case 1:
printf("输入广义表：");
CreatGList(GL);
printf("输出广义表：");
PrintGList(GL);
printf("\n");
break;
case 2:
printf("输入要查找的数据值(单个字符): ");
scanf("%c",&x);
mark=fasle;
FindGlistX(GL,x,&mark);
if(mark)
printf("要查找的数据存在表中！\n");
else
printf("要查找的数据不在表中！\n");
break;
case 3:
printf("输入要求表头的广义表：");
CreatGList(GL);
GL1=head(GL);
printf("广义表的表头是：");
PrintGList(GL1);
printf("\n");
break;
case 4:
printf("输入要求表尾的广义表：");
CreatGList(GL);
GL1=tail(GL);
printf("广义表的表尾是：");
printf("(");
PrintGList(GL1);
printf(")");
printf("\n");
GL=NULL;
break;
case 5:
printf("输入要求深度的广义表：");
CreatGList(GL);
mark=0;
depth(GL,&mark);
printf("广义表的深度是：%5d\n",mark);
break;
case 6:
printf("输入要求长度的广义表：");
CreatGList(GL);
mark=0;
printf("广义表的长度是：%5d\n",GListLength(GL->slink));
break;
case 7:
if (!(NList = (GLNode *)malloc(sizeof(GLNode))))
printf("存储空间分配失败\n");
CopyGList(NList,GL);
printf("输出复制广义表:");
PrintGList(NList);
break;
default:
printf("再见！\n");
return 0;
}
}
}