线性表的存储方式有：链式存储和顺序存储；
1.先来谈谈链式存储：优点：插入元素和删除元素比较方便；缺点：只能顺序存取，不能随机存取；
2.特点：用一组任意的存储单元（内存空间）来存储线性表中的元素，这组存储单元可以是连续的，也可以不是连续的。
3.链表是一种动态地进行存储单元分配的数据结构；为了表示节点（数据元素）之间的逻辑关系，每个节点的存储空间分为两个部分：一部分存储节点的值，称为“数据域”，另外一部分用来存储指向其直接后继的指针，称为“指针域”；如图1.1所示。

图1.1 单链表的节点形式

在单链表中，每个节点的存储位置都包含在其直接前驱（关于直接前驱，直接后继，后继，前驱的问题稍后描述）节点的指针域中，因此，任意一个节点的位置存取都必须从头指针开始（头指针：指向链表的第一个节点，如果没有头指针head，则整个链表都无法访问）。由于单链表是由头指针唯一确定，因此单链表可以用头指针的名字来命名。如下是一个简单的单链表；

4.有时为了操作的方便，会在单链表的第一个节点的前面附加一个节点，称为“头结点”，头结点的数据域一般不存放任何的数据信息， 也可以用来存放一些如链表的长度等附加信息。头指针指向头结点，头结点中指针域的值是单链表的第1个节点的地址。

假设结点中的数据信息只有一个int型的数据成员，则该节点的类型定义为：

typedef int ElemType;
struct node
{ElemType data;       //数据域struct node *next;   //指针域
}Slink;

5.链表的创建：
（1）内存操作函数
因为链表是在程序执行的过程中从无到有动态的建立起来的；即逐个开辟节点和输入各节点数据，同时建立起来前后相链的关系。因此需要采用c语言提供的函数来实现对内存空间的申请和释放。
I. malloc() 函数。原型如下：

void *malloc(unsigned int size);

功能：是在内存的动态存储区中分配size个字节的连续空间，其返回值是“所分配的那一段空间的起始地址”，若分配失败，则返回一个空指针NULL（0）。

II. calloc() 函数。原型如下：

void *calloc(unsigned int n, unsigned int size);

功能：在内存的动态存储区中分配n个长度为size个字节的连续空间，它的返回值是“所分配空间的起始地址；若分配失败，则返回一个空指针NULL(0)”.

III.realloc() 函数，原型如下：

 void *realloc (void *ptr, size_t size);ptr 为需要重新分配的内存空间指针，size 为新的内存空间的大小

功能：realloc() 对 ptr 指向的内存重新分配 size 大小的空间，size 可比原来的大或者小，还可以不变。当 malloc()、calloc() 分配的内存空间不够用时，就可以用 realloc() 来调整已分配的内存。如果 ptr 为 NULL，它的效果和 malloc() 相同，即分配 size 字节的内存空间。如果 size 的值为 0，那么 ptr 指向的内存空间就会被释放，但是由于没有开辟新的内存空间，所以会返回空指针；类似于调用 free()。

VI. free() 函数，其函数原型如下：

void free(void *p);

功能：释放p所指向的内存区，该函数没有返回值。一般p是调用malloc()或calloc()函数的返回值。

（2） 链表创建步骤
1 . 生成只含头结点的空链表。
2. 读取数据的信息，生成新节点，并且将数据存放在新节点中，插入新节点到单链表中去。
3. 重复步骤2

例如：在表尾插入节点生成单链表。（这里约定：当输入的数字为0的时候结束输入）1步：生成头结点；让头指针head去指向头结点。此时链表中有一个节点，当前该节点即是头结点，也是最后一个节点（即尾结点），所以让尾指针rear指向这个节点：如下图：

2步：接受输入的第一个数字，并判断该数字是否为0；若为0，则生成一个新节点s（此时需要malloc分配节点的内存空间），给s->data赋值为刚输入的数字值，同时置当前的指针域为空；反之，则修改尾节点（此时的尾结点为头结点）的指针域指向新的节点s，此时的s便是新的尾节点，同时修改rear指针指向s节点。如下图：
（这里假设输入的数字是“1”）

3.读入数字2，仍然生成新节点s，节点s的数据域值为2，并把当前节点s插入到表尾，修改rear指针指向当前的节点（尾结点s->data=2）；如下图：

重复上面步骤·······知道输入的数字是0，此时的新节点s的指针域置为空（用“^”表示）。如下图：

单链表的创建、插入元素、删除元素、元素定位、求表长等操作；
代码示例：

 /*创建接口*/
#ifndef _SLINK_H
#define _SLINK_H
#include <stdlib.h>
#include <stdio.h>
#define true  1
#define false 0 
typedef int ElemType;
typedef struct node{ElemType data;struct node *next;}Slink;//1. 创建一个含n个元素的带头结点的单链表
Slink *CreateSlink(int n);
//2. 求表长操作
int GetLSlink(Slink *head);
//3. 插入元素操作
int  InsertSlink(Slink *head,int i,ElemType x);
//4. 删除元素
int DeleteSlink(Slink *head,int i, ElemType *e);
//5. 元素定位操作
Slink *LocSlink(Slink *head,ElemType x);
//6. 输出操作
void PrintSlink(Slink *head);
#endif

  /*实现接口*/
#include "Slink.h"//1. 创建一个含n个元素的带头结点的单链表
Slink *CreateSlink(int n){Slink *head,*currnet,*s;int i;currnet=head=(Slink *)malloc (sizeof(Slink));  //创建头结点printf ("请输入%d个值:\n",n);for (i=0;i<n;i++){s=(Slink *)malloc (sizeof(Slink));scanf ("%d",&s->data);currnet->next=s;   //将新节点s插入链表的尾结点currnet=s;         //修改尾指针指向current指向当前的尾结点s}currnet->next=NULL;return head;}//2. 求表长操作
int GetLSlink(Slink *head){Slink *current;int length=0;current=head;while (current->next!=NULL){length++;current=current->next;}return length;}//3. 插入元素操作(在带头结点的单链表head中的第i个节点前插入元素x）
int  InsertSlink(Slink *head,int i,ElemType x){Slink *current,*s;int j=0;if (i<1) return false;   //1.首先检查i是否满足条件current=head;while (current!=NULL&&j<i-1){j++;current=current->next;}if (current==NULL) return false;  //i超过表的长度s=(Slink *)malloc (sizeof(Slink)); //创建新节点ss->data=x;s->next=current->next; current->next=s;return true;}//4. 删除元素(删除带头节点单链表head的第i个节点）
int DeleteSlink(Slink *head,int i, ElemType *e){Slink *current,*rear;int j=0;if (i<1)return false;current=head;while (current->next!=NULL&&j<i-1){j++;current=current->next;}if (current->next==NULL){return false;}rear=current->next;   //令rear尾指针指向第i个节点current->next=rear->next;*e=rear->data;free (rear);   //释放掉第i个节点所占用的内存空间return true;}//5. 元素定位操作(查找元素x在单链表head中第一次出现的位置）
Slink *LocSlink(Slink *head,ElemType x){Slink *current=NULL;int i;current=head;while (current->next!=NULL&&current->data!=x){i++;current=current->next;}return current;}//6. 输出操作
void PrintSlink(Slink *head){Slink *current=NULL;current=head->next;while (current!=NULL){printf ("%-4d",current->data);current=current->next;}printf ("\n");return;}

#include "Slink.h"
#include <stdlib.h>
#include <stdio.h>/*测试接口*/
int main(void){Slink *mslink=NULL;ElemType a;int m=10;mslink=CreateSlink (m);printf ("length:%d\n",GetLSlink (mslink));PrintSlink (mslink);InsertSlink (mslink,2,100);PrintSlink (mslink);DeleteSlink (mslink,4,&a);PrintSlink (mslink);system ("pause");return 0;}