以图明志

数据结构

[专题] 题外话:谈谈malloc()和free()

malloc()和free()里的学问
对于串的顺序存储,有些需要补充说明。串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区,叫做“堆”。这个堆可由C语言的动态分配函数malloc()和free()来管理。那么今天就来点题外话,谈谈malloc()和free()。

数据结构

[专题] 字符串中的子串替换

串的替换
在很多编程语言中,都封装了字符串替换的操作,那么我们这里自己用C语言来实现一个字符串替换的函数。具体需求为:Replace(String S,String T,String V),用V替换主串S中出现的所有与T相等的不重叠的子串。字符串替换这个操作,需要结合我们前面讲到的几个函数。

数据结构

[专题] 如何在串中删除特定长度的子串

串的删除
昨天我们写了如何在串中插入另外一个串,那么今天我们来看看对应的操作:如何在串中删除指定长度的子串。也就是,从串S1中删除第pos个字符起长度为len的子串。其实就是数组操作啦,把第pos个元素起的len个元素去掉即可。具体怎么去掉呢?把S[pos+len]赋值给S[pos],把S[pos+len+1]赋值给S[pos+1]……以此类推就OK了。

数据结构

[专题] 如何在串中插入串

串的插入
继续完成一些常见的操作。比如有两个串s1,s2,现在需要把s2安插到s1的特定位置,我们今天来解决这个问题。还是要根据截断分为两种情况。如果没有截断的话,就可以将s2完全插入到s1里。首先从s1的末尾,将从pos位置到末尾的元素复制过去。比如nowamagic.net需要在第4个位置插入lol,则从第四个位置起,将整个s1拷过去,即nownowamagic.net

数据结构

[专题] 寻找子串在主串中的位置

匹配主串与子串的过程
我们先来看这么一个需求。比如主串是 nowamagic.net,子串是 magic,那么如何知道 magic 在主串的第几个字符后的位置呢?设i用于主串s1中当前位置下标值,j用于子串sub中当前位置下标值。首先我们比较s1[1]与sub[1],如果相同的话,可能子串就开始了。如果不相等,那么子串仍然是从sub[1]开始,而主串s1则以s1[2]与其比较。

数据结构

[专题] 串最基本的5个操作的C实现

串的最小操作子集
前面谈到串的最小操作子集:串赋值StrAssign,串比较StrCompare,求串长StrLength,串联接Concat,求子串SubString。这5种操作不可能利用其他串操作来实现,但其他串操作均可在这个最小操作子集上实现。这里我们写程序实现上面的操作吧。

数据结构

[专题] 串的顺序存储结构

串在内存中如何存储?
串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。既然是定长数组,就存在一个预定义的最大串长度,一般可以将实际的串长度值保存在数组的0下标位置,有的书中也会定义存储在数组的最后一个下标位置。

数据结构

[专题] 串的抽象数据类型ADT

定义串的一些操作
串的逻辑结构和线性表很相似,不同之处在于串针对的是字符集,也就是串中的元素都是字符,哪怕串中的字符是“123”这样的数字组成,或者“2010-10-1CT这 样的日期组成,它们都只能理解为长度为3和长度为10的字符串,每个元素都是字符而已。

数据结构

[专题] 如何比较串的大小

其实就是比较串的内部编码
两个数字,很容易比较大小。2比1大,这完全正确,可是两个字符串如何比较呢?事实上,串的比较是通过组成串的字符之间的编码来进行的,而字符的编码指的是字符在对应字符集中的序号。计算机中的常用字符是使用标准的ASCII编码,更准确一点,由7位二进制数表示一个字符,总共可以表示128个字符。

数据结构

[专题] 数据结构里的串是什么东西?

就是字符串啦
早先的计算机在被发明时,主要作用是做一些科学和工程的计算工作,也就是现在我们理解的计算器,只不过它比小小计算器功能更强大、速度更快一些。后来发现,在计算机上作非数值处理的工作越来越多,使得我们不得不需要引入对字符的处理。于是就有了字符串的概念。

数据结构

[专题] 循环队列与链队列的优劣势

循环队列、链队列分别什么时候用
从时间上,其实它们的基本操作都是常数时间,即都为0(1)的,不过循环队列是事先申请好空间,使用期间不释放,而对于链队列,每次申请和释放结点也会存在一些时间开销,如果入队出队频繁,则两者还是有细微差异。对于空间上来说,循环队列必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题。

数据结构

[专题] 补完链队列的其它常见操作

置空、求长度、判断空等
返回队头元素:若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR。求队列的长度:求链队列的长度,用一个工作指针遍历队列然后记录长度即可。判断队列是否为空:判断链队列是否为空很简单,比较队头指针与队尾指针是否重合即可,Q.front==Q.rear 。

数据结构

[专题] 链队列的出队操作

删除首元结点的算法步骤
出队操作时,就是头结点的后继结点出队,将头结点的后继改为它后面的结点,若链表除头结点外只剩一个元素时,则需将rear指向头结点。要删除掉a1结点,思路很简单,就是让头结点Q->front的后继next直接指向a2。但是a2如何标识呢?假设a1结点为p结点,那么a2就是p->next了。如何让a1结点存到p呢?

数据结构

[专题] 链队列的入队操作

与链表插入大致相同
入队操作时,其实就是在链队列(链表)的尾部插入结点。根据这个图,我们就可以大概知道入队操作的步骤了。根据图,我们先创建一个结点s,QueuePtr s=(QueuePtr)malloc(sizeof(QNode));然后给s的data域赋值e,指针域next赋值null。s->data=e;s->next=NULL; 目的就是让它成为新任队尾元素。

数据结构

[专题] 链队列的初始化操作

还有return和exit有区别
链队列的初始化应该怎么写呢?要初始化一个链队列,我们这么这么做:产生头结点 (QueuePtr)malloc(sizeof(QNode)),然后让队头指针(头指针)与队尾指针都指向头结点。置空头结点 Q->front 的指针域 Q->front->next=NULL;

数据结构

[专题] 链队列:队列的链式存储结构

链队列的结构体定义
队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。为了操作上的方便,我们将队头指针指向链队列的头结点,而队尾指针指向终端结点。当队列为空时,front和rear都指向头结点。与链栈一样,我们分两步定义链队列的结构体,首先是按链表来定义链队列的结点。
1 / 10 首页 < Prev 1 2 3 4 5 Next > 尾页 页码: