精华内容
下载资源
问答
  • 本文就介绍了数据结构的基本操作的编程实现,掌握的建立、遍历,求子,定位等基本操作 提示:以下是本篇文章正文内容,下面案例可供参考 一、是什么? 在计算机程序设计中,字符 string 通常是字符序列...



    前言

    本文就介绍了数据结构中串的基本操作的编程实现,掌握串的建立、遍历,求子串,定位等基本操作


    提示:以下是本篇文章正文内容,下面案例可供参考
    有更简洁的代码实现,请移步链接: 数据结构——串的基本操作(C语言,究极简单,完整实现).

    一、串是什么?

    在计算机程序设计中,字符串 string 通常是字符序列,要么是文字常量,要么是某种变量。后者可能允许其元素发生突变,长度改变,或者是固定的(在创建之后)。字符串通常被认为是一种数据类型,通常作为字节(或字)的数组数据结构来实现,它存储了一系列元素,通常是使用一些字符编码的字符。字符串还可以用来表示更一般的数组或其他序列(或列表)数据类型和结构。

    根据所使用的编程语言和精确的数据类型,声明为字符串的变量可能会导致内存中的存储被静态地分配给预先确定的最大长度,或者可以使用动态分配来容纳可变数量的元素。

    当一个字符串在源代码中出现时,它被称为字符串文字或匿名字符串。

    在数学逻辑和理论计算机科学中使用的正式语言中,string 是由一个叫做字母表的集合所选择的有限的符号序列。
    串的实现形式有两种,堆分配和块链存储,本文讲述块链存储

    二、该如何理解串?

    串 sting,一般又可以被称作字符串,是由0个或则多个字符组成的有限序列。一般我们用S = “a1 a2 a3…an” 来表示,其中S 是串的名字,双引号或则单引号作为串的定界符用来表示串的内容即串值,ai (0<= i <= n) 则代表串中的单个元素,n表示穿的个数即串中有几个字符,当n 为0时,该串被称为空串(null string),用双引号“”来表示,符号记为Ф。

    注,空白串(blank string)和空串的区别,空白串是由一个或多个空格组成的串。
    在JAVA中,String有着更深层次的理解,本文不做过多叙述

    三、各类串的形式

    子串(subString):串中任意几个连续的字符组成的子序列即为该串的子串

    主串:相应地,包含该子串的串称为主串

    子串的位置(index):子串在主串中首次出现时,该子串的首字符对应在主串中的序号,即为子串在主串中的位置。

    这里有一个很经典的例子用来辅助说明。例如,设A和B分别为 A=‘This is a string’ B=‘is’ 则B是A的子串,A为主串。B在A中出现了两次,其中首次出现所对应的主串位置是3。因此,称B在A中的位置为3。 特别地,空串是任意串的子串,任意串是其自身的子串。

    连接 (concatenation):连接是一个重要的二进制操作。对于任意两个主串中的子串s和t,它们的连接根据放置s和t 的前后顺序来定符号序列。例如,子串s = love,t = hug,那么st 就是lovehug,ts 就是huglove。

    前缀和后缀 prefixes and suffixes:字符串s 可以说是t 的前缀,如果存在一个字符串u 满足条件t =su。如果u 是非空的,那么可以说s 是t 的一个合适的前缀;相应地,串s 可以说t 的后缀如果存在一个串u 满足条件t=us。如果u 是非空的,s 可以说是t 的一个合适的后缀。前缀和后缀可以说是t 的子串。

    旋转:串s = uv 可以被说成t 的旋转如果t = vu. 举个例子,当u = 00110, v = 01的时候,串0011001 是0100110 的旋转。

    逆转:串的逆转就是具有相同符号单顺序相反的字符串。例如,如果s=abc(a、b和c是字母表中符号),那么s 的逆转就是cba。一个与自身相反的字符串(例如,s=madam,逆转还是madam)被称为回文 palindrome,它还包括空字符串和所有长度为1的字符串。

    四、串的实现

    1.串的实现

    1.1 引入库以及设置结构体

    #include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    #define CHUNKSIZE 80
    
    typedef struct 
    {
    	char *ch;
    	int length;
    }HString;
    

    1.2初始化串

    int StrAssign(HString &T,char *chars)//生成一个其值等于串常量chars的T 
    {
    //	if(T.ch) free(T.ch);
    	int i,n;char *c;
    	for(i=0,c=chars;*c;++i,++c);
    	if(!i)
    	{
    		T.ch=NULL;
    		T.length=0;
    	}
    	else
    	{
    		if(!(T.ch=(char *)malloc(i*sizeof(char))))
    			return -1;
    		for(n=0;n<=i-1;n++)
    		{
    			T.ch[n]=chars[n];
    			T.length=i;
    		}
    	}
    	return 1;
    }
    

    1.3求子串的功能实现

     int SubString(HString &Sub,HString S,int pos,int len)//求子串 
     {
     	int n; 
     	if(pos<0||pos>S.length||len<0||len>S.length-pos+1)
     	{
     		 		return 0;
    	 }
    //	if(Sub.ch) free(Sub.ch);
    	if(!len)
    		{
    			Sub.ch=NULL;
    			Sub.length=0;
    		 } 
    	else
    		{
    			Sub.ch=(char *)	malloc(len * sizeof(char));
    			for(int n=0;n<=len-1;n++)
    			{
    				Sub.ch[n]=S.ch[pos+n-1];
    			}
    			Sub.length=len;
    		}
    	return 1;
     }
    

    1.4两串比较的功能实现

     int StrCompare(HString S,HString T)//若S>T,则返回值>0; 若S=T,则返回值0;若S<T,则返回值<0 
     {
     	for(int i=0;i<S.length&&i<T.length;i++)
     	{
     		if(S.ch[i]!=T.ch[i])
     			return S.ch[i]-T.ch[i];
    		else
    			  return S.length-T.length;
    	 }	
     }
    

    1.5定位功能

    int Index(HString S,HString T,int pos)
    {
    	int i=pos,j=0;
    	while(i<S.length&&j<T.length)
    	{
    		if(S.ch[i]==T.ch[j])
    		{
    			++i;++j;
    		}
    		else
    		{
    			i=i-j+1;
    			j=0;
    		}
    		
    	}
    	if(j>=T.length) return i-T.length;
    	else return 0;
    }
    

    1.6求串的长度功能

    int StrLength(HString T)//求串长 
    {
    	return T.length;
     } 
    

    1.7串的输出功能

    void StrPrint(HString T)
    {
    	int i;
    	for(i=0;i<T.length;i++)
    	{
    		printf("%c",T.ch[i]);
    	}
    } 
    

    1.8主函数实现上述全部功能

    void Show()
    {
    	printf("请输入想选择的指令:\n");
    	printf("1.显示串\n");
    	printf("2.显示串长\n");
    	printf("3.两串做比较\n");
    	printf("4.求子串\n");
    	printf("5.定位\n");
    	printf("0.退出\n");
    	printf("-------------------\n");
    }
    
    int main()
    {
    	int n;
    	Show();	
    	scanf("%d",&n);	
    	char s[15]="qwertasdfzxc";		
    	HString S;
    	StrAssign(S,s);	
    	char t[5]="asdf";
    	HString T;
    	StrAssign(T,t);	
    	HString Sub;
    	while(n!=0)
    	{
    		switch(n)
    		{
    			case 1:	
    					printf("第一个串为:%s\n",S.ch);
    					printf("第二个串为:%s\n",T.ch);break;
    			case 2: printf("第一条串长:%d\n",StrLength(S));
    					printf("第二条串长:%d\n",StrLength(T));break;
    			case 3: 	int n ;
    						n=StrCompare(S,T);
    						if(n!=0)
    							if(n>0)
    								printf("前面长\n");
    							else
    								printf("后面长\n");
    						else
    							printf("一样长\n");break; 
    			case 4:printf("请输入你想取的位置及长度:\t");
    					int j,l;
    					scanf("%d %d",&j,&l);
    					SubString(Sub,S,j,l);
    					StrPrint(Sub);break;
    			case 5: int k;
    					printf("输入查询的位置:\n");
    					scanf("%d",&k);
    					int x=Index(S,T,k);
    				    printf("定位到的位置为:%d",x);break;
    		 } 
    			printf("\n");
    			Show();
    			scanf("%d", &n);
    		}
    	return 0;
     } 
    

    总结

    以上就是今天要讲的内容,本文仅仅简单介绍了串基础结构以及基础功能的相应实现。
    希望对你有所帮助
    展开全文
  • 本文就介绍了数据结构的基本操作的编程实现,掌握的建立、遍历,求子,定位等基本操作 提示:以下是本篇文章正文内容,下面案例可供参考 有更简洁的代码实现,请移步 一、是什么? 在计算机程序设计中,...



    前言

    本文就介绍了数据结构中串的基本操作的编程实现,掌握串的建立、遍历,求子串,定位等基本操作


    提示:以下是本篇文章正文内容,下面案例可供参考
    有更简洁的代码实现,请移步

    一、串是什么?

    在计算机程序设计中,字符串 string 通常是字符序列,要么是文字常量,要么是某种变量。后者可能允许其元素发生突变,长度改变,或者是固定的(在创建之后)。字符串通常被认为是一种数据类型,通常作为字节(或字)的数组数据结构来实现,它存储了一系列元素,通常是使用一些字符编码的字符。字符串还可以用来表示更一般的数组或其他序列(或列表)数据类型和结构。

    根据所使用的编程语言和精确的数据类型,声明为字符串的变量可能会导致内存中的存储被静态地分配给预先确定的最大长度,或者可以使用动态分配来容纳可变数量的元素。

    当一个字符串在源代码中出现时,它被称为字符串文字或匿名字符串。

    在数学逻辑和理论计算机科学中使用的正式语言中,string 是由一个叫做字母表的集合所选择的有限的符号序列。
    串的实现形式有两种,堆分配和块链存储,本文讲述块链存储

    二、该如何理解串?

    串 sting,一般又可以被称作字符串,是由0个或则多个字符组成的有限序列。一般我们用S = “a1 a2 a3…an” 来表示,其中S 是串的名字,双引号或则单引号作为串的定界符用来表示串的内容即串值,ai (0<= i <= n) 则代表串中的单个元素,n表示穿的个数即串中有几个字符,当n 为0时,该串被称为空串(null string),用双引号“”来表示,符号记为Ф。

    注,空白串(blank string)和空串的区别,空白串是由一个或多个空格组成的串。
    在JAVA中,String有着更深层次的理解,本文不做过多叙述

    三、各类串的形式

    子串(subString):串中任意几个连续的字符组成的子序列即为该串的子串

    主串:相应地,包含该子串的串称为主串

    子串的位置(index):子串在主串中首次出现时,该子串的首字符对应在主串中的序号,即为子串在主串中的位置。

    这里有一个很经典的例子用来辅助说明。例如,设A和B分别为 A=‘This is a string’ B=‘is’ 则B是A的子串,A为主串。B在A中出现了两次,其中首次出现所对应的主串位置是3。因此,称B在A中的位置为3。 特别地,空串是任意串的子串,任意串是其自身的子串。

    连接 (concatenation):连接是一个重要的二进制操作。对于任意两个主串中的子串s和t,它们的连接根据放置s和t 的前后顺序来定符号序列。例如,子串s = love,t = hug,那么st 就是lovehug,ts 就是huglove。

    前缀和后缀 prefixes and suffixes:字符串s 可以说是t 的前缀,如果存在一个字符串u 满足条件t =su。如果u 是非空的,那么可以说s 是t 的一个合适的前缀;相应地,串s 可以说t 的后缀如果存在一个串u 满足条件t=us。如果u 是非空的,s 可以说是t 的一个合适的后缀。前缀和后缀可以说是t 的子串。

    旋转:串s = uv 可以被说成t 的旋转如果t = vu. 举个例子,当u = 00110, v = 01的时候,串0011001 是0100110 的旋转。

    逆转:串的逆转就是具有相同符号单顺序相反的字符串。例如,如果s=abc(a、b和c是字母表中符号),那么s 的逆转就是cba。一个与自身相反的字符串(例如,s=madam,逆转还是madam)被称为回文 palindrome,它还包括空字符串和所有长度为1的字符串。

    四、串的实现

    1.串的实现

    1.1 引入库以及设置结构体

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<malloc.h>
    typedef struct{
    	char *ch;
    	int length;
    }BBT;//定义一个串的结构体 
    

    1.2初始化串

    int StrAssign(BBT &T,char *chars){
    	int i ;
    	char *c;
    //	if(T.ch)
    //		free(T.ch);
    	for(i=0,c=chars;*c;i++,c++);
    	if(!i){
    		T.ch=NULL;
    		T.length=0;
    	}//如果所求的串是空串 
    	else{
    		if(!(T.ch=(char*)malloc(i*sizeof(char)))){
    			return -1;
    		}
    		for(int n=0;n<=i-1;n++)
    			T.ch [n]=chars[n];
    		T.length =i;
    		}
    	return 0; 
    }
    

    1.3求子串的功能实现

    //求子串
    int SubString(BBT &Sub,BBT S,int pos ,int len){
    	if (pos<1||pos>S.length ||len<0||len>S.length-pos+1)
    	return 0;
    	if(Sub.ch) free(Sub.ch);
    	if(!len){Sub.ch=NULL;Sub.length=0;}
    	else{
    		Sub.ch=(char*)malloc(len*sizeof(char));
    		for(int j=0,pos;j<len,pos<pos+len-2;j++,pos++){
    			Sub.ch[j]=S.ch[pos];
    		}
    			Sub.length=len; 
    	}
    	return 0;
    }
    

    1.4两串比较的功能实现

    int StrCompare(BBT S,BBT T){
    	for(int i=0;i<S.length && i<T.length ;++i)
    	if(S.ch[i]!=T.ch[i])   return S.ch[i]-T.ch[i];
    	return S.length -T.length ;
    } 
    

    1.5定位功能

    int index(BBT S,BBT T,int pos){
    	int m,n;
    	BBT Sub;
    	if(pos>0){
    		n=StrLength(S);m=StrLength(T);int i=pos;
    		while(i<n-m+1){
    			SubString(Sub,S,i,m);
    			if(StrCompare(Sub,T)!=0) i++;
    		else return i;
    		}
    	}	
    	return 0;
    }
    

    1.6求串的长度功能

    int StrLength(BBT S){
    	return S.length;
    } 
    

    1.7串的输出功能

    void StrPrint(HString T)
    {
    	int i;
    	for(i=0;i<T.length;i++)
    	{
    		printf("%c",T.ch[i]);
    	}
    } 
    

    1.8判断串的是否为空功能

    bool StrClear(BBT &S)
    {
    	if(S.ch)
    	{
    		free(S.ch);
    		S.ch=NULL;
    	}
    	S.length=0;
    	return true;
    }
    

    1.8主函数实现上述全部功能

    int main(){
    	BBT S;
    	char s1[15]="aabbccdssssdff";	
    	StrAssign(S,s1);
    	printf(S.ch);printf("\n");
    	int n=StrLength(S);
    	BBT T;
    	char s2[15]="aabb";
    	StrAssign(T,s2);
    	printf(T.ch);printf("\n");
    //	int q=StrCompare(T,S);
    //	printf("%d\n",q);	
    	printf("%d,%d,%d\n",n,StrLength(T),StrCompare(S,T));
    	printf("%d\n",index(S,T,0));
    	return 0;
    }
    

    总结

    以上就是今天要讲的内容,本文仅仅简单介绍了串基础结构以及基础功能的相应实现。
    希望对你有所帮助
    展开全文
  • Redis的五种数据结构的底层实现原理

    万次阅读 2021-01-31 02:49:22
    Redis的五种数据结构的底层实现原理: 1、String底层实现方式:动态字符sds 或者 long; 2、Hash底层实现方式:压缩列表ziplist 或者 字典dict; 3、List在Redis3.2之前的底层实现方式:压缩列表ziplist 或者 双向...

    一、Redis的两层数据结构简介

    redis的性能高的原因之一是它每种数据结构都是经过专门设计的,并都有一种或多种数据结构来支持,依赖这些灵活的数据结构,来提升读取和写入的性能。如果要了解redis的数据结构,可以从两个不同的层面来讨论它:

    (1)第一个层面,是从使用者的角度,这一层面也是Redis暴露给外部的调用接口,比如:

    • string
    • list
    • hash
    • set
    • sorted set

    (2)第二个层面,是从内部实现的角度,属于更底层的实现,比如:

    • dict
    • sds
    • ziplist
    • quicklist
    • skiplist
    • intset

    本文的重点在于讨论第二个层面:

    • Redis数据结构的内部实现
    • 这两个层面的数据结构之间的关系:Redis如何通过组合第二个层面的各种基础数据结构来实现第一个层面的更高层的数据结构

    在讨论任何一个系统的内部实现的时候,我们都要先明确它的设计原则,这样我们才能更深刻地理解它为什么会进行如此设计的真正意图。在本文接下来的讨论中,我们主要关注以下几点:

    • 存储效率。Redis是专用于存储数据的,它对于计算机资源的主要消耗就在于内存,因此节省内存是它非常非常重要的一个方面。这意味着Redis一定是非常精细地考虑了压缩数据、减少内存碎片等问题。
    • 快速响应时间。与快速响应时间相对的,是高吞吐量。Redis是用于提供在线访问的,对于单个请求的响应时间要求很高,因此,快速响应时间是比高吞吐量更重要的目标。有时候,这两个目标是矛盾的。
    • 单线程。Redis的性能瓶颈不在于CPU资源,而在于内存访问和网络IO。而采用单线程的设计带来的好处是,极大简化了数据结构和算法的实现。相反,Redis通过异步IO和pipelining等机制来实现高速的并发访问。显然,单线程的设计,对于单个请求的快速响应时间也提出了更高的要求。

     

    二、redisObject:两层数据结构的桥梁

    redisObject数据结构详解:http://zhangtielei.com/posts/blog-redis-robj.html

    1、什么是redisObject:

    从Redis的使用者的角度来看,一个Redis节点包含多个database(非cluster模式下默认是16个,cluster模式下只能是1个),而一个database维护了从key space到object space的映射关系。这个映射关系的key是string类型,而value可以是多种数据类型,比如:string, list, hash、set、sorted set等。我们可以看到,key的类型固定是string,而value可能的类型是多个。

    而从Redis内部实现的角度来看,database内的这个映射关系是用一个dict来维护的。dict的key固定用一种数据结构来表达就够了,这就是动态字符串sds。而value则比较复杂,为了在同一个dict内能够存储不同类型的value,这就需要一个通用的数据结构,这个通用的数据结构就是robj,全名是redisObject

    举个例子:

    • 如果value是一个list,那么它的内部存储结构是一个quicklist或者是一个ziplist
    • 如果value是一个string,那么它的内部存储结构一般情况下是一个sds。但如果string类型的value的值是一个数字,那么Redis内部还会把它转成long型来存储,从而减小内存使用。

    所以,一个robj既能表示一个sds,也能表示一个quicklist,甚至还能表示一个long型。

    2、redis的数据结构定义:(基于Redis3.2版本)

    /* Object types */
    #define OBJ_STRING 0
    #define OBJ_LIST 1
    #define OBJ_SET 2
    #define OBJ_ZSET 3
    #define OBJ_HASH 4
    
    /* Objects encoding. Some kind of objects like Strings and Hashes can be
     * internally represented in multiple ways. The 'encoding' field of the object
     * is set to one of this fields for this object. */
    #define OBJ_ENCODING_RAW 0     /* Raw representation */
    #define OBJ_ENCODING_INT 1     /* Encoded as integer */
    #define OBJ_ENCODING_HT 2      /* Encoded as hash table */
    #define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
    #define OBJ_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
    #define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
    #define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
    #define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
    #define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
    #define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
    
    #define LRU_BITS 24
    typedef struct redisObject {
        unsigned type:4;
        unsigned encoding:4;
        unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */
        int refcount;
        void *ptr;
    } robj;

    (1)一个robj包含如下5个字段:

    • type: 对象的数据类型。占4个bit。可能的取值有5种:OBJ_STRING, OBJ_LIST, OBJ_SET, OBJ_ZSET, OBJ_HASH,分别对应Redis对外暴露的5种数据结构
    • encoding: 对象的内部表示方式(也可以称为编码)。占4个bit。可能的取值有10种,即前面代码中的10个OBJ_ENCODING_XXX常量。
    • lru: 做LRU替换算法用,占24个bit。这个不是我们这里讨论的重点,暂时忽略。
    • refcount: 引用计数。它允许robj对象在某些情况下被共享。
    • ptr: 数据指针。指向真正的数据。比如,一个代表string的robj,它的ptr可能指向一个sds结构;一个代表list的robj,它的ptr可能指向一个quicklist。

    (2)encoding字段的说明:

    这里特别需要仔细察看的是encoding字段。对于同一个type,还可能对应不同的encoding,这说明同样的一个数据类型,可能存在不同的内部表示方式。而不同的内部表示,在内存占用和查找性能上会有所不同。

    当type = OBJ_STRING的时候,表示这个robj存储的是一个string,这时encoding可以是下面3种中的一种:

    • OBJ_ENCODING_RAW: string采用原生的表示方式,即用sds来表示。
    • OBJ_ENCODING_INT: string采用数字的表示方式,实际上是一个long型。
    • OBJ_ENCODING_EMBSTR: string采用一种特殊的嵌入式的sds来表示。

    当type = OBJ_HASH的时候,表示这个robj存储的是一个hash,这时encoding可以是下面2种中的一种:

    • OBJ_ENCODING_HT: hash采用一个dict来表示
    • OBJ_ENCODING_ZIPLIST: hash采用一个ziplist来表示

    (3)10种encoding的十种取值:

    • OBJ_ENCODING_RAW: 最原生的表示方式。其实只有string类型才会用这个encoding值(表示成sds)。
    • OBJ_ENCODING_INT: 表示成数字。实际用long表示。
    • OBJ_ENCODING_HT: 表示成dict。
    • OBJ_ENCODING_ZIPMAP: 是个旧的表示方式,已不再用。在小于Redis 2.6的版本中才有。
    • OBJ_ENCODING_LINKEDLIST: 也是个旧的表示方式,已不再用。
    • OBJ_ENCODING_ZIPLIST: 表示成ziplist。
    • OBJ_ENCODING_INTSET: 表示成intset。用于set数据结构。
    • OBJ_ENCODING_SKIPLIST: 表示成skiplist。用于sorted set数据结构。
    • OBJ_ENCODING_EMBSTR: 表示成一种特殊的嵌入式的sds。
    • OBJ_ENCODING_QUICKLIST: 表示成quicklist。用于list数据结构。

    3、robj的作用:

    • redisObject就是Redis对外暴露的第一层面的数据结构:string, list, hash, set, sorted set,而每一种数据结构的底层实现所对应的是哪些第二层面的数据结构(dict, sds, ziplist, quicklist, skiplist等),则通过不同的encoding来区分。可以说,robj是联结两个层面的数据结构的桥梁。
    • 为多种数据类型提供一种统一的表示方式。
    • 允许同一类型的数据采用不同的内部表示,从而在某些情况下尽量节省内存。
    • 支持对象共享和引用计数。当对象被共享的时候,只占用一份内存拷贝,进一步节省内存。

     

    三、第一层数据结构

    1、String:

    String数据结构是最简单的数据类型。一般用于复杂的计数功能的缓存:微博数,粉丝数等。

    (1)底层实现方式:动态字符串sds 或者 long

    String的内部存储结构一般是sds(Simple Dynamic String,可以动态扩展内存),但是如果一个String类型的value的值是数字,那么Redis内部会把它转成long类型来存储,从而减少内存的使用。

    • 确切地说,String在Redis中是用一个robj来表示的。
    • 用来表示String的robj可能编码成3种内部表示:OBJ_ENCODING_RAW,OBJ_ENCODING_EMBSTR,OBJ_ENCODING_INT。其中前两种编码使用的是sds来存储,最后一种OBJ_ENCODING_INT编码直接把string存成了long型。
    • 在对string进行incr, decr等操作的时候,如果它内部是OBJ_ENCODING_INT编码,那么可以直接进行加减操作;如果它内部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR编码,那么Redis会先试图把sds存储的字符串转成long型,如果能转成功,再进行加减操作。
    • 对一个内部表示成long型的string执行append, setbit, getrange这些命令,针对的仍然是string的值(即十进制表示的字符串),而不是针对内部表示的long型进行操作。比如字符串”32”,如果按照字符数组来解释,它包含两个字符,它们的ASCII码分别是0x33和0x32。当我们执行命令setbit key 7 0的时候,相当于把字符0x33变成了0x32,这样字符串的值就变成了”22”。而如果将字符串”32”按照内部的64位long型来解释,那么它是0x0000000000000020,在这个基础上执行setbit位操作,结果就完全不对了。因此,在这些命令的实现中,会把long型先转成字符串再进行相应的操作。

    2、Hash:

    Hash特别适合用于存储对象,因为一个对象的各个属性,正好对应一个hash结构的各个field,可以方便地操作对象中的某个字段。

    (1)底层实现方式:压缩列表ziplist 或者 字典dict

    当Hash中数据项比较少的情况下,Hash底层才用压缩列表ziplist进行存储数据,随着数据的增加,底层的ziplist就可能会转成dict,具体配置如下:

    hash-max-ziplist-entries 512
    hash-max-ziplist-value 64

    • 当hash中的数据项(即filed-value对)的数目超过512时,也就是ziplist数据项超过1024的时候
    • 当hash中插入的任意一个value的长度超过了64字节的时候

    当满足上面两个条件其中之一的时候,Redis就使用dict字典来实现hash。

    Redis的hash之所以这样设计,是因为当ziplist变得很大的时候,它有如下几个缺点:

    • 每次插入或修改引发的realloc操作会有更大的概率造成内存拷贝,从而降低性能。
    • 一旦发生内存拷贝,内存拷贝的成本也相应增加,因为要拷贝更大的一块数据。
    • 当ziplist数据项过多的时候,在它上面查找指定的数据项就会性能变得很低,因为ziplist上的查找需要进行遍历。

    总之,ziplist本来就设计为各个数据项挨在一起组成连续的内存空间,这种结构并不擅长做修改操作。一旦数据发生改动,就会引发内存realloc,可能导致内存拷贝。

    3、List:

    list 的实现为一个双向链表,经常被用作队列使用,支持在链表两端进行push和pop操作,时间复杂度为O(1);同时也支持在链表中的任意位置的存取操作,但是都需要对list进行遍历,支持反向查找和遍历,时间复杂度为O(n)。

    list是一个能维持数据项先后顺序的列表(各个数据项的先后顺序由插入位置决定),便于在表的两端追加和删除数据,而对于中间位置的存取具有O(N)的时间复杂度。

    list 的应用场景非常多,比如微博的关注列表,粉丝列表,消息列表等功能都可以用Redis的 list 结构来实现。可以利用lrange命令,做基于redis的分页功能。

    (1)Redis3.2之前的底层实现方式:压缩列表ziplist 或者 双向循环链表linkedlist

    当list存储的数据量比较少且同时满足下面两个条件时,list就使用ziplist存储数据:

    • list中保存的每个元素的长度小于 64 字节;
    • 列表中数据个数少于512个。

    当不能同时满足上面两个条件的时候,list就通过双向循环链表linkedlist来实现了

    (2)Redis3.2及之后的底层实现方式:quicklist

    quicklist是一个双向链表,而且是一个基于ziplist的双向链表,quicklist的每个节点都是一个ziplist,结合了双向链表和ziplist的优点

    4、Set:

    set是一个存放不重复值的无序集合,可以做全局去重的功能,提供了判断某个元素是否在set集合内的功能,这个也是list所不能提供的。基于set可以实现交集、并集、差集的操作,计算共同喜好,全部的喜好,自己独有的喜好等功能。

    (1)底层实现方式:有序整数集合intset 或者 字典dict

    当存储的数据同时满足下面这样两个条件的时候,Redis 就采用整数集合intset来实现set这种数据类型:

    • 存储的数据都是整数
    • 存储的数据元素个数小于512个

    当不能同时满足这两个条件的时候,Redis 就使用dict来存储集合中的数据

    5、Sorted Set:

    Sorted set多了一个权重参数score,集合中的元素能够按score进行排列。可以做排行榜应用,取TOP N操作。另外,sorted set可以用来做延时任务。最后一个应用就是可以做范围查找。

    (1)底层实现方式:压缩列表ziplist 或者 zset

    当存储的数据同时满足下面这两个条件的时候,Redis就使用压缩列表ziplist实现sorted set

    • 集合中每个数据的大小都要小于 64 字节
    • 元素个数要小于 128 个,也就是ziplist数据项小于256个

    当不能同时满足这两个条件的时候,Redis 就使用zset来实现sorted set,这个zset包含一个dict + 一个skiplist。dict用来查询数据到分数(score)的对应关系,而skiplist用来根据分数查询数据(可能是范围查找)。

     

    四、第二层的数据结构

    1、sds:

    sds数据结构详解:http://zhangtielei.com/posts/blog-redis-sds.html

    (1)什么是sds:

    sds全称是Simple Dynamic String,具有如下显著的特点:

    • 可动态扩展内存。sds表示的字符串其内容可以修改,也可以追加。在很多语言中字符串会分为mutable和immutable两种,显然sds属于mutable类型的。
    • 采用预分配冗余空间的方式来减少内存的频繁分配。内部为当前字符串实际分配的空间,一般要高于实际字符串的长度,当字符串的长度小于1M时,扩容都是扩一倍,如果超过1M,扩容是最多扩1M的空间,字符串的最大长度是512M
    • 二进制安全(Binary Safe)。sds能存储任意二进制数据,而不仅仅是可打印字符。
    • 与传统的C语言字符串类型兼容。

    (2)sds的数据结构:

    sds是Binary Safe的,它可以存储任意二进制数据,不能像C语言字符串那样以字符’\0’来标识字符串的结束,因此它必然有个长度字段。但这个长度字段在哪里呢?实际上sds还包含一个header结构:

    struct __attribute__ ((__packed__)) sdshdr5 {
        unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
        char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr8 {
        uint8_t len; /* used */
        uint8_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr16 {
        uint16_t len; /* used */
        uint16_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr32 {
        uint32_t len; /* used */
        uint32_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr64 {
        uint64_t len; /* used */
        uint64_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };

    sds一共有5种类型的header。之所以有5种,是为了能让不同长度的字符串可以使用不同大小的header。这样,短字符串就能使用较小的header,从而节省内存。

    sds字符串的完整结构,由在内存地址上前后相邻的两部分组成:

    • 一个header。通常包含字符串的长度(len)、最大容量(alloc)和flags。sdshdr5有所不同。
    • 一个字符数组。这个字符数组的长度等于最大容量+1。真正有效的字符串数据,其长度通常小于最大容量。在真正的字符串数据之后,是空余未用的字节(一般以字节0填充),允许在不重新分配内存的前提下让字符串数据向后做有限的扩展。在真正的字符串数据之后,还有一个NULL结束符,即ASCII码为0的’\0’字符。这是为了和传统C字符串兼容。之所以字符数组的长度比最大容量多1个字节,就是为了在字符串长度达到最大容量时仍然有1个字节存放NULL结束符。

    除了sdshdr5之外,其它4个header的结构都包含3个字段:

    • len: 表示字符串的真正长度(不包含NULL结束符在内)。
    • alloc: 表示字符串的最大容量(不包含最后多余的那个字节)。
    • flags: 总是占用一个字节。其中的最低3个bit用来表示header的类型。header的类型共有5种,在sds.h中有常量定义。

    #define SDS_TYPE_5  0
    #define SDS_TYPE_8  1
    #define SDS_TYPE_16 2
    #define SDS_TYPE_32 3
    #define SDS_TYPE_64 4

    sds字符串的header,其实隐藏在真正的字符串数据的前面(低地址方向)。这样的一个定义,有如下几个好处:

    • header和数据相邻,而不用分成两块内存空间来单独分配。这有利于减少内存碎片,提高存储效率(memory efficiency)。
    • 虽然header有多个类型,但sds可以用统一的char *来表达。且它与传统的C语言字符串保持类型兼容。如果一个sds里面存储的是可打印字符串,那么我们可以直接把它传给C函数,比如使用strcmp比较字符串大小,或者使用printf进行打印。

    (3)String robj的编码与解码过程:

    OBJ_STRING类型的字符串对象的编码和解码过程在Redis里非常重要,应用广泛。

    当我们执行Redis的set命令的时候,Redis首先将接收到的value值(string类型)表示成一个type = OBJ_STRING并且encoding = OBJ_ENCODING_RAW的robj对象,然后在存入内部存储之前先执行一个编码过程,试图将它表示成另一种更节省内存的encoding方式。这一过程的核心代码,是object.c中的tryObjectEncoding函数。

    当我们需要获取字符串的值,比如执行get命令的时候,我们需要执行与前面讲的编码过程相反的操作——解码。这一解码过程的核心代码,是object.c中的getDecodedObject函数。

    对于编码的核心代码tryObjectEncoding函数和解码的核心代码getDecodedObject函数的详细说明,样请读者移步这篇文章:http://zhangtielei.com/posts/blog-redis-robj.html

    2、dict:

    dict数据结构详解:http://zhangtielei.com/posts/blog-redis-dict.html

    dict是一个用于维护key-value映射关系的数据结构。Redis的一个database中所有key到value的映射,就是使用一个dict来维护的。不过,这只是它在Redis中的一个用途而已,它在Redis中被使用的地方还有很多。比如,Redis的hash结构,当它的field较多时,便会采用dict来存储。再比如,Redis配合使用dict和skiplist来共同维护一个sorted set。

    在Redis中,dict本质上是为了解决算法中的查找问题,是一个基于哈希表的算法,在不要求数据有序存储,且能保持较低的哈希值冲突概率的前提下,查询的时间复杂度接近O(1)。它采用某个哈希函数从key计算得到在哈希表中的位置,采用拉链法解决冲突并在装载因子(load factor)超过预定值时自动扩展内存,引发重哈希(rehashing)。Redis的dict实现最显著的一个特点,就在于它的重哈希。它采用了一种称为增量式重哈希(incremental rehashing)的方法,在需要扩展内存时避免一次性对所有key进行重哈希,而是将重哈希操作分散到对于dict的各个增删改查的操作中去。这种方法能做到每次只对一小部分key进行重哈希,而每次重哈希之间不影响dict的操作。dict之所以这样设计,是为了避免重哈希期间单个请求的响应时间剧烈增加,这与前面提到的“快速响应时间”的设计原则是相符的。

    当装载因子大于 1 的时候,Redis 会触发扩容,将散列表扩大为原来大小的 2 倍左右;当数据动态减少之后,为了节省内存,当装载因子小于 0.1 的时候,Redis 就会触发缩容,缩小为字典中数据个数的大约2 倍大小。

    3、ziplist:

    ziplist数据结构详解:http://zhangtielei.com/posts/blog-redis-ziplist.html

    ziplist是一个经过特殊编码的双向链表,可以用于存储字符串或整数,其中整数是按真正的二进制表示进行编码的,而不是编码成字符串序列。它能以O(1)的时间复杂度在表的两端提供pushpop操作。

    一个普通的双向链表,链表中每一项都占用独立的一块内存,各项之间用地址指针(或引用)连接起来,但这种方式会带来大量的内存碎片,而且地址指针也会占用额外的内存。而ziplist却是使用一整块连续的内存,将表中每一项存放在前后连续的地址空间内,类似于一个数组。

    另外,ziplist为了在细节上节省内存,对于值的存储采用了变长的编码方式,大概意思是说,对于大的整数,就多用一些字节来存储,而对于小的整数,就少用一些字节来存储。

    总的来说,ziplist使用一块连续的内存空间来存储数据,并采用可变长的编码方式,支持不同类型和大小的数据的存储,比较节省内存。而且数据存储在一片连续的内存空间,读取的效率也非常高。

    4、quicklist:

    quicklist数据结构详解:http://zhangtielei.com/posts/blog-redis-quicklist.html

    (1)什么是quicklist:

    quicklist是一个双向链表,而且是一个基于ziplist的双向链表,quicklist的每个节点都是一个ziplist,比如,一个包含3个节点的quicklist,如果每个节点的ziplist又包含4个数据项,那么对外表现上,这个list就总共包含12个数据项。

    quicklist的结构为什么这样设计呢?总结起来,大概又是一个空间和时间的折中

    • 双向链表便于在表的两端进行push和pop操作,但是它的内存开销比较大。首先,它在每个节点上除了要保存数据之外,还要额外保存两个指针;其次,双向链表的各个节点是单独的内存块,地址不连续,节点多了容易产生内存碎片。
    • ziplist由于是一整块连续内存,所以存储效率很高。但是,它不利于修改操作,每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候,一次realloc可能会导致大批量的数据拷贝,进一步降低性能。

    于是,结合了双向链表和ziplist的优点,quicklist就应运而生了。

    (2)quicklist中每个ziplist长度的配置:

    不过,这也带来了一个新问题:到底一个quicklist节点包含多长的ziplist合适呢?比如,同样是存储12个数据项,既可以是一个quicklist包含3个节点,而每个节点的ziplist又包含4个数据项,也可以是一个quicklist包含6个节点,而每个节点的ziplist又包含2个数据项。

    这又是一个需要找平衡点的难题。我们只从存储效率上分析一下:

    • 每个quicklist节点上的ziplist越短,则内存碎片越多。内存碎片多了,有可能在内存中产生很多无法被利用的小碎片,从而降低存储效率。这种情况的极端是每个quicklist节点上的ziplist只包含一个数据项,这就蜕化成一个普通的双向链表了。
    • 每个quicklist节点上的ziplist越长,则为ziplist分配大块连续内存空间的难度就越大。有可能出现内存里有很多小块的空闲空间(它们加起来很多),但却找不到一块足够大的空闲空间分配给ziplist的情况。这同样会降低存储效率。这种情况的极端是整个quicklist只有一个节点,所有的数据项都分配在这仅有的一个节点的ziplist里面。这其实蜕化成一个ziplist了

    可见,一个quicklist节点上的ziplist要保持一个合理的长度。那到底多长合理呢?这可能取决于具体应用场景。实际上,Redis提供了一个配置参数list-max-ziplist-size,就是为了让使用者可以来根据自己的情况进行调整。

    list-max-ziplist-size -2

    这个参数可以取正值,也可以取负值。

    当取正值的时候,表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如,当这个参数配置成5的时候,表示每个quicklist节点的ziplist最多包含5个数据项。

    当取负值的时候,表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时,它只能取-1到-5这五个值,每个值含义如下:

    • -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。(注:1kb => 1024 bytes)
    • -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。
    • -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。
    • -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。(-2是Redis给出的默认值)
    • -1: 每个quicklist节点上的ziplist大小不能超过4 Kb。

    5、intset:

    intset数据结构详解:http://zhangtielei.com/posts/blog-redis-intset.html

    (1)什么是intset:

    intset是一个由整数组成的有序集合,从而便于进行二分查找,用于快速地判断一个元素是否属于这个集合。它在内存分配上与ziplist有些类似,是连续的一整块内存空间,而且对于大整数和小整数(按绝对值)采取了不同的编码,尽量对内存的使用进行了优化。

    (2)intset的数据结构:

    typedef struct intset {
        uint32_t encoding;
        uint32_t length;
        int8_t contents[];
    } intset;
    
    #define INTSET_ENC_INT16 (sizeof(int16_t))
    #define INTSET_ENC_INT32 (sizeof(int32_t))
    #define INTSET_ENC_INT64 (sizeof(int64_t))

    各个字段含义如下:

    • encoding: 数据编码,表示intset中的每个数据元素用几个字节来存储。它有三种可能的取值:INTSET_ENC_INT16表示每个元素用2个字节存储,INTSET_ENC_INT32表示每个元素用4个字节存储,INTSET_ENC_INT64表示每个元素用8个字节存储。因此,intset中存储的整数最多只能占用64bit。
    • length: 表示intset中的元素个数。encodinglength两个字段构成了intset的头部(header)。
    • contents: 是一个柔性数组(flexible array member),表示intset的header后面紧跟着数据元素。这个数组的总长度(即总字节数)等于encoding * length。柔性数组在Redis的很多数据结构的定义中都出现过(例如sdsquicklistskiplist),用于表达一个偏移量。contents需要单独为其分配空间,这部分内存不包含在intset结构当中。

    其中需要注意的是,intset可能会随着数据的添加而改变它的数据编码:

    • 最开始,新创建的intset使用占内存最小的INTSET_ENC_INT16(值为2)作为数据编码。
    • 每添加一个新元素,则根据元素大小决定是否对数据编码进行升级。

    (3)intset与ziplist相比:

    • ziplist可以存储任意二进制串,而intset只能存储整数。
    • ziplist是无序的,而intset是从小到大有序的。因此,在ziplist上查找只能遍历,而在intset上可以进行二分查找,性能更高。
    • ziplist可以对每个数据项进行不同的变长编码(每个数据项前面都有数据长度字段len),而intset只能整体使用一个统一的编码(encoding)。

    6、skiplist:

    skiplist数据结构详解:http://zhangtielei.com/posts/blog-redis-skiplist.html

    (1)什么是跳表:

    跳表是一种可以进行二分查找的有序链表,采用空间换时间的设计思路,跳表在原有的有序链表上面增加了多级索引(例如每两个节点就提取一个节点到上一级),通过索引来实现快速查找。跳表是一种动态数据结构,支持快速的插入、删除、查找操作,时间复杂度都为O(logn),空间复杂度为 O(n)。跳表非常灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗。

    ① 跳表的删除操作:除了要删除原始链表中的节点,还要删除索引中的节点。

    ② 插入元素后,索引的动态更新:不停的往跳表里面插入数据,如果不更新索引,就有可能出现某两个索引节点之间的数据非常多的情况,甚至退化成单链表。针对这种情况,我们在添加元素的时候,通过一个随机函数,同时选择将这个数据插入到部分索引层。比如随机函数生成了值 K,那我们就将这个结点添加到第一级到第K级这K级的索引中

     

    展开全文
  • 编写一个程序exp4-3.cpp,实现顺序的各种模式匹配运算,并在此基础上完成以下功能 建立目标s=”abcabcdabcdeabcdefabcdefg”和模式t=”abcdeabcdefab”。 采用简单匹配算法求t在s中的位置 采用KMP算法求t在...

    实验三

    1. 实验目的:

    掌握串的模式匹配算法(即BF和KMP算法)设计

    2. 仪器与材料:

    装有Windows操作系统和VC++6.0编程环境的PC机一台。

    3. 实验内容:

    编写一个程序exp4-3.cpp,实现顺序串的各种模式匹配运算,并在此基础上完成以下功能

    1. 建立目标串s=”abcabcdabcdeabcdefabcdefg”和模式串t=”abcdeabcdefab”。
    2. 采用简单匹配算法求t在s中的位置
    3. 采用KMP算法求t在s中的位置

    4. 实验记录:

        数据结构设计:

    BF算法比较粗暴直观,它直接从第1字符开始一个一个字符地比较主串和子串的字符,如果不一样就回溯到开始的第2个字符(也就是i-j+2)开始比较,而子串是回到其第1个字符(即j=1),但其时间复杂度比较高。

    KMP算法:开始对主串和子串进行匹配,当匹配过程中产生“失配”时,指针i不变,指针j退回至next[j]所指示位置重新进行比较,如果不匹配,则指针退回至next[next[j]]进行对比...直到指针j退至0时,指针i和指针j便需同时增1,也就是说如果主串的第i个字符和子串的第1个字符不等,则从主串的第i+1个字符起重新匹配。综上所述,可以发现KMP的关键点是next[j]的获取。

        函数功能:

     BF(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。

    KMP算法在匹配过程中主串中的第i个字符与模式中的第j个字符比较不等时(S[i]!=T[j]),仅需要将模式串向右滑动至模式中的第k个字符,与主串中的第i个字符对齐,此时的模式中的k-1个子串必然和主串满足关系式1,在从j=k位置依次与i对应位置的元素进行比较。(j回溯的位置即为k  j=k)

    令next[j]=k为当在第j位比较失败时,模式中重新与此该主串中字符比较的字符位置。(模式串向右移动的位数为:已匹配的字符数-失配字符上一位字符所对应的前后缀公共元素的最大长度)

    5. 实验体会:

    KMP之所以比BF算法简单,是因为引入了一个next数组,降低查询时间,相比而言,增加了空间,通过数组的下标快速匹配。

    展开全文
  • 前言本文主要介绍关于Redis的五基本数据结构的底层实现原理,然后来分析我们常用的使用场景。先简单回顾一下知识点。Redis 是一个开源(BSD许可)的,内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件...
  • 2.2 线性表的逻辑结构 2.2.1 线性表的定义 2.2.2 线性表的抽象数据类型定义 第2章 线性表 2.1 引言 线性表是描述单一的前驱和后继的关系 2.2 线性表的逻辑结构 2.2.1 线性表的定义 线性表是一个有限的序列,...
  • 字符str1、str2连接,三种存储方式一、定长存储 一、定长存储 #include<iostream> using namespace std; #define MAXLEN 255 typedef struct { char ch[MAXLEN + 1]; int length; }String; void StrAssign...
  • 数据结构是计算机存储、组织数据的方式。一好的数据结构可以带来更高的运行或者存储效率。数据在内存中是呈线性排列的,但是我们可以使用指针等道具,构造出类似“树形”的复杂结构。下面介绍八个常见的数据结构
  • 二叉树的实现1.1 引入库以及设置结构体1.2初始化二叉树1.3队列的基本操作实现1.4二叉树深度遍历的三种方法1.5层次遍历1.6求子叶个数以及结点个数1.7的输出功能1.8主函数实现上述全部功能2.运行截图总结 前言 1....
  • 常见数据结构的理解

    万次阅读 2021-11-22 15:55:35
    还有朋友可能不太理解什么是数据结构,就像喝水,你总是喝到最上面的一层,我称之为“水的栈”这便是一结构 顾名思义数据结构,便是数据的结构,数据结构并不是什么很高深的东西 起初数据结构并没有一门专门的...
  • 因为教材中的概念之间存在冲突,所以广泛浏览各类教材、视频,对数据结构进行系统、辩证的梳理。建议考研看不懂教材或者视频的同学看一看。
  • 文章目录1、线性表2、顺序表2.1 概念及结构2.2 顺序表接口的实现2.2.1 打印顺序表2.2.2 在pos位置新增元素2.2.3 判定是否包含某个元素2.2.4 查找某个元素对应的位置2.2.5 获取 pos 位置的元素2.2.6 给 pos 位置的...
  • c语言实现家谱(孩子兄弟树)数据结构

    千次阅读 多人点赞 2021-05-03 15:27:25
    使用树型结构对家谱进行管理,实现查看祖先和子孙个人信息,插入家族成员,删除家族成员的功能 【基本要求】 (1)采用树形结构完成家谱成员信息的建立,可利用孩子兄弟表示方法表示树型结构 (2)完成家谱成员...
  • 数据结构复习题(绪论)

    千次阅读 多人点赞 2021-05-31 23:24:41
    选择题数据结构复习(复习题)绪论二级目录级目录 绪论 线性结构中数据元素的位置之间存在( )的关系 A.一多 B.一一 C.多多 D.每一个元素都有一个直接前驱和一个直接后继 数据结构中,与所使用的计算机...
  • 二、KMP算法的解决题型、模式移动距离的判断(next数组)四、KMP算法的具体实现五、KMP算法的时间复杂度六、next数组的改进--nextval数组及具体代码七、最后的话 一、什么是KMP算法? KMP算法是一改进的字符...
  • 数据结构是一特殊的组织和存储数据的方式,可以使我们可以更高效地存储的数据执行操作。数据结构在计算机科学和软件工程领域具有广泛而多样的用途。几乎所有已开发的程序或软件系统都使用数据结构...
  • 数据结构课程设计

    2021-01-04 15:04:53
    我可以代做,私信我。 1、特殊矩阵计算器 问题描述:创建两个特殊矩阵 A 和 B,计算 A+B、A-B、AB、BA、A(或 B)的逆、A(或 B)的 转置、A(或 B)的行列式等,...④ 各运算需自己实现,禁止调用语言內建或第方类库
  • 数据结构和数据类型

    2021-01-25 17:46:15
    数据结构是指相互之间存在一或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 名词定义 数据结构是指相互之间...
  • 记录下上学期的数据结构实验 本电话号码查询系统基于两散列方法和两解决冲突的方法实现 提示:以下是本篇文章正文内容,下面案例可供参考 一、问题描述 设计散列表,实现电话号码查找系统。设电话号码簿长度
  • 《C语言复习提纲模块2:三种基本结构及流程控制》由会员分享,可在线阅读,更多...这 种结构分别需要借助于特定的语句控制实现。(1)顺序结构: 赋值语句和函数调用语句是控制该结构的主要 语句。函数调用语句中...
  • 本文代码实现基本按照《数据结构》课本目录顺序,外加大量的复杂算法实现,一篇文章足够。能换你一个收藏了吧?
  • 文章目录前言三种优化过的数据结构SDS 设计**redisObject 结构体****嵌入式字符**ziplist 设计intset 设计共享对象 前言 Redis 作为内存数据库,如何高效地使用内存非常重要。为了提升内存的使用率,主要采取数据...
  • 总结Redis常见的数据结构和使用场景
  • 用Excel也能实现和Python数据分析一样的功能! 这是一篇关于如何用excel做数据分析的案例。目的是帮助大家,在遇到小型数据样本时,快速利用excel做分析。所以本篇文章的重点是分析思路+数据处理+可视化的实现,...
  • 要求(1)粘贴代码图片(图片需包括行号),代码不可超过6行(争取4行); (2)粘贴结果图片,符合条件的整数有四个。【单选题】哪个选项不能正确引用turtle库进而使用setup()函数?【单选题】下面不属于Python保留字的是:...
  • 数据结构面试常见问题

    千次阅读 2021-01-04 16:00:05
    目录一、绪论二、线性表、栈和队列四、、数组和广义表五、树和二叉树六、图七、查找八、内部排序 一、绪论 1.时间复杂度和空间复杂度的区别是什么? (1)时间复杂度是一个算法运行所占用CPU时间多少的量度; ...
  • 第一章 数据结构概述 基本概念与术语 1. 数据:数据是客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被 ...4. 数据结构数据结构是相互之间存在一或多种特定关系的数据元素的集合。 (1
  • 1、领会二叉链存储结构和掌握二叉树中的各种基本运算算法设计; 2、领会线索二叉树的构造过程以及构造二叉树的算法设计; 3、领会哈夫曼树的构造过程以及哈夫曼编码的生成过程; 4、掌握二叉树遍历算法的应用,熟练...
  • 数据结构是指相互之间存在一或多种特定关系的数据元素集合。它强调的是带有结构的数据元素的集合,数据元素之间的相互关系,即数据的组织形式。数据的组织方法与效率密切相关,采用不同数据的组织方法...
  • 基于链表实现

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 317,680
精华内容 127,072
关键字:

数据结构要求对串实现以下三种功能

数据结构 订阅