2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Tout comme pour écrire des interfaces fonctionnelles pour les listes à chaînage unique, écrivons d'abord quelques interfaces pour les listes à double chaînage afin de nous familiariser avec son cadre principal :
#inclure<stdio.h>
#inclure<stdlib.h>
typedef int LDataType;
//Le nœud de la liste chaînée circulaire bidirectionnelle
typedef struct ListNode{
LDataType _données;
//Pointez vers la position de départ du nœud suivant
structure ListNode* _next;
//Pointez vers la position de départ du nœud précédent
structure LIst* _prev;
}ListNode;
//Liste chaînée circulaire bidirectionnelle
typedef struct Liste{
structure ListNode* _head;
}Liste;
struct ListNode* createListNode(LDataType val){
struct ListNode* nœud = (struct ListNode*)malloc(sizeof(struct ListNode));
nœud->_data = val;
nœud->_next = NULL;
nœud->_prev = NULL;
}
void ListInit(Liste* lst){
//Liste chaînée vide
lst->_head = createListNode(0);
lst->_head->_next = lst->_head->_prev = lst->_head;
}
//Insertion de queue O(1) //Insérer une donnée devant la tête ListInsert(lst, lst->_head, val);
void ListpushBack(Liste* lst, LDataType val){
si (lst == NULL){
retour;
struct ListNode* dernier = lst->_head->_prev;
struct ListNode* nouveauNode = createListNode(val);
//_head ... dernier nouveau noeud
dernier->_suivant = nouveauNoeud;
newNode->_prev = dernier;
nouveauNoeud->_suivant = lst->_tête;
lst->_head->_prev = nouveauNoeud;
}
}
//Tail delete://Supprimer le nœud précédent de la tête ListErase(lst, lst->_head->_prev);
void ListPopBack(Liste* lst){
si (lst == NULL)
retour;
//Détermine si la liste chaînée est vide
si (lst->_head->_next == lst->_head)
retour;
struct ListNode* dernier = lst->_head->_prev;
struct ListNode* prev = dernier->_prev;
libre(dernier);
lst->_head->_prev = précédent;
précédent->_suivant = lst->_tête;
}
void printList(Liste* lst){
struct ListNode* cur = lst->_head->_next;
tandis que (cur != lst->_head){
printf("%d", cur->_data);
cur = cur->_next;
}
printf("n");
}
//Insertion de tête//ListInsert(lst,lst->_head->_next,val);
void ListPushFront(Liste* lst, LDataType val){
si (lst == NULL)
retour;
struct ListNode* suivant = lst->_head->_next;
struct ListNode* nouveauNode = createListNode(val);
//_head, nouveauNode, suivant
lst->_head->_next = nouveauNoeud;
nouveauNoeud->_prev = lst->_head;
newNode->_next = suivant;
suivant->_précédent = nouveauNoeud;
}
//Suppression d'en-tête//ListErase(lst,lst->_head->_next);
void ListPopFront(Liste* lst){
si (lst == NULL || lst->_head == lst->_head)
retour;
struct ListNode* suivant = lst->_head->_next;
struct ListNode* nextnext = suivant->_next;
suivantsuivant->_prev = suivant->_suivant;
lst->_head->_next = suivantsuivant;
libre(suivant);
}
void ListErase(Liste* lst, struct ListNode* nœud){
//Impossible de supprimer le nœud principal
si (lst == NULL || lst->_head == nœud)
retour;
//précédent, nœud, suivant
struct ListNode* prev = noeud->_prev;
struct ListNode* suivant = nœud->_next;
prev->_next = suivant;
suivant->_précédent = précédent;
libre(nœud);
}
void ListInsert(Liste* lst, struct ListNode* nœud, LDataType val){
si (lst == NULL)
retour;
struct ListNode* prev = noeud->_prev;
struct ListNode* nouveauNode = createListNode(val);
//précédent nouveau nœud
précédent->_suivant = nouveauNoeud;
newNode->_prev = précédent;
newNode->_next = nœud;
nœud->_prev = nouveauNoeud;
}
//détruire
ListDestoty(Liste* lst){
si (lst){
si (lst->_head){
struct ListNode* cur = lst->_head->_next;
tandis que (cur != lst->_head){
struct ListNode* suivant = couper->_suivant;
libre(actuel);
cur = suivant;
}
libre(lst->_head);
}
}
}
test vide(){
Liste lst;
ListeInit(&lst);
ListePushFront(&lst, 5);
printList(&lst);
ListePushFront(&lst, 1);
printList(&lst);
ListePushFront(&lst, 2);
printList(&lst);
ListePushFront(&lst, 3);
printList(&lst);
ListePushFront(&lst, 4);
printList(&lst);
ListePopFront(&lst);
printList(&lst);
ListePopFront(&lst);
printList(&lst);
ListePopFront(&lst);
printList(&lst);
/*ListPopBack(&lst);
printList(&lst);
ListePopBack(&lst);
printList(&lst);
ListePopBack(&lst);
printList(&lst);
ListePopBack(&lst);
printList(&lst);*/
}
int main(){
test();
système("pause");
retourner 0;
}
La différence et la connexion entre la liste de séquences et la liste chaînée :
Avantages et inconvénients de la table de séquence : Excellent : l'espace est continu, prend en charge l'accès aléatoire, a une utilisation élevée de l'espace et n'est pas susceptible de provoquer une fragmentation de la mémoire, et a une efficacité élevée d'insertion et de suppression de queue.
Inconvénients : 1. La complexité temporelle de l'insertion et de la suppression de la partie centrale ou avant est O(N) 2. Le coût de l'extension de capacité est relativement élevé : demandez la libération de la copie
Avantages et inconvénients des listes chaînées (listes chaînées aléatoires bidirectionnelles)
Avantages : 1. La complexité temporelle de l'insertion et de la suppression à n'importe quelle position est O(1) 2. Il n'y a aucun problème d'extension de capacité, l'insertion d'un espace ouvre un espace et l'efficacité de l'insertion et de la suppression à n'importe quelle position est élevée
Inconvénients : il est stocké en unités de nœuds, ne prend pas en charge l'accès aléatoire et une faible utilisation de l'espace peut facilement provoquer une fragmentation de la mémoire.
piles et files d'attente
Pile : une liste linéaire spéciale qui permet uniquement l'insertion et la suppression d'éléments à une extrémité. L'extrémité où les opérations d'insertion et de suppression de données sont effectuées est appelée le haut de la pile, et l'autre extrémité est appelée le bas de la pile. dans la pile suit le principe LIFO (dernier entré, premier sorti)
Pousser la pile : l'opération d'insertion de la pile est appelée push/push/push, et les données insérées se trouvent en haut de la pile
Pop : L'opération de suppression de la pile est appelée popping, et les données popping se trouvent également en haut de la pile.
Implémentation de l'opération push push--->stocker les éléments depuis le haut de la pile
Tableau de séquence : il peut être considéré comme une opération d'insertion de queue
Liste chaînée : (liste chaînée circulaire bidirectionnelle) la tête de la liste est considérée comme le haut de la pile, qui est l'insertion de la tête, et la queue de la liste est considérée comme le haut de la pile, qui est l'insertion de la tête. insertion de queue
Opération pop pop ---> supprimer des éléments du haut de la pile
Table de séquence : la fin de la table est considérée comme le sommet de la pile et elle est considérée comme l'opération de suppression de queue.
Liste chaînée : (liste chaînée circulaire bidirectionnelle) la tête de la liste est considérée comme le haut de la pile, ce qui correspond à la suppression de la tête, et la queue de la liste est considérée comme le haut de la pile, ce qui est le suppression de la queue.
#inclure<stdio.h>
#inclure<stdlib.h>
typedef int STDataType;
//La table de séquence implémente une pile
typedef struct pile{
STDataType* _données;
int _taille;
int _capacité;
}empiler;
void stackInit(pile* st){
si (st == NULL)
retour;
st->_data = NULL;
st->_size = st->_capacity = 0;
}
void checkCapcacity(pile* st){
si (st->_size == st->_capacity){
int nouvelleCapacité = st->_capacity == 0 ? 1 : 2 * st->_capacity;
st->_data = (STDataType*)realloc(st->_data, sizeof(STDataType)* nouvelleCapacité);
st->_capacity = nouvelleCapacité;
}
}
//Pousser pour empiler
void stackPush(pile* st, STDataType val){
si (st == NULL)
retour;
vérifierCapacité(st);
//Insertion de la queue
st->_data[st->_size++] = val;
}
//populaire
void stackPop(pile* st){
si (st == NULL)
retour;
si (st->_size > 0)
st->_size--;
}
STDataType stackTop(pile* st){
renvoyer st->_data[st->_size - 1];
}
int stackSize(pile* st){
si (st == NULL)
retourner 0;
retourner st->_size;
}
test vide(){
pile st;
stackInit(&st);
stackPush(&st, 1);
stackPush(&st, 2);
stackPush(&st, 3);
stackPush(&st, 4);
pour (int i = 0; i < 4; ++i){
printg("%d", stackTop(&st));
stackPop(&st);
}
printf("n");
}
int main(){
test();
système("pause");
retourner 0;
}
Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.
