线性表的链式存储结构

标签（空格分隔）： DS 线性表 链式存储

1.线性表的单链表存储结构

typedef struct Node
{
    ElemType data;//数据域
    struct Node *next;//指针域
}Node,* pNode;//节点，节点指针
typedef struct Node* LinkList;//头指针指向头节点

2.单链表的读取第i个元素

思路：
1.声明一个指针p指向第一个节点
2.遍历链表，让p不断指向下一个节点直到指向第i个节点
3.若到链表尾都没有指向第i个元素，p=NULL,则说明第i个元素不存在，找不到
4.若找到，返回p的数据

Status GetElem(LinkList L, int i, ElemType *e)
{
    pNode p;//声明指向指针
    p=L->next;//指向第一个节点
    
    int j=1;//j为计数器，统计指向第几个节点
    while(p!=NULL&&j<i)
    {
        p=p->next;
        ++j;
    }
    
    if(!p||j>i)
    return ERROR;//没找着
    
    *e=p->data;//找着了
    return OK;
}

3.单链表在第i个节点后插入

思路：
1.首先要找到第i个节点(参考单链表的读取）
    1.1如果找到了，生成一个空节点s，将要插入的元素e赋值给s->data,然后把节点s插入链表；
    1.2如果没找到，则错误

Status ListInsert(LinkList L, int i, ElemType e)
{
    pNode p;
    p=L->next;
    int j=1;
    while(p!=NULL&&j<i)//寻找第i个节点
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i)
        return ERROR;
    
    pNode s=(pNode)malloc(sizeof(Node));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;

4.单链表删除第i个节点

思路：
1.声明一个节点指针p指向第一个节点，并不断后移，查找第i个节点(p指向第i-1个节点）
    1.1结果1：p->next=NULL,则第i个节点不存在
    1.2结果2：查找成功

Status ListDelete(LinkList L, int i, ElemType *e)
{
    pNode p;//声明指向指针
    p=L;//指向头节点
    
    int j=1;//j为计数器，统计指向第几-1个节点
    while(p->next!=NULL&&j<i)
    {
        p=p->next;
        ++j;
    }
    
    if(!(p->next)||j>i)
    return ERROR;//没找着
    
    *e=p->next->data;//找着了
    q=p->next;//q指向第i个节点
    p->next=q->next;//使原本指向第i个节点的指针指向第i+1个节点
    free(q);//回收第i个节点的空间
    return OK;

5.单链表的整表创建

思路：
1.创建一个空表L并初始化
2.节点指针p依次申请各元素节点空间并初始化
3.将新节点插入表

//头插法
void CreateListHead(LinkList L, int n)
{
    
    L=(LinkList)malloc(sizeof(Node));//L为头指针，指向头节点
    L->next=NULL;//初始化头节点
    
    pNode p;
    srand(time(0));//初始化随机数种子,
    
    for(int i=0;i<n;i++)
    {
    p=(pNode)malloc(sizeof(Node));//p指向一块node型空间
    p->data=rand()%100+1;//初始化p指向的节点
    
    p->next=L->next;
    L->next=p;//头插法
    }
}

//尾插法
void CreateListTail(LinkList L, int n)
{
    L=(LinkList)malloc(sizeof(Node));//L为头指针，指向头节点
    L->next=NULL;//初始化头节点
    
    pNode p,r;//p为新节点指针，r为链表尾指针
    r=L;//空表尾指针指向头节点
    
    for(int i=0;i<n;i++)
    {
        p=(pNode)malloc(sizeof(Node));//p指向一块node型空间
        p->data=rand()%100+1;//初始化p指向的节点
        
        r->next=p;
        r=p;//尾插法
    }
    r->next=NULL;//表示当前链表结束
}

6.单链表的整表删除

思路：
1.声明一个指向待删除节点的指针p，和一个定位指针q；
2.p指向第一个节点，q指向下一个节点；
3.释放p指向节点的空间后，p指向q的节点成为下一个待删除的节点，q再指向p的下一个节点
4.直到p=NULL,即全部删除完
5.使空表的指针指向NULL

Status ClearList(LinkList L)
{
    pNode p,q;
    p=L->next;
    while(p)
    {
        q=p->next;
        free(p);
        p=q;
    }
    L->next=NULL;
    return OK;