数组、单链表和双链表介绍以及双向链表的C/C++/Java实现

c++/c 链表

if (index<0 || index>=mCount)

throw new IndexOutOfBoundsException();

// 正向查找

if (index <= mCount/2) {

DNode node = mHead.next;

for (int i=0; i

node = node.next;

return node;

}

// 反向查找

DNode rnode = mHead.prev;

int rindex = mCount - index -1;

for (int j=0; j

rnode = rnode.prev;

return rnode;

}

// 获取第index位置的节点的值

public T get(int index) {

return getNode(index).value;

}

// 获取第1个节点的值

public T getFirst() {

return getNode(0).value;

}

// 获取最后一个节点的值

public T getLast() {

return getNode(mCount-1).value;

}

// 将节点插入到第index位置之前

public void insert(int index, T t) {

if (index==0) {

DNode node = new DNode(t, mHead, mHead.next);

mHead.next.prev = node;

mHead.next = node;

mCount++;

return ;

}

DNode inode = getNode(index);

DNode tnode = new DNode(t, inode.prev, inode);

inode.prev.next = tnode;

inode.next = tnode;

mCount++;

return ;

}

// 将节点插入第一个节点处。c++/c 链表

public void insertFirst(T t) {

insert(0, t);

}

// 将节点追加到链表的末尾

public void appendLast(T t) {

DNode node = new DNode(t, mHead.prev, mHead);

mHead.prev.next = node;

mHead.prev = node;

mCount++;

}

// 删除index位置的节点

public void del(int index) {

DNode inode = getNode(index);

inode.prev.next = inode.next;

inode.next.prev = inode.prev;

inode = null;

mCount--;

}

// 删除第一个节点

public void deleteFirst() {

del(0);

}

// 删除最后一个节点

public void deleteLast() {

del(mCount-1);

}

}

测试程序(DlinkTest.

public class DlinkTest {

// 双向链表操作int数据

private static void int_test() {

int[] iarr = {10, 20, 30, 40};

System.out.println('----int_test----');

// 创建双向链表

DoubleLink dlink = new DoubleLink();

dlink.insert(0, 20); // 将 20 插入到第一个位置

dlink.appendLast(10); // 将 10 追加到链表末尾

dlink.insertFirst(30); // 将 30 插入到第一个位置

// 双向链表是否为空

System.out.printf('isEmpty()=%b', dlink.isEmpty());

// 双向链表的大小

System.out.printf('size()=%d', dlink.size());

// 打印出全部的节点

for (int i=0; i

System.out.println('dlink('+i+')='+ dlink.get(i));

}

private static void string_test() {

String[] sarr = {'ten', 'twenty', 'thirty', 'forty'};

System.out.println('----string_test----');

// 创建双向链表

DoubleLink dlink = new DoubleLink();

dlink.insert(0, sarr[1]); // 将 sarr中第2个元素 插入到第一个位置

dlink.appendLast(sarr[0]); // 将 sarr中第1个元素 追加到链表末尾

dlink.insertFirst(sarr[2]); // 将 sarr中第3个元素 插入到第一个位置

// 双向链表是否为空

System.out.printf('isEmpty()=%b', dlink.isEmpty());

// 双向链表的大小

System.out.printf('size()=%d', dlink.size());

// 打印出全部的节点

for (int i=0; i

System.out.println('dlink('+i+')='+ dlink.get(i));

}

// 内部类

private static class Student {

private int id;

private String name;

public Student(int id, String name) {

this.id = id;

this.name = name;

}

@Override

public String toString() {

return '['+id+', '+name+']';

}

}

private static Student[] students = new Student[]{

new Student(10, 'sky'),

new Student(20, 'jody'),

new Student(30, 'vic'),

new Student(40, 'dan'),

};

private static void object_test() {

System.out.println('----object_test----');

// 创建双向链表

DoubleLink dlink = new DoubleLink();

insert() 插入一个元素到list中。/*在顺序表的第i个位置插入元素e，插入成功返回1，如果插入位置不合法返回-1，顺序表满返回0*/。二分法插入排序是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

dlink.appendLast(students[0]); // 将 students中第1个元素 追加到链表末尾

dlink.insertFirst(students[2]); // 将 students中第3个元素 插入到第一个位置

// 双向链表是否为空

System.out.printf('isEmpty()=%b', dlink.isEmpty());

// 双向链表的大小

System.out.printf('size()=%d', dlink.size());

// 打印出全部的节点

for (int i=0; i

System.out.println('dlink('+i+')='+ dlink.get(i));

}

}

public static void main(String[] args) {

int_test(); // 演示向双向链表操作“int数据”。

string_test(); // 演示向双向链表操作“字符串数据”。

object_test(); // 演示向双向链表操作“对象”。

}

}

运行结果

----int_test----

isEmpty()=false

size()=3

dlink(0)=30

dlink(1)=20

dlink(2)=10

----string_test----

isEmpty()=false

size()=3

dlink(0)=thirty

dlink(1)=twenty

dlink(2)=ten

----object_test----

isEmpty()=false

size()=3

dlink(0)=[30, vic]

dlink(1)=[20, jody]

dlink(2)=[10, sky]

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-96858-1.html