数组定义

数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。

数组是作为线性表中最具有代表性之一的逻辑结构，我们可以使用顺序存储和链式存储的方法来实现数组。本文将以笔者的视角来实现这两种存储方式的数组。不过在实现之前，读者不妨回忆一下数组相关的操作，以及对应操作的时间复杂度和空间复杂度。同时，有一个非常有意思的现象，那就是为什么数组都是从 0 开始编号，而不是从 1 开始编号呢？

关于数组的概念，首先要明确的是线性表，线性表顾名思义，就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列和栈也都是线性表结构。

数组的顺序存储和链式存储 - 图1

而与之相对立的概念是 非线性表。如二叉树、堆、图等数据结构，在非线性表中，数据之间并不是简单的前后关系。

数组的顺序存储和链式存储 - 图2

数组还有一个显著的特点：连续的内存空间和相同类型的数据。正是这些限制，让数组具有 随机访问 的特性。
但有利就有弊，由于这种特性，针对数组的插入，删除操作，为了保证连续性，需要做大量的数据搬移工作。
数组的寻址公式如下:

  1. // data_type_size 表示数组中每个元素的大小
  2. a[i]_address = base_address + i * data_type_size

面试的时候，常常会问数组和链表的区别，很多人都回答说，“链表适合插入、删除，时间复杂度 O(1)；数组适合查找，查找时间复杂度为 O(1)”。实际上，这种表述是不准确的。数组是适合查找操作，但是查找的时间复杂度并不为 O(1)。即便是排好序的数组，你用二分查找，时间复杂度也是 O(logn)。所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

数组的顺序存储实现

在使用顺序存储结构实现数组之前，我们需要做一些准备工作。

  • 定义数组中元素的类型
  • 定义函数结果状态代码
  • 定义顺序存储的数组的结构体

代码如下:

  1. #define MAXSIZE 100
  2. #define OK 1
  3. #define ERROR 0
  4. #define TRUE 1
  5. #define FALSE 0
  7. /* ElemType类型根据实际情况而定，这里假设为int */
  8. typedef int ElemType;
  9. /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
  10. typedef int Status;
  12. /*线性结构使用顺序表的方式存储*/
  14. //顺序表结构设计
  15. typedef struct {
  16.     ElemType *data;
  17.     int length;
  18. }Sqlist;

这里我们使用的是 int 类型的指针来存储数据

初始化一个空的数组

初始化空的顺序表可以分解为以下几步：

  • 为顺序表分配一个大小为 MAXSIZE 的数据空间
  • 如果分配失败，则退出
  • 如果分配成功，将 length 属性置为 0
  1. //1.1 顺序表初始化
  2. Status InitList(Sqlist *L)
  3. {
  4.     //为顺序表分配一个大小为MAXSIZE 的数组空间
  5.     L->data =  malloc(sizeof(ElemType) * MAXSIZE);
  6.     //存储分配失败退出
  7.     if(!L->data) exit(ERROR);
  8.     //空表长度为0
  9.     L->length = 0;
  10.     return OK;
  11. }

数组的插入

顺序表的插入操作我们需要考虑一些边界值情况，具体步骤如下：

  • 要插入的位置如果小于 1，(注意这里我们在插入和删除的时候，传入的位置最小为 1，而不是为 0)，或大于顺序表的 length 加 一，则说明插入位置非法，返回 ERROR
  • 如果顺序表的存储空间已满，则返回 ERROR
  • 判断插入的位置是否在最后一个位置，如果在，则直接赋值；如果不在，则需要从最后一个元素开始往前遍历，直到遍历到要插入的位置，在遍历过程中将遍历到的元素往后移动一个位置
  • 顺序表的长度加一
  1. //1.2 顺序表的插入
  2. /*
  3.  初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
  4.  操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
  5.  */
  6. Status ListInsert(Sqlist *L,int i,ElemType e){
  8.     //i值不合法判断
  9.     if((i<1) || (i>L->length+1)) return ERROR;
  10.     //存储空间已满
  11.     if(L->length == MAXSIZE) return ERROR;
  13.     //插入数据不在表尾,则先移动出空余位置
  14.     if(i <= L->length){
  15.         for(int j = L->length-1; j>=i-1;j--){
  17.             //插入位置以及之后的位置后移动1位
  18.             L->data[j+1] = L->data[j];
  19.         }
  20.     }
  22.     //将新元素e 放入第i个位置上
  23.     L->data[i-1] = e;
  24.     //长度+1;
  25.     ++L->length;
  27.     return OK;
  28. }

数组的取值

相比于顺序表的插入，取值的下边界不变，仍然是 位置 1（在数组中为0），而上边界变为数组长度(在数组中为数组长度减一)。

  1. //1.3 顺序表的取值
  2. Status GetElem(Sqlist L,int i, ElemType *e){
  3.     //判断i值是否合理, 若不合理,返回ERROR
  4.     if(i<1 || i > L.length) return  ERROR;
  5.     //data[i-1]单元存储第i个数据元素.
  6.     *e = L.data[i-1];
  7.     return OK;
  8. }

数组的删除

跟顺序表的插入相比，顺序表的删除操作也分为以下的步骤：

  • 判断顺序表是否为空，如果为空，则返回 ERROR
  • 判断要删除的位置是否合法，而这个位置的上边界和下边界显然和线性表的取值中的判断一致
  • 从要删除的位置开始，一直遍历到顺序表的最后一个元素的位置。接着把遍历到的每个元素位置往前移动一位
  • 顺序表的 length 减一
  1. //1.4 顺序表删除
  2. /*
  3.  初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
  4.  操作结果: 删除L的第i个数据元素,L的长度减1
  5.  */
  6. Status ListDelete(Sqlist *L,int i){
  8.     //线性表为空
  9.     if(L->length == 0) return ERROR;
  11.     //i值不合法判断
  12.     if((i<1) || (i>L->length)) return ERROR;
  14.     // 最后被删除的其实是 L->data[i - 1] 
  15.     for(int j = i; j < L->length;j++){
  16.         //被删除元素之后的元素向前移动
  17.         L->data[j-1] = L->data[j];
  18.     }
  19.     //表长度-1;
  20.     L->length --;
  22.     return OK;
  24. }

清空数组

因为顺序表是连续的内存空间，所以清空一个数组只需要将 length 置为 0 即可，并不需要去释放内存空间。

  1. //1.5 清空顺序表
  2. /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
  3. Status ClearList(Sqlist *L)
  4. {
  5.     L->length=0;
  6.     return OK;
  7. }

判断数组是否为空

判断数组是否为空也比较简单，只需要判断 length 是否为 0 即可。

  1. //1.6 判断顺序表清空
  2. /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
  3. Status ListEmpty(Sqlist L)
  4. {
  5.     if(L.length==0)
  6.         return TRUE;
  7.     else
  8.         return FALSE;
  9. }

获取数组的长度

这个就没什么说的了，直接返回 length 即可。

  1. //1.7 获取顺序表长度ListEmpty元素个数 */
  2. int ListLength(Sqlist L)
  3. {
  4.     return L.length;
  5. }

顺序输出数组

顺序输出线性表只需要循环一下就可以了。

  1. Status ListTraverse(SqList L)
  2. {
  3.     if (L.length == 0) return ERROR;
  5.     for (int i = 0;i < L.length;i++)
  6.     {
  7.         printf("%d ", L.data[i]);
  8.     }
  9.     printf("\n");
  10.     return OK;
  11. }

查找元素并返回位置

这里说的查找元素并返回位置的实现中，如果元素存在，分为两种情况，存在一个或多个，而最后返回的位置将以第一次出现的位置为准。

  1. //1.9 顺序表查找元素并返回位置
  2. /* 初始条件：顺序线性表L已存在 */
  3. /* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
  4. /* 若这样的数据元素不存在，则返回值为0 */
  5. int LocateElem(Sqlist L,ElemType e)
  6. {
  7.     int i;
  8.     if (L.length==0) return 0;
  10.     for(i=0;i<L.length;i++)
  11.     {
  12.         if (L.data[i]==e)
  13.             break;
  14.     }
  16.     if(i>=L.length) return 0;
  17.     return i+1;
  18. }

最后，我们来验证一下顺序表的实现:

  1. int main(int argc, const char * argv[]) {
  2.     Sqlist L;
  3.     Sqlist Lb;
  4.     ElemType e;
  5.     Status iStatus;
  7.     //1.1 顺序表初始化
  8.     iStatus = InitList(&L);
  9.     printf("初始化L后: L.Length = %d\n", L.length);
  11.     //1.2 顺序表数据插入
  12.     for(int j=1; j <= 5;j++){
  13.         iStatus = ListInsert(&L, 1, j);
  14.     }
  15.     printf("插入数据L长度: %d\n",L.length);
  17.     //1.3 顺序表取值
  18.     GetElem(L, 5, &e);
  19.     printf("顺序表L第5个元素的值为:%d\n",e);
  21.     //1.4 顺序表删除第2个元素
  22.     ListDelete(&L, 2);
  23.     printf("顺序表删除第%d元素,长度为%d\n",2,L.length);
  25.     //1.5 清空顺序表
  26.     iStatus = ClearList(&L);
  27.     printf("清空后,L.length = %d\n",L.length);
  29.     //1.6 判断List是否为空
  30.     iStatus=ListEmpty(L);
  31.     printf("L是否空：i=%d(1:是 0:否)\n",iStatus);
  33.     //1.8 TraverseList
  34.     for(int j=1; j <= 5;j++){
  35.         iStatus = ListInsert(&L, 1, j);
  36.     }
  37.     TraverseList(L);
  40.     return 0;
  41. }

输出如下:

  1. 初始化L后: L.Length = 0
  2. 插入数据L长度: 5
  3. 顺序表L第5个元素的值为:1
  4. 顺序表删除第2元素,长度为4
  5. 清空后,L.length = 0
  6. L是否空：i=1(1:是 0:否)

数组的链式存储实现

链式存储的线性表需要定义如下的结构体:

  1. /*线性结构使用链表的方式存储*/
  2. typedef struct ListNode
  3. {
  4.     struct ListNode *next;
  5.     ElemType data;
  6. }ListNode, *LinkList;

初始化一个空的数组

初始化空的链式表很简单，申请一个内存空间赋值给传入的指针变量。让后将指针变量的 next 指针域指向空指针 NULL。

  1. // 1.链式线性表的初始化
  2. Status InitList(LinkList *L)
  3. {
  4.     *L = (LinkList)malloc(sizeof(ListNode));
  5.     if (*L == NULL) return ERROR;
  6.     (*L)->next = NULL;
  7.     return OK;
  8. }

数组的插入

链式表的插入分为以下的步骤:

  • 通过循环遍历找到要插入位置的前一个结点
  • 判断前一个结点是否为空，如果为空，则插入失败
  • 开辟内存声明一个临时结点，然后将传入的值赋值给临时结点的数据域
  • 让临时结点的next指针域指向要插入结点位置的前一个结点的next指针指向的内存空间
  • 让插入结点位置的前一个结点的next指针指向临时结点
  1. // 2.链式线性表的插入
  2. Status InsertList(LinkList *L, int i, ElemType e)
  3. {
  4.     LinkList temp, p;
  5.     p = *L;
  6.     int count = 1;
  7.     while(p && count < i)
  8.     {
  9.         count++;
  10.         p = p->next;
  11.     }
  13.     if (!p || count > i) return ERROR;
  15.     temp = (LinkList)malloc(sizeof(ListNode));
  16.     if (temp == NULL) return ERROR;
  17.     temp->data = e;
  18.     temp->next = p->next;
  19.     p->next = temp;
  21.     return OK;
  22. }

线性表的取值

线性表的取值步骤如下:

  • 先声明一个局部指针变量指向头结点的next指针
  • 然后循环遍历链表，判断当前遍历中的指针不为空且 j 小于 传入的位置 i，则循环继续
  1. Status GetElem(LinkList L, int i, ElemType *e)
  2. {
  3.     LinkList p = L->next;
  4.     int j = 1;
  5.     while (p && j < i) {
  6.         p = p->next;
  7.         j++;
  8.     }
  9.     if (!p || j > i) return ERROR;
  10.     *e = p->data;
  11.     return OK;
  12. }

线性表的删除

线性表的删除步骤如下:

  • 判断如果头结点后没有其他节点，则返回 ERROR，因为空的链表执行删除操作没有意义
  • 通过循环遍历找到要删除结点的前一个结点
  • 声明一个临时指针变量指向要删除的结点
  • 取出要删除结点中数据域的值赋值给传入的数据指针变量
  • 让待删除结点的前一个结点指向待删除结点的后一个结点
  • 释放掉待删除的结点
  1. // 链式线性表的删除
  2. Status ListDelete(LinkList *L, int i, ElemType *e)
  3. {
  4.     // 如果头结点的next指向NULL，则没有删除的意义
  5.     if ((*L)->next == NULL) return ERROR;
  7.     // 通过遍历找到要删除位置的前一个位置的结点
  8.     LinkList p = (*L)->next;
  9.     int j = 1;
  10.     while (p && j < (i - 1)) {
  11.         p = p->next;
  12.         j++;
  13.     }
  14.     //当i>n 或者 i<1 时,删除位置不合理
  15.     if (!(p->next) || j > (i - 1)) return ERROR;
  17.     // 声明一个temp指针指向要删除的结点
  18.     LinkList temp = p->next;
  19.     *e = temp->data;
  20.     // 让前一个结点指向temp指针指向的下一个结点
  21.     p->next = temp->next;
  22.     // 释放掉temp指针指向的内存空间
  23.     free(temp);
  25.     return OK;
  26. }

清空线性表

清空线性表比较简单，我们只需要先拿到头结点指向的下一结点，然后基于此结点开始循环遍历，然后每次用一个局部变量指针接收当前迭代的结点，然后让当前迭代结点继续前进，接着释放掉局部变量指针指向的内存空间。循环结束后，将头结点的next指针域置空即可。

  1. // 清空链式线性表
  2. Status ClearList(LinkList *L)
  3. {
  4.     LinkList p = (*L)->next;
  5.     LinkList q;
  6.     while(p) {
  7.         q = p;
  8.         p = p->next;
  9.         free(q);
  10.     }
  11.     (*L)->next = NULL;
  12.     return OK;
  13. }

线性表是否为空

只需要判断头结点的next指针是否为空即可。

  1. // 链式线性表是否为空
  2. Status ListEmpty(LinkList L)
  3. {
  4.     if (L->next == NULL) return TRUE;
  5.     else return FALSE;
  6. }

获取线性表的长度

通过一个局部变量 i 来记录线性表的长度即可。注意，这个长度并不包括头结点。

  1. // 链式线性表的长度
  2. int ListLength(LinkList L)
  3. {
  4.     int i = 0;
  5.     LinkList p = L->next;
  6.     while (p)
  7.     {
  8.         p = p->next;
  9.         i++;
  10.     }
  11.     return i;
  12. }

线性表的遍历

直接循环遍历即可。

  1. // 链式线性表的遍历
  2. Status ListTraverse(LinkList L)
  3. {
  4.     LinkList p = L->next;
  5.     while (p) {
  6.         printf("%d ", p->data);
  7.         p = p->next;
  8.     }
  9.     printf("\n");
  10.     return OK;
  11. }

头插法创建线性表

头插法顾名思义就是一直在链表的头部插入数据，逻辑十分简单，代码如下：

  1. // 前插法创建单链表
  2. void CreateListHead(LinkList *L, int n)
  3. {
  4.     // 如果头结点为空创建头结点
  5.     if (*L == NULL) {
  6.         *L = (LinkList)malloc(sizeof(ListNode));
  7.         if (*L == NULL) return ERROR;
  8.         (*L)->next = NULL;
  9.     }
  11.     // 然后循环往头结点后面插入新的结点
  12.     for (int i = 0;i < n;i++) {
  13.         // 创建新结点
  14.         LinkList tempNode = (LinkList)malloc(sizeof(ListNode));
  15.         tempNode->data = i;
  16.         tempNode->next = (*L)->next;
  17.         (*L)->next = tempNode;
  18.     }
  19. }

后插法创建线性表

尾插法顾名思义就是一直在链表的尾部插入数据，和头插法的区别在于，最后要记得把尾指针的next置空。

  1. // 尾插法创建单链表
  2. void CreateListTail(LinkList *L, int n)
  3. {
  4.     // 如果头结点为空创建头结点
  5.     if (*L == NULL) {
  6.         *L = (LinkList)malloc(sizeof(ListNode));
  7.         if (*L == NULL) return ERROR;
  8.         (*L)->next = NULL;
  9.     }
  10.     LinkList tail = (*L);
  11.     LinkList p;
  12.     for (int i = 0;i < n;i++) {
  13.         p = (LinkList)malloc(sizeof(ListNode));
  14.         p->data = i;
  15.         tail->next = p;
  16.         tail = p;
  17.     }
  18.     tail->next = NULL;
  19. }

最后，我们来验证一下链式存储的线性表实现:

  1. int main()
  2. {
  3.     LinkList L;
  4.     Status status;
  5.     ElemType e;
  6.     status = InitList(&L);
  7.     printf("链式线性表初始化结果(1为成功，0为失败): %d\n", status);
  8.     printf("链式线性表插入10个元素:\n");
  9.     for(int i = 1;i <= 10;i++)
  10.     {
  11.         InsertList(&L, 1, i);
  12.     }
  13.     printf("链式线性表遍历\n");
  14.     ListTraverse(L);
  15.     printf("链式线性表长度为:%d\n", ListLength(L));
  16.     GetElem(L, 10, &e);
  17.     printf("链式线性表第10个元素值为%d\n", e);
  18.     printf("链式线性表中 1 的位置为%d\n", LocateElem(L, 1));
  19.     printf("链式线性表中 5 的位置为%d\n", LocateElem(L, 5));
  20.     ListDelete(&L, 3, &e);
  21.     printf("链式线性表删除第3个元素值为%d\n", e);
  22.     printf("链式线性表长度为:%d\n", ListLength(L));
  23.     printf("链式线性表遍历\n");
  24.     ListTraverse(L);
  25.     printf("清空链式线性表\n");
  26.     ClearList(&L);
  27.     printf("链式线性表长度为:%d\n", ListLength(L));
  28.     printf("链式线性表遍历\n");
  29.     ListTraverse(L);
  30.     status=ListEmpty(L);
  31.     printf("L是否空：i=%d(1:是 0:否)\n",status);
  32.     printf("头插法创建单链表\n");
  33.     CreateListHead(&L, 20);
  34.     printf("链式线性表遍历\n");
  35.     ListTraverse(L);
  36.     ClearList(&L);
  37.     printf("链式线性表长度为:%d\n", ListLength(L));
  38.     printf("链式线性表遍历\n");
  39.     printf("尾插法创建单链表\n");
  40.     CreateListTail(&L, 20);
  41.     printf("链式线性表遍历\n");
  42.     ListTraverse(L);
  43.     return 0;
  44. }

打印如下:

链式线性表初始化结果(1为成功，0为失败): 1
链式线性表插入10个元素:
链式线性表遍历
10 9 8 7 6 5 4 3 2 1
链式线性表长度为:10
链式线性表第10个元素值为1
链式线性表中 1 的位置为10
链式线性表中 5 的位置为6
链式线性表删除第3个元素值为8
链式线性表长度为:9
链式线性表遍历
10 9 7 6 5 4 3 2 1
清空链式线性表
链式线性表长度为:0
链式线性表遍历

L是否空：i=1(1:是 0:否)
头插法创建单链表
链式线性表遍历
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
链式线性表长度为:0
链式线性表遍历
尾插法创建单链表
链式线性表遍历
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19