1.定义:

线性表表示0个或者多个数据元素的有限序列

线性表的特性有:

除第一个元素外,每一个元素均有一个直接前驱

出最后一个元素外,每一个元素均有一个直接后继

2.线性表抽象数据类型

ADT List

Data

         /*线性表的数据对象集合为｛a1,a2,...,an｝,每个元素的类型均为DataType.其中，除第一个元素a1外，

  每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。

  数据元素直接是一对一的关系。*/

Operation

         InitList(*L);//初始化操作，建立一个空的线性表

         ListEmpty(L);//若线性表为空，返回true,否则返回false

         ClearList(*L);//清空线性表

         GetElem(L,i,*e);//查找线性表中的第i个位置的元素值，并赋值给e

         LocateElem(L,e);//查找线性表L中与给定值e相等的元素，如果查找成功，则返回第一个相同的元素在L

                       //中的下标；否则，返回0表示失败

         ListInsert(*L,i,e);//在线性表L的第i个位置插入元素e

         ListDelete(*L,i,*e);//删除线性表L中第i个位置元素，并用e返回其值

         ListLength();//返回线性表L的长度

end ADT




实现线性表La和线性表Lb的并集操作，结果保存在La中的伪代码如下所示：


//实现线性表La和线性表Lb的并集操作，结果保存在La中
        void UnionList(*La,Lb)
{
        //计算Lb长度
        int lblength = ListLength(Lb);
        //计算La长度
        int laLength = ListLength(La);
        int i ;
        //便利Lb中所有元素，判断其是否在La中，若不在，则插入La中
        for (i=0;i<length;i++)
        {
                ElemType temp = GetElem(Lb,i,*e);
                if (LocateElem(La,temp)==0)
                {
                        ListInsert(La,++laLength,temp);
                }
        }
}

3.顺序存储结构

3.1顺序存储结构的定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

3.2 数据结构

//线性表的顺序存储结构
#define MAXSIZE 20;//存储空间初始分配量为20
typedef int ElemType;//数据类型为int
type struct
{
        ElemType data[MAXSIZE];//数组存储数据元素
        intlength;//线性表长度
};

3.3 数组长度与线性表长度的区别

数组的长度是存放线性表的存储空间的长度，存储空间分配后这个量一般是不变的。

线性表的长度是线性表中数据元素的个数，随着线性表的插入和删除，这个量是变化的。

3.4 地址计算方法

由于顺序存储结构是按照顺序存储的，所以每个数据元素的地址都可以根据第一个元素的地址推算出来。

LOC(ai) = LOC(a1)+ (i-1)*c



4.顺序存储结构的操作

4.1 获取元素操作

//////////////////////////////////////////////////////////////////////////
//获取顺序链表中第i个元素，并赋值给e
int GetElem(SqList L,int i, ElemType * e)
{
        //线性表长度等于0或者获取元素位置错误返回0
        if (L.Length == 0 || i < 0 || i > L.Length)
        {
                return 0;
        }

        返回第i个元素
        *e = L.data[i-1];
        return 1;
}

4.2插入操作

插入操作算法的思路是：
1.如果插入位置不合理，抛出异常.
2.如果线性表长度大于等于数组长度，则抛出异常或者增加数组长度
3.从最后一个元素开始像前便利到第i个位置，分别将它们像后移动一个位置

4.第i个元素位置插入e
5.表长度加1
//在线性表L的第i个位置插入元素e
int ListInsert(Sqlist *L, int i, ElemType e)
{
        //插入位置错误，返回0
        if (i < 0 || i > L.Length)
        {
                return 0;
        }

        //线性表的长度大于等于数组的最大长度，返回0
        if (L.Length >= MAXSIZE)
        {
                return 0;
        }

        int j = L.Length -1;
        //从第i个元素到最后一个元素，每个元素后移一位
        while (j >= i)
         {
                 L.data[j+1] = L.data[j];
                 j--;
         }

        //第i个元素的位置放入e
        L.data = e;

        //线性表长度加1
        L.Length ++;

}
5.3 线性表删除

删除操作的思路是：
1.如果删除位置不合理，抛出异常
2.取出删除元素
3.从删除位置开始遍历到最后一个元素，分别将她们都向前移动一个位置
4.表长减1

//线性表删除操作
int ListDelete(SqList *L,int i,ElemType *e)
{
        //如果删除的位置不对，则返回0
        if (i < 0 || i > L.Length -1)
        {
                return 0;
        }
       
        *e = L.data[i-1];

        for (j = i-1;i <L.Length-2;j++ )
        {
                L.data[j] = L.data[j+1];
        }

        L.Length --;
        return 1;

}

5.4 线性表存储结构的优缺点


6.线性表的链式存储结构

针对线性表的先行存储结构的不足，提出了线性表的链式存储结构
线性表的链式存储结构的数据结构：
typedef struct Node
{
        ElemType data;
        struct Node *next;
} Node;
typedef struct Node *LinkList;

6.1 单链表的读取
获得链表第i个数据的算法思路是：
1.声明一个节点p指向链表第一个节点，初始化j从1开始
2.当j< i时，就遍历链表，让P的指针向后移动，不断指向下一个节点，j累加1
3.若到链表末尾p为空，则说明第i个元素不存在
4.否则查找成功，返回节点p的数据
int GetElem(LinkList L,int i,ElemType *e)
{
        int j;
        LinkList p;
        p = L->next;//p指向链表第一个节点
        while (p && j < i )
        {
                p = p->next;
                j++;
        }

        if(!p || count > i)
                return 0;
         
        *e = p->data;
        return 1;
}

6.2 单链表插入操作
插入操作的思路是：
1.声明一个节点p指向链表头结点，初始化j从1开始
2.当j<i,遍历链表，让p的指针像后移动，不断指向下一个节点，j累加1；
3.若到链表末尾p为空，则说明第i个元素不存在
4.否则查找成功，在系统中生成一个空节点s
5.将元素e赋值给s->data
6.将节点s插入单链表
7.返回成功

---------------------
【转载，仅作分享，侵删】
作者：longshengguoji
原文：https://blog.csdn.net/longshengguoji/article/details/9191913
版权声明：本文为博主原创文章，转载请附上博文链接！

奈斯，感谢分享！