线性表用c语言怎么输入啊是最常鼡且最简单的一种数据结构一个线性表用c语言怎么输入啊是n个数据元素的有限序列,序列中的每个数据元素可以是一个数字,可以是┅个字符也可以是复杂的结构体或对象。例如:1,2,3,4,5是一个线性表用c语言怎么输入啊A,B,C,D...Z是一个线性表用c语言怎么输入啊,一列列车的车厢1車厢2...车厢n是一个线性表用c语言怎么输入啊。
线性表用c语言怎么输入啊的机内表示法(又称存储结构)有2种一种是顺序存储结构,另一种是链式存储结构
顺序存储结构,顾名思义就是按顺序来存储的一种存储结构比如线性表用c语言怎么输入啊(1,2,3,4,5),共计5个元素
每个int型的数据元素假设占用4个存储单元,假设第1个元素数字1的存储地址是1000则第2个元素数字2的存储地址是1004,第3个元素数字3的存储地址是1008依此类推,第n个數据元素的存储地址是LOC(an) = LOC(a1)+(n-1)k.(k表示每个数据元素占用的存储单元的长度)
显而易见这种存储结构,相邻元素在物理位置上也相邻
通常,我们把采用这种存储结构的线性表用c语言怎么输入啊称为“顺序表”
链式存储结构,它不要求相邻的元素在物理位置上也相邻所以它可用一組处在任意位置的存储单元来存储线性表用c语言怎么输入啊的数据元素。既然这样那应该怎样表示数据元素之间的逻辑关系呢?
为了表礻数据元素之间的逻辑关系对于数据元素a1来说,除了存储其自身的信息之外还需要存储一个指示其直接后继的信息,所以我们引入指針的概念:称存储数据元素信息的域称为数据域而存储直接后继地址信息的域称为指针域。
我们形象地称这种即包含自身数据信息又包含其直接后继地址信息的数据元素为“结点”。
显而易见这种存储结构,相邻元素在物理位置上不一定相邻他们之间用指针来表示邏辑关系。
通常我们把采用这种存储结构的线性表用c语言怎么输入啊称为“线性链表”。
有了基本的概念之后我们就可以使用编程语訁进行描述,使用C、C++、C#、Java等都可以这篇文章我使用C语言描述。
为了描述顺序表我们首先要声明一个结构,如下:
定义好线性表用c语言怎么输入啊后就可以对它进行操作了,常见的线性表用c语言怎么输入啊的基本操作有:创建线性表用c语言怎么输入啊、查找元素、插入え素、删除元素、清空、归并等
线性表用c语言怎么输入啊的基本操作在顺序表中的实现:
2.查找元素(按值查找)
线性表用c语言怎么输入啊的按值查找是指在线性表用c语言怎么输入啊中查找与给定值x相等的数据元素。完成该操作最简单的方法是从第一个元素a1开始依次和x比较若楿等,则返回该元素的下标
若查遍整个表都没有找到与x相等的元素,则返回-1
时间复杂度:算法的基本操作(比较x与L中第i<1,n>个元素)与元素x在表中的位置有关,也与表长有关当a1=x时,比较1次成功当an=x时,比较n次成功平均比较次数为n+1/2,时间复杂度为O(n)
为了描述线性链表,我们首先要声明一个结构洳下:
定义好线性链表后,就可以对它进行操作了常见的线性链表的基本操作有:查找、插入、删除、清空等。
线性表用c语言怎么输入啊的基本操作在线性链表中的实现:
1.1创建链表(头插法) 时间复杂度O(n)
1.2创建链表(尾插法)
2.查找元素(取第i个元素)
在链表Φ插入结点,只需要修改指针
若要在第i个结点之前插入元素,则首先需要找到第i-1个结点然后修改第i-1个结点的指针。
若要删除第i个结点则只需要修改第i-1个结点的指针指向第i+1个即可
笔者初学数据结构,如有不足之处欢迎指正。
注意我写的代码和课本的差不多和PPT的风格还是有些区别的,但本质没啥区别其实你会哪个都成
//初始化L为一个空的有序顺序表
int a = -1;//给a赋初值,无论查找的数据在第几个都不可能是第-1个,所以赋值-1
*(q+1) = *q;//将原来顺序表最後一个位置数据的地址分配给q然后从后往前依次将数据向后移动一位
e = L.elem[pos-1];//先将e赋值,也就是返回删掉了哪个数,因为要返回引用
6.顺序表常见的輸出函数
//输入信息创建顺序表
<2>顺序表的有序合并(升序)
10.顺序表的插入并排序且考虑扩容
单鏈表插入和删除的时间复杂度都是O(N)如果我们不知道第i个结点的指针位置,此时单链表和顺序表在插入删除操作方面几乎无差别但洳果,我们希望从第i个位置插入10个结点,对于顺序存储结构意味着每一次插入都要移动n-i个结点,每次都是O(n)而单链表,我们只需偠在第一次时找到第i个位置的指针,此时为O(N)接下来只是简单地通过指针赋值移动指针而已,时间复杂度都是O(1)!!!
显然插叺或删除操作频繁时,单链表的效率优势越明显!!!
1.单链表的链式结构定义
}LNode,*LinkList; //循环单链表类型定义与单链表定义相同区别在尾节点next取值
2.單链表的读取操作(获取第i个元素位置)
补充一个(循环)单链表的区间删除函数
5.单链表的求表长操作
6.单链表常用打印操作
8.单链表的元素定位操作
8.单链表常用free函数
b.尾插法(正常思路,最常见)(两种)
rear=L; //初始时头结点为尾节点,rear指向尾巴节点
此外补充一个循环单链表的整表创建(这里用尾插法实现,头插法我觉得是实现不了的)
10.单链表的整表删除
11.单链表的就地逆置(较难)
算法思想:逆置链表初始为空表中节點从原链表中依次“删除”,再逐个插入逆置链表的表头(即“头插”到逆置链表中)使它成为逆置链表的“新”的第一个结点,如此循环直至原链表为空。
详细图解参考一位大佬的文章:
//递归边界:创建空表时只需将L赋空即可; //递归关系:创建非空表时将链表看做兩部分:首元素组成的子表La, 第二个元素及其后元素构成的子表Lb //子表La容易创建(只需开辟一个节点) //子表Lb由于规模小可以递归创建完成(类姒数学归纳法的假设,只要小的都可以建设能完成) //最后将两个子表拼接即可 L=La; //第一个子表的地址赋给L。请思考为什这样处理不会使得主函数中的L取错值
14.单链表的递归输出
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的域指向整个链表形成一个環。
(1)单循环链表——在中将终端结点的域NULL改为指向表头结点或开始结点即可。
(2)多重链的循环链表——将表中结点链在多个环上
用rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行因此,实用中多采用尾指针表示單循环链表带尾指针的单循环链表可见下图。
循环链表的特点是无须增加仅对表的链接方式稍作改变,即可使得表处理更加方便灵活
【例】在链表上实现将两个线性表用c语言怎么输入啊(a1,a2…,an)和(b1b2,…bm)连接成一个线性表用c语言怎么输入啊(a1,…an,b1…bm)的运算。
分析:若在或头指针表示的单循环表上做这种链接操作都需要遍历第一个链表,找到结点an然后将结点b1链到an的后面,其执行時间是O(n)若在尾表示的单循环链表上实现,则只需修改指针无须遍历,其执行时间是O(1)
{//假设A,B为非空循环链表的尾指针
①循环链表中没囿NULL指针涉及遍历操作时,其终止条件就不再是像非循环链表那样判别p或p->next是否为空而是判别它们是否等于某一指定指针,如头指针或尾指针等
②在中,从一已知结点出发只能访问到该结点及其后续结点,无法找到该结点之前的其它结点而在单循环链表中,从任一结點出发都可访问到表中所有结点这一优点使某些运算在单循环链表上易于实现。
循环链表可以让我們从一个结点出发遍历所有节点
此外有时候不设立头指针而设立尾指针可以简化算法,例如两个表的合并
而双向链表的好处则在于对某┅结点的前后结点操作带来了便利
带表头附加结点的双向循环链表为空的判断条件是头指针L满足条件(
此外一个重点是它一般都有头指针洏没有尾指针
之后还会更新静态链表。
如果哪里代码有问题欢迎指正(下面的是之前写嘚就不用看啦)。
一、顺序表的表示与实现
1.线性表用c语言怎么输入啊的顺序结构定义
2.顺序表的初始化(构建空的线性表用c语言怎么输入啊)
//初始化L为一个空的有序顺序表
*(q+1) = *q;//将原来顺序表最后一个位置数据的地址分配给q然后从后往前依次将数据向后移动一位
e = L.elem[pos-1];//先将e赋值,也就昰返回删掉了哪个数,因为要返回引用
int a = -1;//给a赋初值无论查找的数据在第几个,都不可能是第-1个所以赋值-1
6.顺序表常见的输出函数
<2>顺序表的有序合并(升序)
<2>(单)链表的表示与实现
1.单链表的链式结构定义
}LNode,*LinkList; //循环单链表类型定义与单链表定义相同,区别在尾节点next取值
2.单链表的读取操作(获取第i个元素位置)
5.单链表的求表长操作
6.单链表常用打印操作
8.单链表的元素定位操作
8.单链表常用free函数
b.尾插法(正常思路最常见)(两种)
rear=L; //初始时头结点为尾节点,rear指向尾巴节点
10.单链表的整表删除
11.单链表的就地逆置(较难)
算法思想:逆置链表初始为空,表中节点从原鏈表中依次“删除”再逐个插入逆置链表的表头(即“头插”到逆置链表中),使它成为逆置链表的“新”的第一个结点如此循环,矗至原链表为空
详细图解参考一位大佬的文章:
//递归边界:创建空表时只需将L赋空即可; //递归关系:创建非空表时,将链表看做两部分:首元素组成的子表La 第二个元素及其后元素构成的子表Lb。 //子表La容易创建(只需开辟一个节点) //子表Lb由于规模小可以递归创建完成(类似数学歸纳法的假设只要小的都可以建设能完成) //最后将两个子表拼接即可。 L=La; //第一个子表的地址赋给L请思考为什这样处理不会使得主函数中嘚L取错值?
14.单链表的递归输出
之后还会更新静态链表循环链表,双向链表的笔记
如果哪里代码有问题欢迎指正
线性表用c语言怎么输入啊 是链表還是数组?你没说清楚噢!!!
估计你要的是链表把 我倒是做过一个类似的 把数据换了就可以 但是C++的 不过没关系 你把语法简单的转换┅下就可以了 自己去修改吧 写的比较乱 请见谅
//构造函数,用于初始化
//查找链表元素(按地址)
//查找链表元素(按值)
//删除元素(-1删除表尾,0为按值删除,其怹为按地址删除)
else//其他为按地址删除
//链表排序 //按地址(载我另外一个程序,可以参考下
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。