《链表栈堆》由会员分享，可在线阅读，更多相关《链表栈堆（21页珍藏版）》请在金锄头文库上搜索。
1、链表，栈（堆栈）堆（堆积树）,不要把循环，条件等语句和函数当作你所编写程序的第一印象,山东大学 13级5班 郭京磊,数据结构：链表,链表是一种人类发明计算机的基本数据类型以后自己发明创造的一种数据结构 这些数据结构都是你自己编写的，遍历和插入删除合并等操作遵循你自己编写的方式和规则进行 何为链表？,链表是一种序列，支持插入操作,如果你将int数组序列中间插入一个数字，复杂度为O（n）意思就是你最坏要移动的数字是n数量级的（n为数组中元素个数） 链表可以快速地插入一个数字，用O（1）的常数时间即可完成 图例：,4,6,2,11,9,左边的如图所示的类是链表的结点类,链表就是由这些结点串联组成的，
2、插入数据的过程就是,链表的 最后一 个元素 的特征： next=null,start,Node的声明,public class Node int data; Node next;/这个就是那个箭头的声明方式 基本的声明就到此为止 那么下面是链表类的声明，此时我们要考虑很多方面的操作,Chain的声明,public class Chain Node start; int sum;/链表中结点的总个数 . . . 接下来是编写方法：有哪些？ 返回链表结点数，将链表倒转，链表排序，向第x个元素处插入元素，删除结点，将链表清空，输出链表最小元素,倒转：将链表清空，存入数组，依次插入链表头部 返回结点数
3、：返回sum 排序：将链表存入数组并清空，排序后倒序插入头部 在第x个元素后插入：如果链表为空或者根本不够x个元素直接抛出异常或者打出信息提示（按照题目要求），否则进行插入操作 清空：start=null;sum=0;/java的垃圾回收机制要时刻考虑到，还有sum也时刻不能忘记,public void insert(int Num,int x) Node node=start; int i; if(this.sumx)return; for(i=1;i=x-1;i+) node=node.next; Node newnode=new Node(); newnode.data=Num; new
4、node.next=node.next; node.next=newnode; this.sum+;/别忘了 ,删除： public void delete(int x) Node node=start; int i; if(this.sumx)return;/看题意 for(i=1;i=x-2;i+)/ node=node.next; node.next=node.next.next; this.sum-; ,输出最小元素： public int minint() Node node=start;/小心，链表为空的情况 if(node=null)return -2147483648;/看题意
5、 int i=start.data;/注意这里初值也可以赋成2147483647 while(node!=null) i=inode.data?i:node.data; node=node.next; return i; ,额外的，其他可以添加的功能,双向链表：除了next还需要在Node结点类中添加pre，并且插入和删除操作中要同步对pre进行处理 循环链表：Chain类里添加一个Node end;表示链表进行到这里时已经跑了一圈，并时刻记得，链表的尾部的next要指向start 那么，双向循环链表我就不提了，两个加起来，而且操作要随时记得同步。,以上就是链表的部分,接下来是扩展的数据结构的
6、基本的知识点，反正你都要学到 栈（堆栈）：先入者后出（薯片罐子）,栈顶指向顶部的元素 还是顶部元素的上部 空白区域你可以自己定,top,22,3,栈的操作：,返回栈顶元素 删除栈顶元素 清空栈（top=0或-1） 向栈顶插入元素,top,22,3,到现在,你要理解的是，数据结构是你自己臆想一种结构，要根据它的实际来编写 到现在，你编程的印象应该是对某种功能的实现，不要拘泥于语句上 下面是堆（堆积树）,堆,堆是一棵完全二叉树，是一棵二叉树，是一棵树。 “完全”你可以忽略的 有这么一棵树，它满足： 父亲结点的数据小于（或者大于）左右儿子结点 那么举个例子,依次向堆中插入8 3 11 6 5 10
7、13后的小根堆,插入：向堆的最后一个结点中插入数据并对其上调（父亲大于自己就交换自己和父亲的data并继续对父亲进行该操作）,删除堆顶元素： 将最后一个结点 上提到堆顶并进 行下调（结点自 己，左儿子，右 儿子哪个小，如 果是自己或者无 儿子，则停止， 是左右儿子中的 一个，就交换并 继续对其进行该 操作）,返回最小值或最大值： 返回堆顶元素,设当前点为n，父亲=n/2,左儿子=n*2,右儿子=n*2+1 堆可以存进数组里 定义堆：int heap=new int 2000;int n=0;,1,3,2,4,5,6,7,那么，完全二叉树的定义： 若设二叉树的深度为h，除第 h 层外，其它各层 (1h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。 根据完全二叉树的特征，我们可以将其巧妙地将其存放进数组里,上调： int current=n;/n为堆的最后一个结点 while(current1 ,下调： int current=1,l,r; while(current*2n) if(heapcurrentl) swap(heapcurrent,heapcurrent*2); return; r=heapcurrent*2+1; if(lr ,谢谢,
