《大话数据结构》线性表的链式存储结构

1.线性表链式存储结构定义

在链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。这两部分信息组成数据元素ai的存储映像，称之为节点node,每个节点包括数据域和指针域

每个节点中只包含一个指针域，所以叫单链表。

链表中第一个结点的存储位置叫做头指针;

线性链表的最后一个结点指针为"空" (通常用 NULL或 "^ " 符号表示）;

为了更加方便地对链装进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。

头指针与头节点的异同点：

2.C语言描述单链表

typedef struct node
{
    int data;
    struct node *next
}node;
typedef struct node *list

结点是由存放数据元素的数据域和存放后继结点地址的指针域组成。重要知识的理解也就是下面的一张图

3.单链表的读取

/*初始条件:线性表L存在，1<=i<=ListLength(L)*/
/*操作结果:用 e 返回 L 中第 i 个数据元素的值*/

tyoedef struct node
{
    int data;
    struct node *next;
}node;

int find(node *L,int i ,int e)
{
    //需要定义一个新的node用来遍历,并让它指向链表的第一个节点
    node p;
    p=L->next；
    int j=1;//j用来计数，常规计数方法，很多在线OJ来减少用来代替for的时间复杂度
    while(p && j<i)//如果p存在
    {
        p=p->next;
        j++；
    }
    e=p->data;
    
    if(!p || j>i)
        return 0;
    
    return 1;
    
}

需要说明的是：时间复杂度：O(n)；

下面是很关键的一句提高和总结的话：

4.单链表的插入

关键思想就是：p的后继节点(指针)改成s的后继节点(p的后继指针指向s，写代码的时候从右往左去想)，再把s变成p的后继节点

s->next=p->next;
p->next=s;

 

/*初始条件:线性表L已存在， 1 <= i <= ListLength (L) , * /
/*操作结果:在 L 中第 i 个位置之前插入新的数据元素 e ，L 的长度加 1 * /
typedef struct node
{
    int data;
    struct node *next;
}node;

//写法1，我是沿用上面的查找
int inserrt(node *L,int i,int e)
{
    node p,s;
    p=L->next;
    int j=1;
    while(p && j<i)//这个p的位置在i
    {
        p=p->next;
        j++;
    }
    s=(node)malloc(sizeof(node));//生成一个新的节点
    s->data=e;
    s->next=p->next;
    p->next=s;
    
    if(p! || j>i)
       return 0;
    return 1;
}

5.单链表的删除

核心思想：

实际上，只有一步：

p->next=p->next->next,用q来代替p->next
就是：
q=p->next;
p->next=q->next;

/*初始条件:线性表L已存在， i<=i<=ListLength (L) */
/操作结果:删除 L 的第 i 个数据元素，并用 e 返回其值， L 的长皮减1* /
typedef struct node
{
    int data;
    struct node;
}node;

//方法1，同样还是按照find的思想写的
int delete(int *L,int i, int e)
{
    node p,q;
    p=L->next;
    int j=1;
    while(p && j<i)//这个p的位置在i-1，删除的node在i的位置上
    {
        p=p->next;
        j++;
    }
    //e=p->next->data;也就是e=q->data
    //p->next=p->next->next;
    q=p->next;
    p->next=q->next;
    e=q->data;
    free(q);
    
    if(p! || j>i)
       return 0;
    return 1;
}

6.单链表的整表创建

链表是一种很散的，是一种动态结构，每个链表所占用的大小和位置是不需要预先分配划定的

所以，创建单链表的过程就是一个动态生成链表的过程，是从空表的初始状态起，依次建立各元素节点，并逐个插入链表。

1）方法1：头插法，新节点都在最前面（太不符合常规了吧）

核心思想如下图所示，在创建单链表的循环中，按照我划的红色箭头去理解，就很好理解了

 

/*随机产生n个元素的值 ， 建立带头节点的单链表L (头插法) */

typedef struct node
{
    int data;
    struct node *next;
}node;


void creat(node *L, int n)
{
    //创造一个带头节点的单链表
    *L=(node)malloc(sizeof(node));
    *L->next=NULL;
    
    node p;
    srand(time(0));//初始化随机数种子

    for(int i=0;i<n;i++)
    {    
        p=(node)malloc(sizeof(node));
        p->data=rand()%100+1//随机生成100以内的数字
        p->next=(*L)->next;
        (*L)->next=p；//插入到表头
    }
    
}

2）尾插法

所谓的先来后到。我们把每次新结点都插在终端结点的后面，这种算法称之为尾插法。
 

/*随机产生n个元素的值 ， 建立带头节点的单链表L (尾插法) */
typedef struct node
{
    int data;
    struct node *next;
}node;

void creat(node *L,int n)
{
    //创造一个带头节点的单链表
    *L=(node)malloc(sizeof(node));
    (*L)->next=NULL;

    //r为指向尾部的节点
    node r;
    r=*L;
    //r=(*L)->next;

    node *p;//定义用来生成新节点的
    for(int i=0;i<n;i++)
    {
        p=(node *)malloc(sizeof(node));//生成一个新节点
        p->data=rand()%100+1;
        r->next=p;//尾节点r的下个节点是p
        r=p;//将新节点p定义为表的尾终端节点
    }
    r->next=NULL;//表示当前链表结束
}

重要的点是：

L是指整个单链表，r是指向尾节点的变量，r会随着循环不断地变化节点，L是随着循环增长为一个多节点的链表

需要理解的结构：

7.单链表的整表删除

将单链表的每个节点在内存中一个个释放掉

/*初始条件:顺序表L已存在，操作结果:将 L重置为空表* /
typedef struct node
{
    int data;
    struct node *next;
}node;

void delete(node *L)
{
    node p,q;
    p=L->next;//p指向第一个节点
    while(p)
    {
        //free(p);p=p->next;//不要这样释放内存
        q=p->next;
        free(q);
        p=q;
    }
    L->next=NULL;//头节点的指针为空
}

8.单链表的结构和顺序存储结构对比