第二章线性表知识小结.ppt

线性表知识小结 线性结构的基本特点 是由n(n=0)个结点组成的有穷序列. (直接)前驱 (直接)后继 一个结点代表一个数据元素,通常要求同一个线性结构中的所有结点所代表的数据元素具有相同的属性(比如:数据项个数相同;对应数据项的类型相同) 所含结点的个数称为线性表的长度(表长),表长为0的线性表称为空表. 线性表的顺序实现----顺序表 基本思想：按逻辑关系来决定排列顺序，实际就是一维数组，数组的下标可以看成是元素的相对地址。逻辑上相邻的元素的物理位置必紧邻。 存储特点： 优点：可随机存取(访问)； 缺点：插入和删除操作时，需移动大量元素 需事先确定表的容量 容易产生“碎片” 长度为n的顺序表中，等概率情况下，插入一个元素的平均移动元素次数为n/2，删除一个元素的平均移动元素次数为（n-1）/2，其时间复杂度都为O（n）。 线性表的链式存储----单链表 基本思想：用一个指针表示结点间的逻辑关系。每个结点的存储单元都分为两部分：一部分存放结点的数据，另一部分存放指向结点后继结点的指针。 存储特点： 优点：对任何位置进行插入和删除操作只需修改指针；不需要预先分配空间； 缺点：顺序存取（访问）的结构（不能从当前结点出发访问到任一结点） 带头结点的单链表sq为空的条件： sq-next==NULL 不带头结点的单链表sq为空的条件 sq==NULL 在单链表中,删除某一指定结点时,需找到该结点的前驱结点。 在单链表中设置头结点的作用： 不管单链表是否为空表，头结点指针均不空，并使得对单链表的操作在各种情况下统一。 在单循环链表中通常设置尾指针（指向最后一个结点）比设置头指针好 从一个具有n 个结点的单链表中查找其值等于x的结点时，在查找成功情况下平均需比较 个结点 思考：对于一个有n个结点的单链表，在已知p所指结点后插入一个结点的时间复杂度是？在给定值为x的结点后插入一个结点的时间复杂度是？ 已知sq是带头结点的非空单链表，且p指向的结点既不是第一个结点也不是最后一个结点，则写出下列语句序列： 删除*p的直接后继结点 删除*p的直接前驱结点 删除*p结点 删除第一个结点 删除最后一个结点 设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C。 其中B表的结点是A表中值小于零的点，而C表中的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表使用A表的结点， 即不再开辟新的结点空间） void split ( linklist lb , linklist lc , linklist la) { linklist p = la-next , r , s ; lb = ( linklist ) malloc ( sizeof ( lnode ) ); lc = ( linklist ) malloc ( sizeof ( lnode ) ); r = lb; s = lc; while ( p != NULL ) { if ( p-data 0 ) //将结点链入B表中 { r-next=p ; r=r-next ; } else if ( p-data 0 ) //将结点链入C表中 { s-next=p ; s=s-next ; } p = p -next; } r-next=NULL; s-next=NULL; free ( la ); } 在非递减有序的顺序表中插入元素x，使其仍保持有序。 分析: 从后向前查找插入位置 ,同时向后移动大于x的元素 status Orderlistinsert(sqlist L , ElemType e) { if (L.length = = MAXSIZE) return ERROR; for( i=L.length-1 ; i=0 L.elem[i]x ; i- - ) L.e