//Static allocation defines the sequence table. The storage space is static and the size is fixed from the beginning. #define MaxSize 10//Define the maximum length typedef struct{ ElemType data[MaxSize]; //Use static "array" to store data elements int length; //Current length of sequence table }SqList; //Type definition of sequence list (static allocation method) ElemType refers to the data type defined by yourself, such as int, double //Initialization sequence table #include<stdio.h> #define MaxSize10 typedef struct{ int data[MaxSize]; int length; }SqList; void InitList(SqList &L){ for(int i=0;i<MaxSize;i) L.data[i]=0; //Set all data elements to default initial values L.length=0; //Set the initial length of the sequence table to 0 } int main(){ SqList L; //Declare a sequence list InitList(L): //Initialization sequence list ... return 0; } //Dynamic allocation implementation sequence table, the size can be changed #include<stiod.h> #define InitSize 10 //Default maximum length typedef struct{ int *data; //Pointer indicating dynamically allocated array int MaxSize; //Maximum capacity of sequence table int length; //Current length of sequence table }SeqList; //Definition of sequence list int main(){ SeqList L; //Declare a sequence list InitList(L): //Insert several elements randomly into the network sequence table IncreaseSize(L,5); return 0; } void InitList(SeqList &L){ //Use the malloc function to apply for a continuous storage space L.data(int *)malloc(InitSize*sizeof(int)); L.length=0; L.MaxSize=InitSize; } //Increase the length of dynamic array void IncreaseSize(SeqList &L,int len){ int *p=L.data; L.data(int *)malloc((L.MaxSize len)*sizeof(int)): for(int i=0;i<L.length;i ){ L.data[i]=p[i]; //Copy data to new area } L.MaxSize=L.MaxSize len; //The maximum length of the sequence table increases by len free(p); //Release the original memory space }

L.data=(ElemType *)malloc(sizeof ElemType *InitSize) The malloc function returns a pointer, which needs to be cast to a pointer to the data element type you defined.

ListInsert(&L,I,e), inserts the specified element e at the i-th position

//Sequential table element insertion #define MaxSize 10 typedef struct{ ElemType data[MaxSize]; int length; }SqList; void ListInsert(SqList &L,int I,int e){ for(int j=L.length;j>I;j--){ //Move the i-th element and subsequent elements backward L.data[j]=L.data[j-1]; } L.data[i-1]=e; //Put e at the i-th position L.length; //Length 1 } int main(){ SqList L; InitList(L): //Omitted here, you can insert a series of elements ListInsert(L,3,3); return 0; } //In order to avoid inserting elements without feedback, for example, if the memory is full, the Insert function must be modified to have a return value. bool ListInsert(SqList &L,int I,int e){ if(i<1 || i>L.length 1) return false; if(L.length>=MaxSize) return false; for(int j=L.length;j>i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=e; L.length; return false; }

ListDelete(SqList &L,int i,int &e), deletes the element at position i in table L and returns the value of the element

//Delete sequence table bool ListDelete(SqList &L,int i,int &e){ if(i<1 || i>L.length 1) //Determine whether the range of i is valid return false; e=L.data[i-1]; for(int j=1;j<L.length;j) L.data[j-1]=L.data[j]; L.length--; return true; } int main(){ SqList L; InitList(L); int e=-1; if(ListDelete(L,3,e)) printf("Delete the 3rd element, the deleted element value is =%d/n",e); else pprintf("The bit order i is illegal, deletion failed "); return 0; }

GetElem(L,i), gets the value of the element at the i-th position in table L

//Search by bit //Static allocation #define MaxSize typedef struct{ ElemType data[MaxSize]; //Use static "array" to store data elements int length; //Current length of sequence table }SqList; //Type definition of sequence list (static allocation method) ElemType GetElem(SqList L,int i){ return L.data[i-1]; //Call the GetElem() function to return the value of the i-th element } //Dynamic allocation #defineInitSize typedef struct{ ElemType *data; int MaxSize; int length; }SeqList; ElemType GetElem(SeqList L,int i){ return L.data[i-1]; }

LocateElem(L,e), finds the element with the given keyword value in table L

//Search by value #defineInitSize 10 typedef struct{ ElemType *data; int MaxSize; int length; }SeqList; //Find the element whose first element value is equal to e in the sequence list L and return its bit order int LocateElem(SeqList L,ElemType e){ for(int i=0;i<L.length,i) if(int i=0;o<L.length;i) return i 1; //The value of the element marked i in the array is equal to e, and its bit order is returned i 1 return 0; //Exit the loop, indicating that the search failed }

Time complexity: best O(1), worst O(n), average O(n)

In addition to storing data elements, each node also stores a pointer to the next node.

struct LNode{ ElemType data; //Define single linked list node type struct LNode *next;//Each node stores a data element } struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode)); //Every time a new node is added, apply for a node space in the memory and use the pointer p to point to this node You can also use typedef struct LNode LNode; instead of LNode *p=(LNode *)maloc(sizeof(LNode)); In this case, you don’t need struct LNode to add nodes.

//Textbook, define a singly linked list typedef struct LNode{} //Define single linked list node type ElemType data; //data field struct LNode *next; //Pointer field LNode,*LinkList; //LNode is renamed, *LinkList is the pointer to this node Use LNode * to emphasize that this is a node Use LinkList to emphasize that this is a singly linked list

Leading node

No leading node

insert

delete

Bitwise search

Find by value

Find the length of the table

step1: Initialize a singly linked list step2: Remove one data element at a time and insert it into the head/foot of the table

tail insertion method

Head insertion method

Singly linked list: A singly linked list cannot be retrieved in reverse, which is sometimes inconvenient. Double linked list: can advance and retreat, lower storage density

//Initialization of double linked list (lead node) bool InitDLinkList(DLinklist &L){ L=(DNode *)malloc(sizeof(DNode)); if(L==NULL) return flase; L->prior=NULL; L->next=NULL; return true; } void testDLinkList(){ //Initialize double linked list DLinklist L; InitDLinkList(L); //...Following code } typedef struct DNode{ ElemType data; struct DNode *prior,*next; }DNode,*DLinklist; //Determine whether the double linked list is empty (lead node) bool Empty(DLinklist L){ if(L->next==NULL) return true; else return false; }

//Insertion into double linked list bool InsertNextDNode(DNode *p,DNode *s){ s->next=p->next; //Insert node *s after node *p p->next->prior=s; s->prior=p; p->next=s; }

//Delete double linked list bool DeleteNextDNode(DNode *p){ if(p==NULL) return flase; DNode *q=p->next; //Find the successor node q of p if(q==NULL) return false; //p has no successor node p->next=q->next; if(q->next!=NULL) //The q node is not the last node q->next->prior=p; free(q); //Release node space return true; } void DestoryList(DLinklist &L){ //Loop to release each data node while(L->next!=NULL) DeleteNextDNode(L); free(L); //Release the head node L=NULL; //Head pointer points to NULL }

//Traversal of double linked list while(p!=NULL){ //Backward traversal //Do corresponding processing for node p p=p->next; } while(p!=NULL){ //Forward traversal p=p->prioe; } while(p->prioe!=NULL){ //Forward traversal, skip the head node p=p->prior; }

Singly linked list: Starting from one node, only subsequent nodes can be found, but the previous nodes are unknown. Circular singly linked list: Starting from one node, you can find any other node.

//Define circular singly linked list typedef struct LNode{ //Define single linked list node type ElemType data; //Each node stores a data element struct LNode *next; //data points to the next node }LNode,*LinkList; //Initialize a circular singly linked list bool InitList(LinkList &L){ L=(LNode *)malloc(sizeof(LNode)); //Allocate a head node if(L==NULL) //Insufficient memory, allocation failed return false; L->next = L; //The head node Next points to the head node return true; } //Determine whether the circular singly linked list is empty bool Empty(LinkList L){ if(L->next==L) return true; else return flase; } //Determine whether node p is the end node of a circular singly linked list bool isTail(LinkList L,LNode *p){ if(p->next==L) return true; else return false; }

//Initialize empty circular double linked list bool InitDLinkList(DLinklist &L){ L=(DNode *)malloc(sizeof(DNode)); //Allocate a head node if(L==NULL) //Insufficient memory, allocation failed return false; L->prior=L; //The priority of the head node points to the head node L->next=L; //next of the head node points to the head node return true; } void testDLinkList(){ //Initialize circular double linked list DLinklist L; InitDLinkList(L); //...Following code } //Determine whether the circular double linked list is empty bool Empty(DLinklist){ if(L->next==L) return true; else return false; } //Determine whether node p is the end node of the circular doubly linked list bool isTail(DLinklist L,DNode *p){ if(p->next==L) return true; else return false; } typedef struct DNode{ ElemType data; struct DNode *prior,*next; }DNode,*DLinklist;

Singly linked list: Each node is randomly allocated in memory. Static linked list: Allocate a whole piece of continuous memory space, and each node is placed centrally.

//Define static linked list #define MaxSize 10 typedef sreuct{} ElemType data; int next; } void testSLinkList(){ struct Node a[MaxSize]; //...Following code } //You can also create a static linked list with the following code #define MaxSize 10 //Maximum length of static linked list typedef struct{ //Definition of static linked list structure type ElemType data; //Storage data elements int next; //array subscript of the next element } SLinkList[MaxSize]; void testSLinkLst(){} SLinkList a; //...Following code }

They are all linear tables and linear structures.

Advantages of sequence tables: support random access and high storage density. Disadvantages: It is inconvenient to allocate large areas of continuous space, and it is inconvenient to change the capacity. Advantages of linked lists: Discrete small spaces are easy to allocate and the capacity is easy to change. Disadvantages: No random access, low storage density.

Sequence table creation: A large contiguous space needs to be pre-allocated. If the allocated space is too small, it will be inconvenient to expand the capacity later; if the allocated space is too large, memory resources will be wasted. Static allocation: static array, immutable capacity Dynamic allocation: dynamic array (malloc, free), the capacity can be changed, but it requires moving a large number of elements, which is time-consuming. Destruction: Modify length=0, statically allocated space will be automatically reclaimed, dynamically allocated malloc application needs to be manually freed Inserting/deleting elements requires moving subsequent elements back/forward. The time complexity is O(n), and the time overhead mainly comes from moving elements. If the moving element is large, the moving time cost is high. Search: Bitwise search: O(1). Search by value: O(n). If the elements in the table are ordered, they can be found in O(log2n) time.

Linked list creation: You only need to allocate a head node (you can also omit the head node and only declare a head pointer), which can be easily expanded later. Destroy: Delete each node in turn (free) Inserting/deleting elements only requires modifying the pointer. The time complexity is O(n), and the time overhead mainly comes from finding the target element. The time cost of finding elements is lower. Search: Bitwise search: O(n). Find by value: O(n).

Use a sequential list or a linked list: The length of the list is difficult to estimate, and elements often need to be added, subtracted/deleted, so use a linked list. The table length can be estimated and there are many query (search) operations, so use a sequential table. Question: Please describe the sequence list and the linked list...Which is better to use the sequence list or the linked list? The logical structures of sequence lists and linked lists are linear results and both belong to linear lists. However, the storage structures of the two are different. The sequence table uses sequential storage... (features, advantages and disadvantages); the linked list uses chain storage... (advantages and disadvantages). Due to the use of different storage methods, the implementation efficiency of basic operations is also different. When initializing...when inserting a data element...when deleting a data element...when searching for a data element...

Implemented using "static array"

Once the size is determined, it cannot be changed

Implemented using "dynamic array"

L.data=(ElemType *)malloc (sizeof(El;emType)* size)

When the sequence table is full, malloc can be used to dynamically expand the maximum throughput of the sequence table.

It is necessary to copy the data elements to a new storage area and use the free function to release the original area.

Can find the i-th element in O(1) time

Definition (how to implement it in code)

Implementation of basic operations

Single list

Double linked list

circular linked list

static linked list

Insert element e into the i-th position of L

Best O(1), worst O(n), average O(n)

Delete the i-th element of L and return it with e

Best O(1), worst O(n), average O(n)

Get the value of the element at position i in table L

Use the array subscript to get the i-th element L.data[i-1]

The best/worst/average time complexity is O(1)

Find the element whose first element value is equal to e in the sequence list L and return its bit order

Search starting from the first element and going backward

The best time complexity is O(1)

Worst time complexity O(n)

Average time complexity O(n)

Empty table judgment: L==NULL

Easy to write code

Empty table judgment: L->next==NULL;

Writing code is inconvenient

Leading node

No leading node