算法与数据结构
课本THU的：算法与数据结构
离散数学IMPORTANT
各章作业20%
编写程序3个：一次实验课上一个 30分
期末考试 50%
1.绪论
1.1数据结构讨论的范畴（废话）
Algorithm+Data Structure = Programs
程序设计：为计算机处理问题编制一组指令集
算法：处理问题的策略
数据结构：问题的数学模型
1.2基本概念：
数据：所有能被输入到计算机中，并且能够被计算机处理的符号的集合。是计算机操作的对象的总称。
是计算机处理的信息的某种特定的符号表示的形式。
数据元素：是数据中的一个“个体”，是数据结构中讨论的基本单位。（可能是数据，也可能不是数据）
数据项：是数据结构中讨论的最小单位，数据元素可以是数据项的集合。
数据结构：带有结构的数据元素的集合，或者说数据结构是相互之间存在着某种逻辑关系的数据元素的集合。（离散数学中的集合相关知识）比如：次序关系，
1.2.1数据的逻辑结构（四类）：
- 线性结构：有一个前驱和后继特别头一个没有前驱，最后一个没有后继
- 树形结构：一个对象的后继不止一个
- 图状结构：前驱不止一个，后继不止一个。（多对多的关系）（自学图论）
- 集合结构：所有的数据对象都属于一个结合，各个元素直接没有一对多等等关系。
1.1.3数据结构的形式
\[Data\_Structure = (D,S)\]D是数据元素的有限集，S是D上关系的有限集。
数据的存储结构 ：是逻辑结构在存储器中的映象。
数据元素的映象：我们通过二进制位串来表示。
关系的映像方法的话，我们通过一下两种方式来实现。
- 顺序映像：以相对的存储位置表示后继关系，整个储存结构中只含有数据元素本身的信息。
- 链式存储：在数据元素中还加有一些附加信息，需要一个和第一个元素在一起的附加信息（指针）来指示下一个信息的存储位置。
1.2数据类型
1.2.1数据类型
在用高级程序语言编写程序中，必须对程序中出现的每一个变量、常量或表达式，明确说明它们所属的数据类型。
数据类型是一个值的集合和定义在此集合上的 一组操作的总称。 不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。
1.3抽象数据类型
抽象数据类型（Abstract Data Type简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。
1.3.1ADT有两个重要的特征：
- 数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。
- 数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。
1.3.2抽象数据类型的描述方法：
抽象数据类型可用（D，S，P）三元组表示。 其中：D 是数据对象；S 是 D 上的关系集；P 是对 D 的基本操作集。
1.3.2.1ADT定义
ADT抽象数据类型名{
数据对象：（数据对象的定义）
数据关系：（数据关系的定义）
基本操作：（基本操作的定义）
}
1.3.2.2基本操作定义
基本操作名（参数表）
初始条件：<初始条件描述>
操作结果：<操作结果描述>
- 引用参数:以&打头，除了可提供输入数值之外，还将返回操作结果。
- 赋值参数:只为操作提供输入值。
- 初始条件:描述了操作执行之前数据结构和参数应该满足的条件，若不满足，则操作失败，并返回相应出错信息。
- 操作结果：说明了操作正常完成之后，数据结构的变化状况和相应的返回结果。若初始条件为空，则省略之。
1.3.2.3抽象数据类型的表示和实现
抽象数据类型是通过固有数据类型来实现的。
1.4算法与算法衡量
1.4.1算法
算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特征：
1.有穷性：对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每一个步骤都能在有限时间内完成。
2.确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义以及如何执行。并且在任何情况下，算法都只有一条执行路径。
3.可行性 ：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现。
4.有输入 ：作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行的时候输入，而有的算法表面上不需要输入，但是实际上都已经被嵌入到算法之中。
5.有输出：它是一组与“输入”有确定关系的量值，使算法进行信息加工后得到的结果，这种确定关系即为算法的功能。
1.4.2算法设计的原则
1正确性：
2.可读性：
3.健壮性
4.高效率和低储存量需求
1.4.3算法效率衡量的方法
算法的储存量包括：
1.输入数据所占空间，2.程序本身所占空间，3.辅助变量所占空间。
算法的执行时间与原操作执行次数之和成正比。因此，以基本操作在算法中重复执行的次数作为算法运行时间的衡量标准。
若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。
若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。
第二章 线性表
线性结构的基本特征为：线形结构是一个数据元素的有序（次序）集：
1.集合中必存在唯一的“第一元素”；
2.集合中必存在唯一的“最后元素”；
3.除最后元素在外，均有唯一的后继；
4.除最后元素在外，均有唯一的前驱；
2.1线性表的类型定义
抽象数据类型线性表定于：
ADT List{
数据对象：
| D＝{ ai | ai ∈ElemSet, i=1,2,…,n, n≥0 }{称 n 为线性表的表长; 称 n=0 时的线性表为空表。} |
ai是元素的集合，比如花名册，则ai就是一个人个人信息集合。
| R1={<ai-1,ai> | an-1,an属于D,i=2…n} |
线性表的基本操作：
初始化操作：是一个开辟储存空间。（InitList）
结构销毁操作：清空储存空间。
引用型操作：
加工型操作：删插改移四项编辑操作。
}ADT List
引用型操作：
ListEmpty(L)、ListLength(L)、PriorElem(L,cur_e,&pre_e)、NextElem(L,cur_e,&next_e)、GetElem(L,i,&e)、LocateElem(L,e,compare())、ListTraverse(L,visit())
2.2线形表类型的实现–顺序映象
–以x的储存位置和y的储存位置之间某种关系表示逻辑关系<x,y>.
最简单的一种顺序映象方法是：令y的存储位置和x的存储位置相邻。用一组地址连续的存储单元一次存放线性表的数据元素。线性表的起始地址称作线性表的基地址（也就是a1的地址）。
以“存储位置相邻”表示有序对<$a_{i-1}$,$a_{i}$>即：LOC($a_{i}$)=LOC($a_{i-1}$)+C, C表示一个数据元素所占存储量。所有数据元素的储存位置均取决于第一个数据元素的存储位置。LOC($a_i$)=LOC($a_1$)+(i-1)C,其中LOC($a_1$)表示基地址.
顺序映象的C语言描述:
2.3线性表类型的实现–链式映象
2.3.1.单链表
用一组地址任意的存储单元存放线性表中的数据元素。
元素（数据元素的映象）和指针（指向后继元素的指针）构成了节点（node），以“结点的序列”表示线性表—-称作链表。
以线性表中第一个数据元素$a_1$的存储地址作为线性表的地址，称作线性表的头指针。有时候为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。
2.3.2结点和单链表的C语言描述
Typedef struct LNode{
ElemType data;//数据域
struct Lnode *next;// 指针域
}LNode, *LinkList;
2.3.3单链表操作的实现
GetElem(L,i,e)单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素，因此查找第i个数据元素的基本操作为：移动指针，比较j和i。令指针p始终指向线性表中第j个数据元素。
status GetElem_L(LinkList L,int i,ElemType &e){
//L是带头结点的链表的头指针，以e返回第i个元素。
p->next; j = 1;
while(p && j < i)
{
p = p->next;
++j;
}
//顺指针向后查找，直到p指向第i个元素。
if(!p||j>i)
return ERROR;
e = p->data;
return OK;
}//GetElem_L
ListInsert(&L,i,e) 在单链表中实现有序对<$a_{i-1}$,$a_{i}$>改变为<$a_{i-1}$,e>和<e,$a_{i}$>
可见在链表中插入结点只需要修改指针。但是同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。因此在单链表中第i个结点之前进行插入的基本操作为：找到线性表中第i-1个结点，然后修改其指向后继的指针。
Status ListInsert_L(LinkList L,int i,ElemType &e){
//L是带头结点的链表的头指针，本算法在链表中第i个结点之前插入新的元素e
P = L; j = 0;
while(P && j<i-1){
p = p->next;
++j;
}
if(!p || j>i-1)
return ERROR;
s = (LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}//LinstInsert_L
线性表的操作ListDelect(&L,i,&e)在链表中的实现：有序对<$a_{i-1}$,$a_{i}$>和<$a_{i}$,$a_{i+1}$>变为<$a_{i-1}$,$a_{i+1}$>
Status ListDelete_L(LinkList L,int i,ElemType &e){
//删除以L为头指针（带头结点）的单链表中第i个结点
p = L; j = 0;
while(p->next && j < i - 1){
p = p->next;
++j;
}
if(!(p->next)||j<i-1)
return ERROR;
q = p->next; p->next = q->next;
e = q->data;free(q);
return OK;
}//ListDelete_L
操作ClearList(&L)在链表中的实现：
void ClearList(&L){
//将单链表重新置为一个空表
while(L->next){
p = L->next; L->next=p->next;
free(p);
}
}
如何从线性表得到单链表
链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入的过程”。例如：位序输入n个数据元素的值，建立带头结点的单链表。
操作步骤：1.建立一个空链表；2.输入数据元素$a_n$,建立结点并插入；3.输入数据元素$a_{n-1}$建立结点并插入；4.依次类推，直到输入$a_1$为止。
void CreateList(LinkList &L, int n){
L = (LinkList)malloc(Sizeof(LNode));
L->next = Null;//先建立一个带头结点的单链表。
for(i=n;i>0;--i){
p = (LinkList)malloc(sizeof(Lnode));
scanf(&p->data);//输入元素
p->next = L-next; L->next = p;//插入
}
}//CreateList
2.3.4一个带头结点的线性链表类型
Typeof struct Node{//结点类型
ElemTpye data;
struct LNode. *next;
} *Link, *Position;
Status MakeNode( Link &p, ElemType e);
//分配由p指向的值为e的结点，并返回OK，若分配失败，则返回ERROR。
void FreeNode(Link &p);
//释放p所指结点。
typedef struct{//链表类型
Link head,tail; //分别指向头结点和最后一个结点的指针
int len; //指示链表的长度
Link current; //指向当前被访问的结点的指针，初始位置指向头结点。
}LinkList
//链表的基本操作：
Status InitList( LinkList &L ); O(1)
Status DestroyList( LinkList &L ); O(n)
Status ListEmpty(LinkList L ); O(1)
int ListLength( LinkList L ); O(n)
Status Prior( LinkList L ); O(n)//改变当前指针指向其前驱
Status Next( LinkList L); O(1)//改变当前指针指向其后继
ElemType GetCurElem( LinkList L ); O(1) //返回当前指针所指数据元素
Status Locate( LinkList L, int i ) O(n) //改变当前指针指向第i个结点
Status locateElem( LinkList L, ElemType e, status(*compare)(ElemType, Elemtype));
//如果存在与e满足函数compare()判定的元素，则移动当前指针指向第i个满足条件的元素的前驱；O(n)
Status ClearList (LinkList &L);//重置L为空表 O(n)
Status SetCurElem(Linklist &L, ElemType e);//更新当前指针所指数据元素。O(1)
Status Append(LinkList &L,Link s );//在表尾结点之后链接一串结点。 O(s)
Status InsAfter(LinkList &L, Elemttype e );//将元素e插入在当前指针之后 O(1)
Status DelAfter(LinkList &L,ElemType e);//删除当前指针之后的结点 O(1)
2.3.5其他形式的链表
1.双向链表
typedef struct DuLNode{
ElemType data; //数据域
struct DuLNode *prior; //指向前驱的指针域
struct DulNode *next; //指向后继的指针域
}DuLNode, *DuLinkList;
2.循环链表
最后一个结点的指针域的指针又指回第一个结点的链表，和单链表唯一的区别就在于，循环链表中最后一个结点的不再是后继为空，而是“后继是否为头结点”。
3.双向循环链表
双向循环链表的特点：1.”查询”和单链表相同。2.“插入”和“删除”时候需要同时修改两个方向上的指针。
2.4一元多项式的表示
一元稀疏多项式可以写成$P_n(x)=p_1x^{e_1}+p_2x^{e_2}+···+p_mx^{e_m}$其中：$p_i$是指数为$e_i$的项的非零系数，
$0≤e_1<e_2<—<e_m=n$ 可以表示为下列的线性表系数：(($p_1$,$e_1$),($p_2$,$e_2$),—,($p_n$,$e_n$))
例如：$P_{999} = 7x^3 - 2x^{12} - 8x^{999}$可用线性表((7,3),(-2,12),(-8,999))表示。
抽象数据类型一元多项式的定义如下：
ADT Polynominal{
//数据对象
D = {ai | ai ∈ TermSet,i=1,2,...,m , m>=0 TermSet中包含了一个表示系数的实数和表示指数的整数}
//数据关系
R1 = {<ai-1,ai> | ai-1,ai ∈ D, i =2,...,n且ai-1中的指数值小于ai的指数值}
//基本操作
PolynLength(P)
}
稀疏多项式的求导函数
//注意这个地方多项式中随着结点向后走，这个阶数是增加的
void Difference(LinkedPoly &pa){
LinkedPoly p,s;
p = pa;
s = p->next;
while(!p->next == pa)//此处认为是循环链表
{
if(s->exp == 0)
{
p->next = s->next;
free(s);
s= p->next;
}
else
{
s->coef = s->exp * s->coef;
s->exp --;
s = s->next;
p = p->next;
}
}
}
第三章 栈和队列
栈和队列是限定插入和删除只能在表的“断点”进行的线性表。
3.1栈的类型定义
ADT Stack{
//数据对象：
D = {ai | ai ∈ ElemSet, i = 1,2,...,n, n>=0}
//数据关系：
R1 = {<ai-1,ai> | ai-1,ai ∈ D}
//基本操作
Push(&S,e);//插入元素e为新的栈顶元素
Pop(&S,&e);//删除S的栈顶元素，并用e返回其值
}
3.2栈的应用举例
3.2.1数制转换
N = (N div d) * d + N mod d
| N | N div 8 | N mod 8 |
|---|---|---|
| 1348 | 168 | 4 |
| 168 | 21 | 0 |
| 21 | 2 | 5 |
| 2 | 0 | 2 |
从上到下是我们的计算顺序，而从下到上是我们的输出顺序，我们输出的是2504。
void conbersion(){
InitStck(S);
scanf("%d",N);
while(N){
Push(S, N % 8);
N = N / 8;
}
while(!StackEmpty){
Pop(S,e);
printf("%d",e);
}
}//conversion
3.2.2括号匹配的检验
假设在表达式中( [ ] ( ) )或 [ ( [ ] [ ] ) ]等为正确格式。
算法的设计思想：
1）凡出现左括弧，则进栈；
2）凡出现右括弧，首先检查栈是否空，若栈空，则表明改“右括弧”多余，否则和栈顶元素比较，若匹配，则左括弧出栈，否则表示不匹配。
3）表达式检验结束时，若栈为空，则表明表达式中国匹配正确，否则表明“左括弧”有余。
Status matching(string& exp){
int state = 1;
while(1<=Length(exp) && state){
switch of exp[i]{
case 左括弧：{
Push(S.exp[i]);i++;break;
}
case ")":{
if(NOT StackEmpty(S)&&GetTop(S)="("){
Pop(S,e);i++;
}
else{
state = 0;
break;}
}
}
}
3.2.3行编译程序问题
在用户输入一行的过程中，允许用户输入出错，并在发现有错误时可以及时修改。
合理的做法是：设立一个输入的缓冲区，用以接收用户的一行字符，然后逐行存入用户数据区，并假设“#”为推格符，“@”为退行符。
whli##ilr#e(s#*s)
while(*s)
outcha@putchar(*s=#++)
putchar(*s++)
while(ch!=EOF){//EOF为全文结束符
while(ch!=EOF&&ch!="\n"){
switch(ch){
case "#":
Pop(S,c);
break;
case "@":
ClearStack(S);
break;
default:
Push(S,ch);
break;
}
if(ch!=EOF){
ch = getchar();
}
}
}
3.2.4迷宫求解
求迷宫路径算法的基本思想是：
- 如果当前位置“可通”，则 纳入路径，继续前进；
- 若当前位置“不可通”，则后退，换方向继续探索；
- 若四周“均无通路”，则将当前位置从路径中删除出去；
从迷宫中一条从入口到出口的路径的算法：(最开始在右侧开始试探)
do{
若当前位置可通则{
将当前位置插入栈顶；
若该位置是出口，则算法结束；
否则切换当前位置的东邻方块为新的当前位置；
}else{
若栈不空且栈顶位置尚有其他方向未被探索
则假设新的位置为：沿顺时针方向旋转找到的栈顶位置的下一相邻块；
若栈不空但栈顶位置的四周均不可通，
则{
删去栈顶位置；
若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至栈空；
}
}
}
若栈空，则表明迷宫没有出路
3.2.5表达式求值
表达式 的样式 (操作数) + (运算符) + (操作符)
操作数 的样式 简单变量 ｜ 表达式
简单变量 的样式 表示符｜无符号整数 \(例如：Exp = a \times b + (c-d/e) \times f\) $前缀式：+\times a b \times -c/def$
$中缀式：a\times b + c - d /e \times f$
$后缀式：ab\times cde/-f\times$
结论：
- 操作数之间的相对位置不变；
- 运算符的相对次序不同；
- 中缀式丢失了括弧信息，致使次序不正确；
- 前缀式的运算法规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式
- 后缀表达式的运算规则为：运算符在式中出现的顺序恰为表达式的运算顺序；每个运算符和在它之前出现且紧靠它的两个操作数构成了一个最小表达式。
如何从后缀表达式求值？先找运算符，再找操作数。
1.创建栈 2.从左向右顺序获取中缀表达式
a.数字直接输出 b.运算符 情况一：遇到左括号直接入栈，遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出，同时左括号出栈但是不输出。
情况二：遇到乘号和除号直接入栈，直到遇到优先级比它更低的运算符，依次弹栈。
情况三：遇到加号和减号，如果此时栈空，则直接入栈，否则，将栈中优先级高的运算符依次弹栈（注意：加号和减号属于同一个优先级，所以也依次弹栈）直到栈空或则遇到左括号为止，停止弹栈。（因为左括号要匹配右括号时才弹出）。
情况四：获取完后，将栈中剩余的运算符号依次弹栈输出
3.2.6实现递归
3.3栈类型的实现
顺序栈、
顺序栈实现栈满的判定条件为：S.top-S.base==S.stacksize;
顺序栈栈空的判定条件为：S.top == S.base;
链栈
3.4队列的类型定义
ADT Queue{
//数据对象
D = {ai | ai ∈ ElemSet, i = 1,2,...,n, n>=0}
//数据关系
R1 = {<ai-1 , ai>|ai-1,ai∈ D}
//约定a1为队列头，an端位队列尾
//基本操作
InitQueue(&Q);
DestoryQueue(&Q);
QueueEmpty(Q);
QueueLength(Q);
GetHead(Q, &e);
ClearQueue(&Q);
EuQueue(&Q,e);
DeQueue(&Q,&e);
QueueTraver(Q,visit());
}
3.5队列类型的实现
链队列
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
type struct{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
//创建队列
Status InitQueue(LinkQueue &Q){
Q.front = Q.rear =(QueuePtr)malloc(sizeof(QNode))
if(!Q.front)exit(OVERFLOW);
Q.front->next = NULL;
return OK;
}
//插入元素
Status EnQueue(LinkQueue &Q,QElemType e){
p = (QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data = e;
p->next = NULL;
Q.rear->next = P;
Q.rear = p;
return OK;
}
Status DeQueue(SqQueue &Q,ElemType &e)
{
if(Q.front == Q.rear) return ERROR;
p = Q.front -> next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p) Q.rear = Q.front;
free(p);
return OK;
}
循环队列
队列满的判定条件为：(Q.rear + 1) % MAXSIZE == Q.front
判断队列为空的条件为：Q.front== Q.rear;
第四章 串
4.1串的抽象数据类型
串的基本操作：
StrAssign (&T, chars)
//chars 是字符串常量。把 chars 赋为 T 的值。
DestroyString(&S)
//串 S 存在。串 S 被销毁.
StrCopy (&T, S)
//串 S 存在。操作结果：由串 S 复制得串 T
StrLength(S)
//串 S 存在,返回 S 的元素个数, 称为串的长度
StrCompare (S, T)
//串 S 和 T 存在,如果S>T,则返回值>0,若S = T，则返回值 = 0,若S < T，则返回值 < 0。
//这个地方特别指出来，小写字母比大写字母大。
Concat (&T, S1, S2)
//用 T 返回由 S1 和 S2联接而成的新串。
//例如： Concate( T, "man", "kind") 求得 T = "mankind".
StrEmpty (S)
//串S存在若 S 为空串，则返回TRUE，否则返回 FALSE。
SubString (&Sub, S, pos, len)
//用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
ClearString (&S)
//将S清为空串
Index (S, T, pos)
//若主串 S 中存在和串 T 值相同的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置;否则函数值为0。
Replace (&S, T, V)
//用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。
StrInsert (&S, pos, T)
//在串S的第pos个字符之前插入串T。
StrDelete (&S, pos, len)
//从串S中删除第pos个字符起长度为len的子串。
4.2串的表示和实现
一、串的定长顺序存储表示
typedef unsigned char Sstring[MAXSTRLEN + 1];
//0号单元存放串的长度
//特点：串的实际长度可在这个预设定的长度范围之外，超出这个范围的串值被舍去，称之为截断。
//按这种串的表示方法实现的串运算时，其基本操作为"字符序列的复制"
//由于截断的特点，所以在串的链接中，可以分为三种情况。
Status Concata(SString S1,SString2 S2,SString &T){
if(S1[0]+S2[0] <= MAXSTRLEN){
}
else if(S1[0]<=MAXSTRLEN){
}else{
}
}
//思路很清晰我就不展开了。
二、串的堆分配存储表示
通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( )和free( )进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值。
这类串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。
//特点是：以一组地址连续的储存单元存放串值字符序列，但它们的储存单元是在程序执行过程中动态分配而得到的。
typedef struct {
char *ch;
// 若是非空串，则按串长分配存储区，
// 否则ch为NULL
int length; // 串长度
} HString;
Status Concat(HString &T, HString S1, HString S2) {
// 用T返回由S1和S2联接而成的新串
if (T.ch) free(T.ch); // 释放旧空间
if (!(T.ch = (char *)malloc((S1.length+S2.length)*sizeof(char))))
exit (OVERFLOW);
T.ch[0..S1.length-1] = S1.ch[0..S1.length-1];
T.length = S1.length + S2.length;
T.ch[S1.length..T.length-1] = S2.ch[0..S2.length-1];
return OK;
} // Concat
三、串的块链存储表示
也可用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。 \(储存密度 = \frac{数据元素所占储存位}{实际分配的储存位}\)
4.3 串的模式匹配算法
第六章 树和二叉树
邻接矩阵：
分成两个部分去存储，一部分存储顶点，定点用一维数组来储存，一部分存储关系，用二维数组来存储图中边的信息，。
