嵌入式学习--线性表Day01

顺序表、单向链表、单向循环链表、双向链表、双向循环链表、顺序栈、链式栈、循环队列（顺序队列）、链式队列

1）逻辑结构：线性结构

2）存储结构：顺序、链式

3）特点：一对一，每一个节点最多有一个前驱和一个后继，首节点无前驱，尾节点无后继

顺序表

特点：内存连续（数组）

1）逻辑结构 ： 线性结构

2）存储结构： 顺序存储结构

3）操作 ：增删改查

1.1数组的插入、删除操作

函数名命名规则：

下滑线法：create_empty_seqlist

小驼峰法：createEmptySeqList

大驼峰法：CreateEmptySeqList

练习：

int a[100]={1,2,3,4,5,6,7,8};

//1)向数组的第几个位置插入数据

int *p //保存的数组的首地址

int n//n代表的是数组中有效的元素个数（非数组的长度size 100）8

int post;//位置 代表的是第几个位置，数组元素下标 位置的编号从0开始 position

int data;//插入到数组中的数据

void insertIntoA (int *p,int post,int data,int n)

{

//1.将n-1位置到post位置的数据整体向后移动一位

//2.将新数据data赋值到post位置

}

//删除数组指定位置的数据

void deleteFromA(int *p, int n, int post)

{

//1.将post+1位置----》n-1位置所有数据整体向前移动一个位置，覆盖删除

}

arr.c

#include <stdio.h>
//1)向数组的第几个位置插入数据
void insertIntoA(int *p, int post, int data, int n)
{
    int i;
    // 1.将n-1位置到post位置的数据整体向后移动一位
    for(i=n-1;i>=post;i--)
        p[i+1]=p[i];
    // 2.将新数据data赋值到post位置
    p[post] = data;
}
// 2）删除数组指定位置的数据
void deleteFromA(int *p, int n, int post)
{
    int i;
    // 1.将post+1位置----》n-1位置所有数据整体向前移动一个位置，覆盖删除
    for(i=post+1;i<=n-1;i++)
        p[i-1]=p[i];
}
//3)遍历输出A
void showA(int *p,int n)
{
    for(int i=0;i<n;i++)
        printf("%d ",p[i]);
    printf("\n");
}

int main(int argc, char const *argv[])
{
    int a[100] = {1, 2, 3, 4, 5, 6, 7, 8};
    showA(a,8);
    insertIntoA(a,2,300,8);
    showA(a,9);
    deleteFromA(a,9,2);
    showA(a,8);
    return 0;
}

1.2修改为last版本

#include <stdio.h>
int last = 7;//n-1，最后一个有效元素下标

//1)向数组的第几个位置插入数据
void insertIntoA(int *p, int post, int data)
{
    int i;
    // 1.将last位置到post位置的数据整体向后移动一位
    for(i=last;i>=post;i--)
        p[i+1]=p[i];
    // 2.将新数据data赋值到post位置
    p[post] = data;
    //3. 最后一个有效元素下标+1
    last++;
}
// 2）删除数组指定位置的数据
void deleteFromA(int *p,int post)
{
    int i;
    // 1.将post+1位置----》last位置所有数据整体向前移动一个位置，覆盖删除
    for(i=post+1;i<=last;i++)
        p[i-1]=p[i];
    //2. 最后一个有效元素下标-1
    last--;
}
//3)遍历输出A
void showA(int *p)
{
    for(int i=0;i<=last;i++)
        printf("%d ",p[i]);
    printf("\n");
}

int main(int argc, char const *argv[])
{
    int a[100] = {1, 2, 3, 4, 5, 6, 7, 8};
    showA(a);
    insertIntoA(a,2,300);
    showA(a);
    deleteFromA(a,2);
    showA(a);
    return 0;
}

1.3顺序表相关操作

#ifndef _SEQLIST_H__
#define _SEQLIST_H__
#include <stdio.h>
#include <stdlib.h>

#define N 5
typedef struct seq
{
    int data[N];
    int last;
}seqlist_t;

//1.创建一个空的顺序表
seqlist_t *CreateEpSeqlist();//返回的是申请空间的首地址
//2.向顺序表的指定位置插入数据
int InsertIntoSeqlist(seqlist_t *p, int post,int data);//post第几个位置，data插入的数据
//3.遍历顺序表sequence 顺序 list 表
void ShowSeqlist(seqlist_t *p);
//4.判断顺序表是否为满,满返回１ 未满返回０
int IsFullSeqlist(seqlist_t *p);
//5.判断顺序表是否为空
int IsEpSeqlist(seqlist_t *p);
//6.删除顺序表中指定位置的数据post删除位置
int DeletePostSeqlist(seqlist_t *p, int post);
//7.清空顺序表
void ClearSeqList(seqlist_t *p);
//8.修改指定位置的数据
int ChangePostSeqList(seqlist_t *p,int post,int data);//post被修改的位置，data修改成的数据
//9.查找指定数据出现的位置
int SearchDataSeqList(seqlist_t *p,int data);//data代表被查找的数据


#endif

#include "seqlist.h"
// 1.创建一个空的顺序表
seqlist_t *CreateEpSeqlist() // 返回的是申请空间的首地址
{
    // 1.开辟一个结构体大小的空间
    seqlist_t *p = (seqlist_t *)malloc(sizeof(seqlist_t));
    if (NULL == p)
    {
        perror("p malloc err");
        return NULL;
    }
    // 2.对last初始化
    p->last = -1;
    return p;
}
// 4.判断顺序表是否为满,满返回１ 未满返回０
int IsFullSeqlist(seqlist_t *p)
{
    return p->last + 1 == N;
}
// 2.向顺序表的指定位置插入数据
int InsertIntoSeqlist(seqlist_t *p, int post, int data) // post第几个位置，data插入的数据
{
    // 0.容错判断
    if (post < 0 || post > p->last + 1 || IsFullSeqlist(p))
    {
        perror("InsertIntoSeqlist err ");
        return -1;
    }
    // 1.将last----post整体向后移动一个位置
    for (int i = p->last; i >= post; i--)
        p->data[i + 1] = p->data[i];
    // 2.将data插入到post位置
    p->data[post] = data;
    // 3.last++
    p->last++;
    return 0;
}
// 3.遍历顺序表sequence 顺序 list 表
void ShowSeqlist(seqlist_t *p)
{
    for (int i = 0; i <= p->last; i++)
        printf("%d ", p->data[i]);
    printf("\n");
}
//5.判断顺序表是否为空
int IsEpSeqlist(seqlist_t *p)
{
    return p->last == -1;
}
// 6.删除顺序表中指定位置的数据post删除位置
int DeletePostSeqlist(seqlist_t *p, int post)
{
    // 0.容错判断
    if(post < 0 || post > p->last || IsEpSeqlist(p))
    {
        perror("DeletePostSeqlist err");
        return -1;
    }
    // 1.将post+1位置----》last位置所有数据整体向前移动一个位置，覆盖删除
    for (int i = post + 1; i <= p->last; i++)
        p->data[i - 1] = p->data[i];
    // 2.最后一个有效元素下标--
    p->last--;
    return 0;
}
//7.清空顺序表
void ClearSeqList(seqlist_t *p)
{
    p->last = -1;
}
//8.修改指定位置的数据
int ChangePostSeqList(seqlist_t *p,int post,int data)//post被修改的位置，data修改成的数据
{
    //0.容错判断
    if(post < 0 || post > p->last || IsEpSeqlist(p))
    {
        perror("ChangePostSeqList err");
        return -1;
    }
    //1.修改数据
    p->data[post] = data;
    return 0;
}
//9.查找指定数据出现的位置
int SearchDataSeqList(seqlist_t *p,int data)//data代表被查找的数据
{
    for(int i=0;i<=p->last;i++)
        if(p->data[i]==data)
            return i;
    return -1;
}

#include"seqlist.h"
int main(int argc, char const *argv[])
{
    seqlist_t * p = CreateEpSeqlist();
    for(int i=0;i<N;i++)
        InsertIntoSeqlist(p,i,i+1);
    ShowSeqlist(p);//1 2 3 4 5
    DeletePostSeqlist(p,0);
    ShowSeqlist(p);//2 3 4 5
    ChangePostSeqList(p,0,200);
    ShowSeqlist(p);//200 3 4 5
    printf("%d post is %d\n",200,SearchDataSeqList(p,200));
    ClearSeqList(p);
    if(IsEpSeqlist(p))
        printf("IsEpSeqlist!!!\n");
    free(p);
    p=NULL;
    return 0;
}

CC=gcc
CFLAGS=-c -g -Wall
OBJS=main.o seqlist.o 

seqlist:$(OBJS)
	$(CC) $^ -o $@
%.o:%.c 
	$(CC) $(CFLAGS) $< -o $@

.PHONY:clean
clean:
	$(RM) *.o seqlist