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

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

#include
#include
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
#include
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     {
        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     {
        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
#include
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
	{
		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
	{
		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;
}