数据结构

986244073 发表于 2019-1-7 17:17

本帖最后由 986244073 于 2019-1-7 17:18 编辑

# 绪论

> 程序=算法+数据结构

> 线性结构: 元素间存在一对一的线性关系
>
> 树形结构: 元素间存在一对多的层次关系
>
> 图结构: 元素间存在多对多的网状关系

> 数据(Data): 能输入到计算机并被计算机处理的符号总称。
>
> 例：公司每个部门通讯录总集
>
> 数据元素（Data Element）: **数据的基本单位**，通常也是程序处理的单位，用于描述一个对象。
>
> 例：具体某位员工的信息
>
> 数据项（Data Item）: 组成数据元素的有独立含义的、不可分割的最小单位。
>
> 例：具体某位员工信息中的电话号码
>
> 数据对象（Data Object）: 数据元素的集合，是数据的一个子集。
>
> 例：某部门员工信息集合

> 学生信息表
>
> 数据对象：整张表
>
> 数据元素：某位学生信息
>
> 数据项：某位学生的某项具体信息，比如姓名

!(https://upload-images.jianshu.io/upload_images/5862031-c49abc57dac1eed1.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

> 数据结构: 是相互之间存在一种或多种特定关系的数据元素的集合。

!(https://upload-images.jianshu.io/upload_images/5862031-8406c4f0a314e603.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

!(https://upload-images.jianshu.io/upload_images/5862031-d857e952de6f9070.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

!(https://upload-images.jianshu.io/upload_images/5862031-a5b81a1a20ca04f3.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

!(https://upload-images.jianshu.io/upload_images/5862031-f88b7d7e9c0992b3.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

!(https://upload-images.jianshu.io/upload_images/5862031-84f58f784b58506f.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

# 算法

> 定义 :为解决某类问题而规定的一个有限长的操作序列。

> 特性 :
>
> 有穷性: 在执行**有穷步**后结束每一步都在**有穷时间**内完成
>
> 确定性 : 每种情况下执行的操作有确切的含义，**无二义性**
>
> 可行性 : 所有操作都可以通过已经实现的基本操作运算执行有限次来实现
>
> 输入: 一个算法有零个或多个输入
>
> 输出:一个算法有一个或多个输出

> 设计要求
>
> 正确性 : 在合理的数据输入下，能够在有限的运行时间内得到正确的结果。
>
> 可读性 :便于理解和交流，易于调试和修改。
>
> 健壮性 : 当输入非法数据时，能适当地做出正确反应和相应处理。
>
> 通用性 : 执行效率高，占用存储容量合理

## 时间复杂度

> 时间复杂度主要是衡量算法执行时间的长短。
>
> 一个算法的时间复杂度大致上等于其所有语句执行次数的总和。

> T(n)= O(f(n))
>
> n: 问题规模
>
> f(n): 关于n的函数，表示算法中基本语句执行次数
>
> O(): 表示数量级

> O(1)< O(log2n)< O(n) < O(n2) < O(n3)

## 空间复杂度

> 除了需要存储程序本身所用的常数、变量等数据外，还需要堆数据进行操作的辅助存储空间。

> S(n)
> = O(f(n))

# 数组

## 数组的初始化

```c
int a = {1, 2, 3, 4, 5}; //如果初值表中的数据太多，产生语法错误（syntax error）

int a = {1};//剩下的元素的初值是 0

int a[ ] = {1, 2, 3, 4, 5};//数组的长度就是初值表中数值的个数

//int a = { };初值表不能为空
//没有初始化的数组，其元素的值不确定

```

## 把数组传递给函数

```c
#include <stdio.h>
void main() {
int array;
printf("array = %p\n&array = %p\n",array, &array);
}

```

## C 指向数组的指针

```c
#include <stdio.h>

int main ()
{
/* 带有 5 个元素的整型数组 */
double balance = {1000.0, 2.0, 3.4, 17.0, 50.0};
double *p;
int i;

p = balance;

/* 输出数组中每个元素的值 */
printf( "使用指针的数组值\n");
for ( i = 0; i < 5; i++ )
{
   printf("*(p + %d) : %f\n",i, *(p + i) );
}

printf( "使用 balance 作为地址的数组值\n");
for ( i = 0; i < 5; i++ )
{
   printf("*(balance + %d) : %f\n",i, *(balance + i) );
}

return 0;
}
```

## C 传递数组给函数

```c
void myFunction(int *param)
{
.
.
.
}

void myFunction(int param)
{
.
.
.
}

void myFunction(int param[])
{
.
.
.
}
```

## 二维数组

```c
int a = {
{0, 1, 2, 3} , /*初始化索引号为 0 的行 */
{4, 5, 6, 7} , /*初始化索引号为 1 的行 */
{8, 9, 10, 11} /*初始化索引号为 2 的行 */
};
```

给部分元素赋初值时，不指定第一维的长度，但要指定第二维的长度。

## 把二维数组传递给函数

```c
void exchange(int a[], int b[], int m, int n);
void main() {
…
exchange(a, b, 2, 3);
…
}

```

# 函数

## 实参和形参

```c
int max(int a, int b)//简称“形参”。只有在函数被调用、启动后，才临时为其分配存储单元，并接受主调函数传来的数据。

{ int c=a>=b?a:b;
return c;
}
main()
{ int a, b, c;//实参是函数调用时主调函数传送给被调函数的形式参数的实际值。实参可以是常量、变量和表达式。实参必须有确定的值。在函数调用结束后，形参所占存储单元被释放。

scanf(“%d%d”, &a, &b);
c=max(a, b);
}
/*实参与形参不共用存储单元。
参数传递时，把实参的值复制一份给形参。
形参值的变化不影响实参的值。
所以，形参和实参可以同名。
*/
```

# 结构体

结构体是派生的数据类型

```c
typedef struct Node {//struct：引入结构体定义。Node：结构体的名称，必须与 struct 一起使用。
int data;//数据域
struct Node *pNext;//指针域
} NODE, *PNODE;//NODE==struct Node*PNODE== struct Node *
//typedef为已经定义的数据类型创建一个别名。

```

结构体的成员可以是基本类型和构造类型（数组和其他结构体）。

结构体不能包含自身的实例。

但可以包含指向自身的指针。

## 定义声明结构体变量

```c
PNODE pHead = NULL;//struct Node * pHead =NULL;
```

## 初始化结构体变量

```c
//全部成员赋初值
struct StuRec {
int num;
char name;
struct date { int year,month,day; } birthday;
float score;
} student={101, “WangHai”, 1982, 5, 21, 80};

//部分
struct StuRec {
int num;
char name;
struct date { int year,month,day; } birthday;
float score;
} student={101, “WangHai”};

```

## 访问结构体成员的两种方式

```c
//结构体成员运算符：.
struct card myCard;
printf(“%s”, myCard.face);
//结构体指针运算符：->
struct card *cardPtr;
printf(“%s”, cardPtr->face);
//等价于 (*cardPtr).face

```

## 结构体数组

```c
struct student {
int num;
char name;
float scores;
};

struct student students;

```

# 指针

## 指针的概念

> 指针变量就是保存内存地址的变量。
>
> 内存对象包括：变量，数组，函数等。
>
> C语言允许直接通过地址来处理数据。

指针变量的定义和初始化

```c
int *x_pointer, *y_pointer;

char *charPtr;
int x, *p=(int *)0xffe;

```

指针运算符

取地址运算符：&

指针运算符：*

```c
int y, *yPtr;
y = 5;
yPtr = &y;

```

```c
#include <stdio.h>
void main() {
int a, *aPtr;
a = 7;
aPtr = &a;

printf("The address of a is %p"
      "\nThe value of aPtr is %p", &a, aPtr);
printf("\n\nThe value of a is %d"
      "\nThe value of *aPtr is %d", a, *aPtr);
printf("\n\nShowing that * and & are inverses of each other."
      "\n&*aPtr = %p"
      "\n*&aPtr = %p", &*aPtr, *&aPtr);
}

```

指针作为函数参数

```c
void swap(int *x, int *y) {
int tmp;
tmp=*x; *x=*y; *y=tmp;
}

void main() {
int a=4, b=6;
swap(&a, &b);
printf("a=%d,b=%d",a,b);
}

```

指针与数组

```c
int b;
int *bPtr;
bPtr = b;

//下标法
main() {
int i, a={1,2,3,4,5};
for (i=0; i<5; i++)
printf("%2d",a);
}

//地址法
main() {
int i, a={1,2,3,4,5};
for (i=0; i<5; i++)
printf("%2d",*(a+i));
}

//指针法
main() {
int a={1,2,3,4,5}, *p;
for (p=a; p<(a+5); p++)
printf("%2d",*p);
}

```

指针与字符串

程序设计举例

# 表

## 单链表

结构体指针的声明

```c
typedef struct student
{
int ID;
charname;
float score;
struct student* next; //指针，指向直接后继
}STUDENT;

//结构体变量：
STUDENTzs = {100,”zs”,96.0};
//结构体指针：
STUDENT * ptr = &zs;

//成员运算符”.”
zs.ID;
zs.name;
zs.score;
//成员运算符”->”
ptr->ID;
ptr->name;
ptr->score;
// 或者：
(*ptr).ID ; //相当于zs.ID

```

线性表的链式存储

```c
typedef struct student
{
int ID;
charname;
float score;
struct student* ptr; //指示下一位学生
}STUDENT;

```

链表的分类

> 单链表:每个结点中只包含一个指针域。
>
> 双向链:表每个结点中包含两个指针域，一个指向直接后继，另一个指向直接前驱。
>
> 循环链:表单链表中最后一个结点的指针域指向头结点，整个链表形成一个环。

头结点与首元结点

> 首元结点：链表中存储第一个数据元素的结点。

头结点：数据域可以不存储任何信息，指针域指向首元结点。

头指针：指向链表中第一个结点的指针。

思考：链表怎么判空？

顺序存储

n要找到第i个元素必须从头指针出发顺链表进行寻找。

```c
STUDENT * q = head;
while(q) q = q->next;

```

!(https://upload-images.jianshu.io/upload_images/5862031-114ff0036b2c868a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

### 单链表的初始化

!(https://upload-images.jianshu.io/upload_images/5862031-da45dea7f4ededbc.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

!(https://upload-images.jianshu.io/upload_images/5862031-37bd71931e47c004.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

!(https://upload-images.jianshu.io/upload_images/5862031-73394fedcfc9488a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

!(https://upload-images.jianshu.io/upload_images/5862031-cfbc35d21e5faaf7.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

```c
STU zs = {100,"张三",20};

PNODE pHead = (PNODE) malloc(sizeof(NODE));

```

```c
//定义结构体
typedef struct Student {
int ID;
char name;
int score;
struct Student *next;
} PSTU, STU;

//初始化创建头结点
PSTU Init() {
PSTU head = (PSTU) malloc(sizeof(STU));
head->next = NULL;
return head;
}

//前插法
void CreatList_H(PSTU head, int n) {
PSTU q = NULL;
printf("please input ID name score");
for (int i = 0; i < n; ++i) {
   //分配空间
   q = (PSTU) malloc(sizeof(STU));
   scanf("%d %s %d", &(q->ID), q->name, &(q->score));
   //核心代码
   q->next = head->next;
   head->next = q;
}
}

//后插法
void CreatList_R(PSTU head, int n) {
PSTU tail = head;
PSTU q = NULL;
printf("please input ID name score");
for (int i = 0; i < n; ++i) {
   q = (PSTU) malloc(sizeof(STU));

   scanf("%d %s %d", &(q->ID), q->name, &(q->score));
   q->next = NULL;
   tail->next = q;
   tail = q;
}
}
```

### 单链表的取值和查找

```c
//按节点查询
PSTU GetElement(PSTU head, int index) {
PSTU p = head->next;
int i = 1;
while (p && (i < index)) {
   p = p->next;
   i++;
}
return p;
}

//按Id查询
PSTU FindbyID(PSTU head, int ID) {
PSTU p = head->next;
while (p) {
   if (ID == p->ID) {
         break;
   }
   p = p->next;
}
return p;
}
```

### 单链表的插入和删除

!(https://upload-images.jianshu.io/upload_images/5862031-bcb13af1b4399275.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

!(https://upload-images.jianshu.io/upload_images/5862031-df725ca7db753554.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

```c
//插入新的节点
void Insert(PSTU head, int index) {
PSTU q = NULL;
PSTU p = head;
int i = 0;
while (p && (i < index - 1)) {
   printf("please input ID name score");
   q = (PSTU) malloc(sizeof(STU));
   scanf("%d %s %d", &(q->ID), q->name, &(q->score));
   p = p->next;
   i++;
}
q->next = p->next;
p->next = q;
}

//删除节点
void Delete(PSTU head, int index) {
PSTU p = head;
int i = 0;
while (p && (i < index - 1)) {
   p = p->next;
   i++;
}
PSTU q = p->next;
p->next = q->next;
free(q);
}
```

## 线性表

### 线性表插入

```c
// 线性表的插入操作是值在第i个位置插入新的元素，使长度为n的线性表变成长度为n+1的线性表。

void arr_insert(int *arr, int index, int value) {
int len = 15;
if (0 < index && index < len + 1) {//如果顺序表存储空间已满，则不能再插入元素，除非创建新的更大的数组并将数据迁移过去。

   for (int i = 15; i > index - 1; i--) {
         arr = arr;
   }
   arr = value;
   len++;//需从最后一个(第n个)元素开始，依次向后移动一个位置，直至第i个元素，共移动n-i+1个元素。

} else {
   printf("error");
exit(-1);
}
}
```

### 线性表删除

```c
//线性表的删除操作是指将第i个元素删去，使长度为n的线性表变成长度为n-1的线性表。
void arr_delete(int *arr, int index) {
//如果顺序表已空，则不能再删除元素。可删除元素范围1 ≤i ≤n

for (int i = index-1; i <15; ++i) {
   arr = arr;
   //需将第i+1个至第n个元素依次向前移动一个位置，共移动n-i个元素。

}
}
```

# 栈

## 顺序栈

> 线性栈: 限定在栈顶进行插入or删除操作的线性表

顺序栈: 顺序储存结构实现的栈

!(https://upload-images.jianshu.io/upload_images/5862031-bbdfb570373c7f03.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

!(https://upload-images.jianshu.io/upload_images/5862031-c99488b196e1001f.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

!(https://upload-images.jianshu.io/upload_images/5862031-dba77b77df46ed76.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

```c
#define StackSize 10

typedef struct Stack {
int top;
char Stack;
} STA, *PSTA;

//初始化栈
PSTA InitStack() {
PSTA Stack = (PSTA) malloc(StackSize * sizeof(STA));
Stack->top = -1;
return Stack;
}
//入栈
void Push(PSTA Stack, char elem) {
//判满
if (Stack->top == StackSize - 1) {
   printf("full");
}
Stack->Stack[++(Stack->top)] = elem;

}

//出栈
void Pop(PSTA Stack, char *ele) {
//判空
if (-1 == Stack->top) {
   printf("stack is empty!\n");
} else {
//    elem = Stack->Stack;
//    Stack->top--;
   *ele = Stack->Stack;
   Stack->top--;

}

}

//取栈顶元素
char GetTop(PSTA Stack) {
//判空
if (-1 == Stack->top) {
   printf("stack is empty!\n");
}
return Stack->Stack;
}

```

## 链式栈

!(https://upload-images.jianshu.io/upload_images/5862031-ea027b672a3f2b55.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

## 字符串 and Bubble Sort

> 字符串: 由0个或多个字符组成的有限序列

!(https://upload-images.jianshu.io/upload_images/5862031-b6119d1861a5665b.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

```c
#include <stdio.h>
#include <mem.h>

int main() {
int t = 0;
char s[] = "people";
for (int i = 0; i < 5; ++i) {
   for (int j = 0; j < 5 - i; ++j) {
         if (s > s) {
            t = s;
            s = s;
            s = t;
         }
   }
}
printf("%s", &s);
return 0;
}
```

# 队

## 顺序队列

> 只允许在表的一端插入而在另一端删除元素的线性表
>
> 先进先出

```c
QueueSize =6;
front =0 ;
rear=0;
//入队
Queue=e;
//出队
return Queue;
//判空
front==rear;
//判满
(rear-front) == QueueSize;
//判满2
rear == QueueSize;

```

利用空闲空间

1. 删除移动

1. 循环队列

## 循环队列

!(https://upload-images.jianshu.io/upload_images/5862031-2d15ba8c7049d43f.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

```c
//入队
Queue=e;
rear=(rear+1)%QueueSize;
//出队
e=Queue;
front=(front+1)%QueueSize;
//判空
rear==front;
//判满
(rear+1)%QueueSize ==front;
//队列长度
(rear-front+QueueSize)%QueueSize;

```

## 链式队列

采用链式存储结构实现的队列

!(https://upload-images.jianshu.io/upload_images/5862031-98bf5fdeb8dc7fd1.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

```c
typedef struct QNode{
char data;
sruct QNode * next;
}QNODE;

//初始化
QNODE * front =(QNODE *)malloc(sizeof(QNODE));
front->next=NULL;
QNODE * rear=front;
//判空
front==rear;
//判空2
front->next==NULL;
//入队不判满
q->next =NULL;
rear -> newxt =q;
rear=q;
//出队判空
q=front->next;
front -> next=->next;
if(q==rear)
rear=front;
delete q;

```

# 树

## 基本概念

> n个节点组成的非线性数据结构
>
>
>
> !(https://upload-images.jianshu.io/upload_images/5862031-1625f28f394a03ba.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

结点: 树中的独立单元 13个节点

结点的度: 节点的子树数量 A的度为3e 的度为2

树的度:各节点度的最大值3

叶子节点 : 度为0的节点KLFGMIJ

内部节点 : 度不为0的节点 EBCDHA

孩子 : 节点的子树的根 kl是节点e的孩子

双亲 e是KL的双亲

兄弟 : 同一双亲的孩子 EF

祖先 :父亲的父亲kl的祖先b

层次 :层数从1开始

堂兄的 : 双亲在同一层的结点

树的深度 : 结点的最大层次

有序树 : 子树从左到右的次序不能交换

森林互不相交的树的集合

## 二叉树的性质

> 每个结点至多只有两棵子树
>
> 子树有左右之分,次序不能颠倒
>
> 在二叉树的第 i 层上至多有
> $$
> 2^{i-1}
> $$
> 个节点
> 深度为 K 的二叉树至多有
> $$
> 2^K-1
> $$
> 个节点
>
> 如果叶子结点数N0, 度为2的结点数为N2, 则 N0 =N2 +1
>
> 满二叉树深度为K且含有2^K-1 个节点的二叉树内部节点每个都有两个后继
>
> 完全二叉树: n个结点每个都与满二叉树编号从1到n一一对应
>
> 满二叉树是完全二叉树
>
>

> 完全二叉树性质:
>
> 具有N个结点的完全二叉树的深度
> $$
> |log_2^{N}| +1
> $$
> 满二叉树的深度为k=log2(n+1);
>
>
>
> 具有n个结点的完全二叉树,其任一结点i
>
> 其双亲结点为
> $$
> \frac{i}{2}
> $$
> 其左结点为
> $$
> 2i
> $$
> 其右结点为
> $$
> 2i+1
> $$
>

## 遍历二叉树

### 1.先序遍历：按照根节点->左子树->右子树的顺序访问二叉树

!(https://upload-images.jianshu.io/upload_images/5862031-f872573e19aba9da.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

先序遍历：（1）访问根节点；（2）采用先序递归遍历左子树；（3）采用先序递归遍历右子树；

先序遍历结果：A BDFE CGHI

思维过程：（1）先访问根节点A，

（2）A分为左右两个子树，因为是递归调用，所以左子树也遵循“先根节点-再左-再右”的顺序，所以访问B节点，

（3）然后访问D节点，

（4）访问F节点的时候有分支，同样遵循“先根节点-再左--再右”的顺序,

(5)访问E节点，此时左边的大的子树已经访问完毕，

(6)然后遵循最后访问右子树的顺序，访问右边大的子树，右边大子树同样先访问根节点C,

(7)访问左子树G,

(8)因为G的左子树没有，所以接下俩访问G的右子树H,

(9)最后访问C的右子树I

###2.中序遍历：按照左子树->根节点->右子树的顺序访问

!(https://upload-images.jianshu.io/upload_images/5862031-ce763f11394909a5.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

中序遍历：（1）采用中序遍历左子树；（2）访问根节点；（3）采用中序遍历右子树

中序遍历结果：DBEF A GHCI

### 3.后序遍历

!(https://upload-images.jianshu.io/upload_images/5862031-d107f9fbe3134571.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

后序遍历：（1）采用后序递归遍历左子树；（2）采用后序递归遍历右子树；（3）访问根节点；

后序遍历的结果：DEFBHGIC A

## 哈夫曼树

> 最优树带权路径长度之和最短的树

!(https://upload-images.jianshu.io/upload_images/5862031-0dec33c40bf3a520.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

!(https://upload-images.jianshu.io/upload_images/5862031-edde892be2d4254b.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

JensenLiu 发表于 2019-1-7 17:26

好像很全的样子，感谢分享

明明我就喜欢你 发表于 2019-1-7 17:28

谢谢分享先看看

你的秋裤 发表于 2019-1-7 17:35

令人吐血的操作

fihuang2315 发表于 2019-1-7 17:42

表示读不懂机器人。

wabmlpb 发表于 2019-1-7 17:48

先看看学习一下

ISHAO 发表于 2019-1-7 18:05

挺有用的

csa 发表于 2019-1-7 19:31

谢谢，下载看看先

新司机丶听雪 发表于 2019-1-7 22:27

数据结构真的难

Norton 发表于 2019-1-7 23:51

挺详细的

页: [1] 2 3

吾爱破解 - 52pojie.cn's Archiver

数据结构