数据结构学习笔记2

数据结构
第二章：chapter 1线性表线性存储
引入:
线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
可表示为：（a1 , a2 , ……, an）
线性结构表达式：（a1 , a2 , ……, an）
线性结构的特点：
① 只有一个首结点和尾结点；
② 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。
逻辑关系是： 一对一
线性结构包括线性表、堆栈、队列、字符串、数组等等
线性表：线性表的重要基本操作

1. 初始化
2. 取值
3. 查找
4. 插入
5. 删除
   初始化：

Status InitList_Sq(SqList &M){    //构造一个空的顺序表M
    M.elem=new ElemType[MAXSIZE];   //为顺序表分配空间
    if(!M.elem) exit(OVERFLOW);       //存储分配失败
    M.length=0;					  //空表长度为0
    return OK;
}

取值：
获取线性表M中的某个数据元素的内容

int GetElem(SqList M,int i,ElemType &e)
{
  if (i<1||i>M.length) return ERROR;   
   //判断i值是否合理，若不合理，返回ERROR
  e=M.elem[i-1];   //第i-1的单元存储着第i个数据
  return OK;
}

查找：
在线性表M中查找值为e的数据元素

int LocateELem(SqList M,ElemType e)
{
  for (i=0;i< M.length;i++)
      if (M.elem[i]==e) return i+1;                
  return 0;
}

插入：
在线性表M中第i个数据元素之前插入数据元素e

Status ListInsert_Sq(SqList &M,int i ,ElemType e){
   if(i<1 || i>M.length+1) return ERROR;	         //i值不合法
   if(M.length==MAXSIZE) return ERROR;    //当前存储空间已满     
   for(j=M.length-1;j>=i-1;j--) 
       M.elem[j+1]=M.elem[j];    //插入位置及之后的元素后移
    M.elem[i-1]=e;                     //将新元素e放入第i个位置
  M.length++;		     	//表长增1
  return OK;
}

删除：
将线性表M中第i个数据元素删除

Status ListDelete_Sq(SqList &M,int i){
   if((i<1)||(i>M.length)) return ERROR;	 //i值不合法
   for (j=i;j<=M.length-1;j++)                   
　  　M.elem[j-1]=M.elem[j];       //被删除元素之后的元素前移  
   M.length--;               	      //表长减1
  return OK;
}