Java数据结构和算法之链表

  三、链表  

  链结点  

  在链表中,每个数据项都被包含在‘点“中,一个点是某个类的对象,这个类可认叫做LINK。因为一个链表中有许多类似的链结点,所以有必要用一个不同于链表的类来表达链结点。每个LINK对象中都包含一个对下一个点引用的字段(通常叫做next)但是本身的对象中有一个字段指向对第一个链结点的引用。

  单链表  

  用一组地址任意的存储单元存放线性表中的数据元素。  

  以元素(数据元素的映象)  + 指针(指示后继元素存储位置)  = 结点(表示数据元素 或 数据元素的映象)  

  以“结点的序列”表示线性表,称作线性链表(单链表)  

  单链表是一种顺序存取的结构,为找第 i 个数据元素,必须先找到第 i-1 个数据元素。  

  因此,查找第 i 个数据元素的基本操作为:移动指针,比较 j 和 i  

  1、链接存储方法  链接方式存储的线性表简称为链表(Linked List)。  

  链表的具体存储表示为:  

  ① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的)  

  ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针

(pointer)或链(link))  

  注意:  链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。  

  2、链表的结点结构  

┌──--┬──--┐  

│data │next│  

└──---┴─--─┘  

  data域--存放结点值的数据域

  next域--存放结点的直接后继的地址(位置)的指针域(链域)

  注意:  

  ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。  

  ②每个结点只有一个链域的链表称为单链表(Single Linked List)。  

  【例】线性表(bat,cat,eat,fat,hat,jat,lat,mat)的单链表示如示意图  

  3、头指针head和终端结点指针域的表示  单链表中每个结点的存储地址是存放在其前趋结点next域中,而开始结点无前趋,故应设头指针head指向开始结点。  

  注意:  链表由头指针唯一确定,单链表可以用头指针的名字来命名。  

  【例】头指针名是head的链表可称为表head。  终端结点无后继,故终端结点的指针域为空,即NULL。  

  4、单链表的一般图示法  由于我们常常只注重结点间的逻辑顺序,不关心每个结点的实际位置,可以用箭头来表示链域中的指针,线性表(bat,cat,fat,hat,jat,lat,mat)的单链表就可以表示为下图形式。  bat->cat->fat->hat->jat->lat->mat

  5、单链表类型描述  

  typedef char DataType; //假设结点的数据域类型为字符  

  typedef struct node{ //结点类型定义  

  DataType data; //结点的数据域  

  struct node *next;//结点的指针域  

  }ListNode  

  typedef ListNode *LinkList;  

  ListNode *p;  

  LinkList head;  

  注意:  

  ①*LinkList和ListNode是不同名字的同一个指针类型(命名的不同是为了概念上更明确)  

  ②*LinkList类型的指针变量head表示它是单链表的头指针  

  ③ListNode类型的指针变量p表示它是指向某一结点的指针  

  6、指针变量和结点变量

                       指针变量               │             结点变量   

│ 定义     │在变量说明部分显式定义  │在程序执行时,通过标准函数malloc生成

│ 取值     │ 非空时,存放某类型结点 │实际存放结点各域内容的地址

│操作方式│ 通过指针变量名访问       │ 通过指针生成、访问和释放

  ①生成结点变量的标准函数  p=( ListNode *)malloc(sizeof(ListNode));  //函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中  

  ②释放结点变量空间的标准函数  free(p);//释放p所指的结点变量空间  

  ③结点分量的访问  利用结点变量的名字*p访问结点分量  

  方法一:(*p).data和(*p).next  

  方法二:p-﹥data和p-﹥next  

  ④指针变量p和结点变量*p的关系

   指针变量p的值——结点地址

  结点变量*p的值——结点内容

  (*p).data的值——p指针所指结点的data域的值

  (*p).next的值——*p后继结点的地址

  *((*p).next)——*p后继结点  

  注意:  

  ① 若指针变量p的值为空(NULL),则它不指向任何结点。此时,若通过*p来访问结点就意味着访问一个不存在的变量,从而引起程序的错误。 

  ② 有关指针类型的意义和说明方式的详细解释  可见,在链表中插入结点只需要修改指针。但同时,若要在第i个结点之前插入元素,修改的是第i-1个结点的指针。

  因此,在单链表中第i个结点之前进行插入的基本操作为: 找到线性表中第i-1个结点,然后修改其指向后继的指针。

  双端链表  

  双端链表与传统的链表非常相似,但是它有一个新增的特性:即对最后一个链结点的引用,就像对第一个链结点的引用一样。

  对最后一个链结点的引用允许像在表头一样,在表尾直接插入一个链结点。当然,仍然可以在普通的单链表的表尾插入一个链结点,方法是遍历整个链表直到到达表尾,但是这种方法效率很低。  

  对最后一个链结点的引用允许像在表头一样,在表尾直接插入一个链结点。当然,仍然可以在普通的单链表的表尾插入一个链结点,方法是遍历整个链表直到到达表尾,但是这种方法效率很低。  

  像访问表头一样访问表尾的特性,使双端链表更适合于一些普通链表不方便操作的场合,队列的实现就是这样一个情况。  

  下面是一个双端链表的例子。

class Link3{  

  public long dData;  

  public Link3 next;  

  public Link3(long d){

    dData=d;

  }

  public void displayLink(){   

  System.out.print(dData+" ");  

  }

}

//////////////////////////////////////////////

class FirstLastList{  

  private Link3 first;  

  private Link3 last;  

  public FirstLastList(){  

    first=null;   

    last=null;  

  }  

  public boolean isEmpty(){   

    return first==null;  

  }  

  public void insertFirst(long dd){   

    Link3 newLink=new Link3(dd);   .  

    if(isEmpty()){    

      last=newLink;    

      newLink.next=first;    

      first=newLink;

    }   

  }

  public void insertLast(long dd){   

    Link3 newLink=new Link3(dd);   

    if(isEmpty()){    

      first=newLink;   

    }else{    

      last.next=newLink;    

      last=newLink;   

    }  

  }

  public long deleteFirst(){   

    long temp=first.dData;   

    if(first.next==null){    

    last=null;    

    first=first.next;    

    return temp;   

    }  

  }  

  public void displayList(){   

    System.out.print("List (first-->last): ");   

    Link3 current=first;   

    while(current!=null){    

      current.displayLink();   

       current=current.next;   

    }   

    System.out.println("");  

  }

}

//////////////////////////////////////////////////////

public class FirstLastApp {  

  public static void main(String[] args){   

  FirstLastList theList=new FirstLastList();    

  theList.insertFirst(22);   

  theList.insertFirst(44);   

  theList.insertFirst(66);   

  theList.insertLast(11);   

  theList.insertLast(33);   

  theList.insertLast(55);   

  theList.displayList();   

  theList.deleteFirst();   

  theList.deleteFirst();   

  theList.displayList();  

  }

}  

  为了简单起见,在这个程序中,把每个链结点中的数据字段个数从两个压缩到一个。这更容易显示链结点的内容。(记住,在一个正式的程序中,可能会有非常多的数据字段,或者对另外一个对象的引用,那个对象也包含很多数据字段。)

   这个程序在表头和表尾各插入三个链点,显示插入后的链表。然后删除头两个链结点,再次显示。  

  注意在表头重复插入操作会颠倒链结点进入的顺序,而在表尾的重复插入则保持链结点进入的顺序。  

  双端链表类叫做FirstLastList。它有两个项,first和last,一个指向链表中的第一个链结点,另一个指向最后一个链结点。如果链表中只有一个链结点,first和last就都指向它,如果没有链结点,两者都为Null值。  

  这个类有一个新的方法insertLast(),这个方法在表尾插入一个新的链结点。这个过程首先改变last.next,使其指向新生成的链结点,然后改变last,使其指向新的链结点。   插入和删除方法和普通链表的相应部分类似。然而,两个插入方法都要考虑一种特殊情况,即插入前链表是空的。如果isEmpty()是真,那么insertFirst()必须把last指向新的链结点,insertLast()也必须把first指向新的链结点。  

  如果用insertFirst()方法实现在表头插入,first就指向新的链结点,用insertLast()方法实现在表尾插入,last就指向新的链结点。如果链表只有一个链结点,那么多表头删除也是一种特殊情况:last必须被赋值为null值。  

  不幸的是,用双端链表也不能有助于删除最后一个链结点,因为没有一个引用指向倒数第二个链结点。如果最后一个链结点被删除,倒数第二个链结点的Next字段应该变成Null值。为了方便的删除最后一个链结点,需要一个双向链表。(当然,也可以遍历整个链表找到最后一个链结点,但是那样做效率不是很高。)  有序链表  在有序链表中,数据是按照关键值有序排列的。有序链表的删除常常是只限于删除在链表头部的最小链结点。不过,有时也用Find()方法和Delete()方法在整个链表中搜索某一特定点。  

  一般,在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度,另外链表可以扩展到全部有效的使用内存,而数组只能局限于一个固定的大小中。但是,有序链表实现起来比有序数组更困难一些。  

  后而将看到一个有序链表的应用:为数据排序。有序链表也可以用于实现优先级队列,尽管堆是更常用的实现方法。   在有序链表中插入一个数据项的Java代码,为了在一个有序链表中插入数据项,算法必须首先搜索链表,直到找到合适的位置:它恰好在第一个比它大的数据项的前面。  

  当算法找到了要插入的位置,用通常的方式插入数据项:把新链结点的Next字段指向下一个链结点,然后把前一个链结点的Next字段改为指向新的链结点。然而,需要考虑一些特殊情况:链结点有可以插在表头,或者插在表尾。看一下这段代码:

  Public void insert(long key){  

    Link newLink= new Link(key);  

    Link previous= null;  

    Link current=first;  

    While(current!= null&&key>current.dData){   

      Previous= current;   

      Current=current.next;  

    }    

    if(previous== null){       

      First=newLink;  

    }else{  

    Previous.next= newLink;   

    newLink.next=current;  

  }  

  在链表上移动时,需要用一个previous引用,这样才能把前一个链结点的Next字段指向新的链结点。创建新链结点后,把current变量设为first,准备搜索正确的插入点。这时也把previous设为Null值,这步操作很重要,因为后面要用这个Null值判断是否仍在表头。  

  While循环和以前用来搜索插入点的代码类似,但是有一个附加的条件。如果当前检查的链结点的关键值不再小于待插入的链结点的关键值,则循环结束;这是最常见的情况,即新关键值插在链表中部的某个地方。 然而,如果current为Null值,while循环也会停止。这种情况发生在表尾,或者链表为空时。  

  如果current在表头或者链表为空,previous将为Null值;所以让first指向新的链结点。否则current处在链表中部或结尾,就使previous的next字段指向新的链结点。 不论哪种情况、都让新链结点的Next字段指向current。如果在表尾,current为Null值,则新链结点的Next字段也本应该设为这个值(Null)。  

  下面是有序链表的程序  SortedList.java程序实现了一个SortedList类,它拥有insert()、remove()和displayList()方法。只有insert()方法与无序链表中的insert()方法不同。

  package 有序链表;

class Link{  

  public long dData;  

  public Link next;  

  public Link(long dd){   

  dData= dd;  

  }  

  //.........................  

  public void displayLink(){   

    System.out.print(dData+" ");  

  }

}

////////////////////////////////////////

class SortedList{ 

  private Link first;  

  //..........................  

  public SortedList(){   

    first=null;  

  }  

  //.........................  

  public boolean isEmpty(){   

    return (first== null);  

  }  

  //..........................  

  public void insert(long key){   

    Link newLink=new Link(key);   

    Link previous= null;   

    Link current= first;   

    while(current!=null&&key>current.dData){    

    previous=current;    

    current=current.next;   

    }   

    if(previous== null){   

       first=newLink;   

    } else{    

      previous.next= newLink;    

      newLink.next=current;   

    }  

  //................................  

  public Link remove(){   

    Link temp=first;   

    first= first.next;   

    return temp;  

  }  

  //................................  

  public void displayList(){   

    System.out.print("List (first-->last): ");   

    Link current= first;  

    while(current!=null){    

      current.displayLink();     

      current= current.next;   

    }   

    System.out.println("");  

  }

}

////////////////////////////////////////

public class SortedLinkApp{  

  public static void main(String[] args){   

    SortedList theSortedList=new SortedList();   

    theSortedList.insert(20);   

    theSortedList.insert(40);   

    theSortedList.displayList();   

    theSortedList.insert(10);   

    theSortedList.insert(30);   

    theSortedList.insert(50);    

    theSortedList.displayList();   

    theSortedList.remove(); 

    theSortedList.displayList();   

    System.exit(0);  

  }

}

  在Main()方法中,插入值为20和40的两个链结点。然后再插入三个链结点,分别是10、30和50。这三个值分别插在表头、表中和表尾。这说明insert()方法正确地处理了特殊情况。最后删除了一个链结点,表现出删除操作总是从表头进行。每一步变化后,都显示整个链表。  

  双向链表  

  双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

  /* 线性表的双向链表存储结构 */

  typedef struct DuLNode{    

    ElemType data;    

    struct DuLNode *prior,*next;  

  }DuLNode,*DuLinkList;   

  /*带头结点的双向循环链表的基本操作(14个) */   

  void InitList(DuLinkList *L){/* 产生空的双向循环链表L */    

    *L=(DuLinkList)malloc(sizeof(DuLNode));   if(*L){    

    (*L)->next=(*L)->prior=*L;   

    }else{    

      exit(OVERFLOW);   

    }  

  void DestroyList(DuLinkList *L){   

    /* 操作结果:销毁双向循环链表L */   

    DuLinkList q,p=(*L)->next;/* p指向第一个结点 */   

    while(p!=*L){   

      /* p没到表头 */     

       q=p->next;      

      free(p);      

      p=q;     

    }     

    free(*L);      

    *L=NULL;    

  }    

  void ClearList(DuLinkList L) {/* 不改变L */  

     /* 初始条件:L已存在。操作结果:将L重置为空表 */  

    DuLinkList q,p=L->next; /* p指向第一个结点 */   

    while(p!=L) {/* p没到表头 */    

      q=p->next;  

      free(p);  

      p=q;  

    }  

    L->next=L->prior=L; /* 头结点的两个指针域均指向自身 */   

    }  

  Status ListEmpty(DuLinkList L){ /* 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */  

      if(L->next==L&&L->prior==L){   

        return TRUE;  

      }else{   

        return FALSE;  

  }  

  int ListLength(DuLinkList L){  /* 初始条件:L已存在。操作结果:返回L中数据元素个数 */   

      int i=0;   

      DuLinkList p=L->next; /* p指向第一个结点 */   

      while(p!=L) {/* p没到表头 */       

        i++;    

        p=p->next;   

      }   

      return i;  

  }  

  Status GetElem(DuLinkList L,int i,ElemType *e){  

      /* 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */   

      int j=1; /* j为计数器 */     

      DuLinkList p=L->next; /* p指向第一个结点 */     

      while(p!=L&&jnext){    

        j++;   

      }   

      if(p==L||j>i) /* 第i个元素不存在 { */      

        return ERROR;   

      }   

      *e=p->data; /* 取第i个元素 */

      return OK;

  }

  int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType)){  

    /* 初始条件:L已存在,compare()是数据元素判定函数 */  

    /* 操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。 */  

    /* 若这样的数据元素不存在,则返回值为0 */   

    int i=0;  

    DuLinkList p=L->next;/* p指向第1个元素 */   

    while(p!=L){   

      i++;    

      if(compare(p->data,e)){ /* 找到这样的数据元素 */   

      return i;   

      p=p->next;   

    }  

    return 0;   

  }    

  Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)   { /* 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */    

     /* 否则操作失败,pre_e无定义 */    

    DuLinkList p=L->next->next; /* p指向第2个元素 */    

    while(p!=L){ /* p没到表头*/      

      if(p->data==cur_e){  

        *pre_e=p->prior->data;   

        return TRUE;   

      }    

      p=p->next;   

    }    

    return FALSE;   

  }    

  Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e){  

  /* 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继, */

  /* 否则操作失败,next_e无定义 */    

    DuLinkList p=L->next->next; /* p指向第2个元素 */   

    while(p!=L){ /* p没到表头 */       

      if(p->prior->data==cur_e)    {    

        *next_e=p->data;   

        return TRUE; 

      }    

      p=p->next;   

    }    

    return FALSE;   

  }    

  DuLinkList GetElemP(DuLinkList L,int i) {

  /* 另加 */  

  /* 在双向链表L中返回第i个元素的地址。i为0,返回头结点的地址。若第i个元素不存在,*/  

  /* 返回NULL */   

    int j;    

    DuLinkList p=L; /* p指向头结点 */  

    if(i<0||i>ListLength(L)){ /* i值不合法 */  

      return NULL;  

    }

    for(j=1;j<=i;j++){

      p=p->next;  

      return p;   

    }  

  } 

  Status ListInsert(DuLinkList L,int i,ElemType e)   { /* 在带头结点的双链循环线性表L中第i个位置之前插入元素e,i的合法值为1≤i≤表长+1 */  

    /* 改进算法2.18,否则无法在第表长+1个结点之前插入元素 */  

    DuLinkList p,s;  

    if(i<1||i>ListLength(L)+1){ /* i值不合法 */   

      return ERROR;  

      p=GetElemP(L,i-1); /* 在L中确定第i个元素前驱的位置指针p */

    }  

    if(!p) {/* p=NULL,即第i个元素的前驱不存在(设头结点为第1个元素的前驱) */   

      return ERROR;  

      s=(DuLinkList)malloc(sizeof(DuLNode));  

    }

    if(!s){  

      return OVERFLOW;

    }

    s->data=e;    

    s->prior=p; /* 在第i-1个元素之后插入 */   

    s->next=p->next;   

    p->next->prior=s;   

    p->next=s;   

    return OK;  

  }    

  Status ListDelete(DuLinkList L,int i,ElemType *e){ /* 删除带头结点的双链循环线性表L的第i个元素,i的合法值为1≤i≤表长 */  

    DuLinkList p; 

    if(i<1){ /* i值不合法 */   

    return ERROR; 

    }

    p=GetElemP(L,i); /* 在L中确定第i个元素的位置指针p */  

    if(!p) {/* p=NULL,即第i个元素不存在 */   

    return ERROR;

    }   

    *e=p->data;    

    p->prior->next=p->next;   

    p->next->prior=p->prior;   

    free(p);   

    return OK;   

  }

  void ListTraverse(DuLinkList L,void(*visit)(ElemType))   { /* 由双链循环线性表L的头结点出发,正序对每个数据元素调用函数visit() */

    DuLinkList p=L->next; /* p指向头结点 */   

    while(p!=L)   {

      visit(p->data);   

    p=p->next;   

    }    

    printf("\n");  

  }  

  void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))   { /* 由双链循环线性表L的头结点出发,逆序对每个数据元素调用函数visit()。另加 */

    DuLinkList p=L->prior; /* p指向尾结点 */   

    while(p!=L)    {

    visit(p->data);   

    p=p->prior;  

    }

      printf("\n");  

  }

   迭代器  

  迭代器是一种对象,它能够用来遍历STL容器中的部分或全部元素,每个迭代器对象代表容器中的确定的地址。迭代器修改了常规指针的接口,所谓迭代器是一种概念上的抽象:那些行为上象迭代器的东西都可以叫做迭代器。然而迭代器有很多不同的能力,它可以把抽象容器和通用算法有机的统一起来。  

  迭代器提供一些基本操作符:*、++、==、!=、=。这些操作和C/C++“操作array元素”时的指针接口一致。不同之处在于,迭代器是个所谓的smart pointers,具有遍历复杂数据结构的能力。其下层运行机制取决于其所遍历的数据结构。因此,每一种容器型别都必须提供自己的迭代器。事实上每一种容器都将其迭代器以嵌套的方式定义于内部。因此各种迭代器的接口相同,型别却不同。这直接导出了泛型程序设计的概念:所有操作行为都使用相同接口,虽然它们的型别不同。  

  功能   迭代器使开发人员能够在类或结构中支持foreach迭代,而不必整个实现IEnumerable或者IEnumerator接口。只需提供一个迭代器,即可遍历类中的数据结构。当编译器检测到迭代器时,将自动生成IEnumerable接口或者IEnumerator接口的Current,MoveNext和Dispose方法。  

  特点  

  1.迭代器是可以返回相同类型值的有序序列的一段代码;  

  2.迭代器可用作方法、运算符或get访问器的代码体;     

  3.迭代器代码使用yield return语句依次返回每个元素,yield break将终止迭代; 

  4.可以在类中实现多个迭代器,每个迭代器都必须像任何类成员一样有惟一的名称,并且可以在foreach语句中被客户端代码调用;     

  5.迭代器的返回类型必须为IEnumerable和IEnumerator中的任意一种;   

  6.迭代器是产生值的有序序列的一个语句块,不同于有一个 或多个yield语句存在的常规语句块;       

  7.迭代器不是一种成员,它只是实现函数成员的方式,理解这一点是很重要的,一个通过迭代器实现的成员,可以被其他可能或不可能通过迭代器实现的成员覆盖和重载;

  8.迭代器块在C#语法中不是独特的元素,它们在几个方面受到限制,并且主要作用在函数成员声明的语义上,它们在语法上只是语句块而已;

Java数据结构和算法之链表,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。