二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(6)

if ( i<L.length )

找到;

else

未找到;

2. 插入算法 ListInsert(&L,i,x)

a) 前提：表不满

b) 合理的插入范围：1≤i≤L.length+1

注：位序i在C/C++中对应于下标i-1。

c) 步骤

第i至最后所有元素后移一个元素

在第i个位置插入元素x

表长增1

d) 算法

4bool ListInsert ( SqList& L, int i, DataType x )

{

if ( L.length==MAXSIZE || i<1 || i>L.length+1 ) return false; // 失败

// 元素后移

for ( j=L.length-1; j>=i-1; j-- ) // 这里j为下标，从L.length-1到i-1

L.elem[j+1] = L.elem[j]; // 若作为位序，有如何修改？

// 插入x

L.elem[i-1] = x;

// 表长增1

L.length++;

return true; // 插入成功

}

3. 删除算法 ListDelete(&L,i,&x)

a) 前提：表非空

b) 合理的删除范围：1≤i≤L.length

c) 步骤

取出第i个元素

第i个元素之后的元素向前移动一个位置 4 这里返回true表示正确插入，返回false表示插入失败。以下常用来区分操作是否正确执行。

表长减1

d) 算法

bool ListDelete ( SqList& L, int i, DataType& x )

{

if ( L.length==0 || i<1 || i>L.length ) return false; // 失败 x = L.elem[i-1];

for ( j=i; j<L.length; j++ )

L.elem[j-1] = L.elem[j];

L.length--;

return true; // 删除成功

}

4. 算法分析

表 错误！文档中没有指定样式的文字。.1 顺序表插入和删除算法的分析

基本操作

平均移动次

数

时间复杂度

尾端操作 插入 移动元素 1n?1n(n?i?1)? ?i?1?删除 移动元素 1n?1?i(n?i)?n?1 O(n) O(n) 插入第n+1个元素，不移动 删除第n个元素，不移动 插入、删除需移动大量元素O(n)；但在尾端插入、删除效率高O(1)。

5. 其他算法

a) InitList (&L), ClearList (&L)

L.length = 0;

b) ListEmpty (L)

return L.length == 0;

c) ListLength (L)

return L.length;

d) GetElem (L, i, &e)

e = L.elem[i-1];

单链表——线性表的链式存储结构之一

6. 概念

线性链表，单链表，结点；数据域，指针域；头指针，头结点。

7. 特点

用指针表示数据之间的逻辑关系（逻辑相邻的元素物理位置不一定相邻）。

8. 类型定义

5简而言之，“数据 + 指针”。

typedef struct LNode {

DataType data;

struct LNode *next;

} LNode, *LinkList;

9. 基本形态

带头结点的单链表的基本形态有：

a) 单链表空

条件： L->next == 0

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-6.html