数据结构与算法——单链表

1 数组

1.1 数组含义

数组：相同元素构成有序的元素集合。数组中存储的元素类型是一致的，数组也是学习编程时最先接触的数据集合。

1.2 存储方式

数组在内存中采用连续的存储方式，也就是说数据在内存中存放是连续的。例如：

当程序执行如下代码：

int array[10] //在栈上分配一个有10个int元素的数组

printf("array的地址:%p\n",  &array);

for(int i = 0; i < 10; i++){
    printf("buf[%d]的地址:%p\n", i, &array[i]);
}

输出结果：

array的地址   :00000000006ffe20

array[0]的地址:00000000006ffe20

array[1]的地址:00000000006ffe24

array[2]的地址:00000000006ffe28

array[3]的地址:00000000006ffe2c

array[4]的地址:00000000006ffe30

array[5]的地址:00000000006ffe34

array[6]的地址:00000000006ffe38

array[7]的地址:00000000006ffe3c

array[8]的地址:00000000006ffe40

array[9]的地址:00000000006ffe44

int 类型数据占据 4 个字节空间，因此地址差值为 4 。通过输出结果可以看出，数组的存储空间是连续的，并且array 与 array[0] 的地址是相同的。

1.3 存储缺点

由于数组采用连续的存储方式，在开辟数组空间时需要保证内存有足够的连续内存才能保证内存分配。例如：当内存结构如图所示：

当程序需要内存为 1000 个数据大小的内存空间，但是由于内存中最大的连续空间为 600 ，则会导致程序分配内存失败。但是我们发现内存的使用空间为 1500 ，剩余空间仍有 1400 个数据空间，但由于这 1400 个数据空间不连续，导致创建数组失败。

2 指针

2.1 含义

指针：是一个特殊的变量，它里面存储的值为内存里的一个地址。指针的值是指针本身存储的数值，这个值将被编译器当作一个地址，而不是一个一般的数值。例如：在 32 位程序里，所有类型的指针的值都是一个 32 位整数，因为 32 位程序里内存地址全都是 32 位长。

int a = 0;//定义一个整型变量

int *p = &a;//创建指针变量，并将指针指向变量a

printf("a的值 = %d\n", a );//输出变量值

printf("a的地址 = %p\n" , &a);//输出变量地址

printf("p的内容 = %p\n", p);//输出指针变量的内容

printf("通过指针访问数据a = %d\n", *p);

输出结果：

a的值 = 0

a的地址 = 00000000006ffe3c

p的内容 = 00000000006ffe3c

通过指针访问数据a = 0

通过输出可以看出，指针 p 中存储的是是变量 a 的地址。

2.2 指针大小

指针占据的内存大小只要用函数 sizeof(指针的类型) 即可计算出。例如：在 32 位平台里，指针本身占据了 4 个字节的长度，在 64 位平台，指针占据 8 个字节大小。

测试程序：

int a = 1;

double b = 1.4f;

int *p = &a;

double *q = &b;

printf("int类型指针大小 = %d\n", sizeof(p));

printf("double类型指针大小 = %d\n", sizeof(q));

输出结果：

int类型指针大小 = 8

double类型指针大小 = 8

2.3 指针意义

在 1.3 节中介绍了数组存储方式引发的内存分配问题。那么，如何利用指针解决这一问题呢？

首先，指针中存储的是一块内存的地址，并且通过该地址可以获取变量的内容。那么同样的分配大小为N的数组，我们可以通过指针将 N 个元素分别存储到可用内存空间中，在访问数据时可以通过指针去获取后继元素的内容。

存储图示：

通过指针可以将大小为N的数据分别存储至 M1、M2 和 M3 大小空间内。这种方式可以避免连续内存不足引发的内存分配失败问题。

3 数据节点

3.1 含义

数据节点是研究数据结构与算法中最为常用的术语，通常节点指的事最小的数据单元。

3.2 单链表节点

在 2.3 节中，构造的既能存储数据又能存储地址的数据单元称为单链表节点，单链表节点分为两部分：

1 数据域：存储数据

2 指针域：存储后续节点的内存地址，即指向下一个节点。

定义数据结构：

struct Node{
     int value;//数据域，以int为例
     Node * next;//指针域，指向下一个节点
 };

节点图示：

各个节点数据通过指针的方法串联起来，构成链表。由于Node中只有单向的指针next，因此构成的链表为单链表。

单链表图示：

3.3 头结点

头结点不存储实际的数据元素，用于辅助数据元素的定位，方便插入和删除操作，通常头结点标记为head。

带有头节点单链表：

4 单链表

4.1 单链表创建

创建过程：

创建程序：

//创建链表
int create_List(Node **p) {
    int data = 0;
    int ret = 0;
    Node *pHead = NULL; //头结点指针
    Node *node = NULL;
    Node *tmp = NULL;
    pHead = (Node *)malloc(sizeof(Node));//创建一个头结点
    if(pHead == NULL) {
        ret = -1;
    }
    tmp = pHead;
    printf("请输入一个整数数据\n");//等待用户输入整数数据，输入-1结束
    scanf("%d", &data);
    while(data != -1) {
        node = (Node *)malloc(sizeof(Node));//创建新节点
        if(node == NULL) {
            ret = -1;
            printf("List_Create erro\n");
        }
        node->data = data;//为新节点赋值
        tmp->next = node;//将当前节点添加至当前链表末尾
        tmp = node;//将当前指向的节点指针指向新节点
        printf("请输入一个整数数据\n");
        scanf("%d", &data);
    }
    node->next = NULL;
    *p = pHead;
    return ret;
}

4.2 单链表遍历

单链表的遍历十分简单，只需从链表头开始，沿着指针指向顺序依次输出元素即可。

遍历过程：

遍历程序：

void traverse_List(Node* pHead) {
    Node* pCur;//创建用于遍历链表的指针
    if(pHead == NULL || pHead->next == NULL) {
        printf("LinkList is NULL\n");//表为空
    }

    pCur = pHead;//将pCurrent指向头节点
    while(pCur->next) { //当前节点不为最后的节点
        printf("%d ", pCur->next->data);//输出数据值
        pCur = pCur->next;//将当前节点指针后移，指向下一个节点
    }

}

4.3 单链表查找

单链表的数据查找需要遍历整个链表，在遍历过程中，将节点数据与查找数据比较。

查找程序：

//查找数据为value的节点
Node* find_List(Node *pHead, int value){
    Node *pTmp; //遍历链表指针
    if(pHead == NULL || pHead->next == NULL) {
        printf("Node is NULL\n");
        return NULL;
    }

    pTmp = pHead;
    while(pTmp->next) {//遍历链表
        printf("%d ", pTmp->next->data);
        if(pTmp->next->data == value){//判断值是否相等 
            pTmp = pTmp->next;//查找到目标节点 
            return pTmp; //返回目标节点 
        }
        pTmp = pTmp->next;//继续向下查找 
    }
    return NULL;//查找失败 
} 

4.4 单链表插入

插入过程：

插入代码：

//p节点后插入值为i的节点
void insert_Node(Node *p, int i){
    Node* node = new Node;
    node->value = i;
    node->next = p->next;
    p->next = node;
}

4.5 单链表删除

删除过程：

删除代码：

void delete_List(Node * pHead, int data){
   if(pHead == NULL || pHead->next == NULL) {
        printf("Node is NULL\n");
        return NULL;
    }

    while(1){
        int flag=-1;
        Node* pCur;//指向当前节点的指针
        Node* pPre;//指向当前节点的上一个节点指针
        pCur = pHead->next;
        pPre= pHead;
        while(pCur){
            if(pCur->data==data){//元素比较
                //将当前节点的前驱节点的next指向当前节点的后继节点
                pPre->next = pCur->next;
                flag = 1;
                break;
            }

            //继续向后查找
            pCur = pCur->next;
            pPre = pPre->next;

        }

        if(flag==1){
            free(pCur);//释放当前节点占据空间
            printf("节点删除成功\n");
        }else{
            printf("此链表找不到这个值\n");
        }

    }

}

4.6 单链表逆序

单链表逆序是笔试题中出现频率较高的考点。逆序即将当前链表顺序进行反转。

逆序：

逆序过程：

逆序代码：

//单链表逆序
void reverseLinkList(Node* pHead) {
    Node* pPre = NULL;//指向当前节点的上一个节点
    Node* pCur = NULL;//指向当前节点的指针
    Node* pTmp = NULL;
    if(pHead == NULL || pHead->next == NULL || pHead->next->next == NULL) {
        return;
    }

    pPre = pHead->next;
    pCur = pHead->next->next;

    while(pCur) {//遍历整个链表
        //交换顺序，实现逆序
        pTmp = pCur->next;
        pCur->next = pPre;
        pPre = pCur;
        pCur = pTmp;
    }

    pHead->next->next = NULL;
    pHead->next = pPre;

}

5 总结

单链表优缺点：

优点：

1：插入、删除操作不需移动其他元素, 只需改变指针。

2：链表各个节点在内存中空间不要求连续，空间利用率高。

缺点：

1：访问数组元素效率低