宁波免费建站,wordpress媒体打不开,微网站如何做,百度网站大全旧版知识回顾 在前面的学习中#xff0c;我们已经了解到了链表#xff08;线性表的链式存储#xff09;的一些基本特点#xff0c;并且深入的研究探讨了单链表的一些特性#xff0c;我们知道#xff0c;单链表在实现插入删除上#xff0c;是要比顺序表方便的#xff0c;但是…知识回顾 在前面的学习中我们已经了解到了链表线性表的链式存储的一些基本特点并且深入的研究探讨了单链表的一些特性我们知道单链表在实现插入删除上是要比顺序表方便的但是单链表中每个结点仅存在一个指针指向其后续结点那么如果我们想要找到其前面的节点则需要从头部开始遍历这是十分不方便的那么是不是对其添加一些元素或特性使其的操作更加简单呢那么我们就来看下这节将要学习的一些链表。
双链表 我们知道单链表中每个结点只有一个指向其后续的指针这边可以使得单链表可以从前往后的遍历整个链表但如果我们想要去访问某个结点的前驱节点时则需要从头开始遍历这样就会消耗较多的时间那么为了解决这一问题我们引入双链表。 我们不难观察到双链表则是在单链表的基础上在结点中又添加了一个指针用于指向该结点的前驱结点那么这样的话我们也就可以通过一个结点很好的去查询其前驱和后继结点了虽然我们增加了存储密度但在对链表的操作上就更加的灵活。
结点初始化
typedef struct DNode{int data ;struct DNode *prior, *next ;
}DNode, *DLinkList;
双链表的插入 实际上双链表的插入是类似于单链表的插入的只不过由于双链表存在指向后续结点以及前驱结点的指针所以在进行插入操作时我们需要对这两个指针分别进行类似的操作即可。 如图所示我们若要在双链表中插入x那么我们首先需要让x结点的后续指针指向插入位置后结点之后再将插入位置后结点c的前驱指针指向x之后再让x结点的前驱指针指向插入位置的前驱结点a之后再将插入位置的前驱结点a的后继指针指向x这样我们就成功的将x插入到链表之中了。 需要思考的是当我们的插入位置为链表的末尾时我们应该怎么去操作呢这当然也不难操作通过对双链表的观察我们知道在其末尾结点的后续结点会指向NULL;那么这时就不会存在一个后面的结点指向末尾结点了也就是说在之前我们的结点是存在两个指向结点的箭头和两个指出的箭头但到了末尾就缺少一个指向的箭头。 知道了这层差异那么我们就要对其进行相应的处理首先我们需要判断我们插入位置前的结点是否指向NULL当其指向NULL时则证明我们插入的为末尾结点这里我们对前续的操作不变只不过在对其后续操作时我们只需要让其指向NULL也就前末结点指向的位置即可不需要进行指向插入结点的操作。 当然插入首位的方法也同上所示只不过从特殊处理后续操作转变为特殊处理前驱操作即可。
//插入
bool InsertNextDNode(DNode *p, DNode *s) {if(p NULL || s NULL) return false;s-next p-next;if(p-next ! NULL) {p-next-prior s;}p-next s;s-prior p;return true;
}
双链表的删除 对于删除操作其原理也与单链表的操作类似只不过其具有两个指针所以我们需要更改两个指针的指向即可。 对于双俩表的删除操作例如我们需要删除b结点那么我们只需要让a的后续指针指向cb后续指针指向位置让c的前驱指针指向ab前驱指针指向位置这样我们就可以删除b结点了。 例如删除p指针后的结点b。
p-nextq-next;
q-next-priorp;
free(q);当然删除前驱结点的方法也与之类似我们更改其相应的指针指向即可。 那我们如果删除的结点位于双链表的头部或者尾部呢这样对于我们的操作是否存在什么影响下面我们来看一下在这里我们以末结点为例实际上头结点删除方法与其类似 当我们遇到尾结点时由于我们末尾元素后指向NULL所以其不存在一个指向前的指针也就是说如果我们想要删除末尾元素的话我们就只需要让其前面的元素结点向后指向NULL即可之后再释放我们想要删除的末尾结点就可以解决这种问题了。
//删除(p后的节点
bool DeleteNextDNode(DNode *p) {if(p NULL) return false;DNode *q p-next;if(q NULL) return false;p-next q-next;if(q-next ! NULL) q-next-prior p;free(q);return true;
}双链表的遍历 至于遍历双链表这里由于我们前面的学习这部分的内容就十分的简单了。我们就像单链表遍历一样通过头指针或头结点开始从头部或者我们所指定的某一点以此遍历其next指针直到其指向NULL为止那么这样我们是不是就可以成功的从头部遍历一遍链表了呢 乍一听这与单链表是没什么不同的但由于我们双链表是一个结点存在两个指针的也就是指向前的prior以及指向后续的next指针所以我们在进行遍历的时候也就可以去尝试更多的遍历方法了我们可以尝试从后向前遍历。 这与前面的从前向后遍历并没有什么不同只是我们需要从尾部向头部遍历的时候需要不停的访问改结点的prior指针直到其指向NULL为止。
//遍历
//从前向后遍历
void PriorFindList(DLinkList L) {DNode *p L-next;while(p ! NULL) {cout p-data ;p p-next;}cout endl;
}
//从后向前遍历
void AfterFindList(DLinkList L) {DNode *p L;while(p-next ! NULL) {p p-next;}while(p!L) {cout p-data ;p p-prior;}cout endl;
}
循环链表 循环链表又可以分为循环单链表和循环双链表。其原理是十分相同的。
循环单链表 通过图我们不难看出上面的链表是我们已经讨论过多次的单链表其尾结点指针指向NULL那么我们怎么使其变成循环链表呢 循环、循环顾名思义就是当我们访问某一序列最后一个元素时紧接着我们就可以以相同的操作去访问该序列第一个元素在这里对于链表也是相同的也就是当我们访问的某链表的尾结点时我们依旧可以通过常规的访问该结点的next指针的方法去访问到该链表的头结点。 那么这样我们的思路就十分清晰了我们就只需要在创立链表时使其的末结点的next指针指向该链表的头结点这样我们就可以很轻松的实现循环单链表了。 那么我们为什么要学习单链表呢 如果我们只是使用单链表当我们有某一结点的位置时我们可以通过单链表的特性去合理的访问到其后面的各个结点但其前面的结点对于我们来说就是未知的了。 为了解决这个问题我们就可以引入循环单链表这样我们在得到某一结点位置后我们依次访问最终就可以成功的访问到该链表头结点那么我们指定结点前的区域就不再是未知的了。 在引入循环链表时我们就可以设立一个尾指针甚至说尾指针在这里要比头指针更加的方便我们不难知道对于头指针来说访问链表头部需要O(1)的时间复杂度、访问尾部时需要O(n)的时间复杂度。但对于循环单链表的话我们就可以使用O(1)的时间复杂度访问其头结点和尾结点对于尾结点没什么好说的因为其就指向尾结点我们直接访问即可但对于头结点我们在访问时仅仅需要访问尾结点的next指针由于其是循环的所以我们就可以仅用O(1)的时间复杂度就访问到了头结点这无疑来说节省了很多时间。那么同理我们在遇到某些操作中包含需要查找尾结点的操作时这样都可以节省其时间。
循环双链表 如上图中上方的链表一样该链表是刚才我们已经了解过的双链表那么其循环双链表的建立实际上是类似于循环单链表的只不过需要注意的是由于我们的双链表的每个结点是有两个指针的所以我们在使其尾部指向头部时也要去更改头部的prior指针使其指向链表的尾这样我们就可以实现循环双链表了。 这里由于循环链表于前面的单双链表相似所以这里就不给出其完整代码实现了实际上我们只需对一些地方的代码进行特定的修改就可以得到该循环链表的代码了。
静态链表 通过前面的学习我们知道单链表各个结点的存储在我们计算机的内存中是完全随机杂乱的我们需要通过指针去link连接这些结点那么我们可不可以在内存中申请一块连续的存储空间去进行存储这个链表呢 当然这乍一听与数组十分的相似只不过我们需要通过这一连续的存储空间去实现链表的功能也就是需要通过next指针去指向后续节点。 那么这里我们就可以参考数组我们将结点划分为存数据的data和存下一位置的数组下标next这样我们在存入一个元素时首先判断该数组位置是否已存入数据若没有存入数据的话我们将其存入并将上一尾结点的next更新为该结点的数组下标。 这里我们通过next去串联数组的下标进而实现链表功能。 例如上图所示我们可以将结点的data默认初始化为 -2 (也就是说当我们在某结点进行存入数据时可以判断下其next是否为-2若不是-2则说明该结点已经存在元素)那么我们观察图中链表可以看出这里我们:头-数组[2]-数组[1]-数组[6]-数组[3]--1;-1则表明到达了尾部。 优点增、删 操作不需要大量移动元素 缺点不能随机存取只能从头结点开始依次往后查 找容量固定不可变 适用场景①不支持指针的低级语言②数据元素数 量固定不变的场景如操作系统的文件分配表FAT 代码
双链表代码 // 2.4 双链表#include bits/stdc.husing namespace std ;typedef struct DNode{int data ;struct DNode *prior, *next ;
}DNode, *DLinkList;//初始化
bool InitDLinkList(DLinkList L) {L (DNode *)malloc(sizeof(DNode)) ;if(L NULL) return false ; //分配失败 L-next NULL;L-prior NULL;return true;
}//尾插法建立
DLinkList DList_TailInsert(DLinkList L) {int x;cin x;DNode *s, *r L;while(x!9999) {s (DNode *)malloc(sizeof(DNode)) ;s-data x;r-next s;s-prior r;r s;cin x;}r-next NULL;return L;
} //插入
bool InsertNextDNode(DNode *p, DNode *s) {if(p NULL || s NULL) return false;s-next p-next;if(p-next ! NULL) {p-next-prior s;}p-next s;s-prior p;return true;
}//删除(p后的节点
bool DeleteNextDNode(DNode *p) {if(p NULL) return false;DNode *q p-next;if(q NULL) return false;p-next q-next;if(q-next ! NULL) q-next-prior p;free(q);return true;
}//销毁
void DestoryList(DLinkList L) {while(L-next ! NULL){DeleteNextDNode(L);}free(L);LNULL;
} //遍历
//从前向后遍历
void PriorFindList(DLinkList L) {DNode *p L-next;while(p ! NULL) {cout p-data ;p p-next;}cout endl;
}
//从后向前遍历
void AfterFindList(DLinkList L) {DNode *p L;while(p-next ! NULL) {p p-next;}while(p!L) {cout p-data ;p p-prior;}cout endl;
}int main() {DLinkList L;InitDLinkList(L);DList_TailInsert(L);PriorFindList(L);AfterFindList(L);DNode *p, *s;p L;s L;for(int i0; i3; i) p p-next; //删去第五个值 DeleteNextDNode(p);PriorFindList(L);AfterFindList(L);return 0;
} 尾 由于博主才疏学浅总结的相关知识仅限于自我学习认知若出现错误。望各位大神指点。在这里感谢各位。 由于学习的仓促有些代码未能完全实现以及部分磨块的讲解不充分若后期实现该代码将会进行下一步的补充
