数据结构课件Ch02_线性表-2014

《数据结构课件Ch02_线性表-2014》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法第二章线性表2—1例.按要求编写算法完成下列问题：1.假设红、白、蓝每种颜色的花盆至少有一盆，亦即n>=3，杂乱的排在一起，编写一个高效算法使花盆按红、白、蓝的顺序排序。假设每组输入为：一个整数N，表示有N个花盆。然后N个整数，每个整数为1（若为红花盆）、2（若为白花盆）或3（若为蓝花盆），每个整数用空格分开。输入N=0时程序结束。哈尔滨工业大学计算机科学与技术学院数据结构与算法第二章线性表2—2#include#includevoidmain(){c

2、harflower[100],*r,*y,*w,temp;intcount;cin>>flower;count=strlen(flower);r=flower;y=w=&flower[count-1];while(r-y<0){switch(*y){case‘r’:{temp=*r;*r=*y;*y=temp;r++;break;}case‘y’:{y--;break;}case‘w’:{temp=*y;*y=*w;*w=temp;y--;w--;break;}}}cout<

3、算机科学与技术学院数据结构与算法第二章线性表2—3第2章线性表（LinerList）2.1线性表的抽象数据型2.2线性表的实现2.3栈（Stack）2.4队列（Queue）2.5串（String）2.6数组（Array）2.7广义表（GeneralizedList）哈尔滨工业大学计算机科学与技术学院数据结构与算法第二章线性表2—4知识点：线性表的逻辑结构和各种存储表示方法定义在逻辑结构上的各种基本运算（操作）在各种存储结构上如何实现这些基本运算各种基本运算的时间复杂性特殊线性表哈尔滨工业大学计算机科

4、学与技术学院数据结构与算法第二章线性表2—5重点：熟练掌握顺序表和单链表上实现的各种算法及相关的时间复杂性分析难点：使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题哈尔滨工业大学计算机科学与技术学院数据结构与算法第二章线性表2—62.1线性表的抽象数据型[定义]线性表是由n(n≥0)个相同类型的元素组成的有序集合。记为：(a1,a2,a3,……ai-1,ai,ai+1,……an)其中：①n为线性表中元素个数，称为线性表的长度；当n=0时，为空表，记为（）。②ai为线性表中的元素，类型定义为el

5、ementtype③a1为表中第1个元素，无前驱元素；an为表中最后一个元素，无后继元素；对于…ai-1,ai,ai+1…(1

6、ai∈Elementset,i=1,2,…,n,n≥0}R={H}H={

7、ai-1,ai∈D,i=2,…,n}哈尔滨工业大学计算机科学与技术学院数据

8、结构与算法第二章线性表2—8操作：设L的型为LIST线性表实例，x的型为elementtype的元素实例，p为位置变量。所有操作描述为：①Insert(x,p,L)②Locate(x,L)③Retrive(p,L)④Delete(p,L)⑤Previous(p,L),Next(p,L)⑥Makenull(L)⑦First(L)⑧End(L)哈尔滨工业大学计算机科学与技术学院数据结构与算法第二章线性表2—9例：设计函数Deleval（LIST&L,elementtyped)，其功能为删除L中所有值为d的元素。v

9、oidDeleval(LIST&L,elementtyped){positionp;p=First(L);while(p!=End(L)){if(same(Retrieve(p,L),d))Delete(p,L);elsep=Next(p,L);}}哈尔滨工业大学计算机科学与技术学院数据结构与算法第二章线性表2—102.2线性表的实现问题：确定数据结构（存储结构）实现型LIST，并在此基础上实现各个基本操作。存储结构的三种方式：①连续的存储空间（数组）→静态存储②非连续存储空间——指针（链表）→动态存储③游标

10、（连续存储空间+动态管理思想）→静态链表哈尔滨工业大学计算机科学与技术学院数据结构与算法第二章线性表2—11顺序表是指用一组地址连续的存储单元依次存储线性表的数据元素。特点元素之间的逻辑关系（相继/相邻关系）用物理上的相邻关系来表示（用物理上的连续性刻画逻辑上的相继性）；是一种随机存储结构，也就是可以随机存取表中的任意元素，其存储位置可由一个简单直观的公式来表示。由于高级语言中数组类型具有这种特