链表 实例

mfc编程cstringlist实例MFC编程中的CStringList实例在MFC（Microsoft Foundation Classes）编程中，CStringList是一个非常有用的类，用于管理字符串的链表。

它提供了许多方便的功能，使得操作字符串链表变得更加简单和高效。

在本文中，我们将逐步回答关于CStringList的问题，并给出一些实例代码来帮助读者更好地理解和使用这个类。

问题1：什么是CStringList？CStringList是MFC框架中的一个类，它是一个模板类，用于处理字符串的链表。

它使用的是C++的模板机制，可以在链表中存储任意类型的数据。

但在这里，我们主要关注它在处理字符串方面的应用。

问题2：如何创建一个CStringList对象？要创建一个CStringList对象，只需简单地声明一个新的实例即可：CStringList strList;这将创建一个名为strList的CStringList对象。

您可以根据需要创建多个实例，并在程序的任何地方使用它们。

问题3：如何向CStringList中添加字符串？要向CStringList中添加字符串，可以使用AddHead()或AddTail()成员函数。

AddHead()函数将字符串添加到链表的头部，而AddTail()函数则将字符串添加到链表的尾部。

下面是一些示例代码：CStringList strList;strList.AddHead("Hello");strList.AddTail("World");这将创建一个名为strList的CStringList对象，并向其头部添加字符串"Hello"，在其尾部添加字符串"World"。

问题4：如何遍历并访问CStringList中的字符串？要遍历并访问CStringList中的字符串，可以使用CstringList的一个迭代器。

[转载整理]C语⾔链表实例 C语⾔链表有单链表、双向链表、循环链表。

单链表由数据域和指针域组成，数据域存放数据，指针域存放该数据类型的指针便于找到下⼀个节点。

双链表则含有头指针域、数据域和尾指针域，域单链表不同，双链表可以从后⼀个节点找到前⼀个节点，⼆单链表则不⾏。

循环链表就是在单链表的基础上，将头结点的地址指针存放在最后⼀个节点的指针域⾥以，此形成循环。

此外还有双向循环链表，它同时具有双向链表和循环链表的功能。

单链表如：链表节点的数据结构定义struct node{int num;struct node *p;} ;在此链表节点的定义中，除⼀个整型的成员外，成员p是指向与节点类型完全相同的指针。

※在链表节点的数据结构中，⾮常特殊的⼀点就是结构体内的指针域的数据类型使⽤了未定义成功的数据类型。

这是在C中唯⼀规定可以先使⽤后定义的数据结构。

链表实例代码：1// 原⽂地址 /wireless-dragon/p/5170565.html2 #include<stdio.h>3 #include<stdlib.h>4 #include<string.h>56 typedef int elemType;//定义存⼊的数据的类型可以是int char78 typedef struct NODE{ //定义链表的结构类型9 elemType element;10struct NODE *next;11 }Node;1213/************************************************************************/14/* 以下是关于线性表链接存储（单链表）操作的19种算法 */1516/* 1.初始化线性表，即置单链表的表头指针为空 */17/* 2.创建线性表，此函数输⼊负数终⽌读取数据*/18/* 3.打印链表，链表的遍历*/19/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为⼀个空表 */20/* 5.返回单链表的长度 */21/* 6.检查单链表是否为空，若为空则返回１，否则返回０ */22/* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停⽌程序运⾏ */23/* 8.从单链表中查找具有给定值x的第⼀个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */24/* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */25/* 10.向单链表的表头插⼊⼀个元素 */26/* 11.向单链表的末尾添加⼀个元素 */27/* 12.向单链表中第pos个结点位置插⼊元素为x的结点，若插⼊成功返回１，否则返回０ */28/* 13.向有序单链表中插⼊元素x结点，使得插⼊后仍然有序 */29/* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停⽌程序运⾏ */30/* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停⽌程序运⾏ */31/* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停⽌程序运⾏ */32/* 17.从单链表中删除值为x的第⼀个结点，若删除成功则返回1,否则返回0 */33/* 18.交换2个元素的位置 */34/* 19.将线性表进⾏冒排序 */35363738/*注意检查分配到的动态内存是否为空*/3940414243/* 1.初始化线性表，即置单链表的表头指针为空 */44void initList(Node **pNode)45 {46 *pNode=NULL;47 printf("initList函数执⾏，初始化成功\n");48 }4950/* 2.创建线性表，此函数输⼊负数终⽌读取数据*/51 Node *creatList(Node *pHead)52 {53 Node *p1,*p2;54 p1=p2=(Node *)malloc(sizeof(Node));55if(p1 == NULL || p2 ==NULL)57 printf("内存分配失败\n");58 exit(0);59 }60 memset(p1,0,sizeof(Node));6162 scanf("%d",&p1->element);63 p1->next=NULL;6465while(p1->element >0) //输⼊的值⼤于0则继续，否则停⽌66 {67if(pHead == NULL)//空表，接⼊表头68 {69 pHead=p1;70 }71else72 {73 p2->next=p1;74 }7576 p2=p1;77 p1=(Node *)malloc(sizeof(Node));7879if(p1==NULL||p2==NULL)80 {81 printf("内存分配失败\n");82 exit(0);83 }84 memset(p1,0,sizeof(Node));85 scanf("%d",&p1->element);86 p1->next=NULL;87 }88 printf("CreatList函数执⾏，链表创建成功\n");89return pHead;90 }9192/* 3.打印链表，链表的遍历*/93void printList(Node *pHead)94 {95if(NULL==pHead)96 {97 printf("PrintList函数执⾏，链表为空\n");98 }99else100 {101while(NULL!=pHead)102 {103 printf("%d\n",pHead->element);104 pHead=pHead->next;105 }106 }107108 }109110111/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为⼀个空表 */ 112void clearList(Node *pHead)113 {114 Node *pNext;115116if(pHead==NULL)117 {118 printf("clearList函数执⾏，链表为空\n");119return;120 }121while(pHead->next!=NULL)122 {123 pNext=pHead->next;124free(pHead);125 pHead=pNext;126 }127 printf("clearList函数执⾏，链表已经清除！\n");128129 }130131/* 5.返回链表的长度*/132int sizeList(Node *pHead)133 {134int size=0;135136while(pHead!=NULL)137 {138 size++;139 pHead=pHead->next;141 printf("sizelist函数执⾏，链表长度为%d\n",size);142return size;143 }144145/* 6.检查单链表是否为空，若为空则返回１，否则返回０ */146int isEmptyList(Node *pHead)147 {148if(pHead==NULL)149 {150 printf("isEmptylist函数执⾏，链表为空！\n");151return1;152 }153154else155 printf("isEmptylist函数执⾏，链表⾮空！\n");156return0;157158 }159160/* 7.返回链表中第post节点的数据，若post超出范围，则停⽌程序运⾏*/161int getElement(Node *pHead,int pos)162 {163int i=0;164if(pos<1)165 {166 printf("getElement函数执⾏，pos值⾮法！");167return0;168 }169if(pHead==NULL)170 {171 printf("getElement函数执⾏，链表为空！");172 }173174while (pHead!=NULL)175 {176 ++i;177if(i==pos)178 {179break;180 }181 pHead=pHead->next;182 }183if(i<pos)184 {185 printf("getElement函数执⾏，pos值超出链表长度\n");186return0;187 }188 printf("getElement函数执⾏，位置%d中的元素为%d\n",pos,pHead->element);189190return1;191 }192193//8.从单⼀链表中查找具有给定值x的第⼀个元素，若查找成功后，返回该节点data域的存储位置，否则返回NULL 194 elemType *getElemAddr(Node *pHead,elemType x)195 {196if(NULL==pHead)197 {198 printf("getEleAddr函数执⾏，链表为空");199return NULL;200 }201if(x<0)202 {203 printf("getEleAddr函数执⾏，给定值x不合法\n");204return NULL;205 }206while((pHead->element!=x)&&(NULL!=pHead->next))//判断链表是否为空，并且是否存在所查找的元素207 {208 pHead=pHead->next;209 }210if(pHead->element!=x)211 {212 printf("getElemAddr函数执⾏，在链表中没有找到x值\n");213return NULL;214 }215else216 {217 printf("getElemAddr函数执⾏，元素%d的地址为0x%x\n",x,&(pHead->element));218 }219return &(pHead->element);220221 }222223224/*9.修改链表中第pos个点X的值，如果修改成功，则返回1,否则返回0*/225int modifyElem(Node *pNode,int pos,elemType x)226 {227 Node *pHead;228 pHead=pNode;229int i=0;230if(NULL==pHead)231 {232 printf("modifyElem函数执⾏，链表为空\n");233return0;234 }235236if(pos<1)237 {238 printf("modifyElem函数执⾏，pos值⾮法\n");239return0;240 }241242while(pHead!= NULL)243 {244 ++i;245if(i==pos)246 {247break;248 }249 pHead=pHead->next;250 }251252if(i<pos)253 {254 printf("modifyElem函数执⾏，pos值超出链表长度\n");255return0;256 }257 pNode=pHead;258 pNode->element=x;259 printf("modifyElem函数执⾏,修改第%d点的元素为%d\n",pos,x);260261return1;262263 }264265/* 10.向单链表的表头插⼊⼀个元素 */266int insertHeadList(Node **pNode,elemType insertElem)267 {268 Node *pInsert;269 pInsert=(Node *)malloc(sizeof(Node));270if(pInsert==NULL) exit(1);271 memset(pInsert,0,sizeof(Node));272 pInsert->element=insertElem;273 pInsert->next=*pNode;274 *pNode=pInsert;275 printf("insertHeadList函数执⾏，向表头插⼊元素%d成功\n",insertElem);276return1;277 }278279/* 11.向单链表的末尾添加⼀个元素 */280int insertLastList(Node *pNode,elemType insertElem)281 {282 Node *pInsert;283 Node *pHead;284 Node *pTmp;285286 pHead=pNode;287 pTmp=pHead;288 pInsert=(Node *)malloc(sizeof(Node));289if(pInsert==NULL) exit(1);290 memset(pInsert,0,sizeof(Node));291 pInsert->element=insertElem;292 pInsert->next=NULL;293while(pHead->next!=NULL)294 {295 pHead=pHead->next;296 }297 pHead->next=pInsert;298 printf("insertLastList函数执⾏，向表尾插⼊元素%d成功!\n",insertElem);299return1;300 }301302/* 12.向单链表中第pos个结点位置插⼊元素为x的结点，若插⼊成功返回１，否则返回０*/ 303int isAddPos(Node *pNode,int pos,elemType x)304 {305 Node *pHead;306 pHead=pNode;307 Node *pTmp;308int i=0;309310if(NULL==pHead)311 {312 printf("AddPos函数执⾏，链表为空\n");313return0;314 }315316if(pos<1)317 {318 printf("AddPos函数执⾏，pos值⾮法\n");319return0;320 }321322while(pHead!=NULL)323 {324 ++i;325if(i==pos)326break;327 pHead=pHead->next;328 }329330if(i<pos)331 {332 printf("AddPos函数执⾏，pos值超出链表长度\n");333return0;334 }335336 pTmp=(Node *)malloc(sizeof(Node));337if(pTmp==NULL) exit(1);338 memset(pTmp,0,sizeof(Node));339 pTmp->next=pHead->next;340 pHead->next=pTmp;341 pTmp->element=x;342343 printf("AddPos函数执⾏成功，向节点%d后插⼊数值%d\n",pos,x); 344return1;345 }346347/* 13.向有序单链表中插⼊元素x结点，使得插⼊后仍然有序 */348int OrrderList(Node *pNode,elemType x)349 {350//注意如果此数值要排到⾏尾要修改本代码351 Node *pHead;352 pHead=pNode;353 Node *pTmp;354355if(NULL==pHead)356 {357 printf("OrrderList函数执⾏，链表为空\n");358return0;359 }360361if(x<1)362 {363 printf("OrrderList函数执⾏，x值⾮法\n");364return0;365 }366367while(pHead!=NULL)368 {369if((pHead->element)>=x)370break;371 pHead=pHead->next;372 }373374375if(pHead==NULL)376 {377 printf("OrrderList函数查找完毕，该函数中没有该值\n");378return0;379 }380381382 pTmp=(Node *)malloc(sizeof(Node));383if(pTmp==NULL) exit(1);384 memset(pTmp,0,sizeof(Node));385 pTmp->next=pHead->next;386 pHead->next=pTmp;387 pTmp->element=x;388389 printf("OrrderList函数成功插⼊数值%d\n",x);390return1;391 }392393/*14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停⽌程序运⾏*/ 394int DelHeadList(Node **pList)395 {396 Node *pHead;397 pHead=*pList;398if(pHead!=NULL)399 printf("DelHeadList函数执⾏,函数⾸元素为%d删除成功\n",pHead->element); 400else401 {402 printf("DelHeadList函数执⾏,链表为空!");403return0;404 }405 *pList=pHead->next;406return1;407 }408409/* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停⽌程序运⾏ */410int DelLastList(Node *pNode)411 {412 Node *pHead;413 Node *pTmp;414415 pHead=pNode;416while(pHead->next!=NULL)417 {418 pTmp=pHead;419 pHead=pHead->next;420 }421 printf("链表尾删除元素%d成功!\n",pHead->element);422free(pHead);423 pTmp->next=NULL;424return1;425 }426427/* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停⽌程序运⾏ */ 428int DelPos(Node *pNode,int pos)429 {430 Node *pHead;431 pHead=pNode;432 Node *pTmp;433434int i=0;435436if(NULL==pHead)437 {438 printf("DelPos函数执⾏，链表为空\n");439return0;440 }441442if(pos<1)443 {444 printf("DelPos函数执⾏，pos值⾮法\n");445return0;446 }447448while(pHead!=NULL)449 {450 ++i;451if(i==pos)452break;453 pTmp=pHead;454 pHead=pHead->next;455 }456457if(i<pos)458 {459 printf("DelPos函数执⾏，pos值超出链表长度\n");460return0;461 }462 printf("DelPos函数执⾏成功，节点%d删除数值%d\n",pos,pHead->element); 463 pTmp->next=pHead->next;464free(pHead);465return1;466 }467468/* 17.从单链表中删除值为x的第⼀个结点，若删除成功则返回1,否则返回0 */469int Delx(Node **pNode,int x)470 {471 Node *pHead;472 Node *pTmp;473 pHead=*pNode;474int i=0;475476if(NULL==pHead)477 {478 printf("Delx函数执⾏，链表为空");479return0;480 }481if(x<0)482 {483 printf("Delx函数执⾏，给定值x不合法\n");484return0;485 }486while((pHead->element!=x)&&(NULL!=pHead->next))//判断链表是否为空，并且是否存在所查找的元素487 {488 ++i;489 pTmp=pHead;490 pHead=pHead->next;491 }492if(pHead->element!=x)493 {494 printf("Delx函数执⾏，在链表中没有找到x值\n");495return0;496 }497if((i==0)&&(NULL!=pHead->next))498 {499 printf("Delx函数执⾏，在链表⾸部找到此元素,此元素已经被删除\n");500 *pNode=pHead->next;501free(pHead);502return1;503 }504 printf("Delx函数执⾏，⾸个为%d元素被删除\n",x);505 pTmp->next=pHead->next;506free(pHead);507return1;508 }509510/* 18.交换2个元素的位置 */511int exchange2pos(Node *pNode,int pos1,int pos2)512 {513 Node *pHead;514int *pTmp;515int *pInsert;516int a;517int i=0;518519if(pos1<1||pos2<1)520 {521 printf("DelPos函数执⾏，pos值⾮法\n");522return0;523 }524525 pHead=pNode;526while(pHead!=NULL)527 {528 ++i;529if(i==pos1)530break;531 pHead=pHead->next;532 }533534if(i<pos1)535 {536 printf("DelPos函数执⾏，pos1值超出链表长度\n");537return0;538 }539540 pTmp=&(pHead->element);541 i=0;542 pHead=pNode;543while(pHead!=NULL)544 {545 ++i;546if(i==pos2)547break;548 pHead=pHead->next;549 }550551if(i<pos2)552 {553 printf("DelPos函数执⾏，pos2值超出链表长度\n");554return0;555 }556557 pInsert=&(pHead->element);558 a=*pTmp;559 *pTmp=*pInsert;560 *pInsert=a;561562 printf("DelPos函数执⾏,交换第%d个和第%d个pos点的值\n",pos1,pos2); 563return1;564 }565566int swap(int *p1,int *p2)567 {568int a;569if(*p1>*p2)570 {571 a=*p1;572 *p1=*p2;573 *p2=a;574 }575return0;576 }577578/* 19.将线性表进⾏冒泡排序 */579int Arrange(Node *pNode)580 {581 Node *pHead;582 pHead=pNode;583584int a=0,i,j;585586if(NULL==pHead)587 {588 printf("Arrange函数执⾏，链表为空\n");589return0;590 }591592while(pHead!=NULL)593 {594 ++a;595 pHead=pHead->next;596 }597598 pHead=pNode;599for(i=0;i<a-1;i++)600 {601for(j=1;j<a-i;j++)602 {603 swap(&(pHead->element),&(pHead->next->element));604 pHead=pHead->next;605 }606 pHead=pNode;607 }608 printf("Arrange函数执⾏，链表排序完毕!\n");609return0;610 }611612int main()613 {614 Node *pList=NULL;615int length=0;616617 elemType posElem;618619 initList(&pList);620 printList(pList);621622 pList=creatList(pList);623 printList(pList);624625 sizeList(pList);626 printList(pList);627628 isEmptyList(pList);629630631 posElem=getElement(pList,3);632 printList(pList);633634 getElemAddr(pList,5);635636 modifyElem(pList,4,1);637 printList(pList);638639 insertHeadList(&pList,5);640 printList(pList);641642 insertLastList(pList,10);643 printList(pList);644645 isAddPos(pList,4,5); 646 printList(pList);647648 OrrderList(pList,6);649 printList(pList);650651 DelHeadList(&pList); 652 printList(pList);653654 DelLastList(pList);655 printList(pList);656657 DelPos(pList,5);658 printList(pList);659660 Delx(&pList,5);661 printList(pList);662663 exchange2pos(pList,2,5); 664 printList(pList);665666 Arrange(pList);667 printList(pList);668669 clearList(pList);670return0;671 }。

链表c语言经典例题
链表是计算机科学中的经典数据结构之一，常用于存储和操作动态数据。

以下是一些常见的链表例题，可以帮助理解链表的基本操作和应用。

1. 链表的创建：
- 创建一个空链表。

- 创建一个包含指定节点值的链表。

2. 链表的插入操作：
- 在链表的头部插入一个节点。

- 在链表的尾部插入一个节点。

- 在指定位置插入一个节点。

3. 链表的删除操作：
- 删除链表的头节点。

- 删除链表的尾节点。

- 删除指定数值的节点。

4. 链表的查找操作：
- 查找链表中指定数值的节点。

- 查找链表的中间节点。

5. 链表的逆序操作：
- 反转整个链表。

- 反转链表的前 N 个节点。

- 反转链表的一部分区间内的节点。

6. 链表的合并操作：
- 合并两个有序链表，使其有序。

- 合并 K 个有序链表，使其有序。

7. 链表的环检测：
- 判断链表中是否存在环，若存在，则返回环的起始节点。

8. 链表的拆分操作：
- 将一个链表按照奇偶位置拆分成两个链表。

以上是一些链表的经典例题，通过解答这些例题，可以加深对链表结构和基本操作的理解。

在编写对应的 C 语言代码时，需要注意链表节点的定义、指针的使用以及内存的动态分配和释放等问题。

链表生活中举例子链表是一种常见的数据结构，在生活中也有很多类似的例子可以来解释。

下面是符合要求的十个例子：1. 电线路：电线路可以看作是一条链表，电流从一端流向另一端。

每个电线都连接在一起，形成一个链式结构。

如果其中一个电线断开了，电流就无法顺利流通，就像链表中的节点断开一样。

2. 银行排队取款：在银行排队取款时，每个人按照先后顺序站在一起，形成一个队列。

当某个人取完款后，后面的人依次向前移动一个位置，就像链表中的节点删除和插入操作一样。

3. 图书馆书架：图书馆的书架上摆放着很多书籍，每本书都有自己的位置。

当有新书到达时，会被插入到合适的位置上，就像链表中的节点插入操作一样。

4. 手链：手链由一串串的珠子或者链节组成，每个珠子或链节都连接在一起。

当手链被拉伸时，每个珠子或链节都会依次移动，就像链表中的节点遍历一样。

5. 网络游戏中的队伍：在网络游戏中，玩家可以组队进行战斗。

每个队友按照先后顺序排列，形成一个队伍。

当队伍中有人离开或加入时，队伍的成员顺序会发生变化，就像链表中的节点删除和插入操作一样。

6. 交通信号灯：交通信号灯由红、黄、绿三个灯组成，每个灯都有自己的状态。

当信号灯的状态发生变化时，车辆会根据不同的灯光信号做出相应的动作，就像链表中的节点更新操作一样。

7. 餐厅的等候队列：在繁忙的餐厅，人们会排队等候就餐。

每个人按照先后顺序排列，形成一个等候队列。

当有桌子空出来时，排在队列最前面的人会被叫号，就像链表中的节点删除操作一样。

8. 航班座位预订系统：在航班座位预订系统中，每个座位都有自己的状态（已预订、空闲）。

当有人预订座位或取消预订时，座位的状态会发生变化，就像链表中的节点更新操作一样。

9. 电影院的座位安排：在电影院观影时，每个座位都有自己的位置。

当有人购买电影票时，会选择一个座位坐下，就像链表中的节点插入操作一样。

10. 城市地铁线路：城市地铁线路将不同的地铁站连接在一起，形成一个链式结构。

C语⾔链表实现商品库存管理系统本⽂实例为⼤家分享了C语⾔链表实现商品库存管理系统的具体代码，供⼤家参考，具体内容如下代码：12345678910111213141516171819202122 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54#include <stdio.h>#include <stdlib.h>#include <string.h>//定义⼀个商品结构体typedef struct sp{char no[12]; //商品编号char name[40]; //名称int workload; //库存量struct sp *next; //指向下⼀节点的指针} SP;//函数声明放在这⾥void ListCreate(SP *L, int n); //创建商品链表节点void LIstSearch(SP *L); //查找商品信息void ListModify(SP *L); //修改商品信息void ListInsert(SP *L); //插⼊商品信息void ListDelete(SP *L); //删除商品信息void Input(SP *p, int i); //输⼊商品信息void SumSp(SP *L); //统计商品的库存总量void Sort(SP *L); //对每类商品的库存量进⾏排名void Menu(); //考试报名管理系统的菜单//商品库存管理系统的主函数⼊⼝int main(){int item, n; //item⽤于接收输⼊的命令，n⽤于接收输⼊的商品⼈数 SP *L = NULL; //初始化⼀个头节点L = (SP *)malloc(sizeof(SP)); //为头节点开辟内存空间L->next = NULL; //将头节点的指针域置空do{Menu(); //菜单printf("请输⼊相应的数字，进⾏相应的操作:\n");scanf("%d", &item);55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 system("cls");switch(item){case1:printf("请输⼊您要录⼊的商品数⽬:");scanf("%d", &n);ListCreate(L, n);getchar();printf("\n请按任意键返回主菜单\n");getchar();system("cls");break;case2:LIstSearch(L); //查找商品信息getchar();printf("\n请按任意键返回主菜单\n");getchar();system("cls");break;case3:ListModify(L); //修改商品库存信息getchar();printf("\n请按任意键返回主菜单\n");getchar();system("cls");break;case4:ListDelete(L); //删除商品信息getchar();printf("\n请按任意键返回主菜单\n");getchar();system("cls");break;case5:ListInsert(L); //插⼊商品信息getchar();printf("\n请按任意键返回主菜单\n");getchar();system("cls");break;case6:SumSp(L);getchar();printf("\n请按任意键返回主菜单\n");getchar();system("cls");break;case7:Sort(L);getchar();printf("\n请按任意键返回主菜单\n");getchar();system("cls");break;case0: //退出商品库存管理系统printf("即将退出商品库存管理系统.....");exit(0);default:printf("您输⼊的指令不正确，请重新输⼊"); }printf("\n\n");} while(item);return0;}//创建链表，将新⽣成的节点插⼊到链表的表头void ListCreate(SP *L, int n){int i;for(i = 0; i < n; i++){SP *p;//将新⽣成的节点插⼊到链表中117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 p = NULL;p = (SP *)malloc(sizeof(SP));Input(p, i);p->next = L->next;L->next = p;}printf("录⼊成功！");}//查找商品库存量void LIstSearch(SP *L){char n[40];SP *p = L->next;if(p == NULL)printf("数据为空，⽆法查找！");else{printf("请输⼊您要查找的商品名称:");scanf("%s", n);while(strcmp(p->name, n) != 0){p = p->next;if(p == NULL){printf("没有找到相关信息\n");return;}}printf("%s的库存量为%d\n",p->name,p->workload);}}//修改商品的库存量void ListModify(SP *L){int a;char nam[40];SP *p = L->next;if(p == NULL)printf("数据为空，⽆法修改！");else{printf("请输⼊您修改的商品名称:");scanf("%s",nam);while(strcmp(p->name, nam) != 0){p = p->next;if(p == NULL){printf("没有找到相关信息\n");return;}}printf("请输⼊您修改后的库存量:");scanf("%d",&p->workload);printf("修改成功");}}//删除商品信息void ListDelete(SP *L){char n[40];SP *p = L->next, *pre = L; //定义p指针指向头节点的指向，定义pre指向头节点，pre始终指向p的前驱节点 if(p == NULL)printf("数据为空，⽆法删除！");else{printf("请输⼊您要删除的商品名称:");scanf("%s", n);while(strcmp(p->name, n) != 0)180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 p = pre->next;if(p == NULL){printf("没有找到相关信息，⽆法删除\n"); return;}}pre->next = p->next;free(p);printf("删除成功");}}//插⼊商品库存的相关信息void ListInsert(SP *L){SP *s = NULL; //⽣成⼀个新节点ss = (SP *)malloc(sizeof(SP));printf("请输⼊商品的商品编号:");scanf("%s", s->no);printf("请输⼊商品的名称:");scanf("%s", s->name);printf("请输⼊商品的库存量:");scanf("%d", &s->workload);s->next = L->next;L->next = s;printf("插⼊成功!");}//统计商品的库存总量void SumSp(SP *L){int sum=0;SP *p=L->next;while(p!=NULL){sum+=p->workload;p=p->next;}printf("商品的库存总量为%d\n",sum);}//对每类商品的库存量进⾏排名void Sort(SP *L){SP *p,*q,*tail,*l;tail=NULL;while((L->next->next) != tail){p = L;q = L->next;while(q->next != tail){if((q->workload) > (q->next->workload)){p->next = q->next;q->next = q->next->next;p->next->next = q;q = p->next;}q = q->next;p = p->next;}tail = q;}printf("商品库存量从⼩到⼤结果如下:\n");l=L->next;while(l!=NULL){if(l->next!=NULL){printf("%s(%d)->",l->name,l->workload); l=l->next;242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293{ printf("%s(%d)",l->name,l->workload); l=l->next;}}}//输⼊商品库存的相关信息void Input(SP *p, int i){ printf("请输⼊第%d 个商品的商品编号:", i + 1);scanf("%s", p->no);printf("请输⼊第%d 个商品的名称:", i + 1); scanf("%s", p->name); printf("请输⼊第%d 个商品的库存量:", i + 1); scanf("%d", &p->workload);}//商品库存管理系统的菜单void Menu(){ printf("\n\n"); printf("\t\t\t===================商品库存管理系统======================\n"); printf("\t\t\t* 作者:XXX 班级:XXXXXXXXXXX 学号:XXXXXXXXXX *\n"); printf("\t\t\t* *\n");printf("\t\t\t* 1>. 录⼊商品库存信息 *\n"); printf("\t\t\t* 2>. 查找某个商品的库存量 *\n"); printf("\t\t\t* 3>. 修改某个商品的库存量 *\n");printf("\t\t\t* 4>. 删除某个商品库存相关信息 *\n");printf("\t\t\t* 5>. 插⼊某个商品的相关信息 *\n");printf("\t\t\t* 6>. 统计商品的库存总量 *\n"); printf("\t\t\t* 7>. 对每类商品的库存量排名 *\n"); printf("\t\t\t* 0>. 退出管理系统 *\n"); printf("\t\t\t* 欢迎使⽤本系统!*\n");printf("\t\t\t========================================================\n");printf("\t\t\t 输⼊选项，按回车进⼊选项: \n");}部分运⾏结果截图以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。

C#数据结构之单链表（LinkList）实例详解本⽂实例讲述了C#数据结构之单链表(LinkList)实现⽅法。

分享给⼤家供⼤家参考，具体如下：这⾥我们来看下“单链表(LinkList)”。

在上⼀篇《》的最后，我们指出了：顺序表要求开辟⼀组连续的内存空间，⽽且插⼊/删除元素时，为了保证元素的顺序性，必须对后⾯的元素进⾏移动。

如果你的应⽤中需要频繁对元素进⾏插⼊/删除，那么开销会很⼤。

⽽链表结构正好相反，先来看下结构：每个元素⾄少具有⼆个属性：data和next。

data⽤来存放数据，⽽next⽤来指出它后⾯的元素是谁(有点“指针”的意思)。

链表中的元素，通常也称为节点Node，下⾯是泛型版本的Node.csnamespace 线性表{public class Node<T>{private T data;private Node<T> next;public Node(T val, Node<T> p){data = val;next = p;}public Node(Node<T> p){next = p;}public Node(T val){data = val;next = null;}public Node(){data = default(T);next = null;}public T Data{get { return data; }set { data = value; }}public Node<T> Next{get { return next; }set { next = value; }}}}链表在存储上并不要求所有元素按顺序存储，因为⽤节点的next就能找到下⼀个节点，这好象⼀根“⽤珠⼦串成的链⼦”，要找到其中的某⼀颗珠⼦，只要从第⼀颗节点(通常称为Head节点)开始，不断根据next指向找到下⼀个，直到找到需要的节点为⽌。

第二章指针与链表一、静态存贮和动态存贮1、静态存贮程序中的变量一经说明，计算机操作系统就会在内存空间中分配相应的存贮单元，其中变量名是存贮单元的地址，而变量的值是存贮单元的内容，且该存贮单元自始至终都被该变量所占用，直到程序结束。

如果变量是局部变量，那么在它的作用域内，一经说明也占有一定的存贮单元，直到退出其作用域为止。

这样的变量，在程序执行过程中，不能随时使用随时分配存贮空间，也不能在程序执行的过程中，释放这些空间。

也就是说，一旦给这些变量分配存贮空间，无论程序是否还需要使用，它们都要占用一定的存贮空间，以便给用户存贮数据。

我们称具有这样特点的存贮为静态存贮，它所对应的变量称为静态变量。

如字符类型、数组类型、记录类型等。

这类变量的优点是存贮方便，查找容易，可以通过一个简单的公式随机存取表中的任一元素，逻辑关系上相邻的两个元素在物理位置上也是相邻的，很容易找到前趋与后继元素；缺点是在线性表的长度不确定时，必须分配足够大的存储空间，经常浪费了宝贵的存储资源；而线性表的容量一经定义确定后就难以扩充；在插入和删除线性表的元素时，需要移动大量的元素，时间效率也比较差。

2、动态存贮在程序执行过程中，通过向操作系统申请存贮空间或释放存贮空间的命令，达到动态管理计算机的存贮空间，以保证存贮空间的充分利用。

存贮空间可以随时申请、随时释放，这样的存贮方式称为动态存贮，其变量称为动态变量。

指针变量即为动态变量。

动态存储所需要的空间可以是不连续的，这样有利于充分利用零散的小空间。

但缺无法用O（1）的时间实现存取了。

如何用这些零散的空间存储数组这些大规模数据呢？如何表示这些数据之间的逻辑关系呢？为了表示这些物理存储单元之间的逻辑关系，对于每个数据元素来说，除了要存储它本身的信息（数据域data）外，还要存储它的直接后继元素的存储位置（指针域，一般用link 或next 表示）。

我们往往把这两部分信息合在一起称为一个“结点node”。

实验二链表的基本操作链表是一种常用的数据结构，它由一系列节点组成，每个节点包含两部分：数据和指向下一个节点的指针。

链表的基本操作包括插入、删除和查找等。

本文将围绕链表的基本操作展开讲解，并以此为标题展开内容。

一、链表的插入操作链表的插入操作是指在链表中插入一个新的节点。

插入操作可以分为头插法和尾插法。

1. 头插法：将新节点插入链表的头部，即将新节点的指针指向原链表的头节点，再将链表的头指针指向新节点。

这样可以在常数时间内完成插入操作。

2. 尾插法：将新节点插入链表的尾部，即将原链表的尾节点指针指向新节点，再将新节点的指针指向空。

这样也可以在常数时间内完成插入操作。

二、链表的删除操作链表的删除操作是指删除链表中的一个节点。

删除操作可以分为删除指定节点和删除指定数值的节点两种情况。

1. 删除指定节点：找到待删除节点的前一个节点，将其指针指向待删除节点的下一个节点，再释放待删除节点的内存空间。

2. 删除指定数值的节点：遍历链表，找到数值匹配的节点并删除，具体操作与删除指定节点类似。

三、链表的查找操作链表的查找操作是指在链表中寻找某个节点或数值。

链表的查找操作与数组的查找操作不同，需要从头节点开始遍历整个链表。

1. 查找指定节点：遍历链表，逐个比较节点的值，直到找到目标节点或遍历到链表末尾。

2. 查找指定数值的节点：同样遍历链表，逐个比较节点的值，直到找到目标数值或遍历到链表末尾。

四、链表的其他操作除了插入、删除和查找操作外，链表还可以进行其他操作，如获取链表长度、反转链表和合并链表等。

1. 获取链表长度：遍历链表，计数节点的个数，即为链表的长度。

2. 反转链表：遍历链表，将每个节点的指针指向前一个节点，最后将链表的头指针指向原链表的尾节点。

3. 合并链表：将两个有序链表合并成一个新的有序链表。

遍历两个链表，逐个比较节点的值，将较小值的节点插入新链表中，直到其中一个链表遍历完毕，然后将另一个链表的剩余部分直接插入新链表的尾部。

linux 链表实例一、链表概述链表是一种常见的数据结构，主要由一系列节点组成。

每个节点包含两个部分：数据域和指针域。

数据域用于存储数据，指针域用于存储下一个节点的地址。

链表的头部和尾部分别用头指针和尾指针表示。

链表的头指针通常指向第一个节点，尾指针指向最后一个节点或者NULL。

二、链表节点结构体定义在Linux 系统中，我们可以使用结构体来定义链表节点。

以下是一个简单的链表节点结构体定义：```ctypedef struct Node {int data; // 数据域，存储节点数据struct Node *next; // 指针域，指向下一个节点} Node;```三、链表操作实例3.1 链表创建创建链表的常见方法是使用循环逐个初始化节点。

以下是一个创建链表的示例：```code *create_list(int num) {Node *head = NULL, *tail = NULL;for (int i = 0; i < num; i++) {Node *new_node = (Node *) malloc(sizeof(Node));new_node->data = i + 1;new_node->next = NULL;if (head == NULL) {head = new_node;tail = new_node;} else {tail->next = new_node;tail = new_node;}}return head;}```3.2 链表插入在链表的尾部插入节点，以下是一个插入节点的示例：```cvoid insert_node(Node **head, int data) {Node *new_node = (Node *) malloc(sizeof(Node));new_node->data = data;new_node->next = NULL;if (*head == NULL) {*head = new_node;} else {Node *temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = new_node;}}```3.3 链表删除根据节点值删除链表中的节点，以下是一个删除节点的示例：```cvoid delete_node(Node **head, int data) {if (*head == NULL) {return;}Node *temp = *head;while (temp->next != NULL && temp->next->data != data) { temp = temp->next;if (temp->next == NULL) {return;}if (temp->next->next == NULL) {free(temp->next);temp->next = NULL;} else {Node *next_node = temp->next->next;free(temp->next);temp->next = next_node;}}```3.4 链表遍历以下是一个遍历链表的示例：```cvoid traverse_list(Node *head) {Node *temp = head;while (temp != NULL) {printf("%d -> ", temp->data);temp = temp->next;printf("NULL");}```四、总结与拓展本文介绍了Linux 系统中链表的基本操作，包括链表的创建、插入、删除和遍历。

以下是一个简单的 C 语言链表示例题目：题目描述：给定一个整数数组，请将数组中的元素按逆序输出，并返回逆序输出后的数组。

示例：输入：[1,2,3,4,5]输出：[5,4,3,2,1]解题思路：可以使用链表来实现逆序输出数组。

具体步骤如下：1.定义一个链表结构体，包含一个整数和一个指向下一个节点的指针。

2.遍历给定的整数数组，将每个元素作为链表的节点插入到链表中。

3.定义一个指针指向链表的头节点，从头节点开始遍历链表，依次输出每个节点的值。

4.返回输出的结果数组。

代码如下：c复制代码#include<stdio.h>#include<stdlib.h>typedef struct ListNode {int val;struct ListNode *next;} ListNode;int* reverseList(int* head_ref, int size) {ListNode *p = (ListNode*)malloc(sizeof(ListNode)); // 创建头节点p->val = 0; // 头节点值为0，可以根据实际情况修改p->next = NULL; // 头节点指向空，表示链表为空ListNode *q = p; // q指向头节点，作为输出结果的起始位置for (int i = 1; i <= size; i++) { // 从第二个元素开始遍历数组ListNode *tmp = (ListNode*)malloc(sizeof(ListNode)); // 创建新节点tmp->val = head_ref[i]; // 将当前元素赋值给新节点tmp->next = NULL; // 新节点指向空，表示新节点为链表的最后一个节点q->next = tmp; // q指向的节点的下一个节点指向新节点，完成插入操作q = tmp; // q指向新节点，作为输出结果的下一个位置}int *res = (int*)malloc(sizeof(int) * size); // 创建结果数组int cnt = 0; // 结果数组计数器while (p->next != NULL) { // 遍历链表，依次输出每个节点的值到结果数组中res[cnt++] = p->next->val;p = p->next; // p向后移动到下一个节点}free(p); // 释放头节点内存空间return res; // 返回结果数组}。

链表在现实世界中的应用链表是一种常用的数据结构，它由一系列节点组成，每个节点包含两个部分：数据和指向下一个节点的指针。

链表在计算机科学中被广泛应用于各种场景，而在现实生活中，我们也可以找到许多应用链表的例子：1. 文件系统：在计算机的文件系统中，目录的结构就是一个链表。

每个目录（文件夹）都包含多个文件和子目录。

子目录可以包含更多的文件和子目录，形成了一个层次结构。

这种结构可以用链表来表示，其中每个节点都代表一个目录，节点中的数据部分包含目录的名称，而指针部分指向下一个目录。

2. 网页浏览器的历史记录：当你在网页浏览器中浏览网页时，浏览器的历史记录功能使用链表来记录你访问过的网页。

新访问的网页会被添加到链表的头部，而链表的尾部是你最早访问的网页。

这样，你就可以方便地向前翻页，查看你之前访问过的网页。

3. 电话簿：在电话簿应用中，联系人信息被存储在一个链表中。

每个节点都代表一个联系人，节点中的数据部分包含联系人的姓名和电话号码，指针部分指向下一个联系人。

通过这种方式，你可以方便地按照字母顺序或其他方式浏览联系人列表。

4. 音乐播放器：在许多音乐播放器中，歌曲的播放列表使用链表来组织。

用户可以添加、删除和编辑播放列表，这些操作都可以在链表上方便地实现。

5. 操作系统：在操作系统的进程管理中，链表用于存储正在运行的进程。

每个节点代表一个进程，节点中的数据部分包含进程的状态和相关信息，指针部分指向下一个进程。

操作系统需要经常对链表进行操作，如创建新进程、删除进程和调度进程等。

以上只是链表在现实世界中的一些应用示例，实际上链表的应用非常广泛，它是一种非常有用的数据结构。

链表—应⽤实例链表基本类型结构基本操作：在指定位置插⼊节点，删除节点，添加节点链表实现template <class T> class list{public:list();~list();void insert(list_node<T> *,const T &);void deletenode(list_node<T> *);void addnode(const T &);void print();private:list_node<T> *head;list_node<T> *rear;};template <class T> list<T>::list(){head=new list_node<T>();if (head==NULL)cerr<<"new error"<<endl;head->next=NULL;rear=head;}template<class T> void list<T>::addnode(const T &value){list_node<T>* p=new list_node<T>();p->value=value;p->next=NULL;rear->next=p;rear=p;}template<class T>void list<T>::insert(list_node<T> *pos,const T &value){list_node<T>* p=new list_node<T>;list_node<T>*q=p->nextp->value=value;p->next=pos->next;pos->next=p;}template<class T> void list<T>::deletenode(list_node<T> *pos){list_node<T> *p=head->next;while (p->next!=pos&&p->next!=NULL){p=p->next;}if (p->next==NULL){cout<<"count find postion"<<endl;}p->next=pos->next;delete pos;}template <class T> list<T>::~list(){list_node<T> *p=head,*q=NULL;while (p){q=p->next;delete p;p=q;}}template<class T> void list<T>::print(){list_node<T> *p=head->next;while (p){cout<<p->value<<endl;p=p->next;}}1.链表实现多项式加法如：a=3x^14+2x^8+1 b=8x^14-3x^10+10x^6多项式链式存储：struct poly_node{int coef; //系数int expen; //指数poly_node *next;};多项式加法poly_node * poly_add(poly_node *a,poly_node *b){poly_node *ap=a,*bp=b;poly_node *cp=NULL;poly_node *c=NULL;poly_node *p=NULL;poly_node *left=NULL;while (ap!=NULL&&bp!=NULL){p=(poly_node *)malloc(sizeof(poly_node));if(ap->expen==bp->expen){p->coef=ap->coef+bp->coef;p->expen=ap->expen;p->next=NULL;ap=ap->next;bp=bp->next;}else if (ap->expen>bp->expen){p->coef=ap->coef;p->expen=ap->expen;p->next=NULL;ap=ap->next;}else{p->coef=bp->coef;p->expen=bp->expen;p->next=NULL;bp=bp->next;}if(cp==NULL){cp=p;c=cp;}else{cp->next=p;cp=p;}}if(ap==NULL&&bp!=NULL){left=bp;}else if (ap!=NULL&&bp==NULL){left=ap;}elseleft=NULL;while (left){p=new poly_node;p->coef=left->coef;p->expen=left->expen;p->next=NULL;cp->next=p;cp=cp->next;left=left->next;}return c;}//将⼀个字符串表⽰的多项式转化链表形式poly_node * str2node(const char * str){poly_node * start=NULL;const char * p=str,*q=NULL;poly_node *newnode;poly_node *rear=NULL;;int value=0;int exp=0;int flag=1;while (*p){value=0;exp=0;flag=1;if (isdigit(*p)){q=p;flag=1;}else if(*p=='-'){flag=-1;q=p+1;value=0;}else if (*p=='+'){flag=1;q=p+1;value=0;}else{value=1;flag=1;}while (*q!='x'&&*q!='X'){value=value*10+*q-48;q++;}value=value*flag;q++;if(*q=='-'){flag=-1;q++;}else{flag=1;}while (*q!='\0'&&*q!='+'&&*q!='-'){exp=exp*10+*q-48;q++;}exp=exp*flag;newnode=new poly_node;newnode->coef=value;newnode->expen=exp;newnode->next=NULL;if(start==NULL){start=newnode;rear=newnode;}else{rear->next=newnode;rear=newnode;}p=q;}return start;}//将链表转化为字符串形式void node2str(poly_node *start,char *str){poly_node *p=start;char temp[64];while (p){sprintf(temp,"%+dx%d",p->coef,p->expen); strcat(str,temp);p=p->next;}}。

链表的经典习题练习1•：链式栈//链式栈(top指向第⼀位⽆效的头结点)public class LinkedStack<E> {Node<E> top;//内部类class Node<E> {protected E data;protected Node<E> next;public Node(E data) {this.data = data;}}public LinkedStack() {top = new Node(new Object());}//头插法public void push(E val){Node<E> newNode=new Node(val) ;//创建⼀个值为val的节点newNode.next=top.next; //新插⼊节点的next指向原top指向的nexttop.next=newNode;//再把top.next指向新节点}//获取栈顶元素并删除public E remove(){if(top.next==null){throw new UnsupportedOperationException("the stack has been empty");}E result=top.next.data;top.next=top.next.next;return result;}public E peek(){if(top.next==null){throw new UnsupportedOperationException("the stack has been empty");}return top.next.data;}//从top节点的下⼀个开始遍历，不为空则⼀直的打印public void show(){Node<E> tmp=top.next;while (tmp!=null){System.out.print(tmp.data+" ");tmp=tmp.next;}System.out.println();}public static void main(String[] args) {LinkedStack<Integer> l=new LinkedStack();l.push(3);l.push(4);l.push(5);l.show();System.out.println(l.peek());l.remove();//删除5l.show();l.remove();//删除4l.show();l.remove();//删除3l.show();}}练习2：查找链表中倒数第k个节点//单链表查找倒数第k个节点class FindLastK<E> {Node<E> head;class Node<E> {protected E data;protected Node<E> next;public Node(E data,Node<E> next) {this.data = data;this.next=next;}}////构造函数,第⼀个头结点有效，所以不需要构造函数// public FindLastK() {// this.head = new Node(new Object(),null);// }//找倒数第k个数的⽅法public E lastK(int k){Node<E> cur1=this.head.next;Node<E> cur2=this.head;//cur2指向头if(head==null){return null;}if(k>getLenth()||k<=0){return null;}else if(k==getLenth()){return head.data;}for(int i=1;i<=k;i++) {cur2=cur2.next;if(cur2==null){return null;}}while (cur2.next!=null){cur2=cur2.next;cur1=cur1.next;}return cur1.data;}//获取链表长度public int getLenth(){int length=0;Node<E> cu=head;if(head==null){return 0;}while (cu!=null){ //应该让cur去遍历，不能让head直接遍历，否则打印⼀次后show再次打印链表就会空 length++;cu=cu.next;}return length;}//尾插法public void add(E val) {Node<E> newNode = new Node(val,null);Node<E> current = head;if(head==null){head=newNode;return;}while (current.next != null) {current = current.next;}current.next = newNode;// newNode.next=null;}public void show() {Node<E> current = head;if(current==null){System.out.println("链表空！！");return;}while (current!=null&&current.next!= null) {System.out.print(current.data + " ");current = current.next;}System.out.println(current.data);}}public class FindLastKTest{public static void main(String[] args) {FindLastK<Integer> f=new FindLastK<>();f.add(3);f.add(4);f.add(5);f.add(6);f.show();System.out.println("该链表的长度："+f.getLenth());System.out.println(stK(1));//6System.out.println(stK(4));//3System.out.println(stK(5));//nullf.show();}}练习3：找到带环链表的⼊⼝节点import sun.awt.image.ImageWatched;//单链表查找倒数第k个节点public class LinkedExercise<E> {Node<E> head;static class Node<E> {protected E data;public Node<E> next;public Node(E data, Node<E> next) {this.data = data;this.next = next;}}////构造函数,第⼀个头结点有效，所以不需要构造函数// public FindLastK() {// this.head = new Node(new Object(),null);// }//找倒数第k个数的⽅法public E lastK(int k) {Node<E> cur1 = this.head.next;Node<E> cur2 = this.head;//cur2指向头if (head == null) {return null;} else if (k > getLenth() || k <= 0) {return null;}//如果找的倒数第k个恰好为链表长度，直接将头结点的数返回else if (k == getLenth()) {return head.data;}for (int i = 1; i <= k; i++) {cur2 = cur2.next;if (cur2 == null) {return null;}}//两个节点同时遍历，快节点遍历到最后⼀个节点时，慢节点指向的节点就是要找的节点while (cur2.next != null) {cur2 = cur2.next;cur1 = cur1.next;}return cur1.data;}//获取链表长度public int getLenth() {int length = 0;Node<E> cu = head;if (head == null) {return 0;}while (cu != null) { //应该让cur去遍历，不能让head直接遍历，否则打印⼀次后show再次打印链表就会空 length++;cu = cu.next;}return length;}//判断单链表是否有环/*** 快慢指针，先通过两个指针找到环内的节点，然后再⼀个节点从相交节点出发，* 另⼀个节点从头结点出发，再次相交的节点就是环的⼊⼝节点** @return*/public E getLinkCirclrVal() {Node<E> slow = this.head;Node<E> fast = this.head;//找到了相交节点while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {break;}}if (fast == null) {return null;} else {fast = this.head;while (fast != slow) {fast = fast.next;slow = slow.next;}return slow.data;}}//尾插法public void add(E val) {Node<E> newNode = new Node(val, null);Node<E> current = head;if (head == null) {head = newNode;return;}while (current.next != null) {current = current.next;}current.next = newNode;// newNode.next=null;}public void show() {Node<E> current = head;if (current == null) {System.out.println("链表空！！");return;}while (current != null && current.next != null) {System.out.print(current.data + " ");current = current.next;}System.out.println(current.data);}//构造带环的链表public void con(LinkedExercise<E> link){//将两个节点都指向头LinkedExercise.Node list=link.head;LinkedExercise.Node p=link.head;//list遍历到最后⼀个节点while (list.next!=null){list=list.next;}//让最后⼀个节点的写⼀个指向头结点的下⼀个 6指向5list.next=p.next.next;}public static void main(String[] args) {LinkedExercise<Integer> f = new LinkedExercise<>();f.add(3);f.add(4);f.add(5);f.add(6);f.show();System.out.println("该链表的长度：" + f.getLenth());System.out.println(stK(1));//6System.out.println(stK(4));//3System.out.println(stK(5));//nullf.con(f);System.out.println("环的⼊⼝节点："+f.getLinkCirclrVal());}}练习4：合并两个有序的链表（头结点⽆效时）包含头结点⽆效的⼤多数函数：class SingleLinekdListTakeHead<E extends Comparable> {protected Node<E> head;//头节点class Node<E> {protected E data;//数据域protected Node<E> next;//next引⽤域public Node(E data, Node<E> next) {this.data = data;this.next = next;}}//初始化headpublic SingleLinekdListTakeHead() {head = new Node(new Object(), null);}//在head之后直接插⼊⼀个节点，头插法public void addHead(E element) {Node<E> newNode = new Node(element, null);newNode.next = head.next;//先让新添加的节点的下⼀个指向原head节点指向的 head.next = newNode;//再让head节点指向新节点}//尾插法public void addTail(E element) {Node<E> newNode = new Node(element, null);Node<E> tail = head;//定义⼀个节点从头⾛到尾//tail⾛到当前链表的尾部while (tail.next != null) {tail = tail.next;}tail.next = newNode;newNode.next=null;}/*** 固定位置插⼊⼀个节点* 判断参数合法性* 找到pos位置的前⼀个节点* @param pos 固定位置* @param element 元素*/public void addPos(int pos, E element) {if (pos <= 0 || pos > getLength()) {return;}Node<E> prev = head.next;int index = 1;while (index++ < pos - 1) {prev = prev.next;}Node<E> newNode = new Node<>(element, null);newNode.next = prev.next;prev.next = newNode;}//删除元素为element的节点public boolean remove(E element) {//如果只有⼀个头结点，返回falseif (head.next == null) {return false;}//找到该元素所对应的节点 + 该元素所对应的节点的前⼀个 //从头结点开始遍历Node<E> tmp = head;while (tmp != null) {if (tmp.next != null && tmp.next.data == element) {//tmp.next是我们要删除的节点 tmp是删除节点的前⼀个 tmp.next = tmp.next.next;return true;}tmp = tmp.next;}return false;}//设置某个位置的值为newElementpublic void set(int pos, E newElement){if(pos <= 0 || pos > getLength()){return;}//找pos位置的节点Node<E> tmp = head.next;for(int i=1; i < pos; i++){tmp = tmp.next;}tmp.data = newElement;}//得到某个元素的值public E get(E element){Node<E> tmp = head.next;//从有效节点开始遍历while(tmp != null){if(tmp.data == element){return tmp.data; //找到的话，返回该节点}tmp = tmp.next;}return null;} //合并两个有序的单链表public void merge(SingleLinekdListTakeHead<E> list2){// LinkedExercise<E> list3=new LinkedExercise<>();Node<E> p=this.head;//最后合并成功的的链表Node<E> p1=this.head.next;//第⼀的链表Node<E> p2=list2.head.next;//第⼆个链表while (p1!=null && p2!=null){if(pareTo(p2.data)>=0){p.next=p2;//list3.add(p2.data);p2=p2.next;}else {p.next=p1;// list3.add(p1.data);p1=p1.next;}p=p.next;}if(p1!=null){ //链表1还有剩余节点p.next=p1;}p.next=p2;}// return p.data;}//返回长度public int getLength() {Node<E> tmp = head.next;int length = 0;while (tmp != null) {length++;tmp = tmp.next;}return length;}//打印栈public String toString() {StringBuilder strs = new StringBuilder();Node<E> tmp = head.next;while (tmp != null) {strs.append(tmp.data + " ");tmp = tmp.next;}return strs.toString(); //strs是StringBuilder类型，应该添加toString⽅法，才能返回String类型的 }//逆置带有头结点的单链表public void reverse(){if(head.next==null||head.next.next==null){return;}else {Node<E> cur=this.head.next.next;//指向第⼆个有效的节点this.head.next.next=null;Node<E> pos=null;while (cur!=null){pos=cur.next;//先将cur.next指向poscur.next=head.next;head.next=cur;//头插法，将节点插在head后cur=pos;}}}}public class Linked {public static void main(String[] args) {SingleLinekdListTakeHead<Integer> list=new SingleLinekdListTakeHead();list.addHead(3);list.addHead(5);list.addHead(8);System.out.println(list.toString());//8 5 3list.addTail(1);list.addTail(2);list.addTail(4);System.out.println(list.toString());//8 5 3 1 2 4list.reverse();System.out.println(list.toString());// list.addPos(2, 100); //在2 号位置加⼊元素100// System.out.println(list.toString());// list.addPos(0, 1000);// System.out.println(list.toString());//// list.remove(4);// System.out.println("删除值为4的元素:"+list.toString());//// list.set(2,2);//true,把2号元素的值改为2// System.out.println("把2号元素的值改为2:"+list.toString());// System.out.println(list.get(3));SingleLinekdListTakeHead list1=new SingleLinekdListTakeHead();list1.addTail(2);list1.addTail(6);list1.addTail(7);SingleLinekdListTakeHead list2=new SingleLinekdListTakeHead();list2.addTail(3);list2.addTail(4);list2.addTail(5);list2.addTail(9);list2.addTail(10);list1.merge(list2);System.out.println(list1.toString());}}练习5：链式队列package Exercise;public class LinkedQueue<T> {private Entry<T> front;private Entry<T> rear;private int count;public LinkedQueue(){this.front=this.rear=new Entry<>(null,null);}class Entry<T>{T data;Entry<T> next;public Entry(T data,Entry<T> next){this.data=data;this.next=next;}}public void offer(T data){Entry<T> node=new Entry<>(data,null);this.rear.next=node;this.rear=node;this.count++;}/***出队列需要判断队列空的情况，头节点⽆效；如果队列为空，需要将front和rear都指向空*/public void poll(){if(this.front.next!=null){this.front.next=this.front.next.next;if(this.front.next == null){this.rear = this.front;}this.count--;}}public int size(){return this.count;}public T peek(){return this.front.next.data;}public void show(){Entry<T> cur=this.front.next;while (cur!=null){System.out.print(cur.data+" ");cur=cur.next;}System.out.println();}public static void main(String[] args) {LinkedQueue l=new LinkedQueue();for (int i = 0; i < 4; i++) {l.offer(i);}l.show();System.out.println("队头元素为:"+l.peek());System.out.println("队列长度为："+l.size());l.poll();l.show();}}难点：内部类和外部类的构造函数都需要对相应属性做初始化。

带头节点的循环单链表带头节点的循环单链表是一种特殊的链表结构，它在普通的循环单链表的基础上增加了一个头节点。

本文将详细介绍带头节点的循环单链表的特点、操作以及应用场景。

一、带头节点的循环单链表的特点带头节点的循环单链表与普通的循环单链表相比，多了一个头节点，头节点不存储任何数据，仅作为链表的标志和辅助作用。

头节点的存在使得链表的插入、删除等操作更加方便，同时也能避免一些特殊情况的处理。

1. 初始化链表：创建一个头节点，并将头节点的指针指向自身，表示链表为空。

2. 判断链表是否为空：通过判断头节点的指针是否指向自身，即可判断链表是否为空。

3. 插入节点：在链表的指定位置插入一个新节点。

首先找到插入位置的前一个节点，然后将新节点的指针指向前一个节点的下一个节点，再将前一个节点的指针指向新节点。

4. 删除节点：删除链表中指定位置的节点。

首先找到要删除节点的前一个节点，然后将前一个节点的指针指向要删除节点的下一个节点，最后释放被删除节点的内存空间。

5. 遍历链表：从头节点开始，按照指针的方向遍历链表，直到回到头节点为止，输出每个节点的数据。

三、带头节点的循环单链表的应用场景带头节点的循环单链表在实际应用中有着广泛的应用场景，以下是几个典型的应用场景：1. 约瑟夫环问题：约瑟夫环是一种数学问题，通过使用带头节点的循环单链表可以很方便地解决该问题。

2. 循环队列：循环队列是一种常见的队列结构，使用带头节点的循环单链表可以实现循环队列的操作。

3. 循环链表：带头节点的循环单链表本身就是一种循环链表，可以用于解决一些需要循环访问的问题。

总结：带头节点的循环单链表是一种特殊的链表结构，通过增加一个头节点，使得链表的操作更加方便，并且能够避免一些特殊情况的处理。

带头节点的循环单链表可以用于解决一些需要循环访问的问题，例如约瑟夫环问题和循环队列等。

掌握带头节点的循环单链表的基本操作，对于理解和应用链表结构具有重要的意义。