数据结构

逻辑结构

数据对象中数据元素之间的关系。分为集合结构、线性结构、树形结构、图形结构。

物理结构

数据的逻辑结构在计算机中的存储形式。

分为顺序存储和链式存储。

算法

五个特性：输入、输出、有穷性、确定性和可行性

算法设计的要求：正确性、可读性、健壮性、时间效率高和存储量低

算法效率的估算：程序在计算机上运行时所消耗的时间取决于（1）算法采用的方法（程序）（2）编译产生的代码质量（编译软件）（3）输入问题的规模（4）机器执行指令的速度（硬件）

算法时间复杂度

一般用大O（）表示O(1)是常数阶、O（n）是线性阶、O(n^2)是平方阶……

推导大O阶的方法：用常数1 代替运行时间中所有加法常数，在修改后 的运行次数函数中，只保留最高阶项。如果最高项存在且不是1，则除去与这个数相乘的常数得到的结果就是大O阶。

常见的时间复杂度：

算法的空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公 式记作: S(n)= O(f(n)), 其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

通常复杂度问题还是指时间复杂度。

线性表

顺序存储用一维数组来表示：

顺序表的定义、插入和删除：

typedef struct { datatype data[max]; int len; }SepList; SepList *Init() { SepList *L; L=(Seplist)malloc(sizeof(SepList)); if(L) { L->len=-1; return L; } else { return -1; } } SepList Insert(SepList *L,int i,Data X) { int j; if(L->len=max-1) { return -1;//表满 } else { for(j=L->len;j>=i;j--) { L->data[j+1]=data[j]; } data[i]=x; L->len++; } } SepList Delete(SepList *L,int i) { int j; if(i<1||i>L->len) { return -1; } else { for(j=i+1;j<L->len;j++) { L->data[j-1]=L->data[j]; } L->len--; } }

链表：

typedef struct node { datatype data; struct node *next; } LNode，*Linklist； //头插法 Linklist Insert() { int x; Linklist L=null;//L是单链表 LNode *s; while(x) { s=(LNode *)malloc(sizeof(LNode)); s->data=x; s->next=L; L=s; scanf("%d",x); } return L; } //尾插法 Linklist Insert2() { int x; Linklist L=null; LNode *s; while(x) { s=(LNode *)malloc(sizeof(LNode)); s->data=x; if(L==null) L=s; L->next=s; L=s; scanf("%d",&x); } if(L!=null) { L->next=null; } } //删除算法 int Delete(Linklist L,int i) { Linklist p,s; p=getlist(L,i-1); if(p==null||p->next==null) { return -1; } s=p->next; p->next=s->next; free(s); }

栈先入后出，在表尾插入和删除

把允许插入和删除的一端称为栈顶（top），另一端称为栈底。

typedef struct { Elemtype data[max]; int top; }Sqstack; //进栈 int Push(Sqstack *s,Elentype e) { if(s->top==max-1)//栈满 { return 0; } s->top++; s->data[s->top]=e; return 1; } //出栈 int Pop(Sqstack *s,Elemtype e) { if(s->top==-1) { return 0; } e=s->data[s->top]; s->top--; }

队列

队列是一种只在一端进行插入，只在另一端删除的线性表。先进先出