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

b) 单链表不空

条件：L->next != 0

10. 基本算法 （遍历）

a) 顺序访问所有元素

借助指针，“顺藤摸瓜”(沿着链表访问结点)。 ．．．．

p = L->next; // 注意起始位置的考虑

while ( p!=NULL ) { // 判表尾，另外 (p!=0)或(p)均可 visit( p->data ); // 访问:可以换成各种操作 p = p->next; // 指针沿着链表向后移动 }

例：打印单链表中的数据。

void PrintLinkList ( LinkList L )

{

p = L->next;

while ( p!=NULL ) {

print ( p->data ); // 访问：打印数据域

p = p->next;

}

}

b) 查找元素x

// 在单链表L中查找元素x

// 若找到，返回指向该结点的指针；否则返回空指针

LinkList Find ( LinkList L, DataType x )

{

p = L->next;

while ( p!=NULL ) {

if ( p->data == x ) return p; // 找到x

p = p->next;

} 5 不准确的说法，只为便于理解和记忆，不要在正式场合引用。

return NULL; // 未找到

}

// 在单链表L中查找元素x

// 若找到，返回该元素的位序；否则返回0 int Find ( LinkList L, DataType x )

{

p = L->next; j = 1;

while ( p!=NULL ) {

if ( p->data == x ) return j; // 找到xp = p->next; j++; // 计数器随指针改变 }

return 0; // 未找到

}

前一个算法的另一种写法：

p = L->next;

while ( p && p->data!=x )

p = p->next;

if ( p && p->data==x ) return p;

else return 0;

或者

p = L->next;

while ( p && p->data!=x ) p = p->next; return p; // 为什么

c) 查找第i个元素

LinkList Get ( LinkList L, int i )

{

p = L->next; j = 1;

while ( p && j<i ) {

p = p->next; j++;

}

if ( p && j==i ) return p;

else return 0;

}

d) 查找第i-1个元素

p = L; j = 0;

while ( p && j<i-1 ) {

p = p->next; j++;

}

if ( p && j==i-1 ) return p;

else return 0;

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

技巧：画图辅助分析。

思路：

先查找第i-1个元素

若找到，在其后插入新结点

6bool ListInsert ( LinkList &L, int i, DataType x )

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