当前位置 博文首页 > CW_qian的博客:8月25日笔记数据结构(补10)双向链表
????????????????????????????????????????????????????????????????????????链表的介绍都在前面带头节点单向链表的基础上展开
基本构造(特点):
// 定义数据节点
struct node
{
?? ?dataType data; // 数据域
?? ?struct node *prev; // 指向上一个节点的地址
?? ?struct node *next; // 指针域,存放(指向)下一个节点的地址
};
//-----------------------------------// 定义头节点
struct headNode
{
?? ?struct node *first; // 指向第一个数据节点
?? ?struct node *last; // 指向最后一个数据节点
?? ?int nodeNumber; // 记录链表节点数
};
定义数据节点:struct node
? ? ? ? 存放上指针域:prev和下指针域next
定义头节点:struct headNode
创建链表:struct headNode *create_list()
主函数:
? ? ? ? int main()
{????????创建新链表:
?? ?struct headNode *head = create_list();
功能:
1.打印链表:void show_list(struct headNode *head)
?? ?????????show_list(head);
2.删除节点:struct headNode *del_node(struct headNode *head,dataType data)
?? ?????????head = del_node(head,3);
3.通过双向链表实现添加节点:struct headNode *add_node(struct headNode *head,dataType newdata,dataType data)
????????head = add_node(head,8,3);
????????return 0;
}
具体代码:dLinkedListWithHead.c
#include <stdio.h>
#include <stdlib.h>
//-----------------------------------
typedef int dataType;
//-----------------------------------
// 定义数据节点
struct node
{
dataType data; // 数据域
struct node *prev; // 指向上一个节点的地址
struct node *next; // 指针域,存放(指向)下一个节点的地址
};
//-----------------------------------
// 定义头节点
struct headNode
{
struct node *first; // 指向第一个数据节点
struct node *last; // 指向最后一个数据节点
int nodeNumber; // 记录链表节点数
};
//---------------------------------
// 尾插
void tailAdd(struct node *pnew,struct headNode *head)
{
head->last->next = pnew;
pnew->prev = head->last;
head->last = pnew;
}
//---------------------------------
// 头插
void headAdd(struct node *pnew,struct headNode *head)
{
//printf("__%d__\n",__LINE__);
//head->first->prev = pnew;
pnew->next = head->first;
pnew->next->prev = pnew;
head->first = pnew;
//printf("__%d__\n",__LINE__);
}
//---------------------------------
struct headNode *create_list()
{
// 创建头节点
struct headNode *head = malloc(sizeof(struct headNode));
if(head == NULL)
{
perror("create headNode failed");
return NULL;
}
// 初始化头节点
head->first = NULL;
head->last = NULL;
head->nodeNumber = 0;
// 用于存放获取到的数据,数据内容自定义
dataType data;
while(1)
{
scanf("%d",&data);
if(data == 0)// 链表生成
break;
// 创建新节点
struct node *pnew = malloc(sizeof(struct node));
if(pnew == NULL)
{
perror("create newnode failed");
return NULL;
}
pnew->data = data;
pnew->prev = NULL; // 指向前驱节点
pnew->next = NULL; // 指向后继节点
//将新节点插入到链表
if(head->first == NULL)//从无到有
{
head->first = pnew;
head->last = pnew;
}
else // 从少到多
{
// 尾插法
tailAdd(pnew,head);
/* #if 0
head->last->next = pnew;
pnew->prev = head->last;
head->last = pnew;
#else
pnew->prev = head->last;
pnew->prev->next = pnew;
head->last = pnew;
#endif */
// 头插法
///headAdd(pnew,head);
/* pnew->next = head->first;
head->first->prev = pnew;
head->first = pnew; */
}
// 更新节点数
head->nodeNumber++;
}
return head;
}
//------------------------------
// 打印链表节
void show_list(struct headNode *head)
{
// 从头到尾打印
for(struct node *p = head->first;p != NULL;p = p->next)
{
printf("%d ",p->data);
}
// 从尾到头打印
/* int n = head->nodeNumber;
struct node *p = head->last;
while(n)
{
printf("%d ",p->data);
p = p->prev;
n--;
}
*/
printf("\n");
printf("此链表的节点数据数为%d个\n",head->nodeNumber);
}
//------------------------------
// 练习 : 通过双向链表实现添加节点
struct headNode *add_node(struct headNode *head,dataType newdata,dataType data)
{
// 创建新节点
struct node *pnew = malloc(sizeof(struct node));
if(pnew == NULL)
{
perror("create new node failed:");
return NULL;
}
// 初始化新节点
pnew->data = newdata;
pnew->next = NULL;
// 定义指针p遍历链表
struct node *p = head->first;
// 开始遍历链表查找对应的节
while(p)
{
// 找到了,停止遍历
if(p->data == data)
{
break;
}
else // 继续找
{
p = p->next;
}
}
// 找不到节点
if(p == NULL) //尾插
{
tailAdd(pnew,head);
}
else // 找到对应的节点
{
// 找打的是首节点
if(p == head->first)
{
// 头插法
headAdd(pnew,head);
}
else // 中间插
{
pnew->next = p;
pnew->prev = p->prev;
p->prev->next = pnew;
p->prev = pnew;
}
}
// 链表节点加一
head->nodeNumber++;
return head;
}
/*
del_node : 将head指向的链表中删除所有对应的data数据所对应的节点
*/
struct headNode *del_node(struct headNode *head,dataType data)
{
// 遍历指针
struct node *p = head->first;
while(p)
{
if(p->data == data)// 找到需要删除的节点
{
// 链表节点减一
head->nodeNumber--;
if(p == head->first)// 需要删除的数据为首节点数据
{
head->first = p->next;
// p的下一个节点指向空,相当于首节点
p->next = NULL; // 断开链表
p->prev = NULL;
free(p); // 释放空间
p = head->first;//p重新指向新的首节点
}
else if(p == head->last) // 删除最后一个节点
{
head->last = head->last->prev;
head->last->next = NULL;
p->prev = NULL;
free(p);
p->next = NULL;
}
else //删除的数据不是首节点,也不是尾节点
{
struct node *tp = p->next;
p->prev->next = p->next;
p->next->prev = p ->prev;
p->prev = NULL;
p->next = NULL;
free(p);
p = tp;
}
}
else // 没有找到对应的节点,继续往下找
{
p = p->next;
}
}
return head;
}
int main()
{
// 创建新链表
struct headNode *head = create_list();
//head = add_node(head,8,3);
// 删除节点
head = del_node(head,3);
//打印链表
show_list(head);
return 0;
}
扩展功能:
1.获取两个链表的交集:struct headNode *comn_list(struct headNode *headA,struct headNode *headB)
????????创建新链表
?? ?????????struct headNode *headA = create_list();
?? ?????????struct headNode *headB = create_list();
????????struct headNode *head = comn_list(headA,headB);
struct headNode *comn_list(struct headNode *headA,struct headNode *headB)
{
// 创建新链表用于存放两条链表相同的节点
struct headNode *head = malloc(sizeof(struct headNode));
if(head == NULL)
{
perror("create head failed:"); // 日志 LOG debugview
return NULL;
}
// 初始化头节点
head->first = NULL;
head->last = NULL;
head->nodeNumber = 0;
// 定义pA,pB指针指向headA,headB两条链表的首节点
struct node *pA = headA->first;
struct node *pB = headB->first;
dataType tSave = -1;
struct node *pnew = NULL;
//printf("__%d__\n",__LINE__);
// 遍历pA,pB两条链表
while(pA && pB)
{
// 如果找到pA与pB相同的值
if(pA->data == pB->data)
{
// 如果PA,PB节点里面的内容相同且没有多次出现
if(pA->data != tSave)
{
// 创建新节点用于存放pA,pB取下来的值
pnew = malloc(sizeof(struct node));
if(pnew == NULL)
{
perror("pnew failed:");
return NULL;
}
pnew->next = NULL;
pnew->prev = NULL;
// 将pApB相同的值赋值到pnew->data
pnew->data = pA->data;
//printf("__%d__\n",__LINE__);
// 将新节点插入到链表
if(head->first == NULL)
{
head->first = pnew;
head->last = pnew;
}
else // 尾插法
{
tailAdd(pnew,head);
}
// 链表节点加一
head->nodeNumber++;
// 记录前一个节点的内容
tSave = pA->data;
}
else // 多次出现相同的内容
{
printf("__%d__\n",__LINE__);
pA = pA->next;
pB = pB->next;
}
}
else
{
// 如果pA的节点小于pB的节点
if(pA->data < pB->data)
{
pA = pA->next;
}
else
{
pB = pB->next;
}
}
}
return head;
}
2.链表去重:struct headNode *del_comn(struct headNode *head)
?? ?head = del_comn(head);
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//......
// 找相同的节点,返回true;
bool comnNode(struct headNode *head,struct node *pA)
{
struct node *p = head->first;
while(p != pA) // 第一个节点略过
{
if(p->data == pA->data)
{
return true;
}
p = p->next;
}
return false;
}
// 链表去重
struct headNode *del_comn(struct headNode *head)
{
// 定义遍历指针查找相同的节点
struct node *p = head->first;
while(p)
{
// 如果找到相同的节点则删除
if(comnNode(head,p))
{
//printf("__%d___\n",__LINE__);
head->nodeNumber--;
// 判断是否为尾节点
if(p == head->last)
{
head->last = head->last->prev;
head->last->next = NULL;
p->prev = NULL;
p->next = NULL;
free(p);
break;
}
else
{
struct node *tp = p->next;
p->prev->next = p->next;
p->next->prev = p ->prev;
p->prev = NULL;
p->next = NULL;
free(p);
p = tp;
}
}
else
{
p = p->next;
}
}
return head;
}