Manchester- 后缀子串排序

解题思路:

①:定义一个二维字符数组

②:把输入的字符串存入第一行
③:依次把其后缀字符串存入下面的几行

④:调用排序函数，对字符数组进行排序
⑤:排序完输出

以上思路是我看的在网上学习的

对应代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N 1000

int cmp(const void *a, const void *b)
{
    return strcmp((char *)a, (char *)b);
}

int main(void)
{
    int i, j, k, n;
    char s[N][N];

    while (scanf("%s", s[0]) != EOF)
    {
        n = strlen(s[0]);
        for(i=1; s[0][i]; i++)
        {
            k = 0;
            for(j=i; s[0][j]; j++)
                s[i][k++] = s[0][j];
            s[i][k] = '\0';
        }
        qsort(s, n, sizeof(s[0]), cmp);
        for(i=0; i<n; i++)
            printf("%s\n", s[i]);
    }
    return 0;
}

我的思路(提交不正确):

我的思路：

用一个结点存储一个后缀子串，然后把结点按照一定的顺序连接乘单链表

连接方法：

把字符串从第一个字符开始形成后缀子串：

如：grain

1)grain

2)rain

3)ain

4)in

5)n

每形成一个后缀子串结点，把加入到链表中

加入时：按照首字母顺序从小到大的顺序，以及相同首字母后缀子串长度短的放在前面的的思路

即：

①：形成后缀子串

②：加入到链表中（链表起始为空）

③：加入时寻找指针后移，找到第一个首字符大于等于插入结点首字符的后缀子串结束，或者找到链表末尾

      没找到自动结束

④：如果没找到，则把结点插入到末尾

⑤：找到的话再从首字符相同的后缀子串中，找到第一个长度比它大的后缀子串，然后插入到这个子串的前面

具体插入代码

void add_node(sub_string L,sub_string node)
{ /*定义个指针使它也指向头结点*/
   sub_string p=L;

    /*首先插入顺序：把字母顺序小的且长度短的放前面*/
    /*p始终指向当前结点的前一个，便于插入*/
    /*遍历到链表尾部，或者找到第一个字符大于等于它的结束：node->data[0]>p->next->data[0]*//*这句话很关键*/
       while(p->next!=NULL&&(node->data[0]>p->next->data[0]))
         p=p->next;

         /*如果p->next为空，说明没有字母顺序比node->data[0]大的，或相等的，所以把node插入到末尾*/
         if(p->next==NULL)
         {
           node->next=p->next;
           p->next=node;
         }
         else/*如果不为空，则说明找到了第一个字母顺序比node->data[0]大的或者是相等的*/
             /*接下来，再在首字母相同的子串中，找到以一个长度比它大的*/
             {/*结束条件：①没找到，也就是首字符不相等，或者②找到以一个长度比它大的*/

               while(p->next->data[0]==node->data[0]&&p->next->S_Length<node->S_Length&&p->next!=NULL)
                  p=p->next;

               /*如果到了，则是插入在首字符相同且长度比它长的子串前面*/
               /*如果没找到插入到的是第一个首字符大于它的子串的前面*/
                node->next=p->next;
                p->next=node;
               }

return ;
}

因为插入的后缀子串的长的是越来越短的，所以可以把查找首字符相同的后缀子串中第一个比长度比它长的后缀子串的过程省略，得到一下代码

void add_node(sub_string L,sub_string node)
{ /*定义个指针使它也指向头结点*/
   sub_string p=L;

    /*首先插入顺序：把字母顺序小的且长度短的放前面*/
    /*p始终指向当前结点的前一个，便于插入*/
    /*遍历到链表尾部，或者找到第一个字符大于等于它的结束：node->data[0]>p->next->data[0]*//*这句话很关键*/
       while(p->next!=NULL&&(node->data[0]>p->next->data[0]))
         p=p->next;

         /*如果p->next为空，说明没有字母顺序比node->data[0]大的，或相等的，所以把node插入到末尾*/

           node->next=p->next;
           p->next=node;



return ;
}

对应代码:（提交不正确需要圣人指点）

#include<stdio.h>
#include<malloc.h>
#include<string.h>

#define MAX 10000
typedef struct sub_string_{

  char *data;/*子串指针*/
  int S_Length;/*定义个子串长度后面就不用计算了*/
  struct  sub_string_ *next;

}*sub_string,SUB_STRING;

sub_string creat_node(char *A,int d,int length);/*创建子串结点*/
void add_node(sub_string L,sub_string node);/*添加子串结点*/
void out_put(sub_string L);/*输出子串链表*/
void free_list(sub_string L);/*初始化子串链表*/

/*-----------------------------------------------*/
int main()
{

   char A[MAX];
   sub_string node;
   SUB_STRING head;
   head.next=NULL;/*初始化头结点这样还没有指向的指针一定要赋值null，防止出错*/


     while(scanf("%s",A)!=EOF)
       {
            int length=strlen(A);

             for(int i=0;i<length;i++)
               {
                  node=creat_node(A,i,length);
                  add_node(&head,node);
               }
         out_put(&head);
         free_list(&head);/*这里把输出完的子串链表free了，不free的话输入下一组数据后
                            会在上一组数据基础继续添加子串，这个操作就相当于子串链表的初始化*/
       }
return 0;
}
/*-----------------------------------------------*/
sub_string creat_node(char *A,int d,int length)
{
    int S_length=length-d;
    /*创建子串结构体*/
    sub_string node=(sub_string)malloc(sizeof(SUB_STRING));
    /*为子串分配空间*/
    node->data=(char *)malloc((S_length+1)*sizeof(char));
     node->S_Length=S_length;/*记录子串长度*/
     node->next=NULL;

    /*复制子串数据*/
       for(int j=0,i=d;i<=length;i++)/*这里i<=length是为了直接加入反斜杠零*/
         node->data[j++]=A[i];

         /*返回结点指针*/
         return node;
}
/*-----------------------------------------------*/
void add_node(sub_string L,sub_string node)
{ /*定义个指针使它也指向头结点*/
   sub_string p=L;

    /*首先插入顺序：把字母顺序小的且长度短的放前面*/
    /*p始终指向当前结点的前一个，便于插入*/
    /*遍历到链表尾部，或者找到第一个字符大于等于它的结束：node->data[0]>p->next->data[0]*//*这句话很关键*/
       while(p->next!=NULL&&(node->data[0]>p->next->data[0]))
         p=p->next;

         /*如果p->next为空，说明没有字母顺序比node->data[0]大的，或相等的，所以把node插入到末尾*/

           node->next=p->next;
           p->next=node;



return ;
}
/*-----------------------------------------------*/
void out_put(sub_string L)
{
   sub_string p=L->next;

    while(p!=NULL)
     {
        //puts(p->data);
        printf("%s\n",p->data);
        p=p->next;
     }
  return;
}

void free_list(sub_string L)/*初始化子串链表*/
{
  sub_string p=L->next;
  L->next=NULL;/*这一部很重要，即头结点的next赋值为空，起到初始化作用*/
  sub_string delete_;
    while(p!=NULL)
     {
        delete_=p;
        p=p->next;
        free(delete_);
     }
}

别忘点赞哦-.-