数据结构—线性表的存储方式

   线性表的存储方式有两种，一种是顺序表，另外一种是链表。顺序表是一种简单且常用的存储方式。在顺序表中，逻辑相邻的数据，存储地址也相邻。在链表中，逻辑相邻的数据，存储地址不一定相邻。
    顺序表的实现比较简单，通常用数组实现，数组长度确定，将逻辑相邻的数据存储在相邻的地址中，可以计算每个数据的地址，由序号快速查找数据。但是插入、删除需要平均移动
O(n)数据，很不方便。在长度为n的线性表中第i个位置插入数据的过程，需要移动n-i个数据，删除第i个位置的数据需要移动n-i-1个数据。线性表的顺序表代码实现如下：
  

public class linearDeno1{
 private int currentLength;
 private int array[]=new int[100];
 public linearDemo1{
  array[]=new int[100];
}
public void add(int temp){
array[current]=temp;
currentLength++;
}
public void insert(int i,int temp){
int j;
for( j=currentLength-1;j>i-1;j--){
array[j+1]=array[j];
}
array[j]=temp;
}
public void deleteNum(int i){
for( j=currentLength-1;j>i-1;j--){
array[j-1]=array[j];
}
public void deleteContent(int temp){
for(int i=0;i<currentLength;i++){
if(array[i]==temp)}{
for(int j=j=currentLength-1;j>i-1;j--){
array[j-1]=array[j];

}
}
}
}
}

    链表的实现较为复杂，数据存储在不连续的地址中。不能随机查找，只能按顺序查。但是链表的插入和删除非常方便，且长度可变，很灵活。链表分为单链表和其他链表，线性表的实现以单链表为例。单链表分为带头的和不带头的单链表。当链表需要维护确定的信息是用带头的。这样对于插入和删除也比较方便，不用对头进行特殊处理。但是浪费一些存储空间。当不需维护某些信息时，用不带头的单链表，节省存储空间，但对头需要做特殊处理。下面用带头单链表实现。
  

public class Node{
private int name;
private Node next;
public Node(){
}
public Node(int name){
this.name=name;
}
public Node(Node next){
this.next=next;}
public Node(int name,Node next){
this.name=name;
this.next=next;
}
public void setName(){
this.name=name;

}
public int getName(){
return name;}
public void setNext(){
this.next=next;

}
public int getNext(){
return next;}}
public class linearDeno2{
private Node head;

public linearDeno2{
head =new Node(5);}
public void initFirst(Node temp){
temp.setNext(head.getNext);
head.setNext(temp);
}
public void initLast(Node temp){
int length = getLength();
insert(length,temp);
}
public void insert(int i,Node temp){
Node p=getNode(i-1);
temp.setNext(p.getNext());
p.setNext(temp);
}
public void delete(int i){
Node p=getNode(i-1);
p.setNext(p.getNext.getNext)
}
public void delete(Node temp){
int i=0;
Node p=head.getNext();
while(p!=null){
if(p.getNext().equals(temp){
Node p=getNode(i-1);
p.setNext(p.getNext.getNext
}
)
}

public int getLength(){
int length=0;
if(head.getNext()!=null){
Node p=head.getNext();
while(p!=null){
p=p.getNext}
length++;
}
return length;}
public Node getNode(int i){
if(i<0||i>getLength()){
throw new Exception("输入不合法！")；}
int j=0;
Node p=head.getNext();
while(p!=null&&j<i){
p=p.getNext();
j++;}
return p; }
}

   总之，顺序表适合静态线性表，多次随机查询，尽量少插入删除。单链表适合动态线性表，长度动态变化，多次插入删除。

评论

1 楼 飘零羽 2012-06-15  

这个写得还凑合，比那两篇好