数据结构期末总结

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

0

数据结构重点分析及期末总结

  • 零分(网络ID)是某师范大学，计科专业的一名屌丝，针对数据结构一科目的期末算法编程考试总结了如下几个算法。

重点分析

简单题型

栈

队列

树

排序

简单题型

往下翻……………

栈

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;
const int stackmax=100;//c初始值分配量
typedef char st;
typedef struct{
    char *base;
    char *top;
    int stacksize;
}stack;

int initstack(stack &s){//初始化
    s.base=new st[stackmax];//为顺序栈动态分配d一个最大容量为stachkmax的数组空间
    if (!s.base) {
        return 0;//储存分配空间失败
    }
    s.top=s.base;//top初始为base，空栈
    s.stacksize=stackmax;//置为栈的最大容量
    return 1;
}

int putstack(stack &s,char e){//入栈
    if(s.top-s.base==s.stacksize){//当相等时为满栈
        cout<<"满栈"<<endl;
        return 0;
    }
    *s.top=e;//元素e压入栈顶
    s.top++;//栈顶指针+1
    return 1;
}

char gettop(stack s){
    if(s.top!=s.base)
        cout<<*(s.top-1);//取q栈顶指针
    return 0;
}

int outstack(stack &s,int e){
    if (s.top==s.base) {
        return 0;
    }
    e=*--s.top;//将d栈顶元素给e向下移一位
    return 1;
}

void disp(stack s){
    long int i;
    for(i=0;i<s.top-s.base;i++){
        cout<<s.base[i];
    }
    cout<<endl;
}

int main(){
    char e;
    stack s;
    initstack(s);
    putstack(s,'A');
    putstack(s,'B');
    putstack(s,'C');
    putstack(s,'D');
    cout<<"栈S为：";
    disp(s);
    cout<<"栈顶元素为：";
    e=gettop(s);
    cout<<e<<endl;
    outstack(s,e);
    cout<<"栈顶出栈后的S：";
    disp(s);
    return 0;
}

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
84
85
86
87
88
#include<iostream>
using namespace std;
const int  MAXQSIZE=6;
typedef char QElemType;

typedef  struct
{
    QElemType *base;
    int front ;
    int rear;
    
} SqQueue;

int InitQueue(SqQueue &Q)
{
    Q.base= new QElemType[MAXQSIZE];
    if(!Q.base)
        return 0;
    Q.front =Q.rear=0;
    return 1;
}
int EnQueue( SqQueue &Q,QElemType e)
{
    if((Q.rear+1)%MAXQSIZE==Q.front)//队满
    {
        cout<<"错误"<<endl;
    }
    
    Q.base[Q.rear] =e;//新元素插入队尾
    Q.rear=(Q.rear+1)%MAXQSIZE;//队尾指针向后移动一位
    return 1;
}
int lengt(SqQueue &Q)//求队长度
{
    return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
int deleteQ(SqQueue &Q,QElemType &e)
{
    if(Q.rear==Q.front)//队空
        return 0;
    e=Q.base[Q.front];//保存对头元素
    Q.front=(Q.front+1)%MAXQSIZE;//队头指针向后移动一位
    return 1;
}
int   DisQ(SqQueue Q)
{
    int m,i;
    m=lengt(Q);
    if(m==0)
        cout<<"空队列";
    if((Q.rear+1)%MAXQSIZE==Q.front)
        cout<<"队满"<<endl;
    for(i=Q.front; i%MAXQSIZE!=Q.rear;i++)
        cout<<Q.base[i];
    cout<<endl;
    return 0;
}


int main()
{
    SqQueue Q;
    QElemType e;
    InitQueue(Q);
    DisQ(Q);
    EnQueue(Q,'A');
    EnQueue(Q,'B');
    EnQueue(Q,'C');
    EnQueue(Q,'D');
    cout<<"长度=";
    cout<<lengt(Q);
    cout<<"队列为=";
    DisQ(Q);
    deleteQ(Q,e);
    cout<<"长度=";
    cout<<lengt(Q);
    cout<<"队列为=";
    DisQ(Q);
    EnQueue(Q,'E');
    cout<<"长度=";
    cout<<lengt(Q);
    cout<<"队列为=";
    DisQ(Q);
    EnQueue(Q,'F');
    cout<<"队列为=";
    DisQ(Q);
    return 0;
}

7队列

树

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
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef int InfoType;
typedef int KeyType;            //假定关键字类型为整数
typedef struct node                //结点类型
{
    KeyType key;                //关键字项
    InfoType otherinfo;     //其它数据域，InfoType视应用情况而定，下面不处理它
    struct node *lchild,*rchild;   //左右孩子指针
}BSTNode;
typedef  BSTNode  *BSTree;        //BSTree是二叉排序树的类型

//在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NULL
BSTNode *findbst(BSTree t,KeyType key){
    if(t==NULL||key==t->key)
        return t;
    if(key<t->key)
        return findbst(t->lchild,key);
    else
        return findbst(t->rchild,key);
}

void InsertBST(BSTree *T,int key)
{ //插入一个值为key的节点到二叉排序树中
    BSTNode *p,*q;
    if((*T)==NULL)
    { //树为空树
        (*T)=(BSTree)malloc(sizeof(BSTNode));
        (*T)->key=key;
        (*T)->lchild=(*T)->rchild=NULL;
    }
    else
    {
        p=(*T);
        while(p)
        {
            q=p;
            if(p->key>key)
                p=q->lchild;
            else if(p->key<key)
                p=q->rchild;
            else
            {
                cout<<endl<<"该二叉排序树中含有关键字为"<<key<<"的节点!"<<endl;
                return;
            }
        }
        p=(BSTree)malloc(sizeof(BSTNode));
        p->key=key;
        p->lchild=p->rchild=NULL;
        if(q->key>key)
            q->lchild=p;
        else
            q->rchild=p;
    }
}

BSTree CreateBST(void)
{ //输入一个结点序列，建立一棵二叉排序树，将根结点指针返回
    BSTree T=NULL;    //初始时T为空树
    KeyType key;
    cin>>key;   //读入一个关键字
    while(key)
    { //假设key=0是输入结束标志
        InsertBST(&T,key);  //将key插入二叉排序树T
        cin>>key;  //读入下一关键字
    }
    return T;       //返回建立的二叉排序树的根指针
}


void ListBinTree(BSTree T)   //用广义表示二叉树
{
    if(T!=NULL)
    {
        cout<<T->key;
        if(T->lchild!=NULL||T->rchild!=NULL)
        {
            cout<<"(";
            ListBinTree(T->lchild);
            if(T->rchild!=NULL)
                cout<<",";
            ListBinTree(T->rchild);
            cout<<")";
        }
    }
}



int main()
{
    BSTNode *findbst(BSTree t,KeyType key);
    void InsertBST(BSTree *Tptr,KeyType key);
    BSTree CreateBST();
    void ListBinTree(BSTree T);
    BSTree T;
    BSTNode *p;
    int key;
    cout<<"请输入关键字（输入0为结束标志）："<<endl;
    T=CreateBST();
    ListBinTree(T);
    cout<<endl;
    cout<<"请输入欲查找关键字:";
    cin>>key;
    p=findbst(T,key);
    if(p==NULL)
        cout<<"没有找到"<<key<<"！"<<endl;
    else
        cout<<"找到"<<key<<"！"<<endl;
    ListBinTree(p);
    cout<<endl;
    return 0;
}

5树

冒泡排序

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
#include <stdio.h>
#define MaxSize 20
typedef int KeyType;    //定义关键字类型
typedef char InfoType[10];
typedef struct          //记录类型
{
    KeyType key;        //关键字项
    InfoType data;      //其他数据项,类型为InfoType
} RecType;              //排序的记录类型定义

void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序
{
    int i,j,k;
    RecType tmp;
    for (i=1; i<n; i++)
    {
        tmp=R[i];
        j=i-1;            //从右向左在有序区R[0..i-1]中找R[i]的插入位置
        while (j>=0 && tmp.key<R[j].key)
        {
            R[j+1]=R[j]; //将关键字大于R[i].key的记录后移
            j--;
        }
        R[j+1]=tmp;      //在j+1处插入R[i]
        printf("i=%d: ",i);
        for (k=0; k<n; k++)
            printf("%d ",R[k].key);
        printf("\n");
    }
}

int main()
{
    int i,n=5;
    RecType R[MaxSize];
    KeyType a[]= {3,24,12,6,1};
    for (i=0; i<n; i++)
        R[i].key=a[i];
    printf("排序前:");
    for (i=0; i<n; i++)
        printf("%d ",R[i].key);
    printf("\n");
    InsertSort(R,n);
    printf("排序后:");
    for (i=0; i<n; i++)
        printf("%d ",R[i].key);
    printf("\n");
    return 0;
}

8冒泡

题型分类

插入

删除

合并

排序

折半查找递归算法

顺序表题型

插入

1
2
3
4
5
6
7
8
9
10
int listinsert_sq(sqlist &l,int i,et e){
    if(i<1||i>l.length+1)
        return 0;
    for (int j=l.length-1; j>=i-1; j--) {
        l.elem[j+1]=l.elem[j];
    }
    l.elem[i-1]=e;
    ++l.length;
    return 1;
}

删除

1
2
3
4
5
6
7
8
9
10
int listdelete_sq(sqlist &l,int i,et &e){
    if(i<1||i>l.length)
        return 0;
    e=l.elem[i-1];
    for (int j=i; j<=l.length-1; j++) {
        l.elem[j-1]=l.elem[j];
    }
    --l.length;
    return 1;
}

完整程序

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
#include"iostream"
using namespace std;
#define maxsize 100
typedef char et;
typedef struct{
    et *elem;
    int length;
}sqlist;

int initlist_sq(sqlist &l){
    l.elem=new et[maxsize];
    if(!l.elem)
        return 0;
    l.length=0;
    return 1;
}

int listinsert_sq(sqlist &l,int i,et e){
    if(i<1||i>l.length+1)
        return 0;
    for (int j=l.length-1; j>=i-1; j--) {
        l.elem[j+1]=l.elem[j];
    }
    l.elem[i-1]=e;
    ++l.length;
    return 1;
}

int listdelete_sq(sqlist &l,int i,et &e){
    if(i<1||i>l.length)
        return 0;
    e=l.elem[i-1];
    for (int j=i; j<=l.length-1; j++) {
        l.elem[j-1]=l.elem[j];
    }
    --l.length;
    return 1;
}

void disp_sq(sqlist l){
    if(l.length==0)
        cout<<"此顺序表为空"<<endl;
    for(int i=0;i<l.length;i++){
        cout<<l.elem[i];
    }
    cout<<endl;
}

int main(){
    et e;
    sqlist l;
    initlist_sq(l);
    disp_sq(l);
    listinsert_sq(l,1,'A');
    listinsert_sq(l,2,'B');
    listinsert_sq(l,3,'C');
    disp_sq(l);
    listdelete_sq(l,1,e);
    disp_sq(l);
    cout<<"删除的元素是："<<e<<endl;
}

1顺序

链表题型

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int listinsert(lk &l,int i,et e){
    lk p;
    p=l;
    int j=0;
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if (!p||j>i-1) {
        return 0;
    }
    lk s=new ln;
    s->date=e;//将e的值赋值给s的值域
    s->next=p->next;//新元素s的指针域指向旧元素p的指针域
    p->next=s;//将p的指针域指向s元素
    return 1;
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int listdelete(lk &l,int i,et &e){
    lk p;
    p=l;
    int j=0;
    while(p->next&&j<i-1){
        p=p->next;
        j++;
    }
    if (!(p->next)||j>i-1) {
        return 0;
    }
    lk q;
    q=p->next;//q的指针指向p的指针域
    p->next=q->next;//p的指针域指向q的指针域
    e=q->date;//将删除q的值域的值赋值给e的位置值
    delete q;
    return 1;
}

求最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void mlist(lk l){//最大值
    lk s=new ln;
    lk p=l->next;
    s->data=p->data;
    while(p){
        if(s->data<=p->data){
            s->data=p->data;
            p=p->next;
        }
        else{
            p=p->next;
        }
    }
    cout<<"最大值为："<<s->data<<endl;
}

逆序输出

1
2
3
4
5
6
7
8
9
10
11
12
int rlist(lk &l){//逆序
    lk p=l->next;
    lk q;
    l->next=NULL;
    while(p){
        q=p->next;
        p->next=l->next;
        l->next=p;
        p=q;
    }
    return 1;
}

合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void mergelist(lk &la,lk &lb,lk &lc){
    lk pa=la->next;
    lk pb=lb->next;
    lk pc=lc=la;
    while(pa&&pb){
        if(pa->data<pb->data){
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else{
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
    }
    pc->next=pa?pa:pb;
}

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int max(lk &la){
    lk pa=la->next;//将pa指针指向la表的头结点
    lk ps=la;//ps的初始值指向la的头结点
    int i=1,k=0;//定义两个计数变量
    ps->data=pa->data;//给ps的数据域赋初值
    while(pa){
        if(pa->data>=ps->data){
            ps->data=pa->data;//将ps的数据域指向pa的数据域
            pa=pa->next;//向下移一位
            k=i;//满足条件用k记录
            i++;//循环计数+1
        }
        else{
            pa=pa->next;
            i++;//循环计数+1
        }
    }
    cout<<"最大元素是："<<ps->data<<endl;
    cout<<"位置是第"<<k<<"个元素"<<endl;
    return 1;
}

折半查找

1
2
3
4
5
6
7
8
9
10
11
12
13
int xfind(lk st,keyt t, int low, int high){
    if(low<=high){
        int mid=(low+high)/2;
        if(st.elem[mid].key==t)
            return mid;
        else if (st.elem[mid].key<t)
            return (xfind(st, t, mid+1, high));
        else
            return (xfind(st, t, low, mid-1));
    }
    else
        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
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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include<iostream>
using namespace std;

typedef struct ln{
    int data;
    struct ln *next;
}*lk;

int initlist(lk &l){
    l=new ln;
    l->next=NULL;
    return 1;
}

int insertlist(lk &l,int i,int e){
    lk p=l;//错写成p=l->next
    int j=0;
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if(!p||j>i-1){
        return 0;
    }
    lk s=new ln;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return 1;
}

int deletelist(lk &l,int i,int &e){
    lk p=l;//错写成p=l->next
    int j=0;
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if(!p||j>i-1){
        return 0;
    }
    lk q=p->next;
    p->next=q->next;
    e=q->data;
    delete q;
    return 1;
}

int margeinlist(lk &la,lk &lb,lk &lc){//合并
    lk pa=la->next;
    lk pb=lb->next;
    lk pc=lc=la;
    while(pa&&pb){
        if(pa->data<pb->data){
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else{
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
    }
    pc->next=pa?pa:pb;
    return 1;
}

int rlist(lk &l){//逆序
    lk p=l->next;
    lk q;
    l->next=NULL;
    while(p){
        q=p->next;
        p->next=l->next;
        l->next=p;
        p=q;
    }
    return 1;
}

void mlist(lk l){//最大值
    lk s=new ln;
    lk p=l->next;
    s->data=p->data;
    while(p){
        if(s->data<=p->data){
            s->data=p->data;
            p=p->next;
        }
        else{
            p=p->next;
        }
    }
    cout<<"最大值为："<<s->data<<endl;
}

void disp(lk &l){
    lk p=l->next;
    if(!p){
        cout<<"空表"<<endl;
    }
    while(p){
        cout<<p->data;
        p=p->next;
    }
    cout<<endl;
}

int main(){
    lk la,lb,lc;
    int e;
    initlist(la);
    initlist(lb);
    insertlist(la, 1, 1);
    insertlist(la, 2, 5);
    insertlist(la, 3, 7);
    insertlist(la, 4, 9);
    insertlist(lb, 1, 2);
    insertlist(lb, 2, 3);
    insertlist(lb, 3, 6);
    cout<<"la的元素是：";
    disp(la);
    cout<<"lb的元素是：";
    disp(lb);
    deletelist(la, 2, e);
    cout<<"删除的元素是："<<e<<endl;
    margeinlist(la, lb, lc);
    cout<<"合并后的元素是：";
    disp(lc);
    rlist(lc);
    cout<<"反序输出元素顺序为：";
    disp(lc);
    mlist(lc);
}
#include <iostream>
using namespace std;
typedef char et;
typedef struct ln{
    et date;
    struct ln *next;
}ln,*lk;

int initlist(lk &l){
    l=new ln;
    l->next=NULL;
    return 1;
}

int listinsert(lk &l,int i,et e){
    lk p;
    p=l;
    int j=0;
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if (!p||j>i-1) {
        return 0;
    }
    lk s=new ln;
    s->date=e;//将e的值赋值给s的值域
    s->next=p->next;//新元素s的指针域指向旧元素p的指针域
    p->next=s;//将p的指针域指向s元素
    return 1;
}

int listdelete(lk &l,int i,et &e){
    lk p;
    p=l;
    int j=0;
    while(p->next&&j<i-1){
        p=p->next;
        j++;
    }
    if (!(p->next)||j>i-1) {
        return 0;
    }
    lk q;
    q=p->next;//q的指针指向p的指针域
    p->next=q->next;//p的指针域指向q的指针域
    e=q->date;//将删除q的值域的值赋值给e的位置值
    delete q;
    return 1;
}

void disp(lk l){
    lk p=l->next;
    if (!p) {
        cout<<"此链表为空"<<endl;
    }
    while (p) {
        cout<<p->date;
        p=p->next;
    }
    cout<<endl;
}

int main(){
    lk l;
    et e;
    initlist(l);
    disp(l);
    listinsert(l, 1, 'A');
    listinsert(l, 2, 'B');
    listinsert(l, 3, 'C');
    disp(l);
    listdelete(l, 2, e);
    cout<<"删除的元素是："<<e<<endl;
    disp(l);
    return 0;
}

2链表

完整代码(查找)

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
#include <iostream>
using namespace std;

typedef struct ln{
    int data;
    struct ln *next;
}*lk;

int inilist(lk &l){
    l=new ln;
    l->next=NULL;
    return 1;
}

int listinsert(lk &l,int i,int e){
    lk p=l;//定义一个指针p指向l的头结点
    int j=0;//位置的初始值
    while (p&&j<i-1) {
        p=p->next;//当满足条件是p指向下一位
        j++;//位置值加一
    }
    if (!p||j>i-1) {
        return 0;
    }
    lk s=new ln;//建立一个节点s
    s->data=e;//s节点的数据域等于e的数值
    s->next=p->next;//s的next域指向p的next域
    p->next=s;//p的next域指向s节点
    return 1;
}

int max(lk &la){
    lk pa=la->next;//将pa指针指向la表的头结点
    lk ps=la;//ps的初始值指向la的头结点
    int i=1,k=0;//定义两个计数变量
    ps->data=pa->data;//给ps的数据域赋初值
    while(pa){
        if(pa->data>=ps->data){
            ps->data=pa->data;//将ps的数据域指向pa的数据域
            pa=pa->next;//向下移一位
            k=i;//满足条件用k记录
            i++;//循环计数+1
        }
        else{
            pa=pa->next;
            i++;//循环计数+1
        }
    }
    cout<<"最大元素是："<<ps->data<<endl;
    cout<<"位置是第"<<k<<"个元素"<<endl;
    return 1;
}

int main(){
    lk la;//定义三个表
    inilist(la);//对表la的初始化
    listinsert(la, 1, 2);//向la表中插入数据
    listinsert(la, 2, 3);
    listinsert(la, 3, 5);
    listinsert(la, 4, 7);
    listinsert(la, 5, 10);
    listinsert(la, 6, 9);
    listinsert(la, 7, 8);
    max(la);
}

3查找

完整代码(折半查找)

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
//
//  main.cpp
//  实验六数据结构
//
//  Created by PC-MAC on 2018/12/3.
//  Copyright © 2018 PC-MAC. All rights reserved.
//

#include"iostream"
using namespace std;
const int tmax=10;
typedef int keyt;
typedef struct{
    keyt key;
}elemtype;//每行内容

typedef struct{
    elemtype *elem;
    int length;
}lk;

int find(lk st,keyt key){
    int i;
    st.elem[0].key=key;
    for(i=st.length;st.elem[i].key!=key;i--);
    return i;
}

int twofind(lk st,keyt key){
    int low,high,mid;
    low=1;
    high=st.length;
    while(low<=high){
        mid=(low+high)/2;
        if(st.elem[mid].key==key)
            return mid;
        else if(st.elem[mid].key>key)
            high=mid-1;
        else
            low=mid+1;
    }
    return 0;
}

int xfind(lk st,keyt t, int low, int high){
    if(low<=high){
        int mid=(low+high)/2;
        if(st.elem[mid].key==t)
            return mid;
        else if (st.elem[mid].key<t)
            return (xfind(st, t, mid+1, high));
        else
            return (xfind(st, t, low, mid-1));
    }
    else
        return 0;
}

int main(){
    keyt a[]={0,13,24,35,32,65,19,7,74,20,38};
    lk t;
    t.elem=new elemtype[tmax];
    t.length=10;
    for(int i=1;i<=10;i++){
        t.elem[i].key=a[i];
    }
    cout<<"查找到的元素位置为："<<find(t, 35)<<endl;
    lk s;
    s.elem=new elemtype[tmax];
    s.length=10;
    keyt b[]={0,2,4,6,8,10,12,14,16,18,20};
    for(int k=1;k<=10;k++){
        s.elem[k].key=b[k];
    }
    cout<<"折半查找到的元素位置为："<<twofind(s, 14)<<endl;
    int i, j;
    keyt arr[10];
    for (i = 0; i < 10; i++)
    {
        arr[i] = i * 2;
    }
    cout << "输入查找数字:";
    cin >> j;
    lk P;
    P.elem = new elemtype;
    P.length = 10;
    for (int j = 1; j <= 10; j++)
    {
        P.elem[j].key = arr[j];
    }
    cout<<"递归折半查找到的元素位置为："<<xfind(P, j, 0, 10)<<endl;
    return 0;
}

4折半

TheMrxk个人博客 wechat
欢迎您扫一扫上面的本人微信号，获取更多资源！