一、基本概念
1、数据结构核心名词解释
1）数据：程序的操作对象，用于描述客观事物。特点，可以输入到计算机并可以被计算机处理。
2）数据元素：组成数据的对象的基本单位。
3）数据项：一个数据元素由若干数据项组成。
4）数据对象：性质相同的数据元素的集合（类似与组成）。
5）数据结构：指的数据对象中的数据元素之间的关系。
6）数据类型：指一组性质相同值的集合以及定义在此集合的一些操作的总称
struct Teacher{ //一种数据结构
char *name; //数据项--名字
char *title; //数据项--标题
int age; //数据项--年龄
};
int main(int argc, const char * argv[]) {
struct Teacher t1; //数据元素;
struct Teacher tArray[10]; //数据对象;
t1.age = 18; //数据项
t1.name = "Janice"; //数据项
t1.title = "潇潇暮雨"; //数据项
return 0;
}
2、数据结构 - 逻辑结构
3、数据结构 - 物理结构
4、数据结构 - 算法定义
算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列列, 并且每个指令表示⼀一个或多个操作.
5、数据结构 - 算法特性
1）输⼊入输出
2）有穷性
3）确定性
4）可⾏行行性
6、数据结构 - 算法设计要求
1）正确性
2）可读性
3）健壮性
4）时间效率⾼高和储存量量低
二、复杂度计算
1、时间复杂度
1）大 O 表示法：
a、用常数 1 取代运行时间中所有常数。如，3->O(1)
b、在修改运行次数函数中，只保留最高阶。如，n^3+2n^2+5 -> O(n^3)
3)如果在最高阶存在且不等于1，则去除这个项目相乘的常数。如，2n^3 -> n^3
2）时间复杂度术语：
a、常数阶
b、线性阶
c、平方阶
d、对数阶
e、立方阶
f、nlog阶
g、指数阶(不考虑) O(2^n)或者O(n!) 除非是非常小的n,否则会造成噩梦般的时间消耗. 这是一种不切实际的算法时间复杂度. 一般不考虑!
3）例子
a、常数阶时间复杂度计算
void testSum1(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
sum += (1+n)*n/2; //执行1次
printf("testSum1:%d\n",sum);//执行1次
}
testSum1 时间负责度为：1 + 1 + 1 + 1 = 4 ，O(1)
b、线性阶时间复杂度计算
void testSum3(int n){
int i,sum = 0; //执行1次
for (i = 1; i <= n; i++) { //执行n+1次
sum += i; //执行n次
}
printf("testSum3:%d\n",sum); //执行1次
}
testSum3 时间复杂度为：1 + (n + 1) + n + 1 = 2n + 2 = n, O(n)
c、平方阶时间复杂度计算
void add3(int x,int n){
for (int i = 0; i< n; i++) { //执行n + 1次
for (int j = 0; j < n ; j++) { //执行n*(n + 1) 次
x=x+1; //执行n * n次
}
}
}
add3 的时间复杂度为：(n + 1) + n * (n + 1) + n * n = 2n^2 + 2n + 1, O(n^2)
void testSum4(int n){
int sum = 0; //执行 1 次
for(int i = 0; i < n;i++) //执行 n + 1 次
for (int j = i; j < n; j++) {//执行(n - 0) + (n - 1)... + 1
sum += j; //执行 n * [(n - 0) + (n - 1)... + 1]
}
printf("textSum4:%d",sum); //执行 1 次
}
testSum4 的时间复杂度为 ： n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
d、对数阶时间复杂度计算
void testA(int n){
int x = 1; //执行1次
while (x < n) {
x = x * 2;
}
}
testA 时间复杂度为：2^x = n, 也就是 log2n, 0(logn)
e、立方阶时间复杂度计算
void testB(int n){
int sum = 1; //执行1次
for (int i = 0; i < n; i++) { //执行n + 1次
for (int j = 0 ; j < n; j++) { //执行n*(n + 1)次
for (int k = 0; k < n; k++) {//执行n*n*(n + 1)次
sum = sum * 2; //执行n*n*n次
}
}
}
}
testB 的时间复杂度为：1 + (n + 1) + (n*(n + 1)) + (nn(n + 1)) + (nnn) = n^3, O(n^3)
2、空间复杂度
1）程序空间计算因素:
a、寄存本身的指令
b、常量
c、变量
d、输入
e、对数据进行操作的辅助空间
在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间.
空间复杂度计算：通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记做：S(n) = n(f(n)), 其中，n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数。
2）例子
数组逆序,将一维数组a中的n个数逆序存放在原数组中.
void changeNumberFun1(int *a，int n) {
int temp;
for(int i = 0; i < n/2 ; i++){
temp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}
for(int i = 0;i < 10;i++)
{
printf("%d\n",a[i]);
}
changeNumberFun1 空间复杂度为：O(1)
void changeNumberFun2(int *a，int n) {
int b[10] = {0};
for(int i = 0; i < n;i++){
b[i] = a[n-i-1];
}
for(int i = 0; i < n; i++){
a[i] = b[i];
}
for(int i = 0;i < 10;i++)
{
printf("%d\n",a[i]);
}
changeNumberFun2 空间复杂度为：O(n)
三、线性结构使用顺序表的方式存储
1）顺序表结构设计
#define MAXSIZE 50
#define OK 1
#define ERROR 0
//元素类型
typedef int Element;
//函数类型
typedef int ret;
//顺序表结构
typedef struct {
Element *elem;
int length;
}Sqlist;
2)线性表初始化
ret initList(Sqlist *L) {
//给线性表申请大小为 MAXSIZE 的数组空间
L->elem = malloc(sizeof(Element) * MAXSIZE);
//若分配失败即返回 0
if (!L->elem) exit(ERROR);
//空表长度为0
L->length = 0;
return OK;
}
3)顺序表的插入
/*
初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
*/
ret listInsert(Sqlist *l, int loc ,Element e) {
//i值不合法判断
if((loc < 1) || (loc > (l->length + 1))) return ERROR;
//存储空间已满
if (l->length == MAXSIZE) return ERROR;
//判断插入数据是否在表尾，不在则先移动出空余位置
if (loc <= l->length) {
//从 loc 位置开始往后移一位
for (int i = l->length - 1, i >= loc, loc--) {
l->elem[i+1] = l->elem[i];
}
}
//将新元素插入 loc 位置上
l->ele[loc] = e;
//长度 +1
++l->length;
return YES;
}
4)顺序表的取值
ret getElem(Sqlist l, int loc ,Element *e) {
//判断要取的位置是否合理
if(loc > l->length || loc < 1) return ERROR;
//elem[loc-1]单元存储第i个数据元素.
*e = l.elem[loc-1]
return YES;
}
5)顺序表删除
/*
初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
操作结果: 删除L的第i个数据元素,L的长度减1
*/
ret listDelete(Sqlist *l, int loc) {
//线性表为空
if(l->length == 0) return ERROR;
//loc值不合法判断，如，a[] = @{1,2,3},此时length = 3，如果loc = 4，可以插入，但是 loc = 5，则会出现异常
if(loc<1 || loc>l->length + 1) return ERROR;
for(int i = loc; i < l->length; ++i) {
//被删除元素之后的元素向前移动
l->elem[i-1] = i->[i];
}
//表长度-1;
l->length --;
return OK;
}
6)清空顺序表
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
ret clearList(Sqlist *l) {
l->length=0;
return OK;
}
7)判断顺序表清空
ret isEmptyOfList(Sqlist *l) {
ifif(L.length==0)
return YES;
else
return FALSE;
}
8)获取顺序表长度ListEmpty元素个数
int listLength(Sqlist l)
{
return l.length;
}
9)顺序输出List
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 *
ret printList(Sqlist l) {
for (int i = 0; i < l.length; ++i) {
printf("%d\n",L.elem[i]);
printf("\n");
return OK;
}
10)顺序表查找元素并返回位置
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
ret LocateElem(Sqlist l,Element e) {
int i = 0
if(l->length == 0) return ERROR;
for(i = 0; i < l.length; i++) {
if(l->elem[i] == e)
break;
}
return i + 1;
}
四、线性结构使用链表的方式存储
1）链式表结构设计
#define MAXSIZE 50
#define OK 1
#define ERROR 0
//元素类型
typedef int Element;
//函数类型
typedef int ret;
//定义
typedef struct Node{
Element data;
struct Node *next; //指针域
}Node;
typedef struct Node * LinkList;
2）初始化单链表线性表
ret initList(LinkList *l) {
//产生头结点,并使用L指向此头结点
*l = (LinkList)malloc(sizeof(Node));
//存储空间失败
if(*l == NULL) return ERROR;
//将头结点的指针域置空
(*l)->next = NULL;
return OK;
}
3)单链表插入
/*
初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
操作结果：在L中第i个位置之后插入新的数据元素e，L的长度加1;
*/
ret listInsert(LinkList *l, int loc, Element elem) {
int j;
LinkList p,s;
p = *l;
j = 1
//寻找第loc-1个结点
while(p && j<loc) {
p = p->next; //保存loc-1结点的data
++j
}
//第i个元素不存在
if (!p || j > loc) return ERROR;
//生成新结点s
s = (LinkList)malloc(sizeof(Note));
//将elem赋值给s的数值域
s->elem = elem;
//将p的后继结点赋值给s的后继
s->next = p->next;
//将s赋值给p的后继
p->next = s;
return OK;
}
4）单链表取值
/*
初始条件: 顺序线性表L已存在,1≤i≤ListLength(L);
操作结果：用e返回L中第loc个数据元素的值
*/
ret getElem(LinkList l, int loc, Element *elem) {
int j; //计数
LinkList p; //声明结点 p
//将结点 p 指向链表 l 的第一个结点
p = l->next
j = 1
//p不为空,且计算j不等于loc,则循环继续
while(p && j<loc) {
//p 指向下一个结点
p = p->next;
++j;
}
//如果 p 为空或者j>loc,则返回 ERROR
if (!P || j > loc) return ERROR;
//e = p所指的结点的data
*e = p->data;
return OK;
}
5)单链表删除元素
/*
初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
操作结果：删除L的第loc个数据元素，并用e返回其值，L的长度减1
*/
ret listDelete(LinkList *l, int loc, Element *elem) {
int j; //计数
LinkList p,q
p = (*l)->next;
j = 1;
//查找第loc-1个结点,p指向该结点,j<(loc-1)：是要知道指向被删位置的前一个位置
while (p->next && j<(loc-1)) {
p = p -> next;
++j;
}
//当 p 不存在或者 loc<1 时,删除位置不合理
if(!(p->next) || (j > loc - 1)) return ERROR;
//q指向要删除的结点
q = p -> next;
//将q的后继赋值给p的后继
p->next = q->next;
//将q结点中的数据给e
*e = q->data;
//让系统回收此结点,释放内存;
free(q);
return OK;
}
6)顺序输出List
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
ret listTraverse(LinkList l) {
LinkList p = l->next;
while(p) {
printf("%d\n",p->data);
p = p->next;
}
printf("\n");
return OK;
}
7)清空表
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
ret clearList(LinkList *l) {
LinkList p,q;
p = (*l)->next; //p指向第一个结点
while(p) {
q = p->next;
free(p);
p = q;
}
(*l)->next = NULL; //头结点指针域为空
return OK;
}
8)单链表前插入法
/* 随机产生n个元素值,建立带表头结点的单链线性表L(前插法)*/
void createListHead(LinkList *L, int n) {
LinkList p;
//建立一个带头结点的单链表
*l = (LinkList)malloc(sizeof(Node));
(*l)->next = NULL;
//循环前插入随机数据
for (int i = 0; i < n; i++) {
//生成新结点
p = (LinkList)malloc(sizeof(Node));
//i赋值给新结点的data
p->data = i;
p->next = (*l)->next
//将结点p插入到头结点之后;
(*l)->next = p;
}
}
9）单链表后插入法
/* 随机产生n个元素值,建立带表头结点的单链线性表L(后插法)*/
void createListTail(LinkList *L, int n) {
LinkList p,r;
*l = (LinkList)malloc(sizeof(Node));
//r指向尾部的结点
r = *L;
for(int i = 0; i<n; i++) {
//生成新结点
p = (Node *)malloc(sizeof(Node));
p->data = i;
//将表尾终端结点的指针指向新结点
r->next = p;
//将当期的新结点定义为表尾终端结点
r = p;
}
//将尾指针的next = null
r->next = NULL;
}
总结：
链表结构与顺序存储结构优缺点对⽐
存储分配⽅方式：
1）顺序存储结构⽤用⽤用⼀一段连续的存储单元依次存储线性表的数据元素;
2）单链表采⽤用链式存储结构,⽤用⼀一组任意的存储单元存放线性表的元素;
时间性能：
1）查找
a、顺序存储 O(1)
b、单链表O(n)
2）插⼊入和删除
a、存储结构需要平均移动⼀一个表⻓长⼀一半的元素,时间O(n)
b、单链表查找某位置后的指针后,插⼊入和删除为 O(1)
空间性能：
1）顺序存储结构需要预先分配存储空间,分太⼤大,浪费空间;分⼩小了了,发⽣生上溢出;
2）单链表不不需要分配存储空间,只要有就可以分配, 元素个数也不不受限制;
