数据结构的定义 ：数据元素间的相互关系

(DS)

数据(Data)定义 ：即信息的载体(可以输入计算器且能被计算机识别，存储 和处理的符号总称)

数据元素定义 ：数据的基本元素(即记录)(若干基本项组(字段、数据结构)成)

数据类型定义 ：对元素取值范围与运算的限定

数据存储结构 ：

顺序存储 --将数据结构中的各元素按照其逻辑顺序存放在存储器 的一片连续的存储空间中

链式存储 --将数据结构中的各元素分布在存储器不同点，用地址或 链指针把他们联系起来的存储结构

索引存储 --在数据存储的同时建立一个附加索引表，：索引存储结构=数据文件+索引表

散列存储 --根据数据元素的关键字key计算存储地址然后数据元素按地址存放，的这种存储结构

p126页

数据结构类型

数据结构关系：

物理关系：顺序关系、链式关系

运算关系：增(加)，删(除)，改(修改)，查(询)，排(序)

逻辑关系：

(结构)

集合 ： 数据元素间除同属一集合无其他关系

线性： 线性(关系) ：一对一(如线性表、栈、队列)

非线性： 层次关系(树状结构) ：一对多

网状关系(图状结构) ：多对多

算法特性： (1)有穷性---算法执行的步骤或规则是有限的

(2)确定性---每个计算步骤无二义性

(3)可行性---每个计算步骤都能在有限时间内完成

(4)输入---算法有一个或多个输入

(5)输出---算法有一个或多个输出 p128页

评判算法好(坏)： 消耗时间少 、存储空间少，

易(理解 编程 调试 和维护)的程度，

问题规模(小)：(输入数据量的大小，用n表示)

算法消耗的时间复杂度 T(N)：(算法消耗的时间)

算法消耗的空间复杂度 D(N)：(算法消耗的空间)

语句频度： 可执行语句在算法(或程序)中重复执行的次数

(一条语句的时间复杂度=语句平度 *消耗时间) p129页

算法与程序的联系与区别：

共同点：二者皆为完成某个任务，或解决某个问题而编制的规则(或语句)的 有序集合

区别 ： 一，算法与计算机无关，但程序依赖于具体的计算机语言

二，算法必须有穷而程序可能无穷

三，算法可忽略一些语法细节问题，重点放在解决问题的思路上， 但程序必须严格按相应的语言工具的语法算法换成程序后才能在计算机上运行。

线性表： 是信息表的一种形式，数据元素间满足线性关系(或线性结构)

非空线性表的特征：

a0是表头无前驱

a(n-1)是表尾无后继

其他每个元素有且仅一个直接前驱a(i-1)和直接后继a(i+1)

(当关系表长n<=1时，关系集R为空)

创建Makefile 文件

test:main.c seqlist.c

gcc main.c seqlist.c -o test

创建shell 文件

#ifndef SEQLIST_H

#define SEQLIST_H

#include

#include

#include

typedef int data_t;

#define size 15

typedef struct node{

data_t data[size];

int last;

}seqlist;

//增,删,改,查,排序等

seqlist *create_list();

int insert_list(seqlist *l, int pos, data_t value);

int delte_list(seqlist *l, int pos);

int change_list(seqlist *l, int pos, data_t value);

data_t select_list(seqlist *l, int pos);

void printf_list(seqlist *l);

#endif

创建.c主程序文件

#include "seqlist.h"

#include

#include

#include

seqlist *create_list() //创建空表

{

seqlist *l; //创建链表指针

l = (seqlist *)malloc(sizeof(seqlist)); //开辟malloc空间并强转

if (l == NULL){ //判断是否为空，

return NULL;

}

memset(l->data, 0, 4*size); //把所有空间初始化为0，memset初始化的意思

l->last = -1;

return l;

}

int insert_list(seqlist *l, int pos, data_t value)//插入数据

{

if (l == NULL) //首先判断是否为空

return -1;

if (pos < 0 || pos > l->last + 1 || (l->last + 1 == size)) //判断插入位置是否有效，无效返回-1

return -1;

int i;

for(i = l->last; i >= pos; i--)

l->data[i+1] = l->data[i];

l->data[pos] = value;

l->last = l->last + 1;

return 0;

}

int delte_list(seqlist *l, int pos)//删除某一地址下的数据

{

if(l==NULL || l->last == -1 )//同样判断删除位置是否有效

return -1;

if(pos < 0 || pos>l->last+1)

return -1;

int i;

for(i=pos; ilast; i++)

l->data[i] = l->data[i+1];

l->last--;

return 0;}

int change_list(seqlist *l, int pos, data_t value)//更改

{if (l == NULL)

return -1;

if (pos < 0 || pos > l->last + 1 )

return -1;

int i;

for(i = pos; i < l->last; i++)

l->data[pos] = value;

return 0;

}

data_t select_list(seqlist *l, int pos)//查询

{if (l == NULL)

return -1;

else

return l->data[pos];

}

void printf_list(seqlist *l)//输出函数

{

int i = 0;

printf("seqlist : l->last = %d\n", l->last);

while(i <= l->last){

printf("----%d ", l->data[i]);

i++;

}

printf("\n");

}

创建主函数调用

#include "seqlist.h"

#include

#include

#include

void main()

{

seqlist *l = create_list();

if (l == NULL)

printf("create list failed\n");

insert_list(l, 0, 2);

insert_list(l, 1, 3);

insert_list(l, 2, 5);

insert_list(l, 3, 7);

insert_list(l, 4, 9);

printf_list(l);

insert_list(l, 2, 13);

printf_list(l);

delte_list(l,2);

printf_list(l);

change_list(l,3,666);

printf_list(l);

select_list(l,3);

printf_list(l);

}