单链表

单链表的概念

链式存储结构：用一组任意的存储单元存储线性表的数据元素（可以是连续的，也可以是不连续的）
结点（node）：存储映像

  • 数据域：存储数据元素信息
  • 指针域: 存储直接后继储存位置
    存储的信息叫做指针或域

单链表的定义

1
2
3
4
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,LinkList;//LNode强调是结点，LinkList强调是单链表

单链表的初始化

不带头节点的单链表

1
2
3
4
bool InitList(LinkList &L){
    L=NULL;
    return true;
}

带头节点的单链表

1
2
3
4
5
6
7
8
bool InitList(LinkList &L){
    L=(LNode*)malloc(sizeof(LNode));
    if(L=NULL){
        return false;
    }
    L->next=NULL;
    return true;
}

单链表的插入

不带头节点的单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool ListInsert(LinkList &L,int i,int e){
    if(i<1)return false;
    LNode *p;
    p=L;
    if(i==1){
        LNode *s=(LNode*)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;
        return true;
    }
    int j=0;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

带头节点的单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool ListInsert(LinkList &L,int i,int e){
    if(i<1)return false;
    LNode *p;
    int j=0;
    p=L;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }//找到所插入的地方的前驱节点
    if(p==NULL){
        return false;
    }
    LNode *s=(LNode*)malloc(sizeof(LNode));//为存放插入数据的数据域动态分配空间
    s->data=e;//将插入的数据e放入分配的空间中
    s->next=p->next;//指向后一个结点
    p->next=s;//将前一个结点指向所插入的结点
    return true;
}