По сути, массив - это набор похожих объектов данных, хранящихся в последовательных ячейках памяти под общим заголовком или именем переменной.
В то время как связанный список представляет собой структуру данных, которая содержит последовательность элементов, где каждый элемент связан со своим следующим элементом. В элементе связанного списка есть два поля. Одним из них является поле данных, а другим - поле ссылки, поле данных содержит фактическое значение, которое будет сохранено и обработано. Кроме того, поле ссылки содержит адрес следующего элемента данных в связанном списке. Адрес, используемый для доступа к конкретному узлу, называется указателем.
Другое существенное различие между массивом и связанным списком состоит в том, что массив имеет фиксированный размер и должен быть объявлен ранее, но связанный список не ограничен размером, расширением и сокращением во время выполнения.
Сравнительная таблица
| Основа для сравнения | массив | Связанный список |
|---|---|---|
| основной | Это последовательный набор фиксированного количества элементов данных. | Это упорядоченный набор, содержащий переменное количество элементов данных. |
| Размер | Указано во время декларации. | Не нужно указывать; расти и сжиматься во время исполнения. |
| Распределение памяти | Расположение элемента выделяется во время компиляции. | Положение элемента назначается во время выполнения. |
| Порядок элементов | Хранится последовательно | Хранится в случайном порядке |
| Доступ к элементу | Прямой или случайный доступ, т. Е. Указание индекса массива или индекса. | Последовательный доступ, т. Е. Traverse, начиная с первого узла в списке по указателю. |
| Вставка и удаление элемента | Медленно, поскольку требуется смещение. | Легче, быстрее и эффективнее. |
| поиск | Бинарный поиск и линейный поиск | линейный поиск |
| Требуется память | Меньше | Больше |
| Использование памяти | неэффективный | эффективное |
Определение массива
Массив определяется как набор определенного количества однородных элементов или элементов данных. Это означает, что массив может содержать только один тип данных: все целые числа, все числа с плавающей запятой или все символы. Объявление массива выглядит следующим образом:
int a [10];
Где int указывает тип данных или элементы массива элементов типа. «A» - это имя массива, а число, указанное в квадратных скобках, - это количество элементов, которое может хранить массив, это также называется размером или длиной массива.
Давайте посмотрим на некоторые концепции, которые нужно помнить о массивах:
- Доступ к отдельным элементам массива можно получить, описав имя массива, за которым следует индекс или индекс (определяющий расположение элемента в массиве) в квадратных скобках. Например, чтобы извлечь 5-й элемент массива, нам нужно написать оператор a [4].
- В любом случае элементы массива будут храниться в последовательной ячейке памяти.
- Самый первый элемент массива имеет индекс ноль [0]. Это означает, что первый и последний элемент будут определены как a [0] и a [9] соответственно.
- Количество элементов, которые могут быть сохранены в массиве, т. Е. Размер массива или его длина определяется следующим уравнением:
(верхняя граница - нижняя граница) + 1
Для приведенного выше массива это будет (9-0) + 1 = 10. Где 0 - нижняя граница массива, а 9 - верхняя граница массива. - Массивы могут быть прочитаны или записаны через цикл. Если мы читаем одномерный массив, он требует один цикл для чтения и другой для записи (печати) массива, например:
а. Для чтения массива
для (i = 0; i <= 9; i ++)
{scanf («% d», & a [i]); }
б. Для написания массива
для (i = 0; i <= 9; i ++)
{printf («% d», a [i]); } - В случае двумерного массива потребовалось бы два цикла, и аналогично n-мерному массиву потребовалось бы n циклов.
Операции над массивами:
- Создание массива
- Обход массива
- Вставка новых элементов
- Удаление обязательных элементов.
- Модификация элемента.
- Слияние массивов
пример
Следующая программа иллюстрирует чтение и запись массива.
#include #include void main () { int a[10], i; printf("Enter the array"); for ( i= 0; i <= 9; i++) { scanf ( "%d", &a[ i ] ) ; } printf( "Enter the array" ); for (i = 0 ; i <= 9 ; i++) { printf ( "%d\n", a[ i ] ) ; } getch (); }
Определение связанного списка
Связанный список - это определенный список некоторых элементов данных, связанных друг с другом. В этом каждый элемент указывает на следующий элемент, который представляет логический порядок. Каждый элемент называется узлом, который состоит из двух частей.
Часть INFO, в которой хранится информация, и указатель, указывающий на следующий элемент. Как известно, для хранения адресов у нас есть уникальные структуры данных в Си, называемые указателями. Следовательно, второе поле списка должно быть указателем типа.
Типы связанных списков: Односвязный список, Двусвязный список, Круговой связанный список, Круговой двойной связанный список.
Операции, выполняемые в связанном списке:
- Создание
- Пересекая
- вставка
- делеция
- поиск
- конкатенация
- дисплей
пример
Следующий фрагмент иллюстрирует создание связанного списка:
struct node { int num; stuct node *next; } start = NULL; void create() { typedef struct node NODE; NODE *p, *q; char choice; first = NULL; do { p = (NODE *) malloc (sizeof (NODE)); printf ("Enter the data item\n"); scanf ("%d", & p -> num); if (p == NULL) { q = start; while (q -> next ! = NULL) { q = q -> next } p -> next = q -> next; q -> = p; } else { p -> next = start; start = p; } printf ("Do you want to continue (type y or n) ? \n"); scanf ("%c", &choice) ; } while ((choice == 'y') || (choice == 'Y')); }
Ключевые различия между массивом и связанным списком
- Массив - это структура данных, содержащая набор элементов данных аналогичного типа, тогда как Связанный список рассматривается как не примитивная структура данных, содержит набор неупорядоченных связанных элементов, известных как узлы.
- В массиве элементы принадлежат индексам, т. Е. Если вы хотите попасть в четвертый элемент, вы должны написать имя переменной с указанием ее индекса или местоположения в квадратных скобках.
В связанном списке, тем не менее, вы должны начать с головы и проходить до тех пор, пока не доберетесь до четвертого элемента. - В то время как доступ к массиву элементов быстрый, в то время как связанный список занимает линейное время, он немного медленнее.
- Такие операции, как вставка и удаление в массивах, занимают много времени. С другой стороны, выполнение этих операций в связанных списках происходит быстро.
- Массивы имеют фиксированный размер. В отличие от этого, связанные списки являются динамичными и гибкими и могут расширяться и сокращаться.
- В массиве память выделяется во время компиляции, в то время как в связанном списке она выделяется во время выполнения или выполнения.
- Элементы хранятся последовательно в массивах, в то время как они хранятся в случайном порядке в связанных списках.
- Потребность в памяти меньше из-за фактических данных, хранящихся в индексе в массиве. В отличие от этого, требуется больше памяти в связанных списках из-за хранения дополнительных элементов следующего и предыдущего ссылок.
- Кроме того, использование памяти в массиве неэффективно. И наоборот, использование памяти эффективно в массиве.
Заключение
Массив и связанные списки - это типы структур данных, различающиеся по своей структуре, методам доступа и манипулирования, требованиям к памяти и использованию. И имеют определенные преимущества и недостатки по сравнению с его реализацией. Следовательно, любой из них может быть использован по необходимости.
