基本概念

• 

• 注意：

  ​ 线性表可以是空表，树可以是空树，但图不可以是空，即v一定是非空集

无向图、有向图

线性表的查找

顺序查找

int SerchSqList(SqList &L,int e)
{
	for(int i = 0;i<L.length;i++)
	{
		if(e == L.elem[i]){
			cout<<"已找到元素"<<L.elem[i]<<endl;
			return e;
		}
	}
	return 0;
}

基本概念

• 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找
• 查找表(查找结构)：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成
• 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的

查找表的常见操作

1. 查找符合条件的数据元素(静态查找表)
2. 插入、删除某个元素数据(动态查找表)

基本概念和排序方法

排序的基本概念

1. 排序：从大到小或从小到大排序
2. 排序的稳定性：
   • 稳定的：关键字相同的元素在排序之后相对位置不变
   • 不稳定：相反
3. 排序算法的分类：
   • 内部排序：待排序记录全部放在计算机内存中*(关注算法时间、空间复杂度)*
   • 外部排序：数据过大，以至于内存中不能容纳全部的数据，在排序过程中，尚需对外存进行访问排序*(还要关注读取/写磁盘的次数更少)*

线性表的顺序表示和实现

1. 初始化

   步骤：

   1. 为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址
   2. 将表的当前长度设为0

   代码：

   //初始化
   const int MAXSIZE = 100;
   bool InitList(SqList L)
   {
       L.elem = new ElemType[MAXSIZE];
       if(!L.elem){
           return 0;
       }
       L.length = 0;
       return true;
   }

2. 取值

   步骤:

   1. 判断指定的位置序号i的值是否合理，若不合理，返回false
   2. 若值合理，则将第i个数据元素L.elem[i-1]赋值参数e，通过e返回第i个数据元素的传值

   //取值
   int GetElem(SqList L,int i,ElemType e)
   {
       if(i<1 || i>L.length){
           return -1;
       }
       e=L.elem[i-1];
       return e;
   }

3. 查找

   步骤：

   1. 从第一个元素起，依次将其值和e比较，若找到和e值相等的元素L.elem[i]，则查找成功，返回该元素的序号i+1
   2. 若查遍整个顺序表都没有找到，则查找失败，返回0

   //查找
   int LocateElem(SqList L,ElemType e)
   {
       for(int i=0;i<L.length;i++){
           if(e==L.elem[i]){
               return i+1;            
           }else{
               return 0;
           }
       }
       return 0;
   }

4. 插入

   1. 判断插入位置i是否合法(i值的合法范围为1<=i<=n+1)，若不合法返回FALSE
   2. 判断顺序表的存储空间是否已满，若满了，返回FALSE
   3. 将第n个至第i个元素依次向后移动一个位置，空出第i个位置(i=n+1时无序移动)
   4. 将要插入的元素e放入第i个元素
   5. 表长加一

   //插入
   bool ListInsert(SqList &L,int i,ElemType e)
   {
       if(i<1 || i>L.length+1)
       {
           return false;
       }
       if(L.length==MAXSIZE){//判断顺序表的存储空间是否已满
           return false;
       }
       for(int j=L.length-1;j>=i-1;j--){
           L.elem[j+1]=L.elem[j];    
       }
       L.elem[i-1] = e;
       ++L.length;
       return true;
   }

5. 删除

   步骤:

   1. 判断删除位置i是否合法(合法的值为1<=i<=n)，若不合法则返回FALSE
   2. 将第i+1个元素至第n个元素依次向前移动一个位置(i=n时无需移动)
   3. 表长减一

   //删除
   bool ListDelete(SqList &L,int i)
   {
       if(i>L.length && i<1){
           return false;
       }
       for(int j=i;j<=L.length-1;j++){
           L.elem[j-1]=L.elem[j];
       }
       --L.length;
       return true;
   }