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

// 建立空表

L = (LinkList) malloc(sizeof(LNode));

L->next = NULL; // 空表

p = L; // 用p指向表尾

// 插入元素

for ( i=0; i<n; i++ ) {

scanf ( x );

s = (LinkList) malloc(sizeof(LNode));

s->data = x;

// 插入表尾

s->next = p->next;

p->next = s;

p = s; // 新的表尾

}

}

b) 逆序建表

void CreateLinkList ( LinkList &L, int n)

{

// 建立空表

L = (LinkList) malloc(sizeof(LNode));

L->next = NULL; // 空表

// 插入元素

for ( i=0; i<n; i++ ) {

scanf ( x );

s = (LinkList) malloc(sizeof(LNode));

s->data = x;

// 插入表头

s->next = L->next;

L->next = s;

}

}

循环链表

14. 特点

最后一个结点的指针指向头结点。

15. 类型定义

同单链表。

16. 基本形态

空表：L->next == L。

非空表。

17. 与单链表的联系

判断表尾的方法不同：单链表用p==NULL；循环链表用p==L。

其余操作相同。

双向循环链表

18. 特点

一个结点包含指向后继(next)和指向前驱(prior)两个指针，两个方向又分别构成循环链表。

19. 类型定义

typedef struct DuLNode {

DataType data;

struct DuLNode *prior, *next; // 两个 指针 } DuLNode, *DuLinkList;

20. 基本形态

空表：用后向指针判断L->next == L，或者用前向指针判断L->prior == L。

非空表。

21. 与单链表和循环链表的联系

最大不同：前驱容易求得，可以向前遍历。 判断表尾的方法与循环链表相同：p==L。 插入和删除时需要修改两个方向的指针。 22. 插入和删除

需要修改两个方向的指针。例如：(见下表)

表 错误！文档中没有指定样式的文字。.2 双向循环链表的插入和删除

顺序表与单链表的比较

第三章、栈和队列 栈

栈，栈顶，栈底，空栈，后进先出(LIFO)，入栈(Push)，出栈(Pop)。 顺序栈：栈的顺序存储结构；链栈：栈的链式存储结构。 链栈

存储结构

用不带头结点的单链表实现。 类型定义 同单链表。 基本形态 a) 栈空

条件: S == NULL

S

S S

/\

b) 栈非空

c) 栈满（一般不出现）

基本算法

d) 入栈 Push (&s, x)

bool Push ( LinkList &s, DataType x ) {

// 新建结点

p = (LinkList) malloc (sizeof(LNode)); if ( !p ) return false; // 失败 p->data = x;

// 插入栈顶

p->next = s;

s = p;

return true;

}

e) 出栈 Pop (&s, &x)

前提：栈非空。

bool Pop ( LinkList &s, DataType &x ) {

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