Data structure–sequential implementation of linear tables and chain implementation (c language)

# The definition and characteristics of linear tables:

* Linear List: A finite sequence composed of n elements with the same data characteristics. Such a sequence is called a “linear list”;

* Characteristics of linear tables: The only element that exists is called the “first element”, the only element that exists is called the “last element”, except for the first element, other elements have a “direct predecessor”, except for the “last element” An element” every other element has a direct successor;

* Abstract data type of linear table: (ADT is just a definition of a model and has no implementation, so the parameters here do not need to consider the specific type; there can be different interfaces for different implementations)
ADT List{
Data object: D = {a1,a2,a3…,an} All elements belong to the same data type and are ordered in a limited manner
Data relationship: R = {, , } is a predecessor-successor relationship
Data operations:
InitList( & amp;L): Initialize an empty linear list
DestroyList( & amp;L): Destroy the linear list
ClearList( & amp;L): Clear the linear list
ListLength(L): Returns the number of elements in the linear list
ListEmpty(L): Determine whether the linear list is empty
GetElem(L,i, & amp;e): Get the element at subscript i in the L table
LocateElem(L,e): Locate element e in the linear list and return its subscript. Failure to return -1
PriorElem(L,e, & amp;e): Gets the element before e in L, returns -1 on failure
NextElem(L,e, & amp;e): Get the element after e in L, return -1 on failure
ListInsert(&L,i,e): Insert element e at position i of L
ListDelete(&L,i): Delete the element of L at position i
TraverseList(L): Traverse the linear list L
} ADT List;
Abstract data types correspond to abstract classes in Java. The relationship between data objects and elements can be stored and implemented through member variables, and data operations can be expressed through abstract methods;

* Sequential table: Use sequential storage to implement a linear table, and elements that are logically adjacent are also physically adjacent;
* Linked list: Use linked storage to implement a linear list. Logically adjacent elements may not necessarily be physically adjacent;

————————————————– ————————————————– ——
# Implementation of sequence list (see SqList.c below for code):
* A sequence table uses a set of physically “continuous address” storage units to sequentially store the elements in a linear table, represented by the continuity of the physical addresses of the elements within the computer.
The relationship between data elements; it is a “random access” data structure;
* Since array types in high-level languages also have random storage characteristics, arrays are generally used to implement sequence tables, because the array type is a physically continuous storage space;
However, since the length of the linear table is variable, but the length of the array is immutable, a dynamically allocated one-dimensional array is usually used to implement the sequential table in C:
#define MAXSIZE 100 //Can be adjusted as needed, the size of the array initialization
#define ElemType int //Can be adjusted to the desired sequence table type as needed
typedef struct{

//In the sequence table initialization function, the pointer will point to the base address of the sequence table, with a size of MAXSIZE
ElemType *elem;

int length; //record the length of the sequence table
}SqList; //You can get the elements in the sequence table through: SqList.elem[i]

* Features of sequence table:
Advantages: Supports “random access”, high storage density
Disadvantages: It is inconvenient to add and delete elements randomly, and it is inconvenient to expand the capacity.
Application scenario: suitable for storage, when there are few insertion/deletion operations of elements and many query operations;
Complexity: The time complexity of bitwise search and modification is O(1), and the time complexity of value-based search and modification is O(n); the complexity of random addition and deletion is O(n), but the efficiency is low;

————————————————– ————————————————– ——

# Implementation of linked list (see SLinkedList.c below for code):
* A linked list uses a set of arbitrary storage units to store elements in a linear list. This set of storage units can be continuous or discontinuous; in order to express the relationship between each element and its subsequent elements,
Each node node on the linked list has at least two fields, “data field” and “pointer field”; the linked list itself is also a recursive data structure;

* Single linked list: Each node of a singly linked list has at least two fields. The “data field” is used to store data, and the “pointer field” points to the address of the next node;
Advantages: No continuous storage space is required, no initial capacity and easy expansion;
Disadvantages: low storage density and does not support random access;

* Double linked list:
A singly linked list can only access its successor nodes through the pointer field of the node, and cannot access the predecessor node of the changed node. If you want to find the predecessor node of a node,
You need to start searching from the head node; therefore, in order to facilitate access to the predecessor node, a “double linked list” is created;
In the doubly linked list, the node structure is expanded. In addition to storing data, each node also has two pointer fields used to store the addresses of the predecessor node and the successor node;

* Circular linked list: The last node next of the singly linked list points to the head node, forming a cycle;
(There are also special ones: binary linked lists, cross linked lists, adjacency lists, adjacent multiple lists, etc., which are generally used to implement nonlinear structures)

(
There is also a special way to implement a linear table:
* Static linked list: Use an array to define a linked list. Each position in the array stores a value and the subscript of the next node, usually a structure array.
Advantages: Adding and deleting does not require moving a large number of elements, only the value of the pointer field needs to be modified.
Disadvantages: immutable capacity; requires continuous storage space, low storage density, and does not support random access
Application scenario: Some low-level languages that do not support pointers may need to use arrays to implement singly linked lists.
)

—————-
Comparison of sequential storage and chained storage of linear tables:
Time comparison:
Sequential tables can directly access each element through the index value, realizing random access to elements in the table; linked lists start checking from the head node each time, which is less efficient;
A large number of elements need to be moved when random additions and deletions are made to a sequential list, whereas random additions and deletions to a linked list only require moving the front and rear drive pointers, and do not require many moving elements.
So if it is a query operation, the priority list, if it is random addition and deletion, the priority list

Spatial comparison:
The sequence table needs to allocate a continuous storage space in advance, and idle space will appear during use, and it cannot store very large data; while the space of the linked list is dynamically allocated, and the space of the disk is
The utilization rate is high and no space is wasted. If the length of the linear table changes frequently, chained storage is preferred; if the length does not change much, sequential table is preferred because chained storage is preferred.
Storage requires additional space to store predecessors and successors, and the storage density is low;

*************************************************** *************************************************

SqList.c:

#define ElemType int
#defineMAXSIZE 10
#include <stdlib.h>
#include <stdio.h>

typedef struct{
ElemType* elem; //array base address
int capacity; //maximum capacity of table
int length; //table length
}SqList;

// Null pointer exception, used to determine whether the table pointer is NULL
static void NullPointerException(SqList *list){
if(list == NULL){exit(1);}
}

//Sequence table expansion (2x expansion)
static void ExpandSize(SqList *list){
//First, perform pointer null judgment
NullPointerException(list);

//Temporary pointer old, saves the base address of the old table
ElemType* old = list->elem;

//Apply for a new space, which is twice the original capacity
// First set the table capacity to 2 times the original size
list->capacity *= 2;
// Directly point the table pointer to the address of the new capacity
list->elem = (ElemType*)malloc(list->capacity * sizeof(ElemType));
// If the application fails, the program terminates directly
if(list->elem == NULL){exit(1);}

// The application is successful, copy the contents of the old table
int i;
for(i=0; i<list->length; i + + ){
list->elem[i] = old[i];
}

// Destroy old table
free(old);
}

// InitList( & amp;L): Initialize an empty sequence list, the default capacity is MAXSIZE
void InitList(SqList* list){
//First, perform pointer null judgment
NullPointerException(list);

// malloc dynamically applies for a continuous space and lets the sequence table point to this address.
list->elem = (ElemType*)malloc(MAXSIZE * sizeof(ElemType));
// If the application fails, the program terminates abnormally.
if(list->elem == NULL){exit(1);}
// The application is successful, other attributes in the initial table
list->length = 0;
list->capacity = MAXSIZE;
}

// DestroyList( & amp;L): Destroy sequence list
void DestroyList(SqList* list){
//First, perform pointer null judgment
NullPointerException(list);

// Destroy sequence table
free(list->elem);
// After the sequence table is destroyed, the table pointer is set to empty to prevent the reclaimed memory from being accessed again.
list->elem = NULL;
list->length = 0;
list->capacity = 0;
}

// ClearList( & amp;L): Clear the sequence list
void ClearList(SqList* list){
//First, perform pointer null judgment
NullPointerException(list);

list->length = 0;
}

// ListEmpty(L): Determine whether the sequence list is empty, return 1 if empty
int ListEmpty(SqList list){
return list.length == 0;//Here we only access the length attribute in the sequence table and do not modify it, so the function parameters do not need to be set to pointers.
}

// GetElem(L,i, & amp;e): Get the element at subscript i in the L table
ElemType GetElem(SqList list, int i){
ElemType ret;
if(i >= list.length || i < 0){ //Illegal subscript
exit(1);
}else { //Legal
ret = list.elem[i];
}
return ret;
}

// LocateElem(L,e): Locate the subscript of element e in the sequence table, return -1 on failure
//The time complexity of searching by value in the sequence table is: O(n)
int LocateElem(SqList list, ElemType e){
int ret = -1;
int i;
for(i=0; i<list.length; i + + ){
if(list.elem[i] == e){
ret = i;
break;
}
}
return ret;
}

//Get the table length
int GetSize(SqList list){
return list.length;
}

// ListInsert( & amp; L,i,e): Insert element e at the subscript i position of L, return subscript i successfully, and -1 if failed
//The time complexity of subsequent insertion or deletion in the sequence table is: O(n)
int ListInsert(SqList* list, int i, ElemType e){
//First, perform pointer null judgment
NullPointerException(list);

int ret = i;
if(i > list->length || i < 0){ //The subscript is out of bounds, return -1
ret = -1;
}else {
// Determine whether the table capacity is sufficient. If not, expand the capacity.
if(list->length == list->capacity){
ExpandSize(list);
}
//The capacity is sufficient or the expansion is completed, start inserting
int j;
for(j = list->length; j > i; j--){
list->elem[j] = list->elem[j-1];
}
list->elem[i] = e;
list->length + + ;
}
return ret;
}

// ListDelete( & amp;L,i): Delete the element of L at subscript i, return subscript i if successful, return -1 if failed
//The time complexity of subsequent insertion or deletion in the sequence table is: O(n)
int ListDelete(SqList* list, int i){
//First, perform pointer null judgment
NullPointerException(list);

int ret = i;
//The subscript is out of bounds and returns -1
if(i >= list->length || i < 0){
ret = -1;
}else {
\t\t//delete
int j;
for(j = i; j<list->length-1; j + + ){
list->elem[j] = list->elem[j + 1];
}
list->length --;
}
return ret;
}

// PriorElem(L,e, & amp;e): Get the element before e in L
ElemType PriorElem(SqList list, ElemType e){
ElemType ret;
int i = LocateElem(list, e);
if(i>0){
ret = list.elem[i-1];
}else{ //Element e does not exist or e is the first element and there is nothing in front of it, end the program
exit(1);
}
return ret;
}

// NextElem(L,e, & amp;e): Get the element after e in L
ElemType NextElem(SqList list, ElemType e){
ElemType ret;
int i = LocateElem(list, e);
if( i >= 0 & amp; & amp; i < list.length-1){
ret = list.elem[i + 1];
}else{ //There is no e or the last element, end the program
exit(1);
}
return ret;
}

// TraverseList(L): Traverse the value of each element in L
void TraverseList(SqList list){
printf("\
");
int i;
for(i=0; i<list.length; i + + ){
printf("%d ", list.elem[i]);
}
printf("\
");
}

// Sequence table copy, the parameters are: source table address, destination table address, source table start, destination table start, copy length; copy success returns 1, failure returns 0
int ListCopy(SqList *sList, SqList *dList, int sStart, int dStart, int size){
//First, perform pointer null judgment
NullPointerException(sList);
NullPointerException(dList);

// Check whether the subscript is legal
if(! ((sList->length)-sStart >= size & amp; & amp; (dList->capacity)-dStart <= size) ){return 0;}

//If legal, start copying
int i;
for(i=0; i<size; i + + ){
dList->elem[dStart + i] = sList->elem[sStart + i];
}
return 1;
}

//=============Test program================================== =============================
int main(int argc, char const *argv[])
{
//Define a sequence table and initialize it
SqList list;
InitList( & amp;list);

//Add element
ListInsert( & amp;list, 0, 12);
ListInsert( & amp;list, 1, 22);
ListInsert( & amp;list, 2, 32);
ListInsert( & amp;list, 3, 42);
printf("The element at subscript 3 is: %d\
", GetElem(list, 3));
printf("The subscript of element 32 is: %d\
", LocateElem(list, 32));

ListInsert( & amp;list, 2, 31);
ListDelete(&list, 1);
printf("The element before 31 is: %d\
", PriorElem(list, 31));
printf("The element after 31 is: %d\
", NextElem(list, 31));
TraverseList(list);

printf("Table length is: %d, table capacity is: %d\
", GetSize(list), list.capacity);
printf("Whether the sequence list is empty: %d\
", ListEmpty(list));
ClearList(&list);
printf("Whether the sequence list is empty: %d\
", ListEmpty(list));
printf("================================================ ==================\
");

//Finally, the sequence table must be destroyed
DestroyList( & amp;list);
printf("Whether the sequence list is empty: %d\
", ListEmpty(list));
return 0;
}

operation result:

*************************************************** *************************************************** ****

Single linked list SLinkedList.c:

#define ElemType int
#include <stdlib.h>
#include <stdio.h>

typedef struct Node{ //Single linked list node Node
ElemType elem; //data field
struct Node *next; //Pointer field
}Node;
// You can also add a *SLinkedList here, which omits the definition of the linked list structure below. You can use the data field of the table header to store the length of the table.
// But it is still not easy to use, because we don’t know which node is the end of the table, and it is inconvenient to add or delete at the end of the table; and we need to use double pointers, so we add a linked list structure, as shown below:

typedef struct SLinkedList{ //Singly linked list SLinkedList
struct Node *head; //List head
struct Node *tail; //Tail of linked list
int length; //Table length length
}SLinkedList;

// Null pointer exception, used to determine whether the table pointer is NULL
static void NullPointerException(SLinkedList *list){
if(list == NULL){exit(1);}
}

//Get the pointer to the i-th node on the linked list, no NULL is returned
Node* GetNode(SLinkedList* list, int i){
//First, perform empty judgment on the table pointer
NullPointerException(list);

if(list->length < i || i <= 0){ //Illegal subscript returns NULL
return NULL;
}else if(i == 1){ //Header node
return list->head;
}else if(i == list->length){ //Tail node of list
return list->tail;
}else{ //Node in the middle of the table
Node* t = list->head->next;
int j;
for(j=2; j<i; j + + ){
t = t->next;
}
return t;
}
}

// InitList( & amp;L): Initialize singly linked list
void InitList(SLinkedList* list){
//First, perform empty judgment on the table pointer
NullPointerException(list);

list->head = NULL;
list->tail = NULL;
list->length = 0;
}

// DestroyList( & amp;L): Destroy the singly linked list
void DestroyList(SLinkedList* list){
//First, perform empty judgment on the table pointer
NullPointerException(list);

// Empty table, nothing to do
if(list->length==0){
}else{//Non-empty list, delete linked list nodes layer by layer
Node* t = NULL;
while(list->head->next != NULL){
t = list->head;
list->head = list->head->next;
free(t);
}
free(list->head);

list->head = NULL;
list->tail =NULL;
list->length = 0;
}
}

// ListEmpty(L): Determine whether the singly linked list is empty
int ListEmpty(SLinkedList list){
return list.length == 0;
}

// ClearList( & amp;L): Clear the linear list
void ClearList(SLinkedList* list){
DestroyList(list);
}

//Get the table length
int GetSize(SLinkedList list){
return list.length;
}

//Insert element e into the header
void InsertHead(SLinkedList* list, ElemType e){
//First, perform empty judgment on the table pointer
NullPointerException(list);

// Create new node
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->elem = e;
newNode->next = list->head;
//Change the table header head
list->head = newNode;
list->length + + ;
//If the table length is 1 at this time, make the tail of the table also point to the newly added node
if(list->length == 1){
list->tail = newNode;
}
}

//Insert element e at the end of the table
void InsertTail(SLinkedList* list, ElemType e){
//First, perform empty judgment on the table pointer
NullPointerException(list);

// Create new node
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->elem = e;
newNode->next = NULL;
//If the table length is >0, change the tail of the table
if(list->length > 0){
list->tail->next = newNode;
list->tail = newNode;
}else{//If it is an empty table
list->head = newNode;
list->tail = newNode;
}
list->length + + ;
}

// Delete header
void DeleteHead(SLinkedList* list){
//First, perform empty judgment on the table pointer
NullPointerException(list);

// If the table is empty, do nothing
if(list->length == 0){
return;
}else{//The table is not empty
Node* t = list->head;
list->head = list->head->next;
free(t);
list->length --;
//If the table is empty at this time, set the tail of the table to empty
if(list->length == 0){
list->tail = NULL;
}
}
}

// Delete the end of the table
void DeleteTail(SLinkedList* list){
//First, perform empty judgment on the table pointer
NullPointerException(list);

// If the table is empty, do nothing
if(list->length == 0){
return;
}else{//The table is not empty
//When the table length is 1, just delete the only node of the table
if(list->length == 1){
free(list->head);
list->head = NULL;
list->tail = NULL;
}else{//When the table length is >1, the next of the predecessor node of the tail node needs to be left blank.
Node* t = list->head;
while(t->next!=list->tail){//If the next node is not the tail node, keep looking downwards
t = t->next;
}
//At this time t is the predecessor node of the tail node, delete and update the tail node
t->next = NULL;
free(list->tail);
list->tail = t;
}
//Last update table length
list->length --;
}
}

// ListInsert( & amp;L,i,e): Insert element e at the i-th position of the linked list
void ListInsert(SLinkedList* list, int i, ElemType e){
//First, perform empty judgment on the table pointer
NullPointerException(list);

if(i > list->length + 1 || i <= 0){ //The subscript is out of bounds and exits abnormally
exit(1);
}else { //The subscript is legal
if(list->length == 0 || i == 1){//If it is an empty list, or insert at the header
InsertHead(list, e);
}else if(i == list->length + 1){ //Add to the end of the table
InsertTail(list, e);
}else { //Add to table
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->elem = e;
Node* t = list->head;
int j;
for(j=1; j<i-1; j + + ){
t = t->next;
}
//At this time, t points to the front of the position to be inserted.
newNode->next = t->next;
t->next = newNode;
list->length + + ;
}
}
}

// ListDelete( & amp;L,i): Delete the element at the i-th position of the linked list and return
ElemType ListDelete(SLinkedList* list, int i){
//First, perform empty judgment on the table pointer
NullPointerException(list);

// First determine whether the subscript is out of bounds
if(i<1 || i>list->length){ exit(1); }

ElemType ret;
if(i == 1){ //Delete header
ret = list->head->elem;
DeleteHead(list);
}else if(i == list->length){//Delete the end of the table
ret = list->tail->elem;
DeleteTail(list);
}else{ //Delete the middle of the table
Node* priorNode = GetNode(list, i-1);
ret = priorNode->next->elem;
Node* t = priorNode->next;
priorNode->next = priorNode->next->next;
free(t);
list->length --;
}
return ret;
}

// insert forward
// void PriorInsert(SLinkedList* list, Node* node, ElemType e){//Insert element e forward to node
// Node* newNode = (Node*) malloc(sizeof(Node));
// newNode->elem = node->elem;
// node->elem = e;
// newNode->next = node->next;
// node->next = newNode;
// list->length + + ;
// if(list->tail == node){
// list->tail = newNode;
// }
// }

// insert after
// void NextInsert(SLinkedList* list, Node* node, ElemType e){//Insert element e into node
// Node* newNode = (Node*) malloc(sizeof(Node));
// newNode->elem = e;
// newNode->next = node->next;
// node->next = newNode;
// list->length + + ;
// if(list->tail == node){
// list->tail = newNode;
// }
// }

// GetElem(L,i, & amp;e): Get the element at subscript i in the L table
ElemType GetElem(SLinkedList* list, int i){
return GetNode(list, i)->elem;
}

//LocateElem(L,e): Locate element e in the table to see which element it is, and return -1 on failure
int LocateElem(SLinkedList list, ElemType e){
int ret = -1;
Node* t = list.head;
int i;
for(i=1; i<=list.length; i + + ){
if(t->elem == e){
ret = i;
break;
}else{
t = t->next;
}
}
// while(t != NULL){
// i + + ;
// if (t->elem == e) {
// return i;
// }else{
// t = t->next;
// }
// }
return ret;
}

//Traverse the linked list
void TraverseList(SLinkedList list){
Node* t = list.head;
printf("\
");
while(t != NULL){
printf("%d ", t->elem);
t = t->next;
}
printf("\
");
}

//=============Test program================================== =============================

int main(int argc, char const *argv[])
{
//Define a linked list and initialize it
SLinkedList list;
InitList( & amp;list);

// add element
InsertHead( & amp;list, 33);
InsertHead( & amp;list, 23);
InsertHead( & amp;list, 13);

printf("The second element is: %d\
", GetElem( & amp;list, 2));
printf("Element 33 is the %dth one in the list\
", LocateElem(list, 33));

InsertTail( & amp;list, 43);
ListInsert( & amp;list, 3, 333);
TraverseList(list);

ListDelete(&list, 3);
printf("\
Whether the linked list is empty: %d\
", ListEmpty(list));
DeleteHead( & amp;list);
DeleteTail( & amp;list);
TraverseList(list);
printf("The table length is: %d\
", GetSize(list));

ClearList(&list);
printf("Whether the linked list is empty: %d\
", ListEmpty(list));

//Finally the linked list must be destroyed
DestroyList( & amp;list);
printf("Whether the linked list is empty: %d\
", ListEmpty(list));
return 0;
}

operation result:

————————–

The code needs to be improved, comments and corrections are welcome O.O

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56976 people are learning the system