一、双向链表的结构及数据定义
#define ERROR0
#define TRUE1
#define FALSE0
#define OK1
#define MAXSIZE20/* 存储空间初始分配量 */
//头结点数据
#define HeadNodeData -1
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
//定义结点
typedef struct Node{
structNode*prior;
ElemTypedata;
structNode*next;
}Node;
typedef struct Node *LinkList;
二、创建双向链表
Status CreateLinkList(LinkList *L){
//创建一个头结点
*L = (LinkList)malloc(sizeof(Node));
if(*L ==NULL) {
returnERROR;
}
(*L)->data=HeadNodeData;//无效数据
(*L)->next =NULL;
(*L)->prior=NULL;
//新增数据
LinkListp = *L;
LinkListtemp;
for(inti=0; i<10; i++) {
//创建一个新结点
temp = (LinkList)malloc(sizeof(Node));
temp->data= i;
temp->next=NULL;
temp->prior=NULL;
//为新增的结点建立双向链表关系
//temp 是p的后继
p->next= temp;
//p 是temp的前驱
temp->prior= p;
//p指向最后一个结点
p = temp;
}
returnOK;
}
三、打印循环链表的元素
void display(LinkList L){
if(L ==NULL) {
printf("打印的双向链表为空!\n");
return;
}
//指向第一个元素（非头结点）
LinkListtemp = L->next;
while(temp) {
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
}
四、双向链表插入元素
Status InsertList(LinkList *L,int index,ElemType data){
//参数检查
if(index<1|| *L ==NULL) {
returnERROR;
}
//新建结点
LinkList temp = (LinkList)malloc(sizeof(Node));
temp->data= data;
temp->next=NULL;
temp->prior=NULL;
//指向头结点
LinkListp = *L;
//找到插入位置的上一个结点
inti=1;
while(p && i
p = p->next;
i++;
}
//如果插入的位置超过链表本身的长度
if(p ==NULL) {
returnERROR;
}
//判断插入位置是否为链表尾部;
if(p->next==NULL) {
p->next= temp;
temp->prior= p;
}else{
//新结点的next指向p的next
temp->next= p->next;
//p的下一个结点的prior指向temp
p->next->prior= temp;
//新结点的prior指向p
temp->prior= p;
//p的next指向新结点
p->next= temp;
}
returnOK;
}
五、删除双向链表指定位置上的结点
Status DeleteList(LinkList *L,int index,ElemType *data){
//
if(*L ==NULL|| index<1) {
returnERROR;
}
//找到要删除位置的上一个结点
LinkListp = *L;
for(inti=1; i
p = p->next;
}
if(p==NULL) {
returnERROR;
}
//指向要删除的结点
LinkListdelTemp = p->next;
//p的next指向要删除结点的下一个结点
p->next= delTemp->next;
//如果delTemp不是最后一个结点，则delTemp的下一个结点的prior指向p
if(delTemp->next!=NULL) {
delTemp->next->prior= p;
}
//将值带回去
*data = delTemp->data;
//将要删除结点回收
free(delTemp);
returnOK;
}
六、删除指定元素
Status DeleteListVAL(LinkList *L,ElemType data){
if(*L ==NULL|| data ==HeadNodeData) {
returnERROR;
}
LinkListp = (*L)->next;
while(p) {
if(p->data== data) {
//找到对应数据,p是要被删除的结点
//p的前一个结点的next指向p的next
p->prior->next= p->next;
//不是最后一个结点,则p的下一个结点的prior指向p的前一个结点
if(p->next!=NULL) {
p->next->prior= p->prior;
}
//
free(p);
// break;//只删除第一次出现的那个
}
//没有找到该结点,则继续移动指针p
p = p->next;
}
returnOK;
}
七、在双向链表中查找元素
int SelectList(LinkList L,ElemType elem){
if(L ==NULL) {
return HeadNodeData;
}
//指向首元结点
LinkListp = L->next;
inti =1;
while(p) {
if(p->data== elem) {
returni;
}
p = p->next;
i++;
}
return HeadNodeData;
}
八、在双向链表中更新结点
StatusReplaceList(LinkListL,intindex,ElemTypenewData){
if(L ==NULL|| index<1) {
returnERROR;
}
LinkListp = L->next;
inti=1;
if(p && i
p = p->next;
i++;
}
if(p ==NULL) {
returnERROR;
}
p->data= newData;
returnOK;
}
九、调用
intmain(intargc,constchar* argv[]) {
LinkList L;
CreateLinkList(&L);
display(L);
intindex;
ElemTypedata;
printf("请输入要插入的位置和值：\n");
scanf("%d %d",&index,&data);
InsertList(&L,index,data);
display(L);
printf("请输入要删除的位置1：\n");
scanf("%d",&index);
DeleteList(&L, index, &data);
display(L);
printf("请输入要删除的位置2：\n");
scanf("%d",&index);
DeleteList(&L, index, &data);
display(L);
printf("请输入要删除的位置3：\n");
scanf("%d",&index);
DeleteList(&L, index, &data);
display(L);
printf("请输入要删除的数据1：\n");
scanf("%d",&data);
DeleteListVAL(&L, data);
display(L);
printf("请输入要删除的数据2：\n");
scanf("%d",&data);
DeleteListVAL(&L, data);
display(L);
printf("请输入要查询的数据1：\n");
scanf("%d",&data);
index =SelectList(L, data);
printf("数据在位置：%d \n",index);
printf("请输入要查询的数据2：\n");
scanf("%d",&data);
index =SelectList(L, data);
printf("数据在位置：%d \n",index);
printf("请输入要查询的数据3：\n");
scanf("%d",&data);
index =SelectList(L, data);
printf("数据在位置：%d \n",index);
return0;
}
