本文所有代码运行环境均为Visual Studio Code

1. 需求阶段
2. 分析阶段
3. 设计阶段
4. 求精与编写代码阶段
5. 正确性验证阶段

   1. 第一章 绪论

• 数据（data）：对客观事物的符号表示，所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。
• 数据元素: 是数据（集合）中的一个“个体”，是数据结构中讨论的基本单位。

• 数据项：是数据结构中讨论的最小单位

  数据元素可以是数据项的集合

• 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合；带结构的数据元素的集合,或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。

1.1 数据的逻辑结构：数据对象中数据元素之间的相互关系

• 数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；
• 数据的逻辑结构可以看作是从具体问题抽象出来的数据模型；
• 数据的逻辑结构与数据元素本身的形式、内容无关；
• 数据的逻辑结构与数据元素的相对位置无关。
• 数据的逻辑结构分类
  • 线性结构
    • 线性表
  • 非线性结构
    • 树
    • 图（或网络）
• 集合结构：集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系
• 线性结构：线性结构中的数据元素之间是一对一的关系
• 树形结构：树形结构中的数据元素之间存在一对多的层次关系
• 图形结构：图形结构的数据元素是多对多的关系

1.2 数据的物理（存储）结构：数据的逻辑结构在计算机中的存储形式

• 数据的存储结构是逻辑结构用计算机语言的实现；
• 数据的存储结构依赖于计算机语言。
  • 顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据之间的逻辑关系和物理关系是一致的
  • 链接存储结构：把数据元素存放在任意的存储单元里，这里的存储单元可以是连续的，也可以是不连续的
  • 索引存储结构
  • 散列存储结构

1.3 抽象数据类型及面向对象概念

数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称

定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称.

1. 构造数据类型由基本数据类型或构造数据类型组成。
2. 构造数据类型由不同成分类型构成。
3. 基本数据类型可以看作是计算机中已实现的数据结构。
4. 数据类型就是数据结构，不过它是从编程者的角度来使用的。
5. 数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。

抽象数据类型：一个数学模型及定义在该模型上的一系列操作。

1.4 算法，就是有穷规则的集合，其中的规则规定了解决某特定类型问题的运算序列

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

算法的特性

• 有穷性：一个算法在执行有限步之后必须结束。
• 确定性：算法的每一步骤必须确切定义。执行者可根据该算法的每一步要求进行操作，并最终得出正确的结果（即无歧义） 。
• 可行性：算法中所有的运算都可以精确地实现。
• 输入：算法有零个或多个输入，即在算法开始之前，对算法给定的初始量。
• 输出：算法有一个或多个输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。

算法的性能标准

• 正确性
• 可使用性
• 可读性
• 效率高
• 健壮性

算法效率的度量方法

• 事后统计方法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间的比较，从而确定算法效率的高低。
• 事前分析估计方法：在计算机程序编制前，根据统计方法进行估算。

函数的渐近增长

• 函数的渐近增长：给定两个函数和，如果存在一个整数，使得对于所有，总是大于，那么我们说的增长渐近快于。（一般可以忽略常数）
• 判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。

1.4.1 算法时间复杂度

• 在进行算法分析时，语句总的执行次数是关于问题规模的函数，进行分析随的变化情况并确定的数量级。算法的时间复杂度，也就是算法的时间度量，记作。它表示随文题规模的增大，算法执行时间的增长率和的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中是问题规模的某个函数。
• 这样用大写来体现算法时间复杂度的技法，我们称之为大记法。
• 推导大阶
  1. 用常数1取代运行时间中的加法常数
  2. 在修改后的运行函数中，只保留最高阶项。
  3. 如果最高阶项存在且其系数不是1，则去除与这个项相乘的系数。得到的结果就是大阶。

     1. 常数阶
     2. 线性阶
     3. 对数阶
     4. 平方阶

     常用的时间复杂度所耗费的时间从小到大依次是:

1.4.2 算法空间复杂度

• 算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算式记作:，其中,为问题的规模,为语句关于所占存储空间的函数。

  2. 第二章 线性表

  线性表：零个或多个数据元素的有限序列。
  线性结构的基本特征为:

1. 集合中必存在唯一的一个“第一元素”；
2. 集合中必存在唯一的一个 “最后元素” ；
3. 除最后元素在外，均有 唯一的后继；
4. 除第一元素之外，均有 唯一的前驱。

2.1 抽象数据类型线性表的定义如下

ADT List{
    数据对象：D={a_i|a_i属于ElenSet,i=1,2,...,n}
    数据关系：R1={<a_{i-1},a_i>|a_i属于D,i=1,2,...,n}
    基本操作：
    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, compare( ))/*定位函数*/
        初始条件：线性表L已存在，e为给定值，compare( )是元素判定函数。
        操作结果：返回L中第1个与e满足关系compare( )的元素的位序。若这样的元素不存在，则返回值为0。
    PriorElem( L, cur_e, &pre_e )/*求数据元素的前驱*/
        初始条件：线性表L已存在。
        操作结果：若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。
    NextElem( L, cur_e, &next_e )/*求数据元素的后继*/
        初始条件：线性表L已存在。
        操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。
    ListInsert( &L, i, e )/*插入数据元素*/
        初始条件：线性表L已存在，且   1≤i≤LengthList(L)+1 。
        操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。
    ListDelete(&L, i, &e)/*删除数据元素*/
        初始条件：线性表L已存在且非空，1≤i≤LengthList(L) 。
        操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。
    PutElem( &L, i, &e )
        初始条件：线性表L已存在，且 1≤i≤LengthList(L) 。
        操作结果：L中第i个元素赋值同e的值。
    ListTraverse(L, visit( ))/*遍历线性表*/
        初始条件：线性表L已存在，Visit() 为某个访问函数。
        操作结果：依次对L的每个元素调用函数visit( )。一旦visit( )失败，则操作失败。
}

2.2 线性表顺序存储结构(代码实例)

#include "stdio.h"    
#include "stdlib.h"  
#include "math.h"  
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20          /* 存储空间初始分配量 */
typedef int ElemType;       /* ElemType类型根据实际情况而定，这里假设为int */
typedef struct
{
    ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
    int length;             /* 线性表当前长度 */
}SqList;
typedef int Status;         /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
Status visit(ElemType c)
{
    printf("%d ",c);
    return OK;
}
/* 初始化顺序线性表 */
Status InitList(SqList *L) 
{ 
    L->length=0;
    return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(SqList L)
{ 
    if(L.length==0)
        return TRUE;
    else
        return FALSE;
}
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(SqList *L)
{ 
    L->length=0;
    return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(SqList L)
{
    return L.length;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 || i<1 || i>L.length)
            return ERROR;
    *e=L.data[i-1];
    return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(SqList L,ElemType e)
{
    int i;
    if (L.length==0)
            return 0;
    for(i=0;i<L.length;i++)
    {
            if (L.data[i]==e)
                    break;
    }
    if(i>=L.length)
            return 0;
    return i+1;
}
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{ 
    int k;
    if (L->length==MAXSIZE)  /* 顺序线性表已经满 */
        return ERROR;
    if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
        return ERROR;
    if (i<=L->length)        /* 若插入数据位置不在表尾 */
    {
        for(k=L->length-1;k>=i-1;k--)  /* 将要插入位置之后的数据元素向后移动一位 */
            L->data[k+1]=L->data[k];
    }
    L->data[i-1]=e;          /* 将新元素插入 */
    L->length++;
    return OK;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e) 
{ 
    int k;
    if (L->length==0)               /* 线性表为空 */
        return ERROR;
    if (i<1 || i>L->length)         /* 删除位置不正确 */
        return ERROR;
    *e=L->data[i-1];
    if (i<L->length)                /* 如果删除不是最后位置 */
    {
        for(k=i;k<L->length;k++)/* 将删除位置后继元素前移 */
            L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
            visit(L.data[i]);
    printf("\n");
    return OK;
}
/*将所有的在线性表Lb中但不在La中的数据元素插入到La中*/
void unionL(SqList *La,SqList Lb)
{
    int La_len,Lb_len,i;
    ElemType e;                        /*声明与La和Lb相同的数据元素e*/
    La_len=ListLength(*La);            /*求线性表的长度 */
    Lb_len=ListLength(Lb);
    for (i=1;i<=Lb_len;i++)
    {
        GetElem(Lb,i,&e);              /*取Lb中第i个数据元素赋给e*/
        if (!LocateElem(*La,e))        /*La中不存在和e相同数据元素*/
            ListInsert(La,++La_len,e); /*插入*/
    }
}
int main()
{
    SqList L;
    SqList Lb;
    ElemType e;
    Status i;
    int j,k;
    i=InitList(&L);
    printf("初始化L后：L.length=%d\n",L.length);
    for(j=1;j<=5;j++)
            i=ListInsert(&L,1,j);
    printf("在L的表头依次插入1～5后：L.data=");
    ListTraverse(L); 
    printf("L.length=%d \n",L.length);
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);
    i=ClearList(&L);
    printf("清空L后：L.length=%d\n",L.length);
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);
    for(j=1;j<=10;j++)
            ListInsert(&L,j,j);
    printf("在L的表尾依次插入1～10后：L.data=");
    ListTraverse(L); 
    printf("L.length=%d \n",L.length);
    ListInsert(&L,1,0);
    printf("在L的表头插入0后：L.data=");
    ListTraverse(L); 
    printf("L.length=%d \n",L.length);
    GetElem(L,5,&e);
    printf("第5个元素的值为：%d\n",e);
    for(j=3;j<=4;j++)
    {
            k=LocateElem(L,j);
            if(k)
                    printf("第%d个元素的值为%d\n",k,j);
            else
                    printf("没有值为%d的元素\n",j);
    }
    k=ListLength(L); /* k为表长 */
    for(j=k+1;j>=k;j--)
    {
            i=ListDelete(&L,j,&e); /* 删除第j个数据 */
            if(i==ERROR)
                    printf("删除第%d个数据失败\n",j);
            else
                    printf("删除第%d个的元素值为：%d\n",j,e);
    }
    printf("依次输出L的元素：");
    ListTraverse(L); 
    j=5;
    ListDelete(&L,j,&e); /* 删除第5个数据 */
    printf("删除第%d个的元素值为：%d\n",j,e);
    printf("依次输出L的元素：");
    ListTraverse(L); 
    //构造一个有10个数的Lb
    i=InitList(&Lb);
    for(j=6;j<=15;j++)
            i=ListInsert(&Lb,1,j);
    unionL(&L,Lb);
    printf("依次输出合并了Lb的L的元素：");
    ListTraverse(L); 
    return 0;
}

输出

初始化L后：L.length=0
在L的表头依次插入1～5后：L.data=5 4 3 2 1 
L.length=5
L是否空：i=0(1:是 0:否)
清空L后：L.length=0
L是否空：i=1(1:是 0:否)
在L的表尾依次插入1～10后：L.data=1 2 3 4 5 6 7 8 9 10
L.length=10
在L的表头插入0后：L.data=0 1 2 3 4 5 6 7 8 9 10
L.length=11
第5个元素的值为：4
第4个元素的值为3
第5个元素的值为4
删除第12个数据失败
删除第11个的元素值为：10
依次输出L的元素：0 1 2 3 4 5 6 7 8 9
删除第5个的元素值为：4
依次输出L的元素：0 1 2 3 5 6 7 8 9
依次输出合并了Lb的L的元素：0 1 2 3 5 6 7 8 9 15 14 13 12 11 10

2.3 线性表类型的实现——顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单位依次存储线性表的数据元素。

2.3.1 顺序表元素插入

Status ListInsert(SqList *L,int i,ElemType e)
{ 
    int k;
    if (L->length==MAXSIZE)
        return ERROR;
    if (i<1 || i>L->length+1)
        return ERROR;
    if (i<=L->length)
    {
        for(k=L->length-1;k>=i-1;k--)
            L->data[k+1]=L->data[k];
    }
    L->data[i-1]=e;
    L->length++;
    return OK;
}

2.3.2 顺序表元素删除

Status ListDelete(SqList *L,int i,ElemType *e)
{ 
    int k;
    if (L->length==0)
        return ERROR;
    if (i<1 || i>L->length)
        return ERROR;
    *e=L->data[i-1];
    if (i<L->length)
    {
        for(k=i;k<L->length;k++)
            L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}

2.4 线性表链式存储结构(代码实例)

#include "stdio.h"    
    #include "string.h"
    #include "ctype.h"      
    #include "stdlib.h"   
    #include "math.h"  
    #include "time.h"
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 20 /* 存储空间初始分配量 */
    typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
Status visit(ElemType c)
{
    printf("%d ",c);
    return OK;
}
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList */
/* 初始化链式线性表 */
Status InitList(LinkList *L) 
{ 
    *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
    if(!(*L)) /* 存储分配失败 */
        return ERROR;
    (*L)->next=NULL; /* 指针域为空 */
    return OK;
}
/* 初始条件：链式线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(LinkList L)
{ 
    if(L->next)
        return FALSE;
    else
        return TRUE;
}
/* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{ 
    LinkList p,q;
    p=(*L)->next;           /*  p指向第一个结点 */
    while(p)                /*  没到表尾 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;        /* 头结点指针域为空 */
    return OK;
}
/* 初始条件：链式线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(LinkList L)
{
    int i=0;
    LinkList p=L->next; /* p指向第一个结点 */
    while(p)                        
    {
        i++;
        p=p->next;
    }
    return i;
}
/* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
    int j;
    LinkList p;        /* 声明一结点p */
    p = L->next;        /* 让p指向链表L的第一个结点 */
    j = 1;        /*  j为计数器 */
    while (p && j<i)  /* p不为空或者计数器j还没有等于i时，循环继续 */
    {   
        p = p->next;  /* 让p指向下一个结点 */
        ++j;
    }
    if ( !p || j>i ) 
        return ERROR;  /*  第i个元素不存在 */
    *e = p->data;   /*  取第i个元素的数据 */
    return OK;
}
/* 初始条件：链式线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(LinkList L,ElemType e)
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        i++;
        if(p->data==e) /* 找到这样的数据元素 */
            return i;
        p=p->next;
    }
    return 0;
}
/* 初始条件：链式线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{ 
    int j;
    LinkList p,s;
    p = *L;   
    j = 1;
    while (p && j < i)     /* 寻找第i个结点 */
    {
        p = p->next;
        ++j;
    } 
    if (!p || j > i) 
        return ERROR;   /* 第i个元素不存在 */
    s = (LinkList)malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
    s->data = e;  
    s->next = p->next;      /* 将p的后继结点赋值给s的后继  */
    p->next = s;          /* 将s赋值给p的后继 */
    return OK;
}
/* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L,int i,ElemType *e) 
{ 
    int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while (p->next && j < i)    /* 遍历寻找第i个元素 */
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j > i) 
        return ERROR;           /* 第i个元素不存在 */
    q = p->next;
    p->next = q->next;            /* 将q的后继赋值给p的后继 */
    *e = q->data;               /* 将q结点中的数据给e */
    free(q);                    /* 让系统回收此结点，释放内存 */
    return OK;
}
/* 初始条件：链式线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L)
{
    LinkList p=L->next;
    while(p)
    {
        visit(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}
/*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L, int n) 
{
    LinkList p;
    int i;
    srand(time(0));                         /* 初始化随机数种子 */
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;                      /*  先建立一个带头结点的单链表 */
    for (i=0; i<n; i++) 
    {
        p = (LinkList)malloc(sizeof(Node)); /*  生成新结点 */
        p->data = rand()%100+1;             /*  随机生成100以内的数字 */
        p->next = (*L)->next;    
        (*L)->next = p;                        /*  插入到表头 */
    }
}
/*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n) 
{
    LinkList p,r;
    int i;
    srand(time(0));                      /* 初始化随机数种子 */
    *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
    r=*L;                                /* r为指向尾部的结点 */
    for (i=0; i<n; i++) 
    {
        p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
        p->data = rand()%100+1;           /*  随机生成100以内的数字 */
        r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
        r = p;                            /* 将当前的新结点定义为表尾终端结点 */
    }
    r->next = NULL;                       /* 表示当前链表结束 */
}
int main()
{        
    LinkList L;
    ElemType e;
    Status i;
    int j,k;
    i=InitList(&L);
    printf("初始化L后：ListLength(L)=%d\n",ListLength(L));
    for(j=1;j<=5;j++)
        i=ListInsert(&L,1,j);
    printf("在L的表头依次插入1～5后：L.data=");
    ListTraverse(L); 
    printf("ListLength(L)=%d \n",ListLength(L));
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);
    i=ClearList(&L);
    printf("清空L后：ListLength(L)=%d\n",ListLength(L));
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);
    for(j=1;j<=10;j++)
        ListInsert(&L,j,j);
    printf("在L的表尾依次插入1～10后：L.data=");
    ListTraverse(L); 
    printf("ListLength(L)=%d \n",ListLength(L));
    ListInsert(&L,1,0);
    printf("在L的表头插入0后：L.data=");
    ListTraverse(L); 
    printf("ListLength(L)=%d \n",ListLength(L));
    GetElem(L,5,&e);
    printf("第5个元素的值为：%d\n",e);
    for(j=3;j<=4;j++)
    {
        k=LocateElem(L,j);
        if(k)
            printf("第%d个元素的值为%d\n",k,j);
        else
            printf("没有值为%d的元素\n",j);
    }
    k=ListLength(L); /* k为表长 */
    for(j=k+1;j>=k;j--)
    {
        i=ListDelete(&L,j,&e); /* 删除第j个数据 */
        if(i==ERROR)
            printf("删除第%d个数据失败\n",j);
        else
            printf("删除第%d个的元素值为：%d\n",j,e);
    }
    printf("依次输出L的元素：");
    ListTraverse(L); 
    j=5;
    ListDelete(&L,j,&e); /* 删除第5个数据 */
    printf("删除第%d个的元素值为：%d\n",j,e);
    printf("依次输出L的元素：");
    ListTraverse(L); 
    i=ClearList(&L);
    printf("\n清空L后：ListLength(L)=%d\n",ListLength(L));
    CreateListHead(&L,20);
    printf("整体创建L的元素(头插法)：");
    ListTraverse(L); 
    i=ClearList(&L);
    printf("\n删除L后：ListLength(L)=%d\n",ListLength(L));
    CreateListTail(&L,20);
    printf("整体创建L的元素(尾插法)：");
    ListTraverse(L); 
    return 0;
}

输出

初始化L后：ListLength(L)=0
在L的表头依次插入1～5后：L.data=5 4 3 2 1 
ListLength(L)=5
L是否空：i=0(1:是 0:否)
清空L后：ListLength(L)=0
L是否空：i=1(1:是 0:否)
在L的表尾依次插入1～10后：L.data=1 2 3 4 5 6 7 8 9 10
ListLength(L)=10
在L的表头插入0后：L.data=0 1 2 3 4 5 6 7 8 9 10
ListLength(L)=11
第5个元素的值为：4
第4个元素的值为3
第5个元素的值为4
删除第12个数据失败
删除第11个的元素值为：10
依次输出L的元素：0 1 2 3 4 5 6 7 8 9
删除第5个的元素值为：4
依次输出L的元素：0 1 2 3 5 6 7 8 9
清空L后：ListLength(L)=0
整体创建L的元素(头插法)：82 14 68 79 56 3 54 61 5 33 33 100 15 2 6 27 9 8 97 35
删除L后：ListLength(L)=0
整体创建L的元素(尾插法)：35 97 8 9 27 6 2 15 100 33 33 5 61 54 3 56 79 68 14 82

2.5 线性表类型的实现—-链式存储结构

2.5.1 一、单链表

线性表的链式存储结构 : 用一组地址任意的存储单元存放线性表中的数据元素。

• 数据元素的存储映像，也称结点，包括:
  • 数据域:元素本身信息
  • 指针域:指示直接后继的存储位置

以元素(数据元素的映象)+ 指针(指示后继元素存储位置)= 结点(表示数据元素 或 数据元素的映象)，以“结点的序列”表示线性表称作链表。

以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。
有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。

单链表元素插入

Status ListInsert(LinkList *L,int i,ElemType e)
{ 
    int j;
    LinkList p,s;
    p = *L;   
    j = 1;
    while (p && j < i) 
    {
        p = p->next;
        ++j;
    } 
    if (!p || j > i) 
        return ERROR; 
    s = (LinkList)malloc(sizeof(Node)); 
    s->data = e;  
    s->next = p->next;
    p->next = s;
    return OK;
}

单链表元素删除

Status ListDelete(LinkList *L,int i,ElemType *e) 
{ 
    int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while (p->next && j < i)
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j > i) 
        return ERROR;
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q); 
    return OK;
}

单链表的整表创建

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L, int n) 
{
    LinkList p;
    int i;
    srand(time(0));                         /* 初始化随机数种子 */
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;                      /*  先建立一个带头结点的单链表 */
    for (i=0; i<n; i++) 
    {
        p = (LinkList)malloc(sizeof(Node)); /*  生成新结点 */
        p->data = rand()%100+1;             /*  随机生成100以内的数字 */
        p->next = (*L)->next;    
        (*L)->next = p;                        /*  插入到表头 */
    }
}
/*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n) 
{
    LinkList p,r;
    int i;
    srand(time(0));                      /* 初始化随机数种子 */
    *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
    r=*L;                                /* r为指向尾部的结点 */
    for (i=0; i<n; i++) 
    {
        p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
        p->data = rand()%100+1;           /*  随机生成100以内的数字 */
        r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
        r = p;                            /* 将当前的新结点定义为表尾终端结点 */
    }
    r->next = NULL;                       /* 表示当前链表结束 */
}

单链表整表删除

/* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{ 
    LinkList p,q;
    p=(*L)->next;           /*  p指向第一个结点 */
    while(p)                /*  没到表尾 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;        /* 头结点指针域为空 */
    return OK;
}

2.5.2 单链表结构与顺序存储结构的优缺点

存储分配方式
顺序存储结构：一段连续存储单元依次存储线性的数据元素
链式存储结构（单链表）：一组任意的存储单元存放线性表的元素
时间性能
查找：
顺序存储结构O(1)
单链表O(n)
插入与删除
顺序存储结构：需要平均移动表长一半的元素，时间复杂度为O(n)
单链表：找出位置的指针后，插入和删除时间复杂度仅为O(1)
空间性能
顺序存储结构：需要预分配存储空间，分大了，浪费。分小了，易发生上溢。
单链表：不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

2.5.3 二，静态链表

用数组描述的链表叫做静态链表

#include "string.h"
#include "ctype.h"      
#include "stdio.h"    
#include "stdlib.h"   
#include "math.h"  
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 1000 /* 存储空间初始分配量 */
typedef int Status;           /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char ElemType;        /* ElemType类型根据实际情况而定，这里假设为char */
Status visit(ElemType c)
{
    printf("%c ",c);
    return OK;
}
/* 线性表的静态链表存储结构 */
typedef struct 
{
    ElemType data;
    int cur;  /* 游标(Cursor) ，为0时表示无指向 */
} Component,StaticLinkList[MAXSIZE];
/* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */
Status InitList(StaticLinkList space) 
{
    int i;
    for (i=0; i<MAXSIZE-1; i++)  
        space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0; /* 目前静态链表为空，最后一个元素的cur为0 */
    return OK;
}
/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
int Malloc_SSL(StaticLinkList space) 
{ 
    int i = space[0].cur;                   /* 当前数组第一个元素的cur存的值 */
                                            /* 就是要返回的第一个备用空闲的下标 */
    if (space[0]. cur)         
        space[0]. cur = space[i].cur;       /* 由于要拿出一个分量来使用了， */
                                            /* 所以我们就得把它的下一个 */
                                            /* 分量用来做备用 */
    return i;
}
/*  将下标为k的空闲结点回收到备用链表 */
void Free_SSL(StaticLinkList space, int k) 
{  
    space[k].cur = space[0].cur;    /* 把第一个元素的cur值赋给要删除的分量cur */
    space[0].cur = k;               /* 把要删除的分量下标赋值给第一个元素的cur */
}
/* 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(StaticLinkList L)
{
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
        i=L[i].cur;
        j++;
    }
    return j;
}
/*  在L中第i个元素之前插入新的数据元素e   */
Status ListInsert(StaticLinkList L, int i, ElemType e)   
{  
    int j, k, l;   
    k = MAXSIZE - 1;   /* 注意k首先是最后一个元素的下标 */
    if (i < 1 || i > ListLength(L) + 1)   
        return ERROR;   
    j = Malloc_SSL(L);   /* 获得空闲分量的下标 */
    if (j)   
    {   
        L[j].data = e;   /* 将数据赋值给此分量的data */
        for(l = 1; l <= i - 1; l++)   /* 找到第i个元素之前的位置 */
           k = L[k].cur;           
        L[j].cur = L[k].cur;    /* 把第i个元素之前的cur赋值给新元素的cur */
        L[k].cur = j;           /* 把新元素的下标赋值给第i个元素之前元素的ur */
        return OK;   
    }   
    return ERROR;   
}
/*  删除在L中第i个数据元素   */
Status ListDelete(StaticLinkList L, int i)   
{ 
    int j, k;   
    if (i < 1 || i > ListLength(L))   
        return ERROR;   
    k = MAXSIZE - 1;   
    for (j = 1; j <= i - 1; j++)   
        k = L[k].cur;   
    j = L[k].cur;   
    L[k].cur = L[j].cur;   
    Free_SSL(L, j);   
    return OK;   
} 
Status ListTraverse(StaticLinkList L)
{
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
            visit(L[i].data);
            i=L[i].cur;
            j++;
    }
    return j;
    printf("\n");
    return OK;
}
int main()
{
    StaticLinkList L;
    Status i;
    i=InitList(L);
    printf("初始化L后：L.length=%d\n",ListLength(L));
    i=ListInsert(L,1,'F');
    i=ListInsert(L,1,'E');
    i=ListInsert(L,1,'D');
    i=ListInsert(L,1,'B');
    i=ListInsert(L,1,'A');
    printf("\n在L的表头依次插入FEDBA后：\nL.data=");
    ListTraverse(L); 
    i=ListInsert(L,3,'C');
    printf("\n在L的“B”与“D”之间插入“C”后：\nL.data=");
    ListTraverse(L); 
    i=ListDelete(L,1);
    printf("\n在L的删除“A”后：\nL.data=");
    ListTraverse(L); 
    printf("\n");
    return 0;
}

输出

初始化L后：L.length=0
在L的表头依次插入FEDBA后：
L.data=A B D E F
在L的“B”与“D”之间插入“C”后：
L.data=A B C D E F
在L的删除“A”后：
L.data=B C D E F

静态链表的优缺点

优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点。
缺点：没有解决连续存储带分配来的表长难以确定的问题。失去了链式存储结构随机存取的特性。

2.5.4 三，循环链表

代码示例

#include <stdio.h>
#include <stdlib.h>
typedef struct List
{
    int data;
    struct List *next;
} list, *p_list;
void creat_list(list **p) //如果链表为空，则创建一个链表，指针域指向自己，否则寻找尾节点，将
{                         //将尾节点的指针域指向这个新节点，新节点的指针域指向头结点
    int item;
    list *temp;
    list *target;
    printf("输入节点的值，输入0结束\n");
    while (1)
    {
        scanf("%d", &item);
        if (item == 0)
            break;
        if (*p == NULL) //如果输入的链表是空。则创建一个新的节点，使其next指针指向自己  (*head)->next=*head;
        {
            *p = (list *)malloc(sizeof(list));
            if (!*p)
                exit(0);
            (*p)->data = item;
            (*p)->next = *p;
        }
        else //输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
        {
            for (target = *p; target->next != *p; target = target->next)
                ; //寻找尾节点
            temp = (list *)malloc(sizeof(list));
            if (!temp)
                exit(0);
            temp->data = item;
            temp->next = *p;     //新节点指向头节点
            target->next = temp; //尾节点指向新节点
        }
    }
}
void insert(list **pNode, int place, int num) //链表的插入
{
    list *temp, *target;
    int i;
    if (place == 1) //如果输入的数字是1，表示要插入头节点。应该特殊处理
    {               //首先找到尾节点，让后让新节点的next指向头节点，尾节点指向新的头节点，在让头指针指向temp。这要特别注意
        temp = (list *)malloc(sizeof(list));
        if (!temp)
            exit(0);
        temp->data = num;
        for (target = *pNode; target->next != *pNode; target = target->next)
            ;
        temp->next = *pNode;
        target->next = temp;
        *pNode = temp; //特别注意
    }
    else //在其他的地方插入节点。  同样先找到要插入的位置，如果位置超出链表的长度，自动插入队尾。                        tar  new  原来是2
    {    //找到要插入位置的前一个节点target，让target->next=temp，插入节点的前驱指向新节点，新节点指向target->next的地址  1    2   3
        for (i = 1, target = *pNode; target->next != *pNode && i != place - 1; target = target->next, i++)
            ;
        temp = (list *)malloc(sizeof(list));
        temp->data = num;
        temp->next = target->next;
        target->next = temp;
    }
}
void Delete(list **pNode, int place) //删除操作
{
    list *temp, *target;
    int i;
    temp = *pNode;
    if (temp == NULL) //首先判断链表是否为空
    {
        printf("这是一个空指针 无法删除\n");
        return;
    }
    if (place == 1) //如果删除的是头节点
    {               //应当特殊处理，找到尾节点，使尾节点的next指向头节点的下一个节点 rear->next=(*head)->next;然后让新节点作为头节点，释放原来的头节点
        for (target = *pNode; target->next != *pNode; target = target->next)
            ;
        temp = *pNode;
        *pNode = (*pNode)->next;
        target->next = *pNode;
        free(temp);
    }
    else
    { //删除其他节点
        for (i = 1, target = *pNode; target->next != *pNode && i != place - 1; target = target->next, i++)
            ;                       //首先找出尾节点
        if (target->next == *pNode) //判断要删除的位置是否大于链表长度，若大于链表长度，特殊处理直接删除尾节点
        {
            for (target = *pNode; target->next->next != *pNode; target = target->next)
                ;                //找出尾节的前一个节点
            temp = target->next; //    尾节点的前一个节点直接指向头节点  释放原来的尾节点
            target->next = *pNode;
            printf("数字太大删除尾巴\n");
            free(temp);
        }
        else
        {
            temp = target->next;       //  删除普通节点  找到要删除节点的前一个节点target，使target指向要删除节点的下一个节点  转存删除节点地址
            target->next = temp->next; //  然后释放这个节点
            free(temp);
        }
    }
}
int findval(list *pNode, int val) //寻找值
{
    int i = 1;
    list *node;
    node = pNode;
    while (node->data != val && node->next != pNode)
    {
        i++;
        node = node->next;
    }
    if (node->next == pNode && node->data != val) //尾节点指向头节点就跳出，因此还要检测一次为节点的data
    {
        return -1;
    }
    return i;
}
void show(list *p) //遍历，循环链表的遍历最好用do while语句 ，因为头节点就有值
{
    list *temp;
    temp = p;
    do
    {
        printf("%5d", temp->data);
        temp = temp->next;
    } while (temp != p);
    printf("\n");
}
int main()
{
    list *head = NULL;
    // list *val;
    int place, num;
    creat_list(&head);
    printf("原始的链表：");
    show(head);
    printf("输入要删除的位置：");
    scanf("%d", &place);
    Delete(&head, place);
    show(head);
    printf("输入要插入的位置和数据用空格隔开：");
    scanf("%d %d", &place, &num);
    insert(&head, place, num);
    show(head);
    printf("输入你想查找的值:");
    scanf("%d", &num);
    place = findval(head, num);
    if (place != -1)
        printf("找到的值的位置是place=%d\n", place);
    else
        printf("没找到值\n");
    return 0;
}