数据结构-线性表的基本操作

---

数据结构-线性表的基本操作

本文介绍我在学习数据结构的过程中如何利用线性表编写算法解决实际问题的方法

---

一、线性表

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

二、带头结点的单链表存储

编写一个Java语言程序，实现带头结点的单链表存储及基本操作，要求依次实现单链表插入、删除、追加、查找、取元素、判空、求长度等

（1）声明单链表结点类

public class Node<T>{
   
    public T data;                               //数据域，存储数据元素
    public Node<T> next;                         //地址域，引用后继结点

    public Node(T data, Node<T> next){
   
            //构造结点，data指定数据元素，next指定后继结点
        this.data = data;                        //T对象引用赋值
        this.next = next;                        //Node<T>对象引用赋值
    }
    public Node() {
   
        this(null, null);
    }
    public String toString(){
                       //返回结点数据域的描述字符串
       return this.data.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（2）编写单链表存取数据，加入插入、删除、追加、查找、取元素、判空、求长度等操作代码

public class SinglyList<T> extends Object {
   
	public Node<T>head;
public SinglyList() {
   
		this.head=new Node<T>();
	}
	public SinglyList(T[] values) {
   //尾插法创建单链表，数组提供元素
		this();//创建只有头节点的单链表
		Node<T>rear=this.head;
		for(int i=0;i<values.length;i++) {
   
			rear.next=new Node<T>(values[i],null);//尾插法
			rear=rear.next;//指向新的尾结点
		}
	}
	public boolean isEmpty() {
   //判断单链表是否为空
		return this.head.next==null;
	}

	//存取
	public T get(int i) {
   //获取值，若i越界，返回null
		Node<T>p=this.head.next;
		for(int j=0;p!=null&&j<i;j++)
			p=p.next;//若p指向i，返回其data值
				return(i>=0&&p!=null)?p.data:null;
	}

	public void set(int i,T x) {
   //设置第i个元素为x
	int j=0;
	Node<T>p=this.head.next;
	for(i=0;p!=null&&j<i;j++) {
   //遍历单链表，寻找结点
		p=p.next;
	}
	if(i>=0&&p!=null) {
   
		p.data=x;
	}
	}

	public int size() {
   //返回单链表长度
		int len=0;
		Node tmp=head;
		while(tmp!=null) {
   
			len++;
			tmp=tmp.next;
		}
		return len;
	}
	  
	public String toString() {
   //返回单链表所有元素的描述字符，形式为"(,)"，覆盖Object类的toString方法
		String str=this.getClass().
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59