单链表的实现一.链表的概念与结构二.文件的创造三.对存储的数据进行重命名typedef四.存数据五.创建节点以及连接节点5.1使用malloc函数申请空间5.2创建和连接节点的两个方法5.2.1第一种方法的代码5.2.2第二种方法的代码六.关于单链表的方法的实现6.1链表的打印6.2链表的尾插6.3链表的头插6.4链表的尾删6.5链表的头删6.6链表的查找6.7链表指定位置的删除6.8链表的销毁一.链表的概念与结构链表是一种物理存储结构上非连续,非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。二.文件的创造要实现单链表,首先要创建三个文件,一个头文件,两个点c文件,SList.h是用来定义结构体的,以及一些函数的声明,在SList.c文件是对那些函数的实现的具体步骤,最后的test.c文件是对这个链表的测试三.对存储的数据进行重命名typedef为什么要对数据进行typedef主要是因为如果在代码量特别大的情况下如果存储的数据有所变化的话对数据类型一个一个改变的话太过于麻烦但是如果有typedef的话仅仅需要改变一个就行typedefintSLTDataType四.存数据对于链表来说我们要通过地址去访问数据我们不妨把每个节点的地址都存起来并且创建一个结构体去存储当前的数据并且记录下来下一个节点的地址structSListNode{structSListNode*next;//存储着下一个节点SLTDataType x;//存储上数据};为了方便写结构体的类型我们也可以把结构体类型也给重命名所以也可以这么写但是切记结构体里面的struct SListNode不能改变因为在结构体里面找不到重命名的操作typedefstructSListNode{structSListNode*next;//存储着下一个节点SLTDataType x;//存储上数据}SLTNode;五.创建节点以及连接节点5.1使用malloc函数申请空间先讲一下关于申请空间所需要的函数malloc,此函数仅有一个参数就是你需要插入的数据的字节长度即sizeof,对于链表我们只需申请sizeof(SLTNode)这么多空间就可以并且要把malloc的返回值强转为结构体类型的指针代码如下(SLTNode*)malloc(sizeof(SLTNode));5.2创建和连接节点的两个方法创建节点可分为两种办法直接创建所需要的数据并且存储起来最后再把节点连接起来在需要创建数据的时候再去申请出来一块空间从而把新创建出来的节点与上一个连接起来5.2.1第一种方法的代码//创建节点存储数据SLTNode*phead(SLTNode*)malloc(sizeof(SLTNode));phead-x1;SLTNode*newnode1(SLTNode*)malloc(sizeof(SLTNode));phead-x2;SLTNode*newnode2(SLTNode*)malloc(sizeof(SLTNode));phead-x3;//连接节点phead-nextnewnode1;newnode-nextnewnode2;newnode2-nextNULL;//最后一个节点的next为空指针因为单链表不循环防止next成为野指针5.2.2第二种方法的代码我们可以先封装成一个函数如果需要插入数据直接调用这个函数就行SLTNode*SLTBuyNode(SLTDataType x){SLTNode*newnode(SLTNode*)malloc(sizeof(SLTNode));//申请空间失败直接退出if(newnodeNULL){perror(malloc);exit(1);}//代码到这里说明申请成功了newnode-nextNULL;newnode-xx;returnnewnode;}六.关于单链表的方法的实现6.1链表的打印下图就是链表的结构我们可以通过这个图形进行链表的打印我们可以通过头节点从头节点开始访问完再访问这个节点的next节点从而遍历整个链表代码如下voidSLTPrint(SLTNode*phead){SLTNode*headphead;while(head!NULL)//只要下一个节点不为空就一直访问{printf(%d-,head-x);headhead-next;}printf(NULL\n);}6.2链表的尾插我们同样使用上图进行分析从而写出尾插的代码1. 在上面的第二种方法创建节点的方式的代码已经写过所以我们直接调用函数我们要通过头节点找到末尾的节点从而实现链表的链接。2. 但是我们应注意一点的就是在实现这个函数的时候头节点要传二级指针因为如果这个是个空链表的话那么我们就会对头节点进行修改所以要传二级指针除此之外我们还要防止传入的指针为空所以要assert断言3. 在测试代码的时候传入的头指针的地址phead。voidSLTPushBack(SLTNode**phead,SLTDataType x){assert(phead);//防止传入的为空指针SLTNode*newnodeSLTBuyNode(x);SLTNode*plist*phead;if(*pheadNULL){*pheadnewnode;//修改了头节点}else{while((plist)-next){plist(plist)-next;}(plist)-nextnewnode;}}6.3链表的头插我们先根据下图去理解头插的操作1. 关于头插我们要将新来的节点头插到头结点的前面2. 还要把新来的节点的next指针指向原链表的头节点3. 最后再让新插入的节点的地址newnode成为新链表的头节点voidSLTPushFront(SLTNode**phead,SLTDataType x){assert(phead);SLTNode*newnodeSLTBuyNode(x);newnode-next*phead;*pheadnewnode;}6.4链表的尾删对于尾删直接介绍我们只需要将指向尾节点的那个next指向NULL就可以最后销毁原链表的尾节点的那块空间并且free掉那块空间再将指向那块空间的指针置为空需要注意的点1. 传入的头节点不能为空2. 链表也不可以为空3. 应定义两个指针的、找到尾节点和倒数第二个节点4. 特别考虑只有一个头节点的情况***先说一下只有头结点的情况只需要free掉那个空间就行并且把头节点置为空if ((phead)-next NULL){free(phead);phead NULL;return;}知道以上的操作之后我们只需要这样写while循环就可以while (cur-next){plist cur;cur cur-next;}所以代码如下voidSLTPopBack(SLTNode**phead){assert(phead*phead);if((*phead)-nextNULL)//如果只有一个节点的情况{free(*phead);*pheadNULL;return;}SLTNode*cur*phead;SLTNode*plist*phead;while(cur-next){plistcur;curcur-next;}plist-nextNULL;free(cur);curNULL;}6.5链表的头删对于头删的直接介绍我们直接把头指针存下来让头指针指向头指针的next最后销毁空间再将指向原链表的指针置为NULL。需要注意的点传入的头节点不能为空链表也不可以为空***voidSLTPopFront(SLTNode**phead){assert(phead*phead);SLTNode*plist*phead;*phead(*phead)-next;//改变头节点free(plist);plistNULL;}6.6链表的查找这里的查找是为了方便于后面的链表的删除在这里我们传的仍然为二级指针但是传一级指针之所以传二级指针是为了保证与前面的传二级指针的一致性应注意的几点返回值应为那个节点的地址查找的链表不能为空传进去的二级指针也不可以为空SLTNode*SLTFind(SLTNode**phead,SLTDataType x){assert(phead*phead);SLTNode*pcur*phead;while(pcur){if(pcur-datax)//通过x去找到节点{returnpcur;}pcurpcur-next;}returnNULL;//程序走到这里说明没有找到}6.7链表指定位置的删除这里进行删除要传入的是上面查找返回的*SLTNode的节点的地址然后利用while循环进行查找这个结点应注意几点再定义一个指针找到要删除结点的前一个结点传进去的二级指针和链表都不能为空删除头结点的时候要另外讨论原因如第一个图最后出了函数要把指向那个空间的指针置为空因为Find方法返回值是一级指针传到Earse也是一级指针具体操作看图二代码如下voidSLTErase(SLTNode**phead,SLTNode*plist){assert(phead*phead);SLTNode*pcur*phead;if(plist*phead)//删除头节点特殊讨论{free(plist);*pheadNULL;return;}while(pcur-next!plist){pcurpcur-next;}pcur-nextplist-next;free(plist);//把空间释放掉}出函数把plist置为空6.8链表的销毁销毁链表要从头节点一直到尾节点依次销毁销毁一个之后再把指针向后移动注意事项出了函数不要忘记把头节点置为空指针传入的二级指针不为空链表不为空不要忘记了把当前节点的下一个节点存起来代码如下voidSLDestory(SLTNode**phead){assert(phead*phead);SLTNode*pcur*phead;while(pcur){SLTNode*plistpcur-next;//把下一个节点保存下来free(pcur);pcurplist;}}不要忘记出了函数把头节点置为空