科技公司建设网站公司,仿淘宝网站模板,seo推广营销公司,做网站好多钱目录
带头结点的双向循环链表 1.存储定义
2.结点的创建
3.结点的初始化
4.尾插结点
5.尾删结点
6.头插结点
7.头删结点
8.查找并返回结点
9.在pos结点前插入结点
10.删除pos结点
11.打印链表 12.销毁链表
13.头插结点2.0版 14.尾插结点2.0版 前言#xff1a;
当…目录
带头结点的双向循环链表 1.存储定义
2.结点的创建
3.结点的初始化
4.尾插结点
5.尾删结点
6.头插结点
7.头删结点
8.查找并返回结点
9.在pos结点前插入结点
10.删除pos结点
11.打印链表 12.销毁链表
13.头插结点2.0版 14.尾插结点2.0版 前言
当我们使用单链表时想要去找到前面的前驱结点的时候我们发现了受到限制因为当时的结点只能去找后面的结点。
于是就到了这里的带头结点的双向循环链表。
如图 首先给出 双向链表的定义是在单链表的每个结点中再设置一个指向其前驱结点的指针域。
那双向循环链表就是最后一个结点的next指向头结点头结点的前驱指向尾结点。 带头结点的双向循环链表 1.存储定义
typedef int CLDataType;typedef struct ListNode
{CLDataType val;struct ListNode* next; //存放后面结点的指针struct ListNode* pre; //存放前面结点的指针
}ListNode;
2.结点的创建
结点的创建刚开始创建头结点我们一般会采用二级指针的方式这里我们采用使用函数返回值的形式来避免野指针问题。
//创建链表
ListNode* CreateNode(CLDataType x)
{//这里采用返回值的形式进行创建结点ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL) {perror(malloc);exit(-1);}newnode-val x;newnode-pre NULL;newnode-next NULL;return newnode;
} 如果是刚开始创建的头节点的话 3.结点的初始化
这个时候就能体现带头结点双向循环链表的好处了
ListNode* InitNode()
{ListNode* phead CreateNode(-1);//让头节点的前驱和后继结点都指向自己phead-next phead; phead-pre phead;return phead;
} 因为修改了头结点所以接着使用函数返回值的形式。
注意初始化时头结点的前驱和后继指针都指向自己。如图 4.尾插结点
之前的单链表尾插需要遍历整个链表去找尾结点但是这里是带头结点的双向循环链表只需去找头结点的前驱结点就找到了尾结点。
//尾插结点
void ListPushBack(ListNode* phead, CLDataType x)
{assert(phead);ListNode* newnode CreateNode(x);ListNode* tail phead-pre;tail-next newnode; //之前的尾结点的后继指针指向新结点newnode-pre tail; //新结点的前驱指向之前的尾结点newnode-next phead; //新结点的后继指针指向头结点phead-pre newnode; //头结点的前驱指向当链表中只有一个头结点的时候tail指向自己。 再继续尾插时仍是这样。 5.尾删结点 一般都是先找到尾节结点然后再去找到尾结点的前一个结点Pre。Pre指向头结点头结点的前驱指向Pre。之后再删去尾节结。
//尾删结点
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead-next ! phead); //避免只有一个头结点ListNode* tail phead-pre;ListNode* Pre tail-pre; //用来记录尾结点的前一个结点Pre-next phead;phead-pre Pre;free(tail);tail NULL;
}
注意当只有一个头结点的情况时说明已经没有链表结点。所以不能进行删除。进而这里采用assert( phead-next ! phead) 来避免此情况。 6.头插结点
和单链表的头插相似用next指针记录头结点的下一个结点。先让新结点与next指针指向的结点建立连接再与头结点建立连接。
//头插结点
void ListPushFront(ListNode* phead,CLDataType x)
{assert(phead);ListNode* newnode CreateNode(x);ListNode* next phead-next; //记录头结点后的第一个结点newnode-next next;next-pre newnode;phead-next newnode;newnode-pre phead;
} 7.头删结点
这里需要注意的是避免只有一个头结点的情况下删除结点这样使用同尾删结点一样的方法通过断言 assert(phead-next ! phead);
//头删结点
void ListPopFront(ListNode* phead)
{assert(phead);assert(phead-next ! phead);phead-next phead-next-next;phead-next-next-pre phead;
} 8.查找并返回结点
这里采用cur指针去遍历链表找到就返回结点没有找到就返回空。
//查找并返回结点
ListNode* ListFind(ListNode* phead, CLDataType x)
{assert(phead);ListNode* cur phead-next;while (cur ! phead) {if (cur-val x){return cur;}cur cur-next;}return NULL;
}
9.在pos结点前插入结点
因为是带头结点的双向循环链表这样就可以直接进行插入。
//在pos前面插入结点
void ListInsert(ListNode* pos, CLDataType x)
{assert(pos);ListNode* newnode CreateNode(x);//注意顺序//先让后驱建立连接newnode-next pos;pos-pre-next newnode;//再前驱建立连接newnode-pre pos-pre;pos-pre newnode;
} 10.删除pos结点 修改pos的前驱和后继
//删除pos位置的结点
void ListErase(ListNode* pos)
{assert(pos);pos-pre-next pos-next;pos-next-pre pos-pre;
} 11.打印链表
//打印链表
void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur phead-next;printf(phead);while (cur ! phead) {printf(%d, cur-val);cur cur-next;}printf(\n);
} 12.销毁链表
//销毁链表
void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur phead-next;while (cur ! phead){ListNode* next cur-next;free(cur);cur next;}free(phead);phead NULL;
} 13.头插结点2.0版
这里我们借助 在pos结点前插入结点 的接口。
头插结点那就是把pos结点变为 phead-next 的结点。这样结点的插入就模拟了头插结点从而减少了一写代码的工作量。
//头插结点2.0
void ListushFront(ListNode* phead, CLDataType x)
{assert(phead);ListNode* newnode CreateNode(x);ListNode* next phead-next; //记录头结点后的第一个结点ListInsert(next,x); //这里的next相当于pos结点
}
例如 在 1结点 前插入 结点25 14.尾插结点2.0版
根据带头结点的双向循环链表的特性再借助前面的 在pos结点前插入结点ListInsert 的接口
这时我们会想到的就是 尾插结点不是在尾结点的后面进行插入的吗而ListInsert是在pos前面进行结点的插入。 这时就采用 在头结点的前进行插入结点从而达到尾插结点的特性。
//尾插结点
void ListPushBack(ListNode* phead, CLDataType x)
{assert(phead);ListNode* newnode CreateNode(x);ListInsert(phead,x);
}
