串心得 数据结构
2018-04-01 17:01:00 qq_39382769 阅读数 172

学习串的时候写的一点笔记

方便自己复习,也希望能给需要这个的人一点帮助

代码如下:

#include<bits/stdc++.h>//万能头文件,G++编译器
#define maxsize 1024
using namespace std;
int strlenth (char s[])//s代表目标串
{
    int i=0;
    while(s[i]!='\0')
    {
        i++;
    }
    return i;
}//求串的长度算法
int strconcat(char s1[],char s2[],char s[])//s1,s2代表需要连接的目标串,s2连接在s1的后面,s代表连接之后的结果串
{
    int i=0,j,len1,len2;
    len1=strlenth(s1);
    len2=strlenth(s2);
    if(len1+len2>maxsize)
        return 0;//长度不够
    i=0;
    while(s1[i]!='\0')
    {
        s[i]=s1[i];
        i++;
    }
    j=0;
    while(s2[j]!='\0')
    {
        s[i]=s2[j];
        j++;
        i++;
    }
    s[i]='\0';
    return 1;
}//两个串的连接算法
int strsub(char t[],char s[],int i,int len)//t代表结果子串,s代表目标母串,i代表从母串中的第i个字符开始取字串,len代表字串的长度
{
    int slen;
    slen=strlenth(s);
    if(i<1||i>slen||len<0||len>slen-i+1)
    {
        printf("参数不对");
        return 0;
    }
    for(int j=0;j<len;j++)
    {
     t[j]=s[i+j-1];
    }
    t[len]='\0';
    return 1;
}//求子串的算法
int strcomp(char *s1,char *s2)
{
    int i=0;
    while(s1[i]==s2[i]&&s1[i]!='\0')
        i++;
    return (s1[i]-s2[i]);
}//串比较函数
int main()
{
    char a[10]={'a','b','c','d','e','f','g','h','i','\0'};
    char b[10]={'1','2','3','4','5','6','7','8','9','\0'};
    printf("字符串a长度:%d\n",strlenth(a));
    printf("字符串b长度:%d\n",strlenth(b));
    char c[maxsize];
    strconcat(a,b,c);
    puts(c);
    char d[maxsize];
    strsub(d,c,1,5);
    puts(d);
    return 0;
}

运行结果:

有任何错误的地方欢迎各位拍砖指正哦!!!

2014-07-29 08:24:10 zesicus 阅读数 444

串(string)是由零个或多个字符组成的有限序列,又名字符串。

1、串的比较

给定两个串:s="a1a2……an", t="b1b2……bm",当满足以下条件之一时,s<t。

①n<m,且ai=bi(i=1,2,...,n)。

例如当s="hap",t="happy",就有s<t。因为t比s多两个字母。

②存在k<min(m,n),是的ai=bi(i=1,2,...,k-1)ak<bk。

例如当s="happen", t="happy", 因为 t 第5个字母ASCII值为121,而s的ASCII第五个字母值为

101,所以s<t 。

2、串的存储结构

· 串顺序存储结构

字符串存放于定长数组当中。

· 串的链式存储结构

一个节点存放一个字符,会造成很大的空间浪费,因此可以考虑一个节点存放一个或多个字符,如果最后一个节点不满,可以

用非串值字符补全(如#)。

3、匹配模式算法

· 模式匹配算法
/*******匹配模式算法*******/
int Index(String S,String T,int pos)
{
	int n,m,i;
	String sub;
	if(pos>0)
	{
		n=StrLength(S);	//得到主串S的长度
		m=StrLength(T);	//得到主串T的长度
		i=pos;
		while(i<n-m+1)
		{
			SubString(sub,S,i,m);//取主串第i个位置,长度与T相等的子串给sub
			if(StrCompare(sub,T)!=0)//如果两串不相等
				++i;
			else					//如果两串相等
				return i;	//返回i的值
		}
	}
	return 0;	//若无子串与T相等,返回0
}
/*******朴素的模式匹配算法***********/
int Index(String S,String T,int pos)
{
	int i=pos;	//i用于主串S中当前位置下标,若pos不为1,则从pos位置开始匹配
	int j=1;	//j用于子串T中当前位置下标值
	//若i小于S长度且j小于T的长度,这种算法是把长度值放在数组头
	while(i<S[0]&&j<=T[0])
	{
		if(S[i]==T[j])//两字母相等则继续
		{
			++i;
			++j;
		}
		else	//指针后退重新开始匹配
		{
			i=i-j+2;//i退回到上次匹配首位的下一位
			j=1;	//j退回到子串T的首位
		}
	}
	if(j>T[0])
		return i-T[0];
	else
		return 0;
}
/********KMP模式匹配算法********/
void get_next(String T,int *next)
{
	int i,j;
	i=1;
	j=0;
	next[1]=0;
	while(i<T[0])//处T[0]表示串T长度
	{
		if(j==0||T[i]==T[j])//T[i]表示后缀的单个字符,T[j]表示前缀的单个字符
		{
			++i;
			++j;
			next[i]=j;
			if(T[i]!=T[j])
				nextval[i]=j;
			else
				nextval[i]=nextval[j];
		}
		else
			j=next[j];//若字符不相同,则j回溯
	}
}
/*返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0*/
int Index_KMP(String S,String T,int pos)
{
	int i=pos;//i用于主串S当前下标值,若pos不为1,则从pos位置开始匹配。
	int j=1;//j用于子串T中当前位置下标值
	int next[255];//定义一next数组
	get_next(T,next);//对串T做分析,得到next数组
	while(i<=S[0]&&j<=T[0])//若i小于S的长度且j小于T的长度,循环继续
	{
		if(j==0||S[i]==T[j])//两字母相等则继续,与朴素算法增加了j=0判断
		{
			++i;
			++j;
		}
		else	//指针后退从新开始匹配
		{
			j=next[j];//j退回合适的位置,i值不变
		}
	}
	if(j>T[0])
		return i-T[0];
	else
		return 0;
}


2018-11-06 21:28:26 wh_0727 阅读数 155

1、串的概念
       字符串简称串,是一种特殊的线性表,它的数据元素仅由一个字符组成。

2、串的定义
       串(String)是由零个或多个字符组成的有限序列,又称字符串。

       其中s是串名,用双引号括起来的字符序列为串值,但引号本身并不属于串的内容。ai(1<=i<=n)是一个任意字符,它称为串的元素,是构成串的基本单位,i是它在整个串中的序号;n为串的长度,表示串中所包含的字符个数。

3、术语描述
(1)长度–串中字符的个数,称为串的长度。
(2)空串–长度为零的字符串称为空串。
(3)空格串–由一个或多个连续空格组成的串称为空格串。
(4)串相等–两个串相等,是指两个串的长度相等且对应的字符都相等。
(5)子串–串中任意连续的字符组成的子序列称为该串的子串。
(6)主串–包含子串的串为该子串的主串。
(7)模式匹配–子串的定位运算又称为模式匹配,是一个求子串的队医给字符在主串中序号的运算。被匹配的主串称为目标串,子串称为模式。

字符串场长度为n,子串个数为:n(n+1)/2+1      注:1为空串

 

串实现

1.初始化

2.拷贝

3.链接

4.插入

5.删除

6.判断是否相等

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct String
{
	char* pstr;
	int curlen;
	int totallen;//备用空间  
}String,*PString;


void StrAssign(PString pstring, char* sub)
{
	if (pstring == NULL || sub == NULL)
	{
		return;
	}
	int len = strlen(sub);
	pstring->pstr = (char*)malloc(len + 1);
	if (pstring->pstr == NULL)exit(0);
	for (int i = 0; i < len; ++i)
	{
		pstring->pstr[i] = sub[i];
	}
	pstring->pstr[len] = '\0';

	pstring->curlen = len;
	pstring->totallen = len + 1;
}

void StrCopy(PString ps1, PString ps2)
{
	if (ps1 == NULL || ps2 == NULL)
	{
		return;
	}
	int len1 = ps1->curlen;
	int len2 = ps2->curlen;
	
	if (len2 >= ps1->totallen)
	{
		char* pnewstr = (char*)malloc(len2 + 1);
		free(ps1->pstr);
		ps1->pstr = pnewstr;
		ps1->totallen = len2 + 1;
	}
	int i = 0;
	for (i; i < len2 + 1; ++i)
	{
		ps1->pstr[i] = ps2->pstr[i];
	}
	ps1->curlen = len2;
}

void StrCat(PString ps1, PString ps2)
{
	if (ps1 == NULL || ps2 == NULL)
	{
		return;
	}
	int len1 = ps1->curlen;
	int len2 = ps2->curlen;

	if (len1 + len2 >= ps1->totallen)
	{
		char* pnewstr = (char*)malloc(len1 + len2 + 1);
		for (int i = 0; i < len1; ++i)
		{
			pnewstr[i] = ps1->pstr[i];
		}
		free(ps1->pstr);
		ps1->pstr = pnewstr;
		ps1->totallen = len1 + len2 + 1;
	}

	for (int j = 0; j < len2 + 1; ++j)
	{
		ps1->pstr[j + len1] = ps2->pstr[j];
	}
	ps1->curlen = len1 + len2;
}

bool StrInsert(PString ps1, int pos, PString ps2)
{
	if (ps1 == NULL || ps2 == NULL || pos < 0 || pos > ps1->curlen)
	{
		return false;
	}
	int len1 = ps1->curlen;
	int len2 = ps2->curlen;

	if (len1 + len2 >= ps1->totallen)
	{
		char* pnewstr = (char*)malloc(len1 + len2 + 1);
		for (int i = 0; i < len1; ++i)
		{
			pnewstr[i] = ps1->pstr[i];
		}
		free(ps1->pstr);
		ps1->pstr = pnewstr;
		ps1->totallen = len1 + len2 + 1;
	}
	for (int index = len1; index >= pos; index--)
	{
		ps1->pstr[index + len2] = ps1->pstr[index];
	}
	for (int i = 0; i < len2; ++i)
	{
		ps1->pstr[i + pos] = ps2->pstr[i];
	}
	ps1->curlen = len1 + len2;
	return true;
}

bool StrDelete(PString ps, int pos, int len)
{
	if (ps == NULL || pos < 0 || pos + len > ps->curlen)
	{
		return false;
	}
	int index = pos + len;
	for (index; index <= ps->curlen; index++)
	{
		ps->pstr[index - len] = ps->pstr[index];
	}
	ps->curlen = ps->curlen - len;
	return true;
}

bool StrEqual(PString ps1, PString ps2)
{
	if (ps1 == NULL || ps2 == NULL)
	{
		return false;
	}
	if (ps1->curlen != ps2->curlen)
	{
		return false;
	}
	for (int i = 0; i < ps1->curlen; i++)
	{
		if (ps1->pstr[i] != ps2->pstr[i])
		{
			return false;
		}
	}
	return true;
}

void Print(PString ps)
{
	if (ps == NULL)
	{
		return;
	}
	int i = 0;
	for (i; i < ps->curlen; ++i)
	{
		printf("%c", ps->pstr[i]);
	}
	printf("\n");
}

void Destroyed(PString ps1)
{
	if (ps1 == NULL)
	{
		return;
	}
	free(ps1->pstr);
	ps1->pstr = NULL;
	ps1->curlen = ps1->totallen = 0;
}

 

2015-03-02 17:22:19 Dream_WHui 阅读数 417
// string.cpp : Defines the entry point for the console application.
/*-----CODE FOR FUN---------------
-------CREATED BY Dream_Whui--
-------2015-1-27-------------------*/

#include "stdafx.h"
#include <stdlib.h>
#include <iostream>
using namespace std;

#define   TRUE                    1
#define   FALSE                    0
#define   OK                        1
#define   ERROR                0
#define   OVERFLOW       -2
#define   INFEASIBLE           -1

typedef struct//定义串的结构
{
    char *ch;
    int length;
}HString;

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

int StrLength(HString S)//串的长度
{
    return S.length;
}

int StrCompare(HString S, HString T)//串比较
{
    for(int i=0; i<S.length && i<T.length; i++)
    {
        if(S.ch[i] > T.ch[i])
            return 1;
        else if(S.ch[i] < T.ch[i])
            return -1;
    }
    return S.length - T.length;
}

int ClearString(HString &S)//清空串,释放串的空间
{
    if(S.ch)
    {
        free(S.ch);
        S.ch = NULL;
    }
    S.length = 0;
    return OK;
}

int Concat(HString &T, HString S1, HString S2)//T返回S1和S2连接的新串
{
    if(T.ch)
        free(T.ch);
    T.ch = (char*)malloc( (S1.length + S2.length) * sizeof(char) );
    if(!T.ch)
        return ERROR;
    int i;
    for(i=0; i<S1.length+S2.length; i++)
    {
        if(i<S1.length)
            T.ch[i] = S1.ch[i];
        else
            T.ch[i] = S2.ch[i-S1.length];
    }
    T.ch[i] = '\0';
    T.length = S1.length+S2.length;
    return OK;
}

int SubString(HString &sub, HString S, int pos, int len)//截取从串S第pos个位置开始的len个字符,由sub返回
{
    if(pos<1 || pos>S.length || len<0 || len>S.length-pos+1)
        return ERROR;
    if(sub.ch)
        free(sub.ch);
    if(!len)
    {
        sub.ch = NULL;
        sub.length = 0;
    }
    else
    {
        sub.ch = (char*)malloc(len * sizeof(char));
        int i,j;
        for(i=pos-1, j=0; j<len; i++, j++)
            sub.ch[j] = S.ch[i];
        sub.ch[j]='\0';
        sub.length = len;
    }
    return OK;
}

int StrInsert(HString &S, int pos, HString T)//在串S的第pos个位置之前插入串T
{
    if(pos<0 || pos >S.length+1)
        return ERROR;
    S.ch = (char*)realloc(S.ch, (S.length+T.length) * sizeof(char));
    int i,j;
    for(i=S.length-1; i>=pos-1; i--)
        S.ch[i+T.length] = S.ch[i];
    for(i=pos-1, j=0; j<T.length; j++,i++)
        S.ch[i] = T.ch[j];
    S.length += T.length;
    S.ch[S.length] = '\0';
    return OK;
}

void InitString(HString &S)//初始化串
{
    S.ch = (char*)malloc(sizeof(char));
    S.ch[0] = '\0';
    S.length = 0;
}

int main(int argc, char* argv[])
{
    HString T;
    InitString(T);
    cout<<T.ch<<endl;
    char *c = "123456";
    cout<<c<<endl;
    StrAssign(T, c);
    cout<<T.ch<<endl;
    cout<<strlen(T.ch)<<endl;
    HString S;
    S.ch = "abcdef";
    S.length = 6;
    cout<<StrCompare(S,T)<<endl;
    HString P;
    InitString(P);
    Concat(P,S,T);
    cout<<"P: "<<P.ch<<" "<<P.length<<endl;
    HString sub;
    InitString(sub);
    SubString(sub,P,3,5);
    cout<<"sub: "<<sub.ch<<" "<<sub.length<<endl;
    StrInsert(P,5,sub);
    cout<<P.ch<<" "<<P.length<<endl;
    return 0;
}

2018-12-27 17:09:15 Helloirbd 阅读数 162
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
//串的顺序存储

typedef struct st{
	char *ch;       //串存放的起始地址,串中第i个字符存储在ch[i-1]中
	int length;     //串的长度
	int strsize;    //分配的存储空间的大小,如果不足,在通过realloc()分配增加空间
}string;

//串的初始化操作
string CreateNullString(){
	string s;
	s.length = 0;
	s.ch = (char*)malloc(MAXSIZE *sizeof(char));
	s.strsize = MAXSIZE;
	return s;
}

//判断空串
int isEmpty(string s){
	if (s.length == 0)
		return 1;
	else
		return 0;
}

//赋值操作
void StringAssign(string *s1, char s2[]){
	int i = 0;
	while (s2[i] != '\0')  // '\0' 是字符串的结束符,任何字符串之后都会自动加上'\0'
		i++;            //计算s2的长度
	if (i>s1->strsize){
		//所赋值的字符数组超过字符串的默认容量,则增加存储空间
		s1->ch = (char*)malloc(i*sizeof(char));
		s1->strsize = i;
	}
	s1->length = i;
	for (i = 0; i<s1->length; i++)
		s1->ch[i] = s2[i]; //从第一个字符开始逐个字符赋值
}

//串拷贝操作
void StringCopy(string *s1, string s2){
	if (s1->strsize<s2.length){
		//realloc则对malloc申请的内存进行大小的调整.
		s1->ch = (char*)realloc(s1->ch, s2.length*sizeof(char));
		s1->strsize = s2.length;
	}
	s1->length = s2.length;
	int i;
	for (i = 0; i<s1->length; i++)
		s1->ch[i] = s2.ch[i];
}

//求串的长度
int StringLength(string s){
	return s.length;
}

//串的连接操作
void concat(string *s, string s1, string s2){
	if (s->strsize<s1.length + s2.length){
		s->ch = (char*)realloc(s->ch, (s1.length + s2.length)*sizeof(char));
		s->strsize = s1.length + s2.length;
	}
	s->length = s1.length + s2.length;       //两串连接
	int i;
	for (i = 0; i<s1.length; i++)         //将s1复制到s中
		s->ch[i] = s1.ch[i];
	for (; i<s->length; i++)
		s->ch[i] = s2.ch[i - s1.length]; //将s2复制到s中去
}

//取子串操作
int substr(string s, int i, int len, string *t){
	/*
	i表示从字符串s的第i个位置开始截取(索引从1开始)
	len表示截取字符串的长度
	*/
	if (i <= 0 || i>s.length || len<0 || len>s.length - i + 1)    //参数不合法
		return 0;
	if (t->length<len){ //存储空间不够,继续分配存储空间
		t->ch = (char*)realloc(t->ch, len*sizeof(char));
		t->strsize = len;
	}
	t->length = len;
	int k;
	for (k = 0; k<t->length; k++)
		t->ch[k] = s.ch[i - 1 + k];
	return 1;
}

//插入操作
int insertString(string *s, int i, string t){
	//在字符串s的第i个位置插入字符串t
	if (i <= 0 || i>s->length + 1)
		return 0;
	if (s->strsize<s->length + t.length){  //空间不足
		s->ch = (char*)realloc(s->ch, (s->length + t.length)*sizeof(char));
		s->strsize = s->length + t.length;
	}
	int k;
	for (k = s->length - 1; k >= i - 1; k--) //将s中的后i个字符后移到后面
		s->ch[k + t.length] = s->ch[k];//end[][][] ==> e[][][]nd
	s->length = s->length + t.length;//s->length=3+3
	for (k = 0; k<t.length; k++)              //将t的值赋值给s
		s->ch[k + i - 1] = t.ch[k];//e[][][]nd==>eaaand
	return 1;
}

//删除操作
int deleteString(string *s, int i, int len){
	//从s的第i个字符开始删除len个字符
	if (i <= 0 || i>s->length || len<0 || len>s->length - i + 1)    //参数不合法
		return 0;
	int k;
	for (k = i + len - 1; k<s->length; k++)    //从s的i+len-1个位置开始将其后的所有字符前移
		s->ch[k - len] = s->ch[k];
	s->length -= len;
	return 1;
}

//输出操作
void print(string s){
	int i;
	for (i = 0; i<s.length; i++)
		printf("%c", s.ch[i]);
	printf("\n");
}

int main(){
	string s1 = CreateNullString();
	string s2 = CreateNullString();
	string s3 = CreateNullString();
	char ch[MAXSIZE];
	printf("请输入主串:\n");
	//输入friend
	gets(ch);
	//赋值操作
	StringAssign(&s1, ch);
	printf("主串 s1 为:");
	print(s1);
	//将字符s1拷贝到s2
	StringCopy(&s2, s1);
	printf("拷贝串操作结果如下,结果如下 s2 :");
	print(s2);
	printf("删除操作(1——s1.length-3 全删):");
	//删除操作
	deleteString(&s2, 1, s1.length - 3);
	print(s2);
	printf("插入操作,插入到s2的第2个位置上,请输入插入的字符串:");
	gets(ch);
	//赋值操作 把输入的字符放到s3中
	StringAssign(&s3, ch);
	//进行插入操作,将s3插入到s2的第二个位置上
	insertString(&s2, 2, s3);
	print(s2);
	printf("取子串操作(取s1的子串【2-4】):");
	//提取friend 中[2-4]位置元素-rie
	substr(s1, 2, 3, &s3);
	print(s3);
	//s1==>friend s3==>rie
	printf("串连接操作【将s1与s3合并】:");
	concat(&s1, s1, s2);
	print(s1);
}

 

数据结构-串

阅读数 230

计算机上的非数值处理的对象基本上是字符串数据。串是由零个或多个字符组成的有限序列,一般记为s='a1a2..an'其中s是串的名,用单引号括起来的字符系序列是串的值;ai可以是字母、数字或其他字符,串中字符的数目n称为串的长度。零个字符的串称为空串。它的长度为零。存储的时候,我们用堆存储。存储空间是在程序执行过程中动态分配而得。首先是辅助宏的定义:#defineOK1#...

博文 来自: baidu_38304645

数据结构之串

阅读数 11

感悟主要是串的初始化,连接函数,赋值函数,求串的长度。还有BF算法,但是是求所有可能出现的位置,由于我是从下标0开始存的,所以与书上的不太一样。要注意一下,当获得第一个位置之后,i和j应该怎么移动。#include<bits/stdc++.h>usingnamespacestd;vector<int>V;typedefstruct{char...

博文 来自: weixin_43918531

【数据结构】串

阅读数 352

串:是由零个或多个字符组成的有限序列,又名叫字符串。 串的抽象数据模型:StrAssign(T,*chars);/*生成串*/StrCopy(T,S);/*串S复制给串T*/ClearString(S);/*串清空*/StringEmpty(S);/*串为空,返回true,否则返回false*/St

博文 来自: inf_lmg

数据结构---串

阅读数 277

串:由零个或多个字符构成的有限序列,又叫字符串一般记为:s=”a1a2a3……an”子串和主串:串中任意个数的连续字符组成的子序列称为该串的子串子串在主串中的位置就是子串的第一个字符在主串中的序号串的比较:给定两个串:s=”a1a2a3……an”,t=”b1b2b3……bm”,当满足以下条件之一时,s串的存储结构:顺序存储结构:用一组地址连续的存储单元来存储串中的字符序列。

博文 来自: hliyang

数据结构—串

阅读数 480

一、简答题1、串的逻辑结构是什么?答:串是字符串的简称,它也是一种线性结构。串是由零个或多个字符组成的有限序列。2、空串与空格串的区别是什么?答:空串:含零个字符,长度为0;空格串:只包含空格字符。3、两个串相等的充分必要条件是什么?答:两个串相等的充分必要条件是:当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的。

博文 来自: skyejy
没有更多推荐了,返回首页