精华内容
下载资源
问答
  • 链式存储
    2021-04-18 18:27:08

    链式存储:
    将数据元素存储在一组任意的存储单位中,而应附加的指针表示元素之间的逻辑关系,因此得到的存储表示为链式存储。
    存储结构的每个节点都有两部分组成,数据域和指针与其说数据存放元素。本身的数据指针域存放指针。
    数据类型:
    1.原子类型:每一对象仅由单值构成的类型,其值不可分解。
    2.结构类型:每一对象可由若干个成分按某种结构不同可分成若干成分或称分量
    抽象数据类型一般可以由数据对象、数据关系及基本操作三个要素定义
    抽象数据类型可以用以下三元组表示:
    ADT=(D、S、P)
    其中D是数据对象,用数据元素的有限集合表示,S是D上的关系集,用结点间序偶的集合表示,P是对D的基本操作集。

    更多相关内容
  • 队列是限定仅在表尾进行插入,在表头进行删除操作的线性表。包括:初始化、判空、判满、入队、出队、得到队头元素、队列长度、清空、销毁、遍历。修正了一些问题。
  • 编写程序,实现求采用链式存储结构存储的二叉树的树高
  • 二叉树的链式存储 实现二叉树的基本操作:建立、遍历、计算深度、结点数、叶子数等。 输入C,先序创建二叉树,#表示空节点; 输入H:计算二叉树的高度; 输入L:计算二叉树的叶子个数; 输入N:计算二叉树节点总个数...
  • 中国大学MOOC上浙大的《数据结构》课程队列顺序存储&链式存储实现的代码。包括队列创建、入队、出队。
  • 采用链式结构存放二叉树,实现二叉树的创建,实现二叉树的遍历(前序,后序,中序层次遍历),分别求二叉树的叶子结点和结点的数目,二叉树的查找,二叉树的深度。 。
  • 本资源提供源码,采用结构化设计思想,模块化程序设计方法完成对“多项式链式存储并相加的基本操作”的设计,实现了单链表多项式相加的概念特征及单链表多项式链式存储并相加的设计的基本思想和方法的总结。
  • 实现线性表的顺序存储结构、链式存储结构,以及定义在上述结构的基本操作,栈的顺序存储结构、链式存储结构,以及定义在上述结构的基本操作
  • 本篇文章主要介绍用JAVA 实现二叉树,并提供实例.对二叉树数据结构很好的学习实践,有需要的朋友可以参考下
  • 顺序和链式存储的线性表的创建、获取元素、插入和删除元素等基本操作的实现。 题目要求: 输入:一组整型数据A,一组整型数据B 输出:A与B的交集,以及A与B的并集 要求:A和B使用两种存储方式:顺序存储和链式存储
  • 该文档饱含了数据结构课程中关于线性表的十二个基本操作的实现。对于不同的线性表的存储结构,利用C语言分别实现相应的算法
  • 不多说,程序运行的测试结果,以及运行的环境都有说明,同时也对关键部分写有注释,多项式加法,不过如此。
  • 队列的链式存储与实现。采用链式存储的方式实现队列,并实现了一些基本功能,包括创建、销毁、清空、追加、读取等一些常规的操作。
  • 设二叉树采用链式存储结构 , 试设计一个算法计算一棵给定二叉树中叶子结点的数目 #include<stdio h> #include<stdlib h> #define max 10 typedef struct node{ char data; node *lchild*rchild; }Bitree; Bitree *B...
  • 本资源为线性表的链式存储演示效果可执行文件,欢迎下载欣赏。源码请关注公众号“多米学算法”下载。希望能够帮助到你
  • 带头节点的线性表的链式存储实现,实现了带头节点链表的创建,不同功能的插入操作,按位置插入,头插入尾插入。也有按数据,按位置删除链表的功能。压缩包中有可执行文件,也有makefile,在linux下直接make即可生成...
  • 堆栈-链式存储实现.c

    2020-04-12 12:46:14
    中国大学MOOC上浙大的《数据结构》课程堆栈链式存储实现的代码,包括空栈的创建,入栈、出栈等基本操作
  • 线性表的链式存储与实现。采用链式存储的方式实现线性表,并实现了一些基本功能,包括创建、销毁、清空、插入等一些常规的操作。
  • DynaLnkQueue.cpp - 动态链式队列,即队列的动态链式存储实现
  • 欢迎下载 #include<stdio.h> #include<stdlib.h> #define max 10 typedef struct node{ char data; node *lchild*rchild; }Bitree; Bitree *B[max]; Bitree *Creatree){ //建立二叉树 Bitree *T*S;...
  • 基于链式存储结构的协同过滤推荐算法设计与实现.pdf
  • 这套资料是实现了WindowC++中的数据结构的线性表的链式存储
  • 1.二叉树链式存储的定义 首先自己写了个队列类(其实也可以不用); 树节点模板类的定义:data-数据,left-左孩子指针,right-右孩子指针,含参构造函数; 创建结点的函数-GetBTNode()函数 创建一个树节点并分配内存,同时...

    【学习日记】今天学习了二叉树的链式存储和层次遍历以及将顺序存储转换为链式存储


    前言  

    测试环境为Visual Studio2019

    二叉树的链式存储为二叉链表

    leftdata

    right

    二叉链表的结点结构








    一、代码内容







    1.二叉树链式存储的定义

    首先自己写了个队列类(其实也可以不用);

    树节点模板类的定义:data-数据,left-左孩子指针,right-右孩子指针,含参构造函数;

    创建结点的函数-GetBTNode()函数 创建一个树节点并分配内存,同时利用构造函数存储内容.

    代码如下(示例):

    //BTree.h
    #include <queue>
    #include<vector>
    #include<iostream>
    #include<list>
    using namespace std;
    template<class T>
    class Queue
    {
    private:
    
    public:
    	list<T> queueL;
    	Queue() {}
    	~Queue() {}
    	int Size()const { return (queueL.size()); }
    	bool Empty()const { return (queueL.empty()); }
    	const T& Front()const { return queueL.front(); }
    	void Push(const T& item) { queueL.push_back(item); }
    	T Pop() { T item = queueL.front(); queueL.pop_front(); return(item); }
    };
    template<class T>
    class BinaryTreeNode
    {
    public:
    	T data;
    	BinaryTreeNode* left;//指向结点的左孩子
    	BinaryTreeNode* right;//指向结点的右孩子
    	BinaryTreeNode(const T& item, BinaryTreeNode<T>* lp = nullptr, BinaryTreeNode<T>* rp = nullptr) :data(item), left(lp), right(rp) {}
    
    };
    template<class T>
    BinaryTreeNode<T>* GetBTNode(const T& item, BinaryTreeNode<T>* lp = nullptr, BinaryTreeNode<T>* rp = nullptr)//建立一个二叉链表结点的函数
    {
    	BinaryTreeNode<T>* p;
    	p = new BinaryTreeNode<T>(item, lp, rp);
    	if (p == nullptr)
    	{
    		cout << "Memory allcation failure!" << endl; exit(1);
    	}
    	return p;
    	delete p;
    }
    
     
    







    2.层次遍历函数

    层次遍历:从上到下,从左到右.

    因为层次遍历是一层一层进行的,从当前访问的结点结构中不能直接得到下一个要访问的结点,为此引用队列做为存储二叉链表的结点指针的寄存器.

    建队列,根节点入队-----若队列不为空,则从队列中删除一个结点指针(出队)-----输出其数据,并访问该指针指向的结点,(如果存在)其左右孩子指针依次入队-----重复上一步,直至队列为空

    代码如下(示例):

    template<class T>
    void Level(BinaryTreeNode<T>* t)//层次遍历
    {
    	if (t == NULL)
    		return;
    	Queue<const BinaryTreeNode<T>*> Q;
    	Q.Push(t);
    	while (!Q.Empty())
    	{
    		const BinaryTreeNode<T>* p = Q.queueL.front();
    		Q.Pop();
    		cout << p->data;
    		if (p->left)
    			Q.Push(p->left);
    		if (p->right)
    			Q.Push(p->right);
    	}
    }

    3.顺序存储转换为链式存储(非递归算法)

    与层次遍历一样仍需要一个队列充当结点的寄存器

    根据树的定义:根节点为a[i],则左孩子a[2*i+1] 右孩子a[2*i+2];

    1.建队列,利用数组第一个元素(a[0])建立根节点,根节点入队-----2.声明两个树节点指针,一个为parent(父母),一个为child(孩子)-----3.定义一个整型数组下标,初始值为0(int i=0)-----4.队列不为空时时:队头出队,并赋值给parent-----5.如果左孩子( a[2*i+1] )存在,则生成左孩子,并赋值给child同时入队-----6.右孩子操作同左孩子-----7.数组下标加一(i++)-----循环4~6;

    代码如下(示例):

    template<class T>
    BinaryTreeNode<T>* MakeLinked(const vector<T>& L)//非递归算法
    {
    	if (L.size() == 0)
    		return 0;
    	Queue<BinaryTreeNode<T>*> Q;
    	BinaryTreeNode<T> *t= GetBTNode(L[0]);
    	BinaryTreeNode<T>* parent, * child;
    	Q.Push(t);
    	int i = 0,n = L.size();
    	while (!Q.Empty())
    	{
    		parent = Q.Pop();
    		if (2 * i + 1 < n && L[2 * i + 1] != T())//如果左孩子存在
    		{
    			child = GetBTNode(L[2 * i + 1]);//生成左孩子
    			parent->left = child;
    			Q.Push(child);
    		}
    		if (2 * i + 2 < n && L[2 * i + 1] != T())//如果右孩子存在
    		{
    			child = GetBTNode(L[2 * i + 2]); //生成右孩子
    			parent->right = child;
    			Q.Push(child);
    		}
    		i++;
    		while (i< n && L[i] == T())//i是非零元素下标(找到不为空的下标)
    			i++;
    	}
    	return(t);
    }

    二、运行结果

    1.main函数

    用结点法创建了ABCDEF树,以及用顺序存储(vector数组)自己输入了一个树

    并把这两个树层次遍历打印

    //main.cpp
    #include<iostream>
    #include"BTree.h"
    using namespace std;
    int main()
    {
    	vector<char> arr;
    	for (int i = 0; i < 5; ++i)
    	{
    		char a;
    		cin >>a;
    		arr.push_back(a);
    	}
    	BinaryTreeNode<char>* T;
    	BinaryTreeNode<char>* null = nullptr;
    	BinaryTreeNode<char>* fp = GetBTNode('F');
    	BinaryTreeNode<char>* dp = GetBTNode('D', fp);
    	BinaryTreeNode<char>* bp = GetBTNode('B', null, dp);
    	BinaryTreeNode<char>* ep = GetBTNode('E');
    	BinaryTreeNode<char>* cp = GetBTNode('C', null, ep);
    	BinaryTreeNode<char>* ap = GetBTNode('A', bp, cp);
    	T=MakeLinked<char>(arr);
    	Level(T);
    	cout << '\t';
    	Level(ap);
    	return 0;
    }

    2.运行截图 








    总结

    ✔以上就是我今天个人的学习内容,本文仅仅简单介绍了二叉树的层次遍历和存储转化,欢迎各位大佬批评指正。(PS:求大佬教教我怎么写  顺序存储转换为链式存储(递归算法))😊😊

    展开全文
  • 能够更好使初学者掌握数据结构的链式存储的操作 属于模板让初学者能了解并模仿该操作
  • 串的链式存储

    2014-04-21 14:38:53
    串的链式存储和操作算法,有串的链接,串的插入,串的删除
  • 这是一个链式存储结构堆栈的c语言实现程序,实现进栈和出栈
  • 栈_链式存储

    2017-10-22 15:59:27
    该代码实现了栈 的链式存储,包括创建栈 、删除栈 、清空栈 、插入元素、删除元素等API函数
  • 主要介绍了C++中实现队列类链式存储与栈类链式存储的代码示例,通过注释来说明,直接上代码,简单粗暴XD 需要的朋友可以参考下
  • 链式存储 最后一句表明,k2是k1的后继结点,k3是k2的后继结点,k4是k3的后继结点,k5是k4的后继结点,k5是空的表 单链表 typedef int datatype; ```typedef struct link_node{ datatype info; struct link_node ...

    链式存储

    在这里插入图片描述
    最后一句表明,在这里插入图片描述k2是k1的后继结点,k3是k2的后继结点,k4是k3的后继结点,k5是k4的后继结点,k5是空的表

    单链表

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

    typedef int datatype;//简化算法,数据类型用整形表示
    typedef struct link_node{
    datatype info;//整型数据域
    struct link_node *next;//指针域,指向本结点类型指针
    }node;//取名node
    typedef node *linklist;//指向结构体类型的指针取名linklist
    

    建立一个空的单链表

    赋值

    node *init()
    {
    	return NULL;
    }
    
    int main()
    {
    	linklist  head;
    	head=init();
    }
    
    

    传递指针地址

    void init(linklist *p)//*p指向linklist这种类型的指针
    {
    	*p=NULL;//将链表指针赋值为空
    }
    
    int main()
    {
    	linklist head;
    	init(&head);
    }
    

    输出单链表中各个结点的值

    void display(node *head)//也可以是linklist  head
    {
    	node *p;
    	p=head;//初始值指向单链表第一个结点
    	if(!p) printf("/n单链表是空的!")else
    	{
    		printf("\n单链表各个结点值为:")
    		while(p)
    		{
    		printf("%5d",p->info);
    		p=p->next;//p赋值为p的next
    		}
    	}
    	
    }
    

    在这里插入图片描述

    • 时间复杂度O(n)

    在单链表中查找第i个结点

    node *find(node *head,int i)
    {
    	int j=1;
    	node *p=head;
    	if(i<1) return NULL;
    	while (p&&i!=j){
    		p=p->next;
    		j++;
    	}
    	return p;
    }
    

    若i不存在,返回的是空值

    单链表插入

    最前面插入值为x的新结点

    • 申请一个结点的空间,让指针指向他
      p=(linklist)malloc(sizeof(node));
    • p->info=x
    • p->next=headp->next暂时为head
    • head=phead重新指向这个链表
      在这里插入图片描述

    某一个结点后面插入新结点

    • 申请一个结点的空间,让指针指向他
      p=(linklist)malloc(sizeof(node));
    • p->info=x
    • p->next=q->next
    • q->next=p
      在这里插入图片描述

    算法:在单链表第i个结点后插入一个值为x的新结点

    linklist insert(node *head,datatype x,int i)
    {
    	node *p,*q;
    	q=find(head,i);
    	if(!q&&i!=0)//找到的位置不存在或者i不合法
    		printf("找不到%d个结点,不能插入%d",i,x);
    	else{
    	p=(linklist)malloc(sizeof(node));
    	p->info=x
    	}
    	if(i==0){
    	p->next=head;
    	head=p
    	}
    	else{
    	p->next=q->next;
    	q->next=p;
    }
    return head;
    }
    

    头插法建立单链表

    建立单链表

    linklist creatbystack()
    {  linklist  head,s;
        datatype x;
        head=NULL;
        printf("请输入若干整数序列:\n");
        scanf("%d",&x);
        while (x!=0)		/*以0结束输入*/
        {   s=(linklist)malloc(sizeof(node));  /*生成待插入结点*/
            s->info=x;
            s->next=head;			/*将新结点插入到链表最前面*/
            head=s;
            scanf("%d",&x);
        }
        return head;				/*返回建立的单链表*/
    }
    

    输出单链表

    void print(linklist head)
    {   linklist p;
        int i=0;
        p=head;
        printf("List is:\n");
        while(p)
        {
            printf("%5d",p->info);
            p=p->next;
             i++;
    		 if (i%10==0) printf("\n");
        }
        printf("\n");
    }
    

    在这里插入图片描述

    在尾部建立单链表

    关键一步设置一个链尾指针r,每次将新的结点链在r的后面,使其成为新的表尾结点

    linklist creatbyqueue()
    {
        linklist head,r,s;//node *head,*s,*r;
        datatype x;
        head=NULL;r=NULL;//表首和表尾指针为空
        scanf("%d",&x);
        while (x!=0)
        {
             s=(linklist)malloc(sizeof(node));
             s->info=x;
           if(head==NULL) head=s//原链表为空,head指向链表第一个结点
           else r->next=s;//将s指向的结点加到r指向结点的后面
             r=s;
             scanf("%d",&x);
       }
       if(r!=NULL)
        	r->next=NULL;
        return head;
    }
    

    单链表删除

    删除单链表最前面的结点

    • p=head保留删除的结点
      在这里插入图片描述

    • head=p->nexthead指向链表的第二个结点
      在这里插入图片描述

    • 释放删除结点的空间
      在这里插入图片描述

    删除链表非首结点

    • 找到被删除结点的前驱结点
      在这里插入图片描述
    • pre->next=p->next删除p指示结点
      在这里插入图片描述
    • 释放被删除结点空间 free(p)
      在这里插入图片描述

    算法:在单链表中删除一个值为x的结点

    linklist dele(node *head,datatype x)
    {
    node *pre=NULL,*p;//不仅要知道p的位置,还要知道p前面的位置
    if(!head){
    printf("单链表是空的");
    return head;
    }
    p=head;
    while(p&&p->info!=x)//p不为空且查找的值不是x
    //&&条件不能颠倒,否则视为程序非法访问内存
    {
    	pre=p;//pre指向p
    	p=p->next//p往下走
    }
    if(p!=NULL)
    {
    if(!pre)
    	head=head->next//head指向下一个结点
    }else{
    	pre->next=p->next;
    }
    free(p);
    }
    

    若链表有多个x结点,只能删除第一个结点

    链式存储结构优缺点

    在这里插入图片描述

    课后答疑

    • 对下面代码的了解
    typedef int datatype;//简化算法,数据类型用整形表示
    typedef struct link_node{
    datatype info;//整型数据域
    struct link_node *next;//指针域,指向本结点类型指针
    }node;//取名node
    typedef node *linklist;//指向结构体类型的指针取名linklist
    

    node=link_node
    node*=linklist=link_node*指向结构体的指针类型

    • 建立空链表两种代码的理解
      在这里插入图片描述
      node*表示要返回node*定义的指针,那么应该在main函数里面有个专门的变量去接收返回值。所以在函数里面不需要return返回任何值!
      在这里插入图片描述
      这里void表示没有返回值,也就是说函数里面需要返回值,那么我们想要直接更改函数里的值,即main函数会跟着形参改变,我们就该传一个地址(地址传递)。这个时候就该返回return head等等了

    • p=p->next的理解
      假设前两个单元为k1,k2,让p指向k1,那么p->next是在k1中,里面保留了k2的地址

    • 由上可知,链表最后一个值一定要赋值为空

    • 删除链首结点 对head=head->next理解
      在没有头结点的情况下,head就是k1,head->next就是k1->next,即保留k2结点

    • 头插法对链表就地倒置特别注意:前面head=NULL
      为什么呢?因为在头插法中,最先进来的最后输出,当head赋值为空时,第一个进来的s 要s->next=head,即s的next指针域为空。那么当链表输出中,只有遇到空值,链表才结束。

    • 链表结束后,head,linklist定义的pre,p等等都会被自动释放掉,因为这属于动态分配内存,pre,p,head类似局部变量

    • 但是由malloc函数分配的内存,就像k1,k2,k3等,需要free来释放

    • 链表删除,插入,都不改变其他结点的位置,则其时间复杂度和空间复杂度为O(1)

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 113,380
精华内容 45,352
关键字:

链式存储

友情链接: vcanfly_mp3_thief.rar