DS博客作业02--线性表

曾经终败给现在 2022-01-09 10:09 311阅读 0赞

# 1.思维导图及学习体会 ![1476101-20190309202403056-34355844.jpg][] #

## 1.1 思维导图 ##

![1476101-20190330201739203-130709244.png][]

## 1.2 学习体会 ##

> 线性表的学习是对于对上学期知识的更深入的学习，相较于数组是一种更高效的做法，在本章的学习中，刚开始没有完全理解知识点，总是照着课本写，但是做了两三题之后不看课本，发现并没有完全理解，又重新看了些视频、请教同学，把之前所学的知识理解；但是在完成PTA的过程中，发现还是出现一些类似忘记判断空指针、指针域未置空等问题，还需要更加细心，还要继续加油呀?

# 2.PTA实验作业 ![1476101-20190309202340995-2116737649.jpg][] #

## 2.1 顺序表操作集 ##

> 本题要求实现顺序表的操作集。  
> List MakeEmpty()：创建并返回一个空的线性表；  
> Position Find( List L, ElementType X )：返回线性表中X的位置。若找不到则返回ERROR；  
> bool Insert( List L, ElementType X, Position P )：将X插入在位置P并返回true。若空间已满，则打印“FULL”并返回false；如果参数P指向非法位置，则打印“ILLEGAL POSITION”并返回false；  
> bool Delete( List L, Position P )：将位置P的元素删除并返回true。若参数P指向非法位置，则打印“POSITION P EMPTY”（其中P是参数值）并返回false。

### 2.1.1 设计思路 ###

*  设计思路：在查找，插入和删除函数中，首先都要判断位置是否合法

List MakeEmpty() //创建并返回一个空的线性表
    {
        定义 L;
        动态申请内存;
        置空返回
    } 
    Position Find( List L, ElementType X ) //位置查找
    {
        定义 i;
        for i=0 to i<=L->Last 
            找到并直接返回位置
        end for
        返回 ERROR;
    }
    bool Insert( List L, ElementType X, Position P ) //插入
    {
        定义 i;
        if 表满
            输出 FULL;返回 false;
        end if
        if 位置非法
                输出 ILLEGAL POSITION ;返回 false;
            end if
        for i=L->Last+1 to i>P
            倒序后移
        end for
        L->Data[i]=X; //插入
        L->Last++;  
        返回 true;
    }
    bool Delete( List L, Position P ) //删除
    {
        定义 i;
        if 位置非法
            输出 POSITION P EMPTY ;返回 false;
        end if
        for i=P to i<L->Last
            把i+1个数前移
        end for
        L->Last--;
        返回 true;
    }

### 2.1.2 代码截图 ###

![1476101-20190331093931757-686985409.png][]  
![1476101-20190331094007534-54938190.png][]

### 2.1.3 PTA提交列表说明。 ###

![1476101-20190331101928714-460254334.png][]

*  1-2 刚开始没注意，忘记要用C的语法，就很开心的用C++语法，然后提交了两次，发现了这个问题
 *  3-5 修改成C的语法后，依旧答案错误，请教同学后发现，在创建线性表时，置空L->last=-1，而我是L->last=0，在插入时会少插入一个数

## 2.2 有序链表合并 ##

> 已知两个递增链表序列L1与L2，2个链表都是带头结点链表。设计函数实现L1，L2的合并，合并的链表仍然递增有序，头结点为L1的头结点。 合并后需要去除重复元素。  
> void MergeList(LinkList &L1,LinkList L2);  
> 输入格式: 输入分两行，先输入数据项个数，再输入数据项，数字用空格间隔。  
> 输出格式: 在一行中输出合并后新的递增链表，数字间用空格分开，结尾不能有多余空格。

### 2.2.1 设计思路 ###

*  定义头结点L，遍历L1、L2直到其中某一条结束，按照从小到大的顺序把结点插入L后面，然后把剩余部分插入L中。

定义链表结点 p,q,s,r,L;
        p指向L1的首个有效结点;
        q指向L2的首个有效结点;
        s=new LNode;
        s->next=NULL;
        L=s;
        while p&&q do//同时遍历两条链表，直至其中一条结束 
            if p结点值大于q结点值
                q结点插入L链表后面
                q向后挪
            else if p结点值小于q结点值
                p结点插入L链表后面
                p向后挪
            else
                p结点插入L链表后面
                p和q同时向后挪
            end if
        end while
        if 未到达L1链尾 
            L1剩余部分插入L中; end if
        if 未到达L2链尾 
            L2剩余部分插入L中; end if
        L1=L;

### 2.2.2 代码截图 ###

![1476101-20190406211219120-1266715939.png][]

### 2.2.3 PTA提交列表说明。 ###

![1476101-20190406213514621-569139699.png][]

*  1-2 刚开始是想要直接在L1上操作，后来出现错误之后，采用建一个新的链表的方法解决，然后请教同学后也完成了直接在L1上的做法
 *  3-4 提交后发现在重复数据的测试点过不去，在编译器上多试了几组数据发现处理时会有遗漏，后来进行了修改

## 2.3 顺序表删除重复元素 ##

> 设计一个算法，从顺序表中删除重复的元素，并使剩余元素间的相对次序保存不变。  
> 输入格式: 第一行输入顺序表长度。 第二行输入顺序表数据元素。中间空格隔开。  
> 输出格式：数据之间空格隔开，最后一项尾部不带空格。  
> void CreateSqList(List &L,int a\[\],int n); //创建顺序表  
> void DispSqList(List L);//输出顺序表  
> void DelSameNode(List &L) ;//删除顺序表重复元素

### 2.3.1 设计思路 ###

*  通过冒泡法将顺序表中数据进行排序，然后通过比较相邻数据，将重复的数据删除

其余两个函数与2.1的相同，就不再展示 
        定义 i,j,k=0,n,item;
        n=L->length;
        for i=0 to n
            for j=1 to n-i
                if L->data[j]<L->data[j-1]
                    交换L->data[j]与L->data[j-1]的值
                end if 
            end for
        end for
        j=1;
        for i=1 to i<L->length
            if i-1与i的数据不同 
                L->data[j++]=L->data[i];//重构顺序表
            k=j;
        end for  
        L->length=k;

### 2.3.2 代码截图 ###

![1476101-20190406220553703-1217364123.png][]

### 2.3.3 PTA提交列表说明。 ###

![1476101-20190406221003616-43654780.png][]

*  1 因为没有仔细阅读题目，多提交了一个销毁函数
 *  2-4 空表的测试点没过，因为刚开始将j赋值为重构后顺序表的长度，发现j初始化为1，这样长度至少为1，后来新定义k，当表不为空时，将j的值赋给k

# 3.阅读代码 ![1476101-20190309202327296-688305400.jpg][] #

## 3.1 题目 ##

## 3.2 解题思路 ##

## 3.3 代码截图 ##

## 3.4 学习体会 ##

转载于:https://www.cnblogs.com/qq1191834402/p/10627862.html

[1476101-20190309202403056-34355844.jpg]: /images/20220109/3a84340561e24fdca716aaccd478018d.png
[1476101-20190330201739203-130709244.png]: /images/20220109/ac24995b54b1462f899d51563389a12f.png
[1476101-20190309202340995-2116737649.jpg]: /images/20220109/8690e3a0688e4c6d94fbb181e0002222.png
[1476101-20190331093931757-686985409.png]: /images/20220109/60e1c0943fc14f4dbf7eb207e947b8b5.png
[1476101-20190331094007534-54938190.png]: /images/20220109/f07afcc1c7e6426e9f291016ed74c17c.png
[1476101-20190331101928714-460254334.png]: /images/20220109/c07b9114eb6149a6952364712aa9463c.png
[1476101-20190406211219120-1266715939.png]: /images/20220109/a7690c2f411e42f6842a8515a580bc4c.png
[1476101-20190406213514621-569139699.png]: /images/20220109/e76f1ebb71b54cc99749ac33833a4149.png
[1476101-20190406220553703-1217364123.png]: /images/20220109/9ff2692bab1a49c9ba51a33898d7eb47.png
[1476101-20190406221003616-43654780.png]: /images/20220109/e3c64234f3544d96b05ba5a5a7b6c695.png
[1476101-20190309202327296-688305400.jpg]: /images/20220109/d488bf3a782544839ed38de5a59387fe.png