DS博客作业02--线性表

末蓝、 2021-12-23 12:59 324阅读 0赞

### 1.本周学习总结 ###

## 1.1思维导图 ##

![1474724-20190331112130127-155703212.png][]

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

线性表中的顺序表其实还挺好理解的，和数组的差距不大，链表就比较抽象了，本来插入感觉挺简单的，链表那么一弄，还得先断链，然后接上去要插的这种操作，不过这也有好处，只要对插入的位置进行操作就可以了，不像以前数组还得把后面的数组往后移。链表好用是好用，不过抽象的东西挺多的。链表的头插法和尾插法在很多题目中都用得到。有序表比较好处理。

# 2.PTA实验作业 #

## 2.1.题目1:顺序表删除重复元素 ##

本题要求：从顺序表中删除重复的元素，并使剩余元素间的相对次序保存不变。

### 2.1.1设计思路（伪代码） ###

定义k来判断data\[i\]之前有没有出现过这个数字，如果没出现过让L->data【j】记住L->data【i】，j++；然后最后把j+1赋给L的长度，只输出到j+1；后面的数据不输出。

###void CreateSqList(List &L,int a[],int n)
    定义链表L并动态申请内存。
    
    然后用for循环将a[i]的值赋给L->data[i]
    
    ###void DelSameNode(List &L)
    for循环遍历链表并且在for循环里面有
    
    while(k<=j&&L->data[k]!=L->data[i]) 　　//不断比较前面是否有与L->data[i]重复的元素 
    k++;　　　　　　k是用来判断是否出现重复数字
    if(k>j) L->data[++j]=L->data[i];　　　如果此时的data[i]不为重复数字，k将小于j
    
    最后将j+1赋给L的长度
    
    ###void DispSqList(List L)
    判断链表非空时输出链表，
    
    for(i=0;i<L->length;i++)
    
    当i没有读到链表尾端时输入数据和一个空格，读到尾端时不输出空格。
    
    如果链表为空，return。

## 2.1.2代码截图 ##

![1474724-20190331112155295-99522548.png][]

![1474724-20190331112208087-875617976.png][]

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

![1474724-20190331112229992-175335643.png][]

•Q1：一开始把全部代码都粘贴进去了，然后编译错误。

•A1：后面发现了，改了之后变成了部分正确。

•Q2：还是部分正确，发现空表时不正确。

•A2：添了判断条件if(L->length==0)　　return；的条件还是部分正确，输出部分和别的同学也一样，就是不对。

# 2.2.题目2: 两个有序序列的中位数 #

求出两个有序序列合并后的中位数

## 2.2.1设计思路（伪代码） ##

首先依次比较data1和data2数组各个数据的大小，谁小谁的下标＋1，然后运用flag变量来判断当n读到两链表长度的一半时这时第n个数是data1还是data2数组里的，然后输出L->data1\[i-1\]或L->data2\[j-1\]。

###void CreateList(SqList &L,int n)
    给链L申请动态空间
    
    两个for循环输入两个有序表的数据
    
    ###int seek(SqList &L,int n) 　　　　//寻找中位数 
        定义i，j来比较两有序表中的数，定义k代表读到第k数了。
    
       定义中间变量flag=0，flag作为中间变量判断中位数是data1中的数还是data2中的数
    
    while（k！=n）　　　　　     当读到第n+1个数时跳出循环
    　 {
            if(L->data1[i]<L->data2[j])　　       如果data1[i]大于data2[j] 
     　        flag控制为0，下标　i＋1
    　  else 　
           {
             data1[i]小于data2[j]的情况和等于的情况，等于的话不管谁排在前面都可以，所以不分类讨论
             flag控制为1；　　下标j+1
            }
        }
    
        if判断 （如果flag=0），
                则第n个数是data1的数据，
        否则为data2的数据
        
    return  返回L->data1[i-1]或L->data2[j-1]　　因为读到了第n+1个数，比如说n=5,这时读到了data1[5]是第六个数，所以应该为i-1
    
    ###void DestroyList(SqList &L)
     delete L；　　　　销毁表

## 2.2.2代码截图 ##

![1474724-20190331112245330-167384872.png][]  
![1474724-20190331112257737-207287138.png][]

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

![1474724-20190331112334713-752849482.png][]

•Q1： 一开始用直接返回的是data1\[i\]和data2\[j\]没考虑到已经读到了第n+1个数

•A1： 后面通过调试发现每次输出的都是后一个数，然后就想到用i-1和j-1；

•Q2： 一开始只对了一个测试点，有什么最小N啊奇数序列什么的没过。

•A2： 后面看了代码之后想到因为我的k是从0开始的，如果递增到n的话就是n+1个数了

# 2.3.题目3： jmu-ds-单链表逆置 #

将一个链表的表头置为表尾，表尾置为表头，即倒过来输出链表

## 2.3.1设计思路（伪代码） ##

运用头插法从第二个开始将链表逆置，插入表头，重复插入。直到表头置为表尾。

首先定义结构体指针p，temp。
    然后将p指向表头 p=L->next。
    将p置为空            p=L->next。
    当p非空时          while(p非空）
    临时变量temp储存p，
    将p后移的同时将temp接到表头，
    L->next=temp。
    链表逆置完成。

## 2.3.2代码截图 ##

![1474724-20190331140517163-358668155.png][]

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

![1474724-20190331140645606-1331324639.png][]

•Q1 : 后面好像有忘了L->next=temp这步的操作了，就还是带着以前的思维写作业。  
•A1 : 还是多亏了老师的代码。  
•Q2 ：一开始不太懂temp应该怎么做才能实现链表逆置，不太懂尾插法的使用  
•A2 ： 后面钻研了书上的代码和我拍的老师上课的代码做出来了

# 3、阅读代码 #

## 3.1 题目：已知在一维数组A\[m+n\]中依次存放着两个线性表(a1,a2,a3,…am)和(b1,b2,b3,…,bn)。试编写一个函数，将数组中两个顺序表的位置互换，即将(b1,b2,b3,…,bn)放在(a1,a2,a3,…,am)的前面。 ##

## 3.2 解题思路：首先将第一个与最后一个元素交换，得到bn,bn-1.....b1,am,am-1......a1,然后再对两个线性表分别逆置得到需要的顺序。 ##

## 3.3 代码截图![1474724-20190401170905306-1071109590.png][] ##

## 3.4 学习体会：这份代码没有在一个函数里重复交换，而是灵活的运用函数调用，在 Exchange函数里面反复调用Reverse函数来实现三次逆置的操作。换我是不会想到去这么做，可能就是傻傻的直接在一个函数里面重复逆置。 ##

转载于:https://www.cnblogs.com/yvvq/p/10630602.html

[1474724-20190331112130127-155703212.png]: /images/20211223/deb8ae18320e44f2bcf934eedae1d0de.png
[1474724-20190331112155295-99522548.png]: /images/20211223/85ddb46fbc174961aa58038b3e699588.png
[1474724-20190331112208087-875617976.png]: /images/20211223/622ee330be5f4c3ca3bfda4fe1bbd873.png
[1474724-20190331112229992-175335643.png]: /images/20211223/0b0afdb030c34e90b5a4cfbb66cc8612.png
[1474724-20190331112245330-167384872.png]: /images/20211223/1aa1b19f61a34bdcb59e4d90cecc9655.png
[1474724-20190331112257737-207287138.png]: /images/20211223/36284c1d82f24627b21896b9eab80a19.png
[1474724-20190331112334713-752849482.png]: /images/20211223/58fdfda3aa464b3391d95b0231bb6675.png
[1474724-20190331140517163-358668155.png]: /images/20211223/f39ea0ff9ee84fd889942b44d1150a11.png
[1474724-20190331140645606-1331324639.png]: /images/20211223/dad7be7e8e3843689ba9efabcd631e1c.png
[1474724-20190401170905306-1071109590.png]: /images/20211223/e48e53a452c14b63b88196b36d5c531d.png