各大电商购物网站转化率报表,可以做动画的网站都有哪些,龙岩建筑网,微信小程序商城制作1.1链表的概念定义#xff1a;链表是一种物理存储上非连续#xff0c;数据元素的逻辑顺序通过链表中的指针链接次序#xff0c;实现的一种线性存储结构。特点#xff1a;链表由一系列节点组成#xff0c;节点在运行时动态生成 #xff08;malloc#xff09;#xff0c;…1.1链表的概念定义 链表是一种物理存储上非连续数据元素的逻辑顺序通过链表中的指针链接次序实现的一种线性存储结构。特点 链表由一系列节点组成节点在运行时动态生成 malloc每个节点包括两个部分 一个是存储数据元素的数据域 另一个是存储下一个节点地址的指针域如图1.2链表的概述链表作为 C 语言中一种基础的数据结构在平时写程序的时候用的并不多但在操作系统里面使用的非常多。不管是RTOS还是Linux等使用非常广泛所以必须要搞懂链表链表分为单向链表和双向链表单向链表很少用使用最多的还是双向链表。单向链表懂了双向链表自然就会了。1.3单向不带头不循环的链表的初始化参数的传入涉及改变链表的操作统统用指针传链表其中特别注意的是需要改变传入的头结点时需要传入二级指针不然函数调用完成之后为传入的链表分配的的内存会自动释放链表不会有任何改变。创建头结点为头结点分配内存。令头节点的指针为空指针(指针不初始化容易出现很多问题)PS这里为什么要动态分配内存呢因为线性表的顺序存储结构用数组实现而数组占用的是一整块内存数组元素分布很集中需要提前预定数组的长度。而链表是一种动态结构它所占用的大小和位置是不需要提前分配的可以根据自身的需求即时生成。第二步创建第二个节点将其放在第一个节点的后面第一的节点的指针域保存第二个节点的地址第三步再次创建节点找到原本链表中的最后一个节点接着讲最后一个节点的指针域保存新节点的地址以此内推。1.4单链表的一些操作1.4.1链表的遍历1.输出第一个节点的数据域输出完毕后让指针保存后一个节点的地址2.输出移动地址对应的节点的数据域输出完毕后指针继续后移 3.以此类推直到节点的指针域为NULL。1.4.2链表的查找// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x) {assert(plist);SListNode* cur plist;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}1.4.3链表的头插头删尾插尾删
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{if (*pplist NULL){SListNode* newnode BuySListNode(x);*pplist newnode;}else{SListNode *newnode BuySListNode(x);newnode-next*pplist;*pplist newnode;}
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{assert(*pplist);if ((*pplist)-next NULL)//对结构体指针的地址传值时访问该结构体的成员先得对结构体地址解引用{SListNode* cur *pplist;//直接free(*pplist)会使得pplist被置为随机值free(cur);*pplist NULL;}else{SListNode *cur *pplist;*pplist (*pplist)-next;//左右两边的星号都不要漏。free(cur);}
}// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{if (*pplist NULL){SListNode* newnode BuySListNode(x);*pplist newnode;}else{SListNode* tail *pplist;SListNode* newnode BuySListNode(x);while (tail-next){tail tail-next;}tail-next newnode;}
}
// 单链表的尾删
void SListPopBack(SListNode** pplist) {assert(*pplist);SListNode* tail*pplist,*prev*pplist;if (tail-next NULL){free(tail);*pplist NULL;}else {while (tail-next){prev tail;tail tail-next;}prev-next NULL;free(tail);tail NULL;}
}
1.4.4单链表的插入// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入因为找pos之前的位置需要On的时间复杂度
void SListInsertAfter(SListNode* pos, SLTDateType x) {assert(pos);SListNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos) {assert(pospos-next);SListNode* next pos-next;pos-next next-next;free(next);next NULL;
}// 单链表在pos位置之后插入x// 分析思考为什么不在pos位置之前插入因为找pos之前的位置需要On的时间复杂度进行查找到pos的前一个元素1.4.5链表节点的删除如果链表为空不需要删除如果删除的是第一个结点则需要将保存链表首地址的指针保存第一个结点的下一个结点的 地址 如果删除的是中间结点则找到中间结点的前一个结点让前一个结点的指针域保存这个结 点的后一个结点的地址即可// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos) {assert(pospos-next);SListNode* next pos-next;pos-next next-next;free(next);next NULL;
}
1.4.6单链表的销毁重新定义一个指针q保存p指向节点的地址然后p后移保存下一个节点的地址然后释放q对应的节点以此类推直到p为NULL为止。// 单链表的销毁
void SListDestroy(SListNode* plist) {while (plist){SListNode* next plist;free(plist);plist next;}
}
1.5双向带头不循环的链表虽然听起来复杂但其实只是结构复杂但是遍历还是增删查改插入和删除等都是十分简单的#includeList.hListNode* BuyListNode(int x)
{ListNode* new (ListNode*)malloc(sizeof(ListNode));new-data x;new-next NULL;new-prev NULL;return new;
}
// 创建返回链表的头结点.
ListNode* ListCreate(void)
{ListNode* newhead (ListNode*)malloc(sizeof(ListNode));newhead-next newhead;newhead-prev newhead;return newhead;
}
// 双向链表销毁
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur pHead;while (cur){ListNode* next cur-next;free(cur);cur next;}
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* tail pHead-prev;ListNode* new BuyListNode(x);new-next tail-next;tail-next-prev new;new-prev tail;tail-next new;
}
// 双向链表尾删
//需要注意此处如果链表初始化后不断删除会使得pHead指针指向的地方不确定,如果后续用户未重新创造双向链表的哨兵位而继续插入数据会导致非法访问。
//或者加个条件判断判断是否只有一个哨兵位是的话就不再进行删除。
void ListPopBack(ListNode* pHead)
{assert(pHead);ListNode* tail pHead-prev;tail-prev-next tail-next;//左边修改的是指针域右边是具体的链表的位置。tail-next-prev tail-prev;free(tail);//tail NULL;
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{ListInsert(pHead-next, x);
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;if (cur ! pHead){pHead-next cur-next;cur-next-prev pHead;free(cur);}cur NULL;
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x) {assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){if (cur-data x){return cur;}cur cur-next;}if (cur pHead){return NULL;}
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {assert(pos);ListNode *newBuyListNode(x);ListNode* prev pos-prev;new-next pos;pos-prev new;new-prev prev;prev-next new;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos) {ListNode* prev pos-prev;prev-next pos-next;pos-next-prev prev;free(pos);}着重注意这段// 双向链表尾删//需要注意此处如果链表初始化后不断删除会使得pHead指针指向的地方不确定,如果后续用户未重新创造双向链表的哨兵位而继续插入数据会导致非法访问。//或者加个条件判断判断是否只有一个哨兵位是的话就不再进行删除。void ListPopBack(ListNode* pHead){assert(pHead);ListNode* tail pHead-prev;tail-prev-next tail-next;//左边修改的是指针域右边是具体的链表的位置。tail-next-prev tail-prev;free(tail);//tail NULL;}
