順序表的基本操作——插入、洗掉

1、順序表的基本操作——插入

ListInsert(&L,i,e):插入操作，在表中的第i個位置上插入指定元素e，

#include<stdio.h>
#define MaxSize 10			//定義最大長度
typedef struct {
    int data[MaxSize];	//用靜態的“陣列”存放資料元素
    int length;				//順序表的當前元素
}SqList;					//順序表的型別定義

void ListInsert(SqList &L,int i,int e){
    for(int j=L.length;j>=i;j--)		//將第i個元素之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;					//在位置i出放入e
    L.length++;						//長度+1
}
void InitList(SqList &L){
    int a=1;
	for(int i=0;i<5;i++){
		L.data[i]=a;			//設定陣列元素的初始值
    	a++;}
	L.length=--a;					//順序表長度
}
int main(){
    SqList L;
    InitList(L);
    ListInsert(L,3,3);
    for(int i=0;i<L.length;i++)
        printf("data[%d]=%d\n",i,L.data [i]);
    return 0;
}

運行結果：

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-H8A9taeH-1600083163625)(F:\blog\新建檔案夾\image-20200914131303851.png)]$

在位序3處插入元素3，

如果在插入函式的引數中設定了比MaxSize的大的數值怎么辦呢？所以在函式的書寫程序中需要判斷一下i的取值是否規范，

所以插入函式應做修改

bool ListInsert(SqList &L,int i,int e){
    if(i<1||i>L.length+1)		//判斷i的范圍是否有效
        return false;
    if(L.length>=MaxSize)		//當前存盤空間已滿，不能插入
        return false;
    for(int j=L.length;j>=i;j--)		//將第i個元素之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;					//在位置i出放入e
    L.length++;						//長度+1
    return turn;
}

在插入元素之前，先進行判斷，插入的位置是不是在有效范圍內，

插入操作的時間復雜度：最好情況O(1),最壞情況O（n），平均情況O（n）

2、順序表的基本操作——洗掉

ListDelete(&L,i,&e):洗掉操作，洗掉表L中第i個位置的元素，并用e回傳洗掉元素的值，

和插入類似，把要洗掉的值賦給e，然后將后面的元素依次前移一位，

bool ListDelete(SqList &L,int i,int &e){
   if(i<1||i>L.length)					//判斷i的值是否有效
       return false;
   e=L.data[i-1];						//將被洗掉的元素賦值給e
   for(int j=i;j<L.length;j++)			//將第i個位置后的元素前移
       L.data[j-1]=L.data[j];
   L.length--;
   return true;
}

洗掉操作的時間復雜度：最好情況O(1),最壞情況O（n），平均情況O（n）

對于插入操作：移動元素時，先移動后面的元素，再移動前面的元素

e;
}

洗掉操作的時間復雜度：最好情況O(1),最壞情況O（n），平均情況O（n），

對于插入操作：移動元素時，先移動后面的元素，再移動前面的元素，

對于洗掉操作：移動元素時，先移動前面的元素，再移動后面的元素，

- 王道考研《資料結構》視頻學習筆記！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/58254.html

標籤：其他

上一篇：如何運用無代碼化三維WebGL平臺-雀羽三維平臺trying3d-制作PBR物理材質效果三維模型

下一篇：AMESIM學習——彈簧阻尼器小球位置控制Amesim-Simulink聯合仿真