单链表(c语言实现)贼详细

直接上代码吧

#include<stdio.h>
#include<malloc.h>
/*
单链表特点:
它是一种动态的储存结构,链表中每个节点占用的储存空间不是预先分配的,而是运行时系统根据需求生成的
*/
typedef struct lnode
{
int data;
struct lnode *next;
}lnode,*linklist;
//结点定义
/*
关于头指针的一点说明:
linklist L;
外面用头指针来标识一个单链表,如单链表L,单链表H等,是指链表的第一个节点的地址被记录在指针变量L,H中,头指针为NULL
时,表示一个空的单链表,需要进一步指出的是:上面定义的lnode是节点的类型,linklist是指向lnode节点的指针的类型,
为了增强程序的可读性,通常将标识一个链表的头指针说明为linklist类型的变量
*/
linklist creat_linklist_insert_head_nohead()
{
linklist l=NULL;//定义头指针变量l
lnode *s;//新建一个节点
int flag=-;//输入停止标志位
printf("输入整型数据,数据以空格隔开,输入数据为-1的时候表示输入截止\n");
while()
{
int x;
scanf("%d",&x);
if(x==flag)
break;
s=(lnode*)malloc(sizeof(lnode));//对s节点申请储存空间
s->data=x;//赋值
s->next=l;//s节点的next指向头指针
l=s;//头指针指向新建立的s节点,因为这是在单链表的头部插入数据
}
return l;
}//创建一个单链表,通过在头部插入数据,不含空的头节点
//-------------------------------------------------------------------------------------------------------------//
/*在单链表的表头插入,只要x!=flag,就是一直申请s结点,从而可以一直在表头插入,
其中l=s是最重要的,因为这是将s插入到l的表头,因为是在头部插入,所以只要一个头指针就可以,
若是在单链表的尾部插入,那么就需要尾部指针
关于此函数使用的一点说明:
我们输入数据 1 2 3 4 5的时候,输出的是 5 4 3 2 1,因为我们是在头部插入数据的
*/
//-------------------------------------------------------------------------------------------------------------//
linklist creat_linklist_insert_end_yeshead()
{
linklist l=NULL,r=NULL;//定义头指针变量和尾指针变量
lnode *s;//定义新建节点
int flag=-;//输入结束标志位
printf("输入整型数据,数据以空格隔开,输入数据为-1的时候表示输入截止\n");
while()
{
int x;
scanf("%d",&x);
if(x==flag)//输入数据等于输入结束标志位则跳出循环
break;
s=(lnode*)malloc(sizeof(lnode));//申请内存空间
s->data=x;//赋值
if(l==NULL)//单链表为空
l=s;//则将头指针指向新建节点
else
r->next=s;//不空的话则将尾指针的next指向s,因为如果不空的话,尾指针指向的肯定是一个数据节点,尾指针的next指向s是为了将两个数据节点连接起来
r=s;//尾指针移动到新插入的节点上
}
if(r!=NULL)//有数据
r->next=NULL;//尾指针的next指向空,说明尾指针后面没有数据了,目的的为了保证单链表尾指针逻辑的合理性
return l;
}//建立单链表且在链表尾部插入数据,含空的头节点
//-----------------------------------------------------------------------------------------------------------------------//
/*在单链表的尾部插入,只要没有输入结束的标志,就一直申请s结点,然后把x赋给s结点的data域,
l=s是为了第一个结点的结点的处理,因为在此之前l是一个空表,然后因为不断有新的结点生成,所以就是不断把新的s结点赋给r的next,
这样就不断有s结点加入到了单链表中间,然后最重要的是每次新的结点加入到单链表中后要把r尾指针向后面移动,就是文中的r=s;
关于此函数的一点说明:
输入数据 1 2 3 4 5,输出还是 1 2 3 4 5,而不是 5 4 3 2 1,因为我们插入数据是在链表尾部插入的
*/
//-----------------------------------------------------------------------------------------------------------------------//
int length_linklist_yeshead(linklist l)
{
linklist p=l;
int j=;
while(p->next)
{
j++;
p=p->next;
}
return j;
}//求单链表的表长,针对含有空的头节点的单链表
int length_linklist_nohead(linklist l)
{
lnode *p=l;
int j=;
while(p)
{
j++;
p=p->next;
}
return j;
}//求链表的表长,针对不含空的头节点的单链表
lnode *get_linklist(linklist l,int i)
{
lnode *p=l;
int j=;
while(p!=NULL&&j<i)
{
p=p->next;
j++;
}
if(j==i)
return p;
else
return NULL;
}//单链表的查找第i个元素结点,*p=l就是使p指针指向l链表;
lnode *locate_linklist(linklist l,int x)
{
lnode *p=l->next;//l为头节点
while(p!=NULL&&p->data!=x)
p=p->next;
return p;
}//单链表查找值为x的结点,找到后返回指向这个结点的指针;以后时刻要记得l为头指针,因为定义了头指针比没有定义头指针要方便许多;
int insert_linklist(linklist l,int i,int x)
{
lnode *p,*s;
p=get_linklist(l,i-);//找到第i-1个结点
if(p==NULL)
{printf("i错误");return ;}
else
s=(lnode*)malloc(sizeof(lnode));
s->data=x;
s->next=p->next;
p->next=s;
return ;
}//单链表的第i个结点后面的插入,重要的是申请,封装s结点,
int del_linklist(linklist l,int i)
{
i--;
linklist p,s;
p=get_linklist(l,i-);
if(p==NULL)
{
printf("该i-1节点不存在");
return -;
}
else if(p->next==NULL)
{
printf("第i个结点不存在");
return ;
}
else
{
s=p->next;
p->next=s->next;
free(s);
return ;
}
}//单链表中删除第i个结点,那么就先要找到i个结点的前驱,也就是第i-1个结点,同理单链表中的插入也要知道其前驱结点,所以单链表中的头节点的重要性就可想而知了
void printf_linklist(lnode *plisthead)
{
lnode *ptemp=plisthead;
while(ptemp)
{
printf("%d\t",ptemp->data);
ptemp=ptemp->next;
}
printf("\n");
}//链表打印函数
int main()
{
/*
linklist l=creat_linklist_insert_end_yeshead();
printf("%d\n",length_linklist_yeshead(l));
insert_linklist(l,2,100);//第二个结点的后面插入100
printf_linklist(l);
del_linklist(l,4);//删除第四个结点
printf_linklist(l);
*/
/*
linklist l=creat_linklist_insert_head_nohead();
printf("%d\n",length_linklist_nohead(l));
insert_linklist(l,2,100);
printf_linklist(l);
del_linklist(l,4);
printf_linklist(l);
*/
return ;
}
上一篇:LeetCode 26. Remove Duplicates from Sorted Array (从有序序列里移除重复项)


下一篇:LoadRunner 11 安装破解