数据结构实验5 串运算的实现

/************************************************************************************* ****题目3： ** ****若S和T是用结点大小为1的单链表存储的两个串，设计算法将S中首次与T匹配的子串逆置。 ** *************************************************************************************/ #include "iostream" using namespace std; typedef char datatype; typedef struct node { datatype data; struct node *next; }linkstring; linkstring *creat_linkstring(void) { datatype ch; linkstring *head,*rear,*s; head = NULL; rear = head; while ((ch=getchar())!='\n') { s = new linkstring; s->data = ch; if (head == NULL) head = s; else rear->next = s; rear = s; } if (rear != NULL) rear->next = NULL; return head; } linkstring * turn(linkstring *head,linkstring *rear) { linkstring *p,*q,*r; p = head; q = head->next; if (q == rear) return head; r = q->next; if (r == rear) { q->next = p; p->next = rear; return q; } while (r != rear) { q->next = p; p = q; q = r; r = r->next; } q->next = p; head->next = rear; return q; } linkstring * operate(linkstring *S,linkstring *T) { int flag = 0; linkstring *p,*q,*head,*rear,*temp; p = S; q = T; while (1) { if (p && p->next != NULL && flag == 0) temp = p->next; if (p && q && p->data == q->data) { if (flag == 0) { head = p; flag = 1; } p = p->next; q = q->next; continue; } if (!q) { rear = p; //逆置 temp = turn(head,rear); p = S; if (S == head) return temp; while (p->next != head) p = p->next; p->next = temp; return S; //找到了！ } else if (!p) { cout<<"string S doesnot have string T!"<<endl; return NULL; } else { flag = 0; q = T; p = temp; } if (!p->next) { cout<<"string S doesnot have string T!"<<endl; return NULL; } } } void print_string (linkstring *s) { linkstring *p; p = s; if (s == NULL) cout<<"string is empty!"<<endl; while (p) { cout<<p->data<<"\t"; p = p->next; } cout<<endl; } void main(void) { linkstring *head1,*head2; head1 = creat_linkstring(); head2 = creat_linkstring(); head1 = operate(head1,head2); print_string(head1); }