26数据结构-顺序表

📌有序顺序表的合并

#define MAX_SIZE 20
struct SeqList
{int data[MAX_SIZE];int length;
};
void mergeArray(SeqList &L1,SeqList &L2,SeqList &L)
{int i=0,j =0;while(i<L1.length && j<L2.length){if(L1.data[i]<L2.data[j])L.data[length++] = L1.length[i++];elseL.data[length++] = L2.length[j++];}while(i<L1.length){L.data[length++] = L1.length[i++];}while(i<L2.length){L.data[length++] = L2.length[j++];}
}

📌删除有序顺序表重复元素

void deleteRepeatELement(SeqList &L)
{int slow =0,fast=1;while(fast<L.length){if( L.data[slow] == L.data[fast]){fast++;}else if( L.data[slow] != L.data[fast]){L.data[++slow] =L.data[fast++];}}L.length =slow+1;
}

通过快慢指针的追赶，将不重复的元素 "前移"，覆盖掉重复元素，最终实现原地去重，时间复杂度为 O (n)，空间复杂度为 O (1)。

📌编写算法，对n个关键字取整数值的记录序列进⾏整理，以使得所有关键字为负数的记录排在关键字为⾮负数的记录之前。

void reOrderArray(SeqList &L)
{int i=0,j=0;while(j<L.length){if(L.data[j]<0){if(i!=j){int tmp = L.data[i];L.data[i] = L.data[j];L.data[j] = tmp;}i++;j++;}elsej++;}
}

📌设有⼀组初始记录关键字序列（K1,K2,…,Kn），要求设计⼀个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均⼩于Ki，右半部分的每个关键字均⼤于Ki。

//⽅法⼀：双指针
void spliceArrayother(SeqList &L)
{int left = 0;           //左半部分的索引。int right = L.length -1; //右半部分的索引while( left <= right ){while(L.data[left] < key)left ++;while(L.data[right] > key)right --;//如果left <=right 交换if(left <=right){int tmp = L.data[left];L.data[left] =L.data[right];L.data[right] = tmp;left ++;right--;}}
}

//⽅法⼆：类似快排
void spliceArray(SeqList &L)
{int key;int i = 0,j=0;while(j < L.length){if(L.data[j]> key){if(i != j){int tmp = L.data[i];L.data[i] = L.data[j];L.data[j] = tmp;}i++;j++;}j++;}
}