数据结构

作者: Yancy02 | 来源:发表于2019-01-07 17:19 被阅读0次

[TOC]

绪论

程序=算法+数据结构

线性结构: 元素间存在一对一的线性关系

树形结构: 元素间存在一对多的层次关系

图结构: 元素间存在多对多的网状关系

数据(Data): 能输入到计算机并被计算机处理的符号总称。

例：公司每个部门通讯录总集

数据元素（Data Element）: 数据的基本单位，通常也是程序处理的单位，用于描述一个对象。

例：具体某位员工的信息

数据项（Data Item）: 组成数据元素的有独立含义的、不可分割的最小单位。

例：具体某位员工信息中的电话号码

数据对象（Data Object）: 数据元素的集合，是数据的一个子集。

例：某部门员工信息集合

学生信息表

数据对象：整张表

数据元素：某位学生信息

数据项：某位学生的某项具体信息，比如姓名

1546603636273.png

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

1546603693638.png

1546603734593.png

1546603740834.png

1546603746482.png

1546603756363.png

算法

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

特性 :

有穷性: 在执行有穷步后结束每一步都在有穷时间内完成

确定性 : 每种情况下执行的操作有确切的含义，无二义性

可行性 : 所有操作都可以通过已经实现的基本操作运算执行有限次来实现

输入 : 一个算法有零个或多个输入

输出: 一个算法有一个或多个输出

设计要求

正确性 : 在合理的数据输入下，能够在有限的运行时间内得到正确的结果。

可读性 : 便于理解和交流，易于调试和修改。

健壮性 : 当输入非法数据时，能适当地做出正确反应和相应处理。

通用性 : 执行效率高，占用存储容量合理

时间复杂度

时间复杂度主要是衡量算法执行时间的长短。

一个算法的时间复杂度大致上等于其所有语句执行次数的总和。

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))

数组

数组的初始化

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

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

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

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

把数组传递给函数

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

C 指向数组的指针

#include <stdio.h>
 
int main ()
{
   /* 带有 5 个元素的整型数组 */
   double balance[5] = {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 传递数组给函数

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

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

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

二维数组

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

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

把二维数组传递给函数

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

函数

实参和形参

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);
}
/*实参与形参不共用存储单元。
参数传递时，把实参的值复制一份给形参。
形参值的变化不影响实参的值。
所以，形参和实参可以同名。
*/

结构体

结构体是派生的数据类型

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

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

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

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

定义声明结构体变量

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

初始化结构体变量

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

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

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

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

结构体数组

struct student {
  int num;
  char name[20];
  float scores[4];
};

struct student students[30];

指针

指针的概念

指针变量就是保存内存地址的变量。

内存对象包括：变量，数组，函数等。

C语言允许直接通过地址来处理数据。

指针变量的定义和初始化

int *x_pointer, *y_pointer;

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

指针运算符

取地址运算符：&

指针运算符：*

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

#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);
}

指针作为函数参数

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);
}

指针与数组

int b[5];
int *bPtr;
bPtr = b;

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

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

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

指针与字符串

程序设计举例

表

单链表

结构体指针的声明

typedef struct student
{
    int ID;
    char  name[30];
    float score;
    struct student* next;   //指针，指向直接后继
}STUDENT;



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

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

线性表的链式存储

typedef struct student
{
    int ID;
    char  name[30];
    float score;
    struct student* ptr;   //指示下一位学生
}STUDENT;

链表的分类

单链表:每个结点中只包含一个指针域。

双向链:表每个结点中包含两个指针域，一个指向直接后继，另一个指向直接前驱。

循环链:表单链表中最后一个结点的指针域指向头结点，整个链表形成一个环。

头结点与首元结点

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

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

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

思考：链表怎么判空？

顺序存储

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

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

1546758958027.png

单链表的初始化

1546758958027.png

1546768816131.png

1546768844353.png

1546841488673.png

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

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

//定义结构体
typedef struct Student {
    int ID;
    char name[20];
    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;
    }
}

单链表的取值和查找

//按节点查询
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;
}

单链表的插入和删除

1546769357604.png

1546769408594.png

//插入新的节点
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);
}

线性表

线性表插入

// 线性表的插入操作是值在第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[i + 1] = arr[i];
        }
        arr[index] = value;
        len++;//需从最后一个(第n个)元素开始，依次向后移动一个位置，直至第i个元素，共移动n-i+1个元素。

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

线性表删除

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


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

    }
}

栈

顺序栈

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

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

1546769634693.png

1546769682673.png

1546769694422.png

#define StackSize 10

typedef struct Stack {
    int top;
    char Stack[StackSize];
} 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];
//        Stack->top--;
        *ele = Stack->Stack[Stack->top];
        Stack->top--;


    }

}

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

链式栈

1546770111409.png

字符串 and Bubble Sort

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

1546771191795.png

#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[j] > s[j + 1]) {
                t = s[j + 1];
                s[j + 1] = s[j];
                s[j] = t;
            }
        }
    }
    printf("%s", &s);
    return 0;
}

队

顺序队列

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

先进先出

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

利用空闲空间

删除移动
循环队列

循环队列

1546842115339.png

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

链式队列

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

1546842458315.png

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个节点组成的非线性数据结构
1546778042940.png

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

结点的度: 节点的子树数量 A的度为3 e 的度为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.先序遍历：按照根节点->左子树->右子树的顺序访问二叉树

20180223122131558.jpg

先序遍历：（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.中序遍历：按照左子树->根节点->右子树的顺序访问

20180223122302320.jpg

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

中序遍历结果：DBEF A GHCI

3.后序遍历

20180223122410506.jpg

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

后序遍历的结果：DEFB HGIC A

哈夫曼树

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

1546785740149.png

1546785773623.png