Day1-顺序表

1. 数据结构-基本概念

数据之间的相互关系，包括三种关系：逻辑结构：表示数据元素之间的抽象关系(如邻接关系、从属关系等)。有四种基本的逻辑结构：集合结构、线性结构、树形结构、图状结构存储结构：数据的逻辑结构在计算机内的存储形式分为顺序存储结构、链接存储结构、索引存储结构、散列存储结构数据运算：对数据进行的操作：如插入、删除、查找、排序等。

2. 数据结构-算法

算法：解决特定问题的步骤的描述，在计算机中算法是一个有穷规则(或语句、指令)的有序集合。它确定一解决某一问题的一个运算序列。对于问题的初始输入，通过算法有限步，产生一个或多个输出。算法是解决问题的思想方法程序是计算机语言的具体实现算法的特性：有穷性、确定性、可行性、输入、一个或多个输出

3. 数据结构-线性表

线性表的基本运算：建立一个空表：CreateList(L)置空表：ClearList(L)判断表是否为空：EmptyList(L)若表为空，返回值为True(或1),否则返回false(或0)求表长：Length(L)求表中某个元素：GetList(L,i)定位运算：Locate(L,x)插入：Insert(L,x,i)删除：Delete(L,i)另外还有合并、拆分、复制、排序和遍历等复杂的运算

4. 顺序表的实现一

/*seqlist.h头文件*/
/************************* 创建线性表   reate_seqlist()* 释放线性表   clear_seqlist()* 判断线性表是否为空  is_empty_seqlist()* 判断线性表是否为满  is_full_seqlist()* 设置为空     set_empty_seqlist()* 获取线性表的长度    get_length_seqlist()* 显示线性表内所有有效元素   show_seqlist()** 加入数据    insert_seqlist()* 删除数据    delete_seqlist()* 修改数据    change_seqlist()* 查找数据    search_seqlist()* */
#ifndef __SEQLIST_H__
#define __SEQLIST_H__
​
#define MAXSIZE 100
typedef int data_t;                                     
typedef struct {data_t data[MAXSIZE];int last;
}seqlist_t;
​
seqlist_t *reate_seqlist(void);
void clear_seqlist(seqlist_t *L);
​
int is_empty_seqlist(seqlist_t *L);
int is_full_seqlist(seqlist_t *L);
void set_empty_seqlist(seqlist_t *L);
int get_length_seqlist(seqlist_t *L);
void show_seqlist(seqlist_t *L);
​
int insert_seqlist(seqlist_t *L,data_t x,int pos);
int delete_seqlist(seqlist_t *L,int pos);
int change_seqlist(seqlist_t *L,data_t x,int pos);
int search_seqlist(seqlist_t *L,data_t x);
​
#endif

/*seqlist.c 函数具体实现文件*/
#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"
​
​
seqlist_t *reate_seqlist(void)
{seqlist_t *L=NULL;L = (seqlist_t *)malloc(sizeof(seqlist_t));if(L == NULL){puts("no memory");return NULL;}L->last = -1;return L;
}
void clear_seqlist(seqlist_t *L){if(L == NULL){puts("seqlist_t *L is NULL");return ;}free(L);return ;
}
​
int is_empty_seqlist(seqlist_t *L)
{if(L == NULL){puts("seqlist_t *L is NULL");return -1;}return (L->last == -1);
}
int is_full_seqlist(seqlist_t *L)
{if(L == NULL){puts("seqlist_t *L is NULL");return -1;}return (L->last == MAXSIZE-1);
}
void set_empty_seqlist(seqlist_t *L)
{if(L == NULL){puts("seqlist_t *L is NULL");return ;}L->last = -1;return ;
}
int get_length_seqlist(seqlist_t *L){if(L == NULL){puts("seqlist_t *L is NULL");return -1;}return (L->last + 1);
}
void show_seqlist(seqlist_t *L)
{int i = 0;if(L == NULL){puts("seqlist_t *L is NULL");return ;}for(i=0;i<=L->last;i++)printf("L->data[%d] = %d\n",i,L->data[i]);return ;
}
​
int insert_seqlist(seqlist_t *L,data_t x,int pos)
{int i=0;if(is_full_seqlist(L) || (pos<0) || pos>L->last+1){puts("input argv is invalid");return -1;}for(i=L->last;i>=pos;i--)L->data[i+1] = L->data[i];L->data[pos] = x;L->last++;return 0;
}
int delete_seqlist(seqlist_t *L,int pos)
{int i = 0;if((pos<0)||(pos>L->last)){puts("input post is invalid");return -1;}for(i=pos;i<get_length_seqlist(L);i++)L->data[i] = L->data[i+1];L->last--;return 0;
}
int change_seqlist(seqlist_t *L,data_t x,int pos)
{if((pos<0)||(pos>L->last)){puts("input pos is invalid");return -1;}L->data[pos] = x;return 0;
}
int search_seqlist(seqlist_t *L,data_t x)
{int i = 0;for(i=0;i<L->last;i++){if(L->data[i] == x)return i;}return -1;
}
​

/*Makefile 工程管理文件*/
CC = gcc
CFLAGS = -oo -g -Wall
​
test:test.c seqlist.c$(CC) $(CFLAGS) -o $@ $^
.PHONY:clean
clean:rm -rf test

/*test.c 测试文件*/
#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"
​
int main(int argc,const char *argv[])
{int i=0;seqlist_t *L=NULL;L = reate_seqlist();for(i=0;i<=4;i++)insert_seqlist(L,i,0);printf("seqlist L length is %d\n",get_length_seqlist(L));show_seqlist(L);puts("=================================================");puts("search data = 3");printf("data = 3 pos is %d\n",search_seqlist(L,3));printf("seqlist L length is %d\n",get_length_seqlist(L));show_seqlist(L);puts("=================================================");puts("search data = 3");delete_seqlist(L,search_seqlist(L,3));printf("data = 3 pos is %d\n",search_seqlist(L,3));show_seqlist(L);puts("=================================================");puts("clear data[2] = 99");change_seqlist(L,99,2);printf("seqlist L length is %d\n",get_length_seqlist(L));show_seqlist(L);puts("=================================================");​
​clear_seqlist(L);
​
​return 0;
}
​
/*测试结果：
seqlist L length is 5
L->data[0] = 4
L->data[1] = 3
L->data[2] = 2
L->data[3] = 1
L->data[4] = 0
=================================================
search data = 3
data = 3 pos is 1
seqlist L length is 5
L->data[0] = 4
L->data[1] = 3
L->data[2] = 2
L->data[3] = 1
L->data[4] = 0
=================================================
search data = 3
data = 3 pos is -1
L->data[0] = 4
L->data[1] = 2
L->data[2] = 1
L->data[3] = 0
=================================================
clear data[2] = 99
seqlist L length is 4
L->data[0] = 4
L->data[1] = 2
L->data[2] = 99
L->data[3] = 0
=================================================
*/