<>2.5 Representation and implementation of chain structure
* Head pointer , Header node and primitive node ：
* Benefits of header nodes ：① It is convenient for the processing of primitive nodes ;② Facilitate the processing of empty and non empty tables ;
* Characteristics of chain storage ：① The location of nodes in memory is arbitrary , That is, logically adjacent data elements are not necessarily adjacent physically ;② When accessing, you can only enter the linked list through the header pointer , And through the pointer field of each node
Scan other nodes backward in sequence , Therefore, it takes different time to find the first node and the last node ;
* Single linked list of leading nodes
<>2.5.1 Representation of single linked list
* Storage structure of single linked list ： typedef struct { int num; char name[20]; int score; }ElemType;
typedef struct LNode// Declare the type of the node and the pointer type to the node { ElemType data;// Data field of node struct LNode*
next;// Pointer field of node }LNode, * LinkList;//LinkList Is a pointing structure Lnode Pointer type of /* explain ： A structure type is defined
utilize typedef Rename as Lnode Then define the pointer LinkList point Lnode*/ /* Define node pointer p：Lnode *p; <==> LinkList
P;*/
<>2.5.2 Implementation of single linked list
[ algorithm 2.6 ] Initialization of single linked list （ Single linked list of leading nodes ）
Status InitList(LinkList& L) { L = (LinkList)malloc(sizeof(LNode)); /*L=new
LNode;*/ L->next = NULL; return OK; }
[ Supplementary algorithm 1 ] Determine whether the linked list is empty
int ListEmpty(LinkList L) { if (L->next)// Non empty { return 0; } else { return 1; } }
[ Supplementary algorithm 2 ] Destruction of single linked list
[ Algorithm idea ] Start from scratch , Release all nodes in turn ;
Status DestroyList(LinkList& L) { LNode* p;//LinkList p; while (L) { p = L; L =
L->next; free(p); } return 0; }
[ Supplementary algorithm 3 ] Empty linked list （ The linked list still exists , But there are no elements in the linked list , Become an empty linked list ）
[ Algorithm idea ] Release all nodes in turn , And set the pointer field of the head node to null ;
Status ClearList(LinkList& L) { LNode* p, * q; p = L->next; while (p) { q = p->
next; free(p); p = q; } L->next = NULL;// The pointer field of the header node is null return OK; }
[ Algorithm supplement 4 ] Find the table length of single linked list
[ Algorithm idea ] Starting from the initial node , Count all nodes in turn ;
int ListLength(LinkList L) { int count = 0;// Linked list length LNode* p; p = L->next; while
(p) { count++; p = p->next; } return count; }
[ algorithm 2.7 ] Find page i Elements
Status GetElem(LinkList L, int i, ElemType& e) { LNode* p; int j = 1; p = L->
next; while (p && j < i) { p = p->next; j++; } if (!p || j > i) { return ERROR;
} e = p->data; return OK; }
[ algorithm 2.8 ] Find by value
//O(n) LNode* LocateElem(LinkList L, ElemType e)/* Return address */ { LNode* p; p = L->
next; while (p && p->data != e) { p = p->next; } return p; } int LocateElem(
LinkList L, ElemType e)/* Returns the subscript of the element */ { LNode* p; int j = 1; p = L->next; while (p
&& p->data != e) { p = p->next; j++; } if (p) { return j; } else { return 0; } }
[ algorithm 2.9 ] insert （ In the first i The value inserted before nodes is e New node of ）
Status ListInsert(LinkList& L, int i, ElemType e) { LNode *s, *p; int j = 0; s
->data = e; p = L; while (p && j < i-1)// seek i-1 Nodes p point i-1 node { p = p->next; j++; }
if (!p || j > i-1) { return ERROR; } s->next = p->next; p->next = s; return OK;
}
[ algorithm 2.10 ] delete （ Delete paragraph i Nodes ）
Status ListDelete(LinkList& L, int i,ElemType &e) { LNode* p, * q; int j = 0; p
= L; while (p && j < i - 1) { p = p->next; j++; } if (!p || j > i - 1) { return
ERROR; } q = p->next; p->next = q->next;// Modify pointer e = q->data; free(q); return OK;
}
[ algorithm 2.11 ] Establish single linked list — Head insertion （ The element is inserted at the head of the linked list ）
/* Inverted insertion n Values of elements */ void CreateList(LinkList& L, int n) { LNode* p; int i; for (i =
n; i > 0; i--) { p = (LinkList)malloc(sizeof(LNode)); scanf("%d", &p->data); p
->next = L->next; L->next = p; } }
[ algorithm 2.12 ] Establish single linked list – Tail interpolation （ The element is inserted at the end of the linked list ）
/* Positive sequence input n Values of elements */ void CreateList(LinkList& L, int n) { LNode* p, *r; int i; r =
L; for (i = n; i > 0; i--) { p = (LinkList)malloc(sizeof(LNode)); scanf("%d",&p
->data); p->next = NULL; r->next = p; r = p;// The tail pointer points to the new node } }
<>2.5.3 Circular linked list
Circular linked list ： It's a kind of End to end linked list （ Namely ： The pointer field of the last node in the table points to the head node , The whole linked list forms a ring ）;
[ algorithm 2.13 ] Establishment of circular linked list
void CreateList(LinkList& L, int n) { LNode* p, *r; int i; r = L; for (i = n; i
> 0; i--) { p = (LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data); p->next =
NULL; r->next = p; r = p; } r->next = L; }
[ algorithm 2.14 ] Merging of circular linked list with tail pointer
LinkList Connect(LinkList Ta, LinkList Tb)// hypothesis Ta,Tb Are non empty single cycle linked lists { LNode p; p = (
LinkList)malloc(sizeof(LNode)); p = Ta->next; Ta->next = Tb->next->next; free(Tb
->next); Tb->next = p;// Modify pointer return Tb; }
<> Chain representation and implementation of linear list complete reference code
/* Look at the main function first 2021.1.17*/ #include<stdio.h> #include<stdlib.h> #define ERROR 0 #
define OK 1 typedef int Status; typedef int ElemType; typedef struct LNode {
ElemType data; struct LNode* next; }LNode, * LinkList; Status InitList(LinkList&
L) { L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; return OK; } /* void
CreateList(LinkList& L, int n) { LNode* p; for (int i = n; i > 0; i--) { p =
(LNode *)malloc(sizeof(LNode)); scanf("%d", &p->data); p->next = L->next;
L->next = p; } } */ void CreateList(LinkList& L, int n) { LNode* p, * r; r = L;
for (int i = n; i > 0; i--) { p = (LinkList)malloc(sizeof(LNode)); scanf("%d", &
p->data); p->next = NULL; r->next = p; r = p; } } int ListLength(LinkList L) {
int count = 0;// For counting LNode* p; p = L->next; while (p) { count++; p = p->next; }
return count; } Status GetElem(LinkList L, int i, ElemType& e) { int j = 1;
LNode* p; p = L->next; while (p && j < i) { p = p->next; j++; } if (!p || j > i)
{ return ERROR; } e = p->data; return OK; } int LocateElem(LinkList L, ElemType
e) { LNode* p; int j = 1; p = L->next; while (p && p->data != e) { p = p->next;
j++; } if (p) { return j; } else { return ERROR; } } Status ListInsert(LinkList&
L, int i, ElemType e) { LNode* s, * p; s = (LinkList)malloc(sizeof(LNode)); int
j= 0; p = L; s->data = e; while(p && j < i - 1) { p = p->next; j++; } if (!p ||
j> i - 1) { return ERROR; } s->next = p->next; p->next = s; return OK; } void
print(LinkList L) { LNode* p; p = L->next; while (p) { printf("%d ", p->data); p
= p->next; } printf("\n"); } Status ListDelete(LinkList& L, int i, ElemType& e)
{ LNode* p, * q; p = L; q = (LinkList)malloc(sizeof(LNode)); int j = 0; while (p
&& j < i - 1) { p = p->next; j++; } if (!p || j > i - 1) { return ERROR; } q = p
->next; e = q->data; p->next = q->next; free(q); return OK; } void ListEmpty(
LinkList L) { if (L->next) { printf(" Linked list is not empty \n"); } else { printf(" The linked list is empty \n"); } }
StatusClearList(LinkList& L) { LNode* p, * q; p = L->next; while (p) { q = p->
next; free(p); p = q; } L->next = NULL; return OK; } Status DestroyList(LinkList
& L) { LNode* p; while (L) { p = L; L = L->next; free(p); } printf(" Destruction completed \n");
return OK; } int main() { int n; int i; LinkList L; ElemType e; InitList(L);
/* Linked list initialization of the leading node */ printf(" Enter the number of elements ："); scanf("%d", &n);// Number of elements to enter printf(" Input element ：");
//CreateList(L, n);/* Header interpolation input element - Flashback state */ CreateList(L, n);/* Tail interpolation input element - order */ printf(
" Length of single linked list ：%d\n", ListLength(L));/* Find the table length of single linked list */ printf(" Enter the name of the lookup i position ："); scanf("%d", &i);
GetElem(L, i, e);/* Find page i Elements */ printf(" Find the second i The first element is ：%d\n", e); printf(" Value to find ：");
scanf("%d", &e); printf(" The index of the found element is ：%d\n", LocateElem(L, e));/* Find by value */ printf(
" Insert location ："); scanf("%d",&i); printf(" Element to insert ："); scanf("%d", &e); ListInsert(L, i,
e);/* The first i Insert element before position e*/ printf(" Linked list after inserting elements ："); print(L);// Output linked list printf(" Enter the location of the deleted element ：");
scanf("%d", &i); ListDelete(L, i, e);/* Delete paragraph i Elements */ printf(" Deleted element %d\n",e); printf(
" Linked list after deleting elements ："); print(L); ListEmpty(L);/* Determine whether the linked list is empty */ ClearList(L);/* Empty single linked list */ printf(
" After clearing the single linked list ："); ListEmpty(L);/* Determine whether the linked list is empty */ DestroyList(L);/* Destroy single linked list */ return 0; }
Technology