线性表与字符串-2

1、数组线性表字符串第二章 线性表和字符串1数组二元组的一个集合。存储于一个连续存储空间中的相同数据类型的数据元素的集合；通过数组元素的下标，可以得到存放该数组元素的存储地址，从而可以访问该数组元素的值。一维数组向量具有相同类型的n(n0)个元素的有限序列。n为数组长度或数组大小；n=0为空数组。各数组元素处于一个线性聚集或线性表中。每个元素的数据类型相同；占有相同的存储空间；每个元素的开始位置到相邻元素的开始位置的距离相等。2一维数组的特点数组中的每一个元素在数组中的位置由下标唯一确定；除第一个元素外，其它元素有且仅有一个直接前驱，第一个元素没有前驱。除最后一个元素外，其它元素有且仅有一个直接后

2、继，最后一个元素没有后继。 示例长度为10，每个元素占l个存储字，起始地址为a。3数组的定义和初始化创建数组静态数组在声明数组对象时显式地定义了数组长度；定义了数组的下标范围；对数组各元素赋值；存储空间不随程序的执行而改变。动态数组用指针声明数组；在指针中只存放数组第一个元素的地址，所以仅占用一个存储空间；用+和- -可访问数组下一个元素或前一个元素。数组的标准操作存储抽取示例Positioni=Positioni-1+Numberi-1赋值符号右边表示按下标i-1直接提取相应数组元素的值；赋值符号左边表示按下标i把右边的计算结果直接存储到相应数组元素中。二维数组矩阵由n个行向量m个列向量所组

3、成的向量。共有n*m个数组元素；元素 jk处于第j个行向量的第k个列向量；在行和列方向上各有一个直接前驱和直接后继。某一个数组元素在数组中的位置需由下标的二元组jk唯一确定。三维数组共有m1*m2*m3个数组元素；每个数组元素同时处于三个向量之中；最多有三个直接前驱和直接后继。某一个数组元素在数组中的位置需由下标的三元组ijk唯一确定。 二维数组 三维数组行向量 下标 i 页向量 下标 i列向量 下标 j 行向量 下标 j 列向量 下标 k7n维数组am1m2.mn 总共有m1*m2*mn个数组元素；每一个数组元素ai1i2.in处于n个向量之中；每一个数组元素的位置由下标的n元组i1i2.i

4、n 唯一确定。数组连续存储方式在实现数组存储时，通常是按各个数组元素的排列顺序，顺次存放在一个连续的存储区域内，得到一个所有数组元素的线性序列。一维数组第一个元素的起始位置为，每一个数组元素的存储大小为l。任一数组元素的存储地址LOC(i)：LOC(1) = LOC(0) + l =+ lLOC(2) = LOC(1) + l =+ 2*l，LOC(i) = LOC ( i -1 ) + l =+ i*l9行优先顺序所有数组元素按行向量依次排列，第i+1个行向量紧跟在第i个行向量后面。列优先顺序所有数组元素按列向量依次排列，第j+1个列向量紧跟在第j个列向量后面。二维数组10行优先 LOC (

5、 j, k ) = LOC ( j, 0 )+k*l/第j行开始位置加k*l = LOC ( j-1, 0 )+m*l+k *l /第j-1行开始位置加该行元素个数m*l加k *l = LOC ( j-2, 0 )+2*m*l +k*l /前推到第j-2行 = = LOC (0, 0 )+j*m*l +k*l /前推到第0行 = +( j * m + k )*l设二维数组anm第一个元素a00在相应的一维数组中存放于第一个位置，其地址为，每个元素占l个元素的空间。则任一数组元素ajk在相应一维数组中的存放地址利用递推公式计算：设三维数组am1m2m3中，对于任一数组元素a ijk在一维数组中存

6、放的位置为：页优先 LOC ( i, j, k ) = LOC ( i, 0 , 0 )+j*m3*l+k*l = LOC ( i-1, 0, 0 )+m2*m3*l+j*m3*l+k*l = LOC ( i-2, 0, 0 )+2*m2*m3*l+j*m3*l+k*l = = LOC (0, 0 , 0 )+i*m2*m3*l+j*m3*l+k*l = +(i*m2*m3+j*m3+k)*l三维数组线性表线性聚集，一个存储n(n0)个表项的序列。n是表的长度，可以是任意整数。n=0为空表。表的长度随增加或删除某些表项而发生改变。每个表项都是单个对象，其数据类型相同。各个表项通过其位置来访问；

7、第一个表项位于表的头部，最后一个表项位于表的尾部。除最后一个表项之外，其它每个表项有且仅有一个直接后继。13线性表的特点特点 顺序存取为了得到顺序表中所要求的项，必须从表的第一个表项开始，逐个访问表项，直到找到满足要求的表项为止。 遍历 逐项访问 从前向后 从后向前 从两端向中间14线性表上的基本运算InitList(L) 构造一个空的顺序表Length(L) 求顺序表L中的表元个数GetNode(L, i) 取顺序表L中的第i个表元LocateNode(L, x)在顺序表中找值为x的结点，返回该结点在L中的位置。InsertList(L, x, i)在L的第i个位置插入一个值为x的新表元。D

8、eleteList(L, i) 删除L的第i个表元。线性表 的存储结构常用的存储结构：顺序存储链接存储顺序存储（顺序表）设顺序表的每个表元的结构都相同，记LOC（ ai）为存储ai的开始地址，则 LOC（ ai）=LOC(a0) + i*sizeof(a0)顺序存储线性表的数据类型#define MaxSize 100typedef int DataTypetypedef struct DataType dataMaxSize; int len;SeqList;16顺序搜索图示 x = 48 x = 5017int LocateNode(SeqList *l, DataType key ) i

9、nt i; for(i = 0; i len; i+) if(l-datai = key) return i; return -1;搜索成功 若搜索概率相等，则搜索不成功 数据比较 n 次表项的插入int InsertList (SeqList *l, , DataType x, int i ) int j;/在表中第 i 个位置插入新元素 x if ( i l-len | l-len = MaxSize ) return 0; /插入不成功 else for ( j=l-len; ji; j- ) l-dataj = l-dataj -1; l-datai = x; l-len+; retu

10、rn 1; /插入成功 表项的删除 int DeleteList( SeqList *l, int x ) int i, j; /在表中删除已有元素 x i = LocateNode (l, x); /在表中搜索 x if ( i = 0 ) for ( j=i; jlen-1; j+ ) l-dataj = l-dataj+1; l-len-; return 1; /成功删除 return 0; /表中没有 x 线性表的应用：集合的“并”运算void Union ( SeqList *LA, SeqList *LB) int i, k; DAtaType x; for (i=0; ilen;

11、 i+ ) x = LBi; /在LB中取一元素 k =LocateNode(LA, x); /在LA中搜索它 if ( k = -1 ) /若未找到插入它 InsertList (LA , x, LA-len); 有一个指针指向链表的第一个表元，习惯称该指针为“头指针”或“链表头”。头指针head指向第一个表元，第一个表元又指向第二个表元，直到最后一个表元，该表元不再指向其他表元，习惯称链表的最后一个表元为“表尾”。 一个非空链表一个空链表first = NULL链接存储线性表-单链表结构单链表的存储映像单链表的数据类型typedef char DataType;typedef struct

12、 node DataType data; struct node *next; ListNode;typedef struct ListNode *head; LinkList;1.遍历链表从链表的首表元开始，沿着链表表元的链接顺序逐一考察各表元，直至链表结束。用指针p遍历整个链表，访问表元只做输出表元值的工作。p的初值为链表头指针，在p不等于NULL值时循环，输出p所指表元的值，并准备考察下一个表元(即p = p-next)。遍历链表的函数： void travelLink(LinkList *L) ListNode *p = L-head; while ( p != NULL ) prin

13、tf(”%4c”, p-data); /* 输出表元的值 */ p = p-next; /* 准备访问下一个表元 */ printf(”n”); 2.在链表中查找指定值的表元在链表中查找指定值表元有不同目的获取该表元的详细信息，称为简单查找。对链表的修改，或将查到的表元删除，或在查到的表元之前插入一个新表元等，称为动态查找。另外，查找过程的实现又可分两种情况，一是无序链表上的查找，二是有序链表上的查找。（1）无序链表上的简单查找简单查找过程:从链表头指针所指的第一个表元出发，顺序查找。或发现有指定值的表元，以指向该表元的指针值为查找结果；或查找至链表末尾，未发现有指定值的表元，查找结果为NUL

14、L，表示链表中没有指定值的表元。ListNode * searchSLink(LinkList *L, DataType key) ListNode *v = L-head; while ( v != NULL ) & ( v-data != key) v = v-next; return v; （2）有序链表上的简单查找如链表的表元是按值从小到大有序的，在顺序考察链表表元的查找循环中，当发现还有表元，并且该表元的值比key小时，应继续查找。反之，若不再有表元，或当前表元值不比key值小，则应结束查找。查找循环结束后，仅当还有表元，且表元的值与key值相同情况下，才找到，函数返回当前表元的指针

15、。否则，链表中没有值为key的表元，函数返回NULL值。ListNode *searchSOLink(LinkList *L, DataType key) ListNode *v = L-head; while(v!= NULL)&(v-datanext; return v != NULL & v-data = key ? v : NULL; （3）无序链表上的动态查找动态查找应为插入或删除做好必要的准备工作。由于是单向链表，函数除要回答查找结束时的当前表元的指针外，还应回答该表元的前驱表元指针。令函数返回值是查找结束时当前表元的指针，函数另设一个指针形参，将找到的前驱表元的指针存于环境中的某

16、指针变量中。ListNode *searchDSLink(LinkList *L, DataType key，ListNode * pp) ListNode *v = L-head, *u = NULL; while ( v != NULL ) & ( v-data != key) u = v ; v = v-next; /* 后继表元成为当前表元 */ *pp = u; return v; (4)有序链表上的动态查找表元按值从小到大顺序链接，与无序链表上的动态查找类似，但查找循环当发现查找值不比链表当前表元的值小时，就应提早结束查找循环。 ListNode * searchDOLink(Li

17、nkList *L, DataType key， ListNode * pp) ListNode *v = L-head, *u = NULL; while ( v != NULL ) & ( v-data next; *pp = u; return v; 3.从链表删除指定值的表元为删除首先要查找指定值的表元。若未找到，则不做删除工作；若找到，则将它从链表中删除。删除时要考虑两种不同情况，如删的是首表元，要更改链表头指针；否则更改前驱表元的后继指针。在无序整数链表上删除指定值表元的函数中。因函数在删除链表首表元时，要修改链表头指针。函数返回删除表元的指针。ListNode *sDelete(

18、LinkList *L,DataType key) ListNode *u, *w; u = L-head; /* 让 u 指向链表的首表元 */ while (u != NULL) & (u-data != key) w = u; u = u - next; if (u != NULL)/* 链表中有值为key的表元 */ if (u = L-head) L-head = u-next;/* 修改链表头指针 */ else w-next = u-next; u-next = NULL ; return u;4.在有序链表中插入指定值的表元寻找插入位置，生成新表元并插入之。void rInse

19、rte(LinkList *L, DataType key) ListNode *u, *w, *p; u = searchDOLink(L, key, &w); p=(ListNode*)malloc(sizeof(ListNode); p-data = key; p-next = u; if (w=NULL) L-head = p; /* 修改链表头指针 */ else w-next = p;5.建立单链表(1)头插法建表LinkList CreatListF(void) char ch; LinkList L; ListNode *p; L.head = NULL; while(ch =

20、 getchar() != n) p = (ListNode *)malloc(sizeof(ListNode); p-data = ch; p-next = L.head; L.head = p; return L; (2)尾插法建表LinkList CreatListR(void) char ch; LinkList L; ListNode *p, *r; L.head = r = NULL; while(ch = getchar() != n) p = (ListNode *)malloc(sizeof(ListNode); p-data = ch; if(r = NULL) L.hea

21、d = p; else r-next = p r = p; if(r != NULL) r-next = NULL; return L; 带表头结点的单链表表头结点位于表的最前端，本身不带数据，仅标志表头。设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。非空表 空表循环链表 (Circular List)循环链表是单链表的变形。相同点：两者结点结构相同。不同点：循环链表最后一个结点的link指针不为 0 (NULL)，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。特点：只要知道表中某一结点的地址，就可搜寻到所有其他结点。循环链表的示例带表头结点的循环链表 字符串

22、 (String)字符串是n ( 0 ) 个字符的有限序列，记作 S : “c0c1c2cn-1” 其中，S是串名字 “c0c1c2cn-1”是串值 ci是串中字符 n是串的长度。 如：“Welcome to Shanghai !”41char *subStr (char*s, int pos, int len , char *ss) /从串中第pos个位置起连续提取len个字符 /形成子串返回 int i, j; if ( pos 0 | len 0 ) *ss = 0; /返回空串 else /提取子串 for(i=0, j=pos; sj!=0 & i 0，则目标指针不变， 模式指针回到

23、 p f ( j-1)+1。 运用KMP算法的匹配过程第1趟 目标 a c a b a a b a a b c a c a a b c 模式 a b a a b c a c j = 1 j = f (j-1)+1 = 0第2趟 目标 a c a b a a b a a b c a c a a b c 模式 a b a a b c a c j = 0 目标指针加 1 第3趟 目标 a c a b a a b a a b c a c a a b c 模式 a b a a b c a c j = 5 j = f (j-1)+1 = 2 第4趟 目标 a c a b a a b a a b c a c a a b c 模式 (a b) a a b c a c int