第10章基本数据结构—补充案例

博学谷——让IT教学更简单，让IT学习更有效1第10章基本数据结构案例10-1链表的本质、定义、初始化一、案例描述1、考核知识点编号：00610001名称：链表的本质、定义、初始化2、练习目标掌握链表的本质及链表的定义、初始化的格式3、需求分析用数组存放数据时，必须事先定义数组长度。但有时程序中存放数据的个数是无法确定的。这种情况可以通过定义一个足够大的数组来解决，但是这样难免会浪费内存，而且也无法明确到底多大的数组才足够。在C语言中存在一种特殊的数据结构：链表，链表存储的数据个数不固定，可以很好地解决上述问题。为了加深读者对链表的本质、定义、初始化的理解，本案例将定义并初始化一个链表。4、设计思路（实现原理）1）定义链表节点和链表头节点2）声明main()函数，在main()函数中，初始化链表。二、案例实现编写程序，代码如下：1#includestdio.h2#includestdlib.h3structNode4{5intdata;6structNode*next;7};8structLinkHead9{10intlength;11structNode*head;12};13voidinitLink(structLinkHead*linkHead)14{15linkHead-length=0;博学谷——让IT教学更简单，让IT学习更有效216linkHead-head=NULL;17}18voidmain()19{20structLinkHead*linkHead=(structLinkHead*)malloc(sizeof(struct21LinkHead));22initLink(linkHead);23free(linkHead);24}三、案例总结1、链表如同一条铁链一样，一环扣一环，中间是不能断开的。2、链表的节点和链表的头节点是由两个不同类型的数据组成。3、用malloc申请内存后记得用free释放内存，否则内存得不到释放，易造成内存泄露。案例10-2链表的常用操作一、案例描述1、考核知识点编号：00610002名称：链表的常用操作2、练习目标掌握链表的常用操作3、需求分析链表这种数据结构在编写程序时应用非常广泛，因此熟练地使用链表对优化程序中的数据存储很重要。为了加深初学者对链表的常用操作的理解，本案例将针对链表的获取表元、插入元素、删除元素等常见操作进行讲解。4、设计思路（实现原理）1）定义链表节点和链表头节点。2）实现获取表元、插入元素、查找元素、删除元素、释放链表的函数功能。二、案例实现编写程序，代码如下：1#includestdio.h2#includestdlib.h3structNode4{5intdata;6structNode*next;博学谷——让IT教学更简单，让IT学习更有效37};8structLinkHead9{10intlength;11structNode*head;12};1314voidinitLink(structLinkHead*linkHead)15{16linkHead-length=0;17linkHead-head=NULL;18}19structNode*getNode(structLinkHead*linkHead,intindex)20{21structNode*p=linkHead-head;22for(inti=0;iindex;++i)23{24p=p-next;25}26returnp;27}28voidinsertNode(structLinkHead*linkHead,intindex,intdata)29{30structNode*node=(structNode*)malloc(sizeof(structNode));31node-data=data;32if(index==0)33{34node-next=linkHead-head;35linkHead-head=node;36}37else38{39structNode*priv=getNode(linkHead,index-1);40node-next=priv-next;41priv-next=node;42}43linkHead-length++;44}45structNode*findNode(structLinkHead*linkHead,intdata)46{47structNode*node=linkHead-head;48while(node!=NULL)49{50if(node-data==data)//检查当前节点的值是否匹配博学谷——让IT教学更简单，让IT学习更有效451{52returnnode;53}54else//若不匹配，则移动到下个节点55{56node=node-next;57}58}59returnNULL;60}61voiddeleteNode(structLinkHead*linkHead,intindex)62{63structNode*node;64if(index==0)65{66node=linkHead-head;67linkHead-head=node-next;68free(node);69}70else71{72structNode*prev=findNode(linkHead,index-1);73node=prev-next;74prev-next=node-next;75free(node);76}77linkHead-length--;78}79voidfreeNode(structLinkHead*linkHead)80{81structNode*node=linkHead-head;82while(node!=NULL)83{84linkHead-head=node-next;85free(node);86node=linkHead-head;87}88linkHead-length=0;89}9091voidmain()92{93}博学谷——让IT教学更简单，让IT学习更有效5三、案例总结1、操作链表时一定要保证节点之间是连接的，否则将找不到断掉的节点。2、为链表节点申请内存后，使用完一定要记得释放内存，否则会造成内存泄露。案例10-3链表操作的综合案例一、案例描述1、考核知识点编号：00610003名称：链表操作的综合案例2、练习目标了解链表操作的综合案例3、需求分析为了让读者能够更好地掌握链表的使用，接下来通过一个综合案例来演示如何创建链表、如何向链表中添加元素、如何查找链表、如何删除链表中的元素以及如何释放链表所占的内存。4、设计思路（实现原理）1）定义链表节点和链表头节点。2）实现获取表元、插入元素、查找元素、删除元素、释放链表的函数功能。3）声明main()函数，在main()函数体内调用函数操作链表。二、案例实现编写程序，代码如下：1#includestdio.h2#includestdlib.h3structNode4{5intdata;6structNode*next;7};8structLinkHead9{10intlength;11structNode*head;12};13voidinitLink(structLinkHead*linkHead)14{15linkHead-length=0;博学谷——让IT教学更简单，让IT学习更有效616linkHead-head=NULL;17}18structNode*getNode(structLinkHead*linkHead,intindex)19{20structNode*p=linkHead-head;21for(inti=0;iindex;++i)22{23p=p-next;24}25returnp;26}27voidinsertNode(structLinkHead*linkHead,intindex,intdata)28{29structNode*node=(structNode*)malloc(sizeof(structNode));30node-data=data;31if(index==0)32{33node-next=linkHead-head;34linkHead-head=node;35}36else37{38structNode*priv=getNode(linkHead,index-1);39node-next=priv-next;40priv-next=node;41}42}43structNode*findNode(structLinkHead*linkHead,intdata)44{45structNode*node=linkHead-head;46while(node!=NULL)47{48if(node-data==data)//检查当前节点的值是否匹配49{50returnnode;51}52else//若不匹配，则移动到下个节点53{54node=node-next;55}56}57returnNULL;58}59voiddeleteNode(structLinkHead*linkHead,intindex)博学谷——让IT教学更简单，让IT学习更有效760{61structNode*node;62if(index==0)63{64node=linkHead-head;65linkHead-head=node-next;66free(node);67}68else69{70structNode*prev=getNode(linkHead,index-1);71node=prev-next;72prev-next=node-next;73free(node);74}75linkHead-length--;76}77voidfreeLink(structLinkHead*linkHead)78{79structNode*node=linkHead-head;80while(node!=NULL)81{82linkHead-head=node-next;83free(node);84node=linkHead-head;85}86linkHead-length=0;87}88voidprintLink(structLinkHead*linkHead)89{90structNode*node=linkHead-head;91while(node)92{93printf([%d],node-data);94node=node-next;95}96printf(\n);97}98voidmain()99{100structLinkHead*linkHead=101(structLinkHead*)malloc(sizeof(structLinkHead));102initLink(linkHead);103for(inti=1;i10;i+=2)博学谷——让IT教学更简单，让IT学习更有效8104{105insertNode(linkHead,0,i);106}107printf(输出链表的数据：\n);108printLink(linkHead);109deleteNode(linkHead,1);110printf(删除第2个元素后，输出链表的数据：\n);111printLink(linkHead);112freeLink(linkHead);113}运行结果如图10-1所示。图10-1运行结果三、案例总结在该案例中，定义了许多函数，这些函数的功能各不相同。其中，第18-26行代码定义的函数getNode()用于获取表元。第27-42行代码定义的函数insertNode()用于向链表的指定位置插入元素。第43-58行代码定义的函数findNode()