工大数据结构第二章作业(6)

for (int j=0;j

cout<

void main() {

QUEUE Q; Q.front=0; Q.count=0;

for (int i=1; i<10; i++) enQueue(i, Q); cout<<\队头：\ print(Q);

for (i=0; i<6; i++) deQueue(Q); cout<<\删除前六个元素后的队列：\ print(Q); }

十、设主串T=“abcaabbabcabaacbacba“，模式为p=“abcabaa”。 1、计算模式p的nextval函数值

2、不写算法，只画出利用KMP算法进行模式匹配时，每一趟的匹配过程。 要求：

1、写出模式p的nextval值；

2、画出KMP算法的每一趟匹配过程（可参照教材P61从第8行开始的内容）； 3、不需要编写程序。

Nextval：a b c a b a a 011 0 1 3 2 第一趟匹配： i=5,j=5

abcaabbabcabaacbacba abcab(匹配失败) 第二趟匹配： i=5,j=1

abca abbabcabaacbacba abc（匹配失败） 第三趟匹配： i=7,j=1

abcaab babcabaacbacba a（匹配失败） 第四趟匹配： i=8,j=1

Abcaabbabcabaacbacba abcabaa 匹配成功！

十一、假设表达式中允许包含三种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈（用数组表示的栈）判断表达式中的括号是否正确配对。 要求：

1、定义栈以及栈的型，栈中所存放元素的类型为字符型，定义枚举类型Boolean，其中两个元素分别为TRUE和FALSE。

2、定义栈的各种操作。

3、定义函数Boolean check(char *s); 判断s中的括号是否正确配对，如果正确配对，返回TRUE，否则返回FALSE。

4、在主函数中验证所编写函数的正确性。

//栈的数组实现

//此处将栈底规定在数组的底部，即让maxlength-1指向栈底的第一个元素 #include using namespace std;

#define maxlength 100//栈的容量

//typedef int Elementtype;//数制转换中元素类型为int

typedef char Elementtype;//括号匹配中元素类型为字符型char enum Boolean{TRUE,FALSE};

struct STACK//定义整型线性数组栈 { int top; Elementtype elements[maxlength]; };

bool isEmpty(STACK S)//栈是否为空 { if(S.top>=maxlength) return true; else return false; }

void makeNull(STACK &S)//栈置空 { S.top = maxlength; }

Elementtype top(STACK S)//返回栈顶元素 {

if(isEmpty(S)) return NULL; else return(S.elements[S.top]); }

void pop(STACK &S)//出栈,删除栈顶元素 { if(isEmpty(S)) cout<<\栈为空！\ else S.top++; }

void push(STACK &S, Elementtype x)//进栈 { if(S.top == 0) cout<<\栈已满！\ else { --S.top; S.elements[S.top] = x; } }

//=====================================================数制转换 void convert(int num,STACK &S,int n)//进制转换函数 { while(num!=0) { push(S,num%n); num/=n; } }

void print(STACK S)//输出转后的结果 { while(!isEmpty(S)) { cout<

//====================================================括号匹配

Boolean check(char *s) { STACK S; makeNull(S); int j=0; while(s[j]!='\\0') { switch(s[j]) { case '(': push(S,'('); break; case ')': if(top(S) == '(') pop(S); else return FALSE; break; case '[': push(S,'['); break; case ']': if(top(S) == '[') pop(S); else return FALSE; break; case '{': push(S,'{'); break; case '}': if(top(S) == '{') pop(S); else return FALSE; break; } j++; } if(isEmpty(S)) return TRUE; else return FALSE;

}

void main() {/* STACK S; makeNull(S); int num = 1024; int n = 2; cout<<\转化前的十进制数为：\ cout<<\转化后的\进制数为：\ convert(num,S,n); print(S); */ char *s = \ char *p = \ if(check(s) == TRUE) cout<<\括号匹配！\ else cout<<\括号不匹配！\ if(check(p) == TRUE) cout<<\括号匹配！\ else cout<<\括号不匹配！\}

十二、设有一个带头结点的双向链表h，设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行交换。 要求：

1、定义带头结点的双向链表的型DLIST。 2、定义双向链表DLIST的基本操作。

3、定义函数int swap(elementtype x, DLIST &h)，查找第一个元素之为x的结点，如果在链表中存在元素值为x的结点，并其与其前驱结点进行交换，并返回1，否则返回0。 4、在主函数中测试所编写函数的正确性。

//带头结点的双向链表h，设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行交换。 #include using namespace std; typedef int Elementtype;

struct celltype{ Elementtype element;//数据域 celltype *previous,*next;//前驱和后驱 };