数据结构-线性表（二）单链表

数据结构

线性表（二）单链表

思维导图

2.1 线性表的链式表示

链式存储线性表时，不需要使用地址连续的存储单元，结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。

2.2 单链表

1、定义

线性表的链式存储又称单链表，链表通过指针将一组零散的内存块串联在一起，内存块称为链表的“结点”。每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址，叫作后继指针 next。链表有两个特殊的结点，分别是第一个结点（头结点）和最后一个结点（尾结点）。头结点用来记录链表的基地址，用它可以遍历得到整条链表。尾结点指向一个空地址 NULL，表示这是链表上最后一个结点。

1. 链表是以节点的方式来存储,是链式存储。
2. 每个节点包含 data 域， next 域：指向下一个节点。
3. 链表的各个节点不一定是连续存储。
4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。

头指针是指向链表中第一个结点的指针。

头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息。

首元结点是指链表中存储第一个数据元素a1的结点。

2、优缺点

优点： 不要求大片连续空间，改变容量方便
缺点： 不可随机存取，要耗费一定空间存放指针

3、结构图

（1）内存结构图

（2）逻辑结构图

4、基本操作

（1）建立单链表

头插法建立单链表

该方法从一个空表开始，生成新节点，将新结点插入到当前链表的表头，即头结点之后。

平均时间复杂度：O(n)

头插法的重要应用：链表的逆置 （reverse LinkedList）

尾插法建立单链表

该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针，使其始终指向当前链表的尾结点。

（2）插入单链表

按位序插入

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。

平均时间复杂度：O(n)

对某一结点进行前插操作

时间复杂度：O(1)

对某一结点进行后插操作

时间复杂度：O(1)

（3）删除单链表

按位序删除

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

平均时间复杂度：O(n)

指定结点的删除

时间复杂度：O(1)

（4）查找单链表

按位查找

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

平均时间复杂度：O(n)

按值查找

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

平均时间复杂度：O(n)

（5）表长

遍历链表计算

时间复杂度：O(n)

（6）代码

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;

//定义一个链表
//强调这是一个单链表  ——使用 LinkList
//强调这是一个结点    ——使用 LNode *
typedef struct LNode //定义单链表结点类型
{
    /* data */
    int data;  //数据域
    struct LNode *next;  //指针域
} LNode, *LinkList;      //LNode *p == LinkList p
//指针变量p：表示结点地址
//结点变量 *p：表示一个结点

/**
 * 初始化
 */ 
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));
    if (L == NULL)  //内存不足，分配失败
        return false;
    L->next = NULL;    //头结点之后暂时还没有结点
    //L = NULL; //空表
    return true;
}

/**
 * 判断链表是否为空
 */ 
bool isEmpty(LinkList L) {
    if (L->next == NULL)
        return true;
    else
        return false;
}

/**
 * 头插法
 */ 
LinkList List_HeadInsert(LinkList &L) {
    LNode *s;  //新结点
    for (int i = 1; i <= 10; i++)
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = i; //数据
        s->next = L->next;
        L->next = s; //将新结点插入表中，L为头指针
        /* code */
    }
    return L;
}

/**
 * 尾插法
 */
LinkList List_TailInsert(LinkList &L)
{
    LNode *s; //新结点
    LNode *r = L; //尾指针
    for (int i = 1; i <= 10; i++)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = i; //数据
        r->next = s;
        r = s; //r指向新的表位
        /* code */
    }
    r->next = NULL; //尾结点指针置空
    return L;
}


/**
 * 输出链表
 */ 
void printList(LinkList L) {
    LNode *temp = L->next;
    while (temp != NULL)
    {
        /* code */
        cout << temp->data << endl;
        temp = temp->next;
    }
    
}

/**
 * 按位序插入
 */ 
bool LinkedListInsert(LinkList &L, int i, int e) {
    if(i < 1)
        return false;
    LNode *p = L;
    int j = 0;
    while(p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }    
    if(p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    cout << "在第 " << i << " 位" << "插入数值为：" << e << endl;
    cout << "插入成功！" << endl;
    return true;    
}

/**
 * 对某一结点进行后插操作
 */ 
bool InsertNextNode(LNode *p, int e) {
    if(p == NULL) 
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL)
        return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    cout << "插入成功！" << endl;
    return true;    
}

/**
 * 对某一结点进行前插操作
 */
bool InsertPreNode(LNode *p, int e)
{
    if (p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s == NULL)
        return false;
    s->next = p->next;
    p->next = s;    
    s->data = p->data;
    p->data = e;
    cout << "插入成功！" << endl;
    return true;
}

/**
 * 按位删除
 */ 
bool ListDelete(LinkList &L, int i) {
    if(i < 1)
        return false;
    LNode *p = L;
    int j = 0;
    while(p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }    
    if(p == NULL || p->next == NULL)
        return false;
    LNode *q = p->next;
    int e = q->data;
    p->next = q->next;
    free(q);  //释放
    cout << "删除第 " << i << " 位" <<"数值为：" << e << endl;
    cout << "删除成功！" << endl;
    return true;
}

/**
 * 删除指定元素
 */
bool DeleteByNode(LNode *p)
{
    if (p == NULL)
        return false;
    LNode *q = p->next;
    p->data = p->next->data;
    p->next = q->next;
    free(q); //释放
    cout << "删除成功！" << endl;
    return true;
}

/**
 * 按位查找
 */ 
int LinkedListSearchBySite(LinkList L, int i) {
    cout << "查找第 " << i << " 位的值为：";
    int j = 1;
    LNode *p = L->next; //获得头结点
    if(i < 0)
        return 0;
    while (p != NULL && j < i)
    {
        /* code */
        p = p->next;
        j++;
    }
    return p->data;    

}

/**
 * 按值查找
 */ 
int LinkedListSearchByValue(LinkList L, int e) {
    cout << "查找值为 " << e << " 的位置为：";
    LNode *p = L->next; //获得头结点
    int i = 1;
    while (p != NULL && p ->data != e)
    {
        /* code */
        p = p->next;
        i++;
    }
    return i;    

}

/**
 * 求表长
 */
void GetLength(LinkList L) {
    LNode *p = L;
    int len = 0;
    while (p->next != NULL)
    {
        /* code */
        p = p->next;
        len++;
    }
    cout << "表长为 " << len << endl;
}


int main()
{
    LinkList L; //声明一个指向单链表的指针
    //初始化一个空表
    InitList(L);
    // L = List_HeadInsert(L);
    L = List_TailInsert(L);
    // L = List_TailInsert2(L);
    printList(L);
    GetLength(L);
    //插入元素
    LinkedListInsert(L, 4, 520);
    LinkedListInsert(L, 6, 1314);
    printList(L);
    //删除元素
    ListDelete(L, 2);
    printList(L);
    //查找
    cout << LinkedListSearchBySite(L, 4) << endl;
    cout << LinkedListSearchByValue(L, 8) << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
表长为 10
在第 4 位插入数值为：520
插入成功！
在第 6 位插入数值为：1314
插入成功！
1
2
3
520
4
1314
5
6
7
8
9
10
删除第 2 位数值为：2
删除成功！
1
3
520
4
1314
5
6
7
8
9
10
查找第 4 位的值为：4
查找值为 8 的位置为：9