当前位置: 代码迷 >> 综合 >> 数据结构 绪论线性表 学习笔记
  详细解决方案

数据结构 绪论线性表 学习笔记

热度:26   发布时间:2024-01-18 18:38:46.0

Reference 《数据结构》 安徽大学出版社

第一章、绪论

基本术语(略)

数据元素、字段、数据结构。

算法分析:时间/空间复杂度

 

第二章、线性表(LinearList)

2.1定义

线性表的定义:是n个元素组成的有限序列。

非空线性表有以下特点:

1.有一个唯一的“第一个”数据元素。

2.有一个唯一的“最后一个”数据元素。

3.除了头元素外,表中其他元素有且只有一个直接前驱。

4.除了尾元素外,表中其他元素有且只有一个直接后继。

 

定义六个基本运算:

·初始化,initialList(L);

·求表长度,listLength(L);

·按序号取元素,listGetElement();

·按值查询,listLocate(L,x);

·插入元素,listInsert(L,i,x);

·删除元素,listDelete(L,i).

以上其中i均指的是位置,x指的是数值。

 

2.2顺序存储结构

2.2.1

对应数组,但是由struct封装(C/C++),class封装(C++)

typedef struct sList{elementType data[MAXN]; // elementTyoe Rrpresents INT etc.int listLen;
}seqList;

 2.2.2

1.初始化

void initialList(seqList &L) {//seqList * L <->  L->listLen = 0;L.listLen = 0;
}

思考:为什么不用对表单独进行操作?

提示:其需要的储存结构编译时已经确定,初始化仅需要令表长为0.

 

2.求表长

int listLength(seqList &L) {//seqList L  <->  return L.listLen;//seqList *L  <->  return L->listLen;return L.listLen;
}

 

3.按序号求元素

int getElememt(seqList L, int i, elementType *x) {if(i < 1 || i > L.listLen) {return 0;}else {(*x) = L.data[i - 1];return 1;}
}

注意:此函数设置了返回值,同时进行了边界处理。

除此之外,还可以直接返回一个变量值。

 

4.查找运算

int listLocate(seqList L, elementType x) {for(int i = 0; i < L.listLen; i++) {if(L.data[i] == x) return i + 1;}return 0;
}
int listLocate_1(seqList *L, elementType x) {for(int i = 0;i < L->listLen; i++) {if(L->data[i] == x) {return i + 1;}}return 0;
}
int listLocate_2(seqList &L, elementType x) {for(int i = 0; i < L.listLen; i++) {for(L.data[i] == x) {return i + 1;}}return 0;
}

 

5.插入算法

简要分析:插入之前要进行边界分析,满足条件后从后向前移动,在移出来的空位处放置要插入的元素。然后将表的长度++;

时间复杂度:O(n^2);

int listInsert(seqList *L, elementType x, int i) {if(L->listLen == MAXLEN)return 0;            //溢出else if(i < 1 || i > L->listLen + 1)return 1;           //越界else {for(int j = L->listLen -1; j >= i - 1; j--) {L->data[j + 1] = L->data[j];}L->data[j - 1] = x;L->listLen++;return 2;           //成功}}

 

6.删除

简要分析:删除元素无需真正的删除,只需要将从待删除元素一直到表末尾的元素全部前移一个位置即可。

时间复杂度:O(n^2)

int listDelete(seqList *L, int i) {if(L->listLen <= 0) return 0; //空表else if(i < 1 || i > L->listLen)return 1;                 //越界else {for(int j = i; j <L->listLen; j++) {L->data[j - 1] = L->data[j];}L->listLen--;return 2;}
}