计算机软件基础 第2章 数据结构-2.1~2.4.ppt

* * 例如：某个班学生成绩表，包括：学号、姓名和各科成绩，每一个学生的信息都是一个数据元素。数据元素之间有这样的逻辑关系：在一个数据元素的前面最多有一个与其相邻的数据元素（称为直接前驱），在一个数据元素的后面也最多有一个与其相邻的数据元素（称为直接后继） 。数据元素之间的这种关系构成了学生成绩表的逻辑结构。 * 例如：某个班学生成绩表，包括：学号、姓名和各科成绩，每一个学生的信息都是一个数据元素。数据元素之间有这样的逻辑关系：在一个数据元素的前面最多有一个与其相邻的数据元素（称为直接前驱），在一个数据元素的后面也最多有一个与其相邻的数据元素（称为直接后继） 。数据元素之间的这种关系构成了学生成绩表的逻辑结构。 * 例如：学生的信息，包括：学号、姓名、成绩。一个学生的信息就是一个数据元素。 * * 顺序存储的线性表的特点: 优点：表中任一结点的存取很方便，也能进行插入和删除操作。 缺点： (1) 插入和删除不方便。为保持连续存放，操作中需要移动大量元素。 (2) 会造成空间的浪费以及不易扩充。数组大小固定，对于处理长度变化较大的线性表时，分配数组大小不够，会造成溢出;分配大小太大，会造成空间浪费。 2.4 栈、队列和数组 三、链栈 * 在链式存储结构上实现的栈称为链栈，其结构形式与单链表类似，见图2-17。其中单链表的第一个结点就是链栈的栈顶结点，指向栈顶结点的指针st称为栈顶指针，它相当于单链表的头指针。栈中的其他结点通过它们的link域链接起来。栈底结点的link域为NULL。链栈的优点不会出现因栈满而发生的上溢，只有当整个可利用空间都被占满，malloc函数执行不成功时才会出错。其存储区可以由不连续的存储空间组成。 下面给出栈的基本运算在链栈上的实现，假设数据元素是整数型的，且假设链表是不带头结点的。 2.4 栈、队列和数组 * typedef struct snode{int data；struct snode*link；}NODE； NODE *st； ／*定义了结点的类型和头指针*／ push(int x) ／*在链栈中进栈数据元素x*／ {NODE *p； p=NODE*)malloc(sizeof(NODE))； if(!p){printf(“out of memory!＼n”); return(-1); } else {p-data=x; p-link=st; st=p; } } ／*从链栈中退栈，通过函数返回数据元素*／ int pop() {NODE *p； int y； if(st ==NULL) {printf(”stack is empty!\n”); return(-1); else {p=st； st=st-link; y=p-data， free(p)； return(y)； } } 链栈上的其他运算的实现留给读者，这里不再讨论了。 2.4 栈、队列和数组 2.4.2 队列 队列的结构特点,弄清队列与线性表的异同,掌握循环队列的组织方法[#领会#] 完成在堆栈和队列上实现的简单算法 [#简单应用#] 一、队列的基本概念 队列(queue)是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。允许删除的一端称为队头(front)，允许插入 的一端称为队尾(rear)，如图2-18所示。在队中，新元素总是加入到队尾，每次删除的总是在队头上的元素，即当前“最老的”元素，所以这种结构叫做“先进先出”(FIFO)表。这就犹如在公共汽车站排队等候上车。 队列的基本运算有： (1)建立一个空队列。 (2)在队尾加入一个元素，称作入队。 (3)删除队头的元素，称作出队。 (4)测试队列是否为空队列。 (5)测试队列是否为满。 * 2.4 栈、队列和数组 二、队列的顺序存储结构 * 图2-19所示的是在入队和出队时，头尾指针的变化情况。设有队列q，它的最大容量是5，front为头指针，rear为尾指针。在初始时，队列空，front=rear=0，如图2 -19(a)。入队时，尾指针加一，在依次入队a1、a2、a3三个元素以后，rear=3。如图2-19(b)。出队时，头指针加一，在出队两个元素以后，front=2，如图2-19(c)。接着再入队一个元素a4，rear =4，如图2-19(d)。尾指针已经到了数组的上界，此时如果还要执行入队运算，就要发生“上溢”，但是数组中还有空位置，此种现象称为“假溢出”。 队列和栈一样可以采用顺序