数据结构复习笔记（数据类型及单链表实现）

第一章（算法复杂性以及数据类型）：

一、使用自定义数据类型一般需要初始化函数。Init(Item a,Item b){}

第二章（线性表）

一、用数组实现表：应该将表定义为一个自定义的数据类型，其中含有数据成员n和maxsize和元素数组table，用n记录表长，表为空时n=0，maxsize表示表的最大长度，table是表示存储元素数组。

typedef struct alist *List;
typedef struct alist
{
    int n;int maxsize;
    int *table;        //或者是其他数据类型
}

用数组实现表代码：
#include<cstdio>
#include<cstdlib>
#include<malloc.h>
typedef struct alist *List;
typedef struct alist
{
	int n;
	int maxsize;
	int *table;
}Alist;
List ListInit(int size, List L)
{
	//	List L=(Alist*)malloc(sizeof(aList));
	L->table = (int*)malloc(size * sizeof(int));        //开辟一个size大小的动态数组； 
	L->maxsize = size;
	L->n = 0;
	return L;
}
int ListEmpty(List L)
{
	return L->n == 0;        //如果表为空，则返回真值为1，否则返回0； 
}
int ListLenth(List L)
{
	return L->n;
}
int ListLocate(int x, List L)
{
	int i;
	for (i = 0; i<L->n; i++)
		if (L->table[i] == x)return i + 1;        //如果表中有元素 ，则返回它是表中的第几个元素（从1开始），否则的话返回0 ； 
	return 0;
}
int ListVal(int k, List L)
{
	return L->table[k - 1];        //由于是从1开始算第几个，所以返回k-1位置的元素值； 
}
void ListInsert(int k, int x, List L)
{
	int i;
	for (i = L->n - 1; i >= k; i--)
	{
		L->table[i + 1] = L->table[i];
	}
	L->table[k] = x;
	L->n++;
}
int ListDelete(int k, List L)
{
	int i; int x;
	x = L->table[k - 1];
	for (i = k; i<L->n; i++)
		L->table[i - 1] = L->table[i];
	L->n--;
	return x;
}

int main()
{
	int i, j, n;
	scanf_s("%d", &n);
	Alist *L = new alist;
	ListInit(n, L);
	L->table[0] = 1; L->table[1] = 2; L->n = 2;
	ListInsert(1, 0, L);
	for (i = 0; i<L->n; i++)
		printf("%d
", L->table[i]);
	return 0;
}

用链表实现的代码：

#include<cstdio>
#include<cstdlib>
#include<malloc.h>
typedef struct node *link;
typedef struct node
{
	int element;
	link next;
}Node;

typedef struct alist *List;
typedef struct alist
{
	link first;
}Alist;
List ListInit(List L)
{
	L->first = 0;
	return L;
}
int ListEmpty(List L)
{
	return L->first == 0;
}
int ListLenth(List L)
{
	int len = 0;
	link p;
	p = L->first;
	while (p)
	{
		len++; p = p->next;
	}
	return len;
}
int ListVal(int k, List L)
{
	int i; link p;
	p = L->first; i = 1;
	while (i<k&&p)
	{
		p = p->next; i++;
	}
	return p->element;
}
int ListLocate(int x, List L)
{
	int i = 1; link p;
	p = L->first;
	while (p&&p->element != x)
	{
		p = p->next; i++;
	}
	return p ? i : 0;
}
void ListInsert(int k, int x, List L)
{
	link p, y;
	int i;
	p = L->first;
	for (i = 1; i<k&&p; i++)p = p->next;        //寻找插入位置 
	y = new Node;
	y->element = x;
	if (k)
	{
		y->next = p->next; p->next = y;
	}
	else
	{
		y->next = L->first; L->first = y;
	}
}
int ListDelete(int k, List L)
{
	link p, q;
	int x, i;
	p = L->first;
	if (k == 1)
	{
		L->first = p->next;         //删除表首元素 
	}
	else
	{
		q = L->first;
		for (i = 1; i<k - 1 && q; i++)q = q->next;        //寻找第k-1个元素所在啊的节点q； 
		p = q->next;                             //第k个元素所在的节点p；
		q->next = p->next;
	}
	x = p->element;
	free(p);	//保存第k个元素的值并释放节点p，这里不确定能不能用free（）； 
	return x;
}
void PrintList(List L)
{
	link p;
	for (p = L->first; p; p = p->next)printf("%d
", p->element);
}
int main()
{
	int i, j, n;
	List L = new Alist;
	ListInit(L);
	link p = new Node;
	p->next = 0;
	scanf_s("%d", &n);
	for (i = 1; i <= n; i++)
	{
		if (L->first==NULL)
		{
			scanf_s("%d", &p->element);
			L->first = p;
		}
		else
		{
			link tmp = new Node;
			scanf_s("%d", &tmp->element);
			tmp->next = p->next;
			p->next = tmp;
			p = p->next;
		}
	}
	ListInsert(2, 0, L);                //在第2个位置后面插入
	ListInsert(2, 10, L);              //在第2个位置后面插入
	PrintList(L);
	return 0;
}

第一次作业：

1、（寻找两个数组分别取一个数之和是否等于k）解题思路：对两个数组同步的从头到尾遍历一遍，比较他们与k的大小关系对两个只想数组的标识左移右移；

2、（求数列删除一个元素之后的最大gcd值）解题思路：通过同两个数组分别存储数列的前缀gcd和后缀gcd（当然在求前缀后缀gcd过程需要用动态规划优化求解存储），然后对于所要删除的元素进行遍历，该数的前缀gcd和后缀gcd求一次gcd得到删除该数的gcd，循环找到max_gcd；

第二次作业：

1、（抽奖报数每次超过人数一半的报数者出队，剩一人）解题思路：这是一个寻找规律的题目，首先写出前几次的运作过程，就可以发现每次出队者的规律，然后最后剩下一个人，用纸直接写下前几次的过程找出解法；

2、（每前n个人一次抽奖，先进行m次翻转操作，报数为x的中奖）解题思路：同样这题也需要找规律的思想，写出前几步的过程，很容易可以发现所有的翻转过程都只是影响两个相互对称的数的前后位置，通过对所有数的前后位置关系统计可知道结果；错误收获：有一个容易忽视的是每n个人一次抽奖，但是x有可能比n大，所以在x>n时需要对其求余考虑；另外出现RE错误代表运行时出现错误，一般是出现数组开的不够大，这题题面看错，数组开小了出现两个RE；