大话数据结构-第3章 线性表

    **线性表之单链表**

线性表是数据结构中最简单的基本数据结构。线性表的使用和维护都很简单,这一特点使其成为很多算法的基础。数组、链表、栈、队列是4中最常见的线性表,其外部行为和接口都各有特色。

线性表:零个或多个元素的有限序列;

3. 线性表

3.1 线性表(List): 零个或多个数据元素的有限序列


3.2 线性表的定义

若将线性表记为(a1, … ,ai-1, ai, ai+1, … , an), 则表中 ai-1 领先于
ai, ai, 领先于 ai+1, 称ai-1是ai的直接前驱元素, ai+1 是 ai
的直接后继元素. 当 i=1, 2, … , n-1 时, ai 有且仅有一个直接后继, 当
i=2, 3 , … , n 时, ai 有且仅有一个直接前缀.
线性元素的个数 n (n>=0) 定义为线性表的长度, 当 n = 0 时, 称为空表


3.5 顺序存储结构的插入与删除

  • 线性表的顺序存储结构, 在存, 读 数据时, 时间复杂度是 O[1]
  • 插入, 删除时, 时间复杂度为 O[n]

线性表顺序存储结构的优缺点

  • 优点:
    • 无需为表示表中元素之间的逻辑关系而增加二外的存储空间
    • 可以快速的存取表中任一位置的元素
  • 缺点:
    • 插入和删除操作需要移动大量的元素
    • 当线性表长度变化较大时, 难以确定存储空间的容量
    • 造成存储空间的 “碎片”

一、头文件:LinkedList.h

线性表(List):零个或多个数据元素的一有限序列

图片 1

链表

3.6 线性表的链式存储结构

链式结构中, 除了要存储数据元素信息外, 还要存储它的后继元素地址

为了表示每个元素ai与其直接后继数据元素ai+1之间的逻辑关系,
对数据元素ai来说, 除了存储本身的信息之外,
还需存储一个指示其直接后继的信息(即直接后继的存储位置).
我们把存储元素信息的域称为数据域, 把存储直接后继位置的域称为指针域.
指针域中存储的信息称为指针或者链. 这两部分信息组成数据元素ai的存储映像,
称为节点(Node)

n 个节点(ai的存储映像)链接成一个链表, 即
为线性表(a1,a2,…an)的链式结构,
因为此链表的每个节点中只包含有一个指针域, 所以叫做单链表.

链表中第一个节点的存储位置叫做头指针, 最后一个节点为空(NULL 或者 ^)

单链表的第一个节点前附加一个节点,称为头节点(不是必须的). 不存储任何信息,
指向第一个节点.


3.7 单链表的读取

工作指针后移, 一个一个顺序读取.


3.8 单链表的插入与删除

插入与删除的时间复杂度都是O[1], 对于插入和删除数据越频繁的操作,
单列表的效率优势就越是明显


3.9 单链表的整表创建

    1. 头插法:
    1. 尾插法:

3.10 单链表的整表删除

将链表中的所有元素依次删除


3.11 单链表结构与顺便存储结构优缺点

存储分配方式

  • 顺便存储结构用一段连续的存储单元依次存储线性表的数据元素
  • 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素

时间性能

  • 查找:
    • 顺序存储o(1)
    • 单链表o(n)
  • 插入和删除
    • 顺序存储结构需要平均移动表上一般的元素 时间为o(n)
    • 单链表在得到某位置的指针后, 插入和删除时间仅为o(1)

空间性能

  • 顺序存储结构需要预分配存储空间, 分大了 浪费, 分小了, 容易发生上溢
  • 单链表不需要分配存储空间, 只要有就可以分配, 元素个数也不受限制

结论:

  • 若线性表需要频繁查找, 很少进行插入和删除操作时, 宜采用顺序存储结构.
    若需要频繁插入和删除时, 宜采用单链表结构
  • 当线性表中的元素个数变化较大或者根本不知道有多大时,
    最好用单链表结构. 这样可以不需要考虑存储空间的大小问题.
    而如果实现知道线性表的大致长度,如一年12个月,
    一周就是星期一至星期天共七天, 用顺序存储结构效率会高很多

3.12 静态链表
优点: 在插入和删除操作时, 只需要修改游标, 不需要移动元素,
从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点
缺点: 没有解决连续存储分配带来的表长难以确定的问题
失去了顺序存储结构随机存取的特性

3.13 循环链表
将单链表中终端节点的指针端由空指针改为指向头节点,
就使整个单链表形成一个环, 这种头尾相接的单链表称为单循环链表,
简称循环链表(circular linked list)

3.14 双向链表
双向列表插入, 要先完善插入元素的 next 和 prior 指向, 再完善其他的

3.15 总结

  • 线性表
  • 顺序存储结构
  • 链式存储结构
  • 单链表
  • 静态链表
  • 循环链表
  • 双向链表
  1 //单链表是用一组任意的存储单元存放线性表的元素,这组单元可以是连续的也可以是不连续的,甚至可以是零散分布在内存中的任意位置。
  2 //单链表头文件
  3 #include<iostream>
  4 using namespace std;
  5 //定义单链表结点-结构体类型
  6 template<class DataType>
  7 struct Node
  8 {
  9   //数据域,存放该结点的数据
 10   DataType data;
 11   //指针域,指向下一个结点
 12   Node<DataType> *next;
 13 };
 14 
 15 template<class DataType>
 16 class LinkedList{
 17 public:
 18   //单链表无参构造器
 19   LinkedList();
 20   //单链表有参构造器
 21   LinkedList(DataType array[], int n);
 22   LinkedList(int n, DataType array[]);
 23   //单链表析构函数
 24   ~LinkedList();
 25   //获取单链表的长度
 26   int GetLength();
 27   //查找单链表指定元素的序号
 28   int GetLocal(DataType x);
 29   //获取单链表指序号的元素
 30   DataType GetElement(int index);
 31   //单链表中在指定位置插入指定的元素
 32   void Insert(int index, DataType x);
 33   //在单链表中删除指定位置的元素
 34   DataType Delete(int index);
 35   //按序号输出单链表中的元素
 36   void PrintLinkedList();
 37 
 38 private :
 39   //声明单链表的头指针
 40   Node<DataType> *first;
 41 };
 42 
 43 //实现单链表的无参构造函数
 44 template<class DataType>
 45 LinkedList<DataType>::LinkedList()
 46 {
 47   first = new Node<DataType>;
 48   first->next = NULL;
 49 }
 50 
 51 //头插法建立单链表
 52 template<class DataType>
 53 LinkedList<DataType>::LinkedList(int n,DataType array[])
 54 {
 55   //初始化一个空链表
 56   first = new Node<DataType>;
 57   first->next = NULL;
 58   for (int i = 0; i < n; i++)
 59   {
 60     //为每一个数组元素都申请新结点
 61     Node<DataType> *s = new Node<DataType>;
 62     //数组元素赋值给结点数据域
 63     s->data = array[i];
 64     //将结点插入到头结点之前
 65     s->next = first->next;
 66     first->next = s;
 67 
 68   }
 69 }
 70 
 71 //尾插法建立单链表
 72 template<class DataType>
 73 LinkedList<DataType>::LinkedList(DataType array[], int n)
 74 {
 75   //生成头结点
 76   first = new Node<DataType>;
 77   //定义尾结点
 78   Node<DataType> *r = first;
 79   for (int i = 0; i < n; i++)
 80   {
 81     //为每一个数组元素申请一个结点
 82     Node<DataType> *s = new Node<DataType>;
 83     //把数组元素赋值给结点的数据域
 84     s->data = array[i];
 85     //将每一个结点追加到终端结点之后
 86     r->next = s;
 87     r = s;
 88   }
 89   //尾结点尾NULL
 90   r->next = NULL;
 91 }
 92 
 93 //实现单链表的析构函数
 94 template<class DataType>
 95 LinkedList<DataType>::~LinkedList()
 96 {
 97   //声明工作指针
 98   Node<DataType> *q;
 99   while (first != NULL)
100   {
101     //暂存被释放的结点
102     q = first;
103     //让头指针指向要释放结点的下一个结点
104     first = first->next;
105     delete q;
106   }
107 }
108 
109 //实现单链表插入:在指定的位置插入指定的元素
110 template<class DataType>
111 void LinkedList<DataType>::Insert(int index, DataType x)
112 {
113   //定义工作指针
114   Node<DataType> *p = first->next;
115   //定义计数器,初始值为0
116   int count = 0;
117   while (p != NULL &&count < index - 1)
118   {
119     //工作指针后移
120     p = p->next;
121     count ++;
122   }
123   //找到 index-1 的位置
124   if (p == NULL)
125   {
126     throw "插入的位置有误";
127   }
128   else
129   {
130     //申请一个新结点
131     Node<DataType> *s;
132     s= new Node<DataType>;
133     //其数据域为 x
134     s->data = x;
135     //在新结点的指针域存放工作指针p的指针域
136     s->next = p->next;
137     //将结点s插入到p结点之后
138     p->next = s;
139   }
140 }
141 
142 //实现单链表的按值查找,返回指定元素在单链表中的序号(如不存在,则返回0)
143 template<class DataType>
144 int LinkedList<DataType>::GetLocal(DataType x)
145 {
146   //定义工作指针
147   Node<DataType> *p = first->next;
148   //定义计数器,初始值是1
149   int count = 1;
150   //查找序号所对应的位置
151   while (p != NULL)
152   {
153     if (p->data == x)
154     {
155       return count;
156     }
157     //工作指针后移
158     p = p->next;
159     //计数器加1
160     count++;
161   }
162   //如果找不到该元素,则返回0
163   return 0;
164 }
165 
166 //实现单链表按位查找,返回指定位置的元素
167 template<class DataType>
168 DataType LinkedList<DataType>::GetElement(int index)
169 {
170   //定义工作指针
171   Node<DataType> *p = first->next;
172   //定义计数器,初始值是1
173   int count = 1;
174   //查找序号所对应的位置
175   while (p != NULL&&count < index)
176   {
177     //工作指针后移
178     p = p->next;
179     //计数器加1
180     count++;
181   }
182   //如果找到单链表的末尾,还找不到指定的位置,则抛出异常
183   if (p == NULL)
184   {
185     throw "查找的位置有误";
186   }
187   else
188   {
189     //当找到合适的位置时,返回该位置上的元素
190     return p->data;
191   }
192 
193 }
194 
195 //实现获取单链表的长度
196 template<class DataType>
197 int LinkedList<DataType>::GetLength()
198 {
199   //定义计数器,用来计算单链表的长度
200   int count = 0;
201   //定义工作指针
202   Node<DataType> *p = first->next;
203   while (p != NULL)
204   {
205     p = p->next;
206     count++;
207   }
208   return count;
209 
210 }
211 
212 //实现单链表的按序号输出元素
213 template<class DataType>
214 void LinkedList<DataType>::PrintLinkedList()
215 {
216   //声明工作指针
217   Node<DataType> *p;
218   //初始化工作指针
219   p = first->next;
220   while(p != NULL)
221   {
222     cout << p->data << " ";
223     //工作指针向后移动
224     p = p->next;
225   }
226   cout << endl;
227 }
228 
229 //实现单链表的删除
230 template<class DataType>
231 DataType LinkedList<DataType>::Delete(int index)
232 {
233   Node<DataType> *p = first->next;
234   int count = 0;
235   //查找第 index-1 位置结点
236   while (p != NULL&&count < index - 1)
237   {
238     p = p->next;
239     count++;
240   }
241   //如果能找到
242   if (p == NULL || p->next == NULL)
243   {
244     throw "删除的位置有误";
245   }
246   else
247   {
248     Node<DataType> *q = p->next;
249     DataType x = q->data;
250     p->next = q->next;
251     delete q;
252     return x;
253   }
254 }
  • 序列:元素之间是有顺序的,若元素存在多个则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。
  • 有限:元素个数是有限制的

线性表.jpg

二、测试线性表之单链表的源文件:TestLinkedList.cpp

图片 2

线性表的顺序存储结构

 1 #include<iostream>
 2 #include "LinkedList.h"
 3 using namespace std;
 4 void show()
 5 {
 6   cout << "---------------------------------------" << endl;
 7 }
 8 int main()
 9 {
10   int array[] = { 1, 3, 5, 2, 7, 6, 9, 8, 10, 4};
11   //声明单链表
12   LinkedList<int> linkedList = LinkedList<int>(10,array);
13   cout << "输出单链表:" << endl;
14   linkedList.PrintLinkedList();
15   show();
16   cout << "单链表的长度:" << linkedList.GetLength() << endl;
17   cout << "单链表中第5个元素是:" << linkedList.GetElement(5) << endl;
18   cout << "单链表中元素5的位置是:" << linkedList.GetLocal(5) << endl;
19   show();
20   cout << "在单链表的第5个位置上插入元素22" << endl;
21   linkedList.Insert(5, 22);
22   cout << "输出单链表:" << endl;
23   linkedList.PrintLinkedList();
24   cout << "单链表的长度:" << linkedList.GetLength() << endl;
25   show();
26   cout << "删除第5位置的元素" << endl;
27   linkedList.Delete(5);
28   cout << "输出单链表:" << endl;
29   linkedList.PrintLinkedList();
30   cout << "单链表的长度:" << linkedList.GetLength() << endl;
31   show();
32   return 0;
33 }

线性表

线性表的顺序存储结构:用一段地址连续的存储单元依次存储线性表的数据元素。

三、运行示例结果

线性表元素的个数n(n>0)定义为线性表的长度,当n=0时称为空表。

package dataStructure;
//线性表顺序存储结构
public class SeqList<T>{
    public static int MAXSIZE = 20; //存储空间初始分配量
    private int length; //线性表当前长度
    private T[] data; //数组存储数据元素

    @SuppressWarnings("unchecked")
![Uploading 线性表_425942.jpg . . .]
    public SeqList(){
        data = (T[]) new Object[MAXSIZE];
    }
    //获取第i个元素
    public T getElem(int i){
        if(i<1 || i>getLength()){
            return null;
        }else{
            return data[i-1];
        }
    }

    //在位置i插入元素e
    public boolean ListInsert(int i,T e){
        //若顺序表已满
        if(getLength() == MAXSIZE){
            return false;
        }
        //i不在范围内
        if(i<1 || i>getLength()+1){
            return false;
        }else{
            //插入位置不在表尾
            if(i<getLength()){
                for(int j= getLength()-1;j>=i-1;j--){
                    data[j+1] = data[j];
                }
            }
            data[i-1] = e;
            setLength(getLength() + 1);
            return true;
        }
    }

    //删除第i个元素
    public T ListDelete(int i){
        //若表为空
        if(getLength() == 0){
            return null;
        }
        if(i<1 || i>getLength()){
            return null;
        }else{
            T e = data[i-1];
            //若不是最后一个
            if(i<getLength()){
                for(int j=i-1;j<getLength();j++){
                    data[j] = data[j+1];
                }
            }
            setLength(getLength() - 1);
            return e;
        }
    }
    public int getLength() {
        return length;
    }
    public void setLength(int length) {
        this.length = length;
    }
}

图片 3

图片 4

测试代码:

 

星座列表

package dataStructure;  

import java.util.Random;  

public class SeqListTest {  
    final int MAX = 25;  
    Random r = new Random();  
    SeqList<Integer> seqList;  

    public SeqListTest() {  
        initSeqList();  
    }  

    //创建一个线性表顺序存储结构  
    public void initSeqList() {  

        seqList = new SeqList<Integer>();  
//      int length = (int) Math.random();   //只能产生0.0 - 1.0之间的double随机数  
        int length = Math.abs(r.nextInt(MAX));  //使用Random随机产生一个25左右的值,使用Math.abs()函数来取绝对值    
        System.out.println("产生的数组长度为 :" + length);  

        if(length > SeqList.MAXSIZE) {  
            System.out.println("该长度不合法");  
        }  

        for (int i = 1; i <= length; i++) {  //为生成的数组赋值,同时也测试了插入值的方法  
            int j =r.nextInt(MAX);  
            System.out.print(j + " ");  

            if(!seqList.ListInsert(i, j)) {  
                System.exit(0);   
            }  
        }  
        System.out.println("\n原始数组是 :");  
        display(seqList);  
    }  

    //测试删除方法  
    public void deleteElem() {  
        int i = r.nextInt(MAX);  
        System.out.println("\n\n删除的位置是:" + i);  
        Integer deleteNumber = seqList.ListDelete(i);  

        if( deleteNumber == null) {  
            System.exit(0);  
        } else {  
            System.out.println("删除的元素是 : " + deleteNumber);  
            System.out.println("删除元素后数组是 :");  
            display(seqList);  
        }  
    }  

    //测试随机插入方法  
    public void insertByRandom() {  
        int i = r.nextInt(MAX);  
        System.out.println("\n\n随机插入位置是 :" + i);  
        int elem = r.nextInt(MAX);  
        System.out.println("随机插入数据是 :" + elem);  
        seqList.ListInsert(i, elem);  
        System.out.println("随机插入数据后数组是 :");  
        display(seqList);  
    }  

    //数据展示  
    public  void display(SeqList seqList) {  
        for (int i = 1; i <= seqList.getLength(); i++) {  

            if(seqList.getElem(i) != null) {  
                System.out.print(seqList.getElem(i) + " ");  
            }  

        }  
        System.out.println("数组的长度为 :" + seqList.getLength());  
    }  

    //获取元素  
    public void getElem() {  
        int i = r.nextInt(MAX);  
        System.out.println("\n获取位置为 :" + i);  
        System.out.println("获取到的元素为 : " + seqList.getElem(i));  


    }  

    public static void main(String[] args) {  
        SeqListTest s = new SeqListTest();  
        s.insertByRandom();  
        s.deleteElem();  
        s.getElem();  
    }  
} 

在较复杂的线性表中,一个数据元素可以由若干个数据项组成。

顺序存储优点:
1.无需为表示表中元素之间的逻辑关系而增加额外的存储空间。
2.对于存,读数据时时间复杂度都是O(1)。

图片 5

顺序存储缺点:
1.插入和删除操作需要移动大量元素,时间复杂度为O(n)。
2.线性表长度变化较大时,无法确定存储空间的容量。

复杂线性表中数据元素可由若干数据项组成

线性表的链式存储结构(单链表)

线性表的抽象数据类型

ADT 线性表(List)
Data
  线性表的数据对象集合为{a1,a2,a3...an},每个元素的类型均为DataType。
  其中除第一个元素a1外,每个元素有且只有一个直接前驱元素。
  除了最后一个元素an外,每个元素有且只有一个直接后继元素。
  数据元素之间的关系是一对一的关系。
Operation
  InitList(*L) 初始化建立一个空的线性表L
  ListEmpty(L) 若线性表为空则返回true否则返回false
  ClearList(*L) 将线性表清空
  GetElem(L,i,*e) 将线性表L中的第i个位置元素值返回给e
  LocateElem(L,e) 在线性表L中查找与给定值e相等的元素,若查找成功返回该元素在表中序号表示成功,否则返回0表示失败。
  ListInsert(*L, i, e) 在线性表L中的第i个位置插入新元素e
  ListDelete(*L, i, *e) 删除线性表L中第i个位置元素并用e返回其值
  ListLength(L) 返回线性表L的元素个数
endADT

线性表的链式存储结构:用一组任意的存储单元存储线性表的数据元素。存储单元可以是连续的也可以是不连续的。

线性表的顺序存储结构

线性表的顺序存储结构指的是一段地址连续的存储单元依次存储线性表的数据元素。

图片 6

线性表(a1,a2,…an)的顺序存储

顺序存储结构需要三个属性:

  • 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置。
  • 线性表的最大存储容量:数组长度MAXSIZE
  • 线性表的当前长度:length

#define MAXSIZE 20 //线性表的最大存储空间,存储空间初始大小,数组data的存储位置就是存储空间的存储位置。

typedef int ElemType;//元素类型
typedef struct
{
    ElemType data[MAXSIZE];//使用数组存储数据元素,元素最大个数为MAXSIZE。
    int length;//线性表当前长度
}List;

数据长度和线性表长度区别

  • 数组的长度时存储空间的长度,存储分配后这个量一般是不变的。
  • 线性表的长度时线性表中数据元素的个数,随着线性表插入和删除操作而变化。
  • 在任意时刻,线性表的长度应该小于等于数组的长度。

地址计算方法

图片 7

线性表当前长度

C语言中数组从0开始第一个下标,线性表的第i个元素是要存储在数组下标i-1的位置,即数据元素的序号和存放它的数组下标之间的对应关系。

用数组存储顺序表意味着要分配固定长度的数组空间,由于线性表中可以进行插入和删除操作,因此分配的数组空间要大于等于当前线性表的长度。

存储器中的每个存储单元都有自己的编号,这个编号称为地址。

图片 8

计算线性表中任意位置的地址

  • 头指针:若有头结点,则指向头结点;否则是指向第一个结点。无论链表是否为空,头指针都不为空。
  • 头结点:为了操作的方便而设立,在第一个元素之前。头结点的数据域不存储任何信息,指针指向第一个结点。若线性表为空,头结点的指针域为空。
  • 最后一个结点指针为null

线性表顺序存储结构的插入和删除

获取元素

/*获取元素*/
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
//将线性表list中第pos个位置元素值返回,只要pos的数值在数组下标范围内,就将数组第pos-1下标的值返回即可。
Status GetListElem(List list, int pos, ElemType *ele)
{
    //初始条件:顺序线性表L已存在,1 <= i <= ListLength(L)
    if(list.length == 0 || pos<1 || pos>list.length){
        return ERROR;
    }
    *ele = list.data[pos-1];//用e返回L中第i个数据元素的值
    return OK;
}

插入元素

图片 9

插入操作

/*插入元素*/
Status InsertListElem(List *list, int pos, ElemType ele)
{
    int i;
    //判断线性表是否已经满
    if(list->length == MAXSIZE){
        return ERROR;
    }
    //判断插入位置是否在数组范围内
    if(pos < 1 || pos > list->length+1){
        return ERROR;
    }
    //若插入位置不在线性表末尾
    if(pos <= list->length){
        //将要插入位置后数组元素向后移动一位
        for(i = list->length-1; i >= pos-1; i--){
            list->data[i+1] = list->data[i];
        }
    }
    //将新元素插入线性表中
    list->data[pos-1] = ele;
    list->length++;
    return OK;
}

删除元素

图片 10

线性表的顺序存储结构删除元素

/*删除元素*/
Status DeleteListElem(List *list, int pos, ElemType *ele)
{
    int i;
    //判断线性表是否为空
    if(list->length == 0){
        return ERROR;
    }
    //判断删除位置是否在有效,且删除位置是否有效。
    if(pos<1 || pos > list->length){
        return ERROR;
    }
    //获取要删除元素
    *ele = list->data[pos-1];
    //判断删除位置是否为线性表的最后位置
    if(pos < list->length){
        //将删除位置后续元素前移
        for(i = pos; i < list->length; i++){
            list->data[pos-1] = list->data[i];
        }
    }

    list->length--;
    return OK;
}

/*将两线性表中差集元素插入某线性表中*/
void union(List *l1, List l2)
{
    int l1len, l2len;
    int i;
    ElemType ele;
    //获取线性表的长度
    l1len = ListLength(l1);
    l2len = ListLength(l2);

    for(i=1; i<l1len; i++){
        //获取线性表list2第i个数据元素赋给临时元素ele
        GetListElem(l2, i, ele);
        //判断线性表list1中是否存在和临时元素ele相同的元素
        if(!LocateListElem(l1, ele, equal)){
            //向线性表list1末尾插入临时元素ele
            InsertListElem(l1, ++l1len, ele);
        }
    }
}

线性表顺序存储结构的优缺点

图片 11

线性表顺序存储结构的优缺点

package dataStructure;
//链表中的结点node
public class Node<T>{
    private T data; // 数据域
    private Node<T> next;//指针域
    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public Node<T> getNext() {
        return next;
    }
    public void setNext(Node<T> next) {
        this.next = next;
    }
}

package dataStructure;

public class LinkList<T>{
    private Node<T> head;//头结点
    private int length;//链表的长度

    public LinkList(Node<T> head) {  
        this.head = head;  
    }  

    //获取第i个元素
    public T getElem(int i){
        int j = 1;
        Node<T> n = head.getNext();//第一个元素
        //得到第i个结点
        while(n!=null && j<i){
            n = n.getNext();
            j++;
        }
        if(n == null || j>i){
            return null;
        }else{
            return n.getData();
        }

    }

    //在位置i之后插入e
    public boolean ListInsert(int i,T e){
        int j = 1;
        Node<T> n = head;
        //若为第一次插入
        if(head == null && i==1){
            head = new Node<T>();
            head.setData(null);
            Node<T> first = new Node<T>();
            first.setData(e);
            head.setNext(first);
            length++;
            return true;
        }else{
            //得到第i个结点
            while(n!=null && j<i){
                n = n.getNext();
                j++;
            }
            if(n == null || j>i){
                return false;
            }else{
                Node<T> s = new Node<T>();
                s.setData(e);
                s.setNext(n.getNext());
                n.setNext(s);
                length++;
                return true;
            }
        }

    }

    //删除位置i
    public T ListDelete(int i){
        int j = 1;
        Node<T> n = head.getNext();
        //得到第i-1个结点
        while(n!=null && j<i-1){
            n = n.getNext();
            j++;
        }
        if(n == null || j>i-1){
            return null;
        }else{
            T e = n.getNext().getData();
            n.setNext(n.getNext().getNext());
            length--;
            return e;
        }

    }

    public Node<T> getHead() {
        return head;
    }
    public void setHead(Node<T> head) {
        this.head = head;
    }
    public int getLength() {
        return length;
    }
    public void setLength(int length) {
        this.length = length;
    }
}

线性表的链式存储结构

线性表的顺序存储结构的最大缺点是插入和删除时需要移动大量元素,显然需要耗费时间。考虑下导致这个问题的原因。原因在于相邻像个元素的存储位置也具有邻居关系。

图片 12

单线索无分支 – 线性表的链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存为被占用的任意位置。

线性表的顺序结构中,每个数据元素只需要存储数据元素信息即可。在线性表链式结构中,除了要存储数据元素信息外,还要存储它的后续元素的存储地址。

为了表示每个数据元素ai与其直接后续数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储器本身的信息之外,还需存储一个指示其直接后续的信息(即直接后续的存储位置)。把存储数据元素信息的域称为数据域,把存储直接后续位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素的存储映像,称为结点(node)。

n个结点(ai的存储映像)链接成了一个链表,即为线性表的链式存储结构,因为链表的每个结点中只包含一个指针域,所以叫做单链表。

图片 13

单链表

把链表中第一个节点的存储位置叫做头指针,整个链表的存取必须是从头指针开始。之后每个节点就是上一个的后续指针指向的位置。

链表中最后一个直接后继不存在,应该线性链表的最后一个节点指针为空。通常用NULL或^表示。

图片 14

头指针

为了方便地对链表操作,在单链表的地一个节点前附近设一个结点称为头结点。头节点的数据域可以不存储任何信息,也可以存储线性表长度等附加信息,头节点的指针域存储指向第一个节点的指针。

图片 15

头结点

头指针和头结点的异同

图片 16

头指针和头结点异同点

若线性表为空表,则头结点的指针域为空。

图片 17

空链表

测试代码:

线性表链式存储结构代码描述

图片 18

存储示意图

图片 19

单链表

图片 20

空链表

C语言中使用结构指针来描述单链表

// 线性表的单链表存储结构
typedef struct Node
{
    //存放数据元素的数据域
    ElemType data;
    //存放后续节点地址的指针域
    struct Node *next;
} Node;

// 定义单链表 LinkList
typedef struct Node *LinkList;
package dataStructure;

import java.util.Random;

public class LinkListTest {
    final int MAX = 25;
    Random r = new Random();
    LinkList<Integer> linkList;

    public LinkListTest() {
        initSeqList();
    }

    //创建一个线性表顺序存储结构
    public void initSeqList() {
        linkList = new LinkList<Integer>(null);
        int length = Math.abs(r.nextInt(MAX));  //使用Random随机产生一个25左右的值,使用Math.abs()函数来取绝对值  
        System.out.println("产生的链表长度为 :" + length);

        for (int i = 1; i <= length; i++) { //为生成的链表赋值,同时也测试了插入值的方法
            int j =r.nextInt(MAX);
            System.out.print(j + " ");

            if(!linkList.ListInsert(i, j)) {
                System.exit(0); 
            }
        }
        System.out.println("\n原始链表是 :");
        display(linkList);
    }

    //测试删除方法
    public void deleteElem() {
        int i = r.nextInt(MAX);
        System.out.println("\n\n删除的位置是:" + i);
        Integer deleteNumber = linkList.ListDelete(i);

        if( deleteNumber == null) {
            System.exit(0);
        } else {
            System.out.println("删除的元素是 : " + deleteNumber);
            System.out.println("删除元素后链表是 :");
            display(linkList);
        }
    }

    //测试随机插入方法
    public void insertByRandom() {
        int i = r.nextInt(MAX);
        System.out.println("\n\n随机插入位置是 :" + i);
        int elem = r.nextInt(MAX);
        System.out.println("随机插入数据是 :" + elem);
        linkList.ListInsert(i, elem);
        System.out.println("随机插入数据后链表是 :");
        display(linkList);
    }

    //数据展示
    public  void display(LinkList<Integer> linkList) {
        Node<Integer> node = linkList.getHead();
        while(node != null) {
            System.out.print(node.getData() + " ");
            node = node.getNext();
        }
        System.out.println("链表的长度为 :" + linkList.getLength());
    }

    //获取元素
    public void getElem() {
        int i = r.nextInt(MAX);
        System.out.println("\n获取位置为 :" + i);
        System.out.println("获取到的元素为 : " + linkList.getElem(i));


    }

    public static void main(String[] args) {
        LinkListTest s = new LinkListTest();
        s.insertByRandom();
        s.deleteElem();
        s.getElem();
    }
}

单链表的读取

图片 21

单链表

// 读取单链表的元素:用e返回l中第i个数据元素的值
Status GetItem(LinkList ll, int i, ElemType *et)
{
    // 声明某节点
    LinkList p;
    // 让p指向链表ll的第一个结点
    p = ll->next;

    // 计数器
    int j;
    j = 1;
    //p不为空或计数器j小于i时循环继续
    while(p && j<i){
        // 让p指向下一个结点
        p = p->next;
        ++j;
    }

    // 第i个元素不存在
    if(!p || j>i){
        return ERROR;
    }

    //获取第i个元素的数据
    *et = p->data;

    return OK;
}

由于单链表的结构没有定义表长,因此不方便使用for来控制循环。其主要核心思想是“工作指针后移”。

虽然已上所有链表的操作时间复杂度都为O(n),但如果在第i个位置插入10个结点这种操作,对于顺序存储结构是每次插入都要移动n-i个点,每次都是O(n)。但对于链式存储结构,只要在第一次通过O(n)找到位置i,那么接下来插如的操作时间复杂度都是O(1)。
因此,对于插入或删除数据越频繁的操作,单链表的效率优势越明显。

单链表的插入

图片 22

单链表的插入

图片 23

单链表的表头和表尾的插入

/*单链表插入:在链表l中第i个位置之前插入新数据元素e,链表l长度加1.*/
Status ListInsert(LinkList *l, int i, ElemType e)
{
    LinkList p, s;
    p = *l;
    //计数器
    int j;
    j = 1;
    //寻找第i个结点
    while(p && j<i)
    {
        p = p->next;
        ++j;
    }
    //第i个元素不存在
    if(!p || j>i){
        return ERROR;
    }
    //生成新结点
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;//将p的后续结点赋值给s的后续

    p->next = s;//将s赋值给p的后续

    return OK;
}
  • 单链表的整表创建

单链表的删除

图片 24

单链表的删除

/*单链表的删除:删除链表l的第i个元素,并用元素e返回其值,同时链表l长度减1*/
Status ListDelete(LinkList *l, int i, ElemType *e)
{
    LinkList p,q;
    //计数器
    int j;
    j = 1;
    //遍历寻找第i个元素
    while(p->next && j<i){
        p = p->next;
        ++j;
    }
    //第i个元素不存在
    if(!(p->next) || j>i){
        return ERROR;
    }

    q = p->next;
    p->next = q->next;//将q的后续赋值给p的后续
    *e = q->data;//将q节点中的数据给*e
    free(q);//让系统回收此节点释放内存

    return OK;
}

效率PK: 对于插入或删除数据越频繁的操作,单链表的效率优势就越明显。

单链表的整表创建

  • 对于顺序存储结构的线性表的整表创建,可以使用数组的初始化来直观理解。
  • 单链表和顺序存储结构不一样,不像顺序存储结构数据那样集中,它的数据可以是分散在内存各个角落中,它的增长也是动态的。
  • 对于每个链表来说,所占用空间的大小和位置是无需预先分配划定的,可以根据系统的情况和实际的需求即时生成。
  • 创建单链表的过程是一个动态生成链表的过程,从空表的初始状态开始,依次建立各元素节点并插入链表。

单链表整表创建的算法思路

  • 声明一节点p和计数器变量i
  • 初始空链表L
  • 让L的头节点的指针指向NULL,即建立一个带头节点的单链表。
  • 循环实现后继节点的赋值和插入

头插法建立单链表

  • 从一个空表开始,生成新节点,读取数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。
  • 简单来说就是把新加入的元素放在表头后的第一个位置,先让新节点的next指向头节点之后。然后让表头的next指向新节点。

图片 25

单链表整表创建(头插法)

/*单链表整表创建:随机产生n个元素的值,建立带表头结点的单链线性表l(头插法)*/
void CreateListHead(LinkList *l, int n)
{
    //声明结点
    LinkList p;
    //声明计数器变量
    int i;

    //初始化随机数种子
    srand(time(0));

    //初始化空链表,建立带头结点的单链表。
    *l = (LinkList)malloc(sizeof(Node));
    (*l)->next = NULL;//让链表的头结点指向NULL即创建带头结点的单链表

    for(i=0; i<n; i++){
        //生成新结点赋值给p
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand()%100 + 1;//随机生成100以内的数字,赋值给p的数据域
        //将p插入到头结点与前一结点之间
        p->next = (*l)->next;
        (*l)->next = p;//插入到表头
    }
}

尾插法

void CreateListTail(LinkList *L, int pos)
{
    LinkList p,r;
    int i;

    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    r = *L;

    for(i=0; i<pos; i++){
        p = (Node *)malloc(sizeof(Node));
        p->data = rand()%100+i;
        r->next = p;
        r = p;
    }

    r->next = NULL;
}
package dataStructure;

public class CreateLinkList {
    // 头插法创建长度为n的链表
    public static LinkList<Integer> createListHead(int n) {
        Node<Integer> head = new Node<Integer>();
        LinkList<Integer> list = new LinkList<Integer>(head);
        int j = 1;
        // 将新结点插入到头结点与前一新结点之间
        while (j <= n) {
            Node<Integer> p = new Node<Integer>();
            p.setData((int) (Math.random() * 25));
            System.out.println(p.getData());
            p.setNext(head.getNext());
            head.setNext(p);
            j++;
        }
        return list;

    }

    // 尾插法创建长度为n的链表
    public static LinkList<Integer> createListTail(int n) {
        Node<Integer> head = new Node<Integer>();
        LinkList<Integer> list = new LinkList<Integer>(head);
        int j = 1;
        // 将结点插入到最后
        while (j <= n) {
            Node<Integer> p = new Node<Integer>();
            p.setData((int) (Math.random() * 25));
            System.out.println(p.getData());
            head.setNext(p);
            head = p;
            j++;
        }
        return list;
    }

    // 数据展示
    public static void display(LinkList<Integer> linkList) {
        Node<Integer> node = linkList.getHead();
        while (node != null) {
            System.out.print(node.getData() + " ");
            node = node.getNext();
        }
    }

    public static void main(String args[]) {
        display(createListHead(7));
    }
}

单链表的整表删除

  • 当不打算使用单链表时需将其销毁,即在内存中将其释放掉,以便留出空间给其他程序或软件使用。
  • 单链表整表删除的算法思路
    • 声明节点p和q
    • 将第一个节点赋值给p下一个节点赋值为q
    • 循环执行释放p和将q赋值给p的操作

Status ClearList(LinkList *L)
{
    LinkList p,q;
    p = (*L)->next;//p指向第一个节点
    //没有表尾
    while(p){
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;//头节点指针域为空
    return OK;
}
  • 单链表的整表删除

单链表结构与顺序存储结构优缺点

  • 存储分配方式
    • 顺序存储结构用一段连续的存储单元一次存储线性表的数据元素
    • 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素。
  • 时间性能
    • 查找:顺序存储结构为O(1),单链表为O(n)。
    • 插入和删除:顺序存储结构需平均移动表长一半的元素,时间为O(n)。单链表在计算出某位置的指针后,插入和删除时间仅为O(1)。
  • 空间性能
    • 顺序存储结构需要预先分配存储空间,分大了容易造成空间浪费,分小了容易发生溢出。
    • 单链表不需要分配存储空间,只要有就可以分配,元素个数不受限制。

若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。若需要频繁插入和删除时,宜采用单链表结构。

//整表删除
    public void clearList(){
        Node<T> p = head;
        Node<T> q = new Node<T>();
        while(q != null){
            q = p.getNext();
            if(q!=null){
                p.setNext(q.getNext());
                length--;
            }

        }
    }

比较两种存储方式

图片 26

Paste_Image.png

  • 若线性表要频繁查找,很少进行插入和删除,宜使用顺序存储结构。反之宜用单链表结构。
  • 当线性表中的元素个数变动较大或根本不知道有多大时,最好使用单链表。而如果事先知道线性表的大致长度,则考虑使用顺序结构。

静态链表

静态链表:用数组描述的链表。
每一个数组的元素有两个数据域:数据域与指针域(游标)。

package dataStructure.StaticLinkList;

public class Node<T>{
    private T data;//数据域
    private int cur;//指针域
    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public int getCur() {
        return cur;
    }
    public void setCur(int cur) {
        this.cur = cur;
    }
}

一般数组的第一个元素和最后一个元素会被作为特殊元素处理,不存数据。
通常把未被使用的数据元素成为备用链表。

  • 数组的第一个元素的cur用来存放备用链表的第一个结点的下标。(即第一个没有数据的下标)
  • 数组的最后一个元素的cur用来存放第一个有数值的元素的下标,相当于单链表中的头结点作用。

package dataStructure.StaticLinkList;

@SuppressWarnings("unchecked")
public class StaticLinkList<T> {
    public static int MAXSIZE = 20;
    private Node<T>[] list;
    private int length;

    public StaticLinkList(){
        this.list = new Node[MAXSIZE];
    }
    // 初始化链表
    public void initList() {
        for (int i = 0; i < MAXSIZE; i++) {
            Node<T> n = new Node<T>();
            n.setCur(i+1);
            list[i] = n;
        }

        // 目前静态链表为空,因此最后一个元素的cur为0
        list[MAXSIZE-1].setCur(0);
    }

    // 在第i个元素位置插入e
    public boolean ListInsert(int i, T e) {
        //创建链表
        if((length == 0 && i ==1)|| i == length+1){
            list[i].setData(e);
            list[MAXSIZE-1].setCur(1);
            length++;
            return true;
        }
        if (i < 1 || i > length) {
            return false;
        }
        // 首先取得备用链表第一个结点的下标:
        int cur = list[0].getCur();
        // 同时改变第一个元素的cur,因为刚取出来的cur要被使用了,不再是备用链表的第一个结点了
        list[0].setCur(list[cur].getCur());

        list[cur].setData(e);

        int k = MAXSIZE-1;
        // 此时取出来的k为第i-1个元素的下标
        for (int j = 1; j <= i - 1; j++) {
            k = list[k].getCur();
        }
        // 第i个元素的下标
        int insert = list[k].getCur();
        list[k].setCur(cur);
        list[cur].setCur(insert);
        length++;
        return true;
    }

    // 删除第i个元素
    public T ListDelete(int i) {
        if (i < 1 || i > length) {
            return null;
        }
        int k = MAXSIZE-1;
        // 此时取出来的k为第i-1个元素的下标
        for (int j = 0; j < i - 1; j++) {
            k = list[k].getCur();
        }
        //第i个元素下标:
        int del = list[k].getCur();
        T e = list[del].getData();
        list[k].setCur(list[del].getCur());
        //更改第一个元素的cur与要删除元素的cur,因为要删除的元素变成了备用链表的第一个元素
        list[del].setCur(list[0].getCur());
        list[0].setCur(del);
        length--;
        return e;

    }

    //展示数据
    public void display(){
        int k = list[MAXSIZE-1].getCur();
        for(int i=1;i<=length;i++){
            T e = list[k].getData();
            k = list[k].getCur();
            System.out.print(e + " ");
        }
        System.out.println("链表的长度为 :" + getLength());
    }
    public int getLength() {
        return length;
    }

    public void setLength(int length) {
        this.length = length;
    }

    public Node<T>[] getList() {
        return list;
    }

    public void setList(Node<T>[] list) {
        this.list = list;
    }

}

测试代码:

package dataStructure.StaticLinkList;

import java.util.Random;

public class StaticLinkListTest {
    StaticLinkList<Integer> sllist = new StaticLinkList<Integer>();

    // 用随机数初始化一个长度为n的静态链表
    public void init(int n) {
        sllist.initList();
        for (int i = 1; i <= n; i++) {
            sllist.ListInsert(i, (int) (Math.random() * 25));
        }
        display(sllist);
    }

    // 测试删除方法
    public void deleteElem() {
        int i = (int) (Math.random() * sllist.getLength());
        System.out.println("\n\n删除的位置是:" + i);
        Integer deleteNumber = sllist.ListDelete(i);

        if (deleteNumber == null) {
            System.exit(0);
        } else {
            System.out.println("删除的元素是 : " + deleteNumber);
            System.out.println("删除元素后链表是 :");
            display(sllist);
        }
    }

    // 测试随机插入方法
    public void insertByRandom() {
        int i = (int) (Math.random() * sllist.getLength());
        System.out.println("\n\n随机插入位置是 :" + i);
        int elem = (int) (Math.random() * 20);
        System.out.println("随机插入数据是 :" + elem);
        sllist.ListInsert(i, elem);
        System.out.println("随机插入数据后链表是 :");
        display(sllist);
    }

    // 展示list
    public void display(StaticLinkList<Integer> sslist) {
        sslist.display();
    }

    public static void main(String[] args) {
        StaticLinkListTest s = new StaticLinkListTest();
        s.init(8);
        s.deleteElem();
        s.insertByRandom();
    }

}
  • 静态链表优点:
    在插入和删除时,只需改变游标而无需移动元素。
  • 静态链表缺点:
    没有解决连续存储分配内存空间难以确定的问题;
    失去了顺序存储结构随机存取的特性。

循环链表

将单链表中的终端节点的指针由空指针改为指向头结点,就使得整个单链表形成一个环,这种头尾相接的单链表为循环链表。

循环链表解决了从任何一个结点出发从而遍历到所有结点的问题。

循环链表与单链表的主要差异:循环的判断条件,单链表是判断p.next是否为空,循环列表则判断p.next是否为头结点。

在单链表中,在访问尾结点时需要O(n)的时间。但如果在循环链表中不使用头指针,而是使用尾指针rear,则访问第一个结点和最后一个结点都是O(1)。

双向链表

在单链表的每个结点中,都有一个前驱指针指向其前驱结点。所以双向链表中的结点都有两个指针域,一个指向后继,一个指向前驱。

双向链表使得之前查前驱结点的时间复杂度由O(n)变为O(1)。

但双向链表在插入和删除时都需更改两个指针。

发表评论

电子邮件地址不会被公开。 必填项已用*标注