数据结构学习笔记（二）----线性表（上）

目录

线性表是什么？

线性表抽象数据类型

线性表的存储方式

 顺序表类

顺序表存储结构及特点

顺序表元素的地址计算

 类型描述

顺序表的类定义

顺序表类定义中的 构造函数

顺序表的操作实现：

查找操作

函数表现形式：

代码：

 执行示例：

插入操作

函数形式表示：

代码：

执行实例：

删除操作

函数形式表示：

代码：

执行示例：

逆置操作

代码：

 合并操作：

代码：

---

线性表是什么？

线性表是类型相同的数据元素的有限序列，数据元素可以是字符、整数、记录等；

例如：S={'a’，‘b’，‘c’}，或类似结构体数据；

注：S中‘a'称为前驱元素，‘c’称为后继元素；

线性表抽象数据类型

基本操作：

       

线性表的存储方式

线性表在计算机中的存储方式（又称映射）可分为：

 顺序表类

顺序表存储结构及特点

• 用一组地址连续的存储单元来依次存储线性表的各个元素；
• 用存储单元物理位置的相邻来表示相邻元素间的逻辑关系；

如：

顺序表元素的地址计算

 类型描述

const int maxlen=线性表可能达到的最大长度;
struct TsqList
{ Telem elem[maxlen];
 int curlen;
};
TsqList La,Lb;
La.elem[0]表示线性表的第一个元素，
La.curlen表示线性表的当前长度

顺序表的类定义

template
class SqList :public List

{private:
Telem *elem;

int curlen;

int maxlen;

......
~SqList(){delete[] elem;};

void init(){ curlen=0;};

Telem gete(int i);
int leng(){return curlen;};

int loct (Telem& el);
bool inst (int loc,Telem& el);

Telem dele(int loc);
bool full(){return curlen==maxlen;};

顺序表类定义中的 构造函数

SqList(int maxsz=100):maxlen(maxsz)
{
    curlen=O;
    elem=new Telem[ maxlen];
};
SqList(Telem a[],int n,int maxsz=100):maxlen(maxsz)
{
   curlen=n;
   elem=new Telem[ maxlen];
   for( int i=0;i
};

顺序表的操作实现：

查找操作

函数表现形式：

int loct（Telem& el）//从第一个元素（序号为0）起，依次进行比较，若能找到数据el，则返回该数据在线性表中的序号，否则返回0

代码：

template <class Telem>
int SqList::loct(Telem& el)
{
int i=0;
while ((i
if ( ireturn(i+1); else return(O);
};
//在上述程序中while循环的条件是必须同时满足(i

 执行示例：

假设线性表为

（'a','b','d','e','k','h')

• 若给定的值el='d',则当i=2时比较相等，while循环结束返回值为3；
• 若给定的值el='w',则当i=6时while循环才结束，此时由于i的值已经超过了表长-1，因此返回值为0。

插入操作

函数形式表示：

bool inst（int loc，Telem& el）//表示将元素el插入在顺序表中的第loc个位置处，其中，1<=loc<=curlen+1,若插入成功返回true，否则返回false；

注：在插入操作中，原来loc位置上的元素以及loc后面的所有元素向后移一位；

后移元素

• 逻辑序号从loc到 curlen
• 物理序号从loc-1到curlen-1

由于循环控制变量是以目的位置为准所以i应从loc到curlen程序中 curlen先加了1,然后将loc到curlen的元素后移一个位置。
注意:元素后移时应该从最后一个元素开始移动

代码：

template <class Telem>
	bool SqList::inst(int loc,Telem& el)
	{
	    int i;
	    if((locale<1)||(loc>curlen+1)||(curlen==maxlen))
            return(false);
        else
        {
            curlen++;
            for(i=curlen-1;i>=loc;i--)elem[i]=elem[i-1];
             elem[loc-1]=el;
            return(true);
        };
	};

执行实例：

假设线性表为

 （'a','b','d','e','k','h')

若给定的参数值el=’x'，loc=3则正确插入为：（'a','b','x','d','e','k','h')

若给定的参数值el=’x'，loc=7则正确插入为：（'a','b','d','e','k','h','x')

若给定的参数值el=’x'，loc=9则输出出错信息：false

删除操作

函数形式表示：

Telem dele（int loc）//表示将删除在顺序表中的第loc个位置处的元素并返回该元素，其中，1<=loc<=curlen+1,若位置loc不合法返回NULL；

逐个上移传送:

• 逻辑序号:i从loc＋1到curlen
• 物理序号:i从loc到 curlen-1
• 最后将loc位置的元素删除

代码：

template <class Telem>
	bool SqList::dele(int loc)
	{
	    int i;Telem el;
	    if((locale<1)||(loc>curlen+1)||(curlen==maxlen))
            return NULL;
        else
        {
            el=elem[loc-1];
            curlen++;
            for(i=loc;i-1]=elem[i];
             curlen--;
            return(el);
        };
	};

执行示例：

（'a','b','d','e','k','h')

若给定的参数值loc=3则正确删除，返回‘d’，线性表为：（'a','b','e','k','h')

若给定的参数值loc=7则输出出错信息 NULL

逆置操作

• 将整个元素序列分为前后两部分,
• 然后将这两部分中所有对应的元素进行交换。

交换对象: elem[ i]与Sxb.clem[ n-1 -i]i : 0到n / 2 -1 

代码：

 template <class Telem>
    void SqList::inver()
    {
        int i,m,n;
        Telem temp;
        n=curlen;
        m=n/2;
        for(i=0; i
        {
            temp=elem[i];
            elem[i]=elem[n-1-i];
            elem[n-1-i]=temp;
        };
    };

 合并操作：

代码：

 template <class Telem>
    SqList&SqList::merg(SqList&12)
    {
        int i,m,n;
        m=curlen;
        n=12.curlen;
        if(m+n<=maxlen)
        {
            for(i=0; i12.elem[i];
            curlen=m+n;
            return *this;
        }
    }