重庆网站备案系统,网站建设济南云畅网络技术有限公司,wordpress添加附近商家,dedecms做的系统网站主页是哪一个文件双链表 双链表的特点声明双链表的结构体成员双链表的初始化带头结点的双链表初始化不带头结点的双链表初始化调用双链表的初始化 双链表的判空带头结点的双链表判空不带头结点的双链表判空 双链表的插入#xff08;按值插入#xff09;头插法建立双链表带头结点的头插法每次调… 双链表 双链表的特点声明双链表的结构体成员双链表的初始化带头结点的双链表初始化不带头结点的双链表初始化调用双链表的初始化 双链表的判空带头结点的双链表判空不带头结点的双链表判空 双链表的插入按值插入头插法建立双链表带头结点的头插法每次调用头插法只能插入一个结点每次调用头插法可插入任意个结点调用头插法建立带头结点的双链表的完整代码可以直接赋值运行的 不带头结点的头插法每次调用只能插入一个结点每次调用可以插入任意个结点调用头插法建立不带头结点的双链表的完整代码可以直接赋值运行的 尾插法建立双链表带头结点的尾插法每次调用只能插入一个结点我自己能理解的实现尾插法的思路我的思路的完整代码可以运行的 教材用的实现尾插法的代码我看不懂 不带头结点的尾插法我自己的思路 打印双链表二级目录三级目录 双链表的特点
1. 双链表在创建的过程中每个结点都需要一个数据域和两个指针域所以它的存储密度比之单链表更低一些。
2. 可进可退解决了单链表无法逆向搜索的问题。声明双链表的结构体成员
typedef struct DNode {ElemType data;struct DNode *prior, *next;
}DNode, *DLinklist;// DNode *就等价于DLinklist 之前文章有解释过DNode *就等价于DLinklist
双链表的初始化
双链表的每个结点都有两个指针域一个指向前驱结点一个指向后继结点。头结点的prior永远指向NULL带头结点的双链表初始化
有几个需要注意的地方1. DLinklistL是头指针而不是头结点这是两东西。2. 头结点不存储数据只起到一个标记作用方便对链表进行操作。3. 头指针指向头结点用于记录链表的起始位置。4. 给L分配内存空间是因为这是带头结点的双链表而头指针指向头结点所以实际上是给头结点分配内存空间创建头结点。5. 不带头结点的双链表不用创建头结点自然也不用分配内存空间直接创建第一个结点即可。6. 注意原先我一直疑惑的地方是为啥带头结点就要分配内存空间不带头结点的双链表哪怕不需要头结点也要给第一个结点分配内存空间但是初始化代码的时候并没有写后来我发现不是没写而是不应该在初始化链表的时候给链表的第一个实际结点分配内存空间此时是为了初始化一个空链表后续给链表插入结点的时候才会开始分配内存空间。而此时分配的仅仅只是头结点的内存空间并不是第一个实际结点的带就分配不带就不分配就这么个意思。bool initDList(DLinklistL) {L(DNode *)malloc(sizeof(DNode));/*** L本身是头指针带头结点时它指向头结点的指针域所以可以把L看作是头结点指针域为NULL说明这是个空指针。* 注意空指针本身不占用内存空间。* 指针变量在内存中占用一定的空间但当指针被赋值为NULL时它指向的内存地址为空不指向任何有效的内存空间。* 因此空指针并不占用额外的内存空间*/if(LNULL) { // 空指针不占用内存空间可用此来判断内存不足给头结点分配存储空间失败return false;}// 头结点的prior永远指向NULL// 头指针L指向头结点存储头结点的地址L-prior指向头结点的前指针域存储前指针域的地址为NULL。L-priorNULL; // 头结点之后还没有结点初始化链表这句必须写因为要创建个空表以防被内存中残留数据污染 L-nextNULL; // 头指针L指向头结点存储头结点的地址L-next指向头结点的后指针域存储后指针域的地址为NULL。 return true;
}不带头结点的双链表初始化
void initDList(DLinklistL) {// 由于不带头结点所以头指针L直接指向双链表的第一个实际结点此时链表为空所以指向NULL可看作是个空指针空指针的前、后指针不指向任何有效的内存空间自然不用再区分next、priorLNULL;
}调用双链表的初始化
int main() {DLinklistL;// 初始化双链表initDList(L);
}双链表的判空
带头结点的双链表判空
1. 带头结点的双链表由于头结点的前指针永远指向NULL所以不用管。
2. 主要是头结点的后指针看它后面有没有结点没结点时它应该指向NULL。bool Empty(DLinklist L) {if(L-nextNULL) {return true;}else {return false;}// 这个if判断可以简写成return L-nextNULL;
}不带头结点的双链表判空
bool Empty(DLinklist L) {return LNULL;
}双链表的插入按值插入
1. 这是按值插入不是按位插入只要在找到链表中某个已存在的结点在其后面分配存储空间创建一个新结点改变前、后指针指向以及
新结点的数据域就可以实现插入了这算是后插。
2. 此处只是说明了插入的逻辑代码并不完整也还没有分带不带头结点1. DNode *p表示声明一个指针变量p它指向下一结点的指针域。
2. pNULL表示p指针所在的结点的指针域为NULL它不指向任何有效的地址说明p是个空指针。- 为什么要判断指针p和指针s是否是空指针1. 因为该函数是在找到p结点之后通过改变p结点原先的指向来实现插入的。2. 如果p是个空指针它的后指针域没有任何指向那我在它后面插入一个新结点新结点的后指针域就没有赋值指向了。3. 并且一般链表的最后一个结点的后面是NULL肯定不能在NULL后面再插入新结点要插也最后是在最后一个实际结点后面插4. 参数s表示指针s它所指向的结点是我要插入的新结点一个新结点都要插入一个新结点了肯定不能是个空指针啊如果是个空指针那这个链接岂不是断链了。
3. p-nextNULLp-next表示指针p所在的结点的指针域它存储下一结点的地址指向下一结点的指针域。p-nextNULL就表示指针p指向
的结点的下一结点是NULL。
4. 把指针变量p指向的结点看作是p结点那它的下一结点就是紧跟其后的一个结点即p结点—NULL。
5. 首先明确p是用DNode *去声明的所以p一定是个指针那一个指针它会指向一个结点就可以把p看作是p结点pNULL就是说p结点本
身是NULL。
6. 其次p-next就可以看作是p结点的下一结点是NULLbool InsertNextNode(DNode *p, DNode *s) {if(pNULL || sNULL) {return false;}/*** s指针所指向的结点(简称s结点)的指针域指向p指针所指向的结点(简称p结点)的指针域指向的结点即s结点指向p结点的下一个结点* 此时顺序是p—p下一结点s—p下一结点*/s-nextp-next; /*** 由于是双链表每个结点都有前指针和后指针p结点如果是最后一个结点说明它后面没有结点了指向NULL。* 它的后指针指向NULL这没问题这样子的双链表才是完整的。* 但是NULL没有前、后指针啊所以在操作结点的前指针指向的时候要加个判断当前结点下一结点不是NULL才能操作其前指针*/if(p-next!NULL) {/*** p-next表示p结点的下一结点(简称q结点)* p-next-prior表示q结点的前指针域指向的结点* 赋值s就表示q结点的指针域指向指针s所指向的结点即s结点。* 此时顺序为p—qs—q*/p-next-priors; }// 现在只要把p和s再连上就好了p-nexts;s-priorp;return true;
}头插法建立双链表
需求把一个数组中的数据插入到初始的双链表中如果当前双链表带头结点那么每次都是插在头结点的后面这样每次插入的新结点都是
链表的第一个结点。
如果当前双链表不带头结点那么每次插入都应该让头指针L直接指向当前新插入的这个结点。
这便是头插法。
带头
1. 带头结点的初始双链表头指针L—头结点—NULL
2. 插入1个需要的参数要建立的链表L要插入的元素e
3. 插入n个需要的参数要建立的链表L要插入的多个元素e[]要插入的结点个数n
不带头头指针L—NULL
4. 带头结点的初始双链表头指针L—NULL
5. 需要的参数要建立的链表L要插入的元素e带头结点的头插法
每次调用头插法只能插入一个结点
DLinklist head_insert(DLinklist L, int e) {// 创建新结点分配内存空间DLinklist *s (DLinklist *)malloc(sizeof(DLinklist));/*** 头指针L指向头结点L-next指向头结点的指针域头结点的指针域指向头结点的下一结点* 即L可看作是头结点L-next就是头结点的下一结点。* 1、头结点指向创建的新结点s即在头结点之后插入新结点* 2、此时头结点原指向的结点就要变成s结点的下一结点* 3、此时后指针的指向已全部完成双链表还要再操作一下前指针的指向* - s结点的前指针指向头结点头结点原下一结点的前指针指向s结点* 4、但是要注意一个问题如果是第一次插入双链表此时是空的头结点指向NULL插入的新结点s是链表中最后一个结点* 只要操作其后指针即可而其下一结点的无前指针无需操作所以为了代码的健壮性要加个判断*/s-datae;s-nextL-next;if(L-next!NULL) {L-next-priors;}L-nexts;s-priorL;
}每次调用头插法可插入任意个结点
1. 首先要给分配内存空间有多少个n就分配多少个。
2. 由于插入的n个每个的前指针和后指针还要链接起来所以最好当作1个来操作然后通过循环的方式变成n个。
3. i是数组的下标从0开始表示数组中第一个元素假设n3那就是插入3个结点必须从i0开始循环那就要in或者in-1才能正好取3个。DLinklist head_insert_mult(DLinklist L, int e[], int n) {for(int i0;in;i) { DNode *s(DNode *)malloc(sizeof(DNode));s-nextL-next;s-datae[i];if(L-next!NULL) {L-next-priors;}s-priorL;L-nexts;}return L
}调用头插法建立带头结点的双链表的完整代码可以直接赋值运行的 #includestdio.h
#includestdlib.h// 声明结构体成员
typedef struct DNode {ElemType data;struct DNode *prior, *next;
}DNode, *DLinklist;// 初始化一个带头结点的双链表
DLinklist InitList(DLinklist L) {L(DNode *)malloc(sizeof(DNode));if(LNULL) {return NULL;}L-nextNULL; L-priorNULL;return L;
}// 头插法建立双链表(单个)
DLinklist head_insert(DLinklist L,int e) {DNode *s(DNode *)malloc(sizeof(DNode));s-datae;s-nextL-next;if(L-next!NULL)L-next-priors;L-nexts;s-priorL;return L;
}// 头插法建立双链表多个
DLinklist head_insert_mult(DLinklist L, int e[], int n) {for(int i0;in-1;i) {DNode *s(DNode *)malloc(sizeof(DNode));s-nextL-next;s-datae[i];if(L-next!NULL) {L-next-priors;}s-priorL;L-nexts;}return L;
}// 打印双链表
void printDLinkList(DLinklist L)
{DNode* p L;while(p){printf(%d , p-data);p p-next;}
}int main() {DLinklist L;InitList(L);head_insert(L,2); head_insert(L,3);int arr[5]{1,2,3,4,5};head_insert_mult(L,arr,3); // 顺序为 头结点 3 2 1 3 2 printDLinkList(L); return 0;
}不带头结点的头插法
由于没有头结点了所以操作头指针L直接指向双链表第一个实际结点每次调用只能插入一个结点
DLinklist head_insert_NoT(DLinklist L, int e) {DNode *s(DNode *)malloc(sizeof(DNode));s-nextL;s-datae;if(L!NULL) {L-priors;}Ls; s-priorL;return L;
}每次调用可以插入任意个结点
DLinklist head_insert_NoT_mult(DLinklist TL, int e[], int n) {for(int i0;in;i) {DNode *s(DNode *)malloc(sizeof(DNode));s-datae[i]; // 此时双链表只有一个NULL由TL指向s-nextTL; // s指针所在的结点(简称s结点)的指针域为头指针TL的指向也就是说s结点下一个是NULLs—NULLif(TL!NULL) { TL-priors; // 由于是头茬所以每次TL原先指向的那个结点的前指针都要指向新插入的s}TLs; // TL是头指针每次都要指向新插入的s指针所指向的结点s-priorNULL; // 由于s指针是以头插的形式新插入的它就是第一个结点前面没有任何东西前指针指向NULL}return TL;}调用头插法建立不带头结点的双链表的完整代码可以直接赋值运行的 #includestdio.h
#includestdlib.h// 声明结构体成员
typedef struct DNode {ElemType data;struct DNode *prior, *next;
}DNode, *DLinklist;// 初始化一个带头结点的双链表
DLinklist InitList(DLinklist L) {LNULL;return L;
}DLinklist head_insert_NoT(DLinklist L, int e) {DNode *s(DNode *)malloc(sizeof(DNode));s-nextL;s-datae;if(L!NULL) {L-priors;}Ls; s-priorL;return L;
}DLinklist head_insert_NoT_mult(DLinklist TL, int e[], int n) {for(int i0;in;i) {DNode *s(DNode *)malloc(sizeof(DNode));s-datae[i]; s-nextTL; if(TL!NULL) { TL-priors; }TLs; s-priorNULL; }return TL;}// 打印双链表
void printDLinkList(DLinklist L)
{DNode* p L;while(p){printf(%d , p-data);p p-next;}
}int main() {DLinklist L;InitList_NoT(L);head_insert_NoT(L,2); head_insert_NoT(L,21); head_insert_NoT(L,22);int arr1[5]{2,3,4,7,8};head_insert_NoT_mult(L,arr1,5);printDLinkList(L); return 0;
}尾插法建立双链表
尾插就是每次都在双链表的末尾再插入一个结点新结点后面不会再有其他结点应该是指向NULL的。带头
1. 插入一个需要的参数双链表L、要插入的元素e
不带头
2、带头结点的尾插法
每次调用只能插入一个结点
我自己能理解的实现尾插法的思路
带头结点那就是头结点—新结点—NULL
尾插法思路
1. 要在双链表的最后一个结点后面插入那肯定要找到最后一个结点。而最后一个结点后面没结点指向NULL所以可以根据这个来判断。DNode *tail; // 这是我声明的指向尾结点指针变量tailif(tail-nextNULL) // 说明tail指针目前已经是指向尾结点
2. 双链表是个链表它不具有随机存取的特点所以要找到尾结点只能从第一个结点开始按序遍历tailL; // tail指针要指向头指针L指向的结点即头结点由此开始遍历while(tail-next!NULL)tailtail-next; // 如果tail指针当前指向的结点的下个结点不是NULL那就指向下一个循环遍历 // 此处应该是跳出循环的操作了而跳出循环就说明tail指针已经指向尾结点了
3. 要插入新结点肯定要创建并分配存储空间先让新结点指向尾结点的下一结点再让尾结点指向新结点然后让新结点的前指针指向尾结点s-nexttail-next;tail-nexts;s-priortail;DLinklist tail_insert(DLinklist L, int e) {DNode *tailL; // 声明一个指针变量tail表示尾指针赋值L表示初始值指向头结点while(tail-next!NULL) {tailtail-next;}DNode *s(DNode *)malloc(sizeof(DNode));s-nexttail-next;s-datae;tail-nexts;s-priortail;// 因为是尾插法所以最后s一定指向NULLtail-next-prior是不存在的不用考虑
}我的思路的完整代码可以运行的 #includestdio.h
#includestdlib.htypedef struct DNode {int data;struct DNode *prior;struct DNode *next;
}DNode,*DLinklist;DLinklist InitList(DLinklist L) {L(DNode *)malloc(sizeof(DNode));if(LNULL) {return NULL;}L-nextNULL; L-priorNULL;return L;
} DLinklist tail_insert(DLinklist L, int e) {DNode *tailL; while(tail-next!NULL) {tailtail-next;}DNode *s(DNode *)malloc(sizeof(DNode));s-nexttail-next;s-datae;tail-nexts;s-priortail;
}// 打印双链表
void printDLinkList(DLinklist L)
{DNode* p L;while(p){printf(%d , p-data);p p-next;}
}int main() {DLinklist L;InitList(L);tail_insert(L,2); tail_insert(L,21); tail_insert(L,22);printDLinkList(L); return 0;
}DLinklist tail_insert(DLinklist L, int e) {DNode *s(DNode *)malloc(sizeof(DNode));s-nextL-next;
}教材用的实现尾插法的代码我看不懂
不带头结点的尾插法
我自己的思路
由于此处是双链表不带头结点那么此时头指针L指向双链表的第一个实际结点所以当双链表为空时LNULL但如果双链表不为空L自然也不会是NULL就要通过遍历去获取双链表的尾结点所以要做个if判断DLinklist tail_insert_NoT(DLinkList L,int e) {DNode *s(DNode *)malloc(sizeof(DNode));s-datae;// 这两句没有就无法运行s-next NULL;s-prior NULL;/*** 初始化的时候LNULL头结点是NULL所以tail指针指向NULL* 但是只要插入过结点再调用该函数进行尾插头指针L就不再是指向NULL而是指向一个实际结点* 此时就要通过遍历去获取该链表的尾结点过程同上*/DNode *tail; if(LNULL) { // 不带头的双链表为空时L指向的就是第一个实际结点插入的新结点s就应该是由L指向的Ls第一个结点的前指针用于指向NULLLs;s-priorNULL;}else {while(tail-next!NULL) {tailtail-next;}s-nexttail-next;tail-nexts;s-priortail;}return L;
}打印双链表
插入结点之后想看看当前双链表的结点顺序可以用以下代码打印输出void PrintDLinkList(DLinklist L) { /*** 声明一个指针变量p让它指向头指针L指向的结点* 如果是带头结点的双链表就指向头结点* 如果是不带的就指向双链表的第一个实际结点。* 此处我写L是为了区分终端打印效果如果不想要头结点写成DNode *pL-next*/DNode *pL;while(p!NULL) {printf(%d, p-data);pp-next;}
}二级目录
三级目录
