数据结构21线性表.pptVIP

Ⅱ.算法描述 DataType get_lklist(Lklist L, int i) { p = L-next; j = 1; while (p ji) { p = p-next; ++j;} if ( !p || ji )return 特殊值; e = p-data; // p不为空，且i=j,取第i个元素 return e; } Ⅲ.算法分析:T(n)=O(n),n是线性表的长度 * * （3） 插入元素 如在两元素a和b之间插入元素x，应进行下面的操作： p a b ② ① s x s-next = p-next ; ① p-next = s; ② ① 与②是否能够颠倒 * 在链表L的第i个元素之前插入x p L a1 … ai-1 a i … ② ① S x 线性表的操作insert_lklist(L, i, x)在链表中的实现: Ⅰ.基本操作: ①寻找第i-1个结点，检查有关参数的合理性； ②生成一个新结点, 使新结点数据域的值为x; ③将新结点插入到链表中； ④修改第i-1个结点的指针域 Ⅱ.算法描述 void insert_lklist(Lklist L, int i, DataType x) { p = L; j = 0; while (p j i-1) { p = p-next; ++j; } // 寻找第i-1个结点 if (!p || j i-1) // i小于1或者大于表长 error(‘链表为空或不存在第i个位置’); s =(Lklist)malloc( sizeof(Lnode));// 生成新结点 s-data = x; s-next = p-next; // 插入L中 p-next = s; } Ⅲ.算法分析:T(n)=O(n),n为线性表的长度。 * * (4) 删除元素 p q … a b c ... 要删除线性表中的元素b, 只需进行如下操作： p- next= p-next-next； 如要在删除之后释放结点所占的空间，只需进行如下操作： q = p- next ; p- next= p- next- next ; free(q)； * 线性表的操作delete_lklist(L, i)在链表中的实现. Ⅰ.基本操作 ①寻找第i-1个结点，检查有关参数的合理性； ②用指针q指向被删除结点； ③删除第i个结点，即修改第i-1个结点的指针； ④释放第i个结点。 Ⅱ.算法描述 void delete_lklist(Lklist L, int i) { // 在带头结点的单链表L中，删除第i个元素 p = L; j = 0; while (p-next j i-1) { // 寻找第i个结点，并令p指向其前驱 p = p-next; ++j;} if (!(p-next) || j i-1) error(‘链表为空或删除位置不合理’); q = p-next; p-next = q-next; e = q-data; free(q);} // 删除并释放结点 Ⅲ.算法分析:T(n)=O(n),n是线性表的长度。 * (5)建立链表 create_lklist(L)完成多个数据元素的插入操作 Ⅰ.主要步骤 Ⅱ.算法描述 Ⅲ.算法分析 * * (6) 实现归并算法 La a1 a2