【零基礎學會資料結構】--順序表

什么是順序表

順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完
成資料的增刪查改，

靜態順序表

靜態順序表的本質其實就是陣列，其缺點就是空間有限，容納的資料量有限，

靜態順序表代碼

#define max 100
struct 	Seqlist{
    int arr[max];
    int size;
}

函式介面概念

函式介面:函式介面就是專門進行某一功能的函式，如順序表的資料的尾部插入，資料的頭部插入，順序表的初始
化.....這一系列的函式都稱為函式介面，有了函式介面以后，每個函式的功能變的獨立，也易于程式員進行調
試操作，

動態順序表

顧名思義，動態順序表就是在靜態順序表的基礎上做了升級，動態順序表可以動態的對記憶體空間進行擴容，可以
存盤更多的資料，

順序表的代碼呈現(為了讓代碼趨于作業化，以下代碼進行了分檔案書寫)

代碼一：函式介面的宣告

#pragma once
#include<stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int Seqlistdata;



typedef struct Seqlist {
	Seqlistdata* a;
	Seqlistdata size;
	Seqlistdata capacity;
}SL;

void Seqlistinit(SL* ps);//順序表的初始化
void Seqlistpushback(SL* ps, Seqlistdata x);//順序表的尾插
void Seqlistpopback(SL* ps);//順序表的尾刪
void Seqlistpushfront(SL* ps, Seqlistdata x);//順序表的頭插
void Seqlistpopfront(SL* ps);//順序表的頭刪
void Seqcheckcapacity(SL* ps); //順序表的擴容
void Seqlistprint(SL* ps);   //順序表的列印
void Seqlistdelete(SL* ps); //順序表的銷毀
void Seqlistinsert(SL* ps, int x, int y);//順序表的指定位置插入
int Seqlistfind(SL* ps, Seqlistdata x);//順序表里的資料查找
void Seqlisterase(SL* ps, int x);//順序表的指定下標位置洗掉

代碼二：函式介面的實作

#include"seqlist.h"


void Seqlistinit(SL* ps) {//順序表的初始化
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

void Seqcheckcapacity(SL* ps) {//順序表的擴容
	if (ps->size == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		Seqlistdata* tmp = (Seqlistdata*)realloc(ps->a, newcapacity * sizeof(Seqlistdata));
		if (tmp == NULL) {
			printf("tmp failed");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;





	}

}


void Seqlistpushback(SL* ps, Seqlistdata x) {//順序表的尾插
	Seqcheckcapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;

}

void Seqlistpopback(SL* ps) {//順序表的尾刪
	assert(ps->size > 0);
	ps->size--;
}



void Seqlistprint(SL* ps) {//順序表的列印
	for (int i = 0; i < ps->size; i++)
		printf("%d", ps->a[i]);
}


void Seqlistpushfront(SL* ps, Seqlistdata x) {      //順序表的頭插
	Seqcheckcapacity(ps);
    int end = ps->size;
	while (end) {
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}


void Seqlistpopfront(SL* ps) {//順序表的頭刪
	for (int i = 0; i < ps->size; i++) {
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

void Seqlistdelete(SL* ps) {//順序表的銷毀
	ps->capacity = 0;
	ps->size = 0;
	free(ps->a);
	ps->a = NULL;
}


int Seqlistfind(SL* ps, Seqlistdata x) {//順序表里的資料查找
	for (int i = 0; i < ps->size; i++) {
		if (ps->a[i] == x)
			return i;
	}
	return -1;
}


void Seqlistinsert(SL* ps, int x,int y)順序表的指定位置插入
{


	int end = ps->size;
	while (end - x) {
		ps->a[end] = ps->a[end - 1];
		end--;
	}

	ps->a[x] =y;
	ps->size++;
}

void Seqlisterase(SL* ps, int x) {//順序表的指定下標位置洗掉
	assert(x>= 0 && x < ps->size);

	int begin = x + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}

	ps->size--;
}

代碼三：函式介面的測驗

#include "SeqList.h"
#include<stdio.h>



void test03() {
	SL sll;

	Seqlistinit(&sll);

	Seqlistpushback(&sll, 3);
	Seqlistpushback(&sll, 4);
	Seqlistinsert(&sll, 1, 4);
	Seqlistpushfront(&sll, 8);
	Seqlistpopfront(&sll);
	Seqlistprint(&sll);

}

int main(){
	test03();
}

順序表的代碼分析

第一步 結構體的創建

typedef struct Seqlist {
	Seqlistdata* a;
	Seqlistdata size;
	Seqlistdata capacity;
}SL;

一個順序表的作用就是用來存盤資料，這時就要用到結構體，在這個結構體中定義了三個變數
1. 結構體指標a，結構體指標a用來存盤結構體的地址
2.結構體的容量大小capacity，即這個結構體可以最多存盤的資料的個數，
3.結構體的使用容量size,當前結構體已經存盤的資料的個數，

結構體的初始化

void Seqlistinit(SL* ps) {//順序表的初始化
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}
結構體的初始化需要完成三個操作，
1.將結構指標置為空指標，
2.將結構體的初始容量置為0，
3.將結構體的使用容量置為0，

結構體的擴容操作

void Seqcheckcapacity(SL* ps) {//順序表的擴容
if (ps->size == ps->capacity) {
	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
	Seqlistdata* tmp = (Seqlistdata*)realloc(ps->a, newcapacity * sizeof(Seqlistdata));
	if (tmp == NULL) {
			printf("tmp failed");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;





	}

}

在對順序表進行存盤資料的時候，因為容量有限，所以為了存盤更多的資料，所以需要對順序表的空間大小進行
擴容(即申請一塊更大的空間)
    
進行順序表的擴容有以下幾個操作
1.判斷順序表的容量是否全部用完，方法：比較使用容量size和順序表容量capacity的大小，當使用容量size
==順序表容量capacity時，這時有兩種情況，
情況一：順序表的使用容量===順序表容量！=0，意味著順序表的容量已經用完.
情況二：順序表的使用容量==順序表的容量==0，意味著順序表的容量為0.
所以還需要進行順序表初始容量的判斷，這時進行判斷順序表的容量是否等于0，如果等于0，就申請4個大小的
容量，反之將其容量擴大兩倍，

2.在確立了順序表的容量大小以后，就需要進行第二步操作，為順序表的容量大小申請一塊記憶體空間，這時使用
到realloc函式，并且還需要判斷新空間的申請是否成功，
    
3.最后一步操作，也是非常關鍵的一步操作，將申請的容量賦值給capacity，將新空間的地址賦值給結構體指標
a， 

順序表的尾部插入

void Seqlistpushback(SL* ps, Seqlistdata x) {//順序表的尾插
	Seqcheckcapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;

}

在對順序表的進行尾部插入的時候有以下幾個操作：
1.對順序表進行尾部操作之前需要先對順序表進行擴容，防止順序表的容量不夠，
2.將資料插入到順序表的尾部，再將順序表的使用容量進行自增的操作，    

順序表的尾部洗掉

void Seqlistpopback(SL* ps) {//順序表的尾刪
	assert(ps->size > 0);
	ps->size--;
}


順序表的尾部洗掉具有以下幾個操作：
1.判斷順序表的使用容量，只有當順序表的使用容量大于0時，才能執行順序表的尾部洗掉，
2.在判斷條件成立的情況下將順序表的使用容量進行自減操作，

順序表的頭部插入

void Seqlistpushfront(SL* ps, Seqlistdata x) {      //順序表的頭插
	Seqcheckcapacity(ps);
    int end = ps->size;
	while (end) {
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

順序表的頭部插入具有以下幾個操作

1.將后面的資料進行向后移位操作，這時需要注意的是，移位操作必須從最后一個開始，如圖所示

2.將資料插入到頭部，使用容量進行自增

順序表的頭刪

void Seqlistpopfront(SL* ps) {//順序表的頭刪
    assert(ps->size>0)
	for (int i = 0; i < ps->size; i++) {
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

順序表的頭刪具有以下幾個操作

1.判斷順序表的使用容量是否大于0，如果大于0將順序表后面的資料進行向前移位操作，這時需要從第二個數字開始移位，如圖所示

2.將順序表的使用容量進行自減的操作，

順序表的列印操作

void Seqlistprint(SL* ps) {//順序表的列印
	for (int i = 0; i < ps->size; i++)
		printf("%d", ps->a[i]);
}


這個函式介面的功能不難理解，觀察代碼即可.

順序表的銷毀

void Seqlistdelete(SL* ps) {//順序表的銷毀
	ps->capacity = 0;
	ps->size = 0;
	free(ps->a);
	ps->a = NULL;
}

順序表的銷毀具有以下幾個操作：
1.將順序表所占的記憶體空間進行釋放，
2.將結構體指標置為空，
3.將使用容量和順序表容量置為0，

順序表的傳參(非常重要)

順序表在進行一系列的操作的時候，只需要得知順序表的首地址即可以，所以順序表函式介面的形參都應該接收
一個結構體指標，實參傳遞的也都是一個結構體指標，順序表使用這個結構體指標的下標就可以訪問到順序表里
的所有元素，并進行相應的操作，傳參的這一步操作需要自己進行理解，

剩下的幾個順序表的函式介面大都是在前面的幾個介面的基礎上進行了升級，不做過多的贅述，留給大家自行實
現，
重要的事說三遍!!!!!
一定要理清楚順序表中每個引數的設定原因，函式引數的傳遞原因，并且多動手實作，相信你一定可以敲出一個
完美的順序表.