双链表

glory-yl 2021-04-05 原文

c语言实现的双链表结构，包括插入，查找，删除，清空，销毁等基本操作

代码如下：


#include<stdio.h>
#include<stdlib.h>
typedef struct student
{
char name[10];
int age;
}student;

typedef student Student;

typedef struct LNode
{
Student data;
struct LNode *next,*prior;
}LNode;

//初始化双链表
void InitList(struct LNode*L)
{
L=(LNode*)malloc(sizeof(LNode));
if (!L)
{
printf("双链表初始化失败！\n");
exit(1);
}
L->prior=L;
L->next=L;

return;
} 
//尾插法创建双链表 
LNode* creatList(struct LNode*L)
{
LNode *s,*p;
p=L;
printf("请输入学生的姓名和年龄，当输入的年龄<=0时链表创建成功，最后的元素不接入链表中\n");
s=(LNode*)malloc(sizeof(LNode));
scanf("%s%d",&s->data.name,&s->data.age); 
while (s->data.age>0)
{
p->next=s;
s->prior=p;
s->next=NULL;
p=s;
printf("请输入学生的name,age:\n");
s=(LNode*)malloc(sizeof(LNode));
scanf("%s%d",&s->data.name,&s->data.age);

}
printf("链表创建成功！\n");

return L;
}

//双链表的查询
Student searchList(struct LNode*L,int i)
{
int j;
LNode *p=L;
Student stu;
if (i<0)
{
printf("查询越界！\n");
exit(1);
}
j=0;
while (p->next!=NULL)
{
p=p->next;
j++;
if(j==i)
{
stu=p->data;
break;
}
}
return stu;
} 

//双链表的插入
LNode* InsList(struct LNode*L,int i,Student stu)
{
LNode *p,*s;
p=L;
int j;
if (i<1)
{
printf("插入越界!\n");
exit(1);
}

j=0;
while(p->next!=NULL)
{ 
if (j==i-1)
{
s=(LNode*)malloc(sizeof(LNode));
s->data=stu;
s->next=p->next;
p->next->prior=s;
p->next=s;
s->prior=p;
printf("在第%d个位置插入元素成功!\n",i);
break;
}


}
return L;
} 

//双链表的长度
int Length(struct LNode*L)
{
LNode *p=L; 
int i;
i=0;
while (p->next!=NULL)
{
p=p->next;
i++;
}
return i;
} 

//双链表的删除
Student DelList(struct LNode*L,int i)
{
LNode *p,*s;
int j;
Student stu;
p=L;
if (i<1)
{
printf("插入越界！\n");
exit(1);
}

j=0;
while (p->next!=NULL)
{
p=p->next;
j++; 
if (j==i)
{
s=p;
stu=s->data;
p->next->prior=p->prior;
p->prior->next=p->next;
printf("成功删除第%d个元素，它的name:%s和age:%d\n",i,stu.name,stu.age);
free(s);
}


}
return stu;
}

//清空双链表
void ClearList(struct LNode*L)
{
LNode *p,*r;
p=L;
while (p)
{
p=p->next;
r=p;
free(p);
p=r;
}	
L->next=NULL;
} 

//销毁双链表
void DestroyList(struct LNode*L)
{
LNode *head,*r;
head=L;
while (head)
{
r=head->next;
free(head);
head=r;
}
} 

void main()
{
LNode L;
LNode *r;
r=&L;
InitList(r);
creatList(r);

Student stu;
printf("请输入插入第一个位置的元素，它的name和age:\n");
scanf("%s%d",&stu.name,&stu.age);
InsList(r,1,stu);
ClearList(r);
printf("清空双链表成功！\n");
int l=Length(r);
printf("双链表长度：%d\n",l);
DelList(r,1);
//按双链表顺序输出 （尾插法） 
while (r->next!=NULL)
{
r=r->next;
printf("name:%s,age:%d\n",r->data.name,r->data.age);
}
}