目录
在codeblocks 中建立C++ 控制台项目
将4,5,6,的代码都放进去,即可运行！
1.效果截图：
?2.双链表结点类型DLinkNode声明
typedef char ElemType;
typedef struct DNode
{
ElemType data;//存放元素值
struct DNode *prior;//指向前驱结点
struct DNode *next;//指向后继结点
}DLinkNode;//声明双链表结点类型3.整体建立双链表
头插法：
void CreatListF(DLinkNode *&L,ElemType a[],int n)
{
DLinkNode *s;
L=(DLinkNode *)malloc(sizeof(DLinkNode));
//创建头结点
L->prior=L->next=NULL;
for(int i=0;i<n;i++)//循环创建结点
{
s=(DLinkNode *)malloc(sizeof(DLinkNode));
s->data=a[i];
s->next=L->next;
//将结点s插入到开始结点前,头结点后
//首结点不为空
if(L->next!=NULL)
L->next->prior=s;
//后继结点的前驱指针指向结点s
L->next=s;
s->prior=L;
}
}尾插法：
void CreatListR(DLinkNode *&L,ElemType a[],int n)
{
DLinkNode *s,*r;
L=(DLinkNode *)malloc(sizeof(DLinkNode));
//创建头结点
L->prior=L->next=NULL;
r=L;//r指向终端结点,初始时指向头结点
for(int i=0;i<n;i++)//循环创建结点
{
s=(DLinkNode *)malloc(sizeof(DLinkNode));
s->data=a[i];
r->next=s;
s->next=r;//将s结点插入到r结点后
r=s;//r指向尾结点
}
r->next=NULL;//尾结点next域置为NULL
}4.添加头文件
#include<stdio.h>
#include<malloc.h>5.基本运算算法（9个）
（插入为? 尾插法）
?插入：遍历双链表,找前驱结点，创建结点s保存元素e,s结点指针共修改4次
删除：遍历双链表，查找第i个元素前驱结点，通过创建结点q保存信息，q结点指针共修改两次，
? ? ? ? ? 释放q结点的空间
//初始化双链表
void InitList(DLinkNode *&L)
{
//创建头结点
L=(DLinkNode *)malloc(sizeof(DLinkNode));
L->next=L->prior=NULL;
}
//销毁双链表
void DestroyList(DLinkNode *&L)
{
//删除每个结点
DLinkNode *p=L->next,*pre=L;
while(p!=NULL)//首结点不为空
{
free(p);
p=p->next;//pre,p同步后移一个结点
pre=pre->next;
}
free(p);
}
//判断双链表是否为空
bool ListEmpty(DLinkNode *L)
{
return (L->next==NULL);
//头结点是否为空
}
//求双链表的长度
int ListLength(DLinkNode *L)
{
//循环双链表,记录结点的个数
DLinkNode *p=L;//p指向头结点
int i=0;//记录结点个数
while(p->next!=NULL)
{
i++;
p=p->next;
}
return (i);
}
//输出双链表
void DispList(DLinkNode *L)
{
DLinkNode *p=L->next;//p指向首结点
while(p!=NULL)//遍历双链表
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
//求双链表中第i个元素的值
bool GetElem(DLinkNode *L,int i,ElemType &e)
{
//遍历双链表,找前驱结点
int j=0;
DLinkNode *p=L;
if(i<1)return false;
while(j<i&&p!=NULL)//查找第i-1个结点
{
j++;
p=p->next;
}
if(p->next==NULL)//未找到第i个结点
return false;
else
{
e=p->data;
return true;
}
}
//查找第一个值域为e的元素的元素序号
int LocateElem(DLinkNode *L,ElemType e)
{
//遍历双链表,判断每个结点的值
int i=1;//记录结点序号
DLinkNode *p=L->next;//指向首节点
while(p!=NULL&&p->data!=e)//查找p结点
{
i++;
p=p->next;
}
if(p==NULL)
return 0;
else
return i;
//找到并返回元素序号
}
//在双链表中第i个位置插入元素
bool ListInsert(DLinkNode *&L,int i,ElemType e)
{
//遍历双链表,找前驱结点
int j=0;//记录结点序号
DLinkNode *p=L,*s;
//p指向首结点,s保存插入元素信息
if(i<1) return false;
while(j<i-1&&p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL)//未找到第i-1个结点
return false;
else
{
//创建s结点保存元素e
s=(DLinkNode *)malloc(sizeof(DLinkNode));
s->data=e;
s->next=p->next;//将s结点插入到p结点后
//若p结点后有后继结点,修改前驱指针
if(p->next!=NULL)
p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}
}
//删除双链表中第i个元素
bool ListDelete(DLinkNode *&L,int i,ElemType &e)
{
//遍历双链表,找前驱结点
int j=0;//记录结点序号
if(i<1)return false;
DLinkNode *p=L,*q;
//p指向头结点,q保存被删元素
while(j<i-1&&p!=NULL)//查找第i个元素
{
j++;
p=p->next;
}
if(p->next==NULL)//未找到第i个元素
return false;
q=p->next;//找到第i个元素
q->data=e;
p->next=q->next;//删除结点
//p存在后继结点,修改前驱指针
if(p->next!=NULL)
p->next->prior=p;
free(q);
return true;
}6.主函数：
int main()
{
DLinkNode *L;
ElemType e;
printf("双链表的基本运算如下:\n");
printf(" (1)初始化双链表h\n");
InitList(L);
printf(" (2)依次采用尾插法插入a,b,c,d,e元素\n");
ListInsert(L,1,'a');
ListInsert(L,2,'b');
ListInsert(L,3,'c');
ListInsert(L,4,'d');
ListInsert(L,5,'e');
printf(" (3)输出双链表L:");
DispList(L);
printf(" (4)双链表L长度:%d\n",ListLength(L));
printf(" (5)双链表L为%s\n",(ListEmpty(L)?"空":"非空"));
GetElem(L,3,e);
printf(" (6)双链表L的第3个元素:%c\n",e);
printf(" (7)元素a的位置:%d\n",LocateElem(L,'a'));
printf(" (8)在第4个元素位置上插入f元素\n");
ListInsert(L,4,'f');
printf(" (9)输出双链表h:");
DispList(L);
printf(" (10)删除L的第3个元素\n");
ListDelete(L,3,e);
printf(" (11)输出双链表h:");
DispList(L);
printf(" (12)释放双链表h\n");
DestroyList(L);
return 1;
}7.遇到的问题
元素未成功插入，
应该判断 p=L->next!==NULL;
写成了 p->L!=NULL;