数据结构 教学课件 作者 晋良颖 4.ppt

《数据结构 教学课件 作者 晋良颖 4.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第四章串和数组4．1字符串4．1．1串的定义和操作串的操作，介绍以下几种：1、给串变量赋值（strcpy或=）：2、串的复制（strcpy，strncpy）：3、串的比较（strcmp）4、求串的长度（strlen）：退出5、串连接（strcat）6、定位函数(strstr)7、取子串(substring)8、串插入(strinsert)9、串删除(strdelete)10、串替换(strreplace)4．1．2串的存储结构和相应的操作实现1、串的顺序存储（1）、取子串算法4．1如书第80页所示算法4．2如书第81

2、页所示（2）、求两个串的最长公共子串算法4．3如书第81页所示1、串的堆分配存储方式[例3]串插入函数（使用堆分配）算法4．4、如书第82页所示算法4．5如书第83页所示[例4]串删除函数（使用堆分配）算法4．6如书第84页所示[例5]对一组字符串的排序算法4．7、如书第84页所示算法4.8、如书第84页所示图4-13、串的链式存储方式#defineN5typedefstructstrnode{charsdata[N];structstrnode*next;}STRNODE；图4-24．1．3正文模式匹配算法4．9如

3、书第87页所示如果要找出所有匹配的子串位置，可以执行下列程序段对算法4．8反复调用：beginpos=0;len=strlen(t);while(*(s+beginpos))/*当主串不空*/{i=strindex(s,t,beginpos);/*返回模式在主串中的匹配位置*/if(i==-1){printf(“没有与模式串相匹配的子串！”);break;}beginpos=i+len;}4．1．4文本编辑表4．1表4．24．2数组4．2．1数组的定义和操作1、数组的定义2、数组的操作（1）、通过给定的下标取出相

4、应的元素值；（2）、通过给定的下标修改相应的元素值；4．2．2数组的顺序表示设二维数组A[N][M]中每个元素占L个存储单元，则A[i][j]在映象区中的存储地址可以由下式确定：LOC(aij)=LOC(a00)+（i*N+j）*L；设三维数组A[P][N][M]每个元素需用占L个存储地址，A[i][j][k]在映象区的地址可表示为：LOC(aijk)=LOC(a000)+（i*M*N+j*N+k）*L。4．2．3矩阵的压缩存储1、特殊矩阵的存储（1）、三角矩阵（将A[N][N]，把它的非0元按行主顺序，逐行、逐个存

5、入B[N*（N+1）/2]中）①、上三角矩阵中有A[i][j]与B[k]的对应关系如下：k=i*(2*N-i+1)/2+j-i；②、下三角矩阵中有A[i][j]与B[k]的对应关系如下：k=i*(i+1)/2+j图4-3（2）、对称矩阵可作为三角矩阵处理（3）、带状矩阵（或三对角矩阵）可以把其中的非0元存到B[3*N-2]中图4-41、稀疏矩阵图4．5稀疏矩阵示例（1）、顺序存储可以定义三元组的结点类型如下：#defineN1000typedefstruct/*三元组结构*/{inti,j;/*非0元的行下标、列下标

6、*/elemtypee;/*非0元的元素类型*/}TRIPLE;typedefstruct{TRIPLEdata[N];/*非0元的三元组表*/intmu,nu,tu;/*稀疏矩阵的最大行数、最大列数、非0元个数*/}MATRIX;图4-6算法4.10如书第95页所示（2）、十字链表typedefstructolnode{inti,j;inte;/*结点的三元组，这里假定矩阵元素为整型，可以根据需要修改*/structolnode*right,*down;/*指向行和列的（向右和向下）的指针*/}OLNODE,*OL

7、NODEPTR;typedefstruct{OLNODEPTR*rhead,*chead;/*十字链表的行、列指针数组的二级指针表示，建表时按mu,nu的实际值分配空间*/intmu,nu,tu;/*矩阵的最大行数、列数和非0元个数*/}CROSSLIST;/*十字链表类型*/图4-7算法4．11如书第97页所示