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

第2章 线性表 第1章介绍了几种基本逻辑结构：线性结构、 树形结构和图结构。线性结构是最简单、最基本 的数据结构，本章讨论线性表的基本概念、存储 结构以及相关运算。 主要内容： 线性表的基本概念 线性表的顺序存储结构及实现 线性表的链表存储结构及实现 线性表的应用 1 2.1 线性表的基本概念 现实中存在大量线性表的实例。例如： 大写英文字母表：(A,B,C,Y,Z)； 一周中7天(星期一，星期二，星期日)； MP3播放器中的若干个歌曲的目录。怎样查 找自己喜欢的歌曲？怎样输入新的曲目？删 除过时曲目？这就是本节所研究的内容：线 性表及其运算。 2 2.1.1 线性表的定义 线性表（Linear List）是n(n0)个数据元 素的有限序列。记作：(a1，a2，an) ai(1in)属于同一数据对象，具有相同的 数据类型。 n代表表长，即线性表中数据元素的个数 。 当n=0时，线性表为空表。 对于ai: 当1in时，它有一个直接前驱ai1 ； 当1in时，它有一个直接后继ai+1 。 3 2.1.2 线性表的抽象数据类型 ADT Linear_list 数据对象：D=ai | ai ElemSet , i=1,2,n, n0 ； 数据关系：R= | ai-1 ,aiD, i=2,3, ,n 基本操作：初始化空线性表; 求线性表表长; 取线性表的第i个元素; 在线性表的第i个位置插入元素x; 删除线性表的第i个元素; 修改线性表中的第i个元素; 按某种要求重排线性表中各元素的顺序; 按某个特定值查找线性表中的元素; 等等; ADT Linear_list; 4 2.2 线性表的顺序存储结构及实现 为了用计算机解决线性表问题，需要考 虑数据信息如何在计算机内存储。计算机 可以用多种不同的方法来存储数据信息， 常用的方法是顺序存储结构和链式存储结 构。 5 2.2.1 线性表的顺序存储结构 顺序存储结构是最简单常用 的方法。顺序存储结构也称为 向量存储。向量是内存中一批 地址连续的存储单元。 线性表的顺序存储结构， 要求逻辑上相邻的数据元素在 物理位置上也一定是相邻的， 如图所示。 6 假设a1的地址为LOC(a1)，每个元素占L个字 节（本例L为2），ai的存放地址为： LOC(ai) = LOC(a1) + L*(i1) 只要确定了线性表存储的起始位置，线性表中 任一数据元素的位置都可确定，可以随机存取。 特点：逻辑上相邻物理地址相邻； 可以随机存取数据； 7 为了更好地体现信息隐蔽原则以及数据抽象原 则，一维数组elem和线性表的长度length封装在 一个结构体中。 const int MAXSIZE=100; typedef int ElemType ; struct SqList0 ElemType elemMAXSIZE; /一维数组 int length ; /表的实际长度 SqList0就是顺序存储结构的类型标识符。 在高级语言环境中使用一维数组来模 拟实现顺序存储结构。 8 1在类中使用静态一维数组 静态一维数组是指在声明定义数组时，所给 出数组的大小是确定的。数组的大小留有余地。 const int MAXSIZE=100; typedef int ElemType ; class SqList1 private: ElemType elemMAXSIZE; /一维数组 int length ; /线性表长度 public: ;/其他成员函数; ； 在面向对象的程序设计中，通常将数据元素 的存储结构和对数据的操作封装在一个类之中。 9 2在类中使用动态一维数组 动态一维数组是指在声明定义数组时用指针 表示，数组的大小没有确定。在数据成员中除数 组elem、表长length还给出表的容量maxlen。 class SqList2 private: ElemType *elem； /用指针表示一维数组 int length ; /表的实际长度 int maxlen; /表的最大长度，容量 public: ; /其他成员函数 ; 在面向对象的程序设计中，通常将数据元素 的存储结构和对数据的操作封装在一个类之中。 10 2.2.2 顺序表类定义 顺序表类是指采用顺序存储结构来表 示线性表的类。 线性表采用顺序存储结构，其数组和 线性表长可以作为类的数据成员。线性表 各种操作的处理可以作为类的函数成员， 且大多是公有函数，目的是提供类对外部 的接口供调用。 一个简明的顺序表类：SqList。 11 /顺序表类SqList的定义 typedef int ElemType; /数据元素的类型 const int MAXSIZE=100; /数组的容量 class SqList private: ElemType elemMAXSIZE; /数组 int length; /线性表长 public: SqList( void); /构造函数 SqList() ; /析构函数 void Creat() ; /初建一个简表函数 void PrintOut(); /输出线性表函数 void Insert( int i, ElemType e); /插入函数 ElemType Delet(int i); /删除函数 ;/类定义结束 12 SqList:SqList() length=0; /构造函数，构造空表 void SqList:Creat() /建立一个简表函数 coutlength; coutelemk; void SqList:PrintOut() /输出线性表函数 coutlength) couti; j-) elemj=elemj-1; /移动元素 elemi=e; /插入元素 length+; /线性表长加1 算法采用SqList类的成员函数来表示。默认线性表已经存在 。插入位置i和插入元素值e是已知条件。 16 2顺序表的删除 删除线性表中的第i个元素ai，需把元素ai+1， an分别向前移动一个位置。对于长度为n的线性表： (a1, ，ai1,ai，an) 变成长度为n 1的线性表： (a1,，ai-1,ai+1，an) 删除位置i的合理取值： 1 length-1) coutie; as.Insert(i,e); /调用插入算法函数 as.PrintOut(); couti; x=as.Delet(i); /调用删除算法函数 cout=0 i-; elemi+1=x; /插入数据元素 length+; /表度长加1 ; 算法从表尾元素开始与x比较，当elemix且未到表头元 素时继续循环。一边比较一边向后移动数据元素。 算法的主要考虑数据元素的移动，时间复杂度为O(n)。 若采用从表头元素开始与x比较的方法，其效率如何？ 29 2在非递减有序表中删除所有值为x的元素 。 已知条件是某数据元素x的值。以elemi与x是否相等为判 断条件来查找删除的位置，然后删除所有值为x的元素。 算法2.4 void SqList:Deletaz(ElemType x) int i=0,j; /查找第一个x值出现的位置 while(idata来表示，根据前文定义的数据 域是整型的，像一般的整型变量一样可以在输入/输出、赋 值语句中使用。例如： s-data=110; /或者cins-data; coutdata; /这样输出的结果就是110 结点s的指针域用s-next来表示，可以用来存放另外一 个结点的首地址。根据需要也可以使其为空，如： s-next=NULL； 3结点的动态申请和释放 110 38 要把上述结点s释放、归还给系统，则必须用命 令来实现： delete s; 值得注意的是，这里释放的只是数据元素结点 所占用结点的存储单元，而指针变量h,s本身仍然 存在，只是h,s之中不再有具体地址内容，什么结 点也不指向了。 3结点的动态申请和释放 39 多个结点连接在一起可以构成一个链表。由 于每个结点只包含一个指针域，故称这种链表为 单链表。一个非空线性表(a1，a2，a3)对应的单 链表如图所示。 4链表 详细讲解 40 5指针变量的主要操作 详细讲解 41 2.3.2 单链表类定义 在面向对象的程序设计中，链表被设计成一个 类。链表类在不同教科书有不同的设计。 链表有一种简明的设计，将结点设计为一个结 构体类型，再将该链表的头指针Head作为链表类 的数据成员。 结点结构的定义： typedef int ElemType; struct NodeType /结点类型定义 ElemType data; NodeType *next; ; 42 头指针Head可唯一确地定一个单链表。 对链表中各数据结点的访问都将从头指针 Head开始查找。 将一个NodeType类型结点的指针变量 Head作为单链表的头指针。 单链表类的组成： 将头指针Head作为类LinkList的私有数据 成员； 将重要的算法设计成类的若干成员函数。 43 /链表类定义 class LinkList private: NodeType *Head; /链表头指针 public: LinkList(); /构造函数，初始化空链表 LinkList(); /析构函数 void creat(); /初建一个非空链表 void Display(); /输出链表的数据元素 void insert(int i,ElemType x); /插入 ElemType delet(int i ); /删除第i个结点 ; /类定义结束 44 LinkList:LinkList() /创建一个空链表，有一个头结点 Head=new NodeType; Head-next=NULL; Head-data=0; coutnext; /p 指向第一个数据结点 while(p!=NULL) /循环释放链表的数据结点 Head-next=p-next; delete p; p=Head-next; coutx; /先输入数据：an-1 while(x!=-999) s=new NodeType; s-data=x; s-next=Head-next; /Head为头结点的指针 Head-next=s; coutx; /逐个输入 an -2,a0 coutnext; /p指向第一个数据结点 while(p!=NULL) coutdatanext; /p移向下一个结点 coutdata=x; s-next=p-next; /插入s结点 p-next=s; /注意，两条修改指针的语句顺序不可颠倒。 50 （2）在p指针所指向的结点前插入一个元素， 操作如图所示。 若在p前插入需先找出p前驱结点地址。另设一指针q， 从链表的头结点head开始向后移动进行查找，直到q指向p的 前驱结点为止。然后在q结点之后，p结点之前进行插入。 语句组如下： q=head; while(q-next!=p) q=q-next; /查找p前驱结点 s=new NodeType; s-data=x; s-next=p; q-next=s; /插入s结点 /在已知结点的“前”边进行插入的操作较为复杂。 51 （3）在已知的线性表的第i个位置插入数据元素x。 ，在此作为链表类的公有成员函数来实现。在 线性表的第i个位置进行插入，是指链表中有效 数据元素结点的位置，头结点不包含在内。 介绍典型插入算法。在线性表的第i个位置进行 插入，是指链表中有效数据元素结点的位置，头结 点不包含在内。该算法作为链表类的公有成员函数 来实现。 52 在线性表的第i个位置插入数据元素x。算法2.6 void LinkList:insert(int i,ElemType x) NodeType *p,*q,*s; int k=1; /计数器k，用于寻找i位置 q=Head; p=Head -next; while(knext; k+; if(k=i) s=new NodeType; s-data=x; q-next=s; s-next=p; coutn+1： while()循环会执行到：p= =NULL，q指向最后一个数据 结点，因为k记数也达到n+1，k不等于i，也执行else语句输 出：“n inext; /让q指向p的后继结点 p-next=q-next; /修改指针，绕过q结点 delete q; /删除q结点 56 （2）删除p所指向的结点。 要删除表中p所指向的结点（元素），应先找 到p的前驱结点q。这就需要组织while循环让q从链表 头部q=head向后查找，直到q-next=p为止，然后 进行删除操作。 语句组如下： q=head; while (q-next!=p) q+; /让q向后找p的前驱结点 q-next=p-next; /修改指针，绕过p结点 delete p; /删除p结点 57 （3）在已知的线性表中，删除第i个数据元素结点 ，返回元素的值。 -链表删除典型算法 ，在此作为链表类的公有成员函数来实现。在 线性表的第i个位置进行插入，是指链表中有效 数据元素结点的位置，头结点不包含在内。 已知条件是数据结点的位置i（或称序号）。 为了删除第i位置的数据结点，需要设置指针p从第 一个数据元素（p=Head-next）向后查找，头结 点不包含在内。另外还需要一个辅助指针q作为p 的前驱结点指针紧跟p指针，q的初始值是q=Head 。当它们不断向后移动达到确定位置后，即可进 行删除操作，如图： 58 单链表删除的典型算法2.7 ElemType LinkList:delet(int i) NodeType *p,*q,*s; ElemType x; int k=1; /k为计数器 q=Head; p=Head-next; /q指头指针，p指第一个数据结点 while(knext; k+; if(p!=NULL) x=p-data; q-next=p-next; delete p; coutn： q会指向最后一个数据结点，而p为空，所以执行else语 句输出提示：“n idata=y; q=head; p=q-next; while( p!=NULL) /根据数据的值查找 s-next=p; q-next=s; /插入新结点 65 根据数据元素的值进行删除 （2）删除线性表中值为x的数据元素，输出 “YES！”；如果x不存在，输出“NO！”。 为了查找值为x的结点，设p从头找起； 为了删除该结点，设q指向p的前驱结点； 66 根据数据元素的值删除算法： void LinkList:delet2(ElemType x) NodeType *p,*q; q=head; p=q-next; while(p!=NULL) p+; if (p=NULL) coutnext= p-next; /找到x结点，输出“YES！ ” delete p; /删除结点 coutnext; h-next=NULL; /暂时将头结点与后边数据结点断开 while (p!=NULL) /不断地在头结点之后插入结点 q=p-next; p-next=h-next; h-next=p; p=q; 69 3两条单链表的合并 单链表的合并具有多种不同的方式，一种方 式是将两个有序表合并成为一个新的有序表，还 有一种方式是将两个线性表的元素间隔交叉合并 等。这里介绍两个非递减有序表的合并 两个单链表的合并涉及两个类对象，算法中 是将第1条链表作为基础，将第2条链表合并进来 ，最终结果就在第1条链之中。具体实现见算法 2.9。 70 单链表合并算法2.9 void LinkList:merge( LinkList b) NodeType *p,*q,*r,*s; p=Head; r=p-next; /合并后的链表仍在Head之中 q=b.Head-next; s=q-next; /b是将被合并进来的链表 while(r!=NULL r=r-next; else /b链上结点数据小，将q连入主链 q-next=p-next; p-next=q; p=q; q=s; s=s-next; if(r=NULL)p-next=q; else ; coutnext=A-next; A-next=HB-next; delete HB; /释放B表附加头结点 A=B; /A链尾指针A指新尾结 点 时间复杂度为O(1) 75 2.4.2 双向链表 双向链表中的某个结 点，可以直接找到它的前 驱和后继结点。无论利用 向前这一链还是向后这一 链，都可以遍历整个链表 ，如果有一根链失效了， 还可以利用另一根链修复 整个链表。 结点结构如下： typedef char ElemType; struct NodeType2 ElemType data; NodeType2 *next, *prior; ; NodeType2 *p, *q, *s; 76 假设结点s已准备好，插入结点s的具体操作语句组如下： s-next=p; s-prior=p-prior; /s结点的前驱指针域，取p的前驱结点（值为a）地址 p-prior-next=s; /让p的前驱结点（值为a）的后继指针域，指向s结点 p-prior=s; /让p的前驱指针域，也指向s结点 注意，各语句顺序不可随意改变。 1在双向链表中p结点之前插入一个值为x的结点 。 77 语句组： p-prior-next=p-next; /对应图中上方的虚线指针 p-next-prior=p-prior; /对应图中下方的虚线指针 delete p; 2在双向链表中删除一个p结点。 由此可见，在循环链表、双向链表中进行插 入或删除操作比较方便。 78 2.4.3 顺序结构与链表结构的分析比较 用顺序的方式存储线性表： 1.内存的存储密度高，在结点等长时， 可随机存取结点； 2.对顺序表的插入和删除往往造成大量 信息的移动，效率比较低。 3. 顺序表要求占用连续的存储空间， 存储分配只能预先进行。如果插入操作超 出预先分配的存储区间，需要临时扩大是 困难的。 79 2.4.3 顺序结构与链表结构的分析比较 采用链表存储结构可克服上述不足， 1.它适合于需要频繁插入和删除元素的 线性表，不会大量移动数据元素。 2. 也适合于存储空间大小不能预先确 定的线性表。可以随时分配和释放存储空 间。 3. 链表结构不能随机存取结点中的数 据，而需要在链表上先进行查找，然后进 行存取操作。 80 2.5 一元多项式相加问题 一元符号多项式的相加操作是线性表处理的典型 用例。数学上一个一元多项式如下： 称p为x的n阶多项式，aixi是多项式的某个单项（ 0in），其中x为自变量，ai为系数，i为自变量的指 数。已知有两个一元多项式A和B： 将这两个多项式相加得一个新的多项式C： 81 2.5.1 多项式的链表存储结构 一个多项式可以采用一条链表来表示。每个结点对应 于多项式的一个项，其结点的结构如下： struct Lpoly int coef ; /自变量的系数 int exp ; /自变量的指数 Lpoly *next; /指向下一结点的指针 ; 每个多项式的链表由多个单项的结点组成，高指数 的项（高次幂）结点在链表头部，低指数的项（低次幂） 结点在链表的后部。A，B两个多项式的链表结构如图所示 。 82 2.5.2 多项式相加的实现 一个链表中结点的顺序按照x的指数递减 排列。两个多项式相加实质上是两个有序链表 的合并操作。 为了实现两个多项式相加，现设C链表为 A、B链表相加后的新链表。为了节省内存资 源，以A链表为基础将B链表的结点合并到A链 表中。在此，设C链表头指针为pc，令其指向 pa(pc=pa)，这样以pa链表为基础进行合并操 作，最终的结果就是这条以pc为头指针的链表 。 83 多项式加法（链表合并）的方法 为了进行多项式加法运算，设置p，q两个指 针变量分别指向pa，pb两个链表的第一个数据元 素结点。 然后对p，q两个结点的指数域进行比较： 1. 两个结点的指数相同，则结点的系数相加 。新的系数非零，则连入第3条链表C；否则跳过 这两个结点。 2. 两个结点的指数不同，将指数较大的结点 连入C表。 84 初始状态 第1次处理后 第2次处理后 多项式加法（链表合并）的图示 85 Lpoly *add_poly(Lpoly *pa, Lpoly *pb) Lpoly *pc, *p, *q, *r; p=pa-next; q=pb-next; r=pa; pc=pa; while (p!=NULL if(x!=0) p-coef=x ; r=p; /系数和非零 else r-next=p-next; /系数和为零 p=p-next; q=q-next; 多项式加法（链表合并）算法2.10 86 else /指数不相等 if(p-expq-exp) /p结点指数大，接入p结点 r-next=p; r=p; p p-next; else /q结点指数大，接入q结点 r-next=q; r=q; q=q-next; / while end if(p=NULL) r-next=q; else r-next=p; return pc; /返回合并后的链表头指针pc /add_poly end 多项式加法（链表合并）算法2.10 87 多项式加法（链表合并）算法说明 整个算法主体是一个循环结构，循环条件是 两个while (p!=NULL /数据元素的类型 const int MAXSIZE=100; /数组的容量 class Sqlist private: ElemType elemMAXSIZE; int length; public: Sqlist( void); Sqlist() ; void Creat(); void Insert( int i, ElemType e); ElemType Delet(int i); void PrintOut(); ; 91 /-