程序员入门
第三章：双向链表带头
学习大纲
- 程序员入门
- 前言
- 一、双链表结构图示
- 二、代码区域
- 1.定义结点结构
- 2，初始化头结点
- 3、创建一个结点
- 4、打印节点信息
- 5、修改结点信息
- 6、删除一个结点
- 7、给链表排序
- 8、主函数
前言
Hello!大家好！这里是小新，上一章我们学习了如何用C语言写一个带头的单链表，本章我们将学习如何用C语言写一个带头的双向链表
提示：本章的内容包含链表的增，删，改，查，排序等……
一、双链表结构图示
这里再次说明一下，使用有头结点的链表会让整个链表操作起来更加方便，容易，缺点是新手想要理解他并不是很容易。
二、代码区域
1.定义结点结构
代码如下（示例）：
#include <stdio.h>
#include <stdlib.h>
typedef struct Node *Head;
typedef struct Node list;
struct Node
{
int data;
struct Node *next;//指向下一个结点
struct Node *prior;//指向上一个结点
};
//下面是主函数
int main(int argc, char **argv)
{
Head head = NULL;
return 1;
}
2，初始化头结点
代码如下（示例）：
void head_Init(Head *head)//初始化链表
{
(*head)=(list *)malloc(sizeof(list));
(*head)->next=(*head);
(*head)->prior=(*head);
}
3、创建一个结点
void c_double_list(Head head,int a)//创建一个链表
{
list *p,*q;
q = head;
p=(list *)malloc(sizeof(list));
p->data = a;
while(q->next != head)//找的最后一个位置
{
q=q->next;
}
p->prior =q;
q->next = p;
p->next = head;
return ;
}
4、打印节点信息
void list_d_print(Head head)//打印
{
list *p;
int i=0;
p=head->next;
while(p!=head)
{
printf("第%d个结点%d\n",++i,p->data);
p=p->next;
}
return ;
}
5、修改结点信息
void s_double_list(Head head,int set_n)//修改数据
{
list *p = head->next;
int a=0;
while(p!=head)
{
if(p->data==set_n)
{
printf("将当前值%d 修改为",p->data);
scanf("%d",&a);
p->data = a;
printf("修改成功\n");
return;
}
p=p->next;
}
return;
}
6、删除一个结点
void del_double_list(Head head,int del_n)//删除数据
{
list *p=head->next;
if(p->next==p)
{
printf("这是一个空链表！！！！\n");
return;
}
while(p!=head)//如果没有执行这个，要么是空，要么是没有
{
if(p->data==del_n)
{
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
p=NULL;
return ;
}
p=p->next;
}
printf("没有找到这条链表！！\n");
return;
}
7、给链表排序
第一章：C语言单链表入口【点击学习】
这里排序和之前单链表的排序方法基本相同，但是主体是加入了头结点，所以在某些地方有些不同，我们可以先通过上方链接学习单链表的排序方法，下面让我们看组图示
原链表每次取出头结点后的第一个结点，并打断这个结点与原链表之间的联系，同时，头结点指向已经打断结点的下一个结点，循环以往。打断的结点将进入新的子函数去组成新的排序链表，直到排完所有结点，将原链表的头结点加到新链表的头部
：注意：这整个过程中，因为处理的是头结点的下一个结点，所以我们始终都能找到原链表的头结点
void rank_d_list(Head head)//排序
{
list *p=head->next;
list *new = NULL; //新头
if(p==p->next)
{
printf("空链表！！1\n");
return;
}
while(head!=head->next)//当链表只剩头的时候
{
head->next=p->next;
p->next->prior=head;
p->next=NULL;
p->prior=NULL;
rank(&new,p);//头部没有传入
p=head->next;
}
//组装成一条带头链表
head->next=new;
new->prior=head;
while(new->next)
{
new=new->next;
}
new->next=head;
return;
}
void rank(list **new,list *n)//新链表头插尾插:相当于新建立一个链表
{
list *p = *new;//new为一个不带头的正常的链表
list *q = NULL;//记录之前的位置
while(p)
{
if(p->data>n->data)
{
if(p==*new)//第一个位置找到了，插入前面
{
n->next=*new;
(*new)->prior=n;
}
else
{
n->prior=p->prior;
p->prior->next=n;
n->next=p;
p->prior=n;
}
return;
}
q=p;
p=p->next;//链表中找不到，但是当前位置已经移动到了最后，现在P的地址为空
}
if(*new==NULL)
{
*new=n;
}
else//没有找到直接插入队尾
{
q->next=n;
n->prior=q;
n->next=NULL;
}
return;
}
8、主函数
int main(int argc, char **argv)
{
Head head = NULL;
int i=0;
head_Init(&head);//初始化
for(i=1;i<=5;i++)//创建结点
{
c_double_list(head,i);
c_double_list(head,i*5);
}
list_d_print(head);//打印节点
rank_d_list(head);//给节点排序
s_double_list(head,5);//修改数据为5的结点
list_d_print(head);//打印结点点
del_double_list(head,10);//删除数据为10的结点
list_d_print(head);//打印结点
return 1;
}
上一章：单链表带头【点击学习】
下一章：用C语言写一条“挂帘“链表【点击学习】
QQ群链接：928357277
更多推荐
C语言双链表带头
发布评论