Written with StackEdit中文版.

顺序表

简介

顺序表是线性表的顺序表示，指的是用一组地址连续的存储单元依次存储线性表的数据元素。在C语言中，通常使用动态分配的一维数组来表示这种顺序存储结构。

声明与定义

1
2
3
4
5
6
7
8
9
10
11
12
#define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量
#define LISTINCREMMENT 10  //线性表存储空间的分配增量
#define OK 1
typedef  int ElemType;
typedef  int Status;

typedef struct
{
  ElemType* elem;    //存储空间基地址
  int length;        //长度
  int listsize;      //当前分配的存储容量（以sizeof(ElemType)为单位）
}SqList;

相关方法

构造一个空顺序表L

1
2
3
4
5
6
7
8
9
Status InitList_Sq(SqList *L) {
  L->elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
  if (!L->elem) {
    exit(-1); //存储分配失败
  }
  L->length = 0; //空表长度为0
  L->listsize = LIST_INIT_SIZE; //初始存储容量
  return OK;
}

向顺序表L手动输入n个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Status PushList_Sq(SqList *L, int n){
  printf("开始输入%d个数字\n", n);
  for (int i = 0; i < n; i++)
  {
    if (L->length >= L->listsize){  //当前存储空间已满，增加分配
      ElemType* newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMMENT) * sizeof(ElemType));
      if (!newbase){
        exit(-1); //存储分配失败
      }
      L->elem = newbase; //新基址
      L->listsize += LISTINCREMMENT; //增加存储容量
    }
    scanf_s("%d", &L->elem[i]);//输入元素 把指针L转为地址
    L->length++;
    printf("已输入%d个数字\n", i + 1);
  }
  return OK;
}

在顺序表L中第i个位置插入新的元素e

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Status ListInsert_Sq(SqList *L, int i, ElemType e){
  if (i < 1 || i > L->length + 1){//检测i值是否合法
    printf("插入的位置不合法！\n");
    return 0;
  }
  if (L->length >= L->listsize){  //当前存储空间已满，增加分配
    ElemType* newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMMENT) * sizeof(ElemType));
    if (!newbase){
      exit(-1); //存储分配失败
    }
    L->elem = newbase; //新基址
    L->listsize += LISTINCREMMENT; //增加存储容量
  }

  ElemType* q = &L->elem[i - 1];//q为插入位置
  for (ElemType* p = &(L->elem[L->length - 1]); p >= q; --p){//插入位置以及之后的元素右移
    *(p + 1) = *p;
  }
  L->length++;
  *q = e;
  return OK;
}

在顺序表L中删除第i个元素e,并用e返回其值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status ListDelete_Sq(SqList *L, int i,ElemType *e){
  if (i < 1 || i > L->length){ //i值是否合法
    printf("删除的位置不合法！\n");
    return 0;
  }
  ElemType* p = &L->elem[i - 1];//指针p指向被删除元素所在的地址
  *e = *p;//赋值删除元素
  ElemType* q = &(L->elem[L->length - 1]);//指针q指向表尾元素所在的位置
  for (++p; p <= q; ++p){ //被删除元素之后的元素左移
    *(p - 1) = *p;
  }
  L->length--;//表长减1
  return OK;
}

返回顺序表的第i个元素

1
2
3
4
5
6
7
8
Status GetElem(SqList L, int i,ElemType* e){ //不作修改，只传入表的副本就行
  if (i < 1 || i > L.length + 1){
    printf("获取位置不合法！\n");
    return 0;
  }
  *e = L.elem[i - 1]; //注意是用参数接值
  return OK;
}

一个用于比较元素是否相等的函数，被用于表达式的布尔值判断

1
2
3
4
5
6
7
8
Status compareElem(ElemType a, ElemType b) {
  if (a == b) {
    return OK; //OK == 1
  }
  else {
    return 0;
  }
}

在顺序表L中查找第1个与值e满足函数指针compare的元素的位序,若找到，返回其在L中的位序；否则返回0

1
2
3
4
5
6
7
int LocateElem_Sq(SqList L, ElemType e,Status (*compare) (ElemType,ElemType)){
  int i = 1; //i的初值为第一个元素的位序
  ElemType* p = L.elem; //指针p指向第一个元素的存储位置
  while ((i <= L.length) && !(*compare)(*p++,e))++i;
  if (i <= L.length)return i;
  else return 0;
}

对元素按值非递减排序的两个顺序表La和Lb归并成新按值非递减排序的顺序表Lc

时间复杂度为La和Lb两表长之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void MergeList_Sq(SqList La, SqList Lb,SqList* Lc) {
  //La、Lb都是值传递，Lc是指针传递
  ElemType* pa = La.elem, * pb = Lb.elem;
  Lc->listsize = Lc->length = La.length + Lb.length;
  ElemType* pc = Lc->elem = (ElemType*)malloc(Lc->listsize * sizeof(ElemType));
  if (!Lc->elem){
    printf("存储分配失败！\n");
    exit(-1);
  }
  ElemType* pa_last = La.elem + La.length - 1;//La表尾元素所在的位置
  ElemType* pb_last = Lb.elem + Lb.length - 1;//Lb表尾元素所在的位置

  while (pa <= pa_last && pb <= pb_last){//归并
    if (*pa <= *pb){
      *pc++ = *pa++;
    }
    else *pc++ = *pb++;
  }
  while (pa <= pa_last)*pc++ = *pa++; //插入La的剩余元素
  while (pb <= pb_last)*pc++ = *pb++; //插入Lb的剩余元素
}

遍历顺序表L的所有元素

1
2
3
4
5
6
7
8
9
Status ListTraverse(SqList L){
  printf("该表的长度为%d\n", L.length);
  printf("该表的元素有：\n");
  for (int i = 0; i < L.length; i++){
    printf("%d ", L.elem[i]);
  }
  printf("\n");
  return OK;
}

方法测试

1
2
3
4
5
6
7
8
9
int main(void){
  SqList MyList;
  InitList_Sq(&MyList); //传递SqList类型的指针 必须要&号表示传递指针，如果用SqList *MyList构造，传递MyList相当于把指针副本传递给函数
  printf("创建顺序表MyList的存储空间大小为%d\n",MyList.listsize);
  //非常容易混淆的点，传参需要修改参数时是需要用指针传递，
  //但不是指针的副本传递，
  //同样更不是把指针的指针传递过去
  //& 是地址或变量转指针符号
  //* 是地址或指针取值符号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
  //往MyList中放入n个数字并调用ListTraverse打印其长度和整个表的元素
  int num = 0;
  printf("需要往顺序表里放几个数字？");
  scanf_s("%d", &num);
  PushList_Sq(&MyList, num);
  ListTraverse(MyList);

  //往MyList的第几个位置插入什么数字最后打印
  int pos = 0;
  ElemType e;
  printf("需要往顺序表的第几个位置放元素?\n");
  scanf_s("%d", &pos);
  printf("需要放置的元素是?\n");
  scanf_s("%d", &e);
  ListInsert_Sq(&MyList, pos, e);
  ListTraverse(MyList);

  //删除MyList的第几个位置的元素，并打印被删除元素的值
  pos = 0;
  e = NULL;
  printf("需要删除顺序表的第几个元素?\n");
  scanf_s("%d", &pos);
  ListDelete_Sq(&MyList, pos, &e);
  printf("被删除的元素是：%d\n", e);
  ListTraverse(MyList);

  //返回MyList的第几个位置的元素，并打印其值
  printf("需要返回顺序表的第几个元素?\n");
  scanf_s("%d", &pos);
  GetElem(MyList, pos, &e);
  printf("第%d位的元素是：%d\n", pos,e);

  //测试LocateElem_Sq
  Status(*compare)(ElemType, ElemType);
  compare = compareElem;
  printf("输入需要查找的元素\n");
  scanf_s("%d", &e);
  printf("所找的元素%d,在表中的位置是第%d个\n",e,LocateElem_Sq(MyList, e, compare));

  //新建另一个顺序表
  SqList MyList2;
  InitList_Sq(&MyList2);
  //同第一步
  num = 0;
  printf("新建一个顺序表\n");
  printf("需要往顺序表里放几个数字？");
  scanf_s("%d", &num);
  PushList_Sq(&MyList2, num);
  ListTraverse(MyList2);

  //再新建一个顺序表用于存储上面两个顺序表（必须非递减排序的元素）的归并
  SqList MyNewList;
  printf("这一步上面两个顺序表必须是非递减排序的，下面输出两顺序表的归并：\n");
  InitList_Sq(&MyNewList);
  MergeList_Sq(MyList, MyList2, &MyNewList);
  ListTraverse(MyList);
  ListTraverse(MyList2);
  ListTraverse(MyNewList);
  return 0;
}