第1节：线性表

1.1 概念

线性表是一种简单的线性结构，特点是在非空的有限集合中，且第一个元素没有直接前驱元素，最后一个元素没有直接后继元素，其他元素都有唯一的前驱和后继元素。线性表有顺序存储结构和链式存储结构。
总结一下就是：
对于⾮空的线性表和线性结构,其特点如下:
• 存在唯⼀的⼀个被称作”第⼀个”的数据元素;
• 存在唯⼀的⼀个被称作”最后⼀个"的数据元素
• 除了第⼀个之外,结构中的每个数据元素均有⼀个前驱
• 除了最后⼀个之外,结构中的每个数据元素都有⼀个后继

1.2顺序存储结构

是指将线性表中的各个元素依次存放在一组地址连续的存储单元中，通常将这种方法存储的线性表称为顺序表。

假设，线性表的每个元素需占用m个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个元素的存储位置location(ai+1)和第i个元素的存储位置location(ai)之间满足关系location(ai+1)=location（ai）+m。线性表中第i个元素的存储位置与第一个元素的a1的存储位置满足以下关系，location(ai) =location(a1)+(i-1)*m。其中，第一个元素的位置location(a1)称为起始地址或基地址。

顺序表逻辑上相邻的元素在物理上也是相邻的。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。只要确定了第一个元素的起始位置，线性表中的任一个元素都可以随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构。由于C语言的数组具有随机存储特别，因此采用数组来描述顺序表。如下所示：

typedef struct{
    ElemType list[ListSize];
    int length;
}SeqList;
或者
typedef struct{
    ElemType *list;
    int length;
}SeqList;

其中，ElemType表示数据元素类型，list用于存储线性表中的数据元素，length用来表示线性表中数据元素的个数，SeqList是结构体类型名。定义一个顺序表代码：SeqList L; 指向顺序表的指针：SeqList *L;
基本运算如下

前置条件

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

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

typedef struct{
   ElemType *data;
   int length;
}SeqList;

（1）初始化线性表：

//1.1 顺序表初始化
Status InitList(Sqlist *L){
    //为顺序表分配一个大小为MAXSIZE 的数组空间
    L->data =  malloc(sizeof(ElemType) * MAXSIZE);
    //存储分配失败退出
    if(!L->data) exit(ERROR);
    //空表长度为0
    L->length = 0;
    return OK;
}

(2）线性表非空判断:

int ListEmpty(SeqList L){
    if(L.length ==0)
        return 1;
    else
        return 0;
}

（3）按序号查找：

Status GetElem(Sqlist L,int i, ElemType *e){
    //判断i值是否合理, 若不合理,返回ERROR
    if(i<1 || i > L.length) return  ERROR;
    //data[i-1]单元存储第i个数据元素.
    *e = L.data[i-1];
    
    return OK;
}

(4)按内容查找：

//1.9 顺序表查找元素并返回位置
/* 初始条件：顺序线性表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;
}

（5）插入操作：

//1.2 顺序表的插入
/*
 初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
 */
Status ListInsert(Sqlist *L,int i,ElemType e){
    
    //i值不合法判断
    if((i<1) || (i>L->length+1)) return ERROR;
    //存储空间已满
    if(L->length == MAXSIZE) return ERROR;
 
    //插入数据不在表尾,则先移动出空余位置
    if(i <= L->length){
        for(int j = L->length-1; j>=i-1;j--){
       
            //插入位置以及之后的位置后移动1位
            L->data[j+1] = L->data[j];
        }
    }
    
    //将新元素e 放入第i个位置上
    L->data[i-1] = e;
    //长度+1;
    ++L->length;
    
    return OK;
    
}

(6）删除操作：

//1.4 顺序表删除
/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果: 删除L的第i个数据元素,L的长度减1
 */
Status ListDelete(Sqlist *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;
    
}

（7）清空操作

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

(8)顺序输出链表内容

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

调用尝试

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, Data Structure!\n");
    
    Sqlist L;
    Sqlist Lb;
    ElemType e;
    Status iStatus;
    
    //1.1 顺序表初始化
    iStatus = InitList(&L);
    printf("初始化L后: L.Length = %d\n", L.length);
    
    //1.2 顺序表数据插入
    for(int j=1; j <= 5;j++){
        iStatus = ListInsert(&L, 1, j);
    }
    printf("插入数据L长度: %d\n",L.length);
    
    //1.3 顺序表取值
    GetElem(L, 5, &e);
    printf("顺序表L第5个元素的值为:%d\n",e);
    
    //1.4 顺序表删除第2个元素
    ListDelete(&L, 2);
    printf("顺序表删除第%d元素,长度为%d\n",2,L.length);
    
    //1.5 清空顺序表
    iStatus = ClearList(&L);
    printf("清空后,L.length = %d\n",L.length);
    
    //1.6 判断List是否为空
    iStatus=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",iStatus);
    
    //1.8 TraverseList
    for(int j=1; j <= 5;j++){
        iStatus = ListInsert(&L, 1, j);
    }
    TraverseList(L);
    
    
    return 0;
}

1.3 线性表的链式存储

在解决实际问题时，有时并不适合采用线性表的顺序存储结构，例如两个一元多项式的相加、相乘，这就需要另一种存储结构——链式存储。它是采用一组任意的连续或非连续存储单元存储线性表的元素。为了表示每个元素ai与其直接后继ai+1的逻辑关系，链式存储不仅需要存储元素本身，还要存储一个指向其直接后继元素的地址。这种存储结构被称之为结点（node）。存储元素的叫数据域，存储地址的叫指针域。结点元素的逻辑顺序称之为线性链表或单链表。

结点 单链表逻辑状态

因为第一个结点没有直接前驱结点，因此需要一个头指针指向它。为了方便操作放在第一个元素结点之前一个结点称之为头结点，头指针变成指向头结点，其数据域可以存放如线表长度等信息，而指针域则存放第一个元素结点的地址信息。若该链表为空，则头结点指针域为空。
增加一个头结点的好处：
1.便于⾸元结点处理
2.便于空表和⾮空表的统⼀处理

增加头结点之后的逻辑状态

最后一个元素没有直接后继元素，所以将其指针域设置为“NULL”空。

单链表的存储结构用C语言描述：

typedef struct Node{
    DataType data;
    struct Node *next;
}ListNode,*LinkList;

其中，ListNode是链表的结点类型，LinkList是指向链表结点的指针类型。定义为：LinkList L = ListNode *L。

单链表的基本运算如下：
前置条件

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

#define MAXSIZE 20 /* 存储空间初始分配量 */

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

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

typedef struct Node * LinkList;

（1）初始化单链表：

//2.1 初始化单链表线性表
Status InitList(LinkList *L){
    
    //产生头结点,并使用L指向此头结点
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if(*L == NULL) return ERROR;
    //将头结点的指针域置空
    (*L)->next = NULL;
    
    return OK;
}

（2）单链表非空判断：

int ListEmpty(LinkList L){
    if(L->next == NULL){  //单链表为空
        return 1;
    }
    else
    {
        return 0;
    }
}

（3）按序号查询操作：

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

（4）按内容查找单链表中元素值为e的元素：

//按内容查找单链表中元素值为e的元素
int LocateElem(LinkList head, ElemType e, LinkList r){
    LinkList p;
    if(ListEmpty(head))//非空判断
        return ERROR;

    p = head->next; //指针p指向第一个结点
    while(p){
        if(p->data != e){
            p=p->next;//继续下一个
        }else{
            break;
        }
    }
    r = p;
    return OK;
}

（5）定位操作：

int LocatePos(LinkList head, ElemType e){
    LinkList p;//定义一个指向单链表的结点的指针p
    int i;
    if(ListEmpty(head))//非空判断
        return 0;
    
    p =head->next;//指针p指向一个结点
    i =1;
    wihle(p){
        if(p->data==e)
            return i;
        else
        {
            p=p->next;//指向下一个结点
            i++;
        }
    }
    if(!p)//如果没有找到与e相等的元素
         return 0;
 
}   

(6)插入新数据元素e：

//2.2 单链表插入
/*
 初始条件:顺序线性表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;
    
    //寻找第i-1个结点
    while (p && j<i) {
        p = p->next;
        ++j;
    }
    
    //第i个元素不存在
    if(!p || j>i) return ERROR;
    
    //生成新结点s
    s = (LinkList)malloc(sizeof(Node));
    //将e赋值给s的数值域
    s->data = e;
    //将p的后继结点赋值给s的后继
    s->next = p->next;
    //将s赋值给p的后继
    p->next = s;
    
    return OK;
}

简单点理解：

1 2 3 4 5 将6插入到第三个，实际上是打破2和3个关系插入6，你需要找到i-1也就是2号位置，将2号位置的next指向当前节点，并将当前节点的next指向2号位的下一个节点。结果是1 2 6 3 4 5

插入元素逻辑

(7)删除第i个结点：

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

简单点理解：

1 2 3 4 5 删除第三个，实际上是也是打破2 3的关系，找到i - 1 也就是2号的位置，将2号位置的next指向 3号位置的next也就是4号位置，并且将3号位置释放。结果是1 2 4 5.

删除元素逻辑

(8)遍历操作

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

（9）清空链表

/* 初始条件：顺序线性表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;
}

(10)头插法

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

前插法逻辑

(11)尾插法

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

尾插法逻辑

前插法与尾插法区别在于他们的插入顺序是相逆的

调用调试

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    Status iStatus;
    LinkList L1,L;
    struct Node *L2;
    ElemType e;
    
//    L1 =(LinkList) malloc(sizeof(Node));
//    L2 =(LinkList) malloc(sizeof(Node));
//
//    L1->data = 1;
//    L2->data = 2;
//    printf("L1.data=%d,L2.data=%d\n",L1->data,L2->data);
    
    //2.1 单链表初始化
    iStatus = InitList(&L);
    printf("L 是否初始化成功?(0:失败,1:成功) %d\n",iStatus);
    
    //2.2 单链表插入数据
    for(int j = 1;j<=10;j++)
    {
        iStatus = ListInsert(&L, 1, j);
    }
    printf("L 插入后\n");
    ListTraverse(L);
    
    //2.3 单链表获取元素
    GetElem(L,5,&e);
    printf("第5个元素的值为：%d\n",e);
    
    //2.4 删除第5个元素
    iStatus = ListDelete(&L, 5, &e);
    printf("删除第5个元素值为:%d\n",e);
    ListTraverse(L);
    
    //3.1 前插法整理创建链表L
    iStatus = ClearList(&L);
    CreateListHead(&L, 20);
    printf("整理创建L的元素(前插法):\n");
    ListTraverse(L);
    
    //3.2 后插法整理创建链表L
    iStatus = ClearList(&L);
    CreateListTail(&L, 20);
    printf("整理创建L的元素(后插法):\n");
    ListTraverse(L);
    
}

1.4单链表与顺序表的对比

（1）存储方式：顺序表用一组连续的存储单元依次存储线性表的数据元素；而单链表用一组任意的存储单元存放线性表的数据元素。

（2）时间性能：采用循序存储结构时查找的时间复杂度为O(1)，插入和删除需要移动平均一半的数据元素，时间复杂度为O(n)。采用单链表存储结构的查找时间复杂度为O(n)，插入和删除不需要移动元素，时间复杂度仅为O(1）。

（3）空间性能：采用顺序存储结构时需要预先分配存储空间，分配空间过大会造成浪费，过小会造成问题。采用单链表存储结构时，可根据需要进行临时分配，不需要估计问题的规模大小，只要内存够就可以分配，还可以用于一些特殊情况，如一元多项的表示。