算法与数据结构之二-------单链表

/**************************************************************** 文件内容：线性表之单链表操作 版本V1.0 说明：针对单链表，插入和删除，最好从P节点后面插入或删除操作，避免P节点前面操作。 因为前位操作，需要找前驱，单链表找前驱又要从节点头部遍历开始，效率太低。 后面因为这个效率原因，引入了双向链表，而双向链表就本身带前驱，操作更方便快捷。 作者：HFL 时间：2013-12-22  *****************************************************************/  #include<stdio.h> #include<stdlib.h> //#define RELEASE_VERSION  //release版本开关 //#define TRIDiTION /*inlude<malloc.h> stdlib.h 包含malloc.h*/ #ifdef RELEASE_VERSION #define  Log  #else #define  Log  printf #endif /*为了提高程序的可移植性，千万不能使用裸露的数据类型*/ #ifndef UINT32  typedef unsigned int UINT32 ; #endif #ifndef INT32  typedef  int  INT32 ; #endif /*************************************************************** 因为struct Node 与LNode 和*Linklist 是互为别名，因此以下写法是等效的 struct Node *s等于 LNode *s     等于 Linklist s ****************************************************************/ #ifndef TRIDiTION   typedef  struct Node {     INT32 data;    struct Node *next; } LNode, * Linklist; #else struct Node { INT32 data; struct Node *next; }; #endif /**************************************************************** 函数功能：创建一个节点                         输入参数:  无 返回值：节点的指针  作者:HFL  时间：2013-12-22  *****************************************************************/ Linklist Creat_Node(INT32 X) {  Linklist s;       s=(struct Node *)malloc(sizeof(LNode));  if(NULL==s) { Log(" sorry,Malloc is failed\n"); } else { Log(" Malloc is successed!\n"); s->data = X; } return s; } /**************************************************************** 函数功能：初始化链表1（即头部创建一个链表）                         输入参数:  无 返回值：链表的标头指针  作者:HFL  时间：2013-12-22  *****************************************************************/  Linklist Head_Creat_Linklist() { Linklist L=NULL; LNode *s; INT32 x;     scanf("%d",&x); while(x!=0) {  s=(struct Node *)malloc(sizeof(LNode));  if(NULL==s) { Log(" sorry,Malloc is failed\n"); } else { Log(" Malloc is successed!\n"); s->data = x ;/*一定要注意第一个节点，且一定要注意先后顺序*/ s->next = L; L=s; scanf("%d",&x); } } return L; } /**************************************************************** 函数功能：初始化链表2（即尾部创建一个链表）                         输入参数:  无 返回值：链表的标头指针  说明：要引入一个新的指针变量，用于链接前后节点 作者:HFL  时间：2013-12-22  ************T*****************************************************/  Linklist Tail_Creat_Linklist() { Linklist L=NULL; LNode *s; LNode *probe =NULL; INT32 x;     scanf("%d",&x); while(x!=0) {  s=(struct Node *)malloc(sizeof(LNode));  if(NULL==s) { Log(" sorry,Malloc is failed\n"); } else { Log(" Malloc is successed!\n"); if(L== NULL) { L = s;  //第一个节点就必需保存投节点 } else { probe->next = s; //第二个节点开始，要引入一个临时指针，来暂存上一个节点地址，一遍链接前后两个节点 } probe = s;  //每次创建一个新节点，节点都必需重新移动。 s->data = x ; s->next = NULL; scanf("%d",&x); } } return L; } /**************************************************************** 函数功能：遍历整个链表                         输入参数:  链表头指针 返回值：无  说明：遍历不能影响原来链表的结构。 作者:HFL  时间：2013-12-22  ************T*****************************************************/  void List_Linklist(Linklist L) {   Linklist temp = L;//不能使用L指针，否则将链表头指针移动，链表被破坏，故使用一个临时指针来变量 INT32 i = 0; while(NULL!=temp) { printf("the data[%d]=%d\n",++i,temp->data); //L->next=L->next->next; temp = temp->next; } return ; } /**************************************************************** 函数功能：求链表的长度                         输入参数:  链表头指针 返回值：  链表长度  说明：求长度不能影响原来链表的结构。 作者:HFL  时间：2013-12-22  ************T*****************************************************/  INT32 Length_Linklist(Linklist L) {   Linklist temp = L;//不能使用L指针，否则将链表头指针移动，链表被破坏，故使用一个临时指针来变量 INT32 length= 0; while(NULL!=temp) { temp = temp->next; length++; } return length; } /**************************************************************** 函数功能：按位置查找                         输入参数:  链表头指针和位置i 返回值：  节点指针，如果无NULL，说明没有找到，否则说明找到，为temp指针指向的节点 说明：查找不能影响原来链表的结构。 作者:HFL  时间：2013-12-22  ************T*****************************************************/  Linklist Search_Position_Linklist(Linklist L,INT32 i) {   Linklist temp = L;//不能使用L指针，否则将链表头指针移动，链表被破坏，故使用一个临时指针来变量 INT32 position = 1; while(NULL != temp && position != i) { temp = temp->next; position++; } return temp; } /**************************************************************** 函数功能：按值查找                         输入参数:  链表头指针和位置i 返回值：  节点指针，如果为NULL，说明没有找到，否则说明找到，为temp指针指向的节点 说明：查找不能影响原来链表的结构。 作者:HFL  时间：2013-12-22  ************T*****************************************************/  Linklist Search_Value_Linklist(Linklist L,INT32 X) {   Linklist temp = L;//不能使用L指针，否则将链表头指针移动，链表被破坏，故使用一个临时指针来变量 INT32 position = 1; while(NULL != temp && temp->data != X) { temp = temp->next; position++; } if(temp === NULL ) { Log ("sorry ,can't finded the data); } else { Log("The data is finded at positon[%d]\n",position); } return temp; } /**************************************************************** 函数功能： 从P节点后面插入k节点                      输入参数:  链表头指针和p节点位置 返回值：   头节点 说明:   插入会改变节点的结构，如果是头节点插入，会修改头节点的。 作者:HFL  时间：2013-12-22  ****************************************************************/  Linklist Insert_Back_Linklist(Linklist L, Linklist p,Linklist k) { if(NULL == L || NULL== k || NULL==p) { Log (" The linklist is null\n"); return NULL; } k->next=p->next; p->next=k; return L; } /**************************************************************** 函数功能： 从P节点前面插入s节点                      输入参数:  链表头指针和p节点位置 返回值：   头节点 说明:   插入会改变节点的结构，如果是头节点插入，会修改头节点的。         前面插入要找前驱，效率低，一般使用双向链表，直接使用前驱指针 作者:  HFL  时间：2013-12-22  ****************************************************************/  Linklist Insert_Front_Linklist(Linklist L, Linklist p,Linklist k) { Linklist temp = L; if(NULL == L || NULL== k || NULL==p) { Log (" The linklist is null\n"); return NULL; } while(temp->next != p) { temp = temp->next; //找到前驱指针 } if (NULL ==temp ) { Log ("The rear poniter is NULL,can't insert front\n"); return NULL; } k->next = temp->next; temp->next = k; return L; } /**************************************************************** 函数功能： 从第i节点位置插入值为X的节点                     输入参数:  链表头指针和p节点位置 返回值：   头节点 说明:   先找到i-1节点，然后在i-1节点后找出入一个节点，即i 位置的节点。 作者:HFL  时间：2013-12-22  ****************************************************************/  Linklist Insert_i_Linklsit(Linklist L,INT32 i,INT32 X) { Linklist temp = Search_Position_Linklist(L,i-1); Linklist s = Creat_Node(X); if(!Insert_Back_Linklist(L,temp,s)) { Log(" Insert back of p node is failde \n"); return NULL ; } return L; } /**************************************************************** 函数功能： 从P节点后面删除一个节点                      输入参数:  链表头指针和p节点位置 返回值：   头节点 说明:   插入会改变节点的结构，如果是头节点插入，会修改头节点的。 作者:HFL  时间：2013-12-22  ****************************************************************/  Linklist Delete_Back_Linklist(Linklist L, Linklist p ) { Linklist s; if(NULL == L) { Log (" The linklist is null\n"); return NULL; } s = p->next ; p->next = p->next->next; free(s);//注意是释放p 节点后面的节点，而不是p节点 return L; } /**************************************************************** 函数功能： P节点                      输入参数:  链表头指针和p节点位置 返回值：   头节点 说明:   插入会改变节点的结构，如果是头节点插入，会修改头节点的。         前面插入要找前驱，效率低，一般使用双向链表，直接使用前驱指针 作者:  HFL  时间：2013-12-22  ****************************************************************/  Linklist Delete_PNode_Linklist(Linklist L, Linklist p) {    Linklist temp = L;    if(NULL == L || NULL==p) { Log (" The linklist is null\n"); return NULL; } while(temp->next != p) { temp = temp->next; //找到前驱指针 } temp->next = p->next; return L; } /**************************************************************** 函数功能： 从P节点前面删除s节点                      输入参数:  链表头指针和p节点位置 返回值：   头节点 说明:   插入会改变节点的结构，如果是头节点插入，会修改头节点的。         前面插入要找前驱，效率低，一般使用双向链表，直接使用前驱指针 作者:  HFL  时间：2013-12-22  ****************************************************************/  Linklist Delete_Front_Linklist(Linklist L, Linklist p) { Linklist temp = L,s; if(NULL == L || NULL==p) { Log (" The linklist is null\n"); return NULL; } while(temp->next->next != p) { temp = temp->next; //找到前前驱指针 } if (NULL ==temp ) { Log ("The rear poniter is NULL,can't insert front\n"); return NULL; } s = temp->next; temp->next = p; free (s); //释放I节点前的一个节点 return L; } /**************************************************************** 函数功能： 删除第i节点                     输入参数:  链表头指针和p节点位置 返回值：   头节点 说明:   先找到i-1节点，然后在i-1节点后找出入一个节点，即i 位置的节点。 作者:HFL  时间：2013-12-22  ****************************************************************/  Linklist Delete_i_Linklist(Linklist L,INT32 i) { Linklist temp = Search_Position_Linklist(L,i-1); if(!Delete_Back_Linklist(L,temp)) { Log(" Insert back of p node is failde \n"); return NULL ; } return L; } void main() {   Linklist L,temp; Log("*******************************\n"); Log("*                             *\n"); Log("*   Creat Linklist is start ! *\n"); Log("*                             *\n"); Log("*******************************\n");    L = Tail_Creat_Linklist();    //L = Head_Creat_Linklist(); if(!L)    {   Log(" the Creat Linklist is failed\n");    }    else    {     Log(" the Creat Linklist is secuseed\n");    } Log("*******************************\n"); Log("*                             *\n"); Log("*   List Linklist is start ! *\n"); Log("*                             *\n"); Log("*******************************\n");     List_Linklist(L); Log("***********************************\n"); Log("*                                 *\n"); Log("*   Get Linklist length is start !*\n"); Log("*                                 *\n"); Log("***********************************\n");     Log("The length of linklist is %d\n",Length_Linklist(L)); Log("******************************************\n"); Log("*                                        *\n"); Log("*  search Linklist by position is start !*\n"); Log("*                                        *\n"); Log("******************************************\n"); temp = Search_Position_Linklist(L,5); if (temp) { Log( "The position data is finded ,the data is %d\n",temp->data); } else { Log("the position can't finded\n"); } Log("******************************************\n"); Log("*                                        *\n"); Log("*  search Linklist by value is start !   *\n"); Log("*                                        *\n"); Log("******************************************\n"); temp = Search_Value_Linklist(L,6); if (temp) { Log( "The position data is finded ,the data is %d\n",temp->data); } else { Log("the position can't finded\n"); } Log("******************************************\n"); Log("*                                        *\n"); Log("*  Insert Linklist back of p is start !  *\n"); Log("*                                        *\n"); Log("******************************************\n"); if(!Insert_Back_Linklist(L,temp,Creat_Node( 999))) { Log ("Insert Linklist back of p is failed \n"); }; List_Linklist(L);     Log("******************************************\n"); Log("*                                        *\n"); Log("*  Delete Linklist back of p is start !  *\n"); Log("*                                        *\n"); Log("******************************************\n");     if(!Delete_Back_Linklist( L, temp)) { Log ("Delete Linklist back of p is failed \n"); };     List_Linklist(L); if(!Insert_i_Linklsit(L,3,12345)) { Log ("Delete Linklist at i position failed \n"); } List_Linklist(L); Log("******************************************\n"); Log("*                                        *\n"); Log("*  Insert Linklist Front of p is start ! *\n"); Log("*                                        *\n"); Log("******************************************\n"); if(!Insert_Front_Linklist(L,temp,Creat_Node(6666))) { Log ("Insert Linklist Front of p is failed \n"); }; List_Linklist(L);     Log("******************************************\n"); Log("*                                        *\n"); Log("*  Delete Linklist Front of p is start ! *\n"); Log("*                                        *\n"); Log("******************************************\n"); if(!Delete_Front_Linklist(L,temp)) { Log ("Insert Linklist Front of p is failed \n"); }; List_Linklist(L); Log("******************************************\n"); Log("*                                        *\n"); Log("*  Delete Linklist I NODE  is start !    *\n"); Log("*                                        *\n"); Log("******************************************\n"); if(!Delete_i_Linklist(L,5)) { Log ("Delete Linklist I NODE is failed \n"); }; List_Linklist(L); Log("******************************************\n"); Log("*                                        *\n"); Log("*  Delete Linklist P NODE  is start !    *\n"); Log("*                                        *\n"); Log("******************************************\n"); if(!Delete_PNode_Linklist(L,temp)) { Log ("Delete Linklist P NODE is failed \n"); }; List_Linklist(L); }