【C语言-数据结构】顺序表的基本操作

顺序表的基本操作

【建议：如果对结构体还不太理解的话可以先看 C语言-结构体 这篇文章】

插入操作

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

代码实现

#include <stdio.h>
#include <stdbool.h>
#define MaxSize 10typedef struct{int data[MaxSize];int length;
}SqList;void InitList(SqList* L){L->length = 0;
}bool ListInsert(SqList* L, int i, int e){if(i<1 || i>length+1){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;L->length++;return true;
}int main(){SqList L;InitList(&L);//...向顺序表中插入一些元素...ListInsert(&L,3,3);return 0;
}

时间复杂度分析

• 最好情况：新元素插入到表尾，不需要移动元素
  i = n+1，循环 0 次 ➡️ 最好时间复杂度 = O(1)
• 最坏情况：新元素插入到表头，需要将原有的 n 个元素全都向后移动
  i = 1，循环 n 次 ➡️ 最坏时间复杂度 = O(n)
• 平均情况：假设新元素插入到任何一个位置的概率相同，即 i = 1,2,3,…,length+1 的概率都是 $p=\frac{1}{n+1}$
  i = 1 时，循环 n 次；i = 2 时，循环 n-1 次，…… ，i = n+1 时，循环 0 次
  平均循环次数 = np + (n-1)p + …… + 1·p = $\frac{n(n+1)}{2}\frac{1}{n+1}$ = $\frac{n}{2}$ ➡️ 平均时间复杂度 = O(n)

删除操作

ListDelete(&L,i,&e)：删除操作，删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值

代码实现

#include <stdio.h>
#include <stdbool.h>
#define MaxSize 10typedef struct{int data[MaxSize];int length;
}SqList;void InitList(SqList* L){L->length = 0;
}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; j++){L->data[j-1] = L->data[j];}L->length--;return true;
}int main(){SqList L;InitList(&L);//...向顺序表中插入一些元素...int e = -1;if(ListDelete(&L, 3, &e)){printf("已删除第3个元素，删除元素值为%d\n",e);}else{printf("位序i不合法，删除失败\n");}return 0;
}

时间复杂度分析

• 最好情况：删除表尾元素，不需要移动元素
  i = n，循环 0 次 ➡️ 最好时间复杂度 = O(1)
• 最坏情况：删除表头元素，需要将后续的 n-1 个元素全都向前移动
  i = 1，循环 n-1 次 ➡️ 最坏时间复杂度 = O(n)
• 平均情况：假设删除任何一个元素的概率相同，即 i = 1,2,3,…,length 的概率都是 $p=\frac{1}{n}$
  i = 1 时，循环 n-1 次；i = 2 时，循环 n-2 次，…… ，i = n 时，循环 0 次
  平均循环次数 = (n-1)p + …… + 1·p = $\frac{n(n-1)}{2}\frac{1}{n}$ = $\frac{n-1}{2}$ ➡️ 平均时间复杂度 = O(n)

按位查找操作

GetElem(L,i)：按位查找操作，获取表 L 中第 i 个位置的元素的值

代码实现

ElemType GetElem(SqList* L, int i){return L->data[i-1];
}

时间复杂度：O(1)

按值查找操作

LocateElem(L,e)：按值查找操作，在表 L 中查找具有给定关键字值的元素

代码实现

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqList* L, int e){for(int i = 0; i < L.length; i++){if(L->data[i] == e){return i+1;}}return 0;
}

时间复杂度分析

• 最好情况：目标元素在表头
  循环 1 次 ➡️ 最好时间复杂度 = O(1)
• 最坏情况：目标元素在表尾
  循环 n 次 ➡️ 最坏时间复杂度 = O(n)
• 平均情况：假设目标元素出现在任意一个位置的概率相同，即都是 $p=\frac{1}{n}$
  平均循环次数 = $\frac{n+1}{2}$ ➡️ 平均时间复杂度 = O(n)

---

本文主要参考《王道计算机考研 数据结构》课程视频