数据结构（C语言版）

数据结构项目一共分为二个任务项目一数据结构导论任务一数据结构入门任务二算法与算法分析任务一数据结构入门一、基本术语二、数据的逻辑结构三、数据的存储结构四、数据类型一、基本术语1．数据2．数据元素3．数据项4．数据对象5．数据结构1．数据数据（data）是对客观事物的符号表示，在计算机科学中，是指所有能输入到计算机中并被计算机程序处理的符号的总称。2．数据元素数据元素（dataelement）是数据的基本单位，一个数据元素可由若干个数据项组成，此时的数据元素通常称为记录（record）。3．数据项数据项（dataitem）是数据不可再分的最小单位，如学生信息记录中的学号、姓名等。4．数据对象数据对象（dataobject）是性质相同的数据元素的集合，是数据的一个子集。5．数据结构数据结构（datastructure）是相互之间存在一种或多种特定关系的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。一般包括三个方面的内容：①数据的逻辑结构

②数据的物理结构

③数据的运算及实现

二、数据的逻辑结构数据元素之间除了同属于一个集合外，别无其他关系。数据元素之间是一对一的关系。每个数据元素都有唯一的前驱（第一个元素除外）和后继（最后一个元素除外）。数据元素之间是一对多的关系。在树形结构中，最上面的结点称为根节点，最下面的结点称为叶子结点。数据元素之间是多对多的关系。每个结点都可以有多个前驱或后继。三、数据的存储结构数据的存储结构或物理结构是指数据在计算机中的表示或存储方式，是逻辑结构在计算机中的实现，包括数据元素的表示和关系的表示。1．顺序存储结构2．链式存储结构1．顺序存储结构顺序存储结构是指逻辑上相邻的数据元素，其结点的物理位置（内存中的位置）也相邻，结点间的逻辑关系由存储单元的邻接关系体现。2．链式存储结构在链式存储结构中，结点间的逻辑关系由附加的指针字段来指示的，因此，链式存储结构通常借助于程序设计语言中的指针数据类型来实现。四、数据类型1．数据类型2．抽象数据类型1．数据类型数据类型（datatype）是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用来描述操作对象的特性。在用高级语言编写的程序中，每个变量、常量或表达式都有一个确定的数据类型。2．抽象数据类型抽象数据类型（abstractdatatype，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。ADT抽象数据类型名{数据元素：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>}ADT抽象数据类型名其格式定义如下：任务二算法与算法分析一、算法的概念二、算法的特性三、算法的描述方法四、算法设计的要求五、算法性能分析六、类C语言简介一、算法的概念在计算机领域，根据所要处理的问题，在数据的逻辑结构和物理结构基础上，在有限步骤内解决这一问题所采用的一组指令序列。在实际生活中，算法就是为解决某一问题所采取的方法和步骤。二、算法的特性有限性：有限步骤之内正常结束，不能形成无穷循环。确定性：算法中的每一个步骤必须有确定含义，不能有二义性。可行性：算法中的每一个步骤都应当能有效执行，并得到确切结果。输入：有0个或多个输入。输出：至少有一个或多个输出。三、算法的描述方法1．自然语言2．流程图3．伪代码4．程序设计语言【例】要求一组数据中的最大数和最小数。1．自然语言③重复步骤②，与第4、5等数进行比较，直至结束。①将第1个数和第2个数相比较，记录最大数与最小数。②将最大数和最小数与第3个数比较，记录最大数与最小数。2．流程图3．伪代码开始置i的初值为2置Min和Max的初值为a1当i≤n时，执行如下操作如果Min>ai,则使Min=ai

如果Max<ai,则使Max=aii=i+1（循环体到此结束）打印Max和Min值结束4．程序设计语言main(){inta[5]={50,23,89,12,90};//定义含有五个整数元素的数组

inti=1;//i为指示器，初始指向第2个数组元素

intMax,Min;//定义两个变量，用来保存当前的最大值和最小值

Max=a[0];//令当前的最大值为第1个数组元素

Min=a[0];//令当前的最小值为第1个数组元素

while(i<=4)//i≤4时循环

{if(Min>a[i])//如果当前数组元素小于当前最小值，则将当前数组元素值赋于当前最小值变量Min=a[i];if(Max<a[i]) //如果当前数组元素大于当前最大值，则将当前数/组元素值赋于当前最大值变量

Max=a[i];i=i+1; //循环变量递增1}printf("themaximumis%d,theminimumis%d",Max,Min);}四、算法设计的要求正确性：“正确”的含义可以分为三个层次：①对于几组输入数据能够得出满足要求的结果。②对于精心选择的典型、苛刻且带有刁难性的几组输入数据能够得到满足要求的结果。③对于一切合法的输入数据都能产生满足要求的结果。可读性：算法主要是为了人的阅读与交流，其次才是机器执行。因此，可读性好有助于人对算法的理解。高效率低存储量：通俗地说，效率指的是算法执行的时间。对于同一个问题，若有多个算法可以解决，执行时间短的算法效率就高。存储量指的是算法执行过程中所需要的最大存储空间。稳健性：当输入数据非法时，算法也能做出正确反应或进行相应的处理，而不会产生一些莫名其妙的输出结果。五、算法性能分析算法分析是每个程序设计人员应该掌握的技术。评价一个算法的优劣主要看执行这个算法所需的时间（时间复杂度）和存储空间（空间复杂度）。1．时间复杂度2．空间复杂度1．时间复杂度时间复杂度是指该算法的运行时间与问题规模的对应关系，记作T(n)＝O(f(n))其中，n表示问题的规模；T(n)表示算法中语句的执行次数（称为语句频度或时间频度）；f(n)为辅助函数；O(f(n))表示f(n)是T(n)的同数量级函数。2．空间复杂度一个程序在计算机上执行时，除了需要存储本身所用的指令、常数和输入数据以外，还需要一些对数据进行操作的辅助存储空间。因此，一个算法（程序）的空间复杂度是指程序运行从开始到结束所需的存储空间，记作S(n)＝O(f(n))其中，各参数的意义与上面相同，故不再赘述。六、类C语言简介类C语言就是类似C语言的语言，本书中的算法均使用这种语言进行描述，其目的是让编程人员在设计算法时能够更专注对算法思想的分析，而不受语言细节的约束。类C语言是标准C语言的扩充，个别处使用了对标准C语言的一种简化表示。数据结构项目二共分为三个任务项目二线性表任务一线性表的定义和基本操作任务二线性表的顺序存储结构任务三线性表的链式存储结构一、线性表的定义二、线性表的基本操作任务一线性表的定义和基本操作一、线性表的定义线性表是由n（n≥0）个类型相同的数据元素a1,a2,…,an组成的有限序列，数据元素之间是一对一的关系，记作L＝(a1,a2,…,ai－1,ai,ai＋1,…,an)二、线性表的基本操作①InitList(L)：初始化线性表L，即构造一个空的线性表L。②DestroyList(L)：线性表L已存在，将表L销毁。③ClearList(L)：线性表L已存在，将表L置为空表。④ListEmpty(L)：线性表L已存在，如果表L为空则返回TRUE，否则返回FALSE。⑤ListLength(L)：线性表L已存在，返回表L的长度，即表中数据元素

的个数。⑥GetElem(L,i)：线性表L已存在，返回表L中第i（1≤i≤ListLength(L)）个元素的值。⑦Locate(L,e)：线性表L已存在，返回表L中元素e所在位置；如果表L中不存在元素e，则返回0。⑧InsertList(L,i,e)：线性表L已存在，在表L中第i（1≤i≤ListLength(L)）个位置之前插入新的数据元素e，表L的长度加1。⑨DeleteList(L,i,e)：线性表L已存在且非空，删除表L中的第i个数据元素，并用e返回其值，表L的长度减1。⑩PriorElem(L,e)：线性表L已存在，若e是表L的数据元素且不是第一个，则返回数据元素e的前驱元素；否则操作失败。⑪NextElem(L,e)：线性表L已存在，若e是表L的数据元素且不是最后一个，则返回数据元素e的后继元素；否则操作失败。任务二线性表的顺序存储结构一、顺序表的结构特点

二、顺序表的基本操作

线性表的顺序存储是指，在内存中用一组地址连续的存储单元依次存储线性表中的各个数据元素。采用顺序存储结构的线性表称为顺序表。一、顺序表的结构特点假设线性表中有n个数据元素，每个元素占用k个存储单元，其中第一个数据元素a1的存储地址称为线性表的起始位置或基地址，线性表的顺序存储结构如图2-1所示。相邻两个数据元素的存储地址之间的关系：LOC(ai＋1)＝LOC(ai)＋k

第i个数据元素ai的存储地址：LOC(ai)＝LOC(a1)＋(i－1)×k

线性表的顺序存储结构是一种随机存取的存储结构。若已知线性表的起始位置（基地址）和表中每个数据元素所占存储单元的大小k，就可以计算出线性表中任意一个数据元素的存储地址，这种存取元素的方法称为随机存取法顺序表的存储结构通常用一维数组来描述，用C语言实现线性表的顺序存储结构的类型定义如下：#definec100 //线性表的最大长度typedefstruct{ElemTypeelem[MAXSIZE]; //存储线性表中数据元素的数组intlength; //线性表的当前长度}SeqList;typedefstruct{ElemType*elem; //线性表中数据元素的基地址intlength; //线性表的当前长度intlistsize; //当前为线性表分配的存储容量}SeqList;也可以这样来定义：定义一个顺序表的方法有两种：方法一：SeqListL，表示将L定义为SeqList类型的变量；方法二：SeqList*L，表示将L定义为指向SeqList类型的指针。对表中数据元素进行操作应使用L.elem[i]

对表中数据元素进行操作应使用L->elem[i]

二、顺序表的基本操作1．初始化顺序表2．插入数据元素3．删除数据元素4．查找数据元素1．初始化顺序表初始化顺序表操作是指构造一个空的顺序表，并为其分配存储空间。其算法描述如下：StatusInitList(SqList*L){ //初始化顺序表L->elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));//分配存储空间if(!L->elem)returnOVERFLOW; //存储空间分配失败L->length=0; //当前线性表长度为0L->listsize=LIST_MAX_SIZE; //初始化存储容量returnTRUE;}2．插入数据元素为了在顺序表中第i（1≤i≤n）个位置插入数据元素e，需先将第i个至第n个元素（共n－i＋1个）依次向后移动一个位置，再将e插入到第i个位置。若i＝n＋1，则只需在线性表的末尾插入e即可。算法描述如下：StatusListInsert(SqList*L,inti,ElemTypee){intj;if(i<1||i>L->length+1) returnFALSE; //i值不合法，出错处理if(L->length=L.listsize) //当前存储空间满

returnOVERFLOWfor(j=L->length–1;j>=i-1;j--) L->elem[j+1]=L->elem[j]; //第i个位置之后的元素依次向后移L->elem[i–1]=e; //将e插入到第i个位置L->length++; //表长增1returnTRUE;}假设在顺序表中第i个位置插入一个元素的概率为pi，则在长度为n的线性表中插入一个数据元素时，需要移动其他元素的平均次数为：该算法的时间复杂度为O(n)。3．删除数据元素删除顺序表中第i（1≤i≤n）个数据元素，需将第i＋1个至第n个元素（共n－i个）依次向前移动一个位置。顺序表进行删除操作的前后，其数据元素在存储空间中的位置变化如图2-3所示。算法描述如下：StatusListDelete(SqList*L,inti){//在顺序表L中删除第i个数据元素，其中1≤i≤L->lengthintj;if(i<1||i>L->length)returnFALSE;//i值不合法，出错处理for(j=i;j<L->length;j++) L->elem[j-1]=L->elem[j]; //第i个位置之后的元素依次向前移L->length--; //表长减1returnTRUE;}假设删除顺序表中第i个数据元素的概率为qi，则在长度为n的线性表中删除一个数据元素时，需要移动其他元素的平均次数为该算法的时间复杂度也为O(n)。在顺序表中查找值为e的数据元素，并返回该元素在表中的位置。4．查找数据元素方法：从第一个数据元素开始，依次将表中的元素与e进行比较，若相等，则返回该元素在表中的位置；否则，查找失败。算法描述如下：intLocate(SqListL,ElemTypee){//在顺序表中查找值为e的数据元素，查找成功，返回该元素的位置；否则返回0for(i=0;i<L.length;i++)if(L.elem[i]==e)returni+1; //查找成功，返回序号

return0;} //查找失败，返回0该算法的时间复杂度为O(n)。【例2-1】一个线性表L中的数据元素按升序排列，编写一个算法，实现在线性表中插入一个数据元素item，使得线性表仍然保持升序排列。算法设计如下：voidInsert(SqListL,ElemTypeitem){inti;intj;if(item>=L.elem[L.length-1])//item值大于表中最大的数据元素

L.elem[L.length]=item; //将item插入到表尾else{i=0;while(item>=L.elem[i]) //寻找item的插入位置ii++;ListInsert(&L,i,item);} //将item插入到位置iL.length++;} //表长增1任务三线性表的链式存储结构一、单链表的结构特点二、单链表的基本操作三、静态链表及其基本操作四、循环链表及其基本操作五、双向链表及其基本操作数据元素的存储结构，称为结点（Node）数据域：存储数据元素本身的数据信息指针域：存储直接后继元素地址的信息一、单链表的结构特点将n个数据元素通过其对应结点的指针域按其逻辑关系链接成一个链表，链表中的每个结点只包含一个指针域，这样的链表称为线性链表或单链表，其一般形式如图2-5所示。head称为头指针，用于指向单链表的第一个结点。由于单链表的最后一个结点没有直接后继，所以其指针域为“空”（NULL），用符号“∧”表示。单链表的存储结构定义：typedefstructNode{ //结点类型

ElemTypedata; //数据域

structNode*next; //指针域}Node,*LinkList;通常在单链表的第一个结点之前设立一个结点，称之为头结点。头结点的数据域可以不存储任何数据信息，也可以存储一个线性表中不包括的元素值；头结点的指针域存储第一个结点的地址信息。二、单链表的基本操作1．建立单链表2．插入数据元素3．删除数据元素4．查找数据元素5．求单链表的长度1．建立单链表LinkList*Create(LinkList*L){//建立一个单链表，将新结点插入表尾Node*r,*s;ElemTypec;inti;*L=(LinkList)malloc(sizeof(Node)); //为头结点分配存储空间r=*L; //r初值指向头结点for(i=1;i<=n;i++){READ(c); //获取一个数据元素s=(LinkList)malloc(sizeof(Node)); //生成一个新结点s->data=c; //将要插入数据元素的值赋给新结点的数据域s->next=NULL; //链表末尾结点指针域为空r->next=s; //将新结点插入到当前链表的表尾上r=s; } //r始终指向链表的当前表尾returnL;}算法描述如下：该算法的时间复杂度为O(n)

2．插入数据元素算法描述如下：StatusListInsert(LinkList*L,inti,ElemTypee){//在单链表L中第i个位置插入一个数据元素eNode*p,*s;intj=0;p=*L;while(p!=NULL&&j<i-1){//找到第i－1个结点

p=p->next;j++;}if(j!=i-1) returnFALSE; //未找到插入位置，出错处理s=(LinkList)malloc(sizeof(Node));//生成新结点s->data=e; //将要插入数据元素的值赋给新结点的数据域s->next=p->next; //插入新结点p->next=s;returnTRUE;}该算法的时间复杂度为O(n)

3．删除数据元素算法描述如下：StatusListDelete(LinkList*L,inti,ElemType*e){//删除单链表L中的第i个结点，并用e返回被删除的元素Node*p,*r;intj=0;p=*L;while(p->next!=NULL&&j<i-1){//找到第i－1个结点p=p->next;j++;}if(j!=i-1)returnFALSE; //未找到要删除的结点，出错处理r=p->next; //指针r指向要删除的结点p->next=p->next->next; //删除结点r*e=r->data; //将删除结点的值保存在e中free(r); //释放被删除结点所占的内存空间returnTRUE;}该算法的时间复杂度为O(n)

4．查找数据元素（1）按序号查找查找单链表中的第i个结点，算法描述如下：LinkListGetElem(LinkListL,inti){//在单链表L中查找第i个结点，并返回该结点的指针Node*p;intj=0;p=L; //指针p初值指向头结点while((p->next!=NULL)&&(j<i)){ //逐个结点扫描

p=p->next; //指向下一个结点

j++;} //已扫描过的结点数returnp;} //返回第i个结点算法的时间复杂度为O(n)

（2）按值查找查找单链表中值为e的结点，算法描述如下：LinkListLocate(LinkListL,ElemTypee){ //在单链表中查找值为e的结点，并返回该结点的指针

Node*p; p=L->next; //指针p初值指向表中第1个结点

while((p!=NULL)&&(p->data!=e)) //从表中第1个结点开始逐个比较

p=p->next; returnp;} //返回值为e的结点5．求单链表的长度intListLength(LinkListL){ //返回单链表的长度

Node*p; intj=0; //用来保存单链表的长度

p=L->next; //指针p初值指向表中第1个结点

while(p!=NULL) //用指针p依次指向表中各个结点

{p=p->next; j++;} returnj;} //返回单链表的长度三、静态链表及其基本操作1．初始化静态链表2．分配结点3．回收结点1．初始化静态链表开辟一块连续的存储空间，将整个数组空间初始化为一个空闲静态链表算法描述如下：SeqLinkList*InitList(SeqLinkList*S){ //初始化静态链表

inti; for(i=0;i<MAXSIZE-1;++i) S[i].cur=i+1; //设置各个结点的游标域

S[MAXSIZE-1].cur=0; //最后一个结点的cur值为0 returnS;}2．分配结点当进行插入操作时，从空闲链表上取得第一个结点作为待插入的新结点算法描述如下：intMalloc(SLinkList*S){//从空闲链表中分配结点，返回该结点下标i=S[0].cur; //取第一个空闲结点的下标if(S[0].cur)S[0].cur=S[i].cur;//空闲链表非空，则其头指针赋新值returni; //返回取出的结点下标}3．回收结点当进行删除操作时，将从链表中删除的结点链接到空闲链表中作为备用voidFree(SLinkList*S,intk){//将下标为k的空闲结点回收到空闲链表中S[k].cur=S[0].cur; //将下标为k的结点作为空闲链表的头结点S[0].cur=k;}算法描述如下：四、循环链表及其基本操作将表中最后一个结点的指针域指向头结点，从而形成一个首尾相接的链表，称为循环链表。所有结点被链接到一个环上，从循环链表中任一结点出发均可找到表中其他结点。尾指针（rear）a1＝*(rear－>next－>next)an＝*rear查找首尾结点的时间复杂度都为O(1)

五、双向链表及其基本操作1．插入数据元素2．删除数据元素1．插入数据元素在双向链表中第i个位置插入一个数据元素e，此时需要同时修改两个方向上的指针，如图2-17所示。StatusDListInsert(DLinkList*L,inti,ElemTypee){ //在双向循环链表L中第i个位置插入一个数据元素e DNode*s,*p if(!(p=GetElem(L,i)))returnFALSE;//插入位置不合法

s=(DLinkList)malloc(sizeof(DNode)//生成新结点

if(!s) returnFALSE; s->data=e; //将e赋给新结点的数据域

s->prior=p->prior; //新结点的前驱指向p结点的前驱

p->prior->next=s; //p结点前驱的后继指向新结点

s->next=p; //新结点的后继指向p结点

p->prior=s; //p结点的前驱指向新结点

returnTRUE;}算法描述如下：2．删除数据元素删除双向链表中的第i个结点，其指针变化情况如图2-18所示。算法描述如下：StatusDListDelete(DLinkList*L,inti,ElemType*e){//删除双向链表L中的第i个结点DNode*pif(!(p=GetElem(L,i)))returnFALSE;//i值不合法*e=p->data; //将要删除结点的值赋给ep->prior->next=p->next;//要删除结点前驱的后继指向其后继p->next->prior=p->prior;//要删除结点后继的前驱指向其前驱free(p); //释放p结点returnTRUE;}数据结构项目三共分为二个任务项目三栈和队列任务一栈的定义、存储结构和基本操作任务二队列的定义、存储结构和基本操作任务一栈的定义、存储结构和基本操作一、栈的定义及其基本操作二、栈的顺序存储结构三、栈的链式存储结构四、栈在递归中的应用一、栈的定义及其基本操作1．栈的定义2．栈的基本操作1．栈的定义栈是一种只允许在表的一端进行插入和删除操作的线性表。后进先出原则2．栈的基本操作①InitStack(S)：将栈S初始化为一个空栈。②DestroyStack(S)：栈S已存在，将栈S销毁。③ClearStack(S)：栈S已存在，将栈S置为空栈。④StackEmpty(S)：栈S已存在，如果栈S为空栈则返回TRUE，否则返回FALSE。⑤Push(S,e)：栈S已存在，在栈S的栈顶位置插入一个数据元素e。⑥Pop(S,e)：栈S非空，删除栈S的栈顶元素，并用e返回其值。⑦GetTop(S,e)：栈S非空，用e返回栈S的栈顶元素。二、栈的顺序存储结构1．顺序栈的结构特点2．顺序栈的基本操作3．多栈共享空间1．顺序栈的结构特点顺序栈是指采用顺序存储结构的栈，即在内存中用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设置一个指针top指示栈顶元素的当前位置。类型定义如下：#defineMAXSIZE100 //定义栈的最大容量typedefstruct{ElemTypeelem[MAXSIZE]; //存放栈中元素的一维数组空间inttop; //栈顶指针变量}SeqStack;top用于指示某一时刻栈顶元素的位置elem[0]用于存放栈中第一个元素2．顺序栈的基本操作（1）初始化（2）判断栈是否为空（3）进栈（4）出栈（5）取栈顶元素（1）初始化voidInitStack(SeqStack*S){ //构造一个空栈S S->top=0;}intStackEmpty(SeqStackS){ //判断S是否为空栈，为空时返回TRUE，否则返回FALSE return(S.top==0?TRUE:FALSE);}（2）判断栈是否为空intPush(SeqStack*S,ElemTypee){ //将数据元素e压入栈顶

if(S->top==MAXSIZE)returnFALSE;//栈已满，进栈失败

S->elem[S->top]=e; //将e插入栈顶

S->top++; //修改栈顶指针

returnTRUE;}（3）进栈（4）出栈intPop(SeqStack*S,ElemType*e){ //若栈不空，将栈顶元素弹出，并用e返回其值

if(S->top==0)returnFALSE; else { S->top--; //修改栈顶指针

*e=S->elem[S->top]; //保存栈顶元素

returnTRUE;}}（5）取栈顶元素intGetTop(SeqStackS,ElemType*e){ //若栈不空，则用e返回栈顶元素

if(S.top==0)returnFALSE; *e=S.elem[S.top-1]; //保存栈顶元素

returnTRUE;}3．多栈共享空间当元素进栈时，两个栈都是从两端向中间伸展。通过两个栈顶指针（top1和top2）的动态变化，使其存储空间相互补充。栈满的条件是：top1＝top2＋1栈空的条件是：top1＝0或top2＝M－1两栈共享空间的数据结构定义：#defineM100 //两栈共享的存储空间大小typedefstruct{ ElemTypeStack[M]; //两栈共享的一维数组空间

inttop[2]; //两栈的栈顶指针}DSeqStack;两栈共享空间的一些基本操作：（1）初始化（2）进栈（3）出栈（1）初始化voidInitStack(DSeqStack*S){ //初始化两个空栈

S->top[0]=0; S->top[1]=M-1;}intPush(DSeqStack*S,ElemTypee,inti){//将数据元素e压入第i个栈的栈顶if(S->top[0]==S->top[1]+1)returnFALSE;//栈已满，进栈失败switch(i){case0: //将e压入第1个栈

S->Stack[S->top[0]]=e; S->top[0]++; break;case1: //将e压入第2个栈

S->Stack[S->top[1]]=e; S->top[1]--; break;default: //参数错误

returnFALSE;} returnTRUE;}（2）进栈（3）出栈intPop(DSeqStack*S,ElemType*e,inti){//从第i个栈中弹出栈顶元素，并用e返回其值switch(i){case0: //从第1个栈弹出

if(S->top[0]==0) returnFALSE; *e=S->Stack[S->top[0]-1]; S->top[0]--; break;case1: //从第2个栈弹出

if(S->top[1]==M-1) returnFALSE; *e=S->Stack[S->top[1]+1]; S->top[1]++; break;default: //参数错误

returnFALSE;}returnTRUE;}三、栈的链式存储结构1．链栈的结构特点2．链栈的基本操作1．链栈的结构特点链栈是指利用一个单链表结构来实现的栈，即栈中的每一个数据元素用一个结点来表示，同时设置一个指针top指示栈顶元素的当前位置。链栈的类型定义如下：typedefstructSNode{ ElemTypedata; //数据域

structSNode*next; //指针域}SNode;typedefstruct{ structSNode*top; //栈顶指针}LinkStack;2．链栈的基本操作（1）初始化（2）进栈（3）出栈（1）初始化voidInitStack(LinkStack*S){ //将栈S初始化为空栈

S->top=NULL; //栈顶指针为空}（2）进栈intPush(LinkStack*S,ElemTypee){//将数据元素e压入链栈LinkStack*temp;temp=(LinkStack)malloc(sizeof(structNode));//生成新结点if(temp==NULL)returnFALSE; //分配空间失败temp->data=e; //为新结点数据域赋值temp->next=S->top; //将新结点插入栈顶S->top=temp; //修改栈顶指针returnTRUE;}（3）出栈intPop(LinkStack*S,ElemType*e){ //将栈顶元素弹出，并用e返回其值

LinkStack*temp; if(S->top==NULL) returnFALSE; //栈为空，出栈失败

temp=S->top;S->top=S->top->next; //修改栈顶指针

*e=temp->data; //保存栈顶元素的值

free(temp); //释放出栈结点

returnTRUE;}四、栈在递归中的应用指一个函数在定义自身的同时又直接或间接地调用自身

二阶Fibonacci数列C语言函数描述如下：intfib(intn){A1: if(n==0)return0;A2: elseif(n==1) return1;A3: elsereturnfib(n-1)+fib(n-2);A4: }Fib(3)递归栈的存储空间变化情况：任务二队列的定义、存储结构和基本操作一、队列的定义及其基本操作二、队列的顺序存储结构三、队列的链式存储结构一、队列的定义及其基本操作1．队列的定义2．队列的基本操作队列是另一种操作受限的线性表，它只允许在表的一端进行插入操作，而在另一端进行删除操作。1．队列的定义2．队列的基本操作①InitQueue(Q)：将队列Q初始化为一个空队列。②DestroyQueue(Q)：队列Q已存在，将队列Q销毁。③ClearQueue(Q)：队列Q已存在，将队列Q置为空队列。④QueueEmpty(Q)：队列Q已存在，如果Q为空队列则返回TRUE，否则返回FALSE。⑤EnQueue(Q,e)：队列Q已存在，插入一个数据元素e为新的队尾元素。⑥

DeQueue(Q,e)：队列Q非空，删除Q的队头元素，并用e返回其值。⑦GetHead(Q,e)：队列Q非空，用e返回Q的队头元素。二、队列的顺序存储结构1．顺序队列2．循环队列的结构特点3．循环队列的基本操作1．顺序队列在内存中用一组地址连续的存储单元依次存放从队头到队尾的数据元素，同时设置两个指针front和rear分别指示队头元素和队尾元素的位置。#defineMAXSIZE100 //队列的最大长度typedefstruct{ ElemTypeelem[MAXSIZE];//存放队列中元素的一维数组空间

intfront; //头指针

intrear; //尾指针}SeqQueue;顺序队列的类型定义如下：2．循环队列的结构特点将队列的存储空间看成一个环状的空间，即将队列的首、尾的位置连接起来形成的结构称为循环队列。一般规定：少用一个元素的存储空间，当队列尾指针的下一个位置是队列头指针时，则停止进队操作，此时队列已满。循环队列满的条件是：（rear＋1）modMAXSIZE＝front循环队列空的条件是：front＝rear3．循环队列的基本操作（1）初始化（2）判断队列是否为空（3）进队（4）出队（5）取队头元素（1）初始化voidInitQueue(SeqQueue*Q){ //将Q初始化为一个空的循环队列

Q->front=Q->rear=0;}（2）判断队列是否为空intQueueEmpty(SeqQueueQ){ //判断Q是否为空队列，为空时返回TRUE，否则返回FALSE if(Q.front==Q.rear) returnTRUE; elsereturnFALSE;}（3）进队intEnQueue(SeqQueue*Q,ElemTypee){//将数据元素e插入到队列中if((Q->rear+1)%MAXSIZE==Q->front)//队列已满，插入失败returnFALSE;Q->elem[Q->rear]=e; //将e插入队尾Q->rear=(Q->rear+1)%MAXSIZE;//重新设置尾指针returnTRUE;}（4）出队intDeQueue(SeqQueue*Q,ElemType*e){ //若队列不空，则删除Q的队头元素，并用e返回其值

if(Q->front==Q->rear) //队列空，删除失败

returnFALSE; *e=Q->elem[Q->front]; //用e返回队头元素

Q->front=(Q->front+1)%MAXSIZE;//重新设置头指针

returnTRUE;}（5）取队头元素intGetFront(SeqQueueQ,ElemType*e){ //若队列不空，则用e返回队头元素

if(Q.front==Q.rear)returnFALSE; *e=Q.elem[Q.front]; //保存队头元素

returnTRUE;}}三、队列的链式存储结构1．链队列的结构特点2．链队列的基本操作1．链队列的结构特点采用链表形式表示的队列称为链队列，队列中每一个元素对应链表中的一个结点，并设置两个分别指示队头和队尾的指针。链队列的类型定义如下：typedefstructNode{ ElemTypedata; //数据域

structNode*next; //指针域}LinkQueueNode;typedefstruct{ LinkQueueNode*front; //队头指针

LinkQueueNode*rear; //队尾指针}LinkQueue;2．链队列的基本操作（1）初始化（2）进队（3）出队（1）初始化voidInitQueue(LinkQueue*Q){//将Q初始化为一个空的链队列Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));//生成头结点if(Q->front==NULL)returnFALSE;//存储空间分配失败Q->rear=Q->front; //队头指针和队尾指针都指向头结点Q->front->next=NULL;returnTRUE;}intEnQueue(LinkQueue*Q,ElemTypee){//将数据元素e插入到队列中LinkQueueNode*NewNode;NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));//生成新结点if(NewNode==NULL)returnFALSE;//存储空间分配失败NewNode->data=e; //为新结点的数据域赋值NewNode->next=NULL; Q->rear->next=NewNode; //将新结点插入队尾Q->rear=NewNode; //使队尾指针指向新结点returnTRUE;}（2）进队intDeQueue(LinkQueue*Q,ElemType*e){ //若队列不空，则删除Q的队头元素，并用e返回其值

LinkQueueNode*p; if(Q->front==Q->rear) //队列空，删除失败

returnFALSE; p=Q->front->next; //从队头取出第一个结点

*e=p->data; //用e返回结点p的值

Q->front->next=p->next; //结点p出队

if(Q->rear==p)//如果队列中只有一个结点p，则p出队后成为空队列

Q->rear=Q->front; free(p); //释放存储空间

returnTRUE;}（3）出队数据结构项目四共分为四个任务项目四串和数组任务一串的定义、存储结构和基本操作任务二数组的定义和存储结构任务三矩阵的压缩存储任务四广义表的定义和存储结构任务一串的定义、存储结构和基本操作一、串的定义及其基本操作二、定长顺序存储结构三、堆存储结构四、块链存储结构1．串的定义一、串的定义及其基本操作2．串的基本操作1．串的定义串（string）是零个或多个字符组成的有限序列，通常记作：S＝"a1a2a3…an"（n≥0）串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为该子串的主串。子串在主串中第一次出现时第一个字符的位置称为子串的位置。当两个串的长度相等，并且各个对应位置的字符都相等时，称两个串是相等的。2．串的基本操作①StrAssign(S,string)：串赋值。②StrEmpty(S)：判断串是否为空。③StrCompare(S,T)：串比较。生成一个值为string的串S，string是字符串常量。若串S为空串，则返回TRUE；否则返回FALSE。已知串S和串T，若S＞T，则返回1；若S＝T，则返回0；若S＜T，则返回－1。这里的比较是按字典顺序进行的。例如，比较"that"和"this"，"th"相同，由于"a"＜"i"，故"that"＜"this"；又如"in"和"into"，"in"相同，但"into"长，故"in"＜"into"。④StrCopy(T,S)：串复制。已知串S，将串S的内容复制到串T中。⑤StrLength(S)：求串的长度。已知串S，返回串S的长度，即串中元素的个数。⑥StrClear(S)：串清空。已知串S，将串S清为空串。⑦Concat(T,S1,S2)：串连接。⑧SubString(Sub,S,pos,len)：求子串。已知串S1和串S2，用T返回由S1和S2连接而成的新串。已知串S，1≤pos≤StrLength(S)且1≤len≤

StrLength(S)－pos＋1，用Sub返回串S的第pos个字符起长度为len的子串。⑨StrIndex(S,T,pos)：串定位。已知串S和串T（非空），1≤pos≤StrLength(S)，若串S中存在和串T相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则返回0。⑩StrReplace(S,T,V)：串置换。⑪StrInsert(S,pos,T)：串插入。⑫StrDelete(S,pos,len)：串删除。⑬StrDestroy(S)：串销毁。已知串S、串T（非空）和串V，用串V替换主串S中出现的所有与T相等且不重叠的子串。已知串S和串T，1≤pos≤StrLength(S)＋1，在串S的第pos个位置之前插入串T。已知串S，1≤pos≤StrLength(S)－len＋1，在串S中删除第pos个位置起长度为len的子串。已知串S，将串S销毁以释放内存空间。二、定长顺序存储结构1．定长顺序串的定义2．定长顺序串的基本操作1．定长顺序串的定义串的定长顺序存储结构指用一组地址连续的存储单元存放串的字符序列。类型定义如下：#defineMAXLEN255 //串的最大长度typedefstruct{ charch[MAXLEN]; //数组ch的每个分量存储串的一个字符

intlength; //串的长度}SString;字符串“string”的存储结构：在C语言中以空字符“\0”表示串值结束，但它不计入串的实际长度2．定长顺序串的基本操作（1）串的赋值（2）判断串是否为空（3）串比较（4）串复制（5）求串长（6）串清空（7）串连接（8）求子串（9）串定位（10）串插入（11）串删除（1）串的赋值voidStrAssign(SString*S,char*string){//生成一个值为string的串S，string是一个字符串常量char*str;intlen,i;for(len=0,str=string;str;len++,str++);

//求串string的长度，串结束符为"\0"if(len==0) //为空串{S->ch[0]='\0';S->length=0;}else{for(i=0;i<len;i++) //为串S赋值S->ch[i]=string[i];S->length=len;}} //赋予串的长度（2）判断串是否为空intStrEmpty(SStringS){//判断串是否为空串，若为空，则返回TRUE；否则返回FALSE if(!S.length) returnTRUE; elsereturnFALSE;}（3）串比较intStrCompare(SStringS,SStringT){//已知串S和串T，若S＞T，则返回1；

若S＝T，则返回0；若S＜T，则返回－1inti;for(i=0;i<S.length&&i<T.length;i++) if(S.ch[i]!=T.ch[i]) return(S.ch[i]-T.ch[i]);return(S.length–T.length);}（4）串复制voidStrCopy(SString*T,SStringS){ //将串S的内容复制到串T中

inti; for(i=0;i<S.length;i++) T->ch[i]=S.ch[i]; T->length=S.length;}（5）求串长intStrLength(SStringS){ //返回串S的长度

return(S.length);}（6）串清空voidStrClear(SString*S){ //将串S清为空串

S->length=0;}（7）串连接将串S1和串S2进行串连接时，根据S1和S2长度的不同，可能出现以下三种情况：①当S1.length＋S2.length≤MAXLEN时，则将S2直接加在S1的后面；②当S1.length＋S2.length＞MAXLEN，而S1.length＜MAXLEN时，则与S1连接后，S2中超出MAXLEN的部分被截断；③当S1.length＝MAXLEN时，则S2全部被舍弃，不需要连接。算法描述如下：intConcat(SString*T,SStringS1,SStringS2){//用T返回由串S1和串S2连接而成的新串，

若未截断则返回TRUE；否则返回FALSEinti;if(S1.length+S2.length<=MAXLEN)

//连接后串的长度小于MAXLEN{for(i=0;i<S1.length;i++) T->ch[i]=S1.ch[i];for(i=0;i<S2.length;i++) T->ch[S1.length+i]=S2.ch[i];T->length=S1.length+S2.length;returnTRUE;}elseif(S1.length<MAXLEN) {//连接后串长大于MAXLEN，但串S1的长度小于MAXLEN，即串S2部分被截断for(i=0;i<S1.length;i++)T->ch[i]=S1.ch[i];for(i=S1.length;i<MAXLEN;i++)T->ch[i]=S2.ch[i-S1.length];T->length=MAXLEN;returnFALSE;}else {//串S1的长度等于MAXLEN，即串S2全部被截断for(i=0;i<MAXLEN;i++)T->ch[i]=S1.ch[i];returnFALSE;}}（8）求子串intSubString(SString*Sub,SStringS,intpos,intlen){//用Sub返回串S的第pos个字符起长度为len的子串inti;if(pos<0||pos>=S.length||len<1||len>S.length-pos){ sub->length=0; returnFALSE;}for(i=0;i<len;i++)sub->ch[i]=S.ch[pos+i];sub->length=len;returnTRUE;}（9）串定位intStrIndex(SStringS,SStringT,intpos){//返回串T在主串S中第pos个字符之后第一次出现的位置inti,j;if(S.length==0||T.length==0||pos<0) returnFALSE;i=pos; j=0;while(i<S.length&&j<T.length){if(S.ch[i]==T.ch[j]){i++; j++;}else{i=i–j+1;j=0;}}if(j>=T.length) return(i-j);elsereturn0;}（10）串插入在串S的第pos个位置之前插入串T时，设pos前的部分为串S1，后面的部分为串S2，则根据插入后串S长度的不同，可能有以下三种情况：①当S.length＋T.length≤MAXLEN时，则将S2后移T.length个位置，再将T插入；②当S.length＋T.length＞MAXLEN，而S1.length＋T.length＜MAXLEN时，则将S2后移T.length个位置时超出MAXLEN的部分被截断，再将T插入；③当S1.length＋T.length＞MAXLEN时，则将S2全部舍弃（不需要后移），且在T插入时超出MAXLEN的部分被截断。算法描述如下：intStrInsert(SString*S,intpos,SStringT){//在串S的第pos个位置之前插入串Tinti;if(pos<0||pos>S->length||S->length==0)returnFALSE;//插入位置不合法if(S->length+T.length<=MAXLEN)

//插入后串S长小于等于MAXLEN{for(i=S->length–1+T.length;i>=pos+T.length;i--)

//串S的后半部分后移S->ch[i]=S->ch[i–T.length]; //在串S中插入串Tfor(i=0;i<T.length;i++)S->ch[pos+i]=T.ch[i];S->length=S->length+T.length;}elseif(pos+T.length<=MAXLEN){//插入后串S长大于MAXLEN，但串T可以全部插入//串S的后半部分去掉溢出部分后后移for(i=MAXLEN–1;i>pos–1+T.length;i--) S->ch[i]=S->ch[i–T.length];for(i=0;i<T.length;i++) //在串S中插入串T S->ch[pos+i]=T.ch[i];S->length=MAXLEN;}else //串T需部分截断{for(i=0;i<MAXLEN–pos;i++) //在串S中插入串TS->ch[pos+i]=T.ch[i];S->length=MAXLEN;}returnTRUE;}（11）串删除intStrDelete(SString*S,intpos,intlen){//在串S中删除第pos个位置起长度为len的子串inti;if(pos<0||pos>S->length-len) //删除位置不合法

returnFALSE; for(i=pos+len;i<S->length;i++) S->ch[i-len]=S->ch[i]; S->length=S->length–len; returnTRUE;}三、堆存储结构1．堆串的定义2．堆串的基本操作1．堆串的定义堆存储结构仍然是以一组地址连续的存储单元存放串的字符序列，但它们的存储空间是在程序执行过程中动态分配的。堆串的类型定义如下：typedefstruct{ char*ch; //按串长分配存储区，指示串的起始地址

intlength; //串的长度}HString;2．堆串的基本操作（1）串的赋值（2）串复制（3）串清空（4）串连接（5）求子串（6）串插入（7）串删除（1）串的赋值intStrAssign(HString*S,char*string){//生成一个值为string的串S，string是一个字符串常量char*str;intlen;for(len=0,str=string;str;len++,str++); //求串string的长度，串结束符为"\0"if(len==0) //为空串{S->ch=NULL;S->length=0;}else{S->ch=(char*)malloc(len*sizeof(char));//分配存储空间if(!S->ch)returnFALSE; //存储空间分配失败for(i=0;i<len;i++) //为串S赋值

S->ch[i]=string[i];S->length=len; //赋予串的长度}returnTRUE;}（2）串复制intStrCopy(HString*T,HStringS){ //将串S的内容复制到串T中

inti; T->ch=(char*)malloc(S.length);//为串T分配存储空间

if(!T->ch) returnFALSE //空间分配失败

for(i=0;i<S.length;i++) T->ch[i]=S.ch[i]; T->length=S.length; returnTRUE;}（3）串清空voidStrClear(HString*S){ //将串S清为空串

if(S->ch) free(S->ch); //释放旧空间

S->ch=NULL S->length=0;}（4）串连接intConcat(HString*T,HStringS1,HStringS2){//用T返回由串S1和串S2连接而成的新串，

若未截断则返回TRUE；否