【数据结构】线性表之单向链表的八大基操

线性表可以采用顺序存储结构（依赖于数组）和链式存储结构（依赖于指针） 

下面是单向链表有着八大基本操作（简称八大基操）

SLinkNode.cpp:

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

typedef int ElemType;
typedef struct node {
    ElemType data;      //数据域
    struct node *next;  //指针域
} SLinkNode;     //单节点类型声明

// 1.初始化链表
void InitList(SLinkNode *&L) {      //L为引用类型
    L = (SLinkNode *) malloc(sizeof(SLinkNode));    //创建头结点
    L->next = NULL;     //头结点next置为空代表空链表
}

//2.销毁链表运算
void DestroyLInk(SLinkNode *&L) {
    SLinkNode *pre = L, *p = pre->next;     //一个负责释放内存一个负责扫描
    while (p != NULL) {     //当扫描到尾结点时结束扫描
        free(pre);    //释放当前所指空间
        pre = p;            //移向下一个节点
        p = p->next;        //扫描下下一个节点
    }
}

//3.求链表长度
int GetLength(SLinkNode *L) {
    int i = 0;
    SLinkNode *p = L->next;
    while (p != NULL) {
        i++;
        p = p->next;
    }
    return i;
}

//4.求链表中第i个元素的值
int GetElem(SLinkNode *&L, int i, ElemType &e) {        //返回值用来判断是否查找成功,e用来接收查找到的数据
    int j = 0;
    SLinkNode *p = L;
    if (i < 1)return 0;     //如果逻辑序号异常则查找失败
    while (p != NULL && j < i) {    //直到查找到尾结点且实际节点数小于所查找的位置数
        j++;
        p = p->next;        //移动指针查找下一个结点
    }
    if (p == NULL) {  //如果遍历链表都没找到则查找失败
        return 0;
    } else {      //否则一定找到了
        e = p->data;    //将找到的节点数据存起来
        return 1;
    }
}

//5.按值查找
int Locate(SLinkNode *L, ElemType e) {
    SLinkNode *p = L->next;
    int j = 1;  //逻辑序号初值
    while (p != NULL && p->data != e) { //如果没遍历玩链表且没有找到对应结点的数据
        j++;        //逻辑序号加一
        p = p->next;        //移向下一个结点
    }
    if (p == NULL) {  //如果遍历链表都没找到
        return 0;   //则返回查找失败
    } else {  //否则一定找到了
        return j;   //返回对应结点了逻辑序号
    }
}

//6.插入新结点
int InsElem(SLinkNode *&L, ElemType x, int i) {    //接收要插入元素的链表以及插入位置和插入的数据
    int j = 0;
    SLinkNode *p = L, *s;
    if (i < 1) {    //如果插入位置逻辑序号不对则插入失败
        return 0;
    }
    while (p != NULL && j < i - 1) {  //遍历链表直到找到最后一个结点且结点位置在要求的插入位置以内
        j++;    //记录插入位置
        p = p->next;    //移向下一个结点
    }
    if (p == NULL) {    //如果遍历了数组都没找到
        return 0;   //则插入失败
    } else {  //否则一定可以插入
        s = (SLinkNode *) malloc(sizeof(SLinkNode));   //开辟新的结点
        s->data = x;  //给新结点数据域赋值
        s->next = p->next;  //让新结点指针域等于前驱结点的指针域
        p->next = s;    //让插入结点的前驱结点指针域指向新节点
        return 1;
    }
}
//7.删除结点
int DelElem(SLinkNode *&L,int i){
    int j = 0;      //记录当前结点位置
    SLinkNode *p = L,*q;
    if(i<1){    //若删除的位置不对则删除失败
        return 0;
    }
    while(p!=NULL&&j<i-1){  //遍历链表且链表真实长度小于要删除的结点的前一个位置
        j++;    //记录已经查找的节点个数
        p = p->next;    //移向下一个结点
    }
    if(p == NULL){  //如果遍历链表都没找到则删除失败
        return 0;
    }else{  //否则一定找到该节点的前一个结点
        q = p->next;    //记录被删除结点的指针域
        if(q==NULL){    //如果指针域为空则被删除结点不存在
            return 0;   //删除失败
        }else{  //否则一定存在被删除结点
             p ->next = q->next;    //把被删除结点的上一个节点的之指针域赋值为被删除结点的指针域
            free(q);    //释放被删除结点的内存空间
            return 1;   //删除成功
        }
    }
}
//8.输出链表元素
void DispList(SLinkNode *L){
    SLinkNode *p = L->next;
    while(p!=NULL){
        printf("%d ",p->data);
        p = p->next;
    }
}

main.cpp: 

#include <stdio.h>
#include "SLinkNode.cpp"    //包括前面的单链表基本运算函数

int main() {
    int i;
    ElemType e;
    SLinkNode *L;
    InitList(L);
    InsElem(L, 1, 1);
    InsElem(L, 3, 2);
    InsElem(L, 1, 3);
    InsElem(L, 5, 4);
    InsElem(L, 4, 5);
    InsElem(L, 2, 6);
    printf("线性表：");
    DispList(L);
    printf("\n长度：%d\n", GetLength(L));
    i = 3;
    GetElem(L, i, e);
    printf("第%d个元素：%d\n", i, e);
    e = 1;
    printf("元素%d是第%d个元素\n", e, Locate(L, e));
    i = 4;
    printf("删除第%d个元素\n",i);
    DelElem(L,i);
    printf("线性表：");
    DispList(L);
}

测试：