数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第二章线性表

数据结构,第二章 线性表,第二章 线性表,线性表,知 识 点 线性数据结构的基本特征和基本运算 顺序表的插入与删除运算 链表的插入与删除运算 难 点 顺序表的溢出的判断 利用本章的基本知识设计有效的算法解决与线性相关的应用问题,第二章 线性表,要 求 熟练掌握以下内容： 线性表的基本运算 了解以下内容： 线性表运算时间复杂性分析,第二章 线性表,目录,2.1 线性表及其运算 2.2 顺序存储结构 2.3 链表存储结构 2.4 应用实例及分析 小 结 习题与练习,第二章 线性表,2.1.1 线性表（Linear List）,线性表是由有限数目的相同类型元素组成的序列。 表中的数据元素，除了第一个和最后一个以外，都有一个且只有一个前驱元素，同时也都有一个且只有一个后继元素； 第一个元素只有一个后继元素而无前驱元素；最后一个元素只有一个前驱元素而无后继元素。 线性表的元素个数n称为这个表的长度，当n=0时，这个表叫做空表。,第二章 线性表,线性表在计算机内存中采用各元素顺序存储的方式，这种存储结构叫做向量。 每个线性表元素叫做这个向量的一个分量。 如果已知线性表第一个元素的地址和每个元素占用的存储单元数，由任一元素的序号就可以计算出该元素在内存中的地址。 在编程时以一维数组表示线性表最简单，用的也最普遍。,第二章 线性表,2.1.2 线性表的运算,对于给定的线性表，可进行如下的基本运算： 1. 求线性表的长度n； 2. 在第i个数据元素前面插入一个新的数据元素； 3. 删除第i个数据元素； 4. 存取或更新线性表第i个元素； 5. 将两个或两个以上的线性表合并成一个线性表； 6. 将一个线性表拆成多个线性表； 7. 将线性表中各数据元素按某个域值（如关键字）递增或递减的顺序重新排列； 8. 在线性表中查找满足某种条件的数据元素；,第二章 线性表,1. 数据元素的插入(insert),设用一个一维数组An表示此线性表，原来有m个元素（mn），元素值已给定。 规定数组的下标从1开始，即这里数据元素对应的数组下标从1到n。 要求在第i个元素前插入一个新数据元素，值为G，因原线性表的数据元素是连续排列的，中间没有空单元，所以第i个元素及其后面的各元素均需向后移动一个单元位置，这样才能将G插入到i位置，且元素总数由m增加为（m+1）。,第二章 线性表,插入函数,void insert(A, int n, m, i, G) int j; if (in+1) printf(“i值错！n”); else for (j=m;j=i;j-) Aj+1=Aj; /*将第i个元素及其后面的元素后移*/ Ai=G; m+; /*线性表长度加1*/ ,第二章 线性表,插入函数分析,在循环语句中，当i=1时，须循环m次，表示元素插入线性表头的前面，则原线性表中m个元素均须向后移动一个单元，这是最不利的情况。 当i=m+1时，则循环一次也不进行，这时元素直接插入到线性表尾的后面，所以线性表的所有m个元素均不移动，这是最好的情况。,第二章 线性表,2. 数据元素的删除(Delete),设用一个一维数组An表示此线性表，原来有n个元素，元素值已给定。 要求删除第i个数据元素，由于线性表元素在数组中必须连续排列，中间不能有空单元，故将此元素删除后，它后面的所有元素都需要向前移动一个单元，且数据元素总数由原来的n减少到n-1.,第二章 线性表,删除函数,void delete(A,int n,i) int j; if (in) printf(“i值错！n”); else for (j=i;j=n;j+) Aj=Aj+1; n-; ,第二章 线性表,删除函数分析,在循环语句中，当i=1时，需循环(n-1)次，这是要删除线性表表头元素，是最不利的情况； 当i=n时，则循环一次也不执行，只是将元素数目n比原来减少一个，而第n个数据元素不必再考虑，其余的各单元的元素均维持不变，这是最好的情况。,第二章 线性表,2.3.1 链表及其运算,知 识 点 单链表的结点形式、组织方法和特点 单链表的基本运算和相应的算法 循环链表的组织方法和基本运算算法 双链表的结点形式、组织方法和特点 双链表的基本运算和相应的算法 顺序表与链表比较，各自的优、缺点 链表的应用,第二章 线性表,难 点 双链表插入、删除运算的算法 利用链接结构的特点设计有效算法，解决与链表结构相关的应用问题 要 求 熟练掌握以下内容: 单链表的结构特点、基本运算并能设计简单算法 循环链表的结构特点、基本运算并能设计简单算法 双链表的结构特点、基本运算并能设计简单算法,第二章 线性表,链表及其应用目录,3.1 单链表及其运算 3.2 循环链表与双向链表 3.3 链表应用举例 3.5 应用举例及分析 小 结 习题与练习,第二章 线性表,1. 结点: 在链式存储结构中，结点不仅存放数据元素的值，还附加一个指针（链），用来指向该结点的直接后继结点。 其中，data部分称为数据域，用于存储线性表的一个元素，next部分称为指针域或链域，用于存放一个指针，即存放该结点的直接后继结点的地址。,2.3.2 单链表,第二章 线性表,所有结点通过指针的链接而构成的线性表称为单链表。线性表（a1，a2，an，）的单链表可直观地画成： head是单链表的头指针，指向开始结点a1, an是终端结点，其指针域为空，不指向任何结点。 一个单链表由头指针head唯一标识和确定，因此，可用头指针来命名单链表。,2. 单链表,第二章 线性表,假设线性表中数据元素的类型为datatype，单链表的类型定义如下： typedef struct node * pointer; struct node datatype data; pointer next; ; typedef pointer linklist; 一个结点是由两个域data和next组成的记录,data是结点的数据域，next是结点的链域。,3. 单链表的类型定义,第二章 线性表,4. 指针的概念,假设p是一个pointer类型，应正确区分指针型变量、指针、指针所指的结点和结点的内容这四个密切相关的不同概念： p的值（如果有的话）是一个指针，即是一个所指结点的地址 。 该指针（若不是NULL）指向的某个node型结点用*p来标识。 结点 *p是由两个域组成的记录，这两个域分别用pdata域和pnext域来标识，它们各有自己的值，pdata的值是一个数据元素，pnext的值是一个指针。,第二章 线性表,2.3.3 单链表的基本运算,1. 遍历(Traversal)：根据已给的表头指针，按由前向后的次序访问单链表的各个结点。 在实际应用中遍历是对单链表的最基本运算，例如，当要打印或显示出各个结点的数值域值、计算单链表的长度(即结点数目)或寻找某一个结点时都需要遍历单链表。 假设head是单链表的头指针，计算一个已建立好的单链表的结点个数的算法如下：,第二章 线性表,计算结点个数算法,int length(node *head) /*求表head的长度*/ int count=0; /*计数器置初值*/ node *p=head; /*p指向头结点*/ while (p!=NULL) p=p-next; count+; return(count); /*返回表长值*/ ,第二章 线性表,算法分析,此算法的关键是while循环语句，开始时p指针指向头结点，每一循环都修改指针值，让它指向下一个结点，同时将计数链表长度的变量count加1。 这样每循环一次就向后推移一个结点，直到p所指结点*p的链域值为NULL为止。 空指针NULL起标志的作用，若无此标志，尾结点链域的值为“无定义”，上述算法中的while语句在做最后一次判断时将出现“运行错”，这是应予避免的。,第二章 线性表,2. 插入,所谓插入是指在单链表中第i个结点(i0)之后插入一个元素为x的结点。 实现插入算法主要完成三个基本操作： 1) 在单链表上找到插入位置，即找到第i个结点。 可以用遍历的方法，即从表头起顺次访问单链表的结点，直至找到第i个结点。 2) 生成一个以x为值的新结点。 可通过C的库函数malloc(size)来产生。 3) 将新结点链入单链表中。 需要改变相关结点的指针 ，如下面的图所示。,第二章 线性表,假设指针p指向单链表中的第i个结点，指针s指向已生成的新结点，链入新结点的操作如下： 将新结点*s的链域指向结点*p的后继结点 (即s-next=p-next)； 将结点*p的链域指向新结点(即p-next=s)。,第二章 线性表,插入算法,void insert (node *head, int i, x) node *s,*p; int j; s=(node * )malloc(sizeof(node); /*生成新结点*/ s-data=x; if(i=0) /*如果i=0,则将s所指结点插入到表头*/ s-next=NULL; head=s; else p=head; j=1; /*查找第i个结点，由p所指向*/,第二章 线性表,插入算法续,while(p!=NULL ,第二章 线性表,3. 删除,当需要从单链表上删除结点时，就要通过删除运算来完成。 删除单链表上一个其值为x的结点的主要操作是： 1) 用遍历的方法在单链表上找到该结点； 2) 从单链表上删除该结点。 欲从单链表上删除一个结点，需修改该结点的前一个结点的指针，如下面的图所示。,第二章 线性表,假设指针q指向待删除结点的前一个结点，指针p指向要删除的结点，删除该结点的操作如下：将该结点的前一个结点*q的链域指向*p的后继结点（即q-next=p-next）。,第二章 线性表,删除算法,void delete(node *head, int x) node *p, *q; if (head=NULL) printf(“链表下溢！n”); /*判空*/ if(head-data=x) / *如表头结点值等于x*/ p=head; head=head-next; free(p); else q=head; /*从第二个结点开始查找*/ p=head-next;,第二章 线性表,删除算法续,while(p!=NULL ,返回,第二章 线性表,2.3.4循环链表,循环链表（circular linked list）是一种首尾相接的链表，将单链表表尾结点原来的空指针改为指向表头结点，就成为循环链表。 循环链表并不多占存储单元，但从循环链表的任一个结点出发都可以访问到此链表的每一个结点，因为当访问到表尾结点后又能返回到头结点。,第二章 线性表,1. 带头指针的循环链表,通常在循环链表的表头结点前面再加一个空结点,也叫空表头结点。 表空时空表头结点的指针指向其本身，如下面的图所示为空循环链表。 空表头结点除指针以外的数据域是没有用的，但为了将此结点与一般结点相区别，常常是将其赋以一个特别的数据，以与一般结点相区别。,第二章 线性表,2. 带尾指针的循环链表,另一种方法是不设头指针而改设尾指针，这样无论是找头结点还是尾结点都很方便。因为尾结点由尾指针rear来指示，则头结点的位置是rear-next-next。,第二章 线性表,3.3.5 双链表,双向链表中每个结点除了有向后指针外，还有指向其前一个结点的指针，这样形成的链表中有两条不同方向的链，因此从某一结点均可向两个方向访问。 双链表的结点形式为： 其中链域prior和next分别指向本结点的直接前趋和直接后继结点。,第二章 线性表,如果循环链表的结点再采用双向指针，就成为双向循环链表。,第二章 线性表,双链表较单链表虽然要多占用一些存储单元，但对其插入和删除操作以及查找结点的前趋和后继都非常方