数据结构学习——1
一、概述
数据：数据是承载信息的载体； 数据结构：指数据之间的相互关系
逻辑结构：表示数据运算之间的抽象关系(如邻接关系、从属关系等)，按每个元素可能具有的直接前趋数和直接后继数将逻辑结构分为“线性结构”和“非线性结构”两大类。
存储结构：逻辑结构在计算机中的具体实现方法，分为顺序存储方法、链接存储方法、索引存储万法、散列存储方法。
数据运算：对数据进行的操作，如插入、删除、查找、排序等。
线性结构：1:1 非线性结构：1：N || N:M
程序：由数据结构+算法组成
算法：是-一个有穷规则(或语包.指令)的有序集合。
算法设计：取决于选定的逻辑结构
算法实现：依赖于采用的存储结构
- 有穷性 算法执行的步骤(或规则)是有限的;
- 确定性 每 个计算步骤无_二义性;
- 可行性 个计算步骤能够在有限的时间内完成;
- 输入 算法有零 个或多个外部输入;
- 输出 算法有一个或多个输出。
时间复杂度：算法消耗时间的复杂度；(语句的频度)
空间复杂度计算：所有代码的频率加起来，去掉非最高次幂项，再去掉最高次幂项的系数。
空间复杂度：所开辟空间的消耗量
二、顺序表
顺序表的构成
- 需要用数组(连续空间)来存放数据(任意类型)
- 需要一个表示来表示数组的使用情况
- (可选)需要一个标识来记录表的大小
顺序表结构体
#define MAX 20
struct Seqlist
{
int data[MAX];
int last;
}
memset
void *memset(void *s, int c, size_t n);
功能：设置一片内存空间(批量更改内容)
返回值：设置成功返回设置好的内存地址
参数列表：
s: 要设置的空间的首地址
c: 设置的值
n: 设置的空间大小
错误提示
perror("错误信息1");
底行命令分屏
:vsp 文件名
作业：顺序表实现
main.c
/*===============================================
* 文件名称：main.c
* 创 建 者：甘子煜
* 创建日期：2025年07月25日
* 描 述：
================================================*/
#include <stdio.h>
#include "seqList.h"
int main(int argc, char *argv[])
{
seqlist_t *sq = seqlist_init();
seqlist_t **distroy = &sq;
data_t data;
int index;
if(sq != NULL)
{
printf("MSG : 顺序表初始化成功!\n");
}
else
{
printf("顺序表初始化失败!\n");
return 0;
}
printf("----------菜单----------\n");
printf("选项如下:\n");
printf("1.插入到表尾\n");
printf("2.插入到指定位置\n");
printf("3.删除指定位置元素\n");
printf("4.清空表\n");
printf("5.遍历\n");
printf("6.退出\n");
while(1)
{
char menu;
printf(">:");
scanf("%c",&menu);
if(menu == '6')
break;
switch(menu)
{
case '1':
printf("输入插入值:");
scanf("%d",&data);
if(seqlist_insertAtLast(sq,data))
printf("MSG ：插入成功\n");
else
printf("MSG : 插入失败\n");
break;
case '2':
printf("输入插入值 位置:");
scanf("%d %d",&data,&index);
if(seqlist_insert(sq,data,index))
printf("MSG : 插入成功\n");
else
printf("MSG : 插入失败\n");
break;
case '3':
printf("输入位置:");
scanf("%d",&index);
if(seqlist_delete(sq,index))
printf("MSG : 删除成功\n");
else
printf("MSG : 删除失败\n");
break;
case '4':
seqlist_clear(sq);
if(seqlist_empty(sq))
printf("MSG : 表已清空\n");
else
printf("MSG : 清空失败\n");
break;
case '5':
if(!seqlist_print(sq))
printf("MSG : 表为空\n");
break;
}
printf("----------分割----------\n");
getchar();
}
seqlist_distroy(distroy);
printf("退出成功,顺序表以销毁！\n");
return 0;
}
seqlist.c
/*===============================================
* 文件名称：seqList.c
* 创 建 者：甘子煜(青木莲华)
* 创建日期：2025年07月25日
* 描 述：顺序表实现
================================================*/
#include <stdio.h>
#include "seqList.h"
//初始化创建
seqlist_t *seqlist_init()
{
seqlist_t *sq = (seqlist_t *)malloc(sizeof(seqlist_t));
if(sq == NULL)
{
perror("malloc_1");
return NULL;
}
//memset(sq->data,0,sizeof(sq->data));
sq->last = -1;
return sq;
}
//销毁
void seqlist_distroy(seqlist_t **sq)
{
if(*sq == NULL)
return;
free(*sq);
*sq = NULL;
}
/**
判空函数
返回类型：int类型
返回值1：1 表示表为空
返回值2：0 表示表不为空
*/
int seqlist_empty(seqlist_t *sq)
{
if(sq->last == -1)
return 1;
return 0;
}
/**
判满函数
返回类型：int类型
返回值1：1 表示表满
返回值2：0 表示表未满
*/
int seqlist_full(seqlist_t *sq)
{
if(sq->last == MAXLEN - 1)
return 1;
return 0;
}
//清空
void seqlist_clear(seqlist_t *sq)
{
sq->last = -1;
}
/*
插入到指定位置
参数1：顺序表首地址
参数2：数据
数据3：插入位置下标
返回值1：1 表示插入成功
返回值2：0 表示插入失败
*/
int seqlist_insert(seqlist_t *sq,data_t data,int index)
{
//先判断表满
if(seqlist_full(sq))
return 0;
//判断插入位置是否合法
if(index < 0 || index > sq->last)
return 0;
//表为空且插入位置为0
if(seqlist_empty(sq) && index == 0)
{
sq->data[index] = data;
sq->last += 1;
}
for(int i = sq->last + 1 ; i > index ; i--)
sq->data[i] = sq->data[i-1];
sq->data[index] = data;
sq->last += 1;
return 1;
}
/*
直接插入到末尾
返回值1：1 插入成功
返回值2：0 插入失败
*/
int seqlist_insertAtLast(seqlist_t *sq,data_t data)
{
//判满
if(seqlist_full(sq))
return 0;
sq->data[sq->last + 1] = data;
sq->last += 1;
return 1;
}
/*
删除指定位置的数
参数 index ：删除的元素位置
返回值1 ：1 删除成功
返回值2 ：0 删除失败
*/
int seqlist_delete(seqlist_t *sq,int index)
{
//判断空
if(seqlist_empty(sq))
return 0;
//判断位置合法
if(index < 0 || index > sq->last)
return 0;
for(int i = index ; i < sq->last ; i++)
sq->data[i] = sq->data[i + 1];
sq->last -= 1;
return 1;
}
//遍历
int seqlist_print(seqlist_t *sq)
{
//判空
if(seqlist_empty(sq))
return 0;
int count = 0;
while(count <= sq->last)
{
printf("sq[%d]%d\t",count,sq->data[count]);
count++;
}
printf("\n");
return 1;
}
seqlist.h
/*===============================================
* 文件名称：seqList.h
* 创 建 者：甘子煜
* 创建日期：2025年07月25日
* 描 述：
================================================*/
#ifndef _SEQLIST_H_
#define _SEQLIST_H_
#define MAXLEN 20
#include <stdlib.h>
typedef int data_t;
typedef struct
{
data_t data[MAXLEN];
int last;
}seqlist_t;
//初始化创建
seqlist_t *seqlist_init();
//销毁
void seqlist_distroy(seqlist_t **sq);
//判空
int seqlist_empty(seqlist_t *sq);
//判满
int seqlist_full(seqlist_t *sq);
//清空
void seqlist_clear(seqlist_t *sq);
//插入到指定位置
int seqlist_insert(seqlist_t *sq,data_t data,int index);
//直接插入到末尾
int seqlist_insertAtLast(seqlist_t *sq,data_t data);
//删除
int seqlist_delete(seqlist_t *sq,int index);
//遍历
int seqlist_print(seqlist_t *sq);
#endif
京公网安备 11010502036488号