目录
1.双链表
2.双链表的相关操作
(1)数据结构的定义
(2)初始化和销毁
(3)判断空和表的长度
(4)节点的后插操作
(5)按序查找第i个节点和按值查找节点
(6)定位删除和按序删除
(7)打印操作
(8)主函数
(9)测试
1.双链表
相对于单链表来说就是多一个前驱的指针prior,指向前一个节点(主要是为了方便删除和插入)。
注:由于之前的实现的单链表总是会遇到一种情况就是,如果要删除当前的节点p的话,那么只能通过一种技巧的方式计算交换值;但是如果是需要进行更加复杂的操作的话,就会比较麻烦,可能还需要辅助的指针r来指向当前节点的前驱,这会给程序写起来和理解起来带来不便,所以为了实现当前节点能够访问前驱节点,那么提出了双链表的概念。
使用C语言实现单链表(带头结点)
使用C语言实现单链表(不带头结点)
2.双链表的相关操作
(1)数据结构的定义
#include
#include
#define MAXSIZE 10
typedef int ElemType;
typedef struct DNode {
ElemType data;
struct DNode*prior,*next;
}DNode,*DLinkList;
//清单列表
void MenuLinkList(){
printf("-------------1.插入操作-------------n");
printf("-------------2.定位插入操作---------n");
printf("-------------3.按序查找操作---------n");
printf("-------------4.按值查找操作---------n");
printf("-------------5.定位删除操作---------n");
printf("-------------6.按值删除元素---------n");
printf("-------------7.删除整个表元素节点---n");
printf("-------------8.表的长度-------------n");
printf("-------------9.打印操作-------------n");
printf("-------------10.结束操作-------------n");
}
(2)初始化和销毁
//初始化操作
void InitDLinkList(DLinkList&L){
L=(DNode*)malloc(sizeof(DNode));
if(L==NULL){
printf("申请空间失败!n");
return ;
}
L->prior=NULL;
L->next=NULL;
printf("申请空间成功!n");
}
//销毁表(头节点不销毁)
DNode* DestryDLinkList(DNode*p,DLinkList&L,int flag=9){
//从尾部开始删除节点
DNode*r=p;
while(r!=L){
DNode*s=r;
r=r->prior;
r->next=s->next;
free(s);
}
//如果是结束操作的话,直接将头节点释放
if(flag==10){
free(L);
L=NULL;
}
return r;
}
这里的销毁操作主要是从最后节点开始进行删除,更加的方便,如果从头结点开始删除的话,需要判断的条件更多,相对麻烦一点,所以采用这种方法。读者自己可以实现从前往后的删除操作。
(3)判断空和表的长度
//判空
bool Empty(DLinkList L){
if(L->next==NULL){
return true;
}else{
return false;
}
}
//表的长度
int DLinkListLength(DLinkList L){
int len=0;
DNode*p=L->next;
while(p!=NULL){
len++;
p=p->next;
}
return len;
}
(4)节点的后插操作
#include#include #define MAXSIZE 10 typedef int ElemType; typedef struct DNode { ElemType data; struct DNode*prior,*next; }DNode,*DLinkList; //清单列表 void MenuLinkList(){ printf("-------------1.插入操作-------------n"); printf("-------------2.定位插入操作---------n"); printf("-------------3.按序查找操作---------n"); printf("-------------4.按值查找操作---------n"); printf("-------------5.定位删除操作---------n"); printf("-------------6.按值删除元素---------n"); printf("-------------7.删除整个表元素节点---n"); printf("-------------8.表的长度-------------n"); printf("-------------9.打印操作-------------n"); printf("-------------10.结束操作-------------n"); }
(2)初始化和销毁
//初始化操作
void InitDLinkList(DLinkList&L){
L=(DNode*)malloc(sizeof(DNode));
if(L==NULL){
printf("申请空间失败!n");
return ;
}
L->prior=NULL;
L->next=NULL;
printf("申请空间成功!n");
}
//销毁表(头节点不销毁)
DNode* DestryDLinkList(DNode*p,DLinkList&L,int flag=9){
//从尾部开始删除节点
DNode*r=p;
while(r!=L){
DNode*s=r;
r=r->prior;
r->next=s->next;
free(s);
}
//如果是结束操作的话,直接将头节点释放
if(flag==10){
free(L);
L=NULL;
}
return r;
}
这里的销毁操作主要是从最后节点开始进行删除,更加的方便,如果从头结点开始删除的话,需要判断的条件更多,相对麻烦一点,所以采用这种方法。读者自己可以实现从前往后的删除操作。
(3)判断空和表的长度
//判空
bool Empty(DLinkList L){
if(L->next==NULL){
return true;
}else{
return false;
}
}
//表的长度
int DLinkListLength(DLinkList L){
int len=0;
DNode*p=L->next;
while(p!=NULL){
len++;
p=p->next;
}
return len;
}
(4)节点的后插操作
//判空 bool Empty(DLinkList L){ if(L->next==NULL){ return true; }else{ return false; } } //表的长度 int DLinkListLength(DLinkList L){ int len=0; DNode*p=L->next; while(p!=NULL){ len++; p=p->next; } return len; }
(4)节点的后插操作
//节点的插入操作(后插) DNode* InsertDLinkList(DNode*p,ElemType e){ if(p==NULL){ printf("插入的节点不合法!n"); return NULL; } DNode*s=(DNode*)malloc(sizeof(DNode)); s->data=e; s->next=p->next; p->next=s; s->prior=p; printf("插入节点成功!n"); return s; } //在第i个位置插入节点 void InsertIDLinkList(DLinkList&L,int i,ElemType e){ DNode*p=FindDNode(L,i); //如果是插入到尾节点 if(p->next==NULL){ InsertDLinkList(p,e); return ; } //插入到中间的节点 if(p!=NULL){ DNode*s=(DNode*)malloc(sizeof(DNode)); s->data=e; s->next=p->next; p->next->prior=s; p->next=s; s->prior=p; printf("插入节点成功!n"); return ; } }
(5)按序查找第i个节点和按值查找节点
//查找第i个位序的节点
DNode*FindDNode(DLinkList L,int i){
if(L==NULL){
printf("表为空!n");
return NULL;
}
if(i<0||i>DLinkListLength(L)){
printf("查找的位置不正确!n");
return NULL;
}
int j=1;
DNode*p=L->next;
while(p!=NULL&&jnext;
j++;
}
return p;
}
//按值查找操作
DNode*FindDElem(DLinkList L,ElemType e){
if(L==NULL){
printf("表为空!n");
return NULL;
}
DNode*p=L->next;
while(p->data!=e){
p=p->next;
}
return p;
}
(6)定位删除和按序删除
//定位删除节点 void DeleteDLNode(DLinkList&L,int i,ElemType&e){ DNode*p=FindDNode(L,i); e=p->data; //如果是尾节点直接删除 if(p->next==NULL){ p->prior->next=p->next; free(p); return ; } if(p!=NULL){ DNode*s=p; p->prior->next=s->next; p->next->prior=s->prior; free(s); return ; } } //按值删除 void DeleteDElem(DLinkList&L,ElemType e){ DNode*p=FindDElem(L,e); //如果是尾节点直接删除 if(p->next==NULL){ p->prior->next=p->next; free(p); return ; } if(p!=NULL){ DNode*s=p; p->prior->next=s->next; p->next->prior=s->prior; free(s); return ; } }
(7)打印操作
//打印
void PrintDLinkList(DLinkList L){
DNode*p=L->next;
while(p!=NULL){
printf("%dt",p->data);
p=p->next;
}
printf("n");
}
(8)主函数
int main(){ DLinkList L; InitDLinkList(L); //对顺序表进行插入操作 ElemType x; int flag=-1; DNode*p=L; //各种操作 while(1) { int i=0; ElemType e=0; MenuLinkList(); printf("请输入操作: "); scanf("%d",&flag); int len=0; DNode*s; switch(flag){ case 1: printf("请输入元素(-1_end): "); scanf("%d",&x); while(x!=-1) { p=InsertDLinkList(p,x); printf("请输入元素(-1_end): "); scanf("%d",&x); } break; case 2: printf("请输入元素插入位置: n"); scanf("%d",&i); printf("请输入元素: "); scanf("%d",&x); InsertIDLinkList(L,i,x); break; case 3: printf("请输入查找元素位置: "); scanf("%d",&i); s=FindDNode(L,i); if(s!=NULL){ printf("查找的元素为 = %dn",s->data); } break; case 4: printf("请输入要查找的值: "); scanf("%d",&x); s=FindDElem(L,x); if(s!=NULL){ printf("查找的元素存在!n"); }else{ printf("查找的元素不存在!n"); } break; case 5: printf("请输入删除的定位位置: "); scanf("%d",&i); DeleteDLNode(L,i,e); printf("删除的元素为 = %dn",e); break; case 6: printf("请输入要删除的元素: "); scanf("%d",&e); DeleteDElem(L,e); break; case 7: p=DestryDLinkList(p,L); printf("删除成功!n"); break; case 8: len=DLinkListLength(L); printf("表的长度 = %dn",len); break; case 9: PrintDLinkList(L); break; default: DestryDLinkList(p,L,flag); printf("结束操作n"); } if(flag==10){ break; } } return 0; }
(9)测试