本文共 3292 字，大约阅读时间需要 10 分钟。

1.线性表的定义

线性表是最简单、最基本的一种线性结构，通常采用顺序存储和链式存储，主要的基本操作是插入、删除和查找。

1)、一个线性表是n(n>=0)个元素的有限序列

2)、非空线性表中，除第一个元素外，序列中每个元素都只有一个直接前驱，除最后一个元素外，序列中每个元素均只有一个直接后继。

2.线性表的存储结构

1)、顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

①优点：随机存取表中的元素

②缺点：插入和删除操作需要移动元素

   插入前需要移动元素以挪出空的存储单元，然后再插入元素；

   删除时同样需要移动元素，以填充被删除的元素空出来的存储单元

③初始化：

const int MAX_SIZE = 100;//学生结构体typedef struct{    int id;   //学生id    char name[20];   //学生姓名  }Student;//线性表类class SeqList{public:    SeqList();    ~SeqList();public:    void init();                         //初始化    void insert(Student &t,int index);   //插入    Student del(int index);              //删除    Student findStudent(int index);      //按位查找    int  findIndex(Student s);           //按值查找private:     int m_length;                        //长度    Student m_student[MAX_SIZE];         //顺序表使用数组实现};void SeqList::init(){    m_length = 0;}

④查找 

//按位查找    Student findStudent(int index){    if(index < 1 || index > m_length)    {        throw "数组越界";    }    else    {        return m_student[index-1];    }}//按值查找int  findIndex(Student s){    for(int i=0;i

⑤插入

//插入，前面的元素往后移动一个位置void insert(Student &t,int index){    if(m_length >= MAX_SIZE || index < 1 || index > m_length+1)     {        throw "数组越界";    }    for(int i = m_length;i >= index;i--)    {        m_student[i] = m_student[i-1];    }    m_student[index-1] = t;    m_length++;}

⑥删除

//删除,后面的元素往前移动Student del(int index){    Student stu;    if(m_length == 0)    {        throw "异常";    }    if(index < 1 || index > m_length)    {        throw "位置异常";    }    stu = m_student[index - 1];    for(int j = index;j < m_length;j++)    {        m_student[j-1] = m_student[j];    }    m_length--;    return stu;}

2)、链式存储：通过指针链接起来的结点来存储数据元素，数据域用于存储数据元素的值，指针域则存储当前元素的直接后继的位置信息。

①优点：插入和删除快捷，地址并不要求是连续的，结点空间只有在需要的时候才申请，无需事先分配。

②缺点：不能对数据元素进行随机访问。

③查找

//head为带头结点单链表头指针，key为查找第key个元素LinkList Find(LinkList head,int key){    LinkList P;    int i = 1;    p = head->next;    while(p && i < key)    {        p = p->next;        i++;    }    if(p && i == key)    {        return p;    }    return NULL;}

④插入

基本步骤如下：

（1）s->next = p->next;

（2）p->next = s;

//head为带头结点单链表头指针//Key为插入第K个元素之前//newElem插入的元素int Insert(LinkList head, int key, int newElem){    LinkList p,s;                //临时指针    if(key == 1)    {        p = head;    }    else    {        p = Find(head,key-1);    }    if(!p)    {        return -1;    }    s = (Node*)malloc(sizeof(Node));    if(!s)    {        return -1;    }    s->data = newElem;    s->next = p->next;    p->next = s;    return 0;}

⑤删除

基本步骤如下：

（1）q = p->next;

（2）p->next = p->next->next;

（3）free(q);

//head为带头结点单链表头指针//Key为删除第Key个元素int Delete(LinkList head,int key){    LinkList p,q;    if(key == 1)    {        p = head;    }    else    {        p = Find(head,key-1);    }    if(!p || !p->next)    {        return -1;    }        q = p->next;    p->next = q->next;    free(q);    return 0;}

3)、其他几种链表结构

①双向链表：每个结点包含两个指针，分别指向当前元素的直接前驱和直接后继。其特别是可以从表中任意结点出发，从两个方向上遍历链表。

（1）插入

     基本步骤如下：

     1.s->front = p->front;

     2.p->front->next = s;

     3.s->next = p;

     4.p->front = s;

（2）删除

     基本步骤如下：

     1.p->front->next = p->next;

     2.p->next->front = p->front;

     3.free(p);

②循环链表：在单链表的基础上令表尾结点的指针指向链表的第一个结点，构成循环链表，其特点是可以从表中任意结点开始遍历整个链表。

③静态链表：借助数组来描述线性表的链式存储结构，用数组元素的下标表示元素所在结点的指针。