数据结构笔记
线性表
一、顺序表(线性表的顺序存储结构)
1.顺序表的存储结构
#define MaxSize 100
struct List{
ElemType data[MaxSize]; // 顺序表的元素
int len; // 顺序表的长度
}List;
2.节点的插入(在顺序表的L的第i个位置插入元素e):O(n)
// 1 <= i <= L.len+1
bool ListInsert(List &L, int i, ElemType e){
// defend
if(i < 1 || i > L.len+1){
return false;
}
if(L.len >= MaxSize){
return false;
}
// Insert
for(int j = L.len; j >= i; j--){ // 调整 i 号开始的后继元素
L.data[j] = L.data[j-1];
}
L.data[i-1] = e; // 赋值,插入
L.len += 1;
return L;
}
最好情况(表尾插入,不需要移动元素):O(1)
最坏情况(表头插入,需移动所有元素):O(n)
平均情况:O(n/2)
3.节点的删除(删除顺序表L的第i个位置的元素,并将其值返回):O(n)
bool ListDelete(List &L, int i, ElemType &e){
// defend
if(i<1 || i>L.len){
return false;
}
e = L.data[i-1];
for(int j = i; j < L.len; j++){
L.data[j-1] = L.data[j];
}
L.len -= 1;
return true;
}
最好情况(表尾删除,无需移动元素):O(1)
最坏情况(表头删除,需移动所有元素):O(n)
平均情况:O((n-1)/2)
4.按值查找(在顺序表L中查找值为e的元素,并返回其位序):O(n)
int LocateElem(List L, ElemType e){
for(int i = 0; i < L.len; i++){
if(L.data[i] == e){
return i+1;
}
}
return 0;
}
最坏情况(待查找元素在表头,比较一次即可):O(1)
最好情况(待查找元素在表尾,比较整个列表):O(n)
平均情况:O((n+1)/2)
二、单链表(顺序表的链式存储结构)
1.单链表的存储结构
struct LNode{
ElemType data; // 数据域
struct LNode * next; // 指针域
}LNode, *LinkList;
2.链表的构建(头插法)
LinkeList CreateList(LinkList &L){
// 头指针的构造
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
// 获取后续插入节点的数值
int x;
scanf("%d",&x);
LinkList s; // 创建插入节点
while(x != 9999){
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
return L;
}
3.链表的构建(尾插法)
LinkList CreateList(LinkList &L){
// 头指针的构造,并让尾指针指向当前头指针位置
L = (LinkList)malloc(sizeof(LNode));
LinkList r = L;
int x;
scanf("%d", &x);
LinkList s;
while(x != 9999){
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
scanf("%d", &X);
}
r->next = NULL;
return L;
}
4.按序号查找(查找单链表L中的第i个元素)
LinkList GetElem(LinkList L, int index){
LinkList p = L->next; // 头节点指针赋值给p
int j = 1; // 头节点的序号
if(index == 0){ // index = 0,即返回头节点
return L;
}
if(index < 1){ // index 无效
return NULL;
}
while(p && j < index){
p = p->next;
j++;
}
return p;
}
5.按值查找(查找单链表中值为e的元素)
LinkList LocateElem(LinkeList L, ElemType e){
LinkList p = L->next;
while(p && p->data != e){
p = p->next;
}
return p;
}
6.节点的插入(将值为x的节点插入到L的i号位置上)
p = GetElem(L, i-1);
LinkList s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = p->next;
p->next = s;
7.节点的删除(将单链表L中i号位置的元素删除)
p = GetElem(L, i-1);
q = p->next;
p->next = q->next;
free(q)
三、双链表(在单链表的基础上添加前驱指针)
1.双链表的存储结构
struct DLNode{
ElemType data; // 数据域
struct DLNode *prior, *next; // 前驱和后继节点
}DLNode, *DLinkList;
2.节点的插入(在双链表L中p节点之后插入节点s)
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
3.节点的删除(删除双链表p节点的后继节点q)
p->next = q->next;
q->next->prior = p;
free(q);
四、静态链表
1.静态链表的存储结构
#define MaxSize 100
struct SLink{
ElemType data;
int next; // 下一个元素的数组下标
}SLink[MaxSize];
基本结构
- 1、集合:数据元素同属一个集合
- 2、线性结构:数据元素间存在一对一的关系
- 3、树形结构:结构中元素间是一对多的关系
- 4、图状结构:结构中元素间是多对多的关系
逻辑结构:数据元素之家存在的关系称为数据的逻辑结构
物理结构:树蕨结构在计算机的表示称为数据的物理结构
数据结构在计算机中表示称为数据的物理结构
队列接口:
interface Queue{
void add(Object obj); //向队尾插入元素
Object remove(); //从队头删除元素
int size(); //查看队列的长度
}
可以通过实现这个接口,将数据存储到这个数据结构中,以方便存取。
例:
import java.util.*;
public class DataStructureInterface {
public static void main(String args[]){
ArrayList al=new ArrayList();
al.add("zzz");
al.add("zst");
al.add("cxk");
for(int i=0;i<al.size();i++){
System.out.println(al.get(i));
}
}
}
1、Collection集合接口
Collection接口是数据集合接口,它位于数据结构API的最上部。构成Collection的单位,被称之为元素。接口提供了添加、删除元素等管理数据的功能。根据数据管理的方法不同,可将Collection接口分成为3个部分,分别是:Map接口、Set接口、List接口
所有实现Collection接口的类都必须提供两个标准的构造函数:
*无参数的构造函数,用于创建一个空的Collection
*带Collection参数的构造函数,用于创建一个新的Collection。
这个新的Collection与传入的Collection拥有相同的元素。
(带参数的构造函数主要用来实现复制一个Collection)
如何遍历Collection中的每一个元素?不论Collection的实际类型如何,它都支持iterator()方法,该方法返回迭代器。使用该迭代器即可访问Collection中的每一个元素。
如:
Iterator it=collection.iterator(); //获得一个迭代器
while(it.hasnext()){
Object obj=it.next(); //得到下一个元素
}
List接口和Set接口是两个非常有用的集合接口,数组和列表等数据结构,基本上都是从这两个接口实现而来。
1、List接口:
List接口是有序的Collection,使用此接口能够精确地控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,这类似于数组。除了具有Collection接口必备的iterator()方法外,List还提供listIterator()方法,其返回ListIterator接口。和标准的Iterator接口相比,ListIterator多了一些add()之类的方法,允许添加、删除、设定元素,还能向前和向后遍历。
实现List接口的常用类有LinkedList和ArrayList。
2、LinkedList链表类
LinkedList实现了List接口,允许null元素。此外LinkedList在首部或尾部提供额外的get()、remove()、insert()等方法。LinkedList没有同步方法,如果多个线程同时访问一个List,则必须自己实现访问同步,一种解决方法是在创建List时构造一个同步的List。
List list=Collection.synchronizedList(new LinkedList(…));
3、ArrayList 数据列表类
ArrayList实现了可变大小的数组,它允许存储所有元素,包括null。ArrayList没有同步。每个ArrayList实例都拥有一个容量(Capacity)属性,即存储元素的数组的大小,这个容量可随着不断添加新元素而自动增加,但是增长算法并没有定义。当需要插入大量元素时,在插入前可调用ensureCapacity()方法来增加ArrayList的容量,以提高插入效率。和LinkedList一样,ArrayList也是非同步的。
2、Set接口
Set是一种不包含重复元素的Collection,即任意的两个元素e1和e2比较,结果都不相等。Set最多有一个null元素。实现Set接口的常用类有HashSet和TreeSet
1、HashSet集合类
HashSet类实现了Set接口,允许null元素。在具体使用该类时,要特别注意其不保证集合的迭代顺序,即不保证该顺序恒久不变。关于该集合类的基本操作包括add()、remove()、contains()、size()等方法。
TreeSet集合类
TreeSet类实现了Set接口,与HashSet类相比,该类实现了排序功能。存储在该集合中的元素默认按照升序排序元素,或者根据使用的构造方法不同,可能会按照元素的自然顺序进行排序,或者按照在创建Set集合时所提供的比较器进行排序。
3、Map映射接口
Map没有继承Collection接口,其提供key到value的映射。Map中不能包含相同的key,每个key只能映射一个value。Map接口提供3种集合的视图,Map的内容可以被当作一组key集合、一组value集合或一组key-value映射。
1、Hashtable散列表类
Hashtable继承Map接口,实现一个key-value映射的散列表。任何非空(non-null)的对象都可作为key或value。添加数据使用put(key,value)方法,取出数据使用get(key)方法,这两个基本操作的时间开销为常数。
Hashtable通过initial capacity和load factor两个参数调整性能。通常默认的load factor 0.75较好地实现了时间和空间的均衡,增大load factor可以节省时间,但相应的查找时间将增大,这会影响像get和put这样的操作。
例:
Hashtable numbers=new Hashtable();
numbers.put("one",new Integer(1));
numbers.put("two",new Integer(2));
numbers.put("three",new Integer(3));
//如果想取出2,可以用相应的key
Integer n=(Integer)numbers.get("two");
System.out.println("two="+n);
作为key的对象,将通过计算其散列函数确定与之对应的value位置,因此任何key的对象都必须实现hashCode()和equals()方法。hashCode()和equals()方法继承于根类Object。如果用自定义的类当作key,则要相当小心。按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)=true,则它们的hashCode必须相同。但如果两个对象不同,则它们的hashCode不一定不同。如果两个不同对象的hashCode相同,这种现象称为冲突。冲突会导致操作散列表的时间开销增大,所以尽量定义好的hashCode()方法,能加快散列表的操作。
所以注意:要同时复写equals()方法和hashCode()方法,而不要只写其中的一个。Hashtable是同步的。
2、HashMap散列映射类
HashMap和Hashtable类似,但是HashMap是非同步的,并且允许null,即null value和null key。如将HashMap视为Collection时(values()方法可以返回Collection),其迭代器操作时间开销和HashMap的容量成比例。因此,迭代操作的性能相当重要,切记不要将HashMap的初始容量设得过高,或者将load factor设得过低。
4、Lterator迭代器接口
什么是迭代器?迭代器指向两个元素中间的位置,当调用hasNext()方法时,如果返回true,此时调用next()方法返回下一元素。迭代器指向下两个元素之间的位置,如果要删除下一个元素,必须先调用next()方法,再调用remove()方法。
Iterator接口中定义了以下3个方法:
hasNext():是否还有下一个元素
next():返回下一个元素
remove():删除当前元素
1、迭代器作用
有些接口类没有提供get()操作,这时可用迭代器来获得信息。所有Collection接口的子类、子接口都支持Iterator迭代器。迭代器模式又称为游标模式。
官方定义:提供一种方法访问一个容器对象中各个元素,而又不需暴露该对象的内部细节,这就是迭代器。
2、迭代器模式:由以下角色组成
(1)迭代器角色:负责定义访问和遍历元素的接口迭代器角色定义了遍历的接口,但是没有规定由谁来控制迭代。在JavaCollection的应用中,由客户程序来控制遍历的进程,被称为外部迭代器。还有一种实现方式是由迭代器自身来控制迭代,被称为内部迭代器。外部迭代器要比内部迭代器灵活,强大,而且内部迭代器在Java中,可用性很弱
(2)具体迭代器角色:实现迭代器接口,并记录遍历中的当前位置
(3)容器角色:负责提供创建具体迭代器角色的接口
(4)具体容器角色:实现创建具体迭代器角色的接口————这个具体迭代器角色与该容器的结构相关
注:在迭代器模式中,没有规定谁来实现遍历算法。因为既可以在一个容器上使用不同的遍历算法,也可以将一种遍历算法应用于不同的容器。这样就破坏了容器的封装————容器角色就要公开自己的私有属性。那把它放入容器角色里实现,这样迭代器角色被架空,仅仅具备存放一个遍历当前位置的功能,但是遍历算法和特定的容器紧紧绑在一起。而在Java Collection的应用中,提供的具体迭代器角色是定义在容器角色中的内部类,这样便保护了容器的封装。同时容器也提供遍历算法接口,用户可以扩展自己的迭代器。
容器角色,以List为例。它也仅仅是一个接口,不罗列具体容器角色,是实现了List接口的ArrayList等类。这里只介绍和迭代器相关的内容,具体迭代器角色是以内部类的形式表现出来的。AbstractList是为了将各个具体容器角色的公共部分提取出来而存在的。
设计代码如下:
//迭代器角色,仅仅定义了遍历接口
public interface Iterator{
//声明方法
boolean hasNext();
Object next();
void remove();
}
public abstract class AbstractList implements List{
······
//这个便是负责创建具体迭代器角色的工厂方法
public Iterator iterator(){
return new Itr();
}
}
//作为内部类的具体迭代器角色
private class Itr implements Iterator{ //实现接口
//创建成员变量
int cursor=0;
int lastRet=-1;
int expectedModCount=modCount;
public boolean hasNext(){
return cursor!=size();
}
public Object next(){
checkForComodification();
try{
Object next=get(cursor);
lastRet=cursor++;
return next;
}catch(IndexOutOfBoundsException e){
checkForComodification():
throw new NoSuchElementException():
}
}
public void remove(){
if(lastRet==-1)
throw new IllegalStateException();
checkForComodification();
try{
AbstractList.this.remove(lastRet);
if(lastRet<cursor)
cursor--;
lastRet=-1;
expectedModeCount=modCount;
}catch(IndexOutofBoundsException e){
throw new ConcurrentModificationException();
}
}
//设计方法checkForComodification()
final void checkForComodification(){
if(modCount!=expectedModCount)
throw new ConcurrentModificationException();
}
}
至于迭代器模式的使用,要先得到具体容器角色,然后再通过具体容器角色,得到具体迭代器角色。这样就可以使用具体迭代器角色来遍历容器。上述代码不是完整程序,只是演示各个角色的创建过程。
3、迭代器模式优势
(1)支持以不同的方式遍历一个容器角色,根据实现方式的不同,效果上会有差别。
(2)简化了容器的接口,但是在java Collection中为了提高可扩展性,容器还是提供了遍历的接口。
(3)对同一个容器对象,可以同时进行多个遍历,因为遍历状态保存在每一个迭代器对象中。
4、杂项
1、Collection集合接口与Collections集合类的区别
Collections是java.util下的类,它包含各种有关集合操作的静态方法。
Collection是java.util下的接口,它是各种集合结构的父接口。
*List、Set继承自Collection接口,Map不继承Collection接口。
2、ArrayList数组列表类和Vector存储类的区别
同步性:Vector是线程安全的,是同步的。而ArrayList是线程不安全的,不是同步的。
数据增长:当需要增长时,Vector默认增长为原来一倍,而ArrayList却是原来的一半。
3、HashMap散列映射和Hashtable散列表的区别
二者都属于Map接口的类,作用都是将唯一键映射到特定的值上。
而HashMap类没有分类或排序,它允许一个null键和多个null键。
而Hashtable类似于HashMap,但是不允许有null键和null值,它也比HashMap慢,因为它是同步的。
4、数据结构的种类
数据结构分为两大类:线性数据结构和非线性数据结构。线性数据结构包括:线性表、栈、队列、串、数组和文件;非线性数据结构包括:树、图。
5、List接口和Set接口的区别
List:是一个有序的集合,可以包含重复的元素,提供了按索引访问的方式。这里的有序就是指有顺序的排放,并不是排序。
相关资料
https://blog.csdn.net/snvjd/article/details/103284531