数据的线性结构教学课件

SUMMER TEMPLATE数据的线性结构数据的线性结构从上面两个例子中可以看出：从上面两个例子中可以看出：数据结构中元素之间存在着逻辑关系，数据结构中元素之间存在着逻辑关系，上述例子中给出了三种逻辑结构上述例子中给出了三种逻辑结构线性表、线性表、树、图。树、图。数据结构主要解决：数据结构主要解决：如何分析数据元素之间的关系，并确定合适如何分析数据元素之间的关系，并确定合适的逻辑结构；的逻辑结构；如何在计算机中存储这些数据；如何在计算机中存储这些数据；为完成对数据的操作设计算法，并作出分析。为完成对数据的操作设计算法，并作出分析。二、概念和术语二、概念和术语1.数据数据(data)：表示现实世界中的客观事物、表示现实世界中的客观事物、能输入计算机并能被计算机程序处理的符号能输入计算机并能被计算机程序处理的符号的总称。的总称。2.数据元素数据元素(data element)：数据集合中的一个数据集合中的一个个体，是数据的基本单位。个体，是数据的基本单位。(亦称为结点、记亦称为结点、记录等录等)3.数据项数据项(data item)：数据的不可分割的、含数据的不可分割的、含有独立意义的最小单位。有独立意义的最小单位。4.数据对象数据对象(data object)：性质相同的数据元素性质相同的数据元素的集合。的集合。5.数据结构数据结构(data structure)：相互之间存在着相互之间存在着一种或多种关系的数据元素的集合。一种或多种关系的数据元素的集合。数据结构无公认定义，都认为其研究涉数据结构无公认定义，都认为其研究涉及三个方面：及三个方面：1)数据元素间的逻辑关系数据元素间的逻辑关系(逻辑结构逻辑结构)2)数据元素的存储方式数据元素的存储方式(物理结构物理结构)3)数据元素间的运算数据元素间的运算(操作操作)一般地，一个数据结构中的数据元素一般地，一个数据结构中的数据元素属于同一个数据对象。属于同一个数据对象。2.1.2 2.1.2 数据的逻辑结构和存储方法数据的逻辑结构和存储方法一、数据的逻辑结构一、数据的逻辑结构 逻辑结构逻辑结构是指数据元素之间的特定关系，是指数据元素之间的特定关系，它独立于计算机，是元素之间关系的抽象。它独立于计算机，是元素之间关系的抽象。1 1、定义、定义 数据结构是一个二元组数据结构是一个二元组B=(DB=(D，R)R)。其其中中D D是数据元素是数据元素(即结点即结点)的有限集合；的有限集合；R R是是D D上的关系的有限集合。一般上的关系的有限集合。一般R R中只涉及一种中只涉及一种关系。关系。例如例如：有有4个人，为别为个人，为别为a、b、c、d，其中其中a是是b的父亲，的父亲，b是是c的父亲，的父亲，c是是d的父亲的父亲，如，如果只讨论他们所表达的果只讨论他们所表达的父子父子关系，则可关系，则可以用下面的二元组形式化地表示为：以用下面的二元组形式化地表示为：B(D，R)其中其中 D=a，b，c，d R=r r=，又如又如:另有另有4个人，分别为个人，分别为e,f,g,h；其中其中e是是f和和g的父亲，的父亲，g是是h的父亲，则可用下面的二的父亲，则可用下面的二元组形式化地表示为：元组形式化地表示为：B(D，R)其中其中 D=e，f，g，h R=r r=，可以用图形方式分别表示为：可以用图形方式分别表示为：abcdfegh2、几个概念、几个概念 设设B=(D，R)是一个逻辑结构，是一个逻辑结构，rR，di、dj D。如果如果 r，则称则称di是是dj的前驱，的前驱，dj是是di的后继。的后继。如果某个结点没有前驱，则称之为如果某个结点没有前驱，则称之为开始结点开始结点；如果某个结点没有后继，则称之为如果某个结点没有后继，则称之为终端结点终端结点；既非开始结点，也非终端结点的结点称之为既非开始结点，也非终端结点的结点称之为内部结点内部结点。3、结构分类、结构分类线性结构线性结构 只有一个开始结点和一个终端结点，其它结点只有一只有一个开始结点和一个终端结点，其它结点只有一个前驱结点和一个后继结点，称之为线性结构。即元个前驱结点和一个后继结点，称之为线性结构。即元素之间存在着一对一的关系。素之间存在着一对一的关系。非线性结构非线性结构 如果一个结构不是线性结构，则称之为非线性结构。如果一个结构不是线性结构，则称之为非线性结构。一般地，结构中至少有一个结点存在不止一个前驱结一般地，结构中至少有一个结点存在不止一个前驱结点或后继结点。非线性结构有两类：点或后继结点。非线性结构有两类：a、树形结构：元素之间存在着一对多的关系。树形结构：元素之间存在着一对多的关系。b、图形结构：元素之间存在着多对多的关系。图形结构：元素之间存在着多对多的关系。线性结构线性结构树形结构树形结构 图形结构图形结构141312112345678910456231 1 2 3 4 51二、数据的存储方法二、数据的存储方法 一般地，数据的存储方法有四种：一般地，数据的存储方法有四种：顺序存储顺序存储链式存储链式存储索引存储索引存储散列存储散列存储（后两种方法主要用于查找，本课程不作详述）（后两种方法主要用于查找，本课程不作详述）1、顺序存储顺序存储 把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理位置相邻的存储单元之中。通常借助理位置相邻的存储单元之中。通常借助于程序设计语言中的数组来实现。于程序设计语言中的数组来实现。2、链式存储、链式存储 逻辑上相邻的数据元素不要求其物逻辑上相邻的数据元素不要求其物理存储位置相邻，元素间的逻辑关系用理存储位置相邻，元素间的逻辑关系用附设的指针域来表示。通常借助于程序附设的指针域来表示。通常借助于程序设计语言中的指针来实现。设计语言中的指针来实现。例如：例如：有数据结构有数据结构B=(D，R)，其中其中 D=d1,d2,d3,d4,d5 R=r r=,则用上述两种存储结构表示为：则用上述两种存储结构表示为：d1d2d3d4d5 10001005101010151020 d5 d35000 d14000 d22000 d41000 顺序存储顺序存储（假设每个元素占（假设每个元素占5个存储单元）个存储单元）链式存储链式存储10002000300040005000头指针变量头指针变量存储地址存储地址存储地址存储地址数据域数据域指针域指针域3000数据域数据域链式存储图示为：链式存储图示为：d1d5headd2d3d4线性结构和非线性结构均可采用这两种存储方法。线性结构和非线性结构均可采用这两种存储方法。数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：插入、删除、查找数据的运算：插入、删除、查找、排序、修改等排序、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：2.2 线性表的基本概念线性表的基本概念一、线性表的定义一、线性表的定义 它是最常用且又最简单的线性结构。它是最常用且又最简单的线性结构。定义：定义：线性表是线性表是n(n0)个性质相同的数据元个性质相同的数据元素所构成的有限序列素所构成的有限序列(a1,a2,a3,.,an)。n称为线性表的长度。称为线性表的长度。当当n=0时，称为空表。时，称为空表。数据元素数据元素可以是很简单的整数、英文字母等，可以是很简单的整数、英文字母等，也可以是较复杂的元素。由复杂元素构成的线也可以是较复杂的元素。由复杂元素构成的线性表又称为文件，复杂数据元素称为记录。性表又称为文件，复杂数据元素称为记录。例如：例如：（1，2，7，5，3，9）(A，D，C，B，E )19851985年年4 4月月19861986年年1 1月月男男女女王东林王东林吴红吴红10041001100410011004100210041002出生年月出生年月性别性别姓名姓名学号学号上面这些都是线性表。上面这些都是线性表。二、线性表的基本运算二、线性表的基本运算线性表的初始化（构造一个空的线性表）线性表的初始化（构造一个空的线性表）求表长求表长取第取第i个数据元素个数据元素查找具有特定值的结点，确定其序号查找具有特定值的结点，确定其序号插入操作（在原表的第插入操作（在原表的第i个位置上插入新元素个位置上插入新元素）删除操作（删除原表中第删除操作（删除原表中第i个元素个元素）随着线性表的存储方法不同，各种运算的实现随着线性表的存储方法不同，各种运算的实现方法也不一样。下面结合线性表的不同存储结方法也不一样。下面结合线性表的不同存储结构，讨论实现上述一些运算的算法。构，讨论实现上述一些运算的算法。2.3 线性表的顺序存储（顺序表）线性表的顺序存储（顺序表）一、顺序表的表示方法一、顺序表的表示方法 用一组地址连续的存储单元依次存放用一组地址连续的存储单元依次存放线性表的元素。线性表的元素。假设每个元素占用假设每个元素占用b个存储单元，并以个存储单元，并以元素的第一个存储单元地址作为元素的元素的第一个存储单元地址作为元素的存储地址（结点始址），则存储地址（结点始址），则 loc(ai+1)=loc(ai)+b 一般地，第一般地，第i个元素的存个元素的存储地址为储地址为 loc(ai)=loc(a1)+(i-1)*b 通常称线性表的第一个元通常称线性表的第一个元素素a1的存储地址为线性表的的存储地址为线性表的基地址，设为基地址，设为h，则有则有 loc(ai)=h+(i-1)*b an ai a2a1 hh+bh+(i-1)bh+(n-1)b顺序表特点：顺序表特点：1.逻辑上相邻的元素在物理存储上亦相邻；逻辑上相邻的元素在物理存储上亦相邻；2.任一元素的存取时间相同，是一种随机任一元素的存取时间相同，是一种随机存取结构。存取结构。3.（用类用类C语言描述顺序表语言描述顺序表）二、顺序表上基本运算的实现二、顺序表上基本运算的实现1、顺序表的初始化、顺序表的初始化 把当前表长置把当前表长置0。即：即：void initlist_sq(sqlist*L)*L.length=0;/*或或L-length=0*/2、顺序表的插入操作、顺序表的插入操作 要求在顺序表的第要求在顺序表的第i个位置上插入一个值为个位置上插入一个值为x的新元素。的新元素。原线性表原线性表:(a1,a2,ai-1,ai,ai+1,an)长度为长度为n 插入后的线性表插入后的线性表:(a1,a2,ai-1,x,ai,ai+1,an)长度为长度为n+1设设i的取值范围为的取值范围为1in+1，插入操作的步插入操作的步骤如下：骤如下：（算法描述算法描述）1.将将anai依次向后移动，为新元素让出位依次向后移动，为新元素让出位置；置；2.将将x置入空出的第置入空出的第i个位置；个位置；3.修改表长。修改表长。3、顺序表的删除操作、顺序表的删除操作 要求删除顺序表的第要求删除顺序表的第i个位置上的元素。个位置上的元素。原线性表原线性表 (a1,a2,ai-1,ai,ai+1,an)长度为长度为n 删除后的线性表删除后的线性表 (a1,a2,ai-1,ai+1,an)长度为长度为n-1设设i的取值范围为的取值范围为1in，删除操作的步骤如下：删除操作的步骤如下：将将ai+1an依次向前移动；依次向前移动；（算法描述算法描述）修改表长修改表长2.4 线性表的链式存储（链表）线性表的链式存储（链表）2.4.1单链表单链表1、单链表、单链表结点结构：结点结构：链表中每个结点有一个存放数据元素链表中每个结点有一个存放数据元素的域，另有一个域存放指向后继结点的的域，另有一个域存放指向后继结点的指针（表示逻辑关系），故称为单链表。指针（表示逻辑关系），故称为单链表。（用类用类C语言描述为一个结构语言描述为一个结构）数据域 指针域单链表的两种形式单链表的两种形式heada1ana2heada1a2an带头结点的单链表带头结点的单链表不带头结点的单链表不带头结点的单链表指针变量指针变量head中存放了链表中第一个结点的起始地中存放了链表中第一个结点的起始地址，称之为址，称之为头指针头指针。该指针变量是。该指针变量是“静态静态”定义定义的，即用的，即用NODE*head;定义了指针变量定义了指针变量head。链表中的结点是链表中的结点是“动态动态”生成的生成的(称之为结点变量称之为结点变量)，每个结点可以存放一个数据元素和后继结点的，每个结点可以存放一个数据元素和后继结点的起始地址。最后一个结点因为没有后继结点，故起始地址。最后一个结点因为没有后继结点，故其指针域中存放其指针域中存放NULL(空地址空地址)。当链表中没有数据元素当链表中没有数据元素(即空表即空表)时，第一种单链表时，第一种单链表保留头结点。即保留头结点。即 ，后一种，后一种head中为中为NULL。head建立一个空表的算法为建立一个空表的算法为(带头结点带头结点)：NODE *initlist_link（）NODE *p;p=(NODE*)malloc(sizeof(NODE);p-next=NULL;return(p);2、两个标准函数、两个标准函数 malloc 和和 free 设有变量定义：设有变量定义：NODE *p;则则p=(NODE*)malloc(sizeof(NODE)的作用是由系的作用是由系统生成（得到）一个统生成（得到）一个NODE类型的结点，同时将类型的结点，同时将该结点的起始地址赋给指针变量该结点的起始地址赋给指针变量p。free(p)的作用是由于系统回收（释放）一个由的作用是由于系统回收（释放）一个由p所指向的所指向的NODE类型的结点。类型的结点。注意点：注意点：每次调用每次调用malloc或或free函数只能得到或释放一个结点空间；函数只能得到或释放一个结点空间；用用malloc函数得到的结点中无确定的内容，必须由程序员函数得到的结点中无确定的内容，必须由程序员给予；给予；用用free函数释放一个结点空间，指针变量本身并未释放。函数释放一个结点空间，指针变量本身并未释放。2.4.2单链表上基本运算的实现单链表上基本运算的实现建立单链表建立单链表a.正向建：正向建：b.逆向建：逆向建：heada1ana2a1headp2 p1p2p1anan-1a1headan-2a1headpp算法的详细描述读者可参见本教材实践篇的实验算法的详细描述读者可参见本教材实践篇的实验2 单链表的插入操作单链表的插入操作 要求在带头结点的单链表中第要求在带头结点的单链表中第i个位置上插入一个值为个位置上插入一个值为x的新元素。的新元素。算法思想：算法思想：定义三个指针变量定义三个指针变量p、q和和s；(算法描述算法描述)a)在单链表中寻找第在单链表中寻找第i个元素位置，若找到，则由个元素位置，若找到，则由q指向指向第第i个位置，个位置，p指向第指向第i-1个位置，继续个位置，继续b)；否则结束。否则结束。b)向系统申请一个由向系统申请一个由s指向的新结点，并在数据域置入指向的新结点，并在数据域置入新元素新元素x。c)将将s指向的新结点插入指向的新结点插入q之前，结束。之前，结束。xp 第第i-1个位置个位置q 第第i个位置个位置s单链表的删除操作单链表的删除操作 要求在带头结点的单链表中删除第要求在带头结点的单链表中删除第i个位置的元个位置的元素。素。pq 第第i个位置个位置算法思想：算法思想：（算法描述算法描述）定义两个指针变量定义两个指针变量p和和q。a)在单链表中寻找第在单链表中寻找第i个元素位置，若找到则由个元素位置，若找到则由q指向第指向第i个位置，个位置，p指向第指向第i-1个位置，继续个位置，继续b)，否则结束。否则结束。b)从链表中删除从链表中删除q所指向的结点。所指向的结点。c)释放释放q所指向的结点空间，结束。所指向的结点空间，结束。2.4.3线性表的其它链式存储线性表的其它链式存储1、单循环链表、单循环链表 单循环链表是一种特殊的单循环链表是一种特殊的单链表单链表，其最，其最后一个结点的指针域中不存放后一个结点的指针域中不存放NULL(空空地址地址)，而是放入了链表的头指针。，而是放入了链表的头指针。带头结点的单循环链表带头结点的单循环链表不带头结点的单循环链表不带头结点的单循环链表heada1ana2a1a2anhead空表时空表时 head2、双向链表、双向链表结点结构：结点结构：链表中每一个结点除数据域和指向后继结点的指针链表中每一个结点除数据域和指向后继结点的指针域外，增加了一个指向前驱结点的指针域。域外，增加了一个指向前驱结点的指针域。用类用类C语言描述为：语言描述为：typedef struct dlnode data;struct dlnode *prior,*next;DLNODE;双向链表在做插入和删除操作时，不需要再用双向链表在做插入和删除操作时，不需要再用两个指针在链表上移动。两个指针在链表上移动。后继指针域后继指针域数据域数据域前驱指针域前驱指针域双向链表的形式双向链表的形式带头结点的双向链表带头结点的双向链表不带头结点的双向链表不带头结点的双向链表a1an非循环非循环循环循环heada1anhead非循环非循环循环循环headheada1ana1an3、静态链表、静态链表 用结构数组来描述静态链表。用结构数组来描述静态链表。描述方法：描述方法：#define maxsize 1000 /*定义链表的最大长度定义链表的最大长度*/typedef struct data;int next;SNODE;SNODE sdmaxsize;int sl;上图是一个带头结点的单链表，表示了线性表上图是一个带头结点的单链表，表示了线性表(a1,a2,a3,a4,a5,a6)的链式存储，的链式存储，sl为头指针为头指针变量。变量。1a24a5-1a66a15a42a33datanext0123456maxsize-1sl=02.5 栈栈2.5.1 栈的定义和基本运算栈的定义和基本运算1、栈的定义、栈的定义 实例：装网球的纸筒、子弹夹实例：装网球的纸筒、子弹夹 a1an定义：栈是限定在表的一端（表尾）进行定义：栈是限定在表的一端（表尾）进行 插入和删除操作的线性表。插入和删除操作的线性表。表尾表尾表头表头允许插入和删除的表尾端称为栈顶。允许插入和删除的表尾端称为栈顶。相应的表头端称为栈底。相应的表头端称为栈底。a1an栈顶栈顶栈底栈底栈的两个要素：存放栈元素的栈的两个要素：存放栈元素的存储空间和栈顶指针。存储空间和栈顶指针。栈的特点：数据元素后进先出栈的特点：数据元素后进先出 (LI FOLast In First Out)2、栈的基本运算栈的基本运算栈初始化栈初始化 initstack(s)建立一个空栈建立一个空栈s入栈入栈 push(s,x)把元素把元素x推入栈推入栈s的栈顶的栈顶出栈出栈 pop(s)删除栈删除栈s的栈顶元素的栈顶元素取栈顶元素取栈顶元素 gettop(s,x)取出栈取出栈s的栈顶元素送入的栈顶元素送入x，由由x返回返回a1an出栈出栈入栈入栈2.5.2栈的存储结构和运算的实现栈的存储结构和运算的实现1、顺序存储的栈顺序存储的栈(顺序栈顺序栈)用一组地址连续的存储单元依次存放自栈底到用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设栈顶指针栈顶的数据元素，同时附设栈顶指针top指示栈顶元指示栈顶元素在顺序栈中的位置。（素在顺序栈中的位置。（类类C语言描述为一个结构语言描述为一个结构）例如：例如：43210432104321043210top=-1top=010top=410157168top=210157在顺序栈上基本运算的实现：在顺序栈上基本运算的实现：栈初始化栈初始化 算法描述算法描述43210top=-1栈顶指针赋初值栈顶指针赋初值-1入栈入栈 算法描述算法描述4321043210top=11015top=2if(栈不满栈不满)栈顶指针加栈顶指针加1；将将x的值推入栈顶；的值推入栈顶；else 出错；出错；10157x=7出栈出栈 算法描述算法描述432101043210top=11015top=0if(栈不空栈不空)栈顶指针减栈顶指针减1；else 出错出错;取栈顶元素取栈顶元素算法描述算法描述4321043210top=11015top=1if(栈不空栈不空)栈顶元素送入栈顶元素送入x；else 出错出错;1015x=152、链式存储的栈链式存储的栈(链栈链栈)以单链表作为存储结构，头指针作为栈以单链表作为存储结构，头指针作为栈顶指针。顶指针。其节点结构与单链表的结构相同。其节点结构与单链表的结构相同。基本运算的实现读者可参见本教材实践篇实基本运算的实现读者可参见本教材实践篇实验验3。toptop8161081610即即三、三、栈的应用栈的应用1、算术表达式求值算术表达式求值算术表达式的组成：算术表达式的组成：运算符（运算符（*/）运算对象（整数）运算对象（整数）运算规则：运算规则：先乘除，后加减先乘除，后加减 同级运算符先左后右同级运算符先左后右算法思想算法思想:(需设立两个栈需设立两个栈运算符栈、操作数栈运算符栈、操作数栈)a.从左到右扫描算术表达式从左到右扫描算术表达式;b.遇到运算对象遇到运算对象(称操作数称操作数)，入操作数栈，入操作数栈;c.遇到运算符，若该运算符优先级高于运算遇到运算符，若该运算符优先级高于运算符栈的栈顶运算符，该运算符入栈；若不符栈的栈顶运算符，该运算符入栈；若不高于栈顶运算符，则栈顶运算符出栈，并高于栈顶运算符，则栈顶运算符出栈，并弹出操作数栈的两个操作数进行运算，运弹出操作数栈的两个操作数进行运算，运算结果入操作数栈算结果入操作数栈;d.重复上述过程，直至算术表达式扫描完毕。重复上述过程，直至算术表达式扫描完毕。例：例：#5+3*4#*53534512175运算符栈运算符栈操作数栈操作数栈计算结果为计算结果为172、数制转换数制转换将一个非负的十进制整数转换成一个八进制数。将一个非负的十进制整数转换成一个八进制数。算法思想：算法思想：将待转换的十进制整数除以将待转换的十进制整数除以8得到的得到的 余数压入栈中，再将商除以基数余数压入栈中，再将商除以基数8得得到的余数压入栈中，重复这一过程，到的余数压入栈中，重复这一过程，直到商为直到商为0结束。从栈中弹出的序列结束。从栈中弹出的序列即为转换结果。即为转换结果。算法描述算法描述例：例：将将102转换成八进制数。转换成八进制数。8 102 6 8 12 4 8 1 1 12 1 0646416逐个弹出元素得到的逐个弹出元素得到的146即为转换后的八即为转换后的八进制数进制数2.6 队列队列2.6.1队列的定义和基本运算队列的定义和基本运算1、队列的定义、队列的定义 实例：实例：排队购物排队购物 定义：定义：队列是限定在表的一端进行插入操作，而在队列是限定在表的一端进行插入操作，而在另一端进行删除操作的线性表。另一端进行删除操作的线性表。a1a2an删除删除插入插入队头队头队尾队尾 允许插入的一端称为队尾允许插入的一端称为队尾(rear)，允许删除的一允许删除的一端称为队头端称为队头(front)。上图中上图中a1为队头元素，为队头元素，an为为队尾元素。队尾元素。队列的特点：队列的特点：数据元素先进先出（数据元素先进先出（FIFOFirst In First Out）队列的三个要素：队列的三个要素：存放队列元素的存储空间；存放队列元素的存储空间；队头指针；队头指针；队尾指针。队尾指针。2、队列的基本运算、队列的基本运算队列初始化队列初始化 initqueue(q)建立一个空队列建立一个空队列q入队入队 addq(q,x)在队列在队列q的队尾插入元素的队尾插入元素x出队出队 delq(q)删除队列删除队列q的队头元素的队头元素取队头元素取队头元素 getfront(q,x)取出队列取出队列q的队头元素置入的队头元素置入x，由由x传出。传出。a1a2an出队出队入队入队2.6.2队列的存储结构和运算的实现队列的存储结构和运算的实现1、顺序存储的队列（顺序队列）、顺序存储的队列（顺序队列）用一组地址连续的存储单元依次存放从队头用一组地址连续的存储单元依次存放从队头到队尾的数据元素，同时附设两个指针到队尾的数据元素，同时附设两个指针front和和rear，分别指示队头元素和队尾元素的位置。分别指示队头元素和队尾元素的位置。（用类用类C语言描述为一个结构语言描述为一个结构）为方便起见，队头指针为方便起见，队头指针front指向队头元素的指向队头元素的前一个位置，队尾指针前一个位置，队尾指针rear指向队尾元素位置。指向队尾元素位置。43210432104321043210front10157rearrearfrontrearfrontrear168front在顺序队列上基本运算的实现：在顺序队列上基本运算的实现：v队列的初始化队列的初始化43210q-rearq-front队头指针和队尾指针均赋初值队头指针和队尾指针均赋初值-1。即：即：void initqueue(Squeue *q)q-front=q-rear=-1;v入队入队 (算法描述算法描述)if(队列不满队列不满)队尾指针加队尾指针加1；将元素将元素x插入到队尾；插入到队尾；else 出错；出错；432101015743210q-front1015q-rearq-rearq-frontv出队出队 (算法描述算法描述)if(队列不空队列不空)队头指针加队头指针加1;else 出错；出错；101574321015743210q-frontq-rearq-rearq-frontv取队头元素取队头元素 (算法描述算法描述)if(队列不空队列不空)队头元素置入队头元素置入x中，由中，由x传出传出;else 出错；出错；q.frontq.rear10157432101015743210q.rearq.front2、链式存储的队列、链式存储的队列(链队列链队列)用一个带头结点的单链表作为存储结构。用一个带头结点的单链表作为存储结构。同时根据队列的同时根据队列的FIFO原则，它需要一个原则，它需要一个头指针和一个尾指针。其结点结构和前头指针和一个尾指针。其结点结构和前面的单链表相同。面的单链表相同。图中图中front和和rear是两个独立的指针变量，是两个独立的指针变量，从结构性上考虑，通常把二者封装在一个从结构性上考虑，通常把二者封装在一个结构中。结构中。a1ana2frontrear基本运算的实现可参见本教材实践篇实验基本运算的实现可参见本教材实践篇实验3 END16、业余生活要有意义，不要越轨。华盛顿17、一个人即使已登上顶峰，也仍要自强不息。罗素贝克18、最大的挑战和突破在于用人，而用人最大的突破在于信任人。马云19、自己活着，就是为了使别人过得更美好。雷锋20、要掌握书，莫被书掌握；要为生而读，莫为读而生。布尔沃