单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。单链表的应用非常广，它可以实现栈，队列等。
Problem
我对学习任何东西都希望能找到尽可能简单的例子，而不是看起来好高大上的；
对链表这样简答的数据结构，有些书也是写得太过“完美”啦；
初学者很难抓住重点，反正我初学的时候就是看不懂；
因此我打算从简单入手去演示；
我们需要实现下面图这样的结构，叫做链表哈；
![]()
Solution
首先咱们要想到这几个ABC圆圈可以代表一个数据的节点，什么是节点呢？；
节点就好比是几个同学聚集到一个宿舍一样，他们各自有各自的身高体重；
因此，我们需要一个结构体，声明如下：
<pre class="brush:cpp;toolbar:false">struct node { int height; int weight; };</pre>
这样一个结构体似乎还差些什么，我们观察上面的图发现，在每个圆圈的外边还有一个连接线；
我们需要这样一条线；
因此，我们的代码可能会是这样的：
<pre class="brush:cpp;toolbar:false">struct node { int height; int weight; void * a_line; };</pre>
但是呢！再想想，我们这条线指向的是和它本身一样的结构体；
我们如果声明为和它一样的指针不是更好吗？
<pre class="brush:cpp;toolbar:false">struct node { int height; int weight; struct node * a_line; };</pre>
我们把代码改回来，这样的声明到底合不合法呢？事实上，这里的递归声明一个指针是合法的；
好节点声明完啦，我们可以测试链表啦！这有点不可思议，那么简单吗？看看main函数；
<pre class="brush:cpp;toolbar:false">#include <stdio.h> #include <stdlib.h> 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; }</pre>
好啦！链表完成啦！你或许以为我在开玩笑呢！好吧，其实的确是一个简单的链表啦；
只不过，它只有一个A点，你无法接受这种一个节点的链表，好吧，我们把ABC连接起来；
首先，我们需要三个点；
<pre class="brush:cpp;toolbar:false">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; }</pre>
然后，是把他们连接起来；
A->a_line = B;
B->a_line = C;
好啦！连起来啦，满意啦吧！，你肯定以为我又骗你；
毕竟，怎么也看不出来连接起来啦；
好，让我们从A到C路线走一程，看看能不能走通；
<pre class="brush:cpp;toolbar:false">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; }</pre>
为了，”旅行“我们把名字报道到了旅行社；
并且，我们获取到了第一站地址就是A的地址啦！
出发；
while循环的意思很简单，判断我们是否到达终点；
没有到达就是打印，xxx，，你懂的；
然后we = we->a_line这句话是关键哦！
我不想解释，自己画图想想！！！
想好了看看我们的运行结果吧！
![]()
Discussion
我们的简单链表已经完成，不过他的缺点有点多，比如：
1，要是数据很多怎么办，100000个节点，这个main函数得写多长啊。。。
2，这个连接的方式也太土啦吧！万一某个节点忘记连接下一个怎么办。。。
3，要是我想知道这个节点到底有多长，难道每次都要从头到尾数一遍嘛。。。
4，要是我想在尾部添加一个节点，是不是爬也要爬到尾部去啊。。。
C语言一个单链表的实现
<pre class="brush:cpp;toolbar:false">#include<stdio.h> #include<malloc.h> 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 && i<pos-1)//将指针p移动到要插入元素位置之前 { p = p->next; 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 && i<pos)//将指针p移动到要返回的元素位置 { p = p->next; 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 && i<pos-1)//将指针p移动到要插入元素位置之前 { p = p->next; 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 && i<pos)//将指针p移动到要插入元素位置之前 { p = p->next; 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; }</pre>
您可能感兴趣的文章：
C 语言实例
利用栈来实现单链表的逆序
想系统学习GO语言(Golang
python和c语言的区别是什么
我所理解的链表1
C 语言经典100例
C 语言教程
Go 语言到底适合干什么？
学习golang开始前的准备工作
python用的是什么语言写的
