技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

単一リンク リストの関数インターフェイスを作成するのと同じように、まず二重リンク リストのインターフェイスをいくつか作成して、そのメイン フレームワークに慣れましょう。

＃含む<stdio.h>
＃含む<stdlib.h>

typedef int LDataType;

//双方向循環リンクリストのノード
typedef 構造体ListNode{
LDataType_データ;
//次のノードの開始位置を指す
構造体ListNode*_next;
// 前のノードの開始位置を指す
構造体 LIst* _prev;
}リストノード;

//双方向の先頭循環リンクリスト
typedef 構造体リスト{
構造体ListNode*_head;
}リスト;

構造体ListNode* createListNode(LDataType val){
構造体ListNode* ノード = (構造体ListNode*)malloc(sizeof(構造体ListNode));
ノード-&gt;_data = val;
ノード-&gt;_next = NULL;
ノード-&gt;_prev = NULL;
}

void ListInit(リスト* lst){
//空のリンクリスト
リストノードを作成します。
lst-&gt;_head-&gt;_next = lst-&gt;_head-&gt;_prev = lst-&gt;_head;

}
//末尾挿入 O(1) //先頭の前にデータを挿入 ListInsert(lst, lst-&gt;_head, val);
void リストプッシュバック(リスト* lst, LDataType val){
(lst == NULL)の場合{
戻る;
構造体ListNode* last = lst-&gt;_head-&gt;_prev;
構造体ListNode* newNode = createListNode(val);
//_head ... 最後の newNode
last-&gt;_next = 新しいノード;
newNode-&gt;_prev = 最後;

newNode-&gt;_next = lst-&gt;_head;
lst-&gt;_head-&gt;_prev = newNode;
    }
}

//Tail delete://head の前のノードを削除 ListErase(lst, lst-&gt;_head-&gt;_prev);
void ListPopBack(リスト* lst){
(lst == NULL)の場合
戻る;
//リンクされたリストが空かどうかを判断します
(lst-&gt;_head-&gt;_next == lst-&gt;_head) の場合
戻る;
構造体ListNode* last = lst-&gt;_head-&gt;_prev;
構造体ListNode* prev = last-&gt;_prev;

無料(最後);

lst-&gt;_head-&gt;_prev = 前;
前へ-&gt;_次へ = 次へ-&gt;_ヘッド;
}

void printList(リスト* lst){
構造体ListNode* cur = lst-&gt;_head-&gt;_next;
while (cur != lst-&gt;_head){
printf("%d", cur-&gt;_data);
cur = cur-&gt;_next;
    }
printf("n");
}

//ヘッド挿入//ListInsert(lst,lst-&gt;_head-&gt;_next,val);
void ListPushFront(リスト* lst, LDataType val){
(lst == NULL)の場合
戻る;
構造体ListNode* next = lst-&gt;_head-&gt;_next;
構造体ListNode* newNode = createListNode(val);

//_head、newNode、次
lst-&gt;_head-&gt;_next = 新しいノード;
newNode-&gt;_prev = lst-&gt;_head;

newNode-&gt;_next = 次へ;
次-&gt;_prev = newNode;
}

//ヘッダー削除//ListErase(lst,lst-&gt;_head-&gt;_next);
void ListPopFront(リスト* lst){
(lst == NULL || lst-&gt;_head == lst-&gt;_head)の場合
戻る;
構造体ListNode* next = lst-&gt;_head-&gt;_next;
構造体ListNode* nextnext = next-&gt;_next;
    
次next-&gt;_prev = 次-&gt;_next;
lst-&gt;_head-&gt;_next = 次の次の;

無料(次へ);
    
}

void ListErase(List* lst, struct ListNode* node){
//ヘッドノードは削除できません
(lst == NULL || lst-&gt;_head == ノード)の場合
戻る;
//前、ノード、次
構造体ListNode* prev = node-&gt;_prev;
構造体ListNode* next = node-&gt;_next;

前へ-&gt;_次へ = 次へ;
次-&gt;_prev = 前;

ノードを解放します。

}

void ListInsert(List* lst, struct ListNode* node, LDataType val){
(lst == NULL)の場合
戻る;
構造体ListNode* prev = node-&gt;_prev;
構造体ListNode* newNode = createListNode(val);

//前の newNode ノード
prev-&gt;_next = newNode;
newNode-&gt;_prev = 前;

新しいノード-&gt;_next = ノード;
ノード-&gt;_prev = newNode;
}

//破壊する
リストデストティ(リスト* lst){
もし（1st）{
もし（lst-&gt;_head）{
構造体ListNode* cur = lst-&gt;_head-&gt;_next;
while (cur != lst-&gt;_head){
構造体ListNode* next = cut-&gt;_next;
無料(現在)
次の
            }

解放します(lst-&gt;_head);
        }
    }
}

void テスト(){
リスト lst;
リストを初期化します(&lst);
リストプッシュフロント(&lst, 5);
printList(&lst);
リストプッシュフロント(&lst, 1);
printList(&lst);
リストプッシュフロント(&lst, 2);
printList(&lst);
リストプッシュフロント(&lst, 3);
printList(&lst);
リストプッシュフロント(&lst, 4);
printList(&lst);
リストポップフロント(&lst);
printList(&lst);
リストポップフロント(&lst);
printList(&lst);
リストポップフロント(&lst);
printList(&lst);

/* リストポップバック(&lst);
printList(&lst);
リストポップバック(&lst);
printList(&lst);
リストポップバック(&lst);
printList(&lst);
リストポップバック(&lst);
printList(&lst);*/
}

int main(){

テスト（）;
システム("一時停止");
0を返します。
}

シーケンスリストとリンクリストの違いと関連性:

シーケンス テーブルの長所と短所: 優れています: 空間は連続的で、ランダム アクセスをサポートし、空間使用率が高く、メモリの断片化を引き起こす可能性が低く、末尾の挿入と末尾の削除効率が高くなります。

短所: 1. 中間部分または前部分の挿入と削除の時間計算量は O(N) です。 2. 容量拡張のコストが比較的高い: コピー リリースを申請する

リンクリスト（主導型双方向ランダムリンクリスト）のメリットとデメリット

利点： 1. 任意の位置への挿入と削除の計算量は O(1) 2. 容量拡張の問題がなく、挿入するとスペースが空き、任意の位置への挿入と削除の効率が高い

短所: ノード単位で保存され、ランダム アクセスがサポートされておらず、スペース使用率が低いためメモリの断片化が発生しやすくなります。

スタックとキュー

スタック: データの挿入と削除操作が実行される一方の端のみを許可する特別な線形リスト。スタックの最上部と呼ばれ、もう一方の端はデータと呼ばれます。スタック内では LIFO (後入れ先出し) の原則に従います

スタックのプッシュ: スタックの挿入操作はプッシュ/プッシュ/プッシュと呼ばれ、挿入されたデータはスタックの先頭にあります。

ポップ: スタックの削除操作はポップと呼ばれ、ポップされるデータもスタックの最上位にあります。

プッシュ操作の実装 Push---&gt;スタックの先頭から要素を格納

シーケンステーブル：末尾挿入操作とみなせる

リンク リスト: (双方向のヘッダ付き循環リンク リスト) リストの先頭はスタックの先頭とみなされ、これは先頭の挿入であり、リストの末尾はスタックの先頭とみなされ、これは先頭の挿入です。尻尾の挿入。

ポップ操作 Pop---&gt;スタックの最上位から要素を削除します

シーケンステーブル：テーブルの末尾をスタックの先頭とし、末尾削除とみなします。

リンク リスト: (双方向の先頭循環リンク リスト) リストの先頭はスタックの先頭とみなされ、先頭の削除です。リストの末尾はスタックの先頭とみなされ、これは先頭の削除です。尾部の削除。

＃含む<stdio.h>
＃含む<stdlib.h>

typedef int STDataType;
//シーケンステーブルはスタックを実装します
typedef 構造体スタック{
STDataType* _データ;
整数_サイズ;
整数_容量;
}スタック;

void スタック初期化(スタック* st){
st == NULLの場合
戻る;
st-&gt;_data = NULL;
st-&gt;_size = st-&gt;_capacity = 0;
}

void checkCapcacity(stack* st){
st-&gt;_size == st-&gt;_capacityの場合{
int newCapcacity = st-&gt;_capacity == 0 ? 1 : 2 * st-&gt;_capacity;
st-&gt;_data = (STDataType*)realloc(st-&gt;_data, sizeof(STDataType)* newCapcacity);
st-&gt;_capacity = 新しいCapcacity;
    }

}

//スタックにプッシュ
void スタックプッシュ(スタック* st, STDataType val){
st == NULLの場合
戻る;
チェック容量(st);
//末尾の挿入
st-&gt;_data[st-&gt;_size++] = val;

}

//ポップ
void スタックポップ(スタック* st){
st == NULLの場合
戻る;
(st-&gt;_size &gt; 0)の場合
st-&gt;_size--;
}

STDataType スタックトップ(スタック* st){
st-&gt;_data[st-&gt;_size - 1]を返します。
}

int スタックサイズ(スタック* st){
st == NULLの場合
0を返します。
st-&gt;_size を返します。
}

void テスト(){
スタックst;
スタック初期化(&st);
スタックプッシュ(&st, 1);
スタックプッシュ(&st, 2);
スタックプッシュ(&st, 3);
スタックプッシュ(&st, 4);
(int i = 0; i &lt; 4; ++i)の場合{
printg("%d", スタックトップ(&st));
スタックポップ(&st);
    }
printf("n");
}

int main(){
テスト（）;
システム("一時停止");
0を返します。
}