数据结构笔记

线性表

一、顺序表(线性表的顺序存储结构)

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:是一个有序的集合,可以包含重复的元素,提供了按索引访问的方式。这里的有序就是指有顺序的排放,并不是排序。

相关资料

`D[0_A}7)0%F2P4K~~2GLUY.png

https://blog.csdn.net/snvjd/article/details/103284531

https://zhuanlan.zhihu.com/p/134092789

黑马培训数据结构资料.zip

文章目录