首页 > 其他分享 >数据结构-表

数据结构-表

时间：2023-09-08 09:13:03浏览次数：26  
标签：Node index arr head next 数据结构 data

表：   顺序(数组) 、 链式(链表)

一、顺序表

  • 数据项：

存储元素的内存首地址

表的容量

元素的数量

  • 运算：

创建、销毁、清空、插入、删除、访问、查询、修改、排序、遍历

  • 注意：

1、要确保数据元素的连续性

2、不能越界

  • array 顺序表
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#define TYPE int
#define PH "%d "

//    设计顺序表结构
typedef struct Array
{
    TYPE* ptr;        //    存储元素的内存首地址
    size_t cal;        //    表的容量
    size_t cnt;        //    元素的数量
}Array;

//    创建
Array* create_array(size_t cal)
{
    //    给顺序表结构分配内存
    Array* arr = malloc(sizeof(Array));
    //    给数据元素分配内存
    arr->ptr = malloc(sizeof(TYPE)*cal);
    //    记录表的容量
    arr->cal = cal;
    //    初始化元素的数量
    arr->cnt = 0;

    return arr;
}

//    销毁
void destroy_array(Array* arr)
{
    free(arr->ptr);
    free(arr);
}
//    清空
void clear_array(Array* arr)
{
    arr->cnt = 0;    
}

//    插入
bool insert_array(Array* arr,size_t index,TYPE data)
{
    //    判断表是否满
    if(arr->cnt >= arr->cal)    return false;
    //    判断下标是否能保持元素的连续性
    if(index > arr->cnt) return false;

/*
    //    数据向后移动
    for(int i=arr->cnt; i>index; i--)
    {
        arr->ptr[i] = arr->ptr[i-1];    
    }
*/
    memmove(arr->ptr+index+1,arr->ptr+index,(arr->cnt-index)*sizeof(TYPE));

    //    插入数据
    arr->ptr[index] = data;
    arr->cnt++;
    return true;
}

//    删除
bool delete_array(Array* arr,size_t index)
{
    if(index >= arr->cnt) return false;
    /*
    for(int i=index; i<arr->cnt-1; i++)
    {
        arr->ptr[i] = arr->ptr[i+1];
    }
    */
    memmove(arr->ptr+index,arr->ptr+index+1,(arr->cnt-index-1)*sizeof(TYPE));
    arr->cnt--;
    return true;
}

//    访问
bool access_array(Array* arr,size_t index,TYPE* data)
{
    if(index >= arr->cnt) return false;
    *data = arr->ptr[index];
    return true;
}

//    查询
int query_array(Array* arr,TYPE data)
{
    for(int i=0; i<arr->cnt; i++)
        if(arr->ptr[i] == data) return i;
    return -1;
}
//    修改
bool modify_array(Array* arr,size_t index,TYPE data)
{
    if(index >= arr->cnt) return false;
    arr->ptr[index] = data;
    return true;
}

//    排序
void sort_array(Array* arr)
{
    for(int i=0; i<arr->cnt-1; i++)
    {
        for(int j=i+1; j<arr->cnt; j++)    
        {
            if(arr->ptr[j] < arr->ptr[i])
            {
                TYPE temp = arr->ptr[j];
                arr->ptr[j] = arr->ptr[i];
                arr->ptr[i] = temp;
            }
        }
    }
}

//    遍历
void show_array(Array* arr)
{
    for(int i=0; i<arr->cnt; i++)
    {
        printf(PH,arr->ptr[i]);    
    }
    printf("\n");
}

int main(int argc,const char* argv[])
{
    Array* arr = create_array(10);    

    for(int i=0; i<5; i++)
    {
        insert_array(arr,0,i+1);    
    }

    insert_array(arr,1,8);    
    delete_array(arr,5);
    show_array(arr);

    int num = 0;
    if(access_array(arr,5,&num))
        printf("num=%d\n",num);
    else
        printf("index error\n");

    printf("index=%d\n",query_array(arr,80));

    sort_array(arr);
    clear_array(arr);
    show_array(arr);
    destroy_array(arr);

}

二、链式表list

  • 数据元素(节点)的数据项：

数据域：可以是各种类型的若干项数据项

指针域：指向下一个节点的指针

由若干个节点通过指针域连接起来就形成了链表

  • list 链表
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define TYPE int

//    设计链表的节点结构
typedef struct Node
{
    TYPE data;            //    节点的数据域
    struct Node* next;    //    节点的指针域
}Node;

//    创建节点
Node* create_node(TYPE data)
{
    //    申请节点的内存
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}

//    头添加
void add_head_list(Node** head,TYPE data)
{
    //    创建待添加的节点
    Node* node = create_node(data);
    node->next = *head;    //带头节点node->next = head->next;
    *head = node;    //带头节点head->next = node;
}

//    按值删除
bool del_value_list(Node** head,TYPE data)
{
    if((*head)->data == data)
    {
        Node* temp = *head;
        *head = (*head)->next;
        free(temp);
        return true;
    }
    //    遍历找到待删除节点的前一个节点
    for(Node* n=*head; n->next; n=n->next)
    {
        if(n->next->data == data)
        {
            Node* temp = n->next;
            n->next = n->next->next;
            free(temp);
            return true;
        }
    }
    return false;
}

//    遍历链表
void show_list(Node* head)
{
    for(Node* n=head; n; n=n->next)
    //带头节点for(Node* n=head->next; n; n=n->next)
    {
        printf("%d ",n->data);    
    }
    printf("\n");
}

//    访问
bool access_list(Node* head,size_t index,TYPE* data)
{
    int i = 0;
    for(Node* n = head; n; n=n->next,i++)
    {
        if(i == index) 
        {
            *data = n->data;
            return true;
        }
    }
    return false;
}

//    排序
void sort_list(Node* head)
{
    for(Node* i=head; i->next; i=i->next)
    {
        for(Node* j=i->next; j; j=j->next)
        {
            if(j->data < i->data)
            {
                TYPE temp = j->data;
                j->data = i->data;
                i->data = temp;
            }
        }
    }
}

//    按位置删除
bool del_index_list(Node** head,size_t index)
{
    if(0 == index)
    {
        Node* temp = *head;
        *head = temp->next;
        free(temp);
        return true;
    }

    Node* n = *head;
    for(int i=1; n->next; n=n->next,i++)
    {
        if(i == index)
        {
            Node* temp = n->next;
            n->next = temp->next;
            free(temp);
            return true;
        }
    }
    return false;
    /*
    while(--index)
    {
        n = n->next;
        if(NULL == n) return false;
    }

    if(NULL == n->next) return false;
    Node* temp = n->next;
    n->next = temp->next;
    free(temp);
    */
    return true;
}


int main(int argc,const char* argv[])
{
    Node* head = create_node(10);

    for(int i=0; i<5; i++)
    {
        add_head_list(&head,i+1);    
    }
    show_list(head);
    del_value_list(&head,100);
    show_list(head);
    int num = 0;
    access_list(head,20,&num);
    printf("num=%d\n",num);
    sort_list(head);
    show_list(head);
    del_index_list(&head,2);
    show_list(head);

    /*    理解链表的本质
    Node* n1 = create_node(10);
    Node* n2 = create_node(20);
    Node* n3 = create_node(30);
    Node* n4 = create_node(40);
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;

    for(Node* n=n1; n; n = n->next)
    {
        printf("%d ",n->data);    
    }
    */
}

2.1不带头节点的链表：

定义：第一个节点的数据域存储的是有效数据

缺点：当插入、删除时可能会改变第一个有效节点，传递的参数需要传递二级指针，实现时需要区分是否是操作第一个有效节点，较为麻烦

2.2带头节点的链表：

定义：第一个节点作为头节点，数据域不使用不存储有效数据，它的指针域永远指向链表的第一个有效数据节点，就算链表长度为0，头节点依然存在

有效数据节点的处理应当从head->next开始

  • 链表list
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define TYPE int

typedef struct Node
{
    TYPE data;
    struct Node* next;
}Node;

//    创建节点
Node* create_node(TYPE data)
{
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}

//    头添加
void add_head_list(Node* head,TYPE data)
{
    Node* node = create_node(data);
    node->next = head->next;
    head->next = node;
}

//    遍历
void show_list(Node* head)
{
    //    有效数据节点的处理应当从head->next开始
    for(Node* n=head->next; n; n=n->next)
    {
        printf("%d ",n->data);    
    }
    printf("\n");
}

//    尾添加
void add_tail_list(Node* head,TYPE data)
{
    Node* node = create_node(data);
    Node* n = head;
    while(n->next) n = n->next;
    n->next = node;
}

//    插入
bool insert_list(Node* head,size_t index,TYPE data)
{
    Node* n = head;
    for(int i=0; n->next; n=n->next,i++)
    {
        if(i == index)
        {
            Node* node = create_node(data);
            node->next = n->next;
            n->next = node;
            return true;
        }
    }
    return false;
}

//    按位置删除
bool del_index_list(Node* head,size_t index)
{
    Node* n = head;
    for(int i=0; n->next; n=n->next,i++)
    {
        if(i == index)    
        {
            Node* temp = n->next;
            n->next = temp->next;
            free(temp);
            return true;
        }
    }
    return false;
}

//    按值删除
int del_value_list(Node* head,TYPE data)
{
    int cnt = 0;
    Node* n = head;
    while(n->next)
    {
        if(data == n->next->data)
        {
            Node* temp = n->next;
            n->next = temp->next;
            free(temp);
            cnt++;
        }
        else    
            n = n->next;
    }
    return cnt;
}

//    修改
bool modify_list(Node* head,TYPE old,TYPE data)
{

}

//    访问
bool access_list(Node* head,size_t index,TYPE* data)
{

}

//    排序
void sort_list(Node* head)
{

}

int main(int argc,const char* argv[])
{
    //    head 指向头节点 不使用为有效数据节点
    //    head->next指向第一个有效数据节点
    Node* head = create_node(100);
    for(int i=0; i<10; i++)
    {
        add_tail_list(head,i+1);    
    }
    show_list(head);
    insert_list(head,3,88);
    insert_list(head,5,88);
    insert_list(head,8,88);
    insert_list(head,3,88);
    show_list(head);
    printf("%d\n",del_value_list(head,88));
    show_list(head);
    del_index_list(head,20);
    show_list(head);
}

优点：当插入、删除时是不会改变头节点的指向，只需要改变它的next，因此无需传递头节点的二级指针，并且实现时无需区分两种情况

注意：有效节点的处理必须从头节点的next开始

注意：笔试题时，如果题目没有说明链表是否带头节点，应该两种情况都进行分析

标签：Node,index,arr,head,next,数据结构,data
From： https://www.cnblogs.com/ljf-0804/p/17686570.html

相关文章

  • 数据结构-栈
    栈：只有一个出入口的表结构，先进后出，FILO表栈顶操作一、顺序栈数据项：存储元素的内存首地址栈的容量栈顶位置运算：创建、销毁、入栈、出栈、栈顶、栈空、栈满、数量栈相关的概念：假设栈容量为cal空增栈：top:0开始 先入栈，再top++，存储地址由低到高满增栈：top:-1开始......
  • 数据结构代码题-栈、队列
    目录栈、队列栈队列栈和队列的应用栈、队列栈栈的定义#defineMaxSize100//储存空间的初始分配量typedefintElemType;typedefstruct{inttop;//栈顶指针ElemTypedata[MaxSize];//存放元素的动态数组空间}sqstack;链栈的数据结构描述type......
  • 数据结构维护 mex 总结
    P4137solution1：我最初做这题是莫队，这是一道练习莫队+值域分块的好题。莫队的时候记录两个东西，\(b_i\)表示\(i\)在当前出现的次数，\(c_i\)表示值域第\(i\)块中有出现的数的个数。显然\(b,c\)都是可以满足莫队\(O(1)\)移动指针。而后查询枚举值域块，令\(len_i\)表示......
  • java递归返回树形数据结构
    近期项目有个需求，需要将组织机构数据拼成树型结构返回至前端。我的做法如下方式一、使用递归方式实现privateList<SysDept>getSysDepts(StringdeptId){//1、获取表中所有数据(自行根据实际场景拿到所有表数据)List<SysDept>all=getAllDept();......
  • 数据结构代码题-链表
    链表单链表单链表结构体的声明：typedefstructLink{ intdata;//代表数据域 structLink*next;//代表指针域，指向直接后继元素}link;//link为节点名，每个结点都是一个link结构体另一种：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*Link......
  • 数据结构复习——王道考研
    数据结构一.绪论1.1基本概念数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。数据类型：是相互之间存在一种或......
  • Redis数据结构
    5种基础数据结构：String（字符串）、List（列表）、Set（集合）、Hash（散列）、Zset（有序集合）。这5种数据结构是直接提供给用户使用的，是数据的保存形式，其底层实现主要依赖这8种数据结构：简单动态字符串（SDS）、LinkedList（双向链表）、HashTable（哈希表）、SkipList（跳跃表）、Intset（整数集合）、ZipLis......
  • 数据结构学习记录（二）
    树一、知识要点1、树的定义、表示和术语定义树（Tree）是n个节点构成的有限集合。当n=0时，称为空树；对于任一颗非空树（n>0），它具备以下性质：树中有一个称为树根（Root）的特殊节点，用r表示。树根下的任何子集也是一个树，都称为根节点r的子树（SubTree）。r是这些子树根节点的父节点（Parent）......
  • 数据结构-树状数组
    新接触到的数据结构，根据百度百科：树状数组或二叉索引树（英语：Binary IndexedTree），又以其发明者命名为Fenwick树，最早由PeterM.Fenwick于1994年以ANewDataStructure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE ANDEXPERIENCE。其初衷是解决数据压缩里......
  • C#数据结构之Tree
    usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;namespaceAlgorithmsDemo{publicclassTreeNode<T>{publicTData{get;set;}publicList<TreeNode<......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99