数据结构链表奇思妙想.doc

数据结构 链表 奇思妙想数据结构-链表-奇思妙想2010-12-14 22：06基本函数1，构造节点：/定义节点类型struct Nodeint 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。高级函数1.单链表反转思路1：O(n2).我的做法是狸猫换太子，不进行改动链表结构，只首尾交换len/2次。但是在本函数中用到了定位函数，定位函数实际上是遍历了一遍整个链表，所以综合效率很低，达到O(n2).void reverseList(Node*Head)思路2：O(n).就最一般的情况而言(没有之前写的那么多辅助函数，即条件单纯为只有Head指向一个单链表)。那么可以实现O(n)效率。做法是用三个相邻的指针进行遍历，在遍历的途中，更改指针方向。当然要注意链表数目分情况，和拆链的处理。Node*reverseList2(Node*Head)2.找出单链表的倒数第4个元素思路1：O(2n)先遍历一遍链表记录节点个数。然后定位该位置count-3，定位函数实际上也是遍历一遍，所以总效率O(n)+O(n)bool findLast4th1(Node*Head,int&ans)思路2：O(n)如果题目限制要求，仅允许遍历一遍，则可以按如下方法进行。先定义两个指针，第一个指针先走4步，然后从这时开始，第一个指针和第二个指针同时继续走，即第一个指针和第二个指针相差4步。则第二个指针到头时，第一个指针指向倒数第四个。注意要考虑链表长度。bool findLast4th2(Node*Head,int&ans)思路3：O(n)做一个数组arr4，让我们遍历单链表，把第1个、第5个、第9个第4 N+1个扔到arr0，把第2个、第6个、第10个第4 N+2个扔到arr1，把第3个、第7个、第11个第4 N+3个扔到arr2，把第4个、第8个、第12个第4 N个扔到arr3，这样随着单链表的遍历结束，arr中存储的就是单链表的最后4个元素，找到最后一个元素对应的arri，让k=(i+1)%4，则arrk就是倒数第4个元素。如果不易理解，画个图就好了。注意增加的空间只需要4个，所以是常数级的。比如加到第5个节点时就会把arr0中的值冲掉。bool findLast4th3(Node*Head,int&ans)3.找出单链表的中间元素思路1：O(2n)在函数的支持下，直接求整个链表的长度，然后定位中间元素。bool getMiddleOne1(Node*Head,int&ans)思路2：O(n)如果仍要求只遍历一遍。类似于上题，还是使用两个指针first和second，只是first每次走一步，second每次走两步：bool getMiddleOne2(Node*Head,int&ans)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(len1+len2)合并的办法如下，首先用Node*&方式传入两个链表的头指针Head1，Head2。用指针引用是因为最后要修改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.判断两个单链表是否相交注意这里是判断是否相交。对于判断问题来讲，相对还是比较简单的。注意单链表并非不能有重复元素。思路1：O(len1*len2)把第一个链表的指针值逐项存在hashtable中，遍历第2个链表的每一项的指针值，如果能在第一个链表中找到，则必然相交。但是C+的STL模板中的hash不太会用。所以我使用了set集合，不过貌似set集合是使用遍历的方式来查找元素是否在集合中的，所以效率是比较低的，至少在O(len1*len2)级别。bool judgeIntersectList1(Node*Head1,Node*Head2)思路2：O(len1+len2)把一个链表A接在另一个链表B的末尾，如果有环，则必然相交。如何判断有环呢?从A开始遍历，如果能回到A的表头，则肯定有环。注意，在返回结果之前，要把刚才连接上的两个链表断开，恢复原状。bool judgeIntersectList2(Node*Head1,Node*Head2)思路3：O(len1+len2)如果两个链表的末尾元素相同(指针相同，即为同一个元素，而非值相等)，则必相交。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的原因，我不太会使用C+STL中的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；cin newNode-value；newNode-next=NULL；return newNode；3，在头部增加节点/在表头增加节点/在头指针所指向的链表中增加一个节点,插入头部/这里必须要返回Node*来进行更新，因为传入的Head是Node*类型，而非Node*&Node*addNodeH(Node*Head,Node*InsertNode)if(Head=NULL)Head=InsertNode；elseInsertNode-next=Head；Head=InsertNode；return Head；4，在尾部增加节点/在表尾增加节点/在头指针所指向的链表中增加一个节点,插入尾部/这里必须要返回Node*来进行更新，因为传入的Head是Node*类型，而非Node*&Node*addNodeT(Node*Head,Node*InsertNode)if(Head=NULL)Head=InsertNode；elseNode*p=Head；while(p-next！=NULL)p=p-next；p-next=InsertNode；return Head；5，以升序方式增加节点/以升序增加节点/这里必须要返回Node*来进行更新，因为传入的Head是Node*类型，而非Node*&Node*addNodeSort(Node*Head,Node*InsertNode)if(Head=NULL)Head=InsertNode；elseNode*p=Head；/注意，这里把(p-value)(InsertNode-value)放在p-next！=NULL前面是有原因的，这是避免为了考虑在Head-4加入1的情况while(p-value)(InsertNode-value)&p-next！=NULL)p=p-next；if(p-value)=(InsertNode-value)/因为(p-value)=(InsertNode-value)而退出！表示在p前增加节点(狸猫换太子)/先在p后增加节点InsertNode-next=p-next；p-next=InsertNode；/再交换p和InsertNode的值swap(p-value,InsertNode-value)；else/因为(p-next=NULL)而退出！表示在尾增加节点p-next=InsertNode；return Head；6，构造链表/建立n个节点的链表choose=1,在表头加入，choose=2在表尾加入,choose=3按value值升序加入Node*createList(int n,int choose)Node*Head=NULL,*p=NULL；for(int i=0；i n；i+)p=applyNode()；if(choose=1)Head=addNodeH(Head,p)；else if(choose=2)Head=addNodeT(Head,p)；else if(choose=3)Head=addNodeSort(Head,p)；return Head；7，打印链表/遍历链表并输出void printList(Node*Head)Node*p=Head；while(p！=NULL)cout p-value-；p=p-next；coutNULLendl；8，释放链表/释放链表void freeList(Node*&Head)Node*tmp=Head；while(tmp！=NULL)Head=Head-next；free(tmp)；tmp=Head；Head=NULL；9，链表节点数/数节点个数int numOfNodes(Node*Head)int count=0；while(Head！=NULL)count+；Head=Head-next；return count；10，定位函数/定位第i个节点，i从1开始Node*locateNodeI(Node*Head,int i)/cout定位i位置endl；Node*pos=NULL；int count=numOfNodes(Head)；if(i=0|i count)cout定位越界！endl；elsepos=Head；for(int j=1；j i；j+)pos=pos-next；return pos；11，查找函数/查找值value并返回第一个出现该值的位置，如果需要引用其指针，可以再locate该位置int SearchList(Node*Head,int value)Node*p=Head；int pos=0；bool find=false；while(p！=NULL)pos+；if(p-value=value)find=true；break；p=p-next；if(find)return pos；else return-1；12，删除节点/删除某位置i的节点bool deleteNodeI(Node*&Head,int i)Node*p=locateNodeI(Head,i)；if(p=NULL)return false；elseif(p=Head)/说明p是头节点。Head=p-next；free(p)；elseNode*prep=locateNodeI(Head,i-1)；/定位前一个,必定存在prep-next=p-next；free(p)；return true；13，排序函数/链表排序/排序的方法是不破坏结构，有狸猫换太子的意思，只进行value的交换，不破坏链表结构void sortList(Node*&Head)int count=numOfNodes(Head)；if(count=0|count=1)return；/冒泡排序bool exchange；for(int i=2；i=count；i+)exchange=false；for(int j=count；j=i；j-)Node*p1=locateNodeI(Head,j)；Node*p2=locateNodeI(Head,j-1)；if(p1-value p2-value)exchange=true；swap(p1-value,p2-value)；if(！exchange)break；-高级函数代码：-1.单链表反转1/单链表反转(O(n2)void reverseList(Node*Head)int count=numOfNodes(Head)；/狸猫换太子，首尾交换for(int i=1；i=count/2；i+)Node*p1=locateNodeI(Head,i)；Node*p2=locateNodeI(Head,count+1-i)；swap(p1-value,p2-value)；1.单链表反转2/单链表反转(O(n)Node*reverseList2(Node*Head)if(Head=NULL|Head-next=NULL)/空链和单节点return Head；Node*p1=Head；Node*p2=Head-next；Node*p3=Head-next-next；if(p3=NULL)/只有两个节点p1-next=NULL；p2-next=p1；Head=p2；return Head；else/至少三个节点p1-next=NULL；while(p3！=NULL)p2-next=p1；p1=p2；p2=p3；p3=p3-next；p2-next=p1；Head=p2；return Head；2.找出单链表的倒数第4个元素1/查找倒数第四个元素,传入ans中O(2N)bool findLast4th1(Node*Head,int&ans)/先确定节点个数：int count=numOfNodes(Head)；/定位count-4 Node*p=locateNodeI(Head,count-3)；if(p！=NULL)ans=p-value；return true；elsereturn false；2.找出单链表的倒数第4个元素2/查找倒数第四个元素,传入ans中O(N),只遍历一遍bool findLast4th2(Node*Head,int&ans)Node*p1=Head；Node*p2=Head；/p1先走4步。for(int i=0；i 4；i+)if(p1！=NULL)p1=p1-next；elsereturn false；/肯定链表长度不够/同步移动while(p1！=NULL)p1=p1-next；p2=p2-next；ans=p2-value；return true；2.找出单链表的倒数第4个元素3/查找倒数第四个元素,传入ans中O(N)bool findLast4th3(Node*Head,int&ans)int arr4；Node*p=Head；int i=0；int count=0；while(p！=NULL)arri=p-value；p=p-next；i=(i+1)%4；count+；if(count 4)return false；elseans=arri；return true；3.找出单链表的中间元素1/获取中间元素O(2n)bool getMiddleOne1(Node*Head,int&ans)int count=numOfNodes(Head)；if(count=0)return false；elseNode*p=locateNodeI(Head,(count+1)/2)；ans=p-value；return true；3.找出单链表的中间元素2/获取中间元素O(n)/类似于上题，还是使用两个指针first和second，只是first每次走一步，second每次走两步：bool getMiddleOne2(Node*Head,int&ans)if(Head=NULL)/空链表return false；elseNode*first=Head；Node*second=Head-next；while(second！=NULL&second-next！=NULL)first=first-next；second=second-next；second=second-next；ans=first-value；return true；4.删除无头单链表的一个节点/删除无头单链表的非首尾节点狸猫换太子；void deleteNoHeadList(Node*Head,Node*Current)Node*p=Current-next；/一定是非首尾节点,否则会出错Current-value=Current-next-value；Current-next=Current-next-next；free(p)；4+.增加无头单链表的一个节点，一个指针current指向单链表中的一个节点，在该节点之前增加一个节点insertNode。/增加无头单链表的一个节点，current指针指向该链表某节点(可以为首尾)，在其之前增加节点insertNode。void addNoHeadList(Node*Head,Node*Current,Node*insertNode)insertNode-next=Current-next；Current-next=insertNode；swap(Current-value,insertNode-value)；5.两个不交叉的有序链表的合并/合并两个有序的链表Node*mergeTwoList(Node*&Head1,Node*&Head2)Node*Head=NULL；/合并后的链表Node*Tail=NULL；/合并后链表的尾指针/p1,p2遍历两个链表Node*p1=Head1；Node*p2=Head2；while(！(p1=NULL|p2=NULL)if(p1-value=p2-value)if(Head=NULL)/第一个节点Head=p1；Tail=Head；elseTail-next=p1；Tail=Tail-next；p1=p1-next；elseif(Head=NULL)/第一个节点Head=p2；Tail=Head；elseTail-next=p2；Tail=Tail-next；p2=p2-next；if(p1！=NULL)if(Head！=NULL)Tail-next=p1；elseHead=p1；else if(p2！=NULL)if(Head！=NULL)Tail-next=p2；elseHead=p2；Head1=NULL；Head2=NULL；return Head；8.判断单链表是否有环(6形状)?如何找到环的起始点?如何知道环的长度?1/计算单链表成环，环的长度,输入的参数为成环的交汇点。int getCircleLength(Node*cross)int len=1；Node*p=cross；while(p-next！=cross)/千万不能写作p-next！=plen+；p=p-next；return len；8.判断单链表是否有环(6形状)?如何找到环的起始点?如何知道环的长度?2/判断单链表是否有环,并且返回环的长度bool judgeCircleExists(Node*Head,int&len)if(Head=NULL)/空链return false；else if(Head-next=Head)/1个节点且成环return true；else if(Head-next=NULL)/1个节点不成环return false；/至少两个节点情形/初始化跑步机Node*p1=Head；/跑步者1号,跑到第1个节点Node*p2=Head-next；/跑步者2号，跑到第2个节点while(p2！=NULL&p2-next！=NULL)/利用了&短路p1=p1-next；p2=p2-next-next；if(p1=p2)/此时p1(p2)即为交汇点len=getCircleLength(p1)；return true；return false；9.判断两个单链表是否相交1/判断两个单链表是否相交(Y型)bool judgeIntersectList1(Node*Head1,Node*Head2)set Node*s；Node*p1=Head1；Node*p2=Head2；while(p1！=NULL)s.insert(p1)；p1=p1-next；while(p2！=NULL)if(s.find(p2)！=s.end()s.clear()；return true；p2=p2-next；s.clear()；return false；9.判断两个单链表是否相交2/判断两个单链表是否相交(Y型)bool judgeIntersectList2(Node*Head1,Node*Head2)if(Head1=NULL|Head2=NULL)return false；Node*p1=Head1；Node*p2=Head2；/先找到链表2的末尾,由p2指向while(p2-next！=NULL)p2=p2-next；/将链表1的表头与链表2的表尾连接p2-next=p1；/遍历链表1，如果回到了链表1表头，则相交while(p1！=NULL)if(p1-next=Head1)/记得恢复原状：p2-next=NULL；return true；p1=p1-next；/记得恢复原状：p2-next=NULL；return false；9.判断两个单链表是否相交3/判断两个单链表是否相交(Y型)bool judgeIntersectList3(Node*Head1,Node*Head2)if(Head1=NULL|Head2=NULL)return false；Node*p1=Head1；Node*p2=Head2；/p1与p2记录两链表的尾指针while(p