计算方法chap2 线性表
- 格式:pdf
- 大小:556.00 KB
- 文档页数:76
2. 2线性表2.2.1 线性表的定义和运算一般形式:L=(a1,a2,…,a n)其中L为线性表,a i(i=1,…,n)是属于某数据对象的元素,n(n≥0)为元素个数称为表长,n=0为空表。
线性表的定义:L=(D,R)其中:D={ a1,a2,…,a n}R={< a i-1,a i>| a i-1,a i∈D,2≤i≤n}若a i-1≥a i,i=2,3,…,n,则称该线性表为有序表,否则称为无序表。
线性表的基本运算:插入、删除、查找、排序。
2.2.2顺序存储线性表1.顺序存储结构2.顺序存储结构的插入、删除运算插入INSERTLIST(V,n,i,x)1.if (i<1) OR ((i>n+1) then {参数错return}(i=n+1表示插入在最后)2.for j=n to i step (-1)3.V[j+1]←V[j]4.end (j)5.V[i]←x6.n←n+17.return删除DELETELIST(V,n,i)1.if (i<1) OR ((i>n+1) then {参数错return}2.for j=i to n-13.V[j]←V[j+1]4.end (j)5.n←n-16.return2.2.3 线性链表1.链式存储结构2.线性链表的基本运算(1)基本操作设p,q,s均为指针类型变量,指向数据域为data,指针域为next的结点,表2.2表示线性链表的几项基本操作。
(2)结点的动态生成及回收设具有数据域date,指针域next的空白链表,其头指针为av。
从空白链表中获取一个结点,由指针P指向,其算法为:GETNODE(P)1.p←av2.av←next(av) //修改空白链表头指针//3.return回收一个由P指针指向的结点,放回空白链表的算法为:REP(P)1. Next(P)←av2. av←P3. return(3)插入运算INLINKST(head,a,b)1.GETNODE(p); data(p)←b; //取得一个新结点p//2.if (head=nil) then {head←p;next(p)←nil; return} //空白情况//3.if (data(head)=a) then {next(p)←head; head←p; return} //a为头结点//4.LOOKFOR(head,a,q) //寻找元素a之前的结点q//5.next(p)←next(q); next(q)←p6.return其中LOOKFOR(head,a,q)为在非空链表中寻找包含指定元素a之前的结点q的算法:LOOKFOR(head,a,q)1.q←head2. While (next(q)≠nil) and (data(next(q))≠a) do3. q←next(q) //如果表中无a结点,则q指向链表最后一个结点//(4)删除运算DELINKST(head,a)1.if (head=nil) then {空表return} //空表情况//2.if(data(head)=a) then {s←next(head); RET(head); head←s; return} //a为头结点//3. LOOKFOR(head,a,q)4.if (next(q)=nil) then {无此结点return}5.p←next(q); next (q)←next (p)6.RET(p)7.return3.线性链表的其他形式4.应用实例---一元多项式相加P n(x)=P0+P1X2+…+P i x i+…+P n x n设有一元多项式A(x)和B(x),现要求相加结果C(x)=A(x)+B(x)。
数据结构课件第2章线性表原创力文档线性表是计算机科学中经常使用的一种基本数据结构。
它的定义是指由一系列元素(有序)构成的有限序列,它的基本特征是存储元素有序可重复,其大小受限。
线性表可以用于存储大量类似或者相关的数据,并且支持高效的查找、遍历、访问、插入和删除操作。
线性表可以分为两种,即顺序存储结构和链式存储结构。
顺序存储结构是指将元素序列存储在一组连续的存储空间中,元素紧凑地存储在一起,方便统一管理,但是插入和删除操作效率不高。
而链式存储结构是指以数据元素节点为基本单位,以链表的形式组织起来的数据结构。
它可以采用动态分配的存储空间,使在插入和删除操作的效率更高。
线性表的应用十分广泛,它可以用于存储数据,进行算法表示等。
例如,它可以在字符串和图形处理中用来存储字符或像素点,用于搜索和排序操作,以及时间复杂度分析等。
无论是在计算机科学中,还是在实际工程应用中,线性表都有着重要的作用。
线性表的基本操作是插入、删除、查找和修改。
这四种操作都是基本的数据结构操作,其中插入、删除操作可以在表的任意位置进行,而查找和修改操作则需要先找到指定元素的地址。
线性表的特殊操作也包括求表长、求表中最大、最小值、求前驱、后继元素等操作。
线性表是一种非常有用的数据结构,它可以用在许多不同的地方,例如计算机科学中的图像处理、多媒体处理、数据库管理等,也可以用于实际的应用领域中的自动控制、工程计算、规划计算和解决问题等。
因此,学习和使用线性表是解决计算机问题的重要一步。
综上所述,线性表是一种基本的数据结构,有着广泛的应用,极其方便。
要想更好地了解线性表,需要掌握最基本的概念、基本操作以及特殊操作,以及应用该数据结构的知识。
深入地学习和使用线性表有助于解决大量实际问题,为实现自动化和信息管理提供重要支持。