C语言数据结构双向链表的建立与基本操作

2024-02-27 07:01:03 58

C语言数据结构双向链表的建立与基本操作

双向链表比单链表有更好的灵活性，其大部分操作与线性表相同。下面总结双向链表与单链表之间的不同之处及我在实现过程中所遇到的问题。

1.双向链表的建立

双向链表在初始化时，要给首尾两个节点分配内存空间。成功分配后，要将首节点的prior指针和尾节点的next指针指向NULL，这是十分关键的一步，因为这是之后用来判断空表的条件。同时，当链表为空时，要将首节点的next指向尾节点，尾节点的prior指向首节点。

2.双向链表的插入操作

由于定义双向链表时指针域中多了一个prior指针，插入操作相应变得复杂，但基本操作也并不难理解。只需记住在处理前驱和后继指针与插入节点的关系时，应始终把握好“有序原则”，即若将插入节点与两个已存在的节点构成三角形，则应先处理“向上”的指针，再处理“向下”的指针。下面用代码描述其过程:

pinsert->prior=p;
pinsert->next=p->next;
p->next->prior=pinsert;
p->next=pinsert;

3.双向链表的删除操作

理解了双向链表的插入操作后，删除操作便十分容易理解。下面用代码描述其过程:

p->prior->next=p->next;
p->next->prior=p->prior;
free(p);

双向链表的其他操作与单链表类似，在此不再赘述，完整的代码如下:

#include
#include
#include
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
typedefintstatus;
typedefintelemtype;
typedefstructnode{
elemtypedata;
structnode*next;
structnode*prior;
}node;
typedefstructnode*dlinklist;

statusvisit(elemtypec){
printf("%d",c);
}

/*双向链表初始化*/
statusinitdlinklist(dlinklist*head,dlinklist*tail){
(*head)=(dlinklist)malloc(sizeof(node));
(*tail)=(dlinklist)malloc(sizeof(node));
if(!(*head)||!(*tail))
returnERROR;
/*这一步很关键*/
(*head)->prior=NULL;
(*tail)->next=NULL;
/*链表为空时让头指向尾*/
(*head)->next=(*tail);
(*tail)->prior=(*head);
}

/*判定是否为空*/
statusemptylinklist(dlinklisthead,dlinklisttail){
if(head->next==tail)
returnTRUE;
else
returnFALSE;
}

/*尾插法创建链表*/
statuscreatedlinklisttail(dlinklisthead,dlinklisttail,elemtypedata){
dlinklistpmove=tail,pinsert;
pinsert=(dlinklist)malloc(sizeof(node));
if(!pinsert)
returnERROR;
pinsert->data=data;
pinsert->next=NULL;
pinsert->prior=NULL;
tail->prior->next=pinsert;
pinsert->prior=tail->prior;
pinsert->next=tail;
tail->prior=pinsert;
}

/*头插法创建链表*/
statuscreatedlinklisthead(dlinklisthead,dlinklisttail,elemtypedata){
dlinklistpmove=head,qmove=tail,pinsert;
pinsert=(dlinklist)malloc(sizeof(node));
if(!pinsert)
returnERROR;
else{
pinsert->data=data;
pinsert->prior=pmove;
pinsert->next=pmove->next;
pmove->next->prior=pinsert;
pmove->next=pinsert;
}
}

/*正序打印链表*/
statustraverselist(dlinklisthead,dlinklisttail){
/*dlinklistpmove=head->next;
while(pmove!=tail){
printf("%d",pmove->data);
pmove=pmove->next;
}
printf("\n");
returnOK;*/
dlinklistpmove=head->next;
while(pmove!=tail){
visit(pmove->data);
pmove=pmove->next;
}
printf("\n");
}

/*返回第一个值为data的元素的位序*/
statuslocateelem(dlinklisthead,dlinklisttail,elemtypedata){
dlinklistpmove=head->next;
intpos=1;
while(pmove&&pmove->data!=data){
pmove=pmove->next;
pos++;
}
returnpos;
}

/*返回表长*/
statuslistlength(dlinklisthead,dlinklisttail){
dlinklistpmove=head->next;
intlength=0;
while(pmove!=tail){
pmove=pmove->next;
length++;
}
returnlength;
}

/*逆序打印链表*/
statusinverse(dlinklisthead,dlinklisttail){
dlinklistpmove=tail->prior;
while(pmove!=head){
visit(pmove->data);
pmove=pmove->prior;
}
printf("\n");
}

/*删除链表中第pos个位置的元素，并用data返回*/
statusdeleteelem(dlinklisthead,dlinklisttail,intpos,elemtype*data){
inti=1;
dlinklistpmove=head->next;
while(pmove&&inext;
i++;
}
if(!pmove||i>pos){
printf("输入数据非法\n");
returnERROR;
}
else{
*data=pmove->data;
pmove->next->prior=pmove->prior;
pmove->prior->next=pmove->next;
free(pmove);
}
}

/*在链表尾插入元素*/
statusinserttail(dlinklisthead,dlinklisttail,elemtypedata){
dlinklistpinsert;
pinsert=(dlinklist)malloc(sizeof(node));
pinsert->data=data;
pinsert->next=NULL;
pinsert->prior=NULL;
tail->prior->next=pinsert;
pinsert->prior=tail->prior;
pinsert->next=tail;
tail->prior=pinsert;
returnOK;
}
intmain(void){
dlinklisthead,tail;
inti=0;
elemtypedata=0;
initdlinklist(&head,&tail);
if(emptylinklist(head,tail))
printf("链表为空\n");
else
printf("链表不为空\n");
printf("头插法创建链表\n");
for(i=0;i<10;i++){
createdlinklisthead(head,tail,i);
}
traverselist(head,tail);

for(i=0;i<10;i++){
printf("表中值为%d的元素的位置为",i);
printf("%d位\n",locateelem(head,tail,i));
}
printf("表长为%d\n",listlength(head,tail));
printf("逆序打印链表");
inverse(head,tail);
for(i=0;i<10;i++){
deleteelem(head,tail,1,&data);
printf("被删除的元素为%d\n",data);
}
traverselist(head,tail);
if(emptylinklist(head,tail))
printf("链表为空\n");
else
printf("链表不为空\n");
printf("尾插法创建链表\n");
for(i=0;i<10;i++){
//inserttail(head,tail,i);
createdlinklisttail(head,tail,i);
}
traverselist(head,tail);
printf("逆序打印链表");
inverse(head,tail);
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

C语言数据结构 双向链表的建立与基本操作

热门推荐

随机推荐

C语言数据结构双向链表的建立与基本操作