【資料結構】課後作業——傳回字尾中的第一個元素

P38.22

有A、B兩個字元串，以連結清單形式存放。他們有相同的字尾，請給出字尾的第一個字母。

（1）算法的基本設計思想

分别周遊一遍連結清單并将其倒置為新的連結清單。則兩個新的連結清單的第一個不同的元素之前的元素就是所需的元素。

倒置采用的是頭插法來生成兩個新的連結清單。

（2）代碼如下

#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;
void printList(LinkList &L)
{
	printf("\n");
	LNode *s=L->next;
	while (s != NULL)
	{
		printf("%c", s->data);
		s = s->next;
	}
}
LinkList CreatListend(LinkList &L,LinkList &end)
{
	char x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s, *r = L;
	scanf("%c", &x);
	while (x != '@')
	{
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%c", &x);
	}
	end = r;
	r->next = NULL;
	return L;
}
void main()
{
	int count;
	LinkList L1, L2, L3;
	LinkList _L1, _L2;
	LinkList end1=NULL, end2=NULL,end3=NULL;
	CreatListend(L1,end1);
	CreatListend(L2,end2);
	CreatListend(L3,end3);
	end1->next = L3->next->next;
	end2->next = L3->next->next;
	printList(L1);
	printList(L2);
	_L1= (LinkList)malloc(sizeof(LNode));
	_L2= (LinkList)malloc(sizeof(LNode));
	_L1->next = NULL;
	_L2->next = NULL;
	LNode *s1,*s2;
	while (L1 != NULL)
	{
		s1 = (LNode*)malloc(sizeof(LNode));
		s1->data = L1->data;
		s1->next = _L1->next;
		_L1->next = s1;
		L1 = L1->next;
	}
	while (L2 != NULL)
	{
		s2 = (LNode*)malloc(sizeof(LNode));
		s2->data = L2->data;
		s2->next = _L2->next;
		_L2->next = s2;
		L2 = L2->next;
	}
	if (_L1->data != _L2->data)
		printf("無共同字尾");
	else
		while (_L1->next->data == _L2->next->data)
		{
			_L1 = _L1->next;
			_L2 = _L2->next;
		}
	printf("字尾起始字母為%c", _L1->data);
}
           

（3）複雜度

時間複雜度O(n)

空間複雜度O(n)

較好的算法

（1）算法的基本設計思想

曾經考慮過這樣一個算法，但是由于對指針指向不是很熟練而放棄。就是設定兩個指針，分别指向兩連結清單。向後移動，直到兩指針的位址相同時就是字尾的第一個字母。當然該算法需要知道兩個連結清單各自的長度，是以時間上也沒有好多少。

（2）代碼

#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;//LNode是結構變量，LinkList是結構指針
int countList(LinkList &L)
{
	int count = 0;
	LNode *s = L->next;
	while (s != NULL)
	{
		s = s->next;
		count++;
	}
	return count;
}
void printList(LinkList &L)
{
	printf("\n");
	LNode *s=L->next;
	while (s != NULL)
	{
		printf("%c", s->data);
		s = s->next;
	}
}
LinkList CreatListend(LinkList &L,LNode* &end)//傳回的尾指針的類型應該是結構指針LinkList，也可以是LNode*，不能是結構變量LNode。當然要改變它的值，那麼傳入的就得是位址了
{
	char x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s, *r = L;
	scanf("%c", &x);
	while (x != '\n')
	{
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%c", &x);
	}
	end = r;
	r->next = NULL;
	return L;
}
void main()
{
	int count;
	LinkList L1, L2, L3;
	LinkList end1=NULL, end2=NULL,end3=NULL;
	CreatListend(L1,end1);
	CreatListend(L2,end2);
	CreatListend(L3,end3);
	end1->next = L3->next;
	end2->next = L3->next;
	printList(L1);
	printList(L2);
	int count1 = countList(L1);
	int count2 = countList(L2);
	LNode *p, *q;
	for (p = L1; count1 > count2; count1--)
		p = p->next;
	for (q = L2; count1 < count2; count2--)
		q = q->next;
	while (p->next != NULL&&p->next != q->next)
	{
		p = p->next;
		q = q->next;
	}
	if (p->next == NULL)
		printf("無共同字尾");
	else
		printf("字尾起始字母為%c", p->next->data);
}
           

（3）複雜度

時間複雜度O(n)

空間複雜度O(n)

PS：

人家的算法肯定符合要求，人家傳回的是位址，我傳回的是值。而且當我的在字尾之前有一個字母是相同的時候，就出現了錯誤。總而言之還是我蠢。