@TOC

1. 数据结构简介

数据结构简介

1.1 抽象数据类型

1.1.1 数据类型

数据类型：是指一组性质相同值的激活以及定义在此激活的一些操作的总称。

在C语言中，按照取值的不同，数据类型可以分为2类：

• 原子类型： 是不可以在分解的基本数据类型，包含整型，浮点型，字符型等。
• 结构类型： 由若干类型组合而成，是可以再分解的，例如，整型数组就是由若干整型数据组成的。

1.1.2 抽象数据类型

抽象：是抽取出事物具有的普遍的本质。它是抽出问题的特征二忽略非本质的细节，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏繁杂的细节，只保留实现目标必需要的信息。

抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作；例如，我们在编写计算机绘图软件系统是，经常会使用到坐标。也就是说，会经常使用x,y来描述纵横坐标。而在3D系统中，Z深度就会出现。既然这3个整型数字是始终出现在一起，那么就可以定义成一个Point的抽象数据类型。它有x,y,z三个整型变量。这样开发者就非常方便操作Point数据变量。

抽象数据类型可以理解成实际开发里经常使用的结构体和类；根据业务需求定义合适的数据类型和动作。

在我们生活中有哪些线性表的例子呢？

例如： 26个字母表；例如学生基本信息表。每个学生为一个数据元素，包含学号，姓名，专业等数据项目。满足数据元素不同，但是在同一个线性表中的元素必定具有相同的特点，即属于同一数据对象，相邻数据元素之间存在这个序列关系，注入此类有（n >= 0 ）个数据特性相同的元素构成的有限序列称为：“线性表”

/*
 数据: 程序的操作对象,用于描述客观事物.
 数据的特点: 1️⃣ 可以输入到计算机 2️⃣ 可以被计算机处理
 
 数据项: 一个数据元素由若干数据项组成
 数据元素: 组成数据的对象的基本单位
 数据对象: 性质相同的数据元素的集合(类似于数组)
 
 结构: 数据元素之间不是独立的,存在特定的关系.这些关系即是结构;
 数据结构:指的数据对象中的数据元素之间的关系
 */
#include <stdio.h>

//声明一个结构体类型
struct Teacher{     //一种数据结构
    char *name;     //数据项--名字
    char *title;    //数据项--职称
    int  age;       //数据项--年龄
};


int main(int argc, const char * argv[]) {
   
    struct Teacher t1;     //数据元素;
    struct Teacher tArray[10]; //数据对象;
    
    t1.age = 18;       //数据项
    t1.name = "CC";    //数据项
    t1.title = "讲师";  //数据项
    
    printf("老师姓名:%s\n",t1.name);
    printf("老师年龄:%d\n",t1.age);
    printf("老师职称:%s\n",t1.title);
    
    return 0;
}

线性表中的元素的个数n定义为线性表的长度，如果n=0则称为空表

对应非空的线性表和线性结构，其特点如下：

• 存在唯一的一个被称作“第一个”的数据元素
• 存在唯一一个被称作“最后一个”的数据元素。
• 除了第一个之外，结构中的每个数据元素都有一个前驱。
• 除了最后一个之外，结构中的每个数据元素都有一个后继。

1.2 数据结构基本术语

1.2.1 数据结构基本术语

数据的构成：基本数据单位

数据的构成

• 数据结构的逻辑结构：按逻辑分为：集合结构，线性结构，树形结构，图形机构等。

集合结构

集合机构

线性结构

线性结构

树形结构

树形结构

图形结构

图形结构

• 数据结构按物体机构分为：顺序存储结构，链式存储结构。

顺序存储结构

顺序存储结构

//顺序表结构
typedef struct KSequenceList {
    KElementType *data;
    int length;
}KSList;

链式存储结构

链式存储结构

1.2.2 数据结构与算法关系

数据结构和算法的关系

算法是什么？

算法就是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每个指令表示一个或者多个操作。

算法有以下特性：

• 输入输出
• 有穷性
• 确定性
• 可行性

算法设计要求：

• 正确性
• 可读性
• 健壮性
• 时间效率高和存储量低

1.2.3 时间复杂度和空间复杂度

1.2.3.1 时间复杂度：

例如下面函数的执行次数：

求解函数执行次数

上表对应的函数执行次数如下：

函数执行次数结构

时间复杂实际就是评估算法执行的次数：

时间复杂度比较

O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

• 时间复杂度计算练习

#include <stdio.h>
/*大O表示法
 1. 用常数1取代运行时间中所有常数 3->1 O(1)
 2. 在修改运行次数函数中,只保留最高阶项 n^3+2n^2+5 -> O(n^3)
 3. 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 -> n^3
 */

/*
 时间复杂度术语:
 1. 常数阶
 2. 线性阶
 3. 平方阶
 4. 对数阶
 5. 立方阶
 6. nlog阶
 7. 指数阶(不考虑) O(2^n)或者O(n!) 除非是非常小的n,否则会造成噩梦般的时间消耗. 这是一种不切实际的算法时间复杂度. 一般不考虑!
 */

/* 1. 常数阶时间复杂度计算 O(1) */
//1+1+1 = 3 O(1)
void testSum1(int n){
    int sum = 0;                //执行1次
    sum = (1+n)*n/2;            //执行1次
    printf("testSum1:%d\n",sum);//执行1次
}

//1+1+1+1+1+1+1 = 7 O(1)
void testSum2(int n){
    int sum = 0;                //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    printf("testSum2:%d\n",sum);//执行1次
    
}
//x=x+1; 执行1次
void add(int x){
    x = x+1;
}


/*2.线性阶时间复杂度*/
//x=x+1; 执行n次 O(n)
void add2(int x,int n){
    for (int i = 0; i < n; i++) {
        x = x+1;
    }
}

//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
    int i,sum = 0;               //执行1次
    for (i = 1; i <= n; i++) {   //执行n+1次
        sum += i;                //执行n次
    }
    printf("testSum3:%d\n",sum);  //执行1次
}

/*3.对数阶*/
/*2的x次方等于n x = log2n  ->O(logn)*/
void testA(int n){
    int count = 1;         //执行1次
    //n = 10
    while (count < n) {
        count = count * 2;
    }
    
}


/*4.平方阶*/
//x=x+1; 执行n*n次 ->O(n^2)
void add3(int x,int n){
    for (int i = 0; i< n; i++) {
        for (int j = 0; j < n ; j++) {
            x=x+1;
        }
    }
}

//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
//sn = n(a1+an)/2
void testSum4(int n){
    int sum = 0;
    for(int i = 0; i < n;i++)
        for (int j = i; j < n; j++) {
            sum += j;
        }
    printf("textSum4:%d",sum);
    
}

//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum5(int n){
    int i,j,x=0,sum = 0;           //执行1次
    for (i = 1; i <= n; i++) {     //执行n+1次
        for (j = 1; j <= n; j++) { //执行n(n+1)
            x++;                   //执行n*n次
            sum = sum + x;         //执行n*n次
        }
    }
    printf("testSum5:%d\n",sum);
}


/*5.立方阶*/
void testB(int n){
    int sum = 1;                         //执行1次
    for (int i = 0; i < n; i++) {        //执行n次
        for (int j = 0 ; j < n; j++) {   //执行n*n次
            for (int k = 0; k < n; k++) {//执行n*n*n次
                sum = sum * 2;          //执行n*n*n次
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    
    testSum1(100);
    testSum2(100);
    testSum3(100);
    
    return 0;
}

1.2.3.2 空间复杂度：

算法的空间复杂度：

算法的空间复杂度通过计算算法所需要的存储空间实现，算法空间复杂度的计算公式记做：S(n) = n(f(n)), 其中n为问题的规模， f(n) 为语句关于n 所占内存空间的函数。

• 空间复杂度练习

/*
 程序空间计算因素:
 1. 寄存本身的指令
 2. 常数
 3. 变量
 4. 输入
 5. 对数据进行操作的辅助空间
 
 在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间.
 空间复杂度计算:

 问题: 数组逆序,将一维数组a中的n个数逆序存放在原数组中.
 */

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
   
    int n = 5;
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    
    //算法实现(1)
    int temp;
    for(int i = 0; i < n/2 ; i++){
        temp = a[I];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
    }

    for(int i = 0;i < 10;i++)
    {
        printf("%d\n",a[I]);

    }
    
    //算法实现(2)
    int b[10] = {0};
    for(int i = 0; i < n;i++){
        b[i] = a[n-i-1];
    }
    for(int i = 0; i < n; i++){
        a[i] = b[I];
    }
    for(int i = 0;i < 10;i++)
    {
        printf("%d\n",a[I]);
        
    }
    
    return 0;
}

1.3 线性表

1.3.1 线性表之顺序表

顺序表操作1
顺序表操作2
顺序表操作3

1.3.1.1 顺序表基本操作实现

顺序表完整实现代码点击这里下载：顺序表基本操作实现

1.3.1.1.1 顺序表结构定义

//顺序表结构
typedef struct KSequenceList {
    KElementType *data;
    int length;
}KSList;

1.3.1.1.2 顺序表初始化

// 1 顺序表初始化
KStatus initSequenceList(KSList *L) {
    
    //为顺序表分配一个大小为MAXSIZE 的数组空间
    L->data = malloc(sizeof(KElementType) * MAXSIZE);
    //存储分配失败直接退出
    if(!L->data) return ERROR;
    //空表长度为0
    L->length = 0;
    
    return OK;
}

1.3.1.1.3 顺序表的插入

// 2 顺序表的插入
// 初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
KStatus insertElement(KSList *L, int i, KElementType e) {
    
    //边界条件判断
    //1.1 出入的索引 i 合法性判断, 不能超过链表总长度
    if((i < 1) || (i > L->length+1)) return ERROR;
    //1.2 存储空间是否已满
    if(L->length == MAXSIZE) return ERROR;
    
    //1.3 插入数据如果不在表尾部，则先往后移动腾出位置给要插入的元素
    if(i <= L->length) {
        for(int j = L->length-1; j >= i-1; j--) {
            //插入位置后面的元素都移动1个位置，让出第i个位置
            L->data[i+1] = L->data[I];
        }
    }
    
    //1.4 将新元素赋值到腾出的位置，完成插入
    L->data[i-1] = e;
    
    //1.5 链表长度增加1
    ++L->length;
    
    return OK;
}

1.3.1.1.4 顺序表的取值

// 3. 顺序表的取值
KStatus getElement(KSList L, int i, KElementType *e) {
    
    //边界条件判断，i不能超过总长度
    if(i < 1 || i > L.length) return ERROR;
    
    //直接取出第i个元素的值，索引下标对应为i-1 (下标默认从0开始)
    *e = L.data[i-1];
    
    return OK;
}

1.3.1.1.5 顺序表删除

// 4. 顺序表删除
//初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
//操作结果: 删除L的第i个数据元素,L的长度减1
KStatus deleteElement(KSList *L, int i) {
    
    //边界条件判断
    //线性表是否为空
    if(L->length == 0) return ERROR;
    //i值合法性判断
    if((i < 1) || (i > L->length+1)) return ERROR;
    
    for (int j = i; j < L->length; j++) {
        //被删除的元素后面的所有元素往前移动一个位置
        L->data[j-1] = L->data[j];
    }
    
    //表长度减1
    L->length--;
    
    return OK;
}

1.3.1.1.6 清空顺序表

// 5. 清空顺序表
//初始条件：顺序线性表L已存在。操作结果：将L重置为空表
KStatus clearList(KSList *L) {
    L->length = 0;
    return OK;
}

1.3.1.1.7 判断顺序表清空

// 6. 判断顺序表清空
//初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
KStatus isListEmpty(KSList L) {
    return L.length == 0 ;
}

1.3.1.1.8 获取顺序表表长度

// 7. 获取顺序表表长度
int getListLength(KSList L) {
    return L.length;
}

1.3.1.1.9 遍历顺序表

// 8. 遍历顺序表
//初始条件：顺序线性表L已存在
//操作结果：依次对L的每个数据元素输出
KStatus traverseList(KSList L) {
    for(int i = 0; i < L.length; i++) {
        printf("%d.\n",L.data[I]);
    }
    printf("\n");
    return OK;
}

1.3.1.1.10 查找顺序表元素下标

// 9. 查找顺序表元素下标
//初始条件：顺序线性表L已存在
//操作结果：返回L中第1个与e满足关系的数据元素的位序。
//若这样的数据元素不存在，则返回值为0
int getElementIndex(KSList L, KElementType e) {
    //边界条件判断
    if (L.length == 0 ) return 0;
    
    //顺序查找
    int i = 0;
    for(i = 0; i < L.length; i++) {
        if (L.data[i] == e) {break;}
    }
    
    if (i >= L.length) return 0;
    
    return I;
}

1.3.1.1.11 单元测试

// 10. 单元测试
void test() {
    KSList L1;
    //KSList L2;
    KElementType e;
    KStatus iStatus;
    
    //1.1 顺序表初始化
    iStatus = initSequenceList(&L1);
    printf("初始化L1后: L.Length = %d\n", L1.length);
    
    //1.2 顺序表数据插入
    for(int j=1; j <= 5;j++){
        iStatus = insertElement(&L1, 1, j);
    }
    printf("插入数据L1长度: %d\n",L1.length);
    
    //1.3 顺序表取值
    getElement(L1, 5, &e);
    printf("顺序表L1第5个元素的值为:%d\n",e);
    
    //1.4 顺序表删除第2个元素
    deleteElement(&L1, 2);
    printf("顺序表L1删除第%d元素,长度为%d\n",2,L1.length);
    
    //1.5 清空顺序表
    iStatus = clearList(&L1);
    printf("清空L1后,L.length = %d\n",L1.length);
    
    //1.6 判断List是否为空
    iStatus = isListEmpty(L1);
    printf("L1是否空：i=%d(1:是 0:否)\n",iStatus);
    
    //1.8 遍历打印顺序表
    for(int j=1; j <= 5;j++){
        iStatus = insertElement(&L1, 1, j);
    }
    traverseList(L1);
}

输出结构为：

Hello, World!
初始化L1后: L.Length = 0
插入数据L1长度: 5
顺序表L1第5个元素的值为:446
顺序表L1删除第2元素,长度为4
清空L1后,L.length = 0
L1是否空：i=1(1:是 0:否)
5.
0.
0.
446.
446.

Program ended with exit code: 0

1.3.1.2 线性顺序表完整操作代码

//
//  main.c
//  001_LinearList
//
//  Created by 孔雨露 on 2020/4/5.
//  Copyright © 2020 Apple. All rights reserved.
//

#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

//KElementType类型根据实际情况而定，这里假设为int
typedef int KElementType;
//KStatus是函数的类型,其值是函数结果状态代码，如OK等
typedef int KStatus;


//顺序表结构
typedef struct KSequenceList {
    KElementType *data;
    int length;
}KSList;

// 1 顺序表初始化
KStatus initSequenceList(KSList *L) {
    
    //为顺序表分配一个大小为MAXSIZE 的数组空间
    L->data = malloc(sizeof(KElementType) * MAXSIZE);
    //存储分配失败直接退出
    if(!L->data) return ERROR;
    //空表长度为0
    L->length = 0;
    
    return OK;
}

// 2 顺序表的插入
// 初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
KStatus insertElement(KSList *L, int i, KElementType e) {
    
    //边界条件判断
    //1.1 出入的索引 i 合法性判断, 不能超过链表总长度
    if((i < 1) || (i > L->length+1)) return ERROR;
    //1.2 存储空间是否已满
    if(L->length == MAXSIZE) return ERROR;
    
    //1.3 插入数据如果不在表尾部，则先往后移动腾出位置给要插入的元素
    if(i <= L->length) {
        for(int j = L->length-1; j >= i-1; j--) {
            //插入位置后面的元素都移动1个位置，让出第i个位置
            L->data[i+1] = L->data[I];
        }
    }
    
    //1.4 将新元素赋值到腾出的位置，完成插入
    L->data[i-1] = e;
    
    //1.5 链表长度增加1
    ++L->length;
    
    return OK;
}


// 3. 顺序表的取值
KStatus getElement(KSList L, int i, KElementType *e) {
    
    //边界条件判断，i不能超过总长度
    if(i < 1 || i > L.length) return ERROR;
    
    //直接取出第i个元素的值，索引下标对应为i-1 (下标默认从0开始)
    *e = L.data[i-1];
    
    return OK;
}

// 4. 顺序表删除
//初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
//操作结果: 删除L的第i个数据元素,L的长度减1
KStatus deleteElement(KSList *L, int i) {
    
    //边界条件判断
    //线性表是否为空
    if(L->length == 0) return ERROR;
    //i值合法性判断
    if((i < 1) || (i > L->length+1)) return ERROR;
    
    for (int j = i; j < L->length; j++) {
        //被删除的元素后面的所有元素往前移动一个位置
        L->data[j-1] = L->data[j];
    }
    
    //表长度减1
    L->length--;
    
    return OK;
}

// 5. 清空顺序表
//初始条件：顺序线性表L已存在。操作结果：将L重置为空表
KStatus clearList(KSList *L) {
    L->length = 0;
    return OK;
}

// 6. 判断顺序表清空
//初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
KStatus isListEmpty(KSList L) {
    return L.length == 0 ;
}

// 7. 获取顺序表表长度
int getListLength(KSList L) {
    return L.length;
}

// 8. 遍历顺序表
//初始条件：顺序线性表L已存在
//操作结果：依次对L的每个数据元素输出
KStatus traverseList(KSList L) {
    for(int i = 0; i < L.length; i++) {
        printf("%d.\n",L.data[I]);
    }
    printf("\n");
    return OK;
}

// 9. 查找顺序表元素下标
//初始条件：顺序线性表L已存在
//操作结果：返回L中第1个与e满足关系的数据元素的位序。
//若这样的数据元素不存在，则返回值为0
int getElementIndex(KSList L, KElementType e) {
    //边界条件判断
    if (L.length == 0 ) return 0;
    
    //顺序查找
    int i = 0;
    for(i = 0; i < L.length; i++) {
        if (L.data[i] == e) {break;}
    }
    
    if (i >= L.length) return 0;
    
    return I;
}

// 10. 单元测试
void test() {
    KSList L1;
    //KSList L2;
    KElementType e;
    KStatus iStatus;
    
    //1.1 顺序表初始化
    iStatus = initSequenceList(&L1);
    printf("初始化L1后: L.Length = %d\n", L1.length);
    
    //1.2 顺序表数据插入
    for(int j=1; j <= 5;j++){
        iStatus = insertElement(&L1, 1, j);
    }
    printf("插入数据L1长度: %d\n",L1.length);
    
    //1.3 顺序表取值
    getElement(L1, 5, &e);
    printf("顺序表L1第5个元素的值为:%d\n",e);
    
    //1.4 顺序表删除第2个元素
    deleteElement(&L1, 2);
    printf("顺序表L1删除第%d元素,长度为%d\n",2,L1.length);
    
    //1.5 清空顺序表
    iStatus = clearList(&L1);
    printf("清空L1后,L.length = %d\n",L1.length);
    
    //1.6 判断List是否为空
    iStatus = isListEmpty(L1);
    printf("L1是否空：i=%d(1:是 0:否)\n",iStatus);
    
    //1.8 遍历打印顺序表
    for(int j=1; j <= 5;j++){
        iStatus = insertElement(&L1, 1, j);
    }
    traverseList(L1);
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    test();
    return 0;
}

1.3.2 线性表之单链表

单链表Demo点击这里下载：单链表操作

• 单链表结点

单链表结点

//定义结点
typedef struct KNodeInfo{
    KElementType data;
    struct KNodeInfo *next;
}Node;

• 单链表逻辑状态

  
  单链表逻辑状态

• 增加头结点的单链表逻辑状态

  
  增加头结点的单链表逻辑状态

• 单链表为什么要增加头结点

  
  单链表为什么要增加头结点

1.3.2.1 单链表初始化

//1. 初始化单链表
KStatus initList(KLinkList *L) {
    
    //生成头结点，并使用L指向此头结点
    *L = (KLinkList)malloc(sizeof(Node));
    //如果分配空间失败，直接退出
    if(*L == NULL) return ERROR;
    //将头结点的指针域置为空
    (*L)->next = NULL;
    
    return OK;
}

1.3.2.2 单链表插入结点

• 单链表插入

  
  单链表插入
  

  实现代码：

//2. 单链表插入
//初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
//操作结果：在L中第i个位置之后插入新的数据元素e，L的长度加1;
KStatus insertElement(KLinkList *L, int i, KElementType e) {
    
    int j = 1;
    KLinkList p, s;
    p = *L;
    
    //寻找第i-1个结点
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    //判断第i个元素是否存在
    if(!p || j > i) return ERROR;
    
    //生成新结点s
    s = (KLinkList)malloc(sizeof(Node));
    //将e赋值给s的数值域
    s->data = e;
    //将p的后继结点赋值给s的后继
    s->next = p->next;
    //将s赋值给p的后继
    p->next = s;
    
    return OK;
}

1.3.2.3 单链表删除结点

• 单链表删除

  
  单链表删除

实现代码：

//4. 单链表删除元素
//初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
KStatus deleteElement(KLinkList *L, int i, KElementType *e) {
    
    int j = 1;
    KLinkList p,q;
    p = (*L)->next;
    
    //查找第i-1个结点，p指向该结点
    while (p->next && j < (i-1)) {
        p = p->next;
        ++j;
    }
    
    //当i>n 或者 i<i 时，删除位置不合理
    if (!(p->next) || (j>i-1)) return ERROR;
    
    //q指向要删除的结点
    q = p->next;
    //将q的后继赋值给p的后继
    p->next = q->next;
    //将q结点中的数据赋值给e
    *e = q->data;
    //释放内存
    free(q);
    
    return OK;
}

1.3.2.4 单链表取值

//3. 单链表取值
//初始条件: 顺序线性表L已存在,1≤i≤ListLength(L);
//操作结果：用e返回L中第i个数据元素的值
KStatus getElement(KLinkList L, int i, KElementType *e) {
    int j = 1;
    //将结点p,指向链表L的第一个结点
    KLinkList p = L->next;
    
    //查找结点,p不为空,且计算j不等于i,则循环继续
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    //如果p为空或者j>i,则 返回error
    if(!p || j > i) return ERROR;
    
    *e = p->data;
    
    return OK;
}

1.3.2.5 单链表建表-头插法

• 单链表前插法

  
  单链表前插法
  

  实现代码：

//7. 创建单链表：头插入法
//随机产生n个元素值,建立带表头结点的单链线性表L(前插法)
void createListByHeadInsert(KLinkList *L, int n) {
    KLinkList p;
    //建立1个带头结点的单链表
    *L = (KLinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    //循环前插入随机数据
    for (int i = 0; i < n; i++) {
        //生成新结点
        p = (KLinkList)malloc(sizeof(Node));
        //i赋值给新结点
        p->data = I;
        
        //将结点p插入到头结点之后
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

1.3.2.6 单链表建表-头插法

• 单链表后插法

  
  单链表后插法
  

  实现代码：

//8. 创建单链表：尾部插入法
//随机产生n个元素值,建立带表头结点的单链线性表L(后插法)
void createListByTailInsert(KLinkList *L, int n) {
    
    KLinkList p, r;
    
    //建立1个带头结点的单链表
    *L = (KLinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    //让r指针指向尾部结点
    r = *L;
    
    //循环创建链表结点，尾部插入
    for (int i = 0; i < n; i++) {
        //生成新结点
        p = (Node *) malloc(sizeof(Node));
        //赋值随机数i
        p->data = I;
        
        //尾部插入新结点
        //将表尾终端结点的指针指向新结点
        r->next = p;
        //将当前的新结点定义为表尾终端结点
        r = p;
    }
    
    //将尾部指针next=NULL
    r->next = NULL;
    
}

1.3.2.7 遍历单链表

//5. 遍历单链表
//初始条件：顺序线性表L已存在
//操作结果：依次对L的每个数据元素输出
KStatus traverseList(KLinkList L) {
    KLinkList p = L->next;
    while (p) {
        printf("%d\n",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

1.3.2.8 清空单链表

//6. 清空单链表
//初始条件：顺序线性表L已存在。操作结果：将L重置为空表
KStatus clearList(KLinkList *L) {
    
    KLinkList p, q;
    //指向第一个结点
    p = (*L)->next;
    while (p) {
        //遍历删除每个结点，并释放内存
        q = p->next;
        free(p);
        p = q;
    }
    //头结点指针域赋值为空
    (*L)->next = NULL;
    
    return OK;
}

1.3.2.9 单链表操作完整代码

//
//  main.c
//  003_LInkedStorage
//
//  Created by 孔雨露 on 2020/4/5.
//  Copyright © 2020 Apple. All rights reserved.
//

#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

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

#define MAXSIZE 20

typedef int KStatus;
typedef int KElementType;

//定义结点
typedef struct KNodeInfo{
    KElementType data;
    struct KNodeInfo *next;
}Node;

typedef struct KNodeInfo *KLinkList;


//1. 初始化单链表
KStatus initList(KLinkList *L) {
    
    //生成头结点，并使用L指向此头结点
    *L = (KLinkList)malloc(sizeof(Node));
    //如果分配空间失败，直接退出
    if(*L == NULL) return ERROR;
    //将头结点的指针域置为空
    (*L)->next = NULL;
    
    return OK;
}

//2. 单链表插入
//初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
//操作结果：在L中第i个位置之后插入新的数据元素e，L的长度加1;
KStatus insertElement(KLinkList *L, int i, KElementType e) {
    
    int j = 1;
    KLinkList p, s;
    p = *L;
    
    //寻找第i-1个结点
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    //判断第i个元素是否存在
    if(!p || j > i) return ERROR;
    
    //生成新结点s
    s = (KLinkList)malloc(sizeof(Node));
    //将e赋值给s的数值域
    s->data = e;
    //将p的后继结点赋值给s的后继
    s->next = p->next;
    //将s赋值给p的后继
    p->next = s;
    
    return OK;
}

//3. 单链表取值
//初始条件: 顺序线性表L已存在,1≤i≤ListLength(L);
//操作结果：用e返回L中第i个数据元素的值
KStatus getElement(KLinkList L, int i, KElementType *e) {
    int j = 1;
    //将结点p,指向链表L的第一个结点
    KLinkList p = L->next;
    
    //查找结点,p不为空,且计算j不等于i,则循环继续
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    //如果p为空或者j>i,则 返回error
    if(!p || j > i) return ERROR;
    
    *e = p->data;
    
    return OK;
}

//4. 单链表删除元素
//初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
KStatus deleteElement(KLinkList *L, int i, KElementType *e) {
    
    int j = 1;
    KLinkList p,q;
    p = (*L)->next;
    
    //查找第i-1个结点，p指向该结点
    while (p->next && j < (i-1)) {
        p = p->next;
        ++j;
    }
    
    //当i>n 或者 i<i 时，删除位置不合理
    if (!(p->next) || (j>i-1)) return ERROR;
    
    //q指向要删除的结点
    q = p->next;
    //将q的后继赋值给p的后继
    p->next = q->next;
    //将q结点中的数据赋值给e
    *e = q->data;
    //释放内存
    free(q);
    
    return OK;
}

//5. 遍历单链表
//初始条件：顺序线性表L已存在
//操作结果：依次对L的每个数据元素输出
KStatus traverseList(KLinkList L) {
    KLinkList p = L->next;
    while (p) {
        printf("%d\n",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

//6. 清空单链表
//初始条件：顺序线性表L已存在。操作结果：将L重置为空表
KStatus clearList(KLinkList *L) {
    
    KLinkList p, q;
    //指向第一个结点
    p = (*L)->next;
    while (p) {
        //遍历删除每个结点，并释放内存
        q = p->next;
        free(p);
        p = q;
    }
    //头结点指针域赋值为空
    (*L)->next = NULL;
    
    return OK;
}

//7. 创建单链表：头插入法
//随机产生n个元素值,建立带表头结点的单链线性表L(前插法)
void createListByHeadInsert(KLinkList *L, int n) {
    KLinkList p;
    //建立1个带头结点的单链表
    *L = (KLinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    //循环前插入随机数据
    for (int i = 0; i < n; i++) {
        //生成新结点
        p = (KLinkList)malloc(sizeof(Node));
        //i赋值给新结点
        p->data = I;
        
        //将结点p插入到头结点之后
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

//8. 创建单链表：尾部插入法
//随机产生n个元素值,建立带表头结点的单链线性表L(后插法)
void createListByTailInsert(KLinkList *L, int n) {
    
    KLinkList p, r;
    
    //建立1个带头结点的单链表
    *L = (KLinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    //让r指针指向尾部结点
    r = *L;
    
    //循环创建链表结点，尾部插入
    for (int i = 0; i < n; i++) {
        //生成新结点
        p = (Node *) malloc(sizeof(Node));
        //赋值随机数i
        p->data = I;
        
        //尾部插入新结点
        //将表尾终端结点的指针指向新结点
        r->next = p;
        //将当前的新结点定义为表尾终端结点
        r = p;
    }
    
    //将尾部指针next=NULL
    r->next = NULL;
    
}

//9. 单元测试
void test() {
        KStatus iStatus;
        KLinkList L;
        KElementType e;
        
        //2.1 单链表初始化
        iStatus = initList(&L);
        printf("L 是否初始化成功?(0:失败,1:成功) %d\n",iStatus);
        
        //2.2 单链表插入数据
        for(int j = 1;j<=10;j++)
        {
            iStatus = insertElement(&L, 1, j);
        }
        printf("L 插入后\n");
        traverseList(L);
        
        //2.3 单链表获取元素
        getElement(L,5,&e);
        printf("第5个元素的值为：%d\n",e);
        
        //2.4 删除第5个元素
        iStatus = deleteElement(&L, 5, &e);
        printf("删除第5个元素值为:%d\n",e);
        traverseList(L);
        
        //3.1 前插法整理创建链表L
        iStatus = clearList(&L);
        createListByHeadInsert(&L, 20);
        printf("整理创建L的元素(前插法):\n");
        traverseList(L);
        
        //3.2 后插法整理创建链表L
        iStatus = clearList(&L);
        createListByTailInsert(&L, 20);
        printf("整理创建L的元素(后插法):\n");
        traverseList(L);
}


int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    test();
    return 0;
}