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

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. 线性表是对象或者值的集合

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

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

1
2
3
4
5
6
7
8
9
10
11
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. 封装相应的指针操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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. 打印线性表

1
2
3
4
5
6
7
8
9
10
11
//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. 查找特定项

1
2
3
4
5
6
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. 移除节点

1
2
3
4
5
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. 查找上一个节点

1
2
3
4
5
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. 方法二:我们用数组来存储指数和参数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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是最后一个点,降低插入的复杂度

1
2
3
4
5
6
7
8
9
10
11
12
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为队列最大容量。

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

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

  3. 队空: front = rear

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

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

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

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

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. 静态链表是由数组实现的单链表。

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

8.1. 静态链表的实现


8.2. 实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//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. 部分方法的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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( ) );
}

2019-数据结构-数据结构3.0-List
https://spricoder.github.io/2020/01/17/2019-Data-Structure/2019-Data-Structure-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%843.0-List/
作者
SpriCoder
发布于
2020年1月17日
许可协议