1.简介
线性结构用于描述数据元素之间的线性关系，即数据元素一个接一个的排列，主要用于描述具有单一前驱和后继的数据关系。线性表是一种线性结构，它有顺序存储和链式存储两种方法。线性表的链式存储用结点存储数据元素，元素结点可以连续，也可以不连续，因此，存储数据元素的同时必须存储元素的逻辑关系。结点的结构如下：
其中，前面为数据域，后面为指针域。若节点中只有一个指针域，则称为单链表（线链表）。在链式存储结构中，只需一个指针指向头一个结点，就可以顺序访问表中任意元素。所以，引入一个不存储元素的结点，称为头结点，并令头指针指向该结点。
2.实例
2.1单链表的前置条件
struct Node //定义结点
{
int data; //数据域
Node *next; //指针域
};
class LinkList
{
public:
LinkList(int a[], int n); //建立有n个元素的单链表
int Length(); //求单链表长度
void PrintList(); //遍历单链表，按序号依次输出各元素
void Insert(int i, int x); //在单链表的指定位置插入指定数据
int Get(int i); //获取单链表指定位置的元素
private:
Node *first; //单链表的头指针
};
2.1单链表的创建
LinkList::LinkList(int a[], int n) //建立有n个元素的单链表
{
first = new Node; //申请头结点
first->next = NULL; //初始化一个空链表
for (int i = 0; i<n; i++)
{
Node *s;
s = new Node; //申请新结点
s->data = a[n-1-i]; //给结点数据域赋值
s->next = first->next; //这两句将新结点插入到前一个结点之前
first->next = s;
}
}
注：first->next=NULL；申请结点p，则p->next=NULL（语句一），first->next=p（语句二）；
first->next=p；申请结点t，则t->next=p（语句一），first->next=t（语句二）；
first->next=t；申请结点s，则s->next=t（语句一），first->next=s（语句二）；
最终，指针表示形式为：first->s->t->p->NULL.
2.2单链表的遍历
void LinkList::PrintList()
{
Node *p;
p = first->next; //结点p初始指向头结点的后继结点
while (p != NULL)
{
cout << p->data << " "; //输出对应结点的数据
p = p->next; //结点p变为p的后继结点
}
cout << endl;
}
2.3单链表的插入
void LinkList::Insert(int i, int x) //在第i个位置插入x
{
Node *p;
Node *s;
p = first; //设p为头结点
int count = 1;
while (p != NULL&&count<i )
{
p = p->next; //循环直至p为指定位置的前一个结点
count++;
}
if (p == NULL)throw"位置";
else {
s = new Node; //申请新结点
s->data = x; //为结点s的数据域赋值
s->next = p->next; //新结点的指针指向结点p的后继结点，即位置i上的结点
p->next = s; //原先位置i-1上的结点指针改为指向新结点
}
}
2.4单链表的查询
int LinkList::Get(int i) //获取第i个位置上的元素
{
Node *p;
p=first->next; //p初始为第一个结点
int count=1;
while(p!=NULL&&count<i)
{
p=p->next; //结点后移
count++;
}
if(p==NULL)throw"位置";
else
return p->data;
}
2.5单链表的长度
int LinkList:: Length( ) //获取单链表的长度
{
Node *p;
p=first->next;
int count=0;
while(p!=NULL)
{
p=p->next;
count++;
}
return count;
}
2.6主函数
void main( )
{
int r[5]={1, 9, 7, 2, 5};
LinkList L(r, 5);
cout<<"线性表的数据为："<<endl;
L.PrintList( );
cout<<endl;
cout<<"线性表的数据个数为："<<endl;
cout<<L.Length()<<endl;
cout<<"线性表的第四个数据为:"<<endl;
cout<<L.Get(4)<<endl;
cout<<"线性表的第二个位置插入4:"<<endl;
L.Insert(2,4);
L.PrintList();
}
原文：http://www.cnblogs.com/jfl-xx/p/4890116.html