dynamic allocation for string array

[Jijo]

I coded a program that takes some strings and lexicographically orders the strings and its substrings. I have used dynamic memory allocation technique and its working fine for all strings without consecutive same alphabets.I use a list in which a string is placed in its exact position by moving the others right.

I am unbale to figure out whats the actual problem...

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

#include <conio.h>


char* permute(int strt, int end, char* str)
{
      char *outp=(char *)malloc(2000*sizeof(char));
      
      for(int k=strt;k<=end;k++)
         *(outp+(k-strt))=*(str+k);
      
      *(outp+end-strt+1)='\0';  
      return outp;
}

int addString(char *stra, char **stLst, int tot)
{
    if(tot==0)
    {   
        stLst[tot]=(char*)malloc(2000*sizeof(char));
        strcpy(stLst[0],stra);
        stLst[tot+1]=(char*)malloc(2000*sizeof(char));
        return 1;
    }
    else
        for(int i=tot-1;i>=0;i--)
        {
                if(strcmp(stLst[i],stra)==0)
                    return 0;
                else if(strcmp(stra,stLst[i])<=0)
                    strcpy(stLst[i+1],stLst[i]);
                else
                {
                    strcpy(stLst[i+1],stra);
                    stLst[tot+1]=(char*)malloc(2000*sizeof(char));
                    return 1;
                }
        }
}
      
  
int main() {
    
    char *str,*out;
    char** stringList = (char**)malloc(1000000* sizeof(char*));
     
    str = (char*)malloc(2000*sizeof(char));
    
    int nos=0,k,totS=0,flag=0,i;
      
    scanf("%d",&nos);
    for(k=0;k<nos;k++)
    {  
        scanf("%s",str);
        for(i=0;*(str+i)!='\0';i++)
        {
                for(int j=i;*(str+j)!='\0';j++)
                {
                    flag=0;
                    out=permute(i,j,str);
                    flag=addString(out,stringList,totS);
                    if(flag==1)
                      totS++;

                }
        }
    }
      
    for(k=0;k<totS;k++)
        printf("%s\n",stringList[k]);
  
    
    getch();
    return 0;
}

[kbw]

Do you realise that *(str + i) is the same as str[i]? You can make your code a little easier to read if you make the substitution.

You can shrink those large allocations once you know the size, for example, before permute returns, you can string that allocation with:

outp[end-strt+1]='\0';
return realloc(outp, end-strt+1);

In addString:

int addString(char *stra, char **stLst, int tot)
{
    if(tot==0)
    {   
        stLst[tot]=(char*)malloc(2000*sizeof(char));
        strcpy(stLst[0],stra);

can be written as:

int addString(char *stra, char **stLst, int tot)
{
    if (tot==0)
    {   
        stLst[tot] = strdup(stLst);

No all paths out of addString return a known value. Surely the compiler warned you of that. And that means you can rely on the return value; right?

I don't see why you keep allocating size 2000. Can't you be bothered to work out the actual size you need?

As you're using C++ and not C, you should be using a C++ container and C++ strings.

I can't follow the logic of addString/main interaction, so I can see what's wrong. But you should start by removing your compile time warnings.

[Jijo]

Actually I am not sure of *(str+i) and str[i] refers the same value. Note that str is a pointer. 2000 refers to a constraint for word length. Since the list will be updated with the strings of variable size as new strings are added - by passing it to addString function (it doesn't allow duplicates in the list and keep the lexicographical order) I cannot just allocate it with fixed lengths

[Jijo]

I modified the program using the strdup function you mentioned but stil I m getting the same errors in output.

[Yueeng]

Hi jijo!
1. I think @kwb's reply was quite useful, and about the " *(str+i) and str[i]" thing, i think he/she was right, the compiler will automaticlly add different number to the pointer according to the size of the pointer's type. It's not that stupid (:

2. I runned your program and fount out that your program does not only have problem with consecutive characters but also have problem with any string that has a substr with reversed alphabets. e.g. "wc" , in alphabets, 'c' stand before 'w', and then the program goes wrong.

This problem can be solved by adding a little bit of code in the addString() func. Like this:

 for(int i=tot-1;i>=0;i--)
        {
                if(strcmp(stLst[i],stra)==0)
                    return 0;
                else if(strcmp(stra,stLst[i])<=0)
                {
                    strcpy(stLst[i+1],stLst[i]);
                    if (i==0)
                    {
                        strcpy(stLst[i],stra);
                        stLst[tot+1]=(char*)malloc(2000*sizeof(char));
                        return 1;
                    }
                }
                else
                {
                   strcpy(stLst[i+1],stra);
                    stLst[tot+1]=(char*)malloc(2000*sizeof(char));
                    return 1;
                }

Notice that in the for loop you set
for(int i=tot-1;i>=0;i--)
and in the code block you put the string in right place you write:
strcpy(stLst[i+1],stra);
so, the minium num i could get, is 1. But it should be 0! Now you can see where the problem lies.

3. About the problem with consecutive same alphabets.
If you input:
aaaaa
output is something like:

a
aa
aa
aa
aa
aaa

I noticed that the "aa"s are not duplicated string, it was produced by permute(), think about input "aaaaa", the permute will generate ONE"aa" for string "aaaaa", ONE "aa" for string "aaaa", ONE "aa" for string "aaa", and so on... and in the sort function(which works fine), all "aa"s are sorted befor "aaa" because it's shorter. Then the "moving the others right" block of code just buried other permutation. Solution i suggest is just check if this string already exists. Like this:

bool InList(char **stLst, char sizeLst, char *stra)
{
    for (int i=0;i<sizeLst;++i)
    {
        if (strcmp(stLst[i],stra)==0)
        {
            return true;
        }
    }
    return false;
}

   if (InList(stLst,tot,stra))
        return 0;

Hope this will be helpful.