静态顺序表

程序员文章站 2022-05-08 09:22:18

...

顺序表是一个线性表，它是由一段连续的存储单元来依次存储数据元素的线性结构。
静态顺序表

下面是代码和一些难点解释

.h文件

#pragma once

#ifndef _Seqlist_H_
#define _Seqlist_H_

#include <tchar.h>
#define MAX 10
typedef int Typedata;

typedef struct Seqlist
{
    size_t size;
    Typedata arr[MAX];
}Seq;

void test(Seq* p);
void Init_Seqlist(Seq* pSeq);//初始化
void PushBack_Seqlist(Seq* pSeq, Typedata data);//尾插
void PopBack_Seqlist(Seq* pSeq);//尾删
int Empty(Seq* pSeq);//判空
void PushFront_Seqlist(Seq* pSeq, Typedata data);//头插
void PopFront_Seqlist(Seq* pSeq);//头删
void EraseInser_Seqlist(Seq* pSeq, int pos, Typedata data);//任意位置插入
void ErasePop_Seqlist(Seq* pSeq, int pos);//任意位置删除
int Search_Seqlist(Seq* pSeq, Typedata data);//在顺序表中查找
void Del_FirstData(Seq* pSeq, Typedata data);//删除第一个值为data的数据
void Del_AllData(Seq* pSeq, Typedata data);//删除所有值为data的数据
void Sort_Seqlist(Seq* pSeq);//排序(选择排序)

#endif//_Seqlist_H_

.c文件

#include"Seqlist.h"
#include<stdio.h>
#include<assert.h>

//初始化
void Init_Seqlist(Seq *pSeq)
{
    assert(pSeq);
    pSeq->size = 0;
}

void PushBack_Seqlist(Seq* pSeq, Typedata data)//尾插
{
    assert(pSeq);
    if (pSeq->size >= MAX){
        printf("Full of Seqlist \n");
        return;
    }
    pSeq->arr[pSeq->size] = data;
    pSeq->size++;
}

int Empty_Seqlist(Seq* pSeq)//判空
{
    assert(pSeq);
    return pSeq->size == 0;
}

void PopBack_Seqlist(Seq* pSeq)//尾删
{
    int i = 0;
    assert(pSeq);
    if (Empty_Seqlist(pSeq)){
        printf("Seqlist is empty!\n");
        return;
    }
    pSeq->size--;
}

void PushFront_Seqlist(Seq* pSeq, Typedata data)//头插
{
    int i = 0;
    assert(pSeq);
    i = pSeq->size;
    if (pSeq->size >= MAX){
        printf("Full of Seqlist \n");
        return;
    }

    for (i; i >= 0; --i)
        pSeq->arr[i - 1] = pSeq->arr[i];
    pSeq->arr[0] = data;
    pSeq->size++;
}

void PopFront_Seqlist(Seq* pSeq)//头删
{
    assert(pSeq);
    if (Empty_Seqlist(pSeq)){
        printf("Seqlist is empty!\n");
        return;
    }

    for (size_t i = 1; i < pSeq->size; ++i)
        pSeq->arr[i - 1] = pSeq->arr[i];
    pSeq->size--;
}

void EraseInser_Seqlist(Seq* pSeq, int pos, Typedata data)//任意位置插入
{
    assert(pSeq);
    int i = pSeq->size;//必须要在断言之后，因为断言前还不知道结构体存不存在
    if (pSeq->size >= MAX){
        printf("Full of Seqlist \n");   
        return;
    }
    if ((pos >= pSeq->size) || (pos < 0)){
        printf("wrong pos\n");
        return;
    }


    for (i; i >= pos; --i)
        pSeq->arr[i] = pSeq->arr[i - 1];//搬移元素
    pSeq->arr[pos] = data;//将data插入到要插入的位置

    pSeq->size++;
}

void ErasePop_Seqlist(Seq* pSeq, int pos)//任意位置删除
{
    assert(pSeq);
    int i = pos;
    if (Empty_Seqlist(pSeq)){
        printf("Seqlist is empty!\n");
        return;
    }
    if ((pos >= pSeq->size) || (pos < 0)){
        printf("wrong pos\n");
        return;
    }

    for (i; i < pSeq->size; ++i)
        pSeq->arr[i] = pSeq->arr[i+1];//搬移元素

    pSeq->size--;
}

int Search_Seqlist(Seq* pSeq, Typedata data)///查询
{
    assert(pSeq);
    size_t i = 0;
    while (i < pSeq->size){
        if (pSeq->arr[i] == data)
            return i;
        ++i;
    }
    return -1;
}

void Del_FirstData(Seq* pSeq, Typedata data)//删除第一个为data的值
{
    ErasePop_Seqlist(pSeq, Search_Seqlist(pSeq, data));
}

void Del_AllData(Seq* pSeq, Typedata data)//删除所有值为data的数据
{
    assert(pSeq);
    int i = 0;
    int count = 0;
    for (i; i < pSeq->size; ++i){
        if (pSeq->arr[i] != data)
            //如有连续count个值为data的数据，则将后面不为data的数往前移count位，一次性删除
            pSeq->arr[i - count] = pSeq->arr[i];
        else
            count++;
    }
    pSeq->size - count;
}

void Sort_Seqlist(Seq* pSeq)//排序(选择排序)
{
    assert(pSeq);

    int begin = 0;
    int end = pSeq->size - 1;//设置前后两个标签，分别指向最前面和最后的值

    while (begin < end)
    {
        int MaxPos = begin;
        int MinPos = begin;
        int i = begin + 1;
        while (i < end)
        {
            if (pSeq->arr[i]>pSeq->arr[MaxPos])
                MaxPos = i;
            if (pSeq->arr[i] < pSeq->arr[MinPos])
                MinPos = i;
            ++i;
        }
        if (MaxPos != end){            //将最大值放到最后
            Typedata temp = pSeq->arr[end];
            pSeq->arr[end] = pSeq->arr[MaxPos];
            pSeq->arr[MaxPos] = temp;
        }
        if (MinPos != begin){         //将最小的值放到最前
            Typedata temp = pSeq->arr[begin];
            pSeq->arr[begin] = pSeq->arr[MinPos];
            pSeq->arr[MinPos] = temp;
        }

        ++begin;//begin标签往后移
        --end;//end标签往前移
    }
}

void test(Seq* p)
{
    Init_Seqlist(p);
    PushBack_Seqlist(p, 6);
    PushBack_Seqlist(p, 1);
    PushBack_Seqlist(p, 2);
    PushBack_Seqlist(p, 2);
    PushBack_Seqlist(p, 4);
    PushBack_Seqlist(p, 7);
    PushBack_Seqlist(p, 3);
/*  
    PushBack_Seqlist(p, 7);
    PushBack_Seqlist(p, 9);
    PushBack_Seqlist(p, 10);
    PushBack_Seqlist(p, 11);//尾插直到此行结束
    PopBack_Seqlist(p);
    PopBack_Seqlist(p);
    PopBack_Seqlist(p);
    PopBack_Seqlist(p);//尾删到此行结束
    PushFront_Seqlist(p, 1);
    PushFront_Seqlist(p, 2);
    PushFront_Seqlist(p, 3);
    PushFront_Seqlist(p, 4);
    PushFront_Seqlist(p, 5);//头插到此行结束
    PopFront_Seqlist(p);
    PopFront_Seqlist(p);
    PopFront_Seqlist(p);//头删到此结束   
    EraseInser_Seqlist(p, 3, 6);
    EraseInser_Seqlist(p, 2, 8);
    EraseInser_Seqlist(p, 5, 0);
    EraseInser_Seqlist(p, 12, 1);//任意位置插入到此行结束
    ErasePop_Seqlist(p, 7);
    ErasePop_Seqlist(p, 0);
    ErasePop_Seqlist(p, 4); //任意位置删除到此行结束
    int Pos_Seachr = Search_Seqlist(p, 4); //查询
    Del_FirstData(p, 2);//删除第一个值为data的数据
    Del_AllData(p, 2);//删除所有为data的值       
    */
    Sort_Seqlist(p);//排序
}
int main()
{
    Seq seqlist;
    Seq* pseq = &seqlist;

    test(pseq);
    return 0;
}

静态顺序表

此处删除所有元素为data的数据用的是上图中c方法；a方法时间复杂度太大；b方法利用空间换时间，不太理想；c方法相对前两个方法来说比较巧妙。

以下是解析排序：

“`
void Sort_Seqlist(Seq* pSeq)//排序(选择排序)
{
assert(pSeq);

int begin = 0;
int end = pSeq->size - 1;//设置前后两个标签，分别指向最前面和最后的值

while (begin < end)
{
    int MaxPos = begin;
    int MinPos = begin;
    int i = begin + 1;
    while (i < end)
    {
        if (pSeq->arr[i]>pSeq->arr[MaxPos])
            MaxPos = i;
        if (pSeq->arr[i] < pSeq->arr[MinPos])
            MinPos = i;
        ++i;
    }
    if (MaxPos != end){            //将最大值放到最后
        Typedata temp = pSeq->arr[end];
        pSeq->arr[end] = pSeq->arr[MaxPos];
        pSeq->arr[MaxPos] = temp;
    }
    if (MinPos != begin){         //将最小的值放到最前
        Typedata temp = pSeq->arr[begin];
        pSeq->arr[begin] = pSeq->arr[MinPos];
        pSeq->arr[MinPos] = temp;
    }

    ++begin;//begin标签往后移
    --end;//end标签往前移
}

}
“` 静态顺序表

静态顺序表

利用.htaccess的Rewrite规则实现Discuz论坛的伪静态链接

每日学习心得：SQL查询表的行列转换/小计/统计（with rollup，with cube，pivot解析）

学生表/教师表/课程表/成绩表常见SQL查询

删除一个表中的重复数据同时保留第一次插入那一条以及sql优化

zabbix进行数据库备份以及表分区的方法

MySQL 5.7双主同步部分表的实现过程详解

详解MySQL导出指定表中的数据的实例

MySQL实现快速删除所有表而不删除数据库的方法

详解mysql中的静态变量的作用

浅谈Spring Security 对于静态资源的拦截与放行