影视网站设计,网络维护招聘信息,自建企业邮箱,湛江专业雷剧视频http://blog.csdn.net/lanxuezaipiao/article/details/22100021基本函数#xff08;具体代码实现见后面#xff09; 1#xff0c;构造节点 //定义节点类型 struct Node { int value; Node*next; }; 2#xff0c;分配节点 //之所以要分配节点原因是需要在分配函数中…http://blog.csdn.net/lanxuezaipiao/article/details/22100021基本函数具体代码实现见后面 1构造节点 //定义节点类型 struct Node { int value; Node*next; }; 2分配节点 //之所以要分配节点原因是需要在分配函数中进行初始化并且也利于判断是否分配成功。 Node* applyNode(); 3在头部增加节点 //增加节点在头部无头结点,返回值的原因是由于传入并非指针的引用。 Node* addNodeH(Node* Head,Node* InsertNode); 4在尾部增加节点 //增加节点在尾部无头结点,返回值的原因是由于传入并非指针的引用。 Node* addNodeT(Node* Head,Node* InsertNode); 5以升序方式增加节点 Node* addNodeSort(Node* Head,Node* InsertNode); 6构造链表 //没有额外的表头结点。 //选择参数choose分别对应以何种方式构造链表1为头部增加节点2为尾部增加节点3为升序增加节点。 Node* createList(int n,int choose); 7打印链表 void printList(Node*Head); 8释放链表 void freeList(Node* Head); 9链表节点数 int numOfNodes(Node* Head); 10定位函数 //传入参数i表示第几个节点从1开始返回该节点指针 Node* locateNodeI(Node*Head,int i); 11查找函数 //查找值为value的链表 int SearchList(Node*Head,int value); 12删除节点 //删除位置i的节点 bool deleteNodeI(Node*Head,int i); 13排序函数 //冒泡排序链表具体的做法是“狸猫换太子”即只交换节点中的值对链表结构不做改动。 void sortList(Node* Head); 高级函数具体代码实现见后面 1.单链表反转 思路1O(n^2). 我的做法是“狸猫换太子”不进行改动链表结构只首尾交换len/2次。但是在本函数中用到了定位函数定位函数实际上是遍历了一遍整个链表所以综合效率很低达到O(n^2). void reverseList(Node*Head) 思路2O(n). 就最一般的情况而言没有之前写的那么多辅助函数即条件单纯为只有Head指向一个单链表。那么可以实现On效率。做法是用三个相邻的指针进行遍历在遍历的途中更改指针方向。当然要注意链表数目分情况和拆链的处理。 Node* reverseList2(Node*Head) 2.找出单链表的倒数第4个元素 思路1O(2n) 先遍历一遍链表记录节点个数。然后定位该位置count-3定位函数实际上也是遍历一遍所以总效率O(n)O(n) bool findLast4th1(Node*Head,int ans) 思路2O(n) 如果题目限制要求仅允许遍历一遍则可以按如下方法进行。先定义两个指针第一个指针先走4步然后从这时开始第一个指针和第二个指针同时继续走即第一个指针和第二个指针相差4步。则第二个指针到头时第一个指针指向倒数第四个。注意要考虑链表长度。 bool findLast4th2(Node*Head,int ans) 思路3O(n) 做一个数组arr[4]让我们遍历单链表把第1个、第5个、第9个……第4N1个扔到arr[0]把第2个、第6个、第10个……第4N2个扔到arr[1]把第3个、第7个、第11个……第4N3个扔到arr[2]把第4个、第8个、第12个……第4N个扔到arr[3]这样随着单链表的遍历结束arr中存储的就是单链表的最后4个元素找到最后一个元素对应的arr[i]让k(i1)%4则arr[k]就是倒数第4个元素。如果不易理解画个图就好了。注意增加的空间只需要4个所以是常数级的。比如加到第5个节点时就会把arr[0]中的值冲掉。 bool findLast4th3(Node*Head,int ans) 3.找出单链表的中间元素 思路1O(2n) 在函数的支持下直接求整个链表的长度然后定位中间元素。 bool getMiddleOne1(Node*Head,intans) 思路2O(n) 如果仍要求只遍历一遍。类似于上题还是使用两个指针first和second只是first每次走一步second每次走两步 bool getMiddleOne2(Node*Head,intans) 4.删除无头单链表的一个节点 思路 注意这里的要求是无头链表即未知Head指针。但是知道的是current指针指向该链表的某一位置。现在希望删除该指针而不影响整个链表。即虽然不知道Head指针但是该链还是完整的。 首先需要明确一点即current指针之前的链表段落是不可能知道的。这是由链表的单向性决定的。没有任何技术可以做到这一点。 其次删除链表某节点该节点不能是首节点因为首节点一旦删除Head无法找到该链表了。 再次删除链表某节点该节点不能是尾节点因为尾节点一旦删除则尾节点的前一节点的指针域无法置0因为单链无法回溯。 所以题意解释为删除无头单链表的一个节点既非首节点也非尾节点。 解法是利用“狸猫换太子”。首先复制current指针的下一个节点的value到current节点中。然后删除current的下一节点。 void deleteNoHeadList(Node*Head,Node*Current) 4.增加无头单链表的一个节点一个指针current指向单链表中的一个节点在该节点之前增加一个节点insertNode。 思路 思路还是“狸猫换太子”即在current之后增加一个节点insertNode然后交换insertNode和current的值。 由于在current之后增加节点这个操作在current指向首尾都可以实现。 所以这道问题转化为增加无头单链表的一个节点current指针指向该链表某节点可以为首尾在其之前增加节点p。 void addNoHeadList(Node*Head,Node*Current,Node*insertNode) 5.两个不交叉的有序链表的合并 思路O(len1len2) 合并的办法如下首先用Node* 方式传入两个链表的头指针Head1Head2。用指针引用是因为最后要修改Head1和Head2均为NULL。否则可能被其他人误引用了。然后定义一个合并后的链表的头指针和尾指针Head和Tail。然后不断比较Head1和Head2的首元素加入到新的合并的链表中。注意一点这里的加入并不是先增加申请一个节点分配然后删除释放原来的节点。而是直接将指针指向。也就是说在合并的过程中只是指针指向改变了完全没有申请新的内存和释放节点空间。最后如果有一个Head1或Head2的已经空了则直接将剩余链表连接到Head即可。当然要注意很多细节。 Node* mergeTwoList(Node* Head1,Node* Head2) 6.有个二级单链表其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级单链表。 思路 注意要重新定义二级单链表的结构具体的算法是把所有的下级单链表顺次连接。即可。程序代码略。 7.单链表交换任意两个元素不包括表头 思路 利用“狸猫换太子”不破坏链表结构只交换二者Node* cur1和Node* cur2的指向的值。程序代码略。 其中的任意两个元素由外界给定该两个节点的指针。 8.判断单链表是否有环6形状如何找到环的“起始”点如何知道环的长度 思路 注意分析题意题意并非是说单链表完全成O形状的环而是说单链表成6形状的环。 首先判断是否有环为此我们建立两个指针从Head一起向前跑一个步长为1一个步长为2用 while(直到步长2的跑到结尾) { 检查两个指针是否相等直到找到为止。 } 来进行判断。 原因是在这场跑步中结束循环有两种可能其一是原来无环所以2先跑到结尾因为2比1快二者不可能相等。其二是原来是有环的因为这场赛跑永远没有z终点但是在环中由于2比1快因而必定套圈也即2追上了1这在无环中是不可能出现的情况。 而进行计算环的长度只要找到交汇点然后在圈中跑一次就可以了。 int getCircleLength(Node* cross) bool judgeCircleExists(Node* Head) 9.判断两个单链表是否相交 注意这里是判断是否相交。对于判断问题来讲相对还是比较简单的。注意单链表并非不能有重复元素。 思路1O(len1*len2) 把第一个链表的指针值逐项存在hashtable中遍历第2个链表的每一项的指针值如果能在第一个链表中找到则必然相交。但是C的STL模板中的hash不太会用。所以我使用了set集合不过貌似set集合是使用遍历的方式来查找元素是否在集合中的所以效率是比较低的至少在O(len1*len2)级别。 bool judgeIntersectList1(Node* Head1,Node* Head2) 思路2O(len1len2) 把一个链表A接在另一个链表B的末尾如果有环则必然相交。如何判断有环呢从A开始遍历如果能回到A的表头则肯定有环。 注意在返回结果之前要把刚才连接上的两个链表断开恢复原状。 bool judgeIntersectList2(Node* Head1,Node* Head2) 思路3Olen1len2 如果两个链表的末尾元素相同指针相同即为同一个元素而非值相等则必相交。 bool judgeIntersectList3(Node* Head1,Node* Head2) 10.两个单链表相交计算相交点 思路1 分别遍历两个单链表计算出它们的长度M和N假设M比N大则长度M的链表先前进M-N然后两个链表同时以步长1前进前进的同时比较当前的元素如果相同则必是交点。 Node* getIntersectPoint(Node* Head1,Node* Head2) 思路2 将指针p1,p2定位到两个链表的尾部然后同时将两个指针前移不可以因为是单向链表 11.用链表模拟大整数加法运算 思路 对于高精度大数计算没有数组那么高效具体数组的做法参见OJ高精度链表的好处是可以定义节点其中包含指数次数和值两部分比如20001可以表示为(2,4)-(1,0)-NULL其中2表示值4表示10的4次方。这样的话如果数属于稀疏型的则以较少的空间保存了值。具体程序略。 12.单链表排序 思路 参见基本函数13//冒泡排序链表具体的做法是“狸猫换太子”即只交换节点中的值对链表结构不做改动。 void sortList(Node* Head); 13.删除单链表中重复的元素 思路 用Hashtable辅助遍历一遍单链表就能搞定。同高级函数9的原因我不太会使用CSTL中的hash。而如果使用set集合来存储链表中的所有的值实际上效率和每次重新遍历单链表是一样的。“用了c标准库中的set来保存访问过的元素所以很方便的就可以判断当前节点是否在set集合中直接使用set提供的find函数就可以了。而且使用set的查找在时间复杂度上比较低。”我不太清楚STL中set集合的实现方式如果是基于类似hash结构的话那自然效率O(1),而如果是数组的话实际在遍历一遍所以效率O(n)。不过貌似后者的可能性大一些。 void DeleteDuplexElements(Node*Head); 基本函数代码 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 2分配节点 //分配节点 //将分配内存和初始化该节点放在一个函数中 Node* applyNode() { Node* newNode; if((newNode(Node*)malloc(sizeof(Node)))NULL) { cout分配内存失败endl; ::exit(0); } //建立该节点信息 cout请输入本节点值endl; cinnewNode-value; newNode-nextNULL; return newNode; } 3在头部增加节点 //在表头增加节点 //在头指针所指向的链表中增加一个节点,插入头部 //这里必须要返回Node*来进行更新因为传入的Head是Node*类型而非Node* Node* addNodeH(Node* Head,Node* InsertNode) { if(HeadNULL) { HeadInsertNode; } else { InsertNode-nextHead; HeadInsertNode; } return Head; } 4在尾部增加节点 //在表尾增加节点 //在头指针所指向的链表中增加一个节点,插入尾部 //这里必须要返回Node*来进行更新因为传入的Head是Node*类型而非Node* Node* addNodeT(Node* Head,Node* InsertNode) { if(HeadNULL) { HeadInsertNode; } else { Node* pHead; while(p-next!NULL) { pp-next; } p-nextInsertNode; } return Head; } 5以升序方式增加节点 //以升序增加节点 //这里必须要返回Node*来进行更新因为传入的Head是Node*类型而非Node* Node* addNodeSort(Node* Head,Node* InsertNode) { if(HeadNULL) { HeadInsertNode; } else { Node* pHead; //注意这里把(p-value)(InsertNode-value)放在p-next!NULL前面是有原因的这是避免为了考虑在Head-[4]加入[1]的情况 while((p-value)(InsertNode-value)p-next!NULL) { pp-next; } if((p-value)(InsertNode-value))//因为(p-value)(InsertNode-value)而退出表示在p前增加节点狸猫换太子 { //先在p后增加节点 InsertNode-nextp-next; p-nextInsertNode; //再交换p和InsertNode的值 swap(p-value,InsertNode-value); } else//因为p-nextNULL而退出表示在尾增加节点 { p-nextInsertNode; } } return Head; } 6构造链表 //建立n个节点的链表 choose1,在表头加入choose2在表尾加入,choose3按value值升序加入 Node* createList(int n,int choose) { Node *HeadNULL,*pNULL; for(int i0;in;i) { papplyNode(); if(choose1) { HeadaddNodeH(Head,p); } else if(choose2) { HeadaddNodeT(Head,p); } else if(choose3) { HeadaddNodeSort(Head,p); } } return Head; } 7打印链表 //遍历链表并输出 void printList(Node*Head) { Node*pHead; while(p!NULL) { coutp-value-; pp-next; } coutNULLendl; } 8释放链表 //释放链表 void freeList(Node* Head) { Node* tmpHead; while(tmp!NULL) { HeadHead-next; free(tmp); tmpHead; } HeadNULL; } 9链表节点数 //数节点个数 int numOfNodes(Node* Head) { int count0; while(Head!NULL) { count; HeadHead-next; } return count; } 10定位函数 //定位第i个节点i从1开始 Node* locateNodeI(Node*Head,int i) { //cout定位i位置endl; Node* posNULL; int countnumOfNodes(Head); if(i0||icount) { cout定位越界endl; } else { posHead; for(int j1;ji;j) { pospos-next; } } return pos; } 11查找函数 //查找值value并返回第一个出现该值的位置如果需要引用其指针可以再locate该位置 int SearchList(Node*Head,int value) { Node* pHead; int pos0; bool findfalse; while(p!NULL) { pos; if(p-valuevalue) { findtrue; break; } pp-next; } if(find) return pos; else return -1; } 12删除节点 //删除某位置i的节点 bool deleteNodeI(Node*Head,int i) { Node* plocateNodeI(Head,i); if(pNULL) { return false; } else { if(pHead)//说明p是头节点。 { Headp-next; free(p); } else { Node* preplocateNodeI(Head,i-1);//定位前一个,必定存在 prep-nextp-next; free(p); } return true; } } 13排序函数 //链表排序 //排序的方法是不破坏结构有“狸猫换太子”的意思只进行value的交换不破坏链表结构 void sortList(Node* Head) { int countnumOfNodes(Head); if(count0||count1) { return ; } //冒泡排序 bool exchange; for(int i2;icount;i) { exchangefalse; for(int jcount;ji;j--) { Node* p1locateNodeI(Head,j); Node* p2locateNodeI(Head,j-1); if(p1-valuep2-value) { exchangetrue; swap(p1-value,p2-value); } } if(!exchange) break; } } 高级函数代码 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1.单链表反转1 //单链表反转(O(n^2)) void reverseList(Node*Head) { int countnumOfNodes(Head); //“狸猫换太子”首尾交换 for(int i1;icount/2;i) { Node* p1locateNodeI(Head,i); Node* p2locateNodeI(Head,count1-i); swap(p1-value,p2-value); } } 1.单链表反转2 //单链表反转O(n) Node* reverseList2(Node*Head) { if(HeadNULL||Head-nextNULL)//空链和单节点 { return Head; } Node* p1Head; Node* p2Head-next; Node* p3Head-next-next; if(p3NULL)//只有两个节点 { p1-nextNULL; p2-nextp1; Headp2; return Head; } else//至少三个节点 { p1-nextNULL; while(p3!NULL) { p2-nextp1; p1p2; p2p3; p3p3-next; } p2-nextp1; Headp2; return Head; } } 2.找出单链表的倒数第4个元素1 //查找倒数第四个元素,传入ans中 O(2N) bool findLast4th1(Node*Head,int ans) { //先确定节点个数 int countnumOfNodes(Head); //定位count-4 Node* plocateNodeI(Head,count-3); if(p!NULL) { ansp-value; return true; } else { return false; } } 2.找出单链表的倒数第4个元素2 //查找倒数第四个元素,传入ans中 O(N),只遍历一遍 bool findLast4th2(Node*Head,int ans) { Node* p1Head; Node* p2Head; //p1先走4步。 for(int i0;i4;i) { if(p1!NULL) { p1p1-next; } else { return false;//肯定链表长度不够 } } //同步移动 while(p1!NULL) { p1p1-next; p2p2-next; } ansp2-value; return true; } 2.找出单链表的倒数第4个元素3 //查找倒数第四个元素,传入ans中 O(N) bool findLast4th3(Node*Head,int ans) { int arr[4]; Node* pHead; int i0; int count0; while(p!NULL) { arr[i]p-value; pp-next; i(i1)%4; count; } if(count4) { return false; } else { ansarr[i]; return true; } } 3.找出单链表的中间元素1 //获取中间元素O(2n) bool getMiddleOne1(Node*Head,intans) { int countnumOfNodes(Head); if(count0) { return false; } else { Node* plocateNodeI(Head,(count1)/2); ansp-value; return true; } } 3.找出单链表的中间元素2 //获取中间元素O(n) //类似于上题还是使用两个指针first和second只是first每次走一步second每次走两步 bool getMiddleOne2(Node*Head,intans) { if(HeadNULL)//空链表 { return false; } else { Node*firstHead; Node*secondHead-next; while(second!NULLsecond-next!NULL) { firstfirst-next; secondsecond-next; secondsecond-next; } ansfirst-value; return true; } } 4.删除无头单链表的一个节点 //删除无头单链表的非首尾节点狸猫换太子; void deleteNoHeadList(Node*Head,Node*Current) { Node* pCurrent-next; //一定是非首尾节点,否则会出错 Current-valueCurrent-next-value; Current-nextCurrent-next-next; free(p); } 4.增加无头单链表的一个节点一个指针current指向单链表中的一个节点在该节点之前增加一个节点insertNode。 //增加无头单链表的一个节点current指针指向该链表某节点可以为首尾在其之前增加节点insertNode。 void addNoHeadList(Node*Head,Node*Current,Node*insertNode) { insertNode-nextCurrent-next; Current-nextinsertNode; swap(Current-value,insertNode-value); } 5.两个不交叉的有序链表的合并 //合并两个有序的链表 Node* mergeTwoList(Node* Head1,Node* Head2) { Node* HeadNULL;//合并后的链表 Node* TailNULL;//合并后链表的尾指针 //p1,p2遍历两个链表 Node* p1Head1; Node* p2Head2; while(!(p1NULL||p2NULL)) { if(p1-valuep2-value) { if(HeadNULL)//第一个节点 { Headp1; TailHead; } else { Tail-nextp1; TailTail-next; } p1p1-next; } else { if(HeadNULL)//第一个节点 { Headp2; TailHead; } else { Tail-nextp2; TailTail-next; } p2p2-next; } } if(p1!NULL) { if(Head!NULL) { Tail-nextp1; } else { Headp1; } } else if(p2!NULL) { if(Head!NULL) { Tail-nextp2; } else { Headp2; } } Head1NULL; Head2NULL; return Head; } 8.判断单链表是否有环6形状如何找到环的“起始”点如何知道环的长度1 //计算单链表成环环的长度,输入的参数为成环的交汇点。 int getCircleLength(Node* cross) { int len1; Node* pcross; while(p-next!cross)//千万不能写作p-next!p { len; pp-next; } return len; } 8.判断单链表是否有环6形状如何找到环的“起始”点如何知道环的长度2 //判断单链表是否有环,并且返回环的长度 bool judgeCircleExists(Node* Head,int len) { if(HeadNULL)//空链 { return false; } else if(Head-nextHead)//1个节点且成环 { return true; } else if(Head-nextNULL)//1个节点不成环 { return false; } //至少两个节点情形 //初始化跑步机 Node* p1Head;//跑步者1号,跑到第1个节点 Node* p2Head-next;//跑步者2号跑到第2个节点 while(p2!NULLp2-next!NULL)//利用了短路 { p1p1-next; p2p2-next-next; if(p1p2) { //此时p1p2即为交汇点 lengetCircleLength(p1); return true; } } return false; } 9.判断两个单链表是否相交1 //判断两个单链表是否相交Y型 bool judgeIntersectList1(Node* Head1,Node* Head2) { setNode*s; Node* p1Head1; Node* p2Head2; while(p1!NULL) { s.insert(p1); p1p1-next; } while(p2!NULL) { if(s.find(p2)!s.end()) { s.clear(); return true; } p2p2-next; } s.clear(); return false; } 9.判断两个单链表是否相交2 //判断两个单链表是否相交Y型 bool judgeIntersectList2(Node* Head1,Node* Head2) { if(Head1NULL||Head2NULL) { return false; } Node* p1Head1; Node* p2Head2; //先找到链表2的末尾,由p2指向 while(p2-next!NULL) { p2p2-next; } //将链表1的表头与链表2的表尾连接 p2-nextp1; //遍历链表1如果回到了链表1表头则相交 while(p1!NULL) { if(p1-nextHead1) { //记得恢复原状 p2-nextNULL; return true; } p1p1-next; } //记得恢复原状 p2-nextNULL; return false; } 9.判断两个单链表是否相交3 //判断两个单链表是否相交Y型 bool judgeIntersectList3(Node* Head1,Node* Head2) { if(Head1NULL||Head2NULL) { return false; } Node* p1Head1; Node* p2Head2; //p1与p2记录两链表的尾指针 while(p1-next!NULL) { p1p1-next; } while(p2-next!NULL) { p2p2-next; } if(p1p2) { return true; } return false; } 10.两个单链表相交计算相交点 //两链表相交计算相交点 Node* getIntersectPoint(Node* Head1,Node* Head2) { int len1numOfNodes(Head1); int len2numOfNodes(Head2); int initMoveabs(len1-len2); Node* p1Head1; Node* p2Head2; if(len1len2) { for(int i0;iinitMove;i) { p1p1-next; } } else { for(int i0;iinitMove;i) { p2p2-next; } } while(p1!NULLp2!NULL) { if(p1p2) { return p1; } p1p1-next; p2p2-next; } return NULL; } 12.单链表排序 //链表排序 //排序的方法是不破坏结构有“狸猫换太子”的意思只进行value的交换不破坏链表结构 void sortList(Node* Head) { int countnumOfNodes(Head); if(count0||count1) { return ; } //冒泡排序 bool exchange; for(int i2;icount;i) { exchangefalse; for(int jcount;ji;j--) { Node* p1locateNodeI(Head,j); Node* p2locateNodeI(Head,j-1); if(p1-valuep2-value) { exchangetrue; swap(p1-value,p2-value); } } if(!exchange) break; } } 13.删除单链表中重复的元素 //删除单链表中的重复元素使用set集合来实现 void DeleteDuplexElements(Node*Head) { if(HeadNULL||Head-nextNULL)//链表为空或者只有一个元素 { return ; } //以下至少两个元素 setints; Node* p1Head; Node* p2Head-next; s.clear(); s.insert(p1-value); while(p2!NULL)//要删除的不可能是链表头,因为如果是链表头则集合还为空。 { if(s.find(p2-value)s.end())//没有 { s.insert(p2-value); p2p2-next; p1p1-next; } else//已经有则要删除该节点 { //不可能是链表头 //如果是链表尾 if(p2-nextNULL) { p1-nextNULL; free(p2); p2NULL; } else { p1-nextp2-next; free(p2); p2p1-next; } } } }
