simplelinklist.cpp

来自「数据结构的链表处理函数,可以实现链表的插入删除修改查询连接等算法」· C++ 代码 · 共 132 行

#include "stdio.h"
#include "malloc.h"
struct node{int data;struct node *next;};
struct node *create_link()
{//建立链表
	int x;	struct node *h,*p,*r;
	h=(struct node *)(malloc(sizeof(struct node)));//建立临时结点
	p=h;	
	printf("请输入若干个整数，以0结尾");	scanf("%d",&x);
	while(x)
	{
		r=(struct node *)(malloc(sizeof(struct node)));//建立一个新结点
		r->data=x;	p->next=r;	p=p->next;
		scanf("%d",&x);
	}
	p->next=NULL;	p=h;	h=h->next;	free(p);//删除临时结点
	return h;
}
void print_link(struct node *h)
{//打印链表
	struct node *p=h;
	printf("\nhead");
	while(p!=NULL)
	{	printf("->%d",p->data);	p=p->next;	}
	printf("\n");
}
void insert_link(struct node *head,int x,int y)
{//在值为y的结点右侧插入一个值为x的结点
	struct node *p,*q,*r;
	r=(struct node *)(malloc(sizeof(struct node )));r->data=x;//新结点
	if(head==NULL){head=r;r->next=NULL;}//空表
	else //非空表
	{
		p=head;
		while(p->data!=y&&p!=NULL){q=p;p=p->next;}
		if(p!=NULL)//找到值为y的结点
		{r->next=p->next;p->next=r;	}
		else//没找到值为y的结点
		{r->next=NULL;q->next=r;}
	}
}
void delete_link(struct node *head,int x)
{//删除满足条件的结点
	struct node *p,*q;
	if(head==NULL)printf("链表空，没有结点可以删除！\n");//空表
	else if(head->data==x)
	{//首结点是要找的结点
		p=head;
		if(head->next==NULL)head=NULL;
		else head=head->next;
		free(p);
	}
	else
	{//结点可能在中间
		p=head;	q=p;
		while(p!=NULL&&p->data!=x){q=p;p=p->next;}//查找值为x的结点
		if(p!=NULL){q->next=p->next;free(p);}//找到了没，就删除
		else printf("没有满足条件的结点可以删除！\n");//没找到
	}
}
int length_link(struct node *head)
{//统计链表的长度（结点的个数）
	int i=0;struct node *p=head;
	while(p!=NULL){p=p->next;i++;}
	return i;
}
struct node *merge_link(struct node *X,struct node *Y)
{//交叉归并两个链表
	struct node *px,*py,*pz,*Z;	int m,n,i;
	m=length_link(Y); n=length_link(X);
	px=X;py=Y;
	if(m<=n)
	{//当链表X的长度大于Y时
		Z=px;pz=Z;
		for(i=1;i<2*m;i++)
			if(i%2==0)
			{py=py->next;pz->next=px;pz=pz->next;}
			else
			{px=px->next;pz->next=py;pz=pz->next;}
		pz->next=px;
	}
	else//当链表X的长度小于Y时
	{
		Z=py;pz=Z;
		for(i=1;i<2*n;i++)
			if(i%2==0)
			{px=px->next;pz->next=py;pz=pz->next;}
			else
			{py=py->next;pz->next=px;pz=pz->next;}
		pz->next=py;
	}
	return Z;
}
int search_link(struct node *head,int x)
{//查找结点值为x的结点序号
	struct node *p=head;int i=1;
	while(p!=NULL&&p->data!=x){p=p->next;i++;}
	if(p==NULL)return 0;
	else return i;
}
struct node *revert_link(struct node *head)
{//逆置
	struct node *h=NULL,*p=head,*q;
	while(p!=NULL)
	{q=p->next;	p->next=h;	h=p;	p=q;	}
	return h;
}
void sort_link(struct node *head)
{//排升序
	int m=length_link(head),i,j,t;struct node *p;
	for(i=1;i<m;i++)
	{
		p=head;
		for(j=0;j<m-i;j++)
		{
			if(p->data>p->next->data){t=p->data;p->data=p->next->data;p->next->data=t;}
			p=p->next;
		}
	}
}
void main()
{
	struct node *h1,*h2,*h3;
	h1=create_link();//h2=create_link();
//	h3=merge_link(h1,h2);
//	delete_link(h3,4);
	sort_link(h1);
	print_link(h1);
	//printf("%d",search_link(h1,3));
}