网站jquery上传源代码,wordpress 邀请注册,wordpress自定义管理员头像,网站建设不用虚拟主机目录 例1 矩阵相乘
线性表
2.1 线性表的类型定义
例2-1 求并集 LALA∪LB
例2-2 有序表归并
2. 2 线性表的顺序表示和实现
1#xff0e;构造空表
2#xff0e;插入
3#xff0e;删除
4#xff0e;定位
顺序表的优点#xff1a;
顺序表的缺点#xff1a;
例…目录 例1 矩阵相乘
线性表
2.1 线性表的类型定义
例2-1 求并集 LALA∪LB
例2-2 有序表归并
2. 2 线性表的顺序表示和实现
1构造空表
2插入
3删除
4定位
顺序表的优点
顺序表的缺点
例交替扫描
2. 3 线性表的链式表示和实现 绪论
例1 矩阵相乘
两个方阵相乘Cn×nAn×n × Bn×n
for (i 0; i n; i) {for (j 0; j n; j) {c[i][j] 0;//把新矩阵中的每个数初始化为0方便后续计算新矩阵每位的值for (k 0; k n; k) {c[i][j] c[i][j] a[i][k] * b[k][j];//每次计算第i行第k位上的数和第j列第k位上的数的乘积并进行累加得到新矩阵中第i行第j列上的数}}
}线性表
2.1 线性表的类型定义
基本操作效果InitListL初始化线性表将线性表设置为初始状态比如长度置为 0 等DestroyListL销毁线性表释放线性表占用的内存空间等相关资源ClearListL置空表也就是清除表中已有的元素使表的长度变为 0但保留线性表结构本身以便后续继续使用ListEmptyL判空表判断线性表是否为空若为空返回真通常用 1 表示否则返回假通常用 0 表示ListLengthL求表长返回线性表中当前所包含元素的个数GetElemLie取第 i 个元素将线性表 L 中第 i 个位置的元素值赋给变量 e通过传址 eLocateElemLecompare查找元素根据给定的比较函数 compare在线性表 L 中查找和元素 e 满足比较条件的元素位置比如相等时的首次出现位置等PriorElemLcur_epre_e求前驱元素在线性表 L 中查找元素 cur_e 的前驱元素并将其值赋给 pre_e通过传址 pre_e如果 cur_e 无前驱则按约定进行相应返回比如返回特殊值表示无前驱等NextElemLcur_enext_e求后继元素在线性表 L 中查找元素 cur_e 的后继元素并将其值赋给 next_e通过传址 next_e如果 cur_e 无后继则按约定进行相应返回比如返回特殊值表示无后继等ListInsertLie插入元素将元素 e 插入到线性表 L 的第 i 个位置插入后线性表长度会相应增加ListDeleteLie删除元素删除线性表 L 中第 i 个位置的元素并将被删除的元素值赋给 e通过传址 e删除后线性表长度会相应减少ListTraverseLvisit按照 visit 函数定义的方式遍历表对线性表中的每个元素依次执行 visit 函数指向的操作 例2-1 求并集 LALA∪LB
void union(List La, List Lb)
{int La_len ListLength(La);int Lb_len ListLength(Lb);int e;for (int i 0; i Lb_len; i){GetEleme(Lb, i, e);//把Lb中 i下标的元素放到变量e中if (!LocatList(La, e, equal))//如果La中没有找到和e相同的数ListInsert(La, La_len, e);//把e元素插入到La的最后La的长度再自加}}例2-2 有序表归并
void MergeList(List La, List Lb, List Lc)
{InitList(Lc);int La_len ListLength(La);int Lb_len ListLength(Lb);int i, j, k 0;while (i La_len j Lb_len)//把La和Lb中较小的一个先放入Lc中{GetEleme(La, i, ai);GetEleme(LB, j, Bj);if (ai bj){ListInsert(Lc, k, ai);i;}else {ListInsert(Lc, k, bj);j;}}while (i La_len)//Lb已经遍历完剩下La部分直接插入Lc{GetEleme(La, i, ai);ListInsert(Lc, k, ai);i;}while (j Lb_len)//La已经遍历完剩下Lb部分直接插入Lc{GetEleme(Lb, i, bj);ListInsert(Lc, k, bj);j;}}
2. 2 线性表的顺序表示和实现
顺序表(Sequential List) 用顺序存储的线性表即把线性表的结点按逻辑次序依次存放到一组地址连续的存储单元里 顺序表通过 元素的存储顺序 反映逻辑关系 1构造空表
typedef int Elemtype;//把int类型重命名为Elemtype,想要修改类型时只需改此处
const int maxsize 100;
typedef struct//定义了一个名字叫Sqlist1的数据结构
{Elemtype elem[maxsize];int length;
}Sqlist1;void InitList(Sqlist1* L)//初始化线性表
{l-length 0;
}
2插入
在表的第i0≤i≤n1个位置上插入一个新结点x使长度为n的线性表(a1,…,ai−1,ai,…,an)变为长度为nl的线性表(a1,…,ai−1,x,ai,…,an)。
先将表中位置in上的结点全部后移一位以空出第i个位置然后在该位置上插入新结点x最后表长加1。 注意移动只能从后向前进行即按n,n−1,…,i的次序进行。 int ListInsert(Sqlist* L, ElemType x, int i)//在顺序表L中的第i个位置插入x
{int jifL-n maxsize//判满{ cout 表满不能插入上溢\n;//cout 相当于print是打印的意思return -1; }if (i0 || i L-n 1)//判位{cout 非法插入位置\nreturn 0}//插入操作for (j L-n; j i; j--)L-elem[j] L-elem[j - 1];//把i位置前的数后移L-elem[i - 1] x;//插入x第i个位置的下标是i-1L-n;//表长加一return 1//修改成功}平均时间复杂度 3删除
将表的第i1≤i≤n个结点删去使长度为n的线性表(a1,…,ai−1,ai,ai1,…,an)变为长度为n−1的线性表(a1,…,ai−1,ai1,…,an-1)。
先将表中位置i1n上的结点全部前移一位以填补删除操作造成的空缺。最后表长减1。 注意移动只能从前向后进行即按 i1, i2, …, n 的次序进行。 int ListDelete(Sqlist* L, int i)
{int j;if (L-length 0)//判空cout 表空不能删除下溢\nreturn -1if (i1 || i L-n)//判合法删除cout 非法删除位置\nreturn 0for (j i 1; j L-n; j)//把i位置的后面的数依次前移覆盖掉i位置的数L-elem[j - 2] L-elem[j - 1];//为什么是L-elem[j-2] L-elem[j-1];//“第i个位置”对应i-1下标因为只有第一、二……个位置的说法即i从1开始计数,而下标是从0开始的//删掉“第i个位置”上的数相当于用后一位数覆盖i位置上的数后面剩下的数往前移 补空位//循环控制变量 j 需要从要删除元素位置的下一个【位置】开始也就是 i 1 开始然后依次把 j 【位置】的元素往前移动一位赋值给 j - 1 【位置】//因此j【位置】的数组【下标】是j-1j-1【位置】的数组【下标】是j-2L-n--;//修改表长return 1;}4定位
求表L中第一个值为x的结点的序号当不存在这种结点时结果为0。因此可从前向后比较各结点的值是否等于x。
int LocatElem(Sqlist* L, int x)
{int ifor (i 1; i L-ni)if (elem[i - 1] x) return i;//找到else return 0;//未找到
} 顺序表是线性表最简单的一种存储结构 顺序表的优点
1 无需为表示逻辑关系而增加额外的存储空间(物理顺序可反映逻辑关系)
2.可随机存取任一元素i, l.elem (i-1)sizeof(type)p;a[];
3.方法简单(各种高级语言都有数组类型)。
顺序表的缺点
1.插入、删除会引起大量元素移动
2.空间预(静态)分配有浪费或不足问题。
例交替扫描
已知顺序表结点值有正有负使负值结点位于顺序表的前面部分正值结点位于顺序表的后面部分。
方法1对顺序表从前向后搜索或称扫描遇到正值结点就将它插入到表的后部或从后向前搜索遇到负值结点就将它插入到表的前部。但顺序表上插入或删除不方便要移动大量结点效率不高。
方法2由表的两端向中间交替扫描即先从前向后扫描找到一个值为正的结点再从后向前扫描找到一个值为负的结点然后交换两者的内容。接着再从这两个位置开始继续进行同样的过程直到两个扫描方向相遇整个表扫描处理完毕。这样就避免了大量结点的移动问题。
void order(Sqlist *L)
{Elemtype x;
int i0;
int jL- length-1;
while(ij){while(ij L- elem[i]0) i;//从前往后找正数while(ij L- elem[j]0) j--;//从后往前找负数if(ij)//交换{ x L- elem[i];L- elem[i] L- elem[j];L- elem[j] x;i;j--;}}
}
2. 3 线性表的链式表示和实现
链表 (Linked List) 用链式存储的线性表即用一组任意的存储单元存储线性表的各个数据元素相互间的逻辑关系(前趋或后继)通过附加指针表示所有结点通过指针域链接在一起构成一个链表。 元素之间的逻辑关系通过附加指针表示 结点可以连续可以不连续 结点的逻辑顺序与物理顺序可以不一致。
2.3.1 单链表
单链表(Singly Linked List)每个结点有两部分信息数据域存放结点的值内容指针域亦称链域存放结点后继的地址或位置。由于每个结点只有一个链域故得名。 概念解释
空指针不指向任何结点;头指针单链表第一个结点的地址; 单链表由头指针唯一确定 头指针具有标识单链表的作用 单链表常用头指针命名如 head 表。头结点单链表第一个结点前人为增加的结点不存放数据。 作用1、简化链表操作统一空表与非空表 2、有时可将头结点看成0号结点 创建结点
typedef int ElemType;//给int类型起了一个别名ElemTypetypedef struct LNode{//结点中的两个成员变量
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//通过typedef为struct LNode结构体定义了两个别名
//一个是LNode可以直接用来声明结构体变量等同于使用struct LNode
//另一个是*LinkListLinkList通常用于表示指向链表头节点的指针类型LinkList head,p;// head 和 p 是两个指针变量等价于LNode *head , *p 结点的动态分配与释放
//动态分配
p new LNode;//方法一
p (LinkList) malloc(sizeof(LNode));//方法二//malloc用于在堆内存中动态分配指定字节大小的内存空间
//它的参数sizeof(LNode) 计算了LNode 类型所占用的字节大小
//然后malloc 函数会在堆上找到一块对应大小的空闲内存块
//并返回指向这块内存起始地址的指针该指针类型为void *即无类型指针
//由于需要将其赋值给LinkList 类型的指针p
//所以进行了强制类型转换(LinkList)//释放
delete p;//方法一
pNULL;//方法二
free(p);//方法三
1插入(无头结点)
情况一在空表上、首结点前插入 s new LNode;//产生一个新节点
s-data x;//把x赋到数值域中
s- next head;//把s和head头结点地址赋给s
heads;//s就成了头结点
情况二在中间结点、尾结点后插入
snew LNode;
s-data x;
s-next p -next;//先把后面的链子接上
p-next s; //再链接前面的注意指针修改顺序先改变本身指针域后改变指向本身的指针域。 1插入(有头结点)
情况一插入到任意结点后 s new LNode;
s - data x;
s- next p -next;//先链接上后面
p-next s;//再链接上前面
情况二插入到第i结点前 思路
查找第 i-1个结点建立新结点修改第 i-1个结点和新结点的指针。 不需移动结点只需修改有关指针 需从表头开始顺序查找插入位置 int insert(LinkList head, ElemType x, int i) {LinkList q, s;q LocateElem(head, i - 1);//找到第i-1结点的地址if (q 0) {//无第i-1位置的结点即i1 || i (LinkList-length)cout 非法插入位置\nreturn 0}s new LNode;//生成新结点s-data x;s-next p-next;//新点的后继是原第i个点p-next s; //原第i−1个点的后继是新点return 1;//插入成功
}
1等效插入在*p之前 前插 不用找前趋的前插
新结点插在当前点*p后交换两结点内容 逻辑上与原来在*p之前插入等效。 //正常把s节点插入通过和前一个节点互换数值从而在逻辑上实现“前插”
s new LNode;
s-data p-data;//把p中数值放到s中
s-next p-next;//s链接后面的结点
p-next s;//s链接前面的节点
p-data x;//把s的值放入p中
2删除(无头结点)
情况一删除首结点 phead;//记录头结点
headhead-next;//把下一个结点设为头结点
delete p;//删除原头结点
情况二删除中间结点、尾结点 q-next p-next;
delete p;
2 删除(有头结点)
删除任意结点 q-next p-next;
delete p;
2删除第i结点(等效删除) 思路
查找链表的第 i-1个结点设q指向它 p指向第i个结点修改第 i-1个结点的后继指针使其指向第i个结点的后继释放第i个结点空间
int delete(LinkList head, int i) {LinkList p, q;q LoacteElem(head, i - 1);//找待删点的前驱if (q NULL || q-next NULL) {cout 非法删除位置\nreturn 0;}p q-next;//保存一份待删点的地址q-next p-next;//修改前趋的后继指针delete p;//释放结点return 1;//删除成功}
(3) 建表(头插法)
从空表开始反复读入数据: 生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的前端
直到读入结束符为止。 LinkList create() {//创造头结点LinkList head, s;char ch;head new LNode;//创造头结点while (cin ch, ch ! $) {s new LNode;//创造结点s-next head-next;s-data ch;head-next s;}return head;
} (3)建表(尾插法)
从空表开始反复读入数据
生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的尾端
直到读入结束符为止。 LinkList create()//尾插法建表有头结点
{LinkList head, rear, s;char ch;head new LNode;//生成头结点说明是空表rear head;//第一个结点既是头结点也是尾结点while (cin ch, ch ! $)//这是一个逗号表达式最后一条语句的结果就是的结果cin类似scanf把键盘输入的值传入变量ch中{s new LNode;s-data ch;//生成新节点rear-next s;rear s;//用rear标识尾结点}raer-next NULL;//尾结点的后继为空return head//链表的头结点可以标识一整个链表
}(4)初始化
建立一个只有头结点的空表
LinkList initlist()
{ LinkList head;headnew Lnode;head−nextNULL;return head;
} (5)求表长 int ListLength_L(LinkList L)
{int j 0;LinkList p;p L-next;//从首结点开始//从首结点开始是 p L-next 而不是 p L 的原因:
//在常见的链表实现中尤其是带头结点的链表头结点主要起到一个 “标识” 作用
//它本身通常并不存放实际要处理的数据元素
其 next 指针才指向链表中的第一个真正存有有效数据的节点也就是首结点。while(p !NULL)//逐点检测、计数{j;p p-next;}return j;
}
(6)按值查找
LinkList LocateElem_L(LinkList L, ElemType x)
{LinkList p;p L-next;//从首结点开始搜索 注意不是头结点是首结点while (p ! NULL){if (p-data x) return p;//找到了立即终止函数并返回查找节点的地址p p-next;//没找到继续找}return NULL;//PNULL了都没找到
} 注意返回结点号,头结点视为0号 (7)按序号查找(定位)
LinkList GetElem_L(LinkList L, int i)
{int j;LinkList p;if (i0 || i L-length) {cout 位置非法无此结点\nreturn NULL;}j -1;p head;while (p ! NULL){j;if (j i) break;p p-next;}return p
}
//为什么j要从−1开始//一般情况下链表的节点位置计数是从 1 开始//指针p是从链表的头结点开始搜索的,然而头结点本身在实际数据节点计数时不算在内算作0位置//进入while循环时先j,刚好j为0标识0位置的头结点//当p第一次移动时再变为 1正好和实际数据节点从 1 开始计数的方式相对应
例 单链表求和
ElemType sum(LinkList L)
{LinkList p L-next;ElemType sum 0;while (p ! NULL){sum p-data;p p-next;}return sum;}例 单链表清空 void DeleteAll(LinkList L)
{LinkList p, q;p L-next;while(p ! NULL){q p;//记录待删点p p-next;//p继续往后走delete q;//释放空间}L-next NULL;//只剩头结点了后驱置空}
例 单链表逆置 思路 对每个结点*p将其next改指其前趋*q修改*p的next后将不能从*p搜索到其后继所以修改前先 将其后继*r的位置保留起来。 原首结点成为尾结点其next应为NULL为使该结点的处理与其它结点一致可在算法开始时将其前趋置为NULL而不是head。头结点的next指向原尾结点。 void reverse(LinkList head)
{LinkList q, p, r;p head-next;//因为 head 通常是头结点head-next 才指向链表中第一个存有有效数据的节点q NULL;//用q来标记p的前一个结点while (p ! NULL)//用p来遍历链表{r p-next;//用r来记录当前结点的后驱p-next q;//把p的后驱指向前一个结点此时p原来的后驱就丢失了,而r刚好记录q p;//用q记录pp继续向后走p r;//r记录了p的后驱此时q相当于前一个结点}
} 例 链表合并
将两个递增有序线性链表归并成一个非递减有序表。 原理将两表当前结点中较小的尾插到新表 LinkList merge(LinkList A, LinkList B)
{LinkList p, q, r, head;head new Lnode;r head;p A-next; q B-next;while (p ! NULL q ! NULL)//当pq都没有到末尾时if (p-data q-data) //如果A链表数据更小{ r-next p; //新链表的下一个结点就是pr p; //用r标识新链表中的 当前结点p p-next;//A中p前进一位}else { r-next q; //否则B中数据大r q;q q-next; }if (p ! NULL) r-next p;//如果A链表还没被遍历完新链表直接接上A剩下的结点if (q ! NULL) r-next q;//如果B链表还没被遍历完新链表直接接上B剩下的结点delete A;delete B;
}小结
单链表是线性表的一种链式存储结构线性链表的特点:
通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系插入、删除操作通过修改结点的指针实现不能随机存取元素
