动态顺序串的基本实现

SString.h

#pragma once
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define SIZE 10//初始的内存大小

typedef struct String
{
	char* ch;
	int size;
	int capacity;
}String;

//初始化串
void initString(String* ps);

//扩容
void newCapacity(String* ps);

//打印串
void printString(const String* s);

//输入数据
void enterData(String* ps, char* ch);

//销毁串
void destroyString(String* ps);

//求子串
void subString(String* sub, const String* ps, int pos, int len);

//串的比较
int strCompare(const String* s, const String* t);

//串的定位--返回位置（朴素匹配算法）
int index(const String* s, const String* t);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

SString.cpp

#include "SString.h"

//初始化串
void initString(String* ps)
{
	ps->ch = (char*)malloc(SIZE * sizeof(char) + 1);
	if (NULL == ps->ch)
	{
		cout << strerror(errno) << endl;//创建失败打印错误信息
		exit(-1);
	}
	ps->ch[0] = '#';//下标为0不放数据
	ps->size = 0;
	ps->capacity = SIZE;
}

//扩容
void newCapacity(String* ps)
{
	assert(ps);
	int NewCapacity = ps->capacity * 2;
	char* pc = (char*)realloc(ps->ch, NewCapacity * sizeof(char) + 1);
	if (NULL == pc)
	{
		cout << strerror(errno) << endl;//创建失败打印错误信息
		exit(-1);
	}
	ps->ch = pc;
	ps->capacity = NewCapacity;
}

//打印串
void printString(const String* ps)
{
	assert(ps);
	if (0 == ps->size)
	{
		cout << "串中无数据" << endl;
		return;
	}
	cout << "串： ";
	for (int i = 1; i <= ps->size; i++)
	{
		cout << ps->ch[i] << " ";
	}
	cout << endl;
}

//输入数据
void enterData(String* ps, char* ch)
{
	int len = strlen(ch);
	if (len > ps->capacity)
	{
		newCapacity(ps);
	}
	int i = 0;
	while ('\0' != ch[i])
	{
		ps->ch[i + 1] = ch[i];
		i++;
	}
	ps->size = len;
}

//销毁串
void destroyString(String* ps)
{
	assert(ps);
	free(ps->ch);
	ps->ch = NULL;
	ps->size = ps->capacity = 0;
}

//求子串
void subString(String* sub, const String* ps, int pos, int len)
{
	assert(ps);
	//判断子串是否合法
	if (pos + len - 1 > ps->size)
	{
		cout << "子串不合法" << endl;
		return;
	}
	for (int i = pos ; i < pos + len; i++)
	{
		sub->ch[i - pos + 1] = ps->ch[i];
	}
	sub->size = len;
}

//串的比较
int strCompare(const String* s, const String* t)
{
	assert(s);
	assert(t);
	for (int i = 1; i <= s->size && i <= t->size; i++)
	{
		if (s->ch[i] != t->ch[i])
		{
			return s->ch[i] - t->ch[i];
		}
	}
	//前面字符相同，长的更大
	return s->size - t->size;
}

//串的定位--返回位置
int index(const String* s, const String* t)
{
	assert(s);
	assert(t);
	String sub;//临时存放
	initString(&sub);
	int i = 1;
	while (i < s->size -  t->size + 1)
	{
		subString(&sub, s, i, t->size);
		if (0 == strCompare(&sub, t))
		{
			//销毁
			destroyString(&sub);
			return i;
		}
		i++;
	}
	//销毁
	destroyString(&sub);
	return 0;//s,t不相同
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130