数据结构与算法基础（王卓）（3）

目录

前置：

二、线性表的销毁

三、线性表的清空

四、线性表是否为空 

五、返回线性表元素个数

六、返回线性表第i个元素值

重难点算法：（算法时间复杂度:O(n)）

七、查找元素

八、线性表的插入

九、线性表的删除

十、定位元素位序（第几个元素）

十一、指定元素的前驱与后继

十二（附加）、对线性表内部所有元素进行统一同一操作

---

前置：

//#include
#include//存放exit
 
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE  -1
#define OVERFLOW   -2   
 
#define MAXlength 100  //初始大小为100，可按需修改
 
typedef int Status;         //函数调用状态
 
struct Poly
{
    float p;
    int e;
};
 
struct Sqlist
{
    Poly* elem;
    int length;
};

位置：PPT第二章：72

二、线性表的销毁

void DestroyList(Sqlist& L)
{
    if (L.elem) delete L.elem;
}

三、线性表的清空

void ClearList(Sqlist& L)
{
    L.length = 0;
    //将线性表的长度设置为0
}

四、线性表是否为空 

int IsEmpty(Sqlist L)
{
    if (L.length == 0)
        return true;
    else
        return false;
}

五、返回线性表元素个数

int Listlength(Sqlist L)
{
    return L.length;
}

六、返回线性表第i个元素值

int GetElem(Sqlist L,int i,Poly ele)//element:元素
{
    if (i <= 0 || i > L.length)
        return ERROR;
        ele = L.elem[i-1];
        return OK;
}

int GetElem(Sqlist L,int i,Poly ele)//element:元素
{
    if (i <= 0 || i > L.length)
        return ERROR;
        ele = L.elem[i-1];
        return OK;
}

或者：

bool GetELem(const SqList &L, const size_t i, ElemType &e)
{
    if(i<1 || i>MAXSIZE)
    {
        cerr<<"out of range"<
        return false;
    }
    e = L.elem[i-1];
    return true;
}

 ele = L.elem[i-1]:

elem是结构体Sqlist里面的一个指针（型）变量成员，指向一个Ploy类型的目标变量

也就是说，其本身就是这个类型的对象的首地址，至于剩下的，就不用我多说了吧

如果还要我说，那就详见：C语言日记 25 指针与数组_宇 -Yu的博客-CSDN博客

---

另外，视频里没有说，但是介绍基本操作时要求的操作：

定位元素位序（第几个元素）

指定元素的前驱与后继

对线性表内部所有元素进行统一同一操作

这几个操作算法，我们在本文末尾再补充完整

这个（以上）算法的复杂度都为常量阶O(1)

顺序表可以随机存取（只要进行一次赋值操作，想要哪个都可以）这是其非常大的优点

比如链表就没有（不能实现）这样的功能

---

重难点算法：（算法时间复杂度:O(n)）

七、查找元素

project1：

int LocateElem(Sqlist L, Poly i)
{
    int a;
    for (a = 0; L.elem[a] != i; a++);
    cout << "元素序号:  " << a << endl;
    // cout<<
 
}

注意，我们要的，是把所有符合条件的元素筛选出来，而不是只选取第一个：

---

project2：

int LocateElem(Sqlist L, Poly i)
{
    for (int a = 0; a <= L.length; a++)
    {
        if (i == L.elem[a])
            return a + 1;
        return 0;
    }
}

可结果却显示：

 为什么？？？ 

完整代码：

#include
#include//OVERFLOW,exit
#define OK          1
struct Poly
{
    float p;
    int e;
};
 
struct Sqlist
{
    Poly* elem;
    int length;
};
 
 
int LocateElem(Sqlist L, Poly i)
{
    for (int a = 0; a <= L.length; a++)
    {
        if (i == L.elem[a])
            return a + 1;
        return 0;
    }
}

原因不在我写的操作函数里，而是在前面的类体当中；

究其根本原因，还是因为：==不能直接比较结构体，需要手撸比较的工具：

    bool operator==(Poly& t) 
    {
        return t.p == p && t.e == e;
    }

---

project 3：

#include//OVERFLOW,exit
#define OK          1
struct Poly
{
    float p;
    int e;
    bool operator==(Poly& t) 
    {
        return t.p == p && t.e == e;
    }
};
 
struct Sqlist
{
    Poly *elem;
    int length;
};
 
 
int LocateElem(Sqlist L, Poly i)
{
    for (int a = 0; a <= L.length; a++)
    {
        if (i == L.elem[a])
            return a + 1;
        return 0;
    }
}
int main()
{
 
}

 用while语句实现：

#include
#include//OVERFLOW,exit
#define OK          1
struct Poly
{
    float p;
    int e;
    bool operator==(Poly& t)
    {    return t.p == p || t.e == e;   }
    bool operator!=(Poly& t)
    {
        return t.p != p && t.e != e;
    }
};
 
struct Sqlist
{
    Poly* elem;
    int length;
};
 
int LocateElem(Sqlist L, Poly i)
{
    int a = 0;
    while (a <= L.length && i != L.elem[a])
        a++;
    if(a <= L.length)
        return a + 1;
    return 0;
}
int main()
{
 
}

---

八、线性表的插入

project 1：

int ListInsert(Sqlist L,int i,Poly e)
{//insert:插入//i:插入位置(位置序号)
    if (i<1 || i>L.length + 1)
        return ERROR;
 
    //把插入位置后面的元素全部往后移
    for (int j = L.length - 1; j >= i - 1; j--)//j为下标
        L.elem[j + 1] = L.elem[j];
    //放元素
    L.elem[i-1] =  e;
    return 0;
}

记得（别忘了）写：

    if (L.length == MAXlength)return ERROR;
和

    L.length++;

project 2：

int ListInsert(Sqlist L,int i,Poly e)
{//insert:插入//i:插入位置(位置序号)
    if (i<1 || i>L.length + 1)
        return ERROR;
    if (L.length == MAXlength)return ERROR;//当前储存空间已满
    //把插入位置后面的元素全部往后移
    for (int j = L.length - 1; j >= i - 1; j--)//j为下标
        L.elem[j + 1] = L.elem[j];
    //放元素
    L.elem[i-1] =  e;
    L.length++;
    return 0;
}

//#include
#include//存放exit
 
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE  -1
#define OVERFLOW   -2   
 
#define MAXlength 100  //初始大小为100，可按需修改
 
typedef int Status;         //函数调用状态
 
struct Poly
{
    float p;
    int e;
};
 
struct Sqlist
{
    Poly* elem;
    int length;
};
 
int ListInsert(Sqlist L,int i,Poly e)
{//insert:插入//i:插入位置(位置序号)
    if (i<1 || i>L.length + 1)
        return ERROR;
    if (L.length == MAXlength)return ERROR;
    //把插入位置后面的元素全部往后移
    for (int j = L.length - 1; j >= i - 1; j--)//j为下标
        L.elem[j + 1] = L.elem[j];
    //放元素
    L.elem[i-1] =  e;
    L.length++;
    return 0;
}
int main()
{
 
}

注意：

i：位序；不是下标

j：数组下标（用于访问数据）

L.length：总的元素个数，i的最大值

九、线性表的删除

int ListDelete(Sqlist L,int i)
{
    if (i < 1 || i > L.length )
        return ERROR;
    for (int j = i - 1; j <= L.length-1; j++)
        L.elem[j] = L.elem[j + 1];
    L.length--;
}

按照书上的写法：（不要忘了：    return OK;）

int ListDelete(Sqlist L,int i)
{
    if (i < 1 || i > L.length )
        return ERROR;
    for (int j = i ; j <= L.length; j++)
        L.elem[j-1] = L.elem[j];
    L.length--;
    return OK;
}

bool EraseList(Sqlist &L, const int &i)
{
    //异常判断
    if(i<0 || i>L.length)
    {
        cerr << "wrong erase position!" << endl;
        return false;
    }
    if(L.length == 0)
    {
        cerr << "List has no length" << endl;
        return false;
    }
    //将位于删除位置之后的元素依次向前挪动一位
    for (int p = i + 1; p < L.length; ++p)
    {
        L.elem[p - 1] = L.elem[p];
    }
    //线性表长度-1
    L.length -= 1;
    return true;
    //算法时间复杂度：O(n)
}

---

视频里没有说，但是介绍基本操作时要求的操作：

十、定位元素位序（第几个元素）

Status LoacteElem(Sqlist L, Poly e)
{
    int i = 0;
    if (!&L)//初始条件：L存在
        return false;
    while (L.elem[i] != e)i++;
    if (e == L.elem[i])
        cout << "元素位序为：" << i + 1 << endl;
    return false;
}

 当然，还得在前面手写等于和不等于判断表达式：

struct Poly
{
    float p;
    int e;
 
    bool operator==(Poly t)
    {
        return t.p == p && t.e == e;
    }
    bool operator!=(Poly t)
    {
        return t.p != p || t.e != e;
    }
};

Issues：

（1）：为什么赋初值时 i = 0；（为什么赋给i = 0？）输出结果时输出 i + 1？

i = 0：

显然，线性表以数组形式进行存储，而数组下标下限默认为0；所以在赋初值时必须令 i = 0（而不是 i = 1）

实现让程序从访问数组首个元素开始对线性表（内的）元素逐个访问寻找元素

输出 i + 1：

每个元素的位序恰巧为其下标加一（例：第一个元素的下标为零）

而在程序跳出其中的while循环以后，i的值恰好为我们所要定位的元素的下标

所以在输出时，其元素位序即为i + 1；

---

（2）：更改为下图形式为什么会报错？

详细地说：

数组名不是既可以代表（代指）整个数组，又可以代指这个数组的头指针（首个元素的地址）吗？

那么，为什么

• (!L)无法代表线性表首元素地址
• L->elem无法访问线性表内的元素
• 无法用L = (L + 1)让线性表指向下一位地址

 ？？？

原因其实很简单：

L在程序里，作为一个采用引用传值的变量

传过来的默认就是一个线性表，自然无法被看作是一个头指针了

至于为什么不能写L->elem，必须写成 L.elem[i]：

因为我们定义的 Poly* elem本身就是一个指向（Poly型）目标对象的指针

如果一定要使用指针访问来实现这个操作算法，那就利用L.elem作为指针：

Status LoacteElem(Sqlist& L, Poly e)
{
    int i = 0;
    if (!&L)//初始条件：L存在
        return false;
    while (*(L.elem) != e)
    {
        L.elem= L.elem + 1;
        i++;
    }
    if (e == *(L.elem))
        cout << "元素位序为：" << i + 1 << endl;
    return false;
}

---

在elem不是指针类型（Poly elem）时：（用指针访问）    

Status LoacteElem(Sqlist& L, Poly e)
{
    int i = 0;
    auto p = &L.elem;
    if (!&L)//初始条件：L存在
        return false;
    while (*p != e)
    {
        p++;
        i++;
    }
    if (e == (L.elem))
        cout << "元素位序为：" << i + 1 << endl;
    return false;
}

注意：这种情况下（elem不是指针类型）,不能再想当然地，简单用 

&L.elem = &L.elem + 1;

 来实现由当前元素转移到下一元素，结果：

十一、指定元素的前驱与后继

前驱：

 

Status PriorElem(Sqlist& L, Poly e_current, Poly& e_prior)
{
    int i = 0;
    if (!&L || L.elem[i] != e_current)
        //L存在且e_current不是第一个元素
        cerr << "无意义" << endl;
        return false;
    while (L.elem[i] != e_current)i++;
    e_prior = L.elem[i - 1];
    return true;
}

后继：

Status NextElem(Sqlist& L, Poly e_current, Poly& e_next)
{
    int i = L.length - 1;
    if (!&L || L.elem[i] != e_current)
        //L存在且e_current不是最后一个元素
        cerr << "无意义" << endl;
        return false;
    while (L.elem[i] != e_current)i--;
    e_next = L.elem[i + 1];
    return true;
}

十二（附加）、对线性表内部所有元素进行统一同一操作

：对元素进行操作的内容；

例如：我们在这里给实数加一

（1）在函数内部实现：

Status ListTraverse(Sqlist& L)
{
    if (!&L)
        return false;
    int i = 0;
    while (i < L.length-1)
    {
        (L.elem->p)++;
        i++;
    }
    return true;
}

---

（2）在操作函数外部通过构造visit函数（辅助）实现

1、visit函数在结构体内部：

struct Sqlist
{
    Poly* elem;
    int length;
 
    int visit()
    {
        int i = 0;
        while (i < length - 1)
        {
            elem->p++;
            i++;
        }
        return true;
    }
 
};
 
Status ListTraverse(Sqlist& L)
{
    if (!&L)
        return false;
    int visit();
    return true;
}

这样，在修改对线性表的元素的操作时只需修改visit函数即可

2、visit函数在结构体体之外(独立，自成一派)：

struct Sqlist
{
    Poly* elem;
    int length;
};
 
int visit(Sqlist& L)
    {
        int i = 0;
        while (i < L.length - 1)
        {
            L.elem->p++;
            i++;
        }
        return true;
    }
 
Status ListTraverse(Sqlist& L)
{
    if (!&L)
        return false;
    int visit();
    return true;
}

注意：

这里（面）用的结构体不是类，不可能存在说像类一样把成员函数定义在其结构体范围之外 

也不存在在这个地方用什么友元函数

有关于线性表的所有基本操作到此为止，完结撒花

下一节，我们开关于链表的学习