C语⾔实现单链表的创建及基本操作
C语⾔实现单链表的创建及基本操作
往期⽂章：
这次主要是分享⼀下数据结构中单链表的创建及基本操作，这⼀部分也是属于⽐较基础的内容。但是越基础的东西我们越要投⼊精⼒去学习，不能眼⾼⼿低。我在编写这⼀部分的内容时就出现了许多错误，这也算是⼀次查漏补缺的博客吧，下⾯我们正式开始。
1. 单链表的结构定义
⾸先我们先来看⼀下常规定义的单链表，⼀般情况下会包含数据域和指针域。例如：
typedef struct node{//单链表的结构定义
int data;//定义int类型的数据域
struct node *next;//定义指针域
}node，*linklist;
这个地⽅会出现两个让⼈⽐较迷的东西：结构指针node和linklist。本质上⽽⾔，这两种类型是等价的。通常⽤linklist说明指针变量，强调它是某个单链表的头指针变量，定义为linklist L,L表⽰头指针。node⽤来定义单链表中结点的指针，例如node *p，p为结点的指针变
量，p也可以定义为头结点。但是在⽅法的编写时，这两种定义会混合使⽤，⾮常容易迷惑我们的思维。所以我接下来的所有⽅法都只使
⽤node来定义。
2. 单链表的初始化
node *startlist(node *l){//初始化单链表并设置为空表
l=(node *)malloc(sizeof(node));
l->next=NULL;//使头结点的指针域为空，建⽴⼀个空的单链表
return l;
}
我这⾥有⼀个错误点，在⽅法体内为头结点分配内存空间的时候要注意，必须要返回指针，否则分配的内存在本⽅法运⾏结束后就会释放，相当于没分配内存。当然你也可以使⽤下⾯的⽅法，并在主函数中分配内存。
void startlist(node *l){//初始化单链表并设置为空表
l->next=NULL;//使头结点的指针域为空，建⽴⼀个空的单链表
}
int main(){
node *l,*m;
l=(node *)malloc(sizeof(node));//建⽴⼀个头结点并动态分配存储空间
return0;
}
sizeof 指针3. 头插法建⽴单链表
void creatfromhead(node *l){//利⽤头插法建⽴单链表
node *p;//新建⼀个结点指针
int i=1;
int j;
while(i!=0){
scanf("%d",&j);
if(j!=-1){
p=(node *)malloc(sizeof(node));//新建⼀个结点
p->data=j;//把输⼊的值赋值给新结点的指针域
p->next=l->next;//把新结点插⼊到表头
l->next=p;//头结点要始终放在最前⾯
}
else
{
i=0;//如果输⼊-1则结束单链表的输⼊
}
}
}
4. 尾插法建⽴单链表
void creatfromtail(node *l){//利⽤尾插法建⽴单链表
node *p;//新建⼀个结点指针
node *r;//再建⽴⼀个尾指针
int i=1;
int j;
r=l;//很重要的⼀步，令尾指针r指向头结点l，便于做尾插⼊
while(i!=0){
scanf("%d",&j);
if(j!=-1){
p=(node *)malloc(sizeof(node));//建⽴⼀个新结点
p->data=j;
r->next=p;//尾指针的指针域指向新结点p
r=p;//再让尾指针放在p后⾯，尾指针永远在最后
}
else
{
i=0;//输⼊-1则结束
r->next=NULL;//尾指针的指针域设置为空，表⽰链表的结束
}
}
}
5. 按序号查
在单链表中查第i个结点 到则返回存储位置 。
node *search1(node *l,int i){//在单链表中查第i个结点到则返回存储位置 node *p;//新建⼀个结点指针
int j=0;//建⽴⼀个计数器
if(i<=0)return NULL;//判断结点位置的合法性
p=l;//新结点p指向头结点l 从头开始扫描
while(p->next!=NULL&&j<i){
p=p->next;//指向下⼀结点
j++;//计数
}
if(i==j)return p;//到了就返回p指针
else return NULL;
}
6. 按值查
在单链表中查值为e的结点 到返回结点 。
node *search2(node *l,int e){//在单链表中查值为e的结点到返回结点
node *p;//新建⼀个结点指针
p=l->next ;//从第⼀个结点开始，既头结点后⾯那个
while(p!=NULL){
if(p->data!=e)p=p->next;//指向下个结点
else break;//到则退出循环
}
return p;//返回p指针
}
7. 求单链表的长度
这个没什么好说的，⽐较简单。
int length(node *l){//求单链表的长度
node *p;//新建⼀个结点指针
p=l->next;
int j=0;
while(p!=NULL){
p=p->next;
j++;
}
return j;//返回长度
}
8. 单链表的插⼊操作
void enterlist(node *l,int i,int e){//单链表的插⼊在第i个位置插⼊值为e的数据元素 node *p,*s;//新建两个结点指针
int k=0;
if(i<=0)printf("插⼊的位置不合理\n");
p=l;//从头开始遍历
while(p!=NULL&&k<i-1){//查第i-1个结点
p=p->next;
k++;
}
if(p==NULL){//当遍历完整个表也没到时，说明插⼊位置不合理
printf("插⼊的位置不合理\n");
}
s=(node*)malloc(sizeof(node));//新建⼀个结点S
s->data=e;
s->next=p->next;// 因为p时第i-1个结点故 s的指针域应该指向第i个结点
p->next=s;
printf("插⼊成功！\n");
}
9. 单链表的删除操作
void dellist(node *l,int i){//单链表删除操作删除第i个元素
node *p,*r;
int k=0;
p=l;
while(p->next!=NULL&&k<i-1){
p=p->next;
k++;
}
if(p->next==NULL){
printf("删除位置不合法！\n");
}
r=p->next;
p->next=r->next;//修改指针删除结点
printf("删除的元素是%d\n",r->data);
free(r);//释放内存空间
}
10. 单链表的打印
void printlist(node *l){//对单链表进⾏打印
printf("该链表的内容为：");
while(l->next!=NULL){
printf("%d ",l->next->data);
l=l->next;
}
printf("\n");
}
主函数
int main(){
node *l,*m;
l=startlist(l);
//l=(node *)malloc(sizeof(node));//建⽴⼀个头结点并动态分配存储空间//m=(node *)malloc(sizeof(node));//建⽴⼀个头结点并动态分配存储空间 m=startlist(m);
printf("单链表已初始化\n");
printf("⽤头插法插⼊链表l：\n");
creatfromhead(l);
printlist(l);
printf("⽤尾插法插⼊链表m：\n");
creatfromtail(m);
printlist(m);
printf("查链表m的第⼀个结点\n");
node *s;
s=search1(m,1);
printf("该结点的值为%d\n",s->data);
printf("在链表m的第⼆个位置插⼊1\n");
enterlist(m,2,1);
printlist(m);
printf("删除链表m第⼆个位置的值\n");
dellist(m,2);
return0;
}
运⾏截图：
总结
写博客是指⼀种良好的习惯，可以促进并深化我们对知识的了解与运⽤。代码这种东西还是熟能⽣巧，养成良好的学习习惯才能让我们在求学之路上⾛的更远，加油加油！下期可能会写循环链表或者是栈，慢慢来吧。。。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。