第2讲+线性表及其顺序存储

1、数据结构课程的内容数据结构课程的内容 逻辑结构唯一逻辑结构唯一 存储结构不唯一存储结构不唯一 运算的实现依赖运算的实现依赖 于存储结构于存储结构 2.1 线性表线性表 2.2 顺序表顺序表 A=（a1, a2, ai-1， ，ai, ai1 ， ，, an） 2.1 线性表线性表 1. 定义：定义：n个（个（n0）数据元素）数据元素(结点结点)的有限序列的有限序列 n=0时称为时称为 数据元素数据元素 开始结点开始结点ai的直接前驱的直接前驱ai的直接后继的直接后继 下标，是元素的下标，是元素的 序号，表示元素序号，表示元素 在表中的位置在表中的位置 n为元素总个为元素总个 数，即表长数，即表

2、长 空表空表 终端结点终端结点 线性表的特性：线性表的特性： 逻辑结构是线性结构逻辑结构是线性结构 除开始结点外，任何一个结点有且仅有一个前驱除开始结点外，任何一个结点有且仅有一个前驱 除终端结点外，任何一个结点有且仅有一个后继除终端结点外，任何一个结点有且仅有一个后继 其中其中n n 称为线性表的表长称为线性表的表长 说明：(a1，a2，an) 其中数据元素ai(1in)只是一个抽象 的符号，其具体含义在不同的情况下可 以不同。 例例 ：26 个英文字母组成的英文表个英文字母组成的英文表 （ A, B, C, D, , Z） 学号学号姓名姓名性别性别年龄年龄班级班级 200101181020

3、5于春梅于春梅女女 182001级电信级电信016班班 2001011810260何仕鹏何仕鹏男男 182001级电信级电信017班班 2001011810284王王 爽爽女女 182001级通信级通信011班班 2001011810360王亚武王亚武男男 182001级通信级通信012班班 例：学生情况登记表例：学生情况登记表 数据元素都是学生记录数据元素都是学生记录; 元素间关系是线性；表长为元素间关系是线性；表长为4 数据元素都是字母数据元素都是字母; 元素间关系是线性；表长为元素间关系是线性；表长为26 同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性 2. 线性表

4、上的运算线性表上的运算 l 置一个空表置一个空表 l 建一个线性表建一个线性表 l 求表长求表长 l 查找某个元素查找某个元素 l 插入一个元素插入一个元素 l 删除一个元素删除一个元素 l 拆分线性表拆分线性表 l 合并合并 l 排序排序 l 2.2 顺序表顺序表 2.2.1 顺序表的基本概念及描述顺序表的基本概念及描述 2.2.2 顺序表的实现顺序表的实现 2.2.1 顺序表的基本概念及描述顺序表的基本概念及描述 线性表的顺序存储称为顺序表线性表的顺序存储称为顺序表 1、顺序表的定义顺序表的定义 用一组用一组连续的存储单元连续的存储单元（地址连续）（地址连续） 依次存放线性表的各个数据元素

5、。依次存放线性表的各个数据元素。 即利用数组技术存放元素。即利用数组技术存放元素。 2、顺序表的结点地址计算顺序表的结点地址计算 l 设首元素设首元素a a1 1的存放地址为的存放地址为location(alocation(a1 1) )（称称为首地为首地 址址），）， l 设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为lenlen字节，字节， l 则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为： loction(ai)= loction(a1)+ len*（i-1） (1in) l 若首元素为若首元素为a a0 0： loction(ai)= loc

6、tion(a0)+len*i (0in-1) （参见顺序表存储结构示意图参见顺序表存储结构示意图） 顺序表存储结构示意图顺序表存储结构示意图 a a1 1 a a2 2 a ai i a ai+1 i+1 a an n 地址地址 内容内容 元素在数组中的下标元素在数组中的下标 0 i-1 1 n-1 空闲区空闲区 i len loction(a1) = b b + len b +(i-1)len b +(n-1)len b +(MAX-1)len MAX-1 一个一维数组，下标的范围是一个一维数组，下标的范围是 到，每个数组元素用相邻的到，每个数组元素用相邻的个字节个字节 存储。存储器按字节编

7、址，设存储数组存储。存储器按字节编址，设存储数组 元素元素 的第一个字节的地址是的第一个字节的地址是9 9， 则则 的第一个字节的地址是的第一个字节的地址是 113 例例1 因此：因此：loction( M3 ) = 98 + 5 3 =113 解：地址计算通式为：解：地址计算通式为： loction(ai)= loction(a0) + len *i 1、顺序表数据类型的定义、顺序表数据类型的定义 (1)定义数组的体积定义数组的体积(最多允许的元素个数最多允许的元素个数) #define MAXSIZE 100 (2)数据元素类型定义为数据元素类型定义为 datatype 如：处理学生信息如

8、：处理学生信息 typedef struct int n; char name20; int s; datatype; 如：处理如：处理 int typedef int datatype; 2.2.2 顺序表的实现顺序表的实现 (3) 顺序表的类型定义顺序表的类型定义 typedef struct datatype aMAXSIZE; /*存放线性表元素的数组存放线性表元素的数组*/ int size; /*表示表示 a中实际存放元素个数中实际存放元素个数(表长表长)*/ sequence_list; /* 顺序表的数据类型顺序表的数据类型sequence_list*/ (4) 顺序表变量的定

9、义顺序表变量的定义 sequence_list slt; /*slt为顺序表变量为顺序表变量*/ sequence_list *lp; /*lp为顺序表指针变量为顺序表指针变量*/ 结构体变量结构体变量slt a(数组数组) size (变量变量) slt.ai slt.size 结构指针结构指针lp a(数组数组) size(变量变量) lp-ai lp-size 本课堂顺序表的存储结构的本课堂顺序表的存储结构的C语言描述如下：语言描述如下： #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE;

10、 int size; sequence_list; l即定义相应运算的即定义相应运算的C语言函数。语言函数。 l定义函数要确定：定义函数要确定： 函数名函数名 形参形参 返回值返回值 传入量传入量 传出量传出量 l 出错处理函数出错处理函数 exit(1); /*返回返回OS,告知告知OS程序非正常结束，该函数定程序非正常结束，该函数定 义在义在stdlib.h中中*/ 2、顺序表的算法实现、顺序表的算法实现 算法算法2.1 初始化初始化建立一个空表建立一个空表 空表的表长为空表的表长为0，使顺序表变量中的，使顺序表变量中的size为为0。 函数形参：须初始化顺序表的地址函数形参：须初始化顺序

11、表的地址 返回值：无返回值：无 算法实现算法实现： void init(sequence_list lp) lp-size=0; a(数组数组) size(变量变量) lp 0 算法算法2.2 在表尾插入元素在表尾插入元素 即在数组的即在数组的size位置插入元素，表长增位置插入元素，表长增1。 函数形参：指定顺序表的地址，插入元素函数形参：指定顺序表的地址，插入元素 返回值：无返回值：无 算法实现算法实现： void append(sequence_list lp,datatype x) if(lp-size=MAXSIZE) printf(顺序表是满的顺序表是满的!);exit(1); l

12、p-alp-size=x; lp-size+; 共size个元素 01size-1size x 算法算法2.3 打印表中每个元素打印表中每个元素 遍历整个顺序表，输出元素值。遍历整个顺序表，输出元素值。 函数形参：指定顺序表变量函数形参：指定顺序表变量 返回值：无返回值：无 算法实现算法实现： void display(sequence_list slt) int i; if(!slt.size) printf(n顺序表是空的顺序表是空的!); else for(i=0;islt.size;i+) printf(%5d,slt.ai); 算法算法2.4 判顺序表是否为空表判顺序表是否为空表 判

13、断表长是否为判断表长是否为0。 函数形参：指定顺序表变量函数形参：指定顺序表变量 返回值：返回值： 1表示空表示空, 0表示非空表示非空 算法实现算法实现： int empty(sequence_list slt) return slt.size=0; 遍历顺序表，查找与给定值遍历顺序表，查找与给定值x相同的元素，找到相同的元素，找到 后返回元素的下标值，没找到返回后返回元素的下标值，没找到返回-1。 函数形参：指定顺序表变量函数形参：指定顺序表变量 被找元素值被找元素值 返回值：若找到返回值：若找到下标值下标值 若未找到若未找到 -1 遍历查找的范围 01size-1 算法算法2.5 顺序表

14、中查找指定值的元素顺序表中查找指定值的元素 int find(sequence_list slt,datatype x) int i; for(i=0;islt.size;i+) if(slt.ai=x) return i; return -1; 若datatype是结构类 型，不能用“=”直 接整体比较，应逐一 比较结构中每个成员 算法实现算法实现： 返回序号为返回序号为i的元素值的元素值。 函数形参：指定顺序表变量函数形参：指定顺序表变量 取元素值的序号取元素值的序号 返回值：序号为返回值：序号为i的元素值的元素值 i 的有效范围 01size-1 算法算法2.6 取得顺序表中序号为取得顺

15、序表中序号为i的元素值的元素值 datatype get(sequence_list slt,int i) if(i=slt.size) /*查找位置不正确查找位置不正确*/ printf(n指定位置的结点不存在指定位置的结点不存在!); exit(1); else return slt.ai; 算法实现算法实现： 顺序表的插入运算是将一个值为顺序表的插入运算是将一个值为x的结点插入到顺的结点插入到顺 序表的第序表的第i个位置个位置0in，即将，即将x插入到插入到ki-1和和ki之间，如之间，如 果果i=n，则表示插入到表的最后，一般地可表示为：，则表示插入到表的最后，一般地可表示为： 插入前

16、：插入前：k0, k1, , ki-1, ki, , kn-1 插入后：插入后：k0, k1, , ki-1,x ki, , kn-1 插入过程的图示见下图：插入过程的图示见下图： k ik0k1k i-1k n-1 k0k1k i-1k n-1xk i 后移开始位置后移开始位置后移结束位置后移结束位置 插入前插入前 插入后插入后 顺序表的插入运算顺序表的插入运算 在顺序表在顺序表下标为下标为i（0= i size=MAXSIZE) /*判表满判表满*/ printf(n顺序表是满的顺序表是满的!没法插入没法插入!);exit(1); if(ilp-size) /*判插入位置不对判插入位置不对

17、*/ printf(n指定的插入位置不存在指定的插入位置不存在!);exit(1); for(j=lp-size-1;j=i;j-) /*从后往前元素后移从后往前元素后移*/ lp-aj+1=lp-aj; lp-ai=x; lp-size+; /*插入并表长增插入并表长增1*/ 插入算法实现：插入算法实现： 元素可插入位置元素可插入位置(0size) 0 isize-1size x 从表尾开始到下标i的元素依次向后移一位 k0k1 ki kn-1 移动n-i次 插入位置 移动次数 0 n 最坏O(n) 1 n-1 n-1 1 n 0 最好O(1) i n-i 插入算法分析：插入算法分析： 可能

18、的插入位置为可能的插入位置为i=0,1,n共共n+1个位置个位置 按等概率考虑按等概率考虑,则插入概率：则插入概率：pi=1/(n+1) 平均移动次数：平均移动次数： 2 2 )1( 1 1 n nn n n i n i iI in n inPE 00 )( 1 1 )( 顺序表插入算法平均约需移动顺序表插入算法平均约需移动 一半元素，时间复杂度为一半元素，时间复杂度为O(n) 顺序表的删除运算顺序表的删除运算 顺序表的删除操作是指删除顺序表中的第顺序表的删除操作是指删除顺序表中的第i个结点，个结点，0in- 1，一般地可表示为：，一般地可表示为： 删除前：删除前：k0, k1, , ki-1

19、, ki, ki+1, , kn-1 删除后：删除后：k0, k1, , ki-1, ki+1, , kn-1 删除过程的图示见下图删除过程的图示见下图 ： k ik0k1k i-1k n-1 k0k1k i-1k n-1k i+1 前移结束位置前移结束位置前移开始位置前移开始位置 删除前删除前 删除后删除后 k i+1 在顺序表中删除在顺序表中删除下标为下标为i（0= i size=0) /*判表为空判表为空*/ printf(n顺序表是空的顺序表是空的!);exit(1); if(i=lp-size) )/*判删除位置不对判删除位置不对*/ printf(n指定的删除位置不存在指定的删除位

20、置不存在!);exit(1); for(j=i+1;jsize-1;j+) /*元素前移元素前移*/ lp-aj-1=lp-aj; lp-size-; /*表长减表长减1*/ 删除算法实现：删除算法实现： 删除元素位置(0size-1) 0 i size-1 size 删 除 从下标从下标i+1开始到表尾的元素依次向前移一位开始到表尾的元素依次向前移一位 k0k1 kiki+1 kn-1 移动n-i-1次 删除位置 移动次数 0 n-1 最坏O(n) 1 n-2 n-2 1 n-1 0 最好O(1) i n-i-1 删除算法分析删除算法分析： 可能的删除位置为可能的删除位置为i=0,1,n-1

21、i=0,1,n-1共共n n个位置个位置 按等概率考虑按等概率考虑, ,则删除概率：则删除概率：p pi i=1/n=1/n 平均移动次数：平均移动次数： 顺序表删除算法平均约需移动顺序表删除算法平均约需移动 一半元素。一半元素。时间复杂度为时间复杂度为O(n) 1 0 1 0 ) 1( 1 ) 1( n i n i iI in n inPE 2 1 2 )11 n nn n （ （1）void reverse (sequence_list *lp) 将顺序表将顺序表L就地倒置，即借助于就地倒置，即借助于O（1）的辅助空间。）的辅助空间。 （2）void sprit(sequence_lsit

22、 *l1,sequence_list *l2, sequence_list *l3) 将有序顺序表将有序顺序表L1分裂成两个线性表分裂成两个线性表L2与与L3，L2由表由表 中所奇数组成，中所奇数组成，L3由所有偶数组成。由所有偶数组成。 顺序表上的一些其它常见算法顺序表上的一些其它常见算法 （3）void merge(sequence_lsit *l1,sequence_list *l2, sequence_list *l3) 见顺序表应用见顺序表应用 将有序顺序表将有序顺序表L1与与L2合并成有序顺序表合并成有序顺序表L3。 元素类型元素类型： typedef struct int num

23、;/*学生学号学生学号*/ char name20; /*学生姓名学生姓名*/ int score; /*成绩成绩*/ datatype; 建表要求：建表要求：按输入顺序依次建表按输入顺序依次建表, 输入学号为负时结束输入学号为负时结束 函数形参：被建顺序表地址函数形参：被建顺序表地址 返回值：无返回值：无 建立顺序表建立顺序表 void Create(sequence_list slt) /*建立学生结点顺序表建立学生结点顺序表*/ datatype e; int i=0; /*i为计结点个数变量为计结点个数变量*/ while(1) printf(“nEnter new student:”); scanf(“%d”, if(e.numai=e; i+; slt-size=i;