24/07/11Δομή δεδομένων (6.1215) διπλά συνδεδεμένη λίστα υλοποίηση-στοίβα implement

24/07/11Δομή δεδομένων (6.1215) διπλή συνδεδεμένη λίστα υλοποίησης-υλοποίηση στοίβας

2024-07-12

Ακριβώς όπως γράφουμε ορισμένες λειτουργικές διεπαφές για λίστες μεμονωμένα συνδεδεμένα, ας γράψουμε πρώτα μερικές διεπαφές για διπλά συνδεδεμένες λίστες για να εξοικειωθούμε με το κύριο πλαίσιο του:

#περιλαμβάνω<stdio.h>
#περιλαμβάνω<stdlib.h>

typedef int LDataType;

//Ο κόμβος της αμφίδρομης κυκλικής συνδεδεμένης λίστας
typedef struct ListNode{
LDataType _data;
//Τοποθετήστε το δείκτη στην αρχική θέση του επόμενου κόμβου
struct ListNode* _next;
//Τοποθετήστε το δείκτη στην αρχική θέση του προηγούμενου κόμβου
struct LIst* _prev;
}ListNode;

//Κυκλική συνδεδεμένη λίστα με δύο κατευθύνσεις
typedef struct List{
struct ListNode* _head;
}Λίστα;

struct ListNode* createListNode(LDataType val){
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->_data = val;
node->_next = NULL;
κόμβος->_prev = NULL;
}

void ListInit(List* lst){
//Κενή συνδεδεμένη λίστα
lst->_head = createListNode(0);
lst->_head->_next = lst->_head->_prev = lst->_head;

}
//Εισαγωγή ουράς O(1) //Εισαγωγή δεδομένων μπροστά από την κεφαλή ListInsert(lst, lst->_head, val);
void ListpushBack(List* lst, LDataType val){
αν (lst == NULL){
ΕΠΙΣΤΡΟΦΗ;
struct ListNode* last = lst->_head->_prev;
struct ListNode* newNode = createListNode(val);
//_head ... τελευταίος νέοςΚόμβος
last->_next = newNode;
newNode->_prev = τελευταίος;

newNode->_next = lst->_head;
lst->_head->_prev = newNode;
}
}

//Tail delete://Διαγραφή του προηγούμενου κόμβου της κεφαλής ListErase(lst, lst->_head->_prev);
void ListPopBack(List* lst){
εάν (lst == NULL)
ΕΠΙΣΤΡΟΦΗ;
//Προσδιορίστε εάν η συνδεδεμένη λίστα είναι κενή
αν (lst->_head->_next == lst->_head)
ΕΠΙΣΤΡΟΦΗ;
struct ListNode* last = lst->_head->_prev;
struct ListNode* prev = last->_prev;

δωρεάν (τελευταίο)

lst->_head->_prev = prev;
prev->_next = lst->_head;
}

void printList(List* lst){
struct ListNode* cur = lst->_head->_next;
ενώ (cur != lst->_head){
printf("%d", cur->_data);
cur = cur->_next;
}
printf("n");
}

//Εισαγωγή κεφαλής//ListInsert(lst,lst->_head->_next,val);
void ListPushFront(List* lst, LDataType val){
εάν (lst == NULL)
ΕΠΙΣΤΡΟΦΗ;
struct ListNode* next = lst->_head->_next;
struct ListNode* newNode = createListNode(val);

//_head, newNode, επόμενο
lst->_head->_next = newNode;
newNode->_prev = lst->_head;

newNode->_next = επόμενο;
next->_prev = newNode;
}

//Διαγραφή κεφαλίδας//ListErase(lst,lst->_head->_next);
void ListPopFront(List* lst){
αν (lst == NULL || lst->_head == lst->_head)
ΕΠΙΣΤΡΟΦΗ;
struct ListNode* next = lst->_head->_next;
struct ListNode* nextnext = next->_next;

nextnext->_prev = επόμενο->_next;
lst->_head->_next = nextnext;

δωρεάν (επόμενο);

}

void ListErase(List* lst, struct ListNode* node){
//Δεν είναι δυνατή η διαγραφή του κύριου κόμβου
if (lst == NULL || lst->_head == κόμβος)
ΕΠΙΣΤΡΟΦΗ;
//προηγούμενο, κόμβος, επόμενος
struct ListNode* prev = node->_prev;
struct ListNode* next = node->_next;

prev->_next = επόμενο;
επόμενο->_προηγούμενο = προηγ.

δωρεάν (κόμβος);

}

void ListInsert(List* lst, struct ListNode* node, LDataType val){
εάν (lst == NULL)
ΕΠΙΣΤΡΟΦΗ;
struct ListNode* prev = node->_prev;
struct ListNode* newNode = createListNode(val);

//προηγούμενος νέος κόμβος κόμβου
prev->_next = newNode;
newNode->_prev = prev;

newNode->_next = κόμβος;
node->_prev = newNode;
}

//καταστρέφω
ListDestoty(List* lst){
αν (lst){
if (lst->_head){
struct ListNode* cur = lst->_head->_next;
ενώ (cur != lst->_head){
struct ListNode* next = cut->_next;
δωρεάν (cur);
cur = επόμενος;
}

free(lst->_head);
}
}
}

void test(){
Λίστα lst;
ListInit(&lst);
ListPushFront(&lst, 5);
printList(&lst);
ListPushFront(&lst, 1);
printList(&lst);
ListPushFront(&lst, 2);
printList(&lst);
ListPushFront(&lst, 3);
printList(&lst);
ListPushFront(&lst, 4);
printList(&lst);
ListPopFront(&lst);
printList(&lst);
ListPopFront(&lst);
printList(&lst);
ListPopFront(&lst);
printList(&lst);

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

int main(){

δοκιμή();
system("pause");
επιστροφή 0;
}

Η διαφορά και η σύνδεση μεταξύ λίστας ακολουθιών και συνδεδεμένης λίστας:

Πλεονεκτήματα και μειονεκτήματα του πίνακα ακολουθιών: Εξαιρετικό: Ο χώρος είναι συνεχής, υποστηρίζει τυχαία πρόσβαση, έχει υψηλή χρήση χώρου και δεν είναι πιθανό να προκαλέσει κατακερματισμό της μνήμης και έχει υψηλή απόδοση εισαγωγής και διαγραφής ουράς.

Μειονεκτήματα: 1. Η χρονική πολυπλοκότητα της εισαγωγής και διαγραφής του μεσαίου ή μπροστινού τμήματος είναι O(N) 2. Το κόστος επέκτασης χωρητικότητας είναι σχετικά υψηλό: υποβάλετε αίτηση για έκδοση αντιγράφου

Πλεονεκτήματα και μειονεκτήματα των συνδεδεμένων λιστών (αμφίδρομες τυχαίες συνδεδεμένες λίστες)

Πλεονεκτήματα: 1. Η χρονική πολυπλοκότητα εισαγωγής και διαγραφής σε οποιαδήποτε θέση είναι O(1) 2. Δεν υπάρχει πρόβλημα επέκτασης χωρητικότητας, η εισαγωγή ανοίγει χώρο και η αποτελεσματικότητα εισαγωγής και διαγραφής σε οποιαδήποτε θέση είναι υψηλή

Μειονεκτήματα: Αποθηκεύεται σε μονάδες κόμβων, δεν υποστηρίζει τυχαία πρόσβαση και η χαμηλή χρήση χώρου μπορεί εύκολα να προκαλέσει κατακερματισμό της μνήμης.

στοίβες και ουρές

Στοίβα: Μια ειδική γραμμική λίστα που επιτρέπει μόνο την εισαγωγή και τη διαγραφή στοιχείων στο ένα άκρο στη στοίβα ακολουθεί την αρχή LIFO (last in first out).

Σπρώξιμο της στοίβας: Η λειτουργία εισαγωγής της στοίβας ονομάζεται push/push/push και τα εισαγόμενα δεδομένα βρίσκονται στην κορυφή της στοίβας

Pop: Η λειτουργία διαγραφής της στοίβας ονομάζεται popping και τα δεδομένα που εμφανίζονται βρίσκονται επίσης στην κορυφή της στοίβας.

Εφαρμογή της λειτουργίας ώθησης push--->αποθηκεύστε στοιχεία από την κορυφή της στοίβας

Πίνακας ακολουθίας: Μπορεί να θεωρηθεί ως λειτουργία εισαγωγής ουράς

Συνδεδεμένη λίστα: (αμφίδρομη κυκλική συνδεδεμένη λίστα με επικεφαλίδες) η κεφαλή της λίστας θεωρείται ως η κορυφή της στοίβας, η οποία είναι η εισαγωγή της κεφαλής, και η ουρά της λίστας θεωρείται ως η κορυφή της στοίβας, η οποία είναι η εισαγωγή ουράς.

Λειτουργία pop--->αφαίρεση στοιχείων από την κορυφή της στοίβας

Πίνακας ακολουθίας: Το τέλος του πίνακα θεωρείται ως η κορυφή της στοίβας και θεωρείται ως η λειτουργία διαγραφής ουράς.

Συνδεδεμένη λίστα: (αμφίδρομη κυκλική συνδεδεμένη λίστα) η κεφαλή της λίστας θεωρείται ως η κορυφή της στοίβας, η οποία είναι η διαγραφή κεφαλής, και η ουρά της λίστας θεωρείται ως η κορυφή της στοίβας, η οποία είναι η διαγραφή ουράς.

#περιλαμβάνω<stdio.h>
#περιλαμβάνω<stdlib.h>

typedef int STDataType;
//Ο πίνακας ακολουθιών υλοποιεί μια στοίβα
typedef struct stack{
STDataType* _data;
int _size;
int _capacity;
}σωρός;

void stackInit(stack* st){
αν (st == NULL)
ΕΠΙΣΤΡΟΦΗ;
st->_data = NULL;
st->_size = st->_capacity = 0;
}

void checkCapcacity(stack* st){
αν (st->_size == st->_capacity){
int newCapcacity = st->_capacity == 0 ? 1 : 2 * st->_capacity;
st->_data = (STDataType*)realloc(st->_data, sizeof(STDataType)* newCapcacity);
st->_capacity = newCapcacity;
}

}

//Push to stack
void stackPush(stack* st, STDataType val){
αν (st == NULL)
ΕΠΙΣΤΡΟΦΗ;
checkCapacity(st);
//Εισαγωγή ουράς
st->_data[st->_size++] = val;

}

//κρότος
void stackPop(stack* st){
αν (st == NULL)
ΕΠΙΣΤΡΟΦΗ;
if (st->_size > 0)
st->_size--;
}

STDataType stackTop(stack* st){
επιστροφή st->_data[st->_size - 1];
}

int stackSize(stack* st){
αν (st == NULL)
επιστροφή 0;
επιστροφή st->_size;
}

void test(){
στοίβα st?
stackInit(&st);
stackPush(&st, 1);
stackPush(&st, 2);
stackPush(&st, 3);
stackPush(&st, 4);
για (int i = 0; i < 4; ++i){
printg("%d", stackTop(&st));
stackPop(&st);
}
printf("n");
}

int main(){
δοκιμή();
system("pause");
επιστροφή 0;
}

Κοινή χρήση τεχνολογίας

24/07/11Δομή δεδομένων (6.1215) διπλή συνδεδεμένη λίστα υλοποίησης-υλοποίηση στοίβας

Προσωπικό προφίλ

τα στοιχεία επικοινωνίας μου