C/C++版数据结构之链表

时间:2023-01-07 11:40:43

     今天来讨论下链表中的双向链表。

双向链表:

      概念:在双向链表中,结点除含有数据域外,还含有两个指针域:一个存储直接后继结点的地址,称为右链域;另一个存储直接前驱结点的地址,称为左链域。

typedef struct node
{
int num; //数值域
struct node *lnext; //左链域指针
struct node *rnect; //右链域指针
}stud;

 


      双向链表常用算法:

 

先对三个指针作个声明:

 

head:用来指向链表的头部。链表需要一个指针来标识,这就是头指针。

 

p1:用来指向新结点,以及用来遍历链表的每一个结点。

 

p2:用来指向当前结点。

 

(1)双向链表创建算法

创建结点数目为n的双向链表:

 

 

typedef struct node
{
int num; //数值域
struct node *lnext; //左链域指针
struct node *rnect; //右链域指针
}stud;

stud* Create(int n)
{
stud *head,*p1,*p2;
head=p1=p2=NULL;
for(int i=0;i<n;i++)
{
p1=(stud*)malloc(sizeof(stud));
p1->num=i;
if(i==0)
{
head=p1;
head->lnext=NULL;
}
else
{
p2->rnext=p1
p1->lnext=p2;
}
p2=p1;
}
p2->rnext=null;
return head;
}

 

(2)双向链表的查找算法

(一)头结点输入双向链表查找算法

 

typedef struct node
{
int num; //数值域
struct node *lnext; //左链域指针
struct node *rnect; //右链域指针
}stud;

stud* Find_FormHead(stud *head,int i)
{
stud *p1;
p1=head;
while(p1!=NULL)
{
if(i==p1->num)
{
break;
}
else
{
p1=p1->rnext; //遍历链表
}
}
return p1;
}

 

(二)无序双向链表查找算法

 

typedef struct node
{
int num; //数值域
struct node *lnext; //左链域指针
struct node *rnect; //右链域指针
}stud;
//p是链表中任一个结点指针,i是要查的号码

stud* Find_NoSort(stud *p,int i)
{
stud *p1;
p1=p;

//先住右遍历
while(p1!=NULL)
{
if(i==p1->num)
{
break;
}
else
{
p1=p1->rnext;
}
}

//往左遍历
if(p1==NULL)
{
p1=p;
while(p1!=NULL)
{
if(i==p1->num)
{
break;
}
else
{
p1=p1->lnext;
}
}
}
return p1;
}

 

(三)有序双向链表查找算法(从小到大

 

typedef struct node
{
int num; //数值域
struct node *lnext; //左链域指针
struct node *rnect; //右链域指针
}stud;

stud* Find_IsSort(stud *p,int i)
{
stud *p1;
p1=p;
while(p1!=NULL)
{
if(i==p1->num)
{
break;
}
else
{
if(i > p1->num) //往右遍历
{
p1=p1->rnext;
}
else
{
p1=p1->lnext; //往左遍历
}
}
}
return p1;
}

 

(3)双向链表的删除算法

(一)头指针输入双向链表删除算法

 

typedef struct node
{
int num; //数值域
struct node *lnext; //左链域指针
struct node *rnect; //右链域指针
}stud;

bool Delete_FormHead(stud *head,int i)
{
bool flag=false;
if(head)
{
stud *p1,*p2;
while(p1->num!=i && p1->rnext!=NULL)
{
p2=p1;
p1=p1->rnext;
}
if(p1->num==i)
{
if(p1==head)
{
head=p1->rnext;
}
else
{
p2->rnext=p1->rnext;
}
free(p1); //释放已经脱离链表的结点内存
flag=true;
}
}
return flag;
}

 

(二)无序双向链表删除算法

 

typedef struct node
{
int num; //数值域
struct node *lnext; //左链域指针
struct node *rnect; //右链域指针
}stud;

bool Delete_NoSort(stud *p,int i)
{
bool flag=false;
if(p)
{
stud *p1,*p2;

//往右遍历
while(p1!=NULL)
{
if(i==p1->num)
{
break;
}
else
{
p2=p1;
p1=p1->rnext;
}
}

//往左遍历
while(p1!=NULL)
{
if(i==p1->num)
{
break;
}
else
{
p2=p1;
p1=p1->lnext;
}
}
}
if(p1->num == i)
{
if(p1=p)
{
p=p1->rnext;
}
else
{
p2->rnext=p1->rnext;
}
free(p1)
flag=true;
}
return flag;
}

 

(三)有序双向链表删除算法

 

typedef struct node
{
int num; //数值域
struct node *lnext; //左链域指针
struct node *rnect; //右链域指针
}stud;

bool Delete_IsSort(stud *p,int i)
{
bool flag=false;
if(p)
{
stud *p1,*p2;
while(p1->num!=i && p1!=NULL)
{
p2=p1;
if(i > p->num) //往右遍历
{
p1=p1->rnext;
}
else //往左遍历
{
p1=p1->lnext;
}
}
if(p1->num==i)
{
if(p1==p)
{
p=p1->rnext;
}
else
{
p2->rnext=p1->rnext;
}
free(p1); //释放已经脱离链表的结点内存
flag=true;
}
}
return flag;
}

 

(4)双向链表的插入算法

(一)双向链表通用插入算法

说明:p0为输入的链表指针,p为插入的结点地址

 

typedef struct node
{
int num; //数值域
struct node *lnext; //左链域指针
struct node *rnect; //右链域指针
}stud;

stud *Insert(stud *p0,stud *p)
{
stud *p1,*p2;
p1=p0;

if(!p0)
{
p0=p;
p->rnext=NULL;
p->lnext-NULL;
}
else
{
//往右遍历
if(p->num > p1->num)
{
while(p->num > p1->num && p1->rnext!=NULL)
{
p2=p1;
p1=p1->rnext;
}

if(p->num < p1->num)
{
if(p0==p1)
{
p0=p;
}
else
{
p2->rnext=p;
p->rnext=p1;
}
}
else //把p插入链表尾部
{
p1->rnext=p;
p->rnext=NULL;
}
}

//往左遍历
else
{
while(p->num < p1->num && p1->lnext!=NULL)
{
p2=p1;
p1=p1->lnext;
}
if(p->num > p1->num)
{
if(p0==p1)
{
p0=p;
}
else
{
p2->lnext=p;
p->lnext=p1;
}
}
else //把这插入链表头部
{
p1->lnext=p;
p->lnext=NULL;
}
}
}
return p0;
}

 

 

(二)头结点输入双向链表插入算法

 

typedef struct node
{
int num; //数值域
struct node *lnext; //左链域指针
struct node *rnect; //右链域指针
}stud;

stud* Insert_FormHead(stud *head,stud *p)
{
stud *p1,*p2;
p1=head;
if(!head)
{
head=p;
p->rnext=NULL;
}
else
{
while(p->num > p1->num && p1->rnext!=NULL)
{
p2=p1;
p1=p1->next;
}
if(p->num < p1->num)
{
if(head==p1)
{
head=p;
}
else
{
p2->rnext=p;
p->rnext=NULL;
}
}
else //将p插入链表尾部
{
p1->rnext=p;
p->rnext=NULL;
}
}
return head;
}

 

 

相关文章:

 

  •  C/C++版数据结构之链表<一>

 

  •  C/C++版数据结构之链表<二>

 

  •  C/C++版数据结构之链表<三>