数据结构做题笔记

1.链表逆序代码**#includestdio.h#includestdlib.htypedefstructNode{intdata;structNode*next;}Node;structNode*reverseList(Node*head){Node*preNULL;Node*curhead;Node*nextNULL;while(cur!NULL){nextcur-next;cur-nextpre;precur;curnext;}returnpre;}Node*CreateNode(intval){Node*NewNode(Node*)malloc(sizeof(Node));NewNode-dataval;NewNode-nextNULL;returnNewNode;}Node*CreateList(intarr[],intn){if(n0)returnNULL;Node*headCreateNode(arr[0]);Node*tailhead;for(inti1;in;i){tail-nextCreateNode(arr[i]);tailtail-next;}returnhead;}voidprintList(Node*head){Node*phead;while(p!NULL){printf(%d,p-data);pp-next;}printf(\n);}intmain(){intarr[]{1,2,3,4,5};intnsizeof(arr)/sizeof(arr[0]);Node*headCreateList(arr,n);printf(原链表:);printList(head);printf(现链表:);headreverseList(head);printList(head);}逆序过程:初始链表1 - 2 - 3 -4 -5 - NULLpreNULLcur1next 保存 21 的 next 指向 pre (NULL)pre1cur2next 保存 32 的 next 指向 1pre2cur3next 保存 43 的 next 指向 2pre3cur4next 保存 54 的 next 指向 3pre4cur5next 保存 NULL5 的 next 指向 4pre5curNULL循环结束返回 pre5新头节点反转后5-4-3-2-1-NULL2.判断链表是否成环#includestdio.h#includestdlib.htypedefstructNode{intdata;structNode*next;}Node;inthasCycle(Node*head){if(headNULL||head-nextNULL)return0;Node*slowhead;Node*fasthead;while(fast!NULLfast-next!NULL){slowslow-next;fastfast-next-next;if(slowfast){return1;}}return0;}Node*CreateNode(intval){Node*NewNode(Node*)malloc(sizeof(Node));NewNode-dataval;NewNode-nextNULL;returnNewNode;}Node*CreateList(intarr[],intn){if(n0)returnNULL;Node*headCreateNode(arr[0]);Node*tailhead;for(inti1;in;i){tail-nextCreateNode(arr[i]);tailtail-next;}returnhead;}通过快慢指针是否相遇判断是否有环;3.数组与单链表的区别数组顺序表内存连续一块空间依靠下标偏移量访问元素。单链表内存分散节点分散在堆中靠指针next串联没有下标。数组:优点:支持随机访问按下标直接取元素查找速度快连续内存缓存命中率高访问效率高结构简单没有指针额外占用内存。缺点:容量固定需要提前分配空间在中间插入、删除元素需要移动后面所有元素效率低容易出现空间浪费开辟大数组只用一部分链表优点:动态分配内存节点按需创建没有固定容量限制已知位置时插入、删除只修改指针不需要移动元素不会预留多余空间。缺点:不能随机访问查找元素必须从头节点开始遍历每个节点要额外存储指针next有额外空间开销连续内存差缓存效果差查找指定位置元素时间复杂度 (O(n))。4.栈和队列的区别以及两者的业务使用场景栈Stack后进先出 LIFO只能在同一端栈顶进行插入入栈和删除出栈。队列Queue先进先出 FIFO在队尾插入队头删除两端操作。栈适用场景递归调用、括号匹配、撤销操作、表达式计算。队列适用场景任务排队、广度优先遍历、消息队列、打印任务调度。5.链表的排序代码#includestdio.h#includestdlib.htypedefstructNode{intdata;structNode*next;}Node;Node*CreateNode(intval){Node*NewNode(Node*)malloc(sizeof(Node));NewNode-dataval;NewNode-nextNULL;returnNewNode;}Node*CreateList(intarr[],intn){if(n0)returnNULL;Node*headCreateNode(arr[0]);Node*tailhead;for(inti1;in;i){tail-nextCreateNode(arr[i]);tailtail-next;}returnhead;}Node*findMid(Node*head){Node*slowhead;Node*fasthead-next;while(fast!NULLfast-next!NULL){slowslow-next;fastfast-next-next;}returnslow;}Node*merge(Node*left,Node*right){Node dummy;Node*pdummy;dummy.nextNULL;while(left!NULLright!NULL){if(left-dataright-data){p-nextleft-data;leftleft-next;}else{p-nextright-data;rightright-next;}pp-next;}p-nextleft?left:right;returndummy.next;}Node*MergeSortList(Node*head){if(headNULL||head-nextNULL)returnhead;Node*midfindMid(head);Node*rightHeadmid-next;mid-nextNULL;Node*leftMergeSortList(head);Node*rightMergeSortList(rightHead);returnmerge(left,right);}fast 初始化为 head-next目的偶数节点时slow 停在左中点方便切分merge函数中注意:left?left:right通过条件把两个长短不一致的链表接到一起举个例子:left 链表1 - 3 - 5right 链表2 - 4 - 6 - 7 - 8循环过程依次比较 1,2,3,4,5把它们接到结果链。循环结束left NULLleft 已经用完right还剩6-7-8。执行p-next left ? left : right;left 是 NULL所以p-next right直接把6-7-8整条接上。反过来left1-3-5-9-10right2-4循环结束right NULLleft 剩余9-10直接接上。MergeSortList函数要注意:mid-next NULL如果不断开递归时还是整条链表会无限递归死循环完整流程举例:原始链表4 - 2 - 7 - 1 - 3第一次切分4,2,7和1,3递归切左半段4,2,7→4,2和7递归切4,2→4和2两个单节点触发递归出口merge(4,2) →2-4merge(2-4,7) →2-4-7递归切右半段1,3→1和3merge 得到1-3最后 merge (2-4-7,1-3) →1-2-3-4-76.编写快排或其它高性能排序算法的代码并描述时间复杂度与空间复杂度以及稳定性#includestdio.hvoidswap(int*a,int*b){inttmp*a;*a*b;*btmp;}intpartition(intarr[],intleft,intright){intpivotarr[left];intileft,jright;while(ij){while(ijarr[j]pivot)j--;while(ijarr[i]pivot)i;swap(arr[i],arr[j]);}swap(arr[left],arr[i]);returni;}voidquickSort(intarr[],intleft,intright){if(leftright)return;intpospartition(arr,left,right);quickSort(arr,left,pos-1);quickSort(arr,pos1,right);}intmain(){intarr[]{5,3,8,6,2,9,1,7,4};intnsizeof(arr)/sizeof(arr[0]);quickSort(arr,0,n-1);for(inti0;in;i){printf(%d ,arr[i]);}return0;}使用刚才代码里的 partition基准 pivot arr[left]左右指针 i、j示例数组arr [5, 3, 8, 6, 2, 9, 1, 7, 4]本次调用left0right8pivot arr[0] 5i 初始 0j 初始 8j 先往左走找小于 pivot 的元素遇到就停下i 再往右走找大于 pivot 的元素遇到就停下如果 ij交换 arr [i] 和 arr [j]循环直到 ij交换 arr [left] 和 arr [i]把基准值放到正确位置返回 i主要作用为返回基准值的下标,便于后一步递归函数的使用.时间复杂度空间来自递归调用栈平均情况(O(n\log n))每次划分把数组分成大致两半递归深度(\log n)每层总比较次数n。最好情况(O(n\log n))每次 pivot 刚好把数组均等分割。最坏情况(O(n^2))数组已经有序 / 逆序每次划分一边只有 1 个元素递归深度n。*不稳定排序相等元素相对位置会被打乱7.二分法查找代码#includestdio.hintbinarySearch(intarr[],intn,inttarget){intleft0;intrightn-1;intmid;while(leftright){intmid(leftright)/2;if(arr[mid]target){returnmid;}elseif(arr[mid]target){leftmid1;}else{rightmid-1;}}return-1;}这个方法只能用于有序数列(数组),不能用于链表.8.合并有序链表代码编写#includestdio.h#includestdlib.htypedefstructNode{intdata;structNode*next;}Node;Node*CreateNode(intval){Node*p(Node*)malloc(sizeof(Node));p-dataval;p-nextNULL;returnp;}Node*mergeList(Node*L1,Node*L2){Node*dummyCreateNode(-1);Node*taildummy;while(L1!NULLL2!NULL){if(L1-dataL2-data){tail-nextL1;L1L1-next;}else{tail-nextL2;L2L2-next;}tailtail-next;}if(L1!NULL)tail-nextL1;elsetail-nextL2;Node*resdummy-next;free(dummy);returnres;}哨兵头结点dummy)尾指针依次比较两个链表当前节点把小的接入结果链表,真正的头结点是dummy-next.