双链表中有头结点⽆头结点的各种基本操作（完整代码）
代码是⽤C语⾔写的，但是bool类型的输出是⽤C++的cout写的。因为对于布尔类型，C++可以返回true或false，C只能返回1或0。
有头结点的双链表
#include<iostream>
using namespace std;
#include<malloc.h>
typedef int ElemType;
typedef struct DNode
{
ElemType data;
struct DNode* prior;
struct DNode* next;
}DNode,* DLinkList;
bool InitDList(DLinkList& L)//初始化单链表
{
L =(DNode*)malloc(sizeof(DNode));//分配⼀个头结点
if(L ==NULL)return false;//内存不⾜，分配失败
L->prior =NULL;//头结点的prior永远指向NULL
L->next =NULL;//头结点之后暂时还没有结点
return true;
}
bool DLinkListEmpty(DLinkList& L)//判断双链表是否为空表
{
return(L->next ==NULL);
}
void CreateListF(DLinkList& L)//头插法创建双链表
{
DNode* s;
int num;
printf("输⼊：\n");//键盘随机输⼊
scanf("%d",&num);
while(num !=999)
{
s =(DNode*)malloc(sizeof(DNode));
s->data = num;
s->next = L->next;
if(L->next !=NULL) s->next->prior = s;
s->prior = L;
L->next = s;
scanf("%d",&num);
}
}
void CreateListR(DLinkList& L)//尾插法创建单链表
{
DNode* s,* r = L;
for(int i =0; i <10; i++)//循环固定输⼊
{
s =(DNode*)malloc(sizeof(DNode));
s->data = i;
r->next = s;
s->prior = r;
r = s;
}
r->next =NULL;
}
}
void PrintDList(DLinkList& L)//输出函数
{
DNode* p = L->next;
while(p !=NULL)
{
printf("%d ", p->data);
p = p->next;
}
}
int DListLength(DLinkList L)
{
DNode* p = L->next;
int n =0;
while(p !=NULL)
{
n++;
p = p->next;
}
return n;
}
bool DListInsertR(DLinkList& L,int i, ElemType e)
{
DNode* p = L,* s;
int j =0;
if(i <=0|| p->next ==NULL)return false;
while(p !=NULL&& j < i)
{
j++;
p = p->next;
}
if(p ==NULL)return false;
else
{
s =(DNode*)malloc(sizeof(DNode));
s->data = e;
s->next = p->next;
if(p->next !=NULL)
p->next->prior = s;
s->prior = p;
p->next = s;
return true;
}
}
bool DListInsertF(DLinkList& L,int i, ElemType e)
{
DNode* p = L,* s;
int j =0;
if(i <=0|| p->next ==NULL)return false;//i输⼊错误或者双链表只有⼀个头结点while(p !=NULL&& j < i)
{
j++;
p = p->next;
}
if(p ==NULL)return false;
else
{
s =(DNode*)malloc(sizeof(DNode));
s->data = e;
s->prior = p->prior;
p->prior->next = s;
s->next = p;
s->next = p;
p->prior = s;
return true;
}
}
bool DListDelete(DLinkList& L,int i, ElemType& e) {
DNode* p = L;
int j =0;
e =-999;//删除失败时，e的值返回-999
if(i <=0|| p->next ==NULL)return false;
while(p !=NULL&& j < i)
{
j++;
p = p->next;
}
if(p ==NULL)return false;
else
{
e = p->data;
p->prior->next = p->next;
if(p->next !=NULL)
p->next->prior = p->prior;
free(p);
return true;
}
}
bool DListDeleteR(DLinkList& L,int i, ElemType& e) {
DNode* p = L,* n;
int j =0;
e =-999;//删除失败时，e的值返回-999
if(i <=0|| p->next ==NULL)return false;
while(p !=NULL&& j < i)
{
j++;
p = p->next;
}
if(p ==NULL)return false;
else
{
if(p->next ==NULL)return false;//i是最后⼀个结点  e = p->next->data;
n = p->next;//i的后⼀个结点
p->next = n->next;
if(n->next !=NULL)//i的后⾯只有最后⼀个结点
n->next->prior = p;
free(n);
return true;
}
}
bool DListDeleteF(DLinkList& L,int i, ElemType& e) {
DNode* p = L,* pre;
int j =0;
e =-999;//删除失败时，e的值返回-999
if(i <=0|| p->next ==NULL)return false;
while(p !=NULL&& j < i)
{
j++;
p = p->next;
}
if(p ==NULL)return false;
if(p ==NULL)return false;
else
{
if(i ==1)return false;//i是⾸结点，除头结点外没有前驱结点
pre = p->prior;
e = pre->data;
pre->prior->next = p;
p->prior = pre->prior;
free(pre);
return true;
}
}
bool  GetElem(DLinkList& L,int i, ElemType& e)
{
DNode* p = L;
int j =0;
e =-999;//查失败，e返回-999
if(i <=0|| p ==NULL)return false;//参数错误
while(p !=NULL&& j < i)
{
j++;
p = p->next;
}
if(p ==NULL)return false;//不存在第i个位置
else
{
e = p->data;
return true;
}
}
int LocateElem(DLinkList& L, ElemType e)
{
DNode* p = L->next;
int j =1;
while(p !=NULL&& p->data != e)
{
j++;
p = p->next;
}
if(p ==NULL)return-999;//不存在第i个位置
else return j;
}
int main()
{
DLinkList L;
InitDList(L);//初始化单链表
cout << boolalpha <<"双链表现在为空吗？-"<<DLinkListEmpty(L)<< endl; printf("\n");
CreateListR(L);//尾插法创建单链表
cout << boolalpha <<"双链表现在为空吗？-"<<DLinkListEmpty(L)<< endl; printf("\n");
printf("双链表L中的各值为：");
PrintDList(L);//调⽤函数，输出单链表L
printf("\n");
printf("双链表的长度为：%d\n\n",DListLength(L));
ElemType num;
int number =2;
printf("(按位查)查第%d个位置的值：\n", number);
cout << boolalpha <<"查成功了吗？—"<<GetElem(L,2, num)<< endl;
cout << boolalpha <<"查成功了吗？—"<<GetElem(L,2, num)<< endl; printf("该位置的值为：%d\n\n", num);
printf("(按元素值查)查值为%d的元素位置：\n", number);
printf("该元素第⼀次出现的位置是：%d\n\n",LocateElem(L,2));
printf("在第%d个位置后插⼊⼀个结点：\n", number);
cout << boolalpha <<"插⼊成功了吗？-"<<DListInsertR(L,2,8)<< endl; printf("插⼊后双链表L中的各值为：");
PrintDList(L);//调⽤函数，输出单链表L
printf("\n");
printf("插⼊后双链表的长度为：%d\n\n",DListLength(L));
printf("在第%d个位置前插⼊⼀个结点：\n", number);
cout << boolalpha <<"插⼊成功了吗？-"<<DListInsertF(L,2,8)<< endl; printf("插⼊后双链表L中的各值为：");
PrintDList(L);//调⽤函数，输出单链表L
printf("\n");
printf("插⼊后双链表的长度为：%d\n\n",DListLength(L));
ElemType num1;
printf("删除第%d个位置的结点：\n", number);
cout << boolalpha <<"删除成功了吗？-"<<DListDelete(L,2, num1)<< endl; printf("删除的值为：%d\n", num1);
printf("删除后双链表L中的各值为：");
PrintDList(L);//调⽤函数，输出单链表L
printf("\n");
printf("删除后双链表的长度为：%d\n\n",DListLength(L));
ElemType num2;
printf("删除第%d个位置的后⼀个结点：\n", number);
cout << boolalpha <<"删除成功了吗？-"<<DListDeleteR(L,2, num2)<< endl; printf("删除的值为：%d\n", num2);
printf("删除后双链表L中的各值为：");
PrintDList(L);//调⽤函数，输出单链表L
printf("\n");
printf("删除后双链表的长度为：%d\n\n",DListLength(L));
ElemType num3;
printf("删除第%d个位置的前⼀个结点：\n", number);
cout << boolalpha <<"删除成功了吗？-"<<DListDeleteF(L,2, num3)<< endl; printf("删除的值为：%d\n", num3);c语言listinsert函数
printf("删除后双链表L中的各值为：");
PrintDList(L);//调⽤函数，输出单链表L
printf("\n");
printf("删除后双链表的长度为：%d\n\n",DListLength(L));
return0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。