标签 DataStructure 下的文章

双栈

双栈意思就是双向栈,基本思想就是在一段内存里面,栈从两边分别向中间生长,这样可以提高内存的利用率。下面是C的实现代码,仅仅是基本的功能,重在于思想。

- 阅读剩余部分 -

链表逆置

上次用堆栈实现对链表的逆置,比较麻烦。这次换了个算法,下面主要有两种实现算法。

算法一


首先想到的肯定是创建一个新的空链表,然后把旧的链表中的元素通过指针p从头到尾遍历,每遍历一个,就把该元素从链表中脱离,添加到新的链表的头部,新建空链表的时候可以初始化一个空的无用节点(仅仅是为了操作方便)。

算法二


不通过新建一个新链表,具体是让第一个节点的指针域为NULL,第二个指针域指向第一个节点,第三个指向第二个~~~~~~L指向最后一个节点。

- 阅读剩余部分 -

二叉排序树

二叉排序树(Binary Sort Tree)性质:

(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;

(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;

(3)左、右子树也分别为二叉排序树;

- 阅读剩余部分 -

循环队列

循环队列的C语言实现,把整个队列当作环来处理。一段连续的空间当作队列,front指向队列头,rear指向队列的尾。每次有数据进入队列,则rear向后一个位置移动,如果超过了最大空间,那么取余数;数据出队列,则front向后一个位置移动。队列满的时候rear = front,队列空的时候也是rear = front,于是可以这样处理,如果 rear+1 = front的话就表明是满队列,这样虽然浪费了一个空间,但是可以处理好队列满和空的问题。

- 阅读剩余部分 -

单向链表

到期末了,准备最后一个月把数据结构的一些小算法总结下,都在Fedora上用 codeblocks+ddd写,刚好可以熟悉下linux平台。另外C++还是没开始学,于是就准备在写数据结构实现的过程中直接用C++,发现写成了C+,真是悲剧。。。。

先是简单的单向链表,书上的很简洁,但是看起来不是很懂,于是我就自己写了,虽然复杂了很多,但是还是比较简洁,效率应该是差不多的,我多的不过是几个分支。下面是几个注意点

- 阅读剩余部分 -

二叉树遍历--递归实现

递归这东西真是抽象,我看着看着算法,就囫囵吞枣地的写了下,写得囧了。这次先用递归实现先序,中序,后序遍历算法。先大概说下原理:我输入一大串字符,中间#就是代表了空,基本的储存结构就是二叉链表。主要就是二叉树的创建和三种顺序的遍历。二叉树的创建通过从左孩子开始创建不断递归,知道读取了#,开始创建对应的右孩子,继续递归。访问的时候对于三种顺序不过就是对于操作的顺序改变而已。

- 阅读剩余部分 -

二叉树按层次遍历--队列实现

二叉树(binary tree)

二叉树的基本形态
二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态:
(1)空二叉树——(a)
(2)只有一个根结点的二叉树——(b)
(3)只有左子树——(c)
(4)只有右子树——(d)
(5)完全二叉树——(e)

度(Degree):节点孩子的数目。
叶子(Leaf): 度为0的节点称为叶子。
深度(Depth):树中最大的层次(从最上0开始数)

满二叉树:一棵深度为k且有2^k -1个节点的二叉树。
完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层有叶子节点,并且叶子节点都是从左到右依次排布,这就是完全二叉树。

性质1:在二叉树的第i层上至多有2^(i-1)个节点(i >= 1)
性质2:深度为k的二叉树至多有2^k - 1个节点
性质3:任意一棵二叉树T,若其叶子节点数为n0,度为2的节点数为n2,则n0 = n2 + 1

对于完全二叉树:

性质4:具有n个节点的完全二叉树的深度是[log2n] + 1
性质5:有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:
若I为结点编号则 如果I<>1,则其父结点的编号为I/2;
如果2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子;
如果2*I+1<=N,则其右儿子的结点编号为2*I+1;若2*I+1>N,则无右儿子。

二叉树按层次遍历----队列实现
1.创建二叉树,输入#代表NULL,调用递归创建二叉树。
2.构建一个队列专门用来储存二叉树节点指针,先把根节点入队,假设是A,对A元素进行访问,然后对A的左右孩子依次入队,假设B,C。A出队列,再是对B进行访问,同样将B的左右孩子入队列,B出对列······重复以上,知道队列为空。

下面是的代码是实现按层次从上到下遍历二叉树:

[code]
#include <Windows.h>
#include <stdio.h>

#define ElemType char

typedef struct TreeNode{ //单位节点
struct TreeNode *LChild;
struct TreeNode *RChild;
ElemType c;
}TreeNode,* p_Tree;

typedef struct Link{ //单向链表
struct Link *Next;
TreeNode *Node;
}Link,*P_Link;

typedef struct Queue{ //形成队列
P_Link front;
P_Link rear;
int Q_Len;
}Queue,*p_Queue;

BOOL PrintElement(ElemType e); //对二叉树节点的操作,自定义,这里我设置为打印出内容
BOOL CreateTree(p_Tree* pBiTree); //创建二叉树
P_Link InitLink(P_Link L); //初始化链表
P_Link InsertLink(P_Link L,TreeNode *Tree_Node,p_Queue *Q); //插入队列
p_Queue GetTopLinkNode(P_Link L, BOOL(*Visit)(ElemType),p_Queue Q); //取出队列第一个元素,并且访问左右孩子
p_Queue InitQueue(p_Queue T,P_Link L); //初始化队列

int main()
{
p_Tree Tree = NULL;
P_Link Link = NULL;
p_Queue Queue = NULL;
if(!CreateTree(&Tree)) //创建二叉树
{
printf("Create Tree Error\n");
return 0;
}
p_Tree p_Temp_Node = Tree;
Link = InitLink(Link);
Queue = InitQueue(Queue,Link);

Link = InsertLink(Link,p_Temp_Node,&Queue); //根节点入队

BOOL(*Operate)(ElemType); //定义函数指针
Operate = PrintElement;

while(Queue->front != Queue->rear)
{
Queue = GetTopLinkNode(Link,Operate,Queue); //获取队列第一个节点
Link = InsertLink(Link,Queue->front->Node->LChild,&Queue); //左孩子入队
Link = InsertLink(Link,Queue->front->Node->RChild,&Queue); //右孩子入队
}

return 0;
}

BOOL CreateTree(p_Tree* pBiTree)
{
ElemType ch;
ch = getchar();
if (ch == '#') //#代表NULL
{
(*pBiTree) = NULL;
}
else
{
(*pBiTree) = (p_Tree)calloc(1,sizeof(TreeNode));
if (!(*pBiTree))
{
printf("Allocate Memory Error\n");
return FALSE;
}
else
{
(*pBiTree)->c = ch;
CreateTree(&(*pBiTree)->LChild); //调用递归创建二叉树
CreateTree(&(*pBiTree)->RChild);
}
}
return TRUE;
}

P_Link InitLink(P_Link L)
{
L = (P_Link)calloc(1,sizeof(Link));
if (!L)
{
printf("Memory Error\n");
return NULL;
}
L->Node = NULL;
L->Next = NULL;
return L;
}

p_Queue InitQueue(p_Queue T,P_Link L)
{
T = (p_Queue)calloc(1,sizeof(Queue));
T->Q_Len = 0;
T->front = L;
T->rear = L;
return T;
}

P_Link InsertLink(P_Link L,TreeNode *Tree_Node,p_Queue *Q)
{
if (Tree_Node == NULL)
{
return L;
}
else
{
static P_Link p = L;
P_Link pNew;
pNew = (P_Link)calloc(1,sizeof(Link));
if (!pNew)
{
printf("Memory Error\n");
return 0;
}
pNew->Node = Tree_Node; //New Node
pNew->Next = NULL;
p->Next = pNew; //p to Next
p = pNew;
(*Q)->rear = p; //Add Queue
(*Q)->Q_Len++ ; //Q len ++
return L;
}
}

p_Queue GetTopLinkNode(P_Link L, BOOL(*Visit)(ElemType),p_Queue Q)
{
Q->front = Q->front->Next; //remove first Node
Visit(Q->front->Node->c);
Q->Q_Len--;
return Q;
}

BOOL PrintElement(ElemType e)
{
// 输出元素e的值
printf("%c",e);
return TRUE;
}
[/code]