X

曜彤.手记

随记,关于互联网技术、产品与创业

吉 ICP 备10004938号

数据结构 - 线性顺序表


顺序表就是指用一组连续的物理存储单元来存储表内的每个元素,使得表中相邻的元素在物理地址上也是相邻的。简单的讲,假如第一个元素在地址 0X00000000,且第一个元素占用了2个内存单元,而这时的第二个元素开头则处于地址 0X00000002,以此类推。假如线性表中有n个元素,每个元素占用 k 个单元,第一个元素的地址为 loc(a1),则第 n 个元素的地址为:loc(an) = loc(a1) + (n - 1) * k。

顺序表的存储结构可以用如下 C 语言代码来表示:

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

其中 ElemType 为顺序表内元素的类型。last 变量记录顺序表中最后一个元素在数组 elem[] 中的位置,空表为 -1。

顺序表常用操作 - 查找操作:

按序号查找很简单,只需要按照给出的所有返回对应的数组内容即可,这里我们给出的是按内容查找。即查找出与给定元素内容相同的元素在顺序表中的位置,L 为待查找顺序表,e 为待查找内容。

int Locate(SeqList L, ElemType e) {
  i = 0;
  while ((i <= L.last) && (L.elem[i] != e)) i ++;
  if (i <= L.last) {
    return(i + 1);
  } else {
    return -1;
  } 
}

顺序表常用操作 - 插入操作:

由于顺序表元素的在物理上的存储位置需要与逻辑顺序一致,所以当插入元素时需要将此元素所在位置的后续所有元素依次向后移动,才能保持物理和逻辑上的位置一致。而此时的顺序表长度也由原来的 n 变为 n+1。

#define OK 1
#define ERROR 0
int InsList(SeqList *L, int i, ElemType e) {
  int k;
  if ((i < 1) || (i > L -> last + 2)) {
    printf("插入位置i不合法!");
    return(ERROR);
  }
  if (L -> last >= MAXSIZE - 1) {
    printf("表已满无法插入!");
    return(ERROR);
  }
  for (k = L -> last; k <= i - 1; --k) L -> elem[k + 1] = L -> elem[k];
  L -> elem[i - 1] = e;
  L -> last++;
  return(OK);
}

顺序表常用操作 - 删除操作:

顺序的删除操作同样需要移动元素,且表长度也由原来的 n 变为 n-1,删除后返回删除元素的值。

#define ERROR 0
int DelList(SeqList *L, int i, ElemType *e) {
  int k;
  if ((i < 1) || (i > L -> last + 1)) {
    printf("删除位置i不合法!");
    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);
}


这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)