adtlink.cpp

关于链表的所有操作的代码

#include <stdio.h>
#include <malloc.h>
#define ElemType int
typedef int Status;

// 链表类型
typedef struct Node
{
	ElemType data;
	struct Node *next;
} Node, *LinkList;

// 建立一个带头结点的空线性链表L
void InitList(LinkList &L)
{
	L = (LinkList) malloc(sizeof(Node));
	if (!L) printf("\n Malloc Error \n"); //存储分配失败
	else L->next=NULL;
}//InitList

// 建立一个带头结点的、能够输入n个数据元素的线性链表L
void CreateList(LinkList &L,int n)
{
	int i;
	InitList(L);
	LinkList p,q;
	q=L;
	for (i=1; i<=n; ++i)
	{
		p = (LinkList)malloc(sizeof(Node)); //生成新结点
		if(!p)
		{
			printf("\n Malloc Error \n");
			return;
		} //存储分配失败
		q->next=p;
		printf("%d: ",i);
		scanf("%d",&p->data);
		q=p;
	}
	p->next=NULL;
}//CreateList

// 输出线性链表L中的所有数据元素
void PrintList(LinkList L)
{
	LinkList p;
	p=L->next;
	printf("\nL = ( ");
	while (p!=NULL)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf(")\n");
}//PrintList

// 计算线性链表L中结点的个数
Status LengthList(LinkList L)
{
	LinkList p;
	p=L->next;
	int i=0;
	while (p!=NULL)
	{
		++i;
		p=p->next;
	}
	//printf("\nLength is %d\n",i);
	return(i);
}//LengthList

// 在线性链表中查找第1个与e等值的数据元素的位序
void LocateList(LinkList L)
{
	LinkList p;
	p=L->next;
	int i=1;
	ElemType e;
	printf("\nPlease input Locate-ElemType e: ");
	scanf("%d",&e);
	while (p!=NULL && p->data!=e)
	{
		++i;
		p=p->next;
	}
	if (p==NULL) printf("\nNo the Element = ElemType %d\n",e);
	else printf("\nNo. of the Element = ElemType %d is %d\n",e,i);
}//LocateList

// 输出线性链表中所有值≥e的数据元素，并计算这些数据元素的个数
void FilterList(LinkList L)
{
	LinkList p;
	p=L->next;
	int i=0;
	ElemType e;
	printf("\nPlease input Filter-ElemType e: ");
	scanf("%d",&e);
	printf("\n( ");
	while (p!=NULL)
	{
		if (p->data>=e)
		{
			printf("%d ",p->data);
			++i;
		}
		p=p->next;
	}
	printf(")\nNumber of the Element >= ElemType %d is %d\n",e,i);
}//FilterList

// 更新线性链表L中第i个数据元素的值
void PutList(LinkList &L)
{
	LinkList p;
	p=L->next;
	int j=1,i;
	ElemType e;
	printf("\nPlease input Put-No. i: ");
	scanf("%d",&i);
	printf("\nPlease input Put-ElemType e: ");
	scanf("%d",&e);
	while (p!=NULL && j<i)
	{
		++j;
		p=p->next;
	}
	if (p!=NULL) p->data=e;
}//PutList

// 在线性链表中第i个结点之前插入新的数据元素e
void InsertList(LinkList &L)
{
	LinkList p,q;
	ElemType e;
	int flag=1,i,j;
	while (flag==1)
	{
		j=1;
		printf("\nPlease input Insert-No. i: ");
		scanf("%d",&i);
		if (i<1) return;
		printf("\nPlease input Insert-ElemType e: ");
		scanf("%d",&e);
		p = L;
		while (p!=NULL && j<i)
		{
			++j;
			p=p->next;
		} //寻找第i个结点
		if (p!=NULL)
		{
			q = (LinkList) malloc(sizeof(Node)); //生成新结点
			if(!q)
			{
				printf("\n Malloc Error \n");
				return;
			} //存储分配失败
			q->data = e;
			q->next = p->next; //链接到L中
			p->next = q;
		}
		PrintList(L);
		printf("\n Continue ? (continue:1/over:0) ");
		scanf("%d",&flag);
	}
}//InsertLinst

// 删除线性链表中的第i个结点
void DeleteList(LinkList &L)
{
	LinkList p,q;
	int flag=1,i,j,n;
	n=LengthList(L);
	while (flag==1 && n>0)
	{
		j=1;
		printf("\nPlease input Delete-No. i: ");
		scanf("%d",&i);
		if (i<1) return;
		p = L;
		while (p->next!=NULL && j<i)
		{
			++j;
			p=p->next;
		} //寻找第i个结点
		if (p->next!=NULL)
		{
			q = p->next;
			p->next = q->next;
			free(q); //删除并释放结点
			--n;
		}
		PrintList(L);
		if (L->next)
		{
			printf("\n Continue ? (continue:1/over:0) ");
			scanf("%d",&flag);
		}
	}
}//DeleteList

//将两个按值递增的线性链表La和Lb归并为一个按值递增的线性链表L
void MergeList(LinkList &L, LinkList &Lb)
{
	LinkList p,pa,pb;
	p=L;
	pa=L->next;
	while (Lb->next)
	{
		pb=Lb->next;
		Lb->next=pb->next;
		while (pa && pa->data < pb->data)
		{
			p=pa;
			pa=pa->next;
		}
		if (pa)
		{
			pb->next=pa;
			p->next=pb;
			p=pb;
		}
		else p->next=pb;
	}
	free(Lb); //释放Lb的头结点
}//MergeList

// 销毁线性链表L
void DestroyList(LinkList &L)
{
	free(L);  L=NULL;
	printf("\n线性链表L已销毁\n");
}//DestroyList

// 对带头结点的单链表L进行由小到大排序
void qsort(LinkList L)
{
	if(!L->next) return;
	int ex=0; //交换标记
	LinkList pre,mid,p,r;
	pre=L;
	mid=L->next;
	p=mid->next;
	while(p)
	{
		r=p->next;
		if(p->data<mid->data) //调换p和mid的位置
		{
			mid->next=r;
			p->next=mid;
			pre->next=p;
			pre=p;
			ex=1;
		}
		else //结点的位置保持不变
		{
			pre=mid;
			mid=p;
		}
		p=r;
	}
	if(ex) qsort(L); //对前一部分进行排序
}//qsort

void main()
{
	LinkList L;
	int n;
	printf("\nPlease input Terms n = ");
	scanf("%d",&n);
	if (n<1)
	{
		printf("\n%d < 1\n",n);
		return;
	}
	CreateList(L,n);
	PrintList(L);

	LengthList(L);

	LocateList(L);

	FilterList(L);

	PutList(L);
	PrintList(L);

	InsertList(L);
	
	DeleteList(L);

	qsort(L); PrintList(L);

	LinkList Lb;
	int m;
	printf("\nPlease input Terms m = ");
	scanf("%d",&m);
	if (m<1)
	{
		printf("\n%d < 1\n",m);
		return;
	}
	CreateList(Lb,m);
	PrintList(Lb);

	qsort(Lb); PrintList(Lb);

	MergeList(L,Lb);
	PrintList(L);

	DestroyList(L);
}