线性表PPT学习教案

1、会计学1第1页/共40页n其中：L为线性表名称，习惯用大写书写；nai为组成该线性表的数据元素，习惯用小写书写；n线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。第2页/共40页nstruct bookinfon int No; /图书编号nchar *name; /图书名称nchar *auther; /作者名称n.;n 第3页/共40页第4页/共40页第5页/共40页存 储 地 址 内 存 单 元.d a1d + L a2d + 2 L a3.d + ( i - 1 ) L ai.d + ( n - 1 ) L an. .图图2-1 线性表顺序存储结构示意

2、图线性表顺序存储结构示意图第6页/共40页1)*Ln顺序存储结构的特点n（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；第7页/共40页第8页/共40页第9页/共40页n p r i n t f (错);return(0); n for(j=L-last;j=i-1;j-)n L-dataj+1=L-dataj; /* 结点移动 */n L-datai-1=x;/*新元素插入*/n L-last+; /*last仍指向最后元素*/n return (1);/*插入成功，返回*/n 第10页/共40页动*/nL-last-; nr

3、eturn(1); /*删除成功*/n 第11页/共40页第12页/共40页1n1iis2n1)i(n1n1E第13页/共40页n顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。n1idl21ni)(nn1E第14页/共40页元素的操作时，会产生大量的数据元素移动；nl对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；nl线性表的容量难以扩充。第15页/共40页系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置

4、的信息。假设有一个线性表（a,b,c,d），可用下图2-2所示的形式存储：第16页/共40页存 储 地 址内 容直 接 后 继 存 储 地址1 0 0b1 2 0.1 2 0c1 6 0.1 4 4a1 0 0.1 6 0dN U L L.首 元 素 位 置图图2-2 线性表链式存储结构示意图线性表链式存储结构示意图第17页/共40页headd cba图图 2-3 单联表结构示意图单联表结构示意图第18页/共40页之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。如下图2-4所示：headd cba图图 2-4 带头结点的单链表结构示意图带头结点的单链表结构示意图第19页

5、/共40页第20页/共40页nLinkList H；第21页/共40页第22页/共40页n第23页/共40页n p=p-next; j+; n if (j=i) return p;n else return NULL;n 第24页/共40页n Lnode * p=L-next;n while ( p!=NULL & p-data != x)n p=p-next; n return p;n 第25页/共40页n s=malloc(sizeof(LNode); /*申请、填装结点*/n s-data=x; n s-next=p-next; /*新结点插入在第i-1个结点的后面*/n p-n

6、ext=sn return 1;n 第26页/共40页n printf(第i个结点不存在);return 0; n elsen s=p-next; /*s指向第i个结点*/n p-next=s-next; /*从链表中删除*/ n free(s); /*释放*s */n return 1;n 第27页/共40页head 图图2-7 带头结点的循环链表示意图带头结点的循环链表示意图第28页/共40页第29页/共40页headpriordatanext(a)(b)第30页/共40页第31页/共40页ns-prior=p-prior;n p-prior-next=s;n s-next=p;n p-p

7、rior=s;第32页/共40页ps第33页/共40页双向链表中结点的删除双向链表中结点的删除 p-prior-next=p-next;p-next-prior=p-prior; free(p); 第34页/共40页pxxP第35页/共40页给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。第36页/共40页nwhile (jdatak+=B.dataj+;nC-last=k-1;n n算法的时间复杂度是O(m+n)，其中m是A的表长，n是B的表长。第37页/共40页2.4 应用举例应用举例例例2.4 已知单链表H，写一算法将其倒置。即实现如图2.22的操作。(a)