4

これは面接の質問で、他の人と共有したいと思いました。

「if」を使用せずに、リンクリストの末尾に効率的に追加するにはどうすればよいですか。

この関数からifを削除します。（?はまだifです）。

typedef struct tNode_ tNode;

struct tNode_ {
  tNode* pNext;
  int data;
};

tNode* pHead = NULL;
tNode* pTail = NULL;   

AddTail(tNode* pNode){
  if(!pTail) {
    pHead = pNode;
  }
  else {
    pTail->pNext = pNode;
  }
  pTail = pNode;
  pTail->pNext = NULL;
}
4

4 に答える 4

2

これを行う1つの（明らかにばかげた）方法は、短絡論理演算子&&との動作を使用すること||です。たとえば、次のようにすることができます。

  AddTail(tNode* pNode){
      pTail || (pHead = pNode);
      !pTail || (pTail->pNext = pNode);

      pTail = pNode;
      pTail->pNext = NULL;
 }

ptailnullの場合、最初のステートメントの最初の部分がfalseと評価され、ステートメントの後半の評価が強制されるため、これは機能します||。null以外の場合、ステートメントの後半は評価されません。同様のロジックが次のステートメントでも機能します。

とはいえ、これは非常にばかげたインタビューの質問であり、私は彼らが何をしているのか正直にわかりません。個人的には、このようなコードを書く能力を評価しようとしている誰かの知恵に疑問を投げかけます。

お役に立てれば！

于 2013-01-02T02:01:04.807 に答える
1 
typedef struct tNode_ tNode;

struct tNode_ {
  tNode* pNext;
  int data;
};

/* normal initialization for pHead */

tNode* pHead = NULL;

/* the trick is to point at where you want the next pointer to go
 * instead of saving a pointer to the node.
 */
tNode** ppTail = &pHead;

AddTail(tNode* pNode){
  pNode->pNext = NULL;
  /* update the next pointer */
  *ppTail = pNode;
  /* save the address of the next pointer */
  ppTail = &pNode->pNext;
}

main(){
  int cnt;

  tNode* pNew;

  for(cnt=0; cnt<10; cnt++){
    pNew = malloc(sizeof(tNode));
    pNew->data = cnt;
    AddTail(pNew);
  }

  for(pNew = pHead; pNew; pNew = pNew->pNext){
    printf("%d\n", pNew->data);
  }
}
于 2013-01-02T01:59:45.127 に答える
1

リストごとにダミー要素（またはセンチネルノードと呼ばれる）を使用します。ヘッドへの追加はダミーへの追加になり、テールへの追加は、定義上存在する最後の要素への追加にすぎません。

typedef struct tNode_ tNode;

struct tNode_ {
  tNode* pNext;
  int data;
};

// The Remove operation must never remove this dummy!
tNode* pDummy = (tNode*)calloc(1, sizeof(tNode));
tNode* pHead = pDummy;
tNode* pTail = pDummy;

AddTail(tNode* pNode){
  pTail->pNext = pNode;
  pTail = pNode;
  pTail->pNext = NULL;
}
于 2013-01-02T02:11:51.220 に答える
1 
tNode pHead;
tNode pTail;

void init() {
  pHead.pNext = &pTail;
  pTail.pNext = &pHead;
}

AddTail(tNode* pNode){
  pTail.pNext->pNext = pNode;
  pNode->pNext = &pHead;
  pTail.pNext = pNode;
}
于 2013-01-02T02:20:13.650 に答える