算法与数据结构

发表于 | 更新于: | 分类于
字数统计: 4.3k | 阅读时长 ≈ 21

算法与数据结构

程序 = 数据结构 + 算法
——Nikiklaus Wirth

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
/** 
 *                             _ooOoo_ 
 *                            o8888888o 
 *                            88" . "88 
 *                            (| -_- |) 
 *                            O\  =  /O 
 *                         ____/`---'\____ 
 *                       .'  \\|     |//  `. 
 *                      /  \\|||  :  |||//  \ 
 *                     /  _||||| -:- |||||-  \ 
 *                     |   | \\\  -  /// |   | 
 *                     | \_|  ''\---/''  |   | 
 *                     \  .-\__  `-`  ___/-. / 
 *                   ___`. .'  /--.--\  `. . __ 
 *                ."" '<  `.___\_<|>_/___.'  >'"". 
 *               | | :  `- \`.;`\ _ /`;.`/ - ` : | | 
 *               \  \ `-.   \_ __\ /__ _/   .-` /  / 
 *          ======`-.____`-.___\_____/___.-`____.-'====== 
 *                             `=---=' 
 *          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 
 *                     佛祖保佑        永无BUG 
 *            佛曰: 
 *                   写字楼里写字间，写字间里程序员； 
 *                   程序人员写程序，又拿程序换酒钱。 
 *                   酒醒只在网上坐，酒醉还来网下眠； 
 *                   酒醉酒醒日复日，网上网下年复年。 
 *                   但愿老死电脑间，不愿鞠躬老板前； 
 *                   奔驰宝马贵者趣，公交自行程序员。 
 *                   别人笑我忒疯癫，我笑自己命太贱； 
 *                   不见满街漂亮妹，哪个归得程序员？ 
*/

[TOC]

解决问题的效率

１．解决问题的效率和数据的组织方式有关

２．解决问题的效率和空间的利用效率有关

３．解决问题的效率和算法的巧妙程度有关 　　

抽象数据类型

  • 数据对象集
  • 操作集　　
    抽象数据类型表示（ADT）

    数据结构

  • 逻辑结构
    • 线性
    • 非线性
  • 物理结构
    • 顺序
    • 链式
    • 索引
    • 散列
  • 运算
    • 插删查改排

      算法

      特性

  • 有穷性 ~有穷步骤结束
  • 确定性 ~每一步有明确定义
  • 可行性 ~算法可行，能被计算机识别执行

    算法分析

——————————-提高效率

  • 空间复杂度S（n）——根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
  • 时间复杂度T（n）——根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。
  • 上界 O(f(n)) 　　　 能找到的最小上界（与真实情况贴近）
  • 下界 Ω(g(n)) 　　　能找到的最大下界
  • worst 　　　　　 最坏复杂程度
  • avg 　　　　　 平均复杂程度
    Markdown

线性非线性

一、线性结构：

1.线性结构作为最常用的数据结构，其特点是==数据元素之间存在一对一的线性关系==。

2.线性结构拥有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的，链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。

3.线性结构中存在两种操作受限的使用场景，即队列和栈。栈的操作只能在线性表的一端进行，就是我们常说的先进后出（FILO），队列的插入操作在线性表的一端进行而其他操作在线性表的另一端进行，先进先出（FIFO），由于线性结构存在两种存储结构，因 此队列和栈各存在两个实现方式。

二、非线性结构：

1.非线性结构中各个数据元素不再保持在一个线性序列中，==每个数据元素可能与零个或者多个其他数据元素发生联系==。根据关系的不同，可分为层次结构和群结构。

2.常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。（其中多维数组是由多个一维数组组成的，所以不再是线性结构）。

线性结构

多项式存储方法

  • 数组结构存储
  • 链表结构存储
    Markdown

顺序表

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include "stdio.h"
#include "conio.h"
#define MaxSize 10
typedef int ElemType ;  //将int定义为ElemType

typedef struct{
int *elem;
int length;
int listsize;
} Sqlist;

/**  初始化一个顺序表  */
/**  参数L：Sqlist类型的指针  */
void initSqlist(Sqlist *L){
    L->elem=(int *)malloc(MaxSize*sizeof(ElemType));
    if(!L->elem) exit(0);
    L->length=0;
    L->listsize= MaxSize;
}

/**  向顺序表中插入元素   */
/**  参数L：Sqlist类型的指针  */
/**  参数i：插入元素的位置 */
/**  参数item：插入的元素  */
void InsertElem(Sqlist *L,int i,ElemType item){
    ElemType  *base,* insertPtr,*p;
    if(i<1||i>L->length+1){
    	printf("位置不合法");
    	exit(0);
	}
    if(L->length>=L->listsize){
        base=(ElemType*)realloc(L->elem,(L->listsize+10)*sizeof(ElemType));
        L->elem=base;
    L->listsize=L->listsize+10;
    }
    /*
    insertPtr=&(L->elem[i-1]);
    for(p=&(L->elem[L->length-1]);p>= insertPtr;p--)
            *(p+1)=*p;
    * insertPtr=item;
    L->length++;
    */
    int t;
    for( t=L->length; t>=i; t-- )
        L->elem[t] = L->elem[t-1];    // 将位置P及以后的元素顺序向后移动
    L->elem[i-1] = item;              // 新元素插入
    L->length++;                      //Last仍指向最后元素
}
/**  从顺序表中删除元素   */
/**  参数L：Sqlist类型的指针  */
/**  参数i：删除元素的位置 */
void DelElem(Sqlist *L,int i) {


    if( i<1 || i>L->length+1 ) {     // 检查空表及删除位置的合法性
        printf("位置%d不存在元素", i );
        exit(0);
    }
    int p;
    for(p=i;p<L->length;p++)
    	L->elem[p-1]=L->elem[p];
    L->length--;
}

/** 测试函数 */
 main()
{
    Sqlist l;
    int i;
    initSqlist(&l);                 //初始化一个顺序表
    for(i=0;i<15;i++)
        InsertElem(&l,i+1,i+1);     //向顺序表中插入
    printf("\nThe content of the list is\n");
    for(i=0;i<l.length;i++)
        printf("%d ",l.elem[i]);    //打印出顺序表中的内容
    DelElem(&l,5);                  //删除第5个元素，即5
    printf("\nDelete the fifth element\n");
    for(i=0;i<l.length;i++)         //打印出删除后的结果
        printf("%d ",l.elem[i]);
    printf("\nInsert the fifth element as 5\n");
    InsertElem(&l,5,5);
    for(i=0;i<l.length;i++)
        printf("%d ",l.elem[i]);    //打印出顺序表中的内容
   getche();
}
/**********************************
结果
The content of the list is
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Delete the fifth element
1 2 3 4 6 7 8 9 10 11 12 13 14 15
插入55
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
*/

链表

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <stdio.h>
#include <stdlib.h>
typedef int Elemtype;
typedef struct node{
    Elemtype data;                 //数据
    struct node *next;             //指针
}LNode,*LinkList;

/** 创建长度为n的链表 */
LinkList GreatLinkList(int n){
    LinkList p,r,list=NULL;
    Elemtype e;
    int i;
    for(i=1;i<=n;i++){
        scanf("%d",&e);
        p=(LinkList)malloc(sizeof(LNode));
        p->data=e;
        p->next=NULL;
        if(!list)
            list=p;
        else
            r->next=p;
        r=p;
    }
    return list;
}

/** 已知前节点删除 */
void delLink1(LinkList *list,LinkList r,LinkList q){
    if(q=*list)
        *list=q->next;
    else
        r->next=q->next;
    free(q);
}

/** 未知前节点删除 */
void delLink2(LinkList *list,LinkList q){
    LinkList r;                              //r->next = q
    if(q==*list){
        *list=q->next;
        free(q);
    }
    else{
        for(r=*list;r->next!=q;r=r->next);   //遍历链表，找到q的前节点指针
        if(r->next!=NULL){
            r->next=q->next;
            free(q);
        }
    }

}

/** 节点q后插入 */
void insertList(LinkList *list,LinkList q,Elemtype e){
    LinkList p;
    p=(LinkList)malloc(sizeof(LNode));
    p->data=e;
    if(!*list){
        *list=p;
        p->next=NULL;
    }
    else{
        p->next=q->next;
        q->next=p;
    }
}

/** 销毁链表 */
void destroyLinkList(LinkList *list){
    LinkList p,q;
    p=*list;
    while(p){
        q=p->next;
        free(p);
        p=q;
    }
    *list=NULL;
}

int main()
{
    int e,i;
    LinkList l,q;
    q=l=GreatLinkList(1);


    /** 输入链表数据 */
    scanf("%d",&e);
    while(e){
        insertList(&l,q,e);
        q=q->next;
        scanf("%d",&e);
    }
    q=l;

    /** 输出链表数据 */
    printf("\nThe content of the linklist\n");
    while(q){
        printf("%d ",q->data);
        q=q->next;
    }
    q=l;

    /** 删除链表数据 */
    printf("\nDelete the fifth element\n");
    for(i=0;i<4;i++)
    {
        if(q==NULL){
            printf("Error,the length of linklist is smaller than 5\n");
            return;
        }
        q=q->next;
    }
    delLink2(&l,q);
    q=l;

    /** 输出删除后链表数据 */
    printf("\nThe content of the linklist\n");
    while(q){
        printf("%d ",q->data);
        q=q->next;
    }


    /** 销毁链表 */
    destroyLinkList(&l);

    return 0;
}
/**************************** 
 ============================
 输入 
 1 2 3 4 5 6  0
 ============================
 结果
 The content of the linklist
 1 2 3 4 5 6
 Delete the fifth element
 
 The content of the linklist
 1 2 3 4 6
 */

堆栈（顺序表）

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include "stdio.h"
#include "math.h"
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10

typedef  int ElemType;
typedef struct{
    ElemType *base;
    ElemType *top;
    int stacksize;
}sqStack;

initStack(sqStack *s)
{
    /*内存中开辟一段连续空间作为栈空间，首地址赋值给s->base*/
    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if(!s->base) exit(0);     /*分配空间失败*/
    s->top = s->base;       /*最开始，栈顶就是栈底*/
    s->stacksize = STACK_INIT_SIZE;   /*最大容量为STACK_INIT_SIZE */
}

Push(sqStack *s, ElemType e){
    if(s->top - s->base >= s->stacksize){
    /*栈满，追加空间*/
    s->base = (ElemType *)realloc(s->base, (s->stacksize + 
    STACKINCREMENT)*sizeof(ElemType));
    if(!s->base) exit(0);   /*存储分配失败*/
    //s->top = s->base + s->stacksize;
    s->stacksize = s->stacksize + STACKINCREMENT; /*设置栈的最大容量*/
    }
    *(s->top) = e;  /*放入数据*/
        s->top++;
}

Pop(sqStack *s , ElemType *e){
    if(s->top == s->base) return;
    *e = *--(s->top);     
}

int StackLen(sqStack s){
    return (s.top - s.base) ; 
}
main()
{
	int i,j;
    sqStack a;
    initStack(&a);
    
    for(i=0;i<10;i++){
    	Push(&a,i);
    	printf("push %d\n",i);
	}
	
    int len =StackLen(a);
	for(i=0;i<len;i++){
		Pop(&a,&j);
		printf("pop %d\n",j);
	}
	
	//DestroyStack(&a);	
}
/*****
push 0
push 1
push 2
push 3
push 4
push 5
push 6
push 7
push 8
push 9
pop 9
pop 8
pop 7
pop 6
pop 5
pop 4
pop 3
pop 2
pop 1
pop 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>

using namespace std;

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct SNode *PtrToSNode;
struct SNode {
    ElementType Data;
    PtrToSNode Next;
};
typedef PtrToSNode Stack;

Stack CreateStack( )
{ /* 构建一个堆栈的头结点，返回该结点指针 */
    Stack S;

    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

bool IsEmpty ( Stack S )
{ /* 判断堆栈S是否为空，若是返回true；否则返回false */
    return ( S->Next == NULL );
}

bool Push( Stack S, ElementType X )
{ /* 将元素X压入堆栈S */
    PtrToSNode TmpCell;

    TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
    TmpCell->Data = X;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
    return true;
}

ElementType Pop( Stack S )
{ /* 删除并返回堆栈S的栈顶元素 */
    PtrToSNode FirstCell;
    ElementType TopElem;

    if( IsEmpty(S) ) {
        printf("堆栈空");
        return 0;
    }
    else {
        FirstCell = S->Next;
        TopElem = FirstCell->Data;
        S->Next = FirstCell->Next;
        free(FirstCell);
        return TopElem;
    }
}
int main()
{
    int i;
    Stack a = CreateStack();
    for(i=0;i<5;i++)
        Push(a,i);
    for(i=0;i<5;i++)
        printf("%d",Pop(a));
    return 0;
}
/**** 
结果
43210
*/

队列(链表)

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct QNode* QueuePtr;

typedef struct QNode{
    ElemType Data;       /*数据域*/
    QueuePtr next;       /*指针域*/
}QNode;

typedef struct{
    QueuePtr front; /*队头尾指针*/
    QueuePtr rear;
}LinkQueue;

void initQueue(LinkQueue*q){
    /*初始化*/
    q->front = q->rear =(QueuePtr)malloc(sizeof(QNode));
    if(!q->front) exit(0);
    q->front->next = NULL;
}

void EnQueue(LinkQueue* q,ElemType e){
    /*进入队列*/
    QueuePtr p;
    p = (QueuePtr)malloc(sizeof(QNode));
    if(p==NULL) exit(0);
    p->Data = e;
    p->next =NULL;
    q->rear->next = p;
    q->rear = p;
    printf("%d入队列\n",e);
}

void DeQueue(LinkQueue* q,ElemType *e){
    /*出队列*/
    if(q->front==q->rear) return;
    QueuePtr p;
    p = q->front->next;
    *e = p->Data;
    q->front->next = p->next;
    if(q->rear == p) q->rear=q->front; /*队尾是p,队列空*/
    free(p);
    printf("%d出队列\n",*e);
}

void DestroyQueue(LinkQueue* q){
    while(q->front){
        q->rear=q->front->next;
        free(q->front);
        q->front = q->rear;
    }
    printf("\nDestroy Queue Successfully\n");
}

int main()
{
    LinkQueue q;
    initQueue(&q);
    int i,j;
    for(i=0;i<5;i++)
        EnQueue(&q,i);
    for(i=0;i<5;i++)
        DeQueue(&q,&j);
    DestroyQueue(&q);
    return 0;
}

/** 结果
0入队列
1入队列
2入队列
3入队列
4入队列
0出队列
1出队列
2出队列
3出队列
4出队列

Destroy Queue Successfully
*/

多项式乘加

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <stdio.h>
#include <stdlib.h>
typedef struct PolyNode{
    int coef;                                       //系数
    int expon;                                      //指数
    struct PolyNode* link;
}PolyNode, *Polynomial;                             //指针域

Polynomial ReadPoly(){
    Polynomial P,Rear,t;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->link = NULL;                                 //链表头结点 空
    Rear = P;                                       //链表尾结点                                

    int c,e,n;
    scanf("%d",&n);                                    
    while(n--){
        scanf("%d %d",&c,&e);
        Attach(c,e,&Rear);                          //读取系数指数 插入
    }
    t = P;P = P->link;free(t);                      //删除头结点   使p指向多项式第一组结点
    return P;
}
/** 插入尾部 */
void Attach(int c,int e,Polynomial *pRear){         //传入Polynomial类型的指针，Polynomial本身就是指针。pRear也就是指针的指针
    Polynomial p;
    p = (Polynomial)malloc(sizeof(struct PolyNode));//申请新结点空间
    p->coef = c;
    p->expon = e;
    p->link = NULL;
    (*pRear)->link = p;
    *pRear = p;                                     //pRear指向p的
}

/**  多项式加 */
Polynomial Add(Polynomial p1,Polynomial p2){
    Polynomial front,rear,temp,t1,t2;
    int sum;
    t1=p1;t2=p2;                                          //获取头结点
    front = (Polynomial)malloc(sizeof(struct PolyNode));  //申请 新的 多项式之和 的 链表空间
    front->link = NULL;
    rear=front;
    while(t1&&t2){                                        //两个多项式非空 比较指数大小
        if(t1->expon > t2->expon){                        //指数大的 插入新链表
            Attach(t1->coef,t1->expon,&rear);
            t1 = t1->link;
        }
        else if(t1->expon < t2->expon){                   
            Attach(t2->coef,t2->expon,&rear);
            t2 = t2->link;
        }
        else{                                             //指数相等 判断系数是否为0
            sum = t1->coef+t2->coef;
            if(sum)Attach(sum,p1->expon,&rear);           //如果为0 不操作
            t1 = t1->link;
            t2 = t2->link;
        }
    }
    while (t1){                                           //1个链表空
        Attach(t1->coef, t1->expon, &rear);
        t1 = t1->link;
    }

    while (t2){
        Attach(t2->coef, t2->expon, &rear);
        t2 = t2->link;
    }
    rear->link = NULL;
    temp =front;
    front=front->link;
    free(temp);
    return front;
}

/**  多项式乘 */
Polynomial Mult(Polynomial p1,Polynomial p2){
    Polynomial t1,t2,p,rear,t;

    if(!p1||!p2) return NULL;
    t1=p1;t2=p2;
    p=(Polynomial)malloc(sizeof(struct PolyNode));
    p->link= NULL;
    rear=p;
    while(t2){                                                 //p1第一项乘p2 新链表p
        Attach(t1->coef*t2->coef,t1->expon+t2->expon,&rear);
        t2=t2->link;
    }
    t1=t1->link;

    while(t1){
        t2=p2;rear=p;                                          //rear回到首项
        while(t2){
            int e,c;
            e = t1->expon+t2->expon;
            c = t1->coef*t2->coef;
            while(rear->link&&rear->link->expon>e)             //指数大 向后遍历
                rear=rear->link;
            if(rear->link&&rear->link->expon==e){              //指数相等
                if(rear->link->coef+c)                         //系数不为0
                    rear->link->coef+=c;
                else{                                          //系数为0删除结点
                    t=rear->link;
                    rear->link=t->link;
                    free(t);
                }
            }
            else{                                               //指数小 
                t=(Polynomial)malloc(sizeof(struct PolyNode));  //为小指数申请一个结点
                t->link=NULL;
                t->coef=c;t->expon=e;
                t->link=rear->link;
                rear->link=t;rear=rear->link;
            }
            t2=t2->link;
        }
        t1=t1->link;
    }
    t2=p;p=p->link;free(t2);
    return p;
}

/** 输出 */
void PrintPoly(Polynomial p){
    int flag =0;
    if(!p){
        printf("0 0\n");
        return;
    }
    while(p){
        if(!flag)
            flag = 1;
        else
            printf(" ");
        printf("%d %d",p->coef,p->expon);
        p=p->link;
    }
    printf("\n");
}
int main()
{
    Polynomial p1,p2,pp,ps;
    p1 = ReadPoly();
    p2 = ReadPoly();
    pp = Mult(p1,p2);
    PrintPoly(pp);
    ps = Add(p1,p2);
    PrintPoly(ps);

    return 0;
}
/**************************************************************
输入
4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1
输出
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
*/

串(kmp)

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
59
60
61
62
63
64
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    char s[100];
    int length;
}seqstring;

void initSeq(seqstring *t){                //初始化
    t->length=0;
    int i=0;
    
    while((t->s[i]=getchar())!='\n')
        i++;
    
    t->s[i]='\0';
    
    t->length=i; 
}

void getnext(seqstring *t,int *next){
    int i=0;
    int j=-1;
    next[0]=-1;
    while(i<t->length){
        if(j==-1||t->s[i]==t->s[j]){
            i++;j++;next[i]=j;
        }
        else
            j=next[j];
    }
}

int kmp(seqstring *t,seqstring *p,int *next){
    getnext(&p,next);
    int i,j;
    i=0;j=0;
    while(i<t->length&&j<p->length){
        if(j==-1||t->s[i]==p->s[j]){
            i++;j++;
        }
        else{
            j=next[j];
        }
    }
    if(j==p->length)
        return i-j;
    else
        return 0;
}


int main()
{
    seqstring t;
    initSeq(&t);
    printf("目标字符串已创建\n");
    seqstring p;
    initSeq(&p);
    printf("模式字符串已创建\n");
    int next[100]={0};
    printf("is %d",kmp(&t,&p,next));
    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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct BiNode{
    ElemType data;                   //数据域
    struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

/** 找呀找呀找朋友 */
visit(char c,int level){
    if(c =='D')
        printf("%c is at %dth level of Bitree\n",c,level);
}

/** 先序遍历 */
PreOrderTraverse(BiTree T,int level){
    if(T){                          //T空，递归结束
        visit(T->data,level);             //访问根节点
        PreOrderTraverse(T->lchild,level+1);   //左
        PreOrderTraverse(T->rchild,level+1);   //右
    }
}

/** 中序遍历 */
InOrderTraverse(BiTree T,int level){
    if(T){
        InOrderTraverse(T->lchild,level+1);
        visit(T->data,level);
        InOrderTraverse(T->rchild,level+1);
    }
}

/** 后序遍历 */
PosOrderTraverse(BiTree T,int level){
    if(T){
        PosOrderTraverse(T->lchild,level+1);
        PosOrderTraverse(T->rchild,level+1);
        visit(T->data,level);
    }
}

/** 后序遍历求树深度(递归) */
int PosOrderHeight(BiTree T){
    int hl,hr,h;
    if(T){
        hl=PosOrderHeight(T->lchild);
        hr=PosOrderHeight(T->rchild);
        h =(hl>hr)?hl:hr;
        return h+1;
    }
    else
        return 0;
}


/** 创建二叉树 */
CreatBiTree(BiTree *T){
    char c;
    scanf("%c",&c);
    if(c==' ')
        *T=NULL;
    else{
        (*T)=(BiTree)malloc(sizeof(BiTNode));
        (*T)->data=c;
        CreatBiTree(&((*T)->lchild));
        CreatBiTree(&((*T)->rchild));
    }
}


int main()
{
    int level = 1;
    BiTree T;
    T=NULL;
    CreatBiTree(&T);
    PreOrderTraverse(T,level);
    printf("the height of the tree is %d",PosOrderHeight(T));
    return 0;
}
/*************************
测试二叉树
            A
           / \
          B   E
         / \   \
        C   D   F
（我画的真好看） 
输入
ABC  D  E F  //空格很重要
输出
D is at 3th level of Bitree
the height of the tree is 3

*/