C语言实现单链表实例教程

Problem

我对学习任何东西都希望能找到尽可能简单的例子，而不是看起来好高大上的；
对链表这样简答的数据结构，有些书也是写得太过“完美”啦；
初学者很难抓住重点，反正我初学的时候就是看不懂；
因此我打算从简单入手去演示；
 
我们需要实现下面图这样的结构，叫做链表哈；

Solution

首先咱们要想到这几个ABC圆圈可以代表一个数据的节点，什么是节点呢？；
节点就好比是几个同学聚集到一个宿舍一样，他们各自有各自的身高体重；
因此，我们需要一个结构体，声明如下：

struct node {
    int height;
    int weight;
};

这样一个结构体似乎还差些什么，我们观察上面的图发现，在每个圆圈的外边还有一个连接线；
我们需要这样一条线；
因此，我们的代码可能会是这样的：

struct node {
    int height;
    int weight;
    void * a_line;
};

但是呢！再想想，我们这条线指向的是和它本身一样的结构体；
我们如果声明为和它一样的指针不是更好吗？

struct node {
    int height;
    int weight;
    struct node * a_line;
};

我们把代码改回来，这样的声明到底合不合法呢？事实上，这里的递归声明一个指针是合法的；
好节点声明完啦，我们可以测试链表啦！这有点不可思议，那么简单吗？看看main函数；

#include 
#include 
struct node {
    int hight;
    int weight;
    struct node * a_line;
};
int main(void)
{
    struct node * A = (struct node*)malloc(sizeof(struct node));
    A->weight = 60; //kg
    A->hight =  170;    //cm
    A->a_line = NULL;
    return 0;
}

好啦！链表完成啦！你或许以为我在开玩笑呢！好吧，其实的确是一个简单的链表啦；
只不过，它只有一个A点，你无法接受这种一个节点的链表，好吧，我们把ABC连接起来；
首先，我们需要三个点；

int main(void)
{
    struct node * A = (struct node*)malloc(sizeof(struct node));
    A->weight = 60; //kg
    A->hight =  170;    //cm
    A->a_line = NULL;
    
    struct node * B = (struct node*)malloc(sizeof(struct node));
    B->weight = 50; //kg
    B->hight =  160;    //cm
    B->a_line = NULL;
    
    struct node * C = (struct node*)malloc(sizeof(struct node));
    C->weight = 70; //kg
    C->hight =  180;    //cm
    C->a_line = NULL;
    return 0;
}

然后，是把他们连接起来；

 
    A->a_line = B;
    B->a_line = C;

好啦！连起来啦，满意啦吧！，你肯定以为我又骗你；
毕竟，怎么也看不出来连接起来啦；
好，让我们从A到C路线走一程，看看能不能走通；

struct node * we;   
    we = A;
    while (we != NULL){
        printf("The hight is %d and the weight is %d \n",we->hight,we->weight);
        we = we->a_line;
    }

为了，”旅行“我们把名字报道到了旅行社；
并且，我们获取到了第一站地址就是A的地址啦！

出发；

while循环的意思很简单，判断我们是否到达终点；
没有到达就是打印，xxx，，你懂的；
然后we = we->a_line这句话是关键哦！
我不想解释，自己画图想想！！！
想好了看看我们的运行结果吧！

Discussion

我们的简单链表已经完成，不过他的缺点有点多，比如：
1，要是数据很多怎么办，100000个节点，这个main函数得写多长啊。。。
2，这个连接的方式也太土啦吧！万一某个节点忘记连接下一个怎么办。。。
3，要是我想知道这个节点到底有多长，难道每次都要从头到尾数一遍嘛。。。
4，要是我想在尾部添加一个节点，是不是爬也要爬到尾部去啊。。。

C语言一个单链表的实现

#include
#include
typedef int Item;//定义数据项类型
typedef struct node * PNode;//定义节点指针
//节点的定义
typedef struct node
{
    Item item;//数据域
    PNode next;//链域
    
}Node,* SList;
/*
int SL_Creat(SList *p_list,int size)
参数
p_list：指向一个链表指针，此处传入表头地址
size：要创建的链表分配的数据元素空间个数，不包含头节点
返回值
若成功返回1，否则返回0。
功能
该函数的功能是创建一个大小为size的链表并把链表的头指针赋给p_lsit所指的链表指针。
*/
int SL_Creat(SList *p_list,int size)
{
    PNode p=NULL;
    int i;
    *p_list = (SList)malloc(sizeof(Node));
    if(*p_list==NULL)
        return -1;
    (*p_list)->next = NULL;
    for(i=size;i>0;i--)
    {
        p = (PNode)malloc(sizeof(Node));
        if(p==NULL)
            return -1;
        p->item = 0;
        p->next = (*p_list)->next;
        (*p_list)->next = p;
    }
    return 1;
}
/*
int SL_Insert(SList list,int pos,Item item)
参数
list：要插入数据的单链表
int：指定要插入元素的位置，从1开始计数
item:要插入的数据项
返回值
若成功返回1，否则返回-1。
功能
该函数的功能是在链表list的pos位置插入新元素，其值为item。
*/
int SL_Insert(SList list,int pos,Item item)
{
    PNode p,q;
    int i;
    p = list;
    i = 0;
    while(p!=NULL && inext;
        i++;//i记录p指向的是第几个位置
    }
    if(p==NULL || i > pos-1)
        return -1;
    q = (Node *)malloc(sizeof(Node));//未插入节点分配内存
    if(q!=NULL)//若内存分配成功，将节点插入指定位置
    {
        q->item = item;
        q->next = p->next;
        p->next = q;
        return 1;
    }
    else
    {
        return -1;
    }
}
/*
int SL_GetItem(SList list,int pos,Item *p_item)
参数
list：要获取数据项所在的单链表
int：指定要获取元素在单链表中的位置
p_item:指向要接收数据项的变量
返回值
若成功返回1，否则返回-1。
功能
该函数的功能是获取在链表list的pos位置的元素的数据项，其值赋给p_item所指的变量。
*/
int SL_GetItem(SList list,int pos,Item *p_item)
{
    PNode p;
    int i;    
    p = list;
    i = 0;
    while(p!=NULL && inext;
        i++;//i记录p指向的是第几个位置
    }
    if((p==NULL)||(i>pos))
    {
        return -1;
    }
    *p_item = p->item;
    return 1;
}
/*
int SL_Delete(SList list,int pos,Item * p_item)
参数
list：要删除元素所在的单链表
int：指定要删除元素在单链表中的位置
p_item:指向接收删除元素的数据项的变量
返回值
若成功返回1，否则返回-1。
功能
该函数的功能是删除在链表list的pos位置的元素，其值赋给p_item所指的变量。
*/
int SL_Delete(SList list,int pos,Item * p_item)
{
    PNode p,q;
    int i;
    p = list;
    i = 0;
    while(p!=NULL && inext;
        i++;//i记录p指向的是第几个位置
    }
    if(p->next==NULL || i > pos-1)
        return -1;
    q = p->next;
    p->next = q->next;
    if(p_item != NULL)
        *p_item = q->item;
    free(q);
    return 1;
}
/*
int SL_SetItem(SList list,int pos,Item item)
参数
list：要设置元素所在的单链表
int：指定要设置元素在单链表中的位置
p_item:要设置元素的数据项的值
返回值
若成功返回1，否则返回-1。
功能
该函数的功能是将链表list的pos位置的元素的数据项设置为item。
*/
int SL_SetItem(SList list,int pos,Item item)
{
    PNode p=NULL;
    int i;
    p = list;
    i = 0;
    while(p!=NULL && inext;
        i++;//i记录p指向的是第几个位置
    }
    if(p==NULL || i > pos)
        return -1;
    p->item = item;
    return 1;
}
/*
int SL_Find(SList list,int *pos,Item item)
参数
list：要查找元素所在的单链表
int：指向要存储的查得的元素的位置的变量
p_item:要查找元素的数据项的值
返回值
若成功返回1，否则返回-1。
功能
该函数的功能是在链表list中查找数据项为item的元素，将其位置值赋给pos所指的变量。
*/
int SL_Find(SList list,int *pos,Item item)
{
    PNode p;
    int i;
    p = list;
    i = 0;
    while(p!=NULL && p->item!=item)//将指针p移动到要插入元素位置之前
    {
        p = p->next;
        i++;//i记录p指向的是第几个位置
        if(p->item == item)
        {
            *pos = i; //返回查询到的位置
            return 1;
        }
    }
    return -1;    
}
/*
int SL_Empty(SList list)
参数
list：要判断的单链表
返回值
若为空则返回1，否则返回 0。
功能
该函数的功能是判断链表list是否为空表。
*/
int SL_Empty(SList list)
{
    PNode p;
    p = list;
    if(p->next == NULL)
        return 1;
    return 0;
}
/*
int SL_Size(SList list)
参数
list：要查找的单链表
返回值
返回包含节点的个数。
功能
该函数的功能是返回链表list中节点的个数，包含头节点。
*/
int SL_Size(SList list)
{
    PNode p;
    int i;
    p = list;
    i = 0;
    while(p!=NULL)
    {
        p = p->next;
        i++;
        
    }
    return i;
}
/*
int SL_Clear(SList *p_list)
参数
p_list：指向要清除的单链表
返回值
成功返回值为1。
功能
该函数的功能是清除链表的所有节点，包含头节点。
*/
int SL_Clear(SList *p_list)
{
    PNode p,q;
    int i;
    p = *p_list;
    i = 0;
    while(p!=NULL)
    {
        q = p->next;//借助于q存储p的链域，否则释放p后无法引用
        free(p);
        p = q;
    }
    *p_list = NULL;//将所指的链表指针设为NULL
    
    return 1;
}