【数据结构】单链表基本操作的实现

【单链表的头插和尾插】//无头结点

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
	int date;
	struct LNode *next;
}LNode,*LinkList;
LinkList great_LinkList(LinkList L)//头部插入 
{
	
	LinkList s;
	int x,j=1;
	scanf("%d",&x);
	while(x!=0)
	{
		s=(LNode*)malloc(sizeof(LNode));
		s->date=x;
		s->next=L;
		L=s;
		scanf("%d",&x);
		if(s->next)
		{
			s=s->next;
			j++; 
		}
	}
	printf("表长："); 
	printf("%d\n",j);
	return L;
}
LinkList great_LinkList2(LinkList L)//尾部插入 
{
	LinkList s,r=NULL;
	int x;
	scanf("%d",&x);
	while(x!=0)
	{
		s=(LNode*)malloc(sizeof(LNode));
		s->date=x;
		if(L==NULL)
		L=s;
		else
		r->next=s;
		r=s;
		scanf("%d",&x);
		
	}
	r->next=NULL;//必须要有，不然会死循环 
	return L;
}
LinkList printLink(LinkList L)//链表输出 
{
	if(L==NULL)
	printf("表空\n");
	while(L!=NULL)
	{
		printf("%4d",L->date);
		L=L->next;
	}
	printf("\n");
	return L;
}
int main()
{
	LinkList a=NULL,b=NULL;
	printf("你要输入的数据：\n");
	a=great_LinkList(a);
	printf("头插法："); 
	printLink(a);
	printf("你要输入的数据：\n");
	b=great_LinkList2(b);
	printf("尾插法："); 
	printLink(b);
	return 0;
}

【带头结点的尾插法】

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
	int date;
	struct LNode* next;
}LNode,*LinkList;
LinkList Great_LinkList3()//带头结点的尾插法 
{
	LinkList L=NULL;//头结点 
	LNode *R=NULL;//尾结点
	int x;
	L=(LNode*)malloc(sizeof(LNode));//给头结点申请空间 
	L->next=NULL;//置空表 
	R=L;
	scanf("%d",&x);
	while(x!=0)
	{
		R->next=(LNode*)malloc(sizeof(LNode));//为插入元素申请空间 
		R->next->date=x;
		R=R->next;
		scanf("%d",&x);
	 } 
	R->next=NULL;
	return L;
}
void printLink(LinkList L)//有头结点的输出 
{
	if(L->next==NULL)
	printf("表空！");
	else
	while(L->next!=NULL)
	{
		printf("%4d",L->next->date);
		L=L->next;
	}
	printf("\n");
}
int main()
{
	LinkList a=NULL;
	printf("请输入数据："); 
	a=Great_LinkList3();
	printLink(a);
	return 0;
}

注：加入头结点的目的是操作方便，使得第一个结点的问题不再存在，并使“空表”与“非空表”的处理一致，以下代码段没说有无头结点的都是带头结点的

【带头结点表长】

int length_LinkList(LinkList L)
{
   LinkList p=L;
   int j=0;
   while(p->next)
   {
       p=p->next;
       j++;
   }
   return j;
}

【不带头结点表长】

int Length_LinkList2(LinkList L)
{
   LinkList p=L;
   int j;
   if(p==NULL)
   return 0;
   j=1;
   while(p->next)
   {
       p=p->next;
       j++;
   }
   return j;
}

【按序号查找元素值】

int Locate_LinkList(LinkList L,int i)
{
   LinkList p=L;
   int j=0,x;
   while(p->next!=NULL&&j<i)
   {
       p=p->next;
       j++;
   }
   if(j==i)
   return p->date;
}

【按序号查找结点的位置】

LinkList Get_LinkList(LinkList L,int i)
{
   LinkList p=L;
   int j=0;
   while(p->next!=NULL&&j<i)
   {
       p=p->next;
       j++;
   }
   if(j==i) return p;
   else return NULL;
}

【后插结点】

将s结点插入p结点的后面

（1）s->next=p->next;

（2）p->next=s;

【前插结点】

将s结点插到p的前面，与后插不同的是，先要找到 p的前驱q，然后在q之后插入，相当于q的后插

（1）while(q->next!=p)

q=q->next;

（2）s->next=q->next;

（3）q->next=s;

注：后插结点与前插结点的顺序不能颠倒，前插必须先（1）后（2），后插同理

【单链表的插入算法】

void insert_LinkList(LinkList L)//在第i个位置插入x
{
   LinkList p,s;
   int i,x;
   printf("请输入要插入的位置：");
   scanf("%d",&i);
   p=Get_LinkList(L,i-1);
   printf("请输入要插入的数据：");
   scanf("%d",&x);
   if(p==NULL)
   {
       printf("参数i错误");
   }
   else
   {
       printf("11");
       s=(LinkList)malloc(sizeof(LNode));
       s->date=x;
       s->next=p->next;
       p->next=s;
   }
}

【删除结点】

实现对结点*p的删除，找到*p的前继结点*q

q->next=p->next;

free(p);

【单链表的删除算法】

void Del_LinkList(LinkList L)//删除算法
{
   LinkList p,s;
   int i;
   printf("请输入要删除的第i个结点：");
   scanf("%d",&i);
   p=Get_LinkList(L,i-1);
   if(p==NULL)
   {
       printf("第i-1个结点不存在：");
   }
   else if(p->next==NULL)
   {
       printf("第i个结点不存在：");
   }
   else
   {
       s=p->next;
       p->next=s->next;
       free(s);
   }
}

例：实现对单链表的插入、求表长、按序号查找值、按序号查找结点的位置、在链表中随机插入以及删除链表中的任意值

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
	int date;
	struct LNode* next;
}LNode,*LinkList;
LinkList Great_LinkList3()//带头结点的尾插法 
{
	LinkList L=NULL;//头结点 
	LNode *R=NULL;//尾结点
	int x;
	L=(LNode*)malloc(sizeof(LNode));//给头结点申请空间 
	L->next=NULL;//置空表 
	R=L;
	scanf("%d",&x);
	while(x!=0)
	{
		R->next=(LNode*)malloc(sizeof(LNode));//为插入元素申请空间 
		R->next->date=x;
		R=R->next;
		scanf("%d",&x);
	 } 
	R->next=NULL;
	return L;
}
void printLink(LinkList L)//有头结点的输出 
{
	if(L->next==NULL)
	printf("表空！");
	else
	while(L->next!=NULL)
	{
		printf("%4d",L->next->date);
		L=L->next;
	}
	printf("\n");
}
int length_LinkList(LinkList L)//表长 
{
	LinkList p=L;
	int j=0;
	while(p->next)
	{
		p=p->next;
		j++;
	}
	return j;
}
int Locate_LinkList(LinkList L,int i)//按序号查找值 
{
	LinkList p=L;
	int j=0,x;
	while(p->next!=NULL&&j<i)
	{
		p=p->next;
		j++;
	}
	if(j==i)
	return p->date;
}
LinkList Get_LinkList(LinkList L,int i)//按序号查找结点位置 
{
	LinkList p=L;
	int j=0;
	while(p->next!=NULL&&j<i)
	{
		p=p->next;
		j++;
	}
	if(j==i) return p;
	else return NULL;
}
void insert_LinkList(LinkList L)//在第i个位置插入x
{
	LinkList p,s;
	int i,x;
	printf("请输入要插入的位置：");
	scanf("%d",&i); 
	p=Get_LinkList(L,i-1);
	printf("请输入要插入的数据："); 
	scanf("%d",&x);
	if(p==NULL)
	{
		printf("参数i错误");
	}
	else
	{
		printf("11");
		s=(LinkList)malloc(sizeof(LNode));
		s->date=x;
		s->next=p->next;
		p->next=s;
	}
}
void Del_LinkList(LinkList L)//删除算法 
{
	LinkList p,s;
	int i;
	printf("请输入要删除的第i个结点：");
	scanf("%d",&i); 
	p=Get_LinkList(L,i-1);
	if(p==NULL)
	{
		printf("第i-1个结点不存在："); 
	}
	else if(p->next==NULL)
	{
		printf("第i个结点不存在："); 
	}
	else
	{
		s=p->next;
		p->next=s->next;
		free(s);
	}
}
int main()
{
	LinkList a=NULL;
	int b=0,c=0;
	printf("请输入数据："); 
	a=Great_LinkList3();
	printLink(a);
	b=length_LinkList(a);
	printf("表长：%d\n",b); 
	printf("请输入要查找的元素序号：\n");
	scanf("%d",&c);
	printf("%d\n",Locate_LinkList(a,c)); 
	insert_LinkList(a);
	printf("插入后的链表：");
	printLink(a);
	Del_LinkList(a);
	printf("删除后的链表：");
	printLink(a);
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/150897.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！