算法导论_第十章_基本数据结构
队列和栈：
队列为先进先出，栈为先进后出。
其可以用数组和链表实现。
队列代码如下：
/*************************************************************************
> File Name: queue.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月30日 星期四 10时39分08秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f
#define LEN 5
using namespace std;
typedef long long ll;
int dequeue();
int enqueue(int x);
bool queue_empty();
bool queue_full();
int queue[LEN+1];
int head=1,tail=1;
int main(int argc,char *argv[])
{
enqueue(1);
for(int i=1;i<=LEN;i++) printf("%d ",queue[i]);
printf("\nhead=%d\ntail=%d\n\n",head,tail);
enqueue(2);
for(int i=1;i<=LEN;i++) printf("%d ",queue[i]);
printf("\nhead=%d\ntail=%d\n\n",head,tail);
enqueue(3);
for(int i=1;i<=LEN;i++) printf("%d ",queue[i]);
printf("\nhead=%d\ntail=%d\n\n",head,tail);
printf("%d\n",dequeue());
for(int i=1;i<=LEN;i++) printf("%d ",queue[i]);
printf("\nhead=%d\ntail=%d\n\n",head,tail);
enqueue(1);
for(int i=1;i<=LEN;i++) printf("%d ",queue[i]);
printf("\nhead=%d\ntail=%d\n\n",head,tail);
enqueue(2);
for(int i=1;i<=LEN;i++) printf("%d ",queue[i]);
printf("\nhead=%d\ntail=%d\n\n",head,tail);
enqueue(3);
for(int i=1;i<=LEN;i++) printf("%d ",queue[i]);
printf("\nhead=%d\ntail=%d\n\n",head,tail);
return 0;
}
int enqueue(int x)//入队
{
if(queue_full())
{
printf("the queue is full!\n");
return 0;
}
queue[tail]=x;
if(tail==LEN)
tail=1;
else
tail++;
}
int dequeue()//出队
{
if(queue_empty())
{
printf("the queue is empty!");
return 0;
}
int x=queue[head];
if(head==LEN)
head=1;
else
head++;
return x;
}
bool queue_empty()//判断是否为空
{
if(tail==head) return true;
else return false;
}
bool queue_full()//判断是否满
{
if(head==tail+1||head==1&&tail==LEN) return true;
else return false;
}
栈代码如下：
/*************************************************************************
> File Name: stack.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月30日 星期四 10时28分24秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int push(int key);
bool stack_empty();
int pop();
int stack[100];
int top=0;
int main(int argc,char *argv[])
{
memset(stack,0,sizeof(stack));
push(1);
for(int i=1;i<=10;i++)
printf("%d",stack[i]);
printf("\ntop=%d\n",top);
push(3);
for(int i=1;i<=10;i++)
printf("%d",stack[i]);
printf("\ntop=%d\n",top);
printf("pop=%d",pop());
return 0;
}
int push(int key)//入栈
{
top++;
stack[top]=key;
}
bool stack_empty()//判断栈是否为空
{
if(top==0) return true;
else return false;
}
int pop()//出栈
{
if(stack_empty())
{
printf("the stack is empty!");
return 0;
}
else
return stack[top--];
}
链表：
双向链表，单向链表，循环链表。
其与数组不同的是，其在内存中不连续，用指针链接起来
指针和对象的实现
1.对象的多数组表示：
对象的每一个属性使用一个数组表示，可以用来表示
一组有相同属性的对象。
一个对象的所有属性的数组下标相同
key[]储存其关键值
next[]储存下一个节点位置
prev[]储存上一个节点位置
具体代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int main(int argc,char *argv[])
{
//该数组链表用来储存9->1->3
int arry[20];
memset(arry,0,sizeof(arry));
int head=3;
arry[3]=9; //key
arry[3+1] =7;//next
arry[3+2] =0;//prev
arry[7] =1;
arry[7+1] =14;
arry[7+2] =3;
arry[14] =3;
arry[14+1] =0;
arry[14+2] =7;
for(int i=1;i<=19;i++)
printf("%d ",arry[i]);
return 0;
}
2.对象的单数组表示
在一个数组中指针仅仅是该对象所在的第一个储存单元的地址，
要访问对象其他储存单元可以在指针上加上一个偏移量。
例如keynext prev对应的偏移量分别为0,1,2
则访问其时只需根据偏移量找到其元素
下面看例子的对应代码：
/*************************************************************************
> File Name: single_attay.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月30日 星期四 11时08分58秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f
#define N 6
using namespace std;
typedef long long ll;
int main(int argc,char *argv[])
{
//该数组链表用来储存9->1->3
int next[N];//下一个节点位置
int key[N];//关键值
int prev[N];//上一个节点位置
int head;
memset(next,0,sizeof(next));
memset(key,0,sizeof(key));
memset(prev,0,sizeof(prev));
head=3;
key[3] =9;
next[3]=5;
key[5] =1;
next[5]=2;
prev[5]=3;
prev[2]=5;
key[2] =3;
for(int i=1;i<N;i++)
printf("%d ",next[i]);
printf("\n");
for(int i=1;i<N;i++)
printf("%d ",key[i]);
printf("\n");
for(int i=1;i<N;i++)
printf("%d ",prev[i]);
return 0;
}
对象的分配与释放
用一个头节点为free的链表（自由表），表示其空余的空间，
然后对自由表进行操作，进行空间的分配与释放。
来看代码：
/*************************************************************************
> File Name: 10.3_objetc.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月30日 星期四 09时12分15秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f
#define N 6
using namespace std;
int _free=0;
int allocate_object(int next[],int key[],int prev[]);
void free_object(int x,int next[]);
typedef long long ll;
int main(int argc,char *argv[])
{
//该数组链表用来储存9->1->3
int next[N];
int key[N];
int prev[N];
int head;
memset(next,0,sizeof(next));
memset(key,0,sizeof(key));
memset(prev,0,sizeof(prev));
head=3;
key[3] =9;
next[3]=5;
key[5] =1;
next[5]=2;
prev[5]=3;
prev[2]=5;
key[2] =3;
for(int i=1;i<N;i++)
printf("%d ",next[i]);
printf("\n");
for(int i=1;i<N;i++)
printf("%d ",key[i]);
printf("\n");
for(int i=1;i<N;i++)
printf("%d ",prev[i]);
printf("\nfree=%d\n",_free);
_free=1;//空链表头节点
next[1]=4;
printf("\n\n");
for(int i=1;i<N;i++)
printf("%d ",next[i]);
printf("\n");
for(int i=1;i<N;i++)
printf("%d ",key[i]);
printf("\n");
for(int i=1;i<N;i++)
printf("%d ",prev[i]);
printf("\nfree=%d\n",_free);
int temp=allocate_object(next,key,prev);
if(temp==0) printf("无可用的节点！\n");
else
printf("\n\n%d可用",temp);//返回一个空的节点
printf("\nfree=%d\n\n\n\n",_free);
free_object(5,next);//释放节点5后的情况
for(int i=1;i<N;i++)
printf("%d ",next[i]);
printf("\n");
for(int i=1;i<N;i++)
printf("%d ",key[i]);
printf("\n");
for(int i=1;i<N;i++)
printf("%d ",prev[i]);
printf("\nfree=%d\n",_free);
return 0;
}
int allocate_object(int next[],int key[],int prev[])//根据空链表，返回一个可用的节点
{
if(free==0) return 0;
else
{
int x=_free;
_free=next[x];
return x;
}
}
void free_object(int x,int next[])//释放一个节点，并把其添加到空链表里
{
next[x]=_free;
_free=x;
}
其实可以多个链表共有一个自由表，而且多个链表和自由表位置上
可能交错在一起，不过一个位置只能属于一个链表。
有根树的表示：
二叉树：
一个二叉树包括其父节点指针，指向左儿子节点的指针和
指向右儿子节点的指针还有其卫星数据。
父节点为NULL的表示其为根节点
如果没有左儿子，左儿子节点为NULL，没有右儿子，则右儿子节点为空。
多叉树：
利用左孩子右兄弟表示法：
每个节点都包含一个父节点指针p，且T.root指向树T的根节点。
其含有另外两个节点：
1.x.left-child指向节点x最左边的孩子节点
2.x.right-sibling指向x右侧的兄弟
如果节点没有孩子节点，则x.left-child为NULL
如果节点x是其父节点的最右孩子，则x.right-sibling为NULL