顺序表优点支持随机访问内存空间是连续的顺序表的问题①要插删某个元素时效率低要移动大量元素②容量固定扩容成本高单链表优点插删效率高只需修改相邻节点动态申请节点无容量限制注单链表不能随机访问因为不连续。3.1概念与结构链表是一种物理存储结构上非连续非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。类比淡季时车次的车厢会相应减少旺季时车次的车厢未额外增加几节只需将货车里的某节车厢去掉或加上不会影响其他车厢每节车厢都是独立存在的链表地址不连续3.1.1结点相当于链表里的每节车厢。组成要存储的数据指针下一个节点的地址我们通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点3.1.2链表的打印void SLPrintf(SLTNode*phead) {SLTNode *pcurphead; while(pcur) {printf(%d,pcur-data); pcurpcur-next; } printf(\n); }3.2实现单链表typedef int SLTDataType; typedef struct SListNode {SLTDataType data; struct SListNode *next; }SLTNode;创建新节点 void SLTbuyNode(SLTDataType x) {SLTNode* newnode(SLTNode*)malloc(sizeof(SLTNode)); if(newnodeNULL) perror(malloc fail) exit(1); } newnode-datax; newnode-nextNULL; 尾插 void SLTPushBack(SLTNode**pphead,SLTDataType x) { SLTNode* newnodeSLTbuyNode(x); if(*ppheadNULL) { *ppheadnewnode;} else { SLTNode ptail*pphead; while(ptail-next) { ptailptail-next;} ptail-nextnewnode; } 头插 void SLTPushFront(SLTNode**pphead,SLTDataType x) { assert(pphead); SLTNode* newnodeSLTbuyNode(x); newnode-next*pphead; *ppheadnewnode; } 尾删 void SLTPopBack(SLTNode**pphead) { assert(pphead*pphead); if((*pphead)-nextNULL) { free(*pphead); *ppheadNULL; } else { SLTNode* prevNULL; SLTNode* ptail*pphead; while(ptail-next) { prevptail; ptailptail-next; } prev-nextNULL; free(ptail); ptailNULL; } 头删 void SLTPopFront(SLTNode**pphead) { assert(pphead*pphead); SLTNode* next*pphead-next; free(*pphead); *ppheadnext; } 在指定位置之前插入节点 void SLTInsert(SLTNode**pphead,SLTNode* pos,SLTDataType x) { assert(ppheadpos); if(pos*pphead) { SLTPushFront(pphead,x); } else { SLTNode* newnodeSLTbuyNode(x); SLTNode* prev*pphead; while(prev-nextpos) { prevprev-next; } prev-nextnewnode; newnode-nextpos; } 在指定位置之后插入节点 void SLTInsertAfter(SLTNode**pphead,SLTNode* pos,SLTDataType x) { assert(ppheadpos); SLTNode* newnodeSLTbuyNode(x); newnode-nextpos-next; pos-nextnewnode; } 删除pos节点 void SLTErase(SLTNode**pphead,SLTNode* pos) { assert(ppheadpos); if(pos*pphead) { SLTPopFront(pphead); else { SLTNode* prev*pphead; while(prev-nextpos) {prevprev-next; } prev-nextpos-next; free(pos); posNULL; } 删除pos之后的数据 void SLTEraseAfter(SLTNode**pphead,SLTNode* pos) {assert(ppheadpos); SLTNode* delpos-next; pos-nextdel-next; free(del) delNULL; } 销毁链表 void SListDestroy(SLTNode**pphead) { SLTNode* pcur*pphead; while(pcur) {SLTNode* nextpcur-next: free(pcur); pcurnext; } *ppheadNULL; } 查找 void SLTFind(SLTNode*phead,SLTDataType x) {SLTNode* pcurphead; while(pcur) {if(pcur-datax) {return pcur; } pcurpcur-next; } return NULL; }问为什么单链表创节点直接sizeofSLTNode顺序表还要×newcapacity答单链表每次只创一个节点,只取一个结构体大小顺序表一次不止加一个元素newcapacity就是表示一次加几个元素3.3单链表算法题移除链表元素typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head;int val) {ListNode* newHead,*newTail; newHeadnewTailNULL; ListNode* pcurhead; whlile(pcur) { if(pcur-val!val) { if(newHeadNULL) {newHeadnewTailpcur; } else {newTail-nextpcur; newTailnewTail-next; } } pcurpcur-next; } if(newTail) newTail-nextNULL; return newHead; }创建一个新链表把不是val的放进来反转链表typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) {if(head) {return head; } ListNode* n1,*n2,*n3; n1NULL;n2head;n3n2-next; while(n2) {n2-nextn1; n1n2; n2n3; if(n3) n3n3-next; } return n1; ]问为什么n1不直接从head开始答head反转后变成尾节点它的next为NULL,所以必须在前面设一个n1让head也反转如果n1head,虽然2指向1了但此时1还是指向2自循环了所以让所有节点都反转必须在head前设一个前驱节点链表的中间节点typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head {ListNode*slowhead; ListNode*fasthead; while(fastfast-next) {slowslow-next; fastfast-next-next; } return slow; }合并两个有序链表struct ListNode* mergeTwoList(struct ListNode*list1,struct ListNode*list1) { if(list1) { return list2; } if(list2) { return list1; } ListNode*newHead,*newTail; newHeadnewTail(ListNode*)malloc(sizeof(ListNode)); ListNode*list1l1; ListNode*list2l2; while((l1l2) { if(l1-vall2-val) { newTail-nextl1; newTailnewTail-next; l1l1-next; } else { newTail-nextl2; l2l2-next; } } if(l2) {newTail-nextl2; } if(l1) {newTail-nextl1;} ListNode* rerHeadnewHead-next; free(newHead); newHeadNULL; return retHead; }问为什么合并链表newHead...要申请空间答①合并链表头节点先置空后面必须每次考虑链表为空的情况开始置空只是初始化之后循环仍需判断空不空导致代码冗余②直接给一个空间就不用考虑空不空的情况了③起一个哨兵位的作用链表的回文结构bool chkPalindrome(ListNode* A) {ListNode* midmiddleNode(A); ListNode* rightreverseList(mid); ListNode* leftA; while(right) {if(left-val!right-val) { return false; } leftleft-next; rightright-next; } return ture; }找中间节点断开左右端点比较是否相等相交链表struct ListNode*getIntersectionNode(struct ListNode *headA,struct ListNode *headB) {ListNode*paheadA; ListNode*pbheadB; int sizeA0;sizeB0; while(pa) {sizeA; papa-next; } while(pb) {sizeB; pbpb-next; } int gapabs(sizeA-sizeB) ListNode* shortListheadA; ListNode* longListheadB; if(sizeAsizeB) {longListheadA; shortListheadB; } while(gap--) {longListlongList-next; } while(shortList) {if(longListshortList) {return longList; } longListlongList-next; shortListshortList-next; } return NULL; }算长度差长链表先走差步然后两个表同时往后遍历判断链表是否有环typedef struct ListNode ListNode; bool hasCycle(struct ListNode* head) { ListNode*slow; ListNode*fast; while(fastfast-next) {slowslow-next; fastfast-next-next; if(slowfast) { return true; } } return false; }快慢指针在环里一定会相遇返回入环的第一个节点typedef struct ListNode ListNode; struct ListNode* detectCycle(struct ListNode* head) { ListNode*slow; ListNode*fast; while(fastfast-next) { slowslow-next; fastfast-next-next; if(slowfast) { ListNode* pcurhead; while(pcur!slow) { pcur[cur-next; slowslow-next: } return pcur; } } return NULL; }相遇点和头节点到入环第一个节点距离相等3.4双向链表带头链表里的头节点实际为哨兵位不存储任何有效元素3.4.1实现双向链表typedef int LTDataType; typedef sturct ListNode {struct ListNode* next; struct ListNode* prev; LTDataType data; }LTNode;初始化 LTNode* LTBuyNode(LTDataType x) { LTNode* newnode(LTNode*)malloc(sizeof(LTNdode)); if(newnodeNULL) {perror(malloc fail); exit(1); } newnode-datax; newnode-nextnewnode-prevnewnode; return newnode; } void LTInit(LTNode**pphead) {assert(ppheadd); *ppheadLTBuyNode(-1) }尾插 void LTPushBack(LTNode* phead,LTDataTyoe x) {assert(phead); LTNode* newnodeLTBuyNode(x); newnode-prevphead-prev; newnide-nextphead; } 头插: void LTPushFront(LTNode* phead,LTDataTyoe x) {assert(phead); LTNode* newnodeLTBuyNode(x); newnode-nextphead-next; newnode-prevphead; } 尾删 void LTPopBack(LTNode* phead) {assert(phead); LTNode* delphead-next; del-prev-nextphead; phead-prevdel-prev; free(del); delNULL; } 头删 void LTPopFront(LTNode* phead) { assert(phead); LTNode* delphead-next; del-next-prevphead; phead-nextdel-next; free(del); delNULL; } 在pos位置之后插入数据 void LTInsert(LTNode* phead,LTDataTyoe x) {assert(pos); LTNode* newnodeLTBuyNode(x); newnode-nextpos-next; newnode-prev-pos; } 删除pos位置的节点 void LTErase(LTNode*pos) {assert(pos); pos-next-prevpos-prev; pos-prev-nextpos-next; free(pos); posNULL; } 销毁 void LTDestroy(LTNode* phead) {LTNode* pcurphead-next; while(pcur) {LTNode* nextpcur-next; free(pcur); pcurNULL; } free(phead); pheadNULL; }尾/头插从新节点看前后连接啥尾/头删用del保存要删的节点注意这里的头删删的是phead-next双向链表的头节点不可被删除通过del看怎样连是phead然后再看phead和del的关系当单链表为空时指向第一个节点的指针为空当双向链表中为空时链表中只有一个头节点问为什么双向链表不传二级指针答带头双向链表不修改头节点只改节点指向的内容房子里的家具一级即可头节点是指针房子本身单链表里要改必须传二级