《算法与数据结构》第3章简单数据结构ppt.ppt

算法与数据结构 第 3章 简单数据结构 简单数据结构 简单的数据结构 ， 包括顺序表 、 链表 、 栈 、 队列和 广义表 ， 它们和上一章介绍过的数组和串一起都同属 于 线性结构 。 在线性结构中 ， 数据元素之间的关系是一对一的次 序关系 ， 其逻辑特征为： 存在一个惟一地被称作 “ 第一个 ” 的数据元素； 存在一个惟一地被称作 “ 最后一个 ” 的数据元素； 除第一个之外 ， 每个数据元素都只有一个前趋； 除最后一个之外 ， 每个数据元素都只有一个后继 。 第 3章 简单数据结构 3.1 顺序表 3.2 链表 3.3 栈 3.4 队列 3.5 广义表 3.1 顺序表 3.1.1 线性表的基本概念 3.1.2 线性表的顺序存储结构 顺序表 3.1.3 顺序表上的基本运算 线性表的基本概念 线性表 （ Linear List） 是一种最简单最常用的数据结构 。 一个线性表是由 n（ n0） 个相同类型数据元素 （ 结点 ） 组 成的 有限序列 。 表中有且仅有一个第一个结点 ， 它没有前 趋而只有一个后继；有且仅有一个最后一个结点 ， 它没有 后继而只有一个前趋；其余结点都只有一个前趋和一个后 继 。 根据结点之间的关系可以排成一个线性序列： （ a1， a2， a3， a4， ， an） 其中： a1为第一个结点 ， an为最后一个结点；对于 i=2 n， ai-1是 ai的前趋 ， ai是 ai-1的后继； n称作线性表的 长度 ， n为 0时称作 空表 。 线性表的例子 线性表中的数据元素 （ 结点 ） 可以是一个数 、 一个符号 、 一页书 、 一个记录等 。 下面给出线性表的几个例子： （ “ A”， “ B”， ， “ Z”） 是一个线性表 ， 称作字母表 ， 表中 的数据元素都是单个大写字母字符； （ 3， 7， 9， 12， 66， 87） 是一个线性表 ， 表中的每个数据元素都 是一个整数； 学生成绩表也是一个线性表 ， 表中的数据元素为描述一个学生高 考情况的一个记录 ， 它由姓名 、 准考证号 、 数学 、 语文 、 英语 、 理综 、 总分七个数据项组成 。 线性表的形式化定义 线性表的形式化定义如下： Linear List=(D,R) 其中： D=ai|ai Do， i=1， 2， ， n， n 0； R=|ai-1,ai Do， i=2， 3， ， n； Do为某个数据对象 。 线性表是一种相当灵活的数据结构 ， 其长度可根 据需要增减 ， 即对数据元素不仅可以访问 ， 还可 进行插入和删除 。 线性表的基本运算 置空表 setnull(L)：将线性表 L置为空表 。 求长度 length(L)：计算线性表 L中数据元素的个数 。 取元素 get(L,i)：取出线性表 L中第 i个数据元素； 要求 ilength(L)。 取前趋 prior(L,x)：取出线性表 L中值为 x的元素的 前趋元素；要求 x的位序大于 1。 取后继 next(L,x)：取出线性表 L中值为 x的元素的 后继元素；要求 x的位序小于 length(L)。 定位序 locate(L,x)：确定元素 x在线性表 L中的位置 ， 并给出位置序号；若 L中无 x返回 0。 线性表的基本运算（续） 插入 insert(L,x,i)：在线性表 L中第 i个位置上插入值为 x的新 元素 ， 使表长增 1；要求 1ilength(L)+1。 删除 delete(L,i)：删除线性表 L中的第 i个元素 ， 使表长减 1； 要求 1ilength(L)。 利用这些基本运算 ， 可以实现线性表的其它较复杂运算 ， 如线性表的分拆 、 合并 、 逆置等 。 在实际应用中 ， 当线性表作为一个运算对象时 ， 所需的运 算种类不一定相同 ， 不同的运算将构成不同的抽象数据类 型 。 这里所给出的运算是定义在逻辑结构上的抽象运算 ， 而运 算的实现要依赖于所采用的存储结构 。 3.1 顺序表 3.1.1 线性表的基本概念 3.1.2 线性表的顺序存储结构 顺序表 3.1.3 顺序表上的基本运算 线性表的顺序存储结构 顺序表 顺序表 （ sequential list） 是用一组 地址连续 的存储单 元依次存放线性表中的各个数据元素 ， 是一种最简单 最自然的线性表存储方法 。 这组地址连续的存储空间的大小依线性表中的数据 元素个数而定 ， 线性表中第一个元素存放在这组空间 的开始处 ， 第二个元素紧跟着存放在第一个元素之 后 ， ， 余类推 。 显然 ， 顺序表中相邻的数据元素在计算机内的存储 位置也相邻； 换句话说 ， 顺序表以数据元素在计算机内的 物理位 置相邻 来表示数据元素在线性表中的逻辑相邻关系 。 线性表的存储地址计算公式 由于线性表中的数据元素具有相同的类型 ， 所以可 以很容易地确定顺序表中每个数据元素在存储空间中 与起始单元的相对位置； 假定线性表中每个数据元素需要占用 c个存储单元 ， loc(a1)是第一个数据元素的存储地址 （ 也称作基地 址 ） ， 则第 i个数据元素的存储地址可由下式确定： loc(ai)=loc(a1)+(i-1)*c 其中： 1ilength(L)+ 1。 显然 ， 顺序表是一种可随机存取的数据结构 。 线性表的顺序存储结构示意图 顺序表的顺序存储结构（续） 由于在高级程序设计语言中的一维数组 （ 或向量 ） 在计算机内分配的是一片连续的存储单元 ， 所以可借 助一维数组为顺序表开辟存储空间存储表中的数据元 素 。 考虑到线性表因插入 、 删除运算长度可变 ， 数组的 容量要足够大 （ 可设为 MAXSIZE， 其值依实际问题而 定 ） ， 并设一指示器变量 last指向表中的最后一个元 素位置 。 为了讨论方便 ， 我们假定元素是从数组下标为 1的位 置开始存放 ， 即 last=0时为空表 。 顺序表的类型描述 #define MAXSIZE 500 typedef struct elemtyPe dataMAXSIZE; int last; sequenlist; 即把顺序表类型 sequenlist描述为一个结构体 ， 域 data数组存放表中的数据元素 ， 域 last存放表长 ， datalast存放表中最后一个元素 。 elemtype为表中数据元素的类型 ， 对于不同的实际问 题可以为不同的具体类型 ， 如整型 int、 实型 float、 字符型 char、 双精度实型 double、 或其它结构类型等 。 3.1 顺序表 3.1.1 线性表的基本概念 3.1.2 线性表的顺序存储结构 顺序表 3.1.3 顺序表上的基本运算 顺序表上的基本运算 在定义了线性表的顺序存储结构之后 ， 就可以讨论 各种基本运算的实现问题了 。 顺序表上的许多运算是很容易实现的 。 例如： 置空表就是使表长为 0， 即 (*L).last=0； 求表长就是读出 last域的值 ， 即 (*L).last； 取元素就是按位序取出 data 域中相应元素 ， 即 (*L).datai；取前趋就是将元素 x的位序前一个元素取出 ， 即 (*L).datalocate(L,x)-1； 取后继即取出 (*L).datalocate(L,x)+1的值等 。 这里只讨论定位序 、 插入和删除运算的实现算法 。 1. 定位序 locate(L,x) 定位序即按值查找 ， 确定元素 x在顺序表 L中的位置 。 最简单的方法是从第一个元素起和 x比较 ， 直到找到 一个值为 x的数据元素返回它的位置序号 （ 即数组下 标 ） ， 或者找遍表中所有元素均无值为 x的元素时返 回 0。 其算法描述如下： int locate(L,x) sequenlist *L; elemtyPe x; int i=1; while(ilast) 定位序 （续） if(iL-last) return 0; /*未找到值为 x的元素返回 0*/ else return i; /*找到值为 x的元素返回它的位序 i*/ /*locate*/ 该算法的主要时间花费在于查找比较的循环 。 当 a1=x时一次比较成功 ， 当 an=x时 n次比较成功 ， 在 x 分 布位置等概率的情况下平均比较次数为 (n+1)/2；查找 不成功时的比较次数为 n+1。 所以算法的时间复杂度 为 O(n)。 2. 插入 insert(L,x,i) 插入运算 是指在顺序表 L的第 i个元素之前加入一个 新元素 x。 插入的结果使 x 在顺序表中第 i个元素位置 上 ， 使顺序表的长度由 n变为 n+1。 插入新元素 x后 ， 部分数据元素间的逻辑关系发生了 改变 ， 要求物理存储位置也要相应变化 。 除非 i=n+1， 否则必须将位序为 i,i+1, ,n的数据元 素向后移动一个元素位置 ， 空出第 i个位置插入新元 素 x；在 i=n+1时直接将新元素 x插入表尾 。 在顺序表中插入新元素 x的过程 插入运算的算法描述 void insert(L,x,i) sequenlist *L; elemtype x; int i; int j; if(i(L-last+1) printf(“插入位置不正确 n”); else if(L-last=MAXSIZE) printf(“表已满 ， 发生上溢 n”); else for(j=L-last;j=i;j-) L-dataj+1=L-dataj; L-datai=x; L-last=L-last+1; /*insert*/ 插入运算算法的时间复杂度 算法中的数据元素移动是从第 n个元素到第 i个元素 依次后移的 。 算法中的主要时间开销在于后移元素的 for循环 ， 循环执行 n-i+1次 。 当 i=n+1时不需移动元素是最 好情况 ， 当 i=1时需移动元素 n次是最坏情况 ， 在插 入位置等概率分布时的平均移动次数为 n/2。 所以算法最好情况下的时间复杂度为 O(1)， 在最坏 情况下的时间复杂度为 O(n)， 在平均情况下的时间 复杂度也是 O(n)。 3.删除 delete(L,i) 删除运算是把顺序表中第 i个元素删掉 ， 使顺序表的 长度由 n变为 n-1， 其部分元素的逻辑关系和存储位置 也发生相应变化 ， 即 由 （ a1,a2, ,ai-1,ai,ai+1, ,an） 变成为 （ a1,a2, ,ai-1,ai+1, ,an） 。 除非 i=n时直接删除 ， 否则需要从第 i+1元素到第 n元 素依次前移一个元素位置 。 在顺序表中删除第 i个元素过程 删除运算的算法描述 void delete(L,i) sequenlist *L; int i; int j; if(iL-last) printf(“删除位置不正确 n”); else for(j=i+1;jlast;j+) L-dataj-1=L-dataj; L-last=L-last-1; /*delete*/ 删除运算算法的时间复杂度 由删除过程可以看出 ， 通过元素 ai+1到 an的依次前移 就达到了删除 ai的目的 。 该算法的时间开销也主要是在元素的移动 。 当 i=n时最好不需移动 ， 当 i=1时最坏需移动 n-1次 ， 在等概率的情况下需平均移动元素 (n-1)/2次 。 其时 间复杂度在最好 、 最坏和平均的情况下分别为 O(1)， O(n)和 O(n)。 举例 删除顺序表中的重复元素 一个顺序表中可能含有一些值相同的重复元素 ， 题目 要求对于值相同的重复元素只保留位序最小的一个而 删除其它多余的元素 。 如 （ 5， 2， 2， 3， 5， 2） 经删除重复元素后变为 （ 5， 2， 3） 算法思路 ：从顺序表中第一个元素起 ， 逐个检查它后 面是否有值相同的其它元素 ， 若有便删除之；直到表 中所有元素都已无重复元素为止 。 为此 ， 算法中需设 两重循环 ， 外层控制清除的趟数 ， 内层控制每趟的检 查范围 。 删除顺序表中的重复元素的算法描述 void Purge(L) sequenlist *L; int i,j,k; i=1; while(ilast) j=i+1; while(jlast) if(L-dataj=L-datai) for(k=j+1;klast;k+) L-datak-1=L-datak; L-last=L-last-1; else j+; i+; /*Purge*/ 举例 有序表的合并 顺序表 A和 B的元素均按由小到大的升序排列 ， 编 写算法将它们合并成为顺序表 C， 要求 C中元素也是 从小到大的升序排列 。 算法思路 ：依次扫描 A和 B中元素 ， 比较当前两个 元素值 ， 将较小的元素赋给 C， 直到其中一个顺序 表扫描完毕 ， 然后将另一个顺序表中剩余元素赋给 C即可 。 有序表的合并的算法描述 void merge(C,A,B) sequenlist *C,*A,*B; int i,j,k; i=1;j=1;k=1; while(ilast else C-datak+=B-dataj+; While(ilast) C-datak+=A-datai+; While(jlast) C-datak+=B-dataj+; C-last=k-1; /*merge*/ 第 3章 简单数据结构 3.1 顺序表 3.2 链表 3.3 栈 3.4 队列 3.5 广义表 3.2 链表 顺序表的特点是 ， 逻辑关系上相邻的两个元素在物理位置上 也相邻 。 这一特点使得顺序表有如下两个优点： 无需为表示数据元素之间的关系而额外增加存储空间； 可以随机存取表中任一数据元素 ， 元素存储位置可以用一个简单 、 直观的公式表示 。 这一特点也造成了这种存储结构的两个缺点： 插入和删除运算必须移动大量 （ 几乎一半 ） 数据元素 ， 效率较低； 必须预先分配存储空间 ， 造成空间利用率低 ， 且表的容量难以扩充 。 本节介绍线性表的另一种存储结构 链式存储结构 。 它不 要求逻辑上相邻的元素在物理位置上也相邻 ， 为表示元素之 间的关系要增加额外存储空间 ， 也不能随机存取数据元素； 但是它没有顺序存储结构所具有的缺点 。 3.2 链表 3.2.1 线性表的链式存储结构 链表 3.2.2 单链表上的基本运算 3.2.3 循环链表和双向链表 3.2.4 线性表应用举例 一元多项式相加问题 线性表的链式存储结构 链表 线性表的 链式存储结构 ， 是用一组任意的存储单元 （ 这组存 储单元的地址可以连续 ， 也可以不连续 ） 来存放线性表中的各 个数据元素的 。 为了表示出每个数据元素与其后继之间的关系 ， 对每个元素 除了存储元素本身的信息外 ， 还需存储指示该元素的后继元素 的地址；这两部分信息组成一个结点 。 存放数据元素信息的域 data称作 数据域 ， 存放后继元素地址信 息的域 next称作 指针域 或 链域 。 一个线性表的 n个元素通过每 个结点的指针域拉成一条 “ 链子 ” ， 所以称之 链表 （ Linked List） 。 由于这种链表中每个结点只含有一个指向后继的指针 ， 所以称作 线性链表 或 单链表 （ Single Linked List） 。 单链表存储举例 对于线性表 （ mon,tue,wed,thu,fri,sat,sun） ， 其单链 表存储示意图如下图 。 单链表 由于单链表中每个结点的存储地址是放在其前趋结 点的指针域中 ， 因此整个链表的存取必须从第一个 结点开始；需设立头指针指示链表中的第一个结点 。 这样就可以由头指针找到第一个结点 ， 再由第一个 结点的指针域找到第二个结点 ， ， 依次顺着指 针域找到每个结点 。 此外 ， 在链表中最后一个结点没有后继 ， 该结点的 指针域为空 ， 用 NULL或 表示空指针域 。 单链表（续） 对于单链表 ， 我们并不关心各个结点的实际存储位 置 ， 而关心的是结点间的逻辑次序关系 ， 故可将单 链表 （ mon,tue,wed,thu,fri,sat,sun） 的画成如下图 。 其中用箭头表示的指针域中的指针 。 由上图可以很 清楚地看出 ， 线性表的链式存储结构是通过链指针 来表示数据元素之间的逻辑关系的 ， 是非顺序存储 结构 。 整个单链表可由头指针惟一确定 ， 所以常用 头指针名来命名一个单链表 ， 如称表 H则意味着该单 链表的头指针为 H。 单链表的 类型 描述 typedef struct node elemtype data; struct node *next; LinkList; LinkList *H,*P; 需要说明的是 ， 定义 LinkList与 struct node为相同类 型不同的类型标识符 （ 名字 ） ， 是为了用它说明单链表类型 ， 这种方法有利于提高程序或算法的可读性 。 另外 ， 指针变量所指向的结点地址并不是在程序中显式给 出 ， 而是在程序的执行过程中用标准函数 malloc根据需要 动态生成的 。 单链表结点空间的申请与释放 malloc函数的返回值类型在 ANSI C版本中是 void *类型 ， 所以动态生成的结点类型必须强制转换为指向该结点的指针类 型 。 具体方法为 P=(LinkList*)malloc(sizeof(LinkList); 它获得一个单链表类型结点 ， 结点地址在指针变量 P。 如下图 当要释放结点空间时可用标准函数 free完成 ， 即 free(P); 它释放指针 P所指结点空间给内存 。 对结点中两个域的访问 ， 只能通过指向该结点的指针进行 ， 如 P-data和 P-next 或者 (*P).data和 (*P).next 3.2 链表 3.2.1 线性表的链式存储结构 链表 3.2.2 单链表上的基本运算 3.2.3 循环链表和双向链表 3.2.4 线性表应用举例 一元多项式相加问题 单链表上的基本运算 为了方便运算 ， 使单链表的空表和非空表的处理一 致 ， 通常在单链表的第一个结点前增加一个头结点 。 头结点的数据类型和其它结点一致 ， 它的数据域无 定义 ， 指针域中存放第一个数据结点的地址 ， 空表 时指针域为空 。 空表和非空表的图形表示如下： 若无特殊说明 ， 本章算法均采用带头结点的单链表 。 1.建立单链表 在单链表中每个元素的存储空间是在需要时才申请 ， 其逻辑 关系靠指针来表示 ， 所以在建立单链表的过程中更多关心的 是指针的链接 。 一开始先申请并生成头结点 ， 然后每读入一个数据元素申请 一个结点 ， 填入数据后插入表尾 ， 为此要设一个尾指针 r。 具体的算法描述如下： LinkList *CreateLinkList() char ch; int x; LinkList *head; /*head为头结点指针 */ LinkList *r,*P; head=(LinkList *)malloc(sizeof(LinkList); head-next=NULL; 建立单链表（续） r=head; /*尾指针初始化 */ ch=getchar(); while(ch!=*) /*“*”为输入数据结束符号 */ scanf(“%d”, P=(LinkList *)malloc(sizeof(LinkList); P-data=x; P-next=NULL; r-next=P; r=r-next; ch=getchar(); return head; /*CreateLinkList*/ 该算法的时间复杂度为 O(n)。 单链表建立过程示例 线性表 （ 25， 45， 18， 76， 29） 的单链表动态建立过程如下 图： 2.求表长 只要设一个移动指针扫描整个单链表 ， 就可以统计出元素个 数即表长 。 其算法描述如下： int LengthLinkList(L) LinkList *L; LinkList *P=L; int j=0; While(P-next!=NULL) P=P-next; j+; return j; /*返回表长 */ /*LengthLinkList*/ 该算法扫描整个单链表 ， 时间复杂度为 O(n)。 3.元素的查找方法一 单链表上元素的查找分 按值查找 和按序号查找。 按值查找 的方法是，从第一个结点起判断当前结点的值是否 等于给定值，若找到返回该结点地址，否则继续下一个结点； 若整个表中未找到返回 NULL。算法描述如下： LinkList *LocateLinkList(L,x) LinkList *L; elemtyPe x; LinkList *P; P=L-next; while(P!=NULL) return P; /*返回找到的结点位置或 NULL*/ /*LocateLinkList*/ 元素的查找方法二 按序号查找 的方法是，从第一个结点起做 i次指针传递返回该 结点地址，若找不到 i次已到表尾则返回 NULL， 算法描述如下： LinkList *GetLinkList(L,i) LinkList *L; int i; LinkList *P; int j=0; P=L; while(jnext!=NULL) P=P-next; j+; if(j=i) return P; else return NULL; /*GetLinkList*/ 这两个算法的时间复杂度在最坏情况下和等概率平均情况下都 为 O(n)。 4.插入 在单链表中插入元素只需修改有关结点的指针域内容 ， 不需 象顺序表那样移动元素 。 插入运算有 前插 和 后插 两种：设 P指向单链表中某结点 ， S指 向待插入的新结点 ， 把 *S插入到 *P的前面称作 前插 ， 而把 *S 插入 *P的后面称作 后插 。 后插操作的命令如下 ， 且操作次序不能交换 。 S-next=P-next; P-next=S; 后插的示意图如下图： 插入（续） 前插需要 *P的前趋 *q， 然后再完成在 *q之后插入 *S的后插； 这就需要从第一个结点开始查找 *P的前趋 *q， 使得时间开销 由后插的 O(1)上升到 O(n)。 能不能也用 O(1)的时间开销完成 前插呢 ？ 回答是肯定的 。 我们只要先把 *S插入到 *P的后面 ， 然后再将 P-data与 S-data互相交换即可；这样既能满足逻辑 关系 ， 也能使得时间开销为 O(1)。 其操作过程为 S-next=P-next; P-next=S; x=P-data; P-data=S-data; S-data=x; 插入算法描述 在单链表 L中第 i个位置上插入值为 x的元素的算法描述： LinkList *insertLinkList(L,x,i) LinkList *L; elemtyPe x; int i; LinkList *P,*S; P=getLinkList(L,i-1);/*查找第 i-1个结点 */ if(P=NULL) Printf(“第 i-1个元素不存在 ， 参数 i有错 n”); else S=(LinkList *)malloc(sizeof(LinkList); S-data=x; S-next=P-next; P-next=S; /*insertLinkList*/ 该算法的时间复杂度为 O(n)。 5.删除 设 P为指向单链表中某结点的指针 ， 删除 P所指结点即 *P的操 作示意图如下图 。 由示意图可见 ， 要删除 *P先要找到 *P的前趋结点 *q， 然后完 成指针的变化操作即可 。 显然要找到 *P的前趋得有 O(n)的时间开销 。 在找到 *q的前提 下 ， 删除 *P的操作可由下列语句实现： q-next=P-next; free (P); 删除（续） 若要删除 P所指结点的后继结点 （ 假设存在 ） ， 时间开销 为 O(1),直接完成删除即可： S=P-next; P-next=S-next; free S; 要删除单链表 L中的第 i个结点 ， 关键是先找出第 i-1个结 点 （ 即前趋结点 ） ， 然后完成删除并释放被删结点空间的 工作 。 删除单链表 L中的第 i个结点算法 LinkList *deleteLinkList(L,i) LinkList *L; int i; LinkList *P,*S; P=getLinkList(L,i-1);/*查找第 i-1个结点 */ if(P=NULL) Printf(“第 i-1个元素不存在 ， 参数 i 有错 n”); else S=P-next; P-next=S-next; free (S); *deleteLinkList*/ 该算法的时间复杂度为 O(n)。 举例 将单链表 H逆置 所谓 逆置 是指结点间的关系相反 ， 即前趋变后继而后继变前 趋 。 如图 (a)的单链表逆置后成为图 (b)的单链表 。 算法思路 ：依次从原链表中取出每个结点 ， 每次都把它作为 第一个结点插入到新链表中去 。 为此要借用两个指针变量 P和 q， P用来指向原链表中的当前第一个结点 ， q用来指向从原表 取出的每一个结点并利用它插入到新链表中去 ， 当 P为空时完 成逆置 。 将单链表 H逆置的算法描述 void reverse(H) LinkList *H; LinkList *P,*q; P=H-next; H-next=NULL; while(P!=NULL) q=P; P=P-next; q-next=H-next; H-next=q; *reverse*/ 该算法没有开辟新的存储空间 ， 对链表顺序扫描一遍就完成 了逆置 ， 时间开销为 O(n)。 3.2 链表 3.2.1 线性表的链式存储结构 链表 3.2.2 单链表上的基本运算 3.2.3 循环链表和双向链表 3.2.4 线性表应用举例 一元多项式相加问题 循环链表 循环链表 （ Circular Linked List） 是链式存 储结构的另一种形式 ， 其特点是表中最后一个结点的 指针域指向头结点 ， 使整个链表构成一个环 ， 可以从 表中任一结点出发访问遍所有结点 （ 即遍历 ） 。 单循环链表的空表和非空表两种状态如下图所示： 单循环链表上的基本运算与单链表基本一致 ， 差别 仅在于对最后一个结点的循环处理上；单链表是判断 指针是否为空 （ NULL） ， 而单循环链表是判断指针是 否指向头结点 。 求循环链表的表长算法描述 int Lengthcircularlist(L) LinkList *L; LinkList *P; int j=0; P=L; While(P-next!=L) /*与求单链表表长差别仅在于把 NULL换为头指针 L*/ P=P-next; j+; return j; /*Lengthcircularlist*/ 循环链表（续） 有时对链表常做的操作是在表尾和表头进行 。 为了找尾结点必须从头结点开始扫描全部结点 ， 时 间开销为 O(n)；而找头结点仅 O(1)时间 。 改进的方法是不设头指针而设尾指针 。 这样找到头 结点和尾结点都只需要 O(1)的时间 ， 头结点为 (*(*r).next).next而尾结点为 r， 对于在链表的头尾 操作的应用十分方便 。 带尾指针的循环链表 如下图所示： 双向链表 在单循环链表中 ， 虽然可以从任一已知结点出发找到其 前趋结点 ， 但需耗时 O(n)， 原因在于每个结点只有一个 指向后继的指针域 。 如果希望能够快速确定任一结点的前趋 ， 就必须付出空 间代价 ， 即增加一个指针域存储其前趋信息 ， 这样每个 结点就有两个方向不同的链 ， 称之为 双向链表 （ double linked list） 。 如果让每条链都构成一个环 ， 则称为 双向循环链表 （ double circular linked list） 。 双向链表的使用往往做成双循环链表 ， 和单循环链表类 似 ， 也是由头指针标识 ， 也可以增加头结点方便运算 。 双向链表的结点定义和类型 typedef struct dupnode elemtype data; struct dupnode *prior,*next; dulinklist; dulinklist *H; 双向链表是一种对称结构 ， 每个结点都既有指向其前趋 的指针 ， 也有指向其后继的指针；每个结点的地址既放 在其后继结点的前趋域中 ， 也放在其前趋结点的后继域 中 。 即有 P-next-prior=P=P-prior-next 双向链表示意图 双向链表插入运算 与单链表相比双向链表的运算要方便得多 。 然而由于要 涉及多指针域的运算 ， 对于某些运算要注意运算的先后 顺序 。 在 *P之前插入 *S的步骤为： P-prior-next=s; S-prior=P-prior; S-next=P; P-prior=S; 尽管上面的指针操作顺序不是惟一的 ， 但是也不能任意 次序 ， 必须保证操作 在操作 之前完成 ， 否则 *P的前 趋域的信息就丢掉了 ， 导致不能正确地插入 *S。 双向链表插入运算的示意图 双向链表的删除运算 删除 P所指结点 （ 即 *P） 的操作步骤为： P-prior-next=P-next; P-next-prior=P-prior; free (P); 在双向链表中删除一个结点的运算如下图所示： 3.2 链表 3.2.1 线性表的链式存储结构 链表 3.2.2 单链表上的基本运算 3.2.3 循环链表和双向链表 3.2.4 线性表应用举例 一元多项式相加问题 一元多项式 一个一元多项式可以表示为 P(x)=a0+a1x+a2x2+ +anxn 其中： a0,a1,a2, ,an这 n+1个系数惟一确定了多项式 ， 而 每一项的指数隐含在系数 ai的序号中 ， 所以一元多项式 可以由线性表 （ a0,a1, ,an） 来表示 。 设 A=(a0,a1, ,an )， B=(b0,b1, ,bm)， 则多项式加法就是 求 A+B=C。 其中： C=(a0+b0,a1+b1, ,am+bm,am+1, ,an) 或 C=（ a0+b0,a1+b1, ， an+bn,bn+1, ,bm） 。 一元多项式在计算机中的表示 如何在计算机中表示描述多项式的线性表呢 ？ 我们首先考 虑用顺序表 （ 即顺序存储结构 ） 。 如果只存储系数让指数隐含在系数序号中 ， 则会浪费存储 空间 ， 如 T(x)=3+5x200+7x1000的线性表长度为 1001， 而其中仅 有三个非零元素 ， 故应当避免 。 解决的办法是对每一非零项用 （ 系数 ， 指数 ） 二元组 ， T(x) 只需存储 （ 3， 0） ， （ 5， 200） 和 （ 7， 1000） 三个有序对 ， 显然对高阶稀疏多项式这种方法较好 。 顺序存储便于访问 ， 但插入删除需大量移动元素 ， 所以对 只需求多项式的值无需修改系数和指数值的情况下 ， 采用顺 序表结构较好 。 一元多项式的数据类型定义 如果是多项式的运算问题如相加和相乘等 ， 考虑到 会产生新的项和系数为零项减少这两种情况 ， 宜考 虑采用链式存储结构即单链表实现 。 其数据类型可如下定义： typedef struct linknode float coef; int exp; struct linknode *next; polynomial; 多项式的链式存储表示示例 假设使用头结点 ， 前述的 T(X)= 3+5x200+7x1000可表示 为如下图所示的结构： 多项式相加算法的思路 不产生新结点而利用原有结点空间 ， 设两个指针变 量 p和 q分别指向 A和 B两个多项式单链表的第一个结 点 ， 依次比较两指针所指结点的指数项 。 若指数相等系数相加 ， 和不为零修改 *p的系数项并 删除 *q， 和为零删除 *p和 *q； 若指数不等 ， p-expexp时 *p为和多项式中的一 项 ， p-expq-exp时把 *q插在 *p之前 （ *q为和多项 式中的一项 ） ； 所有操作之后要相应移动指针 。 直到其中一个链空 ， 把另一个链剩下的结点插在 *p之后 。 多项式相加算法的描述 void polyadd(A,B) polynomial *A,*B; polynomial *p,*q,*s,*r; float x; p=A-next; q=B-next; s=A; while(p!=NULL) q-next=p; /*把 p接在 q所指结点后 */ s-next=q; /*把 q接入结果链 */ s=q; q=r; else if(p-expexp) s=p; p=p-next; 多项式相加算法的描述（续） else x=p-coef+q-coef; if(x!=0) p-coef=x; s=p; else s-next=p-next; free(p); p=s-next; r=q; q=q-next; free(r); if(q!=NULL) s-next=q; /*把 q链剩余结点链入结果链 */ free(B); /* polyadd*/ 该算法的比较次数与 A、 B两个多项式的长度 m和 n有关 ， 算法 的时间复杂度为 O(m+n)。 第 3章 简单数据结构 3.1 顺序表 3.2 链表 3.3 栈 3.4 队列 3.5 广义表 3.3 栈 3.3.1 栈的概念及运算 3.3.2 顺序栈及运算实现 3.3.3 链栈及运算实现 3.3.4 栈的应用举例 递归的实现 栈的概念 栈 （ stack） 是操作受限的线性表 ， 限定对元素 的插入和删除运算只能在表的一端进行 。 通常把进行插入和删除操作的这一端称作 栈顶 （ top） ， 另一端称作 栈底 （ bottom） ； 把栈的插入元素操作称作 进栈 、 入栈 或 压入 ； 栈的删除元素操作称作 退栈 、 出栈 或 弹出 ； 当栈中没有元素时称作 空栈 。 栈的概念（续） 由栈的定义可知 ， 每一次 入栈 的 元素都在原栈顶元素之上成为新 的栈顶元素 ， 每一次 出栈 的元素 总是当前栈顶元素使次栈顶元素 成为新的栈顶元素 ， 即最后进栈 的元素总是最先出栈 。 所以栈也 称作 后进先出 （ Last In First Out） 表 ， 简称 LIFO表 。 如右图 所示 ， 元素是以 a1,a2, ,an-1,an 的次序进栈 ， 出栈的次序则是 an,an-1, ,a2,a1。 栈的基本运算 置空栈 setnull(s)：将栈 S设置成空栈 ， 即不管栈的原来 状态如何一律置为空栈； 判栈空 empty(s)：返回一个布尔值 ， 当栈 S为空时返回 1， 否则返回 0； 进栈 push(s,x)：该操作把元素 X压入栈 S中 ， 成为新的栈 顶元素； 出栈 pop(s)：该操作从栈顶弹出栈顶元素并返回 ， 栈 S为空 时返回 NULL； 读栈顶元素 gettop(s)：该操作返回栈 S的栈顶元素 ， 当栈 S为空时返回 NULL；它与 pop(s)的差别仅在于没有弹出栈顶 元素 ， 栈 S 的状态没有改变 ， 只是读栈顶元素的值并返回 。 3.3 栈 3.3.1 栈的概念及运算 3.3.2 顺序栈及运算实现 3.3.3 链栈及运算实现 3.3.4 栈的应用举例 递归的实现 顺序栈 利用顺序存储结构实现的栈称作 顺序栈 （ sequential stack） 。 类似于顺序表 ， 栈中的数据元素用一个预设的足够长度的 一维数组来存放 ， 栈底位置可以设在数组的任一端点 ， 而 栈顶是随着插入和删除运算而变化的 ， 用 top指针指示当前 栈顶的位置 。 顺序栈的类型描述如下： #define MAXSIZE 100 typedef struct elemtype dataMAXSIZE; int top; seqstack; seqstack *s; 顺序栈（续） 通常把 0下标端设为栈底 ， 这样栈空时栈顶指针 top=-1， 栈 满时栈顶指针 top= MAXSIZE-1； 入栈 时栈顶指针加 1（ 即 s-top+） ， 然后数据元素进栈； 出栈 时在读出栈顶数据元素后栈顶指针减 1， 即 s-top-。 在栈满时做入栈操作会产生空间不足的情况 ， 简称 上溢 （ overflow） ； 而在栈空时做出栈操作会产生无元素可出的情况 ， 简称 下 溢 （ underflow） 。 上溢和下溢两种情况均应该避免 ， 而栈空在应用中通常作 为算法 （ 或程序 ） 的控制转移条件 。 栈顶指针与数据元素之间的关系 顺序栈的基本运算 空栈操作 置空栈算法 void setnull(seqstack *s) /*不论栈 S状态如何 ， 都置 top为 -1*/ s-top=-1; 判栈空算法 int empty(seqstack *s) /*依 top值 ， 在空栈时返回 1， 否则返回 0*/ if(s-top=-1) return 1; else return 0; 顺序栈的基本运算 进栈 进栈算法 int push(seqstack *s,elemtype x) /*把元素 x压入栈 s中 */ if(s-top=MAXSIZE-1) return 0; /*栈上溢进栈不成功返回 0标志 */ else s-top+; /*栈顶指针加 1*/ s-datas-top=x; /*元素 x进栈 */ return 1; /*进栈成功返回 1标志 */ 顺序栈的基本运算 出栈 出栈算法 elemtype pop(seqstack *s) if(s-top=-1) return NULL; else s-top-; /*栈顶指针减 1*/ return s-datas-top+1; /*返回原栈顶元素的值 */ 顺序栈的基本运算 读栈顶元素 读栈顶元素算法 elemtype gettop(seqstack *s) /*读栈顶元素并返回其值 */ if(s-top=-1) return NULL; /*栈空无元素返回 NULL*/ else return s-datas-top; /*否则返回栈顶元素值 */ 两栈共享 在一个应用程序中需要使用多个栈的时候 ， 为了提高空间 的使用效率 ， 减少预分配空间过多造成的浪费 ， 又能降低 发生栈上溢而产生错误中断的可能性 ， 可以让多个栈共享 存储空间 。 例如两栈共享一维数组空间 ， 可按 “ 底设两端 、 相向而动 、 迎面增长 ” 的方式组织 共享栈 ， 如下图所示 。 仅当两个栈顶相遇才会发生上溢 ， 栈顶可以越过中间点 ， 显然比各用一半空间发生上溢的概率要小得多 。 两栈共享的数据类型定义 两栈共享的数据类型可如下定义： typedef struct elemtype stackm; /*m为数组长度 ， 可依具体问题而定 */ int top2; /* top0和 top1分别为两栈的栈顶指针 */ sharedstack; 两栈共享的基本运算 置空栈 置空栈算法 void setnull(sharedstack *s) s-top0=-1; /*0号栈空为 -1*/ s-top1=m; /*1号栈空为 m*/ 两栈共享的基本运算 进栈 进栈算法 int push(sharedstack *s,int i,elemtype x) /* i=0,1为两栈的编号 ， 算法把元素 x压入栈 si 中 */ if(i1|s-top0+1=s-top1) return 0; else if(i=0) s-stack+s-top0=x; else s-stack-s-top1=x; return 1; 两栈共享的基本运算 出栈 出栈算法 elemtype pop(sharedstack *s,int i) /*弹出 i号栈的栈顶元素 */ if(i1) return NULL; /*参数出错无法弹出 */ else if(i=0) if (s-top0=-1) return NULL; /*0号栈无法弹出 */ else return s-stacks-top0-; else if(s-top1=m) return NULL; /*1号栈无法弹出 */ else return s-stacks-top1+; 3.3 栈 3.3.1 栈的概念及运算 3.3.2 顺序栈及运算实现 3.3.3 链栈及运算实现 3.3.4 栈的应用举例 递归的实现 链栈的基本概念 利用链式存储结构实现的栈称作 链栈 （ link stack） 。 链栈中的每个数据元素用一个结点表 示 ， 其结构形式与单链表完全相同 。 链栈从本质上讲就是单链表 ， 无非是 限制了插入和删除运算只能在链头进 行 ， 所以可以说链栈就是限制插入和 删除运算只能在链头进行的单链表 。 由于在链头运算 ， 所以不用象单链表 那样附加头结点 ， 更方便运算 ， 如右 图所示 。 链栈的类型定义 链栈的类型定义如下： typedef struct node elemtype data; struct node *next; linkstack; linkstack *top; /*栈顶指针 ， 即链头指针 */ 链栈的基本运算 空栈操作 置空栈算法 void setnull(linkstack *top) top=NULL; /*只要置 top为空即可 */ 判栈空算法 int empty(linkstack *top) /*栈空返回 1否则返回 0*/ if(top=NULL) return 1; else return 0; 链栈的基本运算 进栈 进栈算法 void push(linkstack *top,elemtype x) /*注意：链栈不会发生上溢 ！ */ linkstack *p; p=(linkstack*)malloc(sizeof(linkstack); p-data=x; p-next=top; top=p; 链栈的基本运算 出栈 出栈算法 elemtype pop(linkstack *top) linkstack *p; elemtype x; if(top=NULL) return NULL; /*栈为空无元素弹出 */ else p=top; /*保存栈顶指针于 P中 */ x=top-data; top=top-next; free (p); return x; /*返回弹出元素的值 */ 链栈的基本运算 读栈顶元素 读栈顶元素算法 elemtype gettop(linkstack *top) if(top=NULL) return NULL; /*若栈为空返回空 */ else return top-data; /*否则返回栈顶元素的值 */ 3.3 栈 3.3.1 栈的概念及运算 3.3.2 顺序栈及运算实现 3.3.3 链栈及运算实现 3.3.4 栈的应用举例 递归的实现 栈的应用 栈在计算机学科有着许多重要的应用 。 例如： 把十进制整数转换为二进制整数的方法是 “ 除 2取余 ， 逆序排列 ” ， 利用栈来记下每次余数最后输出栈中内容 即可； 在语言翻译中要把十进制表达式的中缀形式先转换成后 缀形式 ， 然后把后缀表达式翻译成为一条条运算指令 ， 在后续课程 编译原理 中大家会看到都得使用栈结构 来完成； 在算法设计中的需要回溯处理的问题如迷宫问题 、 二叉 树的遍历 、 图的遍历等非递归算法的设计需要借助栈来 完成 ， 把递归过程转换为非递归过程也需要借助栈结构； 还有语言翻译中的函数调用 ， 过程调用 ， 递归子程序处 理等等都离不开栈的应用 。 栈的应用举例 递归的实现 递归 是算法和程序设计中的一个重要概念 ， 也是算法和程 序设计的一种重要方法和手段 。 在高级程序设计语言中有过程 、 函数和子程序等程序模块 的概念 ， 这些程序模块是架构结构化程序的基本单位 。 当这些模块直接或间接地在程序中调用了自身 ， 就称作 递 归程序模块 ； 直接调用自身的称为 直接递归 ， 间接调用自身的称为 间接递归 。 递归的概念对于程序模块而存在 ， 即递归过程 、 递归函数 、 递归子程序等 ， 其前提是问题定义的递归特性和数据结构的 递归特性 。 而问题定义的递归特性主要靠我们在对求解问题本 身的分析和理解的过程中去发现 。 栈的应用举例 递归的实现 (续 ) 在 C语言中 ， 当一个函数体内出现了自身的函数名 （ 即直接调用自身 ） ， 就称该函数为 直接递归函数 ； 当一个函数通过调用其它函数来调用了自身 ， 如 函数 A调用函数 B， 函数 B调用函数 C， 函数 C又调用 了函数 A， 这种情况下称函数为 间接递归函数 （ A、 B、 C都是间接递归函数 ） 。 递归的实现 求阶乘 阶乘函数可递归定义如下： 必须注意 ， 递归定义不能是无限循环地定义 ！ 任何递归定 义必须同时满足如下两个条件： 被定义项在定义中的应用 （ 即作为定义项的出现 ） 应 具有更小的 “ 尺度 ” ； 被定义项在最小 “ 尺度 ” 上的定义不是递归的 。 例如上述的阶乘函数定义中 ， 被定义项 n！ 在定义中的应用 (n-1)!具有比原来 n更小的 “ 尺度 ” n-1；同时 n！ 在最小 “ 尺度 ” 为 0上的定义由自然数 1直接定义不是递归的 。 这两 个条件实际上构成了递归程序设计的基本原则 。 此外 ， 通常把反映条件 的部分 （ 即递归结束条件 ） 写在 递归程序模块的开头处 。 递归的实现 求阶乘 (续 ) 许多实际问题是可以递归定义的 ， 对于这些问题 很容易写出它们的递归求解算法 。 计算阶乘函数的递归算法如下： int fact(int n) if(n=0) return 1; else return n*fact(n-1); 递归的实现 求阶乘 (续 ) 递归函数的运行引起递归调用 。 例如 ， fact(4)的执行中递归函数出现的调用 返回 过程如下图所示： fact(4) fact(3) fact(2) fact(1) fact(0) 1 1 2 6 24 函数 调用与返回 返回值 函数的调用与返回 通常 ， 当一个函数调用另一个函数时 ， 在执行被调 用函数前系统要预先做三件事情： 将所有的实参和函数返回地址等信息传递给被调用函数； 为被调用函数的局部变量分配存储空间 将控制转移到被调用函数的入口处 。 而在从被调用函数返回调用函数之前 ， 系统也需要 做如下三件事情： 保存被调用函数的计算结果； 释放为被调用函数局部变量分配的数据空间； 按返回地址将控制转移给调用函数 。 函数的嵌套调用 当多个函数构成嵌套调用时 ， 系统按照先调用后 返回的原则进行工作 。 这种信息的传递和控制转移符合后进先出的原则 ， 使用栈来实现是非常自然的 。 系统将整个程序运行期间所需要的存储空间都利 用一个工作栈来管理 ， 每当调用 （ 或执行 ） 一个函 数时 ， 就为它在栈顶分配一个存储区； 每当退出 （ 或执行完 ） 一个函数时 ， 就释放为它 所分配的存储区； 当前工作的函数的数据区总在工作栈的当前栈顶 位置 。 函数的嵌套调用时栈变化过程 函数嵌套调用时工作栈的变化情况如下图 ， 其中的 1和 2表 示返回地址 ， 是程序中的语句标号 。 递归函数的执行过程 递归函数的执行过程类似于嵌套调用时的情况 ， 只不过是在直接递归时的调用函数和被调用函数是 同一个函数罢了 。 例如前述的 fact函数 ， 从递归调用开始 ， 每递归 调用深入一层 ， 就在工作栈的栈顶为所有形参局部 变量和返回地址开辟空间保存 ， 每退出一层递归就 从栈顶释放为本层开辟的空间并返回调用层 。 由于是同一个函数 ， 其返回地址应为同一语句位 置设为 r。 递归调用 fact(4)的工作栈变量情况 递归的实现小结 利用递归算法 （ 函数 、 过程 、 子程序等 ）