内蒙古大学《算法与数据结构》课件第2章基本数据结构

1 第第2章章 基本数据结构基本数据结构2.1 线性表线性表 2.1.1 ADT线性表线性表 2.1.2 静态线性表静态线性表 2.1.3 动态线性表动态线性表2.2 数组数组 2.2.1 数组的定义数组的定义 2.2.2 数组的存储数组的存储 2.2.3 特殊矩阵特殊矩阵 2.2.4 稀疏矩阵稀疏矩阵2.3 字符串字符串 2.3.1 串的表示与实现串的表示与实现 2.3.2 串的模式匹配算法串的模式匹配算法2 线性表线性表(Linear List) ：v由由n(n 0)个数据元素个数据元素a1,a2,an组成的组成的有限序列。有限序列。v数据元素的个数数据元素的个数n定义为表的长度。当定义为表的长度。当n=0时称为空表时称为空表v常常将非空的线性表常常将非空的线性表(n0)记作：记作： L(a1,a2,ai,an)注意：注意：这里的数据元素这里的数据元素ai(1 i n)只是一个抽象的符号，只是一个抽象的符号， 其具体含义在不同的情况下可以不同。其具体含义在不同的情况下可以不同。 2.1 线性表线性表3l例例1 1、2626个大写英文字母组成的字母表个大写英文字母组成的字母表( ( A A , , B B ， C C , , , Z Z ）l例例2、某个学生宿舍学生姓名、某个学生宿舍学生姓名 （ wan ， li ， zhao ， ye ， hao ， jia ）2.1.1 ADT线性表线性表4 例例3 3、学生信息情况登记表如下：学生信息情况登记表如下：2.1.1 ADT线性表线性表姓姓 名名学学 号号性性 别别年龄年龄民族民族系系专业专业入学时间入学时间.5非空线性表的逻辑特征：非空线性表的逻辑特征：v1)有且仅有一个开始结点有且仅有一个开始结点a1，它没有它没有(直接直接)前趋，而仅有一前趋，而仅有一个个(直接直接)后继后继a2；v2)有且仅有一个终端结点有且仅有一个终端结点an，它没有它没有(直接直接)后继，而仅有一后继，而仅有一个个(直接直接)前趋前趋an-1；v3)其余的内部结点其余的内部结点ai(2 i n-1)都有且仅有一个都有且仅有一个(直接直接)前趋前趋ai-1和一个和一个(直接直接)后继后继ai+1。线性表的逻辑结构是一种典型的线性结构。线性表的逻辑结构是一种典型的线性结构。2.1.1 ADT线性表线性表6抽象数据类型线性表的定义如下：抽象数据类型线性表的定义如下：ADT List Data 数据元素表数据元素表.即由即由n(n 0)个数据元素的一个有限个数据元素的一个有限 序列，其中每个数据元素的数据类型为序列，其中每个数据元素的数据类型为DataType size: 数据元素的个数数据元素的个数 Operation Constructor Process: 创建空表创建空表 Clear Process: 清空线性表清空线性表IsEmpty Process: 判断线性表是否为空判断线性表是否为空Output: 若线性表为空，返回若线性表为空，返回true,否则返回否则返回false 7Length Process: 求线性表中元素个数求线性表中元素个数 Output: 返回线性表中元素个数返回线性表中元素个数GetElem Input: 要取出的元素的位置要取出的元素的位置 Process: 取出指定位置上的元素取出指定位置上的元素 Output: 返回取出的元素值返回取出的元素值Locate Input: 要定位的元素要定位的元素 Process: 为指定元素定位为指定元素定位 Output: 若线性表中有给定元素，返回元素位置，否则若线性表中有给定元素，返回元素位置，否则 返回返回-1抽象数据类型线性表的定义如下：抽象数据类型线性表的定义如下：8Insert Input: 被插入元素值及其位置被插入元素值及其位置 Process: 将给定元素插入指定位置将给定元素插入指定位置Delete Input: 被删除元素的位置被删除元素的位置 Process: 若线性表中有给定元素，则删除它若线性表中有给定元素，则删除它Prior Input: 要求前驱的元素要求前驱的元素 Process: 求给定元素的直接前驱求给定元素的直接前驱Next Input: 要求后继的元素要求后继的元素 Process: 求给定元素的直接后继求给定元素的直接后继 / List 抽象数据类型线性表的定义如下：抽象数据类型线性表的定义如下：9例例2.1 假设利用线性表假设利用线性表LA和和LB分别表示两个集合分别表示两个集合A和和B（线性（线性表中的数据元素即为集合中的成员），现求一个新的集合表中的数据元素即为集合中的成员），现求一个新的集合AB，并用，并用LA表示结果集合。表示结果集合。void Intersection ( List LA，List LB ) int i=0; while ( i LA.size ) x = LA.GetElem(i); /在在LA中取一元素中取一元素 k = LB.Locate (x); /在在LB中搜索它中搜索它 if ( k = -1 ) /在在LA中未找到，则删除它中未找到，则删除它 LA.Delete (i); LA.size -; else i+; / Intersection时间复杂度为时间复杂度为O (LA.size) 。 2.1.1 ADT线性表线性表练习：写一个求练习：写一个求AB的算法。的算法。101、顺序表、顺序表把线性表的元素按逻辑顺序依次存放在一组地址连续的存把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称储单元里。用这种方法存储的线性表简称顺序表顺序表。 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址称作线性表的称作线性表的基地址基地址(a1，a2，ai，an)2.1.2 线性表的顺序存储线性表的顺序存储11一个数据元素所一个数据元素所占存储量占存储量以以“存储位置相邻存储位置相邻”表示有序对表示有序对 即：即：LOC(ai) = LOC(ai-1) + m存储结构与逻辑结构的关系：存储结构与逻辑结构的关系：任一个数据元素的存储位置均取决于第一个任一个数据元素的存储位置均取决于第一个数据元素的存储位置数据元素的存储位置 LOC(ai) = LOC(a1) + (i -1)m 基地址基地址2.1.2 线性表的顺序存储线性表的顺序存储12const int MaxListSize=100;class SeqList DataType dataMaxListSize; / 顺序表顺序表 int size; /元素的个数元素的个数 public: SegList( )size = 0; /构造一个空线性表构造一个空线性表 void Clear( ); /清空表清空表 bool IsEmpty( ); /判断如果为空表，返回判断如果为空表，返回true，否则返回，否则返回false DataType GetElem(int k)return datak; /返回第返回第k个元素个元素 int Locate(DataType e); /返回第一个与元素返回第一个与元素e匹配的元素位序匹配的元素位序 DataType Prior ( DataType e); /返回元素返回元素e 的前驱的前驱 DataType Next (DataType e); /返回元素返回元素e 的后继的后继 void Insert (DataType e, int i ); /在表中第在表中第 i 个位置插入新元素个位置插入新元素e DataType Delete ( int i ); /删除第删除第i个元素，并返回其值个元素，并返回其值；/SeqList2.1.2 线性表的顺序存储线性表的顺序存储13顺序查找示意图顺序查找示意图顺序查找示意图顺序查找示意图查找成功查找成功查找不成功查找不成功14算法算法2.4 定位算法如下：定位算法如下：int Locate (DataType e) int i = 0; while ( i =size ) return -1;/没有找到没有找到 else return i; /找到此元素，返回其下标找到此元素，返回其下标/ Locate 1516iniicpACN1022)(1*n1 )2(111)(1=101nnnnninACNni 17顺序插入示意图顺序插入示意图18 序序 号号数据元素数据元素 序序 号号数据元素数据元素 序序 号号数据元素数据元素 012 012 012 113 113 113 221 221 221插入插入25 i=4 324 324 324 428 4 425 530 528 528 642 630 630 777 742 742 8 877 877图图2.2 线性表插入前后的情况（插入位置为线性表插入前后的情况（插入位置为i=4）19插入算法如下：插入算法如下：void Insert (DataType e, int i ) if ( i size | size = = MaxListSize ) / i不合法或顺序表已满不合法或顺序表已满; exit; else size+; for (j=size-1; ji; j- ) dataj = dataj-1; datai = e; /插入成功插入成功 / Insert20221)(1)(1 0)1(11)(11=0nnnnnninnAMNni21 序序 号号 数据元素数据元素 序号序号数据元素数据元素 012 012 113 113 221 221删除第删除第3个元素个元素 324 328 428 430 530 542 642 677 777 722DataType Delete ( int i ) if (i= size) return nulldata; /被删除的元素下标错被删除的元素下标错 else e=datai; for ( int j=i; jnext=NULL); /判断是否为空链表判断是否为空链表30void Insert( DataType x, int i ); /在第在第i个结点之前插入元素值为个结点之前插入元素值为x的结点的结点Datatype Delete ( int i ); /删除第删除第i个结点，并返回其元素值个结点，并返回其元素值void Clear( ); /清空链表清空链表DataType Prior ( DataType e); /返回返回e 的前驱结点元素的前驱结点元素DataType Next (DataType e); /返回返回e 的后继结点元素的后继结点元素; / nextList31（1）取元素）取元素DataType LinkList:GetElem(int i) if( head-next=NULL) /空链表，返回空值空链表，返回空值 return nulldata; else p=head; k=0; while(p&knext;k+; if(!p | k=0) return nulldata; /i值不合法值不合法 else return p-data; / GetElem32 插入操作是将值为插入操作是将值为x x的新结点插入到表的第的新结点插入到表的第i i个个结点的位置上，即插入到结点的位置上，即插入到ai-1与与ai之间。之间。 插入过程：插入过程：1 1）定位；）定位；2 2）插入。）插入。pai-1headaixa1newnode newnodenext = pnext; pnext = newnode;Node *newnode , *p;33void LinkList: Insert ( DataType x, int i ) /在第在第i个结点前插入元素值为个结点前插入元素值为x的结点的结点 Node* p = head; int k = 0; if(isize) exit; / 插入位置错误插入位置错误 while ( p &