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

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