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 数据结构基本术语

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

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

集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系，它们之间唯一的相同点就是"同属于一个集合"。

线性结构：线性结构中的数据元素之间的关系是一对一的。常用的线性结构有：线性表、栈、队列、双队列、数组、串。

树形结构：树形结构中的数据元素是一对多的层级关系。常见的树形结构: 二叉树、B树、哈夫曼树、红黑树等。

图形结构：图形结构中的数据元素之间的关系是多对多的。常见的图形结构：邻近矩阵、邻接表。

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

顺序存储结构：指把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。比如一个数组，它的元素是一个接一个，在内存空间中的地址也是连续的，我们可以通过数组的下标访问每一个元素，也可以使用地址递增的方式访问

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

链式存储结构：是把数据元素放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。

1.2.2 数据结构与算法关系

算法是什么？

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

算法有以下特性：

输入输出：算法具有零个或者多个输入，至少有一个或多个输出。
有穷性：有穷性指的是算法在执行有限的步骤之后，自动结束而不会出现无限循环,且每一个步骤都在可接受的时间内完成。
确定性：确定性是指算法的每一个步骤都具有确定的含义，不能出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。
可行性：算法的每一步都必须是可行的，即每一步都能通过执行有限次数完成

算法设计要求：

正确性：算法的正确性是指算法至少应该具有输入，输出和加工处理无歧义性，能正确反映问题的需求、能够得到问题的正确答案。正确性分为4个层次: - 算法程序没有语法错误; - 算法程序对于合法的输入数据能够产生满足要求的输出结果; - 算法程序对于非法的输入数据能够得出满足规格说明的结果; - 算法程序对于精心选择的,甚至刁钻的测试数据都有满足要求的输出结果;
可读性：: 算法设计的另一个目的是为了便于阅读，理解和交流。可读性高有助于人们理解算法，晦涩难懂的算法往往隐含错误，不容易发现，并且难于调试和修改。
健壮性：一个好的算法还应该能对输入数据的不合法的情况做出合适的处理，考虑边界性，也是在写代码经常要做的一个处理。当输入数据不合法时，算法也能做出相关处理，而不是产生异常和莫名其妙的结果。
时间效率高和存储量低：用最少的存储空间和最少的时间，办成同样的事，就是好算法

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

1.2.3.1 时间复杂度：

使用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列的因素:

算法采用的策略、方法
编译产生的代码质量
问题的输入规模
机器执行指令的速度

算法的时间复杂度的定义如下：在进行算法分析时，语句的总执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，即为T(n) = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。大写O( )来体现算法时间复杂度的记法，我们称之为大O记法。推导大O阶的方法：

用常数1取代运行时间中所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果在最高阶项存在且不是1，则去除与这个项相乘的常数
常数阶

int sum = 0, n = 100;
sum = (1 + n) * n / 2;
printf("%d", sum);

这个算法的每行代码都会执行一次，运行次数函数是f(n) = 3，依据推导大O阶的方法，第一步就是将常数替换为1，由于没有最高阶项，所以该算法的时间复杂度为O(1)。需要注意的是，常数阶的算法不管常数是多少，我们都记做O(1)，并没有O(2)、O(3)之类的复杂度。

线性阶

for (int i = 0; i < n; i++) {
    //  时间复杂度为O(1)的操作   
}

分析算法的复杂度，就是要分析循环结构的运行情况。上述代码的时间复杂度为O(n)，是因为循环体中的代码要执行n次。

对数阶

int i = 1;
while (i < n) {
    i = i * 2;
}

在循环体内，i每次都乘以2倍，即为2^x = n，可以得出次数x为以2为低n的对数x = log2n。根据推导大O阶的方法，去除最高阶项的常数，即为O(logn)。

平方阶

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        //  时间复杂度为O(1)的操作   
    }
}

循环嵌套n*n，时间复杂度为O(n^2)。

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

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

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

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 线性表之顺序表

ADT list{ Data:线性表的数据对象集合为{a1,a2,a,......an},每个元素的类型均为DataType，其中，除了第一个元素a1 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an 外，每个元素有且只有一个直接后续元素，数据元素之间的关系是一对一的关系。 OPeration（操作） InitList(&L) 初始化表操作结果：初始化操作，建立一个空的线性表L DestroyList(&L) 销毁表初始条件：线性表L已存在操作结果：销毁线性表L ClearList(&L) 清空表初始条件：线性表L已存在操作结果：将L重置为空表 ListEmpty(L) 表是否为空初始条件：线性表L已存在操作结果：若L为空表，则返回true，否则返回false ListLength(L) 表长度（元素个数）初始条件：线性表L已存在操作结果：返回L中数据元素的个数 ...... GetElem(L,i,&e) 获取元素初始条件: 线性表L已存在,且1<=i<ListLength(L) 操作结果: 用e返回L中第i个数据元素的值; LocateElem(L,e) 初始条件: 线性表L已存在操作结果: 返回L中第1个值与e相同的元素在L中的位置. 若数据不不存在则返回0; PriorElem(L, cur_e,&pre_e); 初始条件: 线性表L已存在操作结果: 若cur_e是L的数据元素,且不不是第⼀一个,则⽤用pre_e返回其前驱,否则操作失败. NextElem(L, cur_e,&next_e); 初始条件: 线性表L已存在操作结果: 若cur_e是L的数据元素,且不不是最后⼀一个,则⽤用next_e返回其后继,否则操作失败. ...... ListInsert(L,i,e); 初始条件: 线性表L已存在,且1<=i<=listLength(L) 操作结果: 在L中第i个位置之前插⼊入新的数据元素e,L⻓长度加1. ListDelete(L,i); 初始条件: 线性表L已存在,且1<=i<=listLength(L) 操作结果: 删除L的第i个元素,L的⻓长度减1. TraverseList(L); 初始条件: 线性表L已存在操作结果: 对线性表L进⾏行行遍历,在遍历的过程中对L的每个结点访问1次. }ADT List.

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;
}

数据结构和算法（一）线性表实现