本章节探究的内容：
1.数据结构
2.存储结构
3.算法、时间复杂度、空间复杂度
4.线性表-关于顺序存储的实现(增删改查)
5.线性表-关于链式(单链表)存储的设计(增删改查与头插法/尾插发)
一、数据结构的术语
- 数据：程序的操作对象，用于描述客观事物。
- 数据的特点：1.可以输入到计算机；2.可以被计算机处理。
- 数据项：是数据元素的其中一个特征。
- 数据元素：一个数据元素由若干数据项组成，饼是数据对象的基本单位。
- 数据对象：性质相同的数据元素的集合(类似于数组)。
// 声明一个结构体类型
#include <stdio.h>
struct Teacher { // 一种数据结构
char *name; // 数据项 - 名称
char *title; // 数据项 - 职称
int age; // 数据项 - 年龄
}
int main(int argc, const char * argv[]) {
struct Teacher t1; // 数据元素
struct Teacher tArray[10]; // 数据对象
t1.name = "安安"; // 数据项
t1.title = "老师"; // 数据项
t1.age = 18; // 数据项
}
- 结构：数据元素之间并不是独立的，存在特定的关系，这些关系即为结构。
- 数据结构：指的是数据对象中的数据元素之间的关系。
二、存储结构：逻辑结构与物理结构
存储结构就是设计出数据与数据之间存在的关系，以什么方式存储到内存中去。
看存储结构有两个视角：逻辑结构(关系) 与 物理结构(方式)
1.逻辑结构
a.集合结构
集合结构描述的是 数据与数据之间的逻辑关系。
-
集合结构：所有的数据都在一个集合里面，数据之间是平等的无序的。
b.线性结构
-
线性结构：数据与数据之间的关系：一对一的关系。所有符合一对一的关系都是线性结构。
（如：线性表、队列、栈、字符串、数组等等，其中队列和栈是特殊的线性结构，特殊在读取方式：先进先出/先进后出；其中字符串是特别的线性结构，特别在只能存储字符串）
c.树形结构
-
树形结构：数据与数据之间的关系：一对多的关系。所有符合一对多的关系都是树形结构。
（如：二叉树、B树、B+树、B-树、多路树、哈夫曼树、红黑树、平衡二叉树等等）
d.图形结构
-
图形结构：数据与数据之间的关系：多对多的关系。所有符合多对多的关系都是图形结构。
（如：邻接矩阵、邻接表等等）
2.物理结构
物理结构：所有的数据都需要被存储到内存中去。无论是什么逻辑结构都需要存储到物理内存中去的。
-
顺序存储结构：需要提前开辟一片连续的内存空间
优点：查询数据很快
缺点：插入数据很慢
-
链式存储结构：不需要提前开辟连续的内存空间
优点：插入数据很慢
缺点：查询数据很快
三、算法
-
算法：解决特定问题求解步骤的描述。在计算机中表现为指令的有限序列，并且每个指令表示一个或多个操作。 -
算法特性：1.输入输出；2.有穷性；3.确定性；4.可行性。 -
设计算法要求：1.正确性；2.可读性；3.健壮性；4.时间效率高和存储量低。
1.时间复杂度
时间复杂度的构成：1.算法输入；2.编译可执行代码；3.执行指令；4.执行重复指令
时间复杂度计算
-
大O表示法规则：
1.用常数1来取代运行时间中所有常数； 如：4->1 O(1)
2.在修改运行次数函数中，只保留最高阶项；如：n3+2n2+5 -> O(n^3)
3.如果在最高阶存在且不等于1，则去除这个项目相乘的常数。如：2n^3 -> n^3 -
时间复杂度常用术语
1.常数阶
2.线性阶
3.平方阶
4.对数阶
5.立方阶
6.nlog阶
7.指数阶(不考虑) O(2^n)或者O(n!) 除非非常小的n，否则会造成噩梦般的时间消耗，这是一种不切实际的算法时间复杂度，一般不考虑！
- 常数阶 时间复杂度计算
// 1+1+1 = 3 => O(1)
void testSum1(int n) {
int sum = 0; // 执行1次
sum = (1+n)*n/2; // 执行1次
printf("testSum1:%d\n",sum); // 执行1次
}
// 1+1+1+1+1+1+1 = 7 => O(1)
void testSum2(int n) {
int sum = 0; // 执行1次
sum = (1+n)*n/2; // 执行1次
sum = (1+n)*n/2; // 执行1次
sum = (1+n)*n/2; // 执行1次
sum = (1+n)*n/2; // 执行1次
sum = (1+n)*n/2; // 执行1次
printf("testSum2:%d\n",sum); // 执行1次
}
- 线性阶 时间复杂度计算
// x=x+1; 执行n次 => O(n)
void add(int x, int n) {
for(int i = 0; i < n; i++) {
x = x + 1;
}
}
// 1+(n+1)+n+1 = 2n+3 => O(n)
void add2(int n) {
int i, sum = 0; // 执行1次
for(i = 1; i <= n; i++) { // 执行n+1次
sum += i; // 执行n次
}
printf("add2:%d\n",sum); // 执行1次
}
- 对数阶 时间复杂度计算
// 2的x次方等于n x = log2n => O(logn)
void test(int n) {
int count = 1; // 执行1次
while(count < n) {
count = count * 2;
}
}
- 平方阶 时间复杂度计算
// x=x+1; 执行了 n*n 次 => O(n^2)
void test1(int x, int n) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
x = x + 1;
}
}
}
// n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2+n/2 => O(n^2)
// sn = n(a1+an)/2
void test2(int n) {
int sum = 0;
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
sum += j;
}
}
printf("test2:%d\n",sum);
/**
内循环执行次数
i = 0; n
i = 1; n-1
i = 2; n-2
... 等差数列（公式：sn = n(a1+an)/2）
*/
}
// 1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n => O(n^2)
void test3(int n) {
int i, j, x = 0, sum = 0; // 执行一次
for(i = 1; i <= n; i++) { // 执行n+1次
for(j = 1; j <=n; j++) { // 执行n(n+1)次
x++; // 执行n*n次
sum = sum + x; // 执行n*n次
}
}
}
- 立方阶 时间复杂度计算
// O(n^3)
void test4(int n) {
int sum = 1;
for(int i = 0; i < n; i++) { // 执行n次
for(int j = 0; j < n; j++) { // 执行n*n次
for(int k = 0; k < n; k++) { // 执行n*n*n次
sum = sum * 2;
}
}
}
}
2.空间复杂度
空间复杂度：通过计算算法所需的存储空间实现。
算法空间复杂度的计算公式：S(n)=n(f(n)) 。
(n为问题的规模，f(n)为语句关于n所占存储空间的函数)
程序空间计算因素：1.寄存本身的指令；2.常数；3.变量；4.输入；5.对数据进行操作的辅助空间
在求算法的空间复杂度主要考虑：算法执行时所需要的辅助空间。
void swapArray() {
// 这两个不算在辅助空间里
int n = 10;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
// 算法实现1 => O(1)
int temp; // 一个临时变量
for(int i = 0; i < n/2; i++) {
temp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}
// 算法实现2 => O(n)
int b[10] = {0}; // 开辟了n个空间去存
for(int i = 0; i < n; i++) {
b[i] = a[n-i-1];
}
for(int i = 0; i < n; i++) {
a[i] = b[i];
}
}
四、线性表
线性表中数据元素之间的关系是一对一的逻辑结构关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的，注意：这句话只适用大部分线性表，而不是全部。比如，循环链表 逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。
对于非空的线性表和线性结构，特点如下：
- 存在唯一的被称作“第一个”的数据元素；
- 存在唯一的被称作“最后一个”的数据元素；
- 除了第一个之外，结构中的每个元素均有一个前驱；
- 除了最后一个之外，结构中的每个元素均有一个后继。
1.线性表-关于顺序存储的设计
线性表->顺序存储（逻辑相邻、物理存储地址相邻）
#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 1
typedef int ElementType;
typedef int Status;
typedef struct {
ElementType *data;
int length;
}sqlist;
// 1，初始化
Status InitList(sqlist *L) {
L->data = malloc(sizeof(ElementType) * MAXSIZE);
if(!L->data) return ERROR;
L->length = 0;
return OK;
}
// 遍历线性表
Status TraverseList(sqlist L) {
int i;
for (i = 0; i < L.length; i++) {
printf("%d\n", L.data[i]);
}
printf("\n");
return OK;
}
// 插入：
// 1. 位置是否合法
// 2.找到位置，进行位移，修改length
Status ListInsert(sqlist *L, int i ,ElementType e) {
// i值是否合法
if ((i < 1) || (i > L->length+1)) return ERROR;
// 存储空间已满
if (L->length == MAXSIZE) return ERROR;
// 插入数据不在表尾，则先移动出空余位置
if (i <= L->length) {
for (int j = L->length-1; j >= i-1; j--) {
// 插入位置以及之后的位置后移动1位
L->data[j+1] = L->data[j];
}
}
// 将新元素e，放在i的位置上
L->data[i-1] = e;
// 长度+1
++L->length;
return OK;
}
// 删除
// 1.顺序线性表L已存在 1<=i<=ListLength(L)
// 删除L的第i个元素，L的长度-1
Status ListDelete(sqlist *L, int i) {
// 线性表为空
if (L->length == 0) return ERROR;
// i值是否合法
if ((i < 1) || (i > L->length+1)) return ERROR;
for (int j = i; j < L->length; j++) {
// 被删除元素之后的元素向前移动
L->data[j-1] = L->data[j];
}
// 长度-1
L->length--;
return OK;
}
// 查
ElementType ListCheck(sqlist *L, int i) {
// 线性表为空
if (L->length == 0) return ERROR;
// i值是否合法
if ((i < 1) || (i > L->length+1)) return ERROR;
return L->data[i];
}
// 清空循序表
Status ListClear(sqlist *L) {
L->length = 0;
return OK;
}
2.线性表-关于链式(单链表)存储的设计
单链表的线性表的特点：
1.首指针；
2.数据+指针=节点；
3.尾节点的指针为空；
4.节点的指针指向下一个节点;
5.存储地址不需要相邻。
注意：首指针可以指向首元结点也可以头结点。
头结点它只是一个链表开头的标志，它不存放任何数据。
为什么首指针设计出指向头结点呢？
1.便于首元结点处理；2.便于空表和非空表的统一处理。
插入链表
删除链表
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElementType;/* ElemType类型根据实际情况而定，这里假设为int */
// 定义链表节点
typedef struct Node{
ElementType data; // 数据域
struct Node *next; // 指针域
}Node;
typedef struct Node *LinkList;
// 1.初始化
Status InitList(LinkList *L) {
// *L 首地址
*L = (LinkList)malloc(sizeof(Node));// 头结点
if (*L == NULL) return ERROR;
(*L)->next = NULL; // 空表的头结点的指针域为NULL
return OK;
}
// 2.遍历单链表
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status TraverseList(LinkList L) {
LinkList node = L->next; // 取出头结点
while(node)
{
printf("%d ",node->data); // 打印数据域
node = node->next; // 并获取下一个节点
}
printf("\n");
return OK;
}
// 3.单链表插入
Status InsertList(LinkList *L, int i, ElementType e) {
int j; // 记录遍历到第几个节点
LinkList p, s; // p:遍历到i的前一个节点，s:创建新节点
p = *L;
j = 1;
// 查找到需要插入的位置的那个节点
while (p && j<i) {
p = p->next;
++j;
}
if (!p || j>i) return ERROR;
// 创建新的节点
s = (LinkList)malloc(sizeof(Node));
s->data = e;
// 插入
s->next = p->next; // p->next 就是下一个节点，让s的指针域去指向
p->next = s; // 当前的节点指针域去指向s节点
return OK;
}
// 4.单链表取值
Status GetElement(LinkList L, int i, ElementType *e){
int j; // 记录遍历到第几个节点
LinkList p; // p:遍历到i的前一个节点
//将结点p 指向链表L的第一个结点;
p = L->next;
//j计算=1
j = 1;
//p不为空,且计算j不等于i,则循环继续
while (p && j<i) {
//p指向下一个结点
p = p->next;
++j;
}
//如果p为空或者j>i,则返回error
if(!p || j > i) return ERROR;
// e = p 所指的结点的data
*e = p->data;
return OK;
}
// 5.单链表删除
Status DeleteList(LinkList *L, int i, ElementType *e) {
int j; // 记录遍历到第几个节点
LinkList p, q; // p:遍历到i的前一个节点，q:保存要删除的节点，因为它的next需要被p的指针去指向
//将结点p 指向链表L的第一个结点;
p = (*L)->next;
//j计算=1
j = 1;
//查找第i-1个结点,p指向该结点(将p定位到i的前一个节点)
while (p->next && j<(i-1)) {
p = p->next;
++j;
}
//当i>n 或者 i<1 时,删除位置不合理
if(!(p->next) || (j>i-1)) return ERROR;
// q指向要删除的节点
q = p->next;
// 将p的next指向q的后继节点
p->next = q->next;
// 将q的数据域赋值给e
*e = q->data;
// 释放q
free(q);
return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL; /* 头结点指针域为空 */
return OK;
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
// 这两种创建方式都是等价的
// LinkList L1;
// struct Node *L2;
// L1 = (LinkList)malloc(sizeof(Node));
// L2 = (LinkList)malloc(sizeof(Node));
// L1->data = 1;
// L2->data = 2;
// printf("%d,%d\n", L1->data, L2->data);
Status iStatus;
LinkList L1,L;
struct Node *L2;
ElementType e;
//2.1 单链表初始化
iStatus = InitList(&L);
printf("L 是否初始化成功?(0:失败,1:成功) %d\n",iStatus);
//2.2 单链表插入数据
for(int j=1; j<=10; j++) {
iStatus = InsertList(&L, 1, j);
}
printf("插入后：");
TraverseList(L);
//2.3 删除第5个元素
iStatus = DeleteList(&L, 5, &e);
printf("被删除的第5个元素的值为：%d\n", e);
printf("删除后：");
TraverseList(L);
// 头插法
CreateListHead(&L1, 20);
printf("前插法：\n");
TraverseList(L1);
// 尾插法
CreateListTail(&L1, 20);
printf("尾插法：\n");
TraverseList(L1);
return 0;
}
头插法
// 头插法
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));
p->data = i; // 这里只做随意的数据演示
p->next = (*L)->next;
(*L)->next = p;
}
}
尾插法
// 尾插法
void CreateListTail(LinkList *L, int n) {
LinkList p, r; // p: 要插入的节点；r:记录最后一个节点
// 创建一个带头结点的单链表
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for (int i = 0; i < n; i++) {
// 创建节点
p = (LinkList)malloc(sizeof(Node));
p->data = i;
r->next = p;
r = p;
}
r->next = NULL; //注意：最后一个节点r->next要指向null
}
网友评论