順序表
靜態(tài)分配內存及初始化
#include<stdio.h>
#include<stdlib.h>
#define Maxsize 100
//靜態(tài)
typedef struct sqlist {
int data[Maxsize];
int length;
}SqList;
void InitList(SqList& L) {
L.length = 0; //順序表的初始長度為0
}
動態(tài)分配內存及初始化
//動態(tài)
typedef struct {
int* data; //指示動態(tài)分配數組的指針
int MaxSize; //順序表的最大容量
int length; //順序表的當前長度
}SeqList;
void InitList(SeqList& L) {
L.data = (int*)malloc(Maxsize * sizeof(int));
L.length = 0;
L.MaxSize = Maxsize;
}
01 對順序表L進行遍歷并輸出每個數據元素的數據值
//對順序表L進行遍歷并輸出每個數據元素的數據值
void print(SqList &L){
for(int i=0;i<L.length;i++){
printf("%d",L.data[i]);
}
}
02 假設有一個順序表L，其存儲的所有數據元素均為不重復的正數，查找 L 中值為 e 的數據元素，若找到則返回其下標，若找不到則返回-1。
int search_e(SqList L, int e) {
for (int i = 0; i < L.length; i++) {
if (e == L.data[i]) {
return i;
}
}
return -1;
}
03 假設有一個順序表 L，其存儲的所有數據元素均為正數，查找 L 中第 i 個數據元素并返回其值。
//假設有一個順序表 L，其存儲的所有數據元素均為正數，查找 L 中第 i 個數據元素并返回其值。
int Get_i(SqList L, int i) {
if (i >= 1 && i <= L.length) {
return L.data[i - 1];
}
return -1;//越界
}
①注意越界的判斷
04 設計一個高效算法，將順序表 L 的所有元素逆置，要求算法的空間復雜度為 O(1) 。
- 逆置：實現(xiàn)頭和尾的轉換
- 空間復雜度O(1)：不能去定義數組啥的，只能用常量級別解決。
- 4個元素，交換兩次，5個元素也交換兩次，交換次數規(guī)律是length/2向下取整，而計算機中自動向下取整，這里大家可以自己去試著模擬一下，i < L.length/2，如果取等號，偶數個元素的順序表，中間的兩個元素會重新?lián)Q回來（i多走了一步）。
- 逆置時用下標找規(guī)律。
//設計一個高效算法，將順序表 L 的所有元素逆置，要求算法的空間復雜度為 O(1)
void Reverse(SqList& L) {
int temp;
for (int i = 0; i < L.length/2; i++) {
temp = L.data[i];
L.data[i] = L.data[L.length - i - 1];
L.data[L.length - i - 1] = temp;
}
}
05 在順序表 L 的第 i 個位置插入新元素 e。若 i 的輸入不合法，則返回 false， 表示插入失?。环駝t，將第 i 個元素及其后的所有元依次往后移動一個位置， 騰出一個空位置插入新元素 e，順序表長度增加 1，插入成功，返回 true。
- 注意插入的位置可以是1~length+1；
- 順序表存滿了也不能存了
- 從后往前的移動元素
- 判斷條件
//在順序表 L 的第 i 個位置插入新元素 e。若 i 的輸入不合法，則返回 false，表示插入失?。环駝t，將第 i 個元素及
//其后的所有元素依次往后移動一個位置，騰出一個空位置插入新元素 e，順序表長度增加 1，插入成功，返回 true。
bool Insert(SqList &L, int i, int e) {
if (i<1 || i>L.length+1) {
return false;
}
if (L.length == Maxsize) {
return false;
}
for (int j = L.length; j > i-1; j--) {
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e;
L.length++;
return true;
}
06 已知一個順序表 L，其中的元素遞增有序排列，設計一個算法在插入元素 x(x 為 int 型)后保持該順序表仍然遞增有序排列，假設c插入操作肯定成功，插入成功后返回插入元素所在位置。
分析
-
先找出位置
-
插入元素
-
注意：要返回插入元素位置，i的定義要放在for循環(huán)外
-
舉例（從后往前移動元素，第一行為順序表，第二行為下標）
①假設x=5，即i=3，初始j=4，判斷移動一次，故判斷條件為j>i或者j>=i+1
②假設x=3，即i=2，初始i=4，判斷移動兩次，第一次移動條件j=4,i=2，第二次移動j=3,i=2，故判斷條件為j>i或者j>=i+1
綜上，判斷條件為j>i或者j>=i+1
int Insert(SqList &L,int x){
int i;//定義變量 i 記錄元素 x 插入位置
for(i=0; i<L.length; i++){
if(L.data[i]>x){
break;
}
}
//也可以換成for(i=0; i<L.length,L.data[i]<=x; i++);
//自己模擬j的條件(易錯)
for(j=L.length;j>i;j--){
L.data[j]=L.data[j-1];
}
L.data[i]=x;
L.length++;
return i;
}
07 刪除順序表 L 中第 i 個位置的元素，若 i 的輸入不合法，則返回 false； 否則將被刪元素賦給引用變量 e，并將第 i+1 個元素及其后的所有元素依次往前 移動一個位置，返回 true。
分析
-
注意i是位置，和下標不一樣
-
被刪元素賦給引用變量 e
-
舉例
位置 1 2 3 4 5
元素 2 5 1 3 4
下標 0 1 2 3 4
刪除第2個位置，i=2，L.length=4，下標為1，要移動兩次(j=2,j=3)，判斷條件為j<L.length -
最后別忘了順序表長度改變
bool ListDelete(SqList &L, int i, int &e){
if(i<1||i>L.length){
return false;
}
e=L.data[i-1];
for(int j=i; j<L.length; j++){
//后面賦值給前面
L.data[j-1]=L.data[j];
}
L.length--;
return ture;
}
08 從順序表 L 中刪除最小值元素并由函數返回被刪元素的值。(假設順序表中數據元素全為正值且最小值唯一)
分析
- 先找到最小值，在進行刪除
- 要判斷不合理情況，如空的順序表
- 首先定義最小值為下標為0的元素，記錄其位置pos
由于最后需要返回被刪元素的值，因此需要有個變量對最小值進行保存，然后刪除操作過程中，最小值被刪除，此后如果沒有保存最小元素的變量，則找不到最小值。
int Delete_min(SqList &L)[
if(L.length==0){
return 0;
}
//查找最小值
int min=L.data[0],pos=0;
for(int i=1;i<L.length;i++){
if(L.data[i]<min){
min=L.data[i];
pos=i;
}
}
//刪除操作,首先定義
//j<L.length-1可以自己模擬出，假設長度為五，假設最小值時，i=pos=3，另j=i，說明只需要移動一次即可，判斷條件
for(int j=pos; j<L.length-1;j--){
L.data[j]=L.data[j+1];
}
//減少長度
L.length--;
return min;
]
09 對長度為 n 的順序表 L，編寫一個時間復雜度為 O(n)、空間復雜度為 O(1) 的算法，該算法刪除順序表中所有值為 x 的數據元素。
- x可能不止一個，因此后面元素前移的數量需要改變
- 定義一個變量k用來記錄目前已經刪除幾個元素,k=1表示后面的元素需要前移1個
- 元素要保留，需要交換，元素不保留，不需要交換，先本次交換，然后在k再加1.
法一：
void Delete_all_x(SqList &L,int x){
int k=0;
for(int i=0;i<L.length;i++){
if(L.data[i]==x){
//應該刪除
k++;
}
else{
//重點
L.data[i-k]=L.data[i];
}
}
L.length=L.length-k;
}
法二：
思路：將順序表需要保存的元素理解為排隊，直接用一個變量記錄排隊位置，
void Delete_all_x(SqList &L,int x){
int k=0;
for(int i=0; i<L.length; i++){
if(L.data[i]!=x){
//需要保留
L.data[k]=L.data[i];
k++;
}
}
//不是k+1，因為排隊結束會執(zhí)行k++的操作
L.length = k;
}
改成while循環(huán)也類似：
void Delete_all_x(SqList &L,int x){
int k=0;
int i=0;
while(i<L.length){
if(L.data[i]!=x){
k++;
}
i++;
}
//不是k+1，因為排隊結束會執(zhí)行k++的操作
L.length = k;
}
10 從順序表中刪除其值在給定值 s 與 t 之間（包含 s 和 t，要求 s<t）的所有元素，若 s 或 t 不合理或順序表為空，則返回 false，若執(zhí)行成功則返回 true。
- 和上一題一樣，有兩種實現(xiàn)方式
法一：文章來源：http://www.zghlxwxcb.cn/news/detail-684382.html
bool Del(SqList &L,int s,int t){
if(s>=t||L.length==0) //若 s 或 t 輸入不合法或順序表為空，則返回 false
return false;
int k=0; //k 用來記錄要刪除元素的數量，初始時為 0
for(int i=0;i<L.length;i++){ //遍歷順序表 L
if(L.data[i]>=s&& L.data[i]<=t) //若元素符合刪除條件則 k 加一
k++;
}
else{ //若元素需保留則前移 k 個位置
L.data[i-k]= L.data[i];
}
L.length= L.length-k; //更新順序表長度
return true; //執(zhí)行結束返回 true
}
法二文章來源地址http://www.zghlxwxcb.cn/news/detail-684382.html
bool Del(SqList &L,int s,int t){
if(s>=t||L.length==0) //若 s 或 t 輸入不合法或順序表為空，則返回 false
return false;
int j=0; //j 用來記錄保留元素的排隊位置
for(int i=0;i<L.length;i++){ //遍歷順序表 L
if(L.data[i]<s||L.data[i]>t){ //判斷此次遍歷到的元素是否為保留元素
L.data[j]=L.data[i]; //是保留元素則過去排隊
j++; //新元素排隊后需更新排隊位置
}
}
L.length= j; //更新順序表長度
return true; //執(zhí)行結束返回 true
}
11 從有序順序表中刪除所有其值重復的元素，使表中所有元素的值均不同。
- 本題目是有序順序表，這個算法和前面兩個有所區(qū)別，在于從第二個元素開始，每次和前一個元素比較；
- 之前是從第一個元素開始，所以記錄排隊位置是0，這次是第二個元素開始（第一個元素肯定不重復，不需要交換），因此我們可以記錄排隊位置變量初始設置為1，然后根據這個進行后續(xù)代碼的改動，還是那句話元素要保留，需要交換，最后注意一下順序表長度即可。
void Del_Same(SqList &L){
int j=1; // j 用來記錄保留元素的排隊位置
for(int i=1;i<L.length;i++){ //遍歷順序表 L
if(L.data[i]!=L.data[j-1]){ //判斷此次遍歷到的元素是否為保留元素
L.data[j]=L.data[i]; //是保留元素則過去排隊
j++; //新元素排隊后需更新排隊位置
}
}
L.length=j; //更新順序表長度
}
12 從有序順序表中刪除其值在給定值 s 與 t 之間(包含 s 和 t，要求 s<t)的所有元素，若 s 或 t 不合理或順序表為空，則返回 false，若執(zhí)行成功則返回 true。
- 這題目的思路是定義兩個變量分別去待刪元素的起始位置和結束位置，這里需要注意的是左邊是小于s，這樣最后一次j就來到了待刪元素處，右邊是小于等于，這樣的話最后一次i來到了待刪元素的后一個位置。
bool Del_s_t(SqList &L,int s,int t){
if(s>=t||L.length==0){ //若 s 或 t 輸入不合法或順序表為空則返回 false
return false;
}
int i,j; //定義兩個變量 i 和 j 負責記錄待刪元素的起始位置和結束位置
for(j=0;j<L.length&&L.data[j]<s;j++); //尋找待刪元素起始位置
if(j==L.length){ //若順序表中所有元素都比 s 小則沒有要刪元素
return false;
}
for(i=j;i<L.length&&L.data[i]<=t;i++); //尋找待刪元素的結束位置
for(;i<L.length;i++,j++){ //將結束位置后的保留元素前移至起始位置
L.data[j]=L.data[i];
}
L.length=j; //更新順序表長度
return true; //執(zhí)行結束則返回 true
}
13 將兩個有序順序表 A 和 B 合并為一個新的有序順序表 C，若合并成功則返回 true，合并失敗則返回 false。
- 首先判斷一下是否有足夠空間進行合并，然后需要三個遍歷指針進行遍歷，最后記得更新C表表長
bool Merge(SeqList A, SeqList B, SeqList& C) {
if (A.length + B.length > C.Maxsize) //判斷 C 存儲空間是否能容納 A 和 B
return false;
int i = 0, j = 0, k = 0; //定義三個遍歷指針，分別遍歷 ABC
while (i < A.length && j < B.length) { //只有 A 和 B 都沒遍歷完才可以繼續(xù)循環(huán)
if (A.data[i] <= B.data[j]) { //若 A 表中值更小則 A 表中遍歷元素賦值給 C 表
C.data[k] = A.data[i];
k++; //更新 C 表元素插入位置
i++; //更新 A 表遍歷位置
}
else { //若 B 表中值更小則 B 表中遍歷元素賦值給 C 表
C.data[k] = B.data[j];
k++; //更新 C 表元素插入位置
j++; //更新 B 表遍歷位置
}
}
while (i < A.length) { //若循環(huán)結束后 A 還有未遍歷元素則順序賦值給 C
C.data[k] = A.data[i];
k++;
i++;
}
while (j < B.length) { //若循環(huán)結束后 B 還有未遍歷元素則順序賦值給 C
C.data[k] = B.data[j];
k++;
j++;
}
C.length = k; //更新 C 表長度
return true; //執(zhí)行結束返回 true
}
到了這里，關于數據結構例題代碼及其講解-順序表的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
