发布作者： 北流泉
百度收录： 正在检测是否收录...
作品采用： 《 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 》许可协议授权
【数据结构】双向链表定义和基本操作
2022年11月11日 6阅读 0评论 0点赞
双向链表： 双向链表的定义：
`typedef struct DuLNode{LElemType data;
struct DuLNode *next;
struct DuLNode *pre;
DuLNode ( LElemType Data=0,struct DuLNode *Pre=NULL,struct DuLNode *Next=NULL){
data=Data;
next=Next;
pre=Pre;
}
}DuLNode,*DuLinkList;
`
双向链表基本操作的实现：
（1）、初始化操作 ( &L )
（2）、建立单链表的操作 （&L , n）
（3）、判断一个线性表是否为空表(L)
（4）、求线性表的长度( L )
（5）、取线性表中的第i个元素(L,i,&e)
（6）、查找元素e在线性表中的位序(L,e)
（7）、插入操作(&L,i,e)
（8）、删除操作(&L,i,&e)
（1）、初始化操作 ( &L )
`void InitDuLinkList(DuLinkList &L){L=new DuLNode;
}`
（2）、建立单链表的操作 （&L , n）
`void CreateLinkList_Tail(DuLinkList &L,int n=0){ //尾插法L=new DuLNode;
DuLinkList Pre=L,p;
LElemType data;
for(int i=1;i>data;
p=new DuLNode(data,Pre);
Pre->next=p;
Pre=p;
}
}`
`void CreateLinkList_Head(DuLinkList &L ,int n=0){//头插法L=new DuLNode;
DuLinkList Pre=L,p,s;
LElemType data;
for(int i=1;i>data;
p=new DuLNode(data,Pre,Pre->next);
s=Pre->next;
if(s)
s->pre=p;
Pre->next=p;
}
}`
（3）、判断一个线性表是否为空表(L)
`int ListIsEmpty(DuLinkList &L){if(L->next){
return 1;
}return 0;
}`
（4）、求线性表的长度( L )
`int ListLength(DuLinkList L){int len=0;
DuLinkList p=L->next;
while(p){
len++;
p=p->next;
}
return len;
}`
（5）、取线性表中的第i个元素(L,i,&e)
`void GetElem(DuLinkList L,int i,LElemType &e){int j=1;
DuLinkList p=L->next;
while(p&&jnext;
}
if(j>i||!p){
printf("");
return ;
}
e=p->data;
}`
（6）、查找元素e在线性表中的位序(L,e)
`LElemType LocateElem(DuLinkList L, LElemType e){int j=1;
DuLinkList p=L->next;
while(p&&p->data!=e){
j++;
p=p->next;
}
if(!p){
printf("LocateElem not found %d\n",e);
return -1;
}
return j;
}`
（7）、插入操作(&L,i双向链表结构双向链表结构,e)
`void ListInsert(DuLinkList L, int i, LElemType e){![双向链表结构_链表结构_双向动态链表元素删除][1]
int j=0;
DuLinkList p=L,s;
while(p&&jnext;
}
if(!p||i-1next)){ //插入位置不能是最后
printf("ListInsert index %d error\n",i);
return ;
}
s=new DuLNode(e,p,p->next);
(p->next)->pre=s;
s->pre=p;
p->next=s;
}`
（8）、删除操作(&L,i,&e)
`void ListDelete(DuLinkList &L,int i,LElemType &e){int j=0;
DuLinkList p=L,s;
while(p->next&&jnext;
}
if(!p->next||inext;
p->next=s->next;
(s->next)->pre=p;
e=s->data;
delete s;
}`
完整的测试代码
#includeinclude
include
include
define LElemType int
using namespace std;
typedef struct DuLNode{
LElemType data;
struct DuLNode *next;
struct DuLNode *pre;
DuLNode ( LElemType Data=0,struct DuLNode *Pre=NULL,struct DuLNode *Next=NULL){
data=Data;
next=Next;
pre=Pre;
}
}DuLNode,*DuLinkList;
void InitDuLinkList(DuLinkList &L){
L=new DuLNode;
}
void CreateLinkList_Tail(DuLinkList &L,int n=0){ //尾插法
L=new DuLNode;
DuLinkList Pre=L,p;
LElemType data;
for(int i=1;i>data;
p=new DuLNode(data,Pre);
Pre->next=p;
Pre=p;
}
}
void CreateLinkList_Head(DuLinkList &L ,int n=0){//头插法
L=new DuLNode;
DuLinkList Pre=L,p,s;
LElemType data;
for(int i=1;i>data;
p=new DuLNode(data,Pre,Pre->next);
s=Pre->next;
if(s)
s->pre=p;
Pre->next=p;
}
}
void OutputDuLinkList(DuLinkList &L){
DuLinkList p=L->next,t;
printf("按顺序输出\n");
while(p){
printf("%d\n",p->data);
t=p;
p=p->next;
}
printf("按逆序输出\n");
p=t;
while(p->pre){
printf("%d\n",p->data);
p=p->pre;
}
}
int ListIsEmpty(DuLinkList &L){
if(L->next){
return 1;
}return 0;
![链表结构_双向链表结构_双向动态链表元素删除][2] } int ListLength(DuLinkList L){ int len=0; DuLinkList p=L->next; while(p){ len++; p=p->next; } return len; } void GetElem(DuLinkList L,int i,LElemType &e){ int j=1; DuLinkList p=L->next; while(p&&jnext; } if(j>i||!p){ printf(""); return ; } e=p->data; } LElemType LocateElem(DuLinkList L, LElemType e){ int j=1; DuLinkList p=L->next; while(p&&p->data!=e){ j++; p=p->next; } if(!p){ printf("LocateElem not found %d\n",e); return -1; } return j; } void ListInsert(DuLinkList L, int i, LElemType e){ int j=0; DuLinkList p=L,s; while(p&&jnext; } if(!p||inext); (p->next)->pre=s; p->next=s; } void ListDelete(DuLinkList &L,int i,LElemType &e){ int j=0; DuLinkList p=L,s; while(p->next&&jnext; } if(!p->next||inext; p->next=s->next; (s->next)->pre=p; e=s->data; delete s; } int main() { DuLinkList La; LElemType e=0,t; CreateLinkList_Tail(La,5); //CreateLinkList_Head(La,5); OutputDuLinkList(La); printf("len=%d\n",ListLength(La)); for(int i=1;i [1]: https://oscimg.oschina.net/oscnet/up-ba1fe84c1f566a91231c8d17217c9c45730.png [2]: https://img-blog.csdnimg.cn/20200103102453372.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9hcnRpc2FuLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70 [3]: https://xfums.cn/index.php/archives/44/
人生倒计时
—— 评论区 ——