zhou.cpp

可以实现线性表的基本操作

	int i,j;
	printf("矩阵为：");
	for(i=0;i<M.mu;i++)
	{
		printf("\n");
		for(j=0;j<M.nu;j++)
			printf("%d\t",M.data[i][j]);
	}
	printf("\n");
}//PrintMatrix

TSMatrix CreatTSMatrix()
//以行序为主序建立三元组表存储的矩阵M
{
	TSMatrix M;
	int mu,nu,tu,i,j,e,k=0,tempi,tempj,tempe;
	do
	{
		printf("输入矩阵的非零元的个数(tu<=100):");
		scanf("%d",&tu);
		getchar();
	}while(!(tu>=0&&tu<=MAXSIZE));
	M.tu=tu;
	do
	{
		printf("输入矩阵的行数(mu<=20):");
		scanf("%d",&mu);
		getchar();
	}while(!(mu>0&&mu<=MAX));
	M.mu=mu;
	do
	{
		printf("输入矩阵的列数(nu<=20):");
		scanf("%d",&nu);
		getchar();
	}while(!(nu>0&&nu<=MAX));
	M.nu=nu;
	while(k<M.tu)
	{
		printf("输入三元组的行下标，列下标和值(i,j,e):");
		scanf("%d,%d,%d",&i,&j,&e);
		getchar();
		while(!(i>=0&&i<M.mu&&j>=0&&j<M.nu))
		{
			printf("非法输入,请再次输入：");
			scanf("%d,%d,%d",&i,&j,&e);
			getchar();
		}
		M.data[k].i=i;
		M.data[k].j=j;
		M.data[k].e=e;
		k++;
	}
	for(k=1;k<tu;k++)
	{
		tempi=M.data[k].i;
		tempj=M.data[k].j;
		tempe=M.data[k].e;
		if(M.data[k-1].i>tempi||(M.data[k-1].i==tempi&&M.data[k-1].j>tempj))
		{
			for(i=k-1;i>=0&&(M.data[i].i>tempi||(M.data[i].i==tempi&&M.data[i].j>tempj));i--)
				M.data[i+1]=M.data[i];
			M.data[i+1].i=tempi;
			M.data[i+1].j=tempj;
			M.data[i+1].e=tempe;
		}//if
	}//for
	return M;
}//CreatTSMatrix

TSMatrix TransTSMatrix(TSMatrix M)
//求矩阵M的快速转置矩阵T
{
	TSMatrix T;
	int col,p,q,num[MAX],cpot[MAX];
	T.mu=M.nu;
	T.nu=M.mu;
	T.tu=M.tu;
	if(T.tu)
	{
		for(col=0;col<M.nu;col++)
			num[col]=0;
		for(p=0;p<M.tu;p++)
			num[M.data[p].j]++;
		cpot[0]=0;
		for(col=1;col<M.nu;col++)
			cpot[col]=cpot[col-1]+num[col-1];
		for(p=0;p<M.tu;p++)
		{
			col=M.data[p].j;
			q=cpot[col];
			T.data[q].i=M.data[p].j;
			T.data[q].j=M.data[p].i;
			T.data[q].e=M.data[p].e;
			cpot[col]++;
		}//for
	}//if
	return T;
}//TransTSMatrix

RLSMatrix CreatRLSMatrix(TSMatrix M)
//将三元组表存储的矩阵M转化为行逻辑链接的顺序表
{
	RLSMatrix T;
	int i,num[MAX];
	T.mu=M.mu;
	T.nu=M.nu;
	T.tu=M.tu;
	for(i=0;i<M.tu;i++)
		T.data[i]=M.data[i];
	for(i=0;i<T.mu;i++)
		num[i]=0;
	for(i=0;i<M.tu;i++)
		num[M.data[i].i]++;
	T.rpos[0]=0;
	for(i=1;i<M.mu;i++)
		T.rpos[i]=T.rpos[i-1]+num[i-1];
	return T;
}//CreatRLSMatrix

RLSMatrix MultRLSMatrix(TSMatrix M,TSMatrix T)
//求矩阵乘积Q=M*T,采用行逻辑链接存储表示
{
	RLSMatrix Q,A,B;
	int i,arow,ctemp[MAX],tp,p,brow,t,q,ccol;
	A=CreatRLSMatrix(M);
	B=CreatRLSMatrix(T);
	if(A.nu!=B.mu)
	{
		printf("无法相乘");
			exit(0);
	}
	Q.mu=A.mu;
	Q.nu=B.nu;
	Q.tu=-1;
	if(A.tu*B.tu)
	{
		for(arow=0;arow<A.mu;arow++)
		{
			for(i=0;i<MAX;i++)
				ctemp[i]=0;
			Q.rpos[arow]=Q.tu+1;
			if(arow<A.mu-1)
				tp=A.rpos[arow+1];
			else
				tp=A.tu;
			for(p=A.rpos[arow];p<tp;p++)
			{
				brow=A.data[p].j;
				if(brow<B.mu-1)
					t=B.rpos[brow+1];
				else
					t=B.tu;
				for(q=B.rpos[brow];q<t;q++)
				{
					ccol=B.data[q].j;
					ctemp[ccol]+=A.data[p].e*B.data[q].e;
				}//for q
			}//for p
			for(ccol=0;ccol<Q.nu;ccol++)
			{
				if(ctemp[ccol])
				{
					if(++Q.tu>MAXSIZE)	
						exit(0);
					Q.data[Q.tu].i=arow;
					Q.data[Q.tu].j=ccol;
					Q.data[Q.tu].e=ctemp[ccol];
				}//if
			}//for ccol
		}//for arow
	}//if
	Q.tu++;
	return Q;
}//MultRLSMatrix

void PrintTSMatrix(TSMatrix M)
//以行序为主序顺序输出三元组表存储的矩阵M
{
	RLSMatrix T;
	int i,j,ccol,tp,k;	//ccol作为循环变量，用来访问矩阵每一行的非零元,tp指向没该行最后一个非零元的下一个位置
	T=CreatRLSMatrix(M);
	printf("矩阵为：");
	for(i=0;i<T.mu;i++)
	{
		printf("\n");
		if(i<T.mu-1)
			tp=T.rpos[i+1];
		else
			tp=T.tu;
		for(j=0,ccol=T.rpos[i];ccol<tp;j++)
		{
			if(j!=T.data[ccol].j)
				printf("0\t");
			else
			{
				printf("%d\t",T.data[ccol].e);
				ccol++;
			}//else
		}//for j
		for(k=j;k<T.nu;k++)
			printf("0\t");
	}//for i
}//PrintfTSMatrix

void PrintRLSMatrix(RLSMatrix T)
//以行序为主序顺序输出行逻辑表存储的矩阵T
{
	int i,j,ccol,tp,k;	//ccol作为循环变量，用来访问矩阵每一行的非零元,tp指向没一行最后一个非零元的下一个位置
	printf("\n矩阵为：");
	for(i=0;i<T.mu;i++)
	{
		printf("\n");
		if(i<T.mu-1)
			tp=T.rpos[i+1];
		else
			tp=T.tu;
		for(j=0,ccol=T.rpos[i];ccol<tp;j++)
		{
			if(j!=T.data[ccol].j)
				printf("0\t");
			else
			{
				printf("%d\t",T.data[ccol].e);
				ccol++;
			}//else
		}//for j
		for(k=j;k<T.nu;k++)
			printf("0\t");
	}//for i
}//PrintRLSMatrix

void MenuSqList()		
//顺序表演示系统菜单函数
{
	printf("\n\n\n\n\n\n======================顺序表演示系统====================");
	printf("\n0.结束");
	printf("\n1.初始化顺序表，并为顺序表赋值,表中元素为字符类型");
	printf("\n2.对顺序表简单进行插入排序，使其按ASC码值递增排列");
	printf("\n3.在顺序表L中第i个元素前插入新的元素");
	printf("\n4.在第一个元素值为e的元素前插入新的元素");
	printf("\n5.在顺序表中删除第i个元素");
	printf("\n6.在顺序表中删除元素值为某一特定值的元素");
	printf("\n7.合并顺序表，使Lb直接接在La后面构成顺序表Lc");
	printf("\n选择操作:");
}//MenuSqList

void ShowSqList()		
//顺序表演示系统
{
	SqList La,Lb,Lc,L;
	int i,loc;
	char e;
	while(1)
	{
		MenuSqList();
		scanf("%d",&i);
		getchar();		//清除垃圾字符——回车字符
		while(!((i>=0)&&(i<=7)))
		{
			printf("输入错误,选择操作:");
			scanf("%d",&i);
			getchar();
		}//while(i)	
		switch(i)
		{
		case 0:	return;
		case 1:	L=InitSqList();
			PrintSqList(L);	break;
		case 2: SortSqList(&L);
			PrintSqList(L);	break;
		case 3:	printf("输入位置pos：(0=<pos<=%d)",L.length+1);
			scanf("%d",&loc);
			getchar();
			InsertPositionSqList(&L,loc);
			PrintSqList(L);	break;
		case 4:	printf("输入要在它前面插入元素的元素值：");
			scanf("%c",&e);
			getchar();
			InsertElemSqList(&L,e);
			PrintSqList(L);	break;
		case 5:	DeletePositionSqList(&L);
			PrintSqList(L);	break;
		case 6:	DeleteElemSqList(&L);
			PrintSqList(L);	break;
		case 7:	printf("建立顺序表La,Lb:\n");
			La=InitSqList();	
			PrintSqList(La);
			printf("\n");
			Lb=InitSqList();	
			PrintSqList(Lb);
			Lc=MergeSqList(La,Lb);
			PrintSqList(Lc);	break;
		}//switch(i)
	}//while(1)
}//ShowSqList

void MenuLinkedList()
//链表演示系统菜单
{
	printf("\n\n\n\n\n\n===============链表演示系统==================");
	printf("\n0.退出");
	printf("\n1.建立链表");
	printf("\n2.对链表排序");
	printf("\n3.清空链表");
	printf("\n4.检查链表是否为空");
	printf("\n5.遍历链表 ");
	printf("\n6.求链表的长度");
	printf("\n7.从链表表中查找元素");
	printf("\n8.从链表表中查找与给定元素值相同的元素在链表中的位置");
	printf("\n9. 向链表中插入元素");
	printf("\n10.从链表中删除元素");
	printf("\n11.合并链表La,Lb，使合并后链表有序");
}//MuneLinkedList

void ShowLinkedList()
//链表演示系统
{
	int i,locate,x;
	LinkedList head,La,Lb,p,Lc;
	while(1)
	{
		MenuLinkedList();
		printf("\n选择操作,输入数i(0=<i<=11)：");
		scanf("%d",&i);
		while(!((i>=0)&&(i<=11)))
		{
			MenuLinkedList();
			printf("\ni值错误");
			printf("\n选择操作,输入数i(0=<i<=11)：");
			scanf("%d",&i);
		}//while(i)
		switch(i)
		{
			case 0:	return;
			case 1:	head=LinkedListCreat();
					LinkedListTraverse(head);	break;	
			case 2:	SortLinkedList(head);
					printf("排序后链表为：");
					LinkedListTraverse(head);	break;
			case 3:	LinkedListClear(head);	break;
			case 4:	if(LinkedListEmpty(head))
						printf("链表为空");
					else
						printf("链表非空");	break;
			case 5:	LinkedListTraverse(head);	break;
			case 6: printf("链表的长度为%d",LinkedListLength(head));	break;
			case 7:	printf("输入位置:");
					scanf("%d",&locate);
					getchar();
					p=LinkedListGet(head,locate);
					if(!p)
						printf("输入非法");
					else
						printf("您要查找的元素是%d",p->data);	break;
			case 8:	printf("输入元素:");
					scanf("%d",&x);
					getchar();
					if(!LinkedListLocate(head,x))
						printf("不存在查找元素");
					else
						printf("元素的位置是%d",LinkedListLocate(head,x));	break;
			case 9:	printf("输入位置pos(1<=pos<=%d):",head->data);
					scanf("%d",&locate);
					getchar();
					printf("输入元素:");
					scanf("%d",&x);
					LinkedListInsert(head,locate,x);
					LinkedListTraverse(head);	break;
			case 10:printf("输入要删除的元素:");
					scanf("%d",&x);
					getchar();
					LinkedListDel(head,x);
					LinkedListTraverse(head);	break;
			case 11:printf("建立链表La:");
					La=LinkedListCreat();
					LinkedListTraverse(La);
					printf("\n建立链表Lb:");
					Lb=LinkedListCreat();
					LinkedListTraverse(Lb);
					Lc=MergeLinkedList(La,Lb);
					printf("\n合并链表La、Lb，并排序后得到");
					LinkedListTraverse(Lc);
		}//switch(i)
	}//while(1)
}//ShowLinkedList

void ShowKMP()
//串的模式匹配演示系统
{
	SqList S,T;
	int pos;
	printf("\t\t\t\t串的模式匹配演示系统\n");
	printf("建立主串:");
	S=InitSqList();
	printf("\n建立模式串:");
	T=InitSqList();
	printf("\n输入主串开始匹配的位置：");
		scanf("%d",&pos);
	if(!IndexKMP(S,T,pos))
		printf("模式匹配不成功");
	else
		printf("模式串在主串中的位置为：%d",IndexKMP(S,T,pos));
}//ShowKMP

void ShowArMatrix()
//二维数组存储结构的矩阵演示系统
{
	int i;
	Matrix M,T,Q;
	printf("\n\n\n\n\n\n===============二维数组存储结构的矩阵演示系统==================");
	printf("\n0.退出");
	printf("\n1.建立二维数组存储结构的矩阵M");
	printf("\n2.求二维数组存储结构的矩阵M的转置矩阵T");
	printf("\n3.求二维数组存储结构的矩阵M和T的乘积矩阵Q");
	while(1)
	{
		printf("\n选择操作：");
		scanf("%d",&i);
		while(!((i>=0)&&(i<=3)))
		{
			printf("输入错误,选择操作:");
			scanf("%d",&i);
		}//while(i)	
		switch(i)
		{
		case 0:	return;
		case 1:	M=CreatMatrix();
			PrintMatrix(M);	break;
		case 2: T=TransMatrix(M);
			PrintMatrix(T);	break;
		case 3:	printf("建立要相乘的矩阵M,T:\n");
			M=CreatMatrix();
			PrintMatrix(M);
			T=CreatMatrix();
			PrintMatrix(T);
			Q=MultMatrix(M,T);
			printf("M*T得到矩阵Q,");
			PrintMatrix(Q);	break;		
		}//switch(i)
	}//while(1)
}//ShowArMatrix

void ShowTSMatrix()
//三元组表存储的矩阵演示系统
{
	TSMatrix M,T;
	RLSMatrix Q;
	int i;
	printf("\n\n\n\n\n\n===============三元组表存储的矩阵演示系统==================");
	printf("\n0.退出");
	printf("\n1.以行序为主序建立三元组表存储的矩阵M");
	printf("\n2.求矩阵M的快速转置矩阵T");
	printf("\n3.求矩阵乘积Q=M*T");
	while(1)
	{
		printf("\n选择操作：");
		scanf("%d",&i);
		while(!((i>=0)&&(i<=3)))
		{
			printf("输入错误,选择操作:");
			scanf("%d",&i);
		}//while(i)	
		switch(i)
		{
		case 0:	return;
		case 1:	M=CreatTSMatrix();
			PrintTSMatrix(M);	break;
		case 2: T=TransTSMatrix(M);
			PrintTSMatrix(T);	break;
		case 3:	printf("建立要相乘的矩阵M,T:\n");
			printf("建立矩阵M:\n");
			M=CreatTSMatrix();
			PrintTSMatrix(M);
			printf("\n建立矩阵T:\n");
			T=CreatTSMatrix();
			PrintTSMatrix(T);
			Q=MultRLSMatrix(M,T);
			printf("M*T得到矩阵Q,");
			PrintRLSMatrix(Q);	break;		
		}//switch(i)
	}//while(1)
}

void MenuMatrix()
//矩阵演示系统菜单
{
	printf("\n\n\n\n\n\n===============矩阵演示系统==================");
	printf("\n0.退出");
	printf("\n1.进入二维数组存储结构的矩阵演示系统");
	printf("\n2.进入三元组表存储的矩阵演示系统");
	printf("\n选择操作：");
}

void ShowMatrix()
//矩阵演示系统
{
	int i;
	while(1)
	{
		MenuMatrix();
		scanf("%d",&i);
		while(!(i>=0&&i<=2))
		{
			printf("非法输入：");
			MenuMatrix();
			scanf("%d",&i);
		}//while i
		switch(i)
		{
		case 0:	return;
		case 1:	ShowArMatrix();	break;
		case 2:	ShowTSMatrix();	break;
		}//switch
	}//while
}//ShowMatrix

void Menu()
{
	printf("\n\n\n\n\n\n======================线性表演示系统====================");
	printf("\n0.结束");
	printf("\n1.进入顺序表演示系统");
	printf("\n2.进入链表演示系统");
	printf("\n3.进入串的模式匹配演示系统");
	printf("\n4.进入矩阵演示系统");
	printf("\n请选择：");
}//Menu

void main()
{
	int i;
	while(1)
	{
		Menu();
		scanf("%d",&i);
		while(!((i>=0)&&(i<=7)))
		{
			printf("输入错误,选择操作:");
			scanf("%d",&i);
		}//while(i)	
		switch(i)
		{
		case 0:	return;
		case 1:	ShowSqList();	break;
		case 2: ShowLinkedList();	break;
		case 3:	ShowKMP();	break;
		case 4:	ShowMatrix();	break;
		}//switch(i)
	}//while(1)
}//main