线性表

1.线性表的定义：由n(大于0)个具有相同类型的数据元素组成的有限序列，也简称为表。

2.线性表的逻辑结构：

　　　　线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。

3.线性表的特征：

1．集合中必存在唯一的一个“第一元素”。

2．集合中必存在唯一的一个 “最后元素” 。

3．除最后一个元素之外，均有唯一的后继(后件)。

4．除第一个元素之外，均有唯一的前驱(前件)。

 

4.顺序表：采用顺序存储的线性表称之为顺序表。

   使用顺序表存储集合 {1,2,3,4,5}，数据最终的存储状态如图 所示：

              

（1）线性表顺序存储的特点：

　　　　　　1.线性表中所有元素所占的存储空间是连续的。

　　　　　　2.线性表中各个数据元素在存储空间中是按逻辑顺序依次存放的。

   （2）地址计算方式：线性表L每个元素之间的地址存在下列关系：Loc（ai）=Loc（ai-1）+d,其中d表示线性表L中每个元素占用d个存储单位。

 由此可以推出公式：Loc（ai）=Loc（a1）+（i-1)*d。

以下代码实现以下线性表：

#include<stdio.h>
typedef struct
{
    int data[100];
    int length;
}List;
void GetElem(List l,int index) //查找某个位置的元素
{
    if(index<1||index>l.length)
      printf("索引错误！");
    else
    {
        printf("%d\n",l.data[index-1]);
    }

}
void Insert(List l,int index,int x) //插入
{
    int k;
    if(index<1||index>l.length)
    printf("插入位置错误");
    if(l.length>=101)
    printf("表已经满！！");
    if(index<=l.length)
    {
        for(k=l.length-1;k>=index-1;k--)
        l.data[k+1]=l.data[k];
    }
    l.data[index-1]=x;
    l.length++;
    for(int i=0;i<l.length;i++)
    printf("%d ",l.data[i]);
    printf("\n");
}
void Delete(List l,int index)   //删除
{
    int k;
    if(index<1||index>l.length)
    printf("删除的位置有误！");
    if(index<l.length)
    {
        for(k=index;k<l.length;k++)
        {
            l.data[k-1]=l.data[k];
        }
    }
    l.length--;
    for(int i=0;i<l.length;i++)
    printf("%d ",l.data[i]);
    printf("\n");
}
void replace(List l,int index ,int x)  //修改
{
     l.data[index-1]=x;
     for(int i=0;i<l.length;i++)
       printf("%d ",l.data[i]);

}
int main()
{
    List l;
    l.length=10;
    for(int i=0;i<l.length;i++)
      l.data[i]=i+1;
    GetElem(l,2);
    Delete(l,2);
    Insert(l,2,66);
    replace(l,2,99);
    // for(int i=0;i<l.length;i++)
    // printf("%d ",l.data[i]);
    // printf("\n");

}