数据结构学习笔记

发布时间:2016-12-9 21:26:44 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"数据结构学习笔记",主要涉及到数据结构学习笔记方面的内容,对于数据结构学习笔记感兴趣的同学可以参考一下。

 最近在看国嵌唐老师的数据结构视频,觉得还不错,所以就把笔记记录下来 本节知识点: 1.数据之间的逻辑结构:    集合结构:数据元素之间没有特别的关系,仅同属相同集合    线性结构:数据元素之间是一对一的关系    树形结构:数据元素之间存在一对多的层次关系    图形结构:数据元素之间是多对多的关系 2.数据之间的物理结构     顺序存储结构:将数据存储在地址连续的存储单元里     链式存储结构:将数据存储在任意的存储单元里,通过保存地址的方式找到相关的数据元素 3.数据结构是相互之间存在一种或多种特定关系的数据元素的集合 4.程序 = 数据结构 + 算法 5.大O表示法:算法效率严重依赖于操作数量,首先关注操作数的最高次项,操作数的估计可以作为时间和空间复杂度的估算,在没有特殊说明的时候,我们应该分析复杂度的最坏情况 6.常见的复杂度类型: 大小关系: 7.线性表是零个或多个数据元素的集合,之间的元素是有顺序的,个数是有限的,数据类型必须相同。线性表包含两种存储方式,一种是顺序表,另一种链表。 8.对于线性表的使用是这样的:应该是在设计算法的时候,考虑算法中使用的数据,这些数据之间是什么关系的,如果是符合线性表特质的,就选择线性表作为数据结构。 9.顺序表与数组的关系:其实顺序表就是在数组的基础上构建的,本质跟数组是一样的,只是在数组的基础上增加了length长度,capacity容量等特性,然后补充了一些列,增、删、改、查的功能。 10. 我觉得链表比顺序表最大的优势,就在于链表的删除和插入要比顺序表简单的多,而且当线性表长度很大的时候很难开辟出整段的连续空间!!!最重要的是顺序表在创建的时候长度就固定了,再也改变不了了,而链表则可以根据情况动态增加,这一点是顺序表无论怎么样都不可能实现的!!!   顺序表的优点是:无需为线性表中的逻辑增加额外的空间,可以快速的通过下标的方式找到表中的合法位置。 11.线性表的常用操作:创建线性表、销毁线性表、清空线性表、将元素插入线性表、将元素从线性表中删除、获取线性表中某个位置的元素、获取线性表的长度 本节代码: 1.本节的代码是一个可以适合各种类型的顺序表,之所以能够适合各种类型,是因为它在顺序表中保存的是元素的地址(其实就是一个指针数组)。 2.代码中的描述顺序表的结构体中的元素介绍:length是顺序表中有元素的个数、capacity是顺序表的容量、node是顺序表的头地址(也是这个指针数组的头地址)、还有一个就是pos,pos是在删除和插入的时候使用的一个参数,它代表的是插入到顺序表位置的下标(数组的下标 是从0开始的 这个很要注意)。顺序表中有length个元素 下标是从0到length-1的。要注意的是 操作顺序表不同功能函数的pos的允许范围是不一样的。 3.本节代码对于函数参数的合法性判断是极其重视的,这个规范是值得学习的。 4.本节代码中对于顺序表的操作函数,凡是外界输入的,和输出到外界的,都是void *类型的,这样就保证了只有在这些操作函数中才能去改变   描述顺序表的结构体里面的值,在其他文件的函数中接受到的都是void *类型,无法直接给这个结构体中的值进行改变,这样的封装,保证了代码的安全性。 5.对于本节代码最值得思考的地方,常见的顺序表是typedef一个A类型,然后在顺序表中定义一个这个A类型的数组和length顺序表元素个数,这个顺序表中是好多个A类型的顺序集合,占用空间的大小是sizeof(A)*capacity。而本节的顺序表中是好多个unsigned int *地址类型的顺序集合,表中只有地址,第一节省了顺序表的空间,第二这样可以变相的保存不同类型的数据,第三它实现了 顺序表(即数据结构) 和 我们打算利用的数据(即元素)的分离。例如:linux内核链表(一个双向循环链表)就是一套单独的链表体制,这个链表用在很多机制上面,它就是变相的存储了好多类型的数据,并且实现了链表和数据的分离。 所以在main.c中  数据要想保存在这个顺序表中  就应该先给这些数据开辟内存    因为顺序表中没有他们呆的地方   顺序表中只能保存他们的地址。 如图: 代码如下: Seqlist.c: [cpp] view plaincopy /************************************************************************************   文件名:Seqlist.c  头文件:Seqlist.h   时间: 2013/08/05   作者: Hao   功能:可以复用 带有增 删 改 查 功能的顺序表  难点:1.顺序表中存放的都是 各种数据的地址        2.void *是用来隔离封装用的 保证顺序表结构体只能被特定的函数改变                                                                                                                                   ************************************************************************************/   #include <stdio.h>   #include <malloc.h>   #include "Seqlist.h"      typedef unsigned int TSeqListNode;//这个顺序表中存放的是 各种数据的地址 所以用unsigned int    typedef struct str_SeqList   {       int length;//顺序已用的长度        int capacity;//顺序表的总容量        TSeqListNode* node;//这个指针是用来在顺序表中游走读取数据用的    }TSeqList;  //定义描述顺序表的结构体       /************************************************************************************   函数名:   Creat_SeqList  函数功能: 创建一个容量为capacity的顺序表   参数:     int capacity 创建顺序表中成员的个数 即顺序表容量  返回值:   void* ret 如果返回NULL 说明创建顺序表失败                       如果返回ret 说明创建顺序表成功  且ret为描述顺序表的结构体   ************************************************************************************/   SeqList* Creat_SeqList(int capacity)   {       TSeqList* ret = NULL;       /*进入函数 第一点是先判断传人参数的合法性*/       if(capacity >= 0)       {           /*给顺序表开辟空间*/           ret=(TSeqList* )malloc(sizeof(TSeqList)+sizeof(TSeqListNode)*capacity);           if(NULL!=ret)//空间开辟成功   给描述顺序表的结构体 赋值            {               ret->capacity=capacity;               ret->length=0;               ret->node=(TSeqListNode* )(ret+1);//把真正顺序表的地址赋给 node            }       }       else       {           ret = NULL;       }        return (SeqList*)(ret);   }       /************************************************************************************   函数名:   Destroy_SeqList  函数功能: 销毁顺序表   free开辟的内存   参数:     void* list 描述顺序表结构体指针  返回值:   void   ************************************************************************************/   void  Destroy_SeqList(SeqList* list)   {       free(list);   }      /************************************************************************************   函数名:  Get_Seqlist_Length  函数功能:获得顺序表 现在的大小  函数参数:void* list 描述顺序表结构体指针  函数返回值:int ret  成功返回length                       失败返回-1   ************************************************************************************/   int Get_Seqlist_Length(SeqList* list)   {       int ret;       TSeqList *Tlist=(TSeqList* )list;       /*函数参数合法性检测*/       if(NULL != Tlist)       {           ret=Tlist->length;       }        else           ret=-1;       return ret;   }      /************************************************************************************  函数名:  Get_Seqlist_Capacity  函数功能:获得顺序表 的容量   函数参数:void* list 描述顺序表结构体指针  函数返回值:int ret  成功返回capacity                        失败返回-1   ************************************************************************************/   int Get_Seqlist_Capacity(SeqList* list)   {       int ret;       TSeqList *Tlist=(TSeqList* )list;       /*函数参数合法性检测*/       if(NULL != Tlist)       {           ret = Tlist->capacity;       }        else           ret=-1;       return ret;   }      /************************************************************************************   函数名:  Clean_Seqlist_Length  函数功能:清空顺序表  其实就是给length=0;   函数参数:void* list 描述顺序表结构体指针  函数返回值:int ret  成功返回0                       失败返回-1   ************************************************************************************/   int Clean_Seqlist_Length(SeqList* list)   {       int ret;       TSeqList *Tlist=(TSeqList* )list;       /*函数参数合法性检测*/       if(NULL != Tlist)       {           Tlist->length=0;           ret=0;       }        else           ret=-1;       return ret;   }      /************************************************************************************  函数名:  Seqlist_Add  函数功能:顺序表中有length个数据  在下标为pos的位置上 插入数据node  所以pos是从0开始的 length是从1开始的   参数:      SeqList* list描述顺序表的结构体地址   SeqListNode* node插入顺序表的数据的地址               int pos插入顺序表的位置   pos的范围是从0(此时在顺序表头部插入)开始  到length(此时就是在顺序尾部插入)              总共是length+1个位置   返回值 :  返回1 说明插入数据成功  返回0 说明插入数据失败  ************************************************************************************/   int Seqlist_Add(SeqList* list, SeqListNode* node ,int pos)   {       /*参数合法性检测*/       TSeqList *Tlist=(TSeqList* )list;       int ret = (NULL != list);       int i;       ret=ret && (pos >= 0);       ret=ret && (Tlist->length+1 <= Tlist->capacity);  //判断再插入一个数据的时候  length有没有超过 capacity        if(1 == ret)       {           if(pos >= Tlist->length)//如果插入的位置pos比 length大的话 默认把length+1赋值给pos            {               pos = Tlist->length;           }           for(i=Tlist->length;i>pos;i--)           {               Tlist->node[i]=Tlist->node[i-1];           }            Tlist->node[i]=(TSeqListNode)node; //把要插入的地址强制类型转换成 unsigned int*            Tlist->length++;       }        return ret;//返回1 说明插入数据成功  返回0 说明插入数据失败    }             /************************************************************************************  函数名:   Get_Node  函数功能:找到顺序表中下标为pos的值    参数:    pos插入顺序表的下标   pos的范围是从0到length-1               SeqList* list描述顺序表的结构体地址  返回值:  void* ret 找到pos为下标的那个值          如果成功返回pos为下标的那个值   如果失败  返回NULL  ************************************************************************************/      SeqListNode* Get_Node(SeqList* list, int pos)   {       TSeqList* Tlist=(TSeqList* )list;       SeqListNode* ret=NULL;       if( (NULL!=Tlist) && (pos>=0) && (pos<Tlist->length) )       {           ret=(SeqListNode* )Tlist->node[pos]; //强制类型转换成void*         }       return ret;   }       /************************************************************************************  函数名:   Del_Node  函数功能:找到顺序表中下标为pos的值  并且删除它   参数:    删除pos为下标的值   pos的范围是从0到length-1               SeqList* list描述顺序表的结构体地址  返回值:  void* ret             如果成功返回pos为下标的那个值   如果失败  返回NULL   ************************************************************************************/   SeqListNode* Del_Node(SeqList* list, int pos)   {       TSeqList* Tlist=(TSeqList* )list;       SeqListNode* ret=NULL;       int i;       if( (NULL!=Tlist) && (pos>=0) && (pos<Tlist->length) )       {           ret=(SeqListNode* )Tlist->node[pos];           for(i=pos+1; i<Tlist->length; i++)           {               Tlist->node[i-1]=Tlist->node[i];           }           Tlist->length--;       }       return ret;   }   Seqlist.h: [cpp] view plaincopy #ifndef __Seqlist__   #define __Seqlist__      typedef void SeqList;  //是用来封装 使顺序表结构体 不被外界改变 只可被Seqlist.c文件中的函数改变                          //因为 这些函数 对外的接口 都是void*     typedef void SeqListNode;//SeqList 是用来表示 顺序表的    SeqListNode是用来表示顺序表 中变量的       SeqList* Creat_SeqList(int capacity);   void  Destroy_SeqList(SeqList* list);   int Get_Seqlist_Length(SeqList* list);   int Get_Seqlist_Capacity(SeqList* list);   int Clean_Seqlist_Length(SeqList* list);   int Seqlist_Add(SeqList* list, SeqListNode* node ,int pos);   SeqListNode* Get_Node(SeqList* list, int pos);   SeqListNode* Del_Node(SeqList* list, int pos);       #endif   main.c: [cpp] view plaincopy #include <stdio.h>   #include <stdlib.h>   #include "Seqlist.h"   int main(int argc, char *argv[])   {       SeqList* My_SeqList = NULL;       int a = 10;       int b = 5;       int c = 3;       int d = 6;       int e = 1;       int *p = NULL;       int i = 0;       My_SeqList = Creat_SeqList(5);       if( NULL != My_SeqList )       {               Seqlist_Add(My_SeqList, &a ,0);               Seqlist_Add(My_SeqList, &b ,0);               Seqlist_Add(My_SeqList, &c ,0);               Seqlist_Add(My_SeqList, &d ,0);               Seqlist_Add(My_SeqList, &e ,0);                              for(i=0; i<Get_Seqlist_Length(My_SeqList); i++)               {                   p=Get_Node(My_SeqList, i);                   printf("%d\n",*p);               }                              Del_Node(My_SeqList, 3);               for(i=0; i<Get_Seqlist_Length(My_SeqList); i++)               {                   p=Get_Node(My_SeqList, i);                   printf("%d\n",*p);               }                      }        Clean_Seqlist_Length(My_SeqList);       Destroy_SeqList(My_SeqList);       return 0;   }   test_main.c: [cpp] view plaincopy #include <stdio.h>   #include <stdlib.h>   #include <malloc.h>   #include "Seqlist.h"      typedef struct student   {       int student_num;       char name[30];       char sex[20];       int age;   }str;   int main()   {       str* str1;       SeqList* slist=NULL;       int i=0;       int age=0;       slist=Creat_SeqList(50);       if(NULL == slist)       {           printf("malloc error!!!\n");           return -1;       }       for(i=0; i<3; i++)       {           put_student(slist, str1);       }              printf("输入你要删除的年龄:\n");       scanf("%d",&age);       printf("\n");       find_student(slist, str1, age);       get_student(slist, str1);              destroy_student(slist, str1);       Clean_Seqlist_Length(slist);       Destroy_SeqList(slist);       return 0;   }      int put_student(SeqList* slist, str* str1)   {        int num;       int ret=(NULL != str1);       if(1 == ret)       {           ret=ret && Seqlist_Add(slist, (str* )malloc(sizeof(str)*1) ,50);           num = Get_Seqlist_Length(slist);           str1 = (str* )Get_Node(slist, num-1);           printf("请输入学生学号:\n");            scanf("%d",&str1->student_num);           printf("请输入学生姓名:\n");           scanf("%s",str1->name);           printf("请输入学生性别:\n");           scanf("%s",str1->sex);           printf("请输入学生年龄:\n");           scanf("%d",&str1->age);           printf("\n");        }              else       {           ret = 0;       }       return ret;   }      int get_student(SeqList* slist, str* str1)   {       int ret=(NULL != str1);       int i=0;       if(1 == ret)       {           for(i=0; i<Get_Seqlist_Length(slist); i++)           {               str1 = (str*)Get_Node(slist, i);               printf("学生学号:%d\n",str1->student_num);                          printf("学生姓名:%s\n",str1->name);                              printf("学生性别:%s\n",str1->sex);                              printf("学生年龄:%d\n",str1->age);           }       }              else       {           ret = 0;       }       return ret;   }      int destroy_student(SeqList* slist, str* str1)   {       int ret=(NULL != str1);       int i=0;       if(1 == ret)       {           for(i=0; i<Get_Seqlist_Length(slist); i++)           {               str1 = (str*)Get_Node(slist, i);               free(str1);           }       }              else       {           ret = 0;       }       return ret;   }      int find_student(SeqList* slist, str* str1, int age)   {       int ret=(NULL != str1);       int i=0;       int num=0;       if(1 == ret)       {           num=Get_Seqlist_Length(slist);           for(i=0; i<num; i++)           {               str1 = (str*)Get_Node(slist, i);               if(str1->age == age)               {                   Del_Node(slist, i);                   num=Get_Seqlist_Length(slist);                   i--;               }           }       }              else       {           ret = 0;       }       return ret;   }   test_main.c: [cpp] view plaincopy #include <stdio.h>   #include <stdlib.h>   #include <malloc.h>   #include "Seqlist.h"      typedef struct student   {       int student_num;       char name[30];       char sex[20];       int age;   }str;   int main()   {       str* str1;       SeqList* slist=NULL;       int i=0;       int age=0;       slist=Creat_SeqList(50);       if(NULL == slist)       {           printf("malloc error!!!\n");           return -1;       }       for(i=0; i<3; i++)       {           put_student(slist, str1);       }              printf("输入你要删除的年龄:\n");       scanf("%d",&age);       printf("\n");       find_student(slist, str1, age);       get_student(slist, str1);              destroy_student(slist, str1);       Clean_Seqlist_Length(slist);       Destroy_SeqList(slist);       return 0;   }      int put_student(SeqList* slist, str* str1)   {        int num;       int ret=(NULL != str1);       if(1 == ret)       {           ret=ret && Seqlist_Add(slist, (str* )malloc(sizeof(str)*1) ,50);           num = Get_Seqlist_Length(slist);           str1 = (str* )Get_Node(slist, num-1);           printf("请输入学生学号:\n");            scanf("%d",&str1->student_num);           printf("请输入学生姓名:\n");           scanf("%s",str1->name);           printf("请输入学生性别:\n");           scanf("%s",str1->sex);           printf("请输入学生年龄:\n");           scanf("%d",&str1->age);           printf("\n");        }              else       {           ret = 0;       }       return ret;   }      int get_student(SeqList* slist, str* str1)   {       int ret=(NULL != str1);       int i=0;       if(1 == ret)       {           for(i=0; i<Get_Seqlist_Length(slist); i++)           {               str1 = (str*)Get_Node(slist, i);               printf("学生学号:%d\n",str1->student_num);                          printf("学生姓名:%s\n",str1->name);                              printf("学生性别:%s\n",str1->sex);                              printf("学生年龄:%d\n",str1->age);           }       }              else       {           ret = 0;       }       return ret;   }      int destroy_student(SeqList* slist, str* str1)   {       int ret=(NULL != str1);       int i=0;       if(1 == ret)       {           for(i=0; i<Get_Seqlist_Length(slist); i++)           {               str1 = (str*)Get_Node(slist, i);               free(str1);           }       }              else       {           ret = 0;       }       return ret;   }      int find_student(SeqList* slist, str* str1, int age)   {       int ret=(NULL != str1);       int i=0;       int num=0;       if(1 == ret)       {           num=Get_Seqlist_Length(slist);           for(i=0; i<num; i++)           {               str1 = (str*)Get_Node(slist, i);               if(str1->age == age)               {                   Del_Node(slist, i);                   num=Get_Seqlist_Length(slist);                   i--;               }           }       }              else       {           ret = 0;       }       return ret;   }   线性表有两种:一种是顺序存储的叫顺序表,上节已经说过了,另一种是链式存储的叫链表,本节说的是单链表,即单向链表(每个节点中只包含一个指针域)。 本节知识点: 1.链表的好处:对于动态链表,可以对未知数据量的数据进行存储。插入和删除比顺序表方便的多,不用大量移动。    链表的缺点:除了数据信息,还需对额外的链表信息进行分配内存,占用了额外的空间。访问指定数据的元素需要顺序访问之前的元素。 2.链表的基本概念:    链表头(表头节点):链表中的第一个节点,包含指向第一个数据元素的指针以及链表自身的一些信息(即链表长度length)    数据节点:链表中的代表数据元素的节点,包含指向下一个数据元素的指针和数据元素的信息    尾节点:链表中的最后一个数据节点,其下一元素指针为空,表示无后继 3.对于本节的可复用单链表的设计想法是这样的:    a. 可复用的顺序表中保存的是各个数据的地址,所以我最初想到的是在链表元素中也保存各个数据的地址:                                           使用这样的结构,add是链表中保存的数据,其实就是想复用保存的各种类型的地址,add是一个unsigned int型,用来保存各种数据类型的地址,next是链表结构,用来指向链表元素的下一个链表元素的。      b.但是这样的结构有一个问题,就是从使用的总空间(链表结构的空间+add中保存数据的空间)角度来看,add就是一个浪费空间的变量。因为在add中保存地址,为什么不强制类型成next的类型(此时next应该是链表第一个结构的类型),直接使用这个地址把各种你想要存储的结构赋值给next,这样存储的各个结构就变成了,如图。           c.但是把所有的类型都转换成链表第一个元素的指针类型 再赋值给next 显得程序很不规整,所以最好直接给链表一个结构,把这些结构类型都统一强制类型转换成这个链表的类型,如下:      [cpp] view plaincopy typedef struct Str_LinkList LinkListNode;  //这个结构体是链表的真身    struct Str_LinkList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型    {                     //转换成(LinkListNode* )的时候  其实就是要开始对每个元素中的 LinkListNode进行赋值了        LinkListNode* next;   };        把什么链表头啊,链表元素啊,想要连接进入这个链表的各种结构都强制类型成 LinkListNode*   但是要保证每个结构中都有LinkListNode* next 成员。      d.最后一点,就有点接受不了,也是为了代码的整洁,提高可读性,使链表结构都规整到LinkListNode这个结构中去,便于对链表进行管理,比如说双向链表的前驱和后继。把每个类型中的LinkListNode* next 成员  变成LinkListNode node。这里面有一个很好的c语言技巧,就是这个LinkListNode node必须要放在每个结构中(如 str)的第一个元素位置,即node的地址就是结构体str的地址,因为只有这样了,在把str强制类型转换成 n=(LinkListNode* )str的时候,访问n->next才是访问str.node->next的值,因为两者地址相同,切记一定要放到第一个元素的位置!!! 4.对于链表这个数据结构,一定要注意一个问题,也是这节我犯的一个很难发现的错误:    就是已经在链表中的元素,千万不要再一次往链表中进行插入,因为这样会导致从它插入的地方开始链表的后继就开始混乱了,把整个链表完全弄乱,出现你想不到的问题。 本节代码: 本节实现的是一个可以复用的单链表: LinkList.c: [cpp] view plaincopy /*******************************************************************************************************  文件名:LinkList.c  头文件:LinkList.h   时间: 2013/08/07  作者: Hao  功能:  可以复用 带有增 删 改 查 功能的单链表  难道: 1.typedef struct Str_LinkList LinkListNode;  //这个结构体是链表的真身           struct Str_LinkList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型           {                     //转换成(LinkListNode* )的时候  其实就是要开始对每个元素中的 LinkListNode进行赋值了               LinkListNode* next;          };           这个链表结构在链表元素中起到的作用 是本节的难点           2.切记一个问题  就是已经是链表中元素的 千万不要再往链表中添加了 否则链表一定出现无穷的错误           3.对于pos值的问题  add、get、del三个函数中 的链表都是 从1开始的到length  0是链表头                             在add函数中pos为0的时候是和pos为1的情况是一样的  都是头插法  0~~~~~无穷大                             在get函数中pos为0的时候是获得链表头 地址      0~~~~~length                             在del函数中pos为0的时候是无效的 del失败       1~~~~~length   *******************************************************************************************************/   #include <stdio.h>   #include <stdlib.h>   #include <malloc.h>   #include "LinkList.h"      typedef struct str_list_head  //这个是链表头 其实也可以当作一个没有前驱的 链表元素 元素的内容是链表长度    {       //LinkListNode* next;       LinkListNode head; //这个参数要特别重视 每一个链表元素结构的第一个参数一定是 LinkListNode                          //因为在寻找链表元素后继的时候 其实就是将链表元素强制类型转换成 LinkListNode*  然后给next进行赋值 其实就是给 LinkListNode变量赋值        int length; //链表长度    }list_head;      /*******************************************************************************************************  函数名: Creat_LinkListHead  函数功能:创建一个链表的链表头 并给链表头分配空间  参数: void  返回值:ret 成功返回链表头地址  失败返回NULL   *******************************************************************************************************/   LinkList* Creat_LinkListHead(void)   {       list_head* ret = NULL;       ret = (list_head* )malloc( sizeof(list_head)*1 );       if(NULL != ret) //malloc分配成功        {           ret -> length = 0;           //ret -> next = NULL;           ret -> head.next = NULL;       }       return (LinkList* )ret;    }      /*******************************************************************************************************  函数名:Destroy_LinkListHead  函数功能:释放一个链表头指针   参数:LinkList* head 链表头指针   返回值: ret 释放成功返回1  释放失败返回0   *******************************************************************************************************/   int Destroy_LinkListHead(LinkList* head)   {       int ret = 0;        list_head* lhead = (list_head* )head;       if( NULL != lhead )       {           free(lhead);           ret = 1;       }       return ret;   }      /*******************************************************************************************************  函数名:Get_Length  函数功能:获得链表的长度   参数: LinkList* head 链表头指针   返回值: ret 成功返回链表长度  失败返回0   *******************************************************************************************************/   int Get_Length(LinkList* head)    {       int ret = 0;       list_head* lhead = (list_head* )head;       if( NULL != lhead )       {           ret = lhead -> length;       }          return ret;   }      /*******************************************************************************************************  函数名:Clean_LinkListHead  函数功能:   清空链表   参数: LinkList* head 链表头指针   返回值:ret 成功返回1 失败返回0   *******************************************************************************************************/   int Clean_LinkListHead(LinkList* head)    {       int ret = 0;       list_head* lhead = (list_head* )head;       if( NULL != lhead )       {           lhead -> length = 0;           //lhead -> next = NULL;           lhead -> head.next = NULL;           ret = 1;       }          return ret;   }      /*******************************************************************************************************  函数名:Add_LinkList  函数功能:往链表里面添加一个链表元素 如果pos的值是0(就是链表头)和1(链表的第一元素 链表元素个数是从1开始算的)都是头插法            pos的值大于链表长度是尾插法  这里面pos值得注意的是 i=1 pos为a的时候 是把链表元素插入第a个元素的位置             当i=0 pos为a的时候 是把链表元素插入 第a个元素位置的后面    切忌:这里面0位置是链表头指针 从1开始是链表元素   参数:   LinkList* head链表头指针    LinkListNode* Node插入元素的指针(被强制类型转化成LinkListNode*)  int pos 插入位置            pos的有效值范围是 从0到无穷大    返回值: ret 插入成功返回1  插入失败返回0   *******************************************************************************************************/   int Add_LinkList(LinkList* head, LinkListNode* Node, int pos)   {       int ret = 0;       int i = 0;       list_head* lhead = (list_head* )head;       LinkListNode* node = (LinkListNode* )head;       ret=( NULL != node) && ( NULL != Node) && (pos >= 0);       if(1 == ret)       {           for(i=1; ( (i<pos) && (node->next != NULL) ); i++)           {               node = node->next;           }           Node -> next = node -> next;           node -> next = Node;                      lhead -> length++;        }       return ret;   }      /*******************************************************************************************************  函数名:Get_LinkListNode  函数功能:获得链表中第pos个元素位置的链表元素 链表是从1开始的  0是链表头   pos为0的时候表示get链表头   参数: LinkList* head链表头指针    int pos获得链表元素的位置  pos的有效取值范围是 1 到  length  0是链表头   返回值: LinkListNode*类型 第pos个链表元素的地址   *******************************************************************************************************/   LinkListNode* Get_LinkListNode(LinkList* head, int pos)   {       int ret = 0;       int i = 0;       list_head* lhead = (list_head* )head;       ret=( NULL != lhead) && (pos >= 0) && (pos <= lhead->length);       if(1 == ret)       {           LinkListNode* node = (LinkListNode* )head;           for(i=0; i<pos; i++) //执行 pos次   得到的是第pos位置的node            {               node = node->next;           }              return (LinkListNode*)node;       }       return NULL;   }      /*******************************************************************************************************  函数名:Del_LinkListNode  函数功能:删除链表中第pos位置的链表元素   参数: LinkList* head链表头指针    int pos删除链表元素的位置  pos是删除的链表元素的位置 跟get和add中的         pos是配套的  有效取值范围依然是 1到 length  在这个函数里面由于不能删除链表头 所以pos为0的时候无效   返回值: LinkListNode* ret这个返回值很重要 因为这个删除仅仅是把链表元素踢出了链表 并没有free开辟的内存           应该通过这个返回的地址free  释放内存           删除成功返回 删除链表元素的地址   删除失败返回 NULL   *******************************************************************************************************/   LinkListNode* Del_LinkListNode(LinkList* head, int pos)   {       LinkListNode* ret = NULL;       int i = 0;       list_head* lhead = (list_head* )head;       if(( NULL != lhead) && (pos > 0) && (pos <= lhead->length))       {           LinkListNode* node = (LinkListNode* )head;           for(i=1; i<pos; i++)//执行 pos次   得到的是第pos位置的node  这个方法行不通            {                   //因为要想删除第pos位置的node 应该先找到它上一个链表元素                node = node->next; //所以这里面i=1 比get函数少执行了一次  得到第pos-1位置的node            }           ret = node->next;           node->next = ret->next;                         lhead->length--;       }       return (LinkListNode*)ret;   }   LinkList.h: [cpp] view plaincopy #ifndef __LinkList_H__   #define __LinkList_H__      typedef void LinkList;  //这个是为了 封装方便    typedef struct Str_LinkList LinkListNode;  //这个结构体是链表的真身    struct Str_LinkList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型    {                     //转换成(LinkListNode* )的时候  其实就是要开始对每个元素中的 LinkListNode进行赋值了        LinkListNode* next;   };      LinkList* Creat_LinkListHead(void);      int Destroy_LinkListHead(LinkList* head);      int Get_Length(LinkList* head);      int Clean_LinkListHead(LinkList* head);      int Add_LinkList(LinkList* head, LinkListNode* Node, int pos);      LinkListNode* Get_LinkListNode(LinkList* head, int pos);      LinkListNode* Del_LinkListNode(LinkList* head, int pos);        #endif   main.c: [cpp] view plaincopy #include <stdio.h>   #include <stdlib.h>   #include <malloc.h>   #include <string.h>   #include "LinkList.h"      typedef struct student   {       //LinkListNode* next;       LinkListNode node;       int num;       char name[30];   }str;   int main(int argc, char *argv[])    {       str str1,str2,str3,str4,str5,str6,*strp;       int i=0;       LinkList* list_head;       list_head = Creat_LinkListHead();              str1.num = 1;       strcpy(str1.name,"haohao");              str2.num = 2;       strcpy(str2.name,"ququ");              str3.num = 3;       strcpy(str3.name,"popo");              str4.num = 4;       strcpy(str4.name,"wowo");              str5.num = 5;       strcpy(str5.name,"tiantian");          str6.num = 6;       strcpy(str6.name,"cheche");              Add_LinkList(list_head, (LinkListNode*)&str1, 0);       Add_LinkList(list_head, (LinkListNode*)&str2, 0);       Add_LinkList(list_head, (LinkListNode*)&str3, 0);       Add_LinkList(list_head, (LinkListNode*)&str4, 0);       Add_LinkList(list_head, (LinkListNode*)&str5, 0);       strp = (str*)Del_LinkListNode(list_head, 5);       printf("%d\n",strp->num);       printf("%s\n",strp->name);       printf("\n");       for(i=1; i<= Get_Length(list_head); i++)       {           strp = (str*)Get_LinkListNode(list_head, i);           printf("%d\n",strp->num);           printf("%s\n",strp->name);       }        printf("\n");       Add_LinkList(list_head, (LinkListNode*)&str6, 3);          for(i=1; i<= Get_Length(list_head); i++)       {           strp = (str*)Get_LinkListNode(list_head, i);           printf("%d\n",strp->num);           printf("%s\n",strp->name);       }                          Clean_LinkListHead(list_head);       Destroy_LinkListHead(list_head);       return 0;   }   课后练习: 1.对于上节顺序表中的unsigned  int型保存数据地址,可不可用void*    这个问题已经得到了唐老师的解答,其实使用void* 最好了,因为使用unsigned int  仅仅能够在32位机上面运行成功,在64位机上运行就会出错的!!! 2.对于有头链表和无头链表的区别 所谓有头链表,就是有头结点的链表,头结点是一个链表元素,但不存放数据。无头链表就是没有头结点的链表。相比之下有头链表比无头链表,方便很多,优点也很多。 无头链表就是在谭浩强老师的c语言书中的那个链表。就是没有头结点,只有一个指针指向链表第一个元素。这个指针被叫做链表头。      个人建议使用有头链表!!! 3.对顺序表和单链表添加一个反转操作    a.对于顺序表 其实就是在不断的交换    b.对于链表  我觉得还是使用双向链表吧,解决这个问题就方便了~~~ 问题描述:假设有一个没有头指针的单链表。一个指针指向此单链表中间的一个节点(不是第一个,也不是最后一个节点),请将该节点从单链表中删除。 一般链表的删除需要顺着头结点向下找到当前待删节点的前驱节点,然后让前驱节点指向后驱节点就行了。这里,没有头结点,就没办法找到前驱结点。但我们可以采用“狸猫换太子”的做法。我们把当前结点“看成”是前驱结点,把后续节点当做待删结点删除(删除之前,记下后续结点的值),只需要让当前结点指向后驱结点的后驱结点。最后把后续结点值赋给当前结点的值。 [cpp] view plaincopy #include<stdio.h>   #include<stdlib.h>   #include<assert.h>      typedef struct node{       int data;       node *next;   }Node;      void printlist(Node *head_ptr);   void delete_random_node(Node *current);      int main(){       Node n1, n2, n3;       n1.data = 10;       n1.next = &n2;       n2.data = 20;       n2.next = &n3;       n3.data = 30;       n3.next = NULL;       printf("Before deleting\n");       printlist(&n1);       delete_random_node(&n2);       printf("\nAfter deleting\n");       printlist(&n1);       return 0;   }      void printlist(Node *head_ptr){         Node *ptr = head_ptr;        while(ptr != NULL){             printf("%d    ", ptr->data);             ptr = ptr->next;         }         printf("\n");     }        void delete_random_node(Node *current){       assert(current != NULL);       Node *next = current->next;       if(next != NULL){           current->next = next->next;           current->data = next->data;       }   }   扩展问题 编写一个函数,给定一个链表的头指针,要求只遍历一次,将单链表中的元素顺序反转过来。 [cpp] view plaincopy #include<stdio.h>   #include<stdlib.h>      typedef struct node{       int data;       node *next;   }Node;      Node *reverse_linklist(Node *head);   void printlist(Node *ptr);      int main(){       Node n1, n2, n3;       Node *head;       head = (Node *)malloc(sizeof(Node));       head->next = &n1;       n1.data = 10;       n1.next = &n2;       n2.data = 20;       n2.next = &n3;       n3.data = 30;       n3.next = NULL;          printf("Before reversing\n");       printlist(head);       printf("\nAftering reversing\n");       printlist(reverse_linklist(head));       return 0;   }      void printlist(Node *head_ptr){       Node *ptr = head_ptr->next;       while(ptr != NULL){           printf("%d    ", ptr->data);           ptr = ptr->next;       }       printf("\n");   }      Node *reverse_linklist(Node *head){       Node *p = head->next;       Node *e = NULL;       Node *q;       while(p->next != NULL){           q = p->next;           p->next = e;           e = p;           p = q;       }       p->next = e;       head->next = p;       return head;   }   本节知识点: 1.静态链表到底是什么:链表就是链式存储的线性表,但是它分为动态和静态两种,所谓动态就是长度不固定,可以根据情况自行扩展大小的,静态链表就是长度大小固定的,链式存储的线性表。 2.本节的静态链表和顺序表很像(其实和数组也很像),准确的来说就是利用顺序表实现的,只是这个顺序表,不是顺序排列的,是通过一个next变量,连接到下一个变量的。 如图: 3.唐老师说静态链表是在一些没有指针的语言中使用的,来实现链表的功能,但是我觉得链表的最大优势就在于它的伸缩,用多少开辟多少。但是静态链表就恰恰失去了这个优势。依我看,学习静态链表的目的是学习它这种类似内存管理的算法思想。 4.静态链表中值得学习的思想:就是在初始化链表的时候,把所以空间都标记成为可用-1,每次插入数据的时候,都在标记为可用的空间内挑取,再把-1改成next。当删除变量的时候在把next改成-1,标记为空间可用。 5.其实仔细想想 看看,静态链表只是一个思想,为什么这么说,首先在获取index的时候,你是顺序获取的,这导致你的next也是连续的,所以他其实就变成了一个顺序表。在这里我想到了一个唐老师的问题,为什么node[0]就可以当作头节点,还要再定义一个head变量。唐老师的解答是:顺序获得index的时候每次都要遍历太浪费时间了,所以最好应该在同一块空间再定义一个链表,来保存这些空闲空间,然后这样就需要两个链表的头节点了,所以需要一个head。然后让node[0]一会是空闲链表的链表头节点,一会是真实保存数据的链表的头节点。当插入的时候,只需要在那个空闲链表取空间就可以了,提高了算法的效率。 PS1:对于node[0]我真的想说,其实让node[0]当作头节点的使用真的很方便,比head方便很多,仅仅是个人体会。 PS2:对于两个链表的那个算法,我觉得如果还是顺序在链表中获得index,依然没有解决这个index是有顺序的且顺序是固定的问题。这里的顺序是指的是那个空闲链表的顺序。所以说这仅仅是一个思想。 6.本节最重要的知识点也是最大的难点:对于柔性数组的描述。 对于柔性数组的结构如下: [cpp] view plaincopy typedef struct _tag_StaticList  //因为静态链表是基于顺序表改写的  这个就是顺序表中描述顺序表的那个结构    {       int capacity;           //静态链表的大小是固定的  这是链表的容量        StaticListNode head;    //链表  头节点         StaticListNode node[];  //利用柔性数组 创建静态链表    }StaticList;   然后:给柔性数组开辟空间 [cpp] view plaincopy StaticList* ret = NULL;    ret = (StaticList*)malloc( sizeof(StaticList)*1 + sizeof(StaticListNode)*(capacity+1) );   其实柔性数组就是以数组的方式访问内存。对于 StaticList  ret这个结构体的大小是不包括StaticLIstNode node[]的,StaticLIstNode node[]是没有大小的,StaticLIstNode node[0]访问的内存是StaticList  ret这个结构体后面的第一个内存,StaticLIstNode node[1]访问的内存是StaticList  ret这个结构体后面的第二个内存等等。 PS:StaticLIstNode node[]这个结构到底是个什么结构,不好说,不是数组,也不是指针。就把它当作为了柔性数组而产生的结构吧!!! 本节代码: StaticList.c: [cpp] view plaincopy /**************************************************************************************************************   文件名:StaticList.c  头文件:StaticList.h  时间:2013/08/15  作者:Hao  功能:可以复用的 带有增 删  改 查 的静态链表   **************************************************************************************************************/   #include <stdio.h>   #include <malloc.h>   #include <string.h>   #include "StaticList.h"      #define AVAILABLE -1      typedef struct _tag_StaticListNode  //这个是静态链表的结构   用来保存链表元素的    {       unsigned int data;   //这个是为了复用  保存数据地址的        int next;            //这个是用来保存下一个节点位置的    }StaticListNode;               typedef struct _tag_StaticList  //因为静态链表是基于顺序表改写的  这个就是顺序表中描述顺序表的那个结构    {       int capacity;           //静态链表的大小是固定的  这是链表的容量        StaticListNode head;    //链表  头节点         StaticListNode node[];  //利用柔性数组 创建静态链表    }StaticList;      /**************************************************************************************************************   函数名 : Creat_StaticList  函数功能:创建一个静态链表使用的空间  具体数据: StaticList这个结构是描述静态链表的结构    StaticListNode这个结构才是真正的静态链表的元素             每一个静态链表的元素都是由两个部分组成的 一个是数据data(即保存的地址)  另一个是下一个链表             元素的位置next                 对于StaticList这个结构中的数据是capacity是静态链表的容量 head是链表的头节点             node[0]也是头节点 node[]是柔性数据  这里面保存的才是真的链表内容   参数: int capacity  链表容量  正确范围 0到无穷大  当为0的时候链表中仅仅有一个node[0]头节点   返回值:StaticList* ret 返回描述静态链表的结构 StaticList的地址   (SList*这个是为了封装)  **************************************************************************************************************/    SList* Creat_StaticList(int capacity)   {       int i=0;        StaticList* ret = NULL;        if( capacity >= 0) //参数合法性检测  一定要大于等于0   如果capacity为0 是给node[0]开辟空间  node[0]是链表头节点        {           ret = (StaticList*)malloc( sizeof(StaticList)*1 + sizeof(StaticListNode)*(capacity+1) );       }       if(NULL != ret)  //判断malloc是否成功 内存是否分配成功        {           ret -> capacity = capacity; //静态链表的容量            ret -> head.data = 0;   //头节点中保存的 链表长度   初始化为0            ret -> head.next = 0;   //头节点中保存的  链表下一个节点的位置  初始化为NULL           for(i=1; i<=capacity; i++)  //把链表中从node[1]开始 到node[capacity]中的next都标志为可用            {               ret -> node[i].next =  AVAILABLE; //这个在插入函数的时候有用            }                   }       return (SList*)ret;           }       /**************************************************************************************************************   函数名:Destroy_StaticList  函数功能:释放StaticList结构开辟的内存   参数:StaticList* Static_List  (SList* Static_List这个是为了 封装)  返回值:void   **************************************************************************************************************/    void Destroy_StaticList(SList* Static_List)   {       free(Static_List); //释放静态链表创建的内存空间    }      /**************************************************************************************************************  函数名: Get_Lenth  函数功能:返回静态链表长度  参数:StaticList* Static_List    (SList* List为了封装)  返回值:成功 int Static_List -> head.data 静态链表使用的长度   失败返回 0   **************************************************************************************************************/   int Get_Lenth(SList* List)    {       StaticList* Static_List = (StaticList*)List;       int ret = 0;       if(NULL != Static_List)       {           ret = Static_List -> head.data; //静态链表的长度        }       return ret;   }      /**************************************************************************************************************  函数名:Get_Capacity  函数功能:返回静态链表的容量  参数:StaticList* Static_List  (SList* List为了封装)  返回值:成功返回 int Static_List -> capacity 静态链表的容量  失败返回 0   **************************************************************************************************************/   int Get_Capacity(SList* List)    {       StaticList* Static_List = (StaticList*)List;       int ret = 0;       if(NULL != Static_List)       {           ret = Static_List -> capacity; //静态链表的容量        }       return ret;   }      /**************************************************************************************************************  函数名: Clear_StaticList  函数功能:重置静态链表  参数:StaticList* Static_List  (SList* List为了封装)  返回值:成功返回1  失败返回0   **************************************************************************************************************/   int Clear_StaticList(SList* List)   {       StaticList* Static_List = (StaticList*)List;       int i = 0;       int ret = 0;       if(NULL != Static_List)       {           Static_List -> head.data = 0;           Static_List -> head.next = 0;           for(i=1; i<=Static_List -> capacity; i++)             {               Static_List -> node[i].next =  AVAILABLE;             }            ret = 1;       }        return ret;   }      /**************************************************************************************************************  函数名: Add_StaticList  函数功能: 在链表中的pos位置处插入一个链表元素   pos的规则跟上节单链表的规则一样 0和1为头插法  无穷大为尾插法             node[0]是链表头节点  其实是head的一个中间变量  使用node[0]真的很方便 此处记得更新头节点  参数:SList* List 要插入的链表地址    SListNode* Node要插入的数据地址   int pos插入的位置   返回值:返回1说明插入成功  返回0说明插入失败   **************************************************************************************************************/   int Add_StaticList(SList* List, SListNode* Node, int pos)   {       StaticList* Static_List = (StaticList*)List;       StaticListNode*  node =  (StaticListNode*)Node;       int ret = 0;       int num = 0;       int index = 0;       int i = 0;       ret = (NULL != Static_List)&&(NULL != node);       ret = ret&&(Static_List->head.data+1 <= Static_List->capacity)&&(pos >= 0);               if(ret)  //参数合法性检测成功        {           for(i=1; i<=Static_List->capacity; i++) //轮询获得可用的位置index            {               if(-1 == Static_List->node[i].next)               {                   index = i;                   break;               }           }           Static_List->node[index].data = (unsigned int)node; //保存链表中的数据            Static_List->node[0] = Static_List->head;  //此时node[0]变成了链表头节点               for(i=1; (i < pos)&&(0 != Static_List->node[num].next); i++)           {               num =  Static_List->node[num].next;           }           Static_List->node[index].next = Static_List->node[num].next;           Static_List->node[num].next = index;                      Static_List->node[0].data++;           Static_List->head = Static_List->node[0];//更新链表头节点        }       return ret;    }          /**************************************************************************************************************  函数名: Get_StaticListNode  函数功能:获得pos位置处的数据  pos的规则跟单向链表一样            范围是 0  到   head->data  0是头节点  参数:  SList* List 要插入的链表地址     int pos插入的位置   返回值: 成功返回pos位置处的数据  失败返回NULL   **************************************************************************************************************/   SListNode* Get_StaticListNode(SList* List, int pos)   {       SListNode* ret = NULL;       int i = 0;       int num = 0;       StaticList* Static_List = (StaticList*)List;        if( (NULL != Static_List) && (pos <= Static_List->head.data) && (pos >= 0) )       {           Static_List->node[0] = Static_List->head;            for(i=0; i<pos; i++)           {               num = Static_List->node[num].next;           }           ret = (SListNode*)Static_List->node[num].data;        }       return ret;   }          /**************************************************************************************************************  函数名: Del_StaticListNode  函数功能:删除pos位置处的数据  pos的规则跟单向链表一样            范围是 1  到   head->data  0是头节点 不能删除  参数: SList* List 要插入的链表地址     int pos删除的位置  返回值:成功返回 pos位置的数据 (目的在于:因为此数据一般是数据的地址  便于释放内存)    失败返回NULL   **************************************************************************************************************/   SListNode* Del_StaticListNode(SList* List, int pos)   {       SListNode* ret = NULL;       int i = 0;       int num = 0;       int temp = 0;        StaticList* Static_List = (StaticList*)List;        if( (NULL != Static_List) && (pos <= Static_List->head.data) && (pos > 0) )       {           Static_List->node[0] = Static_List->head;            for(i=1; i<pos; i++)//得找到要删除的那个节点的上一个            {               num = Static_List->node[num].next;           }           temp = Static_List->node[num].next;           Static_List->node[num].next = Static_List->node[temp].next;                      Static_List->node[0].data--;           Static_List->head = Static_List->node[0]; //更新链表头节点                       Static_List->node[temp].next = AVAILABLE; //把删除的节点标志为可用节点                       ret = (SListNode*)Static_List->node[temp].data;         }       return ret;          }   StaticList.h: [cpp] view plaincopy #ifndef __STATICLIST_H__   #define __STATICLIST_H__       typedef void SList;   typedef void SListNode;      SList* Creat_StaticList(int capacity);   void Destroy_StaticList(SList* Static_List);   int Get_Lenth(SList* List);   int Get_Capacity(SList* List);   int Clear_StaticList(SList* List);   int Add_StaticList(SList* List, SListNode* Node, int pos);   SListNode* Get_StaticListNode(SList* List, int pos);   SListNode* Del_StaticListNode(SList* List, int pos);      #endif   main.c: [cpp] view plaincopy #include <stdio.h>   #include <malloc.h>   #include <string.h>   #include "StaticList.h"      int main()   {       SList* list = Creat_StaticList(10);       int *f = 0;       int i = 0;       int a = 1;       int b = 2;       int c = 3;       int d = 4;       int e = 5;              Add_StaticList(list, &a, 0);       Add_StaticList(list, &b, 0);       Add_StaticList(list, &c, 0);       Add_StaticList(list, &d, 0);              for(i=1; i<=Get_Lenth(list); i++)       {           f=(int* )Get_StaticListNode(list, i);           printf("%d\n",*f);       }               Add_StaticList(list, &e, 2);       printf("\n");       for(i=1; i<=Get_Lenth(list); i++)       {           f=(int* )Get_StaticListNode(list, i);           printf("%d\n",*f);       }               printf("\n");       f=(int* )Del_StaticListNode(list, 4);       printf("del %d\n",*f);       printf("\n");       for(i=1; i<=Get_Lenth(list); i++)       {           f=(int* )Get_StaticListNode(list, i);           printf("%d\n",*f);       }        Destroy_StaticList(list);       return 0;   }   本节知识点: 1.为什么选择循环链表:因为有很多生活中结构是循环的,是单链表解决不了的,比如星期、月份、24小时,对于这些循环的数据,循环链表就体现出它的优势了。 2.循环链表的结构: 循环链表就是从头结点后面开始,尾节点的next不再是NULL了,而是头结点后面的第一个链表元素,如上图。 3.如何创建一个循环链表: 步骤一: 步骤二: 无论是头插法,还是尾插法都没有关系,都可以创建完成这个循环链表。 4.如何将一个单向链表改写成一个循环链表:    第一步 (改写插入函数):    a.把插入位置pos的允许范围改成0~~~无穷大 [cpp] view plaincopy ret=( NULL != node) && ( NULL != Node) && (pos >= 0);      b.把两种方式的头插法情况加入程序,第一种是pos值为0和1的情况,如图:        这种情况分为两部:先把node插入到head和第一个元素直接,然后再把链表尾指向node元素(node表示插入元素)。    代码如下: [cpp] view plaincopy if(node == (CircleListNode* )head)    {       Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length); //获得链表最后一个元素        Last->next = Node; //把头插法的数据连接到 链表的最后一个元素的后面    }      头插法的第二种情况,是循环链表,循环了一圈回来了,与第一种不同的是此时插入的相对位置和第一种的相对位置不一样。(其实这种方法跟普通插入是一样的)  如图:    第二步  (改写删除函数):    a.也是把pos值的取值范围改成0  到 无穷大,但是同时记得判断length要大于0 ,要保证链表中有数据,不然删什么呀~~~~ [cpp] view plaincopy if(( NULL != lhead) && (pos > 0) && (lhead->length>0))      b.对于删除第一个元素有两种情况 这里是难点:首先要在删除链表元素的 前面 判断是否要删除第一个元素(此时的情况是pos为1的情况),然后删除链表元素,再判断是否是删除第一个元素的第二种情况(链表循环一圈后,到达链表第一个元素,此时元素的前一个链表不再是head头结点了)。如图:  代码如下: [cpp] view plaincopy if(node == (CircleListNode* )head)   {       Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length);   }              ret = node->next;   node->next = ret->next;      /*判断是不是循环了一圈后回来的情况 */   if((first == ret) &&(NULL == Last))   {       Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length);   }   /*判断是否要删除链表中的第一个元素*/   if( Last != NULL )   {       Last->next = ret->next;        lhead->head.next = ret->next;   }   图中红笔的代码是: [cpp] view plaincopy ret = node->next;   node->next = ret->next;      图中蓝笔的代码是: [cpp] view plaincopy if( Last != NULL )   {       Last->next = ret->next;        lhead->head.next = ret->next;   }      c.当length为0的是,即链表长度为0的时候,记得给头结点的next赋值为NULL   第三步 (改写获得链表元素函数)   a.记得把pos给成 0 到 无穷大,然后判断length链表长度是否为0 ,如果为0 就不能获取。 5.游标的引入: 在循环链表中一般可以定义一个游标,对于这样一个封装好的可复用循环链表,定义一个游标是十分方便的。例如:如果想依次获得链表中的每一个元素,利用get函数,太过低效了O(n2),想想利用这样一个游标去遍历的话,复杂度仅仅是O(n)。还有就是在循环链表中,游标可以在链表中进行转圈,例如:可以解决约瑟夫环问题。 6.指定删除链表中某一个元素的函数CircleListNode* CircleList_Del(CircleList* head,CircleListNode* node),其实也不是很高效,获得了当前游标的值的时候,再去调用CircleList_Del函数,这个轮询函数获得了pos,再去调用Del_CircleListNode然后又遍历了一边,把复杂的搞到了O(n2)。其实完全可以在找到pos的时候直接删除掉这个链表元素,这样的复杂度是O(n)。 7.我还觉得获得当前游标得值的函数CircleList_Slider的返回值有些问题,我觉得如果返回的是当前游标的上一个链表元素的值会更好,因为这个是一个单向链表,如果得到了上一个链表元素的值,就可以通过游标实现,删除啊,插入啊等高效的操作了。 本节代码: CricleList.c: [cpp] view plaincopy /*******************************************************************************************************  文件名:CircleList.c  头文件:CircleList.h   时间: 2013/08/17  作者: Hao  功能:  可以复用 带有增 删 改 查 功能的循环链表  难道: 1.typedef struct Str_CircleList CircleListNode;  //这个结构体是链表的真身           struct Str_CircleList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型           {                     //转换成(CircleListNode* )的时候  其实就是要开始对每个元素中的 CircleListNode进行赋值了               CircleListNode* next;          };           这个链表结构在链表元素中起到的作用 是本节的难点           2.切记一个问题  就是已经是链表中元素的 千万不要再往链表中添加了 否则链表一定出现无穷的错误           3.对于pos值的问题  add、get、del三个函数中 的链表都是 从1开始的到length  0是链表头                             在add函数中pos为0的时候是和pos为1的情况是一样的  都是头插法  0~~~~~无穷大                             在get函数中pos为0的时候是获得链表头 地址      0~~~~~length                             在del函数中pos为0的时候是无效的 del失败       1~~~~~length   *******************************************************************************************************/   #include <stdio.h>   #include <stdlib.h>   #include <malloc.h>   #include "CircleList.h"      typedef struct str_list_head  //这个是链表头 其实也可以当作一个没有前驱的 链表元素 元素的内容是链表长度    {       //CircleListNode* next;       CircleListNode head; //这个参数要特别重视 每一个链表元素结构的第一个参数一定是 CircleListNode                          //因为在寻找链表元素后继的时候 其实就是将链表元素强制类型转换成 CircleListNode*  然后给next进行赋值 其实就是给 CircleListNode变量赋值        CircleListNode* slider;        int length; //链表长度    }list_head;      /*******************************************************************************************************  函数名: Creat_CircleListHead  函数功能:创建一个链表的链表头 并给链表头分配空间  参数: void  返回值:ret 成功返回链表头地址  失败返回NULL   *******************************************************************************************************/   CircleList* Creat_CircleListHead(void)   {       list_head* ret = NULL;       ret = (list_head* )malloc( sizeof(list_head)*1 );       if(NULL != ret) //malloc分配成功        {           ret->length = 0;           //ret -> next = NULL;           ret->head.next = NULL;           ret->slider = NULL;       }       return (CircleList* )ret;    }      /*******************************************************************************************************  函数名:Destroy_CircleListHead  函数功能:释放一个链表头指针   参数:CircleList* head 链表头指针   返回值: ret 释放成功返回1  释放失败返回0   *******************************************************************************************************/   int Destroy_CircleListHead(CircleList* head)   {       int ret = 0;        list_head* lhead = (list_head* )head;       if( NULL != lhead )       {           free(lhead);           ret = 1;       }       return ret;   }      /*******************************************************************************************************  函数名:Get_Length  函数功能:获得链表的长度   参数: CircleList* head 链表头指针   返回值: ret 成功返回链表长度  失败返回0   *******************************************************************************************************/   int Get_Length(CircleList* head)    {       int ret = 0;       list_head* lhead = (list_head* )head;       if( NULL != lhead )       {           ret = lhead -> length;       }          return ret;   }      /*******************************************************************************************************  函数名:Clean_CircleListHead  函数功能:   清空链表   参数: CircleList* head 链表头指针   返回值:ret 成功返回1 失败返回0   *******************************************************************************************************/   int Clean_CircleListHead(CircleList* head)    {       int ret = 0;       list_head* lhead = (list_head* )head;       if( NULL != lhead )       {           lhead -> length = 0;           //lhead  -> next = NULL;           lhead -> head.next = NULL;           lhead->slider = NULL;           ret = 1;       }          return ret;   }      /*******************************************************************************************************  函数名:Add_CircleList  函数功能:往链表里面添加一个链表元素 如果pos的值是0(就是链表头)和1(链表的第一元素 链表元素个数是从1开始算的)都是头插法            pos的值大于链表长度是尾插法  这里面pos值得注意的是 i=1 pos为a的时候 是把链表元素插入第a个元素的位置             当i=0 pos为a的时候 是把链表元素插入 第a个元素位置的后面    切忌:这里面0位置是链表头指针 从1开始是链表元素   参数:   CircleList* head链表头指针    CircleListNode* Node插入元素的指针(被强制类型转化成CircleListNode*)  int pos 插入位置            pos的有效值范围是 从0到无穷大    返回值: ret 插入成功返回1  插入失败返回0   *******************************************************************************************************/   int Add_CircleList(CircleList* head, CircleListNode* Node, int pos)   {       int ret = 0;       int i = 0;       list_head* lhead = (list_head* )head;       CircleListNode* node = (CircleListNode* )head;       CircleListNode* Last = NULL;       ret=( NULL != node) && ( NULL != Node) && (pos >= 0);       if(1 == ret)       {           for(i=1; ( (i<pos) && (node->next != NULL) ); i++)           {               node = node->next;           }           Node -> next = node -> next;           node -> next = Node;           if(lhead->length == 0)//第一次插入元素的时候把游标 指向这个元素             {               lhead->slider = Node;           }           lhead -> length++; //这个一定要在后面调用 lhead->length值的前面更新            /*判断是否为头插法  所谓头插法 就是pos为0和1的情况 其实也就是没有进for循环的情况  剩下的无论pos为多少  进入多少次循环都没有头插法*/           if(node == (CircleListNode* )head)            {               Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length); //获得链表最后一个元素                Last->next = Node; //把头插法的数据连接到 链表的最后一个元素的后面            }                  }       return ret;   }      /*******************************************************************************************************  函数名:Get_CircleListNode  函数功能:获得链表中第pos个元素位置的链表元素 链表是从1开始的  0是链表头   pos为0的时候表示get链表头   参数: CircleList* head链表头指针    int pos获得链表元素的位置  pos的有效取值范围是 1 到  length  0是链表头   返回值: CircleListNode*类型 第pos个链表元素的地址   *******************************************************************************************************/   CircleListNode* Get_CircleListNode(CircleList* head, int pos)   {       int ret = 0;       int i = 0;       list_head* lhead = (list_head* )head;       /*本来pos应该是有上限的  但是变成了循环链表pos理论上说就可以无穷大了  但是get函数应该是在链表中有值的情况下才成立的 即(lhead->length>0)*/        ret=( NULL != lhead) && (pos >= 0) && (lhead->length>0);        if(1 == ret)       {           CircleListNode* node = (CircleListNode* )head;           for(i=0; i<pos; i++) //执行 pos次   得到的是第pos位置的node            {               node = node->next;           }              return (CircleListNode*)node;       }       return NULL;   }      /*******************************************************************************************************  函数名:Del_CircleListNode  函数功能:删除链表中第pos位置的链表元素   参数: CircleList* head链表头指针    int pos删除链表元素的位置  pos是删除的链表元素的位置 跟get和add中的         pos是配套的  有效取值范围依然是 1到 length  在这个函数里面由于不能删除链表头 所以pos为0的时候无效   返回值: CircleListNode* ret这个返回值很重要 因为这个删除仅仅是把链表元素踢出了链表 并没有free开辟的内存           应该通过这个返回的地址free  释放内存           删除成功返回 删除链表元素的地址   删除失败返回 NULL   *******************************************************************************************************/   CircleListNode* Del_CircleListNode(CircleList* head, int pos)   {       CircleListNode* ret = NULL;       CircleListNode* Last = NULL;       int i = 0;       list_head* lhead = (list_head* )head;       CircleListNode* first = lhead->head.next;              if(( NULL != lhead) && (pos > 0) && (lhead->length>0))       {           CircleListNode* node = (CircleListNode* )head;           for(i=1; i<pos; i++)//执行 pos次   得到的是第pos位置的node  这个方法行不通            {                   //因为要想删除第pos位置的node 应该先找到它上一个链表元素                node = node->next; //所以这里面i=1 比get函数少执行了一次  得到第pos-1位置的node            }           /*判断是不是 pos为1的 情况删除头节点后面的第一个元素(这个是没有进入for循环的)  跟循环一圈后的情况不一样  */           /*循环一圈的是进入for循环的情况   此时的node不再是head了 而是链表最后一个元素*/            if(node == (CircleListNode* )head)           {               Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length);           }                      ret = node->next;           node->next = ret->next;              /*判断是不是循环了一圈后回来的情况 */           if((first == ret) &&(NULL == Last))           {               Last =(CircleListNode* )Get_CircleListNode(lhead, lhead->length);           }           /*判断是否要删除链表中的第一个元素*/           if( Last != NULL )           {               Last->next = ret->next;                lhead->head.next = ret->next;           }           if( lhead->slider == ret)//如果删除的元素恰恰就是游标指向的元素  要把游标往后面移动一位            {               lhead->slider = ret->next;           }           lhead->length--; //这个一定要写在 Get_CircleListNode 后面 不然的话 pos就为0了            /*判断链表是否 减到了空  如果链表中不再有元素 就把head.next赋值为NULL*/           /*单向链表不需要这个的原因 是因为单向链表的最后一个元素的next就是NULL 而双向链表没有NULL的了*/           if(0 == lhead->length)           {               lhead->head.next = NULL;               lhead->slider = NULL;            }                  }       return (CircleListNode*)ret;   }      /*******************************************************************************************************  函数名: CircleList_Slider  函数功能:获得当前游标指向的数据  参数: CircleList* head  返回值:成功返回 CircleListNode* ret  失败返回NULL   *******************************************************************************************************/   CircleListNode* CircleList_Slider(CircleList* head)   {       CircleListNode* ret = NULL;       list_head* lhead = (list_head* )head;       if( (NULL != lhead)&&(NULL != lhead->slider) )//保证slider是有效的        {           ret = lhead->slider;       }       return ret;   }      /*******************************************************************************************************  函数名: CircleList_Reset  函数功能:重置游标 让游标指向head头节点后面的第一个元素   参数: CircleList* head  返回值:成功返回 当前游标的指向CircleListNode* ret  失败返回NULL   *******************************************************************************************************/   CircleListNode* CircleList_Reset(CircleList* head)   {       CircleListNode* ret = NULL;       list_head* lhead = (list_head* )head;       if(NULL != lhead)       {           lhead->slider = lhead->head.next;           ret = lhead->slider;       }       return ret;   }      /*******************************************************************************************************  函数名: CircleList_Next  函数功能:使游标指向下一个元素   参数: CircleList* head  返回值:成功返回 前游标的指向CircleListNode* ret  失败返回NULL   *******************************************************************************************************/   CircleListNode* CircleList_Next(CircleList* head)   {       CircleListNode* ret = NULL;       list_head* lhead = (list_head* )head;       if((NULL != lhead)&&(NULL != lhead->slider)) //保证游标是有效的        {           ret = lhead->slider;           lhead->slider = ret->next;        }       return ret;   }      /*******************************************************************************************************  函数名: CircleList_Del  函数功能:删除链表中的某个指定元素   参数: CircleList* head   CircleListNode* node为指定的元素   返回值:成功返回 删除的链表元素  失败返回NULL   *******************************************************************************************************/   CircleListNode* CircleList_Del(CircleList* head,CircleListNode* node)   {   //这个函数主要是用来删除游标的返回值的            CircleListNode* ret = NULL;       list_head* lhead = (list_head* )head;       int i=0;        if((NULL != head)&&(NULL != node))       {           CircleListNode* current = (CircleListNode*)lhead;           for(i=1; i<=lhead->length; i++)           {               if(node == current->next)               {                   ret = current->next;                   break;                }                current = current->next;           }                      if(NULL == ret)  //说明没有找到node            {               printf("put error!!!\n");            }           else //找到了node            {               Del_CircleListNode(lhead,i);            }        }          return ret;//返回删除的链表元素    }   CircleList.h: [cpp] view plaincopy #ifndef __CircleList_H__   #define __CircleList_H__      typedef void CircleList;  //这个是为了 封装方便    typedef struct Str_CircleList CircleListNode;  //这个结构体是链表的真身    struct Str_CircleList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型    {                     //转换成(CircleListNode* )的时候  其实就是要开始对每个元素中的 CircleListNode进行赋值了        CircleListNode* next;   };      CircleList* Creat_CircleListHead(void);      int Destroy_CircleListHead(CircleList* head);      int Get_Length(CircleList* head);      int Clean_CircleListHead(CircleList* head);      int Add_CircleList(CircleList* head, CircleListNode* Node, int pos);      CircleListNode* Get_CircleListNode(CircleList* head, int pos);      CircleListNode* Del_CircleListNode(CircleList* head, int pos);       CircleListNode* CircleList_Del(CircleList* head,CircleListNode* node);      CircleListNode* CircleList_Next(CircleList* head);      CircleListNode* CircleList_Reset(CircleList* head);      CircleListNode* CircleList_Slider(CircleList* head);       #endif   main.c: [cpp] view plaincopy #include <stdio.h>   #include <stdlib.h>   #include "CircleList.h"      typedef struct _tag_str   {       CircleListNode head;       int i;   }str;   int main(int argc, char *argv[])    {       str str1,str2,str3,str4,str5,str6;       str *strp;       int i=0;       str1.i=1;       str2.i=2;       str3.i=3;       str4.i=4;       str5.i=5;       str6.i=6;       CircleList* head;       head = Creat_CircleListHead();              Add_CircleList(head, (CircleListNode*)&str1, 0);       Add_CircleList(head, (CircleListNode*)&str2, 0);       Add_CircleList(head, (CircleListNode*)&str3, 0);       Add_CircleList(head, (CircleListNode*)&str4, 0);       Add_CircleList(head, (CircleListNode*)&str5, 5);              for(i=1; i<=2*Get_Length(head); i++)       {           strp = (str* )Get_CircleListNode(head, i);           printf("%d\n",strp->i);       }       printf("\n");              printf("%d\n",Get_Length(head));       strp = (str* )Del_CircleListNode(head, 6);       printf("%d\n",strp->i);                printf("%d\n",Get_Length(head));       printf("\n");       for(i=1; i<=2*Get_Length(head); i++)       {           strp = (str* )Get_CircleListNode(head, i);           printf("%d\n",strp->i);       }              printf("\n");       printf("%d\n",Get_Length(head));       strp = (str* )Del_CircleListNode(head, 1);       printf("%d\n",strp->i);                printf("%d\n",Get_Length(head));       printf("\n");       for(i=1; i<=2*Get_Length(head); i++)       {           strp = (str* )Get_CircleListNode(head, i);           printf("%d\n",strp->i);       }                                   printf("\n");       for(i=1; i<=3; i++)       {           strp = (str* )Del_CircleListNode(head, 1);           printf("%d\n",strp->i);       }              /*CircleList_Reset(head);      CircleList_Next(head);      CircleList_Del(head,(CircleListNode*)&str3);      strp = (str* )CircleList_Slider(head);      printf("%d\n",strp->i);      printf("\n");            for(i=1; i<=2*Get_Length(head); i++)      {          strp = (str* )Get_CircleListNode(head, i);          printf("%d\n",strp->i);      }      printf("\n");*/                        Destroy_CircleListHead(head);       return 0;   }           本节知识点: 1.为什么选择双向链表:因为单向链表只能一直指向下一个链表元素,不能获得前一个元素,如果要进行逆序访问操作是极其耗时的,所以引入双向链表。 2.双向链表的结构:在单向链表的基础上增加了一个链表结构pre,如图。 注意:链表第一个元素的前驱pre不是指向头结点head,而是指向NULL,链表尾结点的后继next指向NULL 3.如何将一个单向链表改成双向链表:    第一步 (改变链表的结构加入前驱): [cpp] view plaincopy struct Str_DLinkList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型    {                     //转换成(DLinkListNode* )的时候  其实就是要开始对每个元素中的 DLinkListNode进行赋值了        DLinkListNode* next;       DLinkListNode* pre;   };      第二步 (改写插入函数):    对于一个尾插法,如图:         (1).正常的链表插入操作,代码如下: [cpp] view plaincopy for(i=1; ( (i<pos) && (node->next != NULL) ); i++)   {       node = node->next;   }   /*此处的node是要插入元素的前一个值  Node是要删除的值*/    Node -> next = node -> next;   node -> next = Node;       (2).把刚刚插入的数据的前驱pre跟前一个数据元素相连,代码如下: [cpp] view plaincopy Node->pre = node;       对于一个正常插入,如图:     (1).正常的链表插入操作,代码如下: [cpp] view plaincopy for(i=1; ( (i<pos) && (node->next != NULL) ); i++)   {       node = node->next;   }   /*此处的node是要插入元素的前一个值  Node是要删除的值*/    Node -> next = node -> next;   node -> next = Node;       (2).先判断是不是尾插法,如果是尾插法,就像上一个情况一样,就不进行这一步的操作了,代码如下: [cpp] view plaincopy if(NULL != Node->next) //判断是否为尾插法 如果不是进入如下操作   如果是尾插法  最后一个链表元素不当作NULL的前驱    {       Node->next->pre = Node;    }      (3).把刚刚插入的数据的前驱pre跟前一个数据元素相连,代码如下: [cpp] view plaincopy Node->pre = node;      对于一个头插法,如图:      (1).正常的链表插入操作,代码如下: [cpp] view plaincopy for(i=1; ( (i<pos) && (node->next != NULL) ); i++)   {       node = node->next;   }   /*此处的node是要插入元素的前一个值  Node是要删除的值*/    Node -> next = node -> next;   node -> next = Node;        (2).把附近的两个链表的前驱pre都赋值为正确的值,代码如下: [cpp] view plaincopy if(NULL != Node->next) //判断是否为尾插法 如果不是进入如下操作   如果是尾插法  最后一个链表元素不当作NULL的前驱    {       Node->next->pre = Node;    }   Node->pre = node;        (3).如果是头插法,要记得把插入的元素结点的前驱pre赋值为NULL,代码如下: [cpp] view plaincopy if( node == (DLinkListNode* )head)  //如果是头插法 就要将第一个链表元素的前驱写成NULL  不然前驱就变成了头节点了    {       Node->pre = NULL;   }       (4).第一次插入链表元素,要把游标指向插入的链表元素,代码如下: [cpp] view plaincopy if( 0==lhead->length ) //在第一次插入元素的时候  把游标指向第一次个元素    {       lhead->slider = Node;   }        第三步 (改写删除函数):      有三种情况分别是:删除的是第一个结点元素,删除的是最后一个结点元素,删除的是中间结点元素。      (1).删除第一个结点元素:要注意给下一个结点元素的前驱pre赋值为NULL,不是指向head      (2).删除最后一个结点元素:要注意不要给next的前驱再赋值了,因为next已经为NULL了。并且此时要把游标往再往前面移动一个位置。代码如下: [cpp] view plaincopy DLinkListNode* Del_DLinkListNode(DLinkList* head, int pos)   {       DLinkListNode* ret = NULL;       int i = 0;       list_head* lhead = (list_head* )head;       if(( NULL != lhead) && (pos > 0) && (pos <= lhead->length))       {           DLinkListNode* node = (DLinkListNode* )head;           for(i=1; i<pos; i++)//执行 pos次   得到的是第pos位置的node  这个方法行不通            {                   //因为要想删除第pos位置的node 应该先找到它上一个链表元素                node = node->next; //所以这里面i=1 比get函数少执行了一次  得到第pos-1位置的node            }           /*值得注意的是 此处的node是要删除元素的前一个值  ret是要删除的值*/           ret = node->next;           node->next = ret->next;                 if(NULL != ret->next) //判断删除的值是否为最后一个元素            {               ret->next->pre = ret->pre;               if(node == (DLinkListNode* )head)//判断删除的值是否为第一个元素                {                   ret->next->pre =  NULL;               }                if(lhead->slider == ret) //判断删除的节点是否为游标的位置                {                                      lhead->slider = ret->next;                }            }            else           {               if(lhead->slider == ret) //判断删除的节点是否为游标的位置                {                                      lhead->slider = ret->pre;                }           }              lhead->length--;       }       return (DLinkListNode*)ret;   }   4.双向链表的快速排序: 对于双向链表进行快速排序的效率还不错,比用冒泡排序好很多~~~~~~~此时对快速排序还不是很理解~~~~~等到有了一定理解再回来想想吧!!! 想要提示的一点是,快排是依赖递归实现的,对于递归是有递归层次限制的(其实也是栈溢出的问题),所以快排的最坏情况是已经排序好了的情况,所以对一个链表重复进行快排很容易出现栈溢出的问题!!! 本节代码: DLinkList.c: [cpp] view plaincopy /*******************************************************************************************************  文件名:DLinkList.c  头文件:DLinkList.h   时间: 2013/08/17  作者: Hao  功能:  可以复用 带有增 删 改 查 功能的循环链表  难道: 1.typedef struct Str_DLinkList DLinkListNode;  //这个结构体是链表的真身           struct Str_DLinkList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型           {                     //转换成(DLinkListNode* )的时候  其实就是要开始对每个元素中的 DLinkListNode进行赋值了               DLinkListNode* next;          };           这个链表结构在链表元素中起到的作用 是本节的难点           2.切记一个问题  就是已经是链表中元素的 千万不要再往链表中添加了 否则链表一定出现无穷的错误           3.对于pos值的问题  add、get、del三个函数中 的链表都是 从1开始的到length  0是链表头                             在add函数中pos为0的时候是和pos为1的情况是一样的  都是头插法  0~~~~~无穷大                             在get函数中pos为0的时候是获得链表头 地址      0~~~~~length                             在del函数中pos为0的时候是无效的 del失败       1~~~~~length   *******************************************************************************************************/   #include <stdio.h>   #include <stdlib.h>   #include <malloc.h>   #include "DLinkList.h"      typedef struct str_list_head  //这个是链表头 其实也可以当作一个没有前驱的 链表元素 元素的内容是链表长度    {       //DLinkListNode* next;       DLinkListNode head; //这个参数要特别重视 每一个链表元素结构的第一个参数一定是 DLinkListNode                          //因为在寻找链表元素后继的时候 其实就是将链表元素强制类型转换成 DLinkListNode*  然后给next进行赋值 其实就是给 DLinkListNode变量赋值        DLinkListNode* slider;       int length; //链表长度    }list_head;      /*******************************************************************************************************  函数名: Creat_DLinkListHead  函数功能:创建一个链表的链表头 并给链表头分配空间  参数: void  返回值:ret 成功返回链表头地址  失败返回NULL   *******************************************************************************************************/   DLinkList* Creat_DLinkListHead(void)   {       list_head* ret = NULL;       ret = (list_head* )malloc( sizeof(list_head)*1 );       if(NULL != ret) //malloc分配成功        {           ret->length = 0;           //ret -> next = NULL;           ret->head.next = NULL;           ret->head.pre = NULL;           ret->slider = NULL;       }       return (DLinkList* )ret;    }      /*******************************************************************************************************  函数名:Destroy_DLinkListHead  函数功能:释放一个链表头指针   参数:DLinkList* head 链表头指针   返回值: ret 释放成功返回1  释放失败返回0   *******************************************************************************************************/   int Destroy_DLinkListHead(DLinkList* head)   {       int ret = 0;        list_head* lhead = (list_head* )head;       if( NULL != lhead )       {           free(lhead);           ret = 1;       }       return ret;   }      /*******************************************************************************************************  函数名:Get_Length  函数功能:获得链表的长度   参数: DLinkList* head 链表头指针   返回值: ret 成功返回链表长度  失败返回0   *******************************************************************************************************/   int Get_Length(DLinkList* head)    {       int ret = 0;       list_head* lhead = (list_head* )head;       if( NULL != lhead )       {           ret = lhead -> length;       }          return ret;   }      /*******************************************************************************************************  函数名:Clean_DLinkListHead  函数功能:   清空链表   参数: DLinkList* head 链表头指针   返回值:ret 成功返回1 失败返回0   *******************************************************************************************************/   int Clean_DLinkListHead(DLinkList* head)    {       int ret = 0;       list_head* lhead = (list_head* )head;       if( NULL != lhead )       {           lhead->length = 0;           //lhead -> next = NULL;           lhead->head.next = NULL;           lhead->head.pre = NULL;           lhead->slider = NULL;           ret = 1;       }          return ret;   }      /*******************************************************************************************************  函数名:Add_DLinkList  函数功能:往链表里面添加一个链表元素 如果pos的值是0(就是链表头)和1(链表的第一元素 链表元素个数是从1开始算的)都是头插法            pos的值大于链表长度是尾插法  这里面pos值得注意的是 i=1 pos为a的时候 是把链表元素插入第a个元素的位置             当i=0 pos为a的时候 是把链表元素插入 第a个元素位置的后面    切忌:这里面0位置是链表头指针 从1开始是链表元素   参数:   DLinkList* head链表头指针    DLinkListNode* Node插入元素的指针(被强制类型转化成DLinkListNode*)  int pos 插入位置            pos的有效值范围是 从0到无穷大    返回值: ret 插入成功返回1  插入失败返回0   *******************************************************************************************************/   int Add_DLinkList(DLinkList* head, DLinkListNode* Node, int pos)   {       int ret = 0;       int i = 0;       list_head* lhead = (list_head* )head;       DLinkListNode* node = (DLinkListNode* )head;       ret=( NULL != node) && ( NULL != Node) && (pos >= 0);       if(1 == ret)       {           for(i=1; ( (i<pos) && (node->next != NULL) ); i++)           {               node = node->next;           }           /*此处的node是要插入元素的前一个值  Node是要删除的值*/            Node -> next = node -> next;           node -> next = Node;           if(NULL != Node->next) //判断是否为尾插法 如果不是进入如下操作   如果是尾插法  最后一个链表元素不当作NULL的前驱            {               Node->next->pre = Node;            }           Node->pre = node;                      if( 0==lhead->length ) //在第一次插入元素的时候  把游标指向第一次个元素            {               lhead->slider = Node;           }           if( node == (DLinkListNode* )head)  //如果是头插法 就要将第一个链表元素的前驱写成NULL  不然前驱就变成了头节点了            {               Node->pre = NULL;           }                      lhead -> length++;        }       return ret;   }      /*******************************************************************************************************  函数名:Get_DLinkListNode  函数功能:获得链表中第pos个元素位置的链表元素 链表是从1开始的  0是链表头   pos为0的时候表示get链表头   参数: DLinkList* head链表头指针    int pos获得链表元素的位置  pos的有效取值范围是 1 到  length  0是链表头   返回值: DLinkListNode*类型 第pos个链表元素的地址   *******************************************************************************************************/   DLinkListNode* Get_DLinkListNode(DLinkList* head, int pos)   {       int ret = 0;       int i = 0;       list_head* lhead = (list_head* )head;       ret=( NULL != lhead) && (pos >= 0) && (pos <= lhead->length);       if(1 == ret)       {           DLinkListNode* node = (DLinkListNode* )head;           for(i=0; i<pos; i++) //执行 pos次   得到的是第pos位置的node            {               node = node->next;           }              return (DLinkListNode*)node;       }       return NULL;   }      /*******************************************************************************************************  函数名:Del_DLinkListNode  函数功能:删除链表中第pos位置的链表元素   参数: DLinkList* head链表头指针    int pos删除链表元素的位置  pos是删除的链表元素的位置 跟get和add中的         pos是配套的  有效取值范围依然是 1到 length  在这个函数里面由于不能删除链表头 所以pos为0的时候无效   返回值: DLinkListNode* ret这个返回值很重要 因为这个删除仅仅是把链表元素踢出了链表 并没有free开辟的内存           应该通过这个返回的地址free  释放内存           删除成功返回 删除链表元素的地址   删除失败返回 NULL   *******************************************************************************************************/   DLinkListNode* Del_DLinkListNode(DLinkList* head, int pos)   {       DLinkListNode* ret = NULL;       int i = 0;       list_head* lhead = (list_head* )head;       if(( NULL != lhead) && (pos > 0) && (pos <= lhead->length))       {           DLinkListNode* node = (DLinkListNode* )head;           for(i=1; i<pos; i++)//执行 pos次   得到的是第pos位置的node  这个方法行不通            {                   //因为要想删除第pos位置的node 应该先找到它上一个链表元素                node = node->next; //所以这里面i=1 比get函数少执行了一次  得到第pos-1位置的node            }           /*值得注意的是 此处的node是要删除元素的前一个值  ret是要删除的值*/           ret = node->next;           node->next = ret->next;                 if(NULL != ret->next) //判断删除的值是否为最后一个元素            {               ret->next->pre = ret->pre;               if(node == (DLinkListNode* )head)//判断删除的值是否为第一个元素                {                   ret->next->pre =  NULL;               }                if(lhead->slider == ret) //判断删除的节点是否为游标的位置                {                                      lhead->slider = ret->next;                }            }            else           {               if(lhead->slider == ret) //判断删除的节点是否为游标的位置                {                                      lhead->slider = ret->pre;                }           }              lhead->length--;       }       return (DLinkListNode*)ret;   }      /*******************************************************************************************************  函数名: DLinkList_Slider  函数功能:获得当前游标指向的数据  参数: DLinkList* head  返回值:成功返回 DLinkListNode* ret  失败返回NULL   *******************************************************************************************************/   DLinkListNode* DLinkList_Slider(DLinkList* head)   {       DLinkListNode* ret = NULL;       list_head* lhead = (list_head* )head;       if( (NULL != lhead)&&(NULL != lhead->slider) )//保证slider是有效的        {           ret = lhead->slider;       }       return ret;   }      /*******************************************************************************************************  函数名: DLinkList_Reset  函数功能:重置游标 让游标指向head头节点后面的第一个元素   参数: DLinkList* head  返回值:成功返回 当前游标的指向DLinkListNode* ret  失败返回NULL   *******************************************************************************************************/   DLinkListNode* DLinkList_Reset(DLinkList* head)   {       DLinkListNode* ret = NULL;       list_head* lhead = (list_head* )head;       if(NULL != lhead)       {           lhead->slider = lhead->head.next;           ret = lhead->slider;       }       return ret;   }      /*******************************************************************************************************  函数名: DLinkList_Next  函数功能:使游标指向下一个元素   参数: DLinkList* head  返回值:成功返回 前游标的指向DLinkListNode* ret  失败返回NULL   *******************************************************************************************************/   DLinkListNode* DLinkList_Next(DLinkList* head)   {       DLinkListNode* ret = NULL;       list_head* lhead = (list_head* )head;       if((NULL != lhead)&&(NULL != lhead->slider)) //保证游标是有效的        {           ret = lhead->slider;           lhead->slider = ret->next;        }       return ret;   }      /*******************************************************************************************************  函数名: DLinkList_Pre  函数功能:使游标指向上一个元素   参数: DLinkList* head  返回值:成功返回 前游标的指向DLinkListNode* ret  失败返回NULL   *******************************************************************************************************/   DLinkListNode* DLinkList_Pre(DLinkList* head)   {       DLinkListNode* ret = NULL;       list_head* lhead = (list_head* )head;       if((NULL != lhead)&&(NULL != lhead->slider)) //保证游标是有效的        {           ret = lhead->slider;           lhead->slider = ret->pre;        }       return ret;   }      /*******************************************************************************************************  函数名: DLinkList_Del  函数功能:删除链表中的某个指定元素   参数: DLinkList* head   DLinkListNode* node为指定的元素   返回值:成功返回 删除的链表元素  失败返回NULL   *******************************************************************************************************/   DLinkListNode* DLinkList_Del(DLinkList* head,DLinkListNode* node)   {   //这个函数主要是用来删除游标的返回值的            DLinkListNode* ret = NULL;       list_head* lhead = (list_head* )head;       int i=0;        if((NULL != head)&&(NULL != node))       {           DLinkListNode* current = (DLinkListNode*)lhead;           for(i=1; i<=lhead->length; i++)           {               if(node == current->next)               {                   ret = current->next;                   break;                }                current = current->next;           }                      if(NULL == ret)  //说明没有找到node            {               printf("put error!!!\n");            }           else //找到了node            {               Del_DLinkListNode(lhead,i);                printf("ii%d\n",i);           }        }          return ret;//返回删除的链表元素    }      /*****************************************************************************************************************  函数名: partion  函数功能:快速排序的子函数  参数: LinkList* pstHead 链表头  LinkListNode* pstLow 开始排序的头指针  LinkListNode* pstHigh  结束排序的尾指针   返回值: LinkListNode* partion  返回中值的指针  注意:way_id是比较的数据     data是交换的数据   *****************************************************************************************************************/    DLinkListNode* partion(DLinkList* pstHead, DLinkListNode* pstLow, DLinkListNode* pstHigh)     {              list* list_pstLow= (list*) pstLow;            list* list_pstHigh= (list*) pstHigh;            DATA iTmp;              unsigned int pivot = 0;              pivot = list_pstLow->data.way_id;              while ( pstLow != pstHigh )              {                   //从后面往前换                   while ( (pstLow != pstHigh) && (list_pstHigh->data.way_id >= pivot))                   {                         pstHigh = pstHigh->pre;                        list_pstHigh = (list*) pstHigh;                 }                   //交换high low                   iTmp = list_pstLow->data;                   list_pstLow->data = list_pstHigh->data;                   list_pstHigh->data = iTmp;                                   //从前往后换                   while ( pstLow != pstHigh && list_pstLow->data.way_id <= pivot )                   {                         pstLow = pstLow->next;                        list_pstLow = (list*)pstLow;                 }                   //交换high low                   iTmp = list_pstLow->data;                   list_pstLow->data = list_pstHigh->data;                   list_pstHigh->data = iTmp;              }              return pstLow;     }     /*****************************************************************************************************************  函数名: quick_sort  函数功能:快速排序  参数: LinkList* pstHead 链表头指针 LinkListNode* pstLow 开始排序的头指针 LinkListNode* pstHigh  结束排序的尾指针   返回值:void  无返回值   *****************************************************************************************************************/     void quick_sort(DLinkList* pstHead, DLinkListNode* pstLow, DLinkListNode* pstHigh)     {         DLinkListNode* pstTmp = NULL;         pstTmp = partion(pstHead, pstLow, pstHigh);         if ( pstLow != pstTmp )         {              quick_sort(pstHead, pstLow, pstTmp->pre);         }          if ( pstHigh != pstTmp )          {             quick_sort(pstHead, pstTmp->next, pstHigh);          }           }     DLinkList.h: [cpp] view plaincopy #ifndef __DLinkList_H__   #define __DLinkList_H__      typedef void DLinkList;  //这个是为了 封装方便    typedef struct Str_DLinkList DLinkListNode;  //这个结构体是链表的真身    struct Str_DLinkList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型    {                     //转换成(DLinkListNode* )的时候  其实就是要开始对每个元素中的 DLinkListNode进行赋值了        DLinkListNode* next;       DLinkListNode* pre;   };   /**************************************如下参数是为了快速排序罗列的****************************************/   typedef struct _tag_DATA   {       unsigned int data_length;    //dat中前2个字节  表示一条信息的长度  在用多少个字节        unsigned int way_id;         //4个字节  表示道路唯一id        unsigned int way_name_length;//2个字节  表示道路名称所占字节数 注意:这个不准        unsigned int way_data;       //4个字节  表示道路信息  0~3位表示Class番号   4~6位表示岔路数   7位表示有无flag       unsigned char Class;         //way_data & 0000 0000 0000 0000 0000 0000 0000 1111   0x0f       unsigned char byroad_num;    //way_data & 0000 0000 0000 0000 0000 0000 0111 0000   0x70       unsigned char flag;          //way_data & 0000 0000 0000 0000 0000 0000 1000 0000   0x80       char way_name[256];          //data_length-12个字节   表示道路名称    }DATA;         typedef struct _tag_list   {       DLinkListNode head;        DATA data;    }list;   /****************************************************************************************/      DLinkList* Creat_DLinkListHead(void);      int Destroy_DLinkListHead(DLinkList* head);      int Get_Length(DLinkList* head);      int Clean_DLinkListHead(DLinkList* head);      int Add_DLinkList(DLinkList* head, DLinkListNode* Node, int pos);      DLinkListNode* Get_DLinkListNode(DLinkList* head, int pos);      DLinkListNode* Del_DLinkListNode(DLinkList* head, int pos);       DLinkListNode* DLinkList_Slider(DLinkList* head);      DLinkListNode* DLinkList_Reset(DLinkList* head);      DLinkListNode* DLinkList_Next(DLinkList* head);      DLinkListNode* DLinkList_Pre(DLinkList* head);      DLinkListNode* DLinkList_Del(DLinkList* head,DLinkListNode* node);              #endif   main.c: [cpp] view plaincopy #include <stdio.h>   #include <stdlib.h>   #include "DLinkList.h"      typedef struct _tag_str   {       DLinkListNode head;       int i;   }str;   int main(int argc, char *argv[])   {       int j = 0;       DLinkList* list_head;       list_head = Creat_DLinkListHead();       str str1,str2,str3,str4,str5,str6,*strp;       str1.i=1;       str2.i=2;       str3.i=3;       str4.i=4;       str5.i=5;       str6.i=6;          Add_DLinkList(list_head, (DLinkListNode*)&str1,12);       Add_DLinkList(list_head, (DLinkListNode*)&str2,12);       Add_DLinkList(list_head, (DLinkListNode*)&str3,12);       Add_DLinkList(list_head, (DLinkListNode*)&str4,12);       Add_DLinkList(list_head, (DLinkListNode*)&str5,12);                 //  Add_DLinkList(list_head, (DLinkListNode*)&str6,0);       for(j=1;j<=Get_Length(list_head);j++)       {           strp = (str* )Get_DLinkListNode(list_head, j);           printf("%d\n",strp->i);       }             printf("\n");       //DLinkList_Reset(list_head);       strp = (str* )DLinkList_Slider(list_head);       printf("%d\n",strp->i);       printf("\n");       for(j=1;j<=Get_Length(list_head)-1;j++)       {           DLinkList_Next(list_head);           strp = (str* )DLinkList_Slider(list_head);           printf("%d\n",strp->i);       }              DLinkList_Del(list_head,(DLinkListNode*)&str5);       printf("\n");              for(j=1;j<=Get_Length(list_head)-1;j++)       {           DLinkList_Pre(list_head);           strp = (str* )DLinkList_Slider(list_head);           printf("%d\n",strp->i);       }                    Destroy_DLinkListHead(list_head);       return 0;   }   在前两节的基础上,实现双向循环链表。 本节知识点: 1.双向循环链表的结构: 上面就是双向循环链表的结构图,对于双向链表的插入有3个位置,A、B、C。 但是在插入第一个元素的时候(其实插入第一个元素的时候,就是循环建立的时候),有些特殊,所以就画了一个图,如下: 本节代码: DcLinkList.c: [cpp] view plaincopy /*******************************************************************************************************  文件名:DcLinkList.c  头文件:DcLinkList.h   时间: 2013/08/26  作者: Hao  功能:  可以复用 带有增 删 改 查 功能的双向循环链表  难道: 1.typedef struct Str_DcLinkList DcLinkListNode;  //这个结构体是链表的真身           struct Str_DcLinkList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型           {                     //转换成(DcLinkListNode* )的时候  其实就是要开始对每个元素中的 DcLinkListNode进行赋值了               DcLinkListNode* next;          };           这个链表结构在链表元素中起到的作用 是本节的难点           2.切记一个问题  就是已经是链表中元素的 千万不要再往链表中添加了 否则链表一定出现无穷的错误           3.对于pos值的问题  add、get、del三个函数中 的链表都是 从1开始的到length  0是链表头                             在add函数中pos为0的时候是和pos为1的情况是一样的  都是头插法  0~~~~~无穷大                             在get函数中pos为0的时候是获得链表头 地址      0~~~~~length                             在del函数中pos为0的时候是无效的 del失败       1~~~~~length   *******************************************************************************************************/   #include <stdio.h>   #include <stdlib.h>   #include <malloc.h>   #include "DcLinkList.h"      typedef struct str_list_head  //这个是链表头 其实也可以当作一个没有前驱的 链表元素 元素的内容是链表长度    {       //DcLinkListNode* next;       DcLinkListNode head; //这个参数要特别重视 每一个链表元素结构的第一个参数一定是 DcLinkListNode                          //因为在寻找链表元素后继的时候 其实就是将链表元素强制类型转换成 DcLinkListNode*  然后给next进行赋值 其实就是给 DcLinkListNode变量赋值        DcLinkListNode* slider;        int length; //链表长度    }list_head;      /*******************************************************************************************************  函数名: Creat_DcLinkListHead  函数功能:创建一个链表的链表头 并给链表头分配空间  参数: void  返回值:ret 成功返回链表头地址  失败返回NULL   *******************************************************************************************************/   DcLinkList* Creat_DcLinkListHead(void)   {       list_head* ret = NULL;       ret = (list_head* )malloc( sizeof(list_head)*1 );       if(NULL != ret) //malloc分配成功        {           ret->length = 0;           //ret -> next = NULL;           ret->head.next = NULL;           ret->head.pre = NULL;           ret->slider = NULL;       }       return (DcLinkList* )ret;    }      /*******************************************************************************************************  函数名:Destroy_DcLinkListHead  函数功能:释放一个链表头指针   参数:DcLinkList* head 链表头指针   返回值: ret 释放成功返回1  释放失败返回0   *******************************************************************************************************/   int Destroy_DcLinkListHead(DcLinkList* head)   {       int ret = 0;        list_head* lhead = (list_head* )head;       if( NULL != lhead )       {           free(lhead);           ret = 1;       }       return ret;   }      /*******************************************************************************************************  函数名:Get_Length  函数功能:获得链表的长度   参数: DcLinkList* head 链表头指针   返回值: ret 成功返回链表长度  失败返回0   *******************************************************************************************************/   int Get_Length(DcLinkList* head)    {       int ret = 0;       list_head* lhead = (list_head* )head;       if( NULL != lhead )       {           ret = lhead -> length;       }          return ret;   }      /*******************************************************************************************************  函数名:Clean_DcLinkListHead  函数功能:   清空链表   参数: DcLinkList* head 链表头指针   返回值:ret 成功返回1 失败返回0   *******************************************************************************************************/   int Clean_DcLinkListHead(DcLinkList* head)    {       int ret = 0;       list_head* lhead = (list_head* )head;       if( NULL != lhead )       {           lhead -> length = 0;           //lhead  -> next = NULL;           lhead -> head.next = NULL;           lhead->head.pre = NULL;           lhead->slider = NULL;           ret = 1;       }          return ret;   }      /*******************************************************************************************************  函数名:Add_DcLinkList  函数功能:往链表里面添加一个链表元素 如果pos的值是0(就是链表头)和1(链表的第一元素 链表元素个数是从1开始算的)都是头插法            pos的值大于链表长度是尾插法  这里面pos值得注意的是 i=1 pos为a的时候 是把链表元素插入第a个元素的位置             当i=0 pos为a的时候 是把链表元素插入 第a个元素位置的后面    切忌:这里面0位置是链表头指针 从1开始是链表元素   参数:   DcLinkList* head链表头指针    DcLinkListNode* Node插入元素的指针(被强制类型转化成DcLinkListNode*)  int pos 插入位置            pos的有效值范围是 从0到无穷大    返回值: ret 插入成功返回1  插入失败返回0   *******************************************************************************************************/   int Add_DcLinkList(DcLinkList* head, DcLinkListNode* Node, int pos)   {       int ret = 0;       int i = 0;       list_head* lhead = (list_head* )head;       DcLinkListNode* node = (DcLinkListNode* )head;       DcLinkListNode* Last = NULL;       ret=( NULL != node) && ( NULL != Node) && (pos >= 0);       if(1 == ret)       {           for(i=1; ( (i<pos) && (node->next != NULL) ); i++)           {               node = node->next;           }           Node -> next = node -> next;           node -> next = Node;                      if(NULL != Node->next)            {               Node->next->pre = Node;            }           Node->pre = node;                      if(lhead->length == 0)//第一次插入元素的时候把游标 指向这个元素             {               lhead->slider = Node;           }           lhead -> length++; //这个一定要在后面调用 lhead->length值的前面更新            /*判断是否为头插法  所谓头插法 就是pos为0和1的情况 其实也就是没有进for循环的情况  剩下的无论pos为多少  进入多少次循环都没有头插法*/           if(node == (DcLinkListNode* )head)            {               Last =(DcLinkListNode* )Get_DcLinkListNode(lhead, lhead->length); //获得链表最后一个元素                Last->next = Node; //把头插法的数据连接到 链表的最后一个元素的后面                Node->pre = Last;           }                  }       return ret;   }      /*******************************************************************************************************  函数名:Get_DcLinkListNode  函数功能:获得链表中第pos个元素位置的链表元素 链表是从1开始的  0是链表头   pos为0的时候表示get链表头   参数: DcLinkList* head链表头指针    int pos获得链表元素的位置  pos的有效取值范围是 1 到  length  0是链表头   返回值: DcLinkListNode*类型 第pos个链表元素的地址   *******************************************************************************************************/   DcLinkListNode* Get_DcLinkListNode(DcLinkList* head, int pos)   {       int ret = 0;       int i = 0;       list_head* lhead = (list_head* )head;       /*本来pos应该是有上限的  但是变成了循环链表pos理论上说就可以无穷大了  但是get函数应该是在链表中有值的情况下才成立的 即(lhead->length>0)*/        ret=( NULL != lhead) && (pos >= 0) && (lhead->length>0);        if(1 == ret)       {           DcLinkListNode* node = (DcLinkListNode* )head;           for(i=0; i<pos; i++) //执行 pos次   得到的是第pos位置的node            {               node = node->next;           }              return (DcLinkListNode*)node;       }       return NULL;   }      /*******************************************************************************************************  函数名:Del_DcLinkListNode  函数功能:删除链表中第pos位置的链表元素   参数: DcLinkList* head链表头指针    int pos删除链表元素的位置  pos是删除的链表元素的位置 跟get和add中的         pos是配套的  有效取值范围依然是 1到 length  在这个函数里面由于不能删除链表头 所以pos为0的时候无效   返回值: DcLinkListNode* ret这个返回值很重要 因为这个删除仅仅是把链表元素踢出了链表 并没有free开辟的内存           应该通过这个返回的地址free  释放内存           删除成功返回 删除链表元素的地址   删除失败返回 NULL   *******************************************************************************************************/   DcLinkListNode* Del_DcLinkListNode(DcLinkList* head, int pos)   {       DcLinkListNode* ret = NULL;       DcLinkListNode* Last = NULL;       int i = 0;       list_head* lhead = (list_head* )head;       DcLinkListNode* first = lhead->head.next;              if(( NULL != lhead) && (pos > 0) && (lhead->length>0))       {           DcLinkListNode* node = (DcLinkListNode* )head;           for(i=1; i<pos; i++)//执行 pos次   得到的是第pos位置的node  这个方法行不通            {                   //因为要想删除第pos位置的node 应该先找到它上一个链表元素                node = node->next; //所以这里面i=1 比get函数少执行了一次  得到第pos-1位置的node            }           /*判断是不是 pos为1的 情况删除头节点后面的第一个元素(这个是没有进入for循环的)  跟循环一圈后的情况不一样  */           /*循环一圈的是进入for循环的情况   此时的node不再是head了 而是链表最后一个元素*/            if(node == (DcLinkListNode* )head)           {               Last =(DcLinkListNode* )Get_DcLinkListNode(lhead, lhead->length);           }                      ret = node->next;           node->next = ret->next;              /*判断是不是循环了一圈后回来的情况 */           if((first == ret) && (NULL == Last))           {               Last =(DcLinkListNode* )Get_DcLinkListNode(lhead, lhead->length);           }           /*判断是否要删除链表中的第一个元素*/           if( Last != NULL )           {               Last->next = ret->next;                lhead->head.next = ret->next;               ret->next->pre = Last;           }                      if(1 != lhead->length) //判断删除的值是否为最后一个元素            {               ret->next->pre = ret->pre;               if(node == (DcLinkListNode* )head)//判断删除的值是否为第一个元素                {                   ret->next->pre =  Last;               }                if(lhead->slider == ret) //判断删除的节点是否为游标的位置                {                   lhead->slider = ret->next;                }            }            lhead->length--; //这个一定要写在 Get_DcLinkListNode 后面 不然的话 pos就为0了            /*判断链表是否 减到了空  如果链表中不再有元素 就把head.next赋值为NULL*/           /*单向链表不需要这个的原因 是因为单向链表的最后一个元素的next就是NULL 而双向链表没有NULL的了*/           if(0 == lhead->length)           {               lhead->head.next = NULL;               lhead->head.pre = NULL;               lhead->slider = NULL;            }                  }       return (DcLinkListNode*)ret;   }      /*******************************************************************************************************  函数名: DcLinkList_Slider  函数功能:获得当前游标指向的数据  参数: DcLinkList* head  返回值:成功返回 DcLinkListNode* ret  失败返回NULL   *******************************************************************************************************/   DcLinkListNode* DcLinkList_Slider(DcLinkList* head)   {       DcLinkListNode* ret = NULL;       list_head* lhead = (list_head* )head;       if( (NULL != lhead)&&(NULL != lhead->slider) )//保证slider是有效的        {           ret = lhead->slider;       }       return ret;   }      /*******************************************************************************************************  函数名: DcLinkList_Reset  函数功能:重置游标 让游标指向head头节点后面的第一个元素   参数: DcLinkList* head  返回值:成功返回 当前游标的指向DcLinkListNode* ret  失败返回NULL   *******************************************************************************************************/   DcLinkListNode* DcLinkList_Reset(DcLinkList* head)   {       DcLinkListNode* ret = NULL;       list_head* lhead = (list_head* )head;       if(NULL != lhead)       {           lhead->slider = lhead->head.next;           ret = lhead->slider;       }       return ret;   }      /*******************************************************************************************************  函数名: DcLinkList_Next  函数功能:使游标指向下一个元素   参数: DcLinkList* head  返回值:成功返回 前游标的指向DcLinkListNode* ret  失败返回NULL   *******************************************************************************************************/   DcLinkListNode* DcLinkList_Next(DcLinkList* head)   {       DcLinkListNode* ret = NULL;       list_head* lhead = (list_head* )head;       if((NULL != lhead)&&(NULL != lhead->slider)) //保证游标是有效的        {           ret = lhead->slider;           lhead->slider = ret->next;        }       return ret;   }      /*******************************************************************************************************  函数名: DLinkList_Pre  函数功能:使游标指向上一个元素   参数: DLinkList* head  返回值:成功返回 前游标的指向DLinkListNode* ret  失败返回NULL   *******************************************************************************************************/   DcLinkListNode* DcLinkList_Pre(DcLinkList* head)   {       DcLinkListNode* ret = NULL;       list_head* lhead = (list_head* )head;       if((NULL != lhead)&&(NULL != lhead->slider)) //保证游标是有效的        {           ret = lhead->slider;           lhead->slider = ret->pre;        }       return ret;   }      /*******************************************************************************************************  函数名: DcLinkList_Del  函数功能:删除链表中的某个指定元素   参数: DcLinkList* head   DcLinkListNode* node为指定的元素   返回值:成功返回 删除的链表元素  失败返回NULL   *******************************************************************************************************/   DcLinkListNode* DcLinkList_Del(DcLinkList* head,DcLinkListNode* node)   {   //这个函数主要是用来删除游标的返回值的            DcLinkListNode* ret = NULL;       list_head* lhead = (list_head* )head;       int i=0;        if((NULL != head)&&(NULL != node))       {           DcLinkListNode* current = (DcLinkListNode*)lhead;           for(i=1; i<=lhead->length; i++)           {               if(node == current->next)               {                   ret = current->next;                   break;                }                current = current->next;           }                      if(NULL == ret)  //说明没有找到node            {               printf("put error!!!\n");            }           else //找到了node            {               Del_DcLinkListNode(lhead,i);            }        }          return ret;//返回删除的链表元素    }   DcLinkList.h: [cpp] view plaincopy #ifndef __DcLinkList_H__   #define __DcLinkList_H__      typedef void DcLinkList;  //这个是为了 封装方便    typedef struct Str_DcLinkList DcLinkListNode;  //这个结构体是链表的真身    struct Str_DcLinkList   //每一个链表元素的结构都会包含这个结构  因为当给链表元素强制类型    {                     //转换成(DcLinkListNode* )的时候  其实就是要开始对每个元素中的 DcLinkListNode进行赋值了        DcLinkListNode* next;       DcLinkListNode* pre;   };      DcLinkList* Creat_DcLinkListHead(void);      int Destroy_DcLinkListHead(DcLinkList* head);      int Get_Length(DcLinkList* head);      int Clean_DcLinkListHead(DcLinkList* head);      int Add_DcLinkList(DcLinkList* head, DcLinkListNode* Node, int pos);      DcLinkListNode* Get_DcLinkListNode(DcLinkList* head, int pos);      DcLinkListNode* Del_DcLinkListNode(DcLinkList* head, int pos);       DcLinkListNode* DcLinkList_Del(DcLinkList* head,DcLinkListNode* node);      DcLinkListNode* DcLinkList_Next(DcLinkList* head);      DcLinkListNode* DcLinkList_Pre(DcLinkList* head);      DcLinkListNode* DcLinkList_Reset(DcLinkList* head);      DcLinkListNode* DcLinkList_Slider(DcLinkList* head);       #endif   main.c: [cpp] view plaincopy #include <stdio.h>   #include <stdlib.h>   #include <malloc.h>   #include <string.h>   #include "DcLinkList.h"      typedef struct _tag_str   {       DcLinkListNode head;       int i;   }str;      int main()   {       int i = 0;       str str1,str2,str3,str4,str5,str6,*strp;       str1.i=1;       str2.i=2;       str3.i=3;       str4.i=4;       str5.i=5;       str6.i=6;       DcLinkList* head = NULL;       head = Creat_DcLinkListHead();       Add_DcLinkList(head, (DcLinkListNode*)&str1, Get_Length(head)+1);       Add_DcLinkList(head, (DcLinkListNode*)&str2, Get_Length(head)+1);       Add_DcLinkList(head, (DcLinkListNode*)&str3, Get_Length(head)+1);       Add_DcLinkList(head, (DcLinkListNode*)&str4, Get_Length(head)+1);       Add_DcLinkList(head, (DcLinkListNode*)&str5, Get_Length(head)+1);          Add_DcLinkList(head, (DcLinkListNode*)&str6, 3);           for(i = 1; i<=Get_Length(head); i++)       {           strp = (str*)Get_DcLinkListNode(head, i);           printf("%d\n",strp->i);       }       Del_DcLinkListNode(head, 1);       printf("\n");              for(i = 1+5; i<=Get_Length(head)+5; i++)       {           strp = (str*)Get_DcLinkListNode(head, i);           printf("%d\n",strp->i);       }                 printf("\n");              DcLinkList_Reset(head);       for(i = 1; i<=Get_Length(head)*3; i++)       {           DcLinkList_Pre(head);           strp = (str*)DcLinkList_Slider(head);              printf("%d\n",strp->i);       }              i = 6;       while(i--)       {           Del_DcLinkListNode(head, i);           }              for(i = 1; i<=Get_Length(head); i++)       {           strp = (str*)Get_DcLinkListNode(head, i);           printf("%d\n",strp->i);       }              Destroy_DcLinkListHead(head);       return 0;   }    

上一篇:(android 基础知识) PendingIntent
下一篇:POJ3555//POJ3130//POJ1474-求解多边形内核

相关文章

相关评论