第一题.cpp

另外一个可以实现线性表的程序

#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量
#define LISTINCREMENT 10//线性表存储空间的分配增量
#define MAX 20//矩阵最大行列数
#define MAXSIZE	12500//假设非零元个数的最大值为12500

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;

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;
		}
		L.elem[i]=getchar();	
		L.length++;
		i++;
	}while(L.elem[i-1]!=' ');
	getchar();			
	L.length--;
	return L;
}//InitSqList

void SortSqList(SqList *L){		
	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;
		}
	}
}//SortSqList

void ListInsert_Sq(SqList *L,int i){//在顺序表L中第i个元素前插入新的元素
	int j;
	char e,*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;												
		L->listsize+=LISTINCREMENT;										
	}
	for(j=L->length;j>=i;j--)			
		L->elem[j]=L->elem[j-1];	
	L->elem[i]=e;						
	L->length++;												
}//ListInsert_Sq

void ListDelete_Sq(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+1;j<L->length;j++)
		L->elem[j-1]=L->elem[j];
	L->length--;	
}//ListDelete_Sq

SqList MergeList_Sq(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;
}//MergeList_Sq

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

LinkedList LinkedListCreat(){//建立链表 
	LinkedList L=NULL,p1,p;
	int i,m;
	printf("请输入接点的个数:");
	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("输入数据:");
		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;		
	int temp=0;									
	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;
}//MergeLinkedList

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("%3d",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;

	p1=L;
	while(p&&p->data!=x)
	{	
		p=p1;
		p1=p1->next;
	}
	if(!p)
	{
		printf("要删除的元素不存在.\n");
		return;
	}	
	else p=p1->next;
	free(p1);
	L->data--;
}//LinkedListDel

int * GetNext(SqList 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;