24/07/11Struktur data (6.1215) implementasi tumpukan implementasi daftar tertaut ganda

2024-07-12

Sama seperti menulis beberapa antarmuka fungsional untuk daftar tertaut tunggal, pertama-tama mari kita tulis beberapa antarmuka untuk daftar tertaut ganda agar terbiasa dengan kerangka utamanya:

#termasuk<stdio.h>
#termasuk<stdlib.h>

typedef int TipeDataL;

//Node dari daftar tertaut melingkar berkepala dua
tipedef struct ListNode{
TipeDataL _data;
//Menunjuk ke posisi awal node berikutnya
struct ListNode* _berikutnya;
//Menunjuk ke posisi awal dari node sebelumnya
struct LIst* _sebelumnya;
}NodeDaftar;

//Daftar tertaut melingkar berkepala dua
typedef struct Daftar{
struktur ListNode* _head;
}Daftar;

struct ListNode* buatListNode(TipeDataL val){
struct ListNode* node = (struct ListNode*)malloc(ukuran(struct ListNode));
simpul->_data = nilai;
node->_berikutnya = NULL;
node->_prev = NULL;
}

batalkan ListInit(Daftar* lst){
//Kosongkan daftar tertaut
lst->_head = createListNode(0);
lst->_kepala->_berikutnya = lst->_kepala->_sebelumnya = lst->_kepala;

}
//Penyisipan ekor O(1) //Masukkan data di depan kepala ListInsert(lst, lst->_head, val);
void ListpushBack(Daftar* lst, LDataType val){
jika (lst == NULL){
kembali;
struct ListNode* terakhir = lst->_head->_prev;
struct ListNode* simpulbaru = buatNodeDaftar(nilai);
//_head ... simpul baru terakhir
terakhir->_berikutnya = simpulbaru;
newNode->_prev = terakhir;

simpulbaru->_berikutnya = lst->_kepala;
lst->_head->_prev = simpulbaru;
}
}

//Tail delete://Hapus node head sebelumnya ListErase(lst, lst->_head->_prev);
batalkan ListPopBack(Daftar* lst){
jika (lst == NULL)
kembali;
//Tentukan apakah daftar tertaut kosong
jika (lst->_head->_next == lst->_head)
kembali;
struct ListNode* terakhir = lst->_head->_prev;
struct ListNode* sebelumnya = terakhir->_sebelumnya;

gratis (terakhir);

lst->_head->_prev = sebelumnya;
sebelumnya->_berikutnya = lst->_kepala;
}

void cetakDaftar(Daftar* lst){
struct ListNode* cur = lst->_head->_next;
sementara (cur != lst->_head){
printf("%d", cur->_data);
cur = cur->_berikutnya;
}
cetakf("n");
}

//Masukkan kepala//ListInsert(lst,lst->_head->_next,val);
batalkan ListPushFront(Daftar* lst, LDataType val){
jika (lst == NULL)
kembali;
struct ListNode* berikutnya = lst->_head->_next;
struct ListNode* simpulbaru = buatNodeDaftar(nilai);

//_head, simpulbaru, selanjutnya
lst->_head->_next = simpulbaru;
simpulbaru->_sebelumnya = lst->_kepala;

newNode->_next = berikutnya;
berikutnya->_sebelumnya = simpulbaru;
}

//Hapus header//ListErase(lst,lst->_head->_next);
batalkan ListPopFront(Daftar* lst){
jika (lst == NULL || lst->_head == lst->_head)
kembali;
struct ListNode* berikutnya = lst->_head->_next;
struct ListNode* nextnext = berikutnya->_berikutnya;

selanjutnyaberikutnya->_sebelumnya = selanjutnya->_berikutnya;
lst->_head->_next = berikutnyaberikutnya;

gratis(berikutnya);

}

void ListErase(Daftar* lst, struct ListNode* node){
//Tidak dapat menghapus node kepala
jika (lst == NULL || lst->_head == node)
kembali;
//sebelumnya, simpul, selanjutnya
struct ListNode* sebelumnya = node->_prev;
struct ListNode* berikutnya = node->_next;

sebelumnya->_berikutnya = berikutnya;
berikutnya->_sebelumnya = sebelumnya;

gratis(simpul);

}

void ListInsert(Daftar* lst, struct ListNode* node, LDataType val){
jika (lst == NULL)
kembali;
struct ListNode* sebelumnya = node->_prev;
struct ListNode* simpulbaru = buatNodeDaftar(nilai);

//sebelumnya simpul baru node
sebelumnya->_berikutnya = simpulbaru;
newNode->_prev = sebelumnya;

simpulbaru->_berikutnya = simpul;
node->_prev = simpulbaru;
}

//menghancurkan
ListDestoty(Daftar* lst){
jika (lst){
jika (lst->_head){
struct ListNode* cur = lst->_head->_next;
sementara (cur != lst->_head){
struct ListNode* berikutnya = potong->_berikutnya;
gratis(cur);
cur = berikutnya;
}

gratis(lst->_head);
}
}
}

batal uji(){
Daftar lst;
ListInit(&lst);
ListPushFront(&lst, 5);
cetakList(&lst);
ListPushFront(&lst, 1);
cetakList(&lst);
ListPushFront(&lst, 2);
cetakList(&lst);
ListPushFront(&lst, 3);
cetakList(&lst);
ListPushFront(&lst, 4);
cetakList(&lst);
DaftarPopFront(&lst);
cetakList(&lst);
DaftarPopFront(&lst);
cetakList(&lst);
DaftarPopFront(&lst);
cetakList(&lst);

/*ListPopBack(&lst);
cetakList(&lst);
ListPopBack(&lst);
cetakList(&lst);
ListPopBack(&lst);
cetakList(&lst);
ListPopBack(&lst);
cetakList(&lst);*/
}

int utama(){

tes();
sistem("jeda");
kembali 0;
}

Perbedaan dan hubungan antara daftar urutan dan daftar tertaut:

Kelebihan dan Kekurangan Tabel Urutan: Luar Biasa: Ruangnya kontinu, mendukung akses acak, memiliki pemanfaatan ruang yang tinggi dan tidak mungkin menyebabkan fragmentasi memori, serta memiliki efisiensi penyisipan ekor dan penghapusan ekor yang tinggi.

Kekurangan: 1. Kompleksitas waktu untuk memasukkan dan menghapus bagian tengah atau depan adalah O(N) 2. Biaya perluasan kapasitas relatif tinggi: mengajukan permohonan pelepasan salinan

Keuntungan dan kerugian dari daftar tertaut (led daftar tertaut acak dua arah)

Keuntungan: 1. Kompleksitas waktu penyisipan dan penghapusan pada posisi mana pun adalah O(1) 2. Tidak ada masalah perluasan kapasitas, penyisipan akan membuka ruang, dan efisiensi penyisipan dan penghapusan pada posisi mana pun tinggi

Kekurangan: Disimpan dalam satuan node, tidak mendukung akses acak, dan pemanfaatan ruang yang rendah dapat dengan mudah menyebabkan fragmentasi memori.

tumpukan dan antrian

Tumpukan: Daftar linier khusus yang hanya mengizinkan penyisipan dan penghapusan elemen di satu ujung di mana operasi penyisipan dan penghapusan data dilakukan disebut bagian atas tumpukan, dan ujung lainnya disebut bagian bawah tumpukan data dalam tumpukan mengikuti prinsip LIFO (last in first out).

Mendorong tumpukan: Operasi penyisipan tumpukan disebut push/push/push, dan data yang dimasukkan berada di bagian atas tumpukan

Pop: Operasi penghapusan tumpukan disebut popping, dan data popping juga berada di bagian atas tumpukan.

Implementasi operasi push push--->menyimpan elemen dari atas tumpukan

Tabel urutan: Ini dapat dianggap sebagai operasi penyisipan ekor

Daftar tertaut: (daftar tertaut melingkar berkepala dua) kepala daftar dianggap sebagai bagian atas tumpukan, yang merupakan penyisipan kepala, dan ekor daftar dianggap sebagai bagian atas tumpukan, yaitu penyisipan ekor

Operasi pop pop--->hapus elemen dari atas tumpukan

Tabel urutan: Akhir tabel dianggap sebagai bagian atas tumpukan, dan dianggap sebagai operasi penghapusan ekor.

Daftar tertaut: (daftar tertaut melingkar berkepala dua) kepala daftar dianggap sebagai bagian atas tumpukan, yang merupakan penghapusan kepala, dan ekor daftar dianggap sebagai bagian atas tumpukan, yaitu penghapusan ekor.

#termasuk<stdio.h>
#termasuk<stdlib.h>

tipedef int STDataType;
//Tabel urutan mengimplementasikan tumpukan
typedef struct tumpukan {
TipeDataST* _data;
int _ukuran;
int _kapasitas;
}tumpukan;

batalkan stackInit(tumpukan* st){
jika (st == NULL)
kembali;
st->_data = NULL;
st->_ukuran = st->_kapasitas = 0;
}

batalkan pemeriksaan kapasitas(tumpukan* st){
jika (st->_ukuran == st->_kapasitas){
int KapasitasBaru = st->_kapasitas == 0 ? 1 : 2 * st->_kapasitas;
st->_data = (STDataType*)realloc(st->_data, ukuran(STDataType)* kapasitas baru);
st->_kapasitas = kapasitasbaru;
}

}

//Dorong untuk menumpuk
batalkan stackPush(tumpukan* st, TipeDataST val){
jika (st == NULL)
kembali;
periksaKapasitas(st);
//Penyisipan ekor
st->_data[st->_ukuran++] = val;

}

//muncul
batalkan tumpukanPop(tumpukan* st){
jika (st == NULL)
kembali;
jika (st->_ukuran > 0)
st->_ukuran--;
}

TipeDataST tumpukanTop(tumpukan* st){
kembalikan st->_data[st->_size - 1];
}

int ukuran tumpukan(tumpukan* st){
jika (st == NULL)
kembali 0;
kembalikan st->_size;
}

batal uji(){
tumpukan st;
tumpukanInit(&st);
tumpukanPush(&st, 1);
tumpukanPush(&st, 2);
tumpukanPush(&st, 3);
tumpukanPush(&st, 4);
untuk (int i = 0; i < 4; ++i){
printg("%d", tumpukanAtas(&st));
tumpukanPop(&st);
}
cetakf("n");
}

int utama(){
tes();
sistem("jeda");
kembali 0;
}

Berbagi teknologi

24/07/11Struktur data (6.1215) implementasi tumpukan implementasi daftar tertaut ganda

Profil pribadi

informasi kontak saya