线性表(List):零个或多个数据元素的有限序列
线性表的相邻元素之间存在着序偶关系。如用(a1,…,ai-1,ai,ai+1,…,an)表示一个顺序表,则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。
元素个数有限,元素之间有顺序,第一个元素无前驱,最后一个元素无后继。顺序存储结构的线性表,指的是地址连续的存储单元依次存储线性表的数据元素。
线性表的抽象数据结构
Operation
- init_list(*L);初始化操作,建立一个空的线性表L
- list_empty(L);判断线性表是否为空
- clear_list(*L);清空线性表
- get_elem(L,i,*e);获取线性表L中第i个位置的元素e
- list_insert(*L,i,e);在线性表L的第i个位置插入元素e
- list_delete(L,i,e);删除线性表L的第i个元素,并用e返回
顺序存储结构
<<list_header.h>>1
2
3
4
5
6
7
8
9
10
11
12
typedef int Status;
typedef int ElemType;
typedef struct{
ElemType data[MAXSIZE]; /* 使用数组存储数据元素 */
int length; /* 线性表当前长度 */
} SqList;
获取元素
获取线性表中第i个元素1
2
3
4
5
6
7
8
9
10
11Status get_elem(SqList L, int i, ElemType *e)
{
if(L.length == 0 || i < 1 || i > L.length)
{
printf("输入下标错误\n");
return ERROR;
}
*e = L.data[i-1];
return OK;
}
初始化数据
1 | /* 向线性表L中初始化num个元素 */ |
遍历线性表
1 | /* 遍历线性表 */ |
向线性表中插入数据
向线性表的第i个位置插入元素,所以data[i-1]以及其之后的所有元素都要向后移动一个位置1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23Status list_insert(SqList *L,int i,ElemType e)
{
int k;
if(i < 1 || i > L->length - 1)
{
printf("下标有误\n");
}
if(L->length == MAXSIZE)
{
printf("线性表已满,不能插入新元素\n");
}
if(i <= L->length)
{
for(k=L->length-1 ; k>=i-1 ; k--) //后续元素往后挪一位
{
L->data[k+1] = L->data[k];
}
}
L->data[i-1] = e;
L->length++;
return OK;
}
删除线性表中位置为i的元素,并返回该元素的值
删除线性表第i个位置的元素,所以data[i-1]以及之后的元素都要向前移动一个位置1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/* 删除元素并返回 */
Status list_delete(SqList *L, int i, ElemType *e)
{
//输入校验,略
int j;
*e = L->data[i-1]; //输出被删除的元素
if(i <= L->length && i > 0)
{
for(j=i;j<L->length;j++)
{
L->data[j-1] = L->data[j]; //从data[i-1]后面所有元素,向前挪一位
}
}
L->length--;
return OK;
}
测试:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int main()
{
SqList *L;
int res;
L = (SqList *)malloc(sizeof(SqList));
L->length = 0; //初始化空的线性表
init_data(L,5);
show_list(L);
/* 插入新元素 */
list_insert(L,3,99);
show_list(L);
/* 删除元素 */
list_delete(L,4,&res);
show_list(L);
printf("删除元素:%d\n",res);
return 0;
}
输出:
总结
线性表进行插入和删除操作的时间复杂度是O(n),因为涉及到元素的移动;
线性表进行读取数据时时间复杂度为O(1),直接取出下标元素即可;
优缺点:
优点:
- 无须为表中元素的逻辑关系而增加额外的存储空间
- 可以快速按照下标进行查找
缺点: - 插入和删除元素需要移动大量元素
- 连续内存空间,存在存储元素的上限
本文链接: http://www.xiaopeng.pro/articles/40f24371.html
版权声明: 本原创文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!