文档介绍：网络游戏算法设计
第2章算法分析与数据结构
第2章算法分析与数据结构
数组
链表概念
链表操作
掌握数组
了解链表概念
掌握链表操作
第2章算法分析与数据结构
数组
链表概念
链表操作
数组
链表操作
第2章算法分析与数据结构
线性表
线性表是这样的数据对象,其实例形式为:(e1 ,e2 ,... en ),
其中n是有穷自然数。 e i是表中的元素,n是表的长度。元素本身的结构与线性表的结构无关。当n = 0时,表为空;当n > 0时,e1 是第一个元素,e n是最后一个元素
线性表有两种存储方式:顺序表和链表。
1)顺序表是把线性表的节点按逻辑次序存放在一组地址连续的单元里。
它的特点是用物理位置上的邻接关系来表示节点间的逻辑关系,这一特点使用户可以随机存取表中的任意一个节点,但它也使得插入和删除操作会移动大量的节点。
第2章算法分析与数据结构
2)链表是用一组任意的存储单元(可以是连续的,也可以是不连续的)来存储线性表的各个数据元素。
线性表
每个元素除了需要储藏自身信息外,还需要存储一个指示其后继元素的信息(即直接后继的存储位置),这两部分信息组成了一个数据元素的存储结构,称为一个节点。每个节点包括两个域:数据域和指针域。数据域存储数据元素本身的信息,指针域是后续节点的指针,最后一个节点的指针域为空指针。
第一个节点称为首节点,它的地址存储在链表首节点指针中,链表中的每一个节点都是同一种结构类型。
第2章算法分析与数据结构
线性表
数组可用来表示线性表。
在顺序表的情况下,数组允许在表尾方便增加元素。但删除元素并不方便,因为此时必须频繁的移动各元素。若要插入新的元素,也必须移动元素的位置。
第2章算法分析与数据结构
线性表
bool DeleteArrayData(int array[], int size, int index)
{
if(index < 0 || index >= size){
cout << "数组下标越界" << endl;
return false;
}
  if(index == size - 1){
array[index] = 0;
return true;
}
for(int i = index + 1; i < size; i++){
array[i-1] = array[i];
}
return true;
}
第2章算法分析与数据结构
线性表
向数组中插入一个数值,则要把插入位置后面的每一个元素向后移动。空出要插入的位置,再把要插入的元素插入进去
第2章算法分析与数据结构
线性表
bool InsertArrayData(int array[], int size, int index, int data)
{
if(index < 0 || index >= size){
cout << "插入的位置错误" << endl;
return false;
}
if(index == size - 1){
array[index] = data;
return true;
}
for(int i = size-1; i > index; i--){
array[i] = array[i-1];
}
array[i] = data;
return true;
}
第2章算法分析与数据结构
线性表
链表
链表主要的优点就是可以方便的进行插入、删除操作,利用这一优点,可以在游戏设计过程中方便地管理大量的数据。
在链表中的每个元素都放在节点中进行描述。节点不必是连续的物理单元。每个节点中都包含了与该节点相关的其他节点的位置信息。这种关于其他节点的位置信息被称之为链或指针。
链表概念