数据结构，数据结构与算法
线性表：零个或多个数据元素的有限序列（注：以下都是用的整型数据模拟）
一 顺序存储结构（用一段地址连续的存储单元一次存储线性表的数据元素）
1.1 三个属性:存储空间的起始位置；最大存储容量；当前长度
注：数组长度是存放线性表的存储空间的长度（一般是不变的），不过语言可以动态增加容量，会带来性能损耗；
线性表长度是数据元素的个数；
线性表是从1开始数的，对应数组0的位置
1.2 获取元素、插入元素、删除元素(代码中展示)
1.3 顺序结构优缺点：
优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速地存取表中任一位置元素
缺点：插入和删除操作需要移动大量的元素；当线性表长度裱花较大时，难以确定存储空间容量；造成存储空间'碎片'
<span> //</span><span>用一维数组模拟线性表</span>
<span>class</span><span> Sequential_Structure
{
</span><span>//</span><span>线性表的长度</span>
<span>private</span> <span>$num</span> = 0<span>;
</span><span>//</span><span>数组长度</span>
<span>private</span> <span>$len</span> = 0<span>;
</span><span>//</span><span>数组模拟</span>
<span>private</span> <span>$arr</span> = <span>array</span><span>();
</span><span>/*</span><span>*
* 初始化结构
* @param Int $len 最大数组长度
* @param Array $arr 数组
* @return
</span><span>*/</span>
<span>public</span> <span>function</span> __construct(<span>$len</span>, <span>Array</span> <span>$arr</span><span>)
{
</span><span>$this</span>->len = <span>$len</span><span>;
</span><span>$length</span> = <span>count</span>(<span>$arr</span><span>);
</span><span>if</span>(<span>$length</span> > 0 && <span>$length</span> <= <span>$len</span><span>)
{
</span><span>$this</span>->arr = <span>$arr</span><span>;
</span><span>$this</span>->num = <span>$length</span><span>;
}
}
</span><span>/*</span><span>*
* 获取线性表元素
* @param Int $i 需要获取的第几个元素
* @return
</span><span>*/</span>
<span>public</span> <span>function</span> get_elem(<span>$i</span><span>)
{
</span><span>if</span>(<span>$this</span>->num == 0 || <span>$i</span> < 1 || <span>$i</span> > <span>$this</span>->num) <span>//</span><span>判断查找是否合理</span>
<span>return</span> <span>false</span><span>;
</span><span>return</span> <span>$this</span>->arr[<span>$i</span>-1]; <span>//</span><span>返回数据，时间复杂度O(1)</span>
<span> }
</span><span>/*</span><span>*
* 插入元素（顺序结构中，插入元素后，后面所有的数据都要后移，平均时间复杂度O(1)）:
* 如果插入位置不合理，失败
* 如果线性长度大于数组长度，则返回错误或者动态增加容量
* 从最后一个元素开始向前遍历到第i个位置，分别将它们向后移动一个位置
* 将元素插入i位置
* @param Int $i 需要插入到第几个元素
* @param Int $elem 插入的节点
* @return bool
</span><span>*/</span>
<span>public</span> <span>function</span> insert_elem(<span>$i</span>, <span>$elem</span><span>)
{
</span><span>if</span>(<span>$this</span>->num == <span>$this</span>->len) <span>//</span><span>顺序线性表已满</span>
<span>return</span> <span>false</span><span>;
</span><span>if</span>(<span>$i</span> < 1 || <span>$i</span> > (<span>$this</span>->num+1)) <span>//</span><span>i不在范围之内</span>
<span>return</span> <span>false</span><span>;
</span><span>if</span> (<span>$i</span> <= <span>$this</span>->num) <span>//</span><span>若数据插入位置不在表尾</span>
<span> {
</span><span>for</span>(<span>$k</span> = <span>$this</span>->num-1; <span>$k</span> >= <span>$i</span>-1; --<span>$k</span>) <span>//</span><span>后面所有元素往后移动一位</span>
<span>$this</span>->arr[<span>$k</span>+1] = <span>$this</span>->arr[<span>$k</span><span>];
}
</span><span>$this</span>->arr[<span>$i</span>-1] = <span>$elem</span>; <span>//</span><span>插入元素</span>
++<span>$this</span>-><span>num;
</span><span>return</span> <span>true</span><span>;
}
</span><span>/*</span><span>*
* 删除元素（顺序结构中，插入元素后，后面所有的数据都要前移，平均时间复杂度O(1)）:
* 如果删除位置不合理，失败
* 将元素删除
* 从最后删除元素开始向后遍历到最后，分别将它们向前移动一个位置
* @param Int $i 需要仓储的第几个元素
* @return bool
</span><span>*/</span>
<span>public</span> <span>function</span> delete_elem(<span>$i</span><span>)
{
</span><span>if</span>(<span>$this</span>->num == 0) <span>//</span><span>线性表为空</span>
<span>return</span> <span>false</span><span>;
</span><span>if</span>(<span>$i</span> < 1 || <span>$i</span> > <span>$this</span>->num) <span>//</span><span>删除位置不正确</span>
<span>return</span> <span>false</span><span>;
</span><span>if</span>(<span>$i</span> < <span>$this</span>->num) <span>//</span><span>删除位置不是表尾</span>
<span> {
</span><span>for</span>(<span>$k</span> = <span>$i</span>; <span>$k</span> < <span>$this</span>->num; ++<span>$k</span>) <span>//</span><span>前移</span>
<span>$this</span>->arr[<span>$k</span>-1] = <span>$this</span>->arr[<span>$k</span><span>];
}
</span><span>unset</span>(<span>$this</span>->arr[<span>$this</span>->num-1<span>]);
</span>--<span>$this</span>-><span>num;
</span><span>return</span> <span>true</span><span>;
}
</span><span>/*</span><span>*
* 获取顺序表
* @return
</span><span>*/</span>
<span>public</span> <span>function</span><span> get_arr()
{
</span><span>return</span> <span>$this</span>-><span>arr;
}
</span><span>/*</span><span>*
* 获取长度
* @return
</span><span>*/</span>
<span>public</span> <span>function</span><span> get_len()
{
</span><span>return</span> <span>array</span>('num' => <span>$this</span>->num , 'len' => <span>$this</span>-><span>len);
}
}
</span><span>$link</span> = <span>new</span> Sequential_Structure(10,[1,4,8,7<span>]);
</span><span>echo</span> <span>$link</span>->get_elem(2<span>);
</span><span>var_dump</span>(<span>$link</span>->insert_elem(5,5<span>));
</span><span>var_dump</span>(<span>$link</span>-><span>get_arr());
</span><span>var_dump</span>(<span>$link</span>-><span>get_len());
</span><span>var_dump</span>(<span>$link</span>->delete_elem(1<span>));
</span><span>var_dump</span>(<span>$link</span>-><span>get_arr());
</span><span>var_dump</span>(<span>$link</span>->get_len());
<span>输出:<br />boolean</span> <span>true</span> <span>array</span> (size=5<span>) </span>0 => int 1 1 => int 4 2 => int 8 3 => int 7 4 => int 5 <span>array</span> (size=2<span>) </span>'num' => int 5 'len' => int 10 <span>boolean</span> <span>true</span> <span>array</span> (size=4<span>) </span>0 => int 4 1 => int 8 2 => int 7 3 => int 5 <span>array</span> (size=2<span>) </span>'num' => int 4 'len' => int 10
二 链表存储结构（n个节点链结成一个链表）
2.1 单链表（用数组模拟）
2.1.1 链表中第一个结点的存储位置为头指针(通常为了方便对链表进行操作，会在单链表的第一个结点前附设一个头结点)
注 头指针：指向链表第一个结点的指针，若链表有头结点，这是指向头结点的指针；无论链表是否为空，头指针不为空
头结点：放在第一元素的结点之前
<span>/*</span><span>*
* 用一维数组模拟线性表
* array('data'=>data,'cur'=>cur) data为存放数据，cur为下个数组元素下标
</span><span>*/</span>
<span>class</span><span> Simple_Link
{
</span><span>//</span><span>数组长度</span>
<span>private</span> <span>$len</span> = 0<span>;
</span><span>//</span><span>数组模拟</span>
<span>private</span> <span>$arr</span> = <span>array</span><span>();
</span><span>//</span><span>数组中空闲的下标</span>
<span>private</span> <span>$space_arr</span> = <span>array</span><span>();
</span><span>/*</span><span>*
* 初始化结构
* @param Int $len 最大数组长度
* @param Array $arr 数组
* @return
</span><span>*/</span>
<span>public</span> <span>function</span> __construct(<span>$len</span>, <span>Array</span> <span>$arr</span><span>)
{
</span><span>$this</span>->len = <span>$len</span><span>;
</span><span>$length</span> = <span>count</span>(<span>$arr</span><span>);
</span><span>$this</span>->arr[0]['data'] = <span>$length</span><span>;
</span><span>$this</span>->arr[0]['cur'] = 0<span>;
</span><span>for</span>(<span>$i</span> = 0; <span>$i</span> < <span>$length</span>; ++<span>$i</span><span>)
</span><span>$this</span>->arr[<span>$i</span>]['cur'] = <span>$i</span>+1; <span>//</span><span>模拟链表的指向</span>
<span>if</span>(<span>$length</span><span>)
</span><span>$this</span>->arr[<span>$length</span>]['cur'] = 0; <span>//</span><span>最后一个结点指针空</span>
<span>for</span>(<span>$i</span> = <span>$length</span> + 1; <span>$i</span> <= <span>$len</span>-<span>$length</span> ; ++<span>$i</span>) <span>//</span><span>空闲数组</span>
<span>array_unshift</span>(<span>$this</span>->space_arr,<span>$i</span><span>);
}
</span><span>/*</span><span>*
* 获取线性表元素：
* 初始化$j从1开始
* 当$j<$i，遍历链表
* @param Int $i 需要获取的第几个元素
* @return
</span><span>*/</span>
<span>public</span> <span>function</span> get_elem(<span>$i</span><span>)
{
</span><span>if</span>(<span>$i</span> < 1 || <span>$i</span> > <span>$this</span>->arr[0]['data'<span>])
</span><span>return</span> <span>false</span><span>;
</span><span>$j</span> = 1<span>;
</span><span>$cur</span> = <span>$this</span>->arr[0]['cur']; <span>//</span><span>指向第一个结点</span>
<span>while</span>(<span>$j</span> < <span>$i</span><span>)
{
</span><span>$cur</span> = <span>$this</span>->arr[<span>$cur</span>]['cur'<span>];
</span>++<span>$j</span><span>;
}
</span><span>return</span> <span>$this</span>->arr[<span>$cur</span>]['data'<span>];
}
</span><span>/*</span><span>*
* 插入元素:
* 初始化$j从1开始
* 当$j<$i，遍历链表
* 将元素插入i位置
* @param Int $i 需要插入到第几个元素
* @param Int $elem 插入的节点
* @return bool
</span><span>*/</span>
<span>public</span> <span>function</span> insert_elem(<span>$i</span>, <span>$elem</span><span>)
{
</span><span>$len</span> = <span>$this</span>->arr[0]['data'] + 1<span>;
</span><span>if</span>(<span>$i</span> < 1 || <span>$i</span> > <span>$len</span><span>)
</span><span>return</span> <span>false</span><span>;
</span><span>$j</span> = <span>$this</span>->malloc(); <span>//</span><span>获取空闲下标</span>
<span>if</span>(!<span>$j</span><span>)
</span><span>return</span> <span>false</span><span>;
</span><span>$this</span>->arr[<span>$j</span>]['data'] = <span>$elem</span><span>;
</span><span>$k</span> = 1<span>;
</span><span>$index</span> = 0<span>;
</span><span>$cur</span> = !<span>empty</span>(<span>$this</span>->arr[0]['cur']) ? <span>$this</span>->arr[0]['cur'] : 0; <span>//</span><span>指向第一个结点</span>
<span>while</span>(<span>$k</span> < <span>$i</span><span>)
{
</span><span>//</span><span>记录当前cur和下一个cur</span>
<span>$index</span> = <span>$cur</span><span>;
</span><span>$cur</span> = <span>$this</span>->arr[<span>$index</span>]['cur'<span>];
</span>++<span>$k</span><span>;
}
</span><span>//</span><span>改变指针指向</span>
<span>$this</span>->arr[<span>$index</span>]['cur'] = <span>$j</span><span>;
</span><span>$this</span>->arr[<span>$j</span>]['cur'] = <span>$cur</span><span>;
</span>++<span>$this</span>->arr[0]['data'<span>];
</span><span>return</span> <span>true</span><span>;
}
</span><span>/*</span><span>*
* 删除元素:
* 初始化$j从1开始
* 当$j<$i，遍历链表
* 将i位置删除
* @param Int $i 需要删除第几个元素
* @return bool
</span><span>*/</span>
<span>public</span> <span>function</span> delete_elem(<span>$i</span><span>)
{
</span><span>$len</span> = <span>$this</span>->arr[0]['data'<span>];
</span><span>if</span>(<span>$i</span> < 1 || <span>$i</span> > <span>$len</span><span>)
</span><span>return</span> <span>false</span><span>;
</span><span>$k</span> = 1<span>;
</span><span>$index</span> = 0<span>;
</span><span>$cur</span> = !<span>empty</span>(<span>$this</span>->arr[0]['cur']) ? <span>$this</span>->arr[0]['cur'] : 0; <span>//</span><span>指向第一个结点</span>
<span>while</span>(<span>$k</span> < <span>$i</span><span>)
{
</span><span>//</span><span>记录当前cur和下一个cur</span>
<span>$index</span> = <span>$cur</span><span>;
</span><span>$cur</span> = <span>$this</span>->arr[<span>$index</span>]['cur'<span>];
</span>++<span>$k</span><span>;
}
</span><span>//</span><span>改变指针指向</span>
<span>$this</span>->arr[<span>$index</span>]['cur'] = <span>$this</span>->arr[<span>$cur</span>]['cur'<span>];
</span><span>$this</span>->free(<span>$cur</span><span>);
</span><span>unset</span>(<span>$this</span>->arr[<span>$cur</span><span>]);
</span>--<span>$this</span>->arr[0]['data'<span>];
</span><span>return</span> <span>true</span><span>;
}
</span><span>/*</span><span>*
* 获取空闲的结点下标，也就是相当于申请一个空结点
* @return
</span><span>*/</span>
<span>private</span> <span>function</span><span> malloc()
{
</span><span>if</span>(<span>empty</span>(<span>$this</span>-><span>space_arr))
</span><span>return</span> <span>false</span><span>;
</span><span>return</span> <span>array_pop</span>(<span>$this</span>-><span>space_arr);
}
</span><span>/*</span><span>*
* 释放结点
* @param Int $cur 需要回收的结点下标
</span><span>*/</span>
<span>private</span> <span>function</span> free(<span>$cur</span><span>)
{
</span><span>array_push</span>(<span>$this</span>->space_arr, <span>$cur</span><span>);
}
</span><span>/*</span><span>*
* 打印
* @return
</span><span>*/</span>
<span>public</span> <span>function</span><span> print_arr()
{
</span><span>$i</span> = 0<span>;
</span><span>if</span>(!<span>empty</span>(<span>$this</span>->arr[0]['data'<span>]))
{ </span><span>while</span>(<span>$this</span>->arr[<span>$i</span>]['cur'<span>])
{
</span><span>$i</span> = <span>$this</span>->arr[<span>$i</span>]['cur'<span>];
</span><span>echo</span> <span>$this</span>->arr[<span>$i</span>]['data'].' '<span>;
}
}
}
</span><span>/*</span><span>*
* 获取长度
* @return
</span><span>*/</span>
<span>public</span> <span>function</span><span> get_len()
{
</span><span>return</span> <span>array</span>('num' => <span>$this</span>->arr[0]['data'] , 'len' => <span>$this</span>-><span>len);
}
}
</span><span>$link</span> = <span>new</span> Simple_Link(10,<span>array</span><span>());
</span><span>var_dump</span>(<span>$link</span>->insert_elem(1,5<span>));
</span><span>var_dump</span>(<span>$link</span>->insert_elem(2,4<span>));
</span><span>var_dump</span>(<span>$link</span>->insert_elem(1,6<span>));
</span><span>var_dump</span>(<span>$link</span>->delete_elem(3<span>));
</span><span>echo</span> <span>$link</span>-><span>print_arr();
</span><span>var_dump</span>(<span>$link</span>-><span>get_len());
输出：
</span><span>boolean</span> <span>true</span>
<span>boolean</span> <span>true</span>
<span>boolean</span> <span>true</span>
<span>boolean</span> <span>true</span>
6 5
<span>array</span> (size=2<span>)
</span>'num' => int 2
'len' => int 10
성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
핫 AI 도구
Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱
AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.
Undress AI Tool
무료로 이미지를 벗다
Clothoff.io
AI 옷 제거제
AI Hentai Generator
AI Hentai를 무료로 생성하십시오.
인기 기사
R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
어 ass 신 크리드 그림자 : 조개 수수께끼 솔루션
2 몇 주 전ByDDD
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25 : Myrise에서 모든 것을 잠금 해제하는 방법
4 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
뜨거운 도구
드림위버 CS6
시각적 웹 개발 도구
맨티스BT
Mantis는 제품 결함 추적을 돕기 위해 설계된 배포하기 쉬운 웹 기반 결함 추적 도구입니다. PHP, MySQL 및 웹 서버가 필요합니다. 데모 및 호스팅 서비스를 확인해 보세요.
DVWA
DVWA(Damn Vulnerable Web App)는 매우 취약한 PHP/MySQL 웹 애플리케이션입니다. 주요 목표는 보안 전문가가 법적 환경에서 자신의 기술과 도구를 테스트하고, 웹 개발자가 웹 응용 프로그램 보안 프로세스를 더 잘 이해할 수 있도록 돕고, 교사/학생이 교실 환경 웹 응용 프로그램에서 가르치고 배울 수 있도록 돕는 것입니다. 보안. DVWA의 목표는 다양한 난이도의 간단하고 간단한 인터페이스를 통해 가장 일반적인 웹 취약점 중 일부를 연습하는 것입니다. 이 소프트웨어는
MinGW - Windows용 미니멀리스트 GNU
이 프로젝트는 osdn.net/projects/mingw로 마이그레이션되는 중입니다. 계속해서 그곳에서 우리를 팔로우할 수 있습니다. MinGW: GCC(GNU Compiler Collection)의 기본 Windows 포트로, 기본 Windows 애플리케이션을 구축하기 위한 무료 배포 가능 가져오기 라이브러리 및 헤더 파일로 C99 기능을 지원하는 MSVC 런타임에 대한 확장이 포함되어 있습니다. 모든 MinGW 소프트웨어는 64비트 Windows 플랫폼에서 실행될 수 있습니다.
SecList
SecLists는 최고의 보안 테스터의 동반자입니다. 보안 평가 시 자주 사용되는 다양한 유형의 목록을 한 곳에 모아 놓은 것입니다. SecLists는 보안 테스터에게 필요할 수 있는 모든 목록을 편리하게 제공하여 보안 테스트를 더욱 효율적이고 생산적으로 만드는 데 도움이 됩니다. 목록 유형에는 사용자 이름, 비밀번호, URL, 퍼징 페이로드, 민감한 데이터 패턴, 웹 셸 등이 포함됩니다. 테스터는 이 저장소를 새로운 테스트 시스템으로 간단히 가져올 수 있으며 필요한 모든 유형의 목록에 액세스할 수 있습니다.
