0.PTA得分截图

1.本周学习总结

1.1 线性表内容总结

1.1.1顺序表结构体

1.1.1.1定义

#define MaxSize 100
struct student
{
   int data[maxsize];
   int length;           //记录顺序表最后一个数据的位置
}

如上代码定义了一个最大数据存储量为101的顺序表结构体。

1.1.1.2顺序表插入

现在假设已有顺序表S，要将数据x插入至第p个位置
伪代码

if p大于length
   S->data[p-1]赋值为x
else p小于length
   for length to p
   数组后移一位
   S->data[p-1]赋值为x
  

代码

if(p>length)
{
   s->data[p]=x;
}
else
{
   for(i=length;i>=p;i--)
   {
      s->data[i]=s->data[i-1];
   }
   s->data[p-1]=x;
}

1.1.1.3顺序表数据删除

现在假设已有顺序表S，要将第p个位置的数据删除
伪代码

if p大于length
   删除位置无效，返回false
else p小于length
   for p-1 to length-1 
   数组前移一位

代码

if(p>length)
{
   return false；
}
else
{
   for(i=p-1;i<=length-1;i++)
   {
      s->data[i]=s->data[i+1];
   }
}

1.1.2链表结构体定义

实例：PTA线性表题目集7-1

1.1.2.1头插法

伪代码

建立新空列表，头指针为L
for i=1 to i<=n
{
  建立新节点Node
  Node->next指向L->next
  L->next指向Node
}

实例：PTA线性表题目集6-5头插法建链表

1.1.2.2尾插法

伪代码

建立新空链表，头指针为L
前驱指针为pre指向L
for i=1 to i<=n
{
  建立新节点Node
  Node->next指向pre->next
  pre->next指向Node
  pre指向下一个节点
}

实例：PTA线性表题目集6-6尾插法建链表

1.1.2.3链表插入

伪代码

通过前驱指针pre遍历链表找到插入点
新建节点Node
Node->next指向pre->next
pre->next指向Node
pre指向其下一个节点pre->next

实例：PTA线性表题目集6-10有序链表的插入和删除

1.1.2.4删除操作

伪代码

通过前驱指针pre遍历链表找到插入点
temp指向pre->next
pre->next指向pre->next->next，即更后一个节点
删除 temp

实例：PTA线性表题目集6-10有序链表的插入和删除

1.1.3有序表

1.1.3.1有序单链表数据插入和删除

同上！！！！同上！！！！

1.1.3.2有序表合并

假设现有两个数据递减的有序表L1和L2，将其有序合并且延用L1的头节点
法一：借助数组

• 新建数组A[]将L1和L2的所有数存入其中
• 运用冒泡排序法或者选择排序法将其处理为有序
• 将排序后的A[]的所有数据存进链表，并把L1作为节点
  图示：
  

法二：借助L3

• 新建链表L3
• 将L1和L2中节点数据逐个比较
• 较大的数赋值到新建节点Node插入L3
• 将L3替换为L1，即延用L1作为头节点
  图示
  

法三：直接法（推荐）

• L1作为主链被比较
• 若L2中节点数据找到L1中第一个比它小的数据便插在其前端

• L1若阅尽则L2未比较元素按顺序接到L1后面
  图示
  
  推荐原因：时间复杂度最小，为O(n)；不需要占用新的空间，空间复杂度最小，为O(1)

  1.1.4特殊链表

  1.1.4.1循环链表

  

  1.1.4.2双链表

  
  节点的插入

s->next=p->next;
p->next->prior=s;
s->prioe=p;
p->next=s;

节点的删除

temp=p->next;
p->next->next->prior=p;
p->next=p->next->next;
delete temp;

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

线性表即是一条在计算机中牢固的关系绳子。对于顺序表来说，上学期对数组的掌握够扎实便可轻松应付；而对于链表，操作难度更高，数据存储更灵活，抽象思维的要求需要更强，基本的链表插入，删除，排序的代码需要多加训练才能熟练编写，更值得一提的是，要学会画链表操作示意图来帮助我们寻找解决问题的方法

2.PTA实验作业（0-2分）

选3道PTA题目，不写伪代码，只贴代码截图，并记录代码提交碰到问题及解决方法。必须选择线性结构应用题目，不得选操作集类似题目，头插法、尾插法、链表逆转也不得选。（选，则为0分）选择难度越高题目得分越高。

2.1.题目1：有序链表合并

2.1.1代码截图

2.1.2PTA提交列表说明

Q1:
A1:
Q2:
A2:

2.2 题目2：

2.3 题目3

3.阅读代码（0--4分）

找2份优秀代码，理解代码功能，并讲出你所选代码优点及可以学习地方。主要找以下类型代码：
考研题种关于线性表内容。可以找参加过考研的学长学姐拿。尤其是想要考研同学，可以结合本章内容，用考研题训练学习。
ACM题解
leecode面试刷题网站,找线性表相关题目阅读分析。
leecode经典题目
注意：不能选教师布置在PTA的题目。完成内容如下。
3.1 题目及解题代码
可截图，或复制代码，需要用代码符号渲染。
3.1.1 该题的设计思路
链表题目，请用图形方式展示解决方法。同时分析该题的算法时间复杂度和空间复杂度。
3.1.2 该题的伪代码
文字+代码简要介绍本题思路
3.1.3 运行结果
网上题解给的答案不一定能跑，请把代码复制自己运行完成，并截图。
3.1.4分析该题目解题优势及难

数据结构——线性表

原文：https://www.cnblogs.com/243050cz/p/12444339.html