笔记数据结构 and 刷题之链表

2024-03-25

64

作者编辑

数据结构
malloc的使用
```c
void* malloc(size_t size);
```
这样子进行分配的
```c
int *array = (int*)malloc(10 * sizeof(int));
```
检查分配成功:
malloc 在成功时返回指向分配的内存块的指针，在失败时返回 NULL。因此，你应该检查 malloc 的返回值，以确保内存分配成功：
```c

if (array == NULL) {
    // 处理内存分配失败的情况
}
```
释放内存:
当你不再需要分配的内存时，应该使用 free 函数来释放它：
```c

free(array);
array = NULL; // 好的实践是将指针设置为 NULL，避免悬挂指针
```
注意事项:
####   new

例题
习题2.5 两个有序链表序列的合并
分数 15
作者 DS课程组
单位 浙江大学
本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义：
```cpp
List Merge( List L1, List L2 );
其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */
```
L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。

裁判测试程序样例：
```cpp
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */

List Merge( List L1, List L2 );

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */
```
输入样例：
3
1 3 5
5
2 4 6 8 10
输出样例：
1 2 3 4 5 6 8 10 
NULL
NULL
代码长度限制
16 KB
时间限制
400 ms
内存限制
回答 ：

```cpp
List Merge( List L1, List L2 ){
  
    List L3   =(List) malloc(sizeof(struct Node));
    L3->Next = NULL;
    List p1  = L1;
    List p2 =L2;
    List p3=L3;
    while(p1->Next != NULL && p2->Next != NULL){
        if(p1->Next->Data < p2->Next->Data){
           
            List cur = L1->Next;
            
           L1->Next = L1->Next->Next;
             
           cur->Next = p3->Next;
           p3->Next = cur;
           p3 = p3->Next;
        // 这里的问题还是在有头结点的情况下 L1L2，
            // 你还设置一个P1P2 的情况下这是不合适的这里P1P2使用P1->NEXT=p1->NEXT->NEXT 会让局面非常乱
            
        }
        else {
               
            List cur = L2->Next;
            
           L2->Next = L2->Next->Next;
             
           cur->Next = p3->Next;
           p3->Next = cur;
           p3 = p3->Next;
        }

}
    if(L1->Next!=NULL)
    {
       p3->Next=L1->Next;
        L1 ->Next=NULL;
    }
      if(L2->Next!=NULL)
    {
       p3->Next=L2->Next;
                 L2->Next=NULL;
    }
    
    return L3;

}
```
自己写的md就是舒服~~~~

------------

[========]

### 习题3.3 线性表元素的区间删除
分数 20
作者 DS课程组
单位 浙江大学
给定一个顺序存储的线性表，请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储，并且相对位置不能改变。

函数接口定义：
List Delete( List L, ElementType minD, ElementType maxD );
其中List结构定义如下：
```
typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素在数组中的位置 */
};
```
L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较；minD和maxD分别为待删除元素的值域的下、上界。函数Delete应将Data[]中所有值大于minD而且小于maxD的元素删除，同时保证表中剩余元素保持顺序存储，并且相对位置不变，最后返回删除后的表。

裁判测试程序样例：
```
#include <stdio.h>

#define MAXSIZE 20
typedef int ElementType;

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

List ReadInput(); /* 裁判实现，细节不表。元素从下标0开始存储 */
void PrintList( List L ); /* 裁判实现，细节不表 */
List Delete( List L, ElementType minD, ElementType maxD );

int main()
{
    List L;
    ElementType minD, maxD;
    int i;

L = ReadInput();
    scanf("%d %d", &minD, &maxD);
    L = Delete( L, minD, maxD );
    PrintList( L );

return 0;
}
```
/* 你的代码将被嵌在这里 */
输入样例：
10
4 -8 2 12 1 5 9 3 3 10
0 4
输出样例：
4 -8 12 5 9 10 
我的答案
为什么报错
```
List Delete( List L, ElementType minD, ElementType maxD ){
    // printf("%d",L->Last);
    for(int i=0;i<=L->Last;i++){
      ElementType curdata=  (L->Data )[i];
        if((curdata>minD)&&(curdata<maxD)){
             for(int j= i;j<L->Last;j++){
                (L->Data )[j] = (L->Data )[j+1];
             }
            L->Last=  L->Last -1;
			i--; //这个真的很重要啊啊 啊啊啊~~~~
        }
    }
    return L; 
}
```
gpt 回复
```c
for(int j = i; j < L->Last; j++) {
    (L->Data)[j] = (L->Data)[j+1];
}
```
这段代码将当前位置后面的所有元素向前移动一位，但在你删除元素后，如果当前位置的元素符合条件被删除了，那么该位置后面的元素会向前移动一位，但你的循环变量i已经自增了，导致下一轮循环会跳过一个位置，这样就会出现漏删的情况。

C/C++

考研

博客信息

作者 eeettt123

发布日期 2024-03-25

其他信息 : 其他三字母的人名首字母都是其他同学发布的哦

笔记 数据结构 and 刷题 之链表

笔记数据结构 and 刷题之链表