【数据结构】郝斌数据结构——笔记03

离散存储【链表】

定义：

1、N个节点离散的分配分布

2、使用指针联系彼此

3、每个节点只有一个前驱节点和一个后驱节点

4、首节点没有前驱节点，尾节点没有后续节点

专业术语：

首节点：第一个有效节点

尾节点：最后一个有效节点

头节点：不存储数据内容，不存储总结点个数，提供对链表的更多操作

头指针：指向头节点的指针变量

尾指针：直接尾节点的指针变量

确定一个链表至少需要头指针参数

其他信息可以根据头指针推算得出

分类：

1单链表

2双链表

3循环链表

4非循环链表

操作：

遍历

清空

查找

销毁

求长度

排序

删除节点

插入节点

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

// 没有boolean类型，使用枚举定义
typedef enum{
    FALSE = 0, //逻辑假
    TRUE = 1 //逻辑真
} boolean;

typedef struct Node {
    int data;
    struct Node * pOfNext;
} NODE,* PNODE;


// 封装成安全检查
void safeCheck(struct Node * pointer) {
    if (pointer == NULL) {
        printf("内存分配失败");
        exit(-1);
    }
}

/**
 * 创建非循环单链表
 * @param length 声明链表长度
 * @return
 */
PNODE createList(int length);
void traverseList(PNODE pointerOfHead);
int length(PNODE pointerOfHead);
PNODE insert(PNODE pointerOfHead, int index, int data);
PNODE delete(PNODE pointerOfHead, int);
void sort(PNODE pointerOfHead);

int main() {

    // 创建头指针
    PNODE head = NULL;

    head = createList(4); // 创建一个非循环单链表，并将该链表的头节点地址返回
    traverseList(head);
    insert(head, 0, 9527);
    insert(head, 0, 9528);
    insert(head, 0, 9529);
    traverseList(head);

    free(delete(head, 0));
    traverseList(head);

    free(delete(head, 3));
    traverseList(head);
    sort(head);
    traverseList(head);

    return 0;
}

/**
 * 链表创建
 * @param length
 * @return
 */
PNODE createList(int length) {
    // 头节点创建
    PNODE pHead = (PNODE) malloc(sizeof (NODE));
    safeCheck(pHead);

    // 声明一个尾节点,类似 temp变量的作用，
    PNODE  pTail = pHead;
    pTail -> pOfNext = NULL;

    for (int i = 0; i < length; ++i) {
        PNODE pNode = (PNODE) malloc(sizeof (NODE));
        safeCheck(pNode);

        // 模拟存储的数据
        int data = rand();
        pNode -> data = data;

        // 节点衔接与重置
        pTail -> pOfNext = pNode;
        pNode -> pOfNext = NULL;
        pTail = pNode;

    }

    return pHead;
}

/**
 * 遍历打印
 * @param pointerOfHead
 */
void traverseList(PNODE pointerOfHead) {
    PNODE iterator = pointerOfHead -> pOfNext;

    printf("[");
    while (NULL != iterator) {
        if (iterator -> pOfNext == NULL) {
            printf("%d]", iterator -> data);
            break;
        }
        printf("%d,", iterator -> data);
        iterator = iterator -> pOfNext;
    }
    printf("
");
}

/**
 * 判断链表是否为空
 * @param pointerOfHead
 * @return
 */
boolean isEmpty(PNODE pointerOfHead) {
//    if (pointerOfHead -> pOfNext == NULL) {
//        return TRUE;
//    }
//    return FALSE;
    return pointerOfHead -> pOfNext == NULL;
}



/**
 * 获取链表长度
 * @param pointerOfHead
 * @return
 */
int length(PNODE pointerOfHead) {
    int counter = 0;
    PNODE iterator = pointerOfHead -> pOfNext;
    while (iterator != NULL) {
        iterator = iterator -> pOfNext;
        ++ counter;
    }
    return counter;
}

/**
 * 根据索引查找元素
 * @param pointerOfHead 头节点
 * @param index 索引位置
 * @return
 */
PNODE findByIndex(PNODE pointerOfHead, int index) {
    PNODE iterator = pointerOfHead -> pOfNext;
    int counter = 0;
    while (iterator != NULL && counter < index) {
        iterator = iterator -> pOfNext;
        ++ counter;
    }
    if (counter == index) return iterator;
    return NULL;
}
/**
 * 根据存储的数据查找
 * @param pointerOfHead 头节点
 * @param data 数据
 * @return
 */
PNODE findByData(PNODE pointerOfHead, int data) {
    PNODE iterator = pointerOfHead -> pOfNext;
    while (iterator != NULL && iterator -> data != data) {
        iterator = iterator -> pOfNext;
    }
    return iterator;
}

/**
 * 对链表进行插入操作
 * @param pointerOfHead 头节点
 * @param index 索引位置
 * @param data 数据
 * @return 插入的节点
 */
PNODE insert(PNODE pointerOfHead, int index, int data) {
    PNODE newNode;
    PNODE tempNode;

    if (index == 0) { /* 表示在首节点的位置上插入 */
       newNode = (PNODE)malloc(sizeof(PNODE));
       newNode -> data = data;

       newNode -> pOfNext = pointerOfHead -> pOfNext;
       pointerOfHead -> pOfNext = newNode;

        // tempNode = pointerOfHead -> pOfNext ;
        // pointerOfHead -> pOfNext = newNode;
        // newNode -> pOfNext = tempNode;
       return newNode;
    }
    tempNode = findByIndex(pointerOfHead, index - 1);
    if (tempNode == NULL) return NULL;
    newNode = (PNODE)malloc(sizeof(PNODE));
    newNode -> data = data;

    newNode -> pOfNext = tempNode -> pOfNext;
    tempNode -> pOfNext = newNode;
    return newNode;
}

PNODE delete(PNODE pointerOfHead, int index){
    PNODE tempNode;
    PNODE tempNode2;
    if (index == 0) {
        if ( pointerOfHead -> pOfNext == NULL) return NULL;

        tempNode = pointerOfHead -> pOfNext;
        pointerOfHead -> pOfNext = tempNode -> pOfNext;

        tempNode -> pOfNext = NULL;
        return tempNode;
    }

    tempNode2 = findByIndex(pointerOfHead, index - 1);
    if (tempNode2 == NULL || tempNode2 -> pOfNext == NULL) return NULL;

    tempNode = tempNode2 -> pOfNext;
    tempNode2 -> pOfNext = tempNode -> pOfNext;

    tempNode -> pOfNext = NULL;
    return tempNode;
}




/**
 * 链表排序
 * @param pointerOfHead
 */
void sort(PNODE pointerOfHead) {
    PNODE t, t1, t2;

    int temp;
    int len = length(pointerOfHead);

    if (isEmpty(pointerOfHead)) return;

    for (int i = 0; i < len - 1; i++) {
        t = pointerOfHead -> pOfNext;
        for (int j = 0; j < len - i - 1; j++) {
            t1 = t;
            t2 = t1 -> pOfNext;

            if (t1 -> data > t2 -> data) {
                temp = t1 -> data;
                t1 -> data = t2 -> data;
                t2 -> data = temp;
            }
            t = t -> pOfNext;
        }
    }

}