非循环单链表的创建、遍历、排序等

上周看了3次数据结构的视频，现在看起来，尽然能听的懂🤔，貌似记得大学的时候 数据结构 这门课程，60分压线及格过的呐😭。。。

下面来看看这部分的代码吧，扔图哈，比着自己敲一下，肯定能加深印象，你比伸手党好多了。。。关于这部分代码估计没人讲或者没有视频是看不懂的，那就辛苦下，多看几遍，熟读唐诗3百首，不会作诗也会吟。。。

记得要用 Xcode 中的命令行工具建立工程哈~

链表

呃~~貌似不能全部截图
好吧，下面放代码：

//
//  main.m
//  链表创建和遍历
//
//  Created by 小伴 on 16/7/6.
//  Copyright © 2016年 huangqimeng. All rights reserved.
//

#import <Foundation/Foundation.h>

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

/**
 *  节点的数据类型：包括数据域和指针域
 */
typedef struct Node {
    int data;   //数据域
    struct Node *pNext; //指针域
} NODE, *PNODE;  //NODE 等价于 struct Node ； PNODE 等价于 struct Node *

/**
 *  函数声明
 */
/** 创建 */
PNODE create_list(void);
/** 遍历 */
void traverse_list(PNODE pHead);
/** 判空 */
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[]) {
    @autoreleasepool {

        PNODE pHead = NULL; //等价于struct Node * pHead = NULL;

        pHead = create_list(); //创建一个非循环单链表，并将该链表的头结点的地址赋给 pHead
        traverse_list(pHead); //遍历

        /*
        insert_list(pHead, 3, 45);
        traverse_list(pHead);
         */

        int val;
        if (delete_list(pHead, 3, &val)) {
            printf("删除成功，删除的元素是：%d\n", val);
        } else {
            printf("删除失败，删除的元素不存在！\n");
        }
        traverse_list(pHead);


        int len = length_list(pHead);
        printf("长度len = %d\n", len);

        sort_list(pHead);
        traverse_list(pHead);

        /*
        if (is_empty(pHead)) {
            printf("链表为空\n");
        } else {
            printf("链表不空\n");
        }*/

    }
    return 0;
}

/**
 *  创建非循环单链表
 */
PNODE create_list() {
    int len; //存放有效节点的个数
    int i;
    int val; //临时存放用户输入的节点的值

    //分配一个不存放有效数据的头节点
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (pHead == NULL) {
        printf("分配失败，程序终止\n");
        exit(-1); //程序终止
    }

    PNODE pTail = pHead;
    pTail->pNext = NULL;

    printf("输入需要生成的链表的节点个数：len = ");
    scanf("%d", &len);

    for (i = 0; i < len; i++) {
        printf("输入第 %d 个节点的值：", i + 1);
        scanf("%d", &val);

        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (pNew == NULL) {
            printf("分配失败，程序终止\n");
            exit(-1);
        }
        pNew->data = val;
        pTail->pNext = pNew;
        pNew->pNext = NULL;
        pTail = pNew;
    }

    return pHead;
}

/**
 *  遍历非循环单链表
 */
void traverse_list(PNODE pHead) {
    PNODE p = pHead->pNext;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
}

/**
 *  判空
 */
bool is_empty(PNODE pHead) {
    if (pHead->pNext == NULL) {
        return true;
    } else {
        return false;
    }
}

/**
 *  长度
 */
int length_list(PNODE pHead) {
    PNODE p = pHead->pNext;
    int len = 0;

    while (p!= NULL) {
        len++;
        p=p->pNext;
    }

    return len;
}

/**
 *  排序
 */
void sort_list(PNODE pHead) {
    int i, j, t;
    int len = length_list(pHead);
    PNODE p, q;

    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->data > q->data) {//类似数组中的a[i] > a[j]
                t = p->data; //t = a[i];
                p->data = q->data; //a[i] = a[j];
                q->data = t; //a[j] = t;
            }
        }
    }
}

/**
 *  在pHead所指向链表的第pos个节点的前面插入一个新的节点，该节点的值是val，并且pos的值是从1开始的
 */
///经典的算法
bool insert_list(PNODE pHead, int pos, int val) {
    int i = 0;
    PNODE p = pHead;

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

    //不需要判断链表空、满、算长度
    if (i > pos - 1 || p == NULL) {
        return false;
    } else {
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (pNew == NULL) {
            printf("动态内存分配失败！\n");
            exit(-1);
        } else {
            pNew->data = val;
            PNODE temp = p->pNext;
            p->pNext = pNew;
            pNew->pNext = temp;

            return true;
        }
    }
}

bool delete_list(PNODE pHead, int pos, int *pVal) {
    int i = 0;
    PNODE p = pHead;

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

    if (i > pos - 1 || p->pNext == NULL) {
        return false;
    } else {
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (pNew == NULL) {
            printf("动态内存分配失败！\n");
            exit(-1);
        } else {
            PNODE temp = p->pNext;
            *pVal = temp->data;

            //删除p节点后面的节点
            p->pNext = p->pNext->pNext;
            free(temp);
            temp = NULL;

            return true;
        }
    }
}

自己研究去吧。。。祝你早日看的懂~
链表的插入和删除已经更新了，最强链表的算法拿走不谢，最后插入和删除的算法特别经典，好好看看争取弄懂他。

碎觉😴