07.24.11Структура данных (6.1215) двусвязный список, реализация-стек реализации

07.24.11Структура данных (6.1215) реализация стека реализации двусвязного списка

2024-07-12

Так же, как и при написании функциональных интерфейсов для односвязных списков, давайте сначала напишем несколько интерфейсов для двусвязных списков, чтобы ознакомиться с их основной структурой:

#включать<stdio.h>
#включать<stdlib.h>

typedef int LDataType;

//Узел двустороннего циклического связанного списка
typedef struct ListNode{
LDataType _data;
//Указываем на начальную позицию следующего узла
структура ListNode* _next;
//Указываем на начальную позицию предыдущего узла
структура LIst* _prev;
}УзелСписка;

//Двусторонний кольцевой связанный список
typedef struct Список{
структура ListNode* _head;
}Список;

структура ListNode* createListNode(LDataType val){
структура ListNode* узел = (структура ListNode*)malloc(sizeof(структура ListNode));
узел->_данные = значение;
узел->_следующий = NULL;
узел->_prev = NULL;
}

void ListInit(Список* 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){
возвращаться;
структура ListNode* last = lst->_head->_prev;
структура ListNode* newNode = createListNode(val);
//_head ... последний новый узел
последний->_следующий = новыйУзел;
newNode->_prev = последний;

newNode->_next = lst->_head;
lst->_head->_prev = новыйУзел;
}
}

//Удалить хвост://Удалить предыдущий узел головы ListErase(lst, lst->_head->_prev);
void ListPopBack(Список* lst){
если (lst == NULL)
возвращаться;
//Определяем, пуст ли связанный список
если (lst->_head->_next == lst->_head)
возвращаться;
структура ListNode* last = lst->_head->_prev;
структура ListNode* prev = last->_prev;

свободный(последний);

lst->_head->_prev = предыдущая;
предыдущая->_следующая = последняя->_головная;
}

void printList(Список* lst){
структура ListNode* cur = lst->_head->_next;
в то время как (cur != lst->_head){
printf("%d", cur->_data);
текущ = текущ->_следующий;
}
printf("н");
}

//Вставка головы//ListInsert(lst,lst->_head->_next,val);
void ListPushFront(List* lst, LDataType val){
если (lst == NULL)
возвращаться;
структура ListNode* next = lst->_head->_next;
структура ListNode* newNode = createListNode(val);

//_head, новыйУзел, следующий
lst->_head->_next = новыйУзел;
newNode->_prev = lst->_head;

newNode->_next = следующий;
следующий->_предыдущий = новыйУзел;
}

//Удалить заголовок//ListErase(lst,lst->_head->_next);
void ListPopFront(Список* lst){
если (lst == NULL || lst->_head == lst->_head)
возвращаться;
структура ListNode* next = lst->_head->_next;
структура ListNode* nextnext = next->_next;

следующий->_предыдущий = следующий->_следующий;
lst->_head->_next = nextnext;

бесплатно(следующий);

}

void ListErase(List* lst, struct ListNode* node){
//Невозможно удалить головной узел
если (lst == NULL || lst->_head == узел)
возвращаться;
//предыдущий, узел, следующий
структура ListNode* prev = node->_prev;
структура ListNode* следующий = узел->_следующий;

предыдущий->_следующий = следующий;
следующий->_предыдущий = предыдущий;

свободный(узел);

}

void ListInsert(List* lst, struct ListNode* node, LDataType val){
если (lst == NULL)
возвращаться;
структура ListNode* prev = node->_prev;
структура ListNode* newNode = createListNode(val);

//предыдущий узел newNode
предыдущий->_следующий = новыйУзел;
newNode->_prev = предыдущий;

новыйУзел->_следующий = узел;
узел->_предыдущий = новыйУзел;
}

//разрушать
СписокDestoty(Список* lst){
если (lst){
если (lst->_head){
структура ListNode* cur = lst->_head->_next;
в то время как (cur != lst->_head){
структура ListNode* next = cut->_next;
бесплатно(тек);
текущий = следующий;
}

бесплатно(lst->_head);
}
}
}

недействительный тест(){
Список 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);*/
}

инт основной(){

тест();
система("пауза");
вернуть 0;
}

Разница и связь между списком последовательностей и связанным списком:

Преимущества и недостатки таблицы последовательностей: Отлично: пространство является непрерывным, поддерживает произвольный доступ, имеет высокую степень использования пространства и вряд ли приведет к фрагментации памяти, а также имеет высокую эффективность вставки и удаления хвостов.

Недостатки: 1. Временная сложность вставки и удаления средней или передней части составляет O(N) 2. Стоимость расширения емкости относительно высока: подать заявку на выпуск копии

Преимущества и недостатки связанных списков (двусторонние случайные связанные списки)

Преимущества: 1. Временная сложность вставки и удаления в любой позиции составляет O(1) 2. Нет проблемы расширения емкости, вставка открывает пространство, а эффективность вставки и удаления в любой позиции высока.

Недостатки: он хранится в узлах, не поддерживает произвольный доступ, а низкое использование пространства может легко вызвать фрагментацию памяти.

стопки и очереди

Стек: специальный линейный список, который позволяет вставлять и удалять элементы только на одном конце. Конец, где выполняются операции вставки и удаления данных, называется вершиной стека, а другой конец — нижней частью стека. в стеке следует принципу LIFO (последним пришел — первым ушел)

Перемещение стека: операция вставки в стек называется push/push/push, и вставленные данные находятся на вершине стека.

Удаление: операция удаления стека называется извлечением, и данные извлечения также находятся на вершине стека.

Реализация операции push --->сохранение элементов с вершины стека

Таблица последовательности: ее можно рассматривать как операцию вставки хвоста.

Связанный список: (круговой связанный список с двусторонним заголовком). Глава списка считается вершиной стека, которая является вставкой головы, а хвост списка считается вершиной стека, который является вставка хвоста

Операция Pop pop ---> удалить элементы с вершины стека

Таблица последовательности: конец таблицы считается вершиной стека и считается операцией удаления хвоста.

Связанный список: (круглый связанный список с двусторонним заголовком). Глава списка считается вершиной стека, что является удалением головы, а хвост списка считается вершиной стека, который является вершиной стека. удаление хвоста.

#включать<stdio.h>
#включать<stdlib.h>

typedef int STDataType;
//Таблица последовательности реализует стек
typedef структура стека{
STDataType* _data;
int _size;
int _capacity;
}куча;

void stackInit(стек* ст){
если (ст == NULL)
возвращаться;
st->_data = NULL;
st->_size = st->_capacity = 0;
}

void checkCapcacity(стек* 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;
}

}

//Помещаем в стек
void stackPush(стек* st, STDataType val){
если (ст == NULL)
возвращаться;
checkCapacity(ст);
//Вставка хвоста
st->_data[st->_size++] = значение;

}

//поп
void stackPop(стек* ст){
если (ст == NULL)
возвращаться;
если (ст->_размер > 0)
ст->_размер--;
}

STDataType stackTop(стек* st){
вернуть st->_data[st->_size - 1];
}

int stackSize(стек* ст){
если (ст == NULL)
вернуть 0;
вернуть st->_size;
}

недействительный тест(){
стек ул;
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("н");
}

инт основной(){
тест();
система("пауза");
вернуть 0;
}

Обмен технологиями

07.24.11Структура данных (6.1215) реализация стека реализации двусвязного списка

Личный профиль

моя контактная информация