2.1.求next和nextval的实现
代码：
int next_one(char *str, int len) {
int result = 1;
if(len == 1 || len == 0) return len;
for (size_t i = 1; i < len; i++)
{
if(compare(str, str+len-i, i)) {
result = i+1;
//break;
}
}
return result;
}
int next(char *str, int *arr) {
int count = size(str);
if(count == 1)
{arr[0] = 0; return count;}
for (size_t i = 0; i < count; i++)//i = len
{
arr[i] = next_one(str, i);
}
return count;
}
int nextval(char *str, int *arr) {
int count = size(str);
int k = 0;
if(count == 1)
{arr[0] = 0; return count;}
for (size_t i = 0; i < count; i++)//i = len
{
k = next_one(str, i);//
if(str[i] == str[k-1]) {
arr[i] = 0;
} else {
arr[i] = k;
}
}
return count;
}
int compare(char *src_str, char *dist_str, int len) {
for(int i = 0; i < len; i++) {
if(src_str[i] != dist_str[i]) return 0;
}
return 1;
}
输出结果：
2.2展现t和p的匹配过程
- p的nextval值
- KMP的匹配过程
代码：
int KMP(char *src, char *pat) {
int len_s = size(src);
int len_p = size(pat);
int next[100];
nextval(pat, next);
int j = 0;
for(int i = 0; i < len_s; i++) {
if(src[i] == pat[j]) {
j++;
} else {
j = next[j];
}
printf("i = %d, j = %d\n", i, j);
if(j == len_p) return i-len_p+1;
}
return -1;
}
输出结果：
2.4 广义表的定义
代码：
#include "stdio.h"
typedef char* AtomType;
typedef enum{ATOM, LIST} ElemTag;
typedef struct
{
ElemTag tag;
union node
{
AtomType atom;
struct
{
struct GLnode *head,*tail;
}ptr;
};
}GLnode;
void init(GLnode *node);
void head(AtomType str);
void tail();
void traverse(GLnode *node);
void main() {
GLnode node;
init(&node);
//traverse(node);
}
void init(GLnode *node) {
GLnode glnode = *node;
glnode.tag=1;
GLnode head;
head.tag = 0;
head.atom = "apple\0";
GLnode tail;//tail list
tail.tag = 1;
glnode.ptr.head = &head;
glnode.ptr.tail = &tail;
GLnode head1,tail1;
head1.tag = 1;
tail1.tag = 0;
tail1.atom = "pear\0";
tail.ptr.head = &head1;
tail.ptr.tail = &tail1;
GLnode head2,tail2;
head2.tag = 0;
tail2.tag = 1;
head2.atom = "orange\0";
head1.ptr.head = &head2;
head1.ptr.tail = &tail2;
GLnode head3,tail3;
head3.tag = 0;
tail3.tag = 0;
head3.atom = "strawberry\0";
tail3.atom = "banana\0";
head2.ptr.head = &head3;
head2.ptr.tail = &tail3;
traverse(&glnode);
}
void head(GLnode node, AtomType str) {
if (node.tag)
{
/* code */
}
}
void traverse(GLnode *node) {
if(!node->tag) {
printf("The elem is %s\n", node->atom);
} else {
traverse(node->ptr.head);
traverse(node->ptr.tail);
}
}
3.1 统计字符串中的个数
分析：
1存放字符的数据结构需要动态地添加结点，所以选择链表保存；
2遍历字符串，然后判断链表中是否已经存在，如果不存在，新添加一个结点插入到队列；
如果存在，结点中地统计变量加1.
3 最后把链表地内容输入到文件中。
代码：
#include "stdio.h"
typedef struct
{
char ch;
int count;
struct lnode *next;
}lnode;
void init(lnode *list);
void count(lnode *list, char *str);
void insert(lnode *list, char ch);
void print(lnode *list);
void write_file(lnode *list);
void num_to_str(int num, char *str);
void main() {
lnode list;
char *str = "ahfAJOFJIOhoahf832977689 ofj___";
init(&list);
count(&list, str);
//print(&list);
write_file(&list);
}
void init(lnode *list) {
list->next = NULL;
}
void count(lnode *list, char *str) {
lnode *node = list;
while (*str)
{
if(*str >= 'A' && *str <= 'Z' || *str >= 'a' && *str <= 'z' || *str >= '0' && *str <= '9') {
while (node->next)
{
node = node->next;
if(node->ch == *str) {
node->count++;
break;
}
}
if(!node->next) {
lnode *l_node = (lnode *) malloc (sizeof(lnode));
l_node->ch = *str;
l_node->count = 1;
node->next = l_node;
l_node->next = NULL;
}
}
str++;
node = list;
}
}
void print(lnode *list) {
while (list->next)
{
list = list->next;
printf("%c", list->ch);
}
}
void write_file(lnode *list) {
FILE *file = fopen("count.txt", "a");
while (list->next)
{
list = list->next;
char str[20];
str[0] = list->ch;
str[1] = ':';
char *p = str+2;
num_to_str(list->count, p);
fputs(str, file);
}
fclose(file);
}
void num_to_str(int num, char *str) {
int count = 0;
for(int i = 0; num != 0; i++) {
str[i] = num % 10 + '0';
num = num / 10;
count++;
}
str[count] = '\n';
str[count+1] = 0;
}
输出结果：
3.2 递归实现字符串逆序
代码：
#include "stdio.h"
void reverse(char *str, int i, int j);
void swap(char *a, char *b);
int size(char *str);
void main() {
char *str = "abcd";
int i = 0;
int j = size(str) - 1;
reverse(str, i, j);
}
void reverse(char *str, int i, int j) {
if(i > j) return;
swap(&str[i], &str[j]);
reverse(str, i+1, j-1);
}
void swap(char *a, char *b) {
char temp;
temp = *a;
*a = *b;
*b = temp;
}
int size(char *str) {
int length = 0;
while(*str++) {
length++;
}
return length;
}
输出结果：
3.3 像字符串中插入字符串
分析：
s0 n-1 n s_len
t0 t_len
s0 n-1 n t_len+n-1 s_len+t_len
1.n = s_len-1
2.n<s_len-1, 先搬n到s_len-1的元素到n+t_len, 直到s_len+t_len-1.
3.再填充t0-n, 从n到n+t_len-1.
代码：
#include "stdio.h"
void insert(char *s, char *t, int n);
int size(char *str);
void main() {
char s[200] = "abcdefg";
char t[200] = "xyz";
int n = 3;
insert(s, t, 3);
printf("The string is %s", s);
}
void insert(char *s, char *t, int n) {
int s_len = size(s);
int t_len = size(t);
s[s_len+t_len] = 0;
for(int i = s_len-n-1; i >= 0; i--) {
s[n+t_len+i] = s[n+i];
}
for(int i = 0; i < t_len; i++) {
s[n+i] = t[i];
}
}
int size(char *str) {
int length = 0;
while(*str++) {
length++;
}
return length;
}
输出结果：
3.4.分S1为S1和S2.
分析：S1 len1
S2 len2 = n
S3 len3 = len1-n.
代码：
#include "stdio.h"
void format(char *s1, char *s2, char *s3, int n);
int size(char *str);
void main() {
char s1[200] = "abcdefgadfadfad";
char s2[200];
char s3[200];
int n = 10;
format(s1, s2, s3, n);
printf("The string is %s,%s,%s", s1, s2, s3);
}
void format(char *s1, char *s2, char *s3, int n) {
int count = size(s1);
int j = 0;
for(int i = 0; i < count; i++) {
if(i < n) {
s2[i] = s1[i];
} else {
s3[j++] = s1[i];
}
}
s2[n] = 0;
s3[j] = 0;
}
int size(char *str) {
int length = 0;
while(*str++) {
length++;
}
return length;
}
输出结果：
3.5. 求解二维数组是否有重复元素
代码：
#include "stdio.h"
int same_elem_matrix(int *a[3], int m, int n);
void main() {
int a1[3] = {1,3,5};
int a2[3] = {2,4,6};
int a3[3] = {25,7,9};
int *a[3] = {&a1,&a2,&a3};
same_elem_matrix(a, 3, 3);
}
int same_elem_matrix(int *a[3], int m, int n) {
int **p = a;
for(int i = 0; i < m*n; i++) {
for(int j = 0; j < 3; j++) {
for(int k = 0; k < 3; k++) {
if(i/m == j && i%n == k)break;
if(*(*(p+i/m)+i%n) == a[j][k]) {
printf("yes! the matrix has same elem.");
return 1;
}
}
}
}
printf("no! the matrix has no same elem.");
return 0;
}
输出结果：
3.6. 正负数分离
分析：
申请a[n]，b[n]记录A[n]的正负分布情况。
代码：
#include "stdio.h"
void check_number(int *A, int length);
void main() {
int a[10] = {-1,-3,5,2,-5,9,2,3,-10,-29};
check_number(a, 10);
for(int i = 0; i < 10; i++) {
printf("%d,", a[i]);
}
}
void check_number(int *A, int length) {
int b[10],c[10];
int j = 0;
int k = 0;
for(int i = 0; i < length; i++) {
if(A[i] >= 0) {
b[j++] = A[i];
} else {
c[k++] = A[i];
}
}
k = 0;
for(int i = 0; i < length; i++) {
if(i < j)A[i] = b[i];
else A[i] = c[k++];
}
}
输出结果：
