苏州网站建设营销,中企动力 网站模板,容桂网站制作公司,海晏网站建设公司http://blog.csdn.net/fisherwan/article/details/19701027 我学习了几天数据结构#xff0c;今天下午自己写了一个单向链表的程序。我也是新手#xff0c;所以刚开始学习数据结构的菜鸟们#xff08;有大牛们能屈尊看一看#xff0c;也是我的荣幸#xff09;可以和我一起…http://blog.csdn.net/fisherwan/article/details/19701027 我学习了几天数据结构今天下午自己写了一个单向链表的程序。我也是新手所以刚开始学习数据结构的菜鸟们有大牛们能屈尊看一看也是我的荣幸可以和我一起共同学习、讨论当然也很高兴能指出我的错误因为这是我们一起成长的过程。本代码包含我在写程序时的一些个人理解的说明和一些注释如果那里说错了望大家来指正下面就进入正题了。 首先这是个单向链表的代码下面是我找的一张单向链表的示意图。 很明显可以看出它们是像链子一样串在一起它们是靠什么串在一起的呢可能有些人已经知道了——是指针这里的每一个方格我们叫做“节点”每一个节点包含一个指针指向下一个节点并且自己被上一个节点的指针指着然后串在一起。但是这里有一点要注意就是头节点就是图中的第一个节点是不被其他节点指着的尾节点就是图中的最后一个节点不指向其他的节点程序中我们让它指向NULL就是不指向任何东西。 SgLInkList.h 头文件 这里定义了节点的结构包括一个数据成员和一个结构体指针结构体指针是用来指向下一个节点用的还包括单向链表的相关操作。 [cpp] view plain copy #ifndef _SINGLY_LINKED_LIST_H_H #define _SINGLY_LINED_LIST_H_H //设计节点结构 typedef struct Node { int data; struct Node *pNext; }NODE, *pNODE; //创建单向链表 pNODE CreateSgLinkList(void); //打印单向链表 void TraverseSgLinkList(pNODE pHead); //判断单向链表是否为空 int IsEmptySgLinkList(pNODE pHead); //计算单向链表的长度 int GetLengthSgLinkList(pNODE pHead); //向单向链表插入节点 int InsertEleSgLinkList(pNODE pHead, int pos, int data); //从单向链表删除节点 int DeleteEleSgLinkList(pNODE pHead, int pos); //删除整个链表释放内存 void FreeMemory(pNODE *ppHead); #endif SgLinkList.cpp 存放单向链表相关操作函数的定义包含链表的创建、链表值的打印、判断链表是否为空、计算链表长度、插入节点、删除节点、删除整个链表。 [cpp] view plain copy #include stdio.h #include stdlib.h #include SgLinkList.h 1第一个函数是创建单向链表这里我首先创建了一个节点作为头节点但是这个头节点不参与后面相关函数的运行例如头结点不参与链表数据的打印只包含头节点不包含其他节点时该链表判断为空计算链表长度时头结点不参与计数删除和插入节点函数也都是从头节点后面的节点计数的。当然有一点最后释放内存的时候头节点是要跟着一起释放的因为给头节点分配了内存所以也得释放要不会造成内存泄露这一点很容易忽视了。 [cpp] view plain copy //创建单向链表 pNODE CreateSgLinkList(void) { int i, length, data; pNODE p_new NULL, pTail NULL; //创建头节点头结点是第0个节点后面的节点从1开始计数 pNODE pHead (pNODE)malloc(sizeof(NODE)); if (NULL pHead) { printf(内存分配失败\n); exit(EXIT_FAILURE); } pHead-data 0; pHead-pNext NULL; pTail pHead; printf(请输入要创建链表的长度); scanf(%d, length); for (i1; ilength1; i) { p_new (pNODE)malloc(sizeof(NODE)); if (NULL p_new) { printf(内存分配失败\n); exit(EXIT_FAILURE); } printf(请输入第%d个节点的值, i); scanf(%d, data); p_new-data data; p_new-pNext NULL; pTail-pNext p_new; pTail p_new; } return pHead; } 2这个是打印单向链表函数可以看到是从头结点的后面一个节点开始打印的ppHead-pNext。一直打印到最后一个[cpp] view plain copy //打印单向链表不打印头结点的值。 void TraverseSgLinkList(pNODE pHead) { pNODE pt pHead-pNext; printf(打印链表); while (pt ! NULL) { printf(%d , pt-data); pt pt-pNext; } putchar(\n); } 3这个是判断链表是否为空的函数通过检查头节点的后面一个节点来判断所以这里头节点也不参与运算。[cpp] view plain copy //判断链表是否为空 int IsEmptySgLinkList(pNODE pHead) { if (pHead-pNext NULL) return 1; else return 0; } 4这个是计算链表长度的函数也是从头节点后面的节点开始找到节点就让length加1直到找到最后一个节点为止。[cpp] view plain copy //计算单向链表长度 int GetLengthSgLinkList(pNODE pHead) { int length 0; pNODE pt pHead-pNext; while (pt ! NULL) { length; pt pt-pNext; } return length; } 5这个是向单向链表插入节点的函数这里我定义位置值是从1开始到链表长度加1结束当然也可以自己定义从什么数值开始这里位置要比删除节点函数多一个为什么呢例如一个链表包含三个节点头节点除外它们的元素值分别为1、2、3那么我们可以插入节点的地方就有4个位置了4个位置夹住了三个节点。但是如果是删除节点函数的话呢操作的是实际的节点所以位置值就只能是这三个节点了。说到这里大家应该明白了吧。这里附一张插入节点的示意图 [cpp] view plain copy //向单向链表插入一个节点,位置从1开始到链表长度加1结束。 int InsertEleSgLinkList(pNODE pHead, int pos, int data) { pNODE pt NULL, p_new NULL; if (pos 0 pos GetLengthSgLinkList(pHead) 2) { p_new (pNODE)malloc(sizeof(NODE)); if (NULL p_new) { printf(内存分配失败\n); exit(EXIT_FAILURE); } p_new-data data; while (1) { pos--; if (0 pos) break; pHead pHead-pNext; } pt pHead-pNext; pHead-pNext p_new; p_new-pNext pt; return 1; } else return 0; } 6这个是删除单向链表节点的函数至于位置值为什么是从1到链表的长度上面已经介绍过了这里就不再介绍了。这里就说说在删除节点时要注意的地方首先你要找到要删除的那个节点然后把要删除节点的下一个节点的地址保存好这里保存到pt然后释放该节点的内存让改指针指向NULL指针这里因为马上要用到这个指针就没有让它指向NULL指针接着让被删除节点的上一个的指针指向上面保存好的节点地址也就是pt这样节点被删除了内存也释放了链表也连接起来了。这就是我个人的简单理解下面附一张示意图 [cpp] view plain copy //从单向链表中删除一个节点位置从1开始到链表长度结束。 int DeleteEleSgLinkList(pNODE pHead, int pos) { pNODE pt NULL; if (pos 0 pos GetLengthSgLinkList(pHead) 1) { while (1) { pos--; if (0 pos) break; pHead pHead-pNext; } pt pHead-pNext-pNext; free(pHead-pNext); pHead-pNext pt; return 1; } else return 0; } 7这个是删除整个单向链表的函数当然也起到了释放内存的作用。这里有两个地方要注意的就是第一头节点的内存也要参与释放因为它也分配了内存第二这里为什么要用到指向结构体指针的指针因为内存的分配和释放的原因那么有人可能就要问了为什么上面创建链表的时候没有用到这个那是因为上面用到了返回值来获得分配的内存这也是一种方法。 这里我就补充个知识点可能有很多人已经知道了指针做函数的形参时编译器总是要为函数的每个参数制作临时副本指针参数p的副本是ptemp编译器使ptempp。如果函数体的程序修改了ptemp的内容就相应的就该了参数p的内容这就是指针可以用作输出参数的原因。但是在申请内存时情况就不一样了因为只是把ptemp所指向的内存地址改变了但是p丝毫未变。所以如果非要用指针参数去申请内存那么应该用“指向指针的指针”。 [cpp] view plain copy //删除整个单向链表释放内存。 void FreeMemory(pNODE *ppHead) { pNODE pt NULL; while (*ppHead ! NULL) { pt (*ppHead)-pNext; free(*ppHead); *ppHead pt; } } main.cpp这是测试程序判断函数是否得到了正确的结果。 [cpp] view plain copy #include stdio.h #include stdlib.h #include SgLinkList.h int main(void) { int flag 0, length 0; int position 0, value 0; pNODE head NULL; head CreateSgLinkList(); flag IsEmptySgLinkList(head); if (flag) printf(单向链表为空\n); else { length GetLengthSgLinkList(head); printf(单向链表的长度为%d\n, length); TraverseSgLinkList(head); } printf(请输入要插入节点的位置和元素值(两个数用空格隔开)); scanf(%d %d, position, value); flag InsertEleSgLinkList(head, position, value); if (flag) { printf(插入节点成功\n); TraverseSgLinkList(head); } else printf(插入节点失败\n); flag IsEmptySgLinkList(head); if (flag) printf(单向链表为空不能进行删除操作\n); else { printf(请输入要删除节点的位置); scanf(%d, position); flag DeleteEleSgLinkList(head, position); if (flag) { printf(删除节点成功\n); TraverseSgLinkList(head); } else printf(删除节点失败\n); } FreeMemory(head); if (NULL head) printf(已成功删除单向链表释放内存完成\n); else printf(删除单向链表失败释放内存未完成\n); return 0; } 最后我想给和我一样正在学习编程并打算把编程学好的志同道合之人一个小小的建议光看这个代码是没有用的还是得自己动手敲一遍因为里面有些细节有可能你没有想到当然你是编程神通一眼就可以看会的话那就算我多嘴了。但是我想我们都是普通天才还是占少数的所以还是要动手。 希望能跟大家一起交流好的代码、好的想法祝大家都能梦想成真
