0

私は双方向にリンクされたリストの一連の関数に取り組んできました.リストに要素を挿入するのに問題がありましたが、リストをソートされた順序に保ちます. したがって、{3, 4, 6} のリストがあり、5 を挿入すると、リストは {3, 4, 5, 6} になります。

昨夜書き直した後、最新のコードを完成させました。コメントして、より良い方法があれば教えてください。ヘッダーファイルとcファイルの両方を投稿しています。指摘したいことの 1 つは、現在のノードへのポインターを使用せず、一時的な配置で新しいノードを作成する挿入関数でポインターを 1 つだけ作成することです。

リスト.H

/* custom types */

typedef struct node
{
    int val;
    struct node * next;
    struct node * prev;
}Node;

typedef struct list
{
    Node * head;
    Node * tail;
}List;

/* function prototypes */

/* operation: creates a list */
/* pre: set equal to a pointer to a list*/
/* post: list is initialized to empty */
List* NewList();

/* operation: Insert a number into a list sorted */
/* pre: plist points to a list, num is an int */
/* post: number inserted and the list is sorted */
void Insert(List * plist, int x);

リスト.C

/* c file for implentation of functions for the custome type list */
/* specifically made for dueling lists by, Ryan Foreman */

#include "List.h"
#include <stdlib.h> /* for exit and malloc */
#include <stdio.h>

List* NewList()
{
    List * plist = (List *) malloc(sizeof(List));
    plist->head = NULL;
    plist->tail = NULL;
    return plist;
}

void Insert(List * plist, int x)
{
    /* create temp Node p then point to head to start traversing */
    Node * p = (Node *) malloc(sizeof(Node));
    p->val = x;

    /* if the first element */
    if ( plist->head == NULL) {
        plist->head = p;
        plist->tail = p;
    }
    /* if inserting into begining */
    else if ( p->val < plist->head->val ) {
        p->next = plist->head;
        plist->head->prev = p;
        plist->head = p;
    }

    else {
        p->next = plist->head;
        int found = 0;
        /* find if there is a number bigger than passed val */
        while((p->next != NULL) && ( found == 0)) {
            if(p->val < p->next->val)
                found = 1;
            else {
                p->next = p->next->next;
            }
        }
        /* if in the middle of the list */
        if(found == 1)
        {
            p->prev = p->next->prev;
            p->next->prev = p;
        }
        /* if tail */
        else {
            plist->tail->next = p;
            p->prev = plist->tail;
            plist->tail = p;
        }
    }
}

コードに関するご意見ありがとうございます。コメントをお待ちしております。

4

2 に答える 2

1

malloc（）はメモリをゼロにしない、最初のノードをnext / prevに設定しないため、2番目のノード> =最初のノード値、つまり終了条件p-> next！= NULLが満たされない場合、whileループが永久に続く可能性があります。

于 2013-02-05T19:48:34.810 に答える
1

C' の使用に関するいくつかのコメント。

  • C では、voidポインタからオブジェクトへのポインタへのキャストは不要です。
  • mallocそのようなライブラリでリターンを確認することをお勧めします。
于 2013-02-05T19:13:55.830 に答える