> 队列是一种先进先出的线性表,它只允许在表的一段进行插入，而在另外一端删除元素。  >   >   >  队列的顺序表示—用一维数组base[M] ~~~ #define M 100//最大队列长度 Typedef struct{ QElemType *base; int front; int rear; }SqQueue; ~~~  ~~~ 空队标志:front==rear 入队:base[rear++]=x; 出队:x=base[front++]; ~~~ 但是这样做存在一个问题，如下：   front=0 front≠0  rear=M时 rear=M时  再入队—真溢出 再入队—假溢出  该怎样解决呢？  —-循环队列   ~~~ base[0]接在base[M-1]之后 若rear+1==M 则令rear=0; 实现:利用“模”运算 入队: base[rear]=x; rear=(rear+1)%M; 出队: x=base[front]; front=(front+1)%M; ~~~ 又出现另外一个问题   解决方案:  1.另外设一个标志以区别队空、队满  2.少用一个元素空间:  队空:front==rear  队满:(rear+1)%M==front ### 循环队列 ~~~ #define MAXQSIZE 100 Typedef struct{ QElemType *base;//初始化的动态分配存储空间 int front;//头指针 int rear;//尾指针 }SqQueue; ~~~ 循环队列初始化 ~~~ Status InitQueue(SqQueue &Q) { Q.base=new QElemType[MAXQSIZE] if(!Q.base)exit(OVERFLOW); Q.front=Q.rear=0; return OK; } ~~~ 循环队列的长度 ~~~ int QueueLength(SqQueue Q){ return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; } ~~~ 循环队列入队 ~~~ Status EnQueue(SqQueue &Q,QElemType e){ if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; } ~~~ 顺环队列出队 ~~~ Status DeQueue(LinkQueue &Q,QElemType &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return OK; } ~~~

### 定义 只能在表的一端(栈顶)进行插入和删除运算的线性表 ### 逻辑结构 一对一关系 ### 存储结构 用顺序栈或链栈存储均可，但以顺序栈更常见  ### 运算规则 只能从栈顶运算，且访问结点时依照后进先出(LIFO)或后进后出(FILO)的原则 ### 实现方法 关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同 ### 基本操作 - 入栈 - 出栈 - 读栈顶元素值 - 建栈 - 判断栈满 - 栈空 ### 栈与一般线性表的区别 栈是一种特殊的线性表，它只能在表的一端(栈顶)进行插入或删除运算 | ** | 一般线性 表 | 栈 | |-----|-----|-----| | 逻辑结构 | 一对一 | 一对一 | | 存储结构 | 顺序表、链表 | 顺序栈、链栈 | | 运算规则 | 随机、顺序存储 | 后进先出 | ### 它们之间在于运算规则不同  > 我们在平常的程序设计中，如果需要按照保存数据时相反的顺序来使用数据，可以利用栈来实现。 ### 顺序栈的表示 ~~~ #define MAXSIZE 100 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; ~~~ stacksize 指示栈的最大容量；base为栈底指针，它始终指向栈底位置，若base的值为NULL，则表明栈结构不存在；top为栈顶指针，其初值指向栈底，即top=base可作为栈空的标记。每当插入新的栈顶元素时，指针top增加1；删除栈顶元素时，指针top减1.因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。 base == top 是栈空的重要标志 ### 栈满时的处理方法 1. 报错，返回操作系统。 1. 分更大的空间，作为栈的存储空间，将原栈的内容移入新栈。 ### 初始化  （1）分配空间并检查空间是否分配失败，若失败则返回错误 （2）设置栈底和栈顶指针 S.top = S.base; （3）设置栈大小 【算法描述】 ~~~ Status InitStack(SqStack &S) { S.base=new SElemType[MAXSIZE]; if(!S.base) return OVERFLOW; S.top=S.base; S.stackSize=MAXSIZE; return OK; } ~~~ ### 判断顺序栈是否为空 ~~~ bool StackEmpty(SqStack S) { if(S.top == S.base) return true; else return false; } ~~~ ### 求顺序栈的长度 ~~~ int StackLength(SqStack S) { return S.top-S.base; } ~~~ ### 清空顺序栈 ~~~ Status ClearStack(SqStack S) { if(S.base)S.top = S.base; return OK; } ~~~ ### 销毁顺序栈 ~~~ Status DestroyStack(SqStack &S) { if(S.base) { delete S.base; S.stacksize = 0; S.base = S.top =NULL; } return OK; } ~~~ ### 顺序栈进栈 （1）判断是否栈满，若满则出错 （2）元素e压入栈顶 （3）栈顶指针加1 ~~~ Status Push(SqStack &S,SElemType e) { if(S.top - S.base == S.stacksize)//栈满 return ERROR; *S.top=e; S.top++; return OK; } ~~~ ### 顺序栈出栈 (1)判断是否栈空。若空则出错 （2）获取栈顶元素e （3）栈顶指针减1 Status Pop(SqStack &S,SElemType &e) { if(S.top == S.base)//栈空 return ERROR； –S.top; e= *S.top; return OK; } ### 取顺序栈栈顶元素 判断是否为空栈，若为空则返回错误 否则通过栈顶指针获取栈顶元素 ~~~ Status GetTop(SqStack S,SElemType &e) { if(S.top == S.base) return ERROR;//栈空 e = *(S.top-1); return OK; } ~~~

> 上一篇博客学习了顺序表，最后也说明了顺序表属于静态存储，数据元素的个数不能自由的扩充。为了解决这个问题我们引入了链表 ### 链表存储结构 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻，因此线性表的链式表示又称为非顺序映像或链式映像。 ### 各个结点有两个域组成：  * 数据域:存储元素数值数据 * 指针域：存储直接后继结点的存储位置 ### 名词解析  1. 结点：数据元素的存储映像。有数据域和指针域两部分组成。 2. 链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构 3. 单链表、双链表、循环链表： * 结点只有一个指针域的链表，称为单链表或线性链表 * 有两个指针域的链表，称为双链表 * 首尾相接的链表称为循环链表 4. 头指针是指向链表中第一个结点的指针 5. 首元结点是指链表中存储第一个数据元素a1的结点 6. 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（可无） 当头结点的指针域为空时表示空表 头结点不能计入链表长度值 ### 单链表的定义和实现 非空表 空表  单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名 若头指针名是L，则把链表称为表L 单链表的存储结构定义 ~~~ typedef struct LNode { ElemType data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; //*LinkList为Lnode类型的指针 ~~~ 注意： 指针变量p：表示结点地址 结点变量*p：表示一个结点 ### 单链表基本操作的实现 #### 1.初始化(构造一个空表) 【算法思想】 (1)生成新结点作为头结点，用头结点L指向头结点。 (2)头结点的指针域置空。 【算法描述】 ~~~ Status InitList_L(LinkList &L) { L=new LNode; L->next=NULL; return OK; } ~~~ #### 2.查找 ##### （1）按序号查找 【算法思想】 从链表的第一个结点（L->next）开始顺着链域扫描，用指针p指向当前扫描到的结点，p的初始值指向第1个结点（p=L->next）。用j做计数器，累计当前扫描过的结点数，j的初值为1，当p指向扫描到的下一个结点时，计数器j相应加1.当j=i时，p所指向的结点是想要找的第i个结点。 【算法描述】 ~~~ Status GetElem_L（LinkList L，int i，ElemType &e） { p=L->next;j=1; while(p&&j<i) { p=p->next; ++j; } if(!p||j>i) return ERROR; e=p->data; return OK; } ~~~ #### 按值查找 【算法思想】 链表中查找其值与给定e相等的数据元素的过程和顺序表类似，从第一个结点起，依次和e相比较，如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”；如果查遍整个链表都没有找到其值和e相等的元素，则返回“NULL”。因此需要设置一个指针变量p顺链扫描，直至p为“NULL”，或者p->data和e相等为止。 【算法描述】 ~~~ LNode *LocateElem_L(LinkList L,ElemType e) { p=L->next; while(p&&p->data!=e) { p=p->next; } return p; } ~~~ ### 3.插入 【算法思想】  将值为e的新结点插入到表的第i个结点的位置上，即插入到结点ai-1与ai之间，分为一下几步： 1. 找到结点ai-1并由指针p指向该结点。 1. 生成一个新结点*s。 1. 将新结点*s的数据域置为e。 1. 将新结点*s的指针域指向结点ai。 1. 令结点ai-1的指针域指向新结点*s。 【算法描述】 ~~~ Status ListInsert_L(LinkList &L,int i,ElemType e) { p=L;j=0; while(p&&j<i-1) { p=p->next; ++j; } if(!p||j>i-1) return ERROR; s=new LNode; s->data=e; s->next=p->next; p->next=s; return OK; } ~~~ ### 4.删除 【算法思想】 要删除单链表的第i个结点ai，分以下几步：  1. 找到结点ai-1并由指针p指向该结点。 2. 临时保存待删除结点ai的地址在q中，以备释放。 3. 令p->next指向ai的直接后继结点。 4. 将待删除结点ai的值保留在e中 5. 释放结点ai的空间。 【算法描述】 ~~~ Status ListDelete_L(LinkList &L,int i,ElemType &e) { p=L;j=0; while(p->next&&j<i-1) { p=p->next;++j; } if(!(p->next)||j>i-1) return ERROR; q=p->next; e=q->data; delete q; return OK; } ~~~ ### 5.创建单链表 #### （1）前插法 【算法思想】 前插法是通过将新结点逐个插入链表的头部（头结点之后）来创建链表。首先建立只有一个头结点的空链表，每读入一个数据元素则申请一个新结点，并将新结点插入到头结点之后。  【算法描述】 ~~~ void CreateLst_F(LinkList &L,int n) { L=new LNode; L->next=NULL; for(i=n;i>0;--i) { p=new LNode; cin>>p->data; p->next=L->next;L->next=p; } } ~~~ #### (2)后插法 【算法思想】 后插法是通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样，首先要创建一个只有头结点的空链表L，不同的是，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链表的尾结点，初始化时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点*r之后，然后使r指向新的尾结点。  【算法描述】 ~~~ void CreateList_L(LinkList &L,int n) { L=new LNode; L->next=NULL; r=L; for(i=0;i<n;++i) { p=new LNode; cin>>p->data; p->next=NULL;r->next=p; r=p; } } ~~~ ### 循环链表 循环链表是表中最后一个结点的指针域指向头结点，整个链表形成一个环。  两个线性表合并成一个表，将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点。 ~~~ p=B->next->next; B->next=A->next; A->next=p; ~~~

#### 线性表的定义和特点 ##### 定义： ##### 有n(n≥0)个数据特性相同的元素构成的有序序列称为线性表。 ##### 当个数n(n≥0)定于为线性表的长度，n=0时成为空表。 ##### 特点： 1. 只有一个首结点和尾结点； 1. 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。 #### 分析26个英文字母组成的英文表（A,B,C,D,…..,Z）数据元素都是字母，元素间关系是线性 ##### 抽象数据类型的定义为: ~~~ ADT List { 数据对象：D={ai|ai∈ElemSet，i1,2,3...n,n≥0} 数据关系：R={<ai-1,ai|ai-1,ai∈D,i=2,...,n} 线性表的基本操作 1.初始化线性表 L 2.销毁线性表L 3.清空线性表L 4.求线性表L的长度 5.判断线性表L是否为空 6.获取线性表L中的某个数据元素内容 7.检索值为e的数据元素 8.在线性表L中插入一个数据元素 9.删除线性表L中第i个数据元素 }ADT List ~~~ ### 线性表的顺序表示和实现 线性表的顺序表示又称为顺序存储结构或顺序映像。 ##### 顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。（逻辑上相邻，物理上也相邻） ##### 顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。  ### 顺序表的类型定义 ~~~ #define MAXSIZE 100//最大长度 typedef struct{ ElemType *elem；//指向顺序表的基地址 int length；//顺序表的当前长度 }SqList；//顺序表的类型定义 ~~~ 如果你的C和C++基础不够扎实，建议看下我这篇博客 [C、C++函数传参疑难解析](http://blog.csdn.net/it_ds/article/details/50510962) #### 初始化线性表L（参数用引用） ~~~ Status InitList_Sq（SqList &L） { //构造一个空的顺序表L L.elem=new ElemTyPe[MAXSIZE]; //为顺序表分配空间 //存储分配失败 if(!L.elem)exit(OVERFLOW); //空表长度为0 L.length=0; return OK; } ~~~ #### 初始化线性表L（参数用指针） ~~~ "Status InitList_Sq（SqList *L） { L->elem=new ElemType[MAXSIZE]; if(!L->elem)exit(OVERFLOW); L->length=0; return OK; } ~~~ #### 销毁线性表L ~~~ void DestroyList(Sqlist &L) { if(L.elem) delete[]L.elem;//释放存储空间 } ~~~ #### 清空线性表L ~~~ void ClearList(SqList &L) { L.length=0;//将线性表的长度置为0 } ~~~ #### 求线性表L的长度 ~~~ int GetLength（SqList L） { return（L.length); } ~~~ ##### 判断线性表L是否为空 ~~~ int IsEmpty(SqList L) { if(L.length==0) return 1; else return 0; } ~~~ #### 6.获取线性表L中的某个数据元素的内容 ~~~ 根据指定位置，获取相应位置数据元素的内容 int GetElem(SqList L,int i,ElemType &e) { //判断i值是否合理，若不合理，返回ERROR if(i<1||i>L.length) return ERROR; e=L.elem[i-1];//第i-1的单元存储着第i个数据 return OK; } ~~~ #### 7.在线性表L中查找值为e的数据元素  ~~~ int LocateELem(SqList L,ElemType e) { for(i=0;i<L.length;i++) if(L.elem[i]==e) return i+1; return 0; } ~~~ ##### 8.在线性表L中的第i个数据元素之前插入数据元素e  ~~~ Status ListInsert_Sq(SqList &L,int i,ElemType e) { //值不合法 if(i<1||i>L.length+1)return ERROR; //当前存储空间已满 if(L.length==MAXSIZE)return ERROR; for(j=L.length-1;j>i-1;j--) //插入位置及以后的元素后移 //将新元素e放入第i个位置 L.elem[j+1]=L.elem[j]; L.elem[i-1]=e; ++L.length;//表长增加1 return OK; } ~~~ #### 9.将线性表L中第i个数据元素删除  ~~~ Status ListDelete_Sq(SqList &L,int i,ElemType &e) { if((i<1)||(i>L.length))return ERROR;//i值不合法 e=L.elem[i-1];//将欲删除的元素保留在e中 for(j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j];//被删除元素之后的元素前移 --L.length;//表长减1 return OK; } ~~~ ### 顺序存储结构的特点 1. 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致 1. 在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等。 ### 顺序表的优缺点 #### 优点： 1. 存储密度大（结点本身所占存储量/结点结构所占存储量） 1. 可以随机存取表中任一元素 #### 缺点： 1. 在插入、删除某一元素时，需要移动大量元素浪费存储空间 1. 属于静态存储形式，数据元素的个数不能自由扩充

> 一次数学课上，老师让学生练习算数。于是让他们一个小时内算出1+2+3+4+5+6+……+100的得数。全班只有高斯用了不到20分钟给出了答案，因为他想到了用（1+100）+（2+99）+（3+98）……+（50+51）…………一共有50个101，所以50×101就是1加到一百的得数。后来人们把这种简便算法称作高斯算法。 ### 算法定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 ### 算法的描述： 自然语言 流程图 程序设计语言 伪码 ### 算法的特性： - 输入:有0个或多个输入 - 输出 : 有一个或多个输出（处理结果） - 有穷性 : 算法应在执行有穷步后结束 - 确定性 : 每步定义都是确切、无歧义的 - 可行性 :算法中所有的操作都必须可以通过已经实现的基本操作执行有限次来实现。 ### 算法的评价 - 正确性 - 可读性 - 健壮性 - 高效性（时间代价和空间代价） ### 算法的效率的度量 算法效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量 *事后统计 *事前分析估计 ~~~ 事后统计：利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据，来分辨出优略。 缺点： 1.必须先运行依据算法编制的程序 2.所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣 2.事前分析估计： ~~~ 一个高级语言程序在计算机上运行所消耗的时间取决于： - 1.依据的算法选用何种策略 - 2.问题的规模 - 3.程序语言 - 4.编译程序所产生机器代码质量 - 5机器执行指令速度 注意：同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，——-使用绝对时间单位衡量算法效率不合适 ### 算法的时间和空间复杂性 ##### 时间复杂度（Time Complexity） 设算法中所有语句的语句频度为t(n),f(n)是当n趋向无穷大时与t(n)为同阶无穷大，则 算法的时间复杂度T(n)=O(f(n)) 其中：n为算法计算量或成为规模（size）; f(n)是运算时间随n增大时的增长率； O(f(n))是算法时间特性的量度。 算法分析主要从 分析算法的时间复杂度、空间复杂度这两个方面以考察算法的时间和空间效率。一般情况下，鉴于运算空间较为充足，故作算法的时间复杂度作为分析的重点。算法执行时间T(n)的数量级称为算法的渐近时间复杂度，T(n)=O(f(n)),它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，简称时间复杂度。  ~~~ i=1; ① while (i<=n) i=i*2; ② 解： 语句1的频度是1, 设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n 取最大值f(n)=log2n, T(n)=O(log2n ) ~~~ 常见的时间复杂度按照数量级递增排序依次为：常数阶O(1)、对数阶O(log2 n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、K次方阶O(n^k)、指数阶O(2^n)。 > 愚公移山固然可敬，但发明推土机和炸药，更加实在和聪明。希望大家在今后的学习中，好好利用算法分析的工具，改进自己的代码，让计算机轻松一点，这样你就能更胜一筹.

### **数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。** ### 基本概念和术语 数据（data）–所有能输入到计算机中去的描述客观事物的符号的总称 数据元素（data element）–数据的基本单位，也成结点（node）或记录（record） 数据项（data item）–有独立含义的数据最小单位，也成域（field） ~~~ 三者之间的关系：数据>数据元素>数据项 例如：成绩表>个人信息>学号、姓名、成绩 ~~~ 数据对象（Data Object):相同特征元素的集合，是数据的一个子集 ##### 例如：整数数据对象 N={0,1,2,3…} ##### 字母字符数据对象是集合C={‘A’,’B’,’C’,’D’,….’a’,’b’,’c’,’d’…} 数据结构（data Structure）是相互之间存在一种或多种特定关系的数据元素的集合。（数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。） ### 数据结构的两个层次： 逻辑结构——数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。* 存储结构（物理结构） 数据元素及其关系在计算机存储中的存储方式。 逻辑结构 划分方法一 （1）线性结构— 有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前驱和一个后驱。 例如：线性表、栈、队列、串 （2）非线性结构— 一个结点可能有多个直接前驱和直接后继。 例如：树、图 划分方法二 集合—-数据元素间除“同属于一个集合”外，无其他关系 线性结构—一个对一个，如 线性表、栈、队列 树形结构—-一个对多个，如 树 图形结构–多个对多个，如 图  存储结构分为： 顺序存储结构—–借助元素在存储器中的相对位置来表示数据元素间的逻辑关系 链式存储结构—-借助指示元素存储地址的指针表示数据元素间的逻辑关系 数据类型 定义：在一种程序设计语言中，变量所具有的数据种类 ~~~ 例如：基本数据类型：char int float double void 构造数据类型：数组、结构体、共用体、文件 ~~~ ### 抽象数据类型（ADTs：Abstract Data Types) - **定义： 用户进行软件系统设计时从问题的数据模型中抽象出来的逻辑数据结构和逻辑数据结构上运算，而不考虑计算机的具体存储结构和运算的具体实现算法。** *抽象数据类型可以用三元组表示：* ADT = （D，S，P） D:数据对象 S:D上的关系集 P:D上的操作集 #### ADT定义格式： ~~~ ADT 抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> } ADT抽象数据类型名 ~~~

> 原文出处：[数据结构](http://blog.csdn.net/column/details/datastructureno1.html) 作者：[it_ds](http://blog.csdn.net/it_ds) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # 数据结构 > 数据结构作为计算机类方向的基础性必修课程，这个专栏将从零开始讲解数据结构，一点一滴消化苦涩难学的数据结构。