最近慢慢开始复习数据结构这一块,那么这里用PHP也写一个链表结构吧。PHP本身是弱类型的语言,数据类型的约束会不够严格。虽然下面的代码能够实现链表的基本功能,但也许会存在一些我还没注意到的缺陷。如果你有更好的方案,也可以告诉我~
链表作为线性表的一种实现方式,有插入删除方便的优点,但不能对节点进行随机访问。同时,要想知道某一节点的前驱节点,必须从头节点开始遍历才能找到,这体现了单链表的方向性。下面用C语言简单实现一个单向链表。
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。这里给出整个栈的简单实现,使用链式栈,利用辅助栈提供min值查询。设计包含min函数的栈。
有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。现在需要解决的问题有以下两个:如何判断一个链表是不是这类链表?如果链表为存在环,如果找到环的入口点?
首先是创建一个树节点类,然后再创建一个二叉树类。打印完毕可发现,键值比根键值小的所有节点均在根的左边,反之则在右边,每个节点都是如此。但此树不是平衡树(AVL树),因此查询效率还是比较低,特别是如果是连成一直线,则效率达到最低,不能利用树的对数特性了。
数组是最基本的数据结构,关于数组的操作是程序员最经常用到的。这里将一些常用的操作写成函数。数组求和:给定一个含有n个元素的整型数组a,求a中所有元素的和。可能您会觉得很简单,是的,的确简单,但是为什么还要说呢,原因有二,第一,这道题要求用递归法,只用一行代码。第二,这是我人生中第一次面试时候遇到的题,意义特殊。
链表逆序就是把一个链表按照原来的链接顺序逆序实现(也就是将头变成尾,尾变成头)。编程思路:其实最关键的是先通过原来的链接顺序找到下个节点,然后再把前个节点反序。
以二维数组的遍历方式遍历一维数组。下面是5*6的表格数据,用一维数组存储。遍历,还是二维数组的遍历方式。第一个循环是行的循环,第二个是列的循环。
下面的程序,输入学生的成绩查询其学号。首先将输入的数字与数组的各元素匹配,若匹配的话,该数组元素的索引就是该学生的学号。然后就可以将这个数组元素输出。很明显,最坏的情况,什么也查不到,但整个数组遍历了。
单向链表是一个非常常见的数据结构,下面用JavaScript实现一个单向链表,能够加深对单向链表的理解。已经基本实现了。单链表的基本功能!看下面演示。
通过一次遍历找到单链表中倒数第n个节点,链表可能相当大,可使用辅助空间,但是辅助空间的数目必须固定,不能和n有关。单向链表的特点是遍历到末尾后不能反向重数N个节点。因此必须在到达尾部的同时找到倒数第N个节点。不管是顺数n个还是倒数n个,其实都是距离-标尺问题。标尺是一段距离可以用线段的两个端点来衡量,我们能够判断倒数第一个节点,因为他的next==NULL。
写一个函数,这个函数输出数组的第i个元素的地址及其对应的值。这个函数使用指针算术运算,并以 getAddress(&array[0], length) 的形式调用。第i个元素的地址就是 ptr + i,为了得到第i个元素的值,使用复饮用操作副(复位)*。所以 *(ptr + i) 表示位置 ptr + i 的内容而不是地址。
&在用于计算时就是取变量地址,如int* a = &b,就是将整型变量b的地址取出,赋值给整型指针a,a中的内容就是b的地址,所以a指向b。*在用于计算时,就是取指针所指向的地址中的值,如int b = *a,就是将整型指针a指向的地址中存放的内容赋值给整型变量b。C语言中,&符号大家一定很熟悉吧,它除了可以作为按位运算“与”之外还有更常用的功能——取变量地址。
copyright © 2009 简明现代魔法 学习、分享、进步 power by Gonn 感谢所有关心和支持本站的朋友们 |