線性表(上):Seqlist 順序表
- 基本了解
- 線性表
- 順序表
- 靜態順序表
- 動態順序表
- 編寫動態順序表
- 項目結構
- 基礎結構
- 初始化
- 尾插
- 頭插
- 尾刪
- 頭刪
- 查找
- 指定位置pos之前插入數據
- 刪除指定位置pos的數據
- 銷毀
- 完整代碼
- SeqLIst.h
- SeqLIst.c
- test.c
- 算法題
- 移除元素
- 刪除有序數組中的重復項
基本了解
線性表
線性表(linear list)是n個具有相同特性的數據元素的有限序列。 線性表是?種在實際中?泛使 ?的數據結構,常?的線性表:順序表、鏈表、棧、隊列、字符串…
線性表在邏輯上是線性結構,也就說是連續的?條直線。但是在物理結構上并不?定是連續的, 線性表在物理上存儲時,通常以數組和鏈式結構的形式存儲。
順序表
概念:順序表是??段物理地址連續的存儲單元依次存儲數據元素的線性結構,?般情況下采?數組存儲。順序表一般分為靜態順序表和動態順序表。
靜態順序表
優點:一次性開辟空間
缺點:不可改動,當數據量變化時,空間給大了會造成浪費,空間給小了容易導致數據丟失等問題。
typedef int SLDataType;
#define N 7
typedef struct SeqList {SLDataType arr[N];//定長數組int size; //有效數據個數int capacity; //空間大小
}SL;
動態順序表
優點:靈活可改動,隨時可擴容
typedef int SLDataType;
typedef struct SeqList {SLDataType* arr;//動態順序表,定義動態數組int size; //有效數據個數int capacity; //空間大小
}SL;
增容的一般邏輯:
編寫動態順序表
項目結構
SeqList
├── SeqList.h # 頭文件:定義結構、聲明
函數
├── SeqList.c # 實現文件:函數具體實現└── test.c # 測試文件:每寫一個功能以后都要測試一下
基礎結構
SeqLIst.h 中
typedef int SLDataType;
typedef struct SeqList {SLDataType* arr;//動態順序表,定義動態數組int size; //有效數據個數int capacity; //空間大小
}SL;
初始化
這里有一個易錯點提醒:函數傳參時一定要思考是要傳值還是傳址,只有傳址,函數改動的才是傳過去的變量本身!
比如如果初始化函數這么寫
void SLInit(SL s) {s.arr = NULL;s.size = s.capacity = 0;
}
測試
void test01() {SL sl;SLInit(sl);
}int main() {test01();return 0;
}
此時就會報這樣的錯誤,為什么呢?
因為傳值傳參,函數中形參是實參的拷貝,但sl是未初始化的變量,所以這個值拷貝無法完成,自然就會報錯了
所以注意此處進行傳址調用
void SLInit(SL* ps) {ps->arr = NULL;ps->size = ps->capacity = 0;
}
void test01() {SL sl;SLInit(&sl); //注意這里要傳地址
}int main() {test01();return 0;
}
尾插
注釋中標明了易錯的步驟和知識重點
void SLPushBack(SL* ps, SLDataType x) {//尾插前先判斷順序表是否仍有位置插入if (ps->size == ps->capacity) {ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//避免一開始capacity==0,做乘法以后仍為0出現問題SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) *ps->capacity*2);//用臨時指針接收realloc的返回值,防止擴容失敗返回NULL,導致影響順序表的存儲//注意realloc第二個參數單位是字節,擴容至原capacity的兩倍時,別忘了要乘上SLDataType的字節大小//realloc擴容邏輯:能就地擴就就地擴;不能就另找一塊(malloc新的內存塊)、拷貝(memcpy)、釋放舊塊(free)if (tmp == NULL) {perror("realloc fail!");//會在輸出里變成realloc fail!: Cannot allocate memoryexit(1);//直接退出程序}ps->arr = tmp;}//尾插操作,可以畫圖思考,發現size大小實時對應尾插的位置,不需要額外遍歷//記得自增size!ps->arr[ps->size++] = x;
}
測試
//測試尾插
void test02() {SL sl;SLInit(&sl);SLPushBack(&sl,1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);
}
int main() {test02();return 0;
}
時間復雜度為O(n)
頭插
判滿——將數據向右挪動(從右往左依次挪!)——把新數據放到頭部
判滿操作是在多個功能中都需要使用到的,所以這里我們把它單獨分出來
//判滿擴容操作
void SLCheckCapacity(SL* ps) {if (ps->size == ps->capacity) {ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//避免一開始capacity==0,做乘法以后仍為0出現問題SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);//用臨時指針接收realloc的返回值,防止擴容失敗返回NULL,導致影響順序表的存儲//注意realloc第二個參數單位是字節,擴容至原capacity的兩倍時,別忘了要乘上SLDataType的字節大小//realloc擴容邏輯:能就地擴就就地擴;不能就另找一塊(malloc新的內存塊)、拷貝(memcpy)、釋放舊塊(free)if (tmp == NULL) {perror("realloc fail!");//會在輸出里變成realloc fail!: Cannot allocate memoryexit(1);//直接退出程序}ps->arr = tmp;}
}
void SLPushHead(SL* ps, SLDataType x) {//檢查一下ps,如果傳入了空指針會導致程序直接報錯////比較溫和的方法//if (ps == NULL)// return;//比較粗暴的方法:使用斷言語句assert(ps);//等價于assert(ps!=NULL)SLCheckCapacity(ps);for (int i = ps->size - 1;i >= 0;i--) {ps->arr[i + 1] = ps->arr[i];}ps->arr[0] = x;
}
時間復雜度為O(n)
尾刪
特殊條件:順序表不能為空
操作:有效數據個數size–,原來的數據不做處理也沒有關系
void SLPopBack(SL* ps) {assert(ps && ps->size);ps->size--;
}
時間復雜度O(1)
頭刪
特殊條件:順序表不能為空
操作:
- 讓數組從左到右往左移一位(覆蓋)
- 有效數據個數size–,原來的數據不做處理也沒有關系
void SLPopHead(SL* ps) {assert(ps && ps->size);for (int i = 1;i < ps->size;i++) {ps->arr[i - 1] = ps->arr[i];}ps->size--;
}
時間復雜度O(n)
查找
設定找到了返回下標,未找到返回-1
int SLFind(SL ps, SLDataType x) {for (int i = 0;i < ps.size;i++) {if (ps.arr[i] == x)return i;//找到了就返回位置}//會運行到這一定是沒有找到return -1;
}
指定位置pos之前插入數據
在指定位置pos之前插入數據,實際上新數據就放在pos位置
特殊條件:插入都要判斷空間夠不夠,刪除都要判空
且pos有限制范圍pos>=0&&pos<=size
核心操作:pos之后的數據向右挪動一位(從右往左挪)
//指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x) {assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//插入都要判斷一下!for (int i = ps->size;i > pos;i--) {ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}
刪除指定位置pos的數據
特殊條件:刪除都要判空,且pos有限制范圍pos>=0&&pos<=size
核心操作:pos之后的數據向左挪動一位(從左往右往左挪)
//指定位置刪除數據
void SLErase(SL* ps, int pos) {assert(ps&&ps->size);assert(pos >= 0 && pos <= ps->size);for (int i = pos;i < ps->size-1;i++) {ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
銷毀
//銷毀
void SLDesTroy(SL* ps) {if (ps->arr) {//即arr非空free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}
完整代碼
SeqLIst.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SeqList {SLDataType* arr;//動態順序表,定義動態數組int size; //有效數據個數int capacity; //空間大小
}SL;//初始化
void SLInit(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);//頭插
void SLPushHead(SL* ps, SLDataType x);//尾刪
void SLPopBack(SL* ps);//頭刪
void SLPopHead(SL* ps);//查找
int SLFind(SL ps, SLDataType x);//指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x);//指定位置刪除
void SLErase(SL* ps, int pos);//銷毀
void SLDesTroy(SL* ps);
SeqLIst.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"//初始化
void SLInit(SL* ps) {ps->arr = NULL;ps->size = ps->capacity = 0;
}//判滿擴容操作
void SLCheckCapacity(SL* ps) {if (ps->size == ps->capacity) {ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//避免一開始capacity==0,做乘法以后仍為0出現問題SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);//用臨時指針接收realloc的返回值,防止擴容失敗返回NULL,導致影響順序表的存儲//注意realloc第二個參數單位是字節,擴容至原capacity的兩倍時,別忘了要乘上SLDataType的字節大小//realloc擴容邏輯:能就地擴就就地擴;不能就另找一塊(malloc新的內存塊)、拷貝(memcpy)、釋放舊塊(free)if (tmp == NULL) {perror("realloc fail!");//會在輸出里變成realloc fail!: Cannot allocate memoryexit(1);//直接退出程序}ps->arr = tmp;}
}
//尾插
void SLPushBack(SL* ps, SLDataType x) {SLCheckCapacity(ps);//尾插操作,可以畫圖思考,發現size大小實時對應尾插的位置,不需要額外遍歷//記得自增size!ps->arr[ps->size++] = x;
}//頭插
void SLPushHead(SL* ps, SLDataType x) {//檢查一下ps,如果傳入了空指針會導致程序直接報錯////比較溫和的方法//if (ps == NULL)// return;//比較粗暴的方法:使用斷言語句assert(ps);//等價于assert(ps!=NULL)SLCheckCapacity(ps);for (int i = ps->size - 1;i >= 0;i--) {ps->arr[i + 1] = ps->arr[i];}ps->arr[0] = x;//記得自增size!ps->size++;
}//尾刪
void SLPopBack(SL* ps) {assert(ps && ps->size);ps->size--;
}//頭刪
void SLPopHead(SL* ps) {assert(ps && ps->size);for (int i = 1;i < ps->size;i++) {ps->arr[i - 1] = ps->arr[i];}ps->size--;
}//查找
int SLFind(SL ps, SLDataType x) {for (int i = 0;i < ps.size;i++) {if (ps.arr[i] == x)return i;//找到了就返回位置}//會運行到這一定是沒有找到return -1;
}//指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x) {assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//插入都要判斷一下!for (int i = ps->size;i > pos;i--) {ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}//指定位置刪除數據
void SLErase(SL* ps, int pos) {assert(ps&&ps->size);assert(pos >= 0 && pos <= ps->size);for (int i = pos;i < ps->size-1;i++) {ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//銷毀
void SLDesTroy(SL* ps) {if (ps->arr) {//即arr非空free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"//測試初始化
void test01() {SL sl;SLInit(&sl);
}void test02() {SL sl;SLInit(&sl);//SLPushBack(&sl, 1);//SLPushBack(&sl, 2);//SLPushBack(&sl, 3);//SLPushBack(&sl, 4);//SLPushBack(&sl, 5);SLPushHead(&sl, 1);SLPushHead(&sl, 2);SLPushHead(&sl, 3);SLPushHead(&sl, 4);SLPushHead(&sl, 5);/*for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");SLPopHead(&sl);for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");SLPopBack(&sl);for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");*///測試findSLErase(&sl, 2);for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");SLInsert(&sl, 2, 7);for (int i = 0;i < sl.size;i++) {printf("%d ", sl.arr[i]);}printf("\n");
}int main() {test02();return 0;
}
算法題
移除元素
本題首先要審題,弄明白評測需要什么
- 返回非val的值的個數
- 修改nums,使它的前k個數必須是非val的值(順序不變),后面的數不管。
新數組法:創建一個與nums長度相同的新數組,只選取不等于val的值存儲進去,同時進行計數。再將新數組遍歷賦回給nums。(之前也說過,這個方法是以空間換時間的方法)
雙“指針”法
簡述思路:記錄兩個下標,一個負責探路,一個負責存儲和計數,一次遍歷中兩個下標同時發揮其作用。
int removeElement(int* nums, int numsSize, int val) {int src=0,dst=0;while(src<numsSize){if(nums[src]!=val){nums[dst]=nums[src];dst++;}src++;}return dst;
}
刪除有序數組中的重復項
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
注意題目強調有序數組,這意味著重復項都在一起,要利用好這個特性。
新數組法
創建一個與nums長度相同的新數組,只選取符合條件的數字進去,再將新數組遍歷賦回給nums。
雙"指針"法
畫圖思考讓思路更清晰!
依然是src負責讀取數據,dst負責錄入數據和返回數據數量
想象src在數組上面走,dst在數組下面走。
int removeDuplicates(int* nums, int numsSize) {int src=1,dst=0;//因為第一個元素一定算數,所以src可以從1開始走while(src<numsSize){if(nums[src]!=nums[dst]){nums[++dst]=nums[src];}src++;}return dst+1;
}
這個代碼還可以做進一步優化,減少沒必要的賦值操作:
當nums[src]!=nums[dst]時,如果src只比dst小1, nums[++dst]=nums[src];就相當于這個值自己給自己賦了,所以我們可以據此對代碼進一步優化。
int removeDuplicates(int* nums, int numsSize) {int src=1,dst=0;//因為第一個元素一定算數,所以src可以從1開始走while(src<numsSize){if(nums[src]!=nums[dst]&&++dst!=src){nums[dst]=nums[src];}src++;}return dst+1;
}