1,数据结构,第2章 线性表 第2讲,2,第2章 线性表,线性结构是最简单、最基本的数据结构，本章讨论线性表的基本概念、存储结构以及相关运算。 主要内容： 线性表的基本概念 线性表的顺序存储结构及实现 线性表的链表存储结构及实现 线性表的应用,3,本章分为（45）讲,第1讲 2.1 线性表的基本概念 2.2 线性表的顺序存储结构及实现（2.2.12.2.3）,第3讲 2.3.3（删除）2.3.4 2.4 循环链表和双向链表,第2讲 2.2.4 线性表的其他运算 2.3 线性表的链表存储结构及实现 2.3.12.3.3（插入）,第4讲 2.5 一元多项式相加问题 小结,供教师参考,4,2.2.4 线性表的其他运算,除前面两种基本运算外，还有一些较复杂的运算。 class SqList /代码与前文类Sqlist的定义完全同前； public: /以下是增加的两个公有函数成员 void Insertdz( ElemType x); /有序表插入 void Deletaz(ElemType x); /有序表删除 ;,5,1在非递减有序表中插入一个数据元素x，使线性表仍保持非递减有序。,前提是线性表中数据元素已经有序。已知条件是将要插入的数据x，插入的位置需要程序来查找。 已知有线性表：（14，21，21，38，46，80） 若x=30，结果：（14，21，21，30，38，46，80） 若x=10，结果：（10，14，21，21，38，46，80） 若x=99，结果：（14，21，21，38，46，80，99） 因插入的数据元素x值不同其插入位置也不同。插入位置怎样确定？,6,1在非递减有序表中插入一个数据元素x，使线性表仍保持非递减有序。,算法2.3 void SqList:Insertdz( ElemType x) int i=length-1; while(i=0 算法从表尾元素开始与x比较，当elemix且未到表头元素时继续循环。一边比较一边向后移动数据元素。 算法的主要考虑数据元素的移动，时间复杂度为O(n)。 若采用从表头元素开始与x比较的方法，其效率如何？,7,2在非递减有序表中删除所有值为x的元素。,已知条件是某数据元素x的值。以elemi与x是否相等为判断条件来查找删除的位置，然后删除所有值为x的元素。 算法2.4 void SqList:Deletaz(ElemType x) int i=0,j; /查找第一个x值出现的位置 while(ilength /表长减1 ,8,删除非递减有序表中所有值为x的元素，算法分析,本算法含有两个并列的循环结构，由于影响时间效率的主要因素是大量数据元素的移动，因此前面关于下标i的循环忽略不计。 else中是一个二重循环，如果忽略x重复出现的次数，主要依据是移动数据元素的for循环，经估算元素的平均移动次为(n1)/2，因此算法的时间复杂度是O(n)。 综上所述，线性表采用顺序存储结构在插入、删除时，需大量移动数据元素，效率较低。由于是静态存储结构，需预先定义大小确定的数组，容量有限。,9,2.3 线性表的链表存储结构及实现,采用顺序存储结构的线性表，在频繁进行插入、删除操作时会大量移动数据元素，效率较低。同时，顺序存储必须占用一批地址连续的存储空间，存储分配只能预先进行。但是，它适于直接（随机）存取操作。 本节将讨论线性表的另一种存储结构链表存储结构，由于它不要求逻辑上相邻的数据元素在物理位置上也一定相邻，因此，它没有顺序存储结构所具有的弱点。,10,2.3.1 单链表与指针,对于程序设计基础较好的读者，可以越过本节直接学习2.3.2节。 线性表的链表存储结构可以利用内存空间中一组任意的存储单元来存储线性表的各个数据元素，这些存储单元地址可以连续也可不连续。那么怎样根据第i个数据元素找到第i+1个数据元素呢？ 为了弄清单链表的概念，首先需回顾指针的基本概念。,11,1指针和指针变量,所谓指针是指计算机内某个存储单元的地址。 一个用来存放指针（地址）的独立变量称作指针变量。 如果有：int *a; int m=6; 就允许：a= 那么name指针就是该字符串的首地址。 虽然指针变量可以存放存变量单元的地址，但是根据其数据类型声明的不同，其地址性质是不同的。,12,在存储和表示线性表时，一个结点用来存储线性表的一个数据元素。 每个结点一般分为两个域：数据域；指针域。 一个结点定义为结构体类型： typedef int ElemType; struct NodeType ElemType data; /数据域，存放数据信息 NodeType *next; /指针域，存放同样结构体类型结点的首地址 ;,2结点,13,对结点的访问和处理常通过指针变量。 用来存放结点首地址的指针变量，可用下列语句来声明： NodeType *h,*s; 变量h,s被定义为指针型之后，并没有指向任何实际结点，即指针变量中还没有某个实际结点所占空间的首地址值。 如何为指针变量提供一个结点的首地址？,2结点,14,让指针变量p指向一个新分配的结点，语句如下： p = new NodeType; 系统分配了一个结点所需的存储空间，并且将首地址赋值给指针变量p。 可以通过赋值语句： s=p； 让指针变量s存放与p指针之中相同的地址，也称s和p指向同一个结点，如图所示。,3结点的动态申请和释放,15,结点s的数据域用s-data来表示，根据前文定义的数据域是整型的，像一般的整型变量一样可以在输入/输出、赋值语句中使用。例如： s-data=110; /或者cins-data; coutdata; /这样输出的结果就是110 结点s的指针域用s-next来表示，可以用来存放另外一个结点的首地址。根据需要也可以使其为空，如： s-next=NULL；,3结点的动态申请和释放,16,要把上述结点s释放、归还给系统，则必须用命令来实现： delete s; 值得注意的是，这里释放的只是数据元素结点所占用结点的存储单元，而指针变量h,s本身仍然存在，只是h,s之中不再有具体地址内容，什么结点也不指向了。,3结点的动态申请和释放,17,多个结点连接在一起可以构成一个链表。由于每个结点只包含一个指针域，故称这种链表为单链表。一个非空线性表(a1，a2，a3)对应的单链表如图所示。,4链表,详细讲解,18,5指针变量的主要操作,详细讲解,19,2.3.2 单链表类定义,在面向对象的程序设计中，链表被设计成一个类。链表类在不同教科书有不同的设计。 链表有一种简明的设计，将结点设计为一个结构体类型，再将该链表的头指针Head作为链表类的数据成员。 结点结构的定义： typedef int ElemType; struct NodeType /结点类型定义 ElemType data; NodeType *next; ;,20,头指针Head可唯一确地定一个单链表。,对链表中各数据结点的访问都将从头指针Head开始查找。 将一个NodeType类型结点的指针变量Head作为单链表的头指针。 单链表类的组成： 将头指针Head作为类LinkList的私有数据成员； 将重要的算法设计成类的若干成员函数。,21,/链表类定义 class LinkList private: NodeType *Head; /链表头指针 public: LinkList(); /构造函数，初始化空链表 LinkList(); /析构函数 void creat(); /初建一个非空链表 void Display(); /输出链表的数据元素 void insert(int i,ElemType x); /插入 ElemType delet(int i ); /删除第i个结点 ; /类定义结束,22,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; cout“n 链表已经删除。“endl; delete Head; /最后释放头结点的空间 Head=NULL; ,23,算法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 cout“n 插入结束。链表建成。“endl; ,24,/输出显示链表内容 void LinkList:Display() NodeType *p; p=Head-next; /p指向第一个数据结点 while(p!=NULL) coutdatanext; /p移向下一个结点 coutendl; /p为空，输出完毕 头指针Head必须保持不变，需另设一个指针变量p从第一个数据结点向后逐步移动，边输出边移动p直至表尾。,25,上述函数不是单链表的典型算法，之所以列出是为了配合典型算法，构成体系比较完整的类设计。 为了在实际中应用单链表，还必须能够将算法和函数放在程序系统中去认识和设计编码。 在主函数中声明和创建LinkList链表类对象h，同时初始化h为空链表。然后调用建立链表的函数输入数据，接着调用输出函数将链表内容输出显示。 int main( ) LinkList h; h.creat(); /通过对象h调用建立函数 h.Display(); /通过对象h调用输出函数 _getch(); return 0; ,26,2.3.3 链表的插入和删除,为了规范单链表的表示和运算，约定使用附加头结点，在一般情况下均默认带有附加头结点，简称头结点。所谓头结点是指该结点的数据域并不存放线性表的任何数据元素，一个空表如左图，非空链表如右图。,单链表是数据结构学习的重要基础。下面从最基本的插入、删除的语句组和图示入手，介绍链表类的插入和删除算法。,27,1插入,在讨论插入算法前，首先看单链表中插入结点的基本操作。 （1）假设已知p指针指向的结点，在p结点之后插入一个元素x，操作如图2.8所示。,相关操作的语句组如下： s=new NodeType; /分配新的结点s s-data=x; s-next=p-next; /插入s结点 p-next=s; /注意，两条修改指针的语句顺序不可颠倒。,28,（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结点 /在已知结点的“前”边进行插入的操作较为复杂。,29,（3）在已知的线性表的第i个位置插入数据