zhou.cpp

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

#define LIST_INIT_SIZE 100	//线性表顺序存储结构存储空间初始分配量
#define LISTINCREMENT 10	//存储空间分配增量
#define MAX 20				//矩阵最大行列数
#define MAXSIZE	100			//线性表、链表元素个数最大，矩阵非零元个数最大值
#include<stdio.h>
#include<stdlib.h>

typedef struct
{
	char *elem;		//存储空间基址
	int length;		//表长度
	int listsize;	//当前分配的存储容量
}SqList;

typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkedList;

typedef struct			//矩阵的二维数组存储结构
{
	int data[MAX][MAX];	//矩阵
	int mu,nu;			//矩阵的行数和列数
}Matrix;

//矩阵的三元组表存储结构
typedef struct			//非零元的三元组结构
{
	int i,j;			//非零元的行下标和列下标
	int e;
}Triple;

typedef struct
{
	Triple data[MAXSIZE];	//非零元的三元组表
	int mu,nu,tu;			//矩阵的行数和列数和非零员个数
}TSMatrix;

typedef struct				//矩阵的行逻辑链接的顺序表
{
	Triple data[MAXSIZE];	//非零员的三元组表
	int rpos[MAX];			//各行第一个非零元的位置表
	int mu,nu,tu;			//矩阵的行数和列数和非零员个数
}RLSMatrix;

SqList InitSqList()	
//初始化顺序表，并为顺序表赋值，
//表中元素为字符类型
{
	int i=0;
	SqList L;
	char *newbase;
	L.elem=(char *)malloc(LIST_INIT_SIZE);
	if(!L.elem)
	{
		printf("存储空间分配失败");
			exit(0);
	}
	L.length=0;
	L.listsize=LIST_INIT_SIZE;
	printf("顺序输入顺序表的元素(空格结束，元素为字符型):");
	do
	{
		if(L.length==L.listsize)
		{
			newbase=(char *)realloc(L.elem,(L.listsize+LISTINCREMENT));
			L.elem=newbase;
			L.listsize+=LISTINCREMENT;
		}//if
		L.elem[i]=getchar();	
		L.length++;
		i++;
	}while(L.elem[i-1]!=' ');
	getchar();			//清除垃圾字符——回车字符
	L.length--;
	return L;
}//InitSqList

void SortSqList(SqList *L)		//必须传递指针
//对顺序表简单插入排序，使其按ASC码值递增排列
{
	int i,j;
	char e;
	for(i=1;i<L->length;i++)		//简单插入排序
	{
		if(L->elem[i-1]>L->elem[i])
		{
			e=L->elem[i];
			for(j=i-1;j>=0&&L->elem[j]>e;j--)
				L->elem[j+1]=L->elem[j];
			L->elem[j+1]=e;
		}//if
	}//for
}//SortSqList

void InsertPositionSqList(SqList *L,int i)	//必须传递指针
//在顺序表L中第i个元素前插入新的元素
{
	int j;
	char e;
	char *newbase;
	if(i<1||i>L->length+1)
	{
		printf("位置pos值不合法\n");
		return;
	}
	printf("输入待插入元素:");
	scanf("%c",&e);
	getchar();		//清除垃圾字符
	if(L->length>=L->listsize)					//空间不够，另外分配空间
	{
		newbase=(char *)realloc(L->elem,(L->listsize+LISTINCREMENT));		//重新分配的存储空间的首地址不一																	
		L->elem=newbase;												//定与元空间首地址相同，但realloc
		L->listsize+=LISTINCREMENT;										//会把原地址中的值依次赋给新的空间中
	}
	for(j=L->length;j>=i;j--)			//第i个元素开始向后移
		L->elem[j]=L->elem[j-1];	
	L->elem[i-1]=e;						//插入元素
	L->length++;						
}//InsertPositionSqList

void InsertElemSqList(SqList *L,char e)
//在第一个元素值为e的元素前插入新的元素
{
	int i,j;
	char insert,*newbase;
	printf("输入要插入元素:");
	scanf("%c",&insert);
	getchar();
	if(L->length>=L->listsize)
	{
		newbase=(char *)realloc(L->elem,(L->listsize+LISTINCREMENT));
		L->elem=newbase;
		L->listsize+=LISTINCREMENT;
	}
	for(i=0;i<L->length&&L->elem[i]!=e;i++)
	if(i==L->length-1)																//有问题，为什么是L->length-1,而不是L->length
	{
		printf("顺序表中不存在该元素\n");
		return;
	}
	for(j=L->length-1;j>=i;j--)
	{	
		L->elem[j+1]=L->elem[j];
		L->elem[j]=insert;
	}
	L->length++;
}//InsertElemSqList

void DeletePositionSqList(SqList *L)
//在顺序表中删除第i个元素
{
	int i,j;
	printf("输入删除元素的位置pos(1=<pos<=%d):",L->length);
	scanf("%d",&i);
	getchar();
	if(i<1||i>L->length)
	{
		printf("pos值不合法");
			return;
	}
	for(j=i;j<L->length;j++)
		L->elem[j-1]=L->elem[j];
	L->length--;
}//DeletePositionSqList

void DeleteElemSqList(SqList *L)
//在顺序表中删除元素值为某一特定值的元素
{
	char e;
	int i,del=0;							//del记录当前共需要删除的元素个数
	printf("输入要删除的元素的值:");
	scanf("%c",&e);
	getchar();
	for(i=0;i<L->length;i++)
	{		
		if(L->elem[i]==e)		
			del++;							//当前元素需要删除,del自加
		else
			L->elem[i-del]=L->elem[i];		//不需要删除的元素前移到适当位置
	}
	if(!del)
		printf("不存在要删除的元素\n");
	L->length-=del;
}//DeleteElemSqList

SqList MergeSqList(SqList La,SqList Lb)
//合并顺序表，使Lb直接接在La后面构成顺序表Lc
{
	int i;
	SqList Lc;
	Lc.length=Lc.listsize=La.length+Lb.length;
	Lc.elem=(char*)malloc(Lc.length);
	if(!Lc.elem)
	{
		printf("存储空间分配失败");
		exit(0);
	}
	for(i=0;i<La.length;i++)
		Lc.elem[i]=La.elem[i];
	for(i=0;i<Lb.length;i++)
		Lc.elem[La.length+i]=Lb.elem[i];
	return Lc;
}//MergeSqList

void PrintSqList(SqList L)
//顺序输出顺序表中各元素
{
	int i;
	printf("顺序表的长度为：%d\n",L.length);
	printf("顺序表为：");
	for(i=0;i<L.length;i++)
		printf("%c",L.elem[i]);
}//PrintSqList

LinkedList LinkedListCreat()
//建立链表 
{
	LinkedList L=NULL,p1,p;
	int m,i;
	printf("Input number of the nodes:");
	scanf("%d",&m);
	getchar();
	p=(LinkedList)malloc(sizeof(int));
	p->next=NULL;
	p->data=m;
	L=p;
	p1=p;
	for(i=0;i<m;i++)
	{
		p=(LinkedList)malloc(sizeof(int));
		p->next=NULL;
		printf("Input data:");
		scanf("%d",&p->data);
		getchar();
		p1->next=p;
		p1=p;
	}
	return L;
}//LinkedListCreat

void SortLinkedList(LinkedList L)
//对链表元素选择排序
{
	LinkedList tail=L,head=L->next,p2,p,p1;			//tail指向有序链表的最后一个结点，head指向无序链表的第一个结点，
	int temp=0;									//p指向当前访问结点,p1指向当前找到的最小结点,p2指向p1所指结点的前一个结点
	while(temp<L->data)
	{
		p1=head;
		p=head->next;
		while(p)
		{
			if(p1->data>p->data)
				p1=p;
			p=p->next;
		}
		if(p1==head)
		{
			head=head->next;
			tail->next=p1;
			tail=p1;
			tail->next=NULL;
		}
		else
		{
			for(p2=head;p2->next!=p1;p2=p2->next);				//?????????????????????
			p2->next=p1->next;
			tail->next=p1;
			tail=p1;
			tail->next=NULL;
		}
		temp++;
	}
}//SortLinkedList

LinkedList MergeLinkedList(LinkedList La,LinkedList Lb)
//合并链表La,Lb，使合并后链表有序
{
	LinkedList Lc,pc,pa,pb;
	SortLinkedList(La);
	SortLinkedList(Lb);
	pa=La->next;
	pb=Lb->next;
	Lc=pc=La;
	Lc->data=La->data+Lb->data;
	while(pa&&pb)
	{
		if(pa->data<=pb->data)
		{
			pc->next=pa;
			pc=pa;
			pa=pa->next;
		}
		else
		{	
			pc->next=pb;		
			pc=pb;
			pb=pb->next;
		}		
	}
	if(pa)
		pc->next=pa;
	else
		pc->next=pb;
	free(Lb);
	return Lc;
}

void LinkedListClear(LinkedList L)
//清空链表
{
	LinkedList p;
	p=L;
	while(p)
	{
		L=L->next;
		free(p);
		p=L;
	}
	free(L);
}//LinkedListClear

int LinkedListEmpty(LinkedList L)
//检查链表是否为空
{
	if(!L->data)
		return 1;
	else
		return 0;
}//LinkedListEmpty

void LinkedListTraverse(LinkedList L)
//遍历链表
{
	LinkedList p;
	p=L->next;
	printf("链表为：");
	while(p)
	{
		printf("%5d",p->data);
		p=p->next;
	}
}//LinkedListTraverse

int  LinkedListLength(LinkedList L)
//求链表的长度
{
	return(L->data);
}//LinkedListLength

LinkedList  LinkedListGet(LinkedList L,int i)
//查找链表中第i元素
{
	LinkedList p;
	int j=1;
	p=L->next;
	while(p&&j<i)
	{
		p=p->next;
		j++;
	}
	return p;
}//LinkedListGet

int  LinkedListLocate(LinkedList L,int x)
//从链表表中查找与给定元素值
//相同的元素在链表中的位置
{
	LinkedList p;
	int i=1;
	p=L->next;
	while(p&&p->data!=x)
	{
		p=p->next;
		i++;
	}
	if(!p)
		i=0;
	return i;
}//LinkedListLocate

void  LinkedListInsert(LinkedList L,int i,int x)
//向链表位置i处插入元素x
{
	LinkedList p,p1,p2;
	int j=1;
	if(i>L->data)
	{
		printf("输入非法\n");
		return;
	}
	p=L->next;
	p1=L;
	while(j<i)
	{
		p1=p;
		p=p->next;
		j++;
	}
	p2=(LinkedList)malloc(sizeof(LNode));
	p2->data=x;
	p2->next=p;
	p1->next=p2;
	L->data++;
}//LinkedListInsert

void LinkedListDel(LinkedList  L,int x)
//从链表中删除指定元素x
{
	LinkedList p,p1;
	p=L->next;
	p1=L;
	while(p&&p->data!=x)
	{	
		p=p->next;
		p1=p1->next;
	}
	if(!p)
	{
		printf("不存在要删除的元素\n");
		return;
	}	
	p1->next=p->next;
	free(p);
	L->data--;
}//LinkedListDel

int * GetNext(SqList T)
//求模式串T的next函数值并存入数组next         
{
	int i=0,j=-1,*next;
	next=(int *)malloc((T.length)*sizeof(int));
	next[0]=-1;
	while(i<T.length-1)
	{
		if(j==-1||T.elem[i]==T.elem[j])
		{
			i++;
			j++;
			next[i]=j;
		}//if
		else
			j=next[j];
	}//while
	return next;
}//GetNext

int * GetNextval(SqList T)
//求模式串的next函数的修正值并存入数组nextval
{
	int i=0,j=-1,*nextval;
	nextval=(int *)malloc((T.length)*sizeof(int));
	nextval[0]=-1;
	while(i<T.length-1)
	{
		if(j==-1||T.elem[i]==T.elem[j])
		{
			i++;
			j++;
			if(T.elem[i]!=T.elem[j])
				nextval[i]=j;
			else
				nextval[i]=nextval[j];
		}//if
		else
			j=nextval[j];
	}//while
	return nextval;
}//GetNextval

int IndexKMP(SqList S,SqList T,int pos)
//利用模式串T的next函数求T在主串S中
//第POS个字符之后的位置KMP算法
{
	int i=pos,j=1,*next;		
	next=GetNextval(T);
	while(i<=S.length&&j<=T.length)
	{
		if(j==0||S.elem[i-1]==T.elem[j-1])
		{
			i++;
			j++;
		}
		else
			j=next[j-1]+1;		//j是元素的位置，从一开始，而next是从零开始。next[j-1]为第j个元素的next值
	}
	if(j>T.length)
		return i-T.length-1;		//返回的是子串第一个元素的位置。其序号为i-1即S.elem[i-1]=T.elem[0]
	else
		return 0;
}//IndexKMP

Matrix CreatMatrix()
//建立二维数组存储结构的矩阵M
{
	Matrix M;
	int i,j,mu,nu;
	printf("\n输入行数和列数(mu<=20,nu<=20):");
	scanf("%d,%d",&mu,&nu);
	M.mu=mu;
	M.nu=nu;	
	for(i=0;i<mu;i++)
	{
		for(j=0;j<nu;j++)
		{
			printf("输入元素M[%d][%d]=:",i,j);
			scanf("%d",&M.data[i][j]);
		}
	}
	return M;
}//CreatMatrix

Matrix TransMatrix(Matrix M)
//求二维数组存储结构的矩阵M的转置矩阵T
{
	Matrix T;
	int i,j;
	T.mu=M.nu;
	T.nu=M.mu;
	for(i=0;i<M.mu;i++)
		for(j=0;j<M.nu;j++)
			T.data[j][i]=M.data[i][j];
	return T;
}//TransMatrix

Matrix MultMatrix(Matrix M,Matrix T)
//求二维数组存储结构的矩阵M和T的乘积矩阵Q
{
	Matrix Q;
	int i,j,k;
	if(M.nu!=T.mu)
	{
		printf("这两个矩阵不能相乘");
		exit(0);							
	}
	Q.mu=M.mu;
	Q.nu=T.nu;
	for(i=0;i<M.mu;i++)
		for(j=0;j<T.nu;j++)
		{
			Q.data[i][j]=0;
			for(k=0;k<M.nu;k++)
				Q.data[i][j]+=M.data[i][k]*T.data[k][j];
		}
	return Q;
}//MultMatrix

void PrintMatrix(Matrix M)
//以矩阵形式输出二维数组存储结构的矩阵M
{