【数据结构与算法】(二) c 语言链表的简单操作

//

//  main.c

//  testLink

//

//  Created by lan on 16/3/6.

//  Copyright © 2016年 lan. All rights reserved.

//

#include <stdio.h>

#include <malloc/malloc.h>

#include <stdlib.h>

#include <stdbool.h>

typedef struct Node {

    int date;            // 数据域

    struct Node * pNext; // 指针域

}NODE, * PNODE;

PNODE create_list(void);       // 创建一个链表

void traverse_link(PNODE);     // 遍历链表

bool is_empty(PNODE pHead);

int length_list(PNODE);

bool insert_list(PNODE, int, int);

bool delete_list(PNODE, int, int *);

void sort_list(PNODE);

int main(int argc, const char * argv[])

{

    int val;  // 存放删除节点的值

    PNODE pHead = NULL;

    pHead = create_list();

    printf("创建好的链表: ");

    traverse_link(pHead);

    bool isEmpty = is_empty(pHead);

    printf("链表是否为空 = %d\n", isEmpty);

    int length = length_list(pHead);

    printf("链表的节点数 = %d\n", length);

    insert_list(pHead, 3, 99);

    printf("在第 3 个节点插入 99: ");

    traverse_link(pHead);

    delete_list(pHead, 4, &val);

    printf("删除第 4 个节点: ");

    traverse_link(pHead);

    printf("删除了 = %d\n", val);

    sort_list(pHead);

    printf("降序: ");

    traverse_link(pHead);

    return 0;

}

PNODE create_list()

{

    int len;    // 节点个数

    int value;  // 暂时存放节点的值

    PNODE pHead = (PNODE)malloc(sizeof(NODE));

    if (NULL == pHead)

    {

        printf("分配失败。程序终止!\n");

        exit(-1);

    }

    PNODE pTail = pHead;

    pTail->pNext = NULL;

    printf("请输入创建链表节点的个数: ");

    scanf("%d", &len);

    for (int i = 0; i < len; i++)

    {

        printf("请输入第%d个节点值: ", i+1);

        scanf("%d", &value);

        PNODE pNew = (PNODE)malloc(sizeof(NODE));

        if (NULL == pNew)

        {

            printf("分配失败，程序终止!\n");

            exit(-1);

        }

        pNew->date = value;

        pTail->pNext = pNew;

        pNew->pNext = NULL;

        pTail = pNew;

    }

    return pHead;

}

void traverse_link(PNODE pHead)

{

    PNODE p = pHead->pNext;

    while (NULL != p)

    {

        printf("%d ", p->date);

        p = p->pNext;

    }

    printf("\n");

}

bool is_empty(PNODE pHead) {

    if (NULL == pHead->pNext) {

        return true;

    } else {

        return false;

    }

}

int length_list(PNODE pHead) {

    int len = 0;

    PNODE p = pHead->pNext;

    while (NULL != p) {

        len++;

        p = p->pNext;

    }

    return len;

}

bool insert_list(PNODE pHead, int pos, int value) {

//    if (pos > length_list(pHead) || pos <= 0) {

//        return false;

//    }

//    PNODE pNew = (PNODE)malloc(sizeof(NODE));

//    if (NULL == pNew) {

//        printf("分配失败。程序终止!\n");

//        exit(-1);

//    }

//    pNew->date = value;

//

//    PNODE p = pHead->pNext;

//    for (int i = 1; i < pos - 1; i++) {

//        p = p->pNext;

//    }

//

//    PNODE q = p->pNext;

//    p->pNext = pNew;

//    pNew->pNext = q;

//    return true;

    // 一种更高效的实现方式

    PNODE p = pHead;

    int i = 0;

    while (p != NULL && i < pos - 1) {

        p = p->pNext;

        i++;

    }

    if (p == NULL || i > pos - 1) {

        return false;

    }

    PNODE pNew = (PNODE)malloc(sizeof(NODE));

    if (NULL == pNew) {

        printf("分配失败，程序终止!\n");

        exit(-1);

    }

    pNew->date = value;

    PNODE q = p->pNext;

    p->pNext = pNew;

    pNew->pNext = q;

    return true;

}

bool delete_list(PNODE pHead, int pos, int * pValue) {

//    if (pos > length_list(pHead) || pos <= 0) {

//        return false;

//    }

//    PNODE p = pHead->pNext;

//    for (int i = 1; i < pos - 1; i++) {

//        p = p->pNext;

//    }

//

//    PNODE q = p->pNext;

//    *pValue = q->date;

//    p->pNext = p->pNext->pNext;

//    free(q);

//    q = NULL;

//    return true;

    // 一种更高效的实现方式

    PNODE p = pHead;

    int i = 0;

    while (NULL != p->pNext && i < pos - 1) {

        p = p->pNext;

        i++;

    }

    if (NULL == p->pNext || i > pos - 1) {

        return false;

    }

    PNODE q = p->pNext;

    *pValue = q->date;

    p->pNext = p->pNext->pNext;

    free(q);   // 记得释放 q 所指向的结构体

    q = NULL;  // 并把 q 指针指向 NULL

    return true;

}

void sort_list(PNODE pHead) {

    int i,j,temp,len;

    PNODE p,q;

//    int a[7] = {2,5,3,1,7,4,9};

//    len = 7;

//    for (i = 0; i < len - 1; i ++) {

//        for (j = i + 1; j < len; j++) {

//            if (a[i] < a[j]) {

//                temp = a[i];

//                a[i] = a[j];

//                a[j] = temp;

//            }

//        }

//    }

//    // 打印输出

//    for (int i = 0; i < 7; i ++) {

//        printf("%d ", a[i]);

//    }

//    printf("\n");

    // 仿照数组的排序来实现链表的排序

    len = length_list(pHead);

    for (i = 0, p = pHead->pNext; i < len - 1; i++,p = p->pNext) {

        for (j = i + 1, q = p->pNext; j < len; j++, q = q->pNext) {

            if (p->date < q->date) {

                temp = p->date;

                p->date = q->date;

                q->date = temp;

            }

        }

    }

}

输出结果：

请输入创建链表节点的个数: 5

请输入第1个节点值: 1

请输入第2个节点值: 2

请输入第3个节点值: 3

请输入第4个节点值: 4

请输入第5个节点值: 5

创建好的链表: 1 2 3 4 5

链表是否为空 = 0

链表的节点数 = 5

在第 3 个节点插入 99: 1 2 99 3 4 5

删除第 4 个节点: 1 2 99 4 5

删除了 = 3

降序: 99 5 4 2 1

Program ended with exit code: 0