央企八大设计院,模板网站如何做seo,学做网站的书哪些好,wordpress 小影链表 文章目录 链表前言认识链表单链表结构图带头单循环链表结构图双向循环链表结构图带头双向循环链表结构图 链表特点 链表实现(带头双向循环链表实现)链表结构体(1) 新建头节点(2) 建立新节点(3)尾部插入节点(4)删除节点(5)头部插入节点(6) 头删节点(7) 寻找节点(8) pos位置…链表 文章目录 链表前言认识链表单链表结构图带头单循环链表结构图双向循环链表结构图带头双向循环链表结构图 链表特点 链表实现(带头双向循环链表实现)链表结构体(1) 新建头节点(2) 建立新节点(3)尾部插入节点(4)删除节点(5)头部插入节点(6) 头删节点(7) 寻找节点(8) pos位置插入节点(9) 删除pos位置节点(10) 打印链表测试用例 前言
new一个奶黄包没关系这条路我陪你走到底 认识链表
单链表结构图 带头单循环链表结构图 双向循环链表结构图 带头双向循环链表结构图 链表特点 单链表在内存中并不是连续存储的逻辑上连续。 不支持随机访问 插入时只需要改变指针指向 没有容量的概念 可以高效的在任意位置插入删除 缓存利用率低
链表实现(带头双向循环链表实现)
链表结构体
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;(1) 新建头节点
LTNode* ListInit()//建立头节点
{LTNode* phead buyListNode(-1); //建立一个带头节点phead-next phead; phead-prev phead;return phead;
}(2) 建立新节点
LTNode* buyListNode(LTDataType x)//创建内存初始化数据
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode)); //if (newnode NULL){perror(malloc fail);exit(-1);}// 初始化注意所对的结构来初始化newnode-next NULL;newnode-prev NULL;newnode-data x;return newnode;
}
(3)尾部插入节点
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode buyListNode(x);LTNode* tail phead-prev;tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;
}(4)删除节点
void LTPopBack(LTNode* phead)
{assert(phead);LTNode* tail phead-prev; //记录上一个节点LTNode* tailmove tail-prev; //记录上一个节点的上一个节点tailmove-next phead; phead-prev tailmove;free(tail);
}(5)头部插入节点
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode buyListNode(x); LTNode* first phead-next;newnode-next first;first-prev newnode;first-next phead;phead-prev first;
}(6) 头删节点
void LTPopFront(LTNode* phead)
{assert(phead); //判断是否有头节点assert(phead-next ! NULL); //判断第一个节点是否存在LTNode* tail phead-next;LTNode* tailmove tail-next;tailmove-prev phead;phead-next tailmove;tailmove-next phead;phead-prev tailmove;free(tail);
}(7) 寻找节点
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-data x){//printf(找到了);return cur;//返回指针}curcur-next; //每次都走到下一个节点直到phead}//printf(找不到);return NULL;
}(8) pos位置插入节点
void LTInsert(LTNode* pos, LTDataType x)//头插尾插都可以调用这个函数
{assert(pos);LTNode* newnode buyListNode(x); //新建一个节点LTNode* prev pos-prev; //记录pos位置的前一个节点newnode-next pos; //新节点的下一个节点就是pospos-prev newnode; //pos位置节点prve就链接后面newnode-prev prev;prev-next newnode;
}(9) 删除pos位置节点
void LTErase(LTNode* pos) //删除节点
{assert(pos);LTNode* prve pos-prev;LTNode* next pos-next;prve-next next;next-prev prve;free(pos);
}(10) 打印链表
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur! phead){printf(- %d ,cur-data );cur cur-next;}}测试用例
void test1()
{LTNode* ptail ListInit();LTPushBack(ptail, 1);LTPushBack(ptail, 3);LTPushBack(ptail, 2);LTPushBack(ptail, 4);LTPushBack(ptail, 5);LTPopBack(ptail);LTPrint(ptail);
}
