现的字符。
17．在顺序串上实现串的判等运算EQUAL(S,T)。 18．在链串上实现判等运算EQUAL(S,T)。
19．若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针），设计一个算法将串S中首次与串T匹配的子串逆值。
20．用串的其他运算构造串的子串定位运算index。
第二章 参考答案 一、名词解释 （略） 二、填空题 1、结点 起始 终端 序号 位置 前趋 后趋 2、（） ф 3、前趋 前趋 后趋 后趋 4、线性 5、线性 长度 表长 6、空表 7、初始化INITLATE（L） 求表长LENGTH（L） 读表长GET（L，i） 定位LOCATE （L，X） 插入INSERT（L，X，i） 删除DELETE（L，i） 8、逻辑结构中相邻的结点在存储结构中仍相邻 9、b+（i-1）x k 10、L．data[j]=L．data[j-1] 11、n O(n) n/2 O(n) 12、L.data[j-2]=l.data[j-1] 13、n-1 o(n) (n-1)/2 O(n) 14、i=1 i≦L.last 15、O(n) O(1) 16、L.last L.data[i-1] 17、单链表 循环链表 双链表 18、指针 19，单链表 20、头结点 表结点 21、首结点 尾结点 任何信息、特殊标志 表长 22、头结点 头结点 23、t=malloc(size) t->next=NULL 24、p=haed p=p->next 25、(p->next!=NULL)&&(j
31、单向循环链表（简称循环链表） 双向循环链表（简称双链表） 32、NULL 头结点 33、双链表 三、单项选择题 1、②2、①3、①4、②5、① 6、②7、③8、③9、④10、② 11、④12、③13、⑤14、④15、③ 16、①17、②18、③19、④20、④ 21、④22、223、②24、③25、④ 26、②27、③28、④29、①30、④ 31、②32、②33、④34、④35、③ 36、③37、②38、③39、②40、① 四、简答及应用 1、线性表的数据元素的类型为datatype，则在语言上可用下述类型定义来描述顺序表： const maxsize=顺序表的容量； typedef struct { datatype data[maxsize] int last; }sqlist; sqlist L; 数据域data是一个一维数组，线性表的第1，2??，n个元素分别存放在此数组的第0，1，??，last-1个分量中，数据域last表示线性表当前的长度，而last-1是线性表的终端结点在顺序表中的位置。常数maxsize称为顺序表的容量，从last到maxsize-1为顺序表当前的空闲区（或称备用区）。 Sqlist类型完整地描述了顺序表的组织。L被说明为sqlist类型的变量，即为一顺序表，其表长应写为L.last，而它的终端结点则必须写为 L.data[L.last-1]。 2、假设数据元素的类型为datatype。单链表的类型定义如下： typedef struct node *pointer struct node {datatype data; pointer next; }; typedef pointer lklist; 其中，①ponter是指向struct node类型变量的指针类型;②struct node是结构体类型规定一个结点是由两个域data和next组成的记录，其中data的结点的数据域,next是 12
结点的链域；③lklist与pointer相同类型，用来说明头指针变量的类型，因而lklist也就被用来作为单链表的类型。 3、typedef struct dnode *dpointer; struct dnode {datatype data; dpointer prior,next; } typedaf dpinter dlklist; 链域prior和next分别指向本结点数据域data所含数据元素的直接前趋和直接后继所在的结点。所有结点通过前趋和后继指针链接在一起，再加上起标识作用的头指针，就得到双向循环链表。 4、顺序串的类型定义与顺序表类似，可描述如下： const maxlen=串的最大长度 typedef struct {char ch[maxlen] int curlen; }string 5、链串的类型定义为： const nodesize=用户定义的结点大小; typedef struct node *pointer; struct node {char ch[nodesize] poinernext; } typedef pointer strlist; 当结点大小为1时，可将ch域简单地定义为：char ch 6、head称为头指针变量，该变量的值是指向链表的第一个结点的指针，称为头指针。头指针变量是用于存放头指针的变量。 为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结点。
头指针变量的作用：对单链表中任一结点的访问，必须首先根据头指针变量中存放的头指针找到第一个结点，再依次按各结点链域存放的指针顺序往下找，直到找到或找不到。头指针变量具有标识单链表的作用，故常用头指针变量为命名单链表。 头结点的作用：头结点的数据域可以不存储任何信息，也可以存放一个特殊标志或表长。其作用是为了对链表进行操作时，将对第一个结点煌处理和对其它结点的处理统一起来。 7、循环单链表、循环双链表。 ; 五、算法设计 13
1、 分析：(1)当A、B表都不为空时，比较A，B表中各元素对应位置的内容的大小，进而判断A，B的大小。 (2)当A，B表都不为空时，且A，B表中各各元素对应位置的内容相同时，比较A，B的长度，进而判断A，B的大小或是否相等。 const maxsize=顺序表的容量; typedef struct {int data[maxsize] int last; }sqlist; int CMP_sqlist(sqlist A ,sqlist B) { for (i=0;(iB.data[i])return(1); } if(A.last= =B.last) return(0); else if(A.last>B.last) return(1); else return(-1); } 2、(1)定位LOCATE(L，X) 在带头结点类单链表上实现的算法为： int locate_lklist(lklist head,datatype x) /*求表head中第一个值等于x的的序号，不存在这种结点时结果为0*/ {p=head->next;j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于X的结点时经，继续扫描*/ if (p->data = =x) return(j); else return(0); } 在无头结点的单链表上实现的算法为： int Wlocate(lklist head,datatype X) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ {p=head; j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于X的结点时经，继续扫描*/ if( p->data = =X) return(j); else return(0); 14
} (2)按序号查找find(L,i) 在带头结点的单链表上实现的算法为： pointer find_lklist(lklist head , int i); { j=1; p=head->next; while((j<1)&&(p!=NULL)){p=p->next; j++} if(i= = j) return(p); else return(NULL); } 在无头结点的单链表上实现的算法为： pointer find_lklist(lklist head , int i); { j=1; p=head; while((j<1)&&(p!=NULL)){p=p->next; j++} if(i= = j) return(p); else return(NULL); } (3)、插入INSERT(L，X，i) 在带头结点单链表上实现的算法为： void insert_lklist(lklist head,datatype x,int I) /*在表haed的第i个位置上插入一人以x为值的新结点*/ {p=find_lklist(head,i-1); /*先找第i-1个结点*/ if(p= =NULL)reeor(“不存在第i个位置”)/*若第i-1个结点不存在，退出*/ else{s=malloc(size);s->data=x /*否则生成新结点*/ s->next=p->next /*结点*p在链域值传给结点*s的链域*/ p->next=s; /*修改*p的链域*/ } } 在无头结点的单链表上实现的算法为： void Winsert(lklist head,dataytpe X,int i) /*在表haed的第i个位置上插入一人以x为值的新结点*/ {if(i<=0) error(“i<=0”); else{ s=malloc(size);s->data=X; /*否则生成新结点*/ if(i= =1){s->next=head;head=s;} else{ p=wfind_lklist(lklist head,i-1); if(p= =NULL) error(“i>n+1”); else{s->next=p->next;p->next=s;} } } 15