iOS數(shù)據(jù)結(jié)構(gòu)與算法面試題合集

1、不用中間變量,用兩種方法交換A和B的值

// 1.中間變量
void swap(int a, int b) {
   int temp = a;
   a = b;
   b = temp;
}

// 2.加法
void swap(int a, int b) {
   a = a + b;
   b = a - b;
   a = a - b;
}

// 3.異或（相同為0，不同為1. 可以理解為不進(jìn)位加法）
void swap(int a, int b) {
   a = a ^ b;
   b = a ^ b;
   a = a ^ b;
}

2、求最大公約數(shù)

/** 1.直接遍歷法 */
int maxCommonDivisor(int a, int b) {
    int max = 0;
    for (int i = 1; i <=b; i++) {
        if (a % i == 0 && b % i == 0) {
            max = i;
        }
    }
    return max;
}
/** 2.輾轉(zhuǎn)相除法 */
int maxCommonDivisor(int a, int b) {
    int r;
    while(a % b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return b;
}

// 擴(kuò)展：最小公倍數(shù) = (a * b)/最大公約數(shù)

3、模擬棧操作

• 棧是一種數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)：先進(jìn)后出
• 練習(xí)：使用全局變量模擬棧的操作

#include <stdio.h>
#include <stdbool.h>
#include <assert.h>

//保護(hù)全局變量：在全局變量前加static后，這個(gè)全局變量就只能在本文件中使用
static int data[1024];//棧最多能保存1024個(gè)數(shù)據(jù)
static int count = 0;//目前已經(jīng)放了多少個(gè)數(shù)(相當(dāng)于棧頂位置)

//數(shù)據(jù)入棧 push
void push(int x){
    assert(!full());//防止數(shù)組越界
    data[count++] = x;
}
//數(shù)據(jù)出棧 pop
int pop(){
    assert(!empty());
    return data[--count];
}
//查看棧頂元素 top
int top(){
    assert(!empty());
    return data[count-1];
}

//查詢棧滿 full
bool full() {
    if(count >= 1024) {
        return 1;
    }
     return 0; 
}

//查詢?？?empty
bool empty() {
    if(count <= 0) {
        return 1;
    }
    return 0;
}

int main(){
    //入棧
    for (int i = 1; i <= 10; i++) {
        push(i);
    }

    //出棧
    while(!empty()){
        printf("%d ", top()); //棧頂元素
        pop(); //出棧
    }
    printf("\n");

    return 0;
}

4、排序算法

選擇排序、冒泡排序、插入排序三種排序算法可以總結(jié)為如下：

都將數(shù)組分為已排序部分和未排序部分。

1.選擇排序?qū)⒁雅判虿糠侄x在左端，然后選擇未排序部分的最小元素和未排序部分的第一個(gè)元素交換。
2.冒泡排序?qū)⒁雅判虿糠侄x在右端，在遍歷未排序部分的過程執(zhí)行交換，將最大元素交換到最右端。
3.插入排序?qū)⒁雅判虿糠侄x在左端，將未排序部分元的第一個(gè)元素插入到已排序部分合適的位置。

4.1、選擇排序

• 【選擇排序】：最值出現(xiàn)在起始端
• 第1趟：在n個(gè)數(shù)中找到最小(大)數(shù)與第一個(gè)數(shù)交換位置
• 第2趟：在剩下n-1個(gè)數(shù)中找到最小(大)數(shù)與第二個(gè)數(shù)交換位置
• 重復(fù)這樣的操作...依次與第三個(gè)、第四個(gè)...數(shù)交換位置

• 第n-1趟，最終可實(shí)現(xiàn)數(shù)據(jù)的升序（降序）排列。

  void selectSort(int *arr, int length) {
  for (int i = 0; i < length - 1; i++) { //趟數(shù)
      for (int j = i + 1; j < length; j++) { //比較次數(shù)
          if (arr[i] > arr[j]) {
              int temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
          }
      }
  }
  }

  4.2、冒泡排序

• 【冒泡排序】：相鄰元素兩兩比較，比較完一趟，最值出現(xiàn)在末尾
• 第1趟：依次比較相鄰的兩個(gè)數(shù)，不斷交換（小數(shù)放前，大數(shù)放后）逐個(gè)推進(jìn)，最值最后出現(xiàn)在第n個(gè)元素位置
• 第2趟：依次比較相鄰的兩個(gè)數(shù)，不斷交換（小數(shù)放前，大數(shù)放后）逐個(gè)推進(jìn)，最值最后出現(xiàn)在第n-1個(gè)元素位置
• …… ……
• 第n-1趟：依次比較相鄰的兩個(gè)數(shù)，不斷交換（小數(shù)放前，大數(shù)放后）逐個(gè)推進(jìn)，最值最后出現(xiàn)在第2個(gè)元素位置

  void bublleSort(int *arr, int length) {
  for(int i = 0; i < length - 1; i++) { //趟數(shù)
      for(int j = 0; j < length - i - 1; j++) { //比較次數(shù)
          if(arr[j] > arr[j+1]) {
              int temp = arr[j];
              arr[j] = arr[j+1];
              arr[j+1] = temp;
          }
      } 
  }
  }

  5、折半查找（二分查找）

折半查找：優(yōu)化查找時(shí)間（不用遍歷全部數(shù)據(jù)）
折半查找的原理：

• 1> 數(shù)組必須是有序的
• 2> 必須已知min和max（知道范圍）
• 3> 動(dòng)態(tài)計(jì)算mid的值，取出mid對(duì)應(yīng)的值進(jìn)行比較
• 4> 如果mid對(duì)應(yīng)的值大于要查找的值，那么max要變小為mid-1
• 5> 如果mid對(duì)應(yīng)的值小于要查找的值，那么min要變大為mid+1

// 已知一個(gè)有序數(shù)組, 和一個(gè)key, 要求從數(shù)組中找到key對(duì)應(yīng)的索引位置

int findKey(int *arr, int length, int key) {
    int min = 0, max = length - 1, mid;
    while (min <= max) {
        mid = (min + max) / 2; //計(jì)算中間值
        if (key > arr[mid]) {
            min = mid + 1;
        } else if (key < arr[mid]) {
            max = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

6、集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖形結(jié)構(gòu)

• 1.1、集合結(jié)構(gòu) 說白了就是一個(gè)集合，就是一個(gè)圓圈中有很多個(gè)元素，元素與元素之間沒有任何關(guān)系 這個(gè)很簡(jiǎn)單
• 1.2、線性結(jié)構(gòu) 說白了就是一個(gè)條線上站著很多個(gè)人。 這條線不一定是直的。也可以是彎的。也可以是值的 相當(dāng)于一條線被分成了好幾段的樣子 （發(fā)揮你的想象力）。 線性結(jié)構(gòu)是一對(duì)一的關(guān)系
• 1.3、樹形結(jié)構(gòu) 說白了 做開發(fā)的肯定或多或少的知道xml 解析 樹形結(jié)構(gòu)跟他非常類似。也可以想象成一個(gè)金字塔。樹形結(jié)構(gòu)是一對(duì)多的關(guān)系
• 1.4、圖形結(jié)構(gòu) 這個(gè)就比較復(fù)雜了。他呢 無窮。無邊 無向（沒有方向）圖形機(jī)構(gòu) 你可以理解為多對(duì)多 類似于我們?nèi)说慕患P(guān)系

7、數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)

數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)一般常用的有兩種 順序存儲(chǔ)結(jié)構(gòu) 和 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

• 2.1 順序存儲(chǔ)結(jié)構(gòu)

發(fā)揮想象力啊。 舉個(gè)列子。數(shù)組。1-2-3-4-5-6-7-8-9-10。這個(gè)就是一個(gè)順序存儲(chǔ)結(jié)構(gòu) ，存儲(chǔ)是按順序的 舉例說明啊。 棧。做開發(fā)的都熟悉。棧是先進(jìn)后出 ，后進(jìn)先出的形式 對(duì)不對(duì) ？！他的你可以這樣理解

hello world 在棧里面從棧底到棧頂?shù)倪壿嬕来螢?h-e-l-l-o-w-o-r-l-d 這就是順序存儲(chǔ) 再比如 隊(duì)列 ，隊(duì)列是先進(jìn)先出的對(duì)吧，從頭到尾 h-e-l-l-o-w-o-r-l-d 就是這樣排對(duì)的

• 2.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

再次發(fā)揮想象力 這個(gè)稍微復(fù)雜一點(diǎn) 這個(gè)圖片我一直弄好 ，回頭找美工問問，再貼上 例如 還是一個(gè)數(shù)組

1-2-3-4-5-6-7-8-9-10 鏈?zhǔn)酱鎯?chǔ)就不一樣了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地址)-6(地址)-10(地址)。每個(gè)數(shù)字后面跟著一個(gè)地址 而且存儲(chǔ)形式不再是順序 ，也就說順序亂了，1（地址） 1后面跟著的這個(gè)地址指向的是2，2后面的地址指向的是3，3后面的地址指向是誰你應(yīng)該清楚了吧。他執(zhí)行的時(shí)候是 1(地址)-2(地址)-3(地址)-4(地址)-5(地址)-6(地址)-7(地址)-8(地址)-9(地址)-10(地址)，但是存儲(chǔ)的時(shí)候就是完全隨機(jī)的。明白了？！

8、單向鏈表\雙向鏈表\循環(huán)鏈表

還是舉例子。理解最重要。不要去死記硬背 哪些什么。定義啊。邏輯啊。理解才是最重要滴

• 3.1 單向鏈表

A->B->C->D->E->F->G->H. 這就是單向鏈表 H 是頭 A 是尾 像一個(gè)只有一個(gè)頭的火車一樣 只能一個(gè)頭拉著跑

• 3.2 雙向鏈表

數(shù)組和鏈表區(qū)別：
數(shù)組：數(shù)組元素在內(nèi)存上連續(xù)存放，可以通過下標(biāo)查找元素；插入、刪除需要移動(dòng)大量元素，比較適用于元素很少變化的情況
鏈表：鏈表中的元素在內(nèi)存中不是順序存儲(chǔ)的，查找慢，插入、刪除只需要對(duì)元素指針重新賦值，效率高

• 3.3 循環(huán)鏈表

循環(huán)鏈表是與單向鏈表一樣，是一種鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)，所不同的是，循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的指針是指向該循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)或者表頭結(jié)點(diǎn)，從而構(gòu)成一個(gè)環(huán)形的鏈。發(fā)揮想象力 A->B->C->D->E->F->G->H->A. 繞成一個(gè)圈。就像蛇吃自己的這就是循環(huán) 不需要去死記硬背哪些理論知識(shí)。

9、二叉樹／平衡二叉樹

• 4.1 什么是二叉樹

樹形結(jié)構(gòu)下,兩個(gè)節(jié)點(diǎn)以內(nèi) 都稱之為二叉樹 不存在大于2 的節(jié)點(diǎn) 分為左子樹 右子樹 有順序 不能顛倒 ，懵逼了吧，你肯定會(huì)想這是什么玩意，什么左子樹右子樹 ，都什么跟什么鬼？ 現(xiàn)在我以普通話再講一遍，你把二叉樹看成一個(gè)人 ，人的頭呢就是樹的根 ，左子樹就是左手，右子樹就是右手，左右手可以都沒有（殘疾嘛，聲明一下，絕非歧視殘疾朋友，勿怪，勿怪就是舉個(gè)例子，i am very sorry） , 左右手呢可以有一個(gè)，就是不能顛倒。這樣講應(yīng)該明白了吧

二叉樹有五種表現(xiàn)形式

1.空的樹（沒有節(jié)點(diǎn)）可以理解為什么都沒 像空氣一樣
2.只有根節(jié)點(diǎn)。 （理解一個(gè)人只有一個(gè)頭 其他的什么都沒，說的有點(diǎn)恐怖）
3.只有左子樹 （一個(gè)頭 一個(gè)左手 感覺越來越寫不下去了）
4.只有右子樹
5.左右子樹都有

二叉樹可以轉(zhuǎn)換成森林 樹也可以轉(zhuǎn)換成二叉樹。這里就不介紹了 你做項(xiàng)目絕對(duì)用不到
數(shù)據(jù)結(jié)構(gòu)大致介紹這么多吧。理解為主, 別死記，死記沒什么用

想要了解和閱讀更多的iOS面試題，可以添加QQ群：763164022 ！群內(nèi)有已經(jīng)整理好的面試題以及答案文檔，同時(shí)，也希望大家一起多多交流技術(shù)，行情等等！歡迎你的加入~~