第2章、基本线性表.ppt

1、第2章、基本线性表,2020/8/4,2,引 言 线性表是一种线性数据结构，其用途非常广泛，可用于信息检索、存储管理、模拟技术和通信等领域。,2020/8/4,3,2.1线性表的基本概念,线性表是最常用且最简单的一种数据结构。 线性表是具有相同属性数据元素的一个有限序列。通常表示成下列形式： L=( a1, a2,.,ai-1,ai,ai+1,.,an) 在线性表L中， a1为开始结点， an为终端结点。结点ai-1是结点ai的前驱结点，结点ai+1是结点ai的后继结点。 n（n0）表示线性表的长度 当n=0时，表示线性表是一个空表。,a1,a2,ai-1,ai,ai+1,an,2020/8/

2、4,4,线性表中数据元素的含义广泛，在不同的具体情况下，可以有不同的含义。 英文字母表 （A，B，C，Z） 某公司2007年上半年每月产值表(单位：万元) （400，320，450，500，480，600） 学生信息表,体现在 顺序关系上,记录排列为顺序关系,2020/8/4,5,线性表的特点 开始结点只有后继结点而没有前驱结点 终端结点只有前驱结点而没有后继结点 除了开始结点和后继结点以外，其余结点都有且只有一个前驱结点和一个后继结点,线性结构的基本特性为一对一的关系,2020/8/4,6,2.2 线性表的相关操作,线性表的基本操作 初始化线性表 求线性表的长度 取线性表L中的第i个元素 修

3、改线性表中的第个元素 删除线性表中的第个元素 在线性表中第个元素之后（前）插入一个新元素,2020/8/4,7,2.3 线性表的顺序存储结构及操作实现,线性表的存储方式有顺序存储和链式存储。 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素。 逻辑关系相邻，物理位置相邻 LOC(ai)=LOC(ai-1)+C LOC(ai)=LOC(a1)+(i-1)*C,一个元素所占的存储量,基地址,2020/8/4,8,顺序存储结构是一种随机存取结构。 在高级语言环境中，常用一维数组来存储线性表。,2020/8/4,9,顺序表的基本操作 初始化 为更好体现信息隐蔽原则和数据抽象原则，把

4、顺序表封装起来。(使用类模板) 模板分为类模板和函数模板 类模板就是建立一个通用类，其数据成员的类型、成员函数的返回类型和参数类型都不具体指定，用一个虚拟类型来代表。当使用类模板建立对象时，系统会根据实参的类型来取代类模板中的虚拟类型从而实现不同类的功能。,2020/8/4,10,类模板的一般说明形式是 templateclass className /类声明体 ; 建立类模板后，可用下列方式创建类模板的实例 className object; 类模板是模板的定义，不是一个实实在在的类，定义中用到通用类型参数。 模板类是实实在在的类定义，是类模板的实例化。类定义中参数被实际类型所代替。,202

5、0/8/4,11,顺序表类,/文件名sq_LList.h #include using namespace std; template /模板声明，数据元素虚拟类型为T class sq_LList /顺序表类 private: /数据成员 int mm; /存储空间容量 int nn; /顺序表长度 T *v; /顺序表存储空间首地址 public: /成员函数 sq_LList() mm=0; nn=0; return; sq_LList(int); /建立空顺序表，申请存储空间 void prt_sq_LList(); /顺序输出顺序表中的元素与顺序表长度 int flag_sq_LLi

6、st(); /检测顺序表的状态 void ins_sq_LList(int, T); /在表的指定元素前插入新元素 void del_sq_LList(int); /在表中删除指定位置的元素 ;,2020/8/4,12,插入,2020/8/4,13,假设线性表的存储空间为m个单元，线性表的长度为n（nn时，认为在最后一个元素之后插入； 当i1时，认为在第1个元素之前插入； 将第i个元素至尾元素逐一向后移动一个位置。 将新元素插入到第i个的位置上，并将顺序表长度增加1。,2020/8/4,14,/在表的指定元素前插入新元素 template void sq_LList:ins_sq_LList(

7、int i, T b) int k; if (nn=mm) /存储空间已满，上溢错误 cout nn) i=nn+1; /默认为在最后一个元素之后插入 if (i=i; k-) vk=vk-1; /从最后一个元素直到第i个元素均后移一个位置 vi-1=b; /插入新元素 nn=nn+1; /顺序表长度加1 return; ,2020/8/4,15,删除,2020/8/4,16,假设线性表的存储空间为m个单元，线性表的长度为n（nn或i1时，表示表中没有这个元素。 将表中第i+1个元素至尾元素逐一向前移动一个位置，并将顺序表长度减少1。,2020/8/4,17,/在顺序表中删除指定位置的元素 t

8、emplate void sq_LList:del_sq_LList(int i) int k; if (nn=0) /顺序表为空，下溢错误 cout nn) /顺序表中没有这个元素 cout Not this element in the list! endl; return; for (k=i; knn; k+) vk-1=vk;/从第i+1个元素直到最后一个元素均前移一个位置 nn=nn-1; /顺序表长度减1 return; ,2020/8/4,18,在实际应用中，应当在顺序表中插入新元素时，先调用检测函数flag_sq_LList()检测一下顺序表是否处于满的状态，如果顺序表非满，才

9、调用插入函数ins_sq_LList()进行插入；同样道理在删除输出元素时检测顺序表是否为空，非空才调用删除函数del_sq_LList()进行删除。,2020/8/4,19,/检测顺序表的状态（满、空或正常） template int sq_LList:flag_sq_LList() if (nn=mn) return(-1); /存储空间已满，返回-1 if (nn=0) return(0); /顺序表为空，返回0 return(1); /正常返回1 ,2020/8/4,20,/建立空顺序表，申请存储空间（使用函数模板） template sq_LList:sq_LList(int m)

10、mm=m; /存储空间容量 v=new Tmm; /动态申请存储空间 nn=0; /顺序表长度为0，即建立空顺序表 return; ,2020/8/4,21,/顺序输出顺序表中的元素与顺序表长度 template void sq_LList:prt_sq_LList() int i; cout nn= nn endl; for (i=0; inn; i+) cout vi endl; return; ,2020/8/4,22,时间复杂度分析 插入和删除这两种操作算法的执行时间主要用在元素的移动操作上，而移动元素的次数取决于插入或删除元素的位置。 假设Pi是在第i个元素之前插入一个元素的概率,

11、则在长度为n的线性表中插入一个元素时所需移动元素次数的平均次数为,2020/8/4,23,假设i是删除第个元素的概率, 则在长度为的线性表中删除一个元素时所需移动元素次数的平均次数为 假定在线性表的任何位置上插入和删除元素都是等概率的，即,2020/8/4,24,则 可见, 在顺序表中插入或删除一个元素时, 平均要移动表中大约一半的数据元素。若表长为n, 前两个算法的时间复杂度都为O(n)。,2020/8/4,25,练习 建立容量为100的空顺序表，然后输出该空顺序表，在该顺序表中依次在第0个元素前插入1.5，在第1个元素前插入2.5以及在第4个元素前插入3.5，再输出该顺序表。依次删除该顺序

12、表中的第0个元素以及第1个元素，再输出该顺序表。,2020/8/4,26,/sq_app1.cpp #include sq_LList.h int main() sq_LList s1(100); /建立容量为100的空顺序表对象s1 cout 第1次输出顺序表对象s1: endl; s1.prt_sq_LList(); s1.ins_sq_LList(0,1.5);/在第0个元素前插入1.5 s1.ins_sq_LList(1,2.5);/在第1个元素前插入2.5 s1.ins_sq_LList(4,3.5);/在第4个元素前插入3.5 cout 第2次输出顺序表对象s1: endl; s1

13、.prt_sq_LList(); s1.del_sq_LList(0); /删除顺序表s1中的第0个元素 s1.del_sq_LList(2); /删除顺序表s1中的第0个元素 cout 第3次输出顺序表对象s1: endl; s1.prt_sq_LList(); return 0; ,2020/8/4,27,结论 线性表采用顺序存储结构操作时，需大量移动数据元素，效率较低。 由于是静态存储结构，需预先定义大小确定的数组，容量有限。 适于直接(随机)存取操作。,2020/8/4,28,2.4 线性表的链式存储结构及其操作实现,链式存储是给每个结点附加指针字段，用于存储相邻结点的存储地址，使线性

14、表容易修改。 用链接方式存储的线性表称为链表。 线性表的链表存储结构的特点, 是可用内存空间中一组任意的存储单元（可以是地址连续的, 也可以是不连续的）来存储线性表的数据元素。,2020/8/4,29,在链表中，每个结点所占的存储空间可以分为两部分：数值域和指针域 数值域用来存放结点的数值 指针域用来存放结点之间的相邻关系,2020/8/4,30,单链表,单链表 单链表的每个结点都由数值域和一个指针域组成。 结点的存储结构定义如下 struct node datatype data; node *next; ;,数值域,指针域,data,next,存储每个结点的数值,存储该结点后继结点的地址,

15、struct linklist node *head； int n； ；,2020/8/4,31,头指针 线性表中第一数据元素a1的存储地址，称为线性表的头指针 在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针 线性表为空表时，头结点的指针域为空,2020/8/4,32,示例 node q,*p; q.data = 3; q.next = *; p = ,2020/8/4,33,单链表的查找（在单链表中查找第i个结点，若存在，则返回该结点的地址，否则返回表头结点的地址。） 引入整型变量j和指针变量q，令j的初始值为0，q指向表头结点； 在ji的情况下，反复向后移动指针q，并

16、且q每往后移动一次，j就加1； 当这个循环过程结束时，q指向第i个结点,2020/8/4,34,node *search（linklist L，int i） node *q; int j; q=L.head; j=0; if(i=1) ,思考，不带头结点时应如何修改？,j = 1,2020/8/4,35,单链表的插入（在单链表的第i个结点的后面插入一个数值为x的新结点）,2020/8/4,36,插入新结点的合法位置为0iL.n时，才能正确插入；否则不能进行插入操作 为结点q分配存储单元，将x存入新结点的数值字段中 将p结点指针字段的值存入q结点的指针字段中 将q结点地址存入p结点的指针字段中，

17、最后令线性表长度加1,2020/8/4,37,void insert(linklist /线性表的长度加1 ,2020/8/4,38,单链表的删除（删除线性表的第i个结点） 判断参数i是否正确（iL.n时，不能删除） 确定第i-1个结点的地址p 将p结点指针字段的值存入待删除结点中，用变量q表示 将q结点指针字段的值存入p结点的指针字段中 释放q结点所占用的存储单元 线性表的长度L.n减1,2020/8/4,39,void delete(linklist ,2020/8/4,40,单链表的创建 建立一个线性链表，其元素值依次为从键盘输入的正整数（以输入一个非正整数为结束），然后依次输出线性表中

18、的各元素值，并删除各结点,2020/8/4,41,线性单链表类 将线性链表的数据和基本操作（初始化、扫描输出、插入与删除链头元素等）封装成一个线性单链表类,2020/8/4,42,单链表类 /文件名linked_List.h #include using namespace std; /定义结点类型 template /T为虚拟类型 struct node T data; node *next; ; template /模板声明,数据元素虚拟类型为T class linked_List /单链表类 private: /数据成员 node *head; /链表头指针 int n; /线性表的长度

19、为n public: /成员函数 linked_List(); /构造函数,建立空链表 int flag_linked_List(); /检测单链表状态，是否为空链表 void prt_linked_List(); /从头指针开始扫描输出链表中的元素 void ins_linked_List(T); /将新元素插入到链头 T del_linked_List(); /删除链头元素 ;,2020/8/4,43,/构造函数,建立空链表 template linked_List:linked_List() head=NULL; n=0; return; /检测单链表状态 template int li

20、nked_List:flag_linked_List() if (head=NULL) return(0); /若空链表则函数返回0 return(1); /正常返回1 ,2020/8/4,44,/从头指针开始扫描输出链表中的元素 template void linked_List:prt_linked_List() node *p; p=head; if (p=NULL) cout data next; while (p!=NULL); return; ,2020/8/4,45,/将新元素插入到链头 template void linked_List:ins_linked_List(T x)

21、 node *p; p=new node; p-data=x; p-next=head; head=p; n+; return; ,2020/8/4,46,/删除链头元素 template T linked_List:del_linked_List() T y; node *p; if (head=NULL) cout data; head=p-next; delete p; n-; return(y); /返回删除的元素 ,2020/8/4,47,练习 定义一个空单链表，扫描输出该单链表。 依次在单链表的链头插入元素10、20、30、40，扫描输出该单链表中的元素。 连续两次删除链头元素，扫

22、描输出该单链表中的元素,2020/8/4,48,/文件名linklist_App.cpp #include linked_List.h int main() linked_List s; /定义一个空单链表s cout第1次从头指针开始扫描输出单链表s中的元素：endl; s.prt_linked_List(); s.ins_linked_List(10); /在单链表s的链头插入元素10 s.ins_linked_List(20); /在单链表s的链头插入元素20 s.ins_linked_List(30); /在单链表s的链头插入元素30 s.ins_linked_List(40); /在

23、单链表s的链头插入元素40 cout第2次从头指针开始扫描输出单链表s中的元素：endl; s.prt_linked_List(); if(s.flag_linked_List() /若链表非空，则删除链头元素 cout删除的链头元素是：s.del_linked_List()endl; if(s.flag_linked_List() /若链表非空，则删除链头元素 cout删除的链头元素是：s.del_linked_List()endl; cout连续两次删除链头元素后从头指针开始扫描输出单链表s中的元素：endl; s.prt_linked_List(); return 0; ,2020/8/

24、4,49,思考 在单链表类中请设计并实现成员函数 void search_linked_List(int); 在单链表中查找第i个结点，若存在，打印该结点值 void ins_linked_List(int,T); 在单链表的第i个结点后面插入一个数值为x的新结点 void del_linked_List(int); 删除线性表的第i个结点,如何查找值为x的某个元素呢？,2020/8/4,50,练习 定义一个空单链表，扫描输出该单链表。 依次在单链表的链头插入元素10、20、30、40，再扫描输出该单链表中的元素。 在第3个元素后面插入元素50，扫描输出该单链表中的元素。 连续两次删除链头元素

25、，扫描输出该单链表中的元素。 在第2个元素后面插入元素60，扫描输出该单链表中的元素。 删除第3个元素，扫描输出该单链表中的元素。 查找单链表中第2个元素的值并输出。,2020/8/4,51,循环单向链表,把单链表的首尾相连就构成了“循环单向链表”，即使单链表的最后一个结点的指针字段指向第一个结点。,2020/8/4,52,使用循环链表的主要优点是, 从表中任一结点出发均可找到表中其它结点。 在循环单链表中，用表尾指针Rear代替表头指针Head的形式称为“带表尾指针的循环链表”,2020/8/4,53,两个线性表进行首尾相连的合并操作,node *p; p = rear1-next; rear1-next = rear2-next; rear2-next = p;,2020/8/4,54,双向链表,双链表的每个结点由两个指针域和一个数值域组成。,2020/8/4,55,双链表的插入(P21)