目錄

1.線性表

2.順序存盤結構(順序表)

2.1順序表一般可以分為：

1. 靜態順序表：使用定長陣列存盤元素

1.1靜態順序表:順序表的大小是確定的,容量是固定的.

結論:靜態順序表不是很常量,了解就行.

2. 動態順序表：使用動態開辟的陣列存盤，(重要)

2.1優點:我們可以根據實際情況,對記憶體進行自由分配,從而不造成記憶體分配浪費!

2.2順序表的定義

2.3順序表的初始化

2.4順序表增容:

2.5順序表的洗掉

思路 :

2.6順序表的查找:

思路:

2.7順序表的列印

2.8順序表的釋放

2.9順序表的插入

2.10順序表的頭插頭刪

2.11順序表的尾插尾刪

1.線性表

2.順序存盤結構(順序表)

順序存盤結構(順序表)的定義:線性表的順序存盤結構，指的是用一段地址連續的存盤單元依次存盤線性表的資料元素

2.1順序表一般可以分為：

1. 靜態順序表：使用定長陣列存盤元素

1.1靜態順序表:順序表的大小是確定的,容量是固定的.

#define N 10000//運用宏定義,可以方便修改容量的大小
typedef int SLDataType;//運用宏定義,可以根據情況改變存盤型別

// 靜態順序表
typedef struct SeqList
{
	SLDataType a[N];
	int size; // 表示陣列中存盤了多少個資料
}SL;

結論:靜態順序表不是很常量,了解就行.

2. 動態順序表：使用動態開辟的陣列存盤，(重要)

2.1優點:我們可以根據實際情況,對記憶體進行自由分配,從而不造成記憶體分配浪費!

2.2順序表的定義

typedef int sldatatype;//根據實際情況,可以改變存盤的型別

typedef struct {
	sldatatype* a;//開辟陣列a
	int size;//多少個資料
	int capacity;//容量是多大

}sl;

2.3順序表的初始化

        //順序表初始化
		void SeqListInit(SL* ps)
		{
			ps->a = NULL;
			ps->size = ps->capacity = 0;//賦值0
		}
        //指標設為空指標,ps指向的容量和資料都賦值0

2.4順序表增容:

請記住:兩種情況都要擴容:

記憶體還未開辟

記憶體滿了開辟

代碼如下

		void SeqListCheckCapacity(SL* ps)//順序表擴容
		{
			// 如果沒有空間或者空間不足，那么我們就擴容
			if (ps->size == ps->capacity)
			{
				int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
				if (tmp == NULL)
				{
					printf("realloc fail\n");
					exit(-1);//擴容都要這種判斷是否成功
				}
		
				ps->a = tmp;
				ps->capacity = newcapacity;
			}
}

2.5順序表的洗掉

		// 洗掉pos位置的資料
		void SeqListErase(SL* ps, int pos)
		{
			assert(pos >= 0 && pos < ps->size);//防止越界
		
			int begin = pos + 1;//遍歷從0開始,要加1//取出要刪掉的數字
			while (begin < ps->size)
			{
				ps->a[begin - 1] = ps->a[begin];//刪掉的元素的位置后面每個元素都要往前挪.
				++begin;
			}
		
			ps->size--;
		}

思路 :

1.取出要刪掉的數字;

2.刪掉的元素的位置后面每個元素都要往前挪.

2.6順序表的查找:

//輸入你要查找的資料，找到這個資料就回傳資料的下標，找不到就回傳-1.
			int SeqListFind(SL* ps, SLDataType x)
			{
				for (int i = 0; i < ps->size; i++)
				{
					if (ps->a[i] == x)
					{
						return i;//查找對應那個資料的下標
					}
				}
			
				return -1;
            }

思路:

1.查找你要找的資料

2.找得到,就回傳該資料的下標

3.找不到就回傳-1

2.7順序表的列印

		void SeqListPrint(SL* ps)
		{
			for (int i = 0; i < ps->size; ++i)
			{
				printf("%d ", ps->a[i]);
			}
			printf("\n");
        }

2.8順序表的釋放

	順序表釋放://擴容就要釋放//但只能有一個
		void SeqListDestory(SL* ps)
		{
			free(ps->a);
			ps->a = NULL;
			ps->capacity = ps->size = 0;//釋放都要這樣
		}

2.9順序表的插入

	//順序表插入
		// 指定pos下標位置插入
		void SeqListInsert(SL* ps, int pos, SLDataType x)
		{
			// 溫柔的處理方式
			/*if (pos > ps->size || pos < 0)
			{
				printf("pos invalid\n");
				return;
			}*///防止越界
			// 粗暴的方式
			assert(pos >= 0 && pos <= ps->size);

            //兩種方式都可以,但推薦粗暴的方式
		
			SeqListCheckCapacity(ps);
		
			// 挪動資料
			int end = ps->size - 1;
			while (end >= pos)
			{
				ps->a[end + 1] = ps->a[end];//增加位置,把前面的都推到后面去
				--end;
			}
		
			ps->a[pos] = x;
			ps->size++;

2.10順序表的頭插頭刪

	順序表頭插
	void SeqListPushFront(SL* ps, SLDataType x)
	{
		SeqListCheckCapacity(ps);//擴容

		//挪動資料
		int end = ps->size - 1;
		while (end >= 0)
		{
			ps->a[end + 1] = ps->a[end];
			--end;
		}
		ps->a[0] = x;
		ps->size++;
	
		//SeqListInsert(ps, 0, x);其實用插入就足夠了
	}

	順序表頭刪
	void SeqListPopFront(SL* ps)
	{
		assert(ps->size > 0);
	
	//挪動資料
			int begin = 0;
			while (begin < ps->size-1)
			{
				ps->a[begin] = ps->a[begin+1];
				++ begin;
			}
	
			int begin = 1;
			while (begin < ps->size)
			{
				ps->a[begin-1] = ps->a[begin];
				++begin;
			}
	
		ps->size--;

		//SeqListErase(ps, 0);用這個洗掉就足夠了
	}
	

2.11順序表的尾插尾刪

	//順序表尾插
	void SeqListPushBack(SL* ps, SLDataType x)
	{
		/*SeqListCheckCapacity(ps);
	
		ps->a[ps->size] = x;
		ps->size++;*/
		SeqListInsert(ps, ps->size, x);//用插入就可以代替
	}
	
	//順序表尾刪
	void SeqListPopBack(SL* ps)
	{
		// 溫柔處理方式
		//if (ps->size > 0)
		//{
		//	//ps->a[ps->size - 1] = 0;
		//	ps->size--;
		//}
	
		// 暴力處理方式
		/*assert(ps->size > 0);
		ps->size--;*/
	
		SeqListErase(ps, ps->size-1);//用洗掉就可以洗掉
	}