数据结构（其二）--线性表

目录

1. 基本概念

2.线性表的基本操作

3.顺序表

（1）.静态分配

（2）.动态分配

（3）.顺序表的插入与删除（以静态分配为例）（示例代码中包含了一下必要的基本函数）

 （4）.按位序查找、按值查找

4.链表

（1）.单链表

i.单链表（带头结点）的定义

---

1. 基本概念

线性表：

（1）.其中的各个元素，数据类型相同。

（2）.元素之间，有次序。

（3）.都有表头元素和表尾元素。

（4）.除了表头表尾，每个元素都可以找到一个直接前驱和直接后继。

2.线性表的基本操作

表的从无到有

InitList(&L)：初始化一个线性表

DestroyList(&L)：销毁

。

ListInsert(&L, i, e)：插入，在表L的第 i 处插入元素 e

ListDelete(&L, i, &e)：删除，将表L的第 i 处元素删除，并用 e 返回该被删除的元素

。

LocateElem(L, e)：按值查找，在表中查找特定关键字e 的元素，返回的是e 的位序，而非下标

GetElem(L, i)：按位查找，获取表中第 i 个元素的值

。

其他常规操作：

Length(L)：求表长度

PrintList(L)：输出表的所有元素

Empty(L)：判断表是否为空，返回true or false

高度概括，即为，创销与增删改查

3.顺序表

以顺序存储方式储存数据的线性表

（1）.静态分配

#define MAX 10
//顺序表（静态分配）
class SqList
{
public:int data[MAX];int length;
};
//初始化
void InitList(SqList &l)
{for(int i = 0 ;i < 10 ;i++){l.data[i] = 0;}l.length = 0;
}
//打印所有元素
void PrintList(SqList &l)
{for (int i = 0; i < 10; i++)cout << "第" << i << "个数：" << l.data[i] << endl;
}//测验
void test01()
{SqList l;InitList(l);PrintList(l);
}

（2）.动态分配

#define InitSize 10
//顺序表（动态分配）
class SqList
{
public:int* data;		//指示动态分配数组的指针int MaxSize;	//指示最大容量int length;		//指示当前长度
};
//初始化顺序表
void InitList(SqList& l)
{l.data = new int[InitSize];l.MaxSize = InitSize;l.length = 0;for (int i = 0; i < l.MaxSize; i++){l.data[i] = 0;}
}
//增长数组空间
void IncreaseSize(SqList& l, int len)
{int* p = l.data;					//暂存原数组中的数据l.data = new int[10 + len];			//扩展新的数组for (int i = 0; i < l.length; i++)	//将原数据拷贝进新数组中{l.data[i] = p[i];}l.MaxSize = InitSize + len;			//修改数组的状态数据delete p;							//将p释放
}
//打印所有元素
void PrintList(SqList& l)
{for (int i = 0; i < 10; i++)cout << "第" << i << "个数：" << l.data[i] << endl;
}void test01()
{SqList l;InitList(l);PrintList(l);
}

（3）.顺序表的插入与删除（以静态分配为例）（示例代码中包含了一下必要的基本函数）

//插入

bool ListInsert(SqList& l, int d, int e)
{
    if (l.length >= MAX)                        //首先要判断表是否已满、插入是否合法
    {
        cout << "插入失败，已达上限" << endl;
        return false;
    }
        
    if (d < 1 || d > l.length + 1)
    {
        cout << "插入失败,无直接前驱" << endl;
        return false;
    }
    for (int j = l.length; j >= d; j--)         //将插入点之后的元素后移
        l.data[j] = l.data[j - 1];
    l.data[d - 1] = e;                          //插入，因为d指的是第几个数，在数组的换算中要减一
    l.length++;
    return true;
}

//删除
bool ListDelete(SqList& l, int d, int &e)
{
    if (d < 1 || d >l.length)                   //判断删除的位置是否合法
        return false;
    e = l.data[d - 1];                          //暂存删除掉的元素
    for (int j = d; j < l.length; j++)          //将被删除元素之后的元素前移
        l.data[j - 1] = l.data[j];              //此处，必须是j = d，j-1被j覆盖，若j = d-1，则下文的覆盖会变为j 被j+1 覆盖，而j+1在最后有可能会超过数组的最大容量
    l.length--;
    return true;
}

示例代码

#define MAX 10
//顺序表（静态分配）
class SqList
{
public:int data[MAX];int length;
};
//初始化
void InitList(SqList& l)
{for (int i = 0; i < 10; i++){l.data[i] = 0;}l.length = 0;
}
//打印所有元素
void PrintList(SqList& l)
{for (int i = 0; i < 10; i++)cout << "第" << i << "个数：" << l.data[i] << endl;
}
//存入数据
void InputElem(SqList& l, int e)
{int i = 0;while (i < MAX){if (l.data[i] == 0){l.data[i] = e;l.length++;break;}i++;}
}
//获取顺序表长度
int GetLength(SqList l)
{//cout << l.length << endl;return l.length;
}
//插入
bool ListInsert(SqList& l, int d, int e)
{if (l.length >= MAX)                        //首先要判断表是否已满、插入是否合法{cout << "插入失败，已达上限" << endl;return false;}if (d < 1 || d > l.length + 1){cout << "插入失败,无直接前驱" << endl;return false;}for (int j = l.length; j >= d; j--)         //将插入点之后的元素后移l.data[j] = l.data[j - 1];l.data[d - 1] = e;                          //插入，因为d指的是第几个数，在数组的换算中要减一l.length++;return true;
}
//删除
bool ListDelete(SqList& l, int d, int &e)
{if (d < 1 || d >l.length)                   //判断删除的位置是否合法return false;e = l.data[d - 1];                          //暂存删除掉的元素for (int j = d; j < l.length; j++)          //将被删除元素之后的元素前移l.data[j - 1] = l.data[j];              //此处，必须是j = d，j-1被j覆盖，若j = d-1，则下文的覆盖会变为j 被j+1 覆盖，而j+1在最后有可能会超过数组的最大容量l.length--;return true;
}//查看情况
void CheckList(SqList& l)
{PrintList(l);cout << "当前长度为" << GetLength(l) << endl;
}//测验
void test01()
{SqList l;InitList(l);//输入部分数据InputElem(l, 1);InputElem(l, 2);InputElem(l, 3);InputElem(l, 4);CheckList(l);//开始插入if(ListInsert(l, 3, 6))CheckList(l);//开始删除int a = -1;if (ListDelete(l, 2, a))CheckList(l);
}

 （4）.按位序查找、按值查找

        很简单，不多赘述

//判断d的合法性
bool JugdeD(SqList l, int d)
{if (d < 1 || d > l.length)return false;return true;
}//按位序查找
int GetElem(SqList l, int d)
{if (JugdeD(l, d))return l.data[d - 1];return 0;
}//按值查找
int LocateElem(SqList l, int e)
{for (int i = 0; i < l.length; i++){if (l.data[i] == e)       //数组储存的数据，若是类等复杂的数据类型，则需要对等号进行重载return i + 1;}return 0;
}
//其余代码与上文相同
//其中，JugdeD函数可以替换上文插入与删除中对位序合法性的判别————封装

4.链表

以链式存储方式储存数据的线性表

（1）.单链表

i.单链表（带头结点）的定义

//单链表
class LNode
{
public:int data;           //数据域，存放数据LNode* next;        //指针域，指向下一个节点
};
//用using关键字给类起别名，用LinkList指代的是头结点，代表的是整个链表
using LinkList = LNode*;//初始化
bool InitList(LinkList& L)
{L = new LNode();if (L == nullptr)   //如果成立，则说明内存不足，分配失败return false;L->next = nullptr;return true;
}

ii.插入、删除（带头结点）

不带头结点的，要注意头指针的变动，其他的都雷同。 

插入（普通版）

//插入
bool ListInsert(LinkList& L, int i, int e)
{if (i < 1)                          //判断插入位点是否合法[1]——i值的合法性{cout << "i为负数" << endl;return false;}    LNode* p = L;                       //让p与L指向相同的位点，L是指示头指针的，所以L是不能改变的LNode* s = new LNode();             //新的数据储存s->data = e;while (p != nullptr && i != 1)      //由头结点起始，开始遍历寻找对应位点{p = p->next;i--;}if (p == nullptr)                   //判断插入的位点是否合法[2]——i值对应的节点的合法性{cout << "插入位点超出实际长度" << endl;return false;}                     s->next = p->next;                  //开始接轨，顺序不能乱p->next = s;return true;
}

插入（封装版）

//特定节点的后插操作
bool InsertNextNode(LNode* p, int e)
{if (p == nullptr)                   {cout << "插入位点超出实际长度" << endl;return false;}LNode* s = new LNode();s->data = e;s->next = p->next;p->next = s;return true;
}
//插入
bool ListInsert(LinkList& L, int i, int e)
{if (i < 1)                          //判断插入位点是否合法[1]——i值的合法性{cout << "i为负数" << endl;return false;}    LNode* p = L;                       //让p与L指向相同的位点，L是指示头指针的，所以L是不能改变的while (p != nullptr && i != 1)      //由头结点起始，开始遍历寻找对应位点{p = p->next;i--;}return InsertNextNode(p, e);        //被封装了的部分
}