数据结构与算法整理复习（一）：数据结构概念与线性表

🕗 发布于 2025-01-22 01:50 数据结构

第一章：绪论

1.1 数据结构的基本概念

1.2 算法与算法评价

第一章：绪论

1.1 数据结构的基本概念

可以用“抽象数据类型（ADT）”定义一个完整的数据结构

抽象数据类型（ADT）为一个数学模型以及其定义在数学模型上的一组操作。包含（数据对象、数据关系、以及其基本操作集），故为一个完整的数据结构。

数据的逻辑结构独立于存储结构，但数据的存储结构不能独立于其逻辑结构

1.2 算法与算法评价

好算法应该达到的目标：正确性、可读性、健壮性、高效率与低存储要求。

空间复杂度O(1)：辅助空间的大小与问题规模n无关

时间复杂度O(n^2)：执行时间与n^2成正比。

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        printf("111");
    }
}

上诉代码是时间复杂度为O(nm)。

#include <stdio.h>
 
// 递推方式求解斐波那契数列
long long fibonacci_iterative(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
 
    long long a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

// 递归方式求解斐波那契数列
long long fibonacci_recursive(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}
 
 
int main() {
    int n;
    printf("请输入一个非负整数: ");
    scanf("%d", &n);
    printf("斐波那契数列第%d项是: %lld\n", n, fibonacci_iterative(n));
    printf("斐波那契数列第%d项是: %lld\n", n, fibonacci_recursive(n));
    return 0;
}

第二章：线性表

2.1 线性表的定义和基本操作

每一个元素有且只有一个前驱和后继。

线性表的特性：

表中元素个数有限
元素具有逻辑上的顺序性，有先后顺序
表中元素都是你数据元素，每个数据元素可以包含多个数据项
表中元素的数据类型都相同（每个元素占相同大小的空间）
元素具有抽象性

InitList(List &L)//初始化表
Length(List L)//求表长
LocateElem(List L,ElemType e)//按值查找，返回位序
GetElem(List L,int i)//按位查找
ListInsert(List &L,int i, ElemType e)//插入操作，在表L的第i位序插入元素e
ListDelete(List &L,int i,ElemType &e)//删除第i位序的元素，并用e返回删除元素
PrintList(List L)//输出操作
Empty(List L)//判空操作
DestroyList(List &L)//销毁线性表

2.2 线性表的顺序表示（顺序表）

逻辑顺序与其物理顺序相同

顺序表的任意一个数据元素都可以随机存取。

顺序存储结构是一种随机存取的存储结构。

优点：

支持随机访问O(1)
存储密度高

缺点：

元素的插入（平均需要n/2次操作）和删除（平均需要(n-1)/2次操作）需要移动大量元素
分配需要一段连续的存储空间，灵活性较差

静态分配顺序表代码如下：

#define MAX_SIZE 100

//静态顺序表定义
typedef struct{
    int data[MAX_SIZE];
    int length;
}SqList;

//线性表初始化
InitList(SqList &L){
    for(int i=0;i<L.length;i++){
        L.data[i]=0;
    }
    L.length = 0;
}

//插入操作
bool ListInsert(SqList &L, int i, int e){
    if(i<1||i>L.length+1) return false;
    if(L.length >= MAX_SIZE) return flase
    for(int j = L.length;j>=i;j--){
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;
    L.length++;
    return true;
}
//静态线性表删除操作
bool ListDelete(SqList &L, int i,int &e){
    if(i<1||i>L.length) return false;
    if(L.length<=0) return false;
    e = L.data[i-1]
    for(int j=i;j<L.length;j++){
        L.data[j-1]=L.data[j];
    }
    L.length--;
    return true;
}
//按值查找
int LocateElem(SqList L, int e){
    for(int i=0;i<L.length;i++){
        if(L.data[i]==e){
            return i+1;//返回位序
        }
    }
    return -1;//查找失败
}

动态分配顺序表代码如下：

//动态顺序表定义
typedef struct{
    int *data;
    int length;
    int max_size;
}SqList;

//线性表初始化
InitList(SqList &L){
    L.data = (int *)malloc(sizeof(int)*INIT_SIZE)
    L.length = 0;
    L.max_size = INIT_SIZE;
}
//线性表插入
bool ListInsert(SqList &L,int i, int e){
    if(i<1||i>L.length+1) return false;
    if(L.length>=L.max_size) return false;
    for(int j=L.length;j>=i;j--){
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;
    L.length++;
    return true;
}
//动态线性表删除操作
bool ListDelete(SqList &L, int i,int &e){
    if(i<1||i>L.length) return false;
    if(L.length<=0) return false;
    e = L.data[i-1]
    for(int j=i;j<L.length;j++){
        L.data[j-1]=L.data[j];
    }
    L.length--;
    return true;
}
//按值查找
int LocateElem(SqList L, int e){
    for(int i=0;i<L.length;i++){
        if(L.data[i]==e){
            return i+1;//返回位序
        }
    }
    return -1;//查找失败
}

应用题

1. 原地逆置顺序表

void function(SqList &L){
    int temp;
    for(int i=0;i<L.length/2;i++){
        temp = L.data[i];
        L.data[i] = L.data[L.length-1-i];
        L.data[L.length-1-i] = L.data[i];
    }
}

2.删除所有值为e的元素，要求时间复杂度为O(n)，空间复杂度为O(1)

void function(SqList &L, int e){
    int pos = 0;
    for(int i=0;i<L.length;i++){
        if(L.data[i] != e){
            L.data[pos] = e;
            pos++;
        }
    }
    L.length = pos;
}

3. 有序顺序表中删除所有值重复的元素

bool function(SqList &L){
    if(L.length < 1) return false;
    int i=0;
    int j=1;
    for(j;j<L.length;j++){
        if(L.data[j]==L.data[i]) continue;
        i++;
        L.data[i] = L.data[j];
    }
    L.length = i+1;
    return true;
}

4. merge两个有序顺序表，并返回新的表

SqList mergeList(SqList L1, SqList L2, SqList &result){
    if(L1.length + L2.length > result.maxsize) return false;
    int i_L1 = 0,i_L2 = 0;
    int pos = 0;
    while(i_L1<L1.length && i_L2<L2.length){
        if(L1.data[i_L1]<=L2.data[i_L2]){
            result[pos] = L1.data[i_L1];
            pos++;
            i_L1++;
        }
        result[pos] = L2.data[i_L2];
        pos++;
        i_L2++;
    }
    while(i_L1<L1.length){
        result[pos] = L1.data[i_L1];
        pos++;
        i_L1++;
    }
    while(i_L2<L2.length){
        result[pos] = L2.data[i_L2];
        pos++;
        i_L2++;
    }
    result.length = pos;
    return result;
}

5. 顺序表循环左移p个单位

void reserve(SqList &L, int start, int end){
    int temp;
    for(int i = 0;i <= (start-end)/2; i++){
        temp = L.data[start + i];
        L.data[start + i] = L.data[end - i];
        L.data[end - i] = temp;
    }
}
void function(SqList &L, int p){
    reserve(L, 0, p-1);
    reserve(L, p, L.length-1);
    reserve(L, 0, L.length-1);
}

6. 求两个等长的升序顺序表L1、L2的并集的中位数

void fucntion(SqList L1, SqList L2){
    int mid_L1 = L1.data[L1.length/2];
    int mid_L2 = L2.data[L2.length/2];
    

}

2.3 线性表的链式表达（链表）

2.3.1 单链表

定义与初始化

//单链表的定义
typedef struct LNode{
    ElemType data;
    LNode *next;
}LNode, *LinkList;

//带头节点的初始化（仅需要初始化头节点）
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    return true;
}

//不带头节点的初始化（仅需设定为NULL）
bool InitList(LinkList &L){
    L = NULL;
    return true;
}

单链表的相关操作

//获取单链表长度
int Length(LinkList L){
    int length = 0;
    LNode *temp = L;
    while(temp->next != NULL){
        length++;
        temp = temp->next;
    }
    return length;//带头节点
    return length+1;//不带头节点
}

//按位序号查找节点(带头节点)
LNode* GetElem(LinkList L, int i){
    if(i<1) return false;
    int pos = 0;
    LNode* temp = L;
    while(pos<i || temp->next!=NULL){
        pos++;
        temp = temp->next;
    }
    if(pos == i) return temp;
    return NULL;
}

//按值查找节点(带头节点)
LNode* GetElem(LinkList L, ElemType e){
    LNode* temp = L->next;
    while(temp->data != e && temp!=NULL){
        temp = temp->next;
    }
    return temp;
}

//在第i位序插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1) return false;
    int pos = 0;
    LNode* p = L;
    while(pos<i-1 && p!=NULL){
        pos++;
        p = p->next;
    }
    if(p == NULL) return false;
    LNode* temp = (LNode *)malloc(sizeof(LNode*));
    temp->data = e;
    temp->next = p->next;
    p->next = temp;
}

//删除位序为i的元素并用e返回被删除元素的值
bool ListDelete(LinkList &L, int i, ElemType* e){
    int pos = 0;
    LNode* p = L;
    while(pos < i-1 && p != NULL){
        pos++;
        p = p->next;
    }

    if(p==NULL || p->next == NULL) return false;

    e = p->next->data;
    LNode* temp = p->next;
    p->next = temp->next;
    free(temp);
    return true;
}

//头插法建立链表
LinkList ListHeadInsert(LinkList &L){
    if(L==NULL){
        L = (LNode*)malloc(sizeof(LNode*));//初始化头节点
        L->next = NULL;
    }

    int x;
    scanf("%d", &x)
    while(x!=999){
        LNode* p = (LNode *)malloc(sizeof(LNode*));
        p->data = x;
        p->next = L->next;
        L->next = p;
        scanf("%d", &x)
    }
    return L;
}

//尾插法建立链表
LinkList ListHeadInsert(LinkList &L){
    if(L==NULL){
        L = (LNode*)malloc(sizeof(LNode*));//初始化头节点
        L->next = NULL;
    }
    LNode* p = L;
    int x;
    scanf("%d", &x)
    while(x!=999){
        LNode* temp = (LNode *)malloc(sizeof(LNode*));
        temp->data = x;
        p->next = temp;
        p = temp;
        scanf("%d", &x)
    }
    p->next = NULL;//注意！
    return L;
}

2.3.2 双链表

定义与初始化

//双链表定义
typedef struct DNode{
    struct DNode* prior;
    struct DNode* next;
    ElemType data;
}DNode, *DLinkList;

//双链表初始化
void InitList(DLinkList &L){
    L = (DNode*)malloc(sizeof(DNode));
    L->prior = NULL;
    L->next = NULL;
}

双链表的操作

//双链表的后继插入
bool ListInster_after(DLinkList &L, int i, ElemType e){
    if(i<1 || L==NULL) return false;
    DNode *p = L;
    int pos = 0;
    while(pos < i-1 && p!=NULL){
        p = p->next;
        pos++;
    }
    if(p == NULL) return false;
    DNode* temp = (DNode*)malloc(sizeof(DNode*));
    temp->data = e;
    
    temp->prior = p;
    temp->next = p->next;
    if(p->next != NULL){
        p->next->prior = temp;
    }
    p->next = temp;
    return true;
}

//双链表的删除操作
bool ListDelete(DLinkList &L, int i){
    if(i<1 || L==NULL) return false;
    DNode *p = L;
    int pos = 0;
    while(pos < i && p!=NULL){
        p = p->next;
        pos++;
    }
    if(p == NULL) return false;
    p->prior->next = p->next;
    if(p->next!=NULL) p->next->prior = p->prior;
    free(p);
}

2.3.3 循环链表

循环链表的定义与初始化

//单循环链表的定义
typedef struct LNode{
    struct LNode* next;
    ElemType data;
}LNode, *LinkList;

//双循环链表的定义
typedef struct DNode{
    struct LNode *next, *prior;
    ElemType data;
}DNode, *DLinklist;

//单循环链表的初始化
void InitList(LinkList &L){
    L = (LNode*)malloc(sizeof(LNode));
    if(L==NULL) return false;
    L->next = L;
}

//双循环链表的初始化
void InitList(DLinkList &L){
    L = (DNode*)malloc(sizeof(DNode));
    if(L==NULL) return false;
    L->next = L;
    L->prior = L;
}

循环链表的操作

//判断是否为空
bool Empty(LinkList L){
    return L->next == L;
}

//判断是否为尾节点
bool is_Tail(LinkList L, LNode *p){
    return p->next == L;
}

//插入和删除和之前一样，但是不需要进行边界的判空操作！

2.3.4 静态链表

2.3.5 顺序表与链表的比较

逻辑结构：均为线性结构

存储结构：

顺序表为顺序存储，链表为链式存储

顺序表：

优点：支持随机存储、存储密度高；
缺点：大片连续空间分配不方便、且改变容量不方便

链表：

优点：离散的小空间，分配方便，改变容量方便
缺点：不可随机存取，存储密度低

操作方式：

按值查找：顺序表无序时，时间复杂度为O(n);顺序表有序时，时间复杂度为O(logn);链表始终为O(n)。
按位查找：顺序表为O(1)，链表为O(n)。
插入和删除：顺序表和链表均为O(n)，但是链表比顺序表快得多。（顺序表需要移动大量数据）

评价两种数据结构的方式：

存储结构
逻辑结构
对应的相关运算效率比较
得出结论……

注意

链表节点内的存储单元地址为连续的
建立一个有序单链表的最低时间复杂度为O(nlogn)（数组排序最快为O(nlogn)，排序后建立链表为O(n)，综上为O(nlogn)）
需要分配大量空间，且删除和插入无需移动元素的线性表为：静态链表

原文地址：https://blog.csdn.net/qiantianye/article/details/145241204

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：VIM 的 YCM 插件
下一篇：【C语言3】分支与循环：if-else、关系操作符、条件操作符、逻辑操作符、switch语句、while、for、fo-while循环、break和continue、goto语句

ubuntu24.04安装mysql 5.7.44版本
使用下面命令，查看配置信息是否，这一步非常重要，配置文件不生效，会导致系统区分大小写表。创建该文件，退出的时候，就算不输入内容，也要强制保存一下 :wq!命令来更新init系统，以便在系统启动时自动启
阅读更多2025-01-22
SQLmap 自动注入 -02
SQLmap 是SQL注入的超级工具，这次参数是 -dbs, 还要-users, --current-user
阅读更多2025-01-22
AI大模型-提示工程学习笔记12-检索增强生成(RAG)
是一种结合检索（Retrieval）和生成（Generation）的技术，旨在通过从外部知识库中检索相关信息，增强大语言模型（LLM）的生成能力。尽管 RAG 面临一些挑战（如检索质量、知识库维护成本
阅读更多2025-01-22
在亚马逊云科技上用AI提示词优化功能写出漂亮提示词（下）
提示工程（Prompt Engineering）对各位小伙伴们来说是再熟悉不过了，提示词工程技术是通过编写指令词，指导开发者们调用AI基础模型（FMs）获得期望的响应。但是经常写提示词的朋友们会知道，
阅读更多2025-01-22
他把智能科技引入现代农业领域
江苏田倍丰农业科技有限公司（以下简称“田倍丰”）是一家专注于粮油种植的农业科技公司，为拥有300亩以上田地的大户提供全面的解决方案。田倍丰通过与当地政府合作，将土地承包给大户，并提供农资和技术，实现利
阅读更多2025-01-22
深圳市云盟智慧科技有限公司智慧停车管理系统 SQL注入漏洞复现（附脚本）
深圳市云盟智慧科技有限公司智慧停车管理系统 /GetVideo 接口存在SQL注入漏洞，未经身份验证的恶意攻击者利用 SQL 注入漏洞获取数据库中的信息（例如管理员后台密码、站点用户个人信息）之外，攻
阅读更多2025-01-22
江天科技主要产品销售单价下滑，应收账款、存货周转率大幅下降
报告期各期，公司薄膜类不干胶标签实现营收分别为2.37亿、2.75亿、3.90亿、2.21亿，营收占比分别为68.20%、71.69%、76.77%、79.23%；此外，报告期各期，江天科技毛利率分别
阅读更多2025-01-22
PAT乙级真题 — 1060 爱丁顿数（java）
英国天文学家爱丁顿很喜欢骑车。据说他为了炫耀自己的骑车功力，还定义了一个“爱丁顿数” E ，即满足有 E 天骑车超过 E 英里的最大整数 E。据说爱丁顿自己的 E 等于87。现给定某人 N 天的骑车距
阅读更多2025-01-22
AutoSAR CP RTE 规范核心内容简介以及BswScheduler工作原理解析
本规范详细介绍了AUTOSAR运行时环境（RTE）和基本软件调度器（BswScheduler）的软件规范。RTE概述：AUTOSAR概念：RTE生成过程：RTE功能规范：RTE与基本软件调度器的交互：
阅读更多2025-01-22
UE5 开启“Python Remote Execution“
在启用 Unreal Engine 5（UE5）的“Python 远程执行”功能后，UE5 会启动一个 UDP 组播套接字服务，以监听来自外部应用程序的 Python 命令。通过这种方式，UE5 实现
阅读更多2025-01-22

数据结构与算法整理复习（一）：数据结构概念与线性表

第一章：绪论

1.1 数据结构的基本概念

1.2 算法与算法评价

第二章：线性表

2.1 线性表的定义和基本操作

2.2 线性表的顺序表示（顺序表）

应用题

2.3 线性表的链式表达（链表）

2.3.1 单链表

2.3.2 双链表

2.3.3 循环链表

2.3.4 静态链表

2.3.5 顺序表与链表的比较

相关文章