太原理工大学数据结构实验报告完整版_改用邻接表的方式存储图,试编一程序实现上述算法。 顶点表nodelist的每个元素包含

实验名称

实验一  线性表

实验日期

问题描述

1. 设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。

2、用单链表 ha 存储多项式A（x）=a0+a1x 1 +a2x 2 +…+anx n (其中aI为非零系数)，用单链表 hb 存储多项式B（x）=b0+b1x 1 +b2x 2 +…+bmx m (其中 bj为非零系数)，要求计算C（x）= A（x）+B（x），结果存到单链表 hc 中。试写出程序。

3、设有 n 个人围坐在一个圆桌周围，现从第 s 个人开始报数，数到第 m 的人出列，然后从出列的下一个人重新开始报数，数到 m 的人又出列，如此重复，直到所有的人全部出列为止。Josephus 问题是：对于任意给定的 n，m，s，求出按出列次序得到的 n 个人员的顺序表。

输    入

1、初始字符串，插入位置，插入字符，删除字符。

顺序表A的长度：5

顺序表A的递增有序数据元素：1 3 5 7 9

插入的数据元素x:4

2、请输入第一个多项式的系数和指数

请输入多项式的项数：4

输入第1项的系数：1

输入第1项的指数：2

输入第2项的系数：2

输入第2项的指数：3

输入第3项的系数：3

输入第3项的指数：4

输入第4项的系数：4

输入第4项的指数：6

请输入第二个多项式的系数和指数

请输入多项式的项数：3

输入第1项的系数：2

输入第1项的指数：4

输入第2项的系数：3

输入第2项的指数：5

输入第3项的系数：4

输入第3项的指数：6

3、依次输入n s m:5 3 1

输    出

1、新建立的链表

插入数据元素x后的顺序表A：1 3 4 5 7 9

2、输入的第一个多项式是：

1*X^2 2*X^3 3*X^4 4*X^6

输入的第二个多项式是:

2*X^4 3*X^5 4*X^6

两个多项式的和为：1*X^2 2*X^3 5*X^4 3*X^5 8*X^6

3、输出排序:3 4 5 1 2

存储结构

1. 采取顺序存储结构
2. 采取链式存储结构
3. 采取单项循环链表

算法基本思想

1、先建立一个待插入的结点，然后依次与与链表中的各结点的数据比较大小，找到插入该结点的位置，最后插入该结点。

2、获取A、B两个多项式，每获取一个就建立一个结点插入到头结点之后。形成一个多项式单链表。创建头结点 C 将A，B 多项式串联起来。在操作过程中，一定要将头结点C赋值给 pc ，通过pc连接多项式。因为最后要返回头结点C。A，B多项式比较指数的大小，小项直接接在pc的后面，若相等，计算系数之和，不为零，保存下来。为零，则跳过这个多项式。最后，将A，B多余的多项式，直接串联在pc后就完成了。返回头结点C。

3、 对于n个人，每一次出列一个人，余下的n-1个人仍然是一个Josephus问题，因此可以使用递归的方式，每次出列一个人，直到余下最后一个人。

源程序代码

1、第一题代码如下：

#include <stdio.h>

// 定义顺序表的最大大小

#define MAX_SIZE 100

// 定义顺序表结构体

typedef struct {

    int data[MAX_SIZE];

    int length;

} SeqList;

// 插入元素并保持有序

void insertElement(SeqList *list, int x) {

    int i, j;

    // 寻找插入位置

    for (i = 0; i < list->length && list->data[i] < x; i++);

    // 向后移动元素腾出插入位置

    for (j = list->length; j > i; j--) {

        list->data[j] = list->data[j - 1];

    }

    // 插入元素

    list->data[i] = x;

    // 长度加一

    list->length++;

}

int main() {

    SeqList myList;

    int size, element;

    // 获取顺序表大小

    printf("请输入顺序表长度: ");

    scanf("%d", &size);

    // 获取顺序表元素

    printf("请以递增的顺序输入顺序表中包含的元素:\n");

    for (int i = 0; i < size; i++) {

        printf("元素 %d: ", i + 1);

        scanf("%d", &myList.data[i]);

    }

    myList.length = size;

    // 获取要插入的元素

    printf("输入要插入的元素: ");

    scanf("%d", &element);

    // 插入元素并保持有序

    insertElement(&myList, element);

    // 输出插入后的顺序表

    printf("插入后的顺序表: ");

    for (int i = 0; i < myList.length; i++) {

        printf("%d ", myList.data[i]);

    }

    printf("\n");

    return 0;

}

2、第二题代码如下：

#include<stdio.h>

#include<stdlib.h>

typedef struct list{

int c;//系数

int e;//指数

struct list *next;

}list,*Linklist;

//创建多项式

Linklist creatPolyn(){

Linklist  head,p,q;

int m;

head = (Linklist)malloc(sizeof(list));

head->next= NULL;

q = head;

printf("请输入多项式的项数：");

scanf("%d",&m);

for(int i=0;i<m;i++){

p = (Linklist)malloc(sizeof(list));

printf("输入第%d项的系数：",i+1);

scanf("%d",&p->c);

printf("输入第%d项的指数：",i+1);

scanf("%d",&p->e);

p->next = q->next;

q->next = p;

q = q->next;

}

return head;

}

//多项式相加

Linklist AddPolyn(Linklist pa,Linklist pb){

Linklist a,b,pc,c;

a = pa;//保存pa的头结点

//printf("pa->c = %d pa->e = %d\n",pa->c,pa->e);

b = pb;//保存pb的头结点

c = (Linklist)malloc(sizeof(list)); //给 C 申请一个空间

c->next = NULL; // 生成头结点

pc = c;

while(a&&b){

int m,n,sum;

m=a->e; n=b->e;

if(m>n){

pc->next = b;

pc = pc->next;

b = b->next;

//printf("b多项式指数小  %d*X^%d\n",pc->c,pc->e);

}

else if(m == n){

sum = a->c + b->c;

if(sum!=0){

a->c = sum;

pc->next = a;

pc=pc->next;

//printf("多项式指数一样大  %d*X^%d\n",pc->c,pc->e);

}

a = a->next;

b = b->next;

}

else{

pc->next = a;

pc = pc->next;

a = a->next;

//printf("a多项式指数小  %d*X^%d\n",pc->c,pc->e);

}

}

if(a!=NULL){

pc->next = a;

}

if(b!=NULL){

pc->next = b;

}

return c;

}

void printList(Linklist L){

while(L != NULL){

printf("%d*X^%d ",L->c,L->e);

L = L->next;

}

printf("\n");

}

int main(){

Linklist pa,pb,pc;

printf("请输入第一个多项式的系数和指数\n");

pa = creatPolyn();

printf("请输入第二个多项式的系数和指数\n");

pb = creatPolyn();

printf("输入的第一个多项式是：\n");

printList(pa->next);

printf("输入的第二个多项式是:\n");

printList(pb->next);

pc = AddPolyn(pa->next,pb->next);

printf("两个多项式的和为：");

printList(pc->next);

return 0;

}

3、第三题代码如下：

#include <iostream>

#include <cstdio>

#include <stdlib.h>

#include <malloc.h>

using namespace std;

typedef struct list

{

int date;

struct list *next;

}list,*linklist;

list* l;

void intlist(linklist &l,int n)

{

l = (linklist)malloc(sizeof(list));

l->next = l;

l->date = 1;

linklist p;

for (int i = n; i > 1; i--)

{

p= (linklist)malloc(sizeof(list));

p->next = l->next;

l->next = p;

p->date = i;

}

}

void out(linklist l, int s, int m,int n)

{

list* p = l;

int i ;

for (i = 1;; i++)

{

if (p->date == s)

{

break;

}

p = p->next;

}

if (m != 1)

{

for (int j = 1; j <= n; j++)

{

if (j == 1)

{

for (int h = 1; h < m - 1; h++)

{

p = p->next;

}

}

else

{

for (int h = 1; h < m; h++)

{

p = p->next;

}

}

cout << p->next->date << " ";

p->next = p->next->next;

}

}

else

{

for (int j = 1; j <= n; j++)

{

cout << p->date << " ";

p = p->next;

}

}

}

int main()

{

while (1)

{

int n, s, m;

cout << "依次输入n s m:";

cin >> n >> s >> m;

if (n < s||n<=0||s<=0||m<=0)

{

cout << "输入错误,请重试!" << endl;

continue;

}

intlist(l, n);

cout << "输出排序:";

out(l, s, m, n);

cout << "\n";

}

return 0;

}

心得体会(遇到的问题和解决方法)

1、问题：链表的节点操作理解困难。

解决方法：我发现在链表操作中，理解节点的插入、删除和逆序等操作对于初学者来说可能有些抽象。通过仔细阅读教材、参考相关的代码示例以及尝试编写简单的代码进行练习，逐步加深对节点操作的理解。

2、问题：节点指针的理解和管理。

解决方法：链表中的指针概念对我来说是一个挑战，特别是在节点指针的创建、连接和释放等方面。我通过画图辅助理解节点之间的指针连接关系，并逐步编写简单的链表操作代码，加深了对指针的理解和掌握。

3、问题：逆序输出链表困难。

解决方法：链表的逆序输出在刚开始时让我感到有些困难。我尝试过逐个节点反转指针的方法，但在实践中遇到了一些错误。后来，我重新理解了节点之间的指针关系，采用了迭代或递归的方式，成功实现了链表的逆序输出。

我的学习经历让我深刻意识到，在编程的学习过程中，遇到困难是正常的。解决问题需要耐心和细心，多方查找资料、思考和尝试是解决问题的有效方法。通过实践，我不仅加深了对线性表数据结构的理解，还提高了自己的分析问题和解决问题的能力。这种学习经历对于我日后在编程和解决实际问题中将会是非常有益的。

心得体会(遇到的问题和解决方法)

问题：递归和非递归算法的思路不同，如何将递归算法转化为非递归算法？

解决方法：可以使用栈(stack)来模拟递归过程，将要递归访问的节点依次入栈。在遍历栈的过程中，模拟递归函数的调用和返回过程，直到找到目标节点或者栈为空。

问题：如何处理节点出栈后的情况？

解决方法：在处理节点出栈后的情况时，需要注意区分访问节点和递归访问节点两种情况。对于访问节点的情况，可以将其计数或者进行其他操作；对于递归访问节点的情况，需要将其子节点入栈以便后续访问。

心得体会：递归算法具有简单明了、代码精炼的特点，但是容易陷入栈溢出等问题；非递归算法虽然相对复杂一些，但是可以提高运行效率并且避免栈溢出问题。在实际应用中，需要根据具体情况选择合适的算法实现方式。

实验名称

实验三  图

实验日期

2023年12月04日

问题描述

1、采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。

2、试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点 Vi到 Vj顶点的路径(i≠j)。

3、在上述例题中，如改用邻接表的方式存储图，试编一程序实现上述算法。顶点表 nodelist 的每个元素包含四个字段：

其中 mark 为布尔类型，用来标记顶点是否被访问过。开始时，所有元素的 mark 字段为 false，每访问过一个顶点，则 mark 字段置为 true。info 为顶点值，pre 为访问路径上该顶点的前驱顶点的 序号，out 指向该顶点的出边表。

输    入

1、输入：输入顶点数: 2

输入顶点 0 的值: 1

输入顶点 1 的值: 1

输入边 (输入 -1 结束): 2 1

输入边 (输入 -1 结束): 2 1

输入边 (输入 -1 结束): -1

1. 输入：

请输入要构造的图的顶点总数.

2

请按照下面的提示构造图。

请输入'V1'指向的所有顶点，结束请输入 0

1 0

请输入'V2'指向的所有顶点，结束请输入 0

3 0

请输入要查询的顶点w,v

1,2

请输入要查询的顶点w,v

1,3

1. 输入：

输入顶点数: 3

输入顶点 0 的值: 0

输入顶点 1 的值: 1

输入顶点 2 的值: 2

输入有向边 (输入 -1 结束): 1 2

输入有向边 (输入 -1 结束): 1 3

输入有向边 (输入 -1 结束): 3 1

输入有向边 (输入 -1 结束): -1

输入起始顶点和目标顶点 (用空格分隔): 1 3

输    出

2、输出：

顶点V1，与顶点V2之间不连通。

顶点V1，与顶点V3之间不连通。

3、输出：

存在路径从顶点 1 到顶点 3

路径: 3 <- 1

存储结构

图采用邻接矩阵的方式存储，遍历采用深度优先搜索遍历。

算法基本思想

建立无向图，采用深度优先搜索的方法，从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中说有和v有路径相通的顶点都被访问到；

若此时图中上有顶点未被访问到，则另选一个未曾被访问的顶点作为起始点，重复上述过程。在此过程中，记录下连通分量的个数。

源程序代码

1、第一题代码如下：

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX_VERTEX_NUM 20

typedef struct ArcNode {

    int adjvex;

    struct ArcNode *nextarc;

} ArcNode;

typedef struct VNode {

    int data;

    ArcNode *firstarc;

} VNode;

typedef struct {

    VNode adjlist[MAX_VERTEX_NUM];

    int vexnum, arcnum;

} ALGraph;

void CreateALGraph(ALGraph *G) {

    printf("输入顶点数: ");

    scanf("%d", &G->vexnum);

    G->arcnum = 0;

    for (int i = 0; i < G->vexnum; ++i) {

        printf("输入顶点 %d 的值: ", i);

        scanf("%d", &G->adjlist[i].data);

        G->adjlist[i].firstarc = NULL;

    }

    int start, end;

    while (1) {

        printf("输入边 (输入 -1 结束): ");

        scanf("%d", &start);

        if (start == -1) {

            break;

        }

        scanf("%d", &end);

        ArcNode *arc1 = (ArcNode *)malloc(sizeof(ArcNode));

        arc1->adjvex = end;

        arc1->nextarc = G->adjlist[start].firstarc;

        G->adjlist[start].firstarc = arc1;

        ArcNode *arc2 = (ArcNode *)malloc(sizeof(ArcNode));

        arc2->adjvex = start;

        arc2->nextarc = G->adjlist[end].firstarc;

        G->adjlist[end].firstarc = arc2;

        G->arcnum += 2;

    }

}

void DFS(ALGraph *G, int v, bool visited[]) {

    visited[v] = true;

    ArcNode *p = G->adjlist[v].firstarc;

    while (p != NULL) {

        if (!visited[p->adjvex]) {

            DFS(G, p->adjvex, visited);

        }

        p = p->nextarc;

    }

}

int CountConnectedComponents(ALGraph *G) {

    bool visited[MAX_VERTEX_NUM];

    int count = 0;

    for (int i = 0; i < G->vexnum; ++i) {

        visited[i] = false;

    }

    for (int i = 0; i < G->vexnum; ++i) {

        if (!visited[i]) {

            DFS(G, i, visited);

            count++;

        }

    }

    return count;

}

int main() {

    ALGraph G;

    CreateALGraph(&G);

    int connectedComponents = CountConnectedComponents(&G);

    printf("连通分量个数: %d\n", connectedComponents);

    return 0;

}

2、第二题代码如下：

#include <stdio.h>

#include <malloc.h>

#include <Windows.h>

int n;

//定义结构体

typedef struct arcNode

{

int position;

struct arcNode *next;

}ArcNode, *ArcNode_;

typedef struct vNode

{

int mark;

ArcNode *first;

}VNode, *VNode_;

//定义函数 ，构造数

VNode_ Structure()

{

VNode_ Chart;

int i, j, k;

ArcNode_ p, q;

printf("\n请输入要构造的图的顶点总数.\n");

scanf("%d", &n);

while(n<1)

{

printf("录入的数据有误！请重新输入。\n");

scanf("%d", &n);

}

Chart = (VNode_)malloc(n*sizeof(VNode));

printf("请按照下面的提示构造图。\n\n");

for(i=0; i<n; ++i)

{

printf("请输入'V%d'指向的所有顶点，结束请输入 0 \n", i+1);

scanf("%d", &k);

if(k != 0)

{

q = (ArcNode_)malloc(sizeof(ArcNode));

q->position = k-1;

(Chart+i)->first = q;

p = q;

scanf("%d", &k);

while(k != 0)

{

q = (ArcNode_)malloc(sizeof(ArcNode));

q->position = k-1;

p->next = q;

p = q;

scanf("%d", &k);

}

p->next = NULL;

}

else

{

Chart[i].first = NULL;

}

}

return Chart;

}

//定义函数用于查找

void DFS(VNode_ Chart, int t)

{

ArcNode_ q;

if(Chart[t].mark == 0)

{

Chart[t].mark = 1;

for(q=Chart[t].first; q != NULL; q=q->next)

{

DFS(Chart, q->position);

}

}

}

void Initialize(VNode_ Chart)

{

int i;

for(i=0; i < n; i++)

{

(Chart+i)->mark = 0;

}

}

void End(VNode_ Chart)

{

int i;

ArcNode_ p, q;

for(i=0;i<n;i++)

{

p = Chart[i].first;

while(p!=NULL)

{

q = p;

p = p->next;

free(q);

}

}

free(Chart);

}

//定义主函数

int main()

{

int i=0;

int count=0;

int w, v;

VNode_ Chart = Structure();

while(1){printf("请输入要查询的顶点w,v\n");

scanf("%d,%d", &w, &v);

DFS(Chart, w-1);

if(Chart[v-1].mark)

{

printf("顶点V%d，与顶点V%d之间连通。", w, v);

}

else

{

printf("顶点V%d，与顶点V%d之间不连通。", w, v);

}

printf("\n\n");

End(Chart);}

}

3、第三题代码如下：

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX_VERTEX_NUM 20

// 边表结点

typedef struct ArcNode {

    int adjvex;               // 邻接顶点的序号

    struct ArcNode *nextarc;  // 指向下一个邻接顶点的指针

} ArcNode;

// 顶点表结点

typedef struct {

    int info;          // 顶点值

    bool mark;         // 是否被访问过的标记

    int pre;           // 访问路径上该顶点的前驱顶点的序号

    ArcNode *out;      // 指向该顶点的出边表

} VertexNode;

// 图的邻接表

typedef struct {

    VertexNode nodelist[MAX_VERTEX_NUM];  // 顶点表

    int vexnum, arcnum;                   // 顶点数和边数

} ALGraph;

// 创建有向图的邻接表

void CreateALGraph(ALGraph *G) {

    printf("输入顶点数: ");

    scanf("%d", &G->vexnum);

    G->arcnum = 0;

    for (int i = 0; i < G->vexnum; ++i) {

        printf("输入顶点 %d 的值: ", i);

        scanf("%d", &G->nodelist[i].info);

        G->nodelist[i].mark = false;

        G->nodelist[i].pre = -1;  // 初始前驱为-1

        G->nodelist[i].out = NULL;

    }

    int start, end;

    while (1) {

        printf("输入有向边 (输入 -1 结束): ");

        scanf("%d", &start);

        if (start == -1) {

            break;

        }

        scanf("%d", &end);

        // 创建边表结点

        ArcNode *arc = (ArcNode *)malloc(sizeof(ArcNode));

        arc->adjvex = end;

        arc->nextarc = G->nodelist[start].out;

        G->nodelist[start].out = arc;

        G->arcnum++;

    }

}

// 深度优先搜索

bool DFS(ALGraph *G, int start, int target) {

    G->nodelist[start].mark = true;

    if (start == target) {

        return true;  // 找到目标顶点

    }

    ArcNode *p = G->nodelist[start].out;

    while (p != NULL) {

        if (!G->nodelist[p->adjvex].mark && DFS(G, p->adjvex, target)) {

            G->nodelist[p->adjvex].pre = start;

            return true;

        }

        p = p->nextarc;

    }

    return false;

}

// 判断是否存在路径

bool hasPath(ALGraph *G, int start, int target) {

    for (int i = 0; i < G->vexnum; ++i) {

        G->nodelist[i].mark = false;

        G->nodelist[i].pre = -1;

    }

    return DFS(G, start, target);

}

int main() {

    ALGraph G;

    CreateALGraph(&G);

    int start, target;

    printf("输入起始顶点和目标顶点 (用空格分隔): ");

    scanf("%d %d", &start, &target);

    if (hasPath(&G, start, target)) {

        printf("存在路径从顶点 %d 到顶点 %d\n", start, target);

        // 输出路径

        printf("路径: %d", target);

        int pre = G.nodelist[target].pre;

        while (pre != -1) {

            printf(" <- %d", pre);

            pre = G.nodelist[pre].pre;

        }

        printf("\n");

    } else {

        printf("不存在路径从顶点 %d 到顶点 %d\n", start, target);

    }

    return 0;

}

心得体会(遇到的问题和解决方法)

问题：如何构建邻接表？

解决方法：可以通过创建节点类(Node)和顶点表(nodelist)来构建邻接表。每个节点存储一个顶点及其所有的邻居节点。

问题：如何处理有向图的邻接表？

解决方法：在构建邻接表时，对于有向图，需要考虑边的方向。即一个顶点的邻居节点只能指向它的后继节点。

问题：DFS中如何递归访问节点的邻居节点？

解决方法：在DFS中，可以使用循环来遍历节点的邻居节点，逐个进行递归访问。

心得体会：使用邻接矩阵来存储图和边，但是程序本身过长，空间复杂度较大。当一个图的顶点数目较多时，就会使用算法的运行时间变得很长。经过此次试验我熟悉了图的存储结构，掌握了有关算法的实现，了解了图的运用，学会了通过使用图来解决一些问题。进一步理解了图的两种遍历：DFS和BFS，各有其优点，应该根据实际问题的不同选择更有效的遍历方法，同时加深对邻接链表的理解。

实验名称

实验四  查找和排序

实验日期

2023年12月11日

问题描述

1.编写程序实现下面运算：在二叉排序树中查找关键字为key的记录。

2.试将折半查找的算法改写成递归算法

3.设计一个用链表表示的直接选择排序算法，并用程序实现。

4.对N个关键字取整数的记录进行整序，以使所有关键字为非负数的记录排在关键字为负数的记录之前，要求使用最少的附加空间，且算法的时间复杂度为O(N)。

输    入

1.输入二叉树的结点和查找的关键字

2.关键字序列，要查找的关键字key

3.输入未排序好的数组。

输    出

1.输出查找成功和所找到的记录，或者查找不成功

2.输出一个初始化后顺序查找表，关键字key对应的记录的位置

3.输出排序好的数字，由小到大。

存储结构

1.按二叉排序树的方法存储。

2.线性存储

3.链式存储。

算法基本思想

1.先建立二叉排序树，利用二叉排序树的顺序进行查找，找到结果后输出，查找不成功输出说明

2.折半查找：递归算法，用下标low和high分别标记查找区间的两端，mid为区间中间点位置，如果要查找关键字等于中间点位置关键字，则查找成功，返回关键字对应记录的位置，如果要查找关键字大于中间点位置关键字，则修改low=mid+1，继续查找，否则修改high=mid-1并继续查找，若low大于high，则查找不成功，返回0；输出记录位置

3.已知待排序初始序列用单链表存贮，头指针head指向第一个结点，从这个待排序列中找出最小结点，插入head之后，用r来指示。r以前为已排序序列，r以后为未排序序列。再从未排序序列中找出最小结点插入r的后面，让r指向这个结点。反复执行这个过程，直到排好序。

源程序代码

1. 第一题代码如下：

#include <stdio.h>

#include <stdlib.h>

#define ENDKEY 0

typedef int KeyType;

typedef struct  node

{

    KeyType  key ; /*关键字的值*/

    struct node  *lchild,*rchild;/*左右指针*/

}BSTNode, *BSTree;

void InsertBST(BSTree *bst, KeyType key)

/*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/

{

    BSTree s;

    if (*bst == NULL)/*递归结束条件*/

    {

        s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/

        s-> key=key;

        s->lchild=NULL;

        s->rchild=NULL;

        *bst=s;

    }

    else

    if (key < (*bst)->key)

        InsertBST(&((*bst)->lchild), key);/*将s插入左子树*/

    else

    if (key > (*bst)->key)

        InsertBST(&((*bst)->rchild), key); /*将s插入右子树*/

}

void  CreateBST(BSTree  *bst)

/*从键盘输入元素的值，创建相应的二叉排序树*/

{

    KeyType key;

    *bst=NULL;

    scanf("%d", &key);

    while (key!=ENDKEY)   /*ENDKEY为自定义常量*/

    {

        InsertBST(bst, key);

        scanf("%d", &key);

    }

}

void  PreOrder(BSTree root)

/*中序遍历二叉树, root为指向二叉树根结点的指针*/

{

    if (root!=NULL)

    {

        PreOrder(root->lchild);  /*中序遍历左子树*/

        printf("%d  ",root->key);  /*输出结点*/

        PreOrder(root->rchild);  /*中序遍历右子树*/

    }

}

/*

BSTree  SearchBST(BSTree bst, KeyType key)

{

    if (!bst)

        return NULL;

    else

        if (bst->key == key)

            return bst;/ *查找成功* /

        else

            if (bst->key > key)

                return SearchBST(bst->lchild, key);/ *在左子树继续查找* /

            else

                return SearchBST(bst->rchild, key);/ *在右子树继续查找* /

}*/

BSTree  SearchBST(BSTree bst, KeyType key)

{

    BSTree q;

    q=bst;

    while(q)

    {

        if (q->key == key)

            return q;  /*查找成功*/

        if (q->key > key)

            q=q->lchild;  /*在左子树中查找*/

        else

            q=q->rchild;  /*在右子树中查找*/

    }

    return NULL; /*查找失败*/

}/*SearchBST*/

int main()

{

    BSTree T;

    int k;

    BSTree result;

    printf("建立二叉排序树，请输入序列以0结束:\n");

    CreateBST(&T);

    printf("先序遍历输出序列为:");

    PreOrder(T);

    printf("\n请输入要查找的元素:");

    fflush(stdin);

    scanf("%d",&k);

    result = SearchBST(T,k);

    if (result != NULL)

        printf("已查到");

    else

        printf("未找到!\n");

}

1. 第二题代码如下：

#include <bits/stdc++.h>

int Search(int* a, int k, int low, int hight)

{

    int mid;

    if (low > hight)

    {

        return 0;

    }

    mid = (low + hight) / 2;

    if (a[mid] == k)

    {

        return (mid + 1);

    }

    else if (a[mid] > k)

    {

        return Search(a, k, low, mid - 1);

    }

    else

    {

        return Search(a, k, mid + 1, hight);

    }

}

int main()

{

    system("color f0");

    int i, n, key, position;

    printf("你有多少个数据要输入：\n");

    scanf("%d", &n);

    int p[n];

    printf("请按递增序列输入你的数据（整型变量）：\n");

    scanf("%d", &p[0]);

    for (i = 1; i < n; i++)

    {

            scanf("%d", &p[i]);

        while (p[i] < p[i - 1])

        {

            printf("你输入的数据不合理，请重新输入：\n");

            scanf("%d", &p[i]);

        }

    }

    printf("请输入你要查找的数据：\n");

    scanf("%d", &key);

    position = Search(p, key, 0, n - 1);

    if (position == 0)

    {

        printf("没有找到你要查找的数据！\n");

    }

    else

    {

        printf("你所查找的数据位于原有序表的第%d个位置！\n", position);

    }

    system("pause");

    return 0;

}

1. 第三题代码如下：

#include<stdio.h>

#include<malloc.h>

void sort(int *a, int n){

    int i=0;

    int j=n-1;

    int t;

    while(i<=j){

        while(i<n&&a[i]>=0)  i++;

        while(j>=0&&a[j]<0)  j--;

        if(i<j){

            t=a[i];

            a[i]=a[j];

            a[j]=t;

            i++;

            j--;

        }

    }

}

int main(){

       int n,i;

       int* p;

       printf("请输入n:\n");

       scanf("%d",&n);

       while(n<2){

            printf("您的输入有误，请重新输入：\n");

            scanf("%d", &n);

       }

       p=(int*)malloc(n*sizeof(int));

       printf("请输入一个序列:\n");

       for(i=0;i<n; i++)  scanf("%d", &p[i]);

       sort(p,n);

       printf("排序后的序列为:\n");

       for(i=0;i<n;i++) printf("%-4d",p[i]);

       printf("\n");

}

1. 第四题代码如下：

#include<bits\stdc++.h>

using namespace std;

void sort(int *a, int n)

{

    int i=0;

    int j=n-1;

    int t;

    while(i<=j)

    {

        while(i<n&&a[i]>=0)

        {

            i++;

        }

        while(j>=0&&a[j]<0)

        {

            j--;

        }

        if(i<j)

        {

            t=a[i];

            a[i]=a[j];

            a[j]=t;

            i++;

            j--;

        }

    }

}

int  main()

{   

    system("color f0");

    int n,i;

    int* p;

    printf("Please input n:\n");

    scanf("%d",&n);

    p=(int*)malloc(n*sizeof(int));

    printf("Please input array:\n");

    for(i=0;i<n; i++)

    {

            scanf("%d", &p[i]);

    }

    sort(p,n);

    printf("Adjusted array:\n");

    for(i=0;i<n;i++)

    {

            printf("%-4d",p[i]);

    }

    printf("\n");

    system("pause");

    return 0;

}

心得体会(遇到的问题和解决方法)

如何确定关键字为负数的记录的位置：可以设置两个指针，一个指向数组的起始位置，一个指向数组的末尾位置。通过交换操作将负数关键字放在前面。

如何保证算法的时间复杂度为O(N)：使用计数排序算法可以满足这一要求，因为计数排序的时间复杂度为O(N)。

如何使用最少的附加空间：计数排序算法需要额外的空间来存储计数数组，所以在这个问题中无法做到使用最少的附加空间。但是计数排序的空间复杂度为O(k)，其中k是关键字的范围，所以如果关键字范围较小，额外的空间开销也会比较小。

计数排序是一种简单而高效的排序算法，适用于关键字范围有限且较小的情况。其时间复杂度为O(N)，但需要额外的空间来存储计数数组。在实际应用中，我们可以根据具体问题的特点选择合适的排序算法，以满足时间和空间的要求。