2021-09-04

2024-02-01 20:23:52

数据结构01

1.线性表 （零个或者有限个元素组成的数列）

特点：

（1）线性表元素有限，可以为0个（当为0个时候 = 空表）

（2）元素数据类型相同

（3）索引和数据一一对应

1.1 线性表的顺序存储结构

相当于数组，开辟一块连续的存储空间存储数据

2021-09-04

# define MAXSIZE 20

typedef int ElemType;           //抽象数据类型

typedef struct
{
    ElemType data[MAXSIZE];    //线性表数据   
    int length;                // 当前表最大长度
}Sqlist;

（1）数据起始位置：data

（2）线性表最大存储容量：MAXSIZE

（3）线性表当前长度：length

1.1.1 获取特定元素

将线性表中第i个数据元素返回

2021-09-04

# define OK 1
# define ERROR 0

typedef int status;       // 函数返回类型

status GetElem (Sqlist L,int i, ElemType *pe)
{
    
    if (L.length == 0 || i<1 || i>L.length)      // 线性表的索引[1,n]
    {
        return ERROR;
    }
    
    *pe = L.data[i-1];
    
    return OK;     
}
// 时间复杂度为O(1)

1.1.2 插入元素

在线性表中指定位置插入元素

1. 从索引i - n 向后移动

2.在i处放数据

3.表长度+1

注意： 索引i = 数组中的i-1

2021-09-04

status ListInsert (Sqlist *L,int i, ElemType e)
{
    if (L->length == MAXSIZE)   //表已满
    {
        return ERROR;
        
    }
     
    if (i<1 || i>L->length+1)   // 索引位置不合适
    {
        return ERROR;
    }
    
    int j = 0;
    for (j = L->length-1;j>=i;j--)
    {
        L->data[j] = L->data[j-1];
    }
    
    L->data[i-1] = e;
    L->length++;
    
    return OK;
    
}
// 时间复杂度O(N)

1.1.3 删除元素

删除指定位置的元素，并将删除的元素返回

1.将i处的值取出来

2. i - n处的数据前移

3.表长度-1

注意： 索引i = 数组中的i-1

2021-09-04

status ListDelete (Sqlist *L,int i,ElemType *pe)
{
    if (L->length == 0)  //空表
    {
        return ERROR;
    }
    
    if (i<1 || i>L->length)
    {
        return ERROR;
    }
    
    *pe = L->data[i-1];
    
    int k = 0;
    for (k = i,k<=L->length;k++)
    {
        L->data[i-1] = L->data[i];
    }
    
    L->length--;
    return OK;
}
// 时间复杂度为O(N)

1.1.4 线性表顺序存储结构优缺点

优点：**1. 读取数据的时间复杂度为O(1) **

​ 2.数据的逻辑结构和数据的物理结构相同

缺点： 1.线性表的长度MAXSIZE不可以修改，不能动态维护线性表

​ 2.插入数据和删除数据的时间复杂度为O(N)

1.2 线性表的链式存储结构

为解决顺序存储结构中插入数据和删除数据需要移动大量数据，链式存储数据方式诞生

一组任意内存地址单元存储线性表的数据的组织形式

头结点可有可无，但头指针必须用

2021-09-04

2021-09-04

typedef struct
{
    Elemtype data;                  //数据域
    struct Node* next;              //指针域
}Node;

typedef struct Node* LinkList;

1.2.1 读取数据

算法思路:

​ 1.声明一个节点p指向链表第一个节点，初始化j = 1

​ 2.当j<i时，遍历链表，p的指针向后移动，j++

​ 3.如果链表末尾p为NULL，则第i个元素不在链表中

​ 4.否则查找成功，返回p节点的数据

2021-09-04

status GetElem (LinkList L,int i,ElemType *pe)
{
    LinkList p = L->next;
    
    int j = 1;
    for (j = 1;p != NULL && j<i; j++)
    {
        p = p->next;
    }
    
    if (p==NULL)
    {
        return ERROR;
    }
    *pe = p->data;
    
    return OK;
}
// 时间复杂度为O(N)

1.2.2 插入元素

算法思路：

​ 1. 声明p指向第一个节点，初始化j = 1

​ 2. 当j<i，p的指针向后移；j++

​ 3. 若到链表尾部p为NULL，则该数据元素不在该链表中

  1. 否则查找成功，并生成节点s

​ 5. 将数据e赋值给s->data

  1. 在链表p和p->next中间插入s

2021-09-04

status ListInsert (LinkList *L,int i,ElemType e)
{
    LinkList p = *L;    // p 是指向第一个节点的指针
    
    int j = 1;
    for (j = 1;p != NULL && j<i; j++)
    {
        p = p->next;
    }
    if (p==NULL)
    {
        return ERROR;
    }
    
    LinkList s = (LinkList)malloc(sizeof(Node));
    if (s==NULL)
    {
        return ERROR;  //空间开辟失败
    }
    else
    {
        s->data = e;  
    }
  
    s->next = p->next;
    p->next = s;
    
    return OK;
}
//时间复杂度O(1)

1.2.3 删除元素

算法思路：

  1. 声明p指向第一个节点，初始化j = 1
  2. 当j<i，p的指针向后移；j++
  3. 若到链表尾部p为NULL，则该数据元素不在该链表中
  4. 否则查找成功，将p->next 赋值给q
  5. 释放p,p->next = q->next;
  6. 将q中的数据为返回值

2021-09-04

status ListDelete (LinkList *L,int i,ElemType *pe)
{
    LinkList p = *L;
    
    int j = 1;
    for (j =1;p != NULL && j<i; j++)
    {
        p = p->next;
    }
    
    if(p == NULL)
    {
        return ERROR;
    }
    
    *pe = p->data;
    LinkList q = p->next;
    p->next = q->next;
    free(p);
    
    return OK;
}
//时间复杂度O(1)

1.2.4 单链表的整表创建

算法思路：

​ 1.声明一节点p和计数器变量i

​ 2.初始化一空表L

​ 3.L的头节点指向NULL，建立一个带头节点的单链表

​ 4.循环

​ 生成新结点赋值给p

​ 随机生成数字给p->data

​ 将p插入到头节点与前一新节点之间

void ListCreateHead (LinkList *L,int n)   //头插法
{
    LinkList *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    srand((unsigned)time(0));
    int j = 1;
    // 在 头结点 *L  和第一个节点 （*L）->next 插入p
    for (j = 1; j<n;j++)
    {
       LinkList p = (LinkList)malloc(sizeof(Node));
       p->next = (*L)->next;                             
      (*L)->next = p;
    }

    return OK;
}

void ListCreateTail (LinkList *L,int n)   //尾插法
{
    LinkList *L = (LinkList)malloc(sizeof(Node));
    LinkList r = *L;   //r 指向表尾
    
    srand((unsigned)time());
    
    int j = 1;
    for (j =1;j<n;j++)
    {
        LinkList p = (LinkList)malloc(sizeof(Node));
        p->data =rand()%100+1;
        r->next = p;
        r = p;
    }
    r->next = NULL;
    return OK;
}

2021-09-04

1.2.5 单链表的整表删除

算法思路：

​ 1.声明结点p和q

​ 2.将第一个结点赋值给p

​ 3.循环

​ 将下一节点赋值给q

​ 释放p

​ 将q赋值给p

status ClearList (LinkList *L)
{
    LinkList p,q;
     p = (*L)->next;
    
    int j = 1;
    for (j = 1;p != NULL;j++)
    {
        q = p->next;
        free(q);
        p = q;
    }
    (*L)->next =NULL;
    return OK;
}

1.2.6 链表结构优缺点

顺序存储 链式存储
存储方式 栈区，连续存储单元 堆区，不连续存储单元（动态增加 / 删除）
时间复杂度 读取数据复杂度为O(1) 插入/删除数据复杂度为O(N) 读取数据复杂度为O(N) 插入/删除数据复杂度为O(1)
空间复杂度 需要预分配存储空间 MAXSIZE 不需要预分配内存空间

1.3 静态链表

利用数组描述链表 = 静态链表

1.3.1 静态链表结构

2021-09-04

# define MAXSIZE 50

typedef int ElemType;

typedef struct
{
    ElemType data;
    int cur;
}StaticLinkList[MAXSIZE];

1.3.2 初始化操作

// L[0].cur = 备用链表中第一个数据元素的下标
// L[MAXSIZE-1].cur = 静态链表中第一个数据元素的下标
typedef int Status;

Status InitList(StaicLinkList L)
{
    int i;
    
    for (i = 0;i<MAXSIZE-1;i++)
    {
        L[0].cur = i+1;
    }
    
    L[MAXSIZE-1].cur = 0;
    
    retuern OK;
}

1.3.2 插入数据(1. 从备用链表中取空间 2.插入)

int Malloc_SSL (StaicLinkList L)
{
    int i = L[0].cur;                 // L[0].cur = 备用链表中第一个数据元素的下标
    
    if (i)
    {
        L[0].cur = L[i].cur;         //  链表的第一个元素对应表尾（原来是i，现在是L[i].cur）
    }
    
    return i;
}

Status InsertList (StaicLinkList L,int i,ElemType e)
{
    int j = Malloc_SSL(L);
    int k = MAXSIZE - 1;
    
    if (i < 1 || i > ListLength(L)+1)
    {
        return ERROR;
    }
    
    if (j)
    {
        int l = 0;
    for(l=1;l<i;l++)         // 找到第i-1元素的位置 
    {
        k = L[k].cur;
    }
    
    L[k].data = e;
    
    L[j].cur = L[k].cur;      // 把第i个元素之前的cur赋值给新元素的cur
    L[k].cur = j;             // 把新元素的下标赋值给第i个元素之前元素的Cur
    return OK; 
    }
    
    return ERROR;
}

2021-09-04

1.3.3 删除数据

static Status Free_SSL (StaicLinkList L,int k)
{
    L[k].cur = L[0].cur;               
	L[0].cur = k;                      // L[0].cur 存放的是备用链表中的第一个下标
    
    return OK;
}

Status DeleteList (StaicLinkList L,int i)
{
    if (i < 1 || i > ListLength(L))
    {
        return ERROR;
    }
    
    int k = MAXSIZE - 1;
    for (j = 1;j<i;j++)
    {
        k = L[k].cur;
    }
    
    j = L[k].cur;
    L[k].cur = L[j].cur;
    
    Free_SSL(L,j);
}

优点：删除/插入数据，只需要移动游标

缺点：读取数据麻烦，没有解决连续存储分配带来的内存大小难以确定的问题

上一篇：(含头结点)单链表的节点删除,增加---最易犯错!!!


下一篇：ExtJs中gridpanel分组后组名排序