1顺序表与链表

抽象数据类型

实质：数学模型 （类型的属性和允许进行的操作）

例子：超级玛丽

属性：生命，高度…
操作：攻击，移动，技能…

线性表

线性结构

首端只有一个后继，尾端只有一个前驱，其余只有一个前驱和一个后继

顺序表

定义：一组地址连续的存储单元（通常在高级语言中以数组的形式表现）
基本操作：
增删改查
优点：
易于定位元素（方便查询）
缺点：
插入和删除需要移动大量元素，计算代价高。
长度固定，扩容难以确认，空间浪费。
一般适用于固定数据或很少修改的数据，基本不删除或者插入。
#include<stdio.h>
#include<stdlib.h>
#define Size 5

typedef struct ArrayList{
    //数组属性如下：
    int *e;//数组地址
    int size;//数组中元素个数（因为删除并不会清空最后的数据，所以无法直接判断数组是否已满，所以新增变量来存储）
    int length;//数组大小
}arr;

arr initarray();
void add(arr *myarr,int key);//增
void delete(arr *myarr,int key);//删
void modification(arr *myarr,int index,int key);//修改指定元素
int find(arr *myarr,int key);//查询

//辅助函数
void put(int *p,arr* myarr);
int main()
{
    
}

arr initarray()
{
    arr myarr;
    myarr.e=(int *)malloc(sizeof(int)*Size);
    //防范性检测
    if(!myarr.e)
    {
        printf("初始化失败");
        exit(0);  
    }
    
    myarr.size=0;
    myarr.length=Size;
    return myarr;
}

//按顺序添加元素
/*
myarr:结构体指针
key:添加的数据
*/
void add(arr *myarr,int key)
{
    //数组大小检测
    if(myarr->size<myarr->length)
    {
        myarr->e[myarr->size]=key;
        myarr->size++;
    }  
    else//不够则扩容
    {
        int *p=(int*)malloc(sizeof(int)*(myarr->length+Size));
        put(p,myarr);
        myarr->e[myarr->size]=key;
        myarr->size++;
    }
}

void put(int *p,arr* myarr)
{
    for(int i=0;i<myarr->size;i++)
    {
        p[i]=myarr->e[i];
    }
    free(myarr->e);
    myarr->e=p;
}

//删除操作
/*
arr *myarr:结构体
int key：需要删除的关键字
*/
void delete(arr *myarr,int key)
{
    //需要先找到关键字的下标
    int temp_index=find(myarr,key);
    if(temp_index==-1)
    {
        printf("没找到");
        return ;
    }
    else 
    {
        while(temp_index<myarr->size-1)
        {
            myarr->e[temp_index]=myarr->e[temp_index+1];
            temp_index++;
        }
        //移动完，数组元素个数-1
        myarr->size--;
    }
}

//查询操作
/*
arr *myarr:
int key:
*/
int find(arr *myarr,int key)
{
    //判断指针是否为空
    if(myarr==NULL)
    {
        printf("指针为空");
        return -1;
    }
    //先判断数组内部是否有元素
    if(myarr->size==0)
    {
        printf("当前没有元素");
        return -1;
    }
    else
    {
        for(int i=0;i<myarr->size;i++)
        {
            if(myarr->e[i]==key)
            {
                return i;
            }
        }
        return -1;
    }
    
}

//修改
/*
arr *myarr:结构体指针
int index：下标
int key：关键字
*/
void modification(arr *myarr,int index,int key)
{
    myarr->e[index]=key;
}

链表

定义：物理上不连续，逻辑上连续
结构：数据域与指针域
优点：大小可以不固定
缺点：定位慢

单链表

区分：
头结点：第一个不存放数据的结点（数据从第二个位置去存储）（可以没有这个结点，但头结点比较合适于插入操作）
头指针：指向第一个结点的指针
首元结点：第一个存放数据的结点

定义：只有一个指向下一个的指针

操作：增删改查
#include<stdlib.h>
#include<stdio.h>

typedef struct Linklist{
    int data;
    struct Linklist* next;
}Node;

Node* InitList(Node* node);//初始化链表
void head_insert(Node* head,int key);//头插
void delete(Node* head, int key);//删除
int index(Node* head,int key);//查找元素(返回下标)
Node* find(Node* head,int key);//查找元素(返回指针)
Node *find_l(Node* head,Node *aim);//查找上一个指针
int main()
{
    
}

Node* InitList(Node* node)
{
    node = (Node*)malloc(sizeof(Node));
    node->next=NULL;//初始化next指针为NULL
    if(node==NULL)
    {
        printf("内存分配失败");
        exit(0);
    }
    
    return node;
    
}

void head_insert(Node* node,int key)
{
    Node* temp=(Node*)malloc(sizeof(Node));
    //这个可以省略temp->next=NULL;
    if(temp==NULL)
    {
        printf("内存分配失败");
        exit(0);
    }
    
    //插入指针
    temp->data=key;
    temp->next=node->next;
    node->next=temp;
}

//删除
void delete(Node* head, int key)
{
    Node *temp=find(head,key);
    if(temp==NULL)
    {
        
    }
    else
    {
        Node* last=find_l(head,temp);
        last->next=temp->next;
        free(temp);
    }
    
}

//查找元素(下标返回型)
int index(Node* node,int key)
{
    //先判断
    if(node==NULL)
    {
        return -1;
    }
    Node* temp;
    int i=0;
    temp=node->next;
    while(temp!=NULL)
    {
        if(temp->data==key)
        {
            return i;
        }
        i++;
        temp=temp->next;
    }
    return -1;
}

//查找元素(指针返回型)
Node* find(Node* head,int key)
{
    
    Node *temp=head->next;
    if(temp==NULL)
    {
        return NULL;
    }
    
    while(temp!=NULL)
    {
        if(temp->data==key)
        {
            return temp;
        }
        temp=temp->next;
    }
    
    return NULL;
}

Node *find_l(Node* head,Node *aim)
{
    Node* temp=head->next;
    while(temp->next!=aim)
    {
        temp=temp->next;
    }
    return temp;
}
发布于