数据结构(上)ppt课件

1、数据结构(上)1第1章 绪论第2章 线性表第3章栈和队列第4章 串第5章数组与广义表2第一章 绪论3学习重点： 数据结构的基本概念； 数据的逻辑结构、存储结构以及两者之 间的关系； 算法及特性； 大O记号的表示。41.1 数据结构的概念 1.2 抽象数据类型（ADT） 1.3 算法描述与分析 5程序设计的实质即为计算机处理问题编制一组“指令”，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略；数据结构即为问题的数学模型。6数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述.非数值计算问题的数学模型正是本门课程要讨论的数据结构。7例如：迷宫、棋盘在计算机内部

2、的表示 交叉路口的红绿灯管理 七桥问题 8概括地说， 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。9一、基本概念和术语二、数据结构三、数据类型和抽象数据类型10 所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合。数据是计算机操作的对象的总称。 是计算机处理的信息的某种特定的符号表示形式。11 是数据（集合）中的一个 “个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位。数据元素例如，学生信息系统中学生信息表中的一个记录12它是数据结构中讨论的最小单位。 又如,描述一个学生的数据元素由多个

3、款项构成，其中每个款项称为一个“数据项”。称之为组合项年 月 日姓 名学 号班 号性别出生日期入学成绩原子项13数据对象 具有相同特性的数据元素的集合。如:整数、实数等。14数据结构指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。 15如，在 2 行 3 列的二维数组中六个元素 a1, a2, a3, a4, a5, a6之间存在着两个关系:“行” 的次序关系:row = ,col = ,“列” 的次序关系:a1a2a3a4a5a616 在含 6 个数据元素a1, a2, a3, a4

4、, a5, a6 的集合上存在如下的次序关系:| i=1, 2, 3, 4, 5可见，不同的“关系”构成不同的“结构”则构成“一维数组” 。17数据结构的形式定义描述为:数据结构是一个二元组 Data_Structures = (D, R)其中: D 是数据元素的有限集， R 是 D上关系的有限集。18从关系或结构分，数据结构可归结为以下四类:线性结构树形结构图状结构集合结构19数据结构包括“逻辑结构” 和“物理结构”两个方面(层次):逻辑结构 是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示;物理结构 是逻辑结构在计算机中的表示和实现，故又称“存储

5、结构” 。20数据的存储结构关系有两种表示方法：顺序存储以 B 相对于 A 的存储位置 表示 B是A的后继 例如:令 B 的存储位置和 A 的存储位置之间相差一个预设常量 C，而 C 是一个隐含值， A B21链式存储以附加信息(指针)表示后继关系以和A绑定在一起的附加信息(指针)表示后继关系，这个指针即为 B的存储地址，由此得到的数据存储结构为链式存储结构。 B A以“由数据元素 A 的存储映象和附加的指针合成的结点”表示数据元素。22存储结构的描述方法随编程环境的不同而不同，对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也

6、不同。 23数据类型（Data Type）是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型（Abstract Data Type，简称ADT）是指一个数学模型以及定义在该模型上的一组操作 24抽象数据类型形式定义为：ADT 抽象数据类型名 数据对象： 数据对象的定义 数据关系： 数据关系的定义 基本操作： 基本操作的定义 25一、什么是算法二、算法技术分析初步三、算法效率的衡量方法和准则四、算法的存储空间需求26 是一个有穷的规则集合，这些规则为解决某一特定任务规定了一个运算序列。 算法描述算法的方法有：自然语言程序设计语言（或类程序设计语言）流程图（包括传统流程图和N-S结构图

7、）伪语言PAD图27一个算法必须满足以下五个重要特性：3可行性1有穷性2确定性5有输出4有输入28有穷性一个算法必须在有穷步之后正常结束，即必须在有限时间内完成而不能形成无穷循环。确定性算法的每一步必须有确切的定义，无二义性。算法的执行对应着的相同的输入仅有唯一的一条路经。 29可行性 算法中的每一条指令必须是切实可行的，即原则上可以通过已经实现的基本运算执行有限次来实现。有输入 一个算法具有零个或多个输入，这些输入取自特定的数据对象集合 。30有输出 一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。 31健壮性 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不

8、是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。32和算法执行时间相关的因素：1问题的规模2书写程序的语言 3编译程序所生成目标代码的质量 4硬件的速度 33 一个特定算法的 “运行工作量” 的大小，只依赖于问题的规模（通常用整数量 n 表示），或者说，它是问题规模的函数。 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n)称 T (n) 为算法的(渐近) 时间复杂度34如何估算 算法的时间复杂度？351.空间复杂度空间复杂度（Space

9、 complexity）是指程序运行从开始到结束所需的存储量。它指的是：当问题的规模以某种单位由1增至n时，解决该问题的算法实现所占用的空间也以某种单位由1增至f(n)。则称该算法的空间代价是f(n) 。362.时间复杂度时间复杂度（Time complexity）是指程序运行从开始到结束所需要的时间。 定义为（大记号）：如果存在两个正常数c和n0，使得对所有的n，nn0，有： f(n) cg(n)则有： f(n) (g(n)称为算法的渐进时间复杂度（Asymptotic Complexity）。37例如： 算法语句 对应的语句频度 for（i=0；i n; i+） n for （j=0；jn

10、; j+） n2 cij=0; n2 for (k=0;k n; k+) n3 cij=cij+aik*bkj; n3 38算法的时间复杂度，即是算法的时间量度,记做： T(n)=O(f(n)例如给出X=X+1 x=x+1 ；时间复杂度为O(1)，称为常量阶； for (i=1; i= n; i+) x=x+1; 时间复杂度为O(n)，称为线性阶； for (i=1; i= n; i+) for (j=1;j= n; j+) x=x+1; 时间复杂度为O(n2 ), 称为平方阶。 for (i=0; in-1; i+) for (j=i+1; jn; j+) if (ai.data last)

11、; /* 线性表的数据个数*/ for(i=1; ilast; i+) printf(n data= ); scanf(%d,&(L-datai-1); /* 输入数据*/ /* Creat_Seqlist end */59 在顺序表指定位置插入元素的过程。2往顺序表中插入一个新数据元素60图2-4 顺序表插入前、后的状态示意 61 线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，插入后使原表长为 n的表: (a1，a2，. ，ai-1，ai，ai+1，. ，an)成为表长为 n+1的表: (a1，a2，.，ai-1，x，ai，ai+1，.，an) 。 i 的取值范围为1=ila

12、st=MAXSIZE) printf(n Error?n);return(-1); /* 表空间已满，不能插入! */ if (i L-last) printf(n Error?);return(-1); /*检查插入位置的正确性*/ 63 else /* 向后移动数据数据 */ for (j=L-last-1; j=i; j-) L-dataj+1=L-dataj; L-datai=x; /* 插入数据 */ L-last +; /* 线性表长度加1 */ return(1);/*插入成功，返回*/ 64插入算法的时间性能分析 顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上

13、插入 x ，从 ai 到 an 都要向下(右)移动一个位置，共需要移动 n-i+1个元素，而 i 的取值范围为 ：1= i= n+1，即有 n+1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：65假设在线性表的任何位置插入元素的概率pi相等（暂不考虑概率不相等情况），则 66元素插入位置的可能值： i= 1, 2, n, n+1相应向后移动元素次数： n-i+1= n, n-1, 1, 0 对n,n-1,1,0求总和，显然为n(n+1)/2。所以，插入时数据元素平均移动次数为：67这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为(n)。68

14、线性表的删除运算是指将表中第 i 个元素从线性表中去掉，删除后使原表长为 n的线性表： (a1，a2，ai-1，ai，ai+1，an) 成为表长为 n-1 的线性表：(a1，a2，ai-1， ai+1，an)。 i 的取值范围为：1=i=n ，如图2-5所示。3删除顺序表中的一个数据元素69图2-5 顺序表里删除元素示意 70 void Delete_Seqlist(Seqlist *L,int i) int j; i-; if (i L-last-1) printf(n Not exist！); else for (j=i+1;jlast-1;j+) L-dataj-1=L-dataj; /

15、* 向前移动数据数据 */ L-last-; /* 线性表长度减1 */ 71本算法注意以下问题： （1）删除第i个元素，i的取值为 1=ilast的值为0，条件（iL-last-1）也包括了对表空的检查。 （3）删除 ai 之后，该数据已不存在，如果需要，先取出 ai ，再做删除。 72删除算法的时间性能分析：与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素 ai+1an 都要向上移动一个位置，共移动了 n-i 个元素，所以平均移动数据元素的次数： 73假设在线性表的任何位置删除元素的概率qi相等（暂不考虑概率不相等情况）：元素删除位置的可能值： i= 1,

16、2, n相应向前移动元素次数： n-i= n-1, n-2, 0 74对n-1,1,0求总和，显然为n(n-1)/2。则删除时数据元素平均移动次数为：这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为(n)。75 查找顺序表中第一个与给定数据相等的元素的算法。 给定数据x，在顺序表L中查找第一个与它相等的数据元素。如果查找成功，则返回该元素在表中的位置；如果查找失败，则返回-1。算法如下:4在顺序表中查找一个数据元素 76int Location_SeqList(SeqList *L, DataType x) int i=0; while(idatai!= x)i+

17、; if (iL-last-1) return -1; else return i; /*返回的是存储位置*/该算法的主要运算是比较。显然比较的次数与x在表中的位置有关，也与表长有关。当 a1=x 时，比较一次成功。当 an=x 时比较 n 次成功。平均比较次数为（n+1）/2，时间性能为O(n)。77 打印顺序表中各结点值的算法。算法描述： 当顺序表L不空时，将各个结点的值打印输出。算法如下:5打印顺序表的各结点值78Print_SeqList(SeqList *L) if (L-last = 0) printf (The sequential list is empty !); else

18、for (i=1; ilast; i+) printf (%d, L-datai-1);79 获取顺序表现有元素个数的算法。 算法描述：由于顺序表当前的元素个数，在其管理信息单元L-last里记录，因此只需将顺序表L的L-last当前值读出即可。算法如下:6求顺序表的长度80Length_ SeqList(SeqList *L) printf (The Length of sequential list is =%d, L-last);81 往顺序表末尾添加新元素的算法。 往顺序表L的末尾添加一个新的数据元素x。算法如下:7往顺序表末尾添加一个新的数据元素82Append_ SeqList(S

19、eqList *L, datatype x) if (L-last = MAXSIZE) printf (The sequential list is full !);/* 顺序表已满，不能再插入 */ else L-dataL-last = x ; /* 能够插入 */ L-last+ ; 83 例2-4 设计一个算法，将顺序表： L= (a1, a2,., ai, ai+1, , an1, an ) 中的元素进行逆置，即把顺序表Sq中的元素排列顺序改换成： L = (an, an1, , ai+1,ai, , a2, a1)应用:84 解：为算法取名Invert_SeqList () In

20、vert_ SeqList(SeqList *L) if (L-last last-1 ;85for (i=0; idatai; /* 把第i个元素暂存于temp */ L-datai = L-dataj; /* 把第j个元素存入表的第i个元素 */ 86L-dataj = temp ; /* 把temp里内容存入表的第j个元素 */ 872.3 线性表的链式存储与实现 采用链式存储结构存放数据时，数据元素间的邻接关系不是直接通过存储结点间的位置关系反映出来，而是由每个存储结点里的指针来指明。因此，链式存储结构不要求邻接的数据元素在物理位置上也是邻接的。 2.3.1 单链表88 链表是由一个个

21、结点构成的，结点定义如下：typedef struct node DataType data; /*数据域*/ struct node *next; /*指针域*/ LNode，*LinkList；89图2-7 单链表中存储结点的示意 90 单链表采用的链式存储结构，优点是不以表的总存储需求进行存储分配，而是以单个数据存储结点的大小（size）来进行动态存储分配，即当有新的数据元素希望进入链表时，就按照存储结点的大小向系统提出存储请求。 91图2-8 单链表示意 92图2-8 带头结点的单链表示意 93 单链表表头指针的作用是十分重要的，因为从它可以找到表的第1个存储结点，然后才能够沿着各结点

22、的指针域找到表中的其他所有结点。 当单链表为空（即长度为0）时，其表头指针Head=NULL。 94 我们假定，如果指针p指向一个单链表的存储结点，那么“p-Data”表示所指结点的数据域，“p-Next”表示所指结点的指针域。 2.3.2 单链表的基本算法描述95插入运算 Insert_LinkList(L,i,x) ，在链表L的第i个元素结点处插入值为x的元素。算法思路：.找到第i-1个结点；若存在继续2，否则结束.申请、填装新结点；.将新结点插入。结束。算法如下：1往单链表中插入一个新结点96int Insert_LinkList( LinkList L, int i, TataType

23、 x) /*在含头结点的单链表L的第i个位置上插入值为x的元素*/ LNode *p,*q; p=L;int k=0; while(p!=NULL)&(knext; k+; /*查找第i-1个结点*/ if (p = =NULL|ki-1) printf(参数i错);return 0; /*第i-1个不存在不能插入*/ 97else q=( LNode*)malloc(sizeof(LNode); q-data=x; /*申请、填装结点*/ q-next=p-next; /*新结点插入在第i-1个结点的后面*/ p-next=q; return 1; 98图2-11 单链表上插入值为x的结点9

24、9 删除单链表L上的第i个数据结点：Del_LinkList(L,i)算法思路： .找到第i-1个结点；若存在继续2，否则结束； .若存在第i个结点则继续3，否则结束； .删除第i个结点，结束。算法如下：2从单链表中删除指定的结点100void Del_LinkList(LinkList L，int i) /*删除含头结点的单链表L上的第i个结点*/ LNode *p,*q,*s; q=L,p=q-next;int k=1; while(p&(knext; k+; /*查找第i个结点*/101 if (k=i) )q-next=p-next; free(p) ; printf(“删除结点成功。

25、”); else printf(“inext; L-next=NULL; while (p) q=p-next; p-next=L-next; L-next=p; p=q; 该算法只是对链表中顺序扫描一边即完成了倒置，所以时间性能为O(n)。 1042.4 循环与双向链表2.4.1 双向链表1双链表的结点 所谓“双向链表”，是在数据的存储结点里，存放两个指针域，一个指向它的直接后继，另一个指向它的直接前驱。 105图2-15 双链表结点及双链表示意 106双向链表结点的定义如下：typedef struct dlnode DataType data; struct dlnode *prior,

26、*next;DLNode,*DLinkList;107 在双链表中值为x的结点后插入值为y的结点。算法思想: 先找值为x的结点ptr,有三种情况: 1 不存在 2 最后一个结点 3 一般情况2在双链表指定位置后插入结点108图2-16 在双链表上的后向插入示意图 109 删除双链表上data域的值为x的结点。算法思想: 先找值为x的结点ptr,有四种情况: 1 不存在 2 最后一个结点 3 一般情况 4 最后一个3将双链表上指定取值的结点删除 110 如果把单链表最后一个结点的next域存储的值由NULL改为指向表的起始结点，使整个表的结点首尾相接，形成一个环，这样的链表被称为“循环链表”。

27、2.4.2 循环链表1循环链表的各种形式111图2-18 表头指针式的循环链表 112用表尾指针取代表头指针的循环链表的形式 图2-19 表尾指针式的循环单链表 113 在用表尾指针代替表头指针后，要寻找表的起始结点和终端结点都变得很方便了。 借助于双链表的概念，也可以把结点组织成循环双链表，如图2-20所示。图2-20（a）所示为一个循环双链表的示意；图2-20（b）所示为一个带表头结点的循环双链表，114这时是表头结点的prior域指向链表的终端结点，终端结点的next域指向表头结点，从而构成循环；图2-20（c）所示为带表头结点的空循环双链表的形式，表头结点的prior和next域全都是

28、指向它自己，也就是在循环双链表空时，满足条件Ck_h-prior = Ck_h-next。 115图2-20 表头指针式的循环双链表116 例2-8 有两个循环单链表，表头指针分别是Ck_h1和Ck_h2。编写一个算法，将链表Ck_h1链接到Ck_h2之后，仍然保存循环链表的形式。 117图2-23 两个循环链表的链接 118解：具体算法如下。Link_Ck(LinkList Ck_h1, LinkList Ck_h2) /*两个链表均非空*/ ptr = Ck_h1; while (ptr-Next != Ck_h1) /* 找到Ck_h1的表尾，ptr指向它 */ qtr = Ck_h2

29、; while (qtr-Next != Ck_h2) /* 找到Ck_h2的表尾，qtr指向它 */ qtr-Next = Ck_h1 ; /* 将Ck_h2链接到Ck_h1之后 */ ptr-Next = Ck_h2-next ; /* 保持循环 */1192.5 单链表的应用符号多项式的相加操作是线性表处理的典型用例。在数学上的一个多项式: 我们称为项多项式， 是多项式的项（0in），其中ai为系数，为变数，i为指数，一般多项式可以使用顺序表来表示其数据结构，也可以使用链表来表示。120设有两个已知多项式:将两个多项式相加得一个新的多项式C：121多项式相加的链表存储结构 多项式采用链表

30、来表示。每个结点对应多项式的一个项，存储该项的系数和指数，其结点结构如下： typedef struct poly int coef ; /* 变量的系数 */ intexp ; /* 变量的指数 */ struct poly *next; /* 指到下一结点的指针 */ Lpoly;122每个多项式由多个结点组成，高指数的项（高次幂）的结点在链表头部，低指数的项（低次幂）的结点在链表的后部。A，B两个多项式的链表结构图如下：123多项式相加的算法实现 为了进行加法运算，设置p,q 两个指针变量分别指向pa,pb两个链表的第一个数据元素结点。然后对p,q两个结点的指数域进行比较。指数相同系数相

31、加，连入C链表；指数不同，将指数较大的结点连入C表。124现设C链表头指针pc指向pa（这样充分利用现有结点，节省资源），设指针变量r也指向pa，当有结点连入C表时pc不动r向前移动。每处理一次，相关指针p,q,r一般需要向前移动。125126 对照后面多项式相加的算法和图2.16可看出两个指数为14的项相加后，得一个系数为11新项连在pc链上。当p,q指针前向后移动之后，将p,q所指两个结点的指数相比，q结点的指数较大，于是将q结点连入pc链。这里p不移动，q,r各向前移动一步，此时链表状态如图2.17所示。127图 2.17 第二次处理 结合图示阅读后面的算法，读者自行分析，即可得相加后的

32、链表。算法如下：128Lpoly *add_poly(Lpoly *pa, Lpoly *pb) p=pa-next; q=pb-next; r=pa; pc=pa; while (p!=NULL) & (q!=NULL) if(p-exp=q-exp) x=p-coef+q-coef; if(x!=0) p-coef=x ; r=p; else r-next=p-next; p=p-next; q=q-next; 129 else if(p-expq-exp) r-next=p; r=p; p p-next; else r-next=q; r=q; q=q-next; /* while en

33、d */ if(p=NULL) r-next=q; else r-next=p; return(pc) /* add_poly end */ 130第3章 栈和队列131 栈和队列是二种特殊的线性表。是操作受限的线性表。一、栈1、栈的概述 栈(Stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。132 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。 也就是说，栈是一种后进先出(

34、Last In First Out)的线性表，简称为LIFO表。 133 初始化栈：INISTACK(&S) 将栈S置为一个空栈(不含任何元素)。 进栈：PUSH(&S,X) 将元素X插入到栈S中，也称为 “入栈”、 “插入”、 “压入”。 出栈： POP(&S) 删除栈S中的栈顶元素，也称为”退栈”、 “删除”、 “弹出”。 取栈顶元素： GETTOP(S) 取栈S中栈顶元素。 判栈空： EMPTY(S) 判断栈S是否为空，若为空，返回值为1，否则返回值为0。2、栈的运算134例1：设栈的输入序列是(1,2,3,4),则 不可能是其出栈序列A.1243 B.2134 C.1432 D.431

35、2 E.3214例2：依次读入数据元素序列(a,b,c,d,e,f,g)进栈，每进一个元素，机器可要求下一个元素进栈或出栈；如此进行，则栈空时弹出的元素构成的序列是以下哪些序列？ A.decfbga B.fegdacb C.efdgbca D.cdbefag 135例3：一个输入序列abcd经过一个栈到达输出序列，并且一旦离开输入序列后就不能再返回到输入序列，则下面 为正确输出序列。A.bcad B.cbda C.dabc D.acbd E.dcba二、顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。并设指针top指向栈顶元素的当前位置。1361、顺序栈存储结构定义： Str

36、uct seqstack elemtype stackmaxsize; int top; 注释：空栈时top=0,进栈一个元素top+1.1372、顺序栈的主要运算 进栈操作 void push(ElemType x) if(top=MAXSIZE-1) printf(“溢出”); exit(1); else top+; elemtop=x; 138出栈ElemType pop( ) ElemType x; if(top!=0) x=elemtop; top-; return x; else printf(“栈为空!”); exit(1);139三、链栈typedef struct Lsnod

37、e ElemType data; struct Lsnode *next; Lsnode *top; 一个链表栈由栈顶指针top唯一确定。 140进栈操作 void Push(Lsnode *top; ElemType x) p=(Lsnode *)malloc(sizeof(Lsnode); p-data=x; p-next=top-next; top-next=p; /*Push*/ 1、链栈的主要运算141出栈操作 ElemType Pop(Lsnode *top) if(top-next!=NULL) p=top-next; top-next=p-next; x=p-data; fre

38、e(p); return x; else printf(Stack null! n); return #; /*Pop*/1421、队列的概述 仅允许在一端进行插入，另一端进行删除的线性表，称为队列(queue)。允许插入的一端称为队尾(rear)，允许删除的一端称为队头（front）。 队列是一种先进先出（First In First Out）的特殊线性表，或称FIFO表。四、队列1432、队列的基本运算初始化队列 INIQUEUE(&Q) 将队列Q设置成一个空队列。入队列 ENQUEUE(&Q,X) 将元素X插入到队尾中，也称“进队” ，“插入”。 出队列 DLQUEUE(&Q) 将队列Q

39、的队头元素删除，也称“退队”、“删除”。取队头元素 GETHEAD(Q) 得到队列Q的队头元素之值。判队空 EMPTY(Q) 判断队列Q是否为空，若为空返回1，否则返回0。1441. 队列的顺序存储数据类型描述 struct seqqueue elemtype queuemaxsize; int front; /队头指针 int rear; /队尾指针 ;五、顺序队列1452. 顺序队列 理论上讲，若尾指针rear指向一维数组最后,而头指针指向一维数组开头，称为队满。 但有可能出现这样情况，尾指针指向一维数组最后，但前面有很多元素已经出队，即空出很多位置，这时要插入元素，仍然会发生溢出。我们将

40、这种溢出称为“假溢出”。146 要克服“假溢出”，方法一：平移法。可以将整个队列中元素向前移动，直到头指针front为-1，或者每次出队时，都将队列中元素前移一个位置。因此，顺序队列的队满判定条件为rear=maxsize。但是，在顺序队列中，这些克服假溢出的方法都会引起大量元素的移动，花费大量的时间，所以在实际应用中很少采用，另一方法：采用循环队列形式。3. 循环队列 为了克服顺序队列中假溢出，通常将一维数组queue0到qmaxsize-1看成是一个首尾相接的圆环，即queue0与queuemaxsize-1相接在一起。将这种形式的顺序队列称为循环队列，见下图。147思考：会产生什么问题？

41、如何解决？148进队列 void enqueue (seqqueue q, elemtype x) if (q.rear+1)%maxsize = = q.front) printf(“overflow!n”); else q.rear=(q.rear+1)%maxsize; q.queueq.rear-1=x; 149出队列void dlqueue(seqqueue q ) if (q.rear= =q.front) printf(“underflow”); else q.front =(q.front+1)%maxsize;1501 .链队列的数据类型描述 struct link /定义单

42、链表数据类型 elemtype data; link *next;struct linkqueue /定义链队列数据类型 link *front,*rear; /定义头指针和尾指针; 六、链队列151152入队列void push(linkqueue &s, elemtype x) link *p; p=malloc(sizeof(link); p-data=x; p-next=s.rear-next; s.rear-next=p; s.rear=p;2 .链队列的运算 153出队列void pop(linkqueue &s) link *p; p=s.front-next; if (p-ne

43、xt= =NULL) s.front-next=NULL;s.rear=s.front; else s.front-next =p-next;free (p);154 从上述出队列算法中可知，若链队列中只有一个元素时，需作特殊处理(用if语句判断)，修改队尾指针。为了避免修改队尾指针，我们可以采用一种改进的出队列算法。其基本思想是：出队列时，修改头指针，删除头结点而非队头结点，这时，将队头结点成为新的头结点，队列中第二个结点成为队头结点。这时，不管队列中有多少个元素，都不需作特殊处理（不需用if语句来判断），这种改进的算法如下： void pop(linkqueue &s) link *p;

44、p=s.front; s.front=p-next; free (p);155八、队列的应用 队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅举出两个方面例子来说明它，其它应用在后面章节中将会遇到。 第一个例子就是CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用CPU各自运行自己的程序，它们分别通过各自终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。156 第二个例子就是主机与外部设备之间速

45、度不匹配的问题。以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。157第4章 串4.1 串的基本概念4.2 串的存储与实现4.3 串的模式匹配158 串是一种特殊的线性表，特殊性在于它的

46、每个数据元素只能是字符，在于串可以作为整体参与所需要的处理。 159 本章主要介绍以下几个方面的内容： 串的基本知识； 串的存储实现及各种处理算法； 串的模式匹配；1604.1.1 串的基础知识 串，就是通常所说的字符串，是一种特殊的线性表，它的数据元素仅限于是字符（英文字母、数字、空格以及其他字符）。可把串定义如下。 161 “串”是由0个或多个字符构成的一个有限序列，用双引号作为其定界符。若有一个串s： s = “c1c2cn1cn（n0） 那么，s被称为是该串的“串名”， c1c2cn1cn就是串s的“值”。162 括在双引号内的字符个数n，称为字符串的“长度”。当n=0时，称其是一个“

47、空串”。 串中每个字符的序号，称为它在字符串的“位置”。字符串中任意多个连续字符所组成的子序列，称作是该串的“子串”，字符串本身称为“主串”。子串第1个字符在主串中的位置，称作是该子串在“主串中的位置”。1634.2.1定长顺序串4. 2 串的存储与实现这种存储方法也称为静态存储。类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。即用数组表示串，实际上是把串作为特殊的表来表示，特殊性在于表中的元素类型为字符型。按照事先定义的大小，为每个串变量分配一个固定长度的存储区，用C可描述为：164/*-定长顺序串 -*/#define MAXSTRLEN 255; /*用户自己定义

48、的最大串长*/Typedef structchar chMAXSTRLEN+1; SString;165采用定长顺序存储方式时，进行串的连接操作和插入等操作时，极有可能出现连接后的字符串或插入后的字符串的长度超过预定义的长度MAXSTRLEN，此时会将多出的部分用“截断”的方法处理。这样，就得不到正确的结果。166这就要求事先将串的最大长度定的大一些，但是又会出现浪费空间的问题。克服这个缺点是使用不限定串长的最大长度的方法，即动态分配串值的存储空间。1674.2.2 堆串串的堆分配存储表示即串的动态分配存储空间。这种存储表示的特点是：仍以一组地址连续的存储单元存放字符序列，但是它们的存储空间是

49、在程序执行过程中动态分配而得。168即每个串的存储首地址是在算法执行过程中是动态分配的。在C语言中，已经有一个称为堆的存储空间，动态分配用malloc()和free()函数来完成。 169堆串的定义typedef struct char *ch; /*串数组*/ int length; /*串长*/HString;HString s1;170s1.ch=(char *)malloc(length); /*动态分配存储空间，让s1.ch指向它*/free(s1.ch); /*串的空间释放*/由于堆分配存储结构的特点，因此在串处理的应用程序中常被选用。1714.2.3 串操作的实现前面已介绍了串的

50、几种存储表示。其中堆串是串处理的软件中常被选用的方法。下面就堆分配存储前提下，对串运算的实现进行介绍。 172 1. 串赋值函数串赋值操作是将一个字符串常量tval赋值给串S.算法如下：173int StrAssign (HString *S,char *tval ) /*将字符串tval的值赋值给串S*/ int len,i=0; if(S-ch!=NULL)free(S-ch); while(tvali!=0)i+; len=i; /* 把串tval的长度赋值给len*/174 if(len) S-ch=(char *)malloc(len); if(S-ch=NULL)return (0

51、); for(i=0;ichi=tvali; /* 把串tval赋值给S*/ else S-ch=NULL;S-length=len;return(1);175 2串插入函数串的插入是指在当前主串的pos位置插入一个子串T。这和线性表的插入明显不同，线性表在指定位置仅插入一个数据元素，而串插入在指定位置插入若干个连续字符。176具体实现方法为，将原串中从插入位置pos开始以及后面的字符逐次向后移动相应位置，具体移动长度是插入子串的长度T.length。将从pos到pos+T. length -1的存储空间腾出来，以便装入子串T。原字符串的长度变为length +s. length。 算法如下：

52、177void StrInsert (HString *S, int pos, HString T) /* 若1posStrLength(S)1，则在串S的第pos个*/* 字符之前插入串T， */if (pos S-length+1) printf(“n 位置错误!”);return; /* 插入位置不合法*/ char S1S-length ; /* S1 作为辅助串空间用于暂存 S-ch*/178 if (T.length) /*T 非空，则为S重新分配空间并插入 T*/p=S-ch; i=0; while (i length)S1i+ = *(p+i); /* 暂存串S*/S-ch =

53、 new charS-length + T.length ; /* 为S重新分配串值存储空间*/for ( i=0, k=0; ichk+ = S1i; /*保留插入位置之前的子串*/ j = 0;179while (jchk+ = T.chj+; /* 插入 T*/ while ( ilength) S-chk+ = S1i+; /* 复制插入位置之后的子串*/ S-length+=T.length; /* 置串 S 的长度*/ /* if */ /* StrInsert*/180 3串的删除函数串的删除，指把当前主串的第pos位置开始的len个字符删除。 实现方法为，将当前串从pos+le

54、n位置到字符串尾部的字符依次向前移动len个位置，原字符串的长度变为length-len。 算法如下：181void StrDelete(HString * S ,int pos,int len) if(posS-length) printf(n 位置错误!); else if(pos+len S-length) S-length =pos-1; /*删除的长度超出主串，截尾*/ 182 else for (int i=pos+len-1;ilength; i+) S-chi-len=S-chi; /*字符逐个向前移动，跳过len个*/ S-length = S-length -len; /*

55、设置删除后的新串长*/ 1834串的清空函数 该函数是将串清为空串，并释放占用的内存空间。算法如下：int StrClear(HString *S ) if(S-ch)free(S-ch);S-ch=NULL;S-length=0; return(1);1845串的复制函数该函数是将一个字符串的值复制到另一个串中。 算法如下：185int StrCopy(HString *S, HString T) if(S-ch)free(S-ch); /* 先清空S*/S-ch=(char *)malloc(T.length); if(S-ch=NULL) return(0);for(int i=0;ic

56、hi=T.chi; /* 把串T赋值给S*/S-length=T.length; return(1);186 6串的比较函数该函数是比较两个字符串S和T，当两个串相等时返回0;ST时返回1。 算法如下：187int StrCompare(HString S, HString T) for(int i=0;iT.length&ilength); if(temp=NULL)return(0);189for(int i=0;ilength;i+)tempi=S-chi; /* 先把串S放入临时串temp中*/free(S-ch);S-ch=(char*)malloc(S-length+T.lengt

57、h); /* 为S分配新的空间*/for(int i=0;ilength;i+)S-chi=tempi;for(int j=0;jchi+j=T.chj;return(1);.190 8求子串函数该函数是将某字符串中一连续的字符序列复制到另一个串中。算法如下：void SubString (HString *Sub, HString S, int pos, int len)if(Sub-ch)free(Sub-ch);191if(posS.length|lenS.length-pos+1) Sub-ch=NULL;Sub.length=0; elseSub-ch=(char*)malloc(l

58、en) if(Sub-ch=NULL)return(0); for(int i=1;ichi=S.chpos-1+i; Sub-length=len; 1924.3 串的模式匹配子串的定位通常称为串的模式匹配。设有两个字符串S和T，设S为主串，也称正文串。设T为子串也称为模式。在主串S中查找与子串T（模式）相匹配（相同）的子串，如果匹配成功，确定模式串T的第一个字符在主串S中出现的位置。 称查找模式T在主串S中的匹配位置的运算为模式匹配。 193算法从主串S的第pos 个字符开始查找一个与模式串T相同的子串，若在串S中找到一个与T相同的子串，则函数返回模式串T的第一个字符在串S中出现的位置；若

59、在主串S中从pos位置开始没有找到一个与模式串T相同的子串，则函数返回-1。1944.3.1 朴素模式匹配算法主要思想：从主串S的第pos个字符起和模式T的第一个字符进行比较，若相等则继续比较S和T的后续字符；否则从主串S的第pos+1个字符起再重新和模式T的第一个字符进行比较。依次类推，直至模式T和主串S的一个子串完全相等，则称匹配成功，否则称匹配失败。 195算法如下： int StrIndex (HString S, int pos ,HString T)if(S.length=0|T.length=0)return (0);int i=pos-1,j=0;while(iS.length

60、&j=T.length)return(i-j+1); /* 存在返回第一次出现的位置*/else return(0) ;196朴素模式匹配算法比较简单，易于理解，但效率不高。主要原因是由于主串S指针i回溯消耗了大量的时间。假设主串长度为n=S.length,子串长度为m=T.length,该算法在最好情况下的时间复杂度为O(n+m)。最坏情况下的时间复杂度将达到O(n*m)。 1974.3.2 模式匹配的KMP算法(略) 198第5章 数组和广义表199 一、数组的定义 如果把一维数组看成是一个定长的线性表，则二维数组可看成：它的每个数据元素也是一个定长线性表。( a1,a2, , ap )