线性表——顺序表学习教案

1、会计学1第一页，共26页。第1页/共26页第二页，共26页。第2页/共26页第三页，共26页。 线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点(tdin)是线性表中的数据元素是有序且是有限的。第3页/共26页第四页，共26页。 数据元素之间具有的逻辑关系为线性关数据元素之间具有的逻辑关系为线性关系的数据元素集合称为系的数据元素集合称为线性表线性表。 n n为线性表为线性表的长度的长度, , 长度为长度为0 0的线性表称为空表。的线性表称为空表。第4页/共26页第五页，共26页。L=( a1，a2，a3，ai-1，ai ，ai+1，,.,an ) 表头(bio

2、tu)表尾这里的数据元素这里的数据元素ai(1in)只是一个抽象的符号，只是一个抽象的符号，其具体含义在不同的情况其具体含义在不同的情况(qngkung)下可以不同下可以不同。第5页/共26页第六页，共26页。3. 线性结构线性结构(jigu)特点特点:(1)(1)有且只有一个有且只有一个(y (y )根结点根结点a1 a1 ，无前驱，无前驱 。(2)(2)有且只有一个有且只有一个(y (y )终端结点终端结点an an ，无后，无后继继 。(3)(3)其他结点有且只有一个其他结点有且只有一个(y (y )直接前驱和直接前驱和一个一个(y (y )直接后继。直接后继。第6页/共26页第七页，共

3、26页。几个几个(j )线性表的例子：线性表的例子： 数列数列： ( 25， 12， 78， 34， 100， 88)1 1a1 a2 a3 a4 a5 a6一个数据元一个数据元素为一个整素为一个整数数2 2字母表字母表： ( A， B， C， , Z)a1 a2 a3 a26一个数据元素一个数据元素为一个字母为一个字母1.2 线性表简单简单(jindn)线性表线性表第7页/共26页第八页，共26页。几个几个(j )线性表的例子：线性表的例子：数据文件：数据文件：3 399001 张张 华华 女女17 99002 李李 军军 男男18 99003 王王 明明 男男17 99050 刘刘 东东

4、女女19 学号学号 姓姓 名名性别性别 年龄年龄其其 他他 一个数据元素一个数据元素为一个记录为一个记录a1a2a3 a50.1.2 线性表复杂复杂(fz)线性表线性表第8页/共26页第九页，共26页。 用一组地址连续的存储单元依次存储线性表用一组地址连续的存储单元依次存储线性表中的数据元素，数据元素之间的逻辑关系通过数中的数据元素，数据元素之间的逻辑关系通过数据元素的存储位置直接反映据元素的存储位置直接反映。 ( a1，a2，a3， . . , an ) 所谓一个元素的所谓一个元素的 是指该元素占用的是指该元素占用的若干若干( (连续的连续的) )存储单元的第一个单元的地址。存储单元的第一个

5、单元的地址。地址地址LOC(ai)a1a2a3an d1 d2 d3 dn 1.2.2 线性表的顺序存储结构线性表的顺序存储结构第9页/共26页第十页，共26页。 若假设每个数据若假设每个数据(shj)(shj)元素占用元素占用k k个存储单元个存储单元，并且，并且已知第一个元素的存储位置已知第一个元素的存储位置LOC(a1)LOC(a1)，则有，则有 LOC(ai) = LOC(a1)+(i 1) ka1a2a3an 结论结论(jiln)：LOC(a1)=100 k=4 求求LOC(a5)=?a1a2a3an a4a5100 104 108 112 116 LOC(a5) = 100+(5

6、1) 4=116第10页/共26页第十一页，共26页。事先分配给线性表的空间事先分配给线性表的空间当前已经占用的空间当前已经占用的空间尚未使用的空间尚未使用的空间第11页/共26页第十二页，共26页。#define M 100datatype AM;int n;C 语言语言第12页/共26页第十三页，共26页。1) 顺序存储结构顺序存储结构(jigu)： 2) 第第i个元素个元素(yun s)地址地址p顺序表的基本顺序表的基本(jbn)运算运算 顺序表的插入运算顺序表的插入运算: : 在线性表的第在线性表的第i i个元素之前插入一个新个元素之前插入一个新的元素，先移动，后插入。的元素，先移动，

7、后插入。ABCDEFGH空闲空间插队前大哥，求求你？ABCDEFGH空闲空间插队后大哥，谢谢你！第13页/共26页第十四页，共26页。1) 顺序存储结构顺序存储结构(jigu)： 2) 第第i个元素个元素(yun s)地址地址p顺序表的基本顺序表的基本(jbn)运算运算 顺序表的插入运算顺序表的插入运算: : 在线性表的第在线性表的第i i个元素之前插入一个元素之前插入一个新的元素，先移动，后插入。个新的元素，先移动，后插入。ai-1.a2a1anai+1ai x ai-1. a2 a1 ai an an ai+1 ai ai x第14页/共26页第十五页，共26页。插入程序举例插入程序举例(

8、 (在在8 8个数中任意位置个数中任意位置(wi zhi)(wi zhi)插入一个数插入一个数) )：#define N 8#define N 8main()main() int aN+1=12,34,45,6,78,9,10,91, i,j,x; int aN+1=12,34,45,6,78,9,10,91, i,j,x; printf(“input the location printf(“input the location toto be inserted:”); be inserted:”); scanf(“%d,%d”,&i,&x); scanf(“%d,%d”,&

9、amp;i,&x); ai-1=x; ai-1=x; for(j=0;j=N;j+) for(j=0;j=N;j+) printf(“%d,”,aj); printf(“%d,”,aj); for(j=i-1;j=for(j=i-1;j=i-1;j-);j=i-1;j-) aj+1=aj; aj+1=aj;第15页/共26页第十六页，共26页。插入运算插入运算(yn sun)(yn sun)时间性能分析：时间性能分析：11npi等概率：在第在第i i个位置上作插入个位置上作插入(ch r)x,(ch r)x,则需将第则需将第i i个至第个至第n n个元素移个元素移动，即共需移动动，即共

10、需移动(n-i+1)(n-i+1)个元素。个元素。插入运算，时间主要消耗在数据移动上。在长度为插入运算，时间主要消耗在数据移动上。在长度为n n的线性表中插入一的线性表中插入一个个(y )(y )元素，则平均移动元素次数元素，则平均移动元素次数( (期望值期望值) )：?) 1(11niiisinpEp pi i：在第：在第i i个位置上作插入的概率。个位置上作插入的概率。等差数列求和公式等差数列求和公式: (首项首项+末项末项)项数项数)/211) 1(11niinn(n-i+1)2nMOVEi第16页/共26页第十七页，共26页。线性表线性表(a0,a1,a2)平局平局移动移动(ydng)

11、元素个数元素个数:()*(3+2+1+0)=1.5在一线性表在一线性表(a0,a1,a2)中插入任意一数中插入任意一数i，求平局移动，求平局移动(ydng)元素元素次数次数: i 移动移动(ydng)次数次数(n-i+1) 1(插入到第个数插入到第个数a0前前) 3 2 (插入到第插入到第2个数个数a1前前) 23 (插入到第插入到第3个数个数a2前前) 1 (插入到第插入到第3个数个数a2后后) 0 第17页/共26页第十八页，共26页。1) 顺序存储结构顺序存储结构(jigu)： 2) 第第i个元素个元素(yun s)地址地址p顺序顺序(shnx)表的基本运算表的基本运算2)2)顺序表删除

12、运算：顺序表删除运算：定义：定义：指将表中第指将表中第i个元素从线性表中去掉。个元素从线性表中去掉。原表长为原表长为n n：( a1，a2，ai-1，ai ，ai+1， an ) 新表长为新表长为n-1n-1：( a1，a2，ai-1，ai+1， ， an ) 步骤：步骤：(1)将将ai+1 an， 顺序向前移动顺序向前移动(2)表长表长减一减一第18页/共26页第十九页，共26页。ABCDEFGH空闲空闲(kngxin)空间空间逃离逃离(to l)后后ABCDEFGH空闲空闲(kngxin)空间空间逃离前逃离前骗子，还我钱骗子，还我钱第19页/共26页第二十页，共26页。 (删除删除(shn

13、ch)(shnch)第五个元第五个元素素21) 21) 6741262148916 0 1 2 3 4 5 6 7 867412648916 0 1 2 3 4 5 6 7 867第20页/共26页第二十一页，共26页。p顺序顺序(shnx)表的基本运算表的基本运算2)2)顺序顺序(shnx)(shnx)表删除表删除运算：运算：时间时间(shjin)(shjin)性能分析：性能分析：时间消耗与插入运算相同，时间消耗与插入运算相同，平均移动元素次数：平均移动元素次数：niinn1)(1q qi i: :在第在第i i个位置上作插入的概率。设个位置上作插入的概率。设q qi i=1/n =1/n

14、共需移动共需移动(n-i)(n-i)个元素。个元素。niiidlMOVEqE1niiinq1)(21n第21页/共26页第二十二页，共26页。 i 移动移动(ydng)次数次数(n-i) 1(删除第删除第1个数个数a0) 22 (删除第删除第2个数个数a1) 13 (删除第删除第3个数个数a2) 0线性表线性表(a0,a1,a2)平平局局(pngj)移动元素移动元素个数个数:(1/3)*(2+1+0)=1在一线性表在一线性表(a0,a1,a2)中删除任意一数中删除任意一数i，求平局移动，求平局移动(ydng)元素元素次数次数:niniidlninninqE1121)(1)(作业作业：有一数组，

15、存储十个数，：有一数组，存储十个数，编程序删除其中任意一个数。编程序删除其中任意一个数。第22页/共26页第二十三页，共26页。在顺序存储表示的线性表中在顺序存储表示的线性表中插入或删除一个数据元素，插入或删除一个数据元素，平均约需要移动平均约需要移动(ydng)一一半的元素半的元素 因此，顺序存储表示因此，顺序存储表示(biosh)仅适用于不经仅适用于不经常进行插入和删除操作常进行插入和删除操作并且表中元素相对稳定并且表中元素相对稳定的表的表第23页/共26页第二十四页，共26页。p顺序顺序(shnx)(shnx)表优点和缺点表优点和缺点优点优点(yudin)(yudin)：逻辑上相邻元素存储位置也相邻逻辑上相邻元素存储位置也相邻, ,无需增加无需增加(zngji)(zngji)额外额外存储空间可方便随机存取表中任一元素。存储空间可方便随机