409数据结构学习强化——常见数据结构定义和算法总结(二)

简介: 409数据结构学习强化——常见数据结构定义和算法总结

2.3.5.删除链表中的重复元素

897f91ea488e437280ebd1fddfc4c064.png

void Delete(LinkList &L) {
    LNode *p = L->next;
    while (p) {
        LNode *post = p->next;    //post指向p的下一个结点
        while (post && post->data == p->data) {    //post存在并且值和p相等时
            LNode *temp = post;    //temp指向post
            post = post->next;    //post向后移动
            p->next = post;    //将p的下一个结点修改为post
            free(temp);
        }
        p = p->next;
    }
}

2.3.6.将两个递增链表合并成一个递减链表31bcee4271af4b03b808c33a52267356.png

void Merge(LinkList &L1, LinkList L2) {
    LNode *p = L1->next, *q = L2->next, *temp;
    L1->next = NULL;    //L1断链
    while (p && q) {
        if (p->data <= q->data) {    //当前p指向的元素更小
            temp = p->next;    //temp指向p的下一个结点
            p->next = L1->next;    //将p用头插法插入L1
            L1->next = p;
            p = temp;    //p指向temp
        } else {    //当前q指向的元素更小
            temp = q->next;
            q->next = L1->next;
            L1->next = q;
            q = temp;
        }
    }//while
    while (p) {    //将剩余节点插入L1
        temp = p->next;
        p->next = L1->next;
        L1->next = p;
        p = temp;
    }
    while (q) {
        temp = q->next;
        q->next = L1->next;
        L1->next = q;
        q = temp;
    }
    return;
}

2.3.7.将两个递增链表合并为一个递增链表

LNode *Merge(LinkList L1, LinkList L2) {
    LNode *p = L1->next, *q = L2->next, *r, *temp;
    LNode *L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    r = L;
    while (p && q) {
        if (p->data <= q->data) {    //当前p指向的结点小于等于q
            temp = p->next;
            r->next = p;    //p尾插法插入L中
            r = p;
            p = temp;
        } else {
            temp = q->next;
            r->next = q;
            r = q;
            q = temp;
        }
    }
    while (p) {    //插入剩余结点
        temp = p->next;
        r->next = p;
        r = p;
        p = temp;
    }
    while (q) {
        temp = q->next;
        r->next = q;
        r = q;
        q = temp;
    }
    r->next = NULL;    //将r的next指针置空
    return L;
}

2.3.8.判断链表是否对称68d0f4f27e6d4417a2c3776c06645b4f.png

bool ans(LinkList L) {
  LNode* post = L->prior, * pre = L->next;    //前后指针
    //表中元素为奇数时,终止条件为两者移动到同一结点
    //表中元素为偶数时,终止条件为两者后指针的next指向前指针
  while (post != pre && post->next != pre) {    
    if (post->data != pre->data) return false;    //前后指针的指针域不相等
    pre = pre->next;    //前指针前移
    post = post->prior;    //后指针后移
  }
    //表对称
  return true;
}
bool ans(LinkList L) {
  LNode* p = L->next;
  int len = 0;    //记录表中的元素个数
  while (p != L) {
    p = p->next;
    len++;
  }
  int a = (int*)malloc(len * sizeof(int));    //定义跟链表结点个数相等的长度的数组
  len = 0;
  p = L->next
  while (p != L) {    //遍历链表,用数组保存链表中每个结点的值
    a[len] = p->next;
    p = p->next;
  }
    //遍历数组,前后指针指向元素的值不相等,返回false
  for (int i = 0, j = len - 1; i < j; i++, j--) {
    if (a[i] != a[j]) return false;
  }
  return true;
}

2.3.9.依次输出链表中结点值最小的元素

da5a120bd343499eb0f1dd383d35b0a1.png

void DeleteMin(LinkList &L) {
    LNode *p = L->next, *ppre = L->next, *min, *minpre;
    while (L->next != L) {
        p = L->next;
        ppre = L;
        int tempMin = INT_MAX;    //当前最小值
        while (p != L) {
            if (p->data < tempMin) {    //当前结点值更小,更新最小结点
                min = p;
                minpre = ppre;
            }    //p向后移动
            ppre = p;
            p = p->next;
        }
        cout << min->data;    //输出最小结点的值
        minpre->next = min->next;    //删除min结点
        free(min);
    }//while
    free(L);    //删除头结点
}

2.3.10.真题a822bd0933d74051bf109284bedcdd31.png

void ans(LinkList L, int k){
    LNode *p = L->link, *q = L->link;
    for (int i = 0; i < k; i++) p = p->link;    //p指针向后移动k个结点
    while (p) {
        p = p->link;
        q = q->link;
    }
    cout << q->data;
}

0d293bb78b334ecf8ee9dfdc7392f538.png

void ans(LinkList str1, LinkList str2) {
  LNode *p = str1->next, *q = str2->next;
  int len1 = 0, len2 = 0;
  while (p) {    //遍历str1,得到str1的长度
    len1++;
    p = p->next;
  }
  while (q) {    //遍历str2,得到str2的长度
    len2++;
    q = q->next;
  }
  int len = abs(len1 - len2);    //得到两表长度之差
  p = str1->next;    //重置pq指向第一个结点
  q = str2->next;
  if (len1 >= len2) {    //长表向前移动,使得两表剩余元素相等
    for (int i = 0; i < len; i++) p = p->next;
  }
  else {
    for (int i = 0; i < len; i++) q = q->next;
  }
  while (p) {    //遍历剩余结点,找到两者指向的第一个共同结点
    if (p == q) return p;
    p = p->next;
    q = q->next;
  }
  return NULL;    //两者没有共同后缀
}

c0f0efeb281542c5863afd80a37ddea1.png

void ans(LinkList &L){
    bool A[n + 1];    //长度为n + 1的数组,用来标记该数是否出现过
    for (int i = 0; i < n + 1; i++) A[i] = false;    //初始化A数组
    LNode *p = head->next, *pre = head;
    while (p) {
        int t = abs(p->data);    //取当前结点值的绝对值
        if (A[t]) {    //该值出现过,删除该结点
            LNode *r = p->next;
            pre->next = r;
            free(p);
            p = r;
        } else {    //该值没有出现过,在数组A中标记该值,p和pre向后移动
            A[t] = true;
            pre = p;
            p = p->next;
        }
    }//while
}

6e9952902c0a498ab760546c23af4047.png

void ans(NODE *L) {
  NODE* p = L->next, *f = L->next, *s = L->next, *q, *t;
  while (f->next->next && f->next) {  //找到前半链的最后一个结点
    f = f->next->next;    //快指针移动两个结点
    s = s->next;    //慢指针移动一个结点
  }
  q = s->next;  //q指向后半链的第一个结点
  s->next = NULL; //前半链后半链断开
  LNode* post = (NODE*)malloc(sizeof(NODE));
  post->next = NULL;
  while (q) { //后半链逆置
    t = q->next;
    q->next = post->next;
    post->next = q;
    q = t;
  }
  q = post->next; //q指向逆置后的后半链的第一个结点
  while (q) {
    r = q->next;  //r指向后半链的下一个结点
    t = p->next;  //t指向前半链下一个插入位置
    q->next = p->next;
    p->next = q;
    q = r;  //重置pq
    p = t;
  }
}

3.栈

3.1.栈的数据结构定义

3.1.1.顺序栈

#define MAXSIZE 100
typedef struct Stack {
    int data[MAXSIZE];
    int top = -1;
}Stack;

3.1.2.链栈

typedef struct LStack {
    int data;
    struct LStack *next;
}SNode, *LStack;

3.2.顺序栈的操作

3.2.1.栈的初始化

void InitStack (Stack &S) {
    S.top = -1;
}

3.2.1.入栈

bool Push(Stack &S, int key) {
    if (S.top == MAXSIZE - 1) return false;    //栈满
    S.data[++top] = key;
    return true;
}

3.2.2.出栈

bool Pop (Stack &S, int &key) {
    if (S.top == -1) return false;    //栈空
    key = S.data[top--];
    return true;
}

3.2.3.判断栈空

bool IsEmpty (Stack S) {
    if (S.top == -1) return true;
    else return false;
}

3.3.链栈的基本操作

3.3.1.初始化

void InitStack (LStack &S) {
    SNode *s = (SNode*)malloc(Sizeof(SNode));
    S->next = NULL;
}

3.3.2.入栈

void Push (LStack &S, int key) {
    SNode *p = (SNode*)malloc(sizeof(SNode));
    p->data = key;
    p->next = S->next;    //头插法
    S->next = p;
}

3.3.3.出栈

bool Pop (LStack &S, int &key) {
    if (S->next == NULL) return false;    //栈空
    SNode *p = S->next;
    key = p->data;    //key保存栈顶元素的值
    S->next = p->next;
    free(p);
}

3.3.4.判断栈空

bool IsEmpty(LStack &S) {
    if (S->next == NULL) return true;
    else return false;
}


相关文章
|
5天前
|
负载均衡 算法
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
59 11
架构学习:7种负载均衡算法策略
|
2月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
2月前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
2月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
283 9
|
2月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
44 1
|
11天前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
127 75
|
11天前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
34 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】

热门文章

最新文章