©2020-2024 ioDraw All rights reserved
catalogue
preface
one , Initial preparation
two , Tail insertion and tail deletion
three , Head in tail deletion
four , Random position insertion and deletion
five , Sequence table defect
six , All codes
preface
Both sequential and linked lists are linear lists
The essence of a sequence table is an array , Ability to continuously store data
one , Initial preparation
Establish structure
Static version
Because the static version capacity is fixed , So only two members are needed , That is, data members and members that record valid data
Because the static version is not easy to control the capacity , Big is easy to cause waste , Too small to use , Therefore, the dynamic version is more appropriate
Dynamic version
have 3 Members , One is a pointer to the data member type , Point to the starting position of the opening space , The second member record is valid data , The third is the current capacity
Because the structure type name is too long , Inconvenient to use , So use typedef Change its type name
In order to facilitate the storage of different types of data , Also use typedef Change type name , For example, when storing floating point data , As long as int Change to float or double that will do
Initializing structure variables
Because you want to change the arguments , So you have to send an address , Namely
Set all its data members to 0 or NULL
Judgment capacity
Because there was no space at first , So I don't know if it's full , Or is there no room at all , So use the conditional operator to judge
At the same time, it is also necessary to judge whether the capacity increase fails , If you fail, just give a hint , then exit(-1) Exit program
because realloc There are two cases of capacity increase , Therefore, the starting address is returned to a temporary pointer variable , After the capacity increase is successful, it can be assigned to the original pointer variable
The destruction sequence table is similar to the initialization sequence table , Just one more free
It's too troublesome to debug the code to see if there are no errors , So I have to print
two , Tail insertion and tail deletion
Judge whether the capacity is sufficient every time you tail insert data
Check whether there is any data in the sequence table every time , By way of assertion , Easy to find mistakes
three , Head in tail deletion
Judge whether the capacity is sufficient for each head insertion
The head insert needs to move the data back , Empty the space of the first element , Then insert the data like the inserted data
Check whether there is any data in the sequence table every time the header is deleted , By way of assertion , Easy to find mistakes
four , Random position insertion and deletion
To insert and delete data at random locations , Then you have to find its subscript first
Find subscript , Loop traversal , Returns its subscript if it can be found , Return if not found -1
Determine whether the capacity is sufficient for each random insertion
At the same time, we have to judge i Is it within the index range of the array , Adopt assertion , Easy to find mistakes
Random deletion to judge i Is it within the index range of the array , Adopt assertion , Easy to find mistakes
five , Sequence table defect
There's not enough space , Capacity expansion required , Capacity expansion is costly
Avoid frequent capacity expansion , One time is usually capacity expansion 2 times , There may be a waste of space
When inserting head or middle , Need to move data , There is also consumption
six , All codes
// Header file #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h>
// Static version //typedef int DataType; //#define N 1000 //typedef struct SeqList //{ //
DataType a[N]; // int sz; //}SL; // Dynamic version typedef int DataType; typedef struct
SeqList { DataType* a; int sz;// Number of valid data int capacity;// To open up the size of space }SL; // Initialization sequence table
void SeqListInit(SL* ps); // Check capacity void SeqListCheckCapacity(SL* ps); // Destruction sequence table
void SeqListDestroy(SL* ps); // Print sequence table void SeqListPrint(SL* ps); // Tail insertion void
SeqListPushBack(SL* ps, DataType x); // Tail deletion void SeqListPopBack(SL* ps); // Head insert
void SeqListPushFront(SL* ps, DataType x); // Header deletion void SeqListPopFront(SL* ps);
// lookup int SeqListFind(SL* ps, DataType pos); // Random position insertion void SeqListInsert(SL* ps,
DataType x); // Random location deletion void SeqListDelete(SL* ps); // Definition file #include"SeqList.h"
void SeqListInit(SL* ps) { ps->a = NULL; ps->sz = 0; ps->capacity = 0; } void
SeqListCheckCapacity(SL* ps) { if (ps->sz == ps->capacity) { int newcapacity =
ps->capacity == 0 ? 4 : 2 * ps->capacity; DataType* tmp =
(DataType*)realloc(ps->a, sizeof(DataType) * newcapacity); if (tmp == NULL) {
printf(" Capacity increase failed \n"); exit(-1); } ps->capacity = newcapacity; ps->a = tmp; } } void
SeqListDestroy(SL* ps) { free(ps->a); ps->a = NULL; ps->sz = 0; ps->capacity =
0; } void SeqListPrint(SL* ps) { int i = 0; for (i = 0; i < ps->sz; i++) {
printf("%d ", ps->a[i]); } printf("\n"); } void SeqListPushBack(SL* ps,
DataType x) { SeqListCheckCapacity(ps); ps->a[ps->sz] = x; ps->sz++; } void
SeqListPopBack(SL* ps) { assert(ps->sz > 0); ps->sz--; } void
SeqListPushFront(SL* ps,DataType x) { SeqListCheckCapacity(ps); int end1 =
ps->sz; while (end1) { int end2 = end1 - 1; ps->a[end1--] = ps->a[end2]; }
ps->a[end1] = x; ps->sz++; } void SeqListPopFront(SL* ps) { assert(ps->sz > 0);
int begin1 = 0; while (begin1 < ps->sz) { int begin2 = begin1 + 1;
ps->a[begin1++] = ps->a[begin2]; } ps->sz--; } int SeqListFind(SL* ps, DataType
pos) { int cur = 0; while (cur < ps->sz) { if (ps->a[cur] == pos) { return cur;
} else { cur++; } } return -1; } void SeqListInsert(SL* ps, DataType x) {
SeqListCheckCapacity(ps); int i = SeqListFind(ps, 5); assert(i >= 0 && i <=
ps->sz); int end1 = ps->sz; while (end1 > i) { int end2 = end1 - 1;
ps->a[end1--] = ps->a[end2]; } ps->a[end1] = x; ps->sz++; } void
SeqListDelete(SL* ps) { int i = SeqListFind(ps, 5); assert(i >= 0 && i <=
ps->sz); while (i < ps->sz) { int cur = i + 1; ps->a[i++] = ps->a[cur]; }
ps->sz--; } // Test file #include"SeqList.h" void test1() { SL s; SeqListInit(&s);
SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3);
SeqListPushBack(&s, 4); SeqListPushBack(&s, 5); SeqListPushBack(&s, 6);
SeqListPushBack(&s, 7); SeqListPrint(&s); SeqListPopBack(&s);
SeqListPopBack(&s); SeqListPopBack(&s); SeqListPopBack(&s); SeqListPopBack(&s);
SeqListPrint(&s); SeqListDestroy(&s); } void test2() { SL s; SeqListInit(&s);
SeqListPushFront(&s, 1); SeqListPushFront(&s, 2); SeqListPushFront(&s, 3);
SeqListPushFront(&s, 4); SeqListPushFront(&s, 5); SeqListPushFront(&s, 6);
SeqListPushFront(&s, 7); SeqListPrint(&s); SeqListPopFront(&s);
SeqListPopFront(&s); SeqListPopFront(&s); SeqListPopFront(&s);
SeqListPopFront(&s); SeqListPrint(&s); /*int ret = SeqListFind(&s, 3);
printf(" The index of the number to find is ：%d\n", ret);*/ SeqListDestroy(&s); } void test3() { SL s;
SeqListInit(&s); SeqListPushBack(&s, 1); SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPushBack(&s, 5);
SeqListPushBack(&s, 6); SeqListPushBack(&s, 7); SeqListInsert(&s, 15);
SeqListPrint(&s); SeqListDelete(&s); SeqListPrint(&s); } int main() {
//test1(); //test2(); test3(); return 0; }
Technology