当前位置： 首页 > news >正文

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

news 来源：原创 2024/5/12 16:13:41

1.定义

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

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

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

 在C语言中，已经有一个称为“堆”的自由存储空间，并可用malloc（）和free（）函数完成动态存储管理。因此，我们可以直接利用C语言中的“堆”实现堆串。此时，堆串可定义如下：

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;}

相关文章：

  • python连接clickhouse （CK）
  • MySQL笔记--Ubuntu安装MySQL并基于C++测试API
  • web3 在React dapp中全局管理web3当前登录用户/智能合约等信息
  • conda配置虚拟环境相关记录
  • 利用wasm实现读写本地项目的在线编辑器
  • IDEA 使用技巧
  • javaEE -15（ 13000字 JavaScript入门 - 2）
  • 【Linux】服务器间免登陆访问
  • docker安装Kafka，SpringBoot整合Kafka
  • IOC课程整理-11 Spring 资源管理
  • Failed to launch task: 文件”Setup”不存在 Mac安装Adobe软件报错解决方案
  • 微服务的定义
  • string【C++】
  • 数据库 | 看这一篇就够了！最全MySQL数据库知识框架！
  • Spring MVC（Next-2）
  • 实现windows 窗体的自己画，网上摘抄的，学习了
  • 「前端」从UglifyJSPlugin强制开启css压缩探究webpack插件运行机制
  • ➹使用webpack配置多页面应用(MPA)
  • 2019年如何成为全栈工程师？
  • Android开源项目规范总结
  • Apache Spark Streaming 使用实例
  • CentOS 7 修改主机名
  • eclipse的离线汉化
  • Electron入门介绍
  • Git 使用集
  • linux安装openssl、swoole等扩展的具体步骤
  • python学习笔记－类对象的信息
  • SAP云平台里Global Account和Sub Account的关系
  • Synchronized 关键字使用、底层原理、JDK1.6 之后的底层优化以及 和ReenTrantLock 的对比...
  • windows下如何用phpstorm同步测试服务器
  • 表单中readonly的input等标签，禁止光标进入（focus）的几种方式
  • 开源地图数据可视化库——mapnik
  • 嵌入式文件系统
  • 视频flv转mp4最快的几种方法（就是不用格式工厂）
  • 我这样减少了26.5M Java内存！
  • 一份游戏开发学习路线
  • 一个项目push到多个远程Git仓库
  • 移动端 h5开发相关内容总结(三)
  • MyCAT水平分库
  • # Panda3d 碰撞检测系统介绍
  • #我与Java虚拟机的故事#连载19：等我技术变强了，我会去看你的 ​
  • (c语言版)滑动窗口 给定一个字符串，只包含字母和数字，按要求找出字符串中的最长（连续）子串的长度
  • (LeetCode) T14. Longest Common Prefix
  • （二）七种元启发算法（DBO、LO、SWO、COA、LSO、KOA、GRO）求解无人机路径规划MATLAB
  • （附源码）spring boot智能服药提醒app 毕业设计 102151
  • (汇总)os模块以及shutil模块对文件的操作
  • (解决办法)ASP.NET导出Excel，打开时提示“您尝试打开文件'XXX.xls'的格式与文件扩展名指定文件不一致
  • （十五）Flask覆写wsgi_app函数实现自定义中间件
  • (四) 虚拟摄像头vivi体验
  • （转）LINQ之路
  • (转)setTimeout 和 setInterval 的区别
  • (转载)虚函数剖析
  • .bat批处理（九）：替换带有等号=的字符串的子串
  • .NET Core 实现 Redis 批量查询指定格式的Key
  • .NET Core中Emit的使用