题解 | #字符串排序#

/* 用链表实现的，空间占有较小，时间复杂度较低，但代码较为复杂 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STR_MAX_LEN 128

typedef struct node {
char data[STR_MAX_LEN];
struct node next;
}NODE,PNODE;

PNODE create_node(char *data, int len)
{
PNODE pNode;

pNode = (PNODE)malloc(sizeof(NODE));
if (NULL == pNode) {
    printf("malloc failed!\n");
    return NULL;
}

if (len > 0)
    strncpy(pNode->data, data, len);
pNode->next = NULL;

return pNode;

}

PNODE list_init(void)
{
PNODE pNode;

pNode = create_node(NULL, 0);
if (NULL == pNode)
    return NULL;

return pNode;

}

int node_compare(char data1[], char data2[], int max)
{
int i = 0;

while (data1[i] != '\0' && data2[i] != '\0' && i < max) {
    if (data1[i] > data2[i]) {
        return 1;
    }else if (data1[i] < data2[i]) {
        return -1;
    }else{
        i++;
    }
}

if (strlen(data1) > strlen(data2)) {
    //printf("!!!!!!!!!data1:%s data2:%s\n", data1, data2);
    return 1;
}else {
    //printf("?????????data1:%s data2:%s\n", data1, data2);
    return -1;
}


return 0;

}

int insert_node(PNODE head, char *data, int len)
{
PNODE cur = NULL;
PNODE prev = NULL;
PNODE pNew = NULL;

prev = head;

for (cur = head->next;cur != NULL;cur = cur->next) {
    if (NULL == head->next) {
        pNew = create_node(data, len);
        head->next = pNew;
        return 0;
    }else if (node_compare(cur->data, data, STR_MAX_LEN) >= 0) {
        pNew = create_node(data, len);
        pNew->next = cur;
        prev->next = pNew;

        return 0;
    }
    prev = cur;
}

if (NULL == cur) {
    pNew = create_node(data, len);
    pNew->next = cur;
    prev->next = pNew;
}

return 0;

}

void prt_list(PNODE head)
{
PNODE cur;
int i =0;

for (cur = head->next;cur != NULL;cur = cur->next) {
    printf("%s\n", cur->data);
    i++;
}

return ;

}

int main()
{
char data[STR_MAX_LEN] = {0};
PNODE head = list_init();
int i = 0;
int n;

scanf("%d", &n);

for (i = 0;i < n;i++) {
    scanf("%s", data);
    insert_node(head, data, strlen(data));
    memset(data, 0, STR_MAX_LEN);
}

prt_list(head);

return 0;

}