热搜：前端 nest neovim nvim

数据结构复习第一天：线性表

lxf2023-06-16 03:24:30

线性表

逻辑结构

a1-a2-a3-a4-a5-a6-a7-a8-a9;

基本操作和运算拉

存储/物理结构:arrow_right_hook:包括两种：

  • 顺序表（顺序存储）

  • 链表（链式存储）

    • 单链表
    • 双链表
    • 循环链表
    • 静态链表

顺序表

  • 基本操作

    • 初始化
    • 插入
    • 删除
    • 查找

  • 顺序表的实现之静态分配:

    指的是给每个数据分配连续的存储空间,大小是MaxSize * sizeof(ElemType)

    #define MaxSize 10

typedef struct{
    ElemType data[MaxSize];//ElemType *data;
    int length;
}SqList;

    基本操作

    //顺序表的初始化
void InitList(SqList &L){
    L.length = 0;//顺序表初始长度为0；
}

int main(){
    SqList l;
    InitList(l);
    //.....
    return 0;
}

    //插入操作：插入到第i个位置(第i个位置，下标是i-1)
/*
思想：
1.判断插入位置是否合法。
2.判断容量
3.第i个位置下标i-1，所以从最后一个元素开始，依次前移，直到i-1下标

*/
bool ListInsert(SqlList &L,int i,ElemType e){

    if(i < 1 || i > L.length + 1) return false;
    
    if(l.length >= MAxSize) return false;
    
    for(int j = l.length-1;j >= i-1;j--){
        l.data[j+1] = l.data[j];
    }
    l.data[j] = e;
    l.length ++ ;
    
    return true;
}




//插入操作,插入到第i下标位置
bool ListInsert(SqList &l,int i,ElemType e){
    //首先要进行判断，判断要插入的位置是否存在
    if(i < 0 || i > l.length) return false;
    //判断是否已满
    if(l.length >= MaxSize) return false;

    
    for(int j = l.length-1;j >= i;j--) l.data[i+1] = l.data[i];
    
    l.data[i] = e;
    l.length++; 
    
    return true;
}

//删除操作，删除第i个元素
/**
思想：
1.判断要删除的元素是否合法
2.第i个元素下标是i-1，取出来，然后从i-1开始向前移每一个元素，直到最后一个元素的前一个元素
3.长度减一
    **/
bool ListDelete(SqList &l,int i,ElemType &e){
    if(i < 1 || i > l.length) return false;
    
    e = l.data[i-1];
    for(int j = i-1;j < l.length -1;j++){
        l.data[j] = l.data[j + 1];
    }
    //if(i < L->length){  //如果删除位置不在最后位置
    //    for(k = i;k < L->length;k++){
    //        L->elem[k-1] = L->elem[k];
    //    }
    //}
    //L->length--;    //长度减1
    //此操作可以少进行一次循环

    l.length--; 
    return true;  
}

//查找操作：获取第i个元素(其实是用数组存储的元素，直接下标取元素是更方便的，但是写一个查找函数可以自己控制报错)
bool GetElem(SqList &L, int i,ElemType &e){
    if(i < 1 || i > L.length || L.length == 0) return false;
    e = L.data[i-1];
    return true;
}

//在main函数里
int main(){
    SqList l;
    InitList(l);//初始化表
    //.....插入元素省略
    int e = 0;//用e将要删除的元素带回
    ListDetete(l,4,e);
    return 0;
}

  • 顺序表的实现之动态分配

    通过malloc函数动态实现内存的分配

    l.data = (ElemType *)malloc(sizeof(ElemType * InitSize));

    #define InitSize 10;

typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
}SqList;

    //初始化
void InitList(SqList &l){
    l.data = (ElemType *)malloc(sizeof(ElemType) * InitSize );
    l.length = 0;
    l.MaxSize = InitSize;
}

//增加动态数组（指针）的长度
void Increase(SqList &l,int len){
    ElemType *p = l.data;
    /*因为顺序表是一片连续的存储空间，所以每次增加空间，就需要申请原来的长度加上新增的长度的内存空间，而且还要把原来表中的元素复制到新的表空间里*/
    l.data = (ElemType *)malloc(sizeof(ElemType) * (InitSize + len) );
    for(int i = 0;i < l.length;i++){
        l.data[i] = p[i];
    }
    l.MaxSize = l.MaxSize + len;
    free(p);
}

链表

单链表

什么是单链表？它是指：通过一组任意的存储单元（不一定连续）来存储线性表中的数据元素，对于每个结点，除了存放元素自身信息，还要存放一个指向其后继的指针。

操作
  • 初始化
  • 插入
  • 删除
  • 查找
  • 建立
用代码定义一个单链表
struct LNode{
    ElemType data;
    struct LNode *next;//指针指向下一个同为‘结构’数据类型 的节点
};

//增加一个新的节点，在内存中申请一个节点所需的空间，并用指针p指向这个节点
struct LNode *p = (struct LNode *)malloc(sizeof(struct LNode));

typedef关键字用法：

typedef <数据类型> <别名>

有了typedef关键字之后就有了单链表的以下写法:


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

//要表示一个单链表的时，只需要声明头指针L,指向单链表的第一个节点
LinkList L;
初始化
//先定义单链表
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL;
    return true;
}

//判断不带头结点的单链表是否为空
bool Empty(LinkList L){
    if(L == NULL) return true;
    else return false;
}
/***************************************/
//初始化一个单链表(带头节点的)
bool InitList(LinkList &L){
    L = (LinkList)malloc(sizeof(LNode));
    if(L == NULL) return false;//内存未申请成功
    L->next = NULL;
    return true;
}

//判断带头结点的单链表是否为空
bool Empty(LinkList L){
    if(L->next == NULL) return true;
    else return false;
}
插入删除

  • 按位序插入

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

//在第i个位置(角标是i-1)插入元素e,
//此为存在头节点的插入，还有一种没有头节点，只有链表的第一个元素，所以需要单独对i==1进行判断
bool ListInsert(LinkList &L,int i,ElemType e){
    if(i < 1) return false;//i值要合法
    /*
    if(i == 1){  
    LNode *k = (LinkList)malloc(sizeof(LNode));
    k->data = e;
    k->next = L->next;
    L = k;
    }
    */
    //1.声明一个指针指向链表的头节点
    LNode *p = L ->next;
    //2.遍历链表找到第i-1个位置（要插入元素的前一个位置）
    for(int j = 1;p != NULL && j < i-1;j++){
         p = p->next;
    }
    
    if(p == NULL) {
        printf("不存在第i个节点")
        return false;
    }
        
    //3.将元素e插入
    LNode *k = (LinkList)malloc(sizeof(LNode));//向内存申请一个空间
    if(k == NULL) return false;//未申请成功
    k->data = e;
    k->next = p->next;
    
    
    return true;
}

/*指定节点元素的插入*/
bool ListInsert(LinkList &L,ElemType e){
    LinkList p = L;
    
    
    //前插
    //while(p->next->data != e && p->next != NULL){
    //    p = p->next;    
    //}
    //if(p->next == NULL) return false;
    //InsertNextNode(p,e);
    
    //后插
    while(p->data != e && p != NULL){
        p = p->next;    
    }
    if(p == NULL) return false;
    InsertPriortNode(p,e);
    
    return true;
}



//指定节点的后插
bool InsertNextNode(LNode *p,ElemType e){
    if(p == NULL) return false;
    
    LNode *k =(LinkList)malloc(sizeof(LNode));
    if(k == NULL) return false;
    
    k->data = e;
    k->next = p->next;
    p->next = k;
    free(p);
    return true;
}
/*
重点在于前插
指定节点的前插
*/
bool InsertPriorNode(LNode *p,ElemType e){
    if(p == NULL) return false;
    LNode *k = (LinkList)malloc(sizeof(LNode));
    if(k == NULL) return false;
    
    k->next = p->next;
    k->data = p->data;
    
    p->data = e;
    p->next = k;
}

  • 按位序删除

    bool ListDelete(LinkList &L,int i,ElemType &e){
    
    if(i < 1) return false;//i不合法
    LinkList p;
    p = L;
    
    for(int j = 0;p->next != NULL && j < i-1;j++){
        p = p->next;
    }

    if(p->next == NULL) return false;
    
    e = p->next->data;
    p->next = p->next->next;
    
    free(p);
    return true;   
}

  • 指定节点的删除

    bool DeleteNode(LNode *p){
    if(p = NULL) return false;
    
    p->data = p->next->data;
    p->next = p->next->next;
    
   return true;
}
查找

  • 按位查找

    //查找
LNode * GetElem(LinkList L,int i){
    if(i < 0) return NULL;
    LinkList p = L;
    
    for(int j = 0;j < i && p!= NULL;j++){
        p = p->next;
    }
    return p;
}

//按位查找如果实现了，可以将其当成封装好的一个函数，在链表的插入和删除中使用，替换一部分代码，例如：
bool ListInsert(LinkList &L,int i,ElemType e){
    if(i < 1) return false;

    //1.声明一个指针指向链表的头节点
    //2.遍历链表找到第i-1个位置
    LNode *p = GetElem(L,i-1);
    
    if(p == NULL) {
        printf("不存在第i个节点")
        return false;
    }
        
    //3.将元素e插入   
    return InsertNextNode(p,e);
}

  • 按值查找

    LNode *LocateElem(LinkList &L,ElemType e){
    LNode *p = L->next;
    while(p != NULL && p->data != e){
        p = p->next;
    }
    return p;
}

  • 求表长

    int length(LinkList L){
    int len = 0;
    LNode *p = L;
    
    while(p->next != NULL){
        p = p->next;
        len++;
    }
    
    return len;
}
建立

单链表的建立分为尾插法和头插法

  • 尾插法

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


bool InitList(LinkList &L){
    L=(LinkList)malloc(sizeof(LNode));
    if(L == NULL) return false;//如果未成功申请到内存
    L->next = NULL;
    return true;
}

//尾插法建立单链表的过程(有头节点)
LinkList List_TailInsert(LinkList &L){
    InitList(L);
    LNode *p = L;
    int x;
    //while(scanf("%d",x) != EOF){
    //   LNode *s = (LinkList)malloc(sizeof(LNode));
    //    s->data = x;
    //    p->next = s;
    //    p = p->next;//p = s;
    //}
    
    //p->next = NULL;

    while((scanf("%d",&x)) != 1024){
        LNode *k = (LinkList)malloc(sizeof(LNode));
        k->data = x;
        p->next = k;
        p = k;//等价于p = p->next;
    }
    k->next = NULL;
    return L;
}

  • 头插法

    LinkList List_HeadInsert(LinkList &L){
    InitList(L);
    
    int x;
    while((scanf("%d",&x)) != 1024){
        LNode *k = (LinkList)malloc(sizeof(LNode));
        k->data = x;
        k->next = L->next;
        L->next = k;       
    }
    return L;
}

双链表（带头结点的）

  • 定义双链表

    typedef struct DNode{
    ElemType data;
    struct DNode *prior;
    struct DNode *next;
}DNode,*DLinkList;
//双链表存在前驱和后继节点

  • 初始化

    bool InitDLinkList(DLinkList &L){
    L = (DLinkList)malloc(sizeof(DNode));
    if(L == NULL) return false;
    
    L->prior = NULL;
    L->next = NULL;
    return true;
}

//main方法中
int main(){
    DLinkList L;
    InitDLinkList(L);
}

//如何判断双链表是否为空，看其后继是否为空即可

  • 双链表的插入

    此操作实际上执行的是后插操作， 如果遇到了按位序插入，就遍历到第i个节点的前一个节点执行后插操作 如果遇到了要对某一个节点执行前插操作，只需要通过该节点的prior指针，就可以转换为对prior的后插

    //在p节点之后插入k节点,p和k要保证合理，不能为空，如果不能保证就需要在函数内部进行判断
bool InsertDLinkList(DNode *p,DNode *k){
    //现在已知p节点和其前后指针    
    k->next = p->next; 
    k->prior = p;
    
    p->next = k;
    if(p->next != NULL)
       p->next->prior = k;    
}

  • 双链表的删除

    //删除p的后继结点
bool DeleteNextDNode(DNode *p){
    if(p == NULL) return false;//if(!p)
    if(p->next == NULL) reurn false;//if(!p-next)
    
    p->next = p->next->next;
    if(p->next->next != NULL)
        p->next->next->prior = p; 
    
    return true;
}

循环链表

  • 循环单链表

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

//初始化一个循环单链表
bool InitList(LinkList &L){
    L = (LinkList)malloc(sizeof(LNode));
    if(!L) return false;
    
    L->next = L;
    return true;
}
//判断一个单链表是否为空就是判断L->next是否指向自己（L）。
//判断是否是表位节点是判断p->next是否指向L头节点。

  • 循环双链表

    typedef struct DNode{
    ElemType data;
    struct DNode *prior;
    struct DNode *next;
}DNode,*DLinkList;

//初始化
bool InitDLinkList(DLinkList &L){
    L = (DLinkList)malloc(sizeof(DNode));
    if(!L) return false;
    
    L->prior = L;
    L->next = L;
    return true;
}
本网站是一个以CSS、JavaScript、Vue、HTML为核心的前端开发技术网站。我们致力于为广大前端开发者提供专业、全面、实用的前端开发知识和技术支持。 在本网站中，您可以学习到最新的前端开发技术，了解前端开发的最新趋势和最佳实践。我们提供丰富的教程和案例，让您可以快速掌握前端开发的核心技术和流程。 本网站还提供一系列实用的工具和插件，帮助您更加高效地进行前端开发工作。我们提供的工具和插件都经过精心设计和优化，可以帮助您节省时间和精力，提升开发效率。 除此之外，本网站还拥有一个活跃的社区，您可以在社区中与其他前端开发者交流技术、分享经验、解决问题。我们相信，社区的力量可以帮助您更好地成长和进步。 在本网站中，您可以找到您需要的一切前端开发资源，让您成为一名更加优秀的前端开发者。欢迎您加入我们的大家庭，一起探索前端开发的无限可能!

本文是由"秘密武器开发者中心"本站原创整理，所有内容的版权归原作者所有。

相关专题