数据结构练习记录

Q1

Q2.1

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int *elem;
    int length; // 当前长度
    int listsize; // 当前分配的存储空间
} SqList;

// 初始化顺序表
int initList(SqList *L, int listsize)
{
    L->elem = (int *)malloc(sizeof(int) * listsize);
    if(!L->elem){
        return -1;
    }
    L->length = 0;
    return 0;
}

// 有序插入
void OrderedList_Insert(SqList *L, int x)
{
    // 寻找x的前一个元素和后一个元素
    //int prior = 0, next = 0, pos;
    //for(int i = 0; i < L->listsize; i++) {
    //    if(x > L->elem[i]) {
    //       prior = L->elem[i];
    //       next = L->elem[i+1];
    //       pos = i + 1;
    //    }
    //}


    //printf("前%d，后%d，位置是 %d\n",prior, next, pos);

    // 寻找插入位置
    int pos;
    for(pos = 0; pos < L->length; pos++) {
        if(x <= L->elem[pos]) {
            break;
        }
    }

    // 插入
    for(int j = L->length; j >= pos; j--) {
        L->elem[j+1] = L->elem[j];
    }
    L->elem[pos] = x;
    ++L->length;
}

int main()
{
    // 初始化顺序表
    SqList L;
    printf("请设置表长：");
    scanf("%d", &L.listsize);
    int result = initList(&L, L.listsize);
    if (result == -1) {
        printf("初始化失败！\n");
    }
    else {
        printf("初始化成功！\n");
        printf("当前分配的存储容量为：%d\n", L.listsize);
    }

    // 顺序表赋值
    for(int i = 0; i < L.listsize; i++) {
        if (L.length < L.listsize) {
                L.elem[i] = i * 2;
                ++L.length;
                printf("%d ", L.elem[i]);
        }
        else {
            printf("超出分配空间，无法向顺序表中赋值！");
            break;
        }
    }

    int x;
    printf("\n请插入元素:");
    scanf("%d", &x);
    OrderedList_Insert(&L, x);
    printf("插入后顺序表为:");
    for(int j = 0; j < L.length; j++) {
        printf("%d ",L.elem[j]);
    }

    // 清理内存
    free(L.elem);

    return 0;
}

Q2.2

题目

OrderedList(LinkList L, int min, int max)的时间复杂度：

最好：整个链表没有大于min小于max的结点，遍历链表一次。即O(n)

最坏：所有节点都需要删除，遍历链表一次。即O(n)

平均：O(n)

n为链表长度

#include <stdio.h>
#include <stdlib.h>
#define ERROR -1

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode, *LinkList;

LinkList InitList()
{
    LinkList L = (LinkList)malloc(sizeof(LNode));
    if(L == NULL) {
        printf("链表初始化失败！\n");
        exit(0);
    }
    L->next = NULL;
    printf("链表初始化成功！\n");
    return L;
}

// 后插法
int CreateList_R(LinkList *L, int n)
{
    *L = InitList();
    LinkList r = *L;
    for(int i = 0; i < n; ++i)
    {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        scanf("%d", &p->data);
        p->next = NULL;
        r->next = p;
        r = p;
    }
    return 0;
}

// 删除表中所有大于min小于max的结点
void OrderedList(LinkList *L, int min, int max)
{
    LinkList p = *L;
    LinkList pre = NULL; // 跟踪前一个结点
    int flag = 0;
    while(p != NULL)
    {
        // 找所有大于min小于max的结点
        if(p->data > min && p->data < max)
        {
            LinkList q = p;
            if(pre == NULL)
            {
                *L = p->next; // 如果删除的是头结点，更新头指针
            }
            else
            {
                pre->next = p->next; // 跳过当前结点
            }
            p = p->next;
            free(q);
            flag = 1;
        }
        else {
            pre = p;
            p = p->next;
        }
    }

    if(!flag)
        printf("没有大于min且小于max的结点，没有删除任何元素！");
}

// 输出链表
void PrintList(LinkList L)
{
    LinkList p = L->next;
    while(p != NULL)
    {
        printf("%d ->", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

int main()
{
    LinkList list;
    int n;
    printf("请输入链表长度：");
    scanf("%d", &n);
    if(n <= 0)
    {
        printf("链表长度必须大于0");
        return 0;
    }
    int result = CreateList_R(&list, n);
    if(result == 0) {
        printf("创建链表成功！\n");
        int max, min;
        printf("请输入最大值与最小值(空格分隔)：");
        scanf("%d %d", &max, &min);
        printf("原链表：\n");
        PrintList(list);
        printf("正在删除表中所有大于min小于max的结点\n");
        OrderedList(&list, min, max);
        PrintList(list);
    }
    else {
        printf("创建链表失败！\n");
    }
    return 0;
}

Q3.1

栈特点：先入后出，后入先出

Q3.2

Q3.3

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
#define ERROR -1

typedef struct
{
    char *base;
    char *top;
    int stacksize;
}SqStack, *Stack;

// 初始化
Stack InitStack()
{
    // 给栈这个结构分配内存，也就是实现一个栈的结构框架
    Stack s = (Stack)malloc(sizeof(SqStack));
    if(s == NULL)
    {
        printf("栈内存分配失败！\n");
        exit(0);
    }

    // 给栈的实际数据分配空间
    s->base = (char *)malloc(MAXSIZE * sizeof(char));
    if(s->base == NULL)
    {
        free(s);
        printf("栈内存分配失败！\n");
        exit(0);
    }

    s->top = s->base;
    s->stacksize = MAXSIZE;
    printf("栈初始化成功！\n");
    return s;
}

// 入栈
int Push(Stack s, char e)
{
    if(s->top - s->base == s->stacksize) {
        printf("栈满！\n");
        return ERROR;
    }
    *s->top = e;
    s->top++;
    return 0;
}

// 出栈
int Pop(Stack s, char *e)
{
    if(s->top == s->base)
    {
        printf("栈空！\n");
        return ERROR;
    }
    s->top--;
    *e = *s->top;
    return 0;
}

// 清空栈
void DestroyStack(Stack s)
{
    if(s != NULL) {
        free(s->base);
        s->base = NULL;
        s->top = NULL;
        s->stacksize = 0;
        free(s);
        printf("栈已销毁!\n");
    }
}

// 获取栈顶元素
char GetTop(Stack s)
{
    if(s->top != s->base) {
        return *(s->top - 1);
    }
    exit(0);
}

// 判断栈是否为空
int StackEmpty(Stack s)
{
    return s->top == s->base;
}

int Symmetry(char a[])
{
    Stack s = InitStack();
    int flag = 1; // 标记匹配结果以及控制循环
    int length = strlen(a);
    int mid = -1; // 记录&位置

    // 检查字符串是否以@结尾
    if(a[length - 1] != '@') {
        printf("字符序列没有以 @ 结尾，请重新输入！\n");
        flag = 0;
    }

    // 遍历字符串，找到&后，将其前半部分压入栈中
    for(int i = 0; i < length - 1 && flag; i++) {
        if(a[i] == '&') {
            if(mid == -1) {
                mid = i;
            }
            else {
                printf("只能有一个 & 出现！\n");
                flag = 0;
                break;
            }
        }
        // 没有遇到&，入栈
        else if(mid == -1) {
            Push(s, a[i]);
        }
    }

    // 检查对称， & 后的字符是否和栈内的元素匹配
    if(flag) {
        for(int i = mid + 1; i < length - 1; i++) {
            char topElem = GetTop(s);
            if(topElem == a[i]) {
                Pop(s, &topElem); // 匹配成功后出栈
            }
            else {
                flag = 0; // 如果不匹配，退出循环
                break;
            }
        }
    }

    DestroyStack(s);
    return flag;
}

int main()
{
    char a[MAXSIZE];
    printf("请输入一个以@结尾的字符序列：");
    scanf("%s", a);
    if(Symmetry(a)) {
        printf("字符序列是对称的！\n");
    }
    else {
        printf("字符序列不对称！\n");
    }
    return 0;
}

Q3.4

当front = rear && flag = 0为队空
当front = rear && flag = 1为队满

#include <stdio.h>
#include <stdlib.h>
#define MaxQSize 5
#define ERROR -1

typedef struct
{
    int *base;
    int front;
    int rear;
    int flag;
}SqQueue, *Queue;

// 当front = rear && flag = 0为队空
// 当front = rear && flag = 1为队满

Queue InitQueue()
{
    Queue q = (Queue)malloc(sizeof(SqQueue));
    q->base = (Queue)malloc(MaxQSize * sizeof(SqQueue));
    if(!q->base) {
        printf("队列初始化失败！");
        exit(0);
    }

    q->rear = 0;
    q->front = q->rear;
    q->flag = 0; // 初始化队空
    return q;
}

int EnQueue(Queue q, int e)
{
    // 队满
    if((q->front == q->rear) && q->flag == 1) {
            printf("队满！\n");
        return ERROR;
    }
    q->base[q->rear] = e;
    q->rear = (q->rear + 1) % MaxQSize;
    if(q->front == q->rear)
        q->flag = 1; // 设置标准为1表示队满
    return 0;
}

int main()
{
    Queue q = InitQueue();
    int n, e;
    printf("输入队列长度（最多%d）：", MaxQSize);
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        printf("入队元素：");
        scanf("%d", &e);
        int result = EnQueue(q, e);
        if(result == 0) {
            printf("入队成功！\n");
        }
        else
            printf("入队失败！\n");
    }

    printf("再次尝试入队一个元素：");
    scanf("%d", &e);
    int result = EnQueue(q, e);
    if (result == 0) {
        printf("入队成功！\n");
    } else {
        printf("入队失败！\n");
    }
    return 0;
}

Q5.1

二维数组：

假设每个数据元素占L个存储单元，则二维数组A[0…m-1, 0…n-1]（即下标从0开始，共有m行n列）中任一元素aij的存储位置可下式确定

LOC(i, j) = LOC(0, 0) + (n*i + j)L

LOC(i, j)是aij的存储位置；LOC(0, 0)是a00的存储位置，即二维数组A的起始位置（基地址）

n维数组：

LOC(j1, j2, … , jn) = LOC(0, 0, …, 0) + (b2*…*bn*j1 + b3*…*bn*j2 + … + bn*…*jn-1 + jn ) L