单链表的基本算法

链表与顺序表的逻辑结构一致, 除了首尾节点/元素, 有一个直接前驱和后继, 两者物理结构不同, 链表由一个节点来存储后继节点的地址. 我相信面向对象语言中根据一个对象访问其成员和父类等用的是同样的存储模式.

• 类型定义

typedef struct Node {
    struct Node *pNext; // 指向后继节点
    int data; // 数据域
}NODE,*PNODE;

• 创建

PNODE creat_list() {
    PNODE pHead = (PNODE)(malloc(sizeof(NODE))); // 头结点, 指向首节点, 其数据域为空
    if (NULL==pHead) {
        exit(-1);
    }
    int length;
    PNODE pNew;
    PNODE pEnd = (PNODE)(malloc(sizeof(NODE)));
    if (NULL==pEnd) {
        exit(-1);
    }
    pHead->data = 0;
    printf("请输入长度:");
    scanf("%d",&length);
    pEnd = pHead;
 
    for (int i=0; i<length; i++) {
        int val;
        printf("请输入:");
        scanf("%d",&val);
        pNew = (PNODE)(malloc(sizeof(NODE)));
        if (NULL==pNew) {
            exit(-1);
        }
        pNew->data = val;
        pNew->pNext = NULL;
        pEnd->pNext = pNew;
        pEnd = pNew;
    }
    return pHead;
}

• 遍历

void traverse_list(PNODE pHead)
{
    PNODE p = pHead->pNext;
    while (NULL != p) {
        printf("%d\n", p->data);
        p = p->pNext;
    }
    return;
}

• 获取长度

int length_list(PNODE pHead) {
    PNODE p = pHead->pNext;
    int length = 0; // 此处要初始化为0 不然就是1;
    while (NULL!=p) {
        ++length;
        p = p->pNext;
    }
    return length;
}

• 判空

int is_empty(PNODE pHead) {
    if (NULL == pHead->pNext) {
        return 1;
    } else {
        return 0;
    }
}

• 插入

int insert_list(PNODE pHead, int post, int val) {
    PNODE p = pHead;
    int i = 0;
    while (p && i < post-1) { // 这一步是为了找到第post-1个节点, 并p偏移到这个节点
        p = p->pNext;
        ++i;
    }
    // 此时p已经指向了第post-1个节点
    if (NULL==p->pNext || i>post-1) { // 条件1是当post特别大的时候, 条件2是当post<1的时候
        printf("插入位置不合法");
        return -1;
    }
    
    PNODE e = (PNODE)malloc(sizeof(NODE));
    e->data = val;
    e->pNext = p->pNext;
    p->pNext = e;
    return 1;
}

• 冒泡排序

void sort_list(PNODE pHead) {
    int len = length_list(pHead);
    PNODE p;
    int i,j,t;
    for (i = len - 2 ; i >= 0; --i) {
        for (j = 0,p = pHead->pNext; j <= i; j++) {
            // 取出第j个
            if (p->data > p->pNext->data) {
                t = p->data;
                p->data = p->pNext->data;
                p->pNext->data = t;
            }
            p=p->pNext;
        }
    }
    return;
}

顺序表和链表的存储结构决定了各自的优劣.
查找: 顺序表可以直接根据内存地址计算直接取得, 也就是用数组下标;链表则必须根据其已知节点指针一步步偏移取得, 其效率低于顺序表.
存储空间: 顺序表必须预估一个初始内存大小, 在实际操作过程中内存大小可能需要改变,比较麻烦. 链表则不需要考虑.仅此一点就决定了链表的使用会比顺序表会多一些.