当回首往事的时候，不因虚度年华而悔恨.
2020.9.22
我是真的不太会调格式,而且我是用md写的笔记,调格式调的很烦躁,我把笔记附加到后边了,请下载后病毒查杀!确定安全后打开!!
线性表
-
线性表的定义
D = { $a_i$ | 1 $\leq$ i $\leq$ n, n $\geq$ 0}
R = {r}
r = {<$a_i$,$a_i$$_+$$_1$> | 1 $\leq$ i $\leq$ n-1}
-
线性表的逻辑特征
对于含有一个元素的线性表,除其实元素没有钱去元素外,其他元素有且只有一个直接前驱元素;除终端元素没有后继元素之外,其他元素有且仅有一个直接后继元素.
-
线性表的储存结构
-
顺序储存结构(顺序表)
特点:储存位置为一块连续的储存空间
优点:无需额外开辟空间来储存元素之间的关系
-
链式储存结构(链表)
特点:每个节点带有指针域,比顺序表消费空间大,储存地址可以使不连续(单个节点的地址必须连续)
-
单链表(注:这里的->不是c语言中的指正,只代表指向下一个元素)
-
pre_e.next->cur_e,cur_e.next->next_e
-
pre_e:是当前元素的前驱元素
-
cur_e:当前元素
-
next_e:是当前元素的后继元素
-
双链表
-
双链表
pre_e.next<->cur_e.pre,cur_e,cur_e.next<->next_e.pre
graph LR
A[头结点] -->B(开始节点)
B --> c[....]
c --> d[尾节点]
d --> A
一知半解
(加入此段落,主要是一切对本段知识点的一个总结和回顾,以及一些知识点的比较和认识,自我感觉有助于从整体上了解.)
-
顺序表和链表储存方式的特点
顺序表的优点是可以随机存取元素,存储密度高;缺点是不便于插入和删除元素(需要移动大量的元素).
链表的优点是便于节点的插入和删除(只需要修改指针域,不需要移动节点);缺点是不能进行随机访问,只能顺序访问,另外,每个节点上增加指针域,导致储存密度低.
-
在什么情况下使用顺序表比较好?
当现行表很少进行插入和删除操作,或者插入和删除操作总在尾部进行时.
-
若频繁地对一个线性表进行插入和删除操作,该线性表采用何种储存结构,为什么?
链式储存结构.因为采用链式储存结构储存线性表,在插入和删除操作时只修改相关节点的指针域,不需要移动节点;而采用顺序结构储存线性表是,插入和删除需要平均移动表中的一半元素.修改指针域操作比移动元素华为的时间少很多.
顺序表的算法
-
顺序表的定义
-
顺序表的基本算法
- 初始化顺序表算法
#define MaxSize 50
typedet struct
{
ElemType data[MaxSize]; //存放顺序表的中的元素
int length; //存放顺序表中的长度
} SqList; //声明顺序表的类型
//初始化
void InitList(SqList &L)
{
L.length = 0;
} //时间复杂度 O(1)
- 求顺序表中制定元素位置元素值的算法
void GetElem(SqList L, int i, ElemeType &e)
{
if(i<1 || i>L.length)
return 0;
e = L.data[i-1]; //实际下标从零开始,第一个元素为L.data[0]
return 1;
}//时间复杂度 O(1)
3. 按元素值查找算法
int LocateElem(SqList L, ElemType e)
{
int i = 0;
while(i<L.length && L.data[i] !=e) i++;
if(L>=L.length)
return 0; //未找到返回0
else
return i+1; //下标+1为所及序号
}//时间复杂度 O(n)
4. 插入数据元素算法
int LisInsert(SqList &L, ElemType e, int i)
{
int j;
if(i<1 || i>L.length+1)
return 0; //插入失败
i--;
for(j=L.length; j>i; j--) //循环后移
L.data[j]=L.data[j-1];
L.data[i] = e;
L.length++; //元素个数+1
return 1; //成功插入
}//时间复杂度 O(n)
5. 删除数据元素算法
int ListDelete(SqList &L, int i, ElemeType &e)
{
int j;
if(i<1 || i>L.length)
return 0;
i--;
e = L.data[i];
for(j=i; j<L.length-1; j++)
L.data[j] = L.data[j+1];
L.lengh--;
return 1;
}//时间复杂度 O(n)
- 有序顺序表的归并算法
/**
* 当一个有顺序表采用顺序表储存时(默认从小到大排序),称为有序顺序表.
* 当两个有序顺序表归并为一个有序顺序表的过程,称为有序顺序表的归并.
**/
void Merge(SqList L1, SqList L2, SqList &L3)
{
int i = 0, j = 0, k = 0;
while(i<L1.Length && j<L2.Length)
{
if(L1.data[i] < L2.data[2])
{
L3.data[k] = L1.data[i];
i++; k++;
}
else
{
L3.data[k] = L2.data[j];
j++; k++;
}
}
while(i<L1.Length)
{
L3.data[k] = L1.data[i];
i++; k++;
}
while(i<L2.Length)
{
L3.data[k] = L2.data[j];
j++; k++;
}
return L3.Length = k;
}
以下为Java版本
public class SqList<T> {
/**
* 顺序表中一维数组的初始长度
*/
private int maxSize = 10;
/**
* 存储元素的数组对象
*/
private T[] arr;
private int length;
/**
* 初始顺序表为空
*/
public SqList() {
length = 0;
arr = (T[]) new Object[maxSize];
}
/**
* 初始顺序表为空
* @param length
*/
public SqList(int length) {
if (length > 0) {
this.length = 0;
maxSize = length;
arr = (T[]) new Object[maxSize];
} else {
throw new RuntimeException("请输入长度大于0的正整数!");
}
}
/**
* 在指定位置插入新的元素
* @param t
* @param index
* @return
*/
public boolean add(T t, int index) {
if (index < 1 || index > length + 1) {
System.out.println("请输入正确的插入位置!");
return false;
}
//判断当前顺序表是否已满
if (isFull()) {
System.out.println("顺序表已满,插入失败!");
return false;
}
index--;
if (length - index >= 0) {
System.arraycopy(arr, index, arr, index + 1, length - index);
}
arr[index] = t;
length++;
return true;
}
/**
* 删除指定位置的元素,并返回被删除的元素
* @param index
* @return
*/
public T delete(int index) {
if (isEmpty()) {
System.out.println("顺序表为空!");
return null;
}
if (index < 1 || index > length) {
System.out.println("请输入正确的删除位置");
return null;
}
index--;
T t = arr[index];
if (length - index >= 0) {
System.arraycopy(arr, index + 1, arr, index, length - index);
}
length--;
return t;
}
/**
* 返回第一个相同元素的位置
* @param t
* @return
*/
public int findIndex(T t) {
if (isEmpty()) {
System.out.println("顺序表为空!");
return -1;
}
for (int i = 0; i < length; i++) {
if (arr[i].equals(t)) {
return i + 1;
}
}
return -1;
}
/**
* 返回指定位置的元素
* @param index
* @return
*/
public T findT(int index) {
if (isEmpty()) {
System.out.println("顺序表为空!");
return null;
}
if (index < 1 || index > length) {
System.out.println("请输入正确的查询位置");
return null;
}
return arr[index - 1];
}
/**
* 判断顺序表是否已满
* @return
*/
public boolean isFull() {
return maxSize == length;
}
/**
* 判断顺序表是否为空
* @return
*/
public boolean isEmpty() {
return length == 0;
}
/**
* 返回当前顺序表的长度
* @return
*/
public int getLength() {
return length;
}
/**
* 清空顺序表
* @Description 当初始化长度为0时候已经把顺序表清空了,原有的数值会在下次添加时候覆盖掉
*/
public void clearList() {
length = 0;
arr = null;
}
public static void main(String[] args) {
SqList<Integer> list = new SqList<>(10);
System.out.println(list.isEmpty());
System.out.println(list.add(1, 1));
System.out.println(list.isFull());
System.out.println(list.findIndex(1));
System.out.println(list.findT(1));
System.out.println(list.getLength());
System.out.println(list.delete(1));
list.clearList();
System.out.println(list.isEmpty());
}
}
---
发表于 2020-9-22 22:28
