1. Toy模板网首页
  2. > Toy博客

数据结构（超详细讲解！！）第十八节 串（堆串）

10月前 作者：陌柒2333 分类：Toy博客 阅读(58) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构（超详细讲解！！）第十八节 串（堆串）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.定义

假设以一维数组heap ［MAXSIZE］ 表示可供字符串进行动态分配的存储空间，并设 int start 指向heap 中未分配区域的开始地址(初始化时start =0) 。在程序执行过程中，当生成一个新串时，就从start指示的位置起，为新串分配一个所需大小的存储空间，同时建立该串的描述。这种存储结构称为堆结构。 此时，堆串可定义如下：

typedef  struct
{int   len； 
 int   start； 
} HeapString；

其中len域指示串的长度， start域指示串的起始位置。借助此结构可以在串名和串值之间建立一个对应关系，称为串名的存储映象。系统中所有串名的存储映象构成一个符号表。 

数据结构（超详细讲解！！）第十八节 串（堆串）,数据结构（超详细讲解！！）,数据结构,算法,c语言

 在C语言中，已经有一个称为“堆”的自由存储空间，并可用malloc（）和free（）函数完成动态存储管理。因此，我们可以直接利用C语言中的“堆”实现堆串。此时，堆串可定义如下：文章来源地址https://www.toymoban.com/news/detail-744342.html

typedef  struct
{  
    char  * ch；  
    int   len； 
} HString；

2.基本操作

1.初始化

//初始化
HString * Init_HString( )
{	HString *s;	
	s = (HString *) malloc ( sizeof( HString ) );
 	s->len=0;
 	s->ch=NULL;
 	printf("初始化成功。\n");
	return s;	
}

2.录入

//录入
int Enter_SStrin(HString *s)
{char x;
int len;
printf("请输入字符串长度和元素：");
scanf("%d %c",&len,&x); 
s->ch=(char *) malloc ( len );
while(x!='#')
{
	s->ch[s->len] = x;	
	s->len=s->len+1;  
	scanf(" %c",&x);
}
printf("录入完成。\n");
	return 1;			/*入队成功，函数返回1*/
}

3.插入

//插入 
int StrInsert(HString *s,HString t) /* 在串s中序号为pos的字符之前插入串t */
{
int i,pos;
char *temp;
printf("请输入插入位置：");
scanf("%d",&pos); 
if (pos<0 || pos>s->len || s->len==0) return(0);
temp=(char *)malloc(s->len + t.len);
if (temp==NULL) return(0);
for (i=0;i<pos;i++) temp[i]=s->ch[i];
for (i=0;i<t.len;i++) temp[i+pos]=t.ch[i];
for (i=pos;i<s->len;i++) temp[i + t.len]=s->ch[i];
s->len+=t.len;
free(s->ch);s->ch=temp;
printf("插入成功\n");
return(1);
}

4.删除

//串删除函数
int StrDelete(HString *s) /* 在串s中删除从序号pos起的len个字符 */
{
int i,pos,len;
char *temp;
printf("请输入删除位置和个数：");
scanf("%d %d",&pos,&len); 
if (pos<0 || pos>(s->len - len)) return(0);
temp=(char *)malloc(s->len - len);
if (temp==NULL) return(0);
for (i=0;i<pos;i++) temp[i]=s->ch[i];
for (i=pos;i<s->len - len;i++) temp[i]=s->ch[i+len];
s->len=s->len-len;
free(s->ch);s->ch=temp;
printf("删除成功\n");
return(1);
}

5.遍历

//遍历 
void Printf(HString *s)
{int i;
for(i=0;i<s->len;i++)
{printf("%c",s->ch[i]);
}
printf("\n");
}

6.复制

//串复制函数 
int StrCopy(HString *s,HString t) /* 将串t的值复制到串s中 */
{
int i;
s->ch=(char *)malloc(t.len);
if (s->ch==NULL) return(0);
for (i=0;i<t.len;i++) s->ch[i]=t.ch[i];
s->len=t.len;
printf("复制完成。\n");
return(1);
}

7.判空

//判空函数
int StrEmpty(HString s) /* 若串s为空(即串长为0)，则返回1，否则返回0 */
{
if (s.len==0) {
	printf("堆串为空。\n");
	return(1);
}
else 
printf("堆串不为空。\n");
return(0);
}

8.比较

//串比较函数
int StrCompare(HString s,HString t) /* 若串s和t相等， 则返回0； 若s>t， 则返回1； 若s<t， 则返回-1 */
{
int i;
for (i=0;i<s.len&&i<t.len;i++)  
    if (s.ch[i]!=t.ch[i]) 
	{
    if(s.ch[i]- t.ch[i]==0)
	printf("串s和t相等。\n");
	if(s.ch[i]- t.ch[i]>0)
	printf("串s大于t。\n");
	if(s.ch[i]- t.ch[i]<0)
	printf("串s小于t。\n");
		return(s.ch[i] - t.ch[i]);
	}
	if(s.len - t.len==0)
printf("串s和t相等。\n");
if(s.len - t.len>0)
printf("串s大于t。\n");
if(s.len - t.len<0)
printf("串s小于t。\n");	  	
return(s.len - t.len);
}

9.求串长

//求串长函数
int StrLength(HString s) /* 返回串s的长度 */
{printf("串长为：%d\n",s.len);
return(s.len);
}

10.清空

//清空函数 
int StrClear(HString *s) /* 将串s置为空串 */
{
if (s->ch!=NULL) free(s->ch);
s->ch=NULL;
s->len=0;
printf("清空完成。\n");
return(1);
}

11.连接

//连接函数
int StrCat(HString *s,HString t) /* 将串t连接在串s的后面 */
{
int i;
char *temp;
temp=(char *)malloc(s->len + t.len);
if (temp==NULL) return(0);
for (i=0;i<s->len;i++)
    temp[i]=s->ch[i];
for (i=s->len;i<s->len + t.len;i++) 
    temp[i]=t.ch[i-s->len];
s->len+=t.len;
free(s->ch);s->ch=temp;
printf("连接完成。\n");
return(1);
}

12.求子串

//求子串函数
HString *SubString(HString s) /* 将串s中序号pos起的len个字符复制到sub中 */
{
int i,pos,len;
HString *sub;	
	sub = (HString *) malloc ( sizeof( HString ) );
 	sub->len=0;
 	sub->ch=NULL;
printf("请输入子串起始位置，和子串长度：");
scanf("%d %d",&pos,&len); 
if (sub->ch!=NULL) free(sub->ch);
if (pos<0 || pos>s.len || len<1 || len>s.len-pos) 
   { sub->ch=NULL;
   sub->len=0;
   printf("子串位置不合法。\n");
   return(0);} 
else { 
   sub->ch=(char *)malloc(len); 
   if (sub->ch==NULL) return(0); 
   for (i=0;i<len;i++) 
   sub->ch[i]=s.ch[i+pos]; 
   sub->len=len;  
   printf("截取子串成功。\n");
   return(sub); 
   }
}

13.定位

//定位函数 
int StrIndex(HString s,HString t) /* 求串t在串s中的位置 */
{
int i, j,pos;
printf("请输入在第几个元素之后进行查找：");
scanf("%d",&pos);
if (s.len==0 || t.len==0) 
{printf("s或t不存在。\n");
	return(0);
}
i=pos;j=0;
while (i<s.len && j<t.len)
   { if (s.ch[i]==t.ch[j]) 
     {
       i++;j++;
       } 
    else {
       i=i-j+1;j=0;
       }
    }
if (j>=t.len) 
{printf("串t首在s中的位置为：%d\n",i-j);
	return(i-j);
}
else 
printf("未在s中找到t。\n"); 
return(0);
}

3.代码

 #include<stdio.h>
#include<malloc.h>

typedef  struct
{  
    char  * ch; 
    int   len; 
} HString; 


//初始化
HString * Init_HString( )
{	HString *s;	
	s = (HString *) malloc ( sizeof( HString ) );
 	s->len=0;
 	s->ch=NULL;
 	printf("初始化成功。\n");
	return s;	
}


//录入
int Enter_SStrin(HString *s)
{char x;
int len;
printf("请输入字符串长度和元素：");
scanf("%d %c",&len,&x); 
s->ch=(char *) malloc ( len );
while(x!='#')
{
	s->ch[s->len] = x;	
	s->len=s->len+1;  
	scanf(" %c",&x);
}
printf("录入完成。\n");
	return 1;			/*入队成功，函数返回1*/
}

//遍历 
void Printf(HString *s)
{int i;
for(i=0;i<s->len;i++)
{printf("%c",s->ch[i]);
}
printf("\n");
}


//插入 
int StrInsert(HString *s,HString t) /* 在串s中序号为pos的字符之前插入串t */
{
int i,pos;
char *temp;
printf("请输入插入位置：");
scanf("%d",&pos); 
if (pos<0 || pos>s->len || s->len==0) return(0);
temp=(char *)malloc(s->len + t.len);
if (temp==NULL) return(0);
for (i=0;i<pos;i++) temp[i]=s->ch[i];
for (i=0;i<t.len;i++) temp[i+pos]=t.ch[i];
for (i=pos;i<s->len;i++) temp[i + t.len]=s->ch[i];
s->len+=t.len;
free(s->ch);s->ch=temp;
printf("插入成功\n");
return(1);
} 


//串删除函数
int StrDelete(HString *s) /* 在串s中删除从序号pos起的len个字符 */
{
int i,pos,len;
char *temp;
printf("请输入删除位置和个数：");
scanf("%d %d",&pos,&len); 
if (pos<0 || pos>(s->len - len)) return(0);
temp=(char *)malloc(s->len - len);
if (temp==NULL) return(0);
for (i=0;i<pos;i++) temp[i]=s->ch[i];
for (i=pos;i<s->len - len;i++) temp[i]=s->ch[i+len];
s->len=s->len-len;
free(s->ch);s->ch=temp;
printf("删除成功\n");
return(1);
} 

//串复制函数 
int StrCopy(HString *s,HString t) /* 将串t的值复制到串s中 */
{
int i;
s->ch=(char *)malloc(t.len);
if (s->ch==NULL) return(0);
for (i=0;i<t.len;i++) s->ch[i]=t.ch[i];
s->len=t.len;
printf("复制完成。\n");
return(1);
} 


//判空函数
int StrEmpty(HString s) /* 若串s为空(即串长为0)，则返回1，否则返回0 */
{
if (s.len==0) {
	printf("堆串为空。\n");
	return(1);
}
else 
printf("堆串不为空。\n");
return(0);
} 

//串比较函数
int StrCompare(HString s,HString t) /* 若串s和t相等， 则返回0； 若s>t， 则返回1； 若s<t， 则返回-1 */
{
int i;
for (i=0;i<s.len&&i<t.len;i++)  
    if (s.ch[i]!=t.ch[i]) 
	{
    if(s.ch[i]- t.ch[i]==0)
	printf("串s和t相等。\n");
	if(s.ch[i]- t.ch[i]>0)
	printf("串s大于t。\n");
	if(s.ch[i]- t.ch[i]<0)
	printf("串s小于t。\n");
		return(s.ch[i] - t.ch[i]);
	}
	if(s.len - t.len==0)
printf("串s和t相等。\n");
if(s.len - t.len>0)
printf("串s大于t。\n");
if(s.len - t.len<0)
printf("串s小于t。\n");	  	
return(s.len - t.len);
} 


//求串长函数
int StrLength(HString s) /* 返回串s的长度 */
{printf("串长为：%d\n",s.len);
return(s.len);
} 

//清空函数 
int StrClear(HString *s) /* 将串s置为空串 */
{
if (s->ch!=NULL) free(s->ch);
s->ch=NULL;
s->len=0;
printf("清空完成。\n");
return(1);
} 


//连接函数
int StrCat(HString *s,HString t) /* 将串t连接在串s的后面 */
{
int i;
char *temp;
temp=(char *)malloc(s->len + t.len);
if (temp==NULL) return(0);
for (i=0;i<s->len;i++)
    temp[i]=s->ch[i];
for (i=s->len;i<s->len + t.len;i++) 
    temp[i]=t.ch[i-s->len];
s->len+=t.len;
free(s->ch);s->ch=temp;
printf("连接完成。\n");
return(1);
} 

//求子串函数
HString *SubString(HString s) /* 将串s中序号pos起的len个字符复制到sub中 */
{
int i,pos,len;
HString *sub;	
	sub = (HString *) malloc ( sizeof( HString ) );
 	sub->len=0;
 	sub->ch=NULL;
printf("请输入子串起始位置，和子串长度：");
scanf("%d %d",&pos,&len); 
if (sub->ch!=NULL) free(sub->ch);
if (pos<0 || pos>s.len || len<1 || len>s.len-pos) 
   { sub->ch=NULL;
   sub->len=0;
   printf("子串位置不合法。\n");
   return(0);} 
else { 
   sub->ch=(char *)malloc(len); 
   if (sub->ch==NULL) return(0); 
   for (i=0;i<len;i++) 
   sub->ch[i]=s.ch[i+pos]; 
   sub->len=len;  
   printf("截取子串成功。\n");
   return(sub); 
   }
} 

//定位函数 
int StrIndex(HString s,HString t) /* 求串t在串s中的位置 */
{
int i, j,pos;
printf("请输入在第几个元素之后进行查找：");
scanf("%d",&pos);
if (s.len==0 || t.len==0) 
{printf("s或t不存在。\n");
	return(0);
}
i=pos;j=0;
while (i<s.len && j<t.len)
   { if (s.ch[i]==t.ch[j]) 
     {
       i++;j++;
       } 
    else {
       i=i-j+1;j=0;
       }
    }
if (j>=t.len) 
{printf("串t首在s中的位置为：%d\n",i-j);
	return(i-j);
}
else 
printf("未在s中找到t。\n"); 
return(0);
} 

  void menu()
{
printf("--------1.初始化s------\n"); 
printf("--------2.初始化t------\n"); 
printf("--------3.录入s--------\n"); 
printf("--------4.录入t--------\n"); 
printf("--------5.插入---------\n"); 
printf("--------6.删除---------\n"); 
printf("--------7.判空---------\n"); 
printf("--------8.复制---------\n"); 
printf("--------9.比较---------\n"); 
printf("--------10.求长度------\n"); 
printf("--------11.清空--------\n"); 
printf("--------12.连接--------\n"); 
printf("--------13.求子串sub---\n"); 
printf("--------14.定位-------\n");
printf("--------15.遍历s-------\n"); 
printf("--------16.遍历t-------\n"); 
printf("--------17.遍历sub-----\n"); 
printf("--------18.退出程序----\n");
}

int main()
{HString *s,*t,*sub;
int n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,a,quit=0;
menu();
while(1)
{
scanf("%d",&a);
switch(a)
{
case 1:s=Init_HString( );break;
case 2:t=Init_HString( );break;
case 3:n1=Enter_SStrin(s);break;
case 4:n2=Enter_SStrin(t);break;
case 5:n3=StrInsert(s,*t);break;
case 6:n4=StrDelete(s);break;
case 7:n5=StrEmpty(*s);break;
case 8:n6=StrCopy(s,*t);break;
case 9:n7=StrCompare(*s,*t) ;break;
case 10:n8=StrLength(*s);break;
case 11:n9=StrClear(s);break;
case 12:n10=StrCat(s,*t);break;
case 13:sub=SubString(*s);break;
case 14:n11=StrIndex(*s,*t);break;
case 15:Printf(s);break;
case 16:Printf(t);break;
case 17:Printf(sub);break;
case 18:quit=1;break;
default:printf("输入1~18之间的数字\n");break;
}
if(quit==1)
{break;
}
}
return 0;
 }

到了这里，关于数据结构（超详细讲解！！）第十八节 串（堆串）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【第十八节：微信小程序 常用功能-登录】微信小程序入门，以思维导图的方式展开18

    【第十八节：微信小程序 常用功能-登录】微信小程序入门，以思维导图的方式展开18

    若图片看不清，可私信给五木大大要高清大图哈。      效果               wxml页面         view class=\\\"login-container\\\"nn    view class=\\\"login\\\" wx:if=\\\"{{ !logged }}\\\"nn        view class=\\\"app-info\\\"nn            image class=\\\"app-logo\\\" src=\\\"../../images/logo.png\\\" /nn            text class

    2024年01月17日
    浏览(57)
  • 【数据结构】顺序表 | 详细讲解

    【数据结构】顺序表 | 详细讲解

    在计算机中主要有两种基本的存储结构用于存放线性表：顺序存储结构和链式存储结构。本篇文章介绍采用顺序存储的结构实现线性表的存储。 线性表的顺序存储结构，指的是一段地址连续的存储单元依次存储链性表的数据元素。 线性表的（，……）的顺序存储示意图如下

    2024年02月04日
    浏览(39)
  • 【数据结构】单链表 | 详细讲解

    【数据结构】单链表 | 详细讲解

    无须为了表示中间的元素之间的逻辑关系而增加额外的存储空间； 因为以数组形式存储，可以快速地存取表中任一位置的元素。 插入和删除操作需要移动大量元素，时间复杂度为O(N)； 当线性表长度变化较大时，难以确定存储空间的容量； 造成存储空间的“碎片”。 其实顺

    2024年02月05日
    浏览(47)
  • 数据结构：栈和队列（详细讲解）

    数据结构：栈和队列（详细讲解）

    🎇🎇🎇作者： @小鱼不会骑车 🎆🎆🎆专栏： 《数据结构》 🎓🎓🎓个人简介： 一名专科大一在读的小比特，努力学习编程是我唯一的出路😎😎😎 栈 ：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为 栈顶 ，另

    2024年02月03日
    浏览(46)
  • 【数据结构】快排的详细讲解

    【数据结构】快排的详细讲解

    江河入海，知识涌动，这是我参与江海计划的第7篇。 目录：         快排是排序算法中效率是比较高的，快排的基本思想是运用二分思想，与二叉树的前序遍历类似，将数据划分，每次划分确定1个基准值(就是已经确定好有序后位置的数据)，以升序为例，基准值左面的数据

    2024年02月06日
    浏览(91)
  • 《数据结构》八大排序（详细图文分析讲解）

    《数据结构》八大排序（详细图文分析讲解）

    目录 排序 排序的应用       排序简介 排序的分类 排序算法的好坏评判 冒泡排序法  思路分析 代码实现   选择排序法 思路分析 代码实现   插入排序 思路分析 代码实现  希尔排序 思路分析 代码演示  归并排序法  思路分析 代码演示  快速排序  思路分析 代码实现 

    2024年02月03日
    浏览(49)
  • 【数据结构初阶】——第八节.优先级队列（小根堆的模拟实现）

    【数据结构初阶】——第八节.优先级队列（小根堆的模拟实现）

     作者简介：大家好，我是未央； 博客首页： 未央.303 系列专栏：Java初阶数据结构 每日一句：人的一生，可以有所作为的时机只有一次，那就是现在！！！ 目录 文章目录 前言 引言 一、堆的概念 二、堆的性质  三、堆的操作 3.1 向下调整算法 3.2 小根堆的创建 3.3 向上调整

    2024年02月07日
    浏览(51)

  • C++数据封装以及定义结构的详细讲解鸭~

    名字：阿玥的小东东   博客主页：阿玥的小东东的博客_CSDN博客-pythonc++高级知识,过年必备,C/C++知识讲解领域博主 目录 定义结构 访问结构成员 结构作为函数参数

    2024年02月04日
    浏览(43)
  • 数据结构进阶篇 之【选择排序】详细讲解（选择排序，堆排序）

    数据结构进阶篇 之【选择排序】详细讲解（选择排序，堆排序）

    民以食为天，我以乐为先 嘴上来的嘘寒问暖，不如直接打笔巨款 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 直接选择排序的特性总结 跳转链接：数据结构 之 堆的应用 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀

    2024年04月09日
    浏览(42)
  • 数据结构（超详细讲解！！）第二十一节 特殊矩阵的压缩存储

    数据结构（超详细讲解！！）第二十一节 特殊矩阵的压缩存储

    值相同的元素只存储一次 压缩掉对零元的存储，只存储非零元 特殊形状矩阵： 是指非零元（如值相同的元素）或零元素分布具有一定规律性的矩阵。 如： 对称矩阵 上三角矩阵   下三角矩阵 对角矩阵   准对角矩阵 三角矩阵大体分为三类：下三角矩阵、上三角矩阵和对称

    2024年02月04日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包