Сортировка слиянием 2 отсортированный связанный список


Мои навыки кодирования довольно ржавый и тем более, я никогда не обращал внимание на написание элегантного кода. Я хочу начать на этом. Проблема заключается в слиянии 2 отсортированный связанный список. Алгоритмически это банально, но выглядит хорошо, Проблема в практике кодирования.

struct node
{
 char *data;
 struct node *nextp;
}

typedef struct node node;
typedef struct node list; //I do 2 typedefs here to signify when conceptually I
//mean a whole list and when just a single node.is this a good practice? or only  
//one that confuses.

node * add(node *listp, char *data)
{
 node * newp=(node *)malloc(sizeof(node));
 assert(newp != NULL);
 newp->data=(char *)malloc(sizeof(strlen(data));
 assert(newp->data != NULL);
 strcpy(newp->data,data); // allocate space in newp->data . should there be +1?
 newp->next=NULL;
 if(listp==NULL) 
  listp=nextp ;
 else
  listp->nextp=newp;
 return newp;
}

list *mergelist(list * list1p, list *list2p)
{
// initialize mergedlistp;
node dummy;
node* mergedlistendp=&dummy;
list* leftlistp = NULL;

if (list1p == NULL) leftlistp=list2p;
if(list2p == NULL) leftlistp = list1p;

if(list1p != NULL && list2p!= NULL)
{
while(1)
{

 if(strcmp(list1p -> data,list2p -> data) <=0)
 {
  mergedlistendp=add (mergedlistendp,list1p->data);
  list1p=list1p -> next;
  if(list1p == NULL)
  {leftlistp=list2p; break;}
 }
 else
 {
  mergedlistendp=add (mergedlistendp,list2p->data);
  list2p=list2p -> next;
  if(list2p == NULL)
  {leftlistp=list1p; break;}
 }

}

for(leftlistp!=NULL;leftlistp = leftlistp->next) 
add(mergedlistendp,leftlistp->data);

return mergedlistendp; // I have to return mergedlistp here (i.e. head of list)
//. How to store address of mergedlistendp the first time it is assigned a value?
}

Я хочу, чтобы мой код, чтобы быть пересмотрены.Любой отзыв о наименовании, выполнение программы, правильность, лучше кода, отступы, идиом и т. д. приветствуется. Пожалуйста, посоветуйте, как угловые случаи обрабатываются более элегантно.



980
7
задан 29 мая 2011 в 12:05 Источник Поделиться
Комментарии
2 ответа

Вам следовало бы добавить проверку ошибок:

 node * newp=(node *)malloc(sizeof(node));
newp->data=(char *)malloc(sizeof(strlen(data));

функция malloc может вернуть null, если там не будет достаточно виртуальный адрес пространства. Было бы здорово, если бы вернуть функции код ошибки.

добавить {} он может кусать в следующий раз

  if(listp==NULL) 
listp=nextp ;
else
listp->nextp=newp;
//next live goes here, looks like next statment in else, but it's not.

Использовать PascalCase или верблюжьего

// initialize mergedlistp;
node* mergedlistendp=NULL; // mergedList is a better name
list* leftlistp = NULL;

Придерживаться одного стиля, когда вы:

if (list1p == NULL) leftlistp=list2p;
if(list2p == NULL) leftlistp = list1p;

еще один

  if(listp==NULL) 
listp=nextp ;

или

  if(list2p == NULL)
{leftlistp=list1p; break;}

Одно заявление на одну линию

 if(list2p == NULL)
{leftlistp=list1p; break;} // put break in the next line.

7
ответ дан 29 мая 2011 в 01:05 Источник Поделиться


  • использовать константные , когда функция не изменится аргумент

    node * add(node *listp, const char *data)

  • не привести возвращаемое значение функции malloc(). Литье сервер никакой полезной цели и может скрыть ошибки (в частности, невключение и неправильные предположения, сделанные компилятор о типе возврата)

  • (субъективно) добавить описание для утверждения более легко определить, где они происходят

    assert(newp != NULL && "malloc failed to create node");

  • (субъективно) один пробел отступ слишком маленький

6
ответ дан 29 мая 2011 в 02:05 Источник Поделиться