线性表

前言：线性表是最常用，最简单的数据结构

线性表的逻辑结构及其定义

是由n(n>=0)个数据元素(结点):a1,a2……an组成的有限序列。

该序列中的所有结点具有相同的数据类型。

其中，数据元素的个数n称为线性表的长度。

当n=0时，称为空表。

当n>0时，称为非空的线性表，记作：L=(a1,a2,……,ai,……,an)。

a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。

a1,a2,……ai-1都是ai(2<=i<=n)的前驱，其中ai-1是ai的直接前驱。

ai+1,ai+2……an都是ai(2<=i<=n)的后驱，其中ai+1是ai的直接后驱。

线性表的特点

元素数据是有序的；元素数据是有限的。

在线性表中：

1、存在一个唯一的被称作“第一个”的数据元素。

2、存在一个唯一的被称为“最后一个”的数据元素。

3、除第一个元素外，每个元素均有唯一一个直接前驱。

4、除最后元素外，每个元素均有唯一一个直接后驱。

若线性表中的结点时按值(或按关键字值)由小到大(或由大到小)有序排列的，称线性表是有序的。

对结点ai做个详细介绍

在线性表的定义中，ai只不过是一个抽象的表示符号。

1、ai可以是单值元素(每个元素只有一个数据项)

2、ai也可以是记录型元素，(每个元素含有多个数据项，多个数据项就可以标识这个数据元素，例如：(学校，专业，班级，姓名，座号)就可以标识一个元素)，每个项称为结点的一个域。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。

线性表(数据结构)的存储方式

线性表的存储表示主要有两种

顺序存储表示、链式存储表示

(这边拓展一下数据的存储结构依赖于计算机语言，其中主要的存储方式是顺序存储表示和链式存储表示，这两个主要用于内存的存储表示；索引存储表示和散列存储表示是主要用于**外存(文件)**的存储表示)

顺序存储和链式存储

线性表的顺序存储

顺序存储结构：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方式存储的线性表简称”顺序表“。

顺序存储的线性表的特点：

①线性表的逻辑顺序和物理顺序一致；

②数据元素之间的关系是**以元素在计算机内的”物理位置相邻”**来体现。

下面用代码阐述顺序表

#include<stio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define OK 1
#define ERROR 0

typedef int Status;  //Status是函数的类型，其值是函数结果状态代码，如OK等

typedef int ElemType;  //ElemType的类型根据实际情况而定，这里假定为int
//顺序表数据结构
typedef struct{
    ElemType *elem;
    int length;
}SqList;

1、构造一个空的顺序表

Status InitList(SqList* L){
    //构造一个空的线性表
    L -> elem = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));
    if(!L -> elem){
        return ERROR;
    }
    L -> length = 0;
    return OK;
}

2、顺序表的插入

Status ListInsert(SqList *L,int i,ElemType e){
    int k;
    if(L -> length == MAXSIZE){
        retuen ERROR;
    }
    if(i < 1 || i > L -> length+1){
        return ERROR;
    }
    if(i <= L -> length){  //这个语句判断检查插入位置i是否在表尾之前，如果是，则需要将插入位置之后的元素往后移一位，为新元素腾出一位。注意第i个元素的下标是i-1。
        for(k = L -> length-1;k >= i-1;k--){
           L -> elem[k+1] = L -> elem[k];
        }
    }
    L -> elem[i-1] = e;
    L -> length++;
    return OK;
}

3、顺序表的删除

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

4、获取顺序表某一个位置的元素

Status GetElem(SqList L, int i, ElemType *e){
    if (L.length == 0 || i < 1 || i > L.length){
        return ERROR;
    }
    *e = L.elem[i-1];
    return OK;
}

5、读取顺序表中所有元素

void OutPut(SqList L){
    printf("当前顺序表的长度：%d\n",L.length);
    for(int i = 0; i < L.length; i++){
        printf("%d",L.length[i]);
    }
    printf("\n");
}

小结

1、顺序表时间复杂度

线性表的顺序存储结果在**取值的时间复杂度是O(1)，查找、插入、删除操作的时间复杂度是O(n)**。

2、顺序表的优缺点

优点：物理地址上连续，很好查找元素。

缺点：插入，删除操作需要移动大量元素。

链式存储

用一组任意的存储单元存储线性表中的数据元素。

链表通过在每个结点增加指针域，由指针将线性表的n个结点按其逻辑次序链接在一起。

链表结点 = 数据域(data) + 指针域(prior & next);

根据指针域的数目可分为单链表和双链表。

单链表

定义单链表的结点：

#define END_CODE -999
typedef struct Lnode{
    ElemType data;  //数据域
    struct Lnode *next;  //指针域
}LNode;

单链表的创立一共有两种：头插法和尾插法。

头插法

void show(LNode *L);  //函数声明
//头插法创建单链表，链表的头结点head作为返回值
LNode *create_LinkList_H(){
    LNode *head, *q;  //head-头结点; q-待插入结点指针
    
    //创建只有头结点head的空单链表
    head = new LNode;  //head = (LNode *) malloc(sizeof(LNode));
    head -> next = NULL;
    
    //录入链表各结点的数据，并钩链
    ElemType data;
    cout<<"请录入数据('int'类型)以'头插'创建单链表结点，建入'"<<END_CODE<<"'结束链表创建!\n";
    while(true){
        //键盘输入一个链表结点数据 -> data
        cin >> data;  //scanf("%d",&data);
        //若录入数据data == '数据录入'结束标志END_CODE，则完成链表创建！
        if(data == END_CODE){
            break;
        }
        
        //录入的链表结点数据data有效，则创建一个链表结点存储此数据
        q = new LNode;  //q = (LNode *)malloc(sizeof(LNode));  //新建链表结点
        q -> data = data;  //数据域赋值
        
        //钩链：新创建的结点q总是作为第一个结点
        q -> next = head -> next;
        head -> next = q;
        
        //信息提示:结点创建成功！并显示当前链表的信息内容
        cout <<"结点" << q -> data <<"创建成功，插入在表头!\n";
        show(head);  //显示当前的链表
    }
    
    //返回此单链表的头结点head
    return (head);
}

尾插法

LNode *create_LinkList_R(){
    LNode *head,*p,*q;  //head-头结点;q-待插入结点指针;p-尾结点指针
    
    //创建只有头结点head的'空单链表'，尾结点指针p指向head
    head = p = new LNode;
    head -> next = NULL;
    
    //录入链表各结点数据，并钩链
    ElemType data;
    cout<<"请录入数据('int类型')以'尾插'创建单链表结点，键入'"<<END_CODE<<"'结束链表创建!\n;
    while(true){
        //键盘输入一个链表结点数--》data
        cin >> data;
        
        //若录入数据data =='数据录入'结束标志END_CODE,则完成链表创建!
        if(data ==  END_CODE){
            break;
        }
        
        //录入的链表结点数据data有效，则创建一个链表结点存储此数据
        q = new LNode;
        q -> data = data;
        
        //钩链:新创建结点总是作为最后一个结点(q插入在p的后面)
        q -> next = p -> next;
        p -> next = q;
         p = q; //更新为尾结点指针为p(为q)
        
        //信息提示:结点创建成功!并显示当前链表的内容信息!!!
        cout <<"结点"<< q -> data<<"创建成功，插在表尾!\n";
        show(head);
    }
    
    //返回此单链表的'头结点head'
    return (head);
}

按序号查找，获取单链表的第i个元素

ElemType get_ElemByID(LNode *L, int i){
    if(L == NULL || L -> next == NULL){
        return END_CODE;
    }
    
    int j;  //j-链表结点计数器
    LNode *p;  //p-遍历链表的指针
    
    //初始化: p和j
    p = L-> next; //p指向:首结点
    j = 1; //初始化为1(因p指向'首结点')
    
    //遍历链表，以寻求获得第i个结点
    while(p -> next != NULL && j<i){
        p = -> next;
        j++;
    }
    
    //判断是否找到第i个结点?
    if(j != i){
        return (END_CODE);
    }else{ //Yes
        return (p -> data);
    }
}

按值查找，获取单链表中数据值为x的第一个结点。

LNode *get_NodeByValue(LNode *L,ElemType x){
    if( L == NULL || L -> next == NULL){  //链表不存在或空
        return NULL;
    }
    
    //遍历链表，直到:1)链表末尾或 2)找到值为x的结点
    LNode *p = L -> next;  //p-指向:链表首(第一个)结点
    while (p != NULL && p -> data != x){
        p = -> next;
    }
    
    //处理查找结果，...上述遍历推出，是因为:
    if(p != NULL){  //找到值为x的结点p
        reurn p;
    }else{  //所有链表结点都遍历过了
        //<<"索要查找的值为'"<< x >>"'的结点不存在!\n";
        return NULL;
    }
}

在以L为头结点的单链表的第’i’个位置，插入值为e的结点

bool insert_LNode(LNode *L, int i,ElemType e){
    if(L == NULL){
        return false;
    }
    LNode *p, *q;  //p-游标指针(指向第i-1结点),q-待插入结点e指针
     int j;
}

删除以L为头结点的单链表中，序号为i的结点

bool delete_NodebyID(LNode *L, int i){
    if(L == NULL || L -> next == NULL){
        return false;
    }
    
    //p-游标指针(为指向第i-1个结点),q-指向第i个结点的指针(待删)
    LNode *p, *q;
    
    //初始化:p和q
    p = L;  //指向:头结点
    q = L -> next;  //指向:首结点
    
    int j = 1;  //遍历过的结点计数(初始化为1，因q='首结点')
    
    //遍历链表，使q指向: 1)第i个结点 或 2)链尾NULL
    whlie( q -> next != NULL && j < i){  //移动指针p&q,j计数+1
        //移动指针p&q
        p = q;
        q = q -> next;  //q往后移
        
        //j计数+1
        j++;
    }
    
    //判断是否找到第i个结点?
    if(j != i){  //No(p为NULL:表示i太大;j>i表示i<=0)
        return false;  //删除:失败
    }else{  //Yes
        p -> next = q -> next;  //令p指向:q的直接后继
        delete(q);  //释放结点q(第i个结点)所占的内存空间
        return true;  //删除:成功
    }
}

删除以L为头结点的单链表中所有值相同的结点，使得所有结点的值，都不相同

void delete_ALLSameValue(LNode *L){
    if(L == NULL){
        return false;
    }
    
    LNode *p = L -> next,*q,*ptr;
    //p从首结点开始，检查p的所有后续结点，若值与p相同，则删除
    while(q != NULL){
        q = p, ptr = p -> next;  //q为ptr的直接前驱结点
        
        //检查结点p的所有后继结点ptr
        while(ptr != NULL){
            if(ptr -> data == p -> data){
                q -> next = ptr -> next;  //q指向ptr的直接后继结点
                delete(ptr);  //删除ptr结点
                ptr = q -> next;  //ptr往后移
            }else{  //移动指针q&ptr
                q = ptr;  //q往后移
                ptr = ptr -> next;  //ptr往后移
            }
        }
        //指针p后移
        p = p -> next;
    }    
}

显示链表的内容(以指定的结点L为头结点，头结点中的数据不输出)

void show(LNode *L){
    //单链表为NULL空
    if(L -> next == NULL){
        cout <<"单链表:为NULL空!\n";
        return;
    }
    
    //输出以L为头结点的单链表的各个结点的数据格式:"顺序表:-->e1->e2->...->en"
    LNode *q = L -> next;  //q指向L的下一结点
    cout <<"单链表: ";
    while(q != NULL){  //循环，以输出各结点的w数据
        //输出结点数据
        cout <<" -> "<< q -> data;
        
        //下一结点
        q = q -> next;
    }
    cout << endl;//链表输出结束-换行
}

合并两个单链表

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdib.h>

typedef struct LNode{
    int data;
    struct LNode *next;
}*LinkList,LNode;

//带头结点的初始化
bool Initlist(LinkList& L){
    L = (LNOde*)malloc(sizeof(LNode));
    if(L == NULL){
        return true;
    }
    L -> next = NULL;
    return true;
}

//尾插法创建一个单链表
bool TailInsert(LinkLinst L){
    int num = 0;
    int ele = 0;
    LNode *p = L;
    printf("请输入你要插入的元素个数:\n");
    scanf("%d",&num);
    for(int i = 0;i< num;i++){
        printf("请输入第%d个元素:",i+1)
        scanf("%d",&ele);
        LNode *s = (LNode*)malloc(sizeof(LNode));
        if(s == NULL){
            return false;
        }
        s -> data = ele;
        s -> next = NULL;
        p -> next = s;
        p = p -> next;
    }
    return true;
}

//合并两个单链表
LinlList mergeList(LinkList L1,LinkList L2){
    LNode *head = (LNOde*)malloc(sizeof(LNode));
    LNode *p1 = L1 -> next;
    LNode *p2 = L2 -> next;
    LNode *pre = head;
    while(p1 != NULL && p2 != NULL){
        if(p1 -> data <= p2 -> data){  //按降序进行连接
            pre -> next = p1;
            p1 = p1 -> next;
        }
        else{
            pre -> next = p2;
            p2 = p2 -> next;
        }
        pre = pre -> next;
        
    }
    pre -> next = p1 == NULL ? p2 : p1;
    return head;
}

//遍历一个单链表
void TranverseLinkList(LinkList L){
    LNode *p = L -> next;
    preinf("单链表序列为: ");
    while(p != NULL){
        printf("%d", p -> data);
        p = p -> next;
    }
}

int main(){
    LinkList L1 = NULL;
    LinkList L2 = NULL;
    InitList(L1);
    IniTList(L2);
    TailInsert(L1);
    TailInsert(L2);
    LinlList L3 = mergeList(L1,L2);
    TranverseLinkList(L3);
}

双链表

指的是构成链表的每个结点中设立两个指针域：

A:一个指向其直接前驱的指针域prior

B:一个指向其后继的指针域next

双向链表结构具有对称性，设p指向双向链中的某一结点，则其对称性可用下式描述:

(p -> prior) -> next = p = (p -> next) -> prior

结点p的存储位置存放在:

其直接前驱结点(p -> prior)的直接后继指针域中，同时也存放在其直接后继结点(p -> next)的直接前驱指针域中。

初始化

void InilList(DLinkList &L){
    L = (DNode *)malloc(sizeof(DLinkList));
    L -> prior = NULL;
    L -> next = NULL;
}

创建双链表

头插法

DLinkList HeadInsert(DLinkList &L){
    InitList(L);
    int x;
    cin>>x;
    while(x != 9999){
        DNode *s = (DNode *)malloc(sizeof(DNode));
        s -> data = x;
        if(L -> next == NULL){
            s -> next =NULL;
            s -> prior = L;
            L -> prior = s;
        }else{
            s -> next = L -> next;
            L -> next -> prior = s;
            s -> prior = L;
            L -> next = s;
        }
        cin >> x;
    }
    return L;
}

尾插法

DLinkList TailInsert(DLinkList &L){
    InitList;
    DNode *s,*r = *L;
    int x;
    cin>>x;
    while(x != 9999){
        s = (DNode *)malloc(sizeof(DNode));
        s -> data = x;
        s -> next = NULL;
        s -> prior = r;
        r -> next = s;
        r = s;
        cin >> x;
    }
    return L;
}

插入操作

//将x插入到双链表L中*p结点的下一个结点
void Insert(DLinkList &L, DNode *p,int x){
    DNode *s = (DNode *)malloc(sizeof(DNode));
    s -> data = x;
    s -> next = p -> next;  //1
    p -> next -> prior = s;  //2
    s -> prior = p;  //3
    p -> next = s;  //4    
}  //插入语句不是只有这一种顺序，但必须保证1和2是要再4之前，否则*P的后继结点的指针就会丢掉，导致插入失败。

遍历操作

void PrintList(DLinkList L){
    DNode *p = L -> next;
    while(p){
        cout << p -> data << " ";
       p = p ->next;
    }
    cout << endl
}

求长度

int Length(DLinkList L){
    DNode *p = L -> next;
    int len = 0;
    while(p){
        len++;
        p = p -> next;
    }
    return len;
}

查找值

DNode *LcoateElem(DLinkList L, int x){
    DNode *p = L -> next;
    while(p && p -> next != x){
        p = p -> next;
    }
    return p;
}

删除操作

void Delete(DLinkList &L,int i){
    if(i < 1 || i > length(L)){
        cout <<"delete failed: index is wrong." << endl;
        return;
    }
    DNode *p = GetElem(L ,i-1);
    DNode *q = p -> next;
    p -> next = q -> next;
    q -> next -> prior = p;
    free(q);
}

循环链表

循环链表对于其他的链表的区别主要在判断是否为空链表和链表结尾上：

判断是否为空链表head -> next = head

判断是否为表尾结点p -> next = head