文章目录[x]
- 1:结构定义
- 2:尾插法建立双向链表
- 3:在第i个结点后插入e
- 4:删除第i个结点并用e返回其值
- 5:输出链表
@TOC
今天想写写双向链表的基本操作,其实和单链表差不多,所以就不做太多解释啦
双向链表定义
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。
基本操作
结构定义
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct DNode
{
ElemType data;
struct DNode *pre,*next;//有向前的指针和向后的指针
}DNode,*DoubleList;
是不是和单链表神似?!
只多了一个向前的指针,但顺序操作会简便许多。
尾插法建立双向链表
void CreatFromTail(DNode *head) //尾插法建立双向链表
{
DNode *p,*q;
p=(DNode*)malloc(sizeof(DNode));
p=head;
int flag=1;
char c,b;
while(flag)
{
c=getchar();
b=getchar();
if(c!='$')
{
q=(DNode*)malloc(sizeof(DNode));
q->data=c;
p->next=q;
q->pre=p;
p=q;
}
else {
flag=0;
p->next=NULL;
}
}
}
在第i个结点后插入e
void DInsList(DoubleList head,int i,char e)//在第i个结点后插入e
{
DNode *p,*s;
int k;
if(i<=0) return;
p=head;
k=0;
while(p!=NULL&&k<i+1)//此处与单链表不一样
{
p=p->next;
k=k+1;
}
if(p==NULL)
{
printf("WRONG PLACE");
return ;
}
s=(DNode*)malloc(sizeof(DNode));//这一块和双链表不一样
s->data=e;
s->pre=p->pre;
p->pre->next=s;
s->next=p;
p->pre=s;
return;
}
删除第i个结点并用e返回其值
void DDelList(DoubleList head,int i,char *e)//删除第i个结点并用e返回其值
{
DNode *p,*r;
int k;
p=head;
k=0;
while(p->next!=NULL&&k<i)//此处与单链表不同
{
p=p->next;
k=k+1;
}
if(p->next==NULL)
{
printf("WRONG PLACE");
return;
}
*e=p->data;
p->pre->next=p->next;
p->next->pre=p->pre;
free(p);
return;
}
输出链表
void OutputList(DNode *head){//输出链表
DNode *p = head->next;
while(p){
printf("%c ",p->data);
p = p->next;
}
}
主代码