第3章1-3-线性表

1、线性表是一个含有线性表是一个含有n n（n0）个数据元素的有限序列。个数据元素的有限序列。线性表长度线性表长度D=ai |ai ElemSet, i=1,2,.,n, n=0R1=|ai-1, ai D,i=2,3,.,n . DataType l 线性表的插入是指在表的第线性表的插入是指在表的第i个位置上插入一个位置上插入一个值为个值为 x 的新元素，插入后使原表长为的新元素，插入后使原表长为 n的表的表 (a1，a2，. ，ai-1，ai，ai+1，. ，an) 成为表长为成为表长为 n+1 表表: (a1，a2，.，ai-1，x，ai，ai+1，.，an) li 的取值范围为的取值范围为

2、1 i n+1 012345678MAXSIZE-1a1a2a3a4a5a6a7a8a9123456789i数据数据下标下标Last0123456789MAXSIZE-1a1a2a3a4a5xa6a7a8a912345678910在第在第6个（个（i=6）的位置插入）的位置插入XInsertSListLiXL及插入是否成功标志及插入是否成功标志Int InsertSList ( *L,int i,DataType x) /在第在第i个元素之前插入一个新结点个元素之前插入一个新结点 int j; if (iL-last+2) return (-1); if (L-last=MAXSIZE-1)

3、return (-1); for (j=L-last;j=i-1;j-) L-dataj+1=L- dataj; L- datai-1=x; L-last+; return 1;2) 1(11) 1(1111ninninPEniniiin说明：在顺序表上做插入操作需移动表中一半的说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为数据元素。显然时间复杂度为(n)。 l 线性表的删除是指在表的第线性表的删除是指在表的第i个位置上删除一个位置上删除一个元素，删除后使原表长为个元素，删除后使原表长为 n的表的表 (a1，a2，. ，ai-1，ai，ai+1，. ，an) 成为表长为成

4、为表长为 n-1 的表的表: (a1，a2，.，ai-1，ai+1，.，an) li 的取值范围为的取值范围为1in012345678MAXSIZE-1a1a2a3a4a5a6a7a8a9123456789i数据数据下标下标Last01234567MAXSIZE-1a1a2a3a4a5a7a8a912345678删除第删除第6个元素（个元素（i=6）ListDeleteLiL及删除是否成功标志及删除是否成功标志int ListDelete (L，int i) /删除第删除第i个元素个元素int j; if (iL-last+1) return (-1); if (L-last=-1) retu

5、rn (-1);for (j=i;jlast;j+) L-dataj-1=L-dataj; L-last-; return 1;说明：在顺序表上做删除操作需移动表中一半的数据说明：在顺序表上做删除操作需移动表中一半的数据元素。显然时间复杂度为元素。显然时间复杂度为(n)。 1111E()()2nndeiiinp nininl按序号查找按序号查找: 要求查找线性表中第要求查找线性表中第i个数据元素个数据元素(i 的取值范围为的取值范围为1in): (a1，a2，. ，ai-1，ai，ai+1，. ，an) l按内容查找按内容查找: 要求查找线性表中与给定值要求查找线性表中与给定值x相等相等的数据

6、元素，其结果是：若在表中找到与的数据元素，其结果是：若在表中找到与x相相等的元素，则返回该元素在表中的序号等的元素，则返回该元素在表中的序号i ；若；若找不到，则返回一个找不到，则返回一个“空序号空序号”，如，如-1: (a1，a2，. ，ai-1，ai (x) ，ai+1，. ，an)012345678MAXSIZE-1a1a2a3a4a5a6a7a8a9123456789i数据数据下标下标Last01234567MAXSIZE-1a1a2a3a4a5a6a7a812345678第第6个元素值为个元素值为x（i=6）GetData LxiInt GetData (L， DataType x)

7、 /查找值为查找值为x的元素序号的元素序号iint i=0; if (L.last=-1) return (-1);while (i=L.last &L.datai!=x) i+; if (inext=p-next; p-next=s；ix hixhl创建新结点创建新结点s(x)；l查找查找i结点的地址结点的地址p；l如果不存在，将如果不存在，将s结点插入表尾；结点插入表尾；l将将s连接到链表中连接到链表中p结点之后；结点之后；pq=p-next; p-next=q-next; free(q);qxhxh及删除是否成功标志及删除是否成功标志 p-next=q-next; free(q);dat

8、anextpriortypedef struct DNode DataType data; struct DNode *prior,*next; DLinkList;s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; pl方法简单方法简单,各种高级语言中都有数组各种高级语言中都有数组,易实现。易实现。l不用为表示结点间的逻辑关系而增加额外的存不用为表示结点间的逻辑关系而增加额外的存储开销。储开销。l顺序表具有按元素序号随机访问的特点。顺序表具有按元素序号随机访问的特点。l在顺序表中做插入、删除操作时，平均移动大在顺序表中做插入、删除操作时

9、，平均移动大约表中一半的元素，因此对于表长较大的顺序约表中一半的元素，因此对于表长较大的顺序表效率低。表效率低。l需要预先分配足够大的存储空间，估计过大，需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。小，又会造成溢出。 链表的优缺点恰好与顺序表相反。链表的优缺点恰好与顺序表相反。v线性表的长度：线性表的长度：由于顺序表的存储空间是静态分配的，在程序执由于顺序表的存储空间是静态分配的，在程序执行过程中其占用的存储空间固定不变，而链表是动态分配存储空行过程中其占用的存储空间固定不变，而链表是动态分配存储空间的，所以当对线性表的长度或存储规模相对固定时，采用顺序间的，所以当对线性表的长度或存储规模相对固定时，采用顺序表；反之，采用链表。表；反之，采用链表。v 线性表要进行的操作：线性表要进行的操作：顺序表连续顺序存放，随即存取，所以适顺序表连续顺序存放，随即存取，所以适合频繁查找的操作。但是当线性表要进行大量的删除、插入运算合频繁查找的操作。但是当线性表要进行大量的删除、插入运算时，用顺序存储会导致大量的元素移动，所以易采用链表。时