数据结构线性表学习

1、第二章 线性表,存在唯一的头元素,存在唯一的尾元素,除头元素外，每个元素均有一个直接前驱,除尾元素外，每个元素均有一个直接后继,线性结构的特点, 2.1 线性表的定义,1. 线性表的语言定义,线性表是n个数据元素的有限序列。,例: 英文字母表 (A，B，C，Z),线性表中的数据元素也可以由若干个数据项构成。 这时，数据元素称为记录，含有大量记录的线性表 又称为文件。,例: 学生情况登记表,2. 线性表的形式定义,其中：a1是头元素， an是尾元素， ai是第 i 个元素，,ai-1是ai的直接前驱， ai+1是ai的直接后继。,n为线性表的长度(可根据需要增长或缩短)， n=0 时为空表,i为

2、数据元素ai在线性表中的位序,3. 抽象数据类型 线性表List 的定义,数据对象: D = ai | ai ElemSet，i = 1, 2, , n , n0,数据关系: R1 = | ai-1, ai D， i = 2, , n ,基本操作:,例2-1：用线性表完成集合的并运算，A=AB,若：A=1，3，8 B=2，3，6，9,则：A=AB 1，3，8，2，6，9,void union(List ,执行过程： La_len=3 Lb_len=4 i=1, e=2, La中没有2， La_len=4，将2插到第4个位置 即： A=1，3，8，2 - i=2, e=3, La中有3，返回位序

3、为2 if条件不满足，3不插入 - i=3, e=6, La中没有6， La_len=5，将6插到第5个位置 即： A=1，3，8，2，6 - i=4, e=9, La中没有9， La_len=6，将9插到第6个位置 即： A=1，3，8，2，6，9,例2-2：已知线性表LA、LB为有序表，将LA、LB归并为一个 新线性表LC，且保持其有序性,若：LA=(1，3，8) LB=(2，3，6，9，12，15),则：LC=(1，2，3，3，6，8，9，12，15),LA,LB,LC,1,2,3,3,6,8,12,15,9,void MergeList(List La, List Lb, List ,

4、算法2.2 归并两个有序的线性表, 2.2 线性表的顺序表示和实现,线性表的顺序表示: 用一组地址连续的存储单元依次 存储线性表的数据元素。,LOC(a1),LOC(ai),设每个元素需占用 l 个存储单元,LOC(ai)表示元素ai的存储地址,LOC(a1)是第一个数据元素a1的存储 地址，也是整个线性表的起始地址,LOC(ai+1) = LOC(ai) +l,LOC(ai) = LOC(a1) + (i - 1) l,顺序存储结构的线性表称为顺序表,顺序表的特点： 表中相邻元素ai和ai+1赋以相邻的存储位置LOC(ai)和LOC(ai+1) 即：以元素在计算机内“物理位置相邻”来表示元素

5、间的逻辑关系,只要确定了存储线性表的起始位置，线性表中任一元素都可以随机存取。,线性表顺序存储结构表示,# define LIST_INIT_SIZE 100 /初始分配量,# define LISTINCREMENT 10 /分配增量,typedef struct SqList;,Elemtype * elem; /线性表的起始地址,int length; / 表长，初始为 0,int listsize; / 表存储容量,线性表的顺序存储结构是一种随机存取的存储结构。,Status InitList_Sq ( SqList ,算法2.3 初始化空线性表,线性表的顺序存储结构的优点,可随机存取

6、表中任意数据元素(第 i 个),直接可获取线性表中数据元素的个数,L.length,L.elemi-1,* (L.elem+i-1),算法2.4 在第 i 个数据元素之前插入一个新元素,算法思想:,1. 找到第 i 个元素的位置。,3. 将新元素b插入到第 i 个位置。,例：在第 i 个元素前插入 b,b,2. 将第 n 个到第 i 个元素均向后移动一个位置。,ai,q = L.elem+i-1 ； /找到第 i 个元素位置,* q = e ； / 插入新元素,+L.length ；,return OK；,ElemType *p, *q;,算法2.4的简化描述,不用指针，可以直接用下标 for

7、( k=L.length-1; k=i-1; k- ) L.elemk+1= L.elemk; L.elemi-1=e; L.length+ ;,例：在第4个元素之前插入元素25。(即：i=4 b=25),25,平均时间复杂度：,O(n),*(p+1) = *p,p-,*(p+1) = *p,p-,*(p+1) = *p,p-,*q = e = 25,q = L.elem+i-1 ; for ( p = L.elem+L.length-1 ；p = q ；- p ) *(p+1) = * p ; * q = e ; +L.length ; return OK ;,算法2.4的完整描述,if (

8、 L.length = L.listsize ) /越界处理 L.elem = ( ElemType * ) realloc ( L.elem , ( L.listsize + LISTINCREMENT ) * sizeof(ElemType) ); if ( ! L.elem ) exit(OVERFLOW) ; L.listsize += LISTINCREMENT ; ,if ( i L.length+1 ) return ERROR ; /i合法性检查,补充： realloc( )函数,函数原型：void *realloc(void *p，unsigned int size);,函数

9、功能：将指针p所指向的存储空间的大小改为size个字节。 函数返回值：如果重新分配成功，则返回新分配的存储空间的 首地址(该地址与原来p所指向的地址不一定相同)， 否则返回空指针NULL。,MSDN中对realloc()函数的描述： realloc returns a void pointer to the reallocated (and possibly moved) memory block. The return value is NULL if the size is zero and the buffer argument is not NULL, or if there is n

10、ot enough available memory to expand the block to the given size. In the first case, the original block is freed. In the second, the original block is unchanged. The return value points to a storage space that is guaranteed to be suitably aligned for storage of any type of object. To get a pointer t

11、o a type other than void, use a type cast on the return value.,realloc()函数使用说明：,1. realloc调用成功时返回void * 指针，指向新分配的内存空间。 一般需要对这个指针进行强制类型转换。,2. 若传入的第一个指针参数为NULL，则该函数等同与malloc函数。,3. 当第二个参数为0，且第一个参数不为NULL时，或者没有足够的 内存空间进行分配时，返回NULL。,4. realloc是从堆上分配内存的，当扩大一块内存空间时，realloc函数 首先试图从原来分配的内存块后面获得附加的内存空间，如果原内 存块

12、后面的内存空间不够的话，就使用堆上第一个有足够大小的 内存空间，将原内存块中的数据拷贝到新分配的内存空间中，此时 原内存块被free。,算法2.5 删除第 i 个数据元素,算法思想:,1. 找到第 i 个数据元素。,3. 将第 i+1个到第 n 个元素均向前移动一个位置。,2. 取出第 i 个数据元素。,ai,int ListDelete_Sq ( SqList ,/注意:格式中的小括号不能省略,让指针变量指向函数就是直接将函数名赋给指针变量,使用指针变量调用函数的格式: (*指针变量名)(实参列表),例：编写一个用矩形法求定积分的通用函数,矩形法: 把要求的面积垂直x轴分成n个小矩形, 然后

13、把这n个小矩形的面积相加, 即为所求的定积分的值,用分点a=x0,x1,x2,xn=b将区间a, b 分成n个长度相等的小区间, 每个小区间的长为x=(b-a)/n,设函数y=f(x)对应于各分点的函数值为y0,y1,y2,yn 取小区间右端点的函数值作为窄矩形的高,方法1：每个积分写一个函数,double sinfunc(double a, double b, int n) int i; double x, h, sum=0; h=(b-a)/n; x=a; for(i=1; i=n; i+) x=x+h; sum=sum+sin(x); return(sum*h); ,double cos

14、func(double a, double b, int n) int i; double x, h, sum=0; h=(b-a)/n; x=a; for(i=1; i=n; i+) x=x+h; sum=sum+cos(x); return(sum*h); ,方法1：每个积分写一个函数,double expfunc(double a, double b, int n) int i; double x, h, sum=0; h=(b-a)/n; x=a; for(i=1; i=n; i+) x=x+h; sum=sum+exp(x); return(sum*h); ,方法1：每个积分写一个函

15、数,#include #include double sinfunc(double, double, int); double cosfunc(double, double, int); double expfunc(double, double, int); void main(void) double r1, r2, r3; r1=sinfunc( 0, 1, 20); printf(the integral of sin(x) is:%lfn, r1); r2=cosfunc( 1, 2, 30); printf(the integral of cos(x) is:%lfn, r2);

16、r3=expfunc( 1, 3, 40); printf(the integral of exp(x) is:%lfn, r3); ,方法1：每个积分写一个函数,函数声明,double sinfunc(double a, double b, int n) int i; double x, h, sum=0; h=(b-a)/n; x=a; for(i=1; i=n; i+) x=x+h; sum=sum+sin(x); return(sum*h); ,double cosfunc(double a, double b, int n) int i; double x, h, sum=0; h=

17、(b-a)/n; x=a; for(i=1; i=n; i+) x=x+h; sum=sum+cos(x); return(sum*h); ,double expfunc(double a, double b, int n) int i; double x, h, sum=0; h=(b-a)/n; x=a; for(i=1; i=n; i+) x=x+h; sum=sum+exp(x); return(sum*h); ,方法1：每个积分写一个函数,问题：这三个函数非常相似，这样分别定义太麻烦了,方法2：写一个用矩形法求定积分的通用函数,double func(double (*p)(doub

18、le), double a, double b, int n) int i; double x, h, sum=0; h=(b-a)/n; x=a; for( i=1; i=n; i+) x=x+h; sum=sum+(*p)(x); return(sum*h); ,可能是： sin(x) cos(x) exp(x),指向函数的指针变量作参数,#include #include double func(double (*p)(double), double a, double b, int n); void main( ) double a1=0, b1=1, a2=1, b2=2, a3=1

19、, b3=3, c; int n=20; c=func( sin, a1, b1, n); printf(the integral of sin(x) is:%lfn, c); c=func( cos, a2, b2, n); printf(the integral of cos(x) is:%lfn, c); c=func( exp, a3, b3, n); printf(the integral of exp(x) is:%lfn, c); double func(double (*p)(double), double a, double b, int n) int i; double x

20、, h, sum=0; h=(b-a)/n; x=a; for( i=1; inext; p-next = q-next; free(q);,1. 确定指针,2. 取出要删除的结点,3. 修改指针的指向,4. 释放内存,6. 单链表的删除操作,删除操作的步骤：,Status ListDelete_L ( LinkList j = 0;,return OK ；,if ( ! (p-next) | j i - 1 ) return ERROR;,while ( p-next ,/寻找第 i 个结点，p指向其前驱,q=p-next; p-next = q-next;,void CreateList_

21、L ( LinkList /创建头结点,L-next = NULL;,for ( i = n; i0; -i ) ,p=( LinkList ) malloc ( sizeof(LNode) ); /创建新结点,scanf ( /输入数据,p-next = L-next;,L-next = p; /在表头插入新结点,例: 建立链表的过程演示,Zhao,Qian,p=(LinkList)malloc(sizeof(LNode);,p-next=L-next;,L-next=p;,p=(LinkList)malloc(sizeof(LNode);,p-next=L-next;,L-next=p;,

22、scanf ( ,scanf ( ,算法2.12 两个有序单链表的归并算法,void MergeList_L(LinkList / 释放Lb的头结点 ,单链表作业:习题集 P18 2.22, 2.26,zhao,qian,sun,li,zhou,0,1,2,3,4,5,6,1,2,3,4,5,0,静态链表,某些语言不支持指针类型，通常使用一维数组描述单链表。,线性表的静态单链表存储结构,#define MAXSIZE 1000,typedef struct ElemType data； int cur； component ，SLinkListMAXSIZE ；,data-表示数据元素信息,c

23、ur-代替指针指示结点在数组中的相对位置,静态单链表的插入操作,例：在结点wu前插入新元素 zhou,zhou 2,例： 删除第2个结点,静态单链表的删除操作, 2.3.2 循环链表,循环链表:表中最后一个结点的指针域指向头结点， 整个链表形成一个环。,空表:,循环链表的操作与单链表基本一致，差别在于算法中的循环 结束条件不是判断p是否为空，而是判断p是否等于头指针。,Status GetElem_L ( LinkList L，int i，ElemType struct DuLNode * prior; struct DuLNode * next; DuLNode，* DuLinkList;,

24、 2.3.3 双向链表,双向链表: 链表中的每个结点都有两个指针域， 一个指向其直接后继, 另一个指向其直接前驱。,双向链表存储结构定义如下：,双向链表的示意图,双向循环链表的示意图,性质: 设d 是指向某个结点的指针,d-next-prior = d-prior-next = d,空的双向循环链表的示意图,双向循环链表的插入操作,1. 找到要插入的结点位置，用p指向该位置,3. s-prior = p-prior ；,4. p-prior-next = s ；,5. s-next = p ；,6. p-prior = s ；,2. 构造一个新结点，用s指向该新结点,A,C,B,1. 找到要删

25、除的结点，用p指向该结点,2. p-prior-next = p-next ；,3. p-next-prior = p-prior ；,4. free(p) ；,双向循环链表的删除操作,1. 数学表示: Pn(x) = p0 + p1x + p2x2 + + pnxn,2. 计算机表示: 描述为一个由 n+1 个系数构成的线性表 P = ( p0，p1，p2，pn ),3. 多项式相加,则 Rn(x) = Pn(x) + Qm(x) R = ( p0 + q0，p1 + q1，p2 + q2，pm + qm，pm+1，pn ),显然，采用 结构实现方便。,顺序存储, 2.4 一元多项式的表示及

26、相加,+,问题：实际应用中，多项式的次数往往很高且有很多缺项,例：S(x) = 1 + 3x10000 + 2x20000,计算机表示: P = ( ( p1 ，e1 ) ，( p2 ，e2 ) ，( pm ，em ) ),思考：采用哪种存储结构？,系数,指数,下一个结点,算法2.23 多项式相加，要求: Pa = Pa + Pb,思想: 依据归并两个有序表的过程，分三种情况考虑,1. 令 qa 和 qb 分别指向多项式 A 和 B 中当前进行比较的结点,2. qa-expn qb-expn，应插入qa所指向的结点,3. qa-expn qb-expn，应插入qb所指向的结点,4. qa-ex

27、pn = qb-expn，求和 sum=qa-coef + qb-coef,(1) sum = 0，释放 qa 和 qb 所指结点,(2) sum != 0，修改 qa 所指结点的系数值，释放 qb 所指结点,qa-expn qb-expn 的情况：,ha = qa； qa = qa-next； /qa=NextPos(Pa, qa);,hb-next = qb-next； /DelFirst(hb, qb);,qb = hb-next； /qb=NextPos(Pb, hb); ha = ha-next； /ha=NextPos(Pa, ha);,ha-next = qb；qb-next = qa；/InsFirst(ha, qb);,qa,qb,5,3,7,ha,8,hb,qa-expn qb-expn 的情况：,qa,qb,3,3,7,h