数据结构第2章线性表.ppt

数据结构 与 算法 第二讲：线性表（一） 内容提要 v线性表的定义和基本操作 v线性表的顺序存储结构 v线性表的链式存储结构（单链表） *2 什么叫线性表？ *3 线性表的定义和基本操作 v线性表的定义 q线性表是由n (n 0) 个类型相同的数据元素组成的有限 序列。通常表示成下列形式： L=( a1, a2,., ai-1, ai, ai+1,., an) 其中：L为线性表名称，习惯用大写书写； ai为组成该线性表的数据元素，习惯用小写书写； 线性表中数据元素的个数被称为线性表的长度， 当n=0时，线性表为空，又称为空线性表。 *4 线性表的结构分析 *5 （a1, a2, ai-1，ai, ai1 ，, an） n=0时称为 数据元素 线性起点 ai的直接前趋ai的直接后继 下标，是元素的 序号，表示元素 在表中的位置 n为元素总个 数，即表长 空表 线性终点 线性表特性 1.线性表中元素之间的关系是线性关系： 2.存在唯一的第一个元素； 3.存在唯一的最后一个元素； 4.除第一个元素之外，每个元素均只有一个直接 前驱； 5.除最后一个元素之外，每个元素均只有一个直 接后继。 *6 现实生活中的线性表 【思考】下列哪些关系属于线性关系呢？ q家族的亲戚关系？ q同学之间的友谊？ q恋人之间的爱情？ q班级同学的名册？ q食堂窗口前排队？ q自习教室里占座？ *7 线性表中的元素类型 （）原子类型： 如整数、字符等。 （）结构类型： 如表示一个学生信息的数据元素， 包含学号、姓名、性别等数据项。 *8 线性表举例 1.La=（34，89，765，12，90，-34，22） 数据元素类型为int。 2.Ls=(Hello,World, China, Welcome) 数据元素类型为string。 3.Lb=(book1,book2,.,book100) 数据元素类型为下列所示的结构类型： *9 1.struct bookinfo 2. 3. int No; / 图书编号 4. char *name; / 图书名称 5. char *auther; / 作者名称 6. .; 7. 抽象数据类型线性表定义 ADT List 数据对象：D = ai|aiElemSet, i=1,2,.,n,n0 数据关系：R =| ai,ai+1 D, i=1,2,.,n,n0 基本操作： InitList( 4.ElemType e;/* 声明与La和Lb相同的数据元素e */ 5.La_len = ListLength(La);/* 求线性表的长度 */ 6.Lb_len = ListLength(Lb); 7.for (i = 1; i elem=(ElemType*)malloc(LIST_MAX_LENGTH *sizeof(ElemType); /分配空间 4. if (L-elem=NULL) 5. return ERROR; /若分配空间不成功，返回ERROR 6. L-length=0; /将当前线性表长度置0 7. return OK; /成功返回OK 8. 1. 初始化线性表L 【注意】线性表长度和数组长度的区别。数组长度一般是所分配空间的最大长度，一般是不变的；线 性表长度是当前数据元素的数目，一开始为零，且随着数据的插入删除而变化。 length=0 elemL sizeof(ElemType) LIST_MAX_LENGTH 线性表顺序结构的算法实现（2） 2. 销毁线性表L *21 1.void DestroyList(SQ_LIST *L) 2. 3. if (L-elem) 4. free(L-elem); /释放线性表占据的所有存储空间 5. 1.void ClearList(SQ_LIST *L) 2. 3. L-length=0; /将线性表的长度置为0 4. 3. 清空线性表L length=9 elemL length=9 elemL length=0 线性表顺序结构的算法实现（3） *22 4. 求线性表L的长度 1.int GetLength(SQ_LIST L) 2. 3. return (L.length); 4. 5. 判断线性表L是否为空 1.int IsEmpty(SQ_LIST L) 2. 3. if (L.length=0) 4. return TRUE; 5. else 6. return FALSE; 7. 线性表顺序结构的算法实现（4） *23 6. 获取线性表L中的某个数据元素的内容 1.int GetElem(SQ_LIST L, int i, ElemType *e) 2. 3. if (iL.length) 4. return ERROR; /判断i值是否合理，若不合理，返回ERROR 4. *e=L.elemi-1; /数组中第i-1的单元存储着线性表中第i个数据元素的内容 5. return OK; 6. 【注意】现实中的例子，还记得周星星的电影吗？“9527，出来！” 线性表顺序结构的算法实现（5） *24 7. 在线性表L中检索值为e的数据元素 1.int LocateElem(SQ_LIST L, ElemType e) /算法2.6 2. 3. for (i=0;ilength = LIST_MAX_LENGTH) 4. return ERROR; / 检查是否有剩余空间 5. if (iL-length+1) 6. return ERROR; / 检查i值是否合理 7. for (j=L-length-1; j=i; i-) /将线性表第i个元素 之后的所有元素向后移动 8. 9. L.-elemj=L-elemj-1; 10. 11. L-elemi-1=e; /将新元素的内容放入线性表的第i个位置 12. L-length+; /线性表的长度加一 13. return OK; 14. 线性表顺序结构的算法实现（6续） *26 ABCDEFGH 空闲空间 插队前 大哥，求求你？ ABCDEFGH 空闲空间 插队后 大哥，谢谢你 ！ 加塞的出去 ！ 插入算法的分析 v时间复杂度 q从算法流程上看，查找插入位置、插入元素的时间花费是常数级， 而算法执行时间主要消耗在插入前元素的移动上，而移动元素的个 数与插入位置i有关。 o最好情况: 在表尾插入，不移动元素，T(n)=O(1) o最坏情况: 在表头插入，移动n个元素，T(n)=O(n) o平均复杂度：设pi为在第i个元素之前插入一个元素的概率，且 P1=P2=Pi=Pn=1/(n+1)，则平均移动次数为： 即T(n) = O(n) v空间复杂度 q不需要额外空间，S(n) = O(1) *27 线性表顺序结构的算法实现（7） 9. 将线性表L中第i个数据元素删除 *28 1.Status ListDelete(SQ_LIST *L, int i, ElemType *e) /算法2.5 2. 3. if (IsEmpty(L) 4. return ERROR; /检测线性表是否为空 5. if (iL-length) 6. return ERROR; /检查i值是否合理 7. *e=L-elemi-1; /将欲删除的数据元素内容保留在e所指示的存储 /单元中 8. for (j=i; jlength-1; j+) /将线性表第i+1个元素 之后的所有元素向前移动 9. 10. L-elemj-1=L-elemj; 11. 12. L-length-; 13. return OK; 14. 线性表顺序结构的算法实现（7续） *29 ABCDEFGH 空闲空间 逃离后 ABCDEFGH 空闲空间 逃离前 骗子，还我钱 删除算法的分析 v 时间复杂度 q在进行删除操作时，若假定删除每个元素的可能性均等，则平均移 动元素的个数为： v 分析结论 q顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移 动大约一半的数据元素。当线性表的数据元素量较大，并且经常要 对其做插入或删除操作时，这一点需要值得考虑。 *30 顺序结构总结 v顺序表的优缺点 q优点： o利用存储顺序表示相应的逻辑顺序，不需要额外的存储空 间来表示元素间的逻辑关系； o可以快速地存取表中的任意一个元素； q缺点： o插入和删除元素时要移动大量的元素； o对于长度变化较大的线性表，要一次性地分配足够的存储 空间，但这些空间常常又得不到充分的利用； o容易造成存储空间的“碎片”。 v顺序表的基本运算的复杂度 q插入 oT(n)=O(n) ，S(n)=O(1) q删除 oT(n)=O(n) ，S(n)=O(1) *31 怎么应对线性表顺序存储结构的缺点？ *32 内容提要 v线性表的定义和基本操作 v线性表的顺序存储结构 v线性表的链式存储结构（单链表） *33 线性表的链式存储结构 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以 不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关 系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示 它的直接后继元素存储位置的信息。 假设有一个线性表（a,b,c,d），可用下图所示的形式存储： *34 链式存储结构的特点 v线性表中的数据元素在存储单元中的存放顺序与逻 辑顺序不一定一致； v在对线性表操作时，只能通过头指针进入链表，并 通过每个结点的指针域向后扫描其余结点，这样就 会造成寻找第一个结点和寻找最后一个结点所花费 的时间不等，具有这种特点的存取方式被称为顺序 存取方式。 *35 【注意】和随机存取方式的不同。想想单线联系的地下党组织。 线性表链式存储结构的结点 v 术语 q表示每个数据元素的两部分信息组合在一起被称为结点； q其中表示数据元素内容的部分被称为数据域（data）； q表示直接后继元素存储地址的部分被称为指针或指针域（next）。 v单链表简化的描述形式 * 36 headabcd 其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有 直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（）符号表示。 v带头结点的单链表 headabcd 我们为了更方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，成为头结点。头结点的 数据域可以不存储任何信息，或者存储如线性表的长度等附加信息。头结点的指针域存储指向第一 个结点的指针。 线性表链式存储结构的结点（续） *37 head abcd head abcd 线性表的链式存储结构的类型定义（C语言） *38 1.typedef struct node / 结点类型 2. 3. ElemType data; 4. struct node *next; 5. NODE; 6. typedef struct link_list / 链表类型 7. 8. NODE *head; 9. LINK_LIST; datanext NODE head LINK_LIST 线性表链式存储类型的基本操作 1. 构造一个空的线性表L InitList( /为头结点分配存储单元 4. if (L-head) 5. 6. L-head-next=NULL; 7. return OK; 8. 9. else 10. return ERROR ; 11. NULLnext headLhead 线性表链式结构的算法实现（2） *41 2. 求链表L的长度 1.int ListLength(LINK_LIST L) 2. 3. NODE *p; 4. int len; 5. for(p=L.head, len=0; p-next != NULL; p=p-next, len+); 6. return(len); 7. NULLnext headL data1nextdata2next P len=0 P len=1 P len=2 return len 线性表链式结构的算法实现（3） *42 3. 判链表L空否 1.int IsEmpty(LINK_LIST L) 2. 3. if (L.head-next=NULL) 4. return TRUE; 5. else 6. return FALSE; 7. NULLnext headL return TRUE 线性表链式结构的算法实现（4） *43 4. 通过e返回链表L中第i个数据元素的内容 1.void GetElem(LINK_LIST L,int i,ElemType *e) 2. 3. NODE *p; 4. int j; 5. if (iListLength(L) /检测i值的合理性 6. exit ERROR; 7. for (p=L.head,j=0; j!=i; p=p-next,j+); /找到第i个结点 8. *e=p-data; /将第i个结点的内容赋给e指针所指向的存储单元中 9. NULLnext headL data1nextdata2next P j=0 P j=1 P j=2 【假设】i = 2 *e = p-data 线性表链式结构的算法实现（5） *44 5. 在链表L中检索值为e的数据元素 1.NODE *LocateElem(LINK_LIST L, ElemType e) 2. 3. NODE *p; 4. for (p=L.head-next; p p=p-next); /寻找满足条件的结点 5. return(p); 6. NULLnext headL data1nextenext PP return p 线性表链式结构的算法实现（6） *45 6. 返回链表L中结点e的直接前驱结点 1.NODE *PriorElem(LINK_LIST L, NODE* e) 2. 3. NODE *p; 4. if (L.head-next = e) /检测第一个结点 5. return NULL; 6. for (p=L.head; p-next p=p-next); 7. if (p-next=e) 8. return p; 9. else 10. return NULL; 11. NULL next headL data1nextdata2 next P data3next e P return p P 线性表链式结构的算法实现（7） *46 7. 返回链表L中结点e的直接后继结点 1.NODE *NextElem(LINK_LIST L, NODE* e) 2. 3. NODE *p; 4. for(p=L.head-next; p p=p-next); 5. if (p) 6. p=p-next; 7. return p; 8. NULL next headL data1nextdata2 next P data3next P return p e P 线性表链式结构的算法实现（8） *47 8. 在链表L中第i个数据元素之前插入数据域为e的元素 1.int ListInsert(LINK_LIST *L, int i, ElemType e) 2. 3. NODE *p, *s; 4. int j; 5. if (iListLength(L)+1) 6. return ERROR; 7. s=(NODE*)malloc(sizeof(NODE); /line(7-10) 创建数据域为e的元素 8. if (s=NULL) 9. return ERROR; 10. s-data = e; 11. for (p=L-head, j=0; p j+); /寻找第i-1个结点 12. s-next=p-next; /line(12-13)将s结点插入 13. p-next=s; 14. return OK; 15. 线性表链式结构的算法实现（8续） *48 8. 在链表L中第i个数据元素之前插入数据域为e的元素 1.int ListInsert(LINK_LIST *L, int i, ElemType e) 2. 3. NODE *p, *s; 4. / (0) 检查i是否在合理范围内 5. / (1) 创建数据域为e的元素，此时s指向被创建的新数据元素 6./ (2) 寻找第i-1个结点，此时p指向第i-1个结点 7. s-next=p-next; 8. p-next=s; / (3)将s结点插入 9. return OK; 10. datai-1datai P datas next S next next next next datai-1datainextnextdatasnext PS 线性表链式结构的算法实现（9） *49 9. 将链表L中第i个数据元素删除，并将其内容保存在e中 1.int ListDelete(LINK_LIST *L, int i, ElemType *e) 2. 3. NODE *p, *s; 4. int j; 5. if (iListLength(L) /检查i值的合理性 6. return ERROR; 7. for(p=L-head, j=0; jnext, j+); /寻找第i-1个结点 8. s=p-next; /用s指向将要删除的结点 9. *e=s-data; 10. p-next=s-next; /删除s指针所指向的结点 11. free(s); 12. return OK; 13. 线性表链式结构的算法实现（9续） *50 9. 将链表L中第i个数据元素删除，并将其内容保存在e中 1.int ListDelete(LINK_LIST *L, int i, ElemType *e) 2. 3. NODE *p, *s; 4. /(0) 检查i值的合理性 5. /(1) 寻找第i-1个结点，p指向第i-1个结点 6. s=p-next; /(2) 用s指向将要删除的结点 7. *e=s-data; /(3) 将要删除的内容保存在e中 8. p-next=s-next; /(4) 删除s指针所指向的结点 9. free(s); 10. return OK; 11. datai-1datai+1nextnextdatainext PS next *e = s-data 线性表链式结构的算法实现（10） 10. 销毁链表L *51 1.void DestoryList(LINK_LIST *L) 2. 3. NODE *p; 4. while (L-head) /依次删除链表中的所有结点 5. 6. p=L-head; 7. L-head=L-head-next; 8. free(p); 9. 10. NULLnext headL datanext P head P head 线性表链式结构的算法实现（11） *52 11. 清空链表L 1.void ClearList(LINK_LIST *L) 2. 3. NODE *p; 4. while (L-head-next) 5. 6. p=L-head-next; /p指向链表中头结点后面的第一个结点 7. L-head-next=p-next; /删除p结点 8. free(p); /释放p结点占据的存储空间 9. 10. NULLn