复杂链表与单链表
首先呢,得告诉大家【复杂链表】和【普通链表】的一些区别
可是这个不怎么好描述
不过呢,我请来了【四个小学生】,来帮助大家理解
小时候的小A、小B、小C和小D
我们有四个同学 A、B、C、D
他们【高高兴兴】的排起了队
他们依次站着,无所他想,每个人只记住后面那个人,那么队伍就不会分散
小A、小B、小C和小D的成长
原本安安分分的A、B、C和D都长大了
他们之间有的迸发出了【爱情的火花】
彼此之间会不会【闹出矛盾】???
【友谊的小船】会不会说翻就翻??
在小A、小B、小C和小D的成长过程中
他们发现了【爱情】这个东西
小A:喜欢上了小C
小C:却喜欢小B
小B:表示【无可奈何】,我不想趟这趟浑水(怕小A报复)
小D:作为一只【单身狗】,我表示爱自己就好
现在,问题来了,请读者解答
1、上面四个好朋友中出现了【几角恋】?
2、B为什么拒绝了C
好了,是不是很混乱呢,甚至有点晕乎
那么这就对了,这就是【复杂链表】
复杂链表的定义
在链表的结构体中,除了有一个指向【下个节点】(后面那个人)的【指针】
还有一个指向【链表自身】中【任意节点(或者NULL)】的【指针】
那么这个链表就叫【复杂链表】
复杂链表的处理
复杂链表的构造(完整版代码在最后)
结构体:
typedef struct DNode { int data; struct DNode* next; struct DNode* random; }DNode,*PDNode;
申请一个节点:
PDNode BuyNewNode(int data) { PDNode NewNode = (PDNode)malloc(sizeof(DNode)); if (NewNode == NULL) { return NULL; } NewNode->data = data; NewNode->next = NULL; NewNode->random = NULL; return NewNode; }
构建一个如题所示的复杂链表:
PDNode MakeDiffList() { PDNode pHead = NULL; PDNode CurNode = NULL; PDNode NewNode = BuyNewNode(1); PDNode Node1,Node2,Node3,Node4 = NULL;//把四个节点都保存起来,好表示他们【长大后】的“暗恋”关系 pHead = NewNode; CurNode = pHead; Node1 = CurNode; NewNode = BuyNewNode(2);//NULL CurNode->next = NewNode; CurNode = CurNode->next; Node2 = CurNode; NewNode = BuyNewNode(3);//2 CurNode->next = NewNode; CurNode = CurNode->next; Node3 = CurNode; NewNode = BuyNewNode(4);//自己 CurNode->next = NewNode; CurNode = CurNode->next; Node4 = CurNode; Node1->random = Node3;//小A 暗恋 小C Node2->random = NULL;//小B 谁都不恋 Node3->random = Node2;//小C 暗恋 小B Node4->random = Node4;//小D 爱 自己 return pHead; }
这样我们的复杂链表就够造好啦~~~
复杂链表的复制
(1)首先,是原来的链表
(2)然后我们还是首先复制每一个结点N为N*,并且让N*在对应的N后面,即为
注意:复制的过程中,love指针不能直接复制
比如 【A‘】指向的是 【C】 而不是 【C'】
我们应当指向 【A->love->next】 通过C的下一个来找到 【C'】
(3)最后,将产生的新的复杂链表删除~大工搞成
复制复杂链表的代码:
PDNode CopyDiffList(PDNode*pHead) { PDNode CurNode = *pHead; PDNode NewHead = NULL; PDNode NewNode = NULL; if (pHead == NULL) { return NULL; } /**************首次复制并连接*********************/ while (CurNode!=NULL) { //NewNode = BuyNewNode(CurNode->data*11);//测试中用11 倍的数据,方便调试 NewNode = BuyNewNode(CurNode->data); NewNode->next = CurNode->next; NewNode->random = CurNode->random; CurNode->next = NewNode; CurNode = NewNode->next; } /*************************************************/ /**************进行random的移动*******************/ CurNode = *pHead; while (CurNode!= NULL) { if (CurNode->random != NULL) CurNode->next->random = CurNode->random->next; CurNode = CurNode->next->next; } /*************************************************/ /****************删除原来的元素*******************/ CurNode = *pHead; NewHead = (*pHead)->next; NewNode = (*pHead)->next; while (CurNode->next->next!= NULL) { CurNode->next = NewNode->next; NewNode->next = NewNode->next->next; CurNode = CurNode->next; NewNode = NewNode->next; } NewNode->next = NULL; CurNode->next = NULL; /*************************************************/ return NewHead; }
完整版代码:
//结构体 typedef struct DNode { int data; struct DNode* next; struct DNode* random; }DNode,*PDNode; //生成一个新节点并返回 PDNode BuyNewNode(int data) { PDNode NewNode = (PDNode)malloc(sizeof(DNode)); if (NewNode == NULL) { return NULL; } NewNode->data = data; NewNode->next = NULL; NewNode->random = NULL; return NewNode; } //构造复杂链表 PDNode MakeDiffList() { PDNode pHead = NULL; PDNode CurNode = NULL; PDNode NewNode = BuyNewNode(1); PDNode Node1,Node4 = NULL; pHead = NewNode; CurNode = pHead; Node1 = CurNode; NewNode = BuyNewNode(2);//NULL CurNode->next = NewNode; CurNode = CurNode->next; Node2 = CurNode; NewNode = BuyNewNode(3);//2 CurNode->next = NewNode; CurNode = CurNode->next; Node3 = CurNode; NewNode = BuyNewNode(4);//自己 CurNode->next = NewNode; //CurNode->random = CurNode; CurNode = CurNode->next; Node4 = CurNode; Node1->random = Node3; Node2->random = NULL; Node3->random = Node2; Node4->random = Node4; return pHead; } //复制复杂链表 PDNode CopyDiffList(PDNode*pHead) { PDNode CurNode = *pHead; PDNode NewHead = NULL; PDNode NewNode = NULL; if (pHead == NULL) { return NULL; } /*****************首次复制并连接******************/ while (CurNode!=NULL) { //NewNode = BuyNewNode(CurNode->data*11);//测试中用11 倍的数据,方便调试 NewNode = BuyNewNode(CurNode->data); NewNode->next = CurNode->next; NewNode->random = CurNode->random; CurNode->next = NewNode; CurNode = NewNode->next; } /*************************************************/ /**************进行random的移动*******************/ CurNode = *pHead; while (CurNode!= NULL) { if (CurNode->random != NULL) CurNode->next->random = CurNode->random->next; CurNode = CurNode->next->next; } /*************************************************/ /****************删除原来的元素*******************/ CurNode = *pHead; NewHead = (*pHead)->next; NewNode = (*pHead)->next; while (CurNode->next->next!= NULL) { CurNode->next = NewNode->next; NewNode->next = NewNode->next->next; CurNode = CurNode->next; NewNode = NewNode->next; } NewNode->next = NULL; CurNode->next = NULL; /*************************************************/ return NewHead; } //进行测试 void FunTest() { PDNode pHead = NULL; PDNode pNewHead = NULL; pHead = MakeDiffList(); pNewHead = CopyDiffList(&pHead); return; } //主函数 int main() { FunTest(); return 0; }
皓皓有话说:
问:如何在众多课程的压力下继续看书呢?
Linux、C++primer
还有杨老师给我提示的如何预习Java(异常、继承、正则表达式等....)
挤一挤时间总会有的,下课时间十分钟的【休闲时光】也要搭进去喽~