单链表系列

题目：输入一个链表的头结点，从尾到头反过来打印出每一个节点的值。（不能改变原有链表的结构）

这里单链表的实现用的是当初学习国嵌数据结构和算法视频里面唐老师实现的源码，老师的代码实现的非常经典。今天复习算是领悟到了！

该链表实现精妙之处：写的链表不受业务结构而限制，在我们用的数据类型发生改变时并不需要去改变底层的链表结构。链表结点LinkListNode中只放next指针域。数据业务数据可以根据实际情况随便定义，只需将LinkNode 作为你定义的业务数据类型的第一个成员 就行（这样可以保证该链表节点的地址和该链表指向下一个节点的指针域地址是重合的）。这样可以真正实现程序的低耦合，高内聚！

链表节点定义：

struct Value
{
    LinkListNode* header;      
    int value;  
};

递归实现反转代码：

//递归逆序输出链表的各个节点
void PrintListReversingly_Recursively(struct Value *node) 
{

   	 if( node != NULL )
   	 {
      	 if (node->header != NULL)
		 {
		  	 PrintListReversingly_Recursively( (struct Value *) (node->header));
		 }
		 printf("%d  \t",(struct Value*)node->value );  
   	 }
}

思考这个题目：我最开始能想到的也是栈结构（后进先出），从头到尾遍历链表，同时压到栈中，然后输出打印栈里面的元素。递归的本质就是一个栈的结构！这里用递归比较合适。不然还要维护O(n）的空间内存，还要实现栈结构。

//下面是完整实现文件

LinkList.h源文件：

#ifndef __LISTLINK_H_
#define __LISTLINK_H_
 
typedef void LinkList;
typedef struct _tag_LinkListNode LinkListNode;
struct  _tag_LinkListNode
{
    LinkListNode* next;         
};
 
LinkList* LinkList_Create();
 
void LinkList_Destory(LinkList* list);
 
void LinkList_Clear(LinkList* list);
 
int LinkList_Length(LinkList* list);
 
int LinkList_Insert(LinkList *list,LinkListNode *node,int pos);
 
LinkListNode *LinkList_Get(LinkList* list,int pos);
 
LinkListNode *LinkList_Delete(LinkList *list,int pos);

//void PrintListReversingly_Recursively(LinkList* list);
 
#endif  

LinkList.c源文件：

#include <stdio.h>
#include <malloc.h>
#include "LinkList.h"
 
typedef struct _tag_LinkList
{
    LinkListNode header;    //结构体的首地址 
    int Length;        
}TLinkList;
/*
创建一个头结点 
*/ 
LinkList* LinkList_Create()//O(1)
{
        TLinkList *ret = (TLinkList*)malloc(sizeof(TLinkList));
        
        if(ret != NULL)
        {
            ret->Length = 0;
            ret->header.next = NULL;    
        }
        
        return ret;
}
/*
释放链表 
*/
void LinkList_Destory(LinkList* list)//O(1)
{
    free(list);    
}
/*
链表清空 
*/
void LinkList_Clear(LinkList* list)//O(1)
{
   TLinkList *sList = (TLinkList*)list;
   
   if(sList != NULL)
   {
       sList->Length = 0;
       sList->header.next = NULL;            
   } 
}
/*
得到链表长度 
*/
int LinkList_Length(LinkList* list)//O(1)
{
     TLinkList *sList = (TLinkList*)list;
     int ret = -1;
     
     if(sList != NULL)
     {
        ret = sList->Length;       
     }    
     
     return ret;
}
/*
链表的插入 
*/
int LinkList_Insert(LinkList *list,LinkListNode *node,int pos)//O(n)
{
   TLinkList *sList = (TLinkList*)list;
   int ret = (sList != NULL)&&(pos >= 0)&&(node != NULL);
   int i;
   
   if( ret )
   {
      LinkListNode *current = (LinkListNode*)sList;
      
      for(i=0; (i<pos)&&(current->next != NULL); i++)
      {
            current = current->next;      
      }
      
      node->next = current->next; 
      current->next = node;
      
      sList->Length++;      
   }
   
   return ret;     
} 
/*
链表的查找 
*/ 
LinkListNode *LinkList_Get(LinkList* list,int pos)//O(n)
{
    TLinkList *sList = (TLinkList*)list;
    LinkListNode *ret = NULL; 
    int i; 
    
    if( (0<=pos) && (sList != NULL) &&(pos < sList->Length))
    {
          LinkListNode *current = (LinkListNode*)sList;
          for(i=0; (i<pos); i++)
          {
            current = current->next;      
          } 
          ret = current->next; 
    }
    
    return ret;  
} 
/*
单链表的删除 
*/ 
LinkListNode *LinkList_Delete(LinkList *list,int pos)//O(n)
{
    TLinkList *sList = (TLinkList*)list;
    LinkListNode *ret = NULL; 
    int i; 
    
    if( (0<=pos) && (sList != NULL) &&(pos < sList->Length))
    {
          LinkListNode *current = (LinkListNode*)sList;
          for(i=0; (i<pos); i++)
          {
            current = current->next;      
          } 
          ret = current->next; 
          current->next = ret->next;
          
          sList->Length--;
    }
    return ret;     
} 

测试代码main.c:

#include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"

struct Value
{
    LinkListNode* header;      
    int value;  
};

//递归逆序输出链表的各个节点
void PrintListReversingly_Recursively(struct Value *node) 
{

   	 if( node != NULL )
   	 {
      	 if (node->header != NULL)
		 {
		  	 PrintListReversingly_Recursively( (struct Value *) (node->header));
		 }
		 printf("%d  \t",(struct Value*)node->value );  
   	 }
}


int main(void)
{
    int i = 0;
    LinkList* list = LinkList_Create();
 
    struct Value v1;
    struct Value v2;
    struct Value v3;
    struct Value v4;
    struct Value v5;
    
    
    v1.value = 1;
    v2.value = 2;
    v3.value = 3;
    v4.value = 4;
    v5.value = 5;
    

    /*//头插法 
    LinkList_Insert(list,(LinkListNode*)&v1,0); 
    LinkList_Insert(list,(LinkListNode*)&v2,0); 
    LinkList_Insert(list,(LinkListNode*)&v3,0); 
    LinkList_Insert(list,(LinkListNode*)&v4,0); 
    LinkList_Insert(list,(LinkListNode*)&v5,0);
    */
    //尾插法 
    LinkList_Insert(list,(LinkListNode*)&v1,LinkList_Length(list)); 
    LinkList_Insert(list,(LinkListNode*)&v2,LinkList_Length(list)); 
    LinkList_Insert(list,(LinkListNode*)&v3,LinkList_Length(list)); 
    LinkList_Insert(list,(LinkListNode*)&v4,LinkList_Length(list)); 
    LinkList_Insert(list,(LinkListNode*)&v5,LinkList_Length(list));
    
    for(i=0; i<LinkList_Length(list);i++)
    {
       struct Value* pv =   (struct Value*)LinkList_Get(list,i);
       printf("%d  \t",pv->value);    
    } 
    
    printf("\n########[0]#######\n");
	printf("递归逆序输出链表：\n"); 
    PrintListReversingly_Recursively(LinkList_Get(list,0));
    printf("\n########[0]########\n"); 
    
    printf("删除：\n");
    struct Value* ret = (struct Value*)LinkList_Delete(list,1);
    printf("%d\n",ret->value);
    printf("\n");
    
    for(i=0; i<LinkList_Length(list);i++)
    {
       struct Value* pv =   (struct Value*)LinkList_Get(list,i);
       printf("%d  \t",pv->value);    
    } 
    
    printf("\n########[1]#######\n"); 
    printf("递归逆序输出链表：\n");
    PrintListReversingly_Recursively(LinkList_Get(list,0));
    printf("\n########[1]########\n"); 
    
    LinkList_Destory(list);
    

    printf("Press any key to continue");
    //getchar();
    
    return 0;    
}

运行结果：