每日记录(线性表链式存储结构（链表）)

链表的基本概念
建议每次写的时候都加一个头节点

各结点由两个域组成：
数据域：存储元素数值数据
指针域：存储直接后继结点的存储位置

结点：数据元素的存储映像。 由数据域和指针域两部分组成
链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构
单链表、双链表、循环链表：

结点只有一个指针域的链表，称为单链表或线性链表
有两个指针域的链表，称为双链表
首尾相接的链表称为循环链表
头指针是指向链表中第一个结点的指针

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

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

Q：1.如何表示空表？
有头结点时，当头结点的指针域为空时表示空表
Q：2. 在链表中设置头结点有什么好处

1.便于首元结点的处理 首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;
⒉便于空表和非空表的统一处理

无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻

这种存取元素的方法被称为顺序存取法

优点

数据元素的个数可以自由扩充
插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高
缺点

存储密度小
存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）
前插法

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)
typedef long long ll;
//#define int __int128

typedef struct item
{
    //double coef;
    int expn;
}ElemType;


typedef struct Lnode//将struct Lnode命名为LNode
{
    ElemType data;        //数据域
    struct Lnode *next;   //指针域 是Lnode！
}LNode,*LinkList;//LNode类型的指针LinkList



//单链表的建立（前插法）

void InsertList(LNode *it,int val)//前插法//int index
{
    LNode *tmp;
    tmp=(LNode *)malloc(sizeof (LNode));
    tmp->data.expn=val;
    tmp->next=it->next;
    it->next=tmp;
}

//删除一个节点
void deletenode(LNode *it,int val)
{
    LNode *tmp=it->next,*last=it;
    while(tmp->data.expn!=val&&tmp->next!=NULL){

        tmp=tmp->next;
        last=last->next;
    }
    if(tmp==NULL){//没有数据域为a的结点
        //puts("没有，滚");
        puts("Not found");
    }
    else {
        last->next=tmp->next;
    }
    free(tmp);
}


//单链表的建立（尾插法）

int n,a[10000];


int main()
{
    scanf("%d",&n);
    over(i,1,n)
        scanf("%d",&a[i]);
    LNode *head;
    head=(LNode*)malloc(sizeof (LNode));
    head->next=NULL;
    lver(i,n,1){
        InsertList(head,a[i]);
    }
    deletenode(head,1);
    LNode *p;
    p=head->next;
    while(p!=NULL){
        printf("%d ",p->data.expn);
        p=p->next;
    }
    return 0;
}

还有循环链表：表最后的一个节点的指针指向表头