1、1 / 62 2018数据结构总复习 第一章概论 1.1 数据结构的定义和分类 1. 数据结构的定义 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的 学科。 2. 数据结构包括的内容 （1）逻辑结构 ：数据元素之间的逻辑关系。 （2）存储结构 ：数据元素及其关系在计算机存储器内的表示。 （3）操作 ：数据的运算（检索、排序、插入、删除、修改）。 1.2 为什么学习数据结构 1. 学习数据结构的作用 （1）计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 （2）同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。
2、 （3）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在 很大程度上取决于描述实际问题的数据结构。 2. 电话号码查询问题 （1）要写出好的查找算法，取决于这张表的结构及存储方式。 （2）电话号码表的结构和存储方式决定了查找（算法）的效率。 1.3 算法的概念和特点 1. 算法的概念和特点 算法是由若干条指令组成的有穷序列，具有以下特点： （1）输入 ：具有 0 个或多个输入的外界量。 （2）输出 ：至少产生1 个输出。 （3）有穷性 ：每一条指令的执行次数必须是有限的。 （4）确定性 ：每条指令的含义都必须明确，无二义性。 （5）可行性 ：每条指令的执行时间
3、都是有限的。 2. 算法与程序的区别 （1）一个程序 不一定 满足有穷性，但算法一定。 （2）程序中的指令必须 是机器可执行的，而算法无此限制。 （3）一个算法若用机器可执行的语言来描述，则它就是一个程序。 2 / 62 1.4 算法分析 1. 时间复杂度 算法中基本操作重复执行的次数是问题规模n 的某个函数，用T(n) 表示，若有某个辅助函数f(n) ， 使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n) 是 T(n) 的同数量级函数。 记作 T(n)=O(f(n)，称 O(f(n) 为算法的渐近时间复杂度，简称时间复杂度。算法效率的度量，采用时 间复
4、杂度。 常见函数的时间复杂度按数量递增排列及增长率： 常数阶 O(1) 对数阶 O(log2n) 线性阶 O(n) 线性对数阶O(n log2n) 平方阶 O(n 2) 立方阶 O(n 3) k 次方阶 O(n k) 指数阶 O(2 n) 2. 空间复杂度 空间复杂度是指算法在计算机内执行时所需存储空间的度量，记作：S(n) = O(f(n)。 3. 算法分析的目的 目的在于选择合适算法和改进算法 1.5 例题 例 1： for ( i=1; in; i+ ) y = y+1; / 语句 1 for ( j=0; j=(2*n); j+ ) x+; /语句 2 解：语句1频度为 (n-1) ；
5、语句 2 频度为 (n-1)*(2n+1)=2n2-n-1，因此时间复杂度T(n)=2n2-2=O(n2)。 例 2： i=1; / 语句 1 while (i=n) i=i*2; / 语句 2 解：语句1频度为 1；设语句2频度为 f(n) ，则有 2f(n)=n ，即 f(n)=log2n，去极大值，f(n)=log2n， 因此时间复杂度T(n)=1+log2n=O(log2n)。 3 / 62 第二章线性表 2.1 线性表的概念和运算 1. 线性表的概念 线性表是 n (n0) 个类型相同 的数据元素组成的有限序列 。 其中数据元素的个数n 为线性表的长度， 当 n=0 时称为空表。 2
6、. 线性表的特点 对于非空的线性表，有且仅有一个开始结点 和一个 终端结点 ；开始结点 没有 直接前趋，有且仅有一个 直接后继；终端结点没有 直接后继，有且仅有一个直接前趋；其余任何结点有且仅有一个直接前趋 和一个 直接后继 。 3. 线性表的计算 (1) 置空表 SETNULL(L) ：将线性表L 置为空表。 (2) 求长度 LENGTH(L) ：返回是线性表L 中结点的个数。 (3) 取结点 GET(L, i )：当 1 i LENGTH(L)时，返回线性表L 中的第 i 个结点，否则返回 NULL 。 (4) 定位 LOCATE(L, x)：当线性表L 中存在一个值为x 的结点时，结果是
7、该结点的位置；若表L 中 存在多个值为x 的结点，则返回首次找到的结点位置；若表L 中不存在值为x 的结点，则返回一个特殊值 表示值为x 的结点不存在。 (5) 插入 INSERT(L, x, i)： 在线性表 L 的第 i 个位置插入一个值为x 的新结点。这里 1 i n+1 ， n 是原表 L 的长度。 (6) 删除 DELETE(L, i)：删除线性表L 的第 i 个结点。这里1 i n ，n 是原表 L 的长度。 2.2 线性表的存储结构 1. 顺序存储： （1）定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。简言之，逻辑上 相邻，物理上也相邻。 （2）顺序存储方法
8、：用一组地址连续 的存储单元依次存储线性表的元素，可通过数组 来实现。 （3）地址计算：设首元素a1 的存放地址为LOC(a1)（称为 首地址 ） ，设每个元素占用存储空间（地址 长度）为L 字节 ，则地址计算公式：LOC(ai) = LOC(a1) + ( i-1)*L。 （4）结构定义： #define MAXSIZE 1024 /线性表的最大长度 typedef int datatype; /线性表数据元素类型 typedef struct datatype dataMAXSIZE; int last; /指示线性表的终端结点在表中的下标值 sequenlist; 2. 链式存储： 4
9、/ 62 （1）特点：用一组任意 的存储单元存储线性表的数据元素，利用指针 实现了用不相邻的存储单元存 放逻辑上相邻的元素，每个数据元素ai ，除存储本身信息外，还需存储其直接后继的信息。 （2）头指针、头节点、开始节点 头指针 是指向链表中 第一个 结点（或为头结点或开始结点）的指针， 单链表可由一个头指针唯一确定。 头结点 是在链表的 开始结点之前附设的一个结点；数据域内只放空表标志和表长等信息； 开始结点 是指链表中存储线性表第一个数据元素a1 的结点。 （3）空表的表示 无头结点时，当 头指针的值为空时表示空表； 有头结点时，当 头结点的指针域为空时表示空表。 （4）结构定义 type
10、def int datatype; /线性表数据元素类型 typedef struct node datatype data; /数据域 struct node *next; /指针域 linklist; 3. 存储结构比较 （1）优缺点 顺序存储的 优点 是存储密度大( 1)，存储空间利用率高。缺点 是插入或删除元素时不方便。适合做 查找这样的静态操作。 链式存储的 优点 是插入或删除元素时很方便，使用灵活。 缺点 是存储密度小(1 ） ，存储空间利用率低。 适合做做插入、删除这样的动态操作。 （2）线性表的顺序存储与链式存储对线性表的运算比较 顺序存储 时，相邻数据元素的存放地址也相邻（逻
11、辑与物理统一）；要求内存中可用存储单元的地址 必须是连续的。 链式存储 时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存 放表示结点间关系的指针。 （3）时间复杂度和存储密度比较 顺序存储存储密度=1，链式存储 next; while(t!=NULL if(t-data = x) printf(成功找到 n); else printf(没有找到 n); （2）插入 void insert(Linklist *head,int x) 5 / 62 Linklist *t,*p; p = (Linklist*)malloc(sizeof(Linklist); p-d
12、ata = x; t = head; while(t-next != NULL if(t = head) p-next = head-next; head-next = p; else if(t-next = NULL) t-next = p; p-next = NULL; else p-next = t-next; t-next = p; （3）删除 void dele(Linklist *head) Linklist p ,q; p=head; while (p-next !=NULL) if (p-data !=p-next-data) p=p-next; else q=p-next;
13、p-next=q-next; free(q); （4）逆置 void reverse(Linklist *head) Linklist *s,*t,*p; p = head; s = p-next; while(s-next != NULL) t = s-next; s-next = p; p = s; s = t; s-next = p; head-next-next = NULL; head-next = s; 6 / 62 2.3 例题 例 1：一个一维数组M ，下标的范围是0 到 9，每个数组元素用相邻的5 个字节存储。存储器按字节编址， 设存储数组元素MO的第一个字节的地址是98，则
14、 M3 的第一个字节的地址是 113 。 例 2：在一个长度为n 的顺序表中向第i 个元素（1i n+1）之前插入一个新元素时，需要向后移动n-i+1 个元素（或删除第i 个元素，需要向前移动 n-i 个元素）。 例 3：在单链表中，若*p 结点不是末尾结点，在其前或后插入*s 结点或删除结点的操作是？ 解：在其前插入*s 结点： s-next= p-next ; p-next=s; t=p-data; p-data=s-data ; s-data= t ; 在其后插入 *s 结点： s-next=p-next; p-next=s; 删除其前结点：需要利用遍历 删除其后结点：q = p-nex
15、t; p-next=q-next; free(q); 删除自身接结点：q=p-next; p-data= q-data ; p-next=q-next ; free(q); 例 4：在线性表的下列存储结构中，读取指定序号的元素花费时间最少的是顺序结构。 第三章栈和队列 3.1 栈和队列的基本概念 1. 栈的概念 栈是只允许在同一端 进行 插入 和删除 操作的线性表。允许进行插入和删除的一端叫栈顶 (top) ，另一 端叫 栈底 (bottum) ，栈中无数据元素时，称为空栈 。具有 先进后出 （ FILO）或 后进先出 （LIFO）的特点。 2. 栈的定义 （1）顺序栈 typedef int
16、 datatype; # define MAXSIZE 100 typedef struct datatype dataMAXSIZE; int top; seqstack; seqstack *s; （2）链栈 typedef int datatype; typedef struct node datatype data; struct node * next; linkstack; linkstack * top; top 是栈顶指针，它唯一地确定一个链栈。 top=NULL 时，该链栈为 空栈 。链栈中的结点是动态 产生的， 无需考虑上溢问题。 3. 顺序栈操作 （1）判断栈空 int
17、EMPTY(seqstack *s) return(!stop=0); 7 / 62 （2）置空栈 void SETNULL(seqstack *s) s top=-1; （3）判断栈满 int FULL(seqstack *s) return(stop=MAXSIZE-1); （4）进栈 seqstack * PUSH(seqstack *s，datatype x) if (FULL(s) printf(“stack overflow”); return NULL; stop+; s datas top=x; return s; （5）出栈 datatype POP(seqstack *s)
18、 if (EMPTY(s) printf(“stack underflow”); return NULL; stop-; return(sdatas top+1); （6）取栈顶 datatype TOP(seqstack *s) if (EMPTY(s) printf(“stack is empty”); return NULL; return (sdatas top); 4. 链栈操作 （1）进栈 linkstack *PUSHLSTACK(linkstack *top, datatype x) linkstack *p; p(linkstack *)malloc(sizeof(links
19、tack); p-data x; p-next top; return p; /*返回新栈顶指针*/ （2）出栈 linkstack *POPLSTACK(linkstack *top, datatype *datap) 8 / 62 linkstack *p; if (top=NULL) printf(“under flow”); return NULL; datap top-data; /*栈顶结点数据存入*datap */ p=top; top top-next; free(p); return top; /*返回新栈顶指针*/ 5. 队列的概念 队列 (Queue) 也是一种 运算受限
20、 的线性表。只允许在表的一端进行插入 ，而在另一端进行删除 。允许 删除的一端称为队头 (front)，允许插入的一端称为队尾 (rear)。具有 先进先出 （FIFO）的特点。 6. 队列的定义 （1）顺序队列 #define MAXSIZE 100 typedef struct datatype dataMAXSIZE; int front; int rear; sequeue; sequeue * sq; （2）链式队列 typedef struct queuenode datatype data; struct queuenode *next; QueueNode; typedef s
21、truct QueueNode *front; QueueNode *rear; LinkQueue; 7. 循环队列 （1）假上溢 在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。尽管队 列中实际的元素个数远远小于 向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队 操作，该现象称为假上溢 。 （2）循环队列 为了解决假上溢问题，引入了循环队列的概念。在循环队列中进行出队 、入队 操作时，头尾指针仍要 加 1，朝前移动。只不过当头尾指针指向向量上界 ( MaxSize-1 ) 时，其加1 操作的结果是指向向量的下界 0。 （3）队空队满问题
22、入队时： 尾指针向前追赶头指针，出队时： 头指针向前追赶尾指针，故队空和队满时头尾指针均相等， 无法通过 sq-front= =sq- rear 来判断队列“空”还是“满”。 解决此问题的方法至少有两种： 1、另设一个布尔变量以区别队列的空和满； 2、少用一个元素空间为代价，入队前，测试尾指针 sq- rear+1=sq-front ，若相等则认为队满。 （4）常用操作 队空判断 ：sq-front = sq- rear 队满判断 ：sq- front =(sq- rear + 1) % maxSize 入队 ： sq- rear = (sq- rear + 1) % maxSize 9 /
23、62 出队 ： sq- front = (sq- front + 1) % maxSize 求队长 ：(sq- rear - sq- front+maxSize)%maxSize 8. 循环队列操作 （1）入队 检查队列是否已满，若队满，则进行溢出错误处理。 将队尾指针后移一个位置（即加1） ，指向下一单元。 将新元素赋给队尾指针所指单元。 Status EnQueue (SqQueue *Q, ElemType e) if ( (Q-rear+1)%MAXQSIZE = Q-front ) return(ERROR); /队满上溢 Q-rear=(Q-rear+1)%MAXQSIZE; Q-
24、dataQ-rear=e; return(True); （2）出队 检查队列是否为空，若队空，则进行下溢错误处理。 将队首指针后移一个位置（即加1） 。 取队首元素的值。 Status DeQueue (SqQueue *Q) if (Q-rear= Q-front) return(NULL); /队空下溢 Q-front=(Q-front+1)%MAXQSIZE; return(Q-dataQ-front); （3）置空队 Q-front=Q-rear= MAXQSIZE-1; （4）取队头 datatype GetHead(SqQueue *Q ) if (Q-front=Q-rear)
25、return(NULL); /队空 return (Q-data(Q-front+1)%MAXQSIZE ); （5）判断队空 int QueueEmpty(SqQueue *Q ) if (Q-front=Q-rear) return (True); else return (False); 9. 链式队列操作 （1）置空 void InitQueue(LinkQueue *Q) Q.front=Q.rear=(queuenode *)malloc(sizeof(queuenode ); 10 / 62 Q.front-next=Q.rear-next=NULL; （2）判断队空 int Q
26、ueueEmpty(LinkQueue *Q) return (Q.front-next= =NULL （3）入队 void EnQueue(LinkQueue *Q, datatype x) QueueNode *p; p=(QueueNode * )malloc(sizeof(QueueNode); pdata=x; pnext=NULL; Q-rear next=p; Q-rear=p; （4）出队 DeQueue(linkqueue *Q) linkqueue *p; datatype x; if (EMPTY(Q) return NULL; p = Q-front-next; Q-f
27、ront-next = pnext; if (p-next=NULL) Q-rear = Q-front; x = p-data; free(p); return x; 3.2 栈和队列的应用 1. 递归函数 递归函数又称为自调用函数，它的特点： 在函数内部可以直接或间接地调用函数自己。例如阶乘函数： n!=1, n=1 else return (n*FACT(n-1); 11 / 62 2. 算法表达式求值 计算机系统在处理表达式前，先设置两个栈：操作数栈(OPRD)：存放处理表达式过程中的操作数；运 算符栈 (OPTR)：存放处理表达式过程中的运算符。开始时，在运算符栈中先在栈底压入一个表
28、达式的结束 符“ #” 。 （1）中缀表示法 计算机系统在处理表达式时，从左到右依次读出表达式中的各个符号（操作数或运算符），每读 出一个符号ch 后，根据运算规则做如下处理： 如果 ch 是操作数，则将其压入操作数栈OPRD ，并依次读取下一个符号。 若 ch 是运算符，则： A、若读出的运算符的优先级大于OPTR 栈顶的运算符优先级，则将其压入OPTR ，并依次读下 一个符号。 B、若读出的是“#” ，且 OPTR 栈顶的运算符也是“#” ，则表达式处理结束，最后的计算结果 在 OPRD 的栈顶位置。 C、若读出的是“ （” ，则将其压入OPTR 。 D、若读出的是“） ” ，则： 若 O
29、PTR栈顶不是“ ( ” ，则从OPRD 连续退出两个操作数，从OPTR中退出一个运算符， 然后作相应的运算，并将运算结果压入OPRD ，然后返回a) ，让 ch 继续与 OPTR栈顶元素进 行比较。 若 OPTR栈顶为“ ( ” ，则从 OPTR 退出“ ( ” ，依次读下一个符号。 E、若读出的运算符的优先级小于OPTR栈顶运算符的优先级，则从OPRD 连续退出两个操作 数，从 OPTR中退出一个运算符，然后作相应的运算，将运算结果压入OPRD 。返回 (2) 继续 OPTR栈顶元素 进行比较。 （2）波兰表示法和逆波兰表示法 以 5 + ( 6 4 / 2 ) * 3为例，波兰表示法：+
30、 5 * - 6 / 4 2 3 逆波兰表示法：5 6 4 2 / - 3 * +。 运算时按从左到右的顺序进行，不需要括号。在计算表达式时，可设置一个栈，从左到右扫 描后缀表达式，每读到一个操作数就将其压入栈中；每读到一个运算符时，则从栈顶取出两个操 作数运算，并将结果压入栈中，一直到后缀表达式读完。最后栈顶就是计算结果。 3. 括号匹配 #include #define maxsize 100 typedef int datatype; typedef struct datatype datamaxsize; datatype top; seqstack; seqstack *s; voi
31、d build(); void push(); void pop(); int check(char ss); void main() char ssmaxsize; build(); printf(请输入要测试的算数表达式:); scanf(%s,ss); if(check(ss)=-1) printf(算数表达式不匹配!); else printf(算数表达式匹配!); void build() s=(seqstack*)malloc(sizeof(seqstack); s-top=-1; 12 / 62 int check(char ss) int i=0; while(ssi != 0
32、) i+; if(ssi = () push(); else if(ssi = ) pop(); return s-top; void push() s-top+; void pop() s-top-; 4. 回文串判断 #include #include #include #define maxsize 100 typedef struct char datamaxsize; int top; stack; typedef struct char datamaxsize; int front; int rear; queue; int isempty_queue(queue * stq) r
33、eturn stq-front = stq-rear; int isfull_queue(queue *stq) return stq-rear = maxsize -1 ; queue * init_queue() queue * tmp = (queue*) malloc(sizeof(queue); tmp-front = tmp-rear = 0; return tmp; char dequeue(queue * stq) if( isempty_queue(stq) ) printf(队列为空，无法出队n); exit(0); return stq-datastq-front+; v
34、oid inqueue(queue *stq, char value) if( isfull_queue(stq) ) printf(队列已满，无法入队n); exit(0); stq-datastq-rear+ = value; stack * init_stack() stack * tmp = (stack *) malloc( sizeof(stack) ); tmp-top = 0; return tmp; int isempty_stack(stack *stk) return stk-top = 0 ? 1 : 0; int isfull_stack(stack *stk) re
35、turn stk-top = maxsize -1 ? 1: 0; char pop(stack *stk) if( isempty_stack(stk) ) printf(堆栈为空，无法出栈n); exit(0); 13 / 62 return stk-data-stk-top; void push(stack *stk, char value) if( isfull_stack(stk) ) printf(堆栈已满，无法入栈n); exit(0); stk-datastk-top+ = value; void compare(stack * stk, queue *stq, char st
36、r, int len) int i; int flag = 0; char temp_stack; char temp_queue; for(i = 0; i len; i+) push(stk, stri); inqueue(stq, stri); for(i = 0; i top=0 ，满： ST-top=MAXSIZE-1 。 14 / 62 例 5：判定一个循环队列Q（存放元素位置：0 至 QueueSize-1 ）队满的条件是。 解： sq- front =(sq- rear + 1) % maxSize。 例 6：若用一个大小为6 的数组来实现环形队列，且当前rear和 front
37、的值分别是0 和 3，当从队列中删 除一个元素，再加入两个元素后，rear 和 front的值分别是 2 和 4 。 第四章串 4.1 串的基本概念 1. 串的概念 串(String)是零个或多个字符组成的有限序列。一般记作S= “a1a2a3an” ，其中 S 是 串名 ，用双引 号括起来的字符序列是串值 ；ai(1 i n)可以是字母、数字或其它字符；串中所包含的字符个数称为该 串的长度 。长度为零的串称为空串(Empty String)，它不包含任何字符。 2. 主串和子串 串中 任意个连续字符组成的 子序列 称为该串的 子串 。包含子串 的串相应地称为 主串 。通常将子串在主 串中 首
38、次 出现时的该子串的首字符 对应的主串中的序号，定义为子串在主串中的序号 （或 位置 ） 。 3 空白串和空串 通常将仅由一个或多个空格组成的串称为空白串 (Blank String)。空白串和空串的不同，如“”和 “” 分别表示 长度为 1 的空白串 和 长度为 0 的空串 。 4.2 串的存储结构 1. 顺序存储 #define MAXSTRLEN 256 char sMAXSTRLEN; 2. 堆分配存储 typedef struct char *ch; / 若是非空串 , 则按串长分配存储区, 否则 ch 为 NULL int length; /串长度 HString ; 这类串操作实
39、现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。 （1）求串长 int strlen(HString s) return s.length; （2）置空 Status clearstring(HString s) 15 / 62 if (s.ch) free(s.ch); s.ch=NULL; s.length=0; （3）生成堆 / /生成一个其值等于串常量chars 的串 t Status strassign(HString t, char *chars) if(t.ch) free(t.ch); /释放原空间 i=strlen(chars); /求串长 if (!i) t
40、.ch=NULL; t.length=0; /空串 else if(!(t.ch=(char *)malloc(i*sizeof(char) / 申请存储 exit(OVERFLOW); for (j=0;jT, 返回值 0; S=T, 返回值 0 ; ST, 返回值 0 for(i=0;is.length +i) if(s.chi!=t.chi) return(s.chi-t.chi); return s.length-t.length; （5）拼接函数 / 用 T 返回由 S1和 S2联接而成的新串 Status strcat(HString t, HString s1,HString s
41、2) if(!(t.ch)=(char*)malloc(s1.length+s2.length)*sizeof(char) exit(OVERFLOW); for(j=0; j s1.length ; j+) t.chj=s1.chj; for(k=0;k s2.length ;k+) t.chj+k=s2.chk; t.length=s1.length+s2.length; （6）求子串 / 用 Sub返回串 S的第 pos 个字符起长度为len 的子串 Status substr(HString sub, HString s, int pos, int len) if (poss.leng
42、th | lens.length-pos+1) return ERROR; if (sub.ch) free(sub.ch);/ 释放旧空间 16 / 62 if (!len) sub.ch=NULL; sub.length=0; / 空子串 else sub.ch=(char *)malloc(len*sizeof(char); for(j=0;jlen;j+) sub.chj=s.chpos-1+j; s.length=len; 3. 链式存储 typedef struct node char data; struct node *next; lstring; 但这种方式存储的密度太低，为
43、了提高存储的密度，使得每个节点能够存储多个字符，因此如下定义： #define CHUNKSIZE 80 / 可由用户定义的块大小，实际中根据需要设置大小 typedef struct Chunk / 结点结构 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString; 4.3 串的基本运算 1. 串赋值： strassign(S,T)，表示将T串的值赋给S串。 2. 联接： strcat(T1,T2
44、)，表示将T1 串和 T2 串联接起来，组成一个新的T1串。 3. 求串长度： strlen (T)，求 T 串的长度。 4. 子串： substr (S, i, len)，表示截取S串中从第i 个字符开始连续len 个字符，构成一个新串（显然 该新串是S串的子串）。 5. 串比较大小：strcmp(S,T)，比较 S 串和 T 串的大小，若ST，函数值为正。 6. 串插入： strinsert (S,i,T)，在 S串的第 i 个位置插入T 串。 7. 串删除： strdelete(S,i,len)，删除串S中从第 i 个字符开始连续len 个字符。 8. 求子串位置：index(S,T)，
45、求 T 子串在 S主串中首次出现的位置，若T 串不是 S 串的子串，则位置为 零。 9. 串替换： replace (S,T1,T2)，用串 T2替换串 S中出现的所有子串T1。 4.4 模式匹配 1.BF 算法 17 / 62 （1）算法思想： 将主串的第pos 个字符和模式的第1 个字符比较，若相等 ，继续逐个比较后续字符；若不等 ，从主串 的下一字符 (pos+1) 起，重新与第一个字符比较。直到主串的一个连续子串字符序列与模式相等。返回 值为 S中与 T 匹配的子序列 第一个字符的序号，即 匹配成功 。否则， 匹配失败 ，返回值 0 。 （2）程序段： int S_index(SStr
46、ing t, SString p, int pos) int n,m,i,j; m=strlen(t); n=strlen(p); for (i=pos-1; i=m-n; i+) for (j=0; j=1) ，否则返回0; 串类型为SString int n,m,i,j; m=strlen(s); n=strlen(t); for (i=0; i=m-n; i+) for (j=0; jn j+) ; if(j=n) return(i+1); return(0); 第五章数组和广义表 5.1 数组的定义 在 C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是
47、说： typedef elemtype array2mn; 等价于： 18 / 62 typedef elemtype array1n; typedef array1 array2m; 数组一旦被定义，它的维数 和维界 就不再改变。因此，除了结构的初始化 和销毁 之外，数组只有存取 元素 和修改元素值 的操作。 5.2 数组的存储方式 数组一般采用顺序存储，又分为行优先 和 列优先 。数组的地址计算具有以下前提三要素： 开始结点的存放地址（即基地址）。 维数和每维的上、下界。 每个数组元素所占用的单元数 L 。 设一般的二维数组是Ac1.d1, c2.d2，这里 c1,c2 不一定是0。 行优
48、先存储时的地址公式为：LOC(aij)=LOC(ac1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*L。其中，c1,c2为数 组基地址， i-c1为 aij之前的行数， d2-c2+1 为总列数， j-c2为 aij本行前面元素个数，L 为单个元素长度。 列优先存储的通式为：LOC(aij)=LOC(ac1,c2)+(j-c2)*(d1-c1+1)+(i-c1)*L。 5.3 特殊矩阵 1. 对称矩阵 （1）定义 在一个 n 阶方阵 A中，若元素满足下述性质：aij=aji（0i, jn-1 ） ，即元素关于主对角线对 称。 （2）存储方式 不失一般性，按“行优先顺序”存储主对角线
49、以下元素，存储空间节省一半，如下所示： a11 a21 a 22 a31 a32 a33 . an1 an2 an3ann 在这个下三角矩阵中，i 行(0 in) 恰有 i+1 个元素， 矩阵元素总数为：1+2+ +n=n*(n+1)/2， 因此，可以按从上到下、从左到右将这些元素存放在一个向量sa0.n(n+1)/2-1中。 若 i j ，则aij在下三角矩阵中。 aij之前的i行( 从第0 行到第i-1行) 一共有 1+2+ +i=i*(i+1)/2 个元素，在第i行上 aij 之前恰有j个元素 ( 即ai0,ai1,ai2, ,aij-1)，因此： k=i*(i+1)/2+j，0kn(n
50、+1)/2。 若 ij ，则 aij是在上三角矩阵中。因为 aij=aji，所以只要交换上述对应关系式中的 i 和 j 即 可 得到：k=j*(j+1)/2+i，0k1 时，元素 aij=0 。 在一个 n*n 的三对角矩阵中，只有(n-1)+n+(n-1)个非零元素，故只需3n-2 个存储单元，零元已不占用存 储单元。 将 n*n 的三对角矩阵A压缩存放到只有3n-2 个存储单元的sa 向量中， 假设仍 按行优先 顺序存放 则 sak 与 aij的对应关系为为： 在 aij之前有 i 行，共有 3*i-1个非零元素， 在第 i 行，有 j-i+1个非零元素， 即非零元素aij 的地址为： L
