大数据算法

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

基本概念

定义：栈是限定仅在表头进行插入和删除操作的线性表。要搞清楚这个概念，首先要明白”栈“原来的意思，如此才能把握本质。"栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。

首先系统或者数据结构栈中数据内容的读取与插入（压入push和弹出pop）是两回事！插入是增加数据，弹出是删除数据，这些操作只能从栈顶即最低地址作为约束的接口界面入手操作，但读取栈中的数据是随便的没有接口约束之说。很多人都误解这个理念从而对栈产生困惑。[1] 而系统栈在计算机体系结构中又起到一个跨部件交互的媒介区域的作用即 cpu 与内存的交流通道，cpu只从系统给我们自己编写的应用程序所规定的栈入口线性地读取执行指令，用一个形象的词来形容它就是pipeline（管道线、流水线）。cpu内部交互具体参见 EU与BIU的概念介绍。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。

栈可以用来在函数调用的时候存储断点，做递归时要用到栈！

以上定义是在经典计算机科学中的解释。

在计算机系统中，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。

栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息：

1．函数的返回地址和参数

2．临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量。

栈的模型

基本算法

1．进栈（PUSH）算法

①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；

②置TOP=TOP+1（栈指针加1，指向进栈地址）；

③S(TOP)=X，结束（X为新进栈的元素）；

2．退栈（POP）算法

①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈，空则下溢；不空则作②)；

②X=S(TOP)，（退栈后的元素赋给X）：

③TOP=TOP-1，结束（栈指针减1，指向栈顶）。

实现

栈分顺序栈和链式栈，下面程序介绍了顺序栈的实现。

pascal

1．数组型

Const

m=栈表目数的上限；

Type

stack=array[1..m] of stype; {栈类型}

Var

s:stack;{栈}

top:integer;

2．记录型

const

m=栈表目数的上限；

type

stack=record

elem: array[1..m] of elemtp;

top:0..m; {栈顶指针}

end;

Var

s:stack;{栈}

C++代码

#include

classSqStack

{

private:

enum{MaxSize=100};

intdata[MaxSize];

inttop;

public:

SqStack();

~SqStack();

boolisEmpty();

voidpushInt(intx);

intpopInt();

intgetTop();

voiddisplay();

};

SqStack::SqStack()

{

top=-1;

}

SqStack::~SqStack(){}

boolSqStack::isEmpty()//判断栈为空

{

return(top==-1);

}

voidSqStack::pushInt(intx)//元素进栈

{

if(top==MaxSize-1)

{

std::cout<<"栈上溢出！"<

}

else

{

++top;

data[top]=x;

}

intSqStack::popInt()//退栈

{

inttmp=0;

if(top==-1)

{

std::cout<<"栈已空！"<

}

else

{

tmp=data[top--];

}

returntmp;

}

intSqStack::getTop()//获得栈顶元素

{

inttmp=0;

if(top==-1)

{

std::cout<<"栈空！"<

}

else

{

tmp=data[top];

}

returntmp;

}

voidSqStack::display()//打印栈里元素

{

std::cout<<"栈中元素："<

for(intindex=top;index>=0;--index)

{

std::cout<

}

intmain()

{

SqStackst;

std::cout<<"栈空："<

for(inti=1;i<10;i++)

{

st.pushInt(i);

}

st.display();

std::cout<<"退一次栈"<

st.popInt();

std::cout<<"栈顶元素:"<

st.popInt();

st.display();

return0;

}

C代码

100

#include

#defineDataTypeint

#defineMAXSIZE1024

typedefstruct

{

DataTypedata[MAXSIZE];

inttop;

}SeqStack;

SeqStack*Init_SeqStack()//栈初始化

{

SeqStack*s;

s=(SeqStack*)malloc(sizeof(SeqStack));

if(!s)

{

printf("空间不足n");

returnNULL;

}

else

{

s->top=-1;

returns;

}

intEmpty_SeqStack(SeqStack*s)//判栈空

{

if(s->top==-1)

return1;

else

return0;

}

intPush_SeqStack(SeqStack*s,DataTypex)//入栈

{

if(s->top==MAXSIZE-1)

return0;//栈满不能入栈

else

{

s->top++;

s->data[s->top]=x;

return1;

}

intPop_SeqStack(SeqStack*s,DataType*x)//出栈

{

if(Empty_SeqStack(s))

return0;//栈空不能出栈

else

{

*x=s->data[s->top];

s->top--;

return1;

}//栈顶元素存入*x，返回

}

DataTypeTop_SeqStack(SeqStack*s)//取栈顶元素

{

if(Empty_SeqStack(s))

return0;//栈空

else

returns->data[s->top];

}

intPrint_SeqStack(SeqStack*s)

{

inti;

printf("当前栈中的元素:n");

for(i=s->top;i>=0;i--)

printf("%3d",s->data[i]);

printf("n");

return0;

}

intmain()

{

SeqStack*L;

intn,num,m;

inti;

L=Init_SeqStack();

printf("初始化完成n");

printf("栈空：%dn",Empty_SeqStack(L));

printf("请输入入栈元素个数：n");

scanf("%d",&n);

printf("请输入要入栈的%d个元素：n",n);

for(i=0;i

{

scanf("%d",&num);

Push_SeqStack(L,num);

}

Print_SeqStack(L);

printf("栈顶元素：%dn",Top_SeqStack(L));

printf("请输入要出栈的元素个数（不能超过%d个）：n",n);

scanf("%d",&n);

printf("依次出栈的%d个元素：n",n);

for(i=0;i

{

Pop_SeqStack(L,&m);

printf("%3d",m);

}

printf("n");

Print_SeqStack(L);

printf("栈顶元素：%dn",Top_SeqStack(L));

return0;

}

定义stack的简单代码：

stack sta;

入栈：sta.push(x);

出栈：sta.pop();

判断栈的大小： sta.size();

判断栈是否为空：sta.empty();

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。[1]

顺序队列

建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置，如图所示

每次在队尾插入一个元素是，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。

顺序队列中的溢出现象：

（1） "下溢"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。

（2）"真上溢"现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。

（3）"假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

循环队列

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。[2]

在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。队空和队满的情况如图：

队列的数组实现

队列可以用数组Q[1…m]来存储，数组的上界m即是队列所容许的最大容量。在队列的运算中需设两个指针：head，队头指针，指向实际队头元素；tail，队尾指针，指向实际队尾元素的下一个位置。一般情况下，两个指针的初值设为0，这时队列为空，没有元素。数组定义Q[1…10]。Q(i) i=3,4,5,6,7,8。头指针head=2，尾指针tail=8。队列中拥有的元素个数为:L=tail-head。现要让排头的元素出队，则需将头指针加1。即head=head+1这时头指针向上移动一个位置，指向Q(3)，表示Q(3)已出队。如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1这时Q(9)入队。当队尾已经处理在最上面时，即tail=10，如果还要执行入队操作，则要发生"上溢"，但实际上队列中还有三个空位置，所以这种溢出称为"假溢出"。

克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就"翻转"为1。在结构上采用这种技巧来存储的队列称为循环队列。

队列和栈一样只允许在断点处插入和删除元素。

循环队的入队算法如下：

1、tail=tail+1；

2、若tail=n+1，则tail=1；

3、若head=tail，即尾指针与头指针重合了，表示元素已装满队列，则作上溢出错处理；

4、否则，Q(tail)=X，结束（X为新入出元素）。

队列和栈一样，有着非常广泛的应用。

注意：（1）有时候队列中还会设置表头结点，就是在队头的前面还有一个结点，这个结点的数据域为空，但是指针域指向队头元素。

（2）另外，上面的计算还可以利用下面给出的公式cq.rear=(cq.front+1)/max;

当有表头结点时，公式变为cq.rear=(cq.front+1)/（max+1）。

队列的链表实现

在队列的形成过程中，可以利用线性链表的原理，来生成一个队列。

基于链表的队列，要动态创建和删除节点，效率较低，但是可以动态增长。

队列采用的FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。

队列的基本运算

（1）初始化队列：Init_Queue(q) ，初始条件：队q 不存在。操作结果：构造了一个空队；

（2）入队操作： In_Queue(q,x),初始条件：队q 存在。操作结果：对已存在的队列q，插入一个元素x 到队尾，队发生变化；

（3）出队操作： Out_Queue(q,x)，初始条件: 队q 存在且非空，操作结果：删除队首元素，并返回其值，队发生变化；

（4）读队头元素：Front_Queue(q,x)，初始条件: 队q 存在且非空，操作结果：读队头元素，并返回其值，队不变；

（5）判队空操作：Empty_Queue(q)，初始条件：队q 存在，操作结果：若q 为空队则返回为1，否则返回为0。[3]

操作类型作用返回值例子

length(s)函数求字符串s的长度整型s:='123456789';

l:=length(s);{l的值为9}

copy（s,w,k)函数复制s中从w开始的k位字符串s:='123456789';

s1:=copy(s,3,5);{s1的值是'34567'}

val(s,k,code)过程将字符串s转为数值，存在k中；code是错误代码var s:string;k,code:integer;

begin

s:='1234';

val(s,k,code);

write(k);{k=1234}

str(i,s)过程将数值i转为字符串si:=1234;

str(i,s);

write(s);{s='1234'}

Delete(s,w,k)过程在s中删除从第w位开始的k个字符s := 'Honest Abe Lincoln';

Delete(s,8,4);

Writeln(s); { 'Honest Lincoln' }

Insert(s1, S, w)过程将s1插到s中第w位S := 'Honest Lincoln';

Insert('Abe ', S, 8); { 'Honest Abe Lincoln' }

Pos(c, S)函数求字符c在s中的位置整型S := ' 123.5';

i :=Pos(' ', S);{i的值为1}

+运算符将两个字符串连接起来s1:='1234';

s2:='5678';

s:=s1+s2;{'12345678'}

在STL中，对队列的使用很是较完美

下面给出循环队列的运算算法:

(1)将循环队列置为空

//将队列初始化

SeQueue::SeQueue()

{ front=0;

rear=0;

cout<<"init!"<

}

(2)判断循环队列是否为空

int SeQueue::Empty()

{ if(rear==front) return(1);

else return(0);

}

(3)在循环队列中插入新的元素x

void SeQueue::AddQ(ElemType x)

{ if((rear+1) % MAXSIZE==front) cout<<" QUEUE IS FULL! "<

else{ rear=(rear+1) % MAXSIZE;

elem[rear]=x;

cout<<" OK!";

}

(4)删除队列中队首元素

ElemType SeQueue::DelQ()

{ if(front==rear)

{ cout<<" QUEUE IS EMPTY! "<

else{ front=(front+1) % MAXSIZE;

return(elem[front]);

}

(5)取队列中的队首元素

ElemType SeQueue::Front()

{ ElemType x;

if(front== rear)

cout<<"QUEUE IS EMPTY "<

else x= elem[(front+1)%MAXSIZE];

return (x);

}

链表

线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个"结点"（如概述旁的图所示），表示线性表中一个数据元素。线性表的链式存储表示，有一个缺点就是要找一个数，必须要从头开始找起，十分麻烦。

根据情况，也可以自己设计链表的其它扩展。但是一般不会在边上附加数据，因为链表的点和边基本上是一一对应的（除了第一个或者最后一个节点，但是也不会产生特殊情况）。不过有一个特例是如果链表支持在链表的一段中把前和后指针反向，反向标记加在边上可能会更方便。

对于非线性的链表，可以参见相关的其他数据结构，例如树、图。另外有一种基于多个线性链表的数据结构：跳表，插入、删除和查找等基本操作的速度可以达到O(nlogn），和平衡二叉树一样。

其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。

由分别表示,，…，的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表。

基本操作

（pascal语言）

建立

第一行读入n，表示n个数

第二行包括n个数

以链表的形式存储输出这些数

programproject1;

type

point=^node;

node=record

data:longint;

next:point;

end;

var

i,n,e:longint;

p,q,head,last:point;

begin

write('Inputthenumbercount:');

readln(n);

i:=1;

new(head);

read(e);

head^.data:=e;

head^.next:=nil;

last:=head;

q:=head;

whilei

begin

inc(i);

read(e);

new(p);

q^.next:=p;

p^.data:=e;

p^.next:=nil;

last:=p;

q:=last

end;

//建立链表

q:=head;

whileq^.next<>nildo

begin

write(q^.data,'');

q:=q^.next;

end;

write(q^.data);

//输出

readln;

readln

end.

删除

在以z为头的链表中搜索第一个n，如果找到则删去，返回值为1，否则返回0

functiondelete(n:longint;varz:point):longint;

var

t,s:point;

begin

t:=z;

while(t^.next<>nil)and(t^.data<>n)do

begin

s:=t;

t:=t^.next;

end;

ift^.data<>nthenexit(0);

s^.next:=t^.next;

dispose(t);

exit⑴

end;

查找

类似于删除，只需要找到不删即可

插入

插入，在以zz为头的链表第w个的前面插入nn元素，函数返回值正常是0，如果w超过了链表的长度，函数返回链表的长度

functioninsert(w,nn:longint;varzz:point):longint;

vard:longint;v,vp,vs:point;

begin

v:=zz;

ford:=1towdo

ifv^.next=nil

thenexit(d)

else

begin

vp:=v;

v:=v^.next;

end;

new(vs);

vs^.data:=nn;

vp^.next:=vs;

vs^.next:=v;

exit(0)

end;

链表函数

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

#include

usingnamespacestd;

structNode

{

intdata;//数据域

structNode*next;//指针域

};

Create

*函数功能：创建链表.

*输入：各节点的data

*返回值：指针head

Node*Create()

{

intn=0;

Node*head,*p1,*p2;

p1=p2=newNode;

cin>>p1->data;

head=NULL;

while(p1->data!=0)

{

if(n==0)

{

head=p1;

}

else

p2->next=p1;

p2=p1;

p1=newNode;

cin>>p1->data;

n++;

}

p2->next=NULL;

returnhead;

}

insert

*函数功能：在链表中插入元素.

*输入：head链表头指针，p新元素插入位置，x新元素中的数据域内容

*返回值：无

voidinsert(Node*head,intp,intx)

{

Node*tmp=head;//for循环是为了防止插入位置超出了链表长度

for(inti=0;i

{

if(tmp==NULL)

return;

if(i

tmp=tmp->next;

}

Node*tmp2=newNode;

tmp2->data=x;

tmp2->next=tmp->next;

tmp->next=tmp2;

}

del

*函数功能：删除链表中的元素

*输入：head链表头指针，p被删除元素位置

*返回值：被删除元素中的数据域.如果删除失败返回-1

intdel(Node*head,intp)

{

Node*tmp=head;

for(inti=0;i

{

if(tmp==NULL)

return-1;

if(i

tmp=tmp->next;

}

intret=tmp->next->data;

tmp->next=tmp->next->next;

returnret;

}

voidprint(Node*head)

{

for(Node*tmp=head;tmp!=NULL;tmp=tmp->next)

printf("%d",tmp->data);

printf("n");

}

intmain()

{

Node*head;

head=newNode;

head->data=-1;

head->next=NULL;

return0;

}

例子

#include

#defineNULL0

structstudent

{

longnum;

structstudent*next;

};

intmain()

{

inti,n;

student*p=(structstudent*)malloc(sizeof(structstudent));

student*q=p;

printf("输入几个值");

scanf("%d",&n);

for(i=1;i<=n;i++)

{

scanf("%d",&(q->num));

q->next=(structstudent*)malloc(sizeof(structstudent));

q=q->next;

}

printf("值第几个");

intrank;

scanf("%d%d",&(q->num),&rank);

student*w=p;

for(i=1;i

{

w=w->next;

}

q->next=w->next;

w->next=q;

for(i=1;i<=n+1;i++)

{

printf("%d",p->num);

p=p->next;

}

return0;

}//指针后移麻烦链表形式循环链表

循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。

循环链表的运算与单链表的运算基本一致。所不同的有以下几点：

1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。

2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。

双向链表

双向链表其实是单链表的改进。

当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。

在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。

应用举例概述

约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。例如：n = 9,k = 1,m = 5

参考代码

#include

#defineN41

#defineM5

typedefstructnode*link;

structnode

{

intitem;

linknext;

};

linkNODE(intitem,linknext)

{

linkt=malloc(sizeof*t);

t->item=item;

t->next=next;

returnt;

}

intmain(void)

{

inti;

linkt=NODE（1,NULL);

t->next=t;

for(i=2;i<=N;i++)

t=t->next=NODE(i,t->next);

while(t!=t->next)

{

for(i=1;i

t=t->next;

t->next=t->next->next;

}

printf("%dn",t->item);

return0;

}

其他相关结语与个人总结

C语言是学习数据结构的很好的学习工具。理解了C中用结构体描述数据结构，那么对于理解其C++描述，Java描述都就轻而易举了！

链表的提出主要在于顺序存储中的插入和删除的时间复杂度是线性时间的，而链表的操作则可以是常数时间的复杂度。对于链表的插入与删除操作，个人做了一点总结，适用于各种链表如下：

插入操作处理顺序：中间节点的逻辑，后节点逻辑，前节点逻辑。按照这个顺序处理可以完成任何链表的插入操作。

删除操作的处理顺序：前节点逻辑，后节点逻辑，中间节点逻辑。

按照此顺序可以处理任何链表的删除操作。

如果不存在其中的某个节点略过即可。

上面的总结，大家可以看到一个现象，就是插入的顺序和删除的顺序恰好是相反的，很有意思！

操作

-----悉尼大学工程学院张志刚（Stone Cold）作品

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

#include

typedefstructSlist

{

intdata;

structSlist*next;

}

SLIST;

SLIST*InitList_Sq()/*初始化函数*/

{

inta;

SLIST*h,*s,*r;

h=(SLIST*)malloc(sizeof(SLIST));/*建立头指针，头指针不可以更改！！！*/

r=h;

if(!h)

{

printf("分配失败");

exit(0);

}

scanf("%d",&a);

for(;a!=-1;)

{

s=(SLIST*)malloc(sizeof(SLIST));/*每次都开辟一个结点空间并赋值*/

s->data=a;

r->next=s;

r=s;

scanf("%d",&a);

}

r->next='';

returnh;

}

voidprint_list(SLIST*finder)/*打印函数*/

{

while(finder!='')

{

printf("->%d",finder->data);

finder=finder->next;

}

printf("->endn");

}

intDeleteNode(SLIST*killer)//删除节点函数

{

inti,j=0;

SLIST*p,*q;

intx;

p=killer;

q=killer->next;

printf("请输入您要删除的节点序号：");

scanf("%d",&i);

while((p->next!='')&&(j

{

p=p->next;

j++;

q=p->next;

}

if(p->next==''||j>i-1）

{

printf("nerror");

return-1;

}

else

{

p->next=q->next;

x=q->data;

free(q);

returnx;

}

voidInsert_Node(SLIST*jumper)//插入函数，本算法为前插结点法

{

intt,e,j=0;

SLIST*p,*q;

p=jumper;

printf("请输入要插入位置的序号：");

scanf("%d",&t);

printf("请输入要插入的元素：");

scanf("%d",&e);

while(p->next!=''&&j

{

j++;

p=p->next;

}

if(p==''||j>t-1）

printf("插入的目的位置不存在");

else

{

q=(SLIST*)malloc(sizeof(SLIST));

q->data=e;

q->next=p->next;

p->next=q;

}

voidLocate_List(SLIST*reader)//查找值为e的元素

{

inte,i=0;

SLIST*p;

p=reader;

printf("请输入要查找的元素：");

scanf("%d",&e);

while(p->next!=''&&p->data!=e)

{

i++;

p=p->next;

}

if(p->data==e)

printf("此元素在%d号位置n",i);

else

printf("无此元素！");

}

voidmain()

{

inti,k,y;

SLIST*head;

printf("n1.建立线性表");

printf("n2.在i位置插入元素e");

printf("n3.删除第i个元素，返回其值");

printf("n4.查找值为e的元素");

printf("n5.结束程序运行");

printf("n===================================================");

printf("请输入您的选择：");

scanf("%d",&k);

switch(k)

{

case1:

{

head=InitList_Sq();

print_list(head->next);

}break;

case2:

{

head=InitList_Sq();

print_list(head->next);

Insert_Node(head);

print_list(head->next);

}

break;

case3:

{

head=InitList_Sq();

print_list(head->next);

y=DeleteNode(head);

print_list(head->next);

if(y!=-1）

printf("被删除元素为：%d",y);

}break;//头结点不算，从有数据的开始算第一个

case4:

{

head=InitList_Sq();

print_list(head->next);

Locate_List(head);

}break;

}

本程序可在微软VC++下编译通过并且运行

使用方法简介：运行程序后，先打数字1，然后回车，这样就可以先创建一个新的链表，比如你要创建一个

4->5->6->7这样一个链表，你就输入数字4回车，输入5回车，输入6回车，输入7回车，最后输入-1回车，这个-1就是告诉程序到此为止的标志

假如你要使用插入的功能位置插入，就输入3，回车，程序会问你插入的数值是什么，比如你要插入999，然后回车，999就被插进去了

其他的功能都大同小异

Data_structures

▪集合▪容器

▪数组▪关联数组▪Multimap▪集

▪多重集▪散列表▪树状数组

▪列表▪链表▪队列▪堆栈

▪循环队列▪跳跃列表

▪树▪二叉查找树▪堆▪线段树

▪红黑树▪AVL树

▪图▪有向无环图▪二元决策图▪无向图

词条标签：

科学百科信息科学分类，中国电子学会，

二叉树

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为log2n+1。深度为k的完全二叉树，至少有2^(k-1)个节点，至多有2^k-1个节点。

中文名

二叉树

外文名

Binary Tree

概述

计算机中数据结构的一种

简介

每个结点最多有两个子树的树结构

00001. 1 定义

00002. 2 基本概念

00003. ▪ 类型

00004. ▪ 相关术语

00005. ▪ 二叉树性质

00001. ▪ 存储结构

00002. ▪ 辨析

00003. 3 遍历顺序

00004. ▪ 先序遍历

00005. ▪ 中序遍历

00001. ▪ 后序遍历

00002. ▪ 层次遍历

00003. ▪ 线索二叉树

00004. 4 实现演示

定义

编辑

二叉树在图论中是这样定义的：二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

基本概念

编辑

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

(1)空二叉树——如图(a)；

(2)只有一个根结点的二叉树——如图(b)；

(3)只有左子树——如图(c)；

(4)只有右子树——如图(d)；

(5)完全二叉树——如图(e)。

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。[1]

类型

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。[2]

相关术语

树的结点：包含一个数据元素及若干指向子树的分支；

孩子结点：结点的子树的根称为该结点的孩子；

双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；

兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；

祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙

结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；

树的深度：树中最大的结点层

结点的度：结点子树的个数

树的度：树中最大的结点度。

叶子结点：也叫终端结点，是度为 0 的结点；

分枝结点：度不为0的结点；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；[3]

二叉树性质

(1) 在非空二叉树中，第i层的结点总数不超过

, i>=1；

(2) 深度为h的二叉树最多有

个结点(h>=1)，最少有h个结点；

(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为

（注：[ ]表示向下取整）

(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，则无右儿子。

(6)给定N个节点，能构成h(N)种不同的二叉树。

h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。

(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i[4]

存储结构

(1）顺序存储方式

typenode=record

data:datatype

l,r:integer;

end;

vartr:array[1..n]ofnode;

(2)链表存储方式，如：

typebtree=^node；

node=record

data:datatye;

lchild,rchild:btree;

end;

辨析

二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二

二叉树(3张)

叉树有两个主要差别：

1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；

2. 树的结点无左、右之分，而二叉树的结点有左、右之分。

遍历顺序

编辑

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。

先序遍历

首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树，C语言代码如下：

voidXXBL(tree*root){

//DoSomethingwithroot

if(root->lchild!=NULL)

XXBL(root->lchild);

if(root->rchild!=NULL)

XXBL(root->rchild);

}

中序遍历

首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树，C语言代码如下

voidZXBL(tree*root)

{

if(root->lchild!=NULL)

ZXBL(root->lchild);//DoSomethingwithroot

if(root->rchild!=NULL)

ZXBL(root->rchild);

}

后序遍历

首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根，C语言代码如下

voidHXBL(tree*root){

if(root->lchild!=NULL)

HXBL(root->lchild);

if(root->rchild!=NULL)

HXBL(root->rchild);//DoSomethingwithroot

}

层次遍历

即按照层次访问，通常用队列来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同）

线索二叉树

线索二叉树(保留遍历时结点在任一序列的前驱和后继的信息)：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。还需在结点结构中增加两个标志域LTag和RTag。LTag=0时，lchild域指示结点的左孩子，LTag=1时，lchild域指示结点的前驱；RTag=0时，rchild域指示结点的右孩子，RTag=1时，rchild域指示结点的后继。以这种结点结构构成的二叉线索链表，链表作为二叉树的存储结构，叫做其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。若对二叉树进行中序遍历，则所得的线索二叉树称为中序线索二叉树，线索链表称为为中序线索链表。线索二叉树是一种物理结构。

线索二叉树的存储结构

在中序线索树找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其后继；找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。

在后序线索树中找到结点的后继分三种情况：

若结点是二叉树的根，则其后继为空；若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；若结点是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按后序遍历列出的第一个结点。

数据结构定义为：

/*二叉线索存储表示*/typedefenum{Link,Thread}PointerTag;/* Link(0)：指针，Thread(1)：线索*/typedefstruct BiThrNode{ TElemType data;struct BiThrNode *lchild,*rchild;/*左右孩子指针*/PointerTag LTag,RTag;/* 左右标志 */}BiThrNode,*BiThrTree;

实现演示

编辑

范例二叉树：

B C

D E

此树的顺序结构为：ABCD##E

intmain()

{

node*p=newnode;

node*p=head;

head=p;

stringstr;

cin >>str;

creat(p,str,0)//默认根节点在str下标0的位置

return0;

}

//p为树的根节点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置

intmain()

{

node* p = newnode;

node* p = head;

head = p;

string str;

cin >> str;

creat(p, str, 0)//默认根节点在str下标0的位置

return0;

}

//p为树的根节点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置

voidcreat(node* p, string str, intr)

{

p->data = str[r];

if(str[r * 2 + 1] == '#'|| r * 2 + 1 > str.size() - 1)p->lch = NULL;

else

{

p->lch = newnode;

creat(p->lch, str, r * 2 + 1);

}

if(str[r * 2 + 2] == '#'|| r * 2 + 2 > str.size() - 1)p->rch = NULL;

else

{

p->rch = newnode;

creat(p->rch, str, r * 2 + 2);

}

词条图册更多图册

词条图片(3)

二叉树(3)

计算机科学中的树

二叉树▪二叉树▪二叉查找树▪ 版权声明：本文来源简书，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://www.jianshu.com/p/bf597ef95777
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-01-08 08:17:05

阅读 ( 1739 )

分类：算法

大数据算法

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看