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

目录

各操作的代码实现：

一、初始化

(1)：使用引用：

1.模板：

2.具体实例：

 (2)：使用指针：

1.模板：

2.具体实例：

---

位置：PPT第二章：46 

---

关于ElemType的解释说明：

struct SqList
{
    ElemType data[maxsize];
    int length;
};

其中ElemType表示：线性表中的元素的类型

可以是基本数据类型，例如：char，float...：

struct SqList
{
    int data[maxsize];
    int length;
};

也可以是自己自定义的数据结构类型

如果线性表中的元素的类型为基本数据类型，但是一定想用ElemType，可以将其定义成基本数据类型：

typedef int ElemType;
struct SqList
{
    ElemType data[maxsize];
    int length;
};

---

位置：PPT：62；

各操作的代码实现：

一、初始化

解释说明： 

Init：

initialize；使初始化；

Sq(l):

Sequential List；顺序表；

！： 逻辑非运算

L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));

详见：PPT：47；

如果初始化成功：返回OK，最终返回1；

如果初始化失败：返回OVERFLOW，最终返回-2；

---

我自己写的代码实例：

注：前置准备

#include
#include//OVERFLOW,exit
#define OK          1
struct Poly
{
    float p;
    int e;
};
 
struct Sqlist
{
    Poly* elem;
    int length;
};

要真的不嫌麻烦的话，也可以写成：

//#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;
};

---

(1)：使用引用：

1.模板：

//(1)：使用引用<模板>
函数类型 InitList(Sqlist& L)
{
    L.elem = (表中数据基本单位类型)malloc(MAXlength * sizeof(表中数据基本单位类型));
    //C语言写法,C++写法如下：
    //L.elem = new 表中数据基本单位类型[MAXlength]; //在堆区开辟动态内存
    if (!L.elem)//分配失败        
        exit(OVERFLOW);
    L.length = 0;
    return OK;
}

如果不想写头文件“#include//存放exit”，也可以把exit改成cerr：

//(1)：使用引用<模板>
函数类型 InitList(Sqlist& L)
{
    L.elem = (表中数据基本单位类型)malloc(MAXlength * sizeof(表中数据基本单位类型));
    //C语言写法,C++写法如下：
    //L.elem = new 表中数据基本单位类型[MAXlength]; //在堆区开辟动态内存
    if (!L.elem)//分配失败     
        cerr << "error" << endl;  //cerr：常被用于输出出错信息，类似cout  
    L.length = 0;
    return false;
 
} 

2.具体实例：

//(1)：使用引用<实例>
Status InitList(Sqlist& L)//前面定义过了typedef int Status;
{
    L.elem = new Poly[100]; //在堆区开辟动态内存
    if (!L.elem)//分配失败        
        exit(OVERFLOW);
    L.length = 0;
    return OK;
}
 
int main()
{
 
}

在这里，真正用于开辟空间、初始化的语句，其实只有一句：

    L.elem = new Poly[100]; //在堆区开辟动态内存

关于这个语句的具体详细解释：

其实我们这里，即：

（为新建的变量）new（开辟）一块Poly类型的数组空间（以数组的形式存储）

值得注意的是：

在这里，为我们并没有进行开辟一个线性表的操作，而是进行一个指定接收指针为elem>的new语句操作

注：

L.elem代表线性表内的，一个指向（的目标变量为）Poly（复数，复合）类型的指针elem；

（element：元素）

---

 (2)：使用指针：

1.模板：

//(2)：使用指针<模板>
/*初始化线性表*/
Status InitList(Sqlist* L)
{
    L->elem = (表中数据基本单位类型*)malloc(MAXlength * sizeof(表中数据基本单位类型*));
    if (!L->elem)
        exit(OVERFLOW);
    L->length = 0;
    return OK;
}

2.具体实例：

//(2)：使用指针<实例>
/*初始化线性表*/
Status InitList(Sqlist* L)
{
    L->elem = (Poly*)malloc(MAXlength * sizeof(Poly*));
    if (!L->elem)
        exit(OVERFLOW);
    L->length = 0;
    return OK;
}
 
int main()
{
 
}
 
//#define MAXlength 100  //初始大小为100，可按需修改

同样的，这里真正用于开辟空间、初始化的语句，即：

    L->elem = (表中数据基本单位类型*)malloc(MAXlength * sizeof(表中数据基本单位类型*));
    L->elem = (Poly*)malloc(MAXlength * sizeof(Poly*));

注：

L->elem代表访问线性表内的，一个指向（的目标变量为）Poly（复数，复合）类型的指针elem；（element：元素）

---

关于new语句的使用规范，详见：

数据结构与算法基础（王卓）（8）附：关于new的使用方法详解_宇 -Yu的博客-CSDN博客

---

另外，如果时间允许有兴趣的话，可以看看：

 数据结构与算法基础（青岛大学——王卓） note_Tarench的博客-CSDN博客中

可见另一套系统完整的基本操作实现过程，这里不再赘述，只写我自己写的比较简化的代码和我对其头文件新增了注解的新头文件代码段：

#pragma once
//函数结果状态代码
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE  -1
#define LOVERFLOW   -2   //中已有OVERFLOW，因此换一下
 
#define LIST_INIT_SIZE 100  //初始大小为100，可按需修改
#define LISTINCREMENT 10    //空间分配增量，课按需修改；increment：增加，增长;上涨；提高;增量;
 
typedef int Status;         //函数调用状态
 
#define ELEMTYPE_IS_INT     //数据类型
//#define ELEMTYPE_IS_DOUBLE
//#define ELEMTYPE_IS_CHAR_ARRAY
//#define ELEMTYPE_IS_CHAR_P
//#define ELEMTYPE_IS_STRUCT_STUDENT
//#define ELEMTYPE_IS_STRUCT_STUDENT_P
 
#ifdef ELEMTYPE_IS_DOUBLE
typedef double ElemType;
#elif defined (ELEMTYPE_IS_CHAR_ARRAY)
typedef char ElemType[LISTINCREMENT];
#elif defined (ELEMTYPE_IS_CHAR_P)
typedef char* ElemType;
#elif defined (ELEMTYPE_IS_STRUCT_STUDENT)
typedef struct student {
    int num;
    char name[LISTINCREMENT];
    char sex;
    float score;
    char addr[30];
}ElemType;
#elif defined (ELEMTYPE_IS_STRUCT_STUDENT_P)
typedef struct student {
    int num;
    char name[LISTINCREMENT];
    char sex;
    float score;
    char addr[30];
}ET, * ElemType;
#else
    typedef int ElemType;
#endif
 
typedef struct {
	ElemType* elem;
	int length;
	int listsize;
}sqlist;
 
/*函数声明*/
Status InitList(sqlist* L);  //构造一个空的线性表L
Status DestroyList(sqlist* L);  //销毁线性表L
Status ClearList(sqlist* L);  //将线性表L置为空表
Status ListEmpty(sqlist L);  //若L为空表返回TURE，否则返回FALSE
int ListLength(sqlist L);  //返回L中数据元素个数
Status Getelem(sqlist L, int i, ElemType* e);  //用e返回L中第i个数据元素的值
int LocateElem(sqlist L, ElemType e, Status(*compare)(ElemType e1, ElemType e2)); 
//返回L中第一个与e满足关系compare()的数据元素的位序，若不存在，返回0
Status PriorElem(sqlist L, ElemType cur_e, ElemType* pre_e, Status(*compare)(ElemType e1, ElemType e2));  //用pre_e返回cur_e的前驱
Status NextElem(sqlist L, ElemType cur_e, ElemType* next_e, Status(*compare)(ElemType e1, ElemType e2));  //用next_e返回cur_e的后驱
Status ListInsert(sqlist* L, int i, ElemType e);  //在L的第i个位置插入元素e
Status ListDelete(sqlist* L, int i, ElemType* e);  //删除L的第i个元素，并用e返回其值
Status ListTraverse(sqlist L, Status(*visit)(ElemType e));  //依次对L的每个数据元素调用visit()函数

---

剩下的其他操作，我们下一讲继续