MENU

C语言 单链表及基本操作实现

2017 年 12 月 02 日 • 日常作业

《数据结构》实验让写一个单链表。这里是我的代码,供将来自己检索,和大家参考之用。

/* 
    单链表(有头结点)的结构和基本操作
    By Bro.Xu on 02/12/17 under GCC 5.4.0
    提供给各位参考,未经测试,切勿照搬或轻信,包括命名
*/
#include <malloc.h>
#include <stdio.h>

#define ERROR -1
#define OK 1
#define TRUE 1
#define FALSE 0

typedef struct node{
    DataType data;
    struct node* next;
} Linklist, node;
// Linklist 和 node 两类型等价,都是 struct node 类型。习惯上用 Linklist* 创建链表,指向头结点;node* 代表普通结点。


/*
    初始化单链表
    @返回 已申请空间的单链表的指针,失败返回 NULL
    @使用示例
    Linklist *list = initList();
    if(!list) printf("单链表初始化失败,可能内存不足!");
*/
Linklist* initList(){
    Linklist* L = (Linklist *)malloc(sizeof(Linklist));
    if(!L) return NULL;
    L->next = NULL;
    return L;
}

/*
    计算单链表长度
    @参数 head 单链表头结点指针
    @返回 单链表普通结点个数(只有头结点则记为 0),失败返回 ERROR
*/
int getListSize(Linklist *head){
    if(!head) return ERROR;

    int size = 0;
    node *p = head;
    while(p->next){
        ++size;
        p = p->next;
    }
    return size;
}

/*
    根据索引号得到结点指针
    @参数 head 单链表头结点指针
          index 索引号(规定头结点为 0)
    @返回 索引号对应的结点指针,失败返回 NULL
*/
node *getNode(Linklist *head, int index){
    if(!head) return NULL;
    if(index < 0) return NULL;

    if(0 == index) return head;
    int current = 0;
    node *p = head;
    while(p->next){
        ++current;
        p = p->next;
        if(current == index) return p;
    }
    return NULL;
}

/*
    根据 data 定位索引号和前驱结点
    @参数 head 单链表头结点指针
          data 要查找的数据
          pp 相应前驱结点的指针的指针,若不需要回写前驱结点指针,可设为 NULL
    @返回 由查找得到的第一个索引号,失败返回 ERROR
    @使用示例
    node *temp;
    locateDataAndPreNode(list, 250, &temp);
    if(!temp) printf("未查找到 250,不会进行后续删除操作!");
*/
int locateDataAndPreNode(Linklist *head, DataType data, node **pp){
    if(!head) return ERROR;

    int current = 0;
    node *p = head;
    while(p->next){
        ++current;
        if(p->next->data == data){
            if(pp) *pp = p;
            return current;
        }
        p = p->next;
    }
    if(pp) *pp = NULL;
    return ERROR;
}

/*
    根据 data 定位索引号
    @参数 head 单链表头结点指针
          data 要查找的数据
    @返回 由查找得到的第一个索引号,失败返回 ERROR
*/
int locateData(Linklist *head, DataType data){
    return locateDataAndPreNode(head, data, NULL);
}

/*
    向单链表插入数据(按结点)
    @参数 head 单链表头结点指针
          data 要插入的数据
          pp 结点的指针,将向 pp 结点后一个位置插入新结点
    @返回 新插入结点的指针,失败返回 NULL
*/
node *insertDataBehindNode(Linklist *head, DataType data, node *pp){
    if(!head) return NULL;
    if(!pp) return NULL;

    node *pn = (node *)malloc(sizeof(node));
    if(!pn) return NULL;
    pn->data = data;
    pn->next = pp->next;
    pp->next = pn;
    return pn;
}

/*
    向单链表插入数据(按索引号)
    @参数 head 单链表头结点指针
          data 要插入的数据
          index 索引号,将向 index 后一个位置插入新结点
    @返回 新插入结点的指针,失败返回 NULL
*/
node *insertDataBehindIndex(Linklist *head, DataType data, int index){
    return insertDataBehindNode(head, data, getNode(head, index));
}

/*
    向单链表插入数据(到末尾)
    @参数 head 单链表头结点指针
          data 要插入的数据
    @返回 新插入结点的指针,失败返回 NULL
*/
node *insertDataBehind(Linklist *head, DataType data){ //插入到最后
    //return insertDataBehindNode(head, data, getNode(head, getListSize(head))); //效率不高,不用

    if(!head) return NULL;

    node *pp = head;
    while(pp->next){
        pp = pp->next;
    }

    node *pn = (node *)malloc(sizeof(node));
    if(!pn) return NULL;
    pn->data = data;
    pn->next = NULL;
    pp->next = pn;
    return pn;
}

/*
    删除后继结点(按结点)
    @参数 head 单链表头结点指针
          pp 结点指针,将删除它后一个结点
    @返回 成功返回 OK,失败返回 ERROR
*/
int deleteNextNode(Linklist *head, node *pp){
    if(!head) return ERROR;
    if(!pp) return ERROR;

    node *ps = pp->next;
    if(!ps) return ERROR;
    pp->next = ps->next;
    free(ps);
    return OK;
}

/*
    删除后继结点(按索引号)
    @参数 head 单链表头结点指针
          index 索引号,将删除它后一个结点
    @返回 成功返回 OK,失败返回 ERROR
*/
int deleteNextIndexNode(Linklist *head, int index){
    return deleteNextNode(head, getNode(head, index));
}

/*
    删除所有普通结点(使仅有头结点)
    @参数 head 单链表头结点指针
    @返回 成功返回 OK,失败返回 ERROR
*/
int freeAllNode(Linklist *head){
    if(!head) return ERROR;

    node *p = head, *q;
    while(p->next){
        q = p->next;
        if(p != head) free(p);
        p = q;
    }
    head->next = NULL;
    return OK;
}

/*
    数组转换为单链表
    @参数 arr 包含数据的数组
          length 数组长度
    @返回 生成的单链表的指针,失败返回 NULL
*/
Linklist* arrayToList(DataType *arr, int length){
    if(length < 0) return NULL;

    Linklist *L = initList();
    if(!L) return NULL;
    for(int i=0; i<length; ++i){
        if(!insertDataBehind(L, arr[i])){ //尝试插入数据,若失败则:
            freeAllNode(L); //删除刚才生成的所有结点
            free(L); //删除头结点
            return NULL; //已释放整个 L 链表,返回失败信息
        }
    }
    return L;
}

/*
    输出单链表
    @参数 head 单链表头结点指针
          printNode 输出函数的指针,该函数有两个参数,参数1接收结点指针,参数2接收对应索引号
          sep 分隔符字符串
    @返回 成功返回 OK,失败返回 ERROR
    @使用示例
    void myPrint(node *currentNode, int currentIndex){
        printf("[%d]%d", currentNode->data, currentIndex);
    }
        printList(list, myPrint, ", ");
*/
int printList(Linklist *head, void (*printNode)(node*,int), char *sep){
    if(!head) return ERROR;

    int current = 0;
    node *p = head;
    while(p->next){
        ++current;
        p = p->next;
        if(current > 1) printf("%s", sep);
        printNode(p, current);
    }
    return OK;
}