/* c4-3.h 串的块链存储表示 */
#define CHUNKSIZE 4 /* 可由用户定义的块大小 */
typedef struct Chunk
char ch[CHUNKSIZE];
struct Chunk *
typedef struct
Chunk *head,* /* 串的头和尾指针 */
int /* 串的当前长度 */
/* bo4-3.c 串采用块链存储结构(由c4-3.h定义)的基本操作(16个) */
void InitString(LString *T)
{ /* 初始化(产生空串)字符串T。另加 */
(*T).curlen=0;
(*T).head=NULL;
(*T).tail=NULL;
Status StrAssign(LString *T,char *chars)
{ /* 生成一个其值等于chars的串T(要求chars中不包含填补空余的字符) */
/* 成功返回OK，否则返回ERROR */
int i,j,k,l;
Chunk *p,*q;
i=strlen(chars); /* i为串的长度 */
if(!i||strchr(chars,blank)) /* 串长为0或chars中包含填补空余的字符 */
return ERROR;
(*T).curlen=i;
j=i/CHUNKSIZE; /* j为块链的结点数 */
if(i%CHUNKSIZE)
for(k=0;k&j;k++)
p=(Chunk*)malloc(sizeof(Chunk));
return ERROR;
if(k==0) /* 第一个链块 */
(*T).head=q=p;
q-&next=p;
for(l=0;l&CHUNKSIZE&&*l++)
*(q-&ch+l)=*chars++;
if(!*chars) /* 最后一个链块 */
(*T).tail=q;
q-&next=NULL;
for(;l&CHUNKSIZE;l++) /* 用填补空余的字符填满链表 */
*(q-&ch+l)=
return OK;
Status StrCopy(LString *T,LString S)
{ /* 初始条件:串S存在。操作结果:由串S复制得串T(连填补空余的字符一块拷贝) */
Chunk *h=S.head,*p,*q;
(*T).curlen=S.
p=(*T).head=(Chunk*)malloc(sizeof(Chunk));
*p=*h; /* 复制1个结点 */
p=(Chunk*)malloc(sizeof(Chunk));
q-&next=p;
p-&next=NULL;
(*T).tail=p;
return OK;
return ERROR;
Status StrEmpty(LString S)
{ /* 初始条件:串S存在。操作结果:若S为空串,则返回TRUE,否则返回FALSE */
if(S.curlen) /* 非空 */
return FALSE;
return TRUE;
int StrCompare(LString S,LString T)
{ /* 若S&T,则返回值&0;若S=T,则返回值=0;若S&T,则返回值&0 */
int i=0; /* i为当前待比较字符在S,T串中的位置 */
Chunk *ps=S.head,*pt=T. /* ps,pt分别指向S和T的待比较块 */
int js=0,jt=0; /* js,jt分别指示S和T的待比较字符在块中的位序 */
while(i&S.curlen&&i&T.curlen)
i++; /* 分别找S和T的第i个字符 */
while(*(ps-&ch+js)==blank) /* 跳过填补空余的字符 */
if(js==CHUNKSIZE)
}; /* *(ps-&ch+js)为S的第i个有效字符 */
while(*(pt-&ch+jt)==blank) /* 跳过填补空余的字符 */
if(jt==CHUNKSIZE)
}; /* *(pt-&ch+jt)为T的第i个有效字符 */
if(*(ps-&ch+js)!=*(pt-&ch+jt))
return *(ps-&ch+js)-*(pt-&ch+jt);
else /* 继续比较下一个字符 */
if(js==CHUNKSIZE)
if(jt==CHUNKSIZE)
return S.curlen-T.
int StrLength(LString S)
{ /* 返回S的元素个数,称为串的长度 */
Status ClearString(LString *S)
{ /* 初始条件: 串S存在。操作结果: 将S清为空串 */
Chunk *p,*q;
(*S).head=NULL;
(*S).tail=NULL;
(*S).curlen=0;
return OK;
Status Concat(LString *T,LString S1,LString S2)
{ /* 用T返回由S1和S2联接而成的新串 */
LString a1,a2;
InitString(&a1);
InitString(&a2);
StrCopy(&a1,S1);
StrCopy(&a2,S2);
(*T).curlen=S1.curlen+S2.
(*T).head=a1.
a1.tail-&next=a2.
(*T).tail=a2.
return OK;
Status SubString(LString *Sub, LString S,int pos,int len)
{ /* 用Sub返回串S的第pos个字符起长度为len的子串。 */
/* 其中,1&pos&StrLength(S)且0&len&StrLength(S)-pos+1 */
Chunk *p,*q;
int i,k,n,flag=1;
if(pos&1||pos&S.curlen||len&0||len&S.curlen-pos+1)
return ERROR;
n=len/CHUNKSIZE; /* 生成空的Sub串 */
if(len%CHUNKSIZE)
n++; /* n为块的个数 */
p=(Chunk*)malloc(sizeof(Chunk));
(*Sub).head=p;
for(i=1;i&n;i++)
q=(Chunk*)malloc(sizeof(Chunk));
p-&next=q;
p-&next=NULL;
(*Sub).tail=p;
(*Sub).curlen=
for(i=len%CHUNKSIZE;i&CHUNKSIZE;i++)
*(p-&ch+i)= /* 填充Sub尾部的多余空间 */
q=(*Sub). /* q指向Sub串即将复制的块 */
i=0; /* i指示即将复制的字符在块中的位置 */
p=S. /* p指向S串的当前块 */
n=0; /* n指示当前字符在串中的序号 */
while(flag)
for(k=0;k&CHUNKSIZE;k++) /* k指示当前字符在块中的位置 */
if(*(p-&ch+k)!=blank)
if(n&=pos&&n&=pos+len-1) /* 复制 */
if(i==CHUNKSIZE)
{ /* 到下一块 */
*(q-&ch+i)=*(p-&ch+k);
if(n==pos+len-1) /* 复制结束 */
return OK;
int Index(LString S,LString T,int pos)
{ /* T为非空串。若主串S中第pos个字符之后存在与T相等的子串, */
/* 则返回第一个这样的子串在S中的位置,否则返回0 */
int i,n,m;
if(pos&=1&&pos&=StrLength(S)) /* pos满足条件 */
n=StrLength(S); /* 主串长度 */
m=StrLength(T); /* T串长度 */
while(i&=n-m+1)
SubString(&sub,S,i,m); /* sub为从S的第i个字符起,长度为m的子串 */
if(StrCompare(sub,T)!=0) /* sub不等于T */
void Zip(LString *S)
{ /* 压缩串(清除块中不必要的填补空余的字符)。加 */
int j,n=0;
Chunk *h=(*S).
q=(char*)malloc(((*S).curlen+1)*sizeof(char));
while(h) /* 将LString类型的字符串转换为char[]类型的字符串 */
for(j=0;j&CHUNKSIZE;j++)
if(*(h-&ch+j)!=blank)
*(q+n)=*(h-&ch+j);
*(q+n)=0; /* 串结束符 */
ClearString(S); /* 清空S */
StrAssign(S,q); /* 重新生成S */
Status StrInsert(LString *S,int pos,LString T)
{ /* 1&pos&StrLength(S)+1。在串S的第pos个字符之前插入串T */
int i,j,k;
Chunk *p,*q;
if(pos&1||pos&StrLength(*S)+1) /* pos超出范围 */
return ERROR;
StrCopy(&t,T); /* 复制T为t */
Zip(S); /* 去掉S中多余的填补空余的字符 */
i=(pos-1)/CHUNKSIZE; /* 到达插入点要移动的块数 */
j=(pos-1)%CHUNKSIZE; /* 到达插入点在最后一块上要移动的字符数 */
if(pos==1) /* 插在S串前 */
t.tail-&next=(*S).
(*S).head=t.
else if(j==0) /* 插在块之间 */
for(k=1;k&i;k++)
p=p-& /* p指向插入点的左块 */
q=p-& /* q指向插入点的右块 */
p-&next=t. /* 插入t */
t.tail-&next=q;
if(q==NULL) /* 插在S串后 */
(*S).tail=t. /* 改变尾指针 */
else /* 插在一块内的两个字符之间 */
for(k=1;k&=i;k++)
p=p-& /* p指向插入点所在块 */
q=(Chunk*)malloc(sizeof(Chunk)); /* 生成新块 */
for(i=0;i&j;i++)
*(q-&ch+i)= /* 块q的前j个字符为填补空余的字符 */
for(i=j;i&CHUNKSIZE;i++)
*(q-&ch+i)=*(p-&ch+i); /* 复制插入点后的字符到q */
*(p-&ch+i)= /* p的该字符为填补空余的字符 */
q-&next=p-&
p-&next=t.
t.tail-&next=q;
(*S).curlen+=t.
return OK;
Status StrDelete(LString *S,int pos,int len)
{ /* 从串S中删除第pos个字符起长度为len的子串 */
int i=1; /* 当前字符是S串的第i个字符(1～S.curlen) */
Chunk *p=(*S). /* p指向S的当前块 */
int j=0; /* 当前字符在当前块中的位序(0～CHUNKSIZE-1) */
if(pos&1||pos&(*S).curlen-len+1||len&0) /* pos,len的值超出范围 */
return ERROR;
while(i&pos) /* 找第pos个字符 */
while(*(p-&ch+j)==blank) /* 跳过填补空余的字符 */
if(j==CHUNKSIZE) /* 应转向下一块 */
i++; /* 当前字符是S的第i个字符 */
if(j==CHUNKSIZE) /* 应转向下一块 */
}; /* i=pos,*(p-&ch+j)为S的第pos个有效字符 */
while(i&pos+len) /* 删除从第pos个字符起到第pos+len-1个字符 */
while(*(p-&ch+j)==blank) /* 跳过填补空余的字符 */
if(j==CHUNKSIZE) /* 应转向下一块 */
*(p-&ch+j)= /* 把字符改成填补空余的字符来＂删除＂第i个字符 */
i++; /* 到下一个字符 */
if(j==CHUNKSIZE) /* 应转向下一块 */
(*S).curlen-= /* 串的当前长度 */
return OK;
Status Replace(LString *S,LString T,LString V)
{ /* 初始条件: 串S,T和V存在,T是非空串（此函数与串的存储结构无关） */
/* 操作结果: 用V替换主串S中出现的所有与T相等的不重叠的子串 */
int i=1; /* 从串S的第一个字符起查找串T */
if(StrEmpty(T)) /* T是空串 */
return ERROR;
i=Index(*S,T,i); /* 结果i为从上一个i之后找到的子串T的位置 */
if(i) /* 串S中存在串T */
StrDelete(S,i,StrLength(T)); /* 删除该串T */
StrInsert(S,i,V); /* 在原串T的位置插入串V */
i+=StrLength(V); /* 在插入的串V后面继续查找串T */
}while(i);
return OK;
void StrPrint(LString T)
{ /* 输出字符串T。另加 */
int i=0,j;
while(i&T.curlen)
for(j=0;j&CHUNKSIZE;j++)
if(*(h-&ch+j)!=blank) /* 不是填补空余的字符 */
printf("%c",*(h-&ch+j));
printf("\n");
void DestroyString()
{ /* 块链类型的字符串无法销毁 */
/* main4-3.c 检验bo4-3.c的主程序 */
char blank='#'; /* 全局变量,用于填补空余 */
#include"c1.h"
#include"c4-3.h"
#include"bo4-3.c"
void main()
char *s1="ABCDEFGHI",*s2="12345",*s3="",*s4="asd#tr",*s5="ABCD";
LString t1,t2,t3,t4;
InitString(&t1);
InitString(&t2);
printf("初始化串t1后，串t1空否？%d(1:空 0:否) 串长=%d\n",StrEmpty(t1),StrLength(t1));
k=StrAssign(&t1,s3);
printf("串t1为: ");
StrPrint(t1);
printf("出错\n"); /* 不能生成空串 */
k=StrAssign(&t1,s4);
printf("串t1为: ");
StrPrint(t1);
printf("出错\n"); /* 不能生成含有变量blank所代表的字符的串 */
k=StrAssign(&t1,s1);
printf("串t1为: ");
StrPrint(t1);
printf("出错\n");
printf("串t1空否？%d(1:空 0:否) 串长=%d\n",StrEmpty(t1),StrLength(t1));
StrAssign(&t2,s2);
printf("串t2为: ");
StrPrint(t2);
StrCopy(&t3,t1);
printf("由串t1拷贝得到串t3,串t3为: ");
StrPrint(t3);
InitString(&t4);
StrAssign(&t4,s5);
printf("串t4为: ");
StrPrint(t4);
Replace(&t3,t4,t2);
printf("用t2取代串t3中的t4串后，串t3为: ");
StrPrint(t3);
ClearString(&t1);
printf("清空串t1后，串t1空否？%d(1:空 0:否) 串长=%d\n",StrEmpty(t1),StrLength(t1));
Concat(&t1,t2,t3);
printf("串t1(=t2+t3)为: ");
StrPrint(t1);
printf("去除不必要的占位符后，串t1为: ");
StrPrint(t1);
pos=Index(t1,t3,1);
printf("pos=%d\n",pos);
printf("在串t1的第pos个字符之前插入串t2，请输入pos: ");
scanf("%d",&pos);
k=StrInsert(&t1,pos,t2);
printf("插入串t2后，串t1为: ");
StrPrint(t1);
printf("插入失败！\n");
printf("求从t1的第pos个字符起,长度为len的子串t2,请输入pos,len: ");
scanf("%d,%d",&pos,&len);
SubString(&t2,t1,pos,len);
printf("串t2为: ");
StrPrint(t2);
printf("StrCompare(t1,t2)=%d\n",StrCompare(t1,t2));
printf("删除串t1中的子字符串：从第pos个字符起删除len个字符。请输入pos,len：");
scanf("%d,%d",&pos,&len);
k=StrDelete(&t1,pos,len);
printf("从第%d位置起删除%d个元素后串t1为:",pos,len);
StrPrint(t1);
阅读(...) 评论()
浏览次数：【图文】04-第四章(串)-me (2)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
04-第四章(串)-me (2)
大小：1.15MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢导读：（）正确错误2、串也有两种存储结构：顺序结构和链式结构，（）正确错误3、串的链式结构优于其顺序存储结构，（）正确错误4、在串的块链存储结构中，A、顺序存储结构B、链式存储结构，C、索引存储结构，D、散列存储结构，5、对一个以邻接表为存储结构、有n个顶点e条边的无向连通图，1、图结构中，C、字符指针D、文件指针5、以下关于串的存储方式的说法中正确的是＿＿＿＿＿＿＿＿＿＿。A、定长顺序表示和堆分配C、字符指针 D、文件指针 5、以下关于串的存储方式的说法中正确的是＿＿＿＿＿＿＿＿＿＿。 A、定长顺序表示和堆分配表示都是串的顺序存储表示 B、定长顺序表示的串的存储空间是编译时预先分配的一个比较大的连续空间 C、堆分配表示的串的存储空间是在程序执行过程中动态分配的 D、堆分配存储表示时的空串不占用连续的存储区 第三题、判断题（每题1分，5道题共5分） 1、空串和空格串是相同的。 （ ） 正确 错误 2、串也有两种存储结构：顺序结构和链式结构。 （ ） 正确 错误 3、串的链式结构优于其顺序存储结构。 （ ） 正确 错误 4、在串的块链存储结构中，设尾指针的目的是为了便于进行联结操作。 （ ） 正确 错误 5、在C语言中，用动态分配函数进行管理的自由存储区称为\堆\。 （ ） 正确 错误
第六章 第一题、单项选择题（每题1分，5道题共5分） 1、一个有n个顶点的无向图若是连通图，则至少有＿＿＿＿＿＿＿＿条边。 A、n B、n+1 C、n-1 D、n/2 2、在一个有向图中，所有顶点的入度之和等于所有边数的＿＿＿＿＿＿＿＿倍。 A、1/2 B、1 C、2 D、4 3、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的＿＿＿＿＿＿＿＿倍。 A、1/2 B、1 C、2 D、4 4、邻接表是图的一种＿＿＿＿＿＿＿＿。 A、顺序存储结构 B、链式存储结构 C、索引存储结构 D、散列存储结构 5、对一个以邻接表为存储结构、有n个顶点e条边的无向连通图，深度优先遍历图的时间复杂度是＿＿＿＿＿＿＿＿。 A、O(n) B、O(n*n) C、O(n+e) D、O(n*e) 第二题、多项选择题（每题2分，5道题共10分） 1、判断一个有向图是否存在回路，可以用＿＿＿＿＿＿＿＿。 A、深度优先遍历算法 B、广度优先遍历算法 C、拓扑排序方法 D、求最短路径方法 2、下列说法中正确的有＿＿＿＿＿＿＿＿。 A、图的遍历过程中每个顶点仅被访问一次 B、图的深度优先遍历算法不适用于有向图 C、图的深度优先遍历过程是一个递归过程 D、遍历图的基本方法有深度优先遍历和广度优先遍历 3、任何一个无向连通图的最小生成树＿＿＿＿＿＿＿＿。 A、只有一棵 B、可能有多棵 C、可能不存在 D、可能有一棵 4、在拓扑排序中，拓扑序列的第一个顶点一定是＿＿＿＿＿＿＿＿的顶点。 A、入度为0 B、没有前驱 C、出度为0 D、没有后继 5、有向图的拓扑有序序列＿＿＿＿＿＿＿＿。 A、可能存在 B、一定存在 C、可能有多个 D、肯定有多个 第三题、判断题（每题1分，5道题共5分） 1、图结构中，每个结点的前驱结点数和后续结点数都可以有任意多个。（ ） 正确 错误 2、在n个顶点的无向图中，若边数大于n-1，则该图一定是连通图。 （ ） 正确 错误 3、只要能提高关键活动的速度，就能缩短整个工程的工期。 （ ） 正确 错误 4、从某顶点开始对有向图进行深度优先遍历，若所得的遍历序列唯一，则可断定其弧数为n-1（n为图中顶点数）。 （ ） 正确 错误 5、若有向图的拓扑排序序列唯一，则图中必定仅有一个顶点的入度为0，一个顶点的出度为0。 （ ） 正确 错误
第七 第一题、单项选择题（每题1分，5道题共5分） 1、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相等，用顺序查找来确定结点所在的块，每块有＿＿＿＿＿＿＿个元素时查找效率最佳。 A、10 C、6 B、25 D、625 2、有一个有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}中折半查找值为82的结点时，＿＿＿＿＿＿＿次比较后查找成功。 A、1 C、4 B、2 D、8 3、高度为5的二叉平衡树至少有＿＿＿＿＿＿＿个结点。 A、10 C、15 B、12 D、17 4、假设有k个关键字互为同义词，若用线性探测再散列法将这k个关键字存入散列表中，则至少需要进行＿＿＿＿＿＿＿次探测。 A、k-1 C、k+1 B、k D、k(k+1)/2 5、在对查找表的查找过程中，若被查找的元素不存在，则把该元素插入到查找表中，这种方式主要适合于＿＿＿＿＿＿＿。 A、静态查找表 C、静态查找表与动态查找表 B、动态查找表 D、两种表都不合适 第二题、多项选择题（每题2分，5道题共10分） 1、分块查找的平均查找长度与＿＿＿＿＿＿＿有关。 A、表长 B、块数 C、块中元素个数 D、索引表的查找方式 2、构造哈希表时解决冲突常用的方法有＿＿＿＿＿＿＿。 A、数字分析法、除余法、平方取中法 B、链地址法、线性探测再散列法 C、开放定址法 D、再哈希法、建立公共溢出区 3、在各种查找方法中，平均查找长度与表长有关的查找方法是＿＿＿＿＿＿＿。 A、哈希表查找 B、顺序查找 C、折半查找 D、排序树查找 4、对于10个元素的有序表进行折半查找，须比较3次方可查找成功的元素在表中的位置有＿＿＿＿＿＿＿。 A、1 B、2 C、3 D、4 E、5 F、6 G、7 H、8 5、对序列{50，72，43，85，75，20，35，45，30}按顺序建二叉排序树，则在树中须比较3次方可查找成功的元素有＿＿＿＿＿＿＿。 A、72 B、43 C、85 D、75 E、20 F、35 包含总结汇报、文档下载、党团工作、外语学习、办公文档、工作范文、教学研究、资格考试、旅游景点、出国留学以及数据结构(c)测试等内容。本文共5页
相关内容搜索【图文】第四章 串_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
&&数据结构课件
大小：285.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢502 Bad Gateway
502 Bad Gateway
openresty/1.11.2.2}