C语言-数据结构-串数组广义表

一,串

1,基本概念

2,串的基本运算

3,串的链式存储:

4,优缺点

5,算法练习(替换)

6,串的匹配问题:

(1)BF算法

(2)KMP算法

二,数组

1,基本性质

2,一维数组

3,二维数组

3,特殊矩阵的压缩存储:

1、对称矩阵的压缩存储:

2、三角矩阵的压缩存储

3、对角矩阵的压缩存储

4,稀疏矩阵的压缩存储

三,广义表

1,广义表的性质:

2,计算表头&表尾:

一,串

串（或字符串）是由零个或多个字符组成的有限序列。串中所含字符的个数称为该串的长度（或串长），含零个字符的串称为空串，用Ф表示。

1,基本概念

串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的。

子串：一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。

真子串是指不包含自身的所有子串。

2,串的基本运算

1,StrAssign(&s,cstr)：将字符串常量estr赋给串s，即生成其值等于cstr 的串s。

2 StrCopy(&s,t)：串复制。将串t赋给串s

3 StrEqual(s,t)：判串相等。若两个串s与t相等则返回真；否则返回假。

4 StrLength(s): 求串长。返回串s中字符个数。

5 Concat(s,t)：串连接：返回由两个串s和t连接在一起形成的新串。

6 SubStr(s,i,j): 求子串。返回串s中从第i(1≤i≤n）个字符开始的、由连续j个字符组成的子串。

7,InsStr(s1,i,s2)：插入。将串s2插入到串s1的第i (1≤i≤n+1）个字符中，即将s2的第一个字符作为s1的第i个字符，并返回产生的新串。

8 DelStr(s,i,j)：删除。从串s中删去从第i(1≤i≤n）个字符开始的长度为j的子串，并返回产生的新串。

9,RepStr(s,i,j,t)：替换。在串s中，将第i (1≤i≤n) 个字符开始的j个字符构成的子串用串t替换，并返回产生的新串。

10,DispStr(s)：串输出。输出串s的所有元素值。

3,串的链式存储:

#define MAXSIZE 255
typedef struct {char ch[MAXSIZE + 1];//通常0下标的空间不进行存储int lengh;//当前串的长度
}SString;

算法:设计顺序串上实现串比较运算Strcmp(s,t)的算法。例如： "ab" < "abcd" "abcd" < "abd"

int Strcmp(SqString s,SqString t){  int i,  comlen;if (s.length<t.length)  comlen=s.length;   else comlen=t.length;for (i=0;i<comlen;i++)  {if (s.data[i]>t.data[i])return 1;if (s.data[i]<t.data[i])return -1;}if (s.length==t.length) //s==treturn 0;else if (s.length>t.length)return 1;else  return -1;}

4,优缺点

优点:操作方便;

缺点:存储密度较低,司仪可以存放多个字符在一个节点里面,以克服这种缺点.。

通常将链串中每个节点所存储的字符个数称为节点大小

#define CHUNKSIZE 80
typedef struct Chunk{char ch[CHUNKSIZE];struct Chunk* next;
}SString;
typedef struct {Chunk* head;Chunk* tail;int curlen;}LString;

5,算法练习(替换)

在链串中，设计一个算法把最先出现的子串“ab” 改为“xyz”

void Repl(LiString *&s){ LiString *p=s->next,*q;int find=0;while (p->next!=NULL && find==0){ if (p->data==‘ a’ && p->next->data==‘b’){       p->data=‘x’; p->next->data=‘z’;q=(LiString *)malloc(sizeof(LiString));q->data=‘y’;  q->next=p->next;  p->next=q;find=1;}else p=p->next; }
}

6,串的匹配问题:

(1)BF算法

Brute-Force简称为BF算法，亦称简单匹配算法。采用穷举的思路。算法在字符比较不相等，需要回溯（即i=i-j+1）：即退到s中的下一个字符开始进行继续匹配。


int Index_BF(SString S, SString T)
{int i = 1,j = 1;while (i <= S.lengh && j <= T.lengh){if (S.ch[i] == T.ch[j]) {i++;j++;}else {i = i - j + 2;j = 1;}}if (j >= T.lengh)return i - T.lengh;else return 0;
}

时间复杂度是O(n*m)

(2)KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的，简称KMP算法。该算法较BF算法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高

思路:

nextval值:下标为1的,next为0,nextval也为0,b的next为1,b和下标为1的进行比较,如果不相等则b的nextval等于b的next,如果相等就看下标为1的元素(a),看a的next对应的值和a相比,如果不相等取a的next的值.

时间复杂度是O(n+m)

二,数组

1,基本性质

将数组的所有元素存储在一块地址连续的内存单元中，这是一种顺序存储结构。

1,数组中的数据元素数目固定。

2,数组中的所有数据元素具有相同的数据类型。

3,数组中的每个数据元素都有一组唯一的下标。

4,数组是一种随机存储结构。可随机存取数组中的任意数据元素。

2,一维数组

从逻辑结构上看，一维数组A是n（n＞1）个相同类型数据元素a1、a2、…、an构成的有限序列，其逻辑表示为： A=（a1，a2，…，an）其中，ai（1≤i≤n）表示数组A的第i个元素。

一旦a0的存储地址LOC(a0)确定，并假设每个数据元素占用k个存储单元，则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出:

3,二维数组

一个m行n列的二维数组A可以看作是每个数据元素都是相同类型的一维数组的一维数组

对于一个m行n列的二维数组Am× n ，存储方式：以行序为主序的存储以列序为主序的存储

以行序为主序的存储方式:

以列序为主序的存储方式:

3,特殊矩阵的压缩存储:

1、对称矩阵的压缩存储:

对称元素的值是相等的,以行序为主序存储其下三角+主对角线的元素。

储存的元素个数为:1+2+3...+n=[(1+n)n]/2

2、三角矩阵的压缩存储

储存的元素个数为:1+2+3...+n=[(1+n)n]/2+1(最后一个存放常量)

下三角矩阵:

3、对角矩阵的压缩存储

4,稀疏矩阵的压缩存储

一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t十分小时，即s<<t,，称该矩阵为稀疏矩阵.

稀疏矩阵中的每一个非零元素需由一个三元组： (i ，j ，ai,j ) 唯一确定，稀疏矩阵中的所有非零元素构成三元组线性表.

#define MaxSize 100 //矩阵中非零元素最多个数
typedef struct{ int r; //行号int c; //列号ElemType d; //元素值} TupNode; //三元组定义
typedef struct{ int rows; //行数值int cols; //列数值int nums; //非零元素个数TupNode data[MaxSize];}TSMatrix; //三元组顺序表定义

稀疏矩阵的十字链表表示:

#define M 3
#define N 4
#define Max ((M)>(N)?(M):(N)) //矩阵行列较大者
typedef struct mtxn{int row;//行号int col;//列号struct mtxn *right,*down; //向右和向下的指针union//共用体类型{int value;struct mtxn *link;} tag;} MatNode;  //十字链表节点类型声明

问:稀疏矩阵压缩后具有随机存取的特性吗??

答:稀疏矩阵用十字链表作存储结构自然失去了随机存取的功能。即便用三元组表的顺序存储结构，存取下标为 i和j的元素时，要扫描三元组表，时间复杂度为O(t)，因此也失去了随机存取的功能。

三,广义表

LS=(a1,a2,a3,...an),LS是广义表的名称,n是它的长度,在广义表的定义中,ai可以是单个元素,也可以是广义表,分别称之为广义表LS的原子和子表.习惯上大写字母表示广义表的名称,小写字母表示原子,称第一个元素a1为LS的表头(可以是原子,也可以是子表),其余元素组成的表,是LS的表尾

	表长	元素	表头	表尾
A=()	0
B=(())	1	空表	()	()
C=(a,(b,c))	2	原子a,子表(b,c)	a	((b,c))
D=(x,y,z)	3	原子	x	(y,z)
E=(C,D)	2	子表	C	(D)
F=(a,F)	2	a为原子,F为子表	a	(F)

1,广义表的性质:

(1）广义表中的数据元素有相对次序；一个直接前驱和一个直接后驱

(2）广义表的长度定义为最外层所包含元素的个数；如：C=(a, (b,c)）是长度为2的广义表。

(3）广义表的深度定义为该广义表展开后所含括号的重数； A=(b,c）的深度为1,B= (A, d) 的深度为2,C= (f, B, h) 的深度为3。注意："原子"的深度为0;"空表"的深度为1。

(4）广义表可以为其他广义表共享；如：广义表 B就共享表A。在B中不必列出A的值，而是通过名称来引用，B=(A)。

(5）广义表可以是一个递归的表。如： F=(a, A)=(a, (a, (a, …))) 注意：递归表的深度是无穷值，长度是有限值。

2,计算表头&表尾:

D=(E,F)=((a,(b,c)),F)
GetHead(D)=E	GetTail(D)=(F)
GetHead(E)=a	GetTail(E)=((b,c))
GetHead(((b,c)))=(b,c)	GetTail(((b,c)))=()
GetHead((b,c))=b	GetTail((b,c))=(c)
GetHead((c))=c	GetTail((c))=()