首页 > 其他分享 >71.线性表14道题目--以偏概全

71.线性表14道题目--以偏概全

时间:2024-11-25 09:55:28浏览次数:8  
标签:结点 return LNode -- next 71 NULL data 线性表

之前总结过有关线性表的知识点了 https://www.cnblogs.com/gaodiyuanjin/p/18408773
现在回答那一句话了 来总结一些题目 我认为这几道题目很基础 掌握后
便可以偏概全的应对所有变形题目

顺序表(顺序存储):

1.从顺序表中删除具有最小值(最大值)的元素由函数返回被删除元素的值 空出的位置由最后一个元素填补
若顺序表为空 则显示错误
bool Del_Min(SqList &L,Elemtype &e)
if(L.length==0)
    return false;
e=L.data[0];
int pos=0;
for(int i=1;i<L.length;i++)
    if(L.data[i]<e){
        e=L.data[i];
        pos=i;
    }
    L.data[pos]=L.data[L.length-1];
    L.length--;
    return true;
2.设计一个算法 将顺序表L的所有元素逆置
void  Reverse(SqList &L,ElemType *start,ElemType* end){
    start=0;
    end=L.length-1;
    ElemType temp;
    while(start==end){
        temp=L.data[start];
        L.data[start]=L.data[end];
        L.data[end]=temp;
        start++;
        end--;
    }
}
高效性:
void  Reverse(SqList &L){
    // 高效性实现 只扫描前半部分元素和后半部分元素交换
    ElemType temp;
   for(int i=0;i<L.length/2;i++){
       temp=L.data[i];
       L.data[i]=L.data[L.length-i-1];
       L.data[L.length-i-1]=temp;
   }
}
3.在第i个位置插入一个新元素e 其后元素向后移动一个位置
bool ListInsert(SqList &L,int i,ElemType e){
    //i的范围有效 L.length+1 即位序末尾之前
    if(i<1||i>L.length+1)
        return false;
    //插满了
    if(L.length>=MaxSize)
        return false;
    for(int j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}
4.将两个有序顺序表合并成一个新的有序顺序表
bool Merge(SeqList A,SeqList B,SeqList &C){
    if(A.length+B.length>C.maxSize)
            return false;
    int i=0,j=0,k=0;
    while(i<A.length&&j<B.length){
        if(A.data[i]<=B.data[j])
            C.data[k++]=A.data[i++];
        else
            C.data[k++]=B.data[j++];
    }
    //如果表还有剩下的部分
    while(i<A.length)
        C.data[k++]=A.data[i++];
    while(j<B.length)
        C.data[k++]=B.data[j++];
    C.length=k;
    return true;
}

链表(链式存储):

(有头结点和无头结点)

1.求单链表表长度操作
//带头结点
int Length(LinkList L){
    int len=0;
    LNode *p=L->next;
    while (p!=NULL){
        p=p->next;
        len++;
    }
    return len;
}
//不带头结点
int Length(LinkList L){
    int len=0;
    LNode *p=L;
    while (p->next!=NULL){
        p=p->next;
        len++;
    }
    return len;
}
2.在第i个位置插入一个值为e的新结点
//后插操作 找到插入位置的前驱 然后再其后面插入新结点
bool ListInsert(linkList &L,int i,ElemType e){
//若无头结点 判断插入位置是否为1的位置
进行特殊处理 将头指针L指向新的首结点
   if (i == 1) {
     LNode *s = (LNode *)malloc(sizeof(LNode));
     s->data = e;
     s->next = L;
     L = s;  // 更新头指针
     return true;
}
    LNode *p=L;
    //找到插入位置i的前驱结点
    int j=0;
    while(p!=NULL&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    LNode *s=(LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}
3.删除单链表第i个结点
bool ListDelete(LinkList &L,int i,ElemType &e){
    //无头结点时 判断删除的是不是首结点 若是特殊处理 将头指针L指向新的首结点
    if (i == 1) {
        LNode *q = L;
        e = q->data;
        L = L->next;  // 更新头指针
        free(q);
        return true;
}
LNode *p=L;
    int j=0;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL||p->next=NULL)
        return false;
    LNode *q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;
}
4.(带头结点)删除单链表给定值为e(设唯一)的结点
bool Delete(LinkList L, ElemType e) {
    LNode *p = L;
    //以p->next等于e为条件 找到了待删结点的前驱p
    while (p->next != NULL && p->next->data != e)
        p = p->next;
    LNode *q = p->next;
    p->next = q->next;
    free(q);
    return true;
}
5.(带头结点)删除单链表L中一个最小值(最大值)结点的算法
bool Delete(LinkList L){
    LNode *p = L;
    LNode *tmep=L->next;
    LNode *q=L; //记录最小值结点的前驱
    while(p->next!=NULL){
        //这里的p是一直向后加的前驱
        if(temp->data > p->next->data){
            temp=p->next; //temp等于最小值结点
            q=p;
        }
        p=p->next;
    }
    q->next=temp->next;
    free(temp);
    return true;
}
6.(带头结点)删除单链表中所有值为e(不唯一)的结点
bool Delete(LinkList L,ElemType e){
    //p等于e时的前驱pre q用于指向被删结点
    LNode *p = L->next,*pre=L,*q;
    while(p!=NULL){
        if(p->data==e){
            q=p;
            p=p->next;
            pre->next=p;
            free(q);
        } else{
            //将pre和后移 p用于判断其值是否等于e pre永远指向p的前驱
            pre=p;
            p=p->next;
        }
    }
    return true;
}
7.(带头结点)将单链表逆置的算法
bool Reverse(LinkList L) {
    if (L == NULL || L->next == NULL) {
        return false; 
    }
    LNode *prev = NULL;
    LNode *p = L->next;
    LNode *next = NULL;
    while (p != NULL) {
        next = p->next; 
        p->next = prev; 
        prev = p;      
        p = next;       
    }
    L->next = prev;
    return true;
}
8.(带头结点)将单链表L2链接到L1的末尾 释放掉L2的头结点
bool Merge(LinkList L1, LinkList L1) {
    if (L2 == NULL) {
        return false; 
    }
    LNode *q = L2;
    L2 = L2->next;
    free(q);
    LNode *p = L1;
    while (p->next != NULL)
        p = p->next;
    p->next = L2;
    return true;
}
9.采用头插法建立单链表
bool HeadInsert(LinkList L1) {
   LNode *s;
   int x;
   L=(LNode*)malloc(siezof(LNode));
   L->next=NULL;
   scanf("%d",&x);
   while(x!=链表长度){
       s=(LNode*)malloc(siezof(LNode));
       s->data=x;
       s->next=L->next;
       L->next=s;
       scanf("%d",&x);
    }
    return true;
}
10.采用尾插法建立单链表
bool TailInsert(LinkList L1) {
    LNode *s, *r = L;
    int x;
    L = (LNode *) malloc(siezof(LNode));
    scanf("%d", &x);
    while (x!=链表长度){
        s = (LNode *) malloc(siezof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return true;
}

标签:结点,return,LNode,--,next,71,NULL,data,线性表
From: https://www.cnblogs.com/gaodiyuanjin/p/18567023

相关文章

  • 垃圾满溢识别摄像机
    垃圾满溢识别摄像机部署在街道社区各个角落的垃圾桶附近,垃圾满溢识别摄像机通过捕捉实时画面判断垃圾桶是否溢满或者垃圾桶附近地面是否有垃圾。一旦系统检测到异常情况,如垃圾桶溢出或地面有垃圾,它将立即触发警报。警报触发后,系统会自动通过无线网络将信息发送到街道社区管理部门......
  • 知道为何有些网站访不需要端口号?说说你对端口的理解?
    有些网站访问不需要端口号是因为它们使用了浏览器默认的端口号,对于HTTP协议是80,对于HTTPS协议是443。当你在浏览器地址栏输入一个网址,例如www.example.com,而没有显式指定端口号时,浏览器会自动尝试连接这些默认端口。如果网站服务器正在这些端口上监听,连接就会建立,而无需......
  • 集成电路的发展史
    集成电路(IC,IntegratedCircuit)的发展史是现代电子技术史中至关重要的一部分,它不仅加速了电子产品的小型化,还推动了计算机、通信、医疗、汽车等行业的创新。以下是集成电路的简要发展历程:1.集成电路的初期(1950年代末-1960年代初)真空管和晶体管的替代:在集成电路发明之前,电子设......
  • 第55篇 如何保证接口的幂等性问题
    1.接口幂等性定义接口幂等性这一概念源于数学,原意是指一个操作如果连续执行多次所产生的结果与仅执行一次的效果相同,那么我们就称这个操作是幂等的。在互联网领域,特别是在Web服务、API设计和分布式系统中,接口幂等性具有非常重要的意义。具体到HTTP接口或者服务间的API调用,接口幂......
  • 说说你对js包装对象的理解
    在JavaScript中,基本类型(primitivetypes)例如数字、字符串、布尔值、null和undefined,本身并不是对象。然而,为了方便开发者访问属性和方法,JavaScript提供了一种机制,当我们试图访问基本类型的属性或方法时,它会自动创建一个对应的包装对象(wrapperobject)。这个包装对象是临时的......
  • 日常API之图灵聊天机器人
    机器人是什么?可以吃吗?  嗯,他可以和你聊天,不能吃哦。首先需要到www.tuling123.com注册一只KEY,你才能调用机器人API哦 一、布局(控制台程序可以跳过这一步)本文以WPF为示例来讲解。首先我们需要一只聊天界面,大概需要这些组件:“发送”Button一只 TextBox一条  Scrol......
  • 16.迭代器模式设计思想
    16.迭代器模式设计思想目录介绍01.迭代器模式基础1.1迭代器模式由来1.2迭代器模式定义1.3迭代器模式场景1.4迭代器模式思考1.5主要解决的问题02.迭代器模式原理2.1罗列一个场景2.2用例子理解迭代器2.3案例实现过程2.4迭代器实现步骤03.迭代器模式结......
  • 精灵图和base64如何选择呢?
    在前端开发中,精灵图(SpriteSheet)和Base64编码都是常用的优化图片加载的技巧,但它们各有优劣,需要根据具体情况选择。精灵图(SpriteSheet)原理:将多个小图标或图片合并成一张大图,通过CSS的background-position属性来控制显示哪一部分。优点:减少HTTP请求:将多个小图片......
  • 神了!两个高仿 BiliBili 客户端!
    大家好,我是Java陈序员。之前,给大家推荐过一个复刻高仿B站的视频网站。一个基于SpringBoot+Vue复刻高仿B站的视频网站!今天,给大家推荐两个高仿B站客户端的开源项目!关注微信公众号:【Java陈序员】,获取开源项目分享、AI副业分享、超200本经典计算机电子书籍等。react-b......
  • 【NLP高频面题 - LLM架构篇】什么是旋转位置编码(RoPE)?
    【NLP高频面题-LLM架构篇】什么是旋转位置编码(RoPE)?重要性:★★★......