• 数据结构与算法之:基础数据结构(数组,线性表,链式表)
  • 暖风 发表于 2014/11/19 9:33:00 | 分类标签: 数据结构 算法 线性表
  • 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑结构简单,便于实现和操作。因此,线性表这种数据结构在实际应用中是广泛采用的一种数据结构。其基本操作主要有:
       1)MakeEmpty(L) 这是一个将L变为空表的方法
       2)Length(L) 返回表L的长度,即表中元素个数 
       3)Get(L,i) 这是一个函数,函数值为L中位置i处的元素(1≤i≤n)
       4)Prev(L,i) 取i的前驱元素
       5)Next(L,i) 取i的后继元素
       6)Locate(L,x) 这是一个函数,函数值为元素x在L中的位置
       7)Insert(L,i,x)在表L的位置i处插入元素x,将原占据位置i的元素及后面的元素都向后推一个位置
       8)Delete(L,p) 从表L中删除位置p处的元素
       9)IsEmpty(L) 如果表L为空表(长度为0)则返回true,否则返回false
       10)Clear(L)清除所有元素
       11)Init(L)同第一个,初始化线性表为空
       12)Traverse(L)遍历输出所有元素
       13)Find(L,x)查找并返回元素
       14)Update(L,x)修改元素
       15)Sort(L)对所有元素重新按给定的条件排序
       16) strstr(string1,string2)用于字符数组的求string1中出现string2的首地址
    不管采用哪种方式实现线性表,至少都应该具有上述这些基本方法,下面我会将下数据结构的基本实现方式。

    基础数据结构
    数据结构是一种抽象的数据类型(ADT),可以这么说,我们可以采用任意的方式实现某种数据结构,只要符合将要实现的数据结构的特点,数据结构就是一种标准,我们可以采用不同的方式去实现,最常用的两种就是数组和链表(包括单链表、双向链表等)。数组是非常常见的数据类型,在任何一种语言里都有它的实现,我们这里采用Java来简单实现一下数组。
    数组是一种引用类型的对象,我们可以像下面这样的方式来声明数组:
    1. int a[];    
    2. int[] b;    
    3. int []c;    
    4. [java] view plaincopy  
    5. a = new int[10];    
    总结起来,声明一个数组有基本的三个因素:类型、名称、下标,Java里,数组在格式上相对灵活,下标和名称可以互换位置,前三种情况我们可以理解为声明一个变量,后一种为其赋值。或者像下面这样,在声明的时候赋值:
    1. int c[] = {2,3,6,10,99};    
    2. int []d = new int[10];    
    我稍微解释一下,其实如果只执行:int[] b,只是在栈上创建一个引用变量,并未赋值,只有当执行d = new int[10]才会在堆上真正的分配空间。上述第一行为静态初始化,就是说用户指定数组的内容,有系统计算数组的大小,第二行恰恰相反,用户指定数组的大小,由系统分配初始值,我们打印一下数组的初始值:
    1. int []d = new int[10];    
    2. System.out.println(d[2]);   
    结果输出0,对于int类型的数组,默认的初始值为0.
    但是,绝对不可以像下面这样:

    int e[10] = new int[10];  
    无法通过编译,至于为什么,语法就是这样,这是一种规范,不用去想它。
    我们可以通过下标来检索数组。下面我举个简单的例子,来说明下数组的用法。
    1. public static void main(String[] args) {    
    2.     
    3.     String name[];    
    4.     
    5.     name = new String[5];    
    6.     name[0] = "egg";    
    7.     name[1] = "erqing";    
    8.     name[2] = "baby";    
    9.     
    10.     for (int i = 0; i < name.length; i++) {    
    11.         System.out.println(name[i]);    
    12.     }    
    13. }    
    这是最简单的数组声明、创建、赋值、遍历的例子,下面写个增删的例子。

    1. package com.xtfggef.algo.array;    
    2.     
    3. public class Array {    
    4.     
    5.     public static void main(String[] args) {    
    6.     
    7.         int value[] = new int[10];    
    8.         for (int i = 0; i < 10; i++) {    
    9.             value[i] = i;    
    10.         }    
    11.     
    12.         // traverse(value);    
    13.         // insert(value, 666, 5);    
    14.         delete(value, 3);    
    15.         traverse(value);    
    16.     }    
    17.     
    18.     public static int[] insert(int[] old, int value, int index) {    
    19.         for (int k = old.length - 1; k > index; k--)    
    20.             old[k] = old[k - 1];    
    21.         old[index] = value;    
    22.         return old;    
    23.     }    
    24.     
    25.     public static void traverse(int data[]) {    
    26.         for (int j = 0; j < data.length; j++)    
    27.             System.out.print(data[j] + " ");    
    28.     }    
    29.     
    30.     public static int[] delete(int[] old, int index) {    
    31.         for (int h = index; h < old.length - 1; h++) {    
    32.             old[h] = old[h + 1];    
    33.         }    
    34.         old[old.length - 1] = 0;    
    35.         return old;    
    36.     }    
    37. }    
    简单写一下,主要想说明数组中删除和增加元素的原理:增加元素,需要将index后面的依次向后移动,然后将值插入index位置,删除则将后面的值依次向前移动,较简单。
    要记住:数组是表示相同类型的一类数据的集合,下标从0开始,就行了。
    数组实现的线下表可以参考ArrayList,在JDK中附有源码,感兴趣的同学可以读读。下面我简单介绍下单链表。
    单链表是最简单的链表,有节点之间首尾连接而成,简单示意如下:

    除了头节点,每个节点包含一个数据域一个指针域,除了头、尾节点,每个节点的指针指向下一个节点,下面我们写个例子操作一下单链表。

    1. package com.xtfggef.algo.linkedlist;    
    2.     
    3. public class LinkedList<T> {    
    4.     
    5.     /**  
    6.      * class node  
    7.      * @author egg  
    8.      * @param <T>  
    9.      */    
    10.     private static class Node<T> {    
    11.         T data;    
    12.         Node<T> next;    
    13.     
    14.         Node(T data, Node<T> next) {    
    15.             this.data = data;    
    16.             this.next = next;    
    17.         }    
    18.     
    19.         Node(T data) {    
    20.             this(data, null);    
    21.         }    
    22.     }    
    23.     
    24.     // data    
    25.     private Node<T> head, tail;    
    26.     
    27.     public LinkedList() {    
    28.         head = tail = null;    
    29.     }    
    30.     
    31.     /**  
    32.      * judge the list is empty  
    33.      */    
    34.     public boolean isEmpty() {    
    35.         return head == null;    
    36.     }    
    37.     
    38.     /**  
    39.      * add head node  
    40.      */    
    41.     public void addHead(T item) {    
    42.         head = new Node<T>(item);    
    43.         if (tail == null)    
    44.             tail = head;    
    45.     }    
    46.     
    47.     /**  
    48.      * add the tail pointer  
    49.      */    
    50.     public void addTail(T item) {    
    51.         if (!isEmpty()) {     
    52.             tail.next = new Node<T>(item);    
    53.             tail = tail.next;    
    54.         } else {     
    55.             head = tail = new Node<T>(item);    
    56.         }    
    57.     }    
    58.     
    59.     /**  
    60.      * print the list  
    61.      */    
    62.     public void traverse() {    
    63.         if (isEmpty()) {    
    64.             System.out.println("null");    
    65.         } else {    
    66.             for (Node<T> p = head; p != null; p = p.next)    
    67.                 System.out.println(p.data);    
    68.         }    
    69.     }    
    70.     
    71.     /**  
    72.      * insert node from head  
    73.      */    
    74.     public void addFromHead(T item) {    
    75.         Node<T> newNode = new Node<T>(item);    
    76.         newNode.next = head;    
    77.         head = newNode;    
    78.     }    
    79.     
    80.     /**  
    81.      * insert node from tail  
    82.      */    
    83.     public void addFromTail(T item) {    
    84.         Node<T> newNode = new Node<T>(item);    
    85.         Node<T> p = head;    
    86.         while (p.next != null)    
    87.             p = p.next;    
    88.         p.next = newNode;    
    89.         newNode.next = null;    
    90.     }    
    91.     
    92.     /**  
    93.      * delete node from head  
    94.      */    
    95.     public void removeFromHead() {    
    96.         if (!isEmpty())    
    97.             head = head.next;    
    98.         else    
    99.             System.out.println("The list have been emptied!");    
    100.     }    
    101.     
    102.     /**  
    103.      * delete frem tail, lower effect  
    104.      */    
    105.     public void removeFromTail() {    
    106.         Node<T> prev = null, curr = head;    
    107.         while (curr.next != null) {    
    108.             prev = curr;    
    109.             curr = curr.next;    
    110.             if (curr.next == null)    
    111.                 prev.next = null;    
    112.         }    
    113.     }    
    114.     
    115.     /**  
    116.      * insert a new node  
    117.      * @param appointedItem  
    118.      * @param item  
    119.      * @return  
    120.      */    
    121.     public boolean insert(T appointedItem, T item) {    
    122.         Node<T> prev = head, curr = head.next, newNode;    
    123.         newNode = new Node<T>(item);    
    124.         if (!isEmpty()) {    
    125.             while ((curr != null) && (!appointedItem.equals(curr.data))) {    
    126.                 prev = curr;    
    127.                 curr = curr.next;    
    128.             }    
    129.             newNode.next = curr;     
    130.             prev.next = newNode;    
    131.             return true;    
    132.         }    
    133.         return false;     
    134.     }    
    135.     
    136.     public void remove(T item) {    
    137.         Node<T> curr = head, prev = null;    
    138.         boolean found = false;    
    139.         while (curr != null && !found) {    
    140.             if (item.equals(curr.data)) {    
    141.                 if (prev == null)    
    142.                     removeFromHead();    
    143.                 else    
    144.                     prev.next = curr.next;    
    145.                 found = true;    
    146.             } else {    
    147.                 prev = curr;    
    148.                 curr = curr.next;    
    149.             }    
    150.         }    
    151.     }    
    152.     
    153.     
    154.     public int indexOf(T item) {    
    155.         int index = 0;    
    156.         Node<T> p;    
    157.         for (p = head; p != null; p = p.next) {    
    158.             if (item.equals(p.data))    
    159.                 return index;    
    160.             index++;    
    161.     
    162.         }    
    163.         return -1;    
    164.     }    
    165.     
    166.     /**  
    167.      * judge the list contains one data  
    168.      */    
    169.     public boolean contains(T item) {    
    170.         return indexOf(item) != -1;    
    171.     }    
    172. }    

    单链表最好玩儿的也就是增加和删除节点,下面的两个图分别是用图来表示单链表增、删节点示意,看着图学习,理解起来更加容易!

    接下来的队列和栈,我们分别用不同的结构来实现,队列用数组,栈用单列表,读者朋友对此感兴趣,可以分别再用不同的方法实现。
  • 请您注意

    ·自觉遵守:爱国、守法、自律、真实、文明的原则

    ·尊重网上道德,遵守《全国人大常委会关于维护互联网安全的决定》及中华人民共和国其他各项有关法律法规

    ·严禁发表危害国家安全,破坏民族团结、国家宗教政策和社会稳定,含侮辱、诽谤、教唆、淫秽等内容的作品

    ·承担一切因您的行为而直接或间接导致的民事或刑事法律责任

    ·您在编程中国社区新闻评论发表的作品,本网站有权在网站内保留、转载、引用或者删除

    ·参与本评论即表明您已经阅读并接受上述条款

  • 感谢本文作者
  • 作者头像
  • 昵称:暖风
  • 加入时间:2013/5/17 0:00:00
  • TA的签名
  • 这家伙很懒,虾米都没写
  • +进入TA的空间
  • 以下内容也很赞哦
分享按钮