数据结构--java

第一章 绪论

1.1 什么是数据结构

1.1.1 数据结构的逻辑定义

数据结构：（1）数据元素之间的逻辑关系（数据的逻辑结构）

                  （2）数据元素及其关系在计算机存储器中的存储方式（数据的存储结构）

                  （3）施加在数据上的操作（数据的运算）

数据：可被计算机识别并加工处理的对象

1.1.2 数据的逻辑结构

逻辑结构的表示：表格、图等容易理解的形式

1.1.3 数据的存储结构

数据及数据之间的关系在计算机中的存储方式（正确反映数据元素之间的逻辑关系）

1.顺序存储结构

2.链式存储结构

1.1.4 数据的运算

运算描述+运算实现

1.1.5 数据结构和数据类型

ADT抽象数据类型名{

数据对象：数据对象的声明

数据关系：数据关系的声明

基本运算：基本运算的声明--基本运算名（参数表）：运算功能描述

}

1.2 算法及其描述

1.2.1 什么是算法

1.2.2 算法描述

程序=数据结构+算法

1.3 算法分析

1.3.1 算法设计要求

1.3.2 算法的时间性能分析

1.计算算法频度

2.算法的最好、最坏和平均时间复杂度

1.3.3 算法的存储空间分析

抽象数据类型=数据的逻辑结构（-->成员变量）+抽象运算（-->公有方法）

第二章 线性表

2.1 线性表的定义

定义：具有相同特性的数据元素的一个有限序列

2.1.1 什么是线性表

2.1.2 线性表的抽象数据类型描述

2.2 线性表的顺序存储结构

2.2.1 线性表的顺序存储结构--顺序表

public class SqListClass {       //顺序表泛型类final int initcapacity = 10;    //顺序表的初始容量(常量)public E[] data;                //存放顺序表中元素public int size;                //存放顺序表的长度private int capacity;           //存放顺序表的容量public SqListClass() {  //构造方法，实现data和length的初始化data = (E[]) new Object[initcapacity];  //强制转换为E类型数组capacity = initcapacity;size = 0;}
}

2.2.2 线性表的基本运算算法在顺序表中的实现

二路归并

public class Main {public static SqListClass Merge2(SqListClass A, SqListClass B) {SqListClass C = new SqListClass();int i = 0;  //i:遍历Aint j = 0;  //j遍历Bwhile (i < A.size() && j < B.size()) {if (A.GetElem(i) < B.GetElem(j)) {C.Add(A.GetElem(i));  //较小的A元素+Ci++;} else {C.Add(B.GetElem(j));  //较小的B元素+Cj++;}}while (i < A.size) {  //若A未遍历完全C.Add(A.GetElem(i));i++;}while (j < B.size()) {  //若B未遍历完全C.Add(B.GetElem(j));j++;}return C;}public static void main(String[] args){//1.创建递增的顺序表aInteger[] a={1,3,5,7};SqListClass A=new SqListClass<>();A.CreateList(a);System.out.println("A:"+A);//2.创建增的顺序表bInteger[] b={1,2,5,7,9,10,20};SqListClass B=new SqListClass<>();B.CreateList(b);System.out.println("B:"+B);//3.执行二路归并算法代码System.out.println("二路归并");SqListClass C= Ex2_6.Merge2(A,B);System.out.println("C:"+C);}
}

2.2.4 顺序表容器--ArrayLiist

1.ArrayList的基本应用

2.ArrayList类元素的排序：

（1）按元素递增排序：Collections.sort(myarrlist);

（2）按元素递减排序：Collections.sort(myarrlist,Collections.reverseOrder());

2.3 线性表的链式存储结构

2.3.1 线性表的链式存储结构--链表

指针成员：一个结点中包含有后继结点的地址信息或者前驱结点的地址信息

单链表：只设置一个指向其后继结点的指针成员

双链表：每个结点设置两个指针成员，分别指向其前驱结点和后继结点

2.3.2 单链表

public class LinkNode{//单链表结点泛型类E data;//结点的指针域LinkNodenext;//后继结点的指针域public LinkNode(){//构造方法next=null;}public LinkNode(E d){//重载构造方法this.data=d;this.next=null;}
}

public class LinkListClass {//单链表泛型类public LinkNode head;//存放头结点public LinkListClass() {//构造方法this.head = new LinkNode();//创建头结点this.head.next = null;}//1.头插法public  void  CreateListF(E[] a){LinkNode s;for (int i = 0;i(a[i]);s.next = head.next;head.next = s;}}//2.尾插法public void CreateListR(E[] a){LinkNode s,t = head;for (int i=0;i(a[i]);t.next = s;t=s;}t.next = null;}//线性表的基本运算算法private LinkNode geti(int i){//返回序号为i的结点LinkNode p =head;int j = -1;while (j s = new LinkNode(e);LinkNode p = head;while (p.next!=null){  //查找尾结点pp=p.next;}p.next=s;}//2）求线性表的长度public  int size(){LinkNode p = head;int cnt = 0;while (p.next!=null){cnt++;p=p.next;}return cnt;}//3）设置线性表的长度public void Setsize(int nlen){int len = size();if (nlen<0||nlen>len){throw new IllegalArgumentException("设置长度：n不在有效范围内");}if (nlen==len){return;}LinkNode p = geti(nlen-1);p.next = null;}//4）求线性表中序号为i的元素public E GetElem(int i){int len = size();if(i<0||i>len-1){throw new IllegalArgumentException("查找：位置i不在有效范围内");}LinkNode p = geti(i);return (E)p.data;}//5）设置线性表中序号为i的元素public void SetElem(int i,E e){if (i<0||i>size()-1){throw new IllegalArgumentException("设置:位置i不在有效范围内");}LinkNode p = geti(i);p.data = e;}//6）求线性表中第一个值为e的元素的逻辑序号public int GetNo(E e){int j = 0;LinkNode p = head.next;while (p!=null&&!p.data.equals(e)){j++;p=p.next;}if (p==null){return -1;}else {return j;}}//7）将线性表中序号为i和序号为j的元素交换public void swap(int i ,int j){LinkNode p = geti(i);LinkNode q = geti(j);E tmp = p.data;p.data = q.data;q.data = tmp;}//8）在线性表中插入e作为第i个元素public void Insert(int i ,E e){if (i<0||i>size()){throw new IllegalArgumentException("插入：位置i不在有效范围内");}LinkNode s = new LinkNode(e);LinkNode p = geti(i-1);s.next = p.next;p.next = s;}//9）在线性表中删除第i个数据元素public void Delete(int i){if (i<0||i>size()-1){throw new IllegalArgumentException("删除：位置i不在有效范围内");}LinkNode p = geti(i-1);p.next=p.next.next;}@Overridepublic String toString() {String ans = "";LinkNode p = head.next;while (p!=null){ans+=p.data+"";p=p.next;}return ans;}
}

2.3.3 双链表

class DLinkNode {E data;DLinkNode prior;  //区别：前驱结点指针DLinkNode next;public DLinkNode(){prior=null;next=null;}public DLinkNode(E d) {data = d;prior = null;next = null;}
}public class DLinkListClass {DLinkNode dhead;public DLinkListClass(){dhead=new DLinkNode();dhead.prior=null;dhead.next=null;}//头插法：数组a建立双链表public void CreateListF(E[] a){  DLinkNode s;for(int i=0;i(a[i]);s.next=dhead.next;if(dhead.next!=null){dhead.next.prior=s;}dhead.next=s;s.prior=dhead;}}//尾插法public void CreateListR(E[] a){ DLinkNode s,t;t=dhead;for(int i=0;i(a[i]);t.next=s;s.prior=t; t=s;}t.next=null;}public void Add(E e){DLinkNode s = new DLinkNode(e);DLinkNode p = dhead;while (p.next!=null){p=p.next;}p.next=s;}public  int size(){DLinkNode p = dhead;int cnt = 0;while (p.next!=null){cnt++;p=p.next;}return cnt;}private DLinkNode geti(int i){DLinkNode p = dhead;int j = -1;while (jlen){throw new IllegalArgumentException("设置长度：n不在有效范围内");}if (nlen==len){return;}DLinkNode p = geti(nlen-1);p.next=null;}public E GetElem(int i){int len = size();if (i<0||i>len-1){throw new IllegalArgumentException("查找：位置i不在有效范围内");}DLinkNode p = geti(i);return (E)p.data;}public void SetElem(int i,E e){if (i<0||i>size()-1){throw new IllegalArgumentException("设置：位置i不在有效范围内");}DLinkNode p = geti(i);p.data=e;}public int GetNo(E e){int j=0;DLinkNode p = dhead.next;while (p!=null&&!p.data.equals(e)){j++;p=p.next;}if (p==null){return -1;}else {return j;}}public void Insert(int i,E e){if(i<0 || i>size()){throw new IllegalArgumentException("插入：位置i不在有效范围内");}DLinkNode s=new DLinkNode(e);DLinkNode p=geti(i-1);s.next=p.next;if(p.next!=null){p.next.prior=s;}p.next=s;s.prior=p;}public void Delete(int i){if(i<0 || i>size()-1){throw new IllegalArgumentException("删除：位置i不在有效范围内");}DLinkNode p=geti(i);if(p.next!=null){p.next.prior=p.prior;}p.prior.next=p.next;}public static void Delx(DLinkListClass L,Integer x){DLinkNode p=L.dhead.next;while(p!=null && p.data!=x){p=p.next;}if(p!=null){if(p.next!=null){p.next.prior=p.prior;}p.prior.next=p.next;}}
}

2.3.4 循环链表

public class CLinkListClass{  //循环单链表泛型LinkNodehead;  //存放头结点public CLinkListClass(){  //构造方法head=new LinkNode();  //创建头结点head.next=head;  //置为空的循环单链表}
}

public class CDLinkListClass {  //循环双链表泛型DLinkNodedhead;  //存放头结点public CDLinkListClass(){  //构造方法dhead=new DLinkNode();  //创建头结点dhead.prior=dhead;  //构成空的循环双链表dhead.next=dhead;}
}

2.3.5 链表容器--LinkedList

 LinkedList类对象和ArrayList类对象可以相互转换

2.4 顺序表和链表的比较

2.5 线性表的应用

2.5.1 求解两个多项式相加问题的描述

2.5.2 采用顺序存储结构求解 

2.5.3 采用链式存储结构求解

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！