数据结构完整版课件全套ppt教学教程 最全电子讲义（最新）.ppt

《数据结构完整版课件全套ppt教学教程 最全电子讲义（最新）.ppt》由会员分享，可在线阅读，更多相关《数据结构完整版课件全套ppt教学教程 最全电子讲义（最新）.ppt（500页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构项目一共分为二个任务项目一共分为二个任务项目一项目一 数据结构导论数据结构导论任务一任务一 数据结构入门数据结构入门任务二任务二 算法与算法分析算法与算法分析 数据结构数据结构项目二共分为三个任务项目二共分为三个任务项目二项目二 线性表线性表任务一任务一 线性表的定义和基本操作线性表的定义和基本操作 任务二任务二 线性表的顺序存储结构线性表的顺序存储结构 任务三任务三 线性表的链式存储结构线性表的链式存储结构 一、线性表的定义一、线性表的定义 二、线性表的基本操作二、线性表的基本操作 任务一任务一 线性表的定义和基本操作线性表的定义和基本操作 一、线性表的定义一、线性表的定义

2、线性表是由线性表是由n（n0）个类型相同的数据元素个类型相同的数据元素a1,a2,an组成的有限组成的有限序列，数据元素之间是一对一的关系，记作序列，数据元素之间是一对一的关系，记作L(a1, a2, , ai1, ai, ai1, , an)二、线性表的基本操作二、线性表的基本操作 InitList (L)：初始化线性表初始化线性表L，即，即构造构造一个一个空空的线性的线性表表L。 DestroyList (L)：线性表线性表L已存在，已存在，将表将表L销毁销毁。 ClearList (L)：线性表线性表L已存在，将已存在，将表表L置为空表置为空表。 ListEmpty (L)：线性表线性表

3、L已存在，如果表已存在，如果表L为空为空则返回则返回TRUE，否否则则返回返回FALSE。 ListLength (L)：线性表线性表L已存在，已存在，返回表返回表L的长度的长度，即表中数据元素，即表中数据元素 的个数。的个数。 GetElem (L, i)：线性表线性表L已存在，已存在，返回返回表表L中中第第i（1iListLength (L)）个个元素的值元素的值。 Locate (L, e)：线性表线性表L已存在，已存在，返回表返回表L中元素中元素e所在位置所在位置；如果表；如果表L中不存在元素中不存在元素e，则返回，则返回0。 InsertList (L, i, e)：线性表线性表L已

4、存在，已存在，在在表表L中中第第i（1iListLength (L)）个位置之前插入个位置之前插入新的数据元素新的数据元素e，表，表L的长度加的长度加1。 DeleteList (L, i, e)：线性表线性表L已存在且非空，已存在且非空，删除删除表表L中的中的第第i个数据元个数据元素素，并用并用e返回其值返回其值，表，表L的长度减的长度减1。 PriorElem (L, e)：线性表线性表L已存在，若已存在，若e是表是表L的数据元素且不是第一的数据元素且不是第一个，则个，则返回返回数据元素数据元素e的前驱元素的前驱元素；否则操作失败。；否则操作失败。 NextElem (L, e)：线性表线

5、性表L已存在，若已存在，若e是表是表L的数据元素且不是最后的数据元素且不是最后一个，则一个，则返回返回数据元素数据元素e的后继元素的后继元素；否则操作失败。；否则操作失败。 任务二任务二 线性表的顺序存储结构线性表的顺序存储结构 一、顺序表的一、顺序表的结构特点结构特点 二、顺序表的二、顺序表的基本操作基本操作 线性表的线性表的顺序存储顺序存储是指，在内存中用一是指，在内存中用一组地址连续的存储单元依次存储组地址连续的存储单元依次存储线性表中的各个线性表中的各个数据元素数据元素。采用顺序存储结构的线性表称为采用顺序存储结构的线性表称为顺序表顺序表。一、顺序表的结构特点一、顺序表的结构特点 假设

6、线性表中有假设线性表中有n个数据元素，每个元素占用个数据元素，每个元素占用k个存储单元，其中第一个存储单元，其中第一个数据元素个数据元素a1的存储地址称为线性表的的存储地址称为线性表的起始位置或基地址起始位置或基地址，线性表的，线性表的顺序存储结构如图顺序存储结构如图2-1所示。所示。 相邻两个数据元素的存相邻两个数据元素的存储地址之间的关系：储地址之间的关系： LOC(ai1)LOC(ai)k 第第i个数据元素个数据元素ai的存储地址：的存储地址： LOC(ai)LOC(a1)(i1)k 线性表的顺序存储结构是一种线性表的顺序存储结构是一种随机存取随机存取的存储结构。的存储结构。 若已知线性

7、表的起始位置（基地址）和表中每个数据元素所占若已知线性表的起始位置（基地址）和表中每个数据元素所占存储单元的大小存储单元的大小k k，就可以计算出线性表中任意一个数据元素，就可以计算出线性表中任意一个数据元素的存储地址，这种存取元素的方法称为随机存取法的存储地址，这种存取元素的方法称为随机存取法顺序表的存储结构通常用一维数组来描述，用顺序表的存储结构通常用一维数组来描述，用C语言实现线性表的顺语言实现线性表的顺序存储结构的类型定义如下：序存储结构的类型定义如下： #define c 100/线性表的最大长度线性表的最大长度typedef structElemType elem MAXSIZE;

8、 /存储线性表中数据元素的数组存储线性表中数据元素的数组int length;/线性表的当前长度线性表的当前长度SeqList;typedef structElemType *elem;/线性表中数据元素的基地址线性表中数据元素的基地址int length;/线性表的当前长度线性表的当前长度int listsize;/当前为线性表分配的存储容量当前为线性表分配的存储容量SeqList;也可以这样来定义：也可以这样来定义： 定义一个顺序表的方法有两种：定义一个顺序表的方法有两种： 方法一方法一：SeqList L，表示将，表示将L L定义为定义为SeqList类型的变量；类型的变量； 方法二方法

9、二：SeqList *L，表示将，表示将L L定义为指向定义为指向SeqList类型的指针。类型的指针。 对表中数据元素进行操作应使用对表中数据元素进行操作应使用L.elemi 对表中数据元素进行操作应使用对表中数据元素进行操作应使用L-elemi 二、顺序表的基本操作二、顺序表的基本操作 1初始化顺序表初始化顺序表 2插入数据元素插入数据元素 3删除数据元素删除数据元素 4查找数据元素查找数据元素 1初始化顺序表初始化顺序表 初始化顺序表操作是指构造一个空的顺序表，并为其分配存储空间。初始化顺序表操作是指构造一个空的顺序表，并为其分配存储空间。 其算法描述如下：其算法描述如下：Status

10、InitList (SqList *L)/初始化顺序表初始化顺序表L - elem = (ElemType *) malloc (MAXSIZE * sizeof (ElemType); /分配存储空间分配存储空间if (! L - elem) return OVERFLOW; /存储空间分配失败存储空间分配失败L - length = 0;/当前线性表长度为当前线性表长度为0L - listsize = LIST_MAX_SIZE; /初始化存储容量初始化存储容量return TRUE; 2插入数据元素插入数据元素 为了在顺序表中第为了在顺序表中第i（1in）个位置插入数据元素个位置插入数据

11、元素e，需先，需先将第将第i个至第个至第n个元素（共个元素（共ni1个）依次向后移动一个位个）依次向后移动一个位置，再将置，再将e插入到第插入到第i个位置。个位置。若若in1，则只需在线性表，则只需在线性表的末尾插入的末尾插入e即可。即可。 算法描述如下：算法描述如下： Status ListInsert (SqList *L, int i, ElemType e)int j;if (i L - length + 1)return FALSE; /i值不合法，出错处理值不合法，出错处理if (L - length = L.listsize) /当前存储空间满当前存储空间满return OVER

12、FLOWfor (j = L - length 1; j = i - 1; j -)L - elem j + 1 = L - elemj;/第第i个位置之后的元素依次向后移个位置之后的元素依次向后移L - elemi 1 = e; /将将e插入到第插入到第i个位置个位置L - length +; /表长增表长增1return TRUE; 假设在顺序表中第假设在顺序表中第i个位置插入一个元素的概率为个位置插入一个元素的概率为pi，则在长度为，则在长度为n的的线性表中插入一个数据元素时，需要移动其他元素的平均次数为：线性表中插入一个数据元素时，需要移动其他元素的平均次数为： 该算法的时间复杂度为该

13、算法的时间复杂度为O(n)。 3删除数据元素删除数据元素 删除顺序表中第删除顺序表中第i（1in）个个数据元素，需将第数据元素，需将第i1个至第个至第n个元素（共个元素（共ni个）依次向前个）依次向前移动一个位置。顺序表进行删移动一个位置。顺序表进行删除操作的前后，其数据元素在除操作的前后，其数据元素在存储空间中的位置变化如图存储空间中的位置变化如图2-3所示。所示。算法描述如下：算法描述如下： Status ListDelete (SqList *L, int i)/在顺序表在顺序表L中删除第中删除第i个数据元素，其中个数据元素，其中1iL-lengthint j;if (i L - len

14、gth) return FALSE; /i值不合法，出错处理值不合法，出错处理for (j = i; j length; j +)L - elemj - 1 = L - elemj; /第第i个位置之后的元素依次向前移个位置之后的元素依次向前移L - length -; /表长减表长减1return TRUE; 假设删除顺序表中第假设删除顺序表中第i个数据元素的概率为个数据元素的概率为qi，则在长度为，则在长度为n的线性表的线性表中删除一个数据元素时，需要移动其他元素的平均次数为中删除一个数据元素时，需要移动其他元素的平均次数为 该算法的时间复杂度也为该算法的时间复杂度也为O(n)。 在顺序表

15、中查找值为在顺序表中查找值为e的数据元素，并返回该元素在表中的位置。的数据元素，并返回该元素在表中的位置。 4查找数据元素查找数据元素 方法：方法：从第一个数据元素开始，依次将表中的元素与从第一个数据元素开始，依次将表中的元素与e进行比较，进行比较，若相等，则返回该元素在表中的位置；否则，查找失败。若相等，则返回该元素在表中的位置；否则，查找失败。 算法描述如下：算法描述如下： int Locate (SqList L, ElemType e)/在顺序表中查找值为在顺序表中查找值为e的数据元素，查找成功，返回该元素的数据元素，查找成功，返回该元素的位置；否则返回的位置；否则返回0for (i

16、= 0; i = L.elemL.length - 1) /item值大于表中最大的数据元素值大于表中最大的数据元素 L.elemL.length = item; /将将item插入到表尾插入到表尾else i = 0; while (item = L.elemi) /寻找寻找item的插入位置的插入位置i i +; ListInsert (&L, i, item); /将将item插入到位置插入到位置i L.length +; /表长增表长增1任务三任务三 线性表的链式存储结构线性表的链式存储结构 一、单链表的结构特点一、单链表的结构特点 二、单链表的基本操作二、单链表的基本操作 三、静态链

17、表及其基本操作三、静态链表及其基本操作 四、循环链表及其基本操作四、循环链表及其基本操作 五、双向链表及其基本操作五、双向链表及其基本操作 数据元素的存储结构，称为数据元素的存储结构，称为结点结点（Node） 数据域：数据域：存储数据元素本身的数据信息存储数据元素本身的数据信息指针域：指针域：存储直接后继元素地址的信息存储直接后继元素地址的信息一、单链表的结构特点一、单链表的结构特点 将将n个数据元素通过其对应结点的指针域按其逻辑关系链接成一个链表，个数据元素通过其对应结点的指针域按其逻辑关系链接成一个链表，链表中的每个结点只包含一个指针域，这样的链表称为链表中的每个结点只包含一个指针域，这样

18、的链表称为线性链表或单线性链表或单链表链表，其一般形式如图，其一般形式如图2-5所示。所示。 head称为头指针，用于指称为头指针，用于指向单链表的第一个结点。向单链表的第一个结点。由于单链表的最后一个结由于单链表的最后一个结点没有直接后继，所以其点没有直接后继，所以其指针域为指针域为“空空”（NULL），），用符号用符号“”表示。表示。 单链表的单链表的存储结构存储结构定义：定义： typedef struct Node/结点类型结点类型ElemType data;/数据域数据域struct Node *next;/指针域指针域Node, *LinkList;通常在单链表的第一个结点之前设立

19、一个结点，称之为通常在单链表的第一个结点之前设立一个结点，称之为头结点头结点。头结。头结点的数据域可以不存储任何数据信息，也可以存储一个线性表中不包点的数据域可以不存储任何数据信息，也可以存储一个线性表中不包括的元素值；头结点的指针域存储第一个结点的地址信息。括的元素值；头结点的指针域存储第一个结点的地址信息。 二、单链表的基本操作二、单链表的基本操作 1建立单链表建立单链表 2插入数据元素插入数据元素 3删除数据元素删除数据元素 4查找数据元素查找数据元素 5求单链表的长度求单链表的长度 1建立单链表建立单链表 LinkList *Create (LinkList *L)/建立一个单链表，将

20、新结点插入表尾建立一个单链表，将新结点插入表尾Node *r, *s;ElemType c;int i;*L = (LinkList) malloc (sizeof(Node);/为头结点分配存储空间为头结点分配存储空间r = *L;/r初值指向头结点初值指向头结点for (i = 1; i data = c;/将要插入数据元素的值赋给新结点的数据域将要插入数据元素的值赋给新结点的数据域s - next = NULL;/链表末尾结点指针域为空链表末尾结点指针域为空r - next = s;/将新结点插入到当前链表的表尾上将新结点插入到当前链表的表尾上r = s; /r始终指向链表的当前表尾始终

21、指向链表的当前表尾return L; 算法描述如下：算法描述如下： 该算法的时间复杂度为该算法的时间复杂度为O(n) 2插入数据元素插入数据元素 算法描述如下：算法描述如下： Status ListInsert (LinkList *L, int i, ElemType e)/在单链表在单链表L中第中第i个位置插入一个数据元素个位置插入一个数据元素eNode *p, *s;int j = 0;p = *L;while (p != NULL & j next; j +; if (j != i - 1)return FALSE;/未找到插入位置，出错处理未找到插入位置，出错处理s = (LinkL

22、ist) malloc (sizeof (Node);/生成新结点生成新结点s - data = e;/将要插入数据元素的值赋给新结点的数据域将要插入数据元素的值赋给新结点的数据域s - next = p- next;/插入新结点插入新结点p - next = s;return TRUE; 该算法的时间复杂度为该算法的时间复杂度为O(n) 3删除数据元素删除数据元素 算法描述如下：算法描述如下： Status ListDelete (LinkList *L, int i, ElemType *e)/删除单链表删除单链表L中的第中的第i个结点，并用个结点，并用e返回被删除的元素返回被删除的元素N

23、ode *p, *r;int j = 0;p = *L;while (p - next != NULL & j next;j +; if (j != i - 1) return FALSE;/未找到要删除的结点，出错处理未找到要删除的结点，出错处理r = p - next;/指针指针r指向要删除的结点指向要删除的结点p - next = p - next - next;/删除结点删除结点r*e = r - data;/将删除结点的值保存在将删除结点的值保存在e中中free (r);/释放被删除结点所占的内存空间释放被删除结点所占的内存空间return TRUE; 该算法的时间复杂度为该算法的时

24、间复杂度为O(n) 4查找数据元素查找数据元素 （1 1）按序号查找）按序号查找 查找单链表中的第查找单链表中的第i i个结点，算法描述如下：个结点，算法描述如下： LinkList GetElem (LinkList L, int i)/在单链表在单链表L中查找第中查找第i个结点，并返回该结点的指针个结点，并返回该结点的指针Node *p;int j = 0;p = L;/指针指针p初值指向头结点初值指向头结点while (p - next != NULL) & (j next;/指向下一个结点指向下一个结点 j +; /已扫描过的结点数已扫描过的结点数return p; /返回第返回第i个

25、结点个结点算法的时间复杂度为算法的时间复杂度为O(n) （2）按值查找）按值查找 查找单链表中值为查找单链表中值为e的结点，算法描述如下：的结点，算法描述如下： LinkList Locate (LinkList L, ElemType e)/在单链表中查找值为在单链表中查找值为e的结点，并返回该结点的指针的结点，并返回该结点的指针Node *p;p = L - next;/指针指针p初值指向表中第初值指向表中第1个结点个结点while (p != NULL) & (p - data != e) /从表中第从表中第1个结点开始逐个比较个结点开始逐个比较p = p - next;return p

26、; /返回值为返回值为e的结点的结点5求单链表的长度求单链表的长度 int ListLength (LinkList L)/返回单链表的长度返回单链表的长度Node *p;int j = 0;/用来保存单链表的长度用来保存单链表的长度p = L - next;/指针指针p初值指向表中第初值指向表中第1个结点个结点while (p != NULL)/用指针用指针p依次指向表中各个结点依次指向表中各个结点 p = p - next; j +; return j; /返回单链表的长度返回单链表的长度三、静态链表及其基本操作三、静态链表及其基本操作 1初始化静态链表初始化静态链表 2分配结点分配结点

27、3回收结点回收结点 1初始化静态链表初始化静态链表 开辟一块连续的存储空间，将整个数组开辟一块连续的存储空间，将整个数组空间初始化为一个空闲静态链表空间初始化为一个空闲静态链表算法描述如下：算法描述如下： SeqLinkList *InitList (SeqLinkList *S)/初始化静态链表初始化静态链表int i;for (i = 0; i nextnext)an*rear查找首尾结点的时间复杂度都为查找首尾结点的时间复杂度都为O(1) 五、双向链表及其基本操作五、双向链表及其基本操作 1插入数据元素插入数据元素 2删除数据元素删除数据元素 1插入数据元素插入数据元素 在双向链表中第在

28、双向链表中第i个个位置插入一个数据位置插入一个数据元素元素e，此时需要同，此时需要同时时修改两个方向上修改两个方向上的指针的指针，如图，如图2-17所示。所示。 Status DListInsert (DLinkList *L,int i, ElemType e)/在双向循环链表在双向循环链表L中第中第i个位置插入一个数据元素个位置插入一个数据元素eDNode *s, *pif (! (p = GetElem (L, i) return FALSE; /插入位置不合法插入位置不合法s = (DLinkList) malloc (sizeof (DNode) /生成新结点生成新结点if (! s

29、)return FALSE;s - data = e;/将将e赋给新结点的数据域赋给新结点的数据域s - prior = p - prior; /新结点的前驱指向新结点的前驱指向p结点的前驱结点的前驱p - prior - next = s;/p结点前驱的后继指向新结点结点前驱的后继指向新结点s - next = p;/新结点的后继指向新结点的后继指向p结点结点p - prior = s;/p结点的前驱指向新结点结点的前驱指向新结点return TRUE; 算法描述如下：算法描述如下： 2删除数据元素删除数据元素 删除删除双向链表中的双向链表中的第第i个结点个结点，其指针变化情，其指针变化情况

30、如图况如图2-18所示。所示。 算法描述如下：算法描述如下： Status DListDelete (DLinkList *L,int i, ElemType *e)/删除双向链表删除双向链表L中的第中的第i个结点个结点DNode *pif (! (p = GetElem (L, i) return FALSE;/i值不合法值不合法*e = p - data;/将要删除结点的值赋给将要删除结点的值赋给ep - prior - next = p - next; /要删除结点前驱的后继指向其后继要删除结点前驱的后继指向其后继p - next - prior = p - prior; /要删除结点后

31、继的前驱指向其前驱要删除结点后继的前驱指向其前驱free (p);/释放释放p结点结点return TRUE; 数据结构数据结构项目三共分为二个任务项目三共分为二个任务项目三项目三 栈和队列栈和队列任务一任务一 栈的定义、存储结构和基本操作栈的定义、存储结构和基本操作 任务二任务二 队列的定义、存储结构和基本操作队列的定义、存储结构和基本操作 任务一任务一 栈的定义、存储结构和基本操作栈的定义、存储结构和基本操作 一、栈的定义及其基本操作一、栈的定义及其基本操作 二、栈的顺序存储结构二、栈的顺序存储结构 三、栈的链式存储结构三、栈的链式存储结构 四、栈在递归中的应用四、栈在递归中的应用 一、栈

32、的定义及其基本操作一、栈的定义及其基本操作 1栈的定义栈的定义 2栈的基本操作栈的基本操作 1栈的定义栈的定义 栈是一种栈是一种只允许在表的一端进行插入和删除操作只允许在表的一端进行插入和删除操作的线性表。的线性表。 后进先出后进先出原则原则2栈的基本操作栈的基本操作 InitStack (S)：将栈将栈S初始化为一个空栈。初始化为一个空栈。 DestroyStack (S)：栈栈S已存在，将栈已存在，将栈S销毁。销毁。 ClearStack (S)：栈栈S已存在，将栈已存在，将栈S置为空栈。置为空栈。 StackEmpty (S)：栈栈S已存在，如果栈已存在，如果栈S为空栈则返回为空栈则返回

33、TRUE，否则，否则返回返回FALSE。 Push (S, e)：栈栈S已存在，在栈已存在，在栈S的栈顶位置插入一个数据元素的栈顶位置插入一个数据元素e。 Pop (S, e)：栈栈S非空，删除栈非空，删除栈S的栈顶元素，并用的栈顶元素，并用e返回其值。返回其值。 GetTop (S, e)：栈栈S非空，用非空，用e返回栈返回栈S的栈顶元素。的栈顶元素。 二、栈的顺序存储结构二、栈的顺序存储结构 1顺序栈的结构特点顺序栈的结构特点 2顺序栈的基本操作顺序栈的基本操作 3多栈共享空间多栈共享空间 1顺序栈的结构特点顺序栈的结构特点 顺序栈是指采用顺序存储结构的栈顺序栈是指采用顺序存储结构的栈，即

34、在内存中用一组地址连续的存，即在内存中用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设置一个指针储单元依次存放自栈底到栈顶的数据元素，同时设置一个指针top指示指示栈顶元素的当前位置。栈顶元素的当前位置。 类型定义如下：类型定义如下：# define MAXSIZE 100/定义栈的最大容量定义栈的最大容量typedef structElemType elemMAXSIZE; /存放栈中元素的一维数组空间存放栈中元素的一维数组空间int top;/栈顶指针变量栈顶指针变量SeqStack;top用于指示某一时刻栈顶元素的位置用于指示某一时刻栈顶元素的位置elem0用于存放栈中第一

35、个元素用于存放栈中第一个元素 2顺序栈的基本操作顺序栈的基本操作 （1）初始化）初始化 （2）判断栈是否为空）判断栈是否为空 （3）进栈）进栈 （4）出栈）出栈 （5）取栈顶元素）取栈顶元素 （1）初始化）初始化 void InitStack (SeqStack *S)/构造一个空栈构造一个空栈SS - top = 0;int StackEmpty (SeqStack S)/判断判断S是否为空栈，为空时返回是否为空栈，为空时返回TRUE，否则返回，否则返回FALSEreturn (S.top = 0 ? TRUE : FALSE);（2）判断栈是否为空）判断栈是否为空 int Push (Se

36、qStack *S, ElemType e)/将数据元素将数据元素e压入栈顶压入栈顶if (S - top = MAXSIZE) return FALSE;/栈已满，进栈失败栈已满，进栈失败S - elemS - top = e;/将将e插入栈插入栈顶顶S - top +;/修改栈顶指针修改栈顶指针return TRUE;（3）进栈）进栈 （4）出栈）出栈 int Pop (SeqStack *S, ElemType *e)/若栈不空，将栈顶元素弹出，并用若栈不空，将栈顶元素弹出，并用e返回其值返回其值if (S - top = 0) return FALSE;elseS - top -;/修

37、改栈顶指针修改栈顶指针*e = S - elemS - top;/保存栈顶元素保存栈顶元素return TRUE; （5）取栈顶元素）取栈顶元素 int GetTop (SeqStack S, ElemType *e)/若栈不空，则用若栈不空，则用e返回栈顶元素返回栈顶元素if (S.top = 0) return FALSE;*e = S.elemS.top - 1;/保存栈顶元素保存栈顶元素return TRUE;3多栈共享空间多栈共享空间 当元素进栈时，两个栈都是从两端向中间伸展。通过两个栈顶指当元素进栈时，两个栈都是从两端向中间伸展。通过两个栈顶指针（针（top1和和top2）的动态变

38、化，使其存储空间相互补充。）的动态变化，使其存储空间相互补充。 栈满栈满的条件是：的条件是：top1top21栈空栈空的条件是：的条件是：top10或或top2M1两栈共享空间的两栈共享空间的数据结构定义数据结构定义： # define M 100/两栈共享的存储空间大小两栈共享的存储空间大小typedef structElemType StackM;/两栈共享的一维数组空间两栈共享的一维数组空间int top2;/两栈的栈顶指针两栈的栈顶指针DSeqStack;两栈共享空间的一些基本操作：两栈共享空间的一些基本操作：（1）初始化）初始化 （2）进栈）进栈 （3）出栈）出栈 （1）初始化）初始

39、化 void InitStack (DSeqStack *S)/初始化两个空栈初始化两个空栈S - top0 = 0;S - top1 = M-1;int Push (DSeqStack *S, ElemType e, int i)/将数据元素将数据元素e压入第压入第i个栈的栈顶个栈的栈顶if (S - top0 = S - top1 + 1) return FALSE;/栈已满，进栈失栈已满，进栈失败败switch (i)case 0 :/将将e压入第压入第1个栈个栈S - StackS - top0 = e;S - top0 +;break;case 1 :/将将e压入第压入第2个栈个栈S

40、 - StackS - top1 = e;S - top1 -;break;default :/参数错误参数错误return FALSE; return TRUE; （2）进栈）进栈 （3）出栈）出栈 int Pop (DSeqStack *S, ElemType *e, int i)/从第从第i个栈中弹出栈顶元素，并用个栈中弹出栈顶元素，并用e返回其值返回其值switch (i)case 0 :/从第从第1个栈弹出个栈弹出if (S - top0 = 0)return FALSE;*e = S - StackS - top0 - 1;S - top0 -;break;case 1 :/从第从

41、第2个栈弹出个栈弹出if (S - top1 = M - 1)return FALSE;*e = S - StackS - top1 + 1;S - top1 +;break;default :/参数错误参数错误return FALSE; return TRUE; 三、栈的链式存储结构三、栈的链式存储结构 1链栈的结构特点链栈的结构特点 2链栈的基本操作链栈的基本操作 1链栈的结构特点链栈的结构特点 链栈是指利用一个单链表结构来实现的栈，即栈中的每一个数据元素链栈是指利用一个单链表结构来实现的栈，即栈中的每一个数据元素用一个结点来表示，同时设置一个指针用一个结点来表示，同时设置一个指针top指

42、示栈顶元素的当前位置。指示栈顶元素的当前位置。 链栈的链栈的类型定义类型定义如下：如下： typedef struct SNodeElemType data;/数据域数据域struct SNode *next;/指针域指针域SNode;typedef structstruct SNode *top;/栈顶指针栈顶指针LinkStack;2链栈的基本操作链栈的基本操作 （1）初始化）初始化 （2）进栈）进栈 （3）出栈）出栈 （1）初始化）初始化 void InitStack (LinkStack *S)/将栈将栈S初始化为空栈初始化为空栈S - top = NULL;/栈顶指针为空栈顶指针为空

43、（2）进栈）进栈 int Push (LinkStack *S, ElemType e)/将数据元素将数据元素e压入链栈压入链栈LinkStack *temp;temp = (LinkStack) malloc (sizeof (struct Node);/生成新结点生成新结点if (temp = NULL) return FALSE;/分配空间失败分配空间失败temp - data = e;/为新结点数据域赋值为新结点数据域赋值temp - next = S - top;/将新结点插入栈顶将新结点插入栈顶S - top = temp;/修改栈顶指针修改栈顶指针return TRUE;（3）出

44、栈）出栈 int Pop (LinkStack *S, ElemType *e)/将栈顶元素弹出，并用将栈顶元素弹出，并用e返回其值返回其值LinkStack *temp;if (S - top = NULL) return FALSE; /栈为空，出栈失败栈为空，出栈失败temp = S - top;S - top = S - top- next;/修改栈顶指针修改栈顶指针*e = temp - data;/保存栈顶元素的值保存栈顶元素的值free (temp);/释放出栈结点释放出栈结点return TRUE;四、栈在四、栈在递归递归中的应用中的应用 指一个函数在定义自身的同指一个函数在定

45、义自身的同时又直接或间接地调用自身时又直接或间接地调用自身 二阶二阶FibonacciFibonacci数列数列 C语言函数描述如下：语言函数描述如下： int fib (int n)A1:if (n = 0) return 0;A2:else if (n = 1) return 1;A3:else return fib (n - 1) + fib (n - 2);A4: Fib (3)递归栈的存储空间变化情况：递归栈的存储空间变化情况： 任务二任务二 队列的定义、存储结构和基本操作队列的定义、存储结构和基本操作 一、队列的定义及其基本操作一、队列的定义及其基本操作 二、队列的顺序存储结构二、

46、队列的顺序存储结构 三、队列的链式存储结构三、队列的链式存储结构 一、队列的定义及其基本操作一、队列的定义及其基本操作 1队列的定义队列的定义 2队列的基本操作队列的基本操作 队列队列是另一种操作受限的线性表，它只允许在表的一端进行插入操作，是另一种操作受限的线性表，它只允许在表的一端进行插入操作，而在另一端进行删除操作。而在另一端进行删除操作。 1队列的定义队列的定义 2队列的基本操作队列的基本操作 InitQueue (Q)：将队列将队列Q初始化为一个空队列。初始化为一个空队列。 DestroyQueue (Q)：队列队列Q已存在，将队列已存在，将队列Q销毁。销毁。 ClearQueue

47、(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顺序队列

48、顺序队列 2循环队列的结构特点循环队列的结构特点 3循环队列的基本操作循环队列的基本操作 1顺序队列顺序队列 在内存中用一组地址连续的存储单元依次存放从队头到队尾的数据元素，在内存中用一组地址连续的存储单元依次存放从队头到队尾的数据元素，同时设置两个指针同时设置两个指针front和和rear分别指示队头元素和队尾元素的位置。分别指示队头元素和队尾元素的位置。 # define MAXSIZE 100/队列的最大长度队列的最大长度typedef structElemType elemMAXSIZE;/存放队列中元素的一维数组空间存放队列中元素的一维数组空间int front;/头指针头指针int

49、 rear;/尾指针尾指针SeqQueue;顺序队列的类型定义如下：顺序队列的类型定义如下： 2循环队列的结构特点循环队列的结构特点 将队列的存储空间看成一个环状的空间，即将队列的首、尾的位置连接将队列的存储空间看成一个环状的空间，即将队列的首、尾的位置连接起来形成的结构称为起来形成的结构称为循环队列循环队列。 一般规定：少用一个元素的存储空间，当队列尾指针的下一个位置是一般规定：少用一个元素的存储空间，当队列尾指针的下一个位置是队列头指针时，则停止进队操作，此时队列已满。队列头指针时，则停止进队操作，此时队列已满。 循环队列满的条件是：循环队列满的条件是：（rear1）mod MAXSIZE

50、front 循环队列空的条件是：循环队列空的条件是：frontrear 3循环队列的基本操作循环队列的基本操作 （1）初始化）初始化 （2）判断队列是否为空）判断队列是否为空 （3）进队）进队 （4）出队）出队 （5）取队头元素）取队头元素 （1）初始化）初始化 void InitQueue (SeqQueue *Q)/将将 Q初始化为一个空的循环队列初始化为一个空的循环队列Q - front = Q - rear = 0;（2）判断队列是否为空）判断队列是否为空 int QueueEmpty (SeqQueue Q)/判断判断Q是否为空队列，为空时返回是否为空队列，为空时返回TRUE，否则返