嘉鱼网站建设哪家专业,wordpress 注册审核,广告推广免费发布,北京建设工程教育中心网站目录
编辑
1.链表的分类
2.带头双向循环链表的实现
1.创建结构体
2.创建返回链表的头节点
3.双向链表销毁
4.双向链表打印
5.双向链表尾插
6.双向链表尾删
7.双向链表头插
8.双向链表头删
9.双向链表查找
10.双向链表在pos的前面进行插入
11.双向链表删除pos位…
目录
编辑
1.链表的分类
2.带头双向循环链表的实现
1.创建结构体
2.创建返回链表的头节点
3.双向链表销毁
4.双向链表打印
5.双向链表尾插
6.双向链表尾删
7.双向链表头插
8.双向链表头删
9.双向链表查找
10.双向链表在pos的前面进行插入
11.双向链表删除pos位置的节点
3.源码 4.顺序表和链表的区别 1.链表的分类 链表会根据是单向或者双向带头或者不带头循环或者非循环进行分类组合。以上情况组合起来就有8种链表结构。 其中头指针和头节点是两个概念 头指针 它是一个指针指向链表中第一个节点的地址。头节点它是一个结构体区分数据域和指针域。数据域不存储元素指针域则存放第一个节点的地址。 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。带头双向循环链表带头是指链表最前面有一个头节点它是一个结构体变量分为数据域和指针域数据域一般不存储数据指针域存放的是第一个元素的地址。双向是指一个节点中有两个指针域一个叫前驱指针指向当前节点的前一个节点的指针用于向前遍历一个叫后继指针指向当前节点的后一个节点的指针用于向后遍历。循环是指链表最后一个节点的指针域存放的是头节点的地址这样一来整个链表就形成了循环的效果。 2.带头双向循环链表的实现
1.创建结构体 因为是带头双向循环链表所以我们要定义两个指针一个前驱指针指向当前节点的前一个节点还有一个后继指针指向当前节点的后一个节点。 typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;//后继指针struct ListNode* prev;//前驱指针LTDataType val;
}LTNode;
2.创建返回链表的头节点
//返回创建链表的头节点
LTNode* CreateLTNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-val x;newnode-next NULL;newnode-prev NULL;return newnode;
}
3.双向链表销毁
//销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);
}
4.双向链表打印 要想打印链表中的值就得找到跳出循环的条件。因为哨兵位不存储有效的值所以我们可以定义一个cur变量让它指向哨兵位的下一个节点如果cur ! phead就打印值直到cur走到哨兵位就跳出循环。 //打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;printf(哨兵位);while (cur ! phead){printf(%d, cur-val);cur cur-next;}printf(\n);
}
5.双向链表尾插 带哨兵位的头节点不可能为空哪怕链表一个值都没有它也是指向自己的所以要断言一下。尾插的第一步首先要找到尾双向链表中找尾非常简单哨兵位的前一个节点phead-prev就是尾然后将尾节点tail的后继指针指向新节点newnode新节点newnode的前驱指针指向tail再将新节点newnode的后继指针指向哨兵位phead哨兵位phead的前驱指针指向新节点newnode。 //尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail phead-prev;//找尾节点LTNode* newnode CreateLTNode(x);//phead tail newnodetail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;
}
6.双向链表尾删 因为哨兵位不可能为空所以还是得先断言一下。当链表为空时我们不能在进行尾删但是此时链表里边还有个哨兵位我们得保证不能将哨兵位也删掉所以哨兵位也得断言一下因为链表为空时哨兵位是指向它自己的所以断言的条件应该写成assert(phead-next ! phead)。尾删时一样得先找到尾即哨兵位得前一个节点phead-prev因为要free掉尾所以还得找到尾的前一个节点tailprev tail-prev。这两个都找到后先free掉tail然后让tail的前一个节点tailprev的后继指针指向哨兵位phead再让哨兵位phead的前驱指针指向tailpeev。 //尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTNode* tail phead-prev;LTNode* tailprev tail-prev;free(tail);tailprev-next phead;phead-prev tailprev;
}
7.双向链表头插 头插时我们先搞一个新节点newnode出来然后将newnode与哨兵位和第一个节点链接起来就可以了。但是这儿得注意一下我们要先将newnode与第一个节点链接然后再将哨兵位与newnode链接如果先将哨兵位与newnode链接容易找不到第一个节点就会很麻烦。 //头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode CreateLTNode(x);//第1种方法//newnode-next phead-next;//phead-next-prev newnode;//phead-next newnode;//newnode-prev phead;//第2种方法LTNode* first phead-next;newnode-next first;first-prev newnode;phead-next newnode;newnode-prev phead;
}
8.双向链表头删 头删时我们还得注意链表不能为空的情况即哨兵位不能被删掉所以还得断言assert(phead-next ! phead)。只有销毁链表的时候才能将哨兵位free掉。 //头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTNode* first phead-next;LTNode* second first-next;phead-next second;second-prev phead;free(first);first NULL;
}
9.双向链表查找 查找可以配合其它函数来使用如果找到了就返回那个节点的地址找不到则返回空。 //查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-val x){return cur;}cur cur-next;}return NULL;
}
10.双向链表在pos的前面进行插入 将这个函数写完后我们在回过头看头插、尾插发现头插、尾插刚好可以利用这个函数以一种更简便的方式来实现。LTInsert(phead-next, x)就是头插因为phead的下一个节点刚好就是头节点在头节点的前面插入就是头插LTInsert(phead, x)就是尾插因为phead的前一个节点刚好就是尾。 //在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posprev pos-prev;LTNode* newnode CreateLTNode(x);posprev-next newnode;newnode-prev posprev;newnode-next pos;pos-prev newnode;
}
11.双向链表删除pos位置的节点 这个删除操作也可以用来头删和尾删头删就是LTErase(phead-next)尾删就是LTErase(phead-prev)。 //删除pos的值
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev pos-prev;LTNode* posnext pos-next;posprev-next posnext;posnext-prev posprev;free(pos);
}
3.源码 List.h #pragma once
#include stdio.h
#include stdlib.h
#include assert.htypedef int LTDataType;typedef struct ListNode
{struct ListNode* next;//后继指针struct ListNode* prev;//前驱指针LTDataType val;
}LTNode;//初始化
LTNode* LTInit();
//返回创建链表的头节点
LTNode* CreateLTNode(LTDataType x);
//打印
void LTPrint(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);
//删除pos的值
void LTErase(LTNode* pos);//销毁
void LTDestory(LTNode* phead); List.c #include List.h//初始化
LTNode* LTInit()
{LTNode* phead CreateLTNode(-1);phead-next phead;phead-prev phead;return phead;
}//返回创建链表的头节点
LTNode* CreateLTNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-val x;newnode-next NULL;newnode-prev NULL;return newnode;
}//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;printf(哨兵位);while (cur ! phead){printf(%d, cur-val);cur cur-next;}printf(\n);
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);//第1种方法LTNode* tail phead-prev;//找尾节点LTNode* newnode CreateLTNode(x);tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;//第2种方法//LTInsert(phead, x);
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead-next ! phead);//第1种写法LTNode* tail phead-prev;LTNode* tailprev tail-prev;free(tail);tailprev-next phead;phead-prev tailprev;//第2种写法//LTErase(phead-prev);
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode CreateLTNode(x);//第1种方法//newnode-next phead-next;//phead-next-prev newnode;//phead-next newnode;//newnode-prev phead;//第2种方法LTNode* first phead-next;newnode-next first;first-prev newnode;phead-next newnode;newnode-prev phead;//第3种方法//LTInsert(phead-next, x);}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);//第1种写法LTNode* first phead-next;LTNode* second first-next;phead-next second;second-prev phead;free(first);first NULL;//第2种写法//LTErase(phead-next);
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-val x){return cur;}cur cur-next;}return NULL;
}//在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posprev pos-prev;LTNode* newnode CreateLTNode(x);posprev-next newnode;newnode-prev posprev;newnode-next pos;pos-prev newnode;
}//删除pos的值
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev pos-prev;LTNode* posnext pos-next;posprev-next posnext;posnext-prev posprev;free(pos);
}//销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);
} 4.顺序表和链表的区别
