2019-数据结构-数据结构3.0-List · SpriCoder

List

1. 引入

1.1. Abstract Data Types(ADTS)

1. ADT定义: a set of objects together with a set of operaions. Abstract data types are mathematical abstractions; nowhere in an ADT‟s definition is there any mention of how the set of operations is implemented. 一组物体和一组操作。抽象数据类型是数学抽象；在ADT的定义中，没有提到如何实现操作集。

1.1.1. 数据对象

1.1.2. 数据结构

2. 线性表

1. 线性表是对象或者值的集合

2. 以上是需要实现的方法。

2.1. 线性表需要实现的方法

2.2. 线性表的不同实现

2.2.1. 简单数组实现线性表

1. (e1,e2,………en)，也就是数组向系统请求了一块连续的内存，数据量大小由程序员来确定。
2. each position of the array is called a cell or a node mapping formula: location(i)=i-1
3. 从数组类型存储的线性表中取出一个元素的复杂度是O(1)。
4. 一般我们在线性表中放置的是相同类型的值。

一些方法

1. 顺序查找Search(x)的时间复杂度O(n),平均算法复杂度O((n+1)/2)
   • 平均数据访问次数:n/2
2. 删除remove(k,x)：delete the k’th element and return it in x
   • 最坏和平均情况下的算法复杂度都是O(n)
   • 平均数据移动次数:(n-1)/2
3. 插入操作insert(x,i)
   • 平均数据移动次数:n/2

2.2.2. 单链表(Linked List)实现线性表

1. 特点:在内存中不是连续内存。
2. 一个链表节点中存储一个指针，一个数据。
   • java中的指针是不可以进行加减操作，防止出现一些系统问题。而C++中是可以进行加减运算。
3. 最后的一个指针指向null

部分操作

1. 删除操作:Delete(index,x)
   1. 删除第一个节点:重新指向第一个指针，并且在C++中需要delete掉被解引用的对象。手动释放需要先记下来位置。
   2. 删除中间节点:首先查询，之后删除
      • before.link = before.link.link
2. 插入操作:insert(index,x)
   1. 在线性表开头插入一个元素:首先插入一个元素，然后把头指针指向头。
   2. 在线性表中间插入一个元素:首先查询找到相应元素

2.2.3. 带有表头元素的单链表

1. 有一个头节点，Header: 这个节点的数据是没有的，然后指针是指向第一个元素的

3. 线性表的java实现

1. ListNode：代表结点的类
2. LinkedList：代表表本身的类
3. LinkedListItr：代表游标位置的类
4. 都是包 DataStructure的一部分

3.1. ListNode

class ListNode {   
    object element;
    ListNode next;
    ListNode( object theElement) {
        this( theElement, null);
    }
    ListNode( object theElement, ListNode n) {
        element = theElement; 
        next = n;
    }
} 

3.2. LinkedListItr

1. 封装相应的指针操作

public class LinkedListItr {
    LinkedListItr( ListNode  theNode) {
        current = theNode;
    }
    public boolean isPastEnd( ) {
        return current == null; 
    }
    public object retrieve() {
        //获得当前节点的数据
        return isPastEnd( ) ? null : current.element; 
    }
    public void advance( ) {
        if( ! isPastEnd( ) ) current = current.next; 
    }
    ListNode current; 
}

3.3. LinkedList

public class LinkedList {
    private ListNode header;
    public LinkedList( ) {//这里是含有表头节点的单链表，如果不带表头的话，应该是heder = null
        header = new ListNode( null );
    }
    public boolean isEmpty( ) {
        return header.next = = null ;
    }
    public void makeEmpty( ) {
        header.next = null;
    }
    //指向头指针的Itr
    public LinkedListItr zeroth( ) {
        return new LinkedListItr( header );
    }
    //指向第一个项的Itr
    public LinkedListItr first( ) {
        return new LinkedListItr( header.next );
    } 
    public LinkedListItr find( object x )
    public void remove( object x )
    public LinkedListItr findPrevious( object x )
    public void insert( object x, LinkedListItr p )
}

3.4. 一些方法的实现

3.4.1. 打印线性表

//Method to print a list
public static void printList( LinkedList theList ) {   
    if ( theList.isEmpty( ) ) 
        System.out.print ("Empty list");
    else {
        LinkedListItr itr = theList.first();
        for(;! Itr.isPastEnd(); itr. Advance( ) )
            System.out.print(itr.retrieve() + " " );
    }
    System.out.println();
}

3.4.2. 查找特定项

public LinkedListItr find (object x) {
    ListNode itr = header.next;
    while ( itr != null && !itr.element.equals( x ))
        itr = itr.next;
        return new LinkedListItr( itr );
} 

1. 时间复杂度O(n)

3.4.3. 移除节点

public void remove( object x ) {
    LinkedListItr p = findprevious( x );
    if( p.current.next != null )
        p.current.next = p.current.next.next;
}

1. 时间复杂度O(1)
   • 你可以把findPrevious操作当做是一个单独的先进行的操作，而不是这个操作的一部分。

3.4.4. 查找上一个节点

public LinkedListItr findPrevious( object x ) {
    ListNode itr = header;
    while( itr.next !=null && !itr.next.element.equals( x )) itr = itr.next;
    return new LinkedListItr( itr );
}

1. 时间复杂度O(n)

3.4.5. 例子:多项式求和

1. 我们对两个多项式求和
2. 方法一:我们对齐相加
3. 方法二:我们用数组来存储指数和参数。

public class Polynomial {
    public Polynomial( ) {
        zeroPolynomial( );
    }
    public void insertTerm( int coef, int exp )
    public void zeroPolynomial(){//清空多项式
        for( int i = 0; i<=MAX-DEGREE; i++) 
            coeffArray[i] = 0;
        highPower = 0; 
    }
    public Polynomial add( Polynomial rhs ){
        Polynomial sum = new Polynomial( );
        sum.highPower = max( highPower, rhs.highPower );
        for( int i = sum.highPower;  i>=0;  i--)
            sum.coeffArray[i] = coeffArray[i] + rhs.coeffArray[i];
        return sum; 
    }
    public Polynomial multiply( Polynomial rhs ) throws Overflow
    public void print( )
    public static final int MAX-DEGREE = 100;
    private int coeffArray[ ] = new int [MAX-DEGREE + 1];
    private int highPower = 0;
}

4. 单循环链表

1. 就是最后一个的next指向第一个或者表头

4.1. 例子

1. 约瑟夫问题
   

2. 问题解决:

   • 使用新的单链表来记录。
   • p是最后一个点，降低插入的复杂度

w = m;
for( int i = 1; i<= n-1; i++) {
    for (int j = 1; j<=w-1; j++) rear = rear.link;
    if (i = = 1) { 
        head = rear.link ; p = head;
    } else { 
        p.link = rear.link;
        p = rear.link;
    }
    rear.link = p.link;
    }
    P.link = rear; rear.link = null;

4.2. 循环队列的相关计算公式

1. 我们不妨设front为队头指针，rear为队尾指针，m为队列最大容量。

2. 入队: rear = (rear + 1) % m

3. 出队: front = (front + 1) % m

4. 队空: front = rear

5. 队满: front = (rear + 1) % m

6. 当前队列中的元素个数: n = (rear - front + m) % m

7. 求队头指针位置: (rear - length + 1 + m) % m

8. 循环队列的相关计算公式

5. 多项式问题

5.1. 线性表的数组实现

5.1.1. 部分方法

乘法

5.2. 线性表的单链表实现

5.2.1. 多项式相加

1. 存放非零指数的系数与指数，因此没有节点有三个域组成。
   • (coef + exp)(item) + link
2. 在具体实现时，并不要再重新申请节点，完全利用原来两个链表的结点。
3. 方法:设4个引用变量:
   • pa,pb,pc,p(c++需要)

算术步骤

1. 初始化：pc , pa , pb
2. 当pa和pb都有项时pc永远指向相加时结果链表的最后一个结点。
   1. 指数相等(pa. exp==pb. exp)
      • 对应系数相加：pa. coef=pa. coef + pb. coef ;
      • p= pb(c++需要) ;
      • pb前进 ;
      • if (系数相加结果为0){ p=pa; pa前进; } else { pc. link=pa; pc=pa; pa前进}
   2. 指数不等 pa. exp< pb.exp //pb要插入结果链表
      • {pc. link=pb ; pc=pb ; pb前进}
   3. 指数不等 pa. exp> pb. exp //pa要插入结果链表
      • {pc. link=pa ; pc=pa ; pa前进}
3. 当两链表中有一链表为空，则将另一链表链入结果链表就可以 if(pb空了){pc. link=pa;} else pc. link=pb;

算法复杂度:O(m+n)

6. 双向链表

1. 删除开始，删除中间是不同的

6.1. 删除

1. 删除第一个节点
   
2. 删除中间
   

6.2. 插入

1. 从头插入
   
2. 从中插入
   

6.3. 变形:双向循环链表

1. 带表头的双向链表
2. 不带表头的双向链表
3. 带表头的空双向链表

7. 例子:2009年考研统考题

1. 算法思想:双指针，第一个指针先跑k步，然后跑第二个指针，第一第二个一起往前跑。

8. 静态链表

1. 静态链表是由数组实现的单链表。

2. 在系统中，对于系统来说，内存时这样子的被系统管理的。
3. 如果next是0，那么相当于null

8.1. 静态链表的实现

8.2. 实现代码

//Class skeleton for CursorList 
public class CursorList {
    private static int alloc( )
    private static void free( int p)
    public CursorList( ) {  header = alloc( );   cursorSpace[ header ].next = 0; }
    public boolean isEmpty( ) {  return cursorSpace[ header ].next = = 0; }
    public void makeEmpty( )
    public CursorListItr zeroth( ) {   return new CursorListItr( header ); }
    public CursorListItr first( ) {   return new CursorListItr( cursorSpace[ header ].next ); }
    public CursorListItr find( object x )
    public void insert( object x, CursorListItr p)
    public void remove( object x )
    public CursorListItr findPrevious( object x )
    private int header; static CursorNode [ ] cursorSpace;
    private static final int SPACE-SIZE = 100;
    static {//静态变量对一个类只有一个
        cursorSpace = new CursorNode[ SPACE-SIZE ];
        for( int i = 0; i<SPACE-SIZE; i++) cursorSpace[ i ] = new CursorNode( null, i + 1 );
        cursorSpace[ SPACE-SIZE-1].next = 0;
    }
}

1. 静态部分是系统管理者的
2. 非静态部分是用户的

8.3. 静态链表如何确定还有可以分配的内存

1. 将剩余的内存先存储到一个静态链表中去。

8.4. 部分方法的实现

private static int alloc( ) {
    int p = cursorSpace[ 0 ].next;
    cursorSpace[0].next = cursorSpace[p].next;
    if( p == 0 ) throw new OutOfMemoryError( ); return p; }
private static void free( int p ) {
    cursorSpace[p].element = null;
    cursorSpace[p].next = cursorSpace[0].next;
    cursorSpace[0].next = p; }
public CursorListItr find( object x ) {
    int itr = cursorSpace[ header ].next;
    while( itr != 0 && !cursorSpace[ itr ].element.equals( x ) )
        itr = cursorSpace[ itr ].next;
    return new CursorListItr( itr );
}
public void insert( object x, CursorListItr p ) {
    if( p != null && p.current != 0) {
        int pos = p.current;
        int tmp = alloc( );
        cursorSpace[ tmp ].element = x;
        cursorSpace[ tmp ].next = cursorSpace[ pos ].next;
        cursorSpace[ pos ].next = tmp;
    }
}
public void remove( object x ) {   
    CursorListItr p = findPrevious( x );
    int pos = p.current;
    if( cursorSpace[ pos ].next != 0 ) {
        int tmp = cursorSpace[ pos ].next;
        cursorSpace[ pos ].next = cursorSpace[ tmp ].next;
        free( tmp );
    }
}
public void makeEmpty( ) {
    while( !isEmpty( ) )
        remove( first( ).retrieve( ) );
}