* 数据结构数据结构计算机系计算机系授课人：陈强（副教授）授课人：陈强（副教授） * 第第2 2章章 线性表线性表第第3 3章章 栈和队列栈和队列第第4 4章章 串、数组和广串、数组和广义表义表 线性结构线性结构若若结结构构是是非非空空有有限限集集，则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，并并且且所所有有结结点点都都最最多多只只有有一一个个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a a1 1 , a, a2 2 , , , a, an n） 线性结构的定义：线性结构的定义：线性结构的定义：线性结构的定义：（逻辑、存储（逻辑、存储和运算）和运算） * 线性结构的特点：线性结构的特点： 只有一个首结点和尾结点；只有一个首结点和尾结点； 除除首首尾尾结结点点外外，其其他他结结点点只只有有一一个个直直接接前前驱驱和和一一个直接后继。个直接后继。线性结构表达式：（线性结构表达式：（a a1 1 , a, a2 2 , , , a, an n） 线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最典型、最常用的是线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一 的的 * 第第2 2章章线性表线性表1. 了解线性结构的特点了解线性结构的特点2.2.掌握顺序表的定义、查找、插入和删除掌握顺序表的定义、查找、插入和删除 教学目标教学目标 * 第第2 2章章线性表线性表重点：重点：1.1.顺序表的存储结构顺序表的存储结构2.2.顺序表的基本操作，如顺序表的查找、插顺序表的基本操作，如顺序表的查找、插入、删除入、删除难点：难点：无无 重点与难点重点与难点 * 2.1 线性表的类型定义线性表的类型定义2.2 线性表的顺序表示和实现线性表的顺序表示和实现教学内容教学内容 * （a1, a2, ai-1，ai, ai1 ，, an）线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0n=0时称为时称为数据元素数据元素线性起点线性起点a ai i的直接前趋的直接前趋a ai i的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点2.1 2.1 线性表的类型定义线性表的类型定义 * 例例例例1 1 分析分析分析分析26 26 个英文字母组成的英文表个英文字母组成的英文表个英文字母组成的英文表个英文字母组成的英文表 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级041810205041810205于春梅于春梅女女 18 180404级计算机级计算机1 1班班041810260041810260何仕鹏何仕鹏男男 20 200404级计算机级计算机2 2班班041810284041810284王王 爽爽女女 19 190404级计算机级计算机3 3班班041810360041810360王亚武王亚武男男 18 180404级计算机级计算机4 4班班： ：例例例例2 2 分析学生情况登记表分析学生情况登记表分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母; 元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性 * 线性表的基本操作线性表的基本操作1. 1. 初始化线性表初始化线性表L InitList(L) L InitList(L) 2. 2. 销毁线性表销毁线性表L DestoryList(L) L DestoryList(L) 3. 3. 清空线性表清空线性表L ClearList(L) L ClearList(L) 4. 4. 求线性表求线性表L L的长度的长度 ListLength(L)ListLength(L)5. 5. 判断线性表判断线性表L L是否为空是否为空 IsEmpty(L) IsEmpty(L) 6. 6. 获取线性表获取线性表L L中的某个数据元素内容中的某个数据元素内容 GetElem(L,i,e) GetElem(L,i,e) 7. 7. 检索值为检索值为e e的数据元素的数据元素 LocateELem(L,e)LocateELem(L,e) 8. 8. 在线性表在线性表L L中插入一个数据元素中插入一个数据元素 ListInsert(L,i,e)ListInsert(L,i,e)9. 9. 删除线性表删除线性表L L中第中第i i个数据元素个数据元素 ListDelete(L,i,e)ListDelete(L,i,e)抽象数据类型的定义为抽象数据类型的定义为抽象数据类型的定义为抽象数据类型的定义为 * 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻顺序存储方法：顺序存储方法：用用一组地址连续一组地址连续的存储单元依次存储的存储单元依次存储线性表的元素，可通过线性表的元素，可通过数组数组VnVn来实现。来实现。顺序存储定义：顺序存储定义：把逻辑上相邻的数据元素存储在物理把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。上相邻的存储单元中的存储结构。 * 元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储 * #define MAXSIZE 100 /#define MAXSIZE 100 /最大长度最大长度typedef struct typedef struct ElemType *elem; / ElemType *elem; /指向数据元素的基地址指向数据元素的基地址 int length; /int length; /线性表的当前长度线性表的当前长度 SqListSqList；顺序表的类型定义顺序表的类型定义数据结构基本运算操作有：数据结构基本运算操作有：查找、插入、删除查找、插入、删除 * 线性表的基本操作线性表的基本操作1. 1. 初始化线性表初始化线性表L InitList(L) L InitList(L) 2. 2. 销毁线性表销毁线性表L DestoryList(L) L DestoryList(L) 3. 3. 清空线性表清空线性表L ClearList(L) L ClearList(L) 4. 4. 求线性表求线性表L L的长度的长度 ListLength(L)ListLength(L)5. 5. 判断线性表判断线性表L L是否为空是否为空 IsEmpty(L) IsEmpty(L) 6. 6. 获取线性表获取线性表L L中的某个数据元素内容中的某个数据元素内容 GetElem(L,i,e) GetElem(L,i,e) 7. 7. 检索值为检索值为e e的数据元素的数据元素 LocateELem(L,e)LocateELem(L,e) 8. 8. 在线性表在线性表L L中插入一个数据元素中插入一个数据元素 ListInsert(L,i,e)ListInsert(L,i,e)9. 9. 删除线性表删除线性表L L中第中第i i个数据元素个数据元素 ListDelete(L,i,e)ListDelete(L,i,e)抽象数据类型的定义为抽象数据类型的定义为抽象数据类型的定义为抽象数据类型的定义为 * 典型操作的算法实现典型操作的算法实现1.1.初始化线性表初始化线性表L L （参数用引用）（参数用引用）Status InitList_Sq(SqList &L) /构造一个空的顺序表构造一个空的顺序表L L.elem=new ElemTypeMAXSIZE; /为顺序表分配空间为顺序表分配空间 if(!L.elem) exit(OVERFLOW); /存储分配失败存储分配失败 L.length=0; /空表长度空表长度为为0 return OK; * 1.1.初始化线性表初始化线性表L L （参数用指针）（参数用指针）Status InitList_Sq(SqList *L) /构造一个空的顺序表构造一个空的顺序表L L- elem=new ElemTypeMAXSIZE; /为顺序表分配空间为顺序表分配空间 if(! L- elem) exit(OVERFLOW); /存储分配失败存储分配失败 L- length=0; /空表长度为空表长度为0 return OK; * 2. 2. 销毁线性表销毁线性表L Lvoid DestroyList(SqList &L)void DestroyList(SqList &L) if (L.elem) deleteL.elem; / if (L.elem) deleteL.elem; /释放存储空间释放存储空间 3. 3. 清空线性表清空线性表L Lvoid ClearList(SqList &L) L.length=0; /将线性表的长度置为将线性表的长度置为0 * 4.4. 求线性表求线性表L L的长度的长度int GetLength(SqList L) return (L.length); 5.5.判断线性表判断线性表L L是否为空是否为空int IsEmpty(SqList L) if (L.length=0) return 1; else return 0; * 6. 6. 获取线性表获取线性表L L中的某个数据元素的内容中的某个数据元素的内容/根据指定位置，获取相应位置数据元素的内容根据指定位置，获取相应位置数据元素的内容int GetElem(SqList L,int int GetElem(SqList L,int i,ElemType &ei,ElemType &e) ) if (iL.length) return ERROR; if (iL.length) return ERROR; / /判断判断i i值是否合理，若不合理，返回值是否合理，若不合理，返回ERRORERROR e=L.elemi-1;e=L.elemi-1; / /第第i-1i-1的单元存储着第的单元存储着第i i个数据个数据 return OK;return OK; * 查找查找（根据指定数据查找，返回数据所在的位置）（根据指定数据查找，返回数据所在的位置） 顺序查找图示顺序查找图示25 34 57 16 48 09 0 1 2 3 4 5 data查找查找 16 i25 34 57 16 48 09 i25 34 57 16 48 09 i25 34 57 16 48 09 i查找成功查找成功 * 25 34 57 16 48 0 1 2 3 4data查找 50i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i查找失败查找失败 * 查找算法时间效率分析查找算法时间效率分析 ？7. 7. 在线性表在线性表L L中查找值为中查找值为e e的数据元素的数据元素int LocateELem(SqList L,ElemType e) for (i=0;i L.length;i+) if (L.elemi=e) return i+1; return 0; * 查找成功查找成功的平均比较次数的平均比较次数(p(pi i为各项的查找概率为各项的查找概率为各项的查找概率为各项的查找概率) ) 若查找概率相等，则若查找概率相等，则查找不成功查找不成功 数据比较数据比较 n 次次查找算法时间效率分析查找算法时间效率分析 * 2512478936141234567892512479989361499插入插入251247893614251247893614251247893614插第插第 4 4 个结点之前，移动个结点之前，移动 6 64+14+1 次次插在第插在第 i i 个结点之前，移动个结点之前，移动 n-i+1n-i+1 次次插入插入（插在第（插在第 i i 个结点之前）个结点之前） * （1 1）判断）判断插入位置插入位置i i 是否合法是否合法。（2 2）判断顺序表的）判断顺序表的存储空间是否已满存储空间是否已满。 （3 3）将第）将第n n至第至第i i 位的元素依次位的元素依次向后移动一个位置向后移动一个位置，空，空出第出第i i个位置。个位置。（4 4）将要插入的新元素）将要插入的新元素e e放入第放入第i i个位置个位置。（5 5）表长加表长加1 1，插入成功返回，插入成功返回OKOK。【算法思想算法思想】 * 8. 8. 在线性表在线性表L L中第中第i i个数据元素之前插入数据元素个数据元素之前插入数据元素e e Status ListInsert_Sq(SqList &L,int i ,ElemType e) if(iL.length+1) return ERROR; /i值不合法值不合法 if(L.length=MAXSIZE) return ERROR; /当前存储空间已满当前存储空间已满 for(j=L.length-1;j=i-1;j-) L.elemj+1=L.elemj; /插入位置及之后的元素后移插入位置及之后的元素后移 L.elemi-1=e; /将新元素将新元素e放入第放入第i个位置个位置 +L.length; /表长增表长增1 return OK;【算法描述算法描述】 * 若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部后移（特别慢）；若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共若要考虑在各种位置插入（共n+1n+1种可能）的平均移动次种可能）的平均移动次数，该如何计算？数，该如何计算？算法时间主要耗费在移动元素的操作上算法时间主要耗费在移动元素的操作上【算法分析算法分析】 * 251247893614123456789251247361425124736142512473614删除删除删除删除（删除第（删除第 i i 个结点）个结点） 删除第删除第 4 4 个结点，移动个结点，移动 6 64 4 次次删除第删除第 i i 个结点，移动个结点，移动 n-in-i 次次 * （1 1）判断）判断删除位置删除位置i i 是否合法是否合法（合法值为（合法值为1in1in）。）。（2 2）将欲删除的元素保留在）将欲删除的元素保留在e e中。中。 （3 3）将第）将第i+1i+1至第至第n n 位的元素依次位的元素依次向前移动一个位置向前移动一个位置。（4 4）表长减表长减1 1，删除成功返回，删除成功返回OKOK。【算法思想算法思想】 * 9. 9. 将线性表将线性表L L中第中第i i个数据元素删除个数据元素删除Status ListDelete_Sq(SqList &L,int i,ElemType &e) if(iL.length) return ERROR; /i值不合法值不合法 e=L.elemi-1; /将欲删除的元素保留在将欲删除的元素保留在e中中 for (j=i;j=L.length-1;j+) L.elemj-1=L.elemj; /被删除元素之后的元素前移被删除元素之后的元素前移 -L.length; /表长减表长减1 return OK;【算法描述算法描述】 * 若删除尾结点，则根本无需移动（特别快）；若删除尾结点，则根本无需移动（特别快）；若删除首结点，则表中若删除首结点，则表中n-1n-1个元素全部前移（特别慢）；个元素全部前移（特别慢）；若要考虑在各种位置删除（共若要考虑在各种位置删除（共n n种可能）的平均移动次数，种可能）的平均移动次数，该如何计算？该如何计算？算法时间主要耗费在移动元素的操作上算法时间主要耗费在移动元素的操作上【算法分析算法分析】 * 显然，顺序表的显然，顺序表的空间空间复杂度复杂度S(n)=S(n)=O(1)O(1)（没有占用辅助空间）（没有占用辅助空间）查找、插入、删除算法的平均查找、插入、删除算法的平均时间时间复杂度为复杂度为O(n)O(n) * （1 1）利用数据元素的存储位置表示线性表中相邻数）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的据元素之间的前后关系，即线性表的逻辑结构与逻辑结构与存储结构一致存储结构一致顺序表（顺序存储结构）的特点顺序表（顺序存储结构）的特点这种存取元素的方法被称为这种存取元素的方法被称为随机存取法随机存取法（2 2）在访问线性表时，可以快速地计算出任何一个）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，数据元素的存储地址。因此可以粗略地认为，访访问每个元素所花时间相等问每个元素所花时间相等 * 顺序表的优缺点顺序表的优缺点 缺点：缺点：在插入、删除某一元素时，需要移动大量元素在插入、删除某一元素时，需要移动大量元素浪费存储空间浪费存储空间属于静态存储形式，数据元素的个数不能自由扩属于静态存储形式，数据元素的个数不能自由扩充充链表链表为克服这一缺点为克服这一缺点优优点：点：存储密度大存储密度大（结点本身所占存储量（结点本身所占存储量/结点结构所占存储量）结点结构所占存储量）可以可以随机存取随机存取表中任一元素表中任一元素小结小结线性表的顺序表示又称为顺序存储结构，顺序线性表的顺序表示又称为顺序存储结构，顺序存储定义：把逻辑上相邻的数据元素存储在物存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。顺序表的优缺点顺序表的优缺点优点：存储密度大（结点本身所占存储量优点：存储密度大（结点本身所占存储量/结点结构结点结构所占存储量）；可以随机存取表中任一元素所占存储量）；可以随机存取表中任一元素 缺点：在插入、删除某一元素时，需要移动大量元素；缺点：在插入、删除某一元素时，需要移动大量元素；浪费存储空间；属于静态存储形式，数据元素的个数浪费存储空间；属于静态存储形式，数据元素的个数不能自由扩充。不能自由扩充。 *