由于C语言中的—维数组也是采用顺序存储 表示,故可以用数组类型来描述顺序表。 又因为除了用数组来存储线性表的元素之 外,顺序表还应该用一个变量来表示线性 表的长度属性,所以我们用结构类型来定 义顺序表类型。 t define listsize 100 typedef int Data Type ty pede struct Data Type data[Listsize int length qlIsT
• 由于C语言中的一维数组也是采用顺序存储 表示，故可以用数组类型来描述顺序表。 又因为除了用数组来存储线性表的元素之 外，顺序表还应该用一个变量来表示线性 表的长度属性，所以我们用结构类型来定 义顺序表类型。 • # define ListSize 100 • typedef int DataType; • typedef struct{ • DataType data[ListSize]; • int length; • } Sqlist;
222顺序表上实现的基本操作 在顺序表存储结构中,很容易实现线 性表的一些操作,如线性表的构造、第 元素的访问。 注意:C语言中的数组下标从“0”开始, 因此,若L是 Sqlist类型的顺序表,则表中 第i个元素是 Ldatai-1]。 以下主要讨论线性表的插入和删除两 种运算。 1、插入 线性表的插入运算是指在表的第 i(1至isn+1)个位置上,插入一个新结点x
• 2.2.2 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线 性表的一些操作，如线性表的构造、第i个 元素的访问。 注意：C语言中的数组下标从“0”开始， 因此，若L是Sqlist类型的顺序表，则表中 第i个元素是L.data[i-1]。 以下主要讨论线性表的插入和删除两 种运算。 1、插入 线性表的插入运算是指在表的第 i(1≦i≦n+1)个位置上，插入一个新结点x
使长度为n的线性表 变成长度为n+1的线性表 (a1,∴a;1,x,a;,∴,an) 算法思想: ①进行合法性检查,1<-i<=n+1; ②判断线性表是否已满; ③将第n个至第个元素逐一后移一个单元; ④在第i个位置处插入新元素; ⑤将表的长度加1
使长度为n的线性表 (a1，…a i-1，ai，…，an ) 变成长度为n+1的线性表 (a1，…a i-1，x，ai，…，an ) 算法思想： ① 进行合法性检查，1<=i<=n+1； ② 判断线性表是否已满； ③ 将第n个至第i个元素逐一后移一个单元； ④ 在第i个位置处插入新元素； ⑤ 将表的长度加1
算法2.3在顺序结构的线性表中第i个D之前插入x Void Insertlist(sqlist L, Data Type x, int D) f(l<1‖l> L length+1) i printf( Position error); return ERROR J if (Llength>=ListSize i printf( overflow ) exit(overflow);) for g-L length-1;>=l-1; j-) Ldatal计+1]1 datal; Ldata[I-1=X L length++;)
算法2.3 在顺序结构的线性表中第i个DE之前插入x Void InsertList(Sqlist *L，DataType x，int I) { int j; if (I<1 || I>L.length+1) { printf(“Position error”); return ERROR } if (L.length>=ListSize) { printf(“overflow”); exit(overflow); } for (j=L.length-1;j>=I-1;j--) L.data[j+1]=l.data[j]; L.data[I-1]=x; L.length++; }
现在分析算法的复杂度 这里的问题规模是表的长度,设它的值为n 该算法的时间主要化费在循环的结点后移语句 上,该语句的执行次数(即移动结点的次数 是。由此可看出,所需移动结点的次数不仅依 赖于表的长度,而且还与插入位置有关 当I-n时,由于循环变量的终值大于初值,结 点后移语句将不进行;这是最好情况,其时间 复杂度O(1) 当Ⅰ=1时,结点后移语句将循环执行n次,需移 动表中所有结点,这是最坏情况,其时间复杂 度为O(n)
• 现在分析算法的复杂度。 • 这里的问题规模是表的长度，设它的值为n。 该算法的时间主要化费在循环的结点后移语句 上，该语句的执行次数（即移动结点的次数） 是。由此可看出，所需移动结点的次数不仅依 赖于表的长度，而且还与插入位置有关。 • 当I=n时，由于循环变量的终值大于初值，结 点后移语句将不进行；这是最好情况，其时间 复杂度O（1）； • 当I=1时，结点后移语句将循环执行n次，需移 动表中所有结点，这是最坏情况，其时间复杂 度为O（n）