北京怎样做网站推广,广告设计公司业务范围,模板网优酷,黄冈做网站技术支持的目录 1. 基本概念
2.线性表的基本操作
3.顺序表
#xff08;1#xff09;.静态分配
#xff08;2#xff09;.动态分配
#xff08;3#xff09;.顺序表的插入与删除#xff08;以静态分配为例#xff09;#xff08;示例代码中包含了一下必要的基本函数#xf…目录 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 dj-1被j覆盖若j d-1则下文的覆盖会变为j 被j1 覆盖而j1在最后有可能会超过数组的最大容量 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 dj-1被j覆盖若j d-1则下文的覆盖会变为j 被j1 覆盖而j1在最后有可能会超过数组的最大容量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); //被封装了的部分
}
