目錄
- 1.線性表
- 2.順序表
- 順序表缺陷：
- 順序表的實作
- 順序表的初始化
- 順序表的銷毀
- 順序表擴容
- 順序表的頭插
- 順序表的尾插
- 順序表的遍歷列印
- 順序表的尾刪
- 順序表的頭刪
- 順序表的查找
- 洗掉
- 插入
- 修改
- 順序表的問題及思考：
- 力扣題
- 27. 移除元素:
- 26. 洗掉有序陣列中的重復項:
- 27. 陣列形式的整數加法:
- 旋轉陣列:
- 合并陣列陣列:
1.線性表
線性表（linear list）是n個具有相同特性的資料元素的有限序列， 線性表是一種在實際中廣泛使用的資料結
構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…
線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物
理上存盤時，通常以陣列和鏈式結構的形式存盤，
2.順序表
2.1概念及結構
順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列
上完成資料的增刪查改，
順序表一般可以分為：
-
靜態順序表：使用定長陣列存盤，
-
動態順序表：使用動態開辟的陣列存盤，
順序表缺陷：
1、動態增容有性能消耗（頻繁地malloc是會有記憶體消耗的）
2、需要頭部插入資料，需要挪動資料
順序表的實作
介面宣告
//初始化
void SeqListInit(SeqList *ps);
//頭插
void SeqListPushFront(SeqList *ps, int x);
//尾插
void SeqListPushBack(SeqList *ps,int x);
//頭刪
void SeqListPopFront(SeqList *ps);
//尾刪
void SeqListPopBack(SeqList *ps);
//銷毀
void SeqListDestroy(SeqList *ps);
//擴容
void SeqListCreate(SeqList *ps);
//列印
void SeqListprint(SeqList * ps);
//查找
int SeqListFind(SeqList * ps, int x);
//洗掉
void SeqListErase(SeqList *ps, int pos);
//插入
void SeqListInsert(SeqList *ps, int pos,int x);
//修改
void SeqListmodif(SeqList *ps, int pos, int x);
實作的介面
//初始化
void SeqListInit(SeqList *ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//擴容
void SeqListCreate(SeqList *ps)
{
assert(ps);
if (ps->capacity == ps->size)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
int *newA = (int *)realloc(ps->arr, sizeof(int) * newcapacity);
if (newA == NULL)
{
perror("SeqListCreate:");
exit(1);
}
ps->arr = newA;
ps->capacity = newcapacity;
}
}
//頭插
void SeqListPushFront(SeqList *ps,int x)
{
assert(ps);
SeqListCreate(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->arr[end + 1] = ps->arr[end];
end--;
}
ps->arr[0] = x;
ps->size++;
}
//尾插
void SeqListPushBack(SeqList *ps,int x)
{
assert(ps);
SeqListCreate(ps);
ps->arr[ps->size++] = x;
}
//頭刪
void SeqListPopFront(SeqList *ps)
{
assert(ps);
assert(ps->size > 0);
int begin = 0;
while (begin < ps->size)
{
ps->arr[begin] = ps->arr[begin + 1];
begin++;
}
ps->size--;
}
//尾刪
void SeqListPopBack(SeqList *ps)
{
assert(ps);
assert(ps->size > 0);
ps->size--;
}
//銷毀
void SeqListDestroy(SeqList *ps)
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//列印
void SeqListprint(SeqList * ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ",ps->arr[i]);
}
printf("\n");
}
//查找
int SeqListFind(SeqList * ps, int x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
//洗掉
void SeqListErase(SeqList *ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
int begin = pos;
while (begin < ps->size)
{
ps->arr[begin] = ps->arr[begin + 1];
++begin;
}
ps->size--;
}
//插入
void SeqListInsert(SeqList *ps, int pos, int x)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
SeqListCreate(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->arr[end + 1] = ps->arr[end];
end--;
}
ps->arr[pos] = x;
ps->size++;
}
//修改
void SeqListmodif(SeqList *ps, int pos, int x)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
ps->arr[pos] = x;
}
順序表的初始化
初始化表結構的成員
//初始化
void SeqListInit(SeqList *ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
順序表的銷毀
釋放在堆上開辟的空間
//銷毀
void SeqListDestroy(SeqList *ps)
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
順序表擴容
面對空間已滿，沒法再插入資料的情況，需要增容
//擴容
void SeqListCreate(SeqList *ps)
{
assert(ps);
//空間滿了開辟一塊新的空間
if (ps->capacity == ps->size)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
int *newA = (int *)realloc(ps->arr, sizeof(int) * newcapacity);
if (newA == NULL)
{
perror("SeqListCreate:");
exit(1);
}
ps->arr = newA;
ps->capacity = newcapacity;
}
}
順序表的頭插
頭插資料需要考慮是從前往后挪動資料還是從后往前挪動資料，很明顯如果是從前往后挪動資料的話，會將原有的資料給覆寫掉，所以只能從后往前，頭插的時間復雜度是o(n)
//頭插
void SeqListPushFront(SeqList *ps,int x)
{
assert(ps);
SeqListCreate(ps);
int end = ps->size - 1;
//從后往前挪動資料
while (end >= 0)
{
ps->arr[end + 1] = ps->arr[end];
end--;
}
//頭插資料
ps->arr[0] = x;
ps->size++;
}
順序表的尾插
其實順序表的尾插，時間復雜度o(1)
//尾插
void SeqListPushBack(SeqList *ps,int x)
{
assert(ps);
SeqListCreate(ps);
ps->arr[ps->size++] = x;
}
順序表的遍歷列印
遍歷順序表，o(n)的時間復雜度
//列印
void SeqListprint(SeqList * ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ",ps->arr[i]);
}
}
順序表的尾刪
這里要考慮的是需要判斷表中有沒有資料，如果沒有資料就不需要洗掉
//尾刪
void SeqListPopBack(SeqList *ps)
{
assert(ps);
assert(ps->size > 0);
ps->size--;
}
順序表的頭刪
將后一個資料覆寫掉前一個資料，最后- -size，因為需要挪動資料所以時間復雜度是o(n)
//頭刪
void SeqListPopFront(SeqList *ps)
{
assert(ps);
assert(ps->size > 0);
int begin = 0;
while (begin < ps->size)
{
ps->arr[begin] = ps->arr[begin + 1];
begin++;
}
ps->size--;
}
順序表的查找
找到回傳該位置的下標，O(N)時間復雜度
//查找
int SeqListFind(SeqList * ps, int x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
洗掉
洗掉指定pos位置的元素，可以挪動資料將其覆寫，從前往后的覆寫法，挪動資料時間復雜度O(N)
//洗掉
void SeqListErase(SeqList *ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
int begin = pos;
while (begin < ps->size)
{
ps->arr[begin] = ps->arr[begin + 1];
++begin;
}
ps->size--;
}
插入
將pos位置和pos后的資料整體往后一挪動，再將x插入到指定pos位置，注意選擇的位置不能超出順序表的大小
時間復雜度O(N)
void SeqListInsert(SeqList *ps, int pos, int x)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
SeqListCreate(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->arr[end + 1] = ps->arr[end];
end--;
}
ps->arr[pos] = x;
ps->size++;
}
修改
修改該位置的值
void SeqListmodif(SeqList *ps, int pos, int x)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
ps->arr[pos] = x;
}
順序表的問題及思考：
1、順序表的指定插入和洗掉都需要挪動資料，時間復雜度為O(N)
2、增容需要申請空間，拷貝資料，釋放就空間，會有不小的消耗，一定程度上也會影響效率，增容會存在空間浪費，開大了浪費，開小了又不夠
力扣題
27. 移除元素:
點我.
思路一：
不要使用額外的陣列空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入，找出值為val的位置挪動后面的資料覆寫掉val的值，
時間復雜度是0（N*N）,考慮最壞的情況如果陣列中的值全是val的話，每次找出一個值為val的時間復雜度是o(N)，挪動資料又是o(N)，整體就是O(N * N)
思路二：
開辟一個空間足夠大的陣列，遍歷一遍找出原陣列將值不為val的，拷貝到新陣列中去，時間復雜度是O(N)，空間復雜度是O(N)，空間換時間
思路三：
雙指標解法，在原陣列的基礎上創建一個虛擬陣列，src和dest都從0開始，src去找值不為val的，找到后將src位置的值覆寫掉dest位置的值，他們都自增，如果src的值等于val，src就繼續找，最后回傳dest，時間復雜度是O(N)，空間復雜度是O(1)，
int removeElement(int* nums, int numsSize, int val){
if(numsSize == 0)
return 0;
int dest = 0;
int src = 0;
while(src < numsSize)
{
if(nums[src] != val)
{
nums[dest++] = nums[src++];
}
else
{
src++;
}
}
return dest;
}
26. 洗掉有序陣列中的重復項:
點我.
解題思路：
src和next一前一后，如果src的值不等于dst，就將src的值覆寫在dst的位置上，dst++，next的位置賦值給src，next++找下一個數，在回來判斷next位置的值是否與src相等，如果相等繼續執行，直到條件為假回圈終止
時間復雜度是O(N)，空間復雜度是O(1)
考慮這種情況，如果next已經 > numsize了，回圈終止，但是末尾的那個元素還沒有拷貝過來
int removeDuplicates(int* nums, int numsSize){
if(numsSize == 0)
{
return 0;
}
int cur = 0;
int next = 1;
int count = 0;
int dest = 0;
while(next < numsSize)
{
//cur和next將重復的值給過濾掉，只留下一個值給dst
if(nums[cur] != nums[next])
{
nums[dest++] = nums[cur];
cur = next;
++next;
}
else
{
++next;
}
}
//防止回圈終止后，最后一個資料丟失
if(cur < numsSize)
nums[dest++] = nums[cur];
return dest;
}
27. 陣列形式的整數加法:
- 點我.
.
測驗用例
解題思路：
計算出val的十進制位數，取val或陣列長度大的那一個作為新陣列的大小(存在進位問題)，繼續將val的每一位取下來對應的個位、十位、百位…看成與陣列元素的一種關聯關系，通過不斷拆分相加它們之間的和，和值大于10就考慮進位，小于10不進位，最后將這兩個值相加得到的和存放到對應的位置上，由于是從低位開始計算的，存在陣列的順序也是倒過來的，所以再最后需要整體一逆轉
int* addToArrayForm(int* A, int numSize, int k, int* returnSize){
int ksize = 0;
int num = k;
//記錄num的十進制位數
while(num)
{
num /= 10;
++ksize;
}
int reti = 0;
//擴容一位提供進位
int len = numSize > ksize ? numSize + 1 : ksize + 1;
int Ai = numSize - 1;
int ki = 0;
int next = 0;//進位
int *retArr = (int *)malloc(sizeof(int) * len);
while(Ai >= 0 || ki < ksize)
{
int aval = 0;
if(Ai >= 0)
aval = A[Ai--];
int kval = k % 10;
k /= 10;
ki++;
int ret = kval + aval + next;
if(ret >= 10)
{
next = 1;
ret -= 10;
}
else
{
next = 0;
}
retArr[reti++] = ret;
}
//存放最高位
if(next == 1)
{
retArr[reti++] = 1;
}
//逆置陣列
int begin = 0;
int end = reti - 1;
while(begin < end)
{
int tmp = retArr[begin];
retArr[begin] = retArr[end];
retArr[end] = tmp;
begin++;
end--;
}
*returnSize = reti;
return retArr;
}
旋轉陣列:
點我.
解題思路：
將陣列整體旋轉一次，以k為劃分左旋轉0 ~ k - 1這個區間，
右旋轉k ~ numsize - 1區間，整體就是旋轉k次的陣列，有點類似于左旋轉字串，時間復雜度是O(N + N)，還是O(N）
//逆置陣列
void reverse(int* nums1,int *nums2)
{
while(nums1 < nums2)
{
int tmp = *nums1;
*nums1 = *nums2;
*nums2 = tmp;
++nums1;
--nums2;
}
}
void rotate(int* nums, int numsSize, int k){
if(k >= numsSize)
k %= numsSize;
//整體旋轉
reverse(nums, nums + numsSize - 1);
//左旋轉
reverse(nums,nums + k - 1);
//右旋轉
reverse(nums + k,nums + numsSize - 1);
}
合并陣列陣列:
點我.
解題思路：
從后往前處理，因為兩個陣列都是有序的，從nums1和nums2中先將最大的數挑出來插入到目標陣列，這樣目標陣列的后index就已經可以確定是有序的了，已經是最大了，最后判斷哪個陣列還剩元素就繼續插入在目標陣列中
時間復雜度是O(N)
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int i = m - 1, j = n - 1, index = m + n - 1;
while(i >= 0 && j >= 0)
nums1[index--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
while(j >= 0)
nums1[index--] = nums2[j--];
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/306296.html
標籤：其他