线性表知识小结1.ppt

1、线性表知识小结,线性结构的基本特点,是由n(n=0)个结点组成的有穷序列. 第一个，最后一个，(直接)前驱 (直接)后继 一个结点代表一个数据元素,通常要求同一个线性结构中的所有结点所代表的数据元素具有相同的属性(比如:数据项个数相同;对应数据项的类型相同) 所含结点的个数称为线性表的长度(表长),表长为0的线性表称为空表.,线性表的顺序实现-顺序表,基本思想：按逻辑关系来决定排列顺序，实际就是一维数组，数组的下标可以看成是元素的相对地址。逻辑上相邻的元素的物理位置必紧邻。 存储特点： 优点：可随机存取(访问)； 缺点：插入和删除操作时，需移动大量元素 需事先确定表的容量 容易产生“碎片”,顺

2、序映像的 C 语言描述,typedef struct SqList; / 俗称 顺序表,#define MAXSIZE 100 / 线性表存储空间的分配量，即数组长度,ElemType elemMAXSIZE; /存放线性表的数组,int length; / 当前长度,Status InitList_Sq( SqList,算法时间复杂度：,O(1),L.length = 0; return OK;,int Locate (SqList L, ElemType x) / 在顺序表中查询第一个等于x的数据元素， / 若存在，则返回它的位序，否则返回 0 / Locate,O( L.length )

3、,基本操作是“进行两个元素之间的比较”， 若存在,比较次数是1-L.length,否则为L.length，算法的时间复杂度为：,i = 1; / i 的初值为第 1 元素的位序,while ( i=L.length),if (i = L.length) return i; else return 0;,Status Locate (SqList L, int i, ElemType ,else e=L.elemi-1; return OK; ,Status ListInsert(SqList j=i ; j - - ) L.elemj=L.elemj-1; / 插入位置及之后的元素右移 L.e

4、lemi-1 = e ; / 插入e +L.length; / 表长增1 return OK;,if (iL.length+1|L.length=MAXSIZE) return ERROR; / 插入位置不合法,Status ListDelete_Sq (SqList / ListDelete_Sq,算法时间复杂度为:,O( L.length),长度为n的顺序表中，等概率情况下，插入一个元素的平均移动元素次数为n/2，删除一个元素的平均移动元素次数为（n-1）/2，其时间复杂度都为O（n）。,插入算法时间复杂度分析： 考虑移动元素的平均情况,插入位置,需要移动的结点次数,1,n,2,n-1,n

5、,1,n+1,0,平均次数:,(1+2+n-1+n)/(n+1) =n/2,T(n)=O(n),线性表的链式存储-单链表,基本思想：用一个指针表示结点间的逻辑关系。每个结点的存储单元都分为两部分：一部分存放结点的数据，另一部分存放指向结点后继结点的指针。 存储特点： 优点：对任何位置进行插入和删除操作只需修改指针；不需要预先分配空间； 缺点：顺序存取（访问）的结构（不能从当前结点出发访问到任一结点）,typedef struct LNode ElemType data; / 数据域 struct LNode *next; / 指针域 LNode, *LinkList;,结点和单链表的 C 语言

6、描述,LinkList L； / L 为单链表的头指针,带头结点的单链表sq为空的条件： sq-next=NULL 不带头结点的单链表sq为空的条件： sq=NULL 在单链表中，删除某一指定结点时，需找到该结点的前驱结点。 在单链表中设置头结点的作用： 不管单链表是否为空表，头结点指针均不空，并使得对单链表的操作在各种情况下统一（第一个结点） 。,在单循环链表中通常设置尾指针（指向最后一个结点）比设置头指针好 从一个具有n 个结点的单链表中查找其值等于x的结点时，在查找成功情况下平均需比较 个结点 思考：对于一个有n个结点的单链表，在已知p所指结点后插入一个结点的时间复杂度是？在给定值为x的

7、结点后插入一个结点的时间复杂度是？,（n+1）/2,使得查找开始结点和终端结点都很方便， 其查找时间都是O（1）；,Status GetElem_L(LinkList L, int i, ElemType j = 1; / p指向第一个结点，j为计数器,while (p ?）,if ( !p | ji ) return ERROR; / 第 i 个元素不存在 e = p-data; / 取得第 i 个元素 return OK;,s = (LinkList) malloc ( sizeof (LNode); / 生成新结点 s-data = e; s-next = p-next; p-next

8、= s; / 插入 return OK;,s,p,在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。,q = p-next; p-next = q-next; e = q-data; free(q);,p,q,操作 ClearList(,算法时间复杂度：,O(ListLength(L),建立单链表头插法:,void CreateList_L(LinkList L-next = NULL; / 先建立一个带头结点的单链表,for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf(

9、/ 插入 ,建立单链表尾插法:,r-next = p; r =p;,void CreateList_L(LinkList L-next = NULL; r = L ; / 先建立一个带头结点的单链表,for (i = 0; i data); / 输入元素值 r-next = p; / 插入 r =p; /r指向新的尾结点 ,r-next = NULL ; /尾结点的指针域为空,链表的遍历,void printlist ( LinkList L ) LinkList p = L-next ; while(p) printf ( p-data ) ; p=p-next ; ,线性表实现方法的比较,

10、实现不同 顺序表方法简单，各种高级语言中都有数组类型，容易实现；链表的操作是基于指针的，相对来讲复杂些。,存储空间的占用和分配不同 从存储的角度考虑，顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。而链表是动态分配存储空间的，不用事先估计存储规模。可见对线性表的长度或存储规模难以估计时，采用链表。,线性表运算的实现不同,按序号访问数据元素，使用顺序表优于链表。,插入删除操作，使用链表优于顺序表。,线性表两种存储的比较,最后一个结点的指针域的指针又指回头结点（第一个结点）的链表，整个链表形成一个环。

11、,a1 a2 . an,1. 循环链表,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,其它形式的链表,求表长的操作,int getlen ( linklist L ) int i =0; linklist p = L - next ; while ( p!=L) i + +; p=p-next; return i ; ,与单链表操作比较,Initlist（） 初始化时，头结点的next不为NULL，而是指向自身。 求表长：while中的条件改为 p！=L； 插入、删除操作的基本语句无变化 操作基本一致，通常遇到的循环条件不是判断指针p或p

12、-next 是否为NULL,而是判断它们是否等于头结点,2. 双向链表 ( 用两个指针表示元素间的逻辑关系 ),typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;,L,带头节点的空的双向链表,头结点没有前驱；最后一个结点没有后继；,双向循环链表,空表,非空表,a1 a2 . an,双向链表的操作特点：,“查询” 和单链表相同。,“插入” 和“删除”时需要同时修改两个方向上的指针。,s

13、-next = p-next; p-next = s; s-next-prior = s; s-prior = p;,p,s,插入,删除,q=p-next; p-next = q-next; p-next-prior = p;e=q-data; free(q);,q,p,本章小结,1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。,2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。,3.能够从时间和空间复杂度的角度综合比较线性表两种存

14、储结构的不同特点及其适用场合。,例1：设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C。 其中B表的结点是A表中值小于零的点，而C表中的结点为A表中值大于零的结点。（链表A的元素类型为整型，要求B、C表使用A表的结点，即不再开辟新的结点空间）。,void split ( linklist ,例2：在非递减有序的顺序表中插入元素x，使其仍保持有序。,分析: 从后向前查找插入位置 ,同时向后移动大于x的元素,status Orderlistinsert(sqlist ,例3：有两个带头结点的循环单链表ha和hb，设计一个算法将它们首尾合并成一个带头结点的单链表hc，要求不再开辟新

15、的元素空间。,过程：令hc指向ha，再用一指针p遍历链表ha，找到ha 的最后一个结点，然后将hb（除头结点之外的其他结点）链在其后，再找到hb最后一个结点,修改其后继为空.最后释放hb。,void link(linklist ,一元多项式的表示,在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn),一元多项式,但是对于形如 S(x) = 1 + 3x10000 2x20000 的多项式，上述表示方法是否合适？,一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem 其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 em = n,可以下列线性表表示： （p1, e1）, (p2, e2