期末复习 线性表的顺序存储（数据结构——用C语言描述)

线性表的顺序存储结构

线性表的顺序存储就是用一组连续的储存单元依次存储表中的各个元素。可将顺序表（顺序存储结构存储的线性表）归纳为：关系线性化，节点顺序化。

既然顺序表按顺序存储，那么我们就能轻易计算出任意一个数据元素的存储地址，达到对顺序表中数据元素随机存取的目的。

地址的计算不难，只要套用公式就好。
Loc(ai)=Loc(a1)+(i-1)*k.
其中，Loc(a1)为基地址，k是每个元素所占单元，那么（i-1)*k就是第i个元素前所有元素所占的单元。

然后，我们要怎么表示一下线性表顺序存储呢？
课本上是

#define MAXSIZE 100
typedef struct
{
  ElemType elem[MAXSIZE];
  int last;
}SeqList;

（现在才发现下面还有说明）
说明：
结点类型定义中 ElemType是为了描述统一而定的（为了方便），在实际中，用户可根据自己需要来定义，如int，char，float或struct。

线性表顺序存储结构上的基本运算

(敲一会，过过瘾)
1.查找操作

按内容查找

int Locate(SeqList L,ElemType e)
/*在顺序表L中找和e相同的元素，若是L.elem[i]=e,则找到该元素，并返回i+1，
找不到，返回-1*/
{
  i=0;
  while((i<=L.last)&&(L.elem[i]!=e)) //没扫描完，并且没找到的情况下
  i++;
  if(i<=L.last)
    return i+1;  //返回序号
  else
    return -1;
}   //时间复杂度O(n)

2.插入操作
在进行插入操作时，要把插入位置及其后面的元素依次后移（有点费劲），把位置腾出来，再把元素插入，若是在线性表末尾插入，则不用后移。

#define OK 1
#define ERROR 0
int InsList(SeqList *L ,int i,ElemType e)
{
//i的合法取值范围是1<=i<=L->last+2
//last为最后一个元素的下标值，i表示第i个元素，所以为L->last+2
int k;
if((i<1)||i>L->last+2)//判断位置（健壮性？)
{
  printf("插入位置i不合法")：
  return ERROR;
}
for(k=L->last;k>=i-1;k--)
  L->elem[k+1]=L->elem[k];
L->elem[i-1]=e;  //第i个元素下标为i-1；
L->last++;
return OK;
} 

3.删除操作
如果删除第i个元素，则要把其后的元素前移。

int DelList(SeqList *L,int i,ElemType *e)
{
//指针参数e返回其值
//i的合法取值范围1<=i<=L.last+1
int k;
if((i<1)||(i>L->last+1))
{
  printf("删除位置不合法！");
  return ERROR;
}
*e=L->elem[i-1];
for(k=i;k<=L->last;k++)
{
  L->elem[k-1]=L->elem[k];
}
L->last--;
return OK;
}

4.线性表的合并运算
建立空表LC，为使LC也为非递减有序排列，可用两指针i，j指向LA，LB中元素，若LA.elem[i]>Lb.elem[j],则将LB.elem[j]插入到表LC中，若LA.elem[i]<=Lb.elem[j]，则将LA.elem[i]插入表LC中，直到一个表被扫描完，再将未扫描完的表中剩余元素放到LC中。

void mergeList(SeqList *LA,SeqList *LB,SeqList *LC)
{
  int i,j,k,l;
  i=0;j=0;k=0;
  while(i<LA->last&&j<=LB->last)
  if(LA->elem[i]<=LB->elem[j])
  {
    LC->elem[k]=LA->elem[i];
    k++;i++;         //不太理解的话把i带入个数进去
  }
  else 
  {
     LC->elem[k]=LB->elem[j];
     k++;j++;
  }
  while(i<=LA->last)   //LA表有剩余时
  {
    LC->elem[k]=LA->elem[i];
    i++;k++;
  }
  while(j<=LB->last)     //LB表有剩余时
  {
    LC->elem[k]=LB->elem[j];
    j++;k++;
  }
  LC->last=LA->last+LB->last;
}

（想吃饭）
对于顺序表的基本知识我们已经了解了，最后我们看一下它的优缺点吧。
优点
1.无须为表示结点间的逻辑关系增加额外储存空间
2.方便随机存取表中任何一元素（地址计算）
缺点
1.插入或删除不方便，需要移动大量结点，效率较低。
2.表长变化较大时，难以确定合适的储存规模，可能造成空间浪费或者空间不足导致溢出。

 //看到这里了，给个赞吧