《第3章 简单数据结构精选文档.ppt》由会员分享，可在线阅读，更多相关《第3章 简单数据结构精选文档.ppt（175页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3章 简单数据结构本讲稿第一页，共一百七十五页简单数据结构简单的数据结构，包括顺序表、链表、栈、队列和广义表，它们和上一章介绍过的数组和串一起都同属于线性结构。在线性结构中，数据元素之间的关系是一对一的次序关系，其逻辑特征为：存在一个惟一地被称作“第一个”的数据元素；存在一个惟一地被称作“最后一个”的数据元素；除第一个之外，每个数据元素都只有一个前趋；除最后一个之外，每个数据元素都只有一个后继。本讲稿第二页，共一百七十五页第3章 简单数据结构 3.1 顺序表3.2 链表3.3 栈3.4 队列3.5 广义表本讲稿第三页，共一百七十五页3.1 顺序表3.1.1 线性表的基本概念3.1.2 线性表
2、的顺序存储结构顺序表3.1.3 顺序表上的基本运算本讲稿第四页，共一百七十五页线性表的基本概念线性表（LinearList）是一种最简单最常用的数据结构。一个线性表是由n（n0）个相同类型数据元素（结点）组成的有限序列。表中有且仅有一个第一个结点，它没有前趋而只有一个后继；有且仅有一个最后一个结点，它没有后继而只有一个前趋；其余结点都只有一个前趋和一个后继。根据结点之间的关系可以排成一个线性序列：（a1，a2，a3，a4，an）其中：a1为第一个结点，an为最后一个结点；对于i=2n，ai-1是ai的前趋，ai是ai-1的后继；n称作线性表的长度，n为0时称作空表。本讲稿第五页，共一百七十五页
3、线性表的例子线性表中的数据元素（结点）可以是一个数、一个符号、一页书、一个记录等。下面给出线性表的几个例子：（“A”，“B”，“Z”）是一个线性表，称作字母表，表中的数据元素都是单个大写字母字符；（3，7，9，12，66，87）是一个线性表，表中的每个数据元素都是一个整数；学生成绩表也是一个线性表，表中的数据元素为描述一个学生高考情况的一个记录，它由姓名、准考证号、数学、语文、英语、理综、总分七个数据项组成。本讲稿第六页，共一百七十五页线性表的形式化定义线性表的形式化定义如下：LinearList=(D,R)其中：D=ai|aiDo，i=1，2，n，n0；R=|ai-1,aiDo，i=2，3，
4、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中的位置，并
5、给出位置序号；若L中无x返回0。本讲稿第八页，共一百七十五页线性表的基本运算（续）插入insert(L,x,i)：在线性表L中第i个位置上插入值为x的新元素，使表长增1；要求1ilength(L)+1。删除delete(L,i)：删除线性表L中的第i个元素，使表长减1；要求1ilength(L)。利用这些基本运算，可以实现线性表的其它较复杂运算，如线性表的分拆、合并、逆置等。在实际应用中，当线性表作为一个运算对象时，所需的运算种类不一定相同，不同的运算将构成不同的抽象数据类型。这里所给出的运算是定义在逻辑结构上的抽象运算，而运算的实现要依赖于所采用的存储结构。本讲稿第九页，共一百七十五页3.1
6、 顺序表3.1.1 线性表的基本概念3.1.2 线性表的顺序存储结构顺序表3.1.3 顺序表上的基本运算本讲稿第十页，共一百七十五页线性表的顺序存储结构顺序表顺序表（sequentiallist）是用一组地址连续的存储单元依次存放线性表中的各个数据元素，是一种最简单最自然的线性表存储方法。这组地址连续的存储空间的大小依线性表中的数据元素个数而定，线性表中第一个元素存放在这组空间的开始处，第二个元素紧跟着存放在第一个元素之后，余类推。显然，顺序表中相邻的数据元素在计算机内的存储位置也相邻；换句话说，顺序表以数据元素在计算机内的物理位置相邻来表示数据元素在线性表中的逻辑相邻关系。本讲稿第十一页，共
7、一百七十五页线性表的存储地址计算公式由于线性表中的数据元素具有相同的类型，所以可以很容易地确定顺序表中每个数据元素在存储空间中与起始单元的相对位置；假定线性表中每个数据元素需要占用c个存储单元，loc(a1)是第一个数据元素的存储地址（也称作基地址），则第i个数据元素的存储地址可由下式确定：loc(ai)=loc(a1)+(i-1)*c其中：1ilength(L)+1。显然，顺序表是一种可随机存取的数据结构。本讲稿第十二页，共一百七十五页线性表的顺序存储结构示意图本讲稿第十三页，共一百七十五页顺序表的顺序存储结构（续）由于在高级程序设计语言中的一维数组（或向量）在计算机内分配的是一片连续的存储
8、单元，所以可借助一维数组为顺序表开辟存储空间存储表中的数据元素。考虑到线性表因插入、删除运算长度可变，数组的容量要足够大（可设为MAXSIZE，其值依实际问题而定），并设一指示器变量last指向表中的最后一个元素位置。为了讨论方便，我们假定元素是从数组下标为1的位置开始存放，即last=0时为空表。本讲稿第十四页，共一百七十五页顺序表的类型描述#define MAXSIZE 500 typedef struct elemtyPe dataMAXSIZE;int last;sequenlist;即把顺序表类型sequenlist描述为一个结构体，域data数组存放表中的数据元素，域last存放表
9、长，datalast存放表中最后一个元素。elemtype为表中数据元素的类型，对于不同的实际问题可以为不同的具体类型，如整型int、实型float、字符型char、双精度实型double、或其它结构类型等。本讲稿第十五页，共一百七十五页3.1 顺序表3.1.1 线性表的基本概念3.1.2 线性表的顺序存储结构顺序表3.1.3 顺序表上的基本运算本讲稿第十六页，共一百七十五页顺序表上的基本运算在定义了线性表的顺序存储结构之后，就可以讨论各种基本运算的实现问题了。顺序表上的许多运算是很容易实现的。例如：置空表就是使表长为0，即(*L).last=0；求表长就是读出last域的值，即(*L).la
10、st；取元素就是按位序取出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
11、)sequenlist*L;elemtyPe x;int i=1;while(ilast)&(L-datai!=x)i+;本讲稿第十八页，共一百七十五页定位序（续）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)插入
12、运算是指在顺序表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)pr
13、intf(“插入位置不正确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。所以算法最好情况下的
14、时间复杂度为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)sequ
15、enlist*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)。本讲稿第二十七页
16、，共一百七十五页举例删除顺序表中的重复元素 一个顺序表中可能含有一些值相同的重复元素，题目要求对于值相同的重复元素只保留位序最小的一个而删除其它多余的元素。如（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;whil
17、e(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)sequenl
18、ist*C,*A,*B;int i,j,k;i=1;j=1;k=1;while(ilast&jlast)if(A-dataidataj)C-datak+=A-datai+;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 链表顺序表的特点是，逻辑关系上相邻的两个元素在物理位置上也相邻。这
19、一特点使得顺序表有如下两个优点：无需为表示数据元素之间的关系而额外增加存储空间；可以随机存取表中任一数据元素，元素存储位置可以用一个简单、直观的公式表示。这一特点也造成了这种存储结构的两个缺点：插入和删除运算必须移动大量（几乎一半）数据元素，效率较低；必须预先分配存储空间，造成空间利用率低，且表的容量难以扩充。本节介绍线性表的另一种存储结构链式存储结构。它不要求逻辑上相邻的元素在物理位置上也相邻，为表示元素之间的关系要增加额外存储空间，也不能随机存取数据元素；但是它没有顺序存储结构所具有的缺点。本讲稿第三十三页，共一百七十五页3.2 链表3.2.1 线性表的链式存储结构链表3.2.2 单链表上
20、的基本运算 3.2.3 循环链表和双向链表3.2.4 线性表应用举例一元多项式相加问题本讲稿第三十四页，共一百七十五页线性表的链式存储结构链表 线性表的链式存储结构，是用一组任意的存储单元（这组存储单元的地址可以连续，也可以不连续）来存放线性表中的各个数据元素的。为了表示出每个数据元素与其后继之间的关系，对每个元素除了存储元素本身的信息外，还需存储指示该元素的后继元素的地址；这两部分信息组成一个结点。存放数据元素信息的域data称作数据域，存放后继元素地址信息的域next称作指针域或链域。一个线性表的n个元素通过每个结点的指针域拉成一条“链子”，所以称之链表（LinkedList）。由于这种链
21、表中每个结点只含有一个指向后继的指针，所以称作线性链表或单链表（SingleLinkedList）。本讲稿第三十五页，共一百七十五页单链表存储举例对于线性表（mon,tue,wed,thu,fri,sat,sun），其单链表存储示意图如下图。本讲稿第三十六页，共一百七十五页单链表由于单链表中每个结点的存储地址是放在其前趋结点的指针域中，因此整个链表的存取必须从第一个结点开始；需设立头指针指示链表中的第一个结点。这样就可以由头指针找到第一个结点，再由第一个结点的指针域找到第二个结点，依次顺着指针域找到每个结点。此外，在链表中最后一个结点没有后继，该结点的指针域为空，用NULL或表示空指针域。本讲
22、稿第三十七页，共一百七十五页单链表（续）对于单链表，我们并不关心各个结点的实际存储位置，而关心的是结点间的逻辑次序关系，故可将单链表（mon,tue,wed,thu,fri,sat,sun）的画成如下图。其中用箭头表示的指针域中的指针。由上图可以很清楚地看出，线性表的链式存储结构是通过链指针来表示数据元素之间的逻辑关系的，是非顺序存储结构。整个单链表可由头指针惟一确定，所以常用头指针名来命名一个单链表，如称表H则意味着该单链表的头指针为H。本讲稿第三十八页，共一百七十五页单链表的类型描述 typedef struct node elemtype data;struct node*next;Li
23、nkList;LinkList*H,*P;需要说明的是，定义LinkList与struct node为相同类型不同的类型标识符（名字），是为了用它说明单链表类型，这种方法有利于提高程序或算法的可读性。另外，指针变量所指向的结点地址并不是在程序中显式给出，而是在程序的执行过程中用标准函数malloc根据需要动态生成的。本讲稿第三十九页，共一百七十五页单链表结点空间的申请与释放malloc函数的返回值类型在ANSI C版本中是void*类型，所以动态生成的结点类型必须强制转换为指向该结点的指针类型。具体方法为 P=(LinkList*)malloc(sizeof(LinkList);它获得一个单链
24、表类型结点，结点地址在指针变量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 线性表应用举例一元多项式相加问题本讲稿第四十一页，共一百七十五页单链表上的基本运算为了方便运算，使单链表的空表和非空表的处理一致，通常在单链表的第一个结点前增加一个头结点。头结点的数据类
25、型和其它结点一致，它的数据域无定义，指针域中存放第一个数据结点的地址，空表时指针域为空。空表和非空表的图形表示如下：若无特殊说明，本章算法均采用带头结点的单链表。本讲稿第四十二页，共一百七十五页1.建立单链表在单链表中每个元素的存储空间是在需要时才申请，其逻辑关系靠指针来表示，所以在建立单链表的过程中更多关心的是指针的链接。一开始先申请并生成头结点，然后每读入一个数据元素申请一个结点，填入数据后插入表尾，为此要设一个尾指针r。具体的算法描述如下：LinkList*CreateLinkList()char ch;int x;LinkList*head;/*head为头结点指针*/LinkList
26、*r,*P;head=(LinkList*)malloc(sizeof(LinkList);head-next=NULL;本讲稿第四十三页，共一百七十五页建立单链表（续）r=head;/*尾指针初始化*/ch=getchar();while(ch!=*)/*“*”为输入数据结束符号*/scanf(“%d”,&x);P=(LinkList*)malloc(sizeof(LinkList);P-data=x;P-next=NULL;r-next=P;r=r-next;ch=getchar();return head;/*CreateLinkList*/该算法的时间复杂度为O(n)。本讲稿第四十四页
27、，共一百七十五页单链表建立过程示例线性表（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.元素的查找方法一单链表上元素的查找分按值查找和按序号查找。按值查
28、找的方法是，从第一个结点起判断当前结点的值是否等于给定值，若找到返回该结点地址，否则继续下一个结点；若整个表中未找到返回NULL。算法描述如下：LinkList*LocateLinkList(L,x)LinkList*L;elemtyPe x;LinkList*P;P=L-next;while(P!=NULL)&(P-data!=x)P=P-next;return P;/*返回找到的结点位置或NULL*/*LocateLinkList*/本讲稿第四十七页，共一百七十五页元素的查找方法二按序号查找的方法是，从第一个结点起做i次指针传递返回该结点地址，若找不到i次已到表尾则返回NULL，算法描述如
29、下：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的后面称
30、作后插。后插操作的命令如下，且操作次序不能交换。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-
31、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*/该算法的时间复杂度为
32、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个结点（即前趋结点），然
33、后完成删除并释放被删结点空间的工作。本讲稿第五十三页，共一百七十五页删除单链表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”);elseS=P-next;P-next=S-next;free(S);*deleteLinkList*/该算法的时间复杂度为O(n)。本讲稿第五十四页，共一百七十五页举例将单链表H逆置 所谓逆置是指结点间的关系相反，即前趋变后继而后继变
34、前趋。如图(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*/该算法没有开辟新的存储空
35、间，对链表顺序扫描一遍就完成了逆置，时间开销为O(n)。本讲稿第五十六页，共一百七十五页3.2 链表3.2.1 线性表的链式存储结构链表3.2.2 单链表上的基本运算 3.2.3 循环链表和双向链表3.2.4 线性表应用举例一元多项式相加问题本讲稿第五十七页，共一百七十五页循环链表循环链表（Circular Linked List）是链式存储结构的另一种形式，其特点是表中最后一个结点的指针域指向头结点，使整个链表构成一个环，可以从表中任一结点出发访问遍所有结点（即遍历）。单循环链表的空表和非空表两种状态如下图所示：单循环链表上的基本运算与单链表基本一致，差别仅在于对最后一个结点的循环处理上；单
36、链表是判断指针是否为空（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)时间。改进
37、的方法是不设头指针而设尾指针。这样找到头结点和尾 结 点 都 只 需 要O(1)的 时 间，头 结 点 为(*(*r).next).next而尾结点为r，对于在链表的头尾操作的应用十分方便。带尾指针的循环链表如下图所示：本讲稿第六十页，共一百七十五页双向链表在单循环链表中，虽然可以从任一已知结点出发找到其前趋结点，但需耗时O(n)，原因在于每个结点只有一个指向后继的指针域。如果希望能够快速确定任一结点的前趋，就必须付出空间代价，即增加一个指针域存储其前趋信息，这样每个结点就有两个方向不同的链，称之为双向链表（doublelinkedlist）。如果让每条链都构成一个环，则称为双向循环链表（do
38、ublecircularlinkedlist）。双向链表的使用往往做成双循环链表，和单循环链表类似，也是由头指针标识，也可以增加头结点方便运算。本讲稿第六十一页，共一百七十五页双向链表的结点定义和类型 typedef struct dupnode elemtype data;struct dupnode*prior,*next;dulinklist;dulinklist*H;双向链表是一种对称结构，每个结点都既有指向其前趋的指针，也有指向其后继的指针；每个结点的地址既放在其后继结点的前趋域中，也放在其前趋结点的后继域中。即有 P-next-prior=P=P-prior-next本讲稿第六十二
39、页，共一百七十五页双向链表示意图 本讲稿第六十三页，共一百七十五页双向链表插入运算 与单链表相比双向链表的运算要方便得多。然而由于要涉及多指针域的运算，对于某些运算要注意运算的先后顺序。在*P之前插入*S的步骤为：P-prior-next=s;S-prior=P-prior;S-next=P;P-prior=S;尽管上面的指针操作顺序不是惟一的，但是也不能任意次序，必须保证操作在操作之前完成，否则*P的前趋域的信息就丢掉了，导致不能正确地插入*S。本讲稿第六十四页，共一百七十五页双向链表插入运算的示意图 本讲稿第六十五页，共一百七十五页双向链表的删除运算 删除P所指结点（即*P）的操作步骤为：
40、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
41、,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
42、）三个有序对，显然对高阶稀疏多项式这种方法较好。顺序存储便于访问，但插入删除需大量移动元素，所以对只需求多项式的值无需修改系数和指数值的情况下，采用顺序表结构较好。本讲稿第六十九页，共一百七十五页一元多项式的数据类型定义如果是多项式的运算问题如相加和相乘等，考虑到会产生新的项和系数为零项减少这两种情况，宜考虑采用链式存储结构即单链表实现。其数据类型可如下定义：typedef struct linknode float coef;int exp;struct linknode*next;polynomial;本讲稿第七十页，共一百七十五页多项式的链式存储表示示例假设使用头结点，前述的T(X)=3
43、+5x200+7x1000可表示为如下图所示的结构：本讲稿第七十一页，共一百七十五页多项式相加算法的思路不产生新结点而利用原有结点空间，设两个指针变量p和q分别指向A和B两个多项式单链表的第一个结点，依次比较两指针所指结点的指数项。若指数相等系数相加，和不为零修改*p的系数项并删除*q，和为零删除*p和*q；若指数不等，p-expexp时*p为和多项式中的一项，p-expq-exp时把*q插在*p之前（*q为和多项式中的一项）；所有操作之后要相应移动指针。直到其中一个链空，把另一个链剩下的结点插在*p之后。本讲稿第七十二页，共一百七十五页多项式相加算法的描述void polyadd(A,B)p
44、olynomial*A,*B;polynomial*p,*q,*s,*r;float x;p=A-next;q=B-next;s=A;while(p!=NULL)&(q!=NULL)if(p-exp)(q-exp)r=q-next;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-n
45、ext;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）是操作受限的线性表，限定对元
46、素的插入和删除运算只能在表的一端进行。通常把进行插入和删除操作的这一端称作栈顶（top），另一端称作栈底（bottom）；把栈的插入元素操作称作进栈、入栈或压入；栈的删除元素操作称作退栈、出栈或弹出；当栈中没有元素时称作空栈。本讲稿第七十七页，共一百七十五页栈的概念（续）由栈的定义可知，每一次入栈的元素都在原栈顶元素之上成为新的栈顶元素，每一次出栈的元素总是当前栈顶元素使次栈顶元素成为新的栈顶元素，即最后进栈的元素总是最先出栈。所以栈也称作后进先出（Last In First Out）表，简称LIFO表。如右图所示，元素是以a1,a2,an-1,an的次序进栈，出栈的次序则是an,an-1,a
47、2,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.
48、3.2 顺序栈及运算实现3.3.3 链栈及运算实现3.3.4 栈的应用举例递归的实现本讲稿第八十页，共一百七十五页顺序栈 利用顺序存储结构实现的栈称作顺序栈（sequential stack）。类似于顺序表，栈中的数据元素用一个预设的足够长度的一维数组来存放，栈底位置可以设在数组的任一端点，而栈顶是随着插入和删除运算而变化的，用top指针指示当前栈顶的位置。顺序栈的类型描述如下：#define MAXSIZE 100typedef struct elemtype dataMAXSIZE;int top;seqstack;seqstack*s;本讲稿第八十一页，共一百七十五页顺序栈（续）通常把0
49、下标端设为栈底，这样栈空时栈顶指针top=-1，栈满时栈顶指针top=MAXSIZE-1；入栈时栈顶指针加1（即s-top+），然后数据元素进栈；出栈时在读出栈顶数据元素后栈顶指针减1，即s-top-。在栈满时做入栈操作会产生空间不足的情况，简称上溢（overflow）；而在栈空时做出栈操作会产生无元素可出的情况，简称下溢（underflow）。上溢和下溢两种情况均应该避免，而栈空在应用中通常作为算法（或程序）的控制转移条件。本讲稿第八十二页，共一百七十五页栈顶指针与数据元素之间的关系 本讲稿第八十三页，共一百七十五页顺序栈的基本运算空栈操作置空栈算法 void setnull(seqstac
50、k*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;/*进栈成功