数据结构 – 流程

发布于 2020-06-04  41 次阅读 本文共11655个字


顺序表

实验题目:编写程序实现顺序表的各种基本运算。对给定字符数组a[]={'1','2','2','1','0','2','4','2','3','1'},创建顺序表L,删除从'1'到'3'的元素。

/*
编写程序实现顺序表的各种基本运算。 对给定字符数组a[]={'1','2','2','1','0','2','4','2','3','1'} ,创建顺序表L,删除从'1'到'3'的元素。 */ #include<stdio.h> #include<math.h> #define MaxSize 100 #define ElemType char typedef struct { int* head; int size; int length; // 顺序表当前长度 }SqList; // 初始化顺序表 SqList InitList() { SqList s; s.head = (int*)malloc(sizeof(int)); if (!s.head) { printf("初始化失败"); exit(0); } s.length = 0; s.size = 0; return s; } // 顺序表删除 SqList delList(SqList s, int add) { if (add > s.length || add < 1) { printf("被删除元素的位置有问题\n"); return s; } // 删除 for (int i = add; i < s.length; i++) { s.head[i - 1] = s.head[i]; } s.length--; return s; } // 输出顺序表中的元素 void displayList(SqList t) { for (int i = 0; i < t.length; i++) { printf("%c ", t.head[i]); } printf("\n"); } SqList del(SqList s) { // 首先遍历寻找地址 int Length = NULL; // 要删除的个数 int index = NULL; // 1的位置 for (int i = 0; i < s.length; i++) { if (s.head[i] == '1') { index = i; } if (index != NULL && s.head[i] == '3') { Length = i - index + 1; break; } } // 删除 for (int j = 0; j < Length; j++) { for (int i = index; i < s.length - 1; i++) { s.head[i] = s.head[i + 1]; } s.length--; } return s; } int main() { SqList s = InitList(); char a[] = { '1','2','2','1','0','2','4','2','3','1' }; // 向顺序表中添加元素 for (int i = 1; i <= 10; i++) { s.head[i - 1] = a[i - 1]; s.length++; } printf("起初顺序表中存储的元素分别是: \n"); displayList(s); s = del(s); printf("删除从'1'到'3'元素后顺序表中存储的元素分别是: \n"); displayList(s); return 0; }

图片 8.png

链表

编写程序实现顺序表的各种基本运算。对给定数组a[ ]={6,3,8,5,1,18,9,2,4,15}创建链表(尾插入法),删除数据值为3到5之间的结点,对链表逆置,对链表排序。

#include<stdio.h>
#include<math.h>
typedef int typeElem;

typedef struct link {
    typeElem elem;  // 代表数据域
    struct link* next; // 代表指针域,指向后继元素
} link;

// 链表的创建 x 初始化
link* initLink(int a[], int Length) {
    link* p = (link*)malloc(sizeof(link));
    link* temp = p;
    for (int i = 0; i < Length; i++)
    {
        link* t = (link*)malloc(sizeof(link));
        t->elem = a[i];
        t->next = NULL;
        // 建立新节点与前驱节点的逻辑关系
        temp->next = t;
        temp = temp->next;
    }
    return p;
}


void display(link* p) {
    link* temp = p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null,就执行输出语句。
    while (temp->next) {
        temp = temp->next;
        if (temp->next == NULL)
        {
            printf("%d", temp->elem);
            break;
        }
        printf("%d-> ", temp->elem);
    }
    printf("\n");
}

// 删除元素
link* delElem(link* p, int add) {
    link* temp = p;
    // 遍历到被删除结点的上一个节点
    for (int i = 1;  i < add; i++)
    {
        temp = temp->next;
        if (temp->next == NULL) {
            printf("没有该结点\n");
            return p;
        }
    }
    link* del = temp->next;
    temp->next = temp->next->next;
    free(del);
    return p;
}

// 删除数据值为3到5之间的结点
link* del(link* p) {
    link* temp = p;
    while (temp->next != NULL)
    {
        if (temp->next->elem < 5 && temp->next->elem > 3)
        {
            link* dels = temp->next;
            if (temp->next->next == NULL)
            {
                temp->next = NULL;
            }
            else {
                temp->next = temp->next->next;
            }
            free(dels);
        }
        temp = temp->next;
    }
    return p;
}

// 链表逆置  先到最后一个,然后 有一个指着前一个
link* reverse(link* p) {
    link* pre =  NULL;
    link* cur;
    p = p->next;
    while (p != NULL) {
        cur = p->next;
        p->next = pre;
        pre = p;
        p = cur;
    }
    link* ex = (link*)malloc(sizeof(link));
    ex->next = pre;
    return ex;
}

// 对链表排序
link* sort(link* L) {
    link* p, * q, * pre;
    p = L->next->next;
    L->next->next = NULL;
    while (p != NULL)
    {
        q = p->next;
        pre = L;
        while (pre->next != NULL && pre->next->elem < p->elem)
        {
            pre = pre->next;
        }
        p->next = pre->next;
        pre->next = p;
        p = q;
    }
    return L;
}

int main() {
    int a[] = { 6,3,8,5,1,18,9,2,4,15 };
    link* p = initLink(a,10);
    printf("创建的链表: \n");
    display(p);
    p = del(p);
    printf("删除数据值为 3 到 5 之间的结点后: \n");
    display(p);
    p = reverse(p);
    printf("转置链表: \n");
    display(p);
    p = sort(p);
    printf("排序列表(从小到大): \n");
    display(p);
    return 0;
}

图片 9.png

栈 x 队列

编写程序实现栈和队列的各种基本运算。将一个环形队列(容量为n,元素小标为0~n-1)的元素倒置。

/*
实验题目:编写程序实现栈和队列的各种基本运算。将一个环形队列(容量为n,元素小标为0~n-1)的元素倒置。
*/
#include <stdio.h>
#include <stdlib.h>

// 实现链栈
typedef struct lineStack {
    int data;
    struct lineStack* next;
} lineStack;

// 进栈
lineStack* push(lineStack* stack, int a) {
    lineStack* line = (lineStack*)malloc(sizeof(lineStack));
    line->data = a;
    line->next = stack;
    stack = line;
    return stack;
}

// 出栈

lineStack* pop(lineStack* stack) {
    if (stack)
    {
        lineStack* p = stack;
        stack = stack->next;
        printf("弹栈元素: %d", p->data);
        if (stack)
        {
            printf("栈顶元素: %d\n", stack->data);
        }
        else {
            printf("栈已空");
        }
        free(p);
    }
    else {
        printf("栈内没有元素");
        return stack;
    }
    return stack;
}

#define MaxSize 10
// 实现队列 牺牲掉数组中的一个存储空间 来判断是否满
typedef struct QNode {
    int a[MaxSize];
    // 队尾指针
    int rear;
    // 队头指针
    int front;
}QNode;

QNode * InitQueue() {
    // 初始化队列
    QNode * queue = (QNode*)malloc(sizeof(QNode));
    queue->rear = queue->front = 0;
    return queue;
}

QNode * enQueue(QNode* queue, int data) {
    // 先判断
    if (isFull(queue) == 0)
    {
        printf("空间已经满了,添加失败\n");
    }
    else {
        queue->a[queue->rear % MaxSize] = data;
        queue->rear++;
        printf("添加成功\n");
    }
    return queue;
}

QNode* deQueue(QNode* queue, int *e) {
    if (isEmpty(queue) == 0)
    {
        printf("队列是空的,删除失败\n");
    }
    else {
        *e = queue->a[queue->front];
        queue->front = (queue->front + 1) % MaxSize;
        printf("删除成功\n");
    }
    return queue;
}

int isEmpty(QNode * queue) {
    if (queue->front == queue->rear % MaxSize)
    {
        return 0;
    }
    else {
        return 1;
    }
}

int isFull(QNode* queue) {
    // 满了
    if ((queue->rear + 1) % MaxSize == queue->front)
    {
        return 0;
    }
    else {
        return 1;
    }
}

void disQueue(QNode* queue) {
    if (isEmpty(queue) != 0)
    {
        int front = queue->front;
        int rear = queue->rear;
        for (; front != rear % MaxSize; front = (front + 1) % MaxSize)
        {
            printf("%d->", queue->a[front]);
        }
        printf("\n");
    }
    else {
        printf("队列是空的\n");
    }
}

// 一个环形队列(容量为n,元素小标为0~n-1)的元素倒置。
QNode* reverse(QNode * queue) {
    int len = ((queue->rear - queue->front + MaxSize) % MaxSize);
    int a[MaxSize];
    int e;
    for (int i = 0; i < len; i++)
    {
        queue = deQueue(queue, &e);
        a[i] = e;
    }
    for (int j = len - 1;  j >= 0; j--)
    {
        queue->rear = (queue->rear + 1) % MaxSize;
        queue->a[queue->rear] = a[j];
    }
    queue->rear = (queue->rear + 1) % MaxSize;
    queue->front = (queue->front + 1) % MaxSize;
    return queue;
}

int main() {
    QNode* p = InitQueue();
    int temp;
    for (int i = 0;  i < MaxSize; i++)
    {
        p = enQueue(p, i);
    }
    printf("元素倒置前:\n");
    disQueue(p);
    p = reverse(p);
    printf("元素倒置后:\n");
    disQueue(p);
    return 0;
}

图片 10.png

二叉树算法遍历及其应用

编写程序实现二叉树的先序遍历、中序遍历和后续遍历的递归算法,以及层次遍历的算法。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
/*
实验题目:编写程序实现二叉树的先序遍历、中序遍历和后续遍历的递归算法,
以及层次遍历的算法。
*/

#define TElemType int
typedef struct node {
    TElemType data;
    struct node* lchild, * rchild;
}BSTNode, *BSTTree;


BSTNode CreatBST(BSTTree *T) {
    *T = (BSTNode*)malloc(sizeof(BSTNode));
    (*T)->data = 1;
    (*T)->lchild = (BSTNode*)malloc(sizeof(BSTNode));
    (*T)->rchild = (BSTNode*)malloc(sizeof(BSTNode));

    (*T)->lchild->data = 2;
    (*T)->lchild->lchild = (BSTNode*)malloc(sizeof(BSTNode));
    (*T)->lchild->rchild = (BSTNode*)malloc(sizeof(BSTNode));
    (*T)->lchild->rchild->data = 5;
    (*T)->lchild->rchild->lchild = NULL;
    (*T)->lchild->rchild->rchild = NULL;
    (*T)->rchild->data = 3;
    (*T)->rchild->lchild = (BSTNode*)malloc(sizeof(BSTNode));
    (*T)->rchild->lchild->data = 6;
    (*T)->rchild->lchild->lchild = NULL;
    (*T)->rchild->lchild->rchild = NULL;
    (*T)->rchild->rchild = (BSTNode*)malloc(sizeof(BSTNode));
    (*T)->rchild->rchild->data = 7;
    (*T)->rchild->rchild->lchild = NULL;
    (*T)->rchild->rchild->rchild = NULL;
    (*T)->lchild->lchild->data = 4;
    (*T)->lchild->lchild->lchild = NULL;
    (*T)->lchild->lchild->rchild = NULL;
}

// 层次遍历
int** levelOrder(struct node* root, int* returnSize, int** returnColumnSizes) {
    if (!root)
    {
        *returnSize = 0;
        return 0;
    }
    int** result = (int**)malloc(sizeof(int*) * 2000);
    int i = 0;
    struct node* p = root;
    struct node* queue[2000]; int front = 0, rear = 0;
    queue[rear++] = p;
    *returnColumnSizes = (int*)malloc(sizeof(int) * 2000);
    while (front != rear)
    {
        int size = rear - front;
        result[i] = (int*)malloc(sizeof(int) * size);
        (*returnColumnSizes)[i] = size;
        for (int j = 0; j < size; ++j)
        {
            p = queue[front];
            front = (front + 1) % 2000;
            if (p->lchild)
            {
                queue[rear] = p->lchild;
                rear = (rear + 1) % 2000;
            }
            if (p->rchild)
            {
                queue[rear] = p->rchild;
                rear = (rear + 1) % 2000;
            }
            result[i][j] = p->data;
        }
        ++i;
    }
    *returnSize = i;
    return result;
}

// 输出层次遍历
void disLevel(int** result) {
    printf("[\n");
    for (int i = 0; i < 3; i++)
    {
        printf("  [");
        for (int j = 0; j < pow(2, i); j++)
        {
            printf("%d ", result[i][j]);
        }
        printf("],\n");
    }
    printf("]");
}

// 先序
void BeforeOrderTree(BSTNode* root) {
    if (root == NULL)
    {
        return;
    }
    printf("%d ", root->data);
    if (root->lchild != NULL)
    {
        BeforeOrderTree(root->lchild);
    }
    if (root->rchild != NULL) {
        BeforeOrderTree(root->rchild);
    }
}

void AfterOrderTree(BSTNode* root) {
    if (root == NULL)
    {
        return;
    }
    if (root->lchild != NULL)
    {
        BeforeOrderTree(root->lchild);
    }
    if (root->rchild != NULL) {
        BeforeOrderTree(root->rchild);
    }
    printf("%d ", root->data);
}

// 中序遍历
void CenterOrderTree(BSTNode* root) {
    if (root == NULL)
    {
        return;
    }
    if (root->lchild != NULL)
    {
        BeforeOrderTree(root->lchild);
    }
    printf("%d ", root->data);
    if (root->rchild != NULL) {
        BeforeOrderTree(root->rchild);
    }
}

int main() {
    BSTTree tree;
    CreatBST(&tree);
    printf("先序遍历: \n");
    BeforeOrderTree(tree);
    printf("\n后序遍历: \n");
    AfterOrderTree(tree);
    printf("\n中序遍历: \n");
    CenterOrderTree(tree);
    printf("\n层次遍历: \n");
    int** result = (int**)malloc(sizeof(int*) * 2000);
    int* returnSize = (int*)malloc(sizeof(int*) * 2000);
    result = levelOrder(tree, returnSize, result);
    disLevel(result);
    return 0;
}

图片 11.png

图的遍历算法及其应用

编写程序实现图的深度优先遍历和广度优先遍历算法。(图的存储结构为邻接表)。

/*
实验题目:编写程序实现图的深度优先遍历和广度优先遍历算法。(图的存储结构为邻接表)。
*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>


#define InfoType int
#define Vertex char
#define MAXV 10

typedef struct ANode
{
    int adjvex;  // 该边的终点编号
    struct ANode* nextarc;  // 指向下一条边的指针
    InfoType info;  // 该边的权值等信息
} ArcNode;

// 头节点类型
typedef struct Vnode
{
    Vertex data;  // 顶点信息
    ArcNode* firstarc;  // 指向第一条边
} VNode;

typedef struct {
    VNode adjlist[MAXV];  // 邻接表
    int n, e;  // 图中定点数,边数
}ALGraph;


ALGraph* CreateAdjListGraph(ALGraph* G)
{
    ArcNode* e;
    G->n = 5; //输入当前图的顶点数
    G->e = 6;    //输入当前图的边数
    for (int i = 0; i < G->n; i++)    //建立顶点表
    {
        scanf_s("%c",&G->adjlist[i].data);   //输入顶点信息
        G->adjlist[i].firstarc = NULL;   //将表边指针置为空
    }
    for (int k = 0; k < G->e; k++)
    {
        int i, j, w;
        //输入边两边的顶点和边上的权重
        scanf_s("%d", &i);
        scanf_s("%d", &j);
        scanf_s("%d", &w);
        ArcNode * e = (ArcNode*)malloc(sizeof(ArcNode));   //创建一个表边节点指针
        e->adjvex = j;
        e->info = w;
        e->nextarc = G->adjlist[i].firstarc;
        G->adjlist[i].firstarc = e;
    }
    return G;
}

int visited[MAXV];
// 深度优先遍历
void DFS(ALGraph* G, int v)
{
    ArcNode* p;
    int w;
    visited[v] = 1;
    printf("%d ", v);  // 输出被访问顶点的编号
    p = G->adjlist[v].firstarc;  // p指向顶点v的第一条边的边头节点
    while (p != NULL)
    {
        w = p->adjvex;
        if (visited[w] == 0)
            DFS(G, w);  // 若w未被访问,递归访问它
        p = p->nextarc;  // p指向顶点v的下一条边的变头节点
    }
}

// 广度优先遍历
void BFS(ALGraph* G, int v)
{
    ArcNode * p;
    int w, i;
    int queue[MAXV], front = 0, rear = 0;
    int visited[MAXV];
    for (i = 0; i < G->n; i++) {
        visited[i] = 0;
    }
    printf("%d ", v);
    visited[v] = 1;
    rear = (rear + 1) % MAXV;
    queue[rear] = v;  // 进队
    // 队列不空循环
    while (front != rear)
    {
        front = (front + 1) % MAXV;
        w = queue[front];  // 出队并赋w
        p = G->adjlist[w].firstarc;  // 找w的第一个的邻接点
        while (p != NULL)
        {
            if (visited[p->adjvex] == 0)
            {
                printf("%d ", p->adjvex);  // 访问之
                visited[p->adjvex] = 1;
                rear = (rear + 1) % MAXV;  // 相邻顶点进队
                queue[rear] = p->adjvex;
            }
            p = p->nextarc;  // 找出下一个邻接顶点
        }
    }
}


int main() {
    ALGraph* G = (ALGraph*)malloc(sizeof(ALGraph));
    G = CreateAdjListGraph(G);
    printf("广度优先遍历:\n");
    BFS(G, 0);
    printf("\n深度优先遍历: \n");
    DFS(G, 0);
    return 0;
}

图片 12.png


查找和排序算法设计

1)编写程序输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找法查找关键字9的过程。
2)编写快速排序算法,并输出{6,8,7,9,0,1,3,2,4,5}的排序过程。

/*
实验题目:1)编写程序输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找法查找关键字9的过程。
2)编写快速排序算法,并输出{6,8,7,9,0,1,3,2,4,5}的排序过程。
*/
#include<stdio.h>
#include<stdlib.h>

#define MaxSize 100
#define ElemType int
typedef struct {
    int head[MaxSize];
    int length;  // 顺序表当前长度
}SqList;

// 初始化顺序表

SqList InitList() {
    SqList s;
    s.length = 0;
    return s;
}

void display(SqList s) {
    for (int i = 0;  i< s.length; i++)
    {
        printf("%d ", s.head[i]);
    }
    printf("\n");
}

int BinarySearchHelper(SqList s, int front, int end, int k) {
    int middle = (front + end) / 2;
    printf("%d->", s.head[middle]);
    if (s.head[middle] == k)
    {
        printf("Return");
        return middle;
    }
    else if (s.head[middle] < k) {
        return BinarySearchHelper(s, middle + 1, end, k);
    }
    else {
        return BinarySearchHelper(s, front, middle - 1, k);
    }
}

int BinarySearch(SqList s, int k) {
    return BinarySearchHelper(s, 0, s.length - 1, k);
}

int c = 0;
// 快排
int Partition(SqList *s, int low, int high) {
    c++;
    printf("第 %d 次排序前: ", c);
    display(*s);
    int privotkey = s->head[low];
    // 直到两指针相遇
    while (low < high) {
        // high指针左移,直到遇到比 privotkey值小的记录
        while (low < high && s->head[high] >= privotkey) {
            high--;
        }
        if (low < high)
        {
            s->head[low] = s->head[high];
        }
        // low 指针右移,直到遇到比 privotkey 值大的
        while (low < high && s->head[low] <= privotkey)
        {
            low++;
        }
        if (low < high)
        {
            s->head[high] = s->head[low];
        }
    }
    s->head[low] = privotkey;
    printf("第 %d 次排序后: ", c);
    display(*s);
    return low;
}

void QSort(SqList *s, int low, int high)
{
    if (low < high)
    {
        // 找到支点的位置
        int privotloc = Partition(s, low, high);
        // 对支点左侧的子表进行排序
        QSort(s, low, privotloc - 1);
        // 对支点右侧的子表进行排序
        QSort(s, privotloc + 1, high);
    }
}



void QuickSort(SqList *s) {
    QSort(s, 0, s->length - 1);
}

int main() {
    SqList s = InitList();
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    // 向顺序表中添加元素
    for (int i = 1; i <= 10; i++) {
        s.head[i - 1] = a[i - 1];
        s.length++;
    }
    printf("顺序表的元素:\n");
    display(s);
    printf("折半查找过程:\n");
    printf("\n返回关键字9的下标:%d\n", BinarySearch(s, 9));
    int b[] = { 6,8,7,9,0,1,3,2,4,5 };
    SqList L = InitList();
    for (int i = 1; i <= 10; i++) {
        L.head[i - 1] = b[i - 1];
        L.length++;
    }
    printf("快排算法执行前: \n");
    display(L);
    printf("快排算法执行过程中,顺序表变化: \n");
    QuickSort(&L);
    printf("快排后: \n");
    display(L);
    return 0;
}

图片1.png


数据结构实验报告就此结束。。害,写的过程中也参考了很多教程,总的来说,还是有丶头疼的。最后一个快排,怎么说呢,一直没考虑 & 导致后面的输出一直还是原来的顺序表中的内容,ps. 指针还是脑阔疼。

It's Over


粉色的花瓣,美丽地缠绕在身上。依在风里。