针对数据结构02线性表在头歌平台练习过程中的完成代码，关卡数目较多，每题思路单独在每一关中解释。如有其他需求请留言。

第一关

        可以把问题转换为：遍历B中的元素，如果该元素不在A中，则把该元素插入到A中。 由于集合中的元素没有先后顺序，因此，插入位置可以自由选择。对于顺序表而言，在表尾位置插入不需要移动元素，是最高效的。

int ListLength(SqList L) //返回L的长度
{
	//代码开始
    return L.length;
    //代码结束
}

void GetElem(SqList L, int i, int &e) //用e返回L中第i个元素(1<=i<=L.length)的值 
{
	//代码开始
    e = L.elem[i - 1];
    //代码结束
}

bool LocateElem(SqList L, int e) //判断L中有没有值为e元素,如果有,返回true,否则,返回false 
{
	//代码开始
    for(int i = 0;i <L.length; i++)
    {
        if(L.elem[i] == e)    return 1;
    }
    return 0;
    //代码结束
}

void ListInsert(SqList &L,int e) //在L的最后插入值为e的元素 
{
	//代码开始
    L.elem[L.length++] = e;
    //代码结束
}

第二关

        求解集合A和B的并集，可以把问题转换为：遍历B中的元素，如果该元素不在A中，则把该元素插入到A中。 由于集合中的元素没有先后顺序，因此，插入位置可以自由选择。对于单链表而言，在表头位置插入新结点，时间复杂度为O(1)，是最高效的。

bool LocateElem(LinkList L, int e) //判断L中有没有值为e元素,如果有,返回true,否则,返回false 
{
	//代码开始
    LinkList q = L->next;
    while(q != NULL)
    {
        if(q->data == e)    return 1;
        q = q->next;
    }
    return 0;
    //代码结束
}

void ListInsert(LinkList &L, int e) //在L的开头插入值为e的元素 
{
	//代码开始
    LinkList q = new LNode;
    q -> data = e;
    q -> next = L -> next;
    L -> next = q;
    //代码结束
}

第三关

        一元多项式可以抽象成一个线性表，线性表中的数据元素包含两个数据项，分别表示多项式每项的系数和指数。一元多项式的相加运算就可以抽象成将两个线性表A，B中指数相同的数据元素进行相加的问题。

        此处数据范围较小，直接判断A中的每一项在B中是否存在，存在加到A的指数相同的项，在B中将该节点删除，若相加为0则同样在A中将该节点删除，最后将B中剩余的项按大小插入到A中。

void AddPolyn(Polynomial &Pa, Polynomial &Pb) 
{
	//代码开始
	Polynomial a = Pa;
    while(a -> next != NULL)
    {
        Polynomial b = Pb;
        while(b ->next != NULL)
        {
            if(b -> next -> expn == a -> next -> expn)
            {
                a -> next -> coef += b -> next -> coef;
                b -> next = b -> next -> next;
            }
            else
            {
                b = b -> next;
            }
        }
        if(a -> next -> coef == 0)
        {
            a -> next = a -> next -> next;
        }
        else
        {
            a = a -> next;
        }
    }
    Polynomial b = Pb -> next;
    while(b != NULL)
    {
        Polynomial a = Pa;
        while(a -> next != NULL)
        {
            if(b -> expn < a -> next -> expn)
            {
                Polynomial s = (Polynomial)malloc(sizeof(PNode));
                s = b;
                s ->next = a->next;
                a->next = s;
                break;
            }
            a = a -> next;
        }
        b = b -> next;
    }
	//代码结束 
	
} //AddPolyn

第四关

        如果不考虑遍历的次数，可以先遍历一次单链表求出其长度n，再遍历一次单链表求出第n-k+1个结点，该结点就是倒数第k个结点。但是，本关任务要求通过一次遍历就找出倒数第k个位置上的结点。

        对于该题采用双指针的办法，先构造出大小为k的窗口，然后快慢指针一起移动，当快指针移动到尾节点时候，慢指针恰好移动到倒数第k位

int Search_K(LinkList L,int k)
{

	if(k<=0 || L==NULL)
		return 0;//查找失败返回0 
	//代码开始
    LinkList a = L->next;
    LinkList b = L->next;
    int cnt = 0;
    while(cnt < k)
    {
        b = b->next;
        cnt++;
    }
    while(b != NULL)
    {
        a = a->next;
        b = b->next;
    }
    cout << a -> data;
    return 1;
    //代码结束
}

第五关

        对顺序表的基本操作，不在解释，有什么疑问可留言。

#include <iostream>
#include <string>
#include <string.h>
using namespace std;

//定义结构体最大存书数量
#define MAXSIZE 1000

//定义图书类型
typedef struct BOOK
{
	//代码开始
    string id;
    string name;
    int price;
    //代码结束 
}Book;

//定义图书顺序表类型
typedef struct
{
	//代码开始
    Book data[MAXSIZE];
	int m;
	//代码结束
}BookList;

//初始化
void InitBookList(BookList &L) //构造一个空的顺序表L 
{
	//代码开始
    L.m = 0;
    return ;
	//代码结束
}

//增加一条图书记录
bool ListInput(BookList &L,string ISBN,string BookName,int Price) //数据输入
{
	
	//代码开始
	L.data[L.m].id = ISBN;
    L.data[L.m].name = BookName;
    L.data[L.m++].price = Price;
    return true;
    //代码结束
}


//删除第i条图书记录
bool ListDelete(BookList &L,int i) 
{
	//代码开始
	if(i < 1 || i > L.m)    return false;
    for(int j = i - 1; j < L.m ; j++)
    {
        L.data[j] = L.data[j + 1];
    }
    L.m--;
    //代码结束
}

//修改第i条图书记录并输出该条记录
bool ListUpdate(BookList &L,int i,string ISBN,string BookName,int Price) 
{
	//代码开始
	if(i < 1 || i > L.m)    return false;
    L.data[i - 1].id = ISBN;
    L.data[i - 1].name = BookName;
    L.data[i - 1].price = Price;
    return true;
    //代码结束
}

//查询特定图书名的图书记录并输出该条记录
bool ListSearch(BookList L,string BookName) 
{
	//代码开始
	for(int i = 0; i < L.m ;i++)
    {
        if(L.data[i].name == BookName)
        {
            cout << L.data[i].id << ' ' << L.data[i].name << ' ' << L.data[i].price << endl;
        }
    }
    return true;
    //代码结束
}

//查询当前图书列表的数量
int ListLength(BookList L) 
{
	//代码开始
	return L.m;
    //代码结束
}

//输出当前图书表记录
void ListOutput(BookList L)
{
	//代码开始
	for(int i = 0; i < L.m ; i++ )
    {
        cout << L.data[i].id << ' ' << L.data[i].name << ' ' << L.data[i].price << endl;
    }
    //代码结束
}


//主函数,实现对图书表的增删查改
int main() {

	string ISBN;
	string BookName;
	int Price; 
	//声明并初始化
	BookList LA;
	InitBookList(LA);

	//增加图书信息
    while(1)
	{
		
		cin>>ISBN>>BookName>>Price;
		if(ISBN=="-1"&&BookName=="-1"&&Price==-1)
		{
			break;
		}
		else
		{
			ListInput(LA,ISBN,BookName,Price);
		}
	}
	//输出当前图书列表
	cout<<"当前图书列表"<<endl;
	ListOutput(LA);
	cout<<endl;

	//修改第3条图书信息
	cout<<"修改第3条记录"<<endl;
	ListUpdate(LA,3,"ISBN","BookName",100);
	//输出当前图书列表
	ListOutput(LA);
	cout<<endl;

	//删除第3条图书信息
	cout<<"删除第3条记录"<<endl;
	ListDelete(LA,3);
	//输出当前图书列表
	ListOutput(LA);
	cout<<endl;

	//查询图书列表总数
	cout<<"当前共有记录:"<<ListLength(LA)<<endl;
	//查询特定图书名的图书记录并输出该条记录
	cout<<"查询输出图书名是《DataStructure》的记录:"<<endl;
	ListSearch(LA,"DataStructure"); 

	return 0;
}