第4章 串、数组和广义表

第4章串、数组和广义表

一．填空题

1. 串的数据元素是字符，顺序，链式，即只有当两个串的长度相等，并且各个对应位置的

字符都相等时才相等。

2. 零个字符的串、零；由一个或多个空格字符组成的串、其包含的空格个数 3. 任意个连续的字符组成的子序列 4. 模式匹配，Index(S,T,pos)，S 5. 14 6. 5

7. LOC (A[0][0])+(n*i+j)*k 8. 326 9. 1208

10. 行号，列号，元素

二．单项选择题

题号 答案 题号 答案 1 B 11 B 2 B 12 B 3 B 13 A 4 B 14 LKCID 5 D 15 D 6 C 16 D 7 DB 17 CB 8 C 9 C 10 B 三．算法设计题

1.

#include #define Maxsize 100 typedef struct {

char data[Maxsize]; int length; }Sqstring;

void Strassign(Sqstring *s,char cstr[]) { int i;

for(i=0;cstr[i]!='\\0';i++) s->data[i]=cstr[i];

s->length=i; }

void Dispstr(Sqstring s) { int i; if(s.length>0) {

for(i=0;i

void GetNextval(Sqstring t,int nextval[]) //由模式串t求出nextval值 {

int j=0,k=-1; nextval[0]=-1; while (j

if (k==-1 || t.data[j]==t.data[k]) { j++;k++;

if (t.data[j]!=t.data[k]) nextval[j]=k; else

nextval[j]=nextval[k]; }

else k=nextval[k]; } }

int KMPindex(Sqstring s,Sqstring t,int i) //{

int nextval[Maxsize],j=0; GetNextval(t,nextval);

while (i

if (j==-1 || s.data[i]==t.data[j]) { i++;j++; }

else j=nextval[j]; }

if (j>=t.length) return(i-t.length); else return(-1); }

void Delstr(Sqstring *s,Sqstring t) {

修正的KMP算法,而且增加一个标志i int j,m; j=0; while(j!=-1) {

j=KMPindex(*s,t,j); if(j!=-1) {

for(m=j;mlength-t.length;m++) s->data[m]=s->data[m+t.length]; s->length=s->length-t.length; } } }

void main() {

Sqstring s,t;

Strassign(&s,\ printf(\输出s：\ Dispstr(s);

Strassign(&t,\ printf(\输出t:\

Dispstr(t); Delstr(&s,t); printf(\新的s为:\

Dispstr(s); }

2. 略

3. (1) （b） (2) （d） 4 (1)

GetHead[GetHead[GetTail[GetTail[(((apple)),((pear)),(banana),orange)]]]]

(2) GetHead[GetHead[GetTail[GetHead[GetTail[(apple,(pear,(banana),orange))]]]]]