数据结构

线性表

算法

定义

解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列

特性

  • 有穷性
  • 确定性
  • 可行性

算法效率的度量

运行时间

  • 取决于算法的好坏与问题的输入规模（输入量）

算法时间复杂度

  • $T(n)=O(f(n))$

    • T(n)增长最慢的为最优算法

  • 分类与排序

    • $O(1) < O(log(n))< O(n) < O(nlog(n)) < O(n^2) < O(n^3) < O(n!) < O(n^n)$

  • 最坏情况与平均情况

    • 一般运行时间为最坏运行时间
    • 平均运行时间是一个期望值

算法空间复杂度

  • $S(n)=O(f(n))$

线性表(List)

线性表(List)定义

  • 零个或多个数据元素的有限序列
  • 每个元素都有一个直接前驱和直接后继元素
  • 数据元素是一对一的关系

抽象数据类型

Operation
    IintList(*L);
    ListEmpty(L);
    GetElem(L,i,*e);
    LocateELem(L,e);
    ListInsert(*L,i,e);
    ListDelete(*L,i,*e);
    ListLength(L);
endADT

顺序存储结构

定义

用一段地址连续的存储单元依次存放线性表的数据元素

三个属性

  • 最大长度
  • 当前长度
  • 起始位置

结构代码

1
2
3
4
5
6
7

    #define MAXSIZE 20
    typedef int ElemType
    typedef struct
    {   
        ElemType data[MAXSIZE]; //数组存取数据元素
        int length; //线性表当前长度
    }SqList;

插入与删除

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

    //插入
    Status ListInsert(SqList *L,int i, ElemType e)
    {
        int k;
        if (L->length==MAXSIZE)
            return -1;
        else if (i<1 || i>L->length)
            return -1;
        else
        {
            for(k=L->Length-1;k->i-1;k--)
                L->data[k+1]=L->data[k];
        }
        L->data[i-1]=e;
        L->length++;
        return 0;
    }

    //删除
    Status ListDelete(SqList *L, int i, ElemType e)
    {
        int k;
        if (L->length==0)
            return -1;
        else if (i<1 || i>L->length)
            return -1;
        *e=L->data[i-1];
        if (i<L->length)
        {
            for(k=i;k<L->length;k++)
                L->data[k+1]=L->data[k];
        }
        L->length--;
        return 0;
    }

链式存储结构

结点

数据域

  • 存储数据元素信息的域

指针域

  • 存储直接后继的域
  • 存储的信息称指针(链)
  • 最后一个结点指针为空

头指针

  • 链表中第一个结点的存储位置

头结点

  • 在第一个结点前加一个头结点
  • 数据域可以为空
  • 对第一个结点进行的操作可以统一

单链表(每个结点只包含一个指针域的链表)操作

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

    //定义
    typedef struct Node
    {
        ElemType data;
        struct Node *next;
    }Node;
    typedef struct Node *LinkList;
    
    //读取
    Status GetElem(LinkList L,int i,ElemType *e)
    {
        int j;
        LinkList p;
        p = L->next;
        j = 1;
        while (p && j<i) //p不为空且j小于i的时候
        {
            p = p>-next;
            j++;
        }
        if (!p || j>i)
            return -1; //第i个元素不存在
        *e = p->data; // 取第i个元素的数据
        return 0;
    }

    //插入
    Status ListInsert(LinkList L,int i,ELemType e)
    {
        int j;
        LinkList,p,s;
        p =*L;
        j=1;
        while(p&&j<i)
        {
            p=p->next;
            ++j;
        }
        if (!p||j>i)
            return -1;
        s = (LinkList)malloc(sizeof(Node)); //生成新结点 
        s->data=e;
        s->next=p->next;
        p->next=s;
        return 0;
    }

    //删除
    Status ListDelete(LinkList L,int i,ElemType e)
    {
        int j;
        LinkList p,q;
        p =*L;
        j=1;
        while(p=p->next&&j++<i)
            ;
        if (!(p->next) || j > i)
            return -1;
        q = p->next;
        p ->next = q->next;
        *e = q->data //回收删除数据
        free(q);
        return 0;
    }
    
    //整表创建
    //头插法
    void CreateListHead(LinkList *L, int n)
    {
        LinkList p;
        int i;
        srand(time(0));
        *L = (LinkList)malloc(sizeof(Node));
        (*L)->next = NULL;
        for (i=0;i<n;i++)
        {
            p = (LinkList)malloc(sizeof(Node));
            p->data = rand()%100+1;
            p->next = (*L) ->next;
            (*L)->next = p;
        }
    }
    //尾插法
    void CreateListTail(LinkList *L, int n)
    {
        LinkList p,r;
        int i;
        srand(time(0));
        *L = (LinkList)malloc(sizeof(Node));
        r = *L;
        for(i=0;i<n;i++)
        {
            p = (Node *)malloc(sizeof(Node));
            p->data = rand()%100+1;
            r->next = p;
            r = p;
        }
        r->next = NULL;
    }

    //整表删除
    Status ClearList(LinkList *L)
    {
        LinkList p,q;
        *p=(*L)->next;
        while(p)
        {
            q=p->next;
            free(q);
            p=q;
        }
        (*L)->next=NULL;
        return 0;
    }

单链表结构和顺序存储结构的优缺点

对比/分类 顺序存储结构 单链表
查找 O(1) O(n)
插入和删除 O(n) O(1)
空间 需要预分配，灵活性和安全性低 非常棒

静态链表

定义

用数组描述的链表

组成

  1. 数据域

  2. 游标(cur)

  • 第一个游标存放备用链表第一个结点的下标
  • 最后一个游标存放第一个插入元素的下标
  1. 特殊称呼 —— 备用链表
  • 未被使用的数组元素

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

    //定义
    #define MAXSIZE 1000
    typedef struct
    {
        ELemType data;
        int cur;  
    }Component,StaticLinkList[MAXSIZE];

    //初始化
    Status InitList(StaticLinkList space)
    {
        int i;
        for(i=0;i<MAXSIZE-1;i++)
            space[i].cur=i+1;
        space[MAXSIZE-1].cur=0;
        return 0;
    }
    
    //插入
    Status ListInsert(StaticLinkList L,int i, Elemtype e)
    {
        int j,k,l;
        k=MAXSIZE-1;
               
    }

循环链表

定义

将单链表的最后一个指针指向头结点,形成循环链表

合并循环链表

  • 代码
1
2
3

p = rearA->next; //将A的头结点存起来
rearA->next = rearB->next-next;//让A的尾结点指向B的第二个结点，B的头结点被抛弃
rearB->next = p;//让B的结尾指向A的头结点

双向链表

定义

  • 在每一个结点中设置一个指向其前驱结点的指针的单链表

存储结构

1
2
3
4
5
6

typedef struct DulNode
{
	Elemtype data;
	struct DulNode *prior;
	struct DulNode *next;
} DulNode,*DulLinkList;

有趣的事实

  • 后继的前驱 = 前驱的后继 = 自己
1

p->next->prior = p->prior->next = p

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 插入
s->prior = p;
s->next = p->next;
p->next->prior=s;
p->next=s;

//删除
p->prior->next=p->next;
p-next->prior=p->prior;
free(p);
Licensed under CC BY-NC-SA 4.0
comments powered by Disqus
© 2022 - 2024 Flyfan Blog
Built with Hugo
Theme Stack designed by Jimmy