1.数据结构

1.概念

程序 ==数据结构 + 算法

• 描述数据存储和操作的结构

• 操作数据对象的方法

2.衡量代码质量和效率

在理想情况下，无论代码操作数据量多大，都希望程序代码的运行时间保持恒定。

因此，当代码操作数据量增大的时候，代码运行时间增速缓慢就表明代码的质量和效率高，为了衡量这种数据量和时间的关系，引入时间复杂度和空间复杂度的概念

1.时间复杂度

数据量的增长与程序运行时间的增长所呈现的比例关系就称为时间渐进复杂度函数，也就是时间复杂度

• 常见的时间复杂度：
  • O(1)：程序运行时间维持恒定
  • O(n)：数据量和运行时间关系为线性
  • O(logn)：数据量少时运行时间增长较快，数据量大时运行时间趋于稳定
  • O(nlogn)，O(n^2),O(n3),O(2^n)……

2.空间复杂度

数据的增长与程序占据空间的增长所呈现的比例函数关系，称为空间复杂度

3.数据结构分类

1.逻辑结构

• 线性结构：表(一对一)
• 非线性结构：树(一对多)、图(多对多)

2.存储结构

• 顺序存储
• 链式存储
• 散列存储
• 索引存储

3.常见的数据结构

• 顺序表、链式表
• 顺序栈、链式栈
• 顺序队列、链式队列
• 二叉树、邻接表、邻接矩阵

2.链表

1.与顺序表的区别

• 顺序表（数组）特点：
  • 存储空间连续，访问元素方便
  • 无法利用小的空间，空间必须连续
  • 顺序表元素必须有限
  • 插入和删除效率低
• 链表特点：
  • 存储空间可以不连续，访问元素不方便
  • 可以利用一些小的存储空间
  • 链表元素可以没有上限
  • 插入和删除效率高

2.链表分类

1.单向链表

只能通过链表节点找到后一个节点，访问链表元素的方向是单向的

1.定义链表节点类型

代码实现：

typedef int datatype;/*链表节点类型*/
typedef struct node {datatype data;          // 数据域,存放数据struct node *pnext;     // 指针域，指向下一个节点
} linknode;

2.空链表的创建

• 创建一个空的链表节点
• data不需要赋值，空白节点不存放数据，主要为了保证链表操作的便利性
• pnext必须赋值为NULL，表示该节点为最后一个节点
• 将节点地址返回

代码实现：

linknode *create_empty_linklist(void){linknode *ptmpnode = NULL;ptmpnode = malloc(sizeof(linknode));if(ptmpnode == NULL){printf("filed to malloc");return NULL;}ptmpnode->pnext = NULL;return ptmpnode;
}

3.链表的头插法

• 申请新的节点空间
• 将想要存放的数据存放到新申请的数据控件中
• 将新申请节点的pnext赋值为空白节点的pnext
• 将空白节点的pnext赋值为新申请节点

代码实现：

int insert_head_linklist(linknode *phead,datatype tmpdata){linknode *ptmpnode = NULL;ptmpnode = malloc(sizeof(linknode));ptmpnode->data = tmpdata;ptmpnode->pnext = phead->pnext;phead->pnext = ptmpnode;return 0;
}

4.链表的遍历

代码实现：

方法一：while(p != NULL){p = p->pnext;}	//多用于遍历链表所有元素
方法二：while(p->next != NULL){p = p->next;}	//多用于找出链表的最后一个节点
void show_linklist(linknode *phead){linknode *ptmpnode = NULL;ptmpnode = phead->pnext;while(ptmpnode != NULL){printf("%d ",ptmpnode->data);ptmpnode = ptmpnode->pnext;}printf("\n");return 0;
}

5.链表元素删除

• 定义两个指针ptmpnode,pprenode,ptmpnode用来遍历链表查找要删除的元素，pprenode永远指向ptmpnode的前一个节点
• 当ptmpnode找到要删除的节点元素，让pprenode->pnext赋值为ptmpnode ->ptext
• 将要删除的元素释放，再将ptmpnode赋值为pprenode->pnext
• 让ptmpnode判断下一节点元素是否删除,直到该指针指向NULL为止

代码实现：

int delete_linklist(linknode *phead,datatype tmpdata){linknode *ptmpnode = NULL;linknode *pprenode = NULL;pprenode = phead;ptmpnode = phead->pnext;while(ptmpnode != NULL){if(ptmpnode->data == tmpdata){pprenode->pnext = ptmpnode->pnext;free(ptmpnode);ptmpnode = pprenode->pnext;}else{ptmpnode = ptmpnode->pnext;pprenode = pprenode->pnext;}}retuen 0;
}

3.makefile

工程管理工具，主要用来管理代码的编译

• makefile可以根据文件中的规则来选择符合条件的代码完成编译
• makefile能够根据依赖关系来决定哪些代码需要编译，哪些代码不需要编译

使用规则：

• 在工程目录下，新建一个makefile文件
• 在makefile中编写对应的文件编译规则
• 在工程目录下使用make调用makefile中的规则完成代码编译
• 编译代码成功后即可运行可执行程序

语法规则：

要生成的文件:依赖的所有文件
生成命令方式

习题

1. 封装一个函数返回链表中第一个指定元素节点的地址

   代码实现：

   void search_linklist(linknode *phead, int tmpdata){linknode *ptmpnode = NULL;linknode *pprenode = NULL;ptmpnode = phead->pnext;pprenode = phead;while(ptmpnode != NULL){if(ptmpnode->data == tmpdata){printf("find it! %p\n", ptmpnode);return;}else{ptmpnode = ptmpnode->pnext;pprenode = pprenode->pnext;}}return;}
   

2. 封装一个函数将链表中指定元素的值更新为新值

代码实现：

void change_linklist(linknode *phead, int tmpdata,int overdata){linknode *ptmpnode = NULL;linknode *pprenode = NULL;ptmpnode = phead->pnext;pprenode = phead;while(ptmpnode != NULL){if(ptmpnode->data == tmpdata){ptmpnode->data = overdata;}ptmpnode = ptmpnode->pnext;pprenode = pprenode->pnext;}return;}

3. 封装一个函数实现尾插法

代码实现：

void insert_tail_linklist(linknode *phead,int tmpdata){linknode *ptmpnode = NULL;ptmpnode = phead->pnext;while(ptmpnode->pnext != NULL){ptmpnode = ptmpnode->pnext;}linknode *pnewnode = NULL;pnewnode = malloc(sizeof(linknode));ptmpnode->pnext = pnewnode;pnewnode->data = tmpdata;pnewnode->pnext = NULL;return;
}

LL){

       ptmpnode = ptmpnode->pnext;}linknode *pnewnode = NULL;pnewnode = malloc(sizeof(linknode));ptmpnode->pnext = pnewnode;pnewnode->data = tmpdata;pnewnode->pnext = NULL;return;

}