西安网站搜索引擎优化,网络营销推广的方式有哪些?,sem seo,北京门户网站建设语言#xff1a;C语言软件#xff1a;Visual Studio 2022笔记书籍#xff1a;数据结构——用C语言描述如有错误#xff0c;感谢指正。若有侵权请联系博主
一、线性表的逻辑结构 线性表是n个类型相同的数据元素的有限序列#xff0c;对n0#xff0c;除第一元素无直接…语言C语言软件Visual Studio 2022笔记书籍数据结构——用C语言描述如有错误感谢指正。若有侵权请联系博主
一、线性表的逻辑结构 线性表是n个类型相同的数据元素的有限序列对n0除第一元素无直接前驱、最后一个元素无直接后继外其余的每个元素只有一个直接前驱和一个直接后继。 线性表逻辑结构 线性表的特点
同一性。线性表由同类数据元素组成每一个aⁱ必须属于同一数据类型。有穷性。线性表由有限个数据组成表长度就是表中数据元素的个数。 有序性。线性表中相邻数据元素之间存在着序偶关系aⁱaⁱ1
由此可以看出线性表既是一种最简单的数据结构数据元素之间由前驱/后继直观、有序的关系确定又是一种常见的数据结构矩阵、数组、字符串、堆栈、队列等都符合线性条件。
二、线性表的抽象数据定义
线性表的抽象数据类型定义如下
ADT LinearList{数据对象D{aⁱ|aⁱ∈D₀,i1,2,...,n,n≥0,D₀为某一数据对象}结构关系R{aⁱ,aⁱ1|aⁱ,aⁱ1∈D,i1,2,...,n-1}基本操作1.InitList(L)操作前提L为未初始化线性表。操作结果将L初始化为空表。2.ListLength(L)操作前提线性表L已存在。操作结果如果L为空表则返回0否则返回表中的元素的个数。3.GetData(L,i)操作前提表L存在且1≤i≤ListLength(L)。操作结果返回线性表L中第i个合法元素的值。4.InsList(L,i,e)操作前提表L已存在e为合法元素值且1≤i≤ListLength(L)1。操作结果在L中第i个位置之前插入新的数据元素eL的长度加1。5.DelList(L,i,e)操作前提表L已存在且非空1≤i≤ListLength(L)。操作结果删除L的第i个数据元素并用e返回其值L的长度减1。6.Locate(L,e)操作前提表L已存在e为合法数据元素值。操作结果如果L中存在数据元素e则返回e在L中的位置否则返回空位置。7.DestroyList(L)操作前提线性表已存在。操作结果将L销毁。8.ClearList(L)操作前提线性表L已存在。操作结果将L置为空表。9.EmptyList(L)操作前提线性表L已存在。操作结果如果L为空表则返回TRUE否则返回FALSE。
}ADT LinearList; 以上仅为一个抽象数据类型。因为一个抽象数据类型仅是一个模型的定义并不设计模型的具体实现因此这里使用参数不考虑具体类型。在实际问题中对线性表的运算可能很多例如有时需要将多个线性表合并成一个线性表以及在此问题基础之上进行的有条件合并等。像合并分拆/复制/排序等复合运算问题都可以利用基本运算的组合来实现。 三、线性表的链式存储结构的概念及单链表
1、概念 链式存储是最常用的动态存储方式。为了克服顺序表的缺点可以采用链式存储。通常将采用链式存储结构的线性表称为线性链表。从链式方式的角度来看链表可分为单链表、循环链表和双链表从实现方式角度链表可分为动态链表和静态链表。 2、单链表 在顺序表中是用一组地址连续的存储单元来依次存放线性表的节点因此节点的逻辑顺序和物理顺序是一致的。而链表则是用一组任意的存储单元来存放线性表的节点这组存储单元可以是连续的也可以是非连续的甚至是零散分布在内存的任何位置上。因此链表中节点的逻辑顺序和物理顺序不一定相同。为了正确的表示节点间的逻辑关系必须在存储线性表的每个数据元素值得同时存储指示其后继节点的地址信息这俩部分组成的存储映像称为链表节点。 链表的节点包含俩个域数据域用来存储节点的值指针域用来存储数据元素的直接后继地址。线性链表正是通过每个节点的指针域将n个节点按逻辑顺序链接在一起。每个节点只有一个next指针域的链表称为单链表其结果如下图所示 单链中每个节点的存储地址存放在其前驱节点的指针域中由于线性表中第一个节点无前驱所以应设一个头指针H指向第一个节点由于线性表的最后一个节点没有直接后继则指定单链表的最后一个节点的指针域为“空”(NULL)。 单链表的头指针H标示着整个单链表的开始习惯上用头指针代表单链表。给定单链表的头指针H即可顺着每个节点的next指针域得到单链表中的每个元素。单链表的逻辑顺序如下图所示 单链表的逻辑状态 为了统一、方便可以在单链表的第一个节点之前附设一个头节点。而头节点的指针域则用来存储指向第一个节点的指针即第一个节点的存储位置。此时头指针就不在指向表中第一个节点而是指向头节点。如果线性表为空表则头节点的指针域为“空”。逻辑如下图所示 带头节点的单链表图示 四、线性表的链式存储结构的具体实现单链表
1、单链表的存储结构的表示
typedef struct Node //定义一个结构体 这个结构体的名字叫Nodetypedef:用一个新的类型名代表原来的数据类型名即用Node代表整个结构体类型
{ElemType data; //ElemType代表的是应该存储的数据的类型可以是char,int,数组结构体等等struct Node* next; //定义指向单链表中结点的指针
}Node,*LinkList; //LinkList为结构体指针类型 说明LinkList与Node *同为结构体指针类型这俩种类型是等价的。习惯上用LinkList定义指向某个单链表的头指针变量例如定义LinkList L则L为指向单链表的头指针变量用Node*定义指向单链表中结点的指针例如Node *p则p为指向单链表中节点的指针变量。 2、初始化单链表InitList(L) 算法思想先用malloc为头指针开辟空间。malloc后边括号表示想要开辟空间的大小这里用sizeof运算符获取结构体的内存空间开辟刚好够的空间malloc前边括号是强制类型转换因为malloc返回值类型为void*为了让他成为想要的类型就需要在前边进行强制类型转换。malloc函数要导入stdlib.h头文件代码就是#include stdlib.h
为了放置内存泄漏malloc开辟的空间如果不用了需记得用free()函数释放开辟的空间
/*初始化单链表*/
int InitList(LinkList *L) {*L (LinkList)malloc(sizeof(Node));(*L)-next NULL; //将指针指向的地址置空return 0;
} 第二行传入的参数是个指针这个指针存的数据是一个结构体指针。这个有点复杂相当于把链表的头指针放到一个盒子里而这个头指针本身就是一个盒子。 第三行为这个指针地址里的的值开辟空间 即为盒子里的盒子开辟一个空间。 第四行将指针指向的结构体的指针域置空。不能理解的 去看看前边关于链表结构的说明。 第五行结束函数 返回结果0。 3、返回线性表中元素的个数ListLength(L)
算法思想采用“数”结点的方法求出带头结点单链表中元素个数长度,即从头开始“数”(rr-next),用指针r依次指向各个结点并附设计数器i计数一直数到最后一个结点即p-nextNULL从而的到单链表的长度。
/*返回线性表中元素的个数*/
int ListLength(LinkList L) {Node *r;r L; int i 0;while (r-next ! NULL) {r r-next;i;}return i;
} 第三行定义一个节点指针变量用于遍历时存储节点从而判断节点中的指针域是否为空从而达到‘数’有多少个数据。 第四行将头结点赋值给定义的变量遍历时改变定义的变量从而不需要去破坏原有数据。它可以和第三行合并。 第五行定义一个计数器个数为0。 第六行while循环 不满足条件结束循环即节点中的指针域为空结束循环这括号里的意思是不等于空即为真执行循环等于空结束循环。 第七行更新节点指针变量的值使指向下一个节点。 第八行每执行一次循环计数器1。 第十行函数结束 返回元素个数。 这个函数时间足够的话细细研究一下他是思路链表中的一个关键实现方式思考一下如果将首元节点赋值给r即rL-next循环条件咋设置i的初始值咋设置。 4、返回线性表中第i个合法元素的值GetData(L,i)
算法思想先定义一个结构体指针变量用于存放传入进来的链表要不然一乱赋值整个链表都乱了。定义一个计数器i用于看是否到指定位置。先判断输入地址是否合法即要在0-ListLength(L)内这个边界一定要注意。元素个数是从第一个开始的地址下标才是从0开始的。若合法在进行遍历位于第几个即循环执行链表指针移动多少次最后遍历到的就是存放那个位置的数据。
ElemType GetData(LinkList L,int i) {Node* r;int j0;r L;if ((i ListLength(L)) || i 0) {printf(返回位置不合法);return 0;}for (; j i; j) {r r-next;}printf(第%d个元素是%c,i,r-data);return r-data;
} 第二行声明一个节点结构体指针变量。 第三行声明一个计数器并赋值为0。 第四行为声明的结构体指针赋值便于后边操作链表而不至于破坏链表内数据。 第五行判断寻找的元素是否合法即要在0~链表长度范围内。 第六行用于观察代码执行情况可不要 第七行如果寻找的元素不合法直接结束函数 返回0 第九行for循环遍历寻找第i个数据即循环i次 第十行一层层往后走直到结构体指针变量中存的是第i个节点。 第十二行便于观察函数执行情况可不要。 第十三行将i节点中的数据域内数据作为函数结果返回。 5、将新的元素e插入表尾InsListEnd(L,e)
这个代码和书上给的代码不一样书上给的是连续插入这是另外一个思路不想了解的可以略过这个可以用InsList插入到最后实现。
算法思想定义俩个结构体指针变量一个用于存放新插入的数据一个用于定位指针。为存放新插入的数据的指针变量开辟空间将值存入因为在表尾将指针域置空。将传入的链表头传入定位指针移动定位指针直到最后一个结点即指针域为空再将新的结点插入到后边。
/*将新的元素e插入表尾*/
int InsListEnd(LinkList L, ElemType e) {Node* s (LinkList)malloc(sizeof(Node)),*r;s-data e;s-next NULL;r L;while (r-next ! NULL) {r r-next;}r-next s;return 0;
} 第三行定义一个节点指针变量s赋值时这里用了malloc函数它是C语言中开辟堆内存的函数它前边的括号内是强制类型转换将开辟的空间转换成LinkList类型它后边的括号是开辟的空间大小这里用sizeof运算符获取这个节点应该需要多大的内存空间。后边还声明了另一个节点指针变量r但并为其赋值。 第四行将需要存入的数据放入为其新开辟的节点中的的数据域中。 第五行因为是表尾插入所以后续没有新的节点故将指针域置空。 第六行将链表L的头节点值赋值给声明的指针变量r当做指针指向相应的节点。 第七行判断该节点的指针域是否为空为空结束循环。为啥要用为空来判断嘞因为要把新的数据插入表位单向链表中只有最后一个节点的指针域为空 借此来判断是否遍历到最后一个节点。 第八行更新指针变量r中的值将当前节点的下一节点值赋值给r。 第十行当循环结束时r中存放了最后一个节点故只需要将新的节点的地址赋值给r中的指针域即可。 第十一行结束函数 返回结果0。 6、将新的元素e插入表头InsListStrat(L,e)
算法思想创建一个指针变量为指针变量开辟存储空间将值赋给创建的变量中的数据域再将头结点中存的地址值赋给创建的变量的指针域最后将地址赋给头指针。变化示意图如下所示 示意图 /*将新的元素e插入表头*/
int InsListStart(LinkList L, ElemType e) {Node* r (LinkList)malloc(sizeof(Node));r-data e;r-next L-next;L-next r;return 0;
} 第三行同上第三行 第四行将需要存入的数据存入新开辟的节点中。 第五行将首元节点的地址即头节点中的指针域赋值给新开辟的节点的指针域中相当于图中断开链的那一步。 第六行将新开辟的节点地址赋值给头结点的指针域 相当于图中重新连接的那一步。 第七行函数结束 返回结果0。 7、在第i个地方插入一个新的数据元素 InsList(L,i,e)
算法思想1.判断判断插入地址是否在线性表长度范围内
2.查找在单链表中找到第i-1个结点用于p指针指示
3.申请申请新的结点s将数据域的值置为e
4.插入通过修改指针域将新结点s挂入单链表L
/*在第i个地方插入一个新的数据元素*/
int InsList(LinkList L, int i, ElemType e) {if (i 0 || i (ListLength(L)1)) {printf(插入地址不合法建议使用LinkList()函数查看一下链表的长度);return 0;}Node* r (LinkList)malloc(sizeof(Node)),*p;r-data e;p L;for (int j 0; j (i-1); j) {p p-next;}r-next p-next;p-next r;return 0;
} 第三~六行判断地址i是否合法当小于等于0时是非法比较没用第0个和负几个超过最长长度也不行毕竟如果只有30个你说你要找第31个咋可能有。 第七九行同上第三、四、六行。 第十、十一行遍历循环i次使p中存放的是第i个节点的数据。 第十二行将该节点的指针域内数据赋值给新开辟的节点的指针域中即从该节点断开。 第十三行将新开辟的节点地址存入断开处的指针域中。 不能理解的想象一下小时候玩的老鹰捉小鸡假如有六个人在玩老鹰捉小鸡刚好第三个人是你喜欢的人你就想到她后边你就得先去数数到第三个人然后让她后边的人松开第三个人的衣服来牵着你的衣服即第十二行然后你再去抓住第三个人的衣服即第十三行。 8、删除L的第i个数据元素,并返回第i个元素的值 DeList(L,i)
算法思想1.判断判断需要删除的地址是否合法
2.查找通过循环i-1次将获取需删除元素的前一个结点
3.转移将需删除的结点转移找一个变量中将需删除结点内指针域内数据转移到它前一个结点的指针域中
4.存值将需删除的结点内的值存入一个变量中
5.删除用free函数释放空间最后返回之前存的值
/*删除L的第i个数据元素,并返回第i个元素的值*/
ElemType DelList(LinkList L, int i) {if (i 0 || i ListLength(L)) {printf(删除地址不合法建议使用LinkList()函数查看一下链表的长度);return 0;}Node* r,*pre;ElemType e;r L;for (int j 0; j (i-1); j) {r r-next;}pre r-next;r-next pre-next;e pre-data;free(pre);return e;
} 第三~六行同上三到六行有点细微差别自己思考一下为啥。 第七行声明俩个结构体指针变量一个用于存节点进行删除一个用于遍历节点知道了指向哪个节点了。 第八行声明一个变量用于存储需要删除的节点中的数据域的值也可以不声明用函数的参数带出不过用参数带出需要把参数设置成指针类型。 第九行将头节点赋值给r。 第十十二行for遍历循环到i节点的前一个节点即它的指针域指向的就是i节点之所以在前一个节点停止是为了将i节点的下一节点好放置在该节点要不然按照单向单链表的性质遍历过去了就不能往前走了。 第十三行将i前一个节点的指针域即i节点赋值给存节点的指针变量pre。 第十四行将i中下一节点赋值给i的上一节点的指针域中。至此已将i节点完整取出。 第十五行将i节点中的数据取出。 第十六行是用free函数销毁开辟的堆内存防止内存泄露。 第十七行函数结束 返回结果e即销毁的节点中的数据。 9、按内容查找数据元素 Locate(L,e)
算法思想定义一个计数器j用于计指针所走的结点用while循环遍历内部设置一个指针移动r r-next再设置一个匹配语句和计数语句。
/*按内容查找数据元素*/
int Locate(LinkList L, ElemType e) {Node* r;int j 1;r L;while (r-next!NULL) {r r-next;if (r-data e) {printf(%c为位于数组中%d的位置,e,j);return j;}j;}printf(%c不在数组中,e);return 0;
} 第三行声明一个结构体节点指针。 第四行声明一个计数器并赋值为1为啥要赋值为1嘞因为判断的时候判断的是该节点的指针域去判断的即无论如何都是从第一个开始的。 第五行将头节点赋值给r。 第六行while循环判断下一节点是否为空若为空表示全遍历完了 还是没有。 第七行将节点指向往后移。 第八~十一行将循环中的每个节点中的数据域中的数据和需查找的数据进行匹配匹配成功返回位于第几个。 第十二行计数器 用于计数到第几个了。 10、打印输出顺序表 PrintList(L)
算法思想判断是否为空表因为要[ ]所以最后一个需特殊输出空表直接输出空表提示语句。while遍历循环输出至倒数第二个最后一个特殊输出。注因为最后一个特殊输出不能将r最后赋值为NULL故只能到倒数第二个。我目前只想到这个方法若有好的方法欢迎评论区留言或私信作者
/*打印输出顺序表*/
int PrintList(LinkList L) {if (L-next NULL) {printf(该表是一个空表);return 0;}Node* r;printf([);r L-next;while (r-next ! NULL) {printf(%c,,r-data);r r-next;}printf(%c]\n, r-data);return 0;
} 该函数为自定义的函数用于观察链表中的数据可有可没有不做说明。 11、将线性表L置为空表 ClearList(L)
算法思想将每一个结点逐个遍历逐个销毁空间直至最后一个为空的结点最后将头结点置空。
/*将线性表L置为空表*/
int ClearList(LinkList L) {Node* r, * pre;r L-next;while (r ! NULL) {pre r;r pre-next;printf(销毁%c, pre-data); //查看销毁情况可以不要free(pre);}L-next NULL;return 0;
} 第三行定义两个结构体指针变量用于存储结点已经用于遍历结点。 第四行将首元结点赋值给r。 第五行while循环判断r是否为空即若为空表示遍历到最后一个了。 第六行将r赋值给另一指针变量用于存储某一个结点。 第七行再更改变量r的值。 第八行便于观察程序允许情况可以不要。 第九行销毁拿出来的某一个结点以此循环直至处头节点外所有数据全删除。 第十一行将头结点的指针域置空即为空链表。 12、判断表是否为空 EmptyList(L)
算法思想判断头节点的指针域是否为空即可。
/*判断表是否为空*/
bool EmptyList(LinkList L) {if (L-next NULL) {printf(该表是一个空表);return true;}printf(该表不是一个空表);return false;
} 第三行判断链表是否为空即头节点的指针域是否为空。 第四、五行为空执行的代码最后 返回true。 第七、八行非空执行的代码。 第四、七行可以不要仅仅是为了方便观察程序允许情况。 13、销毁线性表 DestroyList(L)
算法思想先清空表最后把头节点也销毁
/*销毁线性表*/
int DestroyList(LinkList L) {ClearList(L);free(L);return 0;
} 第三行执行线性表置空函数将线性表置空。 第四行销毁头指针。 第五行结束函数返回0。 五、单链表全部代码及每个模块测试
注inputs函数是为了测试而设置的慎用它没有任何错误保障措施也就是有一个出错了直接进入死循环这个函数我自己也没搞懂。故用inputs函数测试的时候别输入离谱的输入否则就会报错。
#include iostream
#include stdlib.h
#define ElemType chartypedef struct Node
{ElemType data;struct Node* next;
}Node,*LinkList;/*初始化单链表*/
int InitList(LinkList *L) {*L (LinkList)malloc(sizeof(Node));(*L)-next NULL;return 0;
}/*返回线性表中元素的个数*/
int ListLength(LinkList L) {Node *r;r L; int i 0;while (r-next ! NULL) {r r-next;i;}return i;
}/*返回线性表中第i个合法元素的值*/
ElemType GetData(LinkList L,int i) {Node* r;int j0;r L;if ((i ListLength(L)) || i 0) {printf(返回位置不合法);return 0;}for (; j i; j) {r r-next;}printf(第%d个元素是%c,i,r-data);return r-data;
}/*将新的元素e插入表尾*/
int InsListEnd(LinkList L, ElemType e) {Node* r;Node* s (LinkList)malloc(sizeof(Node));s-data e;s-next NULL;r L;while (r-next ! NULL) {r r-next;}r-next s;return 0;
}/*将新的元素e插入表头*/
int InsListStart(LinkList L, ElemType e) {Node* r (LinkList)malloc(sizeof(Node));r-data e;r-next L-next;L-next r;return 0;
}/*在第i个地方插入一个新的数据元素*/
int InsList(LinkList L, int i, ElemType e) {if (i 0 || i (ListLength(L)1)) {printf(插入地址不合法建议使用LinkList()函数查看一下链表的长度);return 0;}Node* r (LinkList)malloc(sizeof(Node)),*p;r-data e;p L;for (int j 0; j (i-1); j) {p p-next;}r-next p-next;p-next r;return 0;
}/*删除L的第i个数据元素,并返回第i个元素的值*/
ElemType DelList(LinkList L, int i) {if (i 0 || i ListLength(L)) {printf(删除地址不合法建议使用LinkList()函数查看一下链表的长度);return 0;}Node* r,*pre;ElemType e;r L;for (int j 0; j (i-1); j) {r r-next;}pre r-next;r-next pre-next;e pre-data;free(pre);return e;
}/*按内容查找数据元素*/
int Locate(LinkList L, ElemType e) {Node* r;int j 1;r L;while (r-next!NULL) {r r-next;if (r-data e) {printf(%c为位于数组中%d的位置,e,j);return j;}j;}printf(%c不在数组中,e);return 0;
}/*打印输出顺序表*/
int PrintList(LinkList L) {if (L-next NULL) {printf(该表是一个空表);return 0;}Node* r;printf([);r L-next;while (r-next ! NULL) {printf(%c,,r-data);r r-next;}printf(%c]\n, r-data);return 0;
}/*将线性表L置为空表*/
int ClearList(LinkList L) {Node* r, * pre;r L-next;while (r ! NULL) {pre r;r pre-next;printf(销毁%c, pre-data); //查看销毁情况可以不要free(pre);}L-next NULL;return 0;
}/*判断表是否为空*/
bool EmptyList(LinkList L) {if (L-next NULL) {printf(该表是一个空表);return true;}printf(该表不是一个空表);return false;
}/*销毁线性表*/
int DestroyList(LinkList L) {ClearList(L);free(L);return 0;
}/*通过键盘连续获取值并插入表中*/
int inputs(LinkList L) { int num, chars,i;printf(1.表头插入 2.表尾插入 3.选择位置插入);printf(请输入要插入的方式(数字));for (int n 0; n 5;n) {scanf_s(%d, num);if (num 1 || num 2 || num 3) break;printf(输入错误请在1-3中输入一个数字);}printf(请输入要插入的个数);scanf_s(%d,i);if (num 1) {for (int j 0; j i; j) {printf(请输入第%d个数据,(j1));scanf_s(%c, chars);scanf_s(%c, chars);InsListStart(L, chars);}}else if (num 2) {for (int j 0; j i; j) {printf(请输入第%d个数据, (j 1));scanf_s(%c, chars);scanf_s(%c, chars);InsListEnd(L, chars);}}else {int site;ElemType value;for (int j 0; j i; j) {printf(请输入你要插入的位置);scanf_s(%d, site);printf(请输入你要插入的数据);scanf_s(%c, value);scanf_s(%c, value);InsList(L, site, value);}}return 0;
}int main()
{LinkList *L,list; //list是一个头节点是指针变量L是存放节点的,是存放指针变量的指针变量。L list;InitList(L);printf(---------------------长度为0测试,元素个数、输出测试-------------------\n);printf(元素个数为%d\n, ListLength(list));PrintList(list);printf(\n\n\n--------------------头插法测试、长度获取测试、输出测试-------------------\n);inputs(list);printf(元素个数为%d, ListLength(list));PrintList(list);printf(\n\n\n----------------------尾插法测试、输出测试----------------------\n);inputs(list);printf(元素个数为%d\n, ListLength(list));PrintList(list);printf(\n\n\n---------------------------随机插入测试、输出测试------------------\n);inputs(list);printf(元素个数为%d\n, ListLength(list));PrintList(list);printf(\n\n\n---------------------按位置查找测试---------------------\n);printf(查找第3个值\n);GetData(list, 3);printf(\n查找第0个值\n);GetData(list, 0);printf(\n查找第100个值\n);GetData(list, 100);printf(\n查找第-1个值\n);GetData(list,-1);printf(\n\n\n------------------------按值查找测试---------------------------\n);printf(查找A\n);Locate(list,A);printf(\n查找*\n);Locate(list, *);printf(\n\n\n----------------------------------删除测试-------------------\n);printf(删除第3个位置的值\n);DelList(list, 3);printf(\n删除第100个位置的值\n);DelList(list, 100);printf(\n删除第0个位置的值\n);DelList(list, 0);printf(\n\n\n-------------------------判断表是否为空、置空测试---------------------\n);printf(判断表是否为空\n);EmptyList(list);printf(将表置空\n);ClearList(list);printf(再次判断表是否为空\n);EmptyList(list);printf(\n\n\n-------------------销毁表测试-------------------\n);printf(销毁结果%d,DestroyList(list));
}
测试结果
