读取多行，对字符串数组排序

目标

对字符串数组排序。

例 [“doa”, “awg”, “cye”, “byte”]，排序后应为 [“awg”, “byte”, “cye”, “doa”]。

可使用的函数

操作存储空间的 alloc 函数。

#define ALLOCSIZE 10000
static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf;

char* alloc(int n) {
    // 如果空间足够
    if (allocp + n <= allocbuf + ALLOCSIZE) {
        char *temp = allocp;
        allocp += n;
        return temp;
    } else {
        printf("空间不足！");
        return 0;
    }
}
void afree(char *p) {
    if (p >= allocbuf && p < allocbuf + ALLOCSIZE) allocp = p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复制字符串的 strcp 函数。

void strcp(char *s, char *t) {
	while (*s++ = *t++);
}
1
2
3

对整数排序的 qSort 方法。

private static void qSort(int[] v, int left, int right) {
    int i, last;
    while (left < right) {
        swap(v, left, (left + right) / 2);
        last = left;
        for (i = left + 1; i <= right; i++) {
            if (v[i] < v[left]) swap(v, ++last, i);
        }
        swap(v, left, last);
        qSort(v, left, last - 1);
        left = last + 1;
    }
}
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

比较两个字符串大小的 compare 函数。

int compare(char *s, char *t) {
    for (; *s == *t; s++, t++) {
		if (*s == '\0') {
            return 0;
        }
    }
    return *s - *t;
}
1
2
3
4
5
6
7
8

读取一行的 getLine 函数。

int getLine(char *line, int maxLeng) {
    char c;
    int i;
    for (i = 0; (c = getchar()) != EOF && c != '\n' && i < maxLeng - 1; i++) {
        line[i] = c;
    }
    line[i] = '\0';
    return i;
}
1
2
3
4
5
6
7
8
9

步骤

1. 读取多行
2. 排序
3. 输出

读取多行

行数(字符串数组长度) readLines(字符串数组, 最长行数) {
	while (读取一行，该行长度 > 0 && 行数 < 最长行数) {
        存储指向该行的指针后，行数++
    }
    return 行数;
}
1
2
3
4
5
6

#define MAX_LENG 100
int readLines(char *linesPtr[], int maxLines) {
    char currentLine[MAX_LENG];
    int lineNum, leng;
    char *p;
    
    lineNum = 0;
    while (lineNum < maxLines 
          	&& (leng = getLine(currentLine, MAX_LENG)) > 0
          	&& (p = alloc(leng+1))) {
		strcp(p, currentLine);
        linesPtr[lineNum++] = p;
    }
    return lineNum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

排序

将 Java 版本的方法改造成函数。

void qSort(char *v[], int left, int right) {
    int i, last;
    while (left < right) {
        swap(v, left, (left + right) / 2);
        last = left;
        for (i = left + 1; i <= right; i++) {
            if (compare(v[i], v[left]) < 0) swap(v, ++last, i);
        }
        swap(v, left, last);
        qSort(v, left, last - 1);
        left = last + 1;
    }
}
void swap(char *arr[], int i, int j) {
    char *temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输出

int main() {
    void writeLines(char*[],int);
    char *linesPtr[100];
    char *p = alloc(0);
    int lines = readLines(linesPtr, 100);
	// 排序前
    writeLines(linesPtr,lines);
    qSort(linesPtr, 0, lines-1);
    // 排序后
    writeLines(linesPtr,lines);
    // 释放空间
    afree(p);
}
void writeLines(char *linesPtr[], int lines) {
    printf("[");
    for (int i = 0; i < lines; i++) {
        printf("\"%s\"", linesPtr[i]);
        if (i != lines-1) {
            printf(", ");
        }
    }
    printf("]\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

指针版本的输出。

void writeLines(char *linesPtr[], int lines) {
	printf("{");
	while (lines-- > 0) {
		printf("\"%s\"", *linesPtr++);
		if (lines != 0) {
			printf(", ");
		}
	}
	printf("}\n");
}
1
2
3
4
5
6
7
8
9
10

课后习题。

#define STORE_MAX_LENG 10000
int readLines(char *linesPtr[], int maxLines, char store[]) {
	
    char currentLine[MAX_LENG];
    int lineNum, leng;
    char *p = store;
    
    lineNum = 0;
    while (lineNum < maxLines 
          	&& (leng = getLine(currentLine, MAX_LENG)) > 0
			&& p + leng < store + STORE_MAX_LENG) {
		strcp(p, currentLine);
        linesPtr[lineNum++] = p;
		p += (leng+1);
    }
    return lineNum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

读取多行失败过程

p1 可以指向字符串常量，可以修改以指向其他地址。char[] 类型的变量不行，始终指向同一个位置。所以使用 char* 记录地址。

char *p1 = "abc";
printf("%d\n", p1);// 4210688

p1 = "gd";
printf("%d\n", p1);// 4210696

// 语法错误
// char *p2 = {'d', 'e', '\0'};
1
2
3
4
5
6
7
8

直接将字符串常量赋给指针，只可以访问，但不可修改字符串中的内容。所以使用 char[] 存储字符。

char *p2 = "abc";
printf("%s\n", p2);// abc
printf("%c\n", p2[0]);// a
printf("%c\n", p2[2]);// c

// 程序卡住
p2[0] = 's';
*(p2+1) = 'v';

printf("%s\n", "----");
1
2
3
4
5
6
7
8
9
10

字符串常量可以重复利用，不允许修改。

// p1 和 p3 指向同一个地方
char *p1 = "abc";
char *p2 = "acc";
char *p3 = "abc";

printf("%d\n", &p1[0]);// 4210688
printf("%d\n", &p2[0]);// 4210692
printf("%d\n", &p3[0]);// 4210688
1
2
3
4
5
6
7
8

字符数组是独一份的。推测：将字符串常量的每个字符复制到另一个地方，如 p1 指向字符串副本，副本中的每个字符可以修改。

char p1[] = "abc";
char p2[] = "acc";
char p3[] = "abc";

char *p4 = "abc";
// "abc"的"副本1"
printf("%d\n", &p1[0]);// 6422036
printf("%d\n", &p2[0]);// 6422032
// "abc"的"副本2"
printf("%d\n", &p3[0]);// 6422028
// "abc"
printf("%d\n", &p4[0]);// 4210688
1
2
3
4
5
6
7
8
9
10
11
12

对保存多个字符串的探究。

int main() {
    void readLine(char *[]);

    char *s[10];
    readLine(s);
}
void readLine(char *s[]) {
    // line 始终指向同一个位置，&line[0]
    // s[0] == s[1] == &line[0]
    // 那么输出 s[0]、s[1] 则都是输出 "cd"
    char line[100] = "ab";
    char *p = line;
    s[0] = p;

    line[0] = 'c'; line[1] = 'd';
    p = line;
    s[1] = p;

    for (int i = 0; i < 2; i++) {
        printf("%s\n", s[i]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void readLine(char *s[]) {
	char *p = "pf";
    char line[100] = "ab";
    // p[0] = line[0]，p[1] = line[1]...
    // 但 p[0] 只可访问，不可修改；程序卡住
	strcp(p, line);
    s[0] = p;

    line[0] = 'c'; line[1] = 'd';
    strcp(p, line);
    s[1] = p;
1
2
3
4
5
6
7
8
9
10
11

void readLine(char *s[]) {
	
	char p[100];
    char line[100] = "a";
    // p[0] = 'a'
	strcp(p, line);
    // s[0] = &p[0]
    s[0] = p;

    line[0] = 'c';
    // p[0] = 'c'
    strcp(p, line);
    // s[1] = &p[0]
    s[1] = p;

    // 输出两次 "c"
    for (int i = 0; i < 2; i++) {
        printf("%s\n", s[i]);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int main() {
    char *s[10];	
    readLine(s);
	// 输出乱码，而在 readLine 函数中输出则正常
    // 推测，存储空间 p 保存的地址中的内容，随着 readLine 执行完后被释放空间
    // 将 \n 去掉，输出正常，？？？
    // 将 char p[] 设置为外部变量，输出正常
    // 决断，需要外部变量或作用域更大的变量（如调用者的局部变量被当做实参）存储，alloc 是个好选择
	for (int i = 0; i < 1; i++) {
        printf("%s\n", s[i]);
    }	
}
void readLine(char *s[]) {
	char p[10];
    char line[100] = "afjla";
	strcp(p, line);
    s[0] = p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18