データ構造学習ノート---リニアテーブル(チェーンに関する一般的なアルゴリズムと面接問題)

1.引用 
この文章は主にチェーンの計算方法と面接問題について説明します.
2. シングルチェーン表の逆順(率先して接合しない)

/*             */

#include "ds.h"
using namespace std;

typedef 	int		ElemType;

typedef struct LNode{
	ElemType 		data;
	struct LNode	*next;
}LNode, *LinkList;

void InitList(LinkList &L);
void TailCreList(LinkList &L, int n);
void ReverseList(LinkList &L);
void TraverseList(LinkList L);

void InitList(LinkList &L)
{
	L = NULL;
}

void TailCreList(LinkList &L, int n)
{
	LinkList 	p, tail, s;
	int 		i;
	
	if (0 > n)
		return;
	
	tail = L;
	
	printf("please input %d number:", n);
	
	for (i = 1; i <= n; i++)
	{
		s = (LinkList)malloc(sizeof(LNode));
		scanf("%d", &(s->data));
		if (1 == i)
		{
			s->next = tail;
			L = tail = s;
		}
		else
		{
			tail->next = s;
			tail = tail->next;
		}
	}
	tail->next = NULL;
}

void ReverseList(LinkList &L)
{
	LinkList 	pre_pre, pre, cur;
	
	//                 
	if (NULL == L || NULL == L->next)
		return;
	
	cur = L;
	pre = NULL;
	
	//           ，
	while (cur->next)
	{
		// pre_pre, pre, cur     
		pre_pre = pre;			
		pre = cur;
		cur = cur->next;
		
		//     
		pre->next = pre_pre;
	}
	
	//             
	cur->next = pre;	
	//            L	
	L = cur;				
}

void TraverseList(LinkList L)
{
	LinkList 	p = L;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("
");
}

int main()
{
	LinkList 	L;
	
	InitList(L);
	TailCreList(L, 5);
	TraverseList(L);
	
	ReverseList(L);
	TraverseList(L);
}

3. 一方向チェーンを入力して、このチェーンの最後からk番目のノードを出力します.

//         ，          k    。

#include "ds.h"
using namespace std;

typedef 	int		ElemType;

typedef struct LNode{
	ElemType 		data;
	struct LNode	*next;
}LNode, *LinkList;

void InitList(LinkList &L);
void TailCreList(LinkList &L, int n);
int OutputLast_K(LinkList L, int k);
void TraverseList(LinkList L);

void InitList(LinkList &L)
{
	L = NULL;
}

void TailCreList(LinkList &L, int n)
{
	LinkList 	p, tail, s;
	int 		i;
	
	if (0 > n)
		return;
	
	tail = L;
	
	printf("please input %d number:", n);
	
	for (i = 1; i <= n; i++)
	{
		s = (LinkList)malloc(sizeof(LNode));
		scanf("%d", &(s->data));
		if (1 == i)
		{
			s->next = tail;
			L = tail = s;
		}
		else
		{
			tail->next = s;
			tail = tail->next;
		}
	}
	tail->next = NULL;
}

/*
	     ：
	0 	->     
	-1 	->      k<1
	-2  ->       k
*/

int OutputLast_K(LinkList L, int k)
{
	LinkList 	p_k = L, p_add_k = L;
	int 		i = 0;
	
	//      k<1
	if (NULL == L || k < 1)
	{
		if (k < 1)
			printf("k < 1 
");
		return -1;
	}
	
	//  p_add_k      ，p_k    k    
	while (p_add_k)
	{
		if (i < k)
		{
			i++;
		}
		else
		{
			p_k = p_k->next;
		}
		p_add_k = p_add_k->next;
	}
	
	//         K
	if (i == k)
	{
		while (p_k)
		{
			printf("%d ", p_k->data);
			p_k = p_k->next;
		}
		printf("
");
	}
	//       K
	else
	{
		printf("List L less %d element.
", k);
		return -2;
	}
	
	return 0;
}

void TraverseList(LinkList L)
{
	LinkList 	p = L;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("
");
}

int main()
{
	LinkList 	L;
	
	InitList(L);
	TailCreList(L, 5);
	TraverseList(L);
	
	for (int i = 0; i < 8; i++ )
		OutputLast_K(L, i);
}