“计算机软件技术”课群

1、“计算机软件技术”课群 “计算机软件技术计算机软件技术”课群课群 基础篇之基础篇之 数据结构数据结构 第第2章章 数据的线性结构数据的线性结构 (3学时学时) 第第3章章 查找与排序查找与排序 (2学时学时) “计算机软件技术”课群 第第2章章 数据的线性结构数据的线性结构 2.1.1数据的逻辑结构和存储表示数据的逻辑结构和存储表示 1.基本的概念和术语基本的概念和术语 计算机的应用计算机的应用: 科学计算科学计算=非数值计算非数值计算 一、两个例子一、两个例子 例例1、学生档案管理、学生档案管理 组织成一个二维表组织成一个二维表 学号学号姓名姓名性别性别出生年月出生年月专业专业 . 张明男1

2、985.01.01计算机 李丽女1985.05.30物理 “计算机软件技术”课群 组织成一棵树组织成一棵树 化 工 学 院 0 3 级 学 生 1 学 生 n 0 4 级 0 5 级 计 算 机 系 自 动 化 系 电 子 与 通 信 工 程 系 信 息 科 学 与 工 程 学 院 物 理 系 化 学 系 理 学 院 学 校 “计算机软件技术”课群 例例2、在、在n个城市间建立通信网络个城市间建立通信网络 C1C1 C4C4 C2C2C3C3 C5C5 1 1 3 3 6 66 6 7 7 5 5 9 9 7 7 8 8 4 4 C1 C4 C2C3 C5 1 3 6 4 代价最小代价最小 “

3、计算机软件技术”课群 从上面两个例子中可以看出：从上面两个例子中可以看出： 数据结构中元素之间存在着逻辑关系，数据结构中元素之间存在着逻辑关系， 上述例子中给出了三种逻辑结构线性表、上述例子中给出了三种逻辑结构线性表、 树、图。树、图。 数据结构主要解决：数据结构主要解决： 如何分析数据元素之间的关系，并确定合适如何分析数据元素之间的关系，并确定合适 的逻辑结构；的逻辑结构； 如何在计算机中存储这些数据；如何在计算机中存储这些数据； 为完成对数据的操作设计算法，并作出分析。为完成对数据的操作设计算法，并作出分析。 “计算机软件技术”课群 二、概念和术语二、概念和术语 数据数据(data)：表示

4、现实世界中的客观事物、能表示现实世界中的客观事物、能 输入计算机并能被计算机程序处理的符号的输入计算机并能被计算机程序处理的符号的 总称。总称。 数据元素数据元素(data element)：数据集合中的一个数据集合中的一个 个体，是数据的基本单位。个体，是数据的基本单位。(亦称为结点、记亦称为结点、记 录等录等) 数据项数据项(data item)：数据的不可分割的、含有数据的不可分割的、含有 独立意义的最小单位。独立意义的最小单位。 数据对象数据对象(data object)：性质相同的数据元素性质相同的数据元素 的集合。的集合。 1. 数据结构数据结构(data structure)：相

5、互之间存在着一相互之间存在着一 种或多种关系的数据元素的集合。种或多种关系的数据元素的集合。 “计算机软件技术”课群 数据结构无公认定义，都认为其研究涉数据结构无公认定义，都认为其研究涉 及三个方面：及三个方面： 数据元素间的逻辑关系数据元素间的逻辑关系(逻辑结构逻辑结构) 数据元素的存储方式数据元素的存储方式(物理结构物理结构) 数据元素间的运算数据元素间的运算(操作操作) 一般地，一个数据结构中的数据元素一般地，一个数据结构中的数据元素 属于同一个数据对象。属于同一个数据对象。 “计算机软件技术”课群 2.1.2 2.1.2 数据的逻辑结构和存储方法数据的逻辑结构和存储方法 一、数据的逻辑

6、结构一、数据的逻辑结构 逻辑结构是指数据元素之间的特定关系，逻辑结构是指数据元素之间的特定关系， 它独立于计算机，是元素之间关系的抽象。它独立于计算机，是元素之间关系的抽象。 1 1、定义、定义 数据结构是一个二元组数据结构是一个二元组B=(DB=(D，R)R)。其其 中中D D是数据元素是数据元素( (即结点即结点) )的有限集合；的有限集合；R R是是D D 上的关系的有限集合。一般上的关系的有限集合。一般R R中只涉及一种中只涉及一种 关系。关系。 “计算机软件技术”课群 例如：例如： 有有4个人，为别为个人，为别为a、b、c、d，其中其中a是是b 的父亲，的父亲，b是是c的父亲，的父亲

7、，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 = ， “计算机软件技术”课群 可以用图形方式分别表示为：可以用图形方式分别表示为： ab

8、cd f e g h “计算机软件技术”课群 2、几个概念、几个概念 设设B=(D，R)是一个逻辑结构，是一个逻辑结构，rR， di、dj D。如果如果 r，则称则称di是是 dj的前驱，的前驱， dj是是di的后继。的后继。 如果某个结点没有前驱，则称之为开始结点；如果某个结点没有前驱，则称之为开始结点； 如果某个结点没有后继，则称之为终端结点；如果某个结点没有后继，则称之为终端结点； 既非开始结点，也非终端结点的结点称之为既非开始结点，也非终端结点的结点称之为 内部结点。内部结点。 “计算机软件技术”课群 3、结构分类、结构分类 线性结构线性结构 只有一个开始结点和一个终端结点，其它结点只

9、有一只有一个开始结点和一个终端结点，其它结点只有一 个前驱结点和一个后继结点，称之为线性结构。即元个前驱结点和一个后继结点，称之为线性结构。即元 素之间存在着一对一的关系。素之间存在着一对一的关系。 非线性结构非线性结构 如果一个结构不是线性结构，则称之为非线性结构。如果一个结构不是线性结构，则称之为非线性结构。 一般地，结构中至少有一个结点存在不止一个前驱结一般地，结构中至少有一个结点存在不止一个前驱结 点或后继结点。非线性结构有两类：点或后继结点。非线性结构有两类： a、树形结构：元素之间存在着一对多的关系。树形结构：元素之间存在着一对多的关系。 b、图形结构：元素之间存在着多对多的关系。

10、图形结构：元素之间存在着多对多的关系。 “计算机软件技术”课群 14131211 23 4 5 6789 104 5 6 23 1 1 2 3 4 5 1 “计算机软件技术”课群 二、数据的存储方法二、数据的存储方法 一般地，数据的存储方法有四种：一般地，数据的存储方法有四种： 顺序存储顺序存储 链式存储链式存储 索引存储索引存储 散列存储散列存储 （后两种方法主要用于查找，本课程不作详述）（后两种方法主要用于查找，本课程不作详述） “计算机软件技术”课群 1、顺序存储顺序存储 把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物 理位置相邻的存储单元之中。通常借助理位置相邻的存储单元

11、之中。通常借助 于程序设计语言中的数组来实现。于程序设计语言中的数组来实现。 2、链式存储、链式存储 逻辑上相邻的数据元素不要求其物逻辑上相邻的数据元素不要求其物 理存储位置相邻，元素间的逻辑关系用理存储位置相邻，元素间的逻辑关系用 附设的指针域来表示。通常借助于程序附设的指针域来表示。通常借助于程序 设计语言中的指针来实现。设计语言中的指针来实现。 “计算机软件技术”课群 例如：例如： 有数据结构有数据结构B=(D，R)， 其中其中 D=d1,d2,d3,d4,d5 R=r r=, 则用上述两种存储结构表示为：则用上述两种存储结构表示为： “计算机软件技术”课群 d1 d2 d3 d4 d5

12、 1000 1005 1010 1015 1020 d5 d35000 d14000 d22000 d41000 顺序存储顺序存储 （假设每个元素占（假设每个元素占5个存储单元）个存储单元） 链式存储链式存储 1000 2000 3000 4000 5000 头指针变量头指针变量 存储地址存储地址 存储地址存储地址数据域数据域指针域指针域3000 数据域数据域 “计算机软件技术”课群 链式存储图示为：链式存储图示为： d1d5 head d2d3d4 线性结构和非线性结构均可采用这两种存储方法。线性结构和非线性结构均可采用这两种存储方法。 “计算机软件技术”课群 数据的逻辑结构数据的逻辑结构

13、数据的存储结构数据的存储结构 数据的运算：插入、删除、查找数据的运算：插入、删除、查找、排序、修改等排序、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表 栈栈 队队 树形结构树形结构 图形结构图形结构 数据结构的三个方面：数据结构的三个方面： “计算机软件技术”课群 2.2 线性表的基本概念线性表的基本概念 一、线性表的定义一、线性表的定义 它是最常用且又最简单的线性结构。它是最常用且又最简单的线性结构。 定义：定义： 线性表是线性表是n(n0)个性质相同的数据元个性质相同的数据元 素所构成的有限序列素所构成的有限序列(a1,a2,a3,.,a

14、n)。 n称为线性表的长度。称为线性表的长度。 当当n=0时，称为空表。时，称为空表。 “计算机软件技术”课群 数据元素可以是很简单的整数、英文字母等，数据元素可以是很简单的整数、英文字母等， 也可以是较复杂的元素。由复杂元素构成的线也可以是较复杂的元素。由复杂元素构成的线 性表又称为文件，复杂数据元素称为记录。性表又称为文件，复杂数据元素称为记录。 例如：例如： （1，2，7，5，3，9） ( A，D，C，B，E ) 19851985年年4 4月月 19861986年年1 1月月 男男 女女 王东林王东林 吴红吴红 出生年月出生年月性别性别姓名姓名学号学号 上面这些都是线性表。上面这些都是线

15、性表。 “计算机软件技术”课群 二、线性表的基本运算二、线性表的基本运算 线性表的初始化（构造一个空的线性表）线性表的初始化（构造一个空的线性表） 求表长求表长 取第取第i个数据元素个数据元素 查找具有特定值的结点，确定其序号查找具有特定值的结点，确定其序号 插入操作（在原表的第插入操作（在原表的第i个位置上插入新元素个位置上插入新元素） 删除操作（删除原表中第删除操作（删除原表中第i个元素个元素） 随着线性表的存储方法不同，各种运算的实现随着线性表的存储方法不同，各种运算的实现 方法也不一样。下面结合线性表的不同存储结方法也不一样。下面结合线性表的不同存储结 构，讨论实现上述一些运算的算法。

16、构，讨论实现上述一些运算的算法。 “计算机软件技术”课群 2.3 线性表的顺序存储（顺序表）线性表的顺序存储（顺序表） 一、顺序表的表示方法一、顺序表的表示方法 用一组地址连续的存储单元依次存放用一组地址连续的存储单元依次存放 线性表的元素。线性表的元素。 假设每个元素占用假设每个元素占用b个存储单元，并以个存储单元，并以 元素的第一个存储单元地址作为元素的元素的第一个存储单元地址作为元素的 存储地址（结点始址），则存储地址（结点始址），则 loc(ai+1) = loc(ai)+b “计算机软件技术”课群 一般地，第一般地，第i个元素的存个元素的存 储地址为储地址为 loc(ai)=loc(

17、a1)+(i-1)*b 通常称线性表的第一个元通常称线性表的第一个元 素素a1的存储地址为线性表的的存储地址为线性表的 基地址，设为基地址，设为h，则有则有 loc(ai)=h+(i-1)*b an ai a2 a1 h h+b h+(i-1)b h+(n-1)b “计算机软件技术”课群 顺序表特点：顺序表特点： 逻辑上相邻的元素在物理存储上亦相邻；逻辑上相邻的元素在物理存储上亦相邻； 任一元素的存取时间相同，是一种随机任一元素的存取时间相同，是一种随机 存取结构。存取结构。 1. （用类（用类C语言描述顺序表）语言描述顺序表） “计算机软件技术”课群 define maxnum 100 /*

18、最大元素个数最大元素个数*/ typedef struct datamaxnum; int length; /*当前长度当前长度*/ sqlist; 返回返回 “计算机软件技术”课群 二、顺序表上基本运算的实现二、顺序表上基本运算的实现 1、顺序表的初始化、顺序表的初始化 把当前表长置把当前表长置0。 即：即： void initlist_sq( sqlist *L ) *L.length = 0; /*或或L-length = 0*/ “计算机软件技术”课群 2、顺序表的插入操作、顺序表的插入操作 要求在顺序表的第要求在顺序表的第i个位置上插入一个值为个位置上插入一个值为x 的新元素。的新元

19、素。 原线性表原线性表: (a1, a2, , ai-1, ai, ai+1, , an ) 长度为长度为n 插入后的线性表插入后的线性表: (a1, a2, , ai-1, x , ai, ai+1, , an ) 长度为长度为n+1 “计算机软件技术”课群 设设i的取值范围为的取值范围为1in+1，插入操作的步插入操作的步 骤如下：骤如下： （算法描述）（算法描述） 将将anai依次向后移动，为新元素让出位依次向后移动，为新元素让出位 置；置； 将将x置入空出的第置入空出的第i个位置；个位置； 1. 修改表长。修改表长。 “计算机软件技术”课群 #define ERROR 0 #defin

20、e OK 1 int listinsert_sq ( sqlist *L, int i, x ) int j; if ( L-length = maxnum ) printf( “list is full” ); return (ERROR); if ( iL-length+1 ) printf( “ i is invalid value” ); return (ERROR); for ( j=L-length-1; j=i-1; j- ) L-dataj+1 = L-dataj; /*元素后移元素后移*/ L-datai-1 = x; /*新元素插入新元素插入*/ L-length+; /*

21、表长加表长加1*/ return ( OK ); 返回返回 “计算机软件技术”课群 3、顺序表的删除操作、顺序表的删除操作 要求删除顺序表的第要求删除顺序表的第i个位置上的元素。个位置上的元素。 原线性表原线性表 (a1, a2, , ai-1, ai, ai+1, , an ) 长度为长度为n 删除后的线性表删除后的线性表 (a1, a2, , ai-1, ai+1, , an ) 长度为长度为n-1 设设i的取值范围为的取值范围为1in，删除操作的步骤如下：删除操作的步骤如下： 将将ai+1an依次向前移动；依次向前移动； （算法描述（算法描述） 修改表长修改表长 “计算机软件技术”课群

22、int listdelete_sq ( sqlist *L, int i ) int j; if ( iL-length-1 ) printf( “i is invalid value” ); return( ERROR ); for ( j=i; jlength; j+ ) L-dataj-1 = L-dataj; /*元素前移元素前移*/ L-length-; /*长度减长度减1*/ return ( OK ); 顺序表插入和删除操作的时间复杂度均为顺序表插入和删除操作的时间复杂度均为O(n)。 返回返回 “计算机软件技术”课群 2.4 线性表的链式存储（链表）线性表的链式存储（链表） 2

23、.4.1单链表单链表 1、单链表、单链表 结点结构：结点结构： 链表中每个结点有一个存放数据元素链表中每个结点有一个存放数据元素 的域，另有一个域存放指向后继结点的的域，另有一个域存放指向后继结点的 指针（表示逻辑关系），故称为单链表。指针（表示逻辑关系），故称为单链表。 （用类用类C语言描述为一个结构）语言描述为一个结构） 数据域 指针域 “计算机软件技术”课群 typedef struct node data; /*数据域数据域*/ struct node * next; /*指针域指针域*/ NODE; 返回返回 “计算机软件技术”课群 单链表的两种形式单链表的两种形式 head a1a

24、na2 head a1a2an 带头结点的单链表带头结点的单链表 不带头结点的单链表不带头结点的单链表 “计算机软件技术”课群 指针变量指针变量head中存放了链表中第一个结点的起始地中存放了链表中第一个结点的起始地 址，称之为头指针。该指针变量是址，称之为头指针。该指针变量是“静态静态”定义定义 的，即用的，即用NODE * head;定义了指针变量定义了指针变量head。 链表中的结点是链表中的结点是“动态动态”生成的生成的(称之为结点变量称之为结点变量)， 每个结点可以存放一个数据元素和后继结点的起每个结点可以存放一个数据元素和后继结点的起 始地址。最后一个结点因为没有后继结点，故其始地

25、址。最后一个结点因为没有后继结点，故其 指针域中存放指针域中存放NULL(空地址空地址)。 当链表中没有数据元素当链表中没有数据元素(即空表即空表)时，第一种单链表时，第一种单链表 保留头结点。即保留头结点。即 ，后一种，后一种head中为中为NULL。 head “计算机软件技术”课群 建立一个空表的算法为建立一个空表的算法为(带头结点带头结点)： NODE *initlist_link （ ） NODE *p; p = (NODE *) malloc ( sizeof(NODE) ); p-next = NULL; return ( p ); “计算机软件技术”课群 2、两个标准函数、两个

26、标准函数 malloc 和和 free 设有变量定义：设有变量定义： NODE *p; 则则p=(NODE *) malloc (sizeof(NODE)的作用是由系的作用是由系 统生成（得到）一个统生成（得到）一个NODE类型的结点，同时将类型的结点，同时将 该结点的起始地址赋给指针变量该结点的起始地址赋给指针变量p。 free(p)的作用是由于系统回收（释放）一个由的作用是由于系统回收（释放）一个由p 所指向的所指向的NODE类型的结点。类型的结点。 注意点：注意点： 每次调用每次调用malloc或或free函数只能得到或释放一个结点空间；函数只能得到或释放一个结点空间； 用用malloc

27、函数得到的结点中无确定的内容，必须由程序函数得到的结点中无确定的内容，必须由程序 员给予；员给予； 用用free函数释放一个结点空间，指针变量本身并未释放。函数释放一个结点空间，指针变量本身并未释放。 “计算机软件技术”课群 2.4.2单链表上基本运算的实现单链表上基本运算的实现 建立单链表建立单链表 a. 正向建：正向建： b. 逆向建：逆向建： head a1ana2 a1 head p2 p1 p2 p1 anan-1a1 head an-2 a1 head p p 算法的详细描述读者可参见本教材实践篇的实验算法的详细描述读者可参见本教材实践篇的实验2 “计算机软件技术”课群 单链表的插

28、入操作单链表的插入操作 要求在带头结点的单链表中第要求在带头结点的单链表中第i个位置上插入一个值为个位置上插入一个值为x 的新元素。的新元素。 算法思想：算法思想： 定义三个指针变量定义三个指针变量p、q和和s； (算法描述算法描述) 在单链表中寻找第在单链表中寻找第i个元素位置，若找到，则由个元素位置，若找到，则由q指指 向第向第i个位置，个位置，p指向第指向第i-1个位置，继续个位置，继续b)；否则结否则结 束。束。 向系统申请一个由向系统申请一个由s指向的新结点，并在数据域置入指向的新结点，并在数据域置入 新元素新元素x。 a)将将s指向的新结点插入指向的新结点插入q之前，结束。之前，结

29、束。 x p 第第i-1个位置个位置 q 第第i个位置个位置 s “计算机软件技术”课群 int ListInsert( NODE *L, int i, x ) int j; NODE *p, *q, *s; p = L; q = L-next; j = 1; while( q!=NULL +j; if ( q=NULL | ji ) /*找不到插入点找不到插入点*/ return (ERROR); s = (NODE*) malloc ( sizeof(NODE) ); /*建立新结点建立新结点*/ s-data = x; s-next = q; /* 插入新结点插入新结点*/ p-next

30、 = s; return ( OK ); 该算法的时间复杂度为该算法的时间复杂度为O(n)。 返回返回 “计算机软件技术”课群 单链表的删除操作单链表的删除操作 要求在带头结点的单链表中删除第要求在带头结点的单链表中删除第i个位置的个位置的 元素。元素。 p q 第第i个位置个位置 算法思想：算法思想： （算法描述）（算法描述） 定义两个指针变量定义两个指针变量p和和q。 在单链表中寻找第在单链表中寻找第i个元素位置，若找到则由个元素位置，若找到则由q指向第指向第i个位置，个位置，p 指向第指向第i-1个位置，继续个位置，继续b)，否则结束。否则结束。 从链表中删除从链表中删除q所指向的结点。

31、所指向的结点。 a)释放释放q所指向的结点空间，结束。所指向的结点空间，结束。 “计算机软件技术”课群 int ListDelete ( NODE *L, int i ) int j; NODE *p, *q; p = L; q = L-next; j = 1; while ( q != NULL +j; if ( q=NULL | ji ) /*删除位置不合理删除位置不合理*/ return ( ERROR ); p-next = q-next; /*删除删除q所指向结点所指向结点*/ free ( q ); return ( OK ); 该算法的时间复杂度为该算法的时间复杂度为O(n)。

32、返回返回 “计算机软件技术”课群 2.4.3线性表的其它链式存储线性表的其它链式存储 1、单循环链表、单循环链表 单循环链表是一种特殊的单链表，其最单循环链表是一种特殊的单链表，其最 后一个结点的指针域中不存放后一个结点的指针域中不存放NULL(空空 地址地址)，而是放入了链表的头指针。，而是放入了链表的头指针。 “计算机软件技术”课群 带头结点的单循环链表带头结点的单循环链表 不带头结点的单循环链表不带头结点的单循环链表 head a1ana2 a1a2an head 空表时空表时 head “计算机软件技术”课群 2、双向链表、双向链表 结点结构：结点结构： 链表中每一个结点除数据域和指向

33、后继结点的指针链表中每一个结点除数据域和指向后继结点的指针 域外，增加了一个指向前驱结点的指针域。域外，增加了一个指向前驱结点的指针域。 用类用类C语言描述为：语言描述为： typedef struct dlnode data; struct dlnode *prior, *next; DLNODE; 双向链表在做插入和删除操作时，不需要再用双向链表在做插入和删除操作时，不需要再用 两个指针在链表上移动。两个指针在链表上移动。 后继指针域后继指针域数据域数据域前驱指针域前驱指针域 “计算机软件技术”课群 双向链表的形式双向链表的形式 带头结点的双向链表带头结点的双向链表 不带头结点的双向链表不

34、带头结点的双向链表 a1an 非循环非循环 循环循环 head a1an head 非循环非循环 循环循环 head head a1an a1an “计算机软件技术”课群 3、静态链表、静态链表 用结构数组来描述静态链表。用结构数组来描述静态链表。 描述方法：描述方法： #define maxsize 1000 /*定义链表的最大长度定义链表的最大长度*/ typedef struct data; int next; SNODE; SNODE sdmaxsize; int sl; “计算机软件技术”课群 上图是一个带头结点的单链表，表示了线性表上图是一个带头结点的单链表，表示了线性表 (a1,

35、a2,a3,a4,a5,a6)的链式存储，的链式存储，sl为头指针变量。为头指针变量。 1a2 4a5 -1a6 6a1 5a4 2a3 3 datanext 0 1 2 3 4 5 6 maxsize -1 sl = 0 “计算机软件技术”课群 2.5 栈栈 2.5.1 栈的定义和基本运算栈的定义和基本运算 1、栈的定义、栈的定义 实例：装网球的纸筒、子弹夹实例：装网球的纸筒、子弹夹 a1 an 定义：栈是限定在表的一端（表尾）进行定义：栈是限定在表的一端（表尾）进行 插入和删除操作的线性表。插入和删除操作的线性表。 表尾表尾 表头表头 “计算机软件技术”课群 允许插入和删除的表尾端称为栈顶

36、。允许插入和删除的表尾端称为栈顶。 相应的表头端称为栈底。相应的表头端称为栈底。 a1 an 栈顶栈顶 栈底栈底 栈的两个要素：存放栈元素的栈的两个要素：存放栈元素的 存储空间和栈顶指针。存储空间和栈顶指针。 栈的特点：数据元素后进先出栈的特点：数据元素后进先出 ( LI FOLast In First Out) “计算机软件技术”课群 2、 栈的基本运算栈的基本运算 栈初始化栈初始化 initstack( s )建立一个空栈建立一个空栈s 入栈入栈 push( s, x) 把元素把元素x推入栈推入栈s的栈顶的栈顶 出栈出栈 pop( s ) 删除栈删除栈s的栈顶元素的栈顶元素 取栈顶元素取栈

37、顶元素 gettop( s, x ) 取出栈取出栈s的栈顶元素送入的栈顶元素送入x， 由由x返回返回 a1 an 出栈出栈入栈入栈 “计算机软件技术”课群 2.5.2栈的存储结构和运算的实现栈的存储结构和运算的实现 1、 顺序存储的栈顺序存储的栈(顺序栈顺序栈) 用一组地址连续的存储单元依次存放自栈底到用一组地址连续的存储单元依次存放自栈底到 栈顶的数据元素，同时附设栈顶指针栈顶的数据元素，同时附设栈顶指针top指示栈顶元指示栈顶元 素在顺序栈中的位置。（素在顺序栈中的位置。（类类C语言描述为一个结构）语言描述为一个结构） 例如：例如： 4 3 2 1 0 4 3 2 1 0 4 3 2 1

38、0 4 3 2 1 0 top=-1 top = 0 10 top = 4 10 15 7 16 8 top = 2 10 15 7 “计算机软件技术”课群 #define maxsize 5 typedef struct stack int elemmaxsize; int top; Stack; 返回返回 “计算机软件技术”课群 在顺序栈上基本运算的实现：在顺序栈上基本运算的实现： 栈初始化栈初始化 算法描述算法描述 4 3 2 1 0 top = -1 栈顶指针赋初值栈顶指针赋初值 -1 “计算机软件技术”课群 void initstack ( Stack *s ) (*s).top = -1; 返回 “计算机软件技术”课群 入栈入栈 算法描述算法描述 4 3 2 1 0 4 3 2 1 0 top = 1 10 15 top = 2 if ( 栈不满栈不满 ) 栈顶指针加栈顶指针加1； 将将x的值推入栈顶；的值推入栈顶； else 出错；出错； 10 15 7 x = 7 “计算机软件技术”课群 #define ERROR 0 #define OK 1 int push( Stack *s, int x ) if( (*s).top rear q- front 队头指针和队尾指针均赋初值队头指针和