1、数据结构三要素：逻辑结构、存储结构（物理结构）、数据的运算。
(1)逻辑结构：是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
(2)存储结构（物理结构）：是指数据在计算机中的表示（又称映像），是用计算机语言实现的逻辑结构，它依赖于计算机语言。
(3)数据的运算：包括运算的定义和实现。
2、数据元素：是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。例如：学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。
3、数据对象：是具有相同性质的数据元素的集合，是数据的一个子集。
4、数据类型：是一个值的集合和定义在此集合上的一组操作的总称。
5、数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
6、算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。一个算法应具有5个特性：
通常，设计一个“好”的算法应考虑达到以下目标：
7、时间复杂度
8、空间复杂度
1、知识框架
2、线性表的定义
3、线性表的特点
4、线性表的基本操作
InitList(&L);初始化表，构造一个空的线性表；Length(L);求表长，返回线性表L的长度，即L中数据元素的个数；LocateElem(L, e);按值查找操作，在表L中查找具有给定关键字值的元素；GetElem(L, i);按位查找操作，获取表L中第i个位置的元素的值；ListInsert(&L, i, e);插入操作，在表L中的第i个位置上插入指定元素e；ListDelete(&L, i, &e);删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值；PrintList(L);输出操作，按前后顺序输出线性表L的所有元素值；Empty(L);判空操作，若L为空表，则返回true，否则返回false；DestroyList(&L);销毁操作，销毁线性表，并释放线性表L所占用的内存空间；5、线性表的顺序表示—顺序表
//数组空间静态分配，可能会产生溢出
#define MaxSize 50//定义线性表的最大长度
typedef struct {
ElemType data[MaxSize];//顺序表的元素数组
int length;//顺序表的当前长度
} SqList;//顺序表的类型定义
//数组空间动态申请
#define InitSize 100//表长度的初始定义
typedef struct {
ElemType *data;//指示动态分配数组的指针
int MaxSize, length;//数组的最大容量和当前个数
} SeqList;//动态分配数组的顺序表的类型定义
动态申请得到的内存是连续的，同样属于顺序存储结构。C的初始动态分配语句为：
SeqList L;
L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);
C++的初始动态分配语句为：
L.data = new ElemType[InitSize];
6、顺序表上基本操作的实现
（1）插入操作
false，表示插入失败；否则，将第 i 个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。bool ListInsert(SqList &L, int i, ElemType e) {
if( i < 1 || i > L.length + 1 )//判断i的范围是否有效
return false;
if( L.length >= MaxSize )//当前存储空间已满，不能插入
return false;
for( int j = L.length; j >= i; j -- )//将第i个元素及之后的元素后移
L.data[j] = L.data[j - 1];
L.data[i - 1] = e;//在位置i处放e
L.length ++;//线性表长度加1
return true;
}
i = n + 1），元素后移语句将不执行，时间复杂度为O(1)；i = 1），元素后移语句将执行n次，时间复杂度为O(n)；pi = 1/(n+1)，元素后移语句要执行n-i+1次，所以移动结点的平均次数为 pi * (n-i+1)（ i 从1到n+1求和）= n/2，所以平均时间复杂度为O(n)。
（2）删除操作
e返回。若 i 的输入不合法，则返回false；否则将被删除元素赋给引用变量e，并将第 i + 1个元素及其后的所有元素依次往前移动一个位置，返回true。bool ListDelete(SqList &L, int i, ElemType &e) {
if( i < 1 || i > L.length )//判断i的范围是否有效
return false;
e = L.data[i-1];//将被删除的元素赋值给e
for( int j = i - 1; j < L.length - 1; j ++)//将第i个位置后的元素前移
L.data[j] = L.data[j + 1];
L.length --;//线性表长度减1
return ture;
}
i = n），无需移动元素，时间复杂度为O(1)；i = 1），需移动除表头元素外的所有元素，时间复杂度为O(n)；pi = 1/n，需移动n-i个元素，所以移动元素的平均个数为pi * (n - i)( i从1到n求和）= (n - 1)/2，所以平均时间复杂度为O(n)。
可见，顺序表中插入和删除操作的时间主要耗费在移动元素上，而移动元素的个数取决于插入和删除元素的位置。
(3)按值查找（顺序查找）
int LocateElem(SqList L, ElemType e) {
for( int i = 0; i < L.length; i ++ ) {
if( L.data[i] == e )
return i + 1;//下标为i的元素值等于e，返回其位序i + 1
}
return 0;//退出循环，说明查找失败
}
pi = 1/n，需要比较 i 次，所以平均比较次数为pi * i（ i从1到n求和）= (n + 1)/2，所以平均时间复杂度为O(n)。
7、线性表的链式表示–链表
8、单链表
typedef struct LNode {//定义单链表结点类型
ElemType data;
struct LNode *next;
} LNode, *LinkList;
NULL时表示一个空表；9、单链表上基本操作的实现
(1)采用头插法建立单链表：从一个空表开始，生成新结点，并将读取到的数据放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。
//头插法建立单链表
LinkList List_HeadInsert(LinkList &L) {//逆向建立单链表
LNode *s;
int x;
L = (LinkList)malloc(sizeof(LNode));//创建头结点
L->next = NULL;//初始为空链表
scanf("%d", &x);//输入结点的值
while( x != 9999 ) {//输入9999表示结束
s = (LNode*)malloc(sizeof(LNode));//创建新结点
s->data = x;
s->next = L->next;
L->next = s;//将新结点插入表中，L为头指针
scanf("%d", &x);
}
return L;
}
采用头插法建立单链表时，读入数据的顺序与生成的链表中元素的顺序是相反的。每个结点插入的时间为O(1)，设单链表长为n，则总时间复杂度为O(n)。
(2)采用尾插法建立单链表：将新结点插入到当前链表的表尾，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。
//尾插法建立单链表
LinkList List_TailInsert(LinkList &L) {//正向建立单链表
int x;//设元素类型为整数
L = (LinkList)malloc(sizeof(LNode));//创建头结点
LNode *s, *r = L;//r为表尾指针
scanf("%d", &x);//输入结点的值
while( x != 9999 ) {//输入9999表示结束
s = (LNode*)malloc(sizeof(LNode));//创建新结点
s->data = x;
r->next = s;
r = s;//r指向新的表尾结点
scanf("%d", &x);
}
r->next = NULL;//尾结点指针置空
return L;
}
因为附设了一个指向表尾结点的指针，故时间复杂度和头插法的相同。
(3)按序号查找结点值：在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第 i 个结点为止，否则返回最后一个结点指针域NULL。
//按序号查找结点值
LNode *GetElem(LinkList L, int i) {
int j = 1;//计数，初始为1
LNode *p = L->next;//第1个结点指针赋给p
if( i == 0 )
return L;//若i等于0，则返回头结点
if( i < 1 )
return NULL;//若i无效，则返回NULL
while( p && j < i ) {//从第1个结点开始找，查找第i个结点
p = p->next;
j ++;
}
return p;//返回第i个结点的指针，若i大于表长，则返回NULL
}
按序号查找操作的时间复杂度为O(n)。
(4)按值查找表结点：从单链表的第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL。
//按值查找表结点
LNode *LocateElem(LinkList L, ElemType e) {
LNode *p = L->next;
while( p != NULL && p->data != e )//从第一个结点开始查找data域为e的结点
p = p->next;
return p;//找到后返回该结点指针，否则返回NULL
}
按值查找操作的时间复杂度为O(n)。
(5)插入结点操作：将值为x的新结点插入到单链表的第 i 个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第 i-1 个结点，再在其后插入新结点。
GetElem(L, i - 1)，查找第 i-1 个结点。假设返回的第i-1个结点为*p，然后令新结点*s的指针域指向*p的后继结点，再令结点*p的指针域指向新插入的结点*s。//实现插入结点的代码片段
p = GetElem(L, i - 1);
s->next = p->next;
p-next = s;
本算法主要的时间开销在于查找第i-1个元素，时间复杂度为O(n)。若在给定的结点后面插入新结点，则时间复杂度仅为O(1)。
扩展：对某一结点进行前插操作：
GetElem()找到第 i-1 个结点，即插入结点的前驱结点后，在对其执行后插操作。*s，欲将*s插入到*p的前面，我们仍然将*s插入到*p的后面，然后将p->data与s->data交换，这样既满足了逻辑关系，又能使得时间复杂度为O(1)。//将*s结点插入到*p之前的主要代码片段
s->next = p->next;
p->next = s;
temp = p->data;
p->data = s->data;
s->data = temp;
(6)删除结点操作：将单链表的第 i 个结点删除。先检查删除位置的合法性，后查找表中第 i-1 个结点，即被删结点的前驱结点，再将其删除。
*p为被找到的被删结点*q的前驱结点，为实现这一操作后的逻辑关系的变化，仅需修改*p的指针域，即将*p的指针域next指向*q的下一结点。//实现删除结点的代码片段
p = GetElem(L, i - 1);
q = p->next;
p->next = q->next;
free(q);
该算法的主要时间也耗费在查找操作上，时间复杂度为O(n)。
扩展：删除结点*p：
*p，通常做法是先从链表的头结点开始顺序找到其前驱结点，然后执行删除操作，时间复杂度为O(n)。*p的操作可用删除*p的后继结点操作来实现，实质就是将其后继结点的值赋予其自身，然后删除后继结点，也能使得时间复杂度为O(1)。q = p->next;
p->data = q->data;
p->next = q->next;
free(q);
(7)求表长操作：计算单链表中数据结点（不含头结点）的个数，需要从第一个结点开始顺序依次访问表中的每个结点，为此需要设置一个计数器变量，每访问一个结点计数器加1，直到访问到空结点为止。算法的时间复杂度为O(n)。
10、双链表
prior和next，分别指向其前驱结点和后继结点。typedef struct DNode {//定义双链表结点类型
ElemType data;//数据域
struct DNode *prior, *next;//前驱和后驱指针
} DNode, *DLinkList;
11、双链表上基本操作的实现
(1)双链表中的按值查找和按位查找的操作与单链表相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。因为“链”变化时也需要对prior指针做出修改，其关键是保证在修改的过程中不断链。双链表可以很方便地找到其前驱结点，因此，插入、删除的时间复杂度仅为O(1)。
(2)双链表的插入操作：在双链表中p所指的结点之后插入结点*s，插入操作的代码片段如下：
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
(3)双链表的删除操作：删除双链表中结点*p的后继结点*q，删除操作的代码片段如下：
p->next = q->next;
q->next->prior = p;
free(q);
12、循环链表
(1)循环单链表
NULL，而改为指向头结点，从而整个链表形成一个环。*r的next域指向头结点L，故表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针域是否为空，而是它是否等于头指针。r，r->next即为头指针，对表头与表尾进行操作都只需要O(1)的时间复杂度。(2)循环双链表
prior指针还要指向表尾结点。L中，某结点*p为尾结点时，p->next == L；prior域和next域都等于L。13、静态链表
data和指针域next；
#define MaxSize 50//静态链表的最大长度
typedef struct {//静态链表结构类型的定义
ElemType data;//存储数据元素
int next;//下一个元素的数组下标
} SLinkList[MaxSize];
next == -1作为其结束的标志；14、顺序表和链表的比较
(1)存取（读写）方式：顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。例如在第 i 个位置上执行存或取的操作，顺序表仅需一次访问，而链表则需从表头开始依次访问 i 次。
(2)逻辑结构和物理结构：采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。
(3)查找、插入和删除操作：
(4)空间分配：
在实际中应该怎样选取存储结构？
(1)基于存储的考虑：
(2)基于运算的考虑：
ai的时间复杂度为O(1)，而链表中按序号访问的时间复杂度为O(n)，因此若经常做的运算是按序号访问数据元素，则显然顺序表优于链表。(3)基于环境的考虑：
总之，两种存储结构各有长短，选择哪一种由实际问题的主要因素决定。
通常较稳定的线性表选择顺序存储，而频繁进行插入、删除操作的线性表（即动态性较强）宜选择链式存储。
1、知识框架
2、栈的基本概念
n个不同元素进栈，出栈元素不同排列的个数为[C(n 2n)] / (n+1)，上述公式称为卡特兰数。3、栈的基本操作
InitStack(&S)：初始化一个空栈S。StackEmpty(S)：判断一个栈是否为空，若栈S为空则返回true，否则返回false。Push(&S, x)：进栈，若栈S未满，则将x加入使之成为新栈顶。Pop(&S, &x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。GetTop(S, &x)：读栈顶元素，若栈S非空，则用x返回栈顶元素。DestroyStack(&S)：销毁栈，并释放栈S所占用的存储空间。在解答算法题时，若题干未做出限制，则可直接使用这些基本的操作函数。
4、栈的顺序存储结构
(1)顺序栈的实现
top指示当前栈顶元素的位置。#define MaxSize 50//定义栈中元素的最大个数
typedef struct {
Elemtype data[MaxSize];//存放栈中元素
int top;//栈顶指针
} SqStack;
S.top，初始时设置S.top = -1；S.data[S.top]。S.top == -1；S.top == MaxSize - 1；S.top + 1。由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告消息，以便及时处理，避免出错。
注意：栈和队列的判空、判满条件，会因实际给的条件不同而变化，上面提到的方法以及下面的代码实现只是在栈顶指针设定的条件下的相应方法，而其他情况则需具体问题具体分析。（如有的教辅可能初始时将S.top定义为0，相当于规定top指向栈顶元素的下一个存储单元）
(2)顺序栈的基本运算
void InitStack(SqStack &S) {
S.top = -1;//初始化栈顶指针
}
bool StackEmpty(SqStack S) {
if( S.top == -1 )//栈空
return true;
else//不空
return false;
}
bool Push(SqStack &s, ElemType x) {
if( S.top == MaxSize - 1 )//栈满，报错
return false;
S.data[++S.top] = x;//指针先加1，再入栈
return true;
}
bool Pop(SqStack &s, ElemType &x) {
if( S.top == -1 )//栈空，报错
return false;
x = S.data[S.top--];
return true;
}
bool GetTop(SqStack S, ElemType &x) {
if( S.top == -1 )//栈空，报错
return false;
x = S.data[S.top];//x记录栈顶元素
return true;
}
(3)共享栈
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
top0 = -1 时0号栈为空，top1 = MaxSize时1号栈为空；top1 - top0 = 1）时，判断为栈满；top0先加1再赋值，1号栈进栈时top1先减1再赋值，出栈时则刚好相反。共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为O(1)，对存取效率没有什么影响。
5、栈的链式存储结构
Lhead指向栈顶元素。
typedef struct Linknode {
ElemType data;//数据域
struct Linknode *next;//指针域
} *LiStack;//栈类型定义
6、队列的基本概念
7、队列常见的基本操作
InitQueue(&Q)：初始化队列，构造一个空队列Q。QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。EnQueue(&Q, x)：入队，若队列Q未满，将x加入，使之成为新的队尾。DeQueue(&Q, &x)：出队，若队列Q非空，删除队头元素，并用x返回。GetHead(Q, &x)：读队头元素，若队列Q非空，则将队头元素赋值给x。需要注意的是，栈和队列是操作受限的线性表，因此不是任何对线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。
8、队列的顺序存储结构
(1)队列的顺序存储
front指向队头元素；rear指向队尾元素的下一个位置。注意：不同教材对front和rear的定义可能不同，例如，可以让front指向队头元素、rear指向队尾元素。对于不同的定义，出队入队的操作是不同的。
#define MaxSize 50//定义队列中元素的最大个数
typedef struct {
ElemType data[MaxSize];//存放队列元素
int front, rear;//队头指针和队尾指针
} SqQueue;
Q.front == Q.rear == 0。
Q.front == Q.rear == 0成立，该条件可以作为队列判空的条件。Q.rear == MaxSize作为队列满的条件，上图(d)中，队列中仅有一个元素，但仍满足该条件。这时入队出现“上溢出”，但这种溢出并不是真正的溢出，在data数组中依然存在可以存放元素的空位置，所以是一种“假溢出”。(2)循环队列
Q.front = MaxSize - 1后，再前进一个位置就自动到0，这可以利用除法取余运算%来实现。Q.front = Q.rear = 0。Q.front = (Q.front + 1) % MaxSize。Q.rear = (Q.rear + 1) % MaxSize。(Q.rear + MaxSize - Q.front) % MaxSize。
那么，循环队列队空和队满的判断条件是什么呢？
Q.front == Q.rear。Q.front == Q.rear。为了区分是队空还是队满的情况，有三种处理方式：
( a ) 较为普遍的做法：牺牲一个单元来区分队空和队满，约定以“队头指针在队尾指针的下一位置作为队满的标志”，如上图(d2)所示。
(Q.rear + 1) % MaxSize == Q.frontQ.front == Q.rear(Q.rear + MaxSize - Q.front) % MaxSize( b )类型中增设表示元素个数的数据成员size。这样，队空的条件为Q.size == 0；队满的条件为Q.size == MaxSize。这两种情况都有Q.front == Q.rear。
(c )类型中增设tag数据成员，以区分是队满还是队空。tag等于0时，表示因删除导致Q.front == Q.rear，则为队空；tag等于1时，表示因插入导致Q.front == Q.rear，则为队满。
(3)循环队列的操作（ 基于上面的(a) ）
void InitQueue(SqQueue &Q) {
Q.rear = Q.front = 0;//初始化队首、队尾指针
}
bool isEmpty(SqQueue Q) {
if( Q.rear == Q.front )//队空条件
return true;
else
return false;
}
bool EnQueue(SqQueue &Q, ElemType x) {
if( (Q.rear + 1) % MaxSize == Q.front )//队满则报错
return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize;//队尾指针加1取模
return true;
}
bool DeQueue(SqQueue &Q, ElemType &x) {
if( Q.rear == Q.front )//队空则报错
return false;
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;//队头指针加1取模
return true;
}
9、队列的链式存储结构
(1)队列的链式存储
typedef struct LinkNode {//链式队列结点
ElemType data;
struct LinkNode *next;
} LinkNode;
typedef struct {//链式队列
LinkNode *front, *rear;//队列的队头和队尾指针
} LinkQueue;
Q.front == NULL且Q.rear == NULL时，链式队列为空。Q.front指向下一个结点（若该结点为最后一个结点，则置Q.front和Q.rear都为NULL）。Q.rear指向这个新插入的结点（若原队列为空队，则令Q.front也指向该结点）。不难看出，不带头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了。
用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满而产生溢出的问题。
假如程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列，这样就不会出现存储分配不合理和“溢出”的问题。
(2)链式队列的基本操作（带头结点）
void InitQueue(LinkQueue &Q) {
Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));//建立头结点
Q.front->next = NULL;//初始为空
}
bool IsEmpty(LinkQueue Q) {
if( Q.front == Q.rear )
return true;
else
return false;
}
void EnQueue(LinkQueue &Q, ElemType x) {
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;//创建新结点，插入到链尾
Q.rear->next = s;
Q.rear = s;
}
bool DeQueue(LinkQueue &Q, ElemType &x) {
if( Q.front == Q.rear )//空队
return false;
LinkNode *p = Q.front->next;
x = p->data;
Q.front->next = p->next;
if( p == Q.rear ) //若原队列中只有一个结点，删除后变空
Q.rear = Q.front;
free(p);
return true;
}
10、双端队列
11、栈和队列的应用
(1)栈在括号匹配中的应用
([]())或[([][])]等均为正确的格式，[(])或([())或(()]均为不正确的格式。
[”后，期待与之匹配的第8个括号“]”出现。(”，此时第1个括号“[”暂时放在一边，而急迫期待与之匹配的第7个括号“)”出现。[”，此时第2个括号“(”暂时放在一边，而急迫期待与之匹配的第4个括号“]”出现。第3个括号的期待得到满足，消解之后，第2个括号的期待匹配又称为当前最急迫的任务。算法思想如下：
(2)栈在表达式求值中的应用
1 )三种表达式：
a+b），中缀表达式不仅依赖运算符的优先级，而且还要处理括号。ab+），后缀表达式已经考虑了运算符的优先级，没有括号，只有操作数和运算符。+ab）,前缀表达式也考虑了运算符的优先级，没有括号，只有操作数和运算符。e.g.
中缀表达式：a + b - c
对应的后缀表达式：ab+c-或abc-+（不唯一）
对应的前缀表达式：-+abc或+a-bc（不唯一）
2 )中缀转后缀的手算方法：
3 )后缀表达式的手算方法：
4 )后缀表达式的机算（用栈实现）：
后缀表达式适用于基于栈的编程语言（stack–oriented programming language），如：Forth，PostScript。
5 )中缀转前缀的手算方法：
6 )前缀表达式的机算（用栈实现）：
7 )中缀表达式转后缀表达式（机算）
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况：
(”直接入栈，遇到“ ) ”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意：“ ( ”不加入后缀表达式。(”或栈空则停止。之后再把当前运算符入栈。按上述方法处理完所有字符之后，将栈中剩余运算符依次弹出，并加入后缀表达式。
8 )中缀表达式的计算（用栈实现）
是“中缀转后缀” + “后缀表达式求值”两个算法的结合：
(3)栈在递归中的应用
斐波那契数列就是递归的一个典型例子，用程序实现如下：
int Fib(int n) {//斐波那契数列的实现
if( n == 0 )
return 0;//边界条件
else if( n == 1 )
return 1;//边界条件
else
return Fib(n - 1) + Fib(n - 2);//递归表达式
}
必须注意递归模型不能是循环定义的，其必须满足下面的两个条件：
在递归调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储，递归次数过多容易造成栈溢出。
(4)队列在层次遍历中的应用
在信息处理中有一大类问题需要逐层或逐行处理。这类问题的解决办法往往是在处理当前行时就对下一层或下一行做预处理，把处理顺序安排好，等到当前层或当前行处理完毕，就可以处理下一层或下一行。使用队列是为了保存下一步的处理顺序。
下面用二叉树的层序遍历的例子，说明队列的应用：
该过程简单描述如下：
(5)队列在计算机系统中的应用
①解决主机与外部设备之间速度不匹配的问题（以主机和打印机为例）：主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，由于速度不匹配，若直接把输出的数据送给打印机打印显然是不行的。解决的办法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样做既保证了打印数据的正确，又使主机提高了效率。由此可见，打印数据缓冲区中所存储的数据就是一个队列。
②解决由多用户引起的资源竞争问题：CPU（即中央处理器，它包括运算器和控制器）资源的竞争就是一个典型的例子。在一个带有多终端的计算机系统上，有多个用户需要CPU运行自己的程序，它们分别通过各自的终端向操作系统提出占用CPU的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把CPU分配给新的队首请求的用户使用。这样既满足每个用户的请求，又使CPU能够正常运行。
12、数组和特殊矩阵
在数据结构中考虑的是如何用最小的内存空间来存储同样的一组数据。
所以，我们不研究矩阵及其运算等，而把精力放在如何将矩阵更有效地存储在内存中，并能方便地提取矩阵中的元素。
(1)数组的定义：数组是由 n（ n≥1 ）个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。
数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表；二维数组可视为其元素也是定长线性表的线性表，以此类推。
数组一旦被定义，其维数和维界就不再改变。除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。
(2)数组的存储结构
A[ 0...n-1 ]为例，其存储结构关系式为：LOC(ai) = LOC(a0) + i × L （ 0 ≤ i < n ），其中，L 是每个数组元素所占的存储单元个数。[0, h1]与[0, h2]，则存储结构关系式为：
LOC(ai,j) = LOC(a0,0) + [ i × (h2 + 1) + j ] × L
LOC(ai,j) = LOC(a0,0) + [ j × (h1 + 1) + i ] × L
(3)特殊矩阵的压缩存储
压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是节省存储空间。
特殊矩阵：指具有许多相同元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。
常见的特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等。
特殊矩阵的压缩方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。
1)对称矩阵
A[1...n] [1...n]中的任意一个元素ai,j都有ai,j = aj,i（ 1≤ i, j ≤ n ）,则称其为对称矩阵。
A[1...n] [1...n]存放在一维数组B[n(n+1)/2]中，即元素ai,j存放在bk中。只存放下三角部分（含主对角线）的元素。ai,j（ i ≥ j ）前面的元素个数为：
a1,1）。a2,1，a2,2）。i-1行：i - 1个元素（ai-1,1，ai-1,2，…，ai-1,i-1）。i行：j - 1个元素（ai,1，ai,2，…，ai,j-1）。ai,j在数组B中的下标k = 1 + 2 + ... + (i - 1) + (j - 1) = i(i - 1)/2 + j - 1（数组下标从0开始）。k = i(i - 1)/2 + j - 1， i ≥ j（下三角区和主对角线元素）k = j(j - 1)/2 + i - 1， i < j（上三角区元素ai,j = aj, i）当数组下标从1开始时，可以采用同样的推导方法。
2 )三角矩阵
A[1...n] [1...n]压缩存储在B[n(n+1)/2 + 1]中。k = i(i - 1)/2 + j - 1， i ≥ j（下三角区和主对角线元素）k = n(n + 1)/2， i < j（上三角区元素）
B[n(n+1)/2 + 1]中。ai,j（i ≤ j）前面的元素个数为：
n个元素n - 1个元素i-1行：n - i + 2个元素i行：j - i个元素ai,j在数组B中的下标k = n + (n - 1) + ... + (n - i + 2) + (j - i) = (2n - i + 2)(i - 1)/2 + (j - i)。k = (2n - i + 2)(i - 1)/2 + (j - i)， i ≤ j（上三角区和主对角线元素）k = n(n + 1)/2， i > j（下三角区元素）
注：以上推导均假设数组的下标从0开始，且矩阵按行优先原则存储，若题设有具体要求，则应该灵活应对。
3 )三对角矩阵
ai,j，当|i - j| > 1时，有ai,j = 0（1 ≤ i, j ≤ n），则称为三对角矩阵，如下图所示：
a1,1存放于B[0]中，其存储形式如下图所示：
ai,j（1 ≤ i, j ≤ n，|i - j| ≤ 1）在一维数组B中存放的下标为k = 2i + j - 3。ai,j存放于一维数组B的下标为k的位置，则可得i = floor( (k + 1)/3 ) + 1，j = k - 2i + 3。e.g.
当k = 0时，i = floor( (k + 1)/3 ) + 1 = 1, j = 0 - 2 x 1 + 3 = 1,存放的是a1,1
当k = 2时，i = floor( (k + 1)/3 ) + 1 = 2, j = 2 - 2 x 2 + 3 = 1,存放的是a2,1
当k = 4时，i = floor( (k + 1)/3 ) + 1 = 2, j = 4 - 2 x 2 + 3 = 3,存放的是a2,3
4 )稀疏矩阵
t，相对矩阵元素的个数s来说非常少，即 s >> t 的矩阵称为稀疏矩阵。100 x 100，该矩阵中只有少于100个非零元素。e.g.【2017统考真题】适用于压缩存储稀疏矩阵的两种数据结构是（ ）
A.三元组表和十字链表 B.三元组表和邻接矩阵
C.十字链表和二叉链表 D.邻接矩阵和十字链表
【答案】A
【分析】三元组表的结点存储了行row、列col、值value三种信息，是主要用来存储稀疏矩阵的一种数据结构。
十字链表将行单链表和列单链表结合起来存储稀疏矩阵。
邻接矩阵空间复杂度达O(n^2)，不适合于存储稀疏矩阵。
二叉链表又名左孩子右兄弟表示法，可用于表示树和森林。
我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？ 最佳答案 这是我通过查看rubyzip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳
给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最
我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_
无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD
我正在编写一个简单的静态Rack应用程序。查看下面的config.ru代码:useRack::Static,:urls=>["/elements","/img","/pages","/users","/css","/js"],:root=>"archive"map'/'dorunProc.new{|env|[200,{'Content-Type'=>'text/html','Cache-Control'=>'public,max-age=6400'},File.open('archive/splash.html',File::RDONLY)]}endmap'/pages/search.
点向量坐标矩阵的几何意义介绍旋转矩阵的几何含义之前，先介绍一下点向量坐标矩阵的几何含义点：在一维空间下就是一个标量，如同一条直线上，以任意某一个位置为0点，以一定的尺度间隔为1，2，3...,相反方向为-1，-2，-3...；如此就形成了一维坐标系，这时候任何一个点都可以用一个数值表示，如点p1=5，即即从原点出发沿着x轴正方向移动5个尺度；点p2=-3，负方向移动3个尺度； 在一维坐标系上过原点做垂直于一维坐标系的直线，则形成了二维坐标系，此时描述一个点需要两个数值来表示点p3=（3，2），即从原点出发沿着x轴正方向移动3个尺度，在此基础上沿着y轴正方向移动两个尺度的位置就是点p3。
本教程将在Unity3D中混合Optitrack与数据手套的数据流，在人体运动的基础上，添加双手手指部分的运动。双手手背的角度仍由Optitrack提供，数据手套提供双手手指的角度。 01 客户端软件分别安装MotiveBody与MotionVenus并校准人体与数据手套。MotiveBodyMotionVenus数据手套使用、校准流程参照：https://gitee.com/foheart_1/foheart-h1-data-summary.git02 数据转发打开MotiveBody软件的Streaming，开始向Unity3D广播数据；MotionVenus中设置->选项选择Unit