现设计该线性表的如下存储结构: 0.顺序表 1.带头结点的单链表 2.带头结点的循环单链表 3.不带头结点仅有尾结点指针标识的循环单链表 4.带头结点的双链表 5.带头结点的循环双链表 (1)请分别指出各种存储结构中对应运算算法的时间复杂度。 (2)学号最后两位被6整除余数为几,就请在第几种存储结构下实现运算A、B、E、H。
时间: 2024-02-29 20:55:03 浏览: 105
线性表的存储结构与顺序表的存储实现共4页.pdf.zip
(1)各种存储结构中对应运算算法的时间复杂度如下:
0. 顺序表
a. 访问元素:O(1)
b. 插入元素:最好情况O(1),最坏情况O(n),平均情况O(n)
c. 删除元素:最好情况O(1),最坏情况O(n),平均情况O(n)
1. 带头结点的单链表
a. 访问元素:O(n)
b. 插入元素:O(1)
c. 删除元素:O(1)
2. 带头结点的循环单链表
a. 访问元素:O(n)
b. 插入元素:O(1)
c. 删除元素:O(1)
3. 不带头结点仅有尾结点指针标识的循环单链表
a. 访问元素:O(n)
b. 插入元素:O(1)
c. 删除元素:O(1)
4. 带头结点的双链表
a. 访问元素:O(n)
b. 插入元素:O(1)
c. 删除元素:O(1)
5. 带头结点的循环双链表
a. 访问元素:O(n)
b. 插入元素:O(1)
c. 删除元素:O(1)
(2)如果学号最后两位被6整除余数为0,则在第0种顺序表中实现运算A、B、E、H;如果余数为1,则在第1种带头结点的单链表中实现运算A、B、E、H;如果余数为2,则在第2种带头结点的循环单链表中实现运算A、B、E、H;如果余数为3,则在第3种不带头结点仅有尾结点指针标识的循环单链表中实现运算A、B、E、H;如果余数为4,则在第4种带头结点的双链表中实现运算A、B、E、H;如果余数为5,则在第5种带头结点的循环双链表中实现运算A、B、E、H。
阅读全文