数组

在计算机科学中，数组数据结构（英语：array data structure），简称数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。

最简单的数据结构类型是一维数组。例如，索引为0到9的32位整数数组，可作为在存储器地址2000，2004，2008，…2036中，存储10个变量，因此索引为i的元素即在存储器中的2000+4×i地址。数组第一个元素的存储器地址称为第一地址或基础地址。

二维数组，对应于数学上的矩阵概念，可表示为二维矩形格。例如： $a={\begin{bmatrix}3&6&2\0&1&-4\2&-1&0\end{bmatrix}}$ 而计算机编程中的数组看起来像这样，例如C语言中的数组：

int a[3][3] = {
   {3,  6,  2},
   {0,  1, -4},
   {2, -1,  0}
};

在某些情况下，“向量”一词也可能代表二维数组，虽然在数学意义上更确切地称呼为元组（tuple），而不是向量。但需要注意的是：计算机科学的某些领域，如Matlab，元组是指类似C语言struct类型，具有固定的往往是不同类型的数据成员的数据结构。

数组通常用于实现数据库的表格，特别是查询表；表格有时也被当作是数组的同义词。

数组是最早期和最重要的数据结构之一，很多程序都会用到数组。它们也用于实现许多其他数据结构，譬如列表（list）和字符串（string）。它们有成效地开展了计算机的定址逻辑。在大多数现代计算机和许多外部存储设备中，存储器如同一维数组，索引就是其地址。编译器、处理单元（特别是向量处理器），经常会针对数组操作进行优化。

因为在程序运行时可以计算元素的索引，数组是很有用的。此外，也能以单一迭代语句就处理数组的许多元素。为此，数组数据结构的元素必须具有相同的大小，而且应该使用相同的数据类型表示。

数组一词通常用于表示数组数据类型，一种大多数高阶编程语言都会内置的数据类型。数组类型通常由数组结构来实现；然而在某些语言中，它们可以由散列表、链表、搜索树或其它数据结构来实现。

在算法的描述中，数组一词特别着重意义为关系数组或“抽象的数组”，一种理论上的计算机科学模型（抽象数据类型或 ADT），专注于数组的基本性质上。

一维数组

一维（或单维）数组是一种线性数组，其中元素的访问是以行或列索引的单一下标表示。

譬如考虑C编程语言的数组宣告 int anArrayName [10];

语法为：

datatype anArrayname [sizeofArray];

多维数组

普通数组采用一个整数来作下标。多维数组（高维数组）的概念特别是在数值计算和图形应用方面非常有用。我们在多维数组之中采用一系列有序的整数来标注，如在[ 3,1,5 ] 。这种整数列表之中整数的个数始终相同，且被称为数组的“维度”。关于每个数组维度的边界称为“维”。维度为k的数组通常被称为k维。

多维数组的数组名字，在表达式中自动转换为数组首元素地址值，但这个首元素实际上是去除数组下标第一维之后的数组剩余部分。例如：

1 int a[10][15];
2 int (*p)[15] = a; // a在表达式中自动转换为指向具有15个int的数组的指针值

堆栈

栈（英语：stack）又称为栈或堆叠，是计算机科学中一种特殊的串列形式的抽象数据类型，其特殊之处在于只能允许在链表或数组的一端（称为堆栈顶端指针，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。另外栈也可以用一维数组或链表的形式来完成。堆栈的另外一个相对的操作方式称为队列。

由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

操作

堆栈数据结构使用两种基本操作：推入（压栈，push）和弹出（弹栈，pop）：

推入：将数据放入堆栈的顶端（数组形式或串列形式），堆栈顶端top指针加一。
弹出：将顶端数据数据输出（回传），堆栈顶端数据减一。

特点

栈的基本特点：

先入后出，后入先出。
除头尾节点之外，每个元素有一个前驱，一个后继。

数组堆栈

堆栈可以用链表和数组两种方式实现，一般为一个堆栈预先分配一个大小固定且较合适的空间并非难事，所以较流行的做法是Stack结构下含一个数组。如果空间实在紧张，也可用链表实现，且去掉表头。这里的例程是以数组实现的。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define stack struct Stack
#define STACK_POP_ERR 42

// 堆疊資料結構 堆栈数据结构
struct Stack {
   int val[10]; // 陣列空間
   int top;     // 堆疊頂端指標（栈顶）
};
// 檢查堆疊是否為空
bool empty(stack *stk) {
   return stk->top == 0;
}
// 推入資料
void push(stack *stk, int x) {
   stk->top = stk->top + 1;
   stk->val[stk->top] = x;
}
// 彈出并返回資料
int pop(stack *stk) {
   if (empty(stk))
       return STACK_POP_ERR; // 不能彈出
   else {
       stk->top = stk->top - 1;
       return stk->val[stk->top + 1];
   }
}
int main() {
   // 宣告并初始化資料結構空間
   stack stk;
   stk.top = 0;
   // 推入四个
   push(&stk, 3);
   push(&stk, 4);
   push(&stk, 1);
   push(&stk, 9);
   // 弹出三个
   printf("%d ", pop(&stk));
   printf("%d ", pop(&stk));
   printf("%d ", pop(&stk));
   return 0;
}

串列堆栈

// 链栈的结构定义
typedef struct {
   SLink top; // 棧頂指針
   int length; // 棧中元素個數
} Stack;

// 构造空栈 S
void InitStack (Stack &S) {
   S.top = NULL; // 設棧頂指針的初值為"空"
   S.length = 0; // 空棧中元素個數為0
}
// 如果指针反过来从栈底到栈顶的话，删除栈顶元素时，为修改其前驱指针，需要从栈底一直找到栈顶。

// 在棧頂S 之上插入元素e為新的棧頂元素，並返回成功與否
bool Push (Stack &S, ElemType e) {
   p = new LNode; // 建新的結點
   if (!p) // 存儲分配失敗
       return false;
   p->data = e;
   p->next = S.top;// 鏈接到原來的棧頂
   S.top = p; // 移動棧頂指針
   ++S.length; // 棧的長度增1
}
// 在链栈的类型定义中设立“栈中元素个数”的成员是为了便于求得栈的长度。

// 刪除S 棧頂且以e 返回其數值，返回成功與否
bool Pop (Stack &S, SElemType &e) {
   if (!S.top)
       return false;
   else {
       e = S.top -> data; // 返回棧頂元素
       q = S.top;
       S.top = S.top -> next; // 修改棧頂指針
       --S.length; // 棧的長度減1
       delete q; // 釋放被刪除的結點空間
       return true;
   }
}

队列

队列，又称为伫列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。当front=rear时，队列中没有任何元素，称为空队列。

队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

顺序队列

建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置

循环队列

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。

在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。

伪溢出

伪溢出是指队列的存储区没有满，但队列发生了溢出。

顺序队列中的溢出现象：

（1） “下溢”现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。

（2）”真上溢”现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。

（3）”假上溢”现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现象。

单链队列

单链队列使用链表作为基本数据结果，所以不存在伪溢出的问题，队列长度也没有限制。但插入和读取的时间代价较高

// 单链队列——队列的链式存储结构
typedef struct QNode {
   QElemType data;
   struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
   QueuePtr front, rear; // 队头、队尾指针
} LinkQueue;

// 链队列的基本操作(9个)
void InitQueue(LinkQueue *Q) {
   // 构造一个空队列Q
   Q->front = Q->rear = malloc(sizeof(QNode));
   if (!Q->front)
       exit(OVERFLOW);
   Q->front->next = NULL;
}

void DestroyQueue(LinkQueue *Q) {
   // 销毁队列Q(无论空否均可)
   while (Q->front) {
       Q->rear = Q->front->next;
       free(Q->front);
       Q->front = Q->rear;
   }
}

void ClearQueue(LinkQueue *Q) {
   // 将Q清为空队列
   QueuePtr p, q;
   Q->rear = Q->front;
   p = Q->front->next;
   Q->front->next = NULL;
   while (p) {
       q = p;
       p = p->next;
       free(q);
   }
}

Status QueueEmpty(LinkQueue Q) {
   // 若Q为空队列，则返回TRUE，否则返回FALSE
   if (Q.front->next == NULL)
       return TRUE;
   else
       return FALSE;
}

int QueueLength(LinkQueue Q) {
   // 求队列的长度
   int i = 0;
   QueuePtr p;
   p = Q.front;
   while (Q.rear != p) {
       i++;
       p = p->next;
   }
   return i;
}

Status GetHead_Q(LinkQueue Q, QElemType *e) {
   // 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR
   QueuePtr p;
   if (Q.front == Q.rear)
       return ERROR;
   p = Q.front->next;
   *e = p->data;
   return OK;
}

void EnQueue(LinkQueue *Q, QElemType e) {
   // 插入元素e为Q的新的队尾元素
   QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
   if (!p) // 存储分配失败
       exit(OVERFLOW);
   p->data = e;
   p->next = NULL;
   Q->rear->next = p;
   Q->rear = p;
}

Status DeQueue(LinkQueue *Q, QElemType *e) {
   // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
   QueuePtr p;
   if (Q->front == Q->rear)
       return ERROR;
   p = Q->front->next; // 指向头结点
   *e = p->data;
   Q->front = p->next; // 摘下头节点
   if (Q->rear == p)
       Q->rear = Q->front;
   free(p);
   return OK;
}

void QueueTraverse(LinkQueue Q, void(*vi)(QElemType)) {
   // 从队头到队尾依次对队列Q中每个元素调用函数vi()
   QueuePtr p;
   p = Q.front->next;
   while (p) {
       vi(p->data);
       p = p->next;
   }
   printf("\n");
}

循环队列

循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

// 队列的顺序存储结构(循环队列)，（顺序线性表的实现）
#define MAX_QSIZE 5 // 最大队列长度+1
typedef struct {
   QElemType *base; // 初始化的动态分配存储空间
   int front; // 头指针，若队列不空，指向队列头元素
   int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
} SqQueue;

// 循环队列的基本操作(9个)
void InitQueue(SqQueue *Q) {
   // 构造一个空队列Q
   Q->base = malloc(MAX_QSIZE * sizeof(QElemType));
   if (!Q->base) // 存储分配失败
       exit(OVERFLOW);
   Q->front = Q->rear = 0;
}

void DestroyQueue(SqQueue *Q) {
   // 销毁队列Q，Q不再存在
   if (Q->base)
       free(Q->base);
   Q->base = NULL;
   Q->front = Q->rear = 0;
}

void ClearQueue(SqQueue *Q) {
   // 将Q清为空队列
   Q->front = Q->rear = 0;
}

Status QueueEmpty(SqQueue Q) {
   // 若队列Q为空队列，则返回TRUE；否则返回FALSE
   if (Q.front == Q.rear) // 队列空的标志
       return TRUE;
   else
       return FALSE;
}

int QueueLength(SqQueue Q) {
   // 返回Q的元素个数，即队列的长度
   return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;
}

Status GetHead(SqQueue Q, QElemType *e) {
   // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
   if (Q.front == Q.rear) // 队列空
       return ERROR;
   *e = Q.base[Q.front];//下一个类型步长的地址单元的值
   return OK;
}

Status EnQueue(SqQueue *Q, QElemType e) {
   // 插入元素e为Q的新的队尾元素
   if ((Q->rear + 1) % MAX_QSIZE == Q->front) // 队列满
       return ERROR;
   Q->base[Q->rear] = e;
   Q->rear = (Q->rear + 1) % MAX_QSIZE;//循环队列的指针前进的方式是去余
   return OK;
}

Status DeQueue(SqQueue *Q, QElemType *e) {
   // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
   if (Q->front == Q->rear) // 队列空
       return ERROR;
   *e = Q->base[Q->front];
   Q->front = (Q->front + 1) % MAX_QSIZE;
   return OK;
}

void QueueTraverse(SqQueue Q, void(*vi)(QElemType)) {
   // 从队头到队尾依次对队列Q中每个元素调用函数vi()
   int i;
   i = Q.front;
   while (i != Q.rear) {
       vi(Q.base[i]);
       i = (i + 1) % MAX_QSIZE;
   }
   printf("\n");
}

链表

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

单向链表

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。（例如图的邻接表，通常都是按固定顺序访问的）。

双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）

一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接

在一些低级语言中, XOR-linking 提供一种在双向链表中通过用一个词来表示两个链接（前后），我们通常不提倡这种做法。

双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。

由于另外储存了指向链表内容的指针，并且可能会修改相邻的节点，有的时候第一个节点可能会被删除或者在之前添加一个新的节点。这时候就要修改指向首个节点的指针。有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会被删除或者移动的虚拟节点，形成一个下面说的循环链表。这个虚拟节点之后的节点就是真正的第一个节点。这种情况通常可以用这个虚拟节点直接表示这个链表，对于把链表单独的存在数组里的情况，也可以直接用这个数组表示链表并用第0个或者第-1个（如果编译器支持）节点固定的表示这个虚拟节点。

循环链表

在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存，假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。

指向整个列表的指针可以被称作访问指针。

用单向链表构建的循环链表

循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大(详见下面实例代码)。当然，如果只会在最后插入数据（或者只会在之前），处理也是很容易的。

另外有一种模拟的循环链表，就是在访问到最后一个节点之后的时候，手工的跳转到第一个节点。访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能，在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。

存储结构

链表中的节点不需要以特定的方式存储，但是集中存储也是可以的，主要分下面这几种具体的存储方法：

共用存储空间

链表的节点和其它的数据共用存储空间，优点是可以存储无限多的内容（不过要处理器支持这个大小，并且存储空间足够的情况下），不需要提前分配内存；缺点是由于内容分散，有时候可能不方便调试。
独立存储空间

一个链表或者多个链表使用独立的存储空间，一般用数组或者类似结构实现，优点是可以自动获得一个附加数据：唯一的编号，并且方便调试；缺点是不能动态的分配内存。当然，另外的在上面加一层块状链表用来分配内存也是可以的，这样就解决了这个问题。这种方法有时候被叫做数组模拟链表，但是事实上只是用表示在数组中的位置的下标索引代替了指向内存地址的指针，这种下标索引其实也是逻辑上的指针，整个结构还是链表，并不算是被模拟的（但是可以说成是用数组实现的链表）。

以下代码摘自Linux 内核2.6.21.5源码(部分)，展示了链表的另一种实现思路

struct list_head {
   struct list_head *next, *prev;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
       struct list_head name = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(struct list_head *list) {
   list->next = list;
   list->prev = list;
}

static inline void __list_add(struct list_head *new,
                             struct list_head *prev,
                             struct list_head *next) {
   next->prev = new;
   new->next = next;
   new->prev = prev;
   prev->next = new;
}

static inline void list_add(struct list_head *new, struct list_head *head) {
   __list_add(new, head, head->next);
}

static inline void __list_del(struct list_head *prev, struct list_head *next) {
   next->prev = prev;
   prev->next = next;
}


static inline void list_del(struct list_head *entry) {
   __list_del(entry->prev, entry->next);
   entry->next = NULL;
   entry->prev = NULL;
}

#define __list_for_each(pos, head) \
       for (pos = (head)->next; pos != (head); pos = pos->next)

#define list_for_each_entry(pos, head, member)                          \
       for (pos = list_entry((head)->next, typeof(*pos), member);      \
            prefetch(pos->member.next), &pos->member != (head);        \
            pos = list_entry(pos->member.next, typeof(*pos), member))

著作权声明

作者 Lampard Hong，转载请保留以上链接

数据结构&算法

数据结构篇01-数据队列链表

数组

一维数组

多维数组

堆栈

操作

特点

数组堆栈

串列堆栈

队列

顺序队列

循环队列

伪溢出

单链队列

循环队列

链表

单向链表

双向链表

循环链表

存储结构

著作权声明

FEATURED TAGS

FRIENDS