Code reference “interesting algorithm.C language implementation”

The article directories

• preface
• • 1, create order table
  • Insert elements into the sequence table
  • 3, order table drop element
  • 4. Sequence table instance analysis
  • • 1, the static
    • 2, the dynamic
  • 5. Summary of sequence table

preface

This chapter concludes: from the static and dynamic sequence table creation, insert, delete, and instance analysis

1, create order table

#define MaxSize=100;
ElemType Sqlist[MaxSize];
int len;
Len indicates the length of the order table
Copy the code

#define MaxSize 10

typedef int ElemType;	

typedef struct{
	int *elem;		// point to the first address of the sequence table elem
	int length;		// Table length (number of elements)
	int listsize;	// The storage capacity of the sequential table
}Sqlist;
void initSqlist(Sqlist* L)
{
	L->elem = (int*)malloc(MaxSize*sizeof(ElemType));	// open up memory and assign the first address of the space to L->elem
    if(! L->elem) {printf("Memory allocation failed");
        exit(0);
    }						// Returns if memory allocation fails
	L->length = 0;										// Generate an empty order table
	L->listsize = MaxSize;
}
Copy the code

Insert elements into the sequence table

Inserts a new element item at position I in the order list of length N

1, static table

void InsertElem(ElemType Sqlist[],int &n,int i,ElemType item)
{
    // Insert item into the ith position of the Sqlist
    int t;
    if(n==MaxSize || i<1 ||i>n+1)	exit(0);	// Illegal insert: determine whether the inserted element is in the right place, or whether the table is full, because the memory size of the table is fixed.
    for(t=n- 1; t>=i- 1; t--) Sqlist[t+1]=Sqlist[t];		// Move the element after i-1 one element back
    Sqlist[i- 1]=item;				// Insert item at position I
    n=n+1;							// Array length +1
}
Copy the code

2, dynamic table, if the sequence table is full, you can add a segment of memory space

void InsertElem(Sqlist* L, int i, ElemType item)
{
    // Insert item into position I of sequence table L
    ElemType* base, * insertPtr, * p;
    if (i<1 || i>L->length + 1)
    {
        printf("Unlawful penetration");
        exit(0);
    }	// Illegal insertion
    if (L->length >= L->listsize)
    {
        base = (ElemType*)realloc(L->elem, (L->listsize + 10) * sizeof(ElemType));
        // Reappend space
        L->elem = base;		// Update the memory base address
        L->listsize = L->listsize + 100;		// Increase the storage space by 100 units
    }
    insertPtr = &(L->elem[i - 1]);		//insertPtr is the insertion position
    for (p = &(L->elem[L->length - 1]); p >= insertPtr; p--) *(p +1) = *p;						// Move the elements after i-1 one element back in order
    *insertPtr = item;					// Insert the element at position I
    L->length++;
}
Copy the code

3, order table drop element

void DelElem(ElemType Sqlist[],int &n,int i)
{
    int j;
    if(i<1 || i>n) exit(0);		// Delete.
    for(j=i; j<n; j++) Sqlist[j- 1]=Sqlist[j];
    // Move the elements after position I forward
    n--;		/ long/table 1
}
Copy the code

void DelElem(Sqlist* L, int i)
{
    ElemType* delItem, * q;
    if (i<1 || i>L->length)
    {
        printf("Illegal deletion");
        exit(0);
    }
    delItem = &(L->elem[i - 1]);	//delItem refers to the ith element in the table
    q = L->elem + L->length - 1;			//q points to the end of the table
    for(++delItem; delItem <= q; ++delItem) *(delItem -1) = *delItem;		// Move the elements after position I forward
    L->length--;				/ long/table 1
}
Copy the code

4. Sequence table instance analysis

1, the static

#include "stdio.h"
#define MaxSize 10

// Basic operation //
Sqlist: address of the first table *len: length of the table I: position of the element to be inserted x: value of the element to be inserted
void insertElem(int Sqlist[], int* len, int i, int x)
{
    int t;
    if (i<1 || i> * len + 1 || *len == MaxSize)	// Illegal insert operation, or array elements are full
    {
        printf("This insert is illegal\n");
        return;
    }
    for (t = *len - 1; t >= i -1; t--) Sqlist[t +1] = Sqlist[t];
    Sqlist[i - 1] = x;			// Insert elements
    *len = *len + 1;
}
Sqlist: the first address of the table *len: the length of the table I: the position of the insert element
void DelElem(int Sqlist[], int* len, int i)
{
    int j;
    if (i<1 || i>*len)
    {
        printf("This insert is illgel\n");
        return;
    }
    for(j = i; j <= *len -1; j++) Sqlist[j -1] = Sqlist[j];
    *len = *len - 1;
}
void show_sqlist(int Sqlist[],int len)
{
    int i = 0;
    for (i = 0; i < len; i++)printf("%d", Sqlist[i]);
}
// Test the function
int main(a)
{
    int Sqlist[MaxSize];	// Define a static sequence table
    int len=0;
    int i;
    printf("please input six interger number\n");
    for (i = 0; i <6; i++) {scanf("%d", &Sqlist[i]);
        len++;
    }
    show_sqlist(Sqlist, len);
    printf("\nthe spare length is %d\n", MaxSize - len);
    insertElem(Sqlist, &len, 3.0);
    show_sqlist(Sqlist, len);
    insertElem(Sqlist, &len, 11.0);		Insert the integer 0 at position 11 in the table
    DelElem(Sqlist, &len, 6);
    show_sqlist(Sqlist, len);
    printf("\nthe spare length is %d\n", MaxSize - len);
    return 0;
}
Copy the code

2, the dynamic

Write a program to dynamically create a sequence table. Requirements: 1, the initial length of the order table is 10, enter 15 integers into the order table, and print out 2, delete the fifth element in the order table, print out the deleted result

/* write a program to dynamically create a sequence table. 1, the initial length of the order table is 10, enter 15 integers into the order table, and print out 2, delete the fifth element in the order table, print out the deleted result */
#include "stdio.h"
#include "conio.h"
#include "malloc.h"
#include <stdlib.h>
#define MaxSize 10

typedef int ElemType;	

typedef struct{
	int *elem;		// point to the first address of the sequence table elem
	int length;		// Table length (number of elements)
	int listsize;	// The storage capacity of the sequential table
}Sqlist;

// Initialize a sequence table
void initSqlist(Sqlist* L)
{
	L->elem = (int*)malloc(MaxSize*sizeof(ElemType));	// open up memory and assign the first address of the space to L->elem
    if(! L->elem) {printf("Memory allocation failed");
        exit(0);
    }						// Returns if memory allocation fails
	L->length = 0;										// Generate an empty order table
	L->listsize = MaxSize;
}
/* L: Sqlist type pointer I: insert element position item: insert element */
void InsertElem(Sqlist* L, int i, ElemType item)
{
    // Insert item into position I of sequence table L
    ElemType* base, * insertPtr, * p;
    if (i<1 || i>L->length + 1)
    {
        printf("Unlawful penetration");
        exit(0);
    }	// Illegal insertion
    if (L->length >= L->listsize)
    {
        base = (ElemType*)realloc(L->elem, (L->listsize + 10) * sizeof(ElemType));
        // Reappend space
        L->elem = base;		// Update the memory base address
        L->listsize = L->listsize + 100;		// Increase the storage space by 100 units
    }
    insertPtr = &(L->elem[i - 1]);		//insertPtr is the insertion position
    for (p = &(L->elem[L->length - 1]); p >= insertPtr; p--) *(p +1) = *p;						// Move the elements after i-1 one element back in order
    *insertPtr = item;					// Insert the element at position I
    L->length++;
}
/* L: Sqlist type pointer I: delete element position */
void DelElem(Sqlist* L, int i)
{
    ElemType* delItem, * q;
    if (i<1 || i>L->length)
    {
        printf("Illegal deletion");
        exit(0);
    }
    delItem = &(L->elem[i - 1]);	//delItem refers to the ith element in the table
    q = L->elem + L->length - 1;			//q points to the end of the table
    for(++delItem; delItem <= q; ++delItem) *(delItem -1) = *delItem;		// Move the elements after position I forward
    L->length--;				/ long/table 1
}
void print_list(Sqlist *L)
{
    int i = 0;
    for (i = 0; i < L->length; i++)printf("%d ",L->elem[i]);
}
// Test the function
int main(a)
{
    Sqlist L;
    int i = 0;
    initSqlist(&L);
    for (i = 0; i <15; i++) InsertElem(&L,i+1,i+1);     // Insert one element at a time at the end
    printf("\n the content of list is \n");
    print_list(&L);
    DelElem(&L, 5);
    printf("\n the content of list after delete is \n");
    print_list(&L);
    _getche();
    return 0;
}
Copy the code

5. Summary of sequence table