13518219792
数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。
成都创新互联服务项目包括龙湖网站建设、龙湖网站制作、龙湖网页制作以及龙湖网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，龙湖网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到龙湖省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
使用php实现的基本的数据结构和算法，什么二叉树、二叉搜索树、AVL树、B树、链表和常见排序、搜索算法等等，而且全部是使用面向对象来实现的，确是是很强。
#include stdio.h
#include stdlib.h
#include string.h
//定义顺序串
#define MaxSize 30
typedef struct
{
char data[MaxSize];
int len;
}SqString;
//串的子串个数(顺序串)
int SubNum(SqString s)
{
int n;
n=1+(s.len+1)*s.len/2;
return n;
}
//串的匹配查询(顺序串)
int StrIndex(SqString s,SqString t)//s为主串,t为模式串
{
int i=0,j=0;
while(is.lenjt.len)//是否到末尾
{
if(s.data[i]==t.data[j])//主串与模式串逐一匹配
{
i++;
j++;
}
else //否则，回溯重新开始下一次匹配
{
i=i-j+1; //主串从下一个位置开始
j=0; //模式串从头开始
}
}
if(j=t.len) //如果匹配成功
return (i-t.len); //返回主串第一个下标
else
return -1; //匹配失败,返回-1
}
//串的连接
//将串1和串2合并成新串,原串保留
int Concat(SqString str1,SqString str2,SqString str,int maxlen)
{
int i;
if(str1.len + str2.len maxlen)//长度之和不能超过maxlen
{
printf("两串合并后的长度超过规定长度.\n");
return 0;
}
else
{
for(i=0;istr1.len;i++)
str.data[i]=str1.data[i];//将串1复制给新串
for(i=0;istr2.len;i++)
str.data[str1.len+i]=str2.data[i];//将串2复制给新串
str.data[str1.len+i]='\0';//置结束标志
str.len=str1.len+str2.len;//计算长度和
}
return 1;
}
//串的替换
//串1从第i字符开始的j个字符用串2替换，生成新串
int Replace(SqString str1,int i,int j,SqString str2,SqString str)
{
int m,n;
if(j!=str2.len)//如果替换长度不等于串2,退出
{
printf("替换长度与串2不等.\n");
return 0;
}
if(i+j-1=str1.len)//i开始j的长度在串1之内
{
for(m=0;mi-1;m++)//拷贝串1中0到i-1之间字符
str.data[m]=str1.data[m];
for(n=0;nstr2.len;n++)//拷贝串2的所有字符
str.data[m++]=str2.data[n];
for(n=i+j-1;nstr1.len;n++)//拷贝串1从i+j-1之后的所以字符
str.data[m++]=str1.data[n];
str.data[m]='\0';//置结束标志
str.len=m;//置新串长度
}
else //超过，置长度为0
{
str.data[0]='\0';//置结束标志
str.len=0;
}
return 1;
}
//串中删除字符ch
void Delch(SqString str,char ch)
{
int i,j;
for(i=0;istr.len;i++)//遍历元素
{
while(str.data[i]==ch)//如果为ch,将后面元素前移,直到不等于ch为止
{
for(j=i;jstr.len;j++)
str.data[j]=str.data[j+1];//将后面元素前移
str.len=str.len-1;//长度减一
}
}
}
//删除串中从第i个字符开始j个字符
void Delsub(SqString str,int i,int j)
{
int k;
if(i+j-1str.len)
{
printf("删除子串长度超过主串长度.\n");
}
else
{
for(k=i+j-1;kstr.len;k++)//遍历元素
{
str.data[k-j]=str.data[k];//后面元素前移
}
str.len=str.len-j; //长度减少
str.data[str.len]='\0'; //置末尾结束
}
}
//串逆序
void ReverseSq(SqString str)
{
int i,j;
char t;
i=0;
j=str.len-1;//首尾调换
while(ij)
{
t=str.data[i];
str.data[i]=str.data[j];
str.data[j]=t;
i++;
j--;
}
}
//子串只有一个通配符?,可以代表任意一个字符，返回匹配子串第一次出现位置
int Patten_index(SqString subs,SqString str)
{
int i,j,k;
for(i=0;istr.len;i++)
{
for(j=i,k=0;(str.data[j]==subs.data[k])||(subs.data[k]=='?');j++,k++)
if(subs.data[k+1]=='\0')
return(i+1);
}
return -1;
}
//求最长等值子串串头位置和子串
void EqsubString(SqString str)
{
int i,j;
int pos,max,count;
pos=0;
max=1;
for(i=0,j=1;str.data[i]!='\0'str.data[j]!='\0';i=j,j++)
{
count=1;
while(str.data[i]==str.data[j])
{
j++;
count++;
}
if(count max)
{
max=count;
pos=i;
}
}
if(max1)
{
printf("位置为:%d的最大等值子串:",pos+1);
for(i=pos;ipos+max;i++)
printf("%c",str.data[i]);
}
else
printf("无最大等值子串.");
printf("\n");
}
int main()
{
SqString str1,str2;
SqString str;
strcpy(str1.data,"abcdefghijkl");
str1.len=strlen(str1.data);
strcpy(str2.data,"aaad");
str2.len=strlen(str2.data);
printf("str1=%d,%s\nstr2=%d,%s\n",str1.len,str1.data,str2.len,str2.data);
//1 串的匹配
printf("串的匹配\n");
if(StrIndex(str1,str2)!=-1)
printf("匹配成功!\n");
else
printf("匹配失败!\n");
printf("\n");
//2 串的连接
printf("串的连接\n");
if(Concat(str1,str2,str,MaxSize))
printf("合并后的新串%d,%s\n",str.len,str.data);
else
printf("合并出错.\n");
printf("\n");
//3 串的替换
printf("串的替换\n");
if(Replace(str1,9,4,str2,str))
printf("替换后的新串长度%d,%s\n",str.len,str.data);
printf("\n");
//4 子串的个数
printf("子串的个数\n");
printf("%s子串个数为:%d\n",str.data,SubNum(str));
printf("\n");
//5 删除一个字符
printf("删除一个字符'b'\n");
printf("原串%s\n",str.data);
Delch(str,'b');
printf("删除后串长度%d,%s\n",str.len,str.data);
printf("\n");
//6 串中从第i个字符开始j个字符
printf("删除从第2个位置删除3个字符\n");
Delsub(str,2,3);
printf("删除子串后串长度%d,%s\n",str.len,str.data);
printf("\n");
//7 串逆序
printf("串逆序\n");
ReverseSq(str);
printf("串逆序长度%d,%s\n",str.len,str.data);
printf("\n");
//8 子串通配符?匹配
printf("子串通配符?匹配:g?\n");
int x;
SqString subs;
strcpy(subs.data,"g?");
subs.len=strlen(subs.data);
if((x=Patten_index(subs,str))0)
printf("在%d 匹配成功!\n",x);
else
printf("匹配失败!\n");
printf("\n");
//9 求最长等值子串串头位置和子串
printf("求最长等值子串串头位置和子串\n");
EqsubString(str);
printf("\n");
return 0;
}
数据库属于 IO 密集型的应用程序，其主要职责就是数据的管理及存储工作。而我们知道，从内存中读取一个数据库的时间是微秒级别，而从一块普通硬盘上读取一个IO是在毫秒级别，二者相差3个数量级。所以，要优化数据库，首先第一步需要优化的就是 IO，尽可能将磁盘IO转化为内存IO。本文先从 MySQL 数据库IO相关参数(缓存参数)的角度来看看可以通过哪些参数进行IO优化：
•query_cache_size/query_cache_type (global)
Query cache 作用于整个 MySQL Instance，主要用来缓存 MySQL 中的 ResultSet，也就是一条SQL语句执行的结果集，所以仅仅只能针对select语句。当我们打开了 Query Cache 功能，MySQL在接受到一条select语句的请求后，如果该语句满足Query Cache的要求(未显式说明不允许使用Query Cache，或者已经显式申明需要使用Query Cache)，MySQL 会直接根据预先设定好的HASH算法将接受到的select语句以字符串方式进行hash，然后到Query Cache 中直接查找是否已经缓存。也就是说，如果已经在缓存中，该select请求就会直接将数据返回，从而省略了后面所有的步骤(如 SQL语句的解析，优化器优化以及向存储引擎请求数据等)，极大的提高性能。
当然，Query Cache 也有一个致命的缺陷，那就是当某个表的数据有任何任何变化，都会导致所有引用了该表的select语句在Query Cache 中的缓存数据失效。所以，当我们的数据变化非常频繁的情况下，使用Query Cache 可能会得不偿失。
Query Cache的使用需要多个参数配合，其中最为关键的是 query_cache_size 和 query_cache_type ，前者设置用于缓存 ResultSet 的内存大小，后者设置在何场景下使用 Query Cache。在以往的经验来看，如果不是用来缓存基本不变的数据的MySQL数据库，query_cache_size 一般 256MB 是一个比较合适的大小。当然，这可以通过计算Query Cache的命中率(Qcache_hits/(Qcache_hits+Qcache_inserts)*100))来进行调整。query_cache_type可以设置为0(OFF)，1(ON)或者2(DEMOND)，分别表示完全不使用query cache，除显式要求不使用query cache(使用sql_no_cache)之外的所有的select都使用query cache，只有显示要求才使用query cache(使用sql_cache)。
•binlog_cache_size (global)
Binlog Cache 用于在打开了二进制日志(binlog)记录功能的环境，是 MySQL 用来提高binlog的记录效率而设计的一个用于短时间内临时缓存binlog数据的内存区域。
一般来说，如果我们的数据库中没有什么大事务，写入也不是特别频繁，2MB～4MB是一个合适的选择。但是如果我们的数据库大事务较多，写入量比较大，可与适当调高binlog_cache_size。同时，我们可以通过binlog_cache_use 以及 binlog_cache_disk_use来分析设置的binlog_cache_size是否足够，是否有大量的binlog_cache由于内存大小不够而使用临时文件(binlog_cache_disk_use)来缓存了。
•key_buffer_size (global)
Key Buffer 可能是大家最为熟悉的一个 MySQL 缓存参数了，尤其是在 MySQL 没有更换默认存储引擎的时候，很多朋友可能会发现，默认的 MySQL 配置文件中设置最大的一个内存参数就是这个参数了。key_buffer_size 参数用来设置用于缓存 MyISAM存储引擎中索引文件的内存区域大小。如果我们有足够的内存，这个缓存区域最好是能够存放下我们所有的 MyISAM 引擎表的所有索引，以尽可能提高性能。
此外，当我们在使用MyISAM 存储的时候有一个及其重要的点需要注意，由于 MyISAM 引擎的特性限制了他仅仅只会缓存索引块到内存中，而不会缓存表数据库块。所以，我们的 SQL 一定要尽可能让过滤条件都在索引中，以便让缓存帮助我们提高查询效率。
•bulk_insert_buffer_size (thread)
和key_buffer_size一样，这个参数同样也仅作用于使用 MyISAM存储引擎，用来缓存批量插入数据的时候临时缓存写入数据。当我们使用如下几种数据写入语句的时候，会使用这个内存区域来缓存批量结构的数据以帮助批量写入数据文件：
insert … select …
insert … values (…) ,(…),(…)…
load data infile… into… (非空表)
•innodb_buffer_pool_size(global)
当我们使用InnoDB存储引擎的时候，innodb_buffer_pool_size 参数可能是影响我们性能的最为关键的一个参数了，他用来设置用于缓存 InnoDB 索引及数据块的内存区域大小，类似于 MyISAM 存储引擎的 key_buffer_size 参数，当然，可能更像是 Oracle 的 db_cache_size。简单来说，当我们操作一个 InnoDB 表的时候，返回的所有数据或者去数据过程中用到的任何一个索引块，都会在这个内存区域中走一遭。
和key_buffer_size 对于 MyISAM 引擎一样，innodb_buffer_pool_size 设置了 InnoDB 存储引擎需求最大的一块内存区域的大小，直接关系到 InnoDB存储引擎的性能，所以如果我们有足够的内存，尽可将该参数设置到足够打，将尽可能多的 InnoDB 的索引及数据都放入到该缓存区域中，直至全部。
我们可以通过 (Innodb_buffer_pool_read_requests – Innodb_buffer_pool_reads) / Innodb_buffer_pool_read_requests * 100% 计算缓存命中率，并根据命中率来调整 innodb_buffer_pool_size 参数大小进行优化。
•innodb_additional_mem_pool_size(global)
这个参数我们平时调整的可能不是太多，很多人都使用了默认值，可能很多人都不是太熟悉这个参数的作用。innodb_additional_mem_pool_size 设置了InnoDB存储引擎用来存放数据字典信息以及一些内部数据结构的内存空间大小，所以当我们一个MySQL Instance中的数据库对象非常多的时候，是需要适当调整该参数的大小以确保所有数据都能存放在内存中提高访问效率的。
这个参数大小是否足够还是比较容易知道的，因为当过小的时候，MySQL 会记录 Warning 信息到数据库的 error log 中，这时候你就知道该调整这个参数大小了。
•innodb_log_buffer_size (global)
这是 InnoDB 存储引擎的事务日志所使用的缓冲区。类似于 Binlog Buffer，InnoDB 在写事务日志的时候，为了提高性能，也是先将信息写入 Innofb Log Buffer 中，当满足 innodb_flush_log_trx_commit 参数所设置的相应条件(或者日志缓冲区写满)之后，才会将日志写到文件(或者同步到磁盘)中。可以通过 innodb_log_buffer_size 参数设置其可以使用的最大内存空间。
注：innodb_flush_log_trx_commit 参数对 InnoDB Log 的写入性能有非常关键的影响。该参数可以设置为0，1，2，解释如下：
0：log buffer中的数据将以每秒一次的频率写入到log file中，且同时会进行文件系统到磁盘的同步操作，但是每个事务的commit并不会触发任何log buffer 到log file的刷新或者文件系统到磁盘的刷新操作;
1：在每次事务提交的时候将log buffer 中的数据都会写入到log file，同时也会触发文件系统到磁盘的同步;
2：事务提交会触发log buffer 到log file的刷新，但并不会触发磁盘文件系统到磁盘的同步。此外，每秒会有一次文件系统到磁盘同步操作。
此外，MySQL文档中还提到，这几种设置中的每秒同步一次的机制，可能并不会完全确保非常准确的每秒就一定会发生同步，还取决于进程调度的问题。实际上，InnoDB 能否真正满足此参数所设置值代表的意义正常 Recovery 还是受到了不同 OS 下文件系统以及磁盘本身的限制，可能有些时候在并没有真正完成磁盘同步的情况下也会告诉 mysqld 已经完成了磁盘同步。
•innodb_max_dirty_pages_pct (global)
这个参数和上面的各个参数不同，他不是用来设置用于缓存某种数据的内存大小的一个参数，而是用来控制在 InnoDB Buffer Pool 中可以不用写入数据文件中的Dirty Page 的比例(已经被修但还没有从内存中写入到数据文件的脏数据)。这个比例值越大，从内存到磁盘的写入操作就会相对减少，所以能够一定程度下减少写入操作的磁盘IO。
但是，如果这个比例值过大，当数据库 Crash 之后重启的时间可能就会很长，因为会有大量的事务数据需要从日志文件恢复出来写入数据文件中。同时，过大的比例值同时可能也会造成在达到比例设定上限后的 flush 操作“过猛”而导致性能波动很大。
上面这几个参数是 MySQL 中为了减少磁盘物理IO而设计的主要参数，对 MySQL 的性能起到了至关重要的作用。
队列这种数据结构更简单，就像我们生活中排队一样，它的特性是先进先出(FIFO)。
PHP
SPL中SplQueue类就是实现队列操作，和栈一样，它也可以继承双链表(SplDoublyLinkedList)轻松实现。
SplQueue类摘要如下：
SplQueue简单使用如下：
复制代码
代码如下:
$queue
=
new
SplQueue();
/**
*
可见队列和双链表的区别就是IteratorMode改变了而已，栈的IteratorMode只能为：
*
（1）SplDoublyLinkedList::IT_MODE_FIFO
|
SplDoublyLinkedList::IT_MODE_KEEP
（默认值,迭代后数据保存）
*
（2）SplDoublyLinkedList::IT_MODE_FIFO
|
SplDoublyLinkedList::IT_MODE_DELETE
（迭代后数据删除）
*/
$queue-setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO
|
SplDoublyLinkedList::IT_MODE_DELETE);
//SplQueue::enqueue()其实就是
SplDoublyLinkedList::push()
$queue-enqueue('a');
$queue-enqueue('b');
$queue-enqueue('c');
//SplQueue::dequeue()其实就是
SplDoublyLinkedList::shift()
print_r($queue-dequeue());
foreach($queue
as
$item)
{
echo
$item
.
PHP_EOL;
}
print_r($queue);
而优先队列SplPriorityQueue是基于堆(后文介绍)实现的。
SplPriorityQueue的类摘要如下：
SplPriorityQueue简单使用：
$pq
=
new
SplPriorityQueue();
$pq-insert('a',
10);
$pq-insert('b',
1);
$pq-insert('c',
8);
echo
$pq-count()
.PHP_EOL;
//3
echo
$pq-current()
.
PHP_EOL;
//a
/**
*
设置元素出队模式
*
SplPriorityQueue::EXTR_DATA
仅提取值
*
SplPriorityQueue::EXTR_PRIORITY
仅提取优先级
*
SplPriorityQueue::EXTR_BOTH
提取数组包含值和优先级
*/
$pq-setExtractFlags(SplPriorityQueue::EXTR_DATA);
while($pq-valid())
{
print_r($pq-current());
//a
c
b
$pq-next();
}
