《数据结构(3 结构串 & 4线性链表)》由会员分享，可在线阅读，更多相关《数据结构(3 结构串 & 4线性链表)（20页珍藏版）》请在金锄头文库上搜索。
1、C/C+与数据结构郭 鹏 城市与环境科学学院1C/C+与数据结构结构串3. 结构串 字符串 有效字符序列 字符常量： 单引号为界限符 字符串：“”双引号为界限符号 结尾用0作为结束标志符 存储在字符数组中 char S18 = “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,
2、const char *s2)33. 结构串 问题 存储字符串的是静态数组，声明时候需要指定数组空间，大 小已经确定，在运行时候无法改变 比如用一个字符串，首先要知道要申请多少空间， char? =“fwfewfwesewaewedwew”多少？ 基本功能不够强大？ 无字串替换 要自动申请空间-动态分配单元 void * malloc(unsigned size); void * calloc(unsigned numElements,unsigned siezeOfElements); 程序员必须负责释放空间4内存泄漏：一个程序消耗内存，减少其它程序可用内存，引起系统与硬盘 交换虚拟内存，使
3、得程序在到达内存资源限制时变慢或崩溃，也可能系统 停止工作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
4、 *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); /查找53.
5、 结构串 类型声明 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); 63. 结构串 注意！ 不能直接用“=”赋值 不能用一个结构串初始化另一个 不能作为函数参数 不能作为函数返回值73. 结构串 求字串：SubString（） 串
6、插入（也可利用SubString） 串删除（同上） 模式匹配 可考虑直接找第一个字符后比较模式串的后续字串 根据该思想上面修改程序，添加一个新的函数 FindPat_1()8C/C+与数据结构线性链表4. 线性链表 顺序表的优点 连续存放数据，物理相邻，无需为表示结点间的逻辑关系而增加额外的存储空间，效率高 数组：最直接表现形式-int A5 可以随机存取表中任一元素 顺序表的缺点 插入和删除操作是，平均需移动一半的元素，效率低 因为要求占有连续空间，如果预先进行存储分配，当表长度变化较 大时难以确定合适的存储空间大小，如果按可能达到的最大长度预 先分配表空间，则容易造成一部分空间长期闲置得不
7、到利用；如果 估计不足，则易造成内存溢出；如用指针方式定义，用动态分配存 储空间，此种方式事件开销较大（扩充数组空间过程）。104. 线性链表 为避免顺序表的缺点-链式存储结构（链表） 优点：逻辑相邻的元素不要求物理相邻 缺点：失去了顺序表可随机存取的优点 链表适用于插入或删除频繁，存储空间需求不定的情形 。114.线性链表 单链表 线性链表 特点： 用一组任意的存储单元存储线性表的数据元素，存储单元可 以连续也可以不连续 基于上述要求，必须在一个元素中表达与其后续元素的关系 设计结构： 本身元素信息 + 指向后继的信息 两部分信息组成数据元素的存储映象结点（Node） 数据域 Node *
8、Next; Void SetNode(Node * front, type item, Node * nextptr); Node * NextNode(const Node *ptr); void InsertAfter(Node *ptr, Node *nextptr); Node * DeleteAfter(Node * ptr); Node * GetNode(Type item, Node * nextPtr);144.线性链表 void InsertAfter(Node *ptr, Node *nextptr);154.线性链表 Node * DeleteAfter(Node * ptr);164.线性链表 单链表逆置 while(NextNode(ptr)!=0) nptr=DeleteAfter(ptr);/nptr指向删除的结点 /把删除的结点*nptr插到头结点*f之后 InsertAfter( 头结点：在单链表第一个结点前附设的一个节点 头结点的指针域存储指向第一个结点的指针174.线性链表 双向链表 单链表中，如果要查找某结点的直接前驱，必须从表头 指针出发，SO双向链表 两个指针域， 一个指向直接后继，一个指向直接前驱18插入删除4.线性链表 循环链表 循环单链表 循环双链表19最后一个结点的指针域的指针又指回第一个 结点的链表20
