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

1、NCU-ZQP,1,第2章 线性表,第1章介绍了几种基本逻辑结构：线性结构、树形结构和图结构。线性结构是最简单、最基本的数据结构，本章讨论线性表的基本概念、存储结构以及相关运算。 主要内容： 线性表的基本概念 线性表的顺序存储结构及实现 线性表的链表存储结构及实现 线性表的应用,NCU-ZQP,2,2.1 线性表的基本概念,现实中存在大量线性表的实例。例如： 大写英文字母表：(A,B,C,Y,Z)； 一周中7天(星期一，星期二，星期日)； MP3播放器中的若干个歌曲的目录。怎样查找自己喜欢的歌曲？怎样输入新的曲目？删除过时曲目？这就是本节所研究的内容：线性表及其运算。,NCU-ZQP,3,2.

2、1.1 线性表的定义,线性表（Linear List）是n(n0)个数据元素的有限序列。记作：(a1，a2，an) ai(1in)属于同一数据对象，具有相同的数据类型。 n代表表长，即线性表中数据元素的个数。 当n=0时，线性表为空表。 对于ai: 当1in时，它有一个直接前驱ai1 ； 当1in时，它有一个直接后继ai+1 。,NCU-ZQP,4,2.1.2 线性表的抽象数据类型,ADT Linear_list 数据对象：D=ai | ai ElemSet , i=1,2,n, n0 ； 数据关系：R= | ai-1 ,aiD, i=2,3, ,n 基本操作：初始化空线性表; 求线性表表长;

3、 取线性表的第i个元素; 在线性表的第i个位置插入元素x; 删除线性表的第i个元素; 修改线性表中的第i个元素; 按某种要求重排线性表中各元素的顺序; 按某个特定值查找线性表中的元素; 等等; ADT Linear_list;,NCU-ZQP,5,2.2 线性表的顺序存储结构及实现,为了用计算机解决线性表问题，需要考虑数据信息如何在计算机内存储。计算机可以用多种不同的方法来存储数据信息，常用的方法是顺序存储结构和链式存储结构。,NCU-ZQP,6,2.2.1 线性表的顺序存储结构,顺序存储结构是最简单常用的方法。顺序存储结构也称为向量存储。向量是内存中一批地址连续的存储单元。 线性表的顺序存储

4、结构，要求逻辑上相邻的数据元素在物理位置上也一定是相邻的，如图所示。,NCU-ZQP,7,假设a1的地址为LOC(a1)，每个元素占L个字节（本例L为2），ai的存放地址为： LOC(ai)=LOC(a1)+L*(i1) 只要确定了线性表存储的起始位置，线性表中任一数据元素的位置都可确定，可以随机存取。,特点：逻辑上相邻物理地址相邻； 可以随机存取数据；,NCU-ZQP,8,为了更好地体现信息隐蔽原则以及数据抽象原则，一维数组elem和线性表的长度length封装在一个结构体中。 const int MAXSIZE=100; typedef int ElemType ; struct SqLi

5、st0 ElemType elemMAXSIZE; /一维数组 int length ; /表的实际长度 SqList0就是顺序存储结构的类型标识符。,在高级语言环境中使用一维数组来模拟实现顺序存储结构。,NCU-ZQP,9,1在类中使用静态一维数组 静态一维数组是指在声明定义数组时，所给出数组的大小是确定的。数组的大小留有余地。 const int MAXSIZE=100; typedef int ElemType ; class SqList1 private: ElemType elemMAXSIZE; /一维数组 int length ; /线性表长度 public: ;/其他成员函数

6、; ；,在面向对象的程序设计中，通常将数据元素的存储结构和对数据的操作封装在一个类之中。,NCU-ZQP,10,2在类中使用动态一维数组 动态一维数组是指在声明定义数组时用指针表示，数组的大小没有确定。在数据成员中除数组elem、表长length还给出表的容量maxlen。 class SqList2 private: ElemType *elem； /用指针表示一维数组 int length ; /表的实际长度 int maxlen; /表的最大长度，容量 public: ; /其他成员函数 ;,在面向对象的程序设计中，通常将数据元素的存储结构和对数据的操作封装在一个类之中。,NCU-ZQP

7、,11,2.2.2 顺序表类定义,顺序表类是指采用顺序存储结构来表示线性表的类。 线性表采用顺序存储结构，其数组和线性表长可以作为类的数据成员。线性表各种操作的处理可以作为类的函数成员，且大多是公有函数，目的是提供类对外部的接口供调用。 一个简明的顺序表类：SqList。,NCU-ZQP,12,/顺序表类SqList的定义 typedef int ElemType; /数据元素的类型 const int MAXSIZE=100; /数组的容量 class SqList private: ElemType elemMAXSIZE; /数组 int length; /线性表长 public: Sq

8、List( void); /构造函数 SqList() ; /析构函数 void Creat() ; /初建一个简表函数 void PrintOut(); /输出线性表函数 void Insert( int i, ElemType e); /插入函数 ElemType Delet(int i); /删除函数 ;/类定义结束,NCU-ZQP,13,SqList:SqList() length=0; /构造函数，构造空表 void SqList:Creat() /建立一个简表函数 coutlength; coutelemk; void SqList:PrintOut() /输出线性表函数 cout

9、n length=length ; coutn PrintOut Data:n ; for(int k=0; klength;k+) coutsetw(6)elemk; coutendl; 这两个函数主要是为上机实验提供方便。从“数据结构”课程的角度看，线性表的主要操作是插入、删除等，这些重要算法将在下文详细介绍。,NCU-ZQP,14,2.2.3 顺序表的插入和删除,1顺序表的插入 插入操作是在线性表的第i1个数据元素和第i个数据元素之间插入一个新的数据元素e。使长度为n的线性表： (a1, ，ai-1, ai，an) 变成长度为n+1的线性表： (a1, ，ai-1,e，ai，an) 先把

10、元素an，an1，ai向后各自移动一个位置，然后将e插在第i个位置上。 注意插入位置i取值的正确范围，从逻辑上讲是： 1=i=length+1 由于C/C+的数组下标从零开始，在程序中位置的正确范围变换为： 0=i1=length,NCU-ZQP,15,顺序表的插入,有一线性表（11，23，35，46，57，67，78，89），要求在第4个位置（下标为3）插入一个值为38的数据。,NCU-ZQP,16,顺序表的插入算法-算法2.1,void SqList:Insert( int i, ElemType e) int j; i-; /逻辑位置换算为C+数组下标值 if(ilength) cout

11、i; j-) elemj=elemj-1; /移动元素 elemi=e; /插入元素 length+; /线性表长加1 算法采用SqList类的成员函数来表示。默认线性表已经存在。插入位置i和插入元素值e是已知条件。,NCU-ZQP,17,2顺序表的删除,删除线性表中的第i个元素ai，需把元素ai+1， an分别向前移动一个位置。对于长度为n的线性表： (a1, ，ai1,ai，an) 变成长度为n1的线性表： (a1,，ai-1,ai+1，an) 删除位置i的合理取值： 1=i=length 算法中假设a1存放在elem0中。在程序中位置i的正确范围是： 0=i1=length1,NCU-Z

12、QP,18,顺序表的删除,有一线性表（11，23，35，46，57，67，78，89），要求删除在第4个（下标为3）数据元素。,11 23 35 46 57 67 78 89,11 23 35 57 67 78 89,下标 0 1 2 3 4 5 6 7,NCU-ZQP,19,顺序表的删除算法-算法2.1,ElemType SqList:Delet(int i) ElemType x; int j; i-; /转换成C+数组下标 if(ilength-1) cout i Error!endl; x=-1; /判断删除位置 else x=elemi; for(j=i; jlength-1; j+

13、) elemj=elemj+1; /向前移动数据元素 length-; /线性表长减1 return x; 算法默认线性表已经存在。删除元素的位置i是已知条件。 本函数具有返回值，就是被删除的数据元素值。,NCU-ZQP,20,用顺序表的类对象，调用线性表的插入和删除算法,int main() int i; ElemType e,x; SqList as; /声明创建一个类对象as as.Creat(); /输入数据建立线性表 coutie; as.Insert(i,e); /调用插入算法函数 as.PrintOut(); couti; x=as.Delet(i); /调用删除算法函数 cou

14、tn 元素数值= x; as.PrintOut() _getch(); return 0; ,NCU-ZQP,21,3插入和删除算法的时间复杂度分析,在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在数据元素的移动上。而移动元素的次数取决于插入或删除元素的位置。 算法由于插入（或删除）的位置不同，移动元素的次数也不同，在分析算法时采用移动元素次数的平均值，来估算时间复杂度。,NCU-ZQP,22,插入算法的平均移动次数分析,假设Pi是在第i个元素之前插入一个元素的概率（可能性），ni+1是在第i个元素之前插入一个元素所需移动元素的次数。 在插入时，i的取值范围是1到n

15、+1。在长度为n的线性表中插入一个元素时所需移动元素次数的平均次数为：,NCU-ZQP,23,插入算法的平均移动次数分析,假设在任何位置插入元素的概率pi相等（暂不考虑概率不相等情况）：,元素插入位置的可能值为： i=1,2, n, n+1 相应向后移动元素次数为： ( ni+1)=n,n1, 1,0 对其求总和，为n(n+1)/2。 所以插入时，数据元素平均移动次数为：,NCU-ZQP,24,删除算法的平均移动次数分析,假设qi是删除第i个元素的概率，ni是删除第i个元素所需移动元素的次数。 在删除时，i的取值范围是1到n。 则在长度为n的线性表中删除一个元素时所需移动元次数的平均次数为：,

16、NCU-ZQP,25,删除算法的平均移动次数分析,假设在线性表的任何位置删除元素的概率qi相等（暂不考虑概率不相等情况）:,元素删除位置的可能值： i=1,2,n 相应向前移动元素次数： ni=n1,n-2,0 对n1,1,0求总和，显然为n(n1)/2，则删除时数据元素平均移动次数为：,NCU-ZQP,26,插入和删除算法的时间复杂度分析,在顺序表中插入或删除一个元素时，平均移动表中大约一半的数据元素。根据上述两式( n/2 和 (n-1)/2)，忽略常数项以及常系数。若表长为n，则两个算法的时间复杂度都为：T(n)=O(n)。,NCU-ZQP,27,2.2.4 线性表的其他运算,除前面两种

17、基本运算外，还有一些较复杂的运算。 class SqList /代码与前文类Sqlist的定义完全同前； public: /以下是增加的两个公有函数成员 void Insertdz( ElemType x); /有序表插入 void Deletaz(ElemType x); /有序表删除 ;,NCU-ZQP,28,1在非递减有序表中插入一个数据元素x，使线性表仍保持非递减有序。,前提是线性表中数据元素已经有序。已知条件是将要插入的数据x，插入的位置需要程序来查找。 已知有线性表：（14，21，21，38，46，80） 若x=30，结果：（14，21，21，30，38，46，80） 若x=10，

18、结果：（10，14，21，21，38，46，80） 若x=99，结果：（14，21，21，38，46，80，99） 因插入的数据元素x值不同其插入位置也不同。插入位置怎样确定？,NCU-ZQP,29,1在非递减有序表中插入一个数据元素x，使线性表仍保持非递减有序。,算法2.3 void SqList:Insertdz( ElemType x) int i=length-1; while(i=0 算法从表尾元素开始与x比较，当elemix且未到表头元素时继续循环。一边比较一边向后移动数据元素。 算法的主要考虑数据元素的移动，时间复杂度为O(n)。 若采用从表头元素开始与x比较的方法，其效率如何？

19、,NCU-ZQP,30,2在非递减有序表中删除所有值为x的元素。,已知条件是某数据元素x的值。以elemi与x是否相等为判断条件来查找删除的位置，然后删除所有值为x的元素。 算法2.4 void SqList:Deletaz(ElemType x) int i=0,j; /查找第一个x值出现的位置 while(ilength /表长减1 ,NCU-ZQP,31,删除非递减有序表中所有值为x的元素，算法分析,本算法含有两个并列的循环结构，由于影响时间效率的主要因素是大量数据元素的移动，因此前面关于下标i的循环忽略不计。 else中是一个二重循环，如果忽略x重复出现的次数，主要依据是移动数据元素的

20、for循环，经估算元素的平均移动次为(n1)/2，因此算法的时间复杂度是O(n)。 综上所述，线性表采用顺序存储结构在插入、删除时，需大量移动数据元素，效率较低。由于是静态存储结构，需预先定义大小确定的数组，容量有限。,NCU-ZQP,32,2.3 线性表的链表存储结构及实现,采用顺序存储结构的线性表，在频繁进行插入、删除操作时会大量移动数据元素，效率较低。同时，顺序存储必须占用一批地址连续的存储空间，存储分配只能预先进行。但是，它适于直接（随机）存取操作。 本节将讨论线性表的另一种存储结构链表存储结构，由于它不要求逻辑上相邻的数据元素在物理位置上也一定相邻，因此，它没有顺序存储结构所具有的弱

21、点。,NCU-ZQP,33,2.3.1单链表与指针,对于程序设计基础较好的读者，可以越过本节直接学习2.3.2节。 线性表的链表存储结构可以利用内存空间中一组任意的存储单元来存储线性表的各个数据元素，这些存储单元地址可以连续也可不连续。那么怎样根据第i个数据元素找到第i+1个数据元素呢？ 为了弄清单链表的概念，首先需回顾指针的基本概念。,NCU-ZQP,34,1指针和指针变量,所谓指针是指计算机内某个存储单元的地址。 一个用来存放指针（地址）的独立变量称作指针变量。 如果有：int *a; int m=6; 就允许：a= 那么name指针就是该字符串的首地址。 虽然指针变量可以存放存变量单元的

22、地址，但是根据其数据类型声明的不同，其地址性质是不同的。,NCU-ZQP,35,在存储和表示线性表时，一个结点用来存储线性表的一个数据元素。 每个结点一般分为两个域：数据域；指针域。 一个结点定义为结构体类型： typedef int ElemType; struct NodeType ElemType data; /数据域，存放数据信息 NodeType *next; /指针域，存放同样结构体类型结点的首地址 ;,2结点,NCU-ZQP,36,对结点的访问和处理常通过指针变量。 用来存放结点首地址的指针变量，可用下列语句来声明： NodeType *h,*s; 变量h,s被定义为指针型之后，

23、并没有指向任何实际结点，即指针变量中还没有某个实际结点所占空间的首地址值。 如何为指针变量提供一个结点的首地址？,2结点,NCU-ZQP,37,让指针变量p指向一个新分配的结点，语句如下： p = new NodeType; 系统分配了一个结点所需的存储空间，并且将首地址赋值给指针变量p。 可以通过赋值语句： s=p； 让指针变量s存放与p指针之中相同的地址，也称s和p指向同一个结点，如图所示。,3结点的动态申请和释放,NCU-ZQP,38,结点s的数据域用s-data来表示，根据前文定义的数据域是整型的，像一般的整型变量一样可以在输入/输出、赋值语句中使用。例如： s-data=110; /

24、或者cins-data; coutdata; /这样输出的结果就是110 结点s的指针域用s-next来表示，可以用来存放另外一个结点的首地址。根据需要也可以使其为空，如： s-next=NULL；,3结点的动态申请和释放,NCU-ZQP,39,要把上述结点s释放、归还给系统，则必须用命令来实现： delete s; 值得注意的是，这里释放的只是数据元素结点所占用结点的存储单元，而指针变量h,s本身仍然存在，只是h,s之中不再有具体地址内容，什么结点也不指向了。,3结点的动态申请和释放,NCU-ZQP,40,多个结点连接在一起可以构成一个链表。由于每个结点只包含一个指针域，故称这种链表为单链表

25、。一个非空线性表(a1，a2，a3)对应的单链表如图所示。,4链表,详细讲解,NCU-ZQP,41,5指针变量的主要操作,详细讲解,NCU-ZQP,42,2.3.2 单链表类定义,在面向对象的程序设计中，链表被设计成一个类。链表类在不同教科书有不同的设计。 链表有一种简明的设计，将结点设计为一个结构体类型，再将该链表的头指针Head作为链表类的数据成员。 结点结构的定义： typedef int ElemType; struct NodeType /结点类型定义 ElemType data; NodeType *next; ;,NCU-ZQP,43,头指针Head可唯一确地定一个单链表。,对链

26、表中各数据结点的访问都将从头指针Head开始查找。 将一个NodeType类型结点的指针变量Head作为单链表的头指针。 单链表类的组成： 将头指针Head作为类LinkList的私有数据成员； 将重要的算法设计成类的若干成员函数。,NCU-ZQP,44,/链表类定义 class LinkList private: NodeType *Head; /链表头指针 public: LinkList(); /构造函数，初始化空链表 LinkList(); /析构函数 void creat(); /初建一个非空链表 void Display(); /输出链表的数据元素 void insert(int

27、i,ElemType x);/插入 ElemType delet(int i ); /删除第i个结点 ;/类定义结束,NCU-ZQP,45,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; coutn 链表已经删除。endl; delete Head; /最后释放头结点的空间 Head=NULL;

28、 ,NCU-ZQP,46,算法2.5 void LinkList:creat() /输入建立一个链表 NodeType *s; ElemType x; Coutx; /先输入数据：an-1 while(x!=-999) s=new NodeType; s-data=x; s-next=Head-next; /Head为头结点的指针 Head-next=s; coutx; /逐个输入 an -2,a0 coutn 插入结束。链表建成。endl; ,NCU-ZQP,47,/输出显示链表内容 void LinkList:Display() NodeType *p; p=Head-next; /p指向

29、第一个数据结点 while(p!=NULL) coutdatanext; /p移向下一个结点 coutendl; /p为空，输出完毕 头指针Head必须保持不变，需另设一个指针变量p从第一个数据结点向后逐步移动，边输出边移动p直至表尾。,NCU-ZQP,48,上述函数不是单链表的典型算法，之所以列出是为了配合典型算法，构成体系比较完整的类设计。 为了在实际中应用单链表，还必须能够将算法和函数放在程序系统中去认识和设计编码。 在主函数中声明和创建LinkList链表类对象h，同时初始化h为空链表。然后调用建立链表的函数输入数据，接着调用输出函数将链表内容输出显示。 int main( ) Lin

30、kList h; h.creat(); /通过对象h调用建立函数 h.Display(); /通过对象h调用输出函数 _getch(); return 0; ,NCU-ZQP,49,2.3.3 链表的插入和删除,为了规范单链表的表示和运算，约定使用附加头结点，在一般情况下均默认带有附加头结点，简称头结点。所谓头结点是指该结点的数据域并不存放线性表的任何数据元素，一个空表如左图，非空链表如右图。,单链表是数据结构学习的重要基础。下面从最基本的插入、删除的语句组和图示入手，介绍链表类的插入和删除算法。,NCU-ZQP,50,1插入,在讨论插入算法前，首先看单链表中插入结点的基本操作。 （1）假设已

31、知p指针指向的结点，在p结点之后插入一个元素x，操作如图2.8所示。,相关操作的语句组如下： s=new NodeType; /分配新的结点s s-data=x; s-next=p-next; /插入s结点 p-next=s; /注意，两条修改指针的语句顺序不可颠倒。,NCU-ZQP,51,（2）在p指针所指向的结点前插入一个元素，操作如图所示。 若在p前插入需先找出p前驱结点地址。另设一指针q，从链表的头结点head开始向后移动进行查找，直到q指向p的前驱结点为止。然后在q结点之后，p结点之前进行插入。 语句组如下： q=head; while(q-next!=p) q=q-next; /查

32、找p前驱结点 s=new NodeType; s-data=x; s-next=p; q-next=s; /插入s结点 /在已知结点的“前”边进行插入的操作较为复杂。,NCU-ZQP,52,（3）在已知的线性表的第i个位置插入数据元素x。,，在此作为链表类的公有成员函数来实现。在线性表的第i个位置进行插入，是指链表中有效数据元素结点的位置，头结点不包含在内。,介绍典型插入算法。在线性表的第i个位置进行插入，是指链表中有效数据元素结点的位置，头结点不包含在内。该算法作为链表类的公有成员函数来实现。,NCU-ZQP,53,在线性表的第i个位置插入数据元素x。算法2.6,void LinkList:

33、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 插入成功。 endl; else coutn i1,或 i太大，不存在。endl; coutn 插入结束。; ,NCU-ZQP,54,链表插入算法的说明：,由于算法已知条件是：插入的位置i（或称序号）和被插入的数据元素x，因此函数具有两个形参： void LinkLi

34、st:insert(int i,ElemType x) 在顺序表类中有数据成员length，它显式的是记录线性表的长度，而链表类中没有length。 如要了解链表中有效数据元素的个数（即线性表的长度）还需编写一个函数来统计。 插入的位置i取值仍然是有限制的。它的正确范围（0 i = length + 1），因length 未知而无法显式的进行判断。,NCU-ZQP,55,插入的位置 i取值的正确范围的保障,当i n+1： while()循环会执行到：p= =NULL，q指向最后一个数据结点，因为k记数也达到n+1，k不等于i，也执行else语句输出：n i1,或 i太大，不存在。,NCU-ZQ

35、P,56,2.3.3 链表的插入和删除 2删除,在讨论链表删除的算法之前，先来看单链表中删除结点的基本操作。 （1）删除p所指向结点的后继结点（结点存在）。 假设要删除线性表中p所指向结点（元素a）的后继结点（元素b），如图：,语句组： q=p-next; /让q指向p的后继结点 p-next=q-next; /修改指针，绕过q结点 delete q; /删除q结点 ,NCU-ZQP,57,（2）删除p所指向的结点。 要删除表中p所指向的结点（元素），应先找到p的前驱结点q。这就需要组织while循环让q从链表头部q=head向后查找，直到q-next=p为止，然后进行删除操作。 语句组如下：

36、 q=head; while (q-next!=p) q+; /让q向后找p的前驱结点 q-next=p-next; /修改指针，绕过p结点 delete p; /删除p结点 ,NCU-ZQP,58,（3）在已知的线性表中，删除第i个数据元素结点，返回元素的值。 -链表删除典型算法,，在此作为链表类的公有成员函数来实现。在线性表的第i个位置进行插入，是指链表中有效数据元素结点的位置，头结点不包含在内。,已知条件是数据结点的位置i（或称序号）。为了删除第i位置的数据结点，需要设置指针p从第一个数据元素（p=Head-next）向后查找，头结点不包含在内。另外还需要一个辅助指针q作为p的前驱结点指

37、针紧跟p指针，q的初始值是q=Head。当它们不断向后移动达到确定位置后，即可进行删除操作，如图：,NCU-ZQP,59,单链表删除的典型算法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 删除结点成功。endl; else coutn i1,或 i太大，i不存在。e

38、ndl; x=-1; return x; ,NCU-ZQP,60,链表删除算法的说明,由于算法的已知条件是数据结点的位置i（或称序号），因此，函数仅有一个形参： ElemType LinkList:delet(int i) 本函数有返回值，通过return x;语句获取被删除结点的数据值。 由于链表中不显式存储线性表长度，删除位置i取值正确范围也不是显式判断（0i=length）。但上述算法能够隐含地保证删除位置i的正确取值。,NCU-ZQP,61,删除的位置 i取值的正确范围的保障,当i n： q会指向最后一个数据结点，而p为空，所以执行else语句输出提示：n i1,或 i太大，不存在。,

39、NCU-ZQP,62,3单链表插入和删除算法的时间复杂度分析,在顺序存储结构的线性表中插入/删除一个元素时会大量移动数据元素，其时间复杂度为O(n)。而在链表中插入/删除一个元素时却不大量移动数据元素(只移动指针)，其时间复杂度可以视为O(1)。如果每个数据元素占用字节数比较多，链表结构在时间方面具有明显优势。 但是，顺序结构可以直接存取，其时间复杂度可以视为O(1)。而链表结构则需设一指针从链表的开头向后查找，如果将指针的移动视为影响时间效率的主要因素，则时间复杂度可以视为O(n)。,NCU-ZQP,63,2.3.4 单链表的其他运算,单链表除了上述两种基本运算外，还有其他一些不同的或较为复

40、杂的运算。这些算法可以作为类的函数成员实现。 主要介绍： 1根据数据元素的值进行插入/删除 2单链表的逆置 3两条单链表的合并,NCU-ZQP,64,1根据数据元素的值进行插入/删除,（1）在线性表中值为x的元素前插入一个值为y的数据元素。如果值为x的结点不存在，则将y插在表尾，如图。,NCU-ZQP,65,根据数据元素的值进行插入算法：,void LinkList:insert2(ElemType x, ElemType y) NodeType *p,*q,*s; s=new NodeType; s-data=y; q=head; p=q-next; while( p!=NULL) /插入新

41、结点 ,NCU-ZQP,66,根据数据元素的值进行删除,（2）删除线性表中值为x的数据元素，输出“YES！”；如果x不存在，输出“NO！”。 为了查找值为x的结点，设p从头找起； 为了删除该结点，设q指向p的前驱结点；,NCU-ZQP,67,根据数据元素的值删除算法：,void LinkList:delet2(ElemType x) NodeType *p,*q; q=head; p=q-next; while(p!=NULL) ,NCU-ZQP,68,2单链表的逆置,单链表的逆置方法不唯一。在此，介绍利用在头结点和与之相邻的数据结点之间不断插入后边元素结点的方法，来实现链表逆置，如图所示。,

42、NCU-ZQP,69,链表逆置算法2.8：,void LinkList:nizhi() NodeType *h,*p, *q; h=Haed; /Haed是链表类的私有数据成员 p=h-next; h-next=NULL; /暂时将头结点与后边数据结点断开 while (p!=NULL) /不断地在头结点之后插入结点 q=p-next; p-next=h-next; h-next=p; p=q; ,NCU-ZQP,70,3两条单链表的合并,单链表的合并具有多种不同的方式，一种方式是将两个有序表合并成为一个新的有序表，还有一种方式是将两个线性表的元素间隔交叉合并等。这里介绍两个非递减有序表的合并

43、 两个单链表的合并涉及两个类对象，算法中是将第1条链表作为基础，将第2条链表合并进来，最终结果就在第1条链之中。具体实现见算法2.9。,NCU-ZQP,71,单链表合并算法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 ,NCU-ZQP,72,下面是一段调用程序：,int main() LinkList ha,hb; cout 建立第1条链表，注意数据递增

44、有序！：endl; ha.creat1(); cout 建立第2条链表，注意数据递增有序！：endl; hb.creat1(); ha.merge(hb); /以hb为实參，调用合并链表的函数 ha.Display(); /输出ha新链表 学习算法不仅要掌握算法本身的设计技能，也需要将算法函数放在完整的源程序系统之中认识理解。,NCU-ZQP,73,2.4 循环链表和双向链表,线性表的存储结构除单链表之外，还可以有循环链表和双向链表。单链表是循环链表和双向链表的基础。,NCU-ZQP,74,2.4.1 循环链表,将单链表的最后一个结点的指针指向链表的表头结点，形成一个循环链表，如图所示。 使用

45、头指针h，也使用尾指针r，操作更方便。 优点：从表中任一结点出发均可找到表中其他结点。,NCU-ZQP,75,两条循环链表连接的语句组如下：, B-next=A-next; A-next=HB-next; delete HB; /释放B表附加头结点 A=B; /A链尾指针A指新尾结点 时间复杂度为O(1),NCU-ZQP,76,2.4.2 双向链表,双向链表中的某个结点，可以直接找到它的前驱和后继结点。无论利用向前这一链还是向后这一链，都可以遍历整个链表，如果有一根链失效了，还可以利用另一根链修复整个链表。,结点结构如下： typedef char ElemType; struct NodeT

46、ype2 ElemType data; NodeType2 *next, *prior; ; NodeType2 *p, *q, *s;,NCU-ZQP,77,假设结点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的结点。,NCU-ZQP,78,语句组： p-prior-next=p

47、-next; /对应图中上方的虚线指针 p-next-prior=p-prior; /对应图中下方的虚线指针 delete p; ,2在双向链表中删除一个p结点。,由此可见，在循环链表、双向链表中进行插入或删除操作比较方便。,NCU-ZQP,79,2.4.3 顺序结构与链表结构的分析比较,用顺序的方式存储线性表： 1.内存的存储密度高，在结点等长时，可随机存取结点； 2.对顺序表的插入和删除往往造成大量信息的移动，效率比较低。 3. 顺序表要求占用连续的存储空间，存储分配只能预先进行。如果插入操作超出预先分配的存储区间，需要临时扩大是困难的。,NCU-ZQP,80,2.4.3 顺序结构与链表结

48、构的分析比较,采用链表存储结构可克服上述不足， 1.它适合于需要频繁插入和删除元素的线性表，不会大量移动数据元素。 2. 也适合于存储空间大小不能预先确定的线性表。可以随时分配和释放存储空间。 3. 链表结构不能随机存取结点中的数据，而需要在链表上先进行查找，然后进行存取操作。,NCU-ZQP,81,2.5 一元多项式相加问题,一元符号多项式的相加操作是线性表处理的典型用例。数学上一个一元多项式如下： 称p为x的n阶多项式，aixi是多项式的某个单项（0in），其中x为自变量，ai为系数，i为自变量的指数。已知有两个一元多项式A和B： 将这两个多项式相加得一个新的多项式C：,NCU-ZQP,8

49、2,2.5.1 多项式的链表存储结构,一个多项式可以采用一条链表来表示。每个结点对应于多项式的一个项，其结点的结构如下： struct Lpoly int coef ; /自变量的系数 intexp ; /自变量的指数 Lpoly *next; /指向下一结点的指针 ; 每个多项式的链表由多个单项的结点组成，高指数的项（高次幂）结点在链表头部，低指数的项（低次幂）结点在链表的后部。A，B两个多项式的链表结构如图所示。,NCU-ZQP,83,2.5.2 多项式相加的实现,一个链表中结点的顺序按照x的指数递减排列。两个多项式相加实质上是两个有序链表的合并操作。 为了实现两个多项式相加，现设C链表为

50、A、B链表相加后的新链表。为了节省内存资源，以A链表为基础将B链表的结点合并到A链表中。在此，设C链表头指针为pc，令其指向pa(pc=pa)，这样以pa链表为基础进行合并操作，最终的结果就是这条以pc为头指针的链表。,NCU-ZQP,84,多项式加法（链表合并）的方法,为了进行多项式加法运算，设置p，q两个指针变量分别指向pa，pb两个链表的第一个数据元素结点。 然后对p，q两个结点的指数域进行比较： 1. 两个结点的指数相同，则结点的系数相加。新的系数非零，则连入第3条链表C；否则跳过这两个结点。 2. 两个结点的指数不同，将指数较大的结点连入C表。,NCU-ZQP,85,初始状态 第1次处理后 第