1.双向链表
2.基础操作
（1）头部插入
int InsertHeadDouLinkList(DouLinkList *dl,DATATYPE *data)
{
DouLinkNode *newnode = (DouLinkNode *)malloc(sizeof(DouLinkNode));//定义新节点来存储需插入的数据
if(NULL == newnode)//判断结点空间是否申请成功
{
fprintf(stderr,"intertHeadDouLinkList malloc");
return 1;
}
memcpy(&newnode -> data,data,sizeof(DATATYPE));//将需插入的数据装入新结点
//初始化新结点中的指针内容newnode -> next = NULL;
newnode -> prev = NULL;
newnode -> next = dl -> head;//连接新结点和链表
if(dl -> head)//判断链表是否为空
{
dl -> head -> prev = newnode;
}
dl -> head = newnode;//连接头指针与新结点
dl -> clen++;
return 0;
}
（2）打印（正向打印，反向打印）
int ShowDouLinkList(DouLinkList *dl,DIR dir)
{
if(FORWADR == dir)//正向打印
{
DouLinkNode *tmp = dl -> head;
while(tmp)//遍历
{
printf("%s,%c,%d,%d\n",tmp -> data.name,tmp -> data.sex,tmp -> data.age,tmp -> data.score);
tmp = tmp -> next;
}
}
else if(BACKWADR == dir)//反向打印，从末尾开始向前打印
{
DouLinkNode *tmp = dl -> head;
while(tmp -> next)//遍历链表，使初始位置指向最后结点
{
tmp = tmp -> next;
}
while(tmp)//反向遍历链表
{
printf("%s,%c,%d,%d\n",tmp -> data.name,tmp -> data.sex,tmp -> data.age,tmp -> data.score);
tmp = tmp -> prev;
}
}
}
（3）尾部插入
int IsEmptyLinkList(DouLinkList *dl)
{
return 0 == dl -> clen;
}int InsertTaiDouLinkList(DouLinkList *dl,DATATYPE *data)
{
if(IsEmptyLinkList(dl))//判断链表是否为空
{
return InsertHeadDouLinkList(dl,data);
}
else
{
DouLinkNode *newnode = malloc(sizeof(DouLinkNode));//申请新结点存储待插入数据
if(NULL == newnode)//判断新结点空间是否申请成功
{
fprintf(stderr,"insertTaiDouLinkList malloc\n");
return 1;
}
memcpy(&newnode -> data,data,sizeof(DATATYPE));//存入待插入数据
newnode -> next = NULL;//初始化新结点指针
newnode -> prev = NULL;
DouLinkNode *tmp = dl -> head;//定义新指针，指向头指针
while(tmp -> next)//遍历链表
{
tmp = tmp -> next;
}
newnode -> prev = tmp;//将新结点插入链表尾部
tmp -> next = newnode;
dl -> clen++;
}
return 0;
}
（4）指定位置插入
int GetsizeofDouLinkList(DouLinkList *dl)
{
return dl -> clen;
}int InsertPosDouLinkList(DouLinkList *dl,DATATYPE *data,int pos)
{
int len = GetsizeofDouLinkList(dl);//算出链表长度
if(0 == pos)//头部插入
{
return InsertHeadDouLinkList(dl,data);
}
else if(pos == len)//尾部插入
{
return InsertTaiDouLinkList(dl,data);
}
else
{
DouLinkNode *newnode = malloc(sizeof(DouLinkNode));
if(NULL == newnode)
{
fprintf(stderr,"InsertPosDouLinkList malloc\n");
return 1;
}
memcpy(&newnode -> data,data,sizeof(DATATYPE));
newnode -> next = NULL;
newnode -> prev = NULL;
DouLinkNode *tmp = dl -> head;
for(int i = 0;i < pos;++i)//遍历链表，定位待插位置
{
tmp = tmp -> next;
}
newnode -> next = tmp;//将新结点和待插位置的前结点和后结点连接
newnode -> prev = tmp -> prev;
tmp -> prev = newnode;
newnode -> prev ->next = newnode;
dl ->clen++;}
return 0;
}
（5）查找
DouLinkNode *FindDouLinkList(DouLinkList *dl,char *name)
{
int len = GetsizeofDouLinkList(dl);//获取链表长度
DouLinkNode *tmp = dl -> head;//定义新指针，指向头指针
for(int i = 0;i < len;++i)//遍历链表
{
if(0 == strcmp(tmp -> data.name,name))//用已给name查找结点
{
return tmp;
}
tmp = tmp -> next;
}
return NULL;
}
（6）替换
int ModifyDouLinkLinst(DouLinkList *dl,char *name,DATATYPE *data)
{
DouLinkNode *ret = FindDouLinkList(dl,name);//查找结点
if(NULL == ret)//判断是否找到结点
{
return 1;
}
memcpy(&ret -> data,data,sizeof(DATATYPE));//替换数据
return 0;
}
练习：
（1）销毁
int DestroyDouLinkList(struct DouLinkList* dl)
{
DouLinkNode *tmp = dl -> head;//定义新指针，指向头指针
DouLinkNode *ret ;
while(tmp)//遍历链表
{
ret = tmp;
tmp = tmp -> next;
free(ret);//释放结点空间
ret = NULL;
}
free(dl);
dl = NULL;
return 0;}
（2）删除
int DeleteDouLinkList(struct DouLinkList* dl,char* name)
{
DouLinkNode *tmp = FindDouLinkList(dl,name);//查找待删结点
if(NULL == tmp -> prev)//头删
{
dl -> head = tmp -> next;
tmp -> next -> prev = NULL;
dl -> clen--;
free(tmp);
tmp = NULL;
return 0;
}
else if(NULL == tmp -> next)//尾删
{
tmp -> prev -> next = NULL;
dl -> clen--;
free(tmp);
tmp = NULL;
return 0;
}
else
{
tmp -> prev ->next = tmp -> next;
tmp -> next ->prev = tmp -> prev;
dl -> clen--;
free(tmp);
tmp = NULL;
return 0;
}
}
（3）逆序
int RevertDouLinkList(struct DouLinkList* dl)
{
DouLinkNode *p = NULL;//定义一个指向被逆转结点的指针，初始位空指针
DouLinkNode *tmp = dl -> head;//定义一个指向待逆转结点的指针，初始化位头指针
DouLinkNode *n = tmp ->next;//定义一个指向待逆转结点next的指针，辅助遍历链表
int len = GetsizeofDouLinkList(dl);
if(len < 2)//逆序链表长度必须大于1
{
return 1;
}
while(1)
{
tmp -> next = p;//将待逆序结点指向被逆序节点
tmp -> prev = n;p = tmp;//p++
tmp = n;//tmp++
if(NULL == tmp)//判断指针是否为空
{
break;//指针为空时结束循环
}
n = n -> next;//n++}
dl -> head = p;//将头指针指向已逆序后的链表首位
return 0;
}
注：
1.Makefile: vi Makefile
自动指定编译
（1）简单编译设置
（2）复杂编译设置
