精华内容
下载资源
问答
  • 一个结合链表与数组于一体的高效数据管理类,同时还提供二叉排序及查找功能。
  • 而博主最近看的王道论坛2020的数据结构开篇就有按照逻辑结构和存储结构将各种数据结构进行分类,本文就结合所有知识点充分讲解各个数据结构之间的区别联系。 二、相似概念的线性表区分 在数据结构考试题目中我们...

    一、问题背景

    不管是计算机专业的考研初试还是工作面试,数据结构都是很重要的课程。而博主最近看的王道论坛2020的数据结构开篇就有按照逻辑结构和存储结构将各种数据结构进行分类,本文就结合所有知识点充分讲解各个数据结构之间的区别与联系。

    二、相似概念的线性表区分

    在数据结构考试题目中我们总是要区分这三个概念:线性表顺序表有序表链表,甚至还有线性表的其他概念。
    下图便是博主在结合王道论坛数据结构书本上以及网络上的相关线性表的概念做出的思维导图。
    在这里插入图片描述

    1.线性表

    线性表是具有相同特性的数据元素的一个有限序列。线性表属于逻辑结构中的线性结构,它包括顺序表、链表、栈、队列等。

    2.顺序表

    顺序表是顺序存储结构的线性表,是把线性表中的所有元素按照其逻辑顺序依次存储到计算机存储器中指定位置开始的一块连续的物理地址的空间中。由于顺序表的逻辑地址与其物理地址皆相邻,故称为顺序表。
    编程语言中的数组就是顺序表的一个典型实例。

    3.链表

    链表是链式存储结构的线性表,是用任意一组物理地址来存储数据元素,而数据元素之间的逻辑关系通过指针来表示。所以它的存储结构可以是连续的,也可以不是连续的。
    一般我们说的链表都是不连续的。有一种用数组来表示的特殊链表,叫做静态链表,它的存储结构就是连续的。

    4.有序表

    我们很容易把有序表与顺序表链表相提并论,其实这是错误的。因为顺序表链表是根据线性表的存储结构(顺序或链式)来划分概念的,而有序表是根据线性表的数据元素的数值大小来划分概念,故有序表顺序表链表不是相互独立的,而是内容互相交错的。

    有序表是指表中所有数据元素的数值以递增或递减方式有序排列,是数据元素的数值的有序性。
    有序表只描述元素之间的逻辑关系,故为逻辑结构,因此有序表既可以顺序存储也可以链式存储。

    例如,数组int array[3]=[1,2,3];是顺序存储结构的有序表。因为是数组,所以是顺序存储结构;因为数据元素[1,2,3]是从小到大排列,故是有序表。而单链表1->2->3则是链式存储结构的有序表。由这个例子可见:有序表顺序表链表不是相互独立的,而是内容互相交错的,我们不能把他们相提并论。

    三、逻辑结构与存储结构的区分

    在数据结构的考研真题和计算机笔试中,总有区分逻辑结构与存储结构的题目。
    下图是博主总结的数据结构的三要素:逻辑结构、存储结构(物理结构)、数据运算的思维导图。
    在这里插入图片描述

    先说结论:线性表、有序表是逻辑结构;顺序表,链表是存储结构。

    逻辑结构与存储结构的判定方法:当一个结构(如数组、链表、树、图),在逻辑结构中只有一种定义,而在物理结构中却有两种或多种定义,那么这个结构就属于逻辑结构;相反,当此结构在原有基础上加上了某种限定词(如二叉树->线索二叉树),使得其在物理结构中只有一种定义,那么这个结构就属于物理(存储)结构,或称为数据结构;

    举例1:栈属于什么结构?
    分析:栈在逻辑结构中只能属于线性结构,而在物理结构中它可以使用顺序存储(数组),也可以使用链式存储(链表),所以说栈是一种逻辑结构。

    举例2:线索二叉树属于什么结构?
    分析:首先因为二叉树既可以顺序存储又可链式存储,故可以得到二叉树是一种逻辑结构。但是线索二叉树是二叉树加上限定词线索后的链表结构(不能用顺序存储),也就是说,线索二叉树在计算机内部的只有一种存储结构,所以线索二叉树是物理结构。

    逻辑结构和存储结构的区别点在于:数据的逻辑结构是独立于在计算机中的存储结构的,数据的存储方式有多种不同的选择。例如栈是一种逻辑结构,它可以用顺序存储也可以用链式存储。

    而数据结构是既可以描述逻辑结构又可以描述存储结构和数据运算,必须包含以上三种元素。所以像顺序表、哈希表、单链表都是数据结构。


    本文参考文献:
    [1]线性表,顺序表,链表,数组的区别与联系
    [2]数据结构知识整理4线性表——顺序表、链表、有序表
    [3]有序表
    [4]如何判断某种结构是逻辑结构还是存储结构或数据结构?

    展开全文
  • 之前已经写过单向链表和双向链表的指针实现,这是单向链表数组实现,也称静态实现,即不需要通过new和delete动态管理内存总体指针的实现相似,利用元素所在数组中的位置作为指针next的依据// 用节点数组实现链表的...

    一.之前已经写过单向链表和双向链表的指针实现,这是单向链表的数组实现,也称静态实现,即不需要通过new和delete动态管理内存

    总体与指针的实现相似,利用元素所在数组中的位置作为指针next的依据

    //  用节点数组实现链表的各种操作
    //  与指针实现类似
    #include "list.hpp"
    #include <string>
    #include <sstream>
    #include <assert.h>
    
    list::list() { this->clear(); }
    //  注意在clear中同时对各个成员变量进行了初始化
    //  特别是next的初始化
    list::list(const list& another) { *(this) = another; }
    
    list::~list() {}
    
    list& list::operator=(const list& another) {
      //   直接赋值即可
      // 不需要new内存等问题
      this->clear();
      for (int i = 0; i < MAX_STORAGE; i++) {
        storage[i] = another.storage[i];
      }
      this->head = another.head;
      this->empty_head = another.empty_head;
      this->_size = another._size;
      return *(this);
    }
    
    bool list::empty(void) const { return this->_size == 0; }
    
    list::size_type list::size(void) const { return this->_size; }
    
    std::string list::toString(void) const {
      pointer p = this->head;
      std::string ret;
      while (p != nullpointer) {
        //  将stringstream ss放在while之外,然后使用ss.clear() 无法实现清空的作用
        //  所以用这种方法是最好的
        std::stringstream ss;
        ss << this->storage[p].data;
        ret += ss.str();
        ret += "->";
        p = this->storage[p].next;
      }
      ret += "NULL";
      return ret;
    }
    
    void list::insert(int position, const int& data) {
      //  与指针的实现原理是一样的
      //  首先判断是否能够插入
      //  第一个需要满足的情况是position的范围.
      //  第二个需要满足的情况是 _size不能超过数组最大值
      if (position >= 0 && position <= this->_size) {
        if (this->_size + 1 <= MAX_STORAGE) {
          //  empty_head表示的是数组中没有存入数据的内存所在的数组index
          //  从clear中可知,empty_head实现了数组往下一个一个移动的作用
          pointer freeNode = empty_head;
          empty_head = storage[empty_head].next;
          storage[freeNode].data = data;
          //  position == 0的情况通常需要特殊考虑是因为涉及到head的值的改变
          if (position == 0) {
            storage[freeNode].next = head;
            head = freeNode;
          } else {
            pointer p = head;
            for (int i = 0; i < position - 1; i++) {
              p = storage[p].next;
            }
            storage[freeNode].next = storage[p].next;
            storage[p].next = freeNode;
          }
          this->_size++;
        }
      }
    }
    
    void list::erase(int position) {
      // 判断是否能够进行删除操作
      if (position >= 0 && position < this->_size) {
        if (position == 0) {
          pointer temp = head;
          head = storage[head].next;
          storage[temp].next = empty_head;
          empty_head = temp;
        } else {
          pointer p = head;
          for (int i = 0; i < position - 1; i++) {
            p = storage[p].next;
          }
          pointer temp = storage[p].next;
          assert(storage[p].next != nullpointer);
          // assert函数 如果为假.通过调用obsort终止程序运行
          //  传进去的参数是一个表达式比如, i < 100或者是 p != NULL等等
          storage[p].next = storage[storage[p].next].next;
          storage[temp].next = empty_head;
          empty_head = temp;
        }
        this->_size--;
      }
    }
    
    void list::clear(void) {
      this->head = nullpointer;
      this->_size = 0;
      this->empty_head = 0;
      //  对next的操作
      for (int i = 0; i < MAX_STORAGE - 1; i++) {
        storage[i].next = i + 1;
      }
      //  最后一个数组元素的下一个指向空
      storage[MAX_STORAGE - 1].next = nullpointer;
    }
    
    list& list::sort(void) {
      // 与指针链表的排序相同
      //  首先如果前一个元素比后一个元素要小,则指针分别往下移动
      //  如果前一个元素比后一个元素大,则首先判断fast上的元素是否比head节点中的值小,如果是的话,head中的值需要进行改变
      //  此处单独考虑
      //  如果不是的话,对当前的fast中的值与从head到fast之间的节点一个一个进行比较,并将fast插入到正确的位置
      //  重点是 slow->next = fast->next;
      //        fast->next = pre->next;
      //        pre->next = fast;
      //  注意最后要重新让fast = slow->next;
      //  以便继续进行比较和排序
      if (this->head != nullpointer && this->storage[head].next != nullpointer) {
        pointer slow = head;
        pointer fast = storage[head].next;
        while (fast != nullpointer) {
          if (storage[fast].data >= storage[slow].data) {
            fast = storage[fast].next;
            slow = storage[slow].next;
          } else {
            pointer pre = this->head;
            if (storage[head].data > storage[fast].data) {
              storage[slow].next = storage[fast].next;
              storage[fast].next = this->head;
              this->head = fast;
            } else {
              while (storage[storage[pre].next].data <= storage[fast].data) {
                pre = storage[pre].next;
              }
              storage[slow].next = storage[fast].next;
              storage[fast].next = storage[pre].next;
              storage[pre].next = fast;
            }
            fast = storage[slow].next;
          }
        }
      }
      return *(this);
    }

    注: 一些需要注意的地方已经在代码中直接用注释的方式注明,重点需要理解的是insert, erase, sort和clear四个函数的实现过程,可以通过实例一步步理解,思路会清晰的多,再有是链表问题尽量画图进行理解

    重点:insert函数的理解:insert函数传进去的是一个表达式,对表达式进行判断,如果表达式不正确,则会通过调用obsort函数终止程序的运行

    下面是:list.hpp

    #ifndef LIST_H_
    #define LIST_H_
    #include <string>
    #define MAX_STORAGE 1000
    
    class list{
        typedef int data_type;
        typedef int pointer;
        typedef unsigned int size_type;
        static const pointer nullpointer = -1;
        typedef struct node {
            data_type data;
            pointer next;
            node(const node &another) {
              this->operator=(another);
            }
            node& operator=(const node &another) {
              this->data = another.data;
              this->next = another.next;
            }
            node(data_type data = 0, pointer next = nullpointer) : data(data), next(next) {}
        } node;
        node storage[MAX_STORAGE];
        size_type _size;
        pointer head;
        pointer empty_head;
    
    public:
        list();
        list(const list& another);
        list& operator=(const list&);
        ~list();
    
        // Capacity
        bool empty(void) const;
        size_type size(void) const;
    
        // output
        // list: [1,2,3,4,5]
        // output: 1->2->3->4->5->NULL
        std::string toString(void) const;
    
        void insert(int position, const int& data);
        void erase(int position);
        void clear(void);
        list& sort(void);
    };
    
    #endif // !LIST_H_

    下面是main.cpp测试部分

    #include <string>
    #include "list.hpp"
    
    using std::cin;
    using std::cout;
    using std::endl;
    using std::string;
    
    int main() {
        list li;
    
        int n;
        cin >> n;
    
        for (int i = 0, data, pos; i < n; i++) {
            cin >> pos >> data;
            li.insert(pos, data);
        }
    
        cout << li.toString() << " size: " << li.size() << endl;
    
        list li2(li);
        list li3;
    
        li = li3 = li2 = li;
    
        cout << li.toString() << " size: " << li.size() << endl;
        cout << li2.toString() << " size: " << li2.size() << endl;
        cout << li3.toString() << " size: " << li3.size() << endl;
    
        int m;
        cin >> m;
    
        for (int i = 0, pos; i < m; i++) {
            cin >> pos;
            li.erase(pos);
        }
    
        for (int i = 0, temp; i < m; i++) {
          cin >> temp;
          li.insert(0, temp);
        }
    
        cout << li.toString() << endl;
    
        cout << li.sort().toString() << endl;
        cout << li2.sort().toString() << endl;
        cout << li3.sort().toString() << endl;
    
        return 0;
    }

    下面是测试样例:
    5
    0 2
    1 3
    2 5
    3 6
    2 4
    2->3->4->5->6->NULL size: 5
    2->3->4->5->6->NULL size: 5
    2->3->4->5->6->NULL size: 5
    2->3->4->5->6->NULL size: 5
    1
    1
    1
    1->2->4->5->6->NULL
    1->2->4->5->6->NULL
    2->3->4->5->6->NULL
    2->3->4->5->6->NULL

    展开全文
  • 数组与链表 数组与链表对于每一门编程语言来说都...开发中选择数组还是链表,这就要结合场景和它们各自优缺点. 数组的优缺点 数组的内存是连续, 连续有什么意义,它内存地址是连续的, 比如创建一个new Object[5], 假...

    数组与链表

    数组与链表对于每一门编程语言来说都是重要的数据结构之一。数组是一段内存连续的,有序的元素序列,大小固定,初始化时需要指定可承载的元素个数; 链表是非连续、非顺序的存储结构, 数据元素的顺序是通过指针链接实现的。

    开发中选择数组还是链表,这就要结合场景和它们各自优缺点.

    数组的优缺点

    数组的内存是连续, 连续有什么意义,它内存地址是连续的, 比如创建一个new Object[5], 假如第一个内存地址是init_address, 第二个地址就是init_address + 1。所有数组随机访问很快,访问第某个元素,用初始的地址加上下标就能找到啦, 数组遍历也很快。 数组的大小固定, 数组在元素删除和添加就带来一点麻烦,在实际开发中通常使用数组容器,比如java的ArrayList,ArrayList有个默认数组容量, 为10。 ArrayList.add方法中当添加第11个元素时,需要扩容创建一个新的数组,还需要把原数组的元素复制到新的数组。假如 ArrayList当前有8个元素,当移除第5个元素时,并不是简单把第5个元素设置为null, 还要把第6 - 8 个元素都往前挪移1位。当ArrayList的元素是int等基本类型,会涉及到装箱和拆箱,相对与直接使用Int数组性能会稍微差一点,但是有时方便,牺牲一点性能也可以。

    链表的优缺点

    链表的元素通过指针链接, 故大小是无限,只要不爆内存,不需要像数组那样扩容。链表的添加和删除就相对简单点,下面以单链表为例,添加一个元素,把上一个元素的next指针指向一个新的元素即可; 假如该链表有3个元素,当删除第2个元素时,把第一个元素的next指针指向第3个元素。链表元素遍历相对数组慢一点,而且随机访问第某个元素也相对麻烦,需要遍历。

    链表根据结构通常可以分为:单链表、双向链表、循环链表。

    单链表:

    双向链表:

    循环链表:

    单链表中有环:

    上面图中有个单链表中有环,需要注意一下,在使用单链表时,在遍历过程, 以最后元素的next指针为null作为结束的标志,但是如果出现如图的情况,就会出现死循环。对于链表的代码实现,不多说,可以看java中LinkedList类, LinkedList实现了双向链表。

    栈与队列

    栈是一种操作受限的线性表, 仅允许在一端进行插入和删除运算, 后进者先出,先进者后出。举个形象点的例子,有个硬币大的杯子,往杯子里一个个地放硬币, 所有取硬币只能从顶部一个个取出。(不能倒,杯子用502黏住啦) 这里的硬币就是程序里的元素,而这个杯子就是"栈"。

    怎么实现一个栈?

    上面提到数组和链表都可以实现。以数组实现为例,简单描述一下,压栈(意思是放一个元素)过程只要按顺序依次放到数组的index里,从index=0开始; 数组可以访问任意index的元素,而出栈(意思是取一个元素)只能从顶部出, 所以需要限制数组里元素的访问,取出时只能从装有元素中最大index中取出即可。当然压栈时数组也可能需要扩容,一些细节就不多说啦, java中Stack类就是一个实现栈的例子。

    队列也是一种操作受限的线性表, 只允许在表的一端进行删除操作,而在另一端进行插入操作,先进者先出。来个形象的例子,有个一根玻璃球大的水管, 倾斜着放(假设左边高右边低),在左边不停地放入球,球就会从右边出, 而这水管就可以简单理解为"队列"。队列也可以使用数组或者链表实现。

    栈与队列应用场景

    栈的应用场景很广泛,下面举一些例子:

    • 浏览器的前进和后退可以用栈来实现, 一个标签页是一个栈,在打开一个网压栈,在网页中点一个链接,也就是前进,再压栈,后退对应就是出栈。 浏览器有新建一个标签或者在新的标签里打开页面,就是创建一个新的栈,并把打开链接压栈。

    • 安卓应用的界面前进后退也是,有Activity栈,Fragment栈。

    • 函数调用也可以用栈实现,在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数运行结束的时候,将栈顶复位,正好回到调用函数的作用域内。

    • 表达式求值中应用,比如 4 + (6 - 12 + 2* 2) * 2计算。

    表达式运算过如下图所示:

    队列通常存在不同的类型,比如循环队列,并发队列,阻塞队列等, 不同的队列使用场景有所不同。

    • 阻塞队列, 当队列为空的时候,从队头取数据会被阻塞, 直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作也会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。 阻塞队列通常用在生产者消费者模型中,生产数据和消费数据的速率不一致,如果生产数据速度快一些,消费者处理不过来,就可能会导致数据丢失。这时候我们就可以用阻塞队列来解决。
    • 队列应用在线程池请求排队的场景, 当线程池没有空闲线程时,新的任务请求线程资源,线程池通常会使用队列来存储排队的请求,为什么用队列, 因为队列先进先出,可以比较公平处理排队的请求。如果是使用链表的实现方式,可以实现无限排队的无界队列, 但是可能会导致过多请求排队,造成处理响应时间慢。如果使用数组的实现方式,是有界队列, 当排队请求满了,接下来的请求会被拒绝。所有这两种策略可以看场景使用。

    转载于:https://juejin.im/post/5cbfcfd8e51d456e671c7ddc

    展开全文
  • 本篇目录实现动态数组相关函数的介绍链表链表相关操作 实现动态数组 在往期所有的文章中出现的所有的数组都是静态的,即数组的长度都是固定的,在编写代码的时候手动写入数组的长度,且数组的长度必须是常量,不能是...

    上一篇文章:C语言结构体数组+结构体类型指针+指向结构体数组的指针+typedef类型

    If you have a dream, work at it. If it doesn’t turn out as expected, don’t give up! Try again! Who wants to live and say somewhere, “If only” or “What if?” Stick to what you want and accomplish it. Don’t ever give up! Nothing in the world can take the place of persistence. Talent will not; nothing is more common than unsuccessful men with talent. Education will not; the world is full of educated derelicts. Persistence and determination alone are omnipotent.
    如果你有梦想,那就努力吧。如果结果不尽如人意,不要放弃!再试一次!谁想住在某个地方说“如果”或者“如果呢?”坚持你想要的并完成它。永远不要放弃!世上没有什么能代替坚持。才干不行;没有什么比有才干的不成功的人更常见的了。教育不会;世界上到处都是受过教育的失职者。只有坚持和决心是万能的。

    实现动态数组

    在往期所有的文章中出现的所有的数组都是静态的,即数组的长度都是固定的,在编写代码的时候手动写入数组的长度,且数组的长度必须是常量,不能是变量,即如果写成int n; int a[n],这种写法是不正确的。但是在实际的应用中,很多情况下是无法预测数据的多少的,如果写代码的时候,数组长度分配过少可能会出现长度不够用的情况,如果数组长度太大,就会浪费很多的内存。

    相关函数的介绍

    以下函数均包含在stdlib.h头文件当中,在使用之前不要忘记#include <stdlib.h>

    • malloc()函数,void* malloc(unsigned size)这是一个返回指针值的函数,void*说明这个函数返回值并不指向任何数据类型,所以在使用的时候需要强制数据类型转换,将返回的指针值强制性转换成需要的指针类型。该函数的作用为在内存的动态存储区分配一个长度为size的连续空间申请成功,则返回新分配内存块的起始地址;否则返回NULL
    • calloc()函数,void* calloc(unsigned n, unsigned size),作用为在内存的动态存储区中分配n个连续空间,每一存储空间的长度为size,并且分配后还把存储块里全部初始化为0若申请成功,则返回一个指向被分配内存空间的起始地址的指针若申请不成功,则返回NULL(即0)。它返回的指针值同样是不指向任何数据类型的。和malloc()函数的区别是calloc()函数对分配的存储空间进行初始化。
    • free()函数,void free(void* ptr),这是一个void没有返回值的函数,这里的ptrmalloc()函数或calloc()函数返回的指针值,作用是释放由动态存储分配函数申请得到的整块内存空间ptr为指向要释放空间的首地址释放后不允许再通过该指针去访问已经释放的块,否则可能会引起巨大的错误
    • realloc()函数,void* realloc(void* ptr, unsigned size),作用是更改之前的存储分配,ptr必须是以前通过动态存储分配得到的指针。参数size为现在所需要的空间大小。如果分配失败,返回NULL,同时原来ptr指向存储块的内容不变。如果成功,返回一片能存放大小为size的存储块,并保证该块的内容与原块的一致。如果size小于原块的大小,则内容为原块size范围内的数据;如果新块更大,则原有数据存在新块的前一部分。如果分配成功,原存储块的内容就可能改变了,因此不允许再通过ptr去使用它。

    求任意个数的和

    ——动态数组最经典的案例。使用动态数组实现:先输入一个正整数n,再输入任意n个整数,计算并输出这n个整数的和。
    在这里插入图片描述
    在这里插入图片描述
    exit(0)exit(1)都是退出当前程序返回操作系统的意思,本质上没有区别,任意整数都是可以作为exit()括号里面的参数的,包括负整数在内,例如exit(-10000000000)exit(8)都是一个意思。

    解密一串加密的汉字

    输入一串任意长度的已经加密处理的汉字,从中解读出所要传达的语句,要求使用动态数组实现。加密规则为:从第三个汉字开始读取,每隔四个汉字读取一个汉字。这个规则只有发信息的人和我知道,其他人都不知道,这样就会避免重要的信息泄露出去。加密规则改变,代码也要改变,可以修改代码使加密更加复杂些。
    在这里插入图片描述
    在这里插入图片描述
    特别要注意的问题就是一个汉字占两个字节

    #include <stdio.h>
    #include <stdlib.h> 
    int main()
    {
    	printf("请输入你想要解密的信息:\n"); 
    	char getC;
    	int count = 0;
    	while((getC = getchar()) != '\n')
    		count++;    //用循环统计输入的字节数 
    	char* p;
    	if((p = (char*)malloc(count + 1)) == NULL)
    	{
    		printf("内存申请失败!"); 
    		exit(0); 
    	}     //动态分配内存,字节数加一 
    	printf("请再输入一遍:\n");
    	scanf("%s",p);   //再次输入,将字符串存入分配的内存中 
    	*(p + count) = '\0'; //在字符串的最后加上字符串结束标志 
    	for(char* q = p + 4; *q != '\0'; q++)
    	{
    		if(((q - p - 4) % 10) == 0 || ((q - p - 4) % 10) == 1)
    			printf("%c",*q);
    	}
    	//从第三个汉字开始每隔4个汉字输出内容,注意一个汉字占两个字节 
    	return 0;
    }
    

    链表

    其实链表主要就指针和结构体一个综合运用,只要前面的基础比较牢固,链表是非常简单的。如果觉得链表比较难,主要是指针结构体的基础不够牢固造成的。关于指针与结构体我前面的文章已经写了好多了,而且我已经尽可能写得详细,都是一些简单的例子,先把最简单的东西弄清楚,由简再入繁。所有的知识都没有难的,只有多而繁琐的。大多数人所说的“难”只是因为一些基础还没有打牢固就突然去看一个多而繁琐的东西,猛地一看好多好难产生了畏惧心理,才会去说难,其实则不然,再难的东西,都是由很多简单的东西不断叠加组合在一起的。“世上无难事,只要肯攀登”。注重基础,注重积累。

    关于链表,它是一种常见而重要的动态存储分布的数据结构。链表又分为单向链表和双向链表,本篇博客只讲单向链表。要想建立链表,首先得先定义一个结构体,将数据存储到结构体中。同时在结构体中还要定义一个指向自己本身的一个指针。大概如下:

    struct account
    {
    	char name[10];
    	char gender[10];
    	int money;
    	struct account *next;//定义一个指向本结构体类型的指针
    };
    

    然后使用malloc()函数申请动态存储区内存,申请内存的大小为sizeof(struct account),申请成功后将会返回一个内存地址,将其赋给特定的指针变量。然后再不断地进行申请内存,将返回的内存地址赋给上一个结构体成员的next指针变量,这样每一个结构体当中的数据就被指针连在了一起,所以称之为链表。每次申请得到的内存地址并不是连续的,所以链表在动态存储区中也不连续。每个数据项习惯上称之为结点。第一个节点即头节点,为指向该结构体类型的指针变量head,通常情况下head结点中不存放数据,只作为链表的开始。链表最后一个结点中的next中要存放NULL,表示链表到此结束。对于链表的操作建立链表结点插入删除结点查找数据

    链表的建立与输出

    用一个简单的小例子来简要说明一下建立链表,功能为将一个数组中的十个数据存储到链表中。请看下图代码及详细注释:
    在这里插入图片描述
    在这里插入图片描述
    使用子函数输出:
    在这里插入图片描述
    在这里插入图片描述
    这里只是一个简单的例子,读者可以根据自己对指针和结构体以及链表的理解写出自己的代码,代码也不是固定的,仅作参考

    #include <stdio.h>
    #include <stdlib.h> //使用malloc()函数,包含在该头文件中 
    typedef struct list
    {
    	int data;  //用来存储数据 
    	struct list *next;   //用来指向下一个结点 
    }SLIST;  //typedef为结构体定义一个别名 
    int main()
    {
    	SLIST *head, *p, *q;  //分别定义三个指向该结构体类型的指针
    	//head作为头节点,p作为当前指针,q作为新生成的指针 
    	int a[10] = {1,3,5,9,10,12,14,17,18,22};//十个数据 
    	head = p = (SLIST*)malloc(sizeof(SLIST));//产生头节点 
    	for(int i = 0; i < 10; i++)//for循环10次创建10个结点 
    	{
    		q = (SLIST*)malloc(sizeof(SLIST));//q作为新产生的结点 
    		q -> data = a[i];//将数组中的数据赋给q中的data 
    		p -> next = q;//将当前结点与新产生的结点连接起来 
    		p = q;//将新产生的结点作为当前结点,以备下次循环使用 
    	}
    	p -> next = 0;//将最后一个结点的末尾next赋值0即NULL 
    	//为了验证是否成功,下面将其数据输出 
    	p = head -> next;//将当前结点p从头节点的next开始 
    	do//循环输出 
    	{
    		printf("The data is : %d\n",p -> data);//输出操作 
    		p = p -> next;//将下一个结点地址赋给当前结点,以备下次循环使用 
    	}while(p -> next != NULL);//当p中的next为NULL的时候不再输出 
    	printf("The data is : %d\n",p -> data);//最后一个结点也是有数据的 
    	return 0;
    }
    

    优化一下代码:

    #include <stdio.h>
    #include <stdlib.h> //使用malloc()函数,包含在该头文件中 
    typedef struct list
    {
    	int data;  //用来存储数据 
    	struct list *next;   //用来指向下一个结点 
    }SLIST;  //typedef为结构体定义一个别名 
    void output(SLIST *h)
    {
    	SLIST *p;
    	p = h -> next;
    	while(p!=NULL) 
    	{
    		printf("The data is : %d\n",p -> data);
    		p = p -> next;
    	}
    }
    int main()
    {
    	SLIST *head, *p, *q;  //分别定义三个指向该结构体类型的指针
    	//head作为头节点,p作为当前指针,q作为新生成的指针 
    	int a[10] = {1,3,5,9,10,12,14,17,18,22};//十个数据 
    	head = p = (SLIST*)malloc(sizeof(SLIST));//产生头节点 
    	for(int i = 0; i < 10; i++)//for循环10次创建10个结点 
    	{
    		q = (SLIST*)malloc(sizeof(SLIST));
    		q -> data = a[i]; 
    		p -> next = q; 
    		p = q; 
    	}
    	p -> next = 0;
    	output(head);
    	return 0;
    }
    

    节点插入

    将新产生的结点插入到已有的链表当中,假如已有的链表是按照一定的顺序排列的,那么就要找出需要插入的位置。分为以下几个步骤:

    • 建立新结点,并存入数据
    • 查找位置
    • 调整指针变量中所存储的内存地址,将新结点与链表连在一起

    请看如下代码和详细注释:以下代码仅作参考,读者可以自己尝试写一些不同的代码

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct list{
    	int account;
    	struct list *next;
    }Slist;
    int Size = sizeof(Slist);
    void OutPut(Slist* h)
    {
    	Slist* p = h -> next;
    	while(p != 0)
    	{
    		printf("The account is:%d\n",p -> account);
    		p = p -> next;
    	}
    }
    void Insert(Slist *h, int x)  //插入结点的操作 
    {
    	Slist *p, *q, *t;
    	p = h;
    	q = (Slist*)malloc(Size);
    	if(q == NULL)   //如果内存申请失败应当提示用户 
    	{
    		printf("内存申请失败,请关闭程序");
    		system("pause");    //程序暂停语句
    	}
    	q -> account = x;   //给新结点赋值x
    	while(p != NULL)   //用while循环来找x应当插入哪个位置
    	{
    		if(x>p->account)
    		{
    			t = p;
    			p = p -> next;
    		}
    		else
    			break;
    	}
    	if(p == 0)  //如果p等于零,说明x应当插入最后一个结点
    	{
    		q -> next = 0;
    		t -> next = q;
    	}
    	else   //p不等于NULL,说明插入前面的结点
    	{
    		q -> next = p;
    		t -> next = q;
    	}
    }
    int main()
    {
    	Slist *head, *p, *q;
    	int a[10]=
    	{202000,202001,202002,202003,202004,
    	202005,202007,202008,202009,202010};
    	head = p = (Slist*)malloc(Size);
    	if(head == NULL)   //如果内存申请失败应当提示用户 
    	{
    		printf("内存申请失败,请关闭程序");
    		system("pause");     //程序暂停语句
    	}
    	for(int i = 0; i < 10; i++)   //用for循环将数组里面有序的账户保存到链表 
    	{
    		q = (Slist*)malloc(Size);
    		if(q == NULL)   //如果内存申请失败应当提示用户 
    		{
    		printf("内存申请失败,请关闭程序");
    		system("pause");     //程序暂停语句
    		}
    		q -> account = a[i];
    		p -> next = q;
    		p = q;
    	}
    	p -> next = 0;
    	OutPut(head);
    	int x;   //标准C语言不允许变量定义在代码中间位置,一律定义在开头。但大多数编译器集成了C和C++,所以可以将变量定义在中间位置 
    	printf("请输入一个账户:\n");
    	scanf("%d",&x); 
    	Insert(head, x);   //调用插入链表的函数,将头节点和x的值传进去
    	OutPut(head);   //x插入链表后再输出检验 
    	return 0;
    }
    

    代码调试
    在这里插入图片描述
    在这里插入图片描述
    我是用的是DevCpp编译器,调试代码的时候遇到了问题。代码的逻辑思维是正确的,这个读者应当放心。我的问题是:检验是否将x的值插入到链表时,发现链表中没有x的值,多次调试代码才得到运行的正确结果,不知道是不是编译器的问题。代码是我多次校验的,绝对没有问题。如果读者发现有什么问题,或者调试代码的时候遇到问题,欢迎在评论区讨论。

    删除结点

    • 第一步输入想要删除的数据
    • 第二步在链表中查找想要删除的结点
    • 第三步改变指针的指向,让链表重新连在一起
    • 第四步释放所删除结点的内存

    请看一下代码及详细注释:(仅作参考)

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct list{
    	int account;
    	struct list *next;
    }Slist;
    int Size = sizeof(Slist);
    void OutPut(Slist* h)
    {
    	Slist* p = h -> next;
    	while(p != 0)
    	{
    		printf("The account is:%d\n",p -> account);
    		p = p -> next;
    	}
    }
    void Delete(Slist* h, int x)  //删除结点的函数 
    {
    	Slist *p, *q;
    	p = h;
    	q = p -> next;
    	while(q != NULL)  //while循环找到要删除的结点 
    	{
    		if(q -> account == x)
    		{
    			p -> next = q -> next;    //改变该结点前一个结点next指针的指向 
    			free(q);    //释放该结点的内存 
    			break;    //退出while循环 
    		}
    		else   //本次循环没有找到结点,那就让p = q; 
    		{
    			p = q;
    			q = q -> next;    //改变指针q,进入下一次循环 
    		}
    	}
    } 
    int main()
    {
    	Slist *head, *p, *q;
    	int a[10]=
    	{202000,202001,202002,202003,202004,
    	202005,202007,202008,202009,202010};
    	head = p = (Slist*)malloc(Size);
    	if(head == NULL)
    	{
    		printf("内存申请失败,请关闭程序");
    		system("pause"); 
    	}
    	for(int i = 0; i < 10; i++)   //用for循环将数组里面有序的账户保存到链表 
    	{
    		q = (Slist*)malloc(Size);
    		if(q == NULL)
    		{
    		printf("内存申请失败,请关闭程序");
    		system("pause"); 
    		}
    		q -> account = a[i];
    		p -> next = q;
    		p = q;
    	}
    	p -> next = 0;
    	OutPut(head);
    	int x;   //标准C语言不允许变量定义在代码中间位置,一律定义在开头。但大多数编译器集成了C和C++,所以可以将变量定义在中间位置 
    	printf("请输入想要删除账户:\n");
    	scanf("%d",&x); 
    	Delete(head, x);
    	OutPut(head);   //x插入链表后再输出检验 
    	return 0;
    }
    

    在这里插入图片描述

    查找链表中的数据

    • 输入数据
    • 查找数据
    • 输出数据

    请看一下代码及详细注释:(仅作参考)

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct list{
    	int account;
    	int money;
    	struct list *next;
    }Slist;
    int Size = sizeof(Slist);
    void OutPut(Slist* h)
    {
    	Slist* p = h -> next;
    	while(p != 0)
    	{
    		printf("The account is:%d\n",p -> account);
    		p = p -> next;
    	}
    }
    void Find(Slist *h, int x)
    {
    	Slist *p = h -> next;
    	while(p != NULL)   //用循环来查找 
    	{
    		if(p -> account == x)   //找到后就输出 
    		{
    			printf("该账户目前的资金为:%d",p -> money);
    			return;   //输出后返回主函数 
    		}
    		p = p -> next;   //没有找到就改变p指针的内容,进入下次循环 
    	}
    	printf("没有找到该账户!");  //都循环一遍了没有找到 
    }
    int main()
    {
    	Slist *head, *p, *q;
    	int a[10]=
    	{202000,202001,202002,202003,202004,
    	202005,202007,202008,202009,202010};
    	int b[10]=
    	{1000,37989,78443,329844,2003823,
    	489438,7899,23232,434342,23234324};
    	head = p = (Slist*)malloc(Size);
    	if(head == NULL)
    	{
    		printf("内存申请失败,请关闭程序");
    		system("pause"); 
    	}
    	for(int i = 0; i < 10; i++)   //用for循环将数组里面有序的账户保存到链表 
    	{
    		q = (Slist*)malloc(Size);
    		if(q == NULL)
    		{
    		printf("内存申请失败,请关闭程序");
    		system("pause"); 
    		}
    		q -> account = a[i];
    		q -> money = b[i];
    		p -> next = q;
    		p = q;
    	}
    	p -> next = 0;
    	OutPut(head);
    	int x;   //标准C语言不允许变量定义在代码中间位置,一律定义在开头。但大多数编译器集成了C和C++,所以可以将变量定义在中间位置 
    	printf("请输入想要查找的账户:\n");
    	scanf("%d",&x); 
    	Find(head, x);
    	return 0;
    }
    

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 算法思想:“删除”头结点与链表其他结点的原有联系(即将头结点的指针置空),再逐个插入逆置链表的表头(即“头插”到逆置链表中),使它成为逆置链表的“新”的头结点,如此循环,直至原链表为空。 这是鬼话,看...
  • 理论介绍 数组&amp;...不过,在go语言中数组与切片有一个很大的区别, 数组长度在定义后不可更改,数组声明的时候指定的元素个数,就是此数组添加元素的上限数目。 切片可以动态扩充存放...
  • 这位老哥的这篇文章写的非常好,结合小破站”硬核空间java“up猪的视频一起观看“https://www.bilibili.com/video/av71408100”效果更佳。 概述 文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的...
  • 本系列文章会陆续对 Java 集合框架(Java...因为数组与链表是 Java 集合框架中很多地方都涉及到的知识点,此篇文章作为开头,就先对数组与链表这两种数据结构进行介绍 数组与链表是两种差别较大的数据结构,在内存空...
  • 本篇内容以知识整理为主,会结合萨特吉-萨尼的数据结构书籍和网络上的一些知识整理做一下总结,语言使用c++。 数组 1、定义初始化 数组是有序数据的集合,存储相同类型的数据 定义一维数组:类型名 数组名 [常量...
  • 数据结构-静态链表

    2018-12-21 13:23:54
    静态链表就是把链表与数组结合起来,也就是用数组描述的链表,即称为静态链表。 但是在java和c中这种数据结构是不需要的,它主要用于没有指针的编程语言。 与线性表与数组的区别 首先同样是定义一个头文件在...
  • 链表,二叉树,哈希表,数组

    千次阅读 2017-07-21 18:02:06
    数组:查找快,插入删除麻烦,用于已知的数据... 链表与之相反,删除和插入元素很快,但查找很慢。 二叉排序树就既有链表的好处,也有数组的好处。 在处理大批量的动态的数据是比较有用。前序:根左右中序:左根右后续
  • //链表与数组结合思考 #include<stdio.h> #include<malloc.h> #include<stdlib.h> #define LEN sizeof(struct Student) //Student结构的大小 struct Student *creat(); //...
  • 于是,我写这篇论文——链表与文件的结合使用,并尽自己所能介绍一些比较方便易懂的方法和实例,将它们较好的呈献在大多人面前,以增加大家对链表、指针和文件的理解,提高大家学习C的兴趣。 正文: 用数组存...
  • 主要介绍了Python实现队列的方法,结合实例形式分析了Python基于数组链表实现队列的相关操作技巧相关注意事项,需要的朋友可以参考下
  • 设计可以变更的缓存结构:该结构在构造时确定大小,假设长度 len,且有两个功能: int set(string key,int value):将记录(key,value)插入该结构 ...第1点,set 和 get 的时间复杂度要为O(1),数组虽然
  • 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。 设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为: 看一个实例,下图左...
  • 【nginx源码学习运用】系列博客中的示例代码在csdn的代码托管服务器CODE上,地址https://code.csdn.net/u012819339/nginx_study ,你可以将其自由的下载到本地,或者通过Git来实时获取更新ngx_list_t说是单向链表...
  • 1.块状链表的基本思想 常见的线性表结构修改操作有:再某一位置后插入一...块状链表正好是基于这个思想,将数组链表结合了起来。块状链表整体上看其结构是一个链表链表上每个节点存放着一段数组链表上每个节点...
  • 左神算法课笔记记录,算法的提高还需结合大量的刷题 出发点是,算法学习内容杂且难,整理一份重新还原网课的笔记,当成工具书查阅帮助复习 如果本系列对您有用,求个star〜 笔记阅读传送门 GitHub Pages完整阅读: ...
  • 面试:hashmap

    2021-06-16 21:45:16
    hashmap是一种链表与数组结合的结构,可以看作一个数组,里面的每个元素存储了一个单链表,单链表的长度超过一定的值就转换为树(平衡树),结合了数组与链表的优点 hashmap的重点是hashcode,将key通过hash函数...
  • 引导 今天我们进入链表的学习,我相信大家对链表都很熟悉。链表和数组一样,作为最基础的数据结构。在我们的工作中常常会使用到。但是我们真的了解到数组和链表的区别吗?什么时候使用数组,什么时候使用...链表与...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 464
精华内容 185
关键字:

链表与数组结合