《数据结构》上机实验(第四章)——串
·
1. 假设串采用顺序串存储，设计一个算法Strcmp(s)，按字典顺序比较两个串s和t的大小。
- 算法思想：
- 比较s和t的长度：
①两者相等时返回0；
②s的长度大于t的长度，返回1；
③s的长度小于t的长度，返回-1。- 长度相等时比较对应字符：
①若s的字符大于的字符，返回1；
②若s的字符小于t的字符，返回-1；
③若s的字符等于t的字符，按上述规则继续比较。
int Compare(SqString s, SqString t)
{
int i, result;
if (s.length < t.length) result = -1;
else if (s.length > t.length) result = 1;
else result = 0;
if (result == 0)
for (i = 0; i < s.length; i++)
{
if (s.data[i] > t.data[i]) result = 1;
if (s.data[i] < t.data[i]) result = -1;
else result = 0;
}
return result;
}
运行结果
- s：“intermediary”
- t："intermediary "
- "intermediary "是一个长度为13的串，其中含有一个空格字符。
- 运行结果：
2. 假设串采用顺序串存储，设计一个算法求串s中出现的第一个最长的连续相同字符构成的平台。
SqString LongestString(SqString s)
{
SqString t;
int maxlength = 0, i = 0, j, k = 0;
while (k<s.length)
{
if (s.data[k] != ' ') i++; //i用来统计子串的长度
else i = 0; //遇到空格后，i重新开始计数
if (i >= maxlength)
{
maxlength = i;
j = k; //j为每段子串的终止下标
}
k++; //遍历字符串
}
printf("最长子串的长度为：%d\n该子串的终止下标为：%d\n", maxlength, j);
for (i = 0; i < maxlength; i++)
{
t.data[i] = s.data[j - maxlength + 1 + i];
printf("%c", t.data[i]);
}
运行结果
- 根据子串的终止下标以及子串的长度推测出子串的起始下标，再进行赋值操作。
- 运行结果：
3. 假设串采用链串存储，设计一个算法把串s中最先出现的子串"ab"改为"xyz"。
- 算法思想：在串s中找到最先出现的子串"ab"，即p指向data域值为’a’的结点，其后继结点是data域值为’b"的结点。将它们的data域值分别改为’x和’z’，再创建一个data域值为’y’的结点(由q指向它)，将其插人到p所指的结点之后。
bool Repl(LinkStrNode*& s)
{
LinkStrNode* p = s->next, * q ;
while (p != NULL)
{
if (p->data == 'a' && p->next->data == 'b')
{
p->data = 'x';
p = p->next;
p->data = 'y';
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = 'z';
q->next = p->next;
p->next = q;
break;
}
else p = p->next;
}
if (p == NULL) return false;
return true;
}
运行结果
- 运行结果：
4. 有两个顺序串s1和s2，求顺序串s3，该串中的字符是s1和s2中的公共字符(即两个串都包含的字符)。
- 算法思想：扫描s1，对于当前字符s1.data[i]，若它在s2中出现，则将其加人到串s3中，最后返回s3串。
#include<stdio.h>
#define MaxSize 50
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int length;
}SqString;
void CreateString(SqString& s, ElemType cstr[])
{
int i;
for (i = 0; cstr[i] != '\0'; i++)
s.data[i] = cstr[i];
s.length = i;
}
void PrintString(SqString s)
{
for (int i = 0; i < s.length; i++)
printf("%c", s.data[i]);
}
SqString CommonChar(SqString s1, SqString s2)
{
SqString s3;
int i=0 , j=0 , k = 0;
while (i < s1.length)
{
if (s1.data[i] == s2.data[j])
{
s3.data[k++]=s1.data[i];
i++;
j = 0;
}
else
{
if (j < s2.length) j++;
else
{
i++;
j = 0;
}
}
}
s3.length = k;
printf("\ns3：");
PrintString(s3);
return s3;
}
int main()
{
SqString s1, s2;
ElemType cstr1[] = "floccinaucinihilipilification";
CreateString(s1, cstr1);
printf("s1：");
PrintString(s1);
ElemType cstr2[] = "antidisestablishmentarianism";
CreateString(s2, cstr2);
printf("\ns2：");
PrintString(s2);
CommonChar(s1, s2);
return 0;
}
运行结果
5. 在顺序串s1中从后向前查找子串，即求s2在s1中最后一次出现的位置。
- 算法思想：采用简单模式匹配算法。用k来记录每次t子串成功出现的起始下标，k的初始值为-1。如果s循环结束，k的值没发生变化，说明t不是s的子串；否则返回k的值。
int index(SqString s,SqString t)
{
int i = s.length - 1, j = 0, k = -1;
while (i > 0)
{
if (s.data[i] == t.data[j])
{
i--;
j++;
}
else
{
i--;
j = 0;
}
if (j >= t.length)
{
k = i + 1;
printf("\nk=%d", k);
j = 0;
}
}
return k;
}
运行结果
6. 判断一个字符串s是否为形如"序列1@序列2”模式的字符序列，其中序列1和序列2都不含有’@'字符，且序列2是序列1的逆序列。例如"a+b@b+a"属于该模式的字符序列，而"1+3@3-1"不是。
- 方法一：头尾进行对比。
bool symm(SqString s)
{
int i=0, j=s.length-1;
while (i != j)
{
if (s.data[i] == s.data[j])
{
i++; j--;
}
else return false;
}
DestoryStack(st);
return true;
}
- 方法二：建立一个临时栈st并初始化为空，其元素为char类型。扫描顺序串s的字符，将"@"之前的字符进栈。继续扫描顺序串s中’@'之后的字符，每扫描个字符e，退栈一个字符x，若退栈时溢出或e或不等于x，则返回false。循环结束后，若栈不空，返回false。最后销毁栈st并返回最终结果。
bool symm(SqString s)
{
SqStack st;
char c;
InitStack(st);
int i = 0;
while(i<s.length)
{
if (s.data[i] != '@') Push(st, s.data[i]);
else break;
i++;
}
i++;
while (i < s.length)
{
if(!Pop(st, c)) return false; //第一个字符为@的情况
if (c != s.data[i]) return false;
i++;
}
if (!StackEmpty(st)) return false;
DestoryStack(st);
return true;
}
运行结果
7. 采用顺序结构存储串，求串s中出现的第一个最长重复子串的下标和长度。
void maxsubstr(SqString s)
{
int count = 0, i = 0, j=1, maxlen = 0, k;
while (j < s.length)
{
if (s.data[i] == s.data[j])
{
count++;
i++; j++;
}
else
{
if (maxlen < count)
{
maxlen = count + 1;
k = i - count;
}
count = 0;
i++; j++;
}
}
printf("\n下标：%d 长度：%d ", k, maxlen);
}
运行结果
8. 采用顺序结构存储串，计算指定子串在一个字符串中出现的次数，如果该子串不出现则为0。
int substrcount(SqString s, SqString t)
{
int i = 0, j = 0, count = 0;
while(i < s.length)
{
if (s.data[i] == t.data[j])
{
i++; j++;
}
else
{
if (j >= t.length)
{
count++;
printf("\n下标：%d", i-t.length);
i = i - j + 1;
}
else i++;
j = 0;
}
}
return count;
}
运行结果
9. 计算顺序串s中每一个字符出现的次数。
- 算法思想：设计一个结构体数组cnum用于存放顺序串s中出现的字符和出现的次数。用i扫描s，用k记录cnum中的元素个数，对于s.data[i]，若在cnum数组中没有对应字符，将s.data[i]直接放到cnum中，否则将对应字符的出现次数增1。
typedef struct
{
char c; //字符
int num; //字符计数
}CType;
int fun(SqString s,CType cnum[])
{
int i, j, k = 0; //K记录cnum中的元素个数
for (i = 0; i < s.length; i++)
{
if (k == 0) //cnum中没有元素时将s.data[i]直接放到cnum中
{
cnum[k].c = s.data[i];
cnum[k].num = 1;
k++;
}
else //cnum中存在元素时查找是否有相同的字符
{
for (j = 0; j < k && s.data[i] != cnum[j].c; j++);
if (j >= k) //s.data[i]放入cnum数组中
{
cnum[k].c = s.data[i];
cnum[k].num = 1;
k++;
}
else cnum[j].num++;
}
}
return k;
}
int main()
{
SqString s;
CType cnum[MaxSize];
int i, k;
ElemType cstr1[] = "sun@day!^_^August";
StrAssign(s, cstr1);
printf("s：");
DispStr(s);
printf("\n");
k=fun(s, cnum);
for (i = 0; i < k; i++)
printf("%c %d\n", cnum[i].c, cnum[i].num);
return 0;
}
运行结果
10. 在链串上实现判断两个串是否相等的功能。
- 算法思想：扫描两个链串，并同步比较当前结点值是否相等，若不相等返回false；否则继续比较到结束，若均相等且均结束，则返回true。
bool Equal(LinkStrNode* s, LinkStrNode* t)
{
LinkStrNode* p=s->next, * q=t->next;
while (p != NULL && q != NULL)
{
if (p->data == q->data)
{
p = p->next;
q = q->next;
}
else return false;
}
if (p == NULL && q == NULL) return true;
else return false;
}
11. 假设采用链串存储结构，在链串s中找子串t最后出现的首字符的序号(逻辑序号，序号从1开始)，如果串t不是串s的子串，返回0。
- 算法思想：采用BF模式匹配算法的思路。idx用于求子串在s中最后出现的首字符的序号，其初值为0。用p扫描链串s，i记录结点p的逻辑序号，初始值为0，当p不为NULL时循环：i增1，q=p，r指向串的首结点，当两结点的值相同时循环，即q、r指针均后移一个结点，如果r为NULL，表示找到了一个子串，置idx=i。循环结束，最后返回idx。
int LastPos(LinkStrNode* s, LinkStrNode* t)
{
int i = 0, idx = 0;
LinkStrNode* p = s->next, * q, * r;
while (p != NULL)
{
i++;
q = p;
r = t->next;
while (q != NULL && r != NULL && q->data == r->data)
{
q = q->next;
r = r->next;
}
if (r == NULL) idx = i;
p = p->next;
}
return idx;
}
运行结果
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
13
0- 0
已为社区贡献5条内容
所有评论(0)