第2讲+线性表及其顺序存储解析课件

数据结构课程的内容数据结构课程的内容逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖运算的实现依赖于存储结构于存储结构第第2讲讲 线性表及其顺序存储线性表及其顺序存储2.1 线性表线性表2.2 顺序表顺序表A=（a1,a2,ai-1，ai,ai1，,an）2.1 线性表线性表1.定义：定义：n个（个（n0）数据元素）数据元素(结点结点)的有限序列的有限序列n=0时称为时称为数据元素数据元素开始结点开始结点ai的直接前驱的直接前驱ai的直接后继的直接后继下标，是元素的下标，是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长空表空表终端结点终端结点线性表的特性：线性表的特性：逻辑结构是线性结构逻辑结构是线性结构除开始结点外，任何一个结点有且仅有一个前驱除开始结点外，任何一个结点有且仅有一个前驱除终端结点外，任何一个结点有且仅有一个后继除终端结点外，任何一个结点有且仅有一个后继其中其中n n 称为线性表的表长称为线性表的表长说明：(a1，a2，an)其中数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例例：26 个英文字母组成的英文表个英文字母组成的英文表 （A,B,C,D,Z）学号学号姓名姓名性别性别年龄年龄班级班级2001011810205于春梅于春梅女女 182001级电信级电信016班班2001011810260何仕鹏何仕鹏男男 182001级电信级电信017班班2001011810284王王 爽爽女女 182001级通信级通信011班班2001011810360王亚武王亚武男男 182001级通信级通信012班班例：学生情况登记表例：学生情况登记表数据元素都是学生记录数据元素都是学生记录;元素间关系是线性；表长为元素间关系是线性；表长为4数据元素都是字母数据元素都是字母;元素间关系是线性；表长为元素间关系是线性；表长为26同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性2.线性表上的运算线性表上的运算l置一个空表置一个空表l建一个线性表建一个线性表l求表长求表长l查找某个元素查找某个元素l插入一个元素插入一个元素l删除一个元素删除一个元素l拆分线性表拆分线性表l合并合并l排序排序l2.2 顺序表顺序表2.2.1 顺序表的基本概念及描述顺序表的基本概念及描述2.2.2 顺序表的实现顺序表的实现2.2.1 顺序表的基本概念及描述顺序表的基本概念及描述 线性表的顺序存储称为顺序表线性表的顺序存储称为顺序表1、顺序表的定义顺序表的定义 用一组用一组连续的存储单元连续的存储单元（地址连续）（地址连续）依次存放线性表的各个数据元素。依次存放线性表的各个数据元素。即利用数组技术存放元素。即利用数组技术存放元素。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)=loction(a0)+len*i (0in-1)（参见顺序表存储结构示意图参见顺序表存储结构示意图）顺序表存储结构示意图顺序表存储结构示意图a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在数组中的下标元素在数组中的下标0i-11n-1空闲区空闲区ilenloction(a1)=bb+lenb+(i-1)lenb+(n-1)lenb+(MAX-1)lenMAX-1一个一维数组，下标的范围是一个一维数组，下标的范围是到，每个数组元素用相邻的到，每个数组元素用相邻的个字节个字节存储。存储器按字节编址，设存储数组存储。存储器按字节编址，设存储数组元素元素 的第一个字节的地址是的第一个字节的地址是9 9，则则 的第一个字节的地址是的第一个字节的地址是 113例例1因此：因此：loction(M3)=98+5 3=113解：地址计算通式为：解：地址计算通式为：loction(ai)=loction(a0)+len*i1、顺序表数据类型的定义、顺序表数据类型的定义(1)定义数组的体积定义数组的体积(最多允许的元素个数最多允许的元素个数)#define MAXSIZE 100(2)数据元素类型定义为数据元素类型定义为datatype如：处理学生信息如：处理学生信息typedef struct int n;char name20;int s;datatype;如：处理如：处理 inttypedef int datatype;2.2.2 顺序表的实现顺序表的实现(3)顺序表的类型定义顺序表的类型定义typedef struct datatype aMAXSIZE;/*存放线性表元素的数组存放线性表元素的数组*/int size;/*表示表示 a中实际存放元素个数中实际存放元素个数(表长表长)*/sequence_list;/*顺序表的数据类型顺序表的数据类型sequence_list*/(4)顺序表变量的定义顺序表变量的定义sequence_list slt;/*slt为顺序表变量为顺序表变量*/sequence_list *lp;/*lp为顺序表指针变量为顺序表指针变量*/结构体变量结构体变量slta(数组数组)size(变量变量)slt.aislt.size结构指针结构指针lpa(数组数组)size(变量变量)lp-ailp-size本课堂顺序表的存储结构的本课堂顺序表的存储结构的C语言描述如下：语言描述如下：#define MAXSIZE 100 typedef int datatype;typedef struct datatype aMAXSIZE;int size;sequence_list;l即定义相应运算的即定义相应运算的C语言函数。语言函数。l定义函数要确定：定义函数要确定：函数名函数名 形参形参 返回值返回值传入量传入量传出量传出量l出错处理函数出错处理函数exit(1);/*返回返回OS,告知告知OS程序非正常结束，该函数定程序非正常结束，该函数定义在义在stdlib.h中中*/2、顺序表的算法实现、顺序表的算法实现算法算法2.1 初始化初始化建立一个空表建立一个空表空表的表长为空表的表长为0，使顺序表变量中的，使顺序表变量中的size为为0。函数形参：须初始化顺序表的地址函数形参：须初始化顺序表的地址 返回值：无返回值：无算法实现算法实现：void init(sequence_list lp)lp-size=0;a(数组数组)size(变量变量)lp0算法算法2.2 在表尾插入元素在表尾插入元素即在数组的即在数组的size位置插入元素，表长增位置插入元素，表长增1。函数形参：指定顺序表的地址，插入元素函数形参：指定顺序表的地址，插入元素 返回值：无返回值：无算法实现算法实现：void append(sequence_list lp,datatype x)if(lp-size=MAXSIZE)printf(顺序表是满的顺序表是满的!);exit(1);lp-alp-size=x;lp-size+;共size个元素01size-1sizex算法算法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 判顺序表是否为空表判顺序表是否为空表判断表长是否为判断表长是否为0。函数形参：指定顺序表变量函数形参：指定顺序表变量 返回值：返回值：1表示空表示空,0表示非空表示非空 算法实现算法实现：int empty(sequence_list slt)return slt.size=0;遍历顺序表，查找与给定值遍历顺序表，查找与给定值x相同的元素，找到相同的元素，找到后返回元素的下标值，没找到返回后返回元素的下标值，没找到返回-1。函数形参：指定顺序表变量函数形参：指定顺序表变量 被找元素值被找元素值 返回值：若找到返回值：若找到下标值下标值 若未找到若未找到 -1 遍历查找的范围01size-1算法算法2.5 顺序表中查找指定值的元素顺序表中查找指定值的元素 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 取得顺序表中序号为取得顺序表中序号为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，则表示插入到表的最后，一般地可表示为：，则表示插入到表的最后，一般地可表示为：插入前：插入前：k0,k1,ki-1,ki,kn-1插入后：插入后：k0,k1,ki-1,x,ki,kn-1 插入过程的图示见下图：插入过程的图示见下图：k ik0k1k i-1k n-1k0k1k i-1k n-1xk i后移开始位置后移开始位置后移结束位置后移结束位置插入前插入前插入后插入后顺序表的插入运算顺序表的插入运算 在顺序表在顺序表下标为下标为i（0=i size=MAXSIZE)/*判表满判表满*/printf(n顺序表是满的顺序表是满的!没法插入没法插入!);exit(1);if(ilp-size)/*判插入位置不对判插入位置不对*/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-1sizex 从表尾开始到下标i的元素依次向后移一位k0k1 ki kn-1移动n-i次插入位置 移动次数 0 n 最坏O(n)1 n-1 n-1 1 n 0 最好O(1)i n-i插入算法分析：插入算法分析：可能的插入位置为可能的插入位置为i=0,1,n共共n+1个位置个位置按等概率考虑按等概率考虑,则插入概率：则插入概率：pi=1/(n+1)平均移动次数：平均移动次数：顺序表插入算法平均约需移动一顺序表插入算法平均约需移动一半元素，时间复杂度为半元素，时间复杂度为O(n)顺序表的删除运算顺序表的删除运算 顺顺序序表表的的删删除除操操作作是是指指删删除除顺顺序序表表中中的的第第i个个结结点点，0in-1，一般地可表示为：，一般地可表示为：删除前：删除前：k0,k1,ki-1,ki,ki+1,kn-1 删除后：删除后：k0,k1,ki-1,ki+1,kn-1 删除过程的图示见下图删除过程的图示见下图：k ik0k1k i-1k n-1k0k1k i-1k n-1k i+1前移结束位置前移结束位置前移开始位置前移开始位置删除前删除前删除后删除后k i+1在顺序表中删除在顺序表中删除下标为下标为i（0=i size=0)/*判表为空判表为空*/printf(n顺序表是空的顺序表是空的!);exit(1);if(i=lp-size)/*判删除位置不对判删除位置不对*/printf(n指定的删除位置不存在指定的删除位置不存在!);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,i=0,1,n-1,n-1共共n n个位置个位置按等概率考虑按等概率考虑,则删除概率：则删除概率：p pi i=1/n=1/n平均移动次数：平均移动次数：顺序表删除算法平均约需移动顺序表删除算法平均约需移动一半元素。一半元素。时间复杂度为时间复杂度为O(n)（1）void reverse(sequence_list *lp)将顺序表将顺序表L就地倒置，即借助于就地倒置，即借助于O（1）的辅助空间。）的辅助空间。（2）void sprit(sequence_lsit*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;/*学生学号学生学号*/char name20;/*学生姓名学生姓名*/int score;/*成绩成绩*/datatype;建表要求：建表要求：按输入顺序依次建表按输入顺序依次建表,输入学号为负时结束输入学号为负时结束函数形参：被建顺序表地址函数形参：被建顺序表地址返回值：无返回值：无建立顺序表建立顺序表void Create(sequence_list slt)/*建立学生结点顺序表建立学生结点顺序表*/datatype e;int i=0;/*i为计结点个数变量为计结点个数变量*/while(1)printf(“nEnter new student:”);scanf(“%d”,&e.num);if(e.numai=e;i+;slt-size=i;/*表长就是结点数表长就是结点数*/运算实现运算实现：优点：优点：(1)逻辑结构上相邻的数据元素，其物理位置也是相邻逻辑结构上相邻的数据元素，其物理位置也是相邻的。的。(2)可方便地进行可方便地进行随机存取随机存取任一元素任一元素O(1)。缺点：缺点：(1)插入和删除平均须移动一半元素插入和删除平均须移动一半元素O(n)，效率低。，效率低。(2)存储分配只能预先进行（静态），不易扩充。存储分配只能预先进行（静态），不易扩充。过大过大 浪费浪费 过小过小 溢出溢出 顺序表的优、缺点：顺序表的优、缺点：应用举例应用举例l设元素类型：设元素类型：typedef struct int num;/*学号学号*/char name20;/*姓名姓名*/int score;/*成绩成绩*/datatype;l要求：合并两个升序要求：合并两个升序(依成绩依成绩)顺序表为一个顺序表为一个升序的顺序表升序的顺序表算法实现：算法实现：void merge(sequence_list*la,sequence_list*lb,sequence_list*lc)int i,j,k;i=j=k=0;while(isize&j size)/*la和和lb表都未取完元素表都未取完元素*/if(la-ai.scoreaj.score)lc-ak+=la-ai+;else lc-ak+=lb-aj+;while(isize)/*la表未取完元素表未取完元素*/lc-ak+=la-ai+;while(j size)/*lb表未取完元素表未取完元素*/lc-ak+=lb-aj+;lc-size=la-size+lb-size;l 本讲小结本讲小结 线性表的基本概念线性表的基本概念 顺序表的存储结构顺序表的存储结构 顺序表的数据类型、运算实现顺序表的数据类型、运算实现 阅读教材阅读教材 2.12.2