数据结构(3 结构串 4线性链表).ppt

4.线性链表 单链表逆置 while(NextNode(ptr)!=0) { nptr=DeleteAfter(ptr);//nptr指向删除的结点 //把删除的结点*nptr插到头结点*f之后 InsertAfter(f,nptr); } 头结点：在单链表第一个结点前附设的一个节点 头结点的指针域存储指向第一个结点的指针 * 4.线性链表 双向链表 单链表中，如果要查找某结点的直接前驱，必须从表头指针出发，SO?双向链表 两个指针域， 一个指向直接后继，一个指向直接前驱 * 插入 删除 4.线性链表 循环链表 循环单链表 循环双链表 * 最后一个结点的指针域的指针又指回第一个结点的链表 * * LOGO LOGO C/C++与数据结构 郭　 鹏 guopgis@163.com 城市与环境科学学院 * C/C++与数据结构 结构串 3. 结构串 字符串 有效字符序列 字符常量：‘’ 单引号为界限符 字符串：“”双引号为界限符号 结尾用‘\0’作为结束标志符 存储在字符数组中 char S1[8] = “china” 数组长度不能小于串长+1 char * ps = “china” 处理原型 unsigned int strlen(const char *s) char * strcpy(char *s1,const char *s2) char * strcat(char *s1,const char *s2) int strcmp(const char *s1,const char *s2) * 3. 结构串 问题 存储字符串的是静态数组，声明时候需要指定数组空间，大小已经确定，在运行时候无法改变 比如用一个字符串，首先要知道要申请多少空间， char[?] =“fwfewfwesewaewedwew”—多少？ 基本功能不够强大？？ 无字串替换 要自动申请空间--》动态分配单元 void * malloc(unsigned size); void * calloc(unsigned numElements,unsigned siezeOfElements); 程序员必须负责释放空间 * 内存泄漏：一个程序消耗内存，减少其它程序可用内存，引起系统与硬盘交换虚拟内存，使得程序在到达内存资源限制时变慢或崩溃，也可能系统停止工作 3. 结构串 结构串声明 void SetString(String *s,const char *c); //构造 void FreeString(String *s); //析构 void StrAssign(String *s,const String *cs);//cs赋值给s void CStrAssign(String *s,const char *c); //串c赋值给s int StrCompare(const String *s,const String *cs);//比较 void StrConcat(const String *s,const String *cs,String *w);//连接 void SubString(const String *s,String *cs,int id,int count); //取子串 void StrInsert(String *s,const String *cs,int id); //插入 void StrErase(String *s,int id,int count); //删除 char StrGetData(const String *s,int id); //取值 int Find(const String *s,char ch,int start); //查找 * 3. 结构串 类型声明 struct String { char * str; int size}； 构造函数 SetString void SetString(String *s,const char *c) //构造 { s-size=strlen(c); s-str=(char*)malloc(s-size+1); if(s-str==NULL) StrError(SetString:overflow!); strcpy(s-str,c); } * 3. 结构串 注意！！！ 不能直接用“=”赋值 不能用一个结构串初始化另一个 不能作为函数参数 不能作为函数返回值 * 3. 结构串 求字串：SubString（） 串插入（也可利用SubString） 串删除（同上） 模式匹配 可考虑直接找第一个字符后比较模式串的后续字串 [根据该思想上面修改程序，添加一个新的函数FindPat_1()] *