プログラミングC: 投稿 14 – 二重リンクリスト
コンテンツ
二重にリンクされたリストは、リンクリスト形式ですが、各要素がリスト内でそれに先行すると、次の要素に関連付けられている
1 リストをインストールします。
の構造 1 ノード二重にリンクDSLKDのようなリストが、その前にノードへのより多くのポインタ
typedef int item;
typedef struct Node //cau truc 1 Node
{
item Data; //du lieu cua Node
Node *Left; //Con tro trai
Node *Right; //con tro phai
};
typedef struct DList //cau truc Cua List
{
Node *Head; //con tro dau
Node *Tail; //con tro cuoi
};
そのようなDSLKD DSLKKの構造は持っていない 1 最初のDSへのポインタ, リストへのDSLKK外にポインタが、それでもさらに 1 リストの最後にノードポインタ
2 空の初期化とチェック
これは、に初期化されます 2 開始および終了ポインタはNULLを返す, テストの実行がちょうど見ると空の先頭ポインタNULLポインタが十分ではありません
void Init(DList &L)
{
L.Head = NULL; // Con tro dau tro den NULL
L.Tail = NULL; // Con tro cuoi tro den NULL
}
int Isempty (DList L) //kiem tra DS rong
{
return (L.Head == NULL);
}
3. リストの長さ
DSLKKの長さを見つけるために、我々は絶対にDSLKDのように行うことができます, 開始から終了までのインスタント承認ポインタ, しかし、我々はDSLKKを使用することができます 2 カウントの開始時と終了時にカーソル
int Len (DList L) // Do dai danh sach
{
Node *PH = L.Head, *PT = L.Tail; //tao Node PH (con tro duyet tu dau DS) và PT (con tro duyet tu cuoi DS) de duyet danh sach L
int i = 0; //bien dem
if (PH != NULL) i = 1;
while (PH != NULL) //trong khi P chua tro den NULL (cuoi danh sach thi lam)
{
if (PH == PT) break;
PH = PH->Right; //cho PH tro den Node tiep theo
i++;
if (PH == PT) break;
PT = PT->Left; //cho PT tro den Node truoc do
i++;
}
return i; //tra lai so Node cua L
}
4. 作る 1 ノードPは、情報が含まれてい
Node *Make_Node (item x) //tao 1 Node P chua thong tin la x
{
Node *P = (Node *) malloc (sizeof (Node)); //Cap phat vung nho cho P
P->Data = x; //Ghi du lieu vao Data
P->Left = NULL;
P->Right = NULL;
return P;
}
5. 第一の位置に要素を挿入します
リストが空であるかどうか、リストの先頭に挿入する前にチェックする. 頭と尾のために私たちは空のリストには、Pを指している場合. 空の挿入を実行しない場合、.
void Insert_first (DList &L, item x) //Chen x vao vi tri dau tien trong danh sach
{
Node *P;
P = Make_Node(x); //tao 1 Node P
if (Isempty(L)) //Neu danh sach rong
{
L.Head = P;
L.Tail = P;
}
else
{
P->Right = L.Head;
L.Head->Left = P;
L.Head = P;
}
}
6. リストのようなリスト要素の端を差し込み
void Insert_last (DList &L, item x) //Chen x vao vi tri cuoi trong danh sach
{
Node *P;
P = Make_Node(x); //tao 1 Node P
if (Isempty(L)) //Neu danh sach rong
{
L.Head = P;
L.Tail = P;
}
else
{
L.Tail->Right = P; //ket noi voi danh sach
P->Left = L.Tail; //P tro ve Node truoc
L.Tail = P; //luu lai vi tri cuoi
}
}
7. 位置kに要素を挿入します
所定の位置に挿入する前に位置kのk個の一致をチェックする, リストまたはリストの終わりです. 私は従うリストの間に挿入した場合 4 手順
void Insert_k (DList &L, item x, int k) //chen x vao vi tri k trong danh sach
{
Node *PH = L.Head, *PT, *R;
int i=1, l = Len(L);
if (k<1 || k> l+1) printf("Vi tri chen khong hop le !"); //kiem tra dieu kien
else
{
R = Make_Node(x); //tao 1 Node P
if (k == 1) Insert_first(L,x); //chen vao vi tri dau tien
else
if (k == l+1) Insert_last(L,x); //chen vao vi tri cuoi
else //chen vao vi tri 1<k<l+1
{
while (PH != NULL && i != k-1) //duyet den vi tri k-1
{
i++;
PH = PH->Right;
}
PT = PH->Right; //xac dinh vi tri k
R->Right = PT; //(1)
R->Left = PH; //(2)
PH->Right = R; //(3)
PT->Left = R; //(4)
}
}
}
8. 最初の要素を削除する, リストの末尾
// Lay gia tri can xoa ra, sau do bo qua 1 Node dau tien
void Del_first (DList &L, item &x) //Xoa phan tu dau tien
{
if (!Isempty(L))
{
x = L.Head->Data; //lay gia tri ra neu can dung
L.Head = L.Head->Right; //Cho L tro den Node thu 2 trong danh sach
}
}
// Lay gia tri can xoa ra, sau do bo qua 1 Node cuoi
void Del_last (DList &L, item &x) //Xoa phan tu dau tien
{
if (!Isempty(L))
{
x = L.Tail->Data;
L.Tail = L.Tail->Left;
L.Tail->Right = NULL;
}
}
9. 位置kにある要素を削除する
所定の位置に削除する前に位置kのk個の一致をチェックする, 中央のリストやリスト、またはの終わりです
void Del_k (DList &L, item &x, int k) //Xoa Node k trong danh sach
{
Node *PH = L.Head, *PT;
int i=1, l = Len(L);
if (k<1 || k> l) printf("Vi tri xoa khong hop le !"); //kiem tra dieu kien
else
{
if (k == 1) Del_first(L,x); //xoa vi tri dau tien
else
if (k == l) Del_last(L,x); //xoa vi tri cuoi
else //xoa vi tri 1<k<l+1
{
while (PH != NULL && i != k-1) //duyet den vi tri k-1
{
i++;
PH = PH->Right;
}
x = PH->Right->Data;
PT = PH->Right->Right; //xac dinh vi tri k+1
PH->Right = PT;
PT->Left = PH;
}
}
}
10. DSの要素xを探す
int Search (DList L, item x) //tim x trong danh sach
{
Node *P=L.Head;
int i=1;
while (P != NULL && P->Data != x) //duyet danh sach den khi tim thay hoac ket thuc danh sach
{
P = P->Right;
i++;
}
if (P != NULL) return i; //tra ve vi tri tim thay
else return 0; //khong tim thay
}
11. DSに要素xを削除
void Del_x (DList &L, item x) //xoa phan tu x trong danh sach
{
int l = Search(L,x);
while (l)
{
Del_k (L,x,l); //trong khi van tim thay x thi van xoa
l = Search(L,x);
}
}
12. 完全なプログラム
#include <stdlib.h>
#include <stdio.h>
typedef int item;
typedef struct Node //cau truc 1 Node
{
item Data; //du lieu cua Node
Node *Left; //Con tro trai
Node *Right; //con tro phai
};
typedef struct DList //cau truc Cua List
{
Node *Head; //con tro dau
Node *Tail; //con tro cuoi
};
void Init(DList &L);
int Isempty (DList L); //kiem tra DS rong
int Len (DList L); // Do dai danh sach
Node *Make_Node (Node *P, item x); //tao 1 Node P chua thong tin la x
void Insert_first (DList &L, item x); //Chen x vao vi tri dau tien trong danh sach
void Insert_last (DList &L, item x); //Chen x vao vi tri dau tien trong danh sach
void Insert_k (DList &L, item x, int k); //chen x vao vi tri k trong danh sach
void Del_first (DList &L, item &x); //Xoa phan tu dau tien
void Del_k (DList &L, item &x, int k); //Xoa Node k trong danh sach
int Search (DList L, item x); //tim x trong danh sach
void Del_x (DList &L, item x); //xoa phan tu x trong danh sach
void Input (DList &L); //nhap danh sach
void Output (DList L); //xuat danh sach
void Init(DList &L)
{
L.Head = NULL; // Con tro dau tro den NULL
L.Tail = NULL; // Con tro cuoi tro den NULL
}
int Isempty (DList L) //kiem tra DS rong
{
return (L.Head == NULL);
}
int Len (DList L) // Do dai danh sach
{
Node *PH = L.Head, *PT = L.Tail; //tao Node PH (con tro duyet tu dau DS) và PT (con tro duyet tu cuoi DS) de duyet danh sach L
int i = 0; //bien dem
if (PH != NULL) i = 1;
while (PH != NULL) //trong khi P chua tro den NULL (cuoi danh sach thi lam)
{
if (PH == PT) break;
PH = PH->Right; //cho PH tro den Node tiep theo
i++;
if (PH == PT) break;
PT = PT->Left; //cho PT tro den Node truoc do
i++;
}
return i; //tra lai so Node cua L
}
Node *Make_Node (item x) //tao 1 Node P chua thong tin la x
{
Node *P = (Node *) malloc (sizeof (Node)); //Cap phat vung nho cho P
P->Data = x; //Ghi du lieu vao Data
P->Left = NULL;
P->Right = NULL;
return P;
}
void Insert_first (DList &L, item x) //Chen x vao vi tri dau tien trong danh sach
{
Node *P;
P = Make_Node(x); //tao 1 Node P
if (Isempty(L)) //Neu danh sach rong
{
L.Head = P;
L.Tail = P;
}
else
{
P->Right = L.Head;
L.Head->Left = P;
L.Head = P;
}
}
//Chen vao cuoi danh sach cung tuong tu
void Insert_last (DList &L, item x) //Chen x vao vi tri cuoi trong danh sach
{
Node *P;
P = Make_Node(x); //tao 1 Node P
if (Isempty(L)) //Neu danh sach rong
{
L.Head = P;
L.Tail = P;
}
else
{
L.Tail->Right = P; //ket noi voi danh sach
P->Left = L.Tail; //P tro ve Node truoc
L.Tail = P; //luu lai vi tri cuoi
}
}
void Insert_k (DList &L, item x, int k) //chen x vao vi tri k trong danh sach
{
Node *PH = L.Head, *PT, *R;
int i=1, l = Len(L);
if (k<1 || k> l+1) printf("Vi tri chen khong hop le !"); //kiem tra dieu kien
else
{
R = Make_Node(x); //tao 1 Node P
if (k == 1) Insert_first(L,x); //chen vao vi tri dau tien
else
if (k == l+1) Insert_last(L,x); //chen vao vi tri cuoi
else //chen vao vi tri 1<k<l+1
{
while (PH != NULL && i != k-1) //duyet den vi tri k-1
{
i++;
PH = PH->Right;
}
PT = PH->Right; //xac dinh vi tri k
R->Right = PT; //(1)
R->Left = PH; //(2)
PH->Right = R; //(3)
PT->Left = R; //(4)
}
}
}
void Del_first (DList &L, item &x) //Xoa phan tu dau tien
{
if (!Isempty(L))
{
x = L.Head->Data; //lay gia tri ra neu can dung
L.Head = L.Head->Right; //Cho L tro den Node thu 2 trong danh sach
}
}
void Del_last (DList &L, item &x) //Xoa phan tu dau tien
{
if (!Isempty(L))
{
x = L.Tail->Data;
L.Tail = L.Tail->Left;
L.Tail->Right = NULL;
}
}
void Del_k (DList &L, item &x, int k) //Xoa Node k trong danh sach
{
Node *PH = L.Head, *PT;
int i=1, l = Len(L);
if (k<1 || k> l) printf("Vi tri xoa khong hop le !"); //kiem tra dieu kien
else
{
if (k == 1) Del_first(L,x); //xoa vi tri dau tien
else
if (k == l) Del_last(L,x); //xoa vi tri cuoi
else //xoa vi tri 1<k<l+1
{
while (PH != NULL && i != k-1) //duyet den vi tri k-1
{
i++;
PH = PH->Right;
}
x = PH->Right->Data;
PT = PH->Right->Right; //xac dinh vi tri k+1
PH->Right = PT;
PT->Left = PH;
}
}
}
int Search (DList L, item x) //tim x trong danh sach
{
Node *P=L.Head;
int i=1;
while (P != NULL && P->Data != x) //duyet danh sach den khi tim thay hoac ket thuc danh sach
{
P = P->Right;
i++;
}
if (P != NULL) return i; //tra ve vi tri tim thay
else return 0; //khong tim thay
}
void Del_x (DList &L, item x) //xoa phan tu x trong danh sach
{
int l = Search(L,x);
while (l)
{
Del_k (L,x,l); //trong khi van tim thay x thi van xoa
l = Search(L,x);
}
}
void Input (DList &L) //nhap danh sach
{
int i=0;
item x;
do
{
i++;
printf ("Nhap phan tu thu %d : ",i);
scanf("%d",&x);
if (x != 0) Insert_k(L,x,Len(L)+1);
} while(x != 0); //nhap 0 de ket thuc
}
void Output (DList L) //xuat danh sach
{
Node *P=L.Head;
while (P != L.Tail->Right)
{
printf("%5d",P->Data);
P = P->Right;
}
printf("\n");
}
int main()
{
DList L;
Init(L);
Input(L);
Output(L);
int lua_chon;
printf("Moi ban chon phep toan voi DS LKD:");
printf("\n1: Kiem tra DS rong");
printf("\n2: Do dai DS");
printf("\n3: Chen phan tu x vao vi tri k trong DS");
printf("\n4: Tim mot phan tu trong DS");
printf("\n5: Xoa phan tu tai vi tri k");
printf("\n6: XOa phan tu x trong DS");
printf("\n7: Thoat");
do
{
printf("\nBan chon: ");
scanf("%d",&lua_chon);
switch (lua_chon)
{
case 1:
{
if (Isempty(L)) printf("DS rong !");
else printf ("DS khong rong !");
break;
}
case 2: printf ("Do dai DS la: %d.",Len(L));break;
case 3:
{
item x;
int k;
printf ("Nhap phan tu can chen vao DS: ");
scanf("%d",&x);
printf ("Nhap vi tri can chen: ");
scanf ("%d",&k);
Insert_k (L,x,k);
printf ("DS sau khi chen:\n");
Output(L);
break;
}
case 4:
{
item x;
printf ("Moi ban nhap vao phan tu can tim: ");
scanf("%d",&x);
int k=Search(L,x);
if (k) printf ("Tim thay %d trong DS tai vi tri thu: %d",x,k);
else printf ("Khong tim thay %d trong danh sach !",x);
break;
}
case 5:
{
int k;
item x;
printf ("Nhap vi tri can xoa: ");
scanf ("%d",&k);
Del_k (L,x,k);
printf ("DS sau khi xoa:\n");
Output(L);
break;
}
case 6:
{
item x;
printf ("Nhap phan tu can xoa: ");
scanf ("%d",&x);
Del_x (L,x);
printf ("DS sau khi xoa:\n");
Output(L);
break;
}
case 7: break;
}
}while (lua_chon !=7);
return 0;
}
[ポストをRPS-含ま=”2703″ ショートコード=”偽”]
マイアイン泉, 方法として画面にコードファイル内の彼の記録?
私は、ファイルどのように書かれているものを理解していません.
私は最後のためのより多くのスペースを求め, なぜ必要がありますL.Tail = P; //終了位置Aを保存?
私がいることをコメントしています. 最後の位置を保存するためのコマンド, カンチレバーの年末からポインタを削除すると、どこL.Tailを指しています, 私は新しい場所を指し示すように設定する必要があります.
大井町電子ホイアンラコンTRO L.tail-> 右ファイのTROコンTRO L.head-ヌルVEの> 規定がnull左のコーンの糞のコーンを返す必要があり、それは雑多になります? 上のEカム
E nhamラL.head-> 左ファイのTROは、VEのヌル
[はい
– 項目＃で 8 (端子素子のリストを削除します) 私は、行番号を考えます 8 L.head-必見>左= NULL.
– 項目＃で 9 (位置kにある要素を削除する) 私は、彼らはあなたがリストを削除する要素間のリンクを切断すべきだと思います(NULLか、常に削除を指すように) .
– 私は動的に割り当てられた使用ので、私は私が持っているべきであると思ったので 1 項目を削除.
[はい. このシリーズでは、私は、メモリ解放をスキップしなければなりませんでした. ありがとうございますオフラインコメント.
私はなぜwhileループを聞いてみよう:
– セクション 7 現在 14.
– セクション 9 現在 13.
PHをチェック != NULLは先生を行うには? 私は感謝します.
まだ最後の既知のヌルリストに異なることを確認してください, 他の人はあまりヌルであるが, その後、我々は正しいですT->になります, 残念になりますそうでない場合.
有用なウェブサイト. どうもありがとうございました
ありがとう, オフラインで友達と共有してください.
彼はノードに渡されるmake_node関数プロトタイプ宣言であると彼は私に尋ねた* P, しかし、なぜ先生ので、関数内でのみすべての項目xをそれを呼び出します ?
その機能は、次のように書かれています:
ノード*のMake_Node (項目X)
このように渡されたxが右にあります.
はい, 彼は私がフォーラムを聞いてみましょう ! if文に入れます(isEmpty(L)) で 2 del_first機能と何を意味するdel_lastサー ?, なぜ != ,
! 負の意味.
isEmpty(L) チェックリストは空です. それから !isEmpty(L) その負であります.
ここでCまたはC ++ SIRスターE-C ++ devの先生を実行せず.Cとして保存するコピーのコードがあります,ありがとう!
Cコードの構文C ++混合NHE. あなたは大丈夫ですCPPファイル名の拡張子.
ウェイター, ブロ内のリンクのリストについての話ません.
SME, それについては話ません.
ハニー、番号のシーケンスを属性付きの学生リストに置き換えるかどうかを尋ねることはできますか？
structonlyの入口と出口に変更する入口と出口のテストe,
このファイルからデータをインポートおよびエクスポートするか、実行を続けるかは異なりますか？ファイル内のデータを取得するために実行しましたが、常にエラーが出力されますか？
通常のeを行うだけです. printfの前 1 printf時間番号は、複数の番号または文字列です.