数据结构线性表PPT学习教案

1、会计学1数据结构线性表数据结构线性表2（a1, a2, ai-1，ai, ai1 ，, an）1. 线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点第1页/共42页3学号学号姓名姓名性别性别年龄年龄班级班级012002009524刘禹圻刘禹圻男男 182002级计科级计科0201班班012002009613武武 锐锐男男 182002级计科级计科0202班班012002009710彭彭 隽隽男男 172002级计科级计科0203班班012002009801郭郭 芳芳女女 18

2、2002级计科级计科0204班班012002009904张珍珍女18182002级计科级计科0205班班： ：例2 分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析： 数据元素都是同类型（字母）， 元素间关系是线性的。第2页/共42页4把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：简言之：逻辑上相邻的元素，物理上也相邻可以利用数组Vn来实现。注意：在C语言中数组的下标是从0开始，即：Vn的有效范围是从 V0Vn-1第3页/共42页5设首元素a1的存放地址为LOC(a

3、1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为： LOC(ai+1) = LOC(ai)+L 对上述公式的解释如图所示：第4页/共42页6a a1 1a a2 2a ai ia ai+1i+1a an n 地址 内容 元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b + Lb +(i-1)Lb +(n-1)Lb +(max-1)L第5页/共42页7113因此：LOC( M3 ) = 98 + 5 (3-0) =113解：已知地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）第6页/共42页8回忆：数据结构基本运算操

4、作有： 修改、插入、删除、查找、排序1) 修改 通过数组的下标便可访问某个特定元素并修改之。核心语句: Vi=x;显然，顺序表修改操作的时间效率是T(n)=O(1)第7页/共42页92)插入 在线性表的第i个位置前插入一个元素实现步骤：将第n至第i 位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。事先应判断: 插入位置i 是否合法?表是否已满? 应当有1in+1 或 i=1,n+1for (j=n;j=i;j )aj+1=aj; ai=x; n+;/ 元素后移一个位置/ 插入x / 表长加1 核心语句：第8页/共42页10在线性表的第i个位置前插入一个元素的示意图如下：121

5、3212428304277121321242830427712345678123456789插入第9页/共42页113)删除 删除线性表的第i个位置上的元素for (j=i+1;jdata=; p-next= ; 方式3： p指向结点首地址，然后 (*p).data=； (*p).nextb第20页/共42页22 对于指向结构变量node首地址的指针，可说明为：struct node *p, *q; /或用 struct *p , *q; /注：上面已经定义了node为用户自定义的chy类型。第21页/共42页23设p为指向链表的第i个元素的指针,则第i个元素的数据域写为 ，指针域写为 。练习

6、：p-dataai的值p-nextai+1的地址第22页/共42页24问1：自定义结构类型变量node的长度m是多少？问2：结构变量node的首地址(指针p）是多少？问3：怎样删除结构变量node？*nextdatanode，长度为m字节pmsizeof(node)p(node*)malloc(m)free(p) /只能借助其指针删除！p-data=a; p-next=q第23页/共42页25第24页/共42页26实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址也要及时送给前面的指针。先挖“坑”,后种“萝卜”！第25页/共42页27第26页/共42页28第27页

7、/共42页29讨论：要统计链表中数据元素的个数，该如何改写？ sum+;sum=0;第28页/共42页30缺点：想寻找单链表中第i个元素，只能从头指针开始逐一查询（顺藤摸瓜），无法随机存取 。核心语句：见教材的函数说明Status GetElem_L(LinkList L, int i, ElemType &e)p=L-next; j=1; /带头结点的链表while(p&jnext; +j;if(!p ji)return ERROR;e=p-data;return OK;第29页/共42页31在链表中插入一个元素x的示意图如下：xsabp链表插入的核心语句：p-nexts-nextx结点的生

8、成方式：S=(node*)malloc(m);S-data=x;S-next=p-nextbap第30页/共42页32在链表中删除某元素b的示意图如下：cabp删除动作的核心语句（要借助辅助指针变量q）：q = p-next; /首先保存b的指针，靠它才能找到c；p-next=q-next; /将a、c两结点相连，淘汰b结点；free(q) ； /彻底释放b结点空间p-next思考： 省略free(q)语句行不行？(p-next) - nextq第31页/共42页33答：能。只要将表中最后一个结点的指针域指向头结点即可 (P-next=head;) 。这种形成环路的链表称为循环链表。特别：带头

9、结点的空循环链表之样式参见教材P27 特点： H第32页/共42页34答：只要把单链表再多开一个指针域即可(如用*next和*prior) 。data这种链表称为。其特点是可以双向查找表中结点。参见教材P16。特别：带头结点的双向链表样式：H第33页/共42页35时间效率分析2. 插入和删除 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。 但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是 O(n)。第34页/共42页36空间效率分析链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，空间复杂度为 O(n)。在n个结

10、点的单链表中要删除已知结点*P，需找到它的 ，其时间复杂度为 。 O(n)第35页/共42页37 (参见教材P34 36)讨论：第36页/共42页38但当多项式的次数很高且零系数项很多时，更适于用链表存储。一元多项式的通式可表示为：A xaxaxa xmemeemm().120120分析：一元多项式在计算机内存储时，一般用顺序表存储。a0a1a2am-2am-1顺序表（只存系数项）链表形式am-1 em-1am-2 em-2 a0 e0 或0.0 -1 am-1 em-1 a0 e0通常设计两个数据域（系数项和指数项）和一个指针域。头结点第37页/共42页39 Polynomial数据对象：D=ai|aiTermSet,i=1,2,m, m0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数