資料結構之順序表+常見面試題

資料結構分為兩種

1、物理結構（記憶體中如何存盤的）

2、邏輯結構（是我們想象出來的）

線性表（邏輯上連續）包括順序表、鏈表、堆疊、佇列，

順序表在物理上和邏輯上都是連續的（其實就是陣列）

靜態順序表的基本結構

struct static_Array_list
{
	int arr[10];
	int size;
};

存在的問題

1、資料型別無法改變

2、陣列大小無法改變

所以引入動態順序表，

動態順序表的基本結構

typedef int SLDataType;
typedef struct dynamic_Array_list
{
	SLDataType *arr;//定義陣列指標
	size_t size;//有效資料個數
	size_t capacity//容量
}ArrayList;

缺點

1、順序表在尾插尾刪上很方便，但是在頭(中間)插頭(中間)刪上復雜度為O(n)

2、空間利用率不高，增容會有一定空間浪費（批量增容）

優點

1、記憶體連續，隨機訪問

2、快取命中率高（因為記憶體連續，預加載時把一段資料加載到快取中，如果記憶體不連續，則會進行多次加載來獲取所需要的的資料）

順序表的基本介面

// 基本增刪查改介面
// 順序表初始化
void ArrayListInit(ArrayList* psl, size_t capacity);
// 順序表銷毀
void ArrayListDestory(ArrayList* psl);
// 順序表列印
void ArrayListPrint(ArrayList* psl);
// 檢查空間，如果滿了，進行增容
void CheckCapacity(ArrayList* psl);
// 順序表尾插
void ArrayListPushBack(ArrayList* psl, SLDataType x);
// 順序表尾刪
void ArrayListPopBack(ArrayList* psl);
// 順序表頭插
void ArrayListPushFront(ArrayList* psl, SLDataType x);
// 順序表頭刪
void ArrayListPopFront(ArrayList* psl);
// 順序表查找
int ArrayListFind(ArrayList* psl, SLDataType x);
// 順序表在pos位置插入x
void ArrayListInsert(ArrayList* psl, size_t pos, SLDataType x);
// 順序表洗掉pos位置的值
void ArrayListErase(ArrayList* psl, size_t pos);

總的來說順序表比較簡單，因為底層是可以動態開辟空間的陣列，基本介面的實作網上已經有很多相關的內容，不在贅述，

順序表常見的面試題

1. 原地移除陣列中所有的元素val，要求時間復雜度為O(N)，空間復雜度為O(1)，

//為了達到O(1)的空間復雜度（不能額外開辟陣列長度大小的空間）
//時間復雜度O(N)（只能遍歷一次陣列）
//所以采用雙指標的方法，用不重復的元素替換掉重復的元素
//注意各種判斷條件
int removeElement(int* nums, int numsSize, int val){
    int head = 0;
    int end = numsSize-1;
    while(head<=end)//加=號的目的是防止最后雙指標相遇，相遇點正好是要洗掉的數值
    {
        while(head<numsSize&&nums[head]!=val)
        {
            head++;
        }
        while(end>=0&&nums[end]==val)
        {
            end--;
        }
        if(head<end)
            {
                nums[head]=nums[end];
                head++;
                end--;
            }
    }
    return end+1;
}

2. 洗掉排序陣列中的重復項，

//給排序陣列元素去重
//同樣的，空間復雜度要求是O(1)
//還是利用雙指標的思想，從前往后替換
//注意陣列為空的情況
int removeDuplicates(int* nums, int numsSize){

    if(numsSize==0)
        return 0;
    int head1 = 0;
    int head2 = 1;
    while(head2<=numsSize-1)
    {
        while(head2<=numsSize-1&&nums[head1] == nums[head2])
        {
            head2++;
        }
        if(head2<=numsSize-1)
        {
            nums[++head1] = nums[head2];
        }
    }
    return head1+1;
}

3. 合并兩個有序陣列，

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){

    //開辟額外的空間
    int *tmp = (int*)malloc(sizeof(int)*(m+n));
    //三個索引
    int index1=0;
    int index2=0;
    int index=0;
    while(index1<m && index2<n)
    {
        if(nums1[index1]<nums2[index2])
        {
            tmp[index++]=nums1[index1];
            index1++;
        }
        else
        {
            tmp[index++]=nums2[index2];
            index2++;
        }
    }
//下面是將尾部的元素拷貝過來，可以優化，采用尾指標的方式
//自動判斷誰的尾部還有剩下的元素
    for(int i=index1;i<m;i++)
        tmp[index++]=nums1[i];
    for(int i=index2;i<n;i++)
        tmp[index++]=nums2[i];
//拷貝給nums1
    for(int i=0;i<index;i++)
        nums1[i]=tmp[i];
//整體來說時間復雜度O(2n+m),空間復雜度O(n+m)//可以優化
}

4.旋轉陣列，

//方法1.新建一個陣列
//該方法比較簡單，但空間復雜度高O(N)
void rotate(int* nums, int numsSize, int k){

    int* array_tmp = (int*)malloc(sizeof(int)*numsSize);
    k=k%numsSize;//值得注意的地方
    for(int i=0;i<k;i++)
    {
        array_tmp[i]=nums[numsSize-k+i];
    }
    for(int i = k;i<numsSize;i++)
    {
        array_tmp[i]=nums[i-k];
    }
    for(int i = 0;i<numsSize;i++)
    {
        nums[i] = array_tmp[i];
    }
}

//方法2.旋轉陣列
//時間復雜度O(N)，空間復雜度O(1)
void Reverse(int* nums, int numsSize)
{
    for(int i = 0; i < numsSize/2; i++)
    {
        int tmp = nums[i];
        nums[i] = nums[numsSize-i-1];
        nums[numsSize-i-1] = tmp;
    }
}
void rotate(int* nums, int numsSize, int k){

    k = k%numsSize;
    if(k!=0)//如果k==0，說明原來陣列的沒變
    {
        Reverse(nums,numsSize);
        Reverse(nums,k);
        Reverse(nums+k,numsSize-k);
    }
}

5. 陣列形式的整數加法，

//逐位相加，然后逆轉陣列
int* addToArrayForm(int* num, int numSize, int k, int* returnSize){

    *returnSize = 0;
    int* returnArray = (int*)calloc(fmax(10, numSize + 1),sizeof(int));
    while(k || numSize)
    {
        if(numSize)
        {
            returnArray[*returnSize] = returnArray[*returnSize] + num[numSize-1] + k%10;
            numSize--;
        }
        else
        {
            returnArray[*returnSize] = returnArray[*returnSize] + k%10;
        }
        if(returnArray[*returnSize] > 9)
        {
            returnArray[*returnSize] = returnArray[*returnSize]%10;
            returnArray[(*returnSize) + 1] = 1;
            if(!(k/10)&&!numSize)//防止最后一個數發生進位，資料的長度會增加
                (*returnSize)++;
        }
       
        k = k/10;
        (*returnSize)++;
    }
    for (int i = 0; i < (*returnSize) / 2; i++)
    {
        int tmp = returnArray[i];
        returnArray[i] = returnArray[(*returnSize) - 1 - i];
        returnArray[(*returnSize) - 1 - i] = tmp;
    }
    return returnArray;
}

總的來說順序表是非常基礎的一種資料結構，用處也非常廣泛，在后續的資料結構中也有很多衍生出來的結構是基于順序表的，與之相反的一種資料結構是鏈表，鏈表和順序表的特性恰恰相反，下篇文章共同學習線性表中的鏈表，