线性表分为顺序表和链表，顺序表可以简单理解成“数组”，而链表又可以划分为动态链表和静态链表。
这里主要讲解动态、静态链表的数据结构和实现。
动态链表
动态链表是通过指针来连接位置的，所以其数据结构应该包含数据域和指针域，
可以定义如下：
struct node{ node *next; datatype data; };
定义完之后，需要创建链表和删除、插入结点下面就要介绍这几个函数，由于链表是动态的每开辟一个结点应该给它开辟一个空间，C++中用new 加数据类型就可以得到那片空间的指针，用delete又可以释放这片空间。
对于创建、删除、插入，其实主要是用好pre前指针，pre指向待操作结点的前一个结点，那么待操作结点、操作结点后一个结点也就找到了。
下面是部分代码：
创建：
node* create(datatype a[],int n){ //根据数组数据创建链表 node *p,*pre,*head; head=new node; head->next=NULL; pre=head; for(int i=0;i<n;i++){ p= new node; //开辟空间 p->data=a[i]; p->next=NULL; pre->next=p; pre=p; } return head; }
插入：
void insert(node* head,int pos,datatype x) { //在第pos个位置上插入X int count=pos-1; node *pre=head,*p; while(count){ pre=pre->next; count--; } p=new node; p->data=x; p->next=pre->next; pre->next=p; }
删除：
void del(node* head,datatype x){ //删除值为x的元素 node *pre=head,*temp; while(pre->next){ if(pre->next->data==x){ temp=pre->next; pre->next=temp->next; delete(temp); //释放空间 } pre=pre->next; } }
实际上解决实际问题，如果真的要创建链表，可能用静态链表比较快速。
静态链表
静态链表实质是用数组的下标代替了指针
结构如下
struct Node{ int next;//存放下一个结点的地址、数组下标 datatype data; }node[size];
这里取Node和node不同的名字是为了防止对结构体数组排序出现错误
其他应用同理思考。
最后附动态数据的实现结果
#include<iostream> using namespace std; typedef int datatype; struct node{ //链表结点结构 node *next; datatype data; }; node* create(datatype a[],int n){ //根据数组数据创建链表 node *p,*pre,*head; head=new node; head->next=NULL; pre=head; for(int i=0;i<n;i++){ p= new node; //开辟空间 p->data=a[i]; p->next=NULL; pre->next=p; pre=p; } return head; } void insert(node* head,int pos,datatype x) { //在第pos个位置上插入X int count=pos-1; node *pre=head,*p; while(count){ pre=pre->next; count--; } p=new node; p->data=x; p->next=pre->next; pre->next=p; } void del(node* head,datatype x){ //删除值为x的元素 node *pre=head,*temp; while(pre->next){ if(pre->next->data==x){ temp=pre->next; pre->next=temp->next; delete(temp); //释放空间 } pre=pre->next; } } int main(){ int a[5]={5,3,6,1,2}; node *L=create(a,5); node *p=L->next; del(L,6); insert(L,3,11); while(p) { cout<<p->data<<" " ; p=p->next; } return 0; }
结果
