620-数据结构.pptVIP

数 据 结 构 第二章 线性表 2.1 线性表的定义及运算（逻辑结构） 定义：一个线性表是n（=0）个数据元素的有限序列。 2.2 线性表的顺序存储结构 一、顺序表： 定义：用一组地址连续的存储单元存放一个线性表叫~。 元素地址计算方法： a1 地址已知 LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L—一个元素占用的存储单元个数 LOC(ai)—线性表第i个元素的地址 特点： 实现逻辑上相邻—物理地址相邻 实现随机存取 实现： 可用C/C++语言的一维数组来模拟实现。 一、顺序表（线性表的顺序存储结构） 1. 完整的存储结构描述： const int MAX=100; typedef int ElemType; struct list { ElemType data[MAX]; //静态数组 int length; //线性表实际长度 }; 一、顺序表（线性表的顺序存储结构） 2. 完整的存储结构描述： const int MAX=100; typedef int ElemType; struct list2 { ElemType *data ; //动态数组 int length; //线性表实际长度 }; 二、顺序表的类定义 typedef int ElemType; // 数据元素的类型 const int MAXSIZE=100; // 数组的容量 class Sqlist { private: ElemType elem[MAXSIZE]; int length; //数据个数，表长 public: Sqlist(); ~Sqlist(){ }; void SetData(); void Insert( int i, ElemType e); ElemType Delet(int i); void PrintOut(); int IsEmpty(void)const; }?; void Sqlist::SetData() //建立一个简表函数 { elem[0]=11;elem[1]=12; length=2; } 二、顺序表的主要操作（运算） 1. 插入 2. 删除 1. 插入 定义：线性表的插入是指在第 i（1? i ? n+1）个元素之前插入一个新的数据元素e，使长度为n的线性表: 线性表的插入:在第 i（1? i ? n+1）个元素之前插入一个新的数据元素e。 算法 2.1 void Sqlist::Insert( int i, ElemType e) { int j; i--; //逻辑位置换算为C++数组下标值 if(i0||ilength) //判断插入位置的正确性 cout“\n i Error!endl; else { for(j=length; ji; j--) elem[j]=elem[j-1]; //移动元素 elem[i]=e; //插入元素 length++; //表长加1 } } 插入算法的时间复杂度T(n) （n-i+1）是i 确定时，移动数据元素的次数； 即算法中最大语句频度,而i的取值范围：1,2,…,n+1. 设 Pi 是在第i个元素之前插入一个元素的概率； 1/（n+1） 假设是等概率情况。 则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均移动次数为： 2. 删除 定义：线性表的删除是指将第 i（1?i ? n）个元素删除，使长度为n的线性表： 线性表的删除:是指将第 i（1?i ? n）个元素删除，返回数据值。 算法 2.2 ElemType Sqlist::Delet(int i) { ElemType x; int j; i- -; //转换成C++数组下标 if(i0||ilength-1) //判断i的正确性 { cout “\n i Error!endl; x=-1;} else{ x=elem[i];