предисловие
В начале этой статьи начнется новая серия Структуры данных, важность структур данных в алгоритмах или программировании очевидна, поэтому необходимо хорошо изучить структуры данных. В этой статье в основном представлена первая структура структуры данных — линейная таблица, которая в основном разделена на следующие части:
1. Концепция
2. Структура хранения
- последовательное хранение
- цепь хранения
3. Сравнение преимуществ и недостатков структуры хранения
4. Операции с таблицами
- Операции с односвязным списком
- Операции с двусвязным списком
Примечание. В этой серии языков будет использоваться язык C, поэтому, чтобы понять эту серию, вам необходимо понять некоторые основы языка C.
концепция
Линейная таблица — это ноль или более с одинаковыми характеристикамиэлемент данныхКоличество элементов, содержащихся в последовательности, называется длиной линейной таблицы.Линейная таблица имеет следующие характеристики:
- сначала последовательность
- Второй ограничен
- Он может быть упорядоченным или неупорядоченным. Вы можете думать о линейной таблице как о группе студентов. Вы можете расположить этих студентов в соответствии с их ростом от маленького к большому или их можно расположить в случайном столбце.
- Начальный элемент линейного списка не имеет элементов-предшественников, а имеет только элементы-последователи. Конечный элемент линейного списка не имеет элементов-последователей, а только элементы-предшественники. За исключением начального и конечного элементов, у каждого элемента есть один и только один предшествующий элемент. элемент и один последующий элемент.
структура хранения
Структура хранения линейной таблицы имеет два типа: последовательная структура хранения и связанная структура хранения, Первая называется последовательным списком, а вторая — связанным списком.
последовательная структура хранения
Таблица последовательности предназначена для хранения всех элементов линейной таблицы в определенном логическом порядке в непрерывном пространстве памяти, начиная с указанной позиции.смежное пространство для хранения.
Разница между длиной массива и длиной линейной таблицы: длина массива равна длине места хранения для хранения линейной таблицы.После выделения памяти эта сумма в общем случае неизменна.Длина линейной таблицы - количество элементов данных в линейной таблице, выполняются операции вставки и удаления, и это количество изменяется.
Определение структуры таблицы последовательности:
typedef struct
{
int data[maxsize]; //建立存放int类型数据的一个数组
int lengeth; //存放顺序表的长度
}
Существует также более лаконичный способ написания:
int A[maxsize];
int n;
Преимущества и недостатки последовательной структуры хранения линейной таблицы
| преимущество | недостаток |
|---|---|
| Нет необходимости добавлять дополнительное пространство для хранения для представления логической связи между элементами в таблице. | Операции вставки и удаления требуют перемещения большого количества элементов |
| Может быстро получить доступ к элементам в любом месте таблицы | Операции вставки и удаления требуют перемещения большого количества элементов |
| Когда линейная длина стола сильно различается, трудно определить емкость места для хранения. | |
| Фрагментация места для хранения |
цепная структура хранения
Цепная структура хранения предназначена для устранения недостатков последовательной структуры хранения.Самый большой недостаток последовательной структуры хранения заключается в том, что при вставке и удалении элемента необходимо перемещать большое количество элементов, что требует очень много времени. Зачем это перемещать и удалять определенный элемент нужно перемещать большое количество элементов, ведь позиции хранения двух соседних элементов тоже смежные, и их позиции в памяти тоже рядом друг с другом, в середине нет пустоты , не может Чтобы вставить напрямую, если вы хотите вставить, вам нужно сначала переместить другие элементы.Точно так же, если вы удалите элемент, зазор вытечет, и вам нужно переместить другие элементы, чтобы восполнить. Подводя итог, можно сказать, что основная проблема последовательного хранения заключается в том, что места хранения двух соседних элементов являются смежными, и их местоположения в памяти также находятся рядом друг с другом.
Теперь мы знаем причину проблемы с последовательным хранением, дальше нужно только решить ее целенаправленно, чтобы позиции между элементами не обязательно были соседними, а позиции в памяти не обязательно были рядом друг друга. Мы используем эту структуру хранения. Называемая цепной структурой хранения, цепная структура хранения линейной таблицы характеризуется использованием группы произвольных единиц хранения для хранения элементов данных линейной таблицы. Эта группа единиц хранения может быть непрерывный или прерывистый, что означает, что эти элементы данных могут существовать где угодно в памяти, которая не занята. Другой момент заключается в том, что в последовательной структуре хранения каждое пространство данных должно хранить только информацию об элементе данных, но в цепной структуре, помимо хранения информации об элементе данных, также необходимо хранить место хранения его последующие элементы. Мы называем домен, в котором хранится информация об элементе данных, доменом данных, домен, в котором хранится непосредственная последующая позиция, называется доменом указателя, информация, хранящаяся в домене указателя, называется указателем или цепочкой, а домен данных и домен указателя образуют хранилище. образ элемента данных, вызываемый для узла.
1. Односвязный список
N узлов связаны, чтобы сформировать связанный список, который представляет собой связанную структуру хранения линейного списка. Поскольку каждый узел этого связанного списка содержит только одно поле указателя, он называется односвязным списком. Односвязный список является указателем через каждый узел Домены связывают элементы данных линейной таблицы вместе в их логическом порядке.
Некоторые связанные списки имеют головной узел, а некоторые не содержат головного узла Поле данных головного узла не может хранить информацию, но может хранить дополнительную информацию, например длину линейной таблицы Поле указателя головного узла хранит точки на первом узле Point pointer. Когда в связанном списке есть головной узел, это эквивалентно существованию локомотива, который используется только для указания направления последовательности поездов и не возит гостей. (Связанные списки обычно содержат головные узлы)
В односвязном списке с головным узлом головной указатель head указывает на головной узел, поле данных головного узла не содержит никакой информации, и информация данных сохраняется от узла-преемника головного узла. Указатель head всегда не равен NULL (указатель ссылается на информацию, указывающую на следующий элемент, когда он равен NULL, он не указывает ни на какой элемент), когда head->next равен NULL, связанный список пустой.
Головной указатель head в односвязном списке без головного узла указывает непосредственно на начальный узел.Когда head равен NULL (head->=NULL), связанный список пуст.
Доступ ко всему связанному списку в связанном списке должен начинаться с указателя головы, каждый последующий узел — это позиция, на которую указывает указатель-преемник предыдущего узла, а указатель последнего узла (конечный узел) обычно пуст. NULL или ^ указывает.
определение узла односвязного списка
typedef struct LNode
{
int data; //data中存放结点数据域
struct LNode *next; //指向后继结点的指针
}LNode; //定义单链表结点类型
2. Статический связанный список
Предыдущий односвязный список использует указатели, но некоторые языки программирования не имеют функции указателей, и что? У умных людей всегда так.Некоторым людям пришла в голову идея использовать массивы вместо указателей для описания односвязных списков, чтобы элементы каждого массива состояли из двух полей данных, а каждый индекс массива соответствовал двум поля данных, одно Используется для хранения элементов данных, одно используется для хранения следующего указателя. Мы называем этот связанный список, описываемый массивом, статическим связанным списком.
3. Круговой связанный список
Конец указателя конечного узла в односвязном списке меняется с нулевого указателя на головной узел, так что весь односвязный список образует кольцо.
4. Двусвязный список
На основе односвязного списка в каждом узле устанавливается поле указателя, указывающее на его предшествующий узел, так что узел может указывать на свой предыдущий и следующий.Мы называем этот связанный список двусвязным списком.
Определение узла двусвязного списка
typedef struct DLLNode
{
int data; //data中存放结点数据域（默认是int类型，也可以是其他）
struct DLNode *prior; //指向前驱结点的指针
struct DLNode *next; //指向后继结点的指针
}DLNode; //定义双链表结点类型
Узел — это участок памяти в памяти, выделенный пользователем, существует только один адрес, указывающий на его существование, и нет явного имени, поэтому при выделении пространства узла связанного списка мы определим указатель на в то же время, чтобы сохранить этот кусок.Адрес пространства (этот процесс обычно называют указателем на узел), и имя указателя часто используется в качестве имени узла, например следующее:
LNode *A = (LNode*)malloc(sizeof(LNode)); //用户分配（sizeof）了一片LNode空间，这时定义指针A来指向这个结点，同时我们也把A当作这个结点的名字。
Сравнение последовательного и цепного хранения
Поскольку адреса хранения таблицы последовательности непрерывны, вам нужно знать только позицию первого элемента, и вы можете получить любой элемент в таблице последовательности через смещение начальной позиции.Мы называем эту функцию какфункция произвольного доступа.
Элементы данных в таблице последовательности хранятся в пространстве с непрерывным адресом, и выделение этого пространства хранения (т. е. места хранения) должно быть выполнено заранее. Это.
Последовательные списки должны перемещать множество элементов при вставке и удалении элемента.
Потому что структура хранения связанного списка такова, что один элемент содержит информацию о положении следующего элемента данных, а следующий содержит следующий, то есть каждый элемент данных соединен одной линией.Если вы хотите знать, где последний элемент, вы должны идти от начала до конца, поэтому связанный список не поддерживает произвольный доступ.
Каждый узел в связанном списке должен разделить часть пространства для хранения указателя на следующий узел, поэтому использование пространства для хранения узлов в связанном списке ниже, чем у последовательного списка.
Связанные списки поддерживают динамическое выделение дискового пространства.
При вставке и удалении элемента в связанном списке не нужно перемещать большое количество элементов, а нужно только изменить указатель места вставки.
табличные операции
Табличные операции в основном делятся на несколько типов: поиск, вставка, удаление
Операции с таблицей последовательности:
1. Найти алгоритм по значению элемента,
int findElem (Sqlist L,int e)
{
int i;
for (i=0,i<L.length,++i) //遍历L长度中的每个位置
if(e == L.data[i]) //获取每个位置对应的值和e值进行判断，这里的等于可以是大于、小于
return i; //如果找到与e值相等的值，则返回该值对应的位置
return -1; //如果找不到，则返回-1
}
2. Алгоритм вставки элемента данных
Вставьте новый элемент e в p-ю (0
int insertElem(Sqlist &L,int p,int e) //L是顺序表的长度，要发生变化，所以用引用型
{
int i
if (p<0 || p>L.length || L.length==maxsize) //如果插入e的位置p小于0，或者是大于L的长度，或者是L的长度已经等于了顺序表最大存储空间
return 0;
for (i=L.length-1;i>=p;--i) //从L中的最后一个元素开始遍历L中位置大于p的每个位置
L.data[i+1]=L.data[i]; //依次将第i个位置的值赋值给i+1
L.data[p]=e; //将p位置插入e
++(L.length); //L的长度加1
return 1; //插入成功，返回1
}
3. Алгоритм удаления элемента данных
Удалить элемент e в p-й позиции таблицы последовательности.Если ввод p неверен, он вернет 0, что означает, что удаление не удалось, если ввод p правильный, элементы после позиции p в таблице последовательностей таблица последовательности будет передана вперед по порядку, просто перезапишите элемент в позиции p.
int deleteElem (Sqlist &L,int p,int &e) //需要改变的变量用引用型
{
int i;
if(p<0 || p>L.length-1) //对位置p进行判断，如果位置不对，则返回0，表示删除失败
return 0;
e=L.data[p]; //将要删除的值赋值给e
for(i=p;i<L.length-1;++i) //从位置p开始，将其后边的元素逐个向前覆盖
L.data[i]=L.data[i+1];
--(L.length) //将表的长度减1
return 1; //删除成功，返回1
}
Операции с односвязным списком
1. Операция слияния односвязного списка
A и B – два односвязных списка, в которых элементы расположены в порядке возрастания. Разработайте алгоритм для объединения A и B в связанный список C, упорядоченный по значению элемента не по убыванию, а C состоит из A и B.
Анализ: известно, что элементы в A и B расположены в порядке возрастания. Чтобы после слияния элементы в C оставались в порядке, можно выбрать наименьший элемент из A и B и вставить в конец C, так что, когда все элементы в A и B расположены по порядку. Когда элементы вставляются в C, C должен быть в возрастающем порядке.
void merge(LNode *A,LNode *B,LNode *&C)
{
LNode *p = A->next; //用指针p来追踪链表A的后继指针
LNode *p = B->next; //用指针p来追踪链表B的后继指针
Lnode *r; //r始终指向C的终端结点
C = A; //用A的头结点来做C的头结点
C-> = NULL; //
free(B);
r = C;
while(p!=NULL&&q!=NULL) //当p和q都不为空时，选取p与q中所指结点中较小的值插入C的尾部
{
if(p->data<=q->data) //如果p结点的值小于等于q结点的值，则将p的结点指向r,即C，p的下一个结点继续指向p
{
r->next = p;p = p->next;
r=r->next;
}
else
{
r->next=q;q=q-next;
r=r->next;
}
}
r->next = NULL;
if(p!=NULL)r->next=p;
if(q!=NULL)r->next=q;
}
2. Метод вставки хвоста односвязного списка
Известно, что в массиве a хранится n элементов, используйте метод вставки хвоста (то есть вставка из хвоста), чтобы создать связанный список C
void createlistR(LNode *&C,int a[],int n) //需要不断变化的值用引用型
{
LNode *s,*r; //s用来指向新申请的结点，r始终指向C的终端结点
int i;
C = (LNode * )malloc(sizeof(LNode)); //申请一个头结点空间
C -> next = NULL //初始化一个空链表
r = C; //r为指针，指向头结点C，此时的头结点也是终端结点
for(i=0;i<n;++i):
{
s = (LNode*)malloc(sizeof(LNode)); //新申请一个结点，指针s指向这个结点
s -> data = a[i] //将数组元素a[i]赋值给指针s指向结点的值域
//此时，结点值域和指针都有了，一个完整的结点就建好了，要想把这个结点插进链表C中
//只需要将头结点指针指向这个结点就行
r -> next = s; //头结点指针指向结点s
r = r -> next; //更新r指针目前的指向
}
r -> next = NULL; //直到终端结点为NULL，表示插入成功
}
3. Метод вставки заголовка односвязного списка
Метод вставки в начале и метод вставки в хвост являются соответствующими методами.Метод вставки в начало заключается в вставке из начала связанного списка без изменения конечного узла, метод вставки в конец заключается в вставке из конца связанного списка и оставить головной узел без изменений.
void createlistF(LNode *&C,int a[],int n) //需要不断变化的值用引用型
{
LNode *s;
int i;
C = (LNode * )malloc(sizeof(LNode)); //申请C的结点空间
C -> next = NULL //该节点指向为空
for(i=0;i<n;++i):
{
s = (LNode*)malloc(sizeof(LNode)); //新申请一个结点，指针s指向这个结点
s -> data = a[i] //将数组元素a[i]赋值给指针s指向结点的值域
//此时，结点值域和指针都有了，一个完整的结点就建好了，要想把这个结点插进链表C中
//只需要让这个结点的指针指向链表C的开始结点即可
s -> next = C -> next; //结点s指向C指针的开始结点
C -> next = s; //更新r指针目前的指向
}
}
Операции с двусвязным списком
1. Используйте метод вставки хвоста для создания двойного связанного списка.
void createFlistR(DLNode *&L,int a[],int n)
{
DLNode *s,*r;
int i;
L = (DLNode*)malloc(sizeof(DLNode)); //新建一个结点L
L -> prior = NULL;
L -> next = NULL;
r = L; //r指针指向结点L的终端结点，开始头结点也是尾结点
for(i=0;i<n;++i)
{ s = (DLNode*)malloc(sizeof(DLNode)); //创建一个新节点s
s -> data = a[i] //结点s的值域为a[i]
r -> next = s; //r指针的后继指针指向s结点
s ->prior = r; //s的前结点指向r
r = s; //更新指针r的指向
}
r -> next = NULL; //直到r指针指向为NULL
}
2. Алгоритм поиска узлов
Найти узел со значением x в двусвязном списке, если он найден, вернуть указатель узла, иначе вернуть значение NULL.
DLNode* findNode(DLNode *C,int x)
{
DLNode *p = C -> next;
while(p != NULL)
{
if(p -> data == x)
break;
p = p -> next;
}
return p;
}
3. Алгоритм вставки узлов
Вставьте узел s после узла, на который указывает p в двусвязном списке Основная идея состоит в том, чтобы присвоить точку p s, то есть пусть s указывает на точку p, передним узлом s является p, и задний узел p - это s, конкретный код выглядит следующим образом:
s -> next = p -> next;
s -> prior = p;
p -> next = s;
s -> next -> prior = s;
4. Алгоритм удаления узлов
Чтобы удалить узел-преемник узла p в двусвязном списке, основная идея состоит в том, чтобы сначала передать узел-преемник p в q, а затем позволить p указывать на узел-преемник q и узел-предшественник следующего узла. node q - это p, а затем Release q, конкретный код выглядит следующим образом:
q = p -> next;
p -> = q -> next;
q -> next -> prior = p;
free(q);