数据结构

1.关于算法效率

例1：写程序计算给定多项式在定点x处的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
double f(int n,double a[],double x){
    int i;
    double p=a[0];
    for(i=1;i<=n;i++){
        p+=(a[i]*pow(x,i));
    }
    return p;
    //不合适！！！
}

double f(int n,double a[],double x){
    //a[]用于储存多项式的系数
    int i;
    double p=a[n];
    for(i=n;i>0;i--)
        p=a[i-1]+x*p;//多次提取x
    return p;
}

常用的测试程序运行时间的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<time.h>
using namespace std;
//clock():捕捉从程序开始运行到clock()被调用所耗费的时间，单位为clock tick
clock_t start,stop;
//clock_t是clock()函数返回的变量类型
double duration;
//记录被测函数运行时间，以秒为单位
int main(){
    /*不在测试范围内的准备工作写在clock()调用之前*/

    start=clock();//开始计时
    MyFunction();//被测函数
    stop=clock();//停止计时
    duration=((double)(stop-start))/CLK_TCK;//计算时间

    //CLK_TCK:机器时钟每秒所走的时钟打点数

    /*不在测试范围的处理写在后面*/
    return 0;
}

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<time.h>
#include<math.h>
using namespace std;
#define MAXN 10
#define MAXK 1e7//被测函数最大重复调用次数
double f1(int n, double a[], double x) {
    int i;
    double p = a[0];
    for (i = 1; i <= n; i++) {
        p += (a[i] * pow(x, i));
    }
    return p;
    //不合适！！！
}
double f2(int n, double a[], double x) {
    //a[]用于储存多项式的系数
    int i;
    double p = a[n];
    for (i = n; i > 0; i--)
        p = a[i - 1] + x * p;//多次提取x
    return p;
}


//clock():捕捉从程序开始运行到clock()被调用所耗费的时间，单位为clock tick
clock_t start, stop;
//clock_t是clock()函数返回的变量类型
double duration;
//记录被测函数运行时间，以秒为单位
int main() {
    int i;
    double a[MAXN];
    for (i = 0; i < MAXN; i++) a[i] = (double)i;
    /*不在测试范围内的准备工作写在clock()调用之前*/

    start = clock();//开始计时
    for(i=0;i<MAXK;i++)
        f1(MAXN - 1, a, 1.1);//被测函数
    stop = clock();//停止计时
    duration = ((double)(stop - start)) /CLK_TCK/MAXK;//计算时间
    printf("duration1=%6.2e\n", duration);
    //CLK_TCK:机器时钟每秒所走的时钟打点数
    start = clock();//开始计时
    for (i = 0; i < MAXK; i++)
        f2(MAXN - 1, a, 1.1);//被测函数
    stop = clock();//停止计时
    duration = ((double)(stop - start)) /CLK_TCK/MAXK;//计算时间
    printf("duration2=%6.2e\n", duration);
    /*不在测试范围的处理写在后面*/
    return 0;
}

求N个整型数列的区间和最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//算法1 暴力枚举法
int MaxsubseqSum(int A[],int N){
    int ThisSum,MaxSum=0;
    int i,j,k;
    for(i=0,i++,i<N){
        for(j=i,j++,j<N){
            ThisSum=0;
            for(k=i,k++,k<j){
                ThisSum+=A[k];
            }
            if(ThisSum>MaxSum)
                MaxSum=ThisSum;
        }
    }
    return MaxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//算法2 暴力枚举法优化
int MaxsubseqSum(int A[],int N){
    int ThisSum,MaxSum=0;
    int i,j;
    for(i=0,i++,i<N){
        ThisSum=0;
        for(j=i,j++,j<N){
            ThisSum+=A[j]; 
            if(ThisSum>MaxSum)
                MaxSum=ThisSum;
        }
    }
    return MaxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//算法3 在线处理
int MaxsubseqSum(int A[],int N){
    int ThisSum,MaxSum=0;
    int i;
    ThisSum=MaxSum=0;
    for(i=0,i++,i<N){
        ThisSum+=A[i];
        if (ThisSum>MaxSum)
            MaxSum=ThisSum;
        else if (ThisSum<0)
            ThisSum=0;  
    }
    return MaxSum;
}

一元多项式的表示

运用结构数组，结构中包含指数和系数，按照指数由大到小排列
运用链表存储,链表中每个结点存储多项式中的一个非零项，包括系数和指数两个数据域以及一个指针域

1
2
3
4
5
6
typedef struct  PolyNode *Polynomial;
struct PolyNode{
    int coef; //系数
    int expon;//指数
    Polynomial link;
}

2.线性结构

线性表

抽象数据类型描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
类型名称:线性表(List)

数据对象集:n个元素构成的有序序列

操作集:
List MakeEmpty():初始化一个空线性表

ElementType FindKth(int K,List L):根据位序K,返回相应元素;

int Find(ElementType X,List L):在线性表L中查找X的第一次出现位置;

void Insert(ElementType X,int i,List L):在位序i前插入一个新元素X;

void Delete(int i,List L):删除指定位序i的元素;

int Length(List L):返回线性表L的长度n;

线性表的顺序存储实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
typedef struct LNode *List;
struct LNode
{
    ElementType Data[MAXSIZE];
    int Last;
};
struct LNode L;
List PtrL;

//初始化
List MakeEmpty()
{
    List Ptrl;
    Ptrl = (List)malloc(sizeof(struct LNode));
    Ptrl->Last=-1;
    return Ptrl;
}

//查找
int Find(ElementType X,List L)
{
    int i =0;
    while(i<=Ptrl->Last&&Ptrl->Data[i]!=X)
        i++;
    if (i>Ptrl->Last) return -1;
    else return i;  
}
//插入
void Insert(ElementType X,int i,List L)
{
    int j;
    //判断表是否已满
    if (Ptrl->==MAXSIZE-1){
        cout<<"表已满";
        return;
    }
    //检查插入是否合法
    if (i<1||i>Ptrl->Last+2){
        cout<<"位置不合法";
        return;
    }
    for(j=Ptrl->Last;j>=i-1;j--)
        Ptrl->Data[j+1]=Ptrl->Data[j+1];
    Ptrl->Data[i-1]=X;
    Ptrl->Last++;
    return;
}
//删除
void Delete(int i,List L){
    if (i<1||i>Ptrl->Last+1){
        cout<<"位置不合法";
        return;
    }
    for(j=i;j<=Ptrl->Last;j++)
        Ptrl->Data[j-1]=Ptrl->Data[j];
    Ptrl->Last-;
    return;
}

线性表的链表存储实现

1
2
3
4
5
6
7
8
//创建
typedef struct LNode* List;
struct LNode{
    ElementType Data;
    List Next;
};
struct Lnode L;
List PtrL;

操作
求表长

1
2
3
4
5
6
7
8
9
int Length(List Ptrl){
    List p = Ptrl;
    int j = 0;
    while(p){
        p = p->Next;
        j++;
    }
    return j;
}

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//按序号查找
List FindKth(int K,List Ptrl){
    List p = Ptrl;
    int i = 1;
    while(p != NULL && i < K ){
        p = p->Next;
        i++;
    }
    if(i == K)return p;
    else return NULL;
}

//按值查找
List FindKth(ElementType K,List Ptrl){
    List p = Ptrl;
    
    while(p != NULL && p->Data != X ){
        p = p->Next;
    }
     return p;
}

插入

思路：
(1).先创建一个新的结点,用s指向
(2).再找到链表的第i-1个结点,用p指向;
(3)然后修改指针，插入结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//无头结点情况
List Insert(ElementType X,int i,List Ptrl){
    List p,s;                                       
    if(i == 1){                                         /*新结点插入在表头*/
        s = (List)malloc(sizeof(struct LNode));         /*申请，填装结点*/
        s->Data = X;
        s->Next = Ptrl;
        return s;                                       /*返回新表头指针*/
    }
    p = FindKth(i-1,Ptrl);                              /*查找第i-1个结点*/
    if(p == NULL){
        cout<<"参数i错误"<<endl;                         /*第i-1个结点不存在，不能插入*/
        return NULL;
    }else{
        s = (List)malloc(sizeof(struct LNode));         /*申请，填装结点*/
        s->Data = X;
        s->Next = p->Next;
        p->Next = s;
        return Ptrl;       
    }
}

删除
插入

思路：
(1).先找到第i-1个结点，并用p指向
(2).再用指针s指向要被删除的结点（p的下一个结点）
(3)修改指针，删除s所指结点
(4)最后释放s指针所指的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
List Insert(ElementType X,int i,List Ptrl){
    List p,s;                                       
    if(i == 1){                                         /*若要删除的是表的第一个结点*/
        s = Ptrl;                                       /*s指向第一个结点*/
        if(Ptrl != NULL) Ptrl = Ptrl->Next;             /*从链表中删除*/
        else return NULL;
        free(s);                                        /*释放被删除结点*/
        return Ptrl;                                 
    }
    p = FindKth(i-1,Ptrl);                              /*查找第i-1个结点*/
    if(p == NULL){
        cout<<"第"<<i-1<<"个结点不存在"<<endl;                         /*第i-1个结点不存在，不能插入*/
        return NULL;
    }else if(p->Next == NULL){
        cout<<"第"<<i<<"个结点不存在"<<endl;    
    }else{
        s = p->Next;
        p->Next = s->Next;
        free(s);
        return Ptrl; 
    }
}

多重链表

广义表

广义表表示二元多项式

广义表是线性表的推广
对于线性表而言，n个元素都是基本的单元素
广义表中，这些元素不仅可以是单元素也可以是另一个广义表

1
2
3
4
5
6
7
8
9
typedef struct GNode *GList;
struct GNode{
    int Tag;//标志域，0表示结点是单元素，1表示结点是广义表
    union{ //子表指针域Sublist与单元素数据域Data复用，即共用存储空间
        ElementType Data; 
        GList SubList
    }URegion;
    GList Next;  //指向后继结点
}

十字链表

用于存储稀疏矩阵
只存储矩阵的非0元素项
结点的数据域：行坐标Row，列坐标，数值Value
每个结点通过两个指针域，把同行，同列串起来
[1].行指针(向右指针)Right
[2].列指针(向下指针)Down

堆栈

栈的特点：先进后出，后进先出

后序表达式

a+bc-d/e
abc+de/-

堆栈的抽象数据类型描述
堆栈：具有一定操作约束的线性表，只在一段（栈顶/top）做插入、删除

插入数据:入栈
删除数据：出栈
后入先出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
类型名称:堆栈(Stack)

数据对象集:一个有0个或多个元素的有穷线性表

操作集: 长度为MaxSize的堆栈S,堆栈元素item
Stack CreatStack(int MaxSize):生成空堆栈，其最大长度为MaxSize

int IsFull(Stack S,int MaxSize):判断堆栈S是否已满;

void Push(Stack S,ElementType item):将元素item压入堆栈;

int IsEmpty(Stack S):判断堆栈S是否为空;

ElementType Pop(Stack S);删除并返回栈顶元素

栈的顺序存储实现

1
2
3
4
5
6
#define MaxSize //<储存数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode{
    ElementType Data[Maxsize];
    int Top;
};

入栈

1
2
3
4
5
6
7
8
9
void Push(Stack PtrS,ElementType item)
{
    if (PtrS->Top == MaxSize-1){
        cout<<"栈已满"; return;
    }else{
        PtrS->Data[++(PtrS->Top)] = item;
        return;
    }
}

出栈

1
2
3
4
5
6
7
8
ElementType Pop(Stack PtrS){
    if(PtrS->Top==-1){
        cout<<"堆栈空";
        return ERROR;
    }else{
        return(PtrS->Data[(PtrS->Top)--]);
    }
}

例子 请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功

方法：使两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#define MaxSize //<储存数据元素的最大个数>
struct DStack{
    ElementType Data[Maxsize];
    int Top1;
    int Top2;
}S;
S.Top1 = -1;
S.Top2 = MaxSize;

//Push操作
void Push(strcut DStack *PtrS,ElementType item,int Tag)
{
    if(PtrS->Top2 - PtrS->Top1 == 1){
        cout<<"栈已满"; return;
    }
    if (Tag == 1)/*对第一个堆栈操作 */
        PtrS->Data[++(PtrS->Top1)] = item;
    else         /*对第二个堆栈操作 */
        PtrS->Data[--(PtrS->Top2)] = item
}

//Pop操作
ElementType Pop(struct DStack *PtrS,int Tag){
    if (Tag == 1){
        if(PtrS->Top1 == -1){
        cout<<"堆栈1空";
        return NULL;
        }else
        return(PtrS->Data[(PtrS->Top1)--]);
        
    } else {
        if(PtrS->Top2 == MAXSIZE){
        cout<<"堆栈2空";
        return NULL;
        }else  return(PtrS->Data[(PtrS->Top2)++]);
    }
}

栈的链式存储实现

栈的链式存储结构实际上就是一个单链表,叫做链栈。插入和删除操作只能在链栈的栈顶进行。Top应该在头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
typedef struct SNode*Stack;
struct SNode{
    ElementType Data;
    struct SNode *Next;
};

Stack CreateStack(){
    Stack S;
    S = (Stack)malloc(sizeof(strcut SNode));
    S->Next = NULL;
    return S;
}

int IsEmpty(Stack S){
    /*判断堆栈S是否为空，若为空函数返回整数1，否则返回0 */
    return(S->Next == Next);
}

void Push(ElementType item,Stack S){
    struct SNode* TmpCell;
    TmpCell = (struct SNode*)malloc(sizeof(struct SNode));
    TmpCell->Element = item;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
}

ElementType Pop(Stack S)
{
    struct SNode *FirstCell;
    ElementType TopElem;
    if(IsEmpty(S)){
        cout<<"堆栈空"; return NULL;
    }else{
        FirstCell = S->Next;
        S->Next = FirstCell->Next;
        TopElem = FirstCell->Element;
        free(FirstCell);
        return TopElem;
    }
}

实际应用 中缀表达式求值
basic strategy ：将中缀表达式转化为后缀表达式，然后求值
中缀表达式如何转化为后缀表达式

从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理

  1. 运算数：直接输出
  2. 左括号：压入堆栈
  3. 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；
  4. 运算符：
    • 若优先级大于栈顶运算符时，则把它压栈
    • 若优先级小于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；
  5. 若各对象处理完毕，则把堆栈中存留的运算符一并输出。