数据结构—线性表的储存方式
数据结构—线性表的存储方式
线性表的存储方式有两种,一种是顺序表,另外一种是链表。顺序表是一种简单且常用的存储方式。在顺序表中,逻辑相邻的数据,存储地址也相邻。在链表中,逻辑相邻的数据,存储地址不一定相邻。
顺序表的实现比较简单,通常用数组实现,数组长度确定,将逻辑相邻的数据存储在相邻的地址中,可以计算每个数据的地址,由序号快速查找数据。但是插入、删除需要平均移动
O(n)数据,很不方便。在长度为n的线性表中第i个位置插入数据的过程,需要移动n-i个数据,删除第i个位置的数据需要移动n-i-1个数据。线性表的顺序表代码实现如下:
链表的实现较为复杂,数据存储在不连续的地址中。不能随机查找,只能按顺序查。但是链表的插入和删除非常方便,且长度可变,很灵活。链表分为单链表和其他链表,线性表的实现以单链表为例。单链表分为带头的和不带头的单链表。当链表需要维护确定的信息是用带头的。这样对于插入和删除也比较方便,不用对头进行特殊处理。但是浪费一些存储空间。当不需维护某些信息时,用不带头的单链表,节省存储空间,但对头需要做特殊处理。下面用带头单链表实现。
总之,顺序表适合静态线性表,多次随机查询,尽量少插入删除。单链表适合动态线性表,长度动态变化,多次插入删除。
线性表的存储方式有两种,一种是顺序表,另外一种是链表。顺序表是一种简单且常用的存储方式。在顺序表中,逻辑相邻的数据,存储地址也相邻。在链表中,逻辑相邻的数据,存储地址不一定相邻。
顺序表的实现比较简单,通常用数组实现,数组长度确定,将逻辑相邻的数据存储在相邻的地址中,可以计算每个数据的地址,由序号快速查找数据。但是插入、删除需要平均移动
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
这个写得还凑合,比那两篇好