一、单链表的定义

1. 什么是单链表

每个结点除了存放数据元素外，还要存储指向下一个节点的指针。

1. 优点：不要求大片连续空间，改变容量方便
2. 缺点：不可随机存取，要耗费一定空间存放指针

2. 用代码定义一个单链表

 typedef struct LNode{				// 定义单链表结点类型（结点）
    ElemType data;					// 每个结点存放一个数据元素（数据域）
    struct LNode *next;				// 指针指向下一个结点（指针域）
}LNode, *LinkList;					// LinkList是指向结构体首地址的指针

使用LinkList：强调这是一个单链表；

使用LNode *：强调这是一个结点；

3. 单链表初始化

a. 不带头节点的单链表

bool InitList(LinkList &L){
    L = NULL;					// 空表，暂时还没有任何结点
    return true;
}

b. 带头节点的单链表

bool InitList(LinkLIst &L){
    L = (LNode *) malloc (sizeof(LNode));		// 分配一个头节点
    if(L == NULL)								// 内存不足，分配失败
        return false;
    L -> next = NULL;							// 头节点之后暂时还没有结点
    return true;
}

二、单链表的插入删除

1. ListInsert(&L, i, e)

插入操作。在表L中的第i个位置上插入制定元素e。

a.按位序插入（带头结点）

bool ListInsert(LinkList &L, int i, ElemType e){
    if(i < 1)
        return false;				// 位置不合法
    LNode *p;						// 指针p指向当前扫描到的结点（导航）
    int j = 0;						// 当前p指向的是第几个结点
    p = L;							// 让p指向头节点，即第0个结点
    while(p != NULL && j < i-1){	// 循环找到第i-1个结点
        p = p -> next;
        j++;
    }
    if(p == NULL)					// i值不合法
        return false;
    LNode *s = (LNode *) malloc (sizeof(LNode));	// 为新结点分配内存空间
    s -> data = e;					// 为新结点的数据域复制
    s -> next = p -> next;			// 新结点的后继结点指向导航结点的后继结点
    /* 此时导航结点指向的是第i-1个结点，导航结点的后继结点指向原第i个结点，s插入后成为新的第i个结点 */
    p -> next = s;					// 第i-1个结点的next指向新的第i个结点
    return true;
}

b.按位序插入（不带头节点）

bool ListInsert(LinkList &L, int i, ElemType e){
    if(i < 1)
        return false;				// 位置不合法
    if(i == 1){
        LNode *s = (LNode *) malloc (sizeof(LNode));
        s -> data = e;
        s -> next = L;
        L = s;
        return true;
    }
    LNode *p;						// 指针p指向当前扫描到的结点（导航）
    int j = 1;						// 当前p指向的是第几个结点
    p = L;							// 让p指向头节点，即第0个结点
    while(p != NULL && j < i-1){	// 循环找到第i-1个结点
        p = p -> next;
        j++;
    }
    if(p == NULL)					// i值不合法
        return false;
    LNode *s = (LNode *) malloc (sizeof(LNode));	// 为新结点分配内存空间
    s -> data = e;					// 为新结点的数据域复制
    s -> next = p -> next;			// 新结点的后继结点指向导航结点的后继结点
    /* 此时导航结点指向的是第i-1个结点，导航结点的后继结点指向原第i个结点，s插入后成为新的第i个结点 */
    p -> next = s;					// 第i-1个结点的next指向新的第i个结点
    return true;
}

c.指定结点的后插操作

bool InsertNextNode(LNode *p, ElemType e){
    if(p == NULL)
        return false;
    LNode *s = (LNode *) malloc (sizeof(LNode));
    if(s == NULL)			// 内存分配失败
        return false;
    s -> data = e;
    s -> next = p -> next;
    p -> next = s;
    return true;
}

d.指定结点的前插操作

bool InsertPriorNode(LNode *p, ElemType e){
    if(p == NULL)
        return false;
    LNode *s = (LNode *) malloc (sizeof(LNode));
    if(s == NULL)
        return false;
    s -> next = p -> next;
    p -> next = s;					// 将新结点s连接到p之后
    s -> data = p -> data;			// 将p中元素复制到s中
    p -> data = e;					// p中元素覆盖为e
    return true;
}

2. ListDelete(&L, i, &e)

删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

bool ListDelete(LinkList &L, int i, ElemType e){
    if(i < 1)
        return false;				// 位置不合法
    LNode *p;						// 指针p指向当前扫描到的结点（导航）
    int j = 0;						// 当前p指向的是第几个结点
    p = L;							// 让p指向头节点，即第0个结点
    while(p != NULL && j < i-1){	// 循环找到第i-1个结点
        p = p -> next;
        j++;
    }
    if(p == NULL)					// i值不合法
        return false;
    if(p -> next == NULL)			// 第i-1个结点之后已无其它结点
        return false;
    LNode *q = p -> next;			// 令q指向被删除的结点
    e = q -> data;					// 用e返回元素的值
    p -> next = q -> next;			// 将*q结点从链中断开
    free(q);						// 释放结点的存储空间
    return true;
}

给定结点的删除

bool DeleteNode(LNode *p){
    if(p == NULL)
        return false;
    LNode *q = p -> next;
    p -> data = p -> next -> data;
    p -> next = q -> next;
    free(q);
    return true;
}

三、单链表的查找

1. 按位查找

LNode * GetElem(LinkList L, int i){
    if(i < 0)
        return NULL;
    LNode *p;					// 指针p指向当前扫描到的结点
    int j = 0;					// 当前p指向的是第几个结点
    p = L;						// L指向头节点，头节点是第0个结点
    while(p != NULL && j < i){
        p = p -> next;
        j++;
    }
    return p;
}

2. 按值查找

LNode * LocateElem(LinkList L, ElemType e){
    LNode *p = L -> next;
    while(p != NULL && p -> data != e)
        p = p -> next;
    return p;
}

3. 求表的长度

int Length(LinkList L){
    int len = 0;
    LNode *p = L;
    while(p -> next != NULL){
        p = p -> next;
        len++;
    }
    return len;
}

四、单链表的建立

1. 尾插法建立单链表

LinkList List_tailInsert(LinkLIst &L){
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r = L;						// r为表尾指针
    scanf("%d", &x);
    while(x != 9999){
        s = (LNode *) malloc (sizeof(LNode));
        s -> data = x;
        r -> next = s;
        r = s;
        scanf("%d", &x);
    }
    r -> next = NULL;						// 尾结点指针置空
    return L;
}

2. 头插法建立单链表

LinkList List_HeadInsert(LinkLIst &L){
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L -> next = NULL;
    scanf("%d", &x);
    while(x != 9999){
        s = (LNode *) malloc (sizeof(LNode));
        s -> data = x;
        s -> next = L -> next;
        L -> next = s;							// 将新结点插入表中，L为头指针
        scanf("%d", &x);
    }
    return L;
}