題目

對長度為n的順序表L，編寫一個時間復雜度為O(n)、空間復雜度為O(1)的算法
該算法刪除線性表中所有值為X的數據元素。

分析

O(n) -> 掃描一次順序表
O(1) -> 申請常數個輔助空間
1、找
2、刪除（移動）

算法思想

1、K的作用是記錄順序表中X的個數
最終的鏈表長度：L.length = L.length - K
掃描順序表，記錄其中X的個數(K)，將其中不為X的元素向前移K個單位
2、遍歷順序表，保留下不是X的值（刪除所有的X）

代碼

1、核心代碼段：能體現算法思想的核心代碼段
2、框架（大同小異）

框架代碼段包括：
定義參數，括號匹配{}

void del_x(Sqlist* L,int x) {int i = 0;int k = 0;	//標記遍歷到的x的個數while(i < L->length){if(L->data[i] == x)k++;elseL->data[i - k] = L->data[i];	//向前移動K個單位i++;}L->length = L->length - k;	//這句是什么意思？中斷了？}

void del_x(Sqlist* L,int x){int i = 0;int k = 0;for(i = 0 ;i < L -> length ; i++){if(L->data[i] != x){L->data[k] = L->data[i];k++;}	}L->length = k;	//這句是什么意思？中斷了？
}

完整運行代碼如下：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MaxSize 10//定義最大長度
int InitArr[10] = { 1,2,2,3,4,2,5,2,6,7 };typedef struct {int data[MaxSize];//用靜態的數據存放數據元素int length;//順序表當前長度
}Sqlist;//順序表的類型定義void print(Sqlist* L)
{for (int i = 0;i < L->length;i++){printf("%d ", L->data[i]);}
}
//初始化一個順序表
void InitList(Sqlist* L)
{for (int i = 0;i < MaxSize;i++){L->data[i] = InitArr[i];//將所有數據元素設置為默認初始值}L->length = 10;//順序表初始長度為0
}
//對長度為n的順序表L，編寫一個時間復雜度為O(n)，空間復雜度為O(1)的算法，
//該算法刪除線性表中的所有值為x的數據元素//算法思路
void del_x(Sqlist* L,int x){int i = 0;int k = 0;for(i = 0 ;i < L -> length ; i++){if(L->data[i] != x){L->data[k] = L->data[i];k++;}	}L->length = k;
}
int main() 
{Sqlist L;InitList(&L);//初始化一個順序表：1,2,2,3,4,2,5,2,6,7printf("初始順序表為：");print(&L);printf("請輸入一個值x進行刪除操作：");int x = 0;scanf("%d", &x);printf("\n");del_x(&L,x);printf("刪除所有值為x的元素后順序表為:");print(&L);return 0;
}

---

day04與day01作對比