DS博客作业02--线性表

1.本周学习总结

1.1思维导图

1.2.谈谈你对线性表的认识及学习体会。

在线性表这一章里，学习了数组和链表，虽然在上学期里这两种已经学过了，感觉这次线性表的学习是对链表加深，有建链表的两种
方法，还有循环链表和双链表的建立，学习了这几种链表，在今后的使用链表中有了更多的选择，同时也提高了解部分题目的效率。
在顺序表这一方面，主要学习的是对顺序表的插入和删除操作，链表也同样是插入和删除，再加上扩展的一些操作。这两种线性表各有
其优缺点，在使用时还需要分情况考虑。

2.PTA实验作业

2.1.题目1：题目名称

链表L是一个有序的带头结点链表，实现有序链表插入删除操作

2.1.1设计思路（伪代码）

插入函数ListInsert(LinkList &L, ElemType e)
p1=L
p->data=e
while(p1!=NULL && p1->next != NULL)
       if(p1->next->data > p->data )    //因为链表有序，所以只要找到比插入数大的结点
           插入p结点在p1后
           return
       end if
       p1=p1->next
end while
p1->next=p;           //插入点位于链表尾

删除函数void ListDelete(LinkList &L, ElemType e)
p1=L
while(p1!=NULL && p1->next!=NULL)
        if (p1->next->data == e)             //找到结点data域值为e的结点
                删除p1->next结点
                return
        end if
        p1=p1->next
end while
输出“找不到”

设计思路：若插入点在链表中间则遍历链表插入结点，插入点在链表末尾则将指针移动至链表尾插入结点

2.1.2代码截图

2.1.3本题PTA提交列表说明。

Q1:在vs上面编译一直过不了，一直出现一些看不懂的错误
A1:去百度之后看有人的回答是说因为对某个元素没有进行初始化，看代码看了很久才发现，新建p结点，将e的值存入
p->data却没有将p->next设为NULL才出现这种错误。

2.2.题目2：题目名称

本题要求实现顺序表的操作集。

2.2.1设计思路（伪代码）

查找函数Find(List L, ElementType X)
      for i=0 to L->Last  then
           找到L->data[i]==X
            return i
      end for

插入函数Insert(List L, ElementType X, Position P)
if(P < 0 || P > L->Last+1)  return false    //P指向非法位置
if( L->Last == MaxSize-1)  return false    //顺序表满 
for i=L->Last  to P then
    依次将第P个元素往后移动一个单位
end for
L->data[P]=x
L->Last++

删除函数Delete(List L, Position P)
if (P < 0 || P > L->Last)  return false    //P指向非法位置
for i=P+1 to L->Last then
      依次将P+1至L->Last个元素像前移动一个单位
end for
L->Last--

设计思路：顺序表中的删除和插入都需要对插入删除位置之后的元素操作，插入元素则需将插入位置之后的所有元素向后移动
一个单位，腾出一个空位以便插入。删除元素则需将删除的位置之后的元素向前移动一个单位，将需要删除的位置用其他元素
覆盖掉。

2.2.2代码截图

2.2.3本题PTA提交列表说明

Q1:之前一直提交都是答案错误而且都是一分都没有的情况但是在vs上却可以运行
A1:在vs上可以运行，在PTA里却是一分都没有，之后一直以为是格式的问题，哪里多了或少了一个空格，查完之后
发现格式根本没错误，在看了同学的代码之后发现我的动态分配内存的格式跟他们的不一样，但是在vs上却可以正
常运行，格式改完在PTA上就没问题了

2.3.题目2：题目名称

已知一个带有表头节点的单链表，查找链表中倒数第m个位置上的节点。

2.3.1设计思路（伪代码）

while(p!=NULL)
{
        遍历链表，将链表长度存入变量count
}
index = count - m    //倒数第m个，正数则是第index个
while(L!=NULL)
{
        遍历链表，查找第index个节点，并返回第index节点的值
}

设计思路：题目是求出倒数第m个数，正数则是倒数第m个数链表的长度减去m，这样就可以从表头开始数。

2.3.2代码截图

2.3.3本题PTA提交列表说明

Q1:第一次提交部分正确
A1:第一次在编译器上只实现了题目中的例子，但在输入其他数值时还有些问题，后来把count和i的值重新进行计算
就行了
Q2:第二次提交部分正确
A2:第二次提交在正常情况下是没问题的，但是当index=count-m小于零时会出现错误，改进之后在计算index值的后
面添上了一个index小于零时就return -1

3、阅读代码

3.1 题目

删除链表的倒数第N个节点

3.2 解题思路

定义两个指针都先指向链表头结点，先将第一个指针移动至第n+1个结点，这样一来第一个指针跟第二个指针之间就
相差n个结点，然后同时将第一个和第二个指针往后移动，直到第一个指针到链表的末尾，这是第二个指针所指向的
位置正好就是倒数第n个结点的位置。