使用C编写类sort命令功能的程序

by Posted on

sort命令是linux系统中常用的命令，它的功能是给标准输入中的行进行排序，默认是通过字典序进行排序的。今天，展示如果通过C语言编写一个类似功能的程序。

# sort <<eof
> Hello Paul.
> How are you going?
> Very well. What about you?
> I'm good.
> eof
Hello Paul.
How are you going?
I'm good.
Very well. What about you?

程序设计思路

实现该程序分三个步骤，分别编写三个函数去实现

  • 获取所有的输入行，所有输入行使用字符指针数组。
  • 对所有输入行进行排序操作
  • 打印排好序的行

这三个函数编写好了，程序也就完成了。

#define MAXLINES 1024 

int main (void)
{
    int readlines (char *lineptr[], int maxlines);
    void qsortlines (char *lineptr[], int left, int right);
    void printlines (char *lineptr[], int linenum);

    char *lineptr[MAXLINES];
    int linenum;

    if ((linenum = readlines(lineptr, MAXLINES)) >= 0) {
        qsortlines(lineptr, 0, linenum - 1);
        printlines(lineptr, linenum);
        return 0;
    } else {
        printf("Input too big to sort\n");
        return 1;
    }

}

获取所有输入行

这里使用字符指针数组保存所有输入行， 该函数返回一个int类型。我们需要定义最大行数，超过最大行数的话，那么就返回-1，表示输入文本行数过多。

int readlines (char *lineptr[], int maxlines)
{
    char line[1024];
    int n;
    int linenum = 0;
    char *tmp;

    while ((n = get_line(line)) > 0) {
        if (linenum >= maxlines || (tmp = alloc(n)) == 0) {
            return -1;
        } else {
            line[n-1] = '
int readlines (char *lineptr[], int maxlines)
{
char line[1024];
int n;
int linenum = 0;
char *tmp;
while ((n = get_line(line)) > 0) {
if (linenum >= maxlines || (tmp = alloc(n)) == 0) {
return -1;
} else {
line[n-1] = '\0';
str_cpy(tmp, line);
lineptr[linenum ++] = tmp;
}
}
return linenum;
}
';
            str_cpy(tmp, line);
            lineptr[linenum ++] = tmp;
        }
    }

    return linenum;
}

排序算法

这里我们采用了快速排序算法，来对指定行按字典序进行排序。

void qsortlines (char *lineptr[], int left, int right)
{
    if (left >= right) 
        return;

    int tmpn, i;

    tmpn = left;

    for (i = left + 1; i <= right; i++)
        if (str_cmp(lineptr[left], lineptr[i]) > 0)
            swapline(lineptr, i, ++tmpn);

    swapline(lineptr, left, tmpn);
    qsortlines(lineptr, left, tmpn - 1);
    qsortlines(lineptr, tmpn + 1, right);
}

打印所有行

这个函数功能就非常的简单了，循环遍历即可。

void printlines(char *lineptr[], int linenum)
{
    while (linenum -- > 0){
        printf("%s\n", *lineptr++);
    }

}

以上就是该程序的主体核心部分，自己在编写这个程序的时候，没有花多久，但在调试错误的时候花费了不少时间。出现bug的原因是关于指针和数组的概念没有搞清。

在C中数组名所代表的就是数组最开始的一个元素的地址，把数组名传递给一个函数时，实际上传递的是该数组第一个元素的地址。指针和数组有紧密联系，但它们还是有区别的。区别在于指针是一个变量，而数组名则不是变量

char str[] = "hello";
char *p = str;

str++;  // error
p++;  // ok

最后，附上完整代码

#include <stdio.h>

#define ALLOCSIZE 10000 /* ALLOC SIZE */

static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf; /* next free site */

char *alloc (int n)
{
    if (allocbuf + ALLOCSIZE - allocp >= n) {
        allocp += n;
        return allocp - n;
    } else {
        return 0;
    }
}

void afree (char *p)
{
    if (p >= allocbuf && p < allocbuf + ALLOCSIZE) {
        allocp = p;
    }
}

int get_line(char *s)
{
    int maxlen = 1024;

    int c,i;
    char *p = s;

    for (i = 0; (c = getchar()) != EOF && c != '\n'; i++) {
        if (p - s < maxlen -1) {
            *p++ = c;
        }
    }

    if (c == '\n') {
        if (p-s < maxlen)
            *p++ = c;
        i++;
    }

    *p = '
#include <stdio.h>
#define ALLOCSIZE 10000 /* ALLOC SIZE */
static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf; /* next free site */
char *alloc (int n)
{
if (allocbuf + ALLOCSIZE - allocp >= n) {
allocp += n;
return allocp - n;
} else {
return 0;
}
}
void afree (char *p)
{
if (p >= allocbuf && p < allocbuf + ALLOCSIZE) {
allocp = p;
}
}
int get_line(char *s)
{
int maxlen = 1024;
int c,i;
char *p = s;
for (i = 0; (c = getchar()) != EOF && c != '\n'; i++) {
if (p - s < maxlen -1) {
*p++ = c;
}
}
if (c == '\n') {
if (p-s < maxlen)
*p++ = c;
i++;
}
*p = '\0';
return i;
}
void str_cpy (char *s, char *t)
{
while (*s++ = *t++ )
;
}
int str_cmp (char *s, char *t)
{
for (; *s == *t; s++, t++) {
if (*s == '\0')
return 0;
}
return *s - *t; 
}
int readlines (char *lineptr[], int maxlines)
{
char line[1024];
int n;
int linenum = 0;
char *tmp;
while ((n = get_line(line)) > 0) {
if (linenum >= maxlines || (tmp = alloc(n)) == 0) {
return -1;
} else {
line[n-1] = '\0';
str_cpy(tmp, line);
lineptr[linenum ++] = tmp;
}
}
return linenum;
}
void swapline (char *lineptr[], int i, int j)
{
char *tmp = lineptr[i];
lineptr[i] = lineptr[j];
lineptr[j] = tmp;
} 
void qsortlines (char *lineptr[], int left, int right)
{
if (left >= right) 
return;
int tmpn, i;
tmpn = left;
for (i = left + 1; i <= right; i++)
if (str_cmp(lineptr[left], lineptr[i]) > 0)
swapline(lineptr, i, ++tmpn);
swapline(lineptr, left, tmpn);
qsortlines(lineptr, left, tmpn - 1);
qsortlines(lineptr, tmpn + 1, right);
}
void printlines(char *lineptr[], int linenum)
{
while (linenum -- > 0){
printf("%s\n", *lineptr++);
}
}
#define MAXLINES 1024 
int main (void)
{
int readlines (char *lineptr[], int maxlines);
void qsortlines (char *lineptr[], int left, int right);
void printlines (char *lineptr[], int linenum);
char *lineptr[MAXLINES];
int linenum;
if ((linenum = readlines(lineptr, MAXLINES)) >= 0) {
qsortlines(lineptr, 0, linenum - 1);
printlines(lineptr, linenum);
return 0;
} else {
printf("Input too big to sort\n");
return 1;
}
}
';
    return i;
}

void str_cpy (char *s, char *t)
{
    while (*s++ = *t++ )
        ;
}

int str_cmp (char *s, char *t)
{
    for (; *s == *t; s++, t++) {
        if (*s == '
#include <stdio.h>
#define ALLOCSIZE 10000 /* ALLOC SIZE */
static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf; /* next free site */
char *alloc (int n)
{
if (allocbuf + ALLOCSIZE - allocp >= n) {
allocp += n;
return allocp - n;
} else {
return 0;
}
}
void afree (char *p)
{
if (p >= allocbuf && p < allocbuf + ALLOCSIZE) {
allocp = p;
}
}
int get_line(char *s)
{
int maxlen = 1024;
int c,i;
char *p = s;
for (i = 0; (c = getchar()) != EOF && c != '\n'; i++) {
if (p - s < maxlen -1) {
*p++ = c;
}
}
if (c == '\n') {
if (p-s < maxlen)
*p++ = c;
i++;
}
*p = '\0';
return i;
}
void str_cpy (char *s, char *t)
{
while (*s++ = *t++ )
;
}
int str_cmp (char *s, char *t)
{
for (; *s == *t; s++, t++) {
if (*s == '\0')
return 0;
}
return *s - *t; 
}
int readlines (char *lineptr[], int maxlines)
{
char line[1024];
int n;
int linenum = 0;
char *tmp;
while ((n = get_line(line)) > 0) {
if (linenum >= maxlines || (tmp = alloc(n)) == 0) {
return -1;
} else {
line[n-1] = '\0';
str_cpy(tmp, line);
lineptr[linenum ++] = tmp;
}
}
return linenum;
}
void swapline (char *lineptr[], int i, int j)
{
char *tmp = lineptr[i];
lineptr[i] = lineptr[j];
lineptr[j] = tmp;
} 
void qsortlines (char *lineptr[], int left, int right)
{
if (left >= right) 
return;
int tmpn, i;
tmpn = left;
for (i = left + 1; i <= right; i++)
if (str_cmp(lineptr[left], lineptr[i]) > 0)
swapline(lineptr, i, ++tmpn);
swapline(lineptr, left, tmpn);
qsortlines(lineptr, left, tmpn - 1);
qsortlines(lineptr, tmpn + 1, right);
}
void printlines(char *lineptr[], int linenum)
{
while (linenum -- > 0){
printf("%s\n", *lineptr++);
}
}
#define MAXLINES 1024 
int main (void)
{
int readlines (char *lineptr[], int maxlines);
void qsortlines (char *lineptr[], int left, int right);
void printlines (char *lineptr[], int linenum);
char *lineptr[MAXLINES];
int linenum;
if ((linenum = readlines(lineptr, MAXLINES)) >= 0) {
qsortlines(lineptr, 0, linenum - 1);
printlines(lineptr, linenum);
return 0;
} else {
printf("Input too big to sort\n");
return 1;
}
}
')
            return 0;
    }

    return *s - *t; 
}

int readlines (char *lineptr[], int maxlines)
{
    char line[1024];
    int n;
    int linenum = 0;
    char *tmp;

    while ((n = get_line(line)) > 0) {
        if (linenum >= maxlines || (tmp = alloc(n)) == 0) {
            return -1;
        } else {
            line[n-1] = '
#include <stdio.h>
#define ALLOCSIZE 10000 /* ALLOC SIZE */
static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf; /* next free site */
char *alloc (int n)
{
if (allocbuf + ALLOCSIZE - allocp >= n) {
allocp += n;
return allocp - n;
} else {
return 0;
}
}
void afree (char *p)
{
if (p >= allocbuf && p < allocbuf + ALLOCSIZE) {
allocp = p;
}
}
int get_line(char *s)
{
int maxlen = 1024;
int c,i;
char *p = s;
for (i = 0; (c = getchar()) != EOF && c != '\n'; i++) {
if (p - s < maxlen -1) {
*p++ = c;
}
}
if (c == '\n') {
if (p-s < maxlen)
*p++ = c;
i++;
}
*p = '\0';
return i;
}
void str_cpy (char *s, char *t)
{
while (*s++ = *t++ )
;
}
int str_cmp (char *s, char *t)
{
for (; *s == *t; s++, t++) {
if (*s == '\0')
return 0;
}
return *s - *t; 
}
int readlines (char *lineptr[], int maxlines)
{
char line[1024];
int n;
int linenum = 0;
char *tmp;
while ((n = get_line(line)) > 0) {
if (linenum >= maxlines || (tmp = alloc(n)) == 0) {
return -1;
} else {
line[n-1] = '\0';
str_cpy(tmp, line);
lineptr[linenum ++] = tmp;
}
}
return linenum;
}
void swapline (char *lineptr[], int i, int j)
{
char *tmp = lineptr[i];
lineptr[i] = lineptr[j];
lineptr[j] = tmp;
} 
void qsortlines (char *lineptr[], int left, int right)
{
if (left >= right) 
return;
int tmpn, i;
tmpn = left;
for (i = left + 1; i <= right; i++)
if (str_cmp(lineptr[left], lineptr[i]) > 0)
swapline(lineptr, i, ++tmpn);
swapline(lineptr, left, tmpn);
qsortlines(lineptr, left, tmpn - 1);
qsortlines(lineptr, tmpn + 1, right);
}
void printlines(char *lineptr[], int linenum)
{
while (linenum -- > 0){
printf("%s\n", *lineptr++);
}
}
#define MAXLINES 1024 
int main (void)
{
int readlines (char *lineptr[], int maxlines);
void qsortlines (char *lineptr[], int left, int right);
void printlines (char *lineptr[], int linenum);
char *lineptr[MAXLINES];
int linenum;
if ((linenum = readlines(lineptr, MAXLINES)) >= 0) {
qsortlines(lineptr, 0, linenum - 1);
printlines(lineptr, linenum);
return 0;
} else {
printf("Input too big to sort\n");
return 1;
}
}
';
            str_cpy(tmp, line);
            lineptr[linenum ++] = tmp;
        }
    }

    return linenum;
}

void swapline (char *lineptr[], int i, int j)
{
    char *tmp = lineptr[i];
    lineptr[i] = lineptr[j];
    lineptr[j] = tmp;
} 

void qsortlines (char *lineptr[], int left, int right)
{
    if (left >= right) 
        return;

    int tmpn, i;

    tmpn = left;

    for (i = left + 1; i <= right; i++)
        if (str_cmp(lineptr[left], lineptr[i]) > 0)
            swapline(lineptr, i, ++tmpn);

    swapline(lineptr, left, tmpn);
    qsortlines(lineptr, left, tmpn - 1);
    qsortlines(lineptr, tmpn + 1, right);
}

void printlines(char *lineptr[], int linenum)
{
    while (linenum -- > 0){
        printf("%s\n", *lineptr++);
    }

}

#define MAXLINES 1024 

int main (void)
{
    int readlines (char *lineptr[], int maxlines);
    void qsortlines (char *lineptr[], int left, int right);
    void printlines (char *lineptr[], int linenum);

    char *lineptr[MAXLINES];
    int linenum;

    if ((linenum = readlines(lineptr, MAXLINES)) >= 0) {
        qsortlines(lineptr, 0, linenum - 1);
        printlines(lineptr, linenum);
        return 0;
    } else {
        printf("Input too big to sort\n");
        return 1;
    }

}
Posted in: C

Published by 1024@phper

热爱编程，热爱生活