C语言数据结构练习

2025/2/24 学习 C语言学习

学习通的作业

学习通的作业已存放在网盘(点击进入)

~~最好还是不要让太多人知道了，好东西独自享受喵。~~

实验

实验1 顺序表的基本操作

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/3070/view

二、算法思路与流程

三、程序代码及运行结果

#include <bits/stdc++.h>
using namespace std;
#define OK 1
#define ERROR 0
#define LIST_SIZE 100
#define LISTINCREMENT 10
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
typedef struct{
    ElemType *elem;
    int length;
    int listsize;
}Sqlist;

Status Initlist_sq(Sqlist &L){
    L.elem = (ElemType *)malloc(LIST_SIZE*sizeof(ElemType));
    if(!L.elem) return OVERFLOW;
    L.length = 0;
    L.listsize = LIST_SIZE;
    return OK;
} 

Status ClearList_sq(Sqlist &L){
    if(L.length==0) return ERROR;
    L.length = 0;
    return OK;
}

int LocateElem_sq(Sqlist L, ElemType e){
    int i =1;
    int *p = L.elem;
    while(i<=L.length && *p++!=e) ++i;
    if(i<=L.length) return i;
    else return 0;
}

ElemType LocateIndex_sq(Sqlist L, int i){
    if(i<1||i>L.length) return ERROR;
    return L.elem[i-1];
}

Status ListInsert_sq(Sqlist &L, int i, ElemType e){
    if(i<1|| i>L.length+1) return ERROR;
    if(L.length+1>L.listsize){
        ElemType *newlist = (ElemType *)realloc(L.elem,(L.listsize +1) * sizeof(ElemType));
        L.elem = newlist;
        L.listsize++;
    }
    ElemType *q = &(L.elem[i-1]);
    for(ElemType *p = &(L.elem[L.length-1]);p>=q;--p) *(p+1) = *p;
    *q = e;
    ++L.length;
    return OK;
}

Status ListDelete_sq(Sqlist &L, int i, ElemType &e){
    if(i<1||i> L.length) return ERROR;
    ElemType *p = &(L.elem[i-1]);
    e = *p;
    for(ElemType *q = p+1;q<=&(L.elem[L.length-1]);++q) *(p++) = *q;
    --L.length;
    return OK;
} 


int main(){
    Sqlist L;
    Initlist_sq(L);
    int n, m, index;
    ElemType e, a, b;
    cin >> n >> m;
    for (int i=1;i<=n;i++){
        cin >> e;
        ListInsert_sq(L, i, e);
    }
    string s;
    for (int i=1;i<=m;i++){
        cin >> s;
        if (s[0]=='I'){
            cin >> a >> b;
            ListInsert_sq(L, a, b);
        }
        else if (s[0]=='D'){
            cin >> index;
            ListDelete_sq(L, index, b);
            cout << b << endl;
        }
        else if (s[0]=='G'){
            cin >> index;
            cout << LocateIndex_sq(L, index) << endl;
        }
        else if (s[0]=='L'){
            cin >> b;
            index = LocateElem_sq(L, b);
            cout << index << endl;
        }
        else {
            ClearList_sq(L);
        }
    }
    return 0;
}

四、收获总结

实验2 链表及其多项式相加

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/3049/view

二、算法思路与流程

三、程序代码及运行结果

/* 链表及其多项式相加 */
#include<stdio.h>
#include<stdlib.h>  

#define OVERFLOW -2
#define OK 1

typedef int status;
typedef struct Lnode {
    int exp, data;
    struct Lnode* next;
} Lnode, * Linklist;

//链表建立函数：建立一个长度为n的链表 
status listcreate_L(Linklist L, int n) {
    Lnode* p = L;
    for (int i = 0; i < n; i++) {
        int val = 0, exp = 0;
        Lnode* n = (Lnode*)malloc(sizeof(Lnode));
        scanf("%d %d", &val, &exp);
        n->data = val;
        n->exp = exp;
        n->next = NULL;
        p->next = n;
        p = p->next;
    }
    return 0;
}

//表达式相加函数：将La指向的表达式与Lb指向的表达式相加，赋给Lc 
Linklist listadd_L(Linklist l1, Linklist l2) {
    Linklist lc = (Linklist)malloc(sizeof(Lnode)); //创建头指针
    lc->next = NULL;

    Lnode *la = l1->next, * lb = l2->next, * ld, * le; //ld表示新链表中的节点，le表示创建的新节点
    ld = lc;

    while (la && lb) {
        if (la->exp < lb->exp) {
            ld->next = la; //la赋值给新节点
            la = la->next;
            ld = ld->next;
        }
        else if (la->exp > lb->exp) {
            ld->next = lb; //lb赋值给新节点
            lb = lb->next;
            ld = ld->next;
        }
        else {
            int sum = la->data + lb->data;
            if (!sum) { la = la->next; lb = lb->next; continue; } //如果相加为0，跳过
            
            le = (Linklist)malloc(sizeof(Lnode)); //相加不为0创建一个新节点，把值赋值给新节点，并指向新节点
            le->next = NULL;
            le->exp = la->exp;
            le->data = sum;
            ld->next = le;

            la = la->next;
            lb = lb->next;
            ld = ld->next;
        }
    }
    ld->next = la ? la : lb; //处理剩下的节点
    return lc;
}
//输出链表 
status listouput_L(Linklist L) {
    Lnode* p = L->next;
    int sum = 0, t = 1;
    while (p != NULL) {
        printf("%d %d\n", p->data, p->exp);
        p = p->next;
    }
    return OK;
}
int main() {
        Lnode* A = (Lnode*)malloc(sizeof(Lnode));
        A->next = NULL;
        int n = 0;
        scanf("%d", &n);
        listcreate_L(A, n);

        Lnode* B = (Lnode*)malloc(sizeof(Lnode));
        B->next = NULL;
        int m = 0;
        scanf("%d", &m);
        listcreate_L(B, m);

        Lnode* C = listadd_L(A, B);
        listouput_L(C);
        return 0;
    return 0;
}

四、收获总结

实验3 实践栈结构-括号匹配算法

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/3050/view

二、算法思路与流程

#include <bits/stdc++.h>
using namespace std;

#define OVERFLOW -2
#define UNDERFLOW -1
#define OK 1

typedef char DataType;
typedef struct snode{
    DataType data;
    struct snode *next;
}StackNode; 

typedef struct {
    StackNode *top;
}LinkStack;

void InitStack(LinkStack &S){
    S.top = NULL;
}

bool StackEmpty(LinkStack &S){
    return S.top == NULL;
}

void Push(LinkStack &S, DataType x){
    StackNode * a=(StackNode*)malloc(sizeof(StackNode));
    if(a==NULL) exit(OVERFLOW);
    a->data=x;
    a->next=S.top;
    S.top = a;
}

DataType Pop(LinkStack &S){
    if(S.top==NULL) return UNDERFLOW;
    DataType p;
    snode * q = S.top;
    p = S.top->data;
    q = S.top;
    S.top = S.top->next;
    free(q);
    return p;
}

DataType GetTop(LinkStack &S){
    if(S.top == NULL) return UNDERFLOW;
    return S.top->data;
}

int Length(string s){
    return s.length();
}

bool match(char a, char b){
    if((a=='('&&b==')')||(a=='['&&b==']')){
        return 1;
    }
    else return 0;
}

bool matching(string exp){
    LinkStack S;
    InitStack(S);
    int state=1,i=0;
    while(i<Length(exp) && state){
        switch (exp[i])
        {
        case '(':
        case '[':
            Push(S,exp[i]);
            i++;
            break;
        case ']':
        case ')':
            if(!StackEmpty(S) && match(GetTop(S), exp[i])) {
                Pop(S);
                i++;
            }
            else state =0;
            break;
        }
    }
    if(state==1 && StackEmpty(S))return OK;
    else return 0;
}

int main(){
    string exp;
    cin >> exp;
    if (matching(exp)) printf("yes\n");
    else printf("no\n");
    return 0;
}

三、程序代码及运行结果

四、收获总结

实验4 实践栈结构-编译器中的表达式求值问题

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/3052/view

二、算法思路与流程

#include <cstdio>
#include <iostream>
#include <cstring>

#define OVERFLOW -2
#define UNDERFLOW -1
#define OK 1

using namespace std;

typedef char Dataoptr;
typedef int Dataopnd;

typedef struct stdacknode_optr{
    Dataoptr data;
    struct stdacknode_optr*next;
} Stacknode_optr;

typedef struct {
    Stacknode_optr *top;
    Stacknode_optr *base;
} Stack_optr;

typedef struct stdacknode_opnd{
    Dataopnd data;
    struct stdacknode_opnd*next;
} Stacknode_opnd;

typedef struct {
    Stacknode_opnd *top;
    Stacknode_opnd *base;
} Stack_opnd;


void InitStack_optr(Stack_optr &S) {
    S.top == NULL;
}

void Push_optr(Stack_optr &S, Dataoptr x) {
    Stacknode_optr *p = (Stacknode_optr *)malloc(sizeof(Stacknode_optr));
    p->data = x;
    p->next = S.top;
    S.top = p;
}

Dataoptr Pop_optr(Stack_optr &S) {
    if (S.top == NULL) {
        return UNDERFLOW;
    }
    Dataoptr x;
    Stacknode_optr *p = S.top;
    x = p->data;
    S.top = p->next;
    free(p);
    return x;
}

Dataoptr GetTopnode_optr(Stack_optr &S){
    return S.top->data;
}

Dataopnd GetTopnode_opnd(Stack_opnd &S){
    return S.top->data;
}

void InitStack_opnd(Stack_opnd &S) {
    S.top == NULL;
}

void Push_opnd(Stack_opnd &S, Dataopnd x) {
    Stacknode_opnd *p = (Stacknode_opnd *)malloc(sizeof(Stacknode_opnd));
    p->data = x;
    p->next = S.top;
    S.top = p;
}

Dataopnd Pop_opnd(Stack_opnd &S) {
    if (S.top == NULL) {
        return UNDERFLOW;
    }
    Dataopnd x;
    Stacknode_opnd *p = S.top;
    x = p->data;
    S.top = p->next;
    free(p);
    return x;
}

bool in (char c) {
    return c<='9'&&c>='0';
}
Dataopnd Operate(Dataopnd a,Dataoptr op, Dataopnd b) {
    switch (op) {
        case '+':return a+b;
        case '-':return a-b;
        case '*':return a*b;
        case '/':return a/b;
    }
    return 0;
}

char Precede(char x1, char x2)
{
    if((x1=='('&&x2==')')|| x1=='#'&&x2=='#') return '=';
    else if((x1=='('||x1=='#'||x2=='(')||(x1=='+'||x1=='-')&&(x2=='*'||x2=='/')) return '<';
    else return '>';
}

int EvaluateExpression(char *s)
 
{
    Stack_optr OPTR;
    Stack_opnd OPND; 
    int idx = 0;
    int a, b;
    char op;
 
    InitStack_optr(OPTR);
    InitStack_opnd(OPND);
 
    Push_optr(OPTR, '#');
 
    while (s[idx] != '#' || GetTopnode_optr(OPTR) != '#')
    {
        if (in(s[idx]))
        {
            Push_opnd(OPND, s[idx] - '0');
            printf("%d ", s[idx] - '0');
            idx++;
        }
        else
        {
            switch (Precede(GetTopnode_optr(OPTR), s[idx]))
            {
            case '>':
                op = Pop_optr(OPTR);
                b = Pop_opnd(OPND);
                a = Pop_opnd(OPND);
                printf("%c ", op);
                Push_opnd(OPND, Operate(a, op ,b));
                break;
            case '=':
                Pop_optr(OPTR);
                idx++;
                break;
            case '<':
                Push_optr(OPTR, s[idx++]);
            }
        }
    }
    return GetTopnode_opnd(OPND);
}

int main() {
    char str[2000] = {0};
 
    scanf("%s", str);
    int num;
    str[strlen(str)] = '#';
    num = EvaluateExpression(str);
    printf("\n%d\n", num);
    return 0;
}

三、程序代码及运行结果

四、收获总结

实验5 字符串的模式匹配(KMP)

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/3053/view

二、算法思路与流程

#include <stdio.h>
#include <string.h>

char s[100005];
char t[100005];
int next[100005];
void get_next(char *t)
{
    int i = 0, j = -1;
    next[0] = -1;
    int tlen = strlen(t);
    while (i < tlen)
    {
        if (j == -1 || t[i] == t[j]){
            ++i;
            ++j;
            next[i] = j;
        }
        else j = next[j];
    }
}
int kmp(char *s, char *t)
{
    int i = 0, j = 0;
    int slen = strlen(s);
    int tlen = strlen(t);
    while (i < slen && j < tlen)
    {
        if (j == -1 || s[i] == t[j])
        {
            ++i;
            ++j;
        }
        else j = next[j];
    }
    if (j >= tlen) return 1;
    else return 0;
}

int main(){

    gets(s);
    int count=0;
    scanf("%d",&count);
    getchar(); //读取后面的换行符防止下次对gets读取造成干扰
    for(int i =0;i<count;i++){
        gets(t);
        get_next(t);
        int flag = kmp(s,t);
        if(flag==1) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

三、程序代码及运行结果

四、收获总结

实验6 稀疏矩阵的建立与转置

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/3054/view

二、算法思路与流程

#include <cstdio>
using namespace std;

#define MAXSIZE 12500
#define OK 1

typedef int ElemType;
typedef int Status;

typedef struct {
    int i,j;
    ElemType e;
} Triple;

typedef struct {
    Triple data[MAXSIZE+1];
    int mu,nu,tu;
} TSMatrix;

Status TransposeSMatrix(TSMatrix M, TSMatrix &T){
    int p, q, col;
    T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
    if(T.tu){
        q = 1;
        for (col = 0;col<=M.nu;col++){ // 这里col从0开始
            for (p = 1;p<=M.tu;p++){
                if(M.data[p].j == col){
                    T.data[q].i = M.data[p].j;
                    T.data[q].j = M.data[p].i;
                    T.data[q].e = M.data[p].e;
                    q++;
                }
            }
        }
    }
    return OK;
}

void printMatrix(TSMatrix M){
    int count = 1;
    for (int i =0;i<M.mu;i++){
        for (int j=0;j<M.nu;j++){
            if(M.data[count].i ==i&&M.data[count].j==j){
                printf("%5d", M.data[count].e);
                count++;
            }
            else{
                printf("%5d", 0);
            }
        }
        printf("\n");
    }
}

int main(){
    TSMatrix A;
    TSMatrix B;

    scanf("%d %d %d", &A.mu, &A.nu, &A.tu);
    for (int i =1;i<=A.tu;i++){
        scanf("%d %d %d", &A.data[i].i, &A.data[i].j, &A.data[i].e);
    }

    TransposeSMatrix(A, B);

    printMatrix(A);
    printf("\n");
    printMatrix(B);
    return 0;
}

三、程序代码及运行结果

四、收获总结

实验7 二叉树的创建及遍历

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/3055/view

二、算法思路与流程

三、程序代码及运行结果

四、收获总结

实验8 树的建立与遍历

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/3093/view

二、算法思路与流程

三、程序代码及运行结果

四、收获总结

实验9 图的建立与遍历（多城市间遍历）

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/1416/view

二、算法思路与流程

三、程序代码及运行结果

四、收获总结

实验10 最小生成树prim算法

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/1408/view

二、算法思路与流程

三、程序代码及运行结果

四、收获总结

实验11 城市畅通工程的问题

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/1414/view

二、算法思路与流程

三、程序代码及运行结果

四、收获总结

实验12 单源最短路径

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/3933/view

二、算法思路与流程

三、程序代码及运行结果

四、收获总结

实验13 拓扑排序

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/1413/view

二、算法思路与流程

三、程序代码及运行结果

四、收获总结

实验14 二叉搜索树的构建与应用

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/3065/view

二、算法思路与流程

三、程序代码及运行结果

四、收获总结

实验15 对大量数据快速排序

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/1479/view

二、算法思路与流程

三、程序代码及运行结果

四、收获总结

实验16 堆的建立和维护

一、实验内容与要求

https://acm.zjnu.edu.cn/problem/3067/view

二、算法思路与流程

三、程序代码及运行结果

四、收获总结

作业

两个有序链表的合并

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

typedef int ElemType;
typedef struct Lnode
{
    ElemType data;
    struct Lnode* next;
} Lnode, * linkLnode;

int h_insert_Lnode(Lnode* H, ElemType m) {
    Lnode* p = H;
    for (int i = 0; i < m; i++) {
        ElemType val = 0;
        Lnode* n = (Lnode*)malloc(sizeof(Lnode));
        scanf("%d", &val);
        n->data = val;
        n->next = NULL;
        p->next = n;
        p = p->next;
    }
    return 0;
}

void print_Lnode(Lnode* h) {
    Lnode* p = h->next;
    int sum = 0, t = 1;
    while (p != NULL) {
        printf("%d ", p->data);
        if (t % 2 == 1)sum += p->data;
        t++;
        p = p->next;
    }
    printf("\n");
    printf("%d\n", sum);
}


struct Lnode* mergeTwoLists(struct Lnode* l1, struct Lnode* l2) {
    Lnode* la = l1->next, * lb = l2->next, * lc, * ld;
    lc = (Lnode*)malloc(sizeof(Lnode));
    ld = lc;

    while (la&& lb) {
        if (la->data <= lb->data) {
            lc->next = la;
            la = la->next;
        }
        else {
            lc->next = lb;
            lb = lb->next;
        }
        lc = lc->next;
    }
    lc->next = la ? la : lb;
    return ld;
}


int main() {
    Lnode* A = (Lnode*)malloc(sizeof(Lnode));
    A->next = NULL;
    Lnode* B = (Lnode*)malloc(sizeof(Lnode));
    B->next = NULL;
    int n = 0;
    int m = 0;
    scanf("%d %d", &n, &m);
    h_insert_Lnode(A, n);
    h_insert_Lnode(B, m);
    Lnode* C = mergeTwoLists(A, B);
    print_Lnode(C);
    return 0;
}

链表的删除

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

#define OK 1
#define ERROR 0
#define LIST_SIZE 100
#define LISTINCREMENT 10
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct Lnode
{
    ElemType data;
    struct Lnode* next;
} Lnode, * LinkList;

int ListLength(LinkList L) {
    Lnode* p = L;
    int k = 0;
    while (p->next) {
        p = p->next;
        k++;
    }
    return k;
}

Status GetElem(Lnode* L, int i, ElemType &e) {
    Lnode* p = L->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) return ERROR;
    e = p->data;
    return OK;
}

Status ListInsert_L(LinkList L, int i, ElemType& e) {
    Lnode* p = L,*s;
    int j = 0;
    while (!p || j < i - 1) { p = p->next; j++;}
    if (!p || j > i - 1) return ERROR;
    s = (Lnode*)malloc(sizeof(Lnode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

Status ListDelete_L(LinkList L, int i, ElemType *e) {
    Lnode* p = L, * s;
    int j = 0;
    while (p->next && j < i-1) { p = p->next; j++; }
    if (!p->next || j > i-1) return ERROR;
    s = p->next;
    *e = s->data;
    p->next = s->next;
    free(s);
    return OK;
}

Status CreateList_L(LinkList L, int n) {
    Lnode* p,*m;
    ElemType q;
    m = L;
    for (int i = 0; i < n; i++) {
        p = (LinkList)malloc(sizeof(Lnode));
        p->next = NULL;
        scanf("%d ", &q);
        p->data = q;
        m->next = p;
        m = m->next;
    }
    return OK;
}

void ClearList(LinkList& L) {
    Lnode* p;
    while (L->next) {
        p = L->next;
        L->next = p->next;
        free(p);
    }
}

struct Lnode* mergeTwoLists(struct Lnode* l1, struct Lnode* l2) {
    Lnode* la = l1->next, * lb = l2->next, * lc, * ld;
    lc = (Lnode*)malloc(sizeof(Lnode));
    ld = lc;

    while (la && lb) {
        if (la->data <= lb->data) {
            lc->next = la;
            la = la->next;
        }
        else {
            lc->next = lb;
            lb = lb->next;
        }
        lc = lc->next;
    }
    lc->next = la ? la : lb;
    return ld;
}

int main() {
    int n,count,q;
    ElemType e;
    Lnode *h = NULL;
    h = (LinkList)malloc(sizeof(Lnode));
    h->next = NULL;
    scanf("%d", &n);
    CreateList_L(h,n);
    scanf("%d", &count);
    for (int i = 0; i < count; i++) {
        scanf("%d", &q);
        if (!ListDelete_L(h, q, &e)) printf("-1\n");
        else printf("%d\n", e);
    }
    return 0;
}

链表的操作

//还包括总结的一些其他操作

#include <bits/stdc++.h>
using namespace std;
#define OK 1
#define ERROR 0
#define LIST_SIZE 100
#define LISTINCREMENT 10
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;
typedef struct Lnode
{
    ElemType data;
    struct Lnode* next;
} Lnode, * LinkList;

Status Reverse(LinkList L) {
    Lnode* p = L->next, * q, * s;
    q = p->next;
    if (!q->next) {
        L->next = q;
        q->next = p;
        p->next = NULL;
        return OK;
    }
    p->next = NULL;
    s = q->next;
    do {
        q->next = p;
        p = q;
        q = s;
        s = s->next;
        
    } while (s);
    q->next = p;
    L->next = q;
    return OK;
}

ElemType add_L(LinkList L) {
    Lnode* p = L->next;
    int sum = 0;
    while (p) { sum += p->data; p = p->next; }
    return sum;
}

Status GetElem(Lnode* L, int i, ElemType& e) {
    Lnode* p = L->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) return ERROR;
    e = p->data;
    return OK;
}

ElemType LocateElem_L(LinkList L, ElemType *q) {
    Lnode* p = L->next;
    int k = 1;
    while (p) {
        if (*q == p->data) return k;
        k++;
        p = p->next;
    }
    return ERROR;
}

Status ListInsert_L(LinkList L, int i, ElemType& e) {
    Lnode* p = L, * s;
    int j = 0;
    while (!p || j < i - 1) { p = p->next; j++; }
    if (!p || j > i - 1) return ERROR;
    s = (Lnode*)malloc(sizeof(Lnode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

Status ListDelete_L(LinkList L, int i, ElemType* e) {
    Lnode* p = L, * s;
    int j = 0;
    while (p->next && j < i - 1) { p = p->next; j++; }
    if (!p->next || j > i - 1) return ERROR;
    s = p->next;
    *e = s->data;
    p->next = s->next;
    free(s);
    return OK;
}

Status CreateList_L(LinkList L, int n) {
    Lnode* p, * m;
    ElemType q;
    m = L;
    for (int i = 0; i < n; i++) {
        p = (LinkList)malloc(sizeof(Lnode));
        p->next = NULL;
        scanf("%d ", &q);
        p->data = q;
        m->next = p;
        m = m->next;
    }
    return OK;
}

void ClearList(LinkList& L) {
    Lnode* p;
    while (L->next) {
        p = L->next;
        L->next = p->next;
        free(p);
    }
}

struct Lnode* mergeTwoLists(struct Lnode* l1, struct Lnode* l2) {
    Lnode* la = l1->next, * lb = l2->next, * lc, * ld;
    lc = (Lnode*)malloc(sizeof(Lnode));
    ld = lc;

    while (la && lb) {
        if (la->data <= lb->data) {
            lc->next = la;
            la = la->next;
        }
        else {
            lc->next = lb;
            lb = lb->next;
        }
        lc = lc->next;
    }
    lc->next = la ? la : lb;
    return ld;
}
Status print_L(LinkList L) {
    Lnode* p = L->next;
    while (p) { printf("%d ",p->data); p = p->next; }
    return 0;
}

int main() {
    Lnode* h = (LinkList)malloc(sizeof(Lnode));
    h->next = NULL;
    int n, m, index;
    ElemType e, a, b;
    cin >> n >> m;
    CreateList_L(h, n);
    string s;
    for (int i = 1; i <= m; i++) {
        cin >> s;
        if (s[0] == 'I') {
            cin >> a >> b;
            ListInsert_L(h, a, b);
        }
        else if (s[0] == 'D') {
            cin >> index;
            ListDelete_L(h, index, &b);
            cout << b << endl;
        }
        else if (s[0] == 'G') {
            cin >> index;
            GetElem(h, index, e);
            cout << e << endl;
        }
        else if (s[0] == 'L') {
            cin >> b;
            index = LocateElem_L(h, &b);
            cout << index << endl;
        }
        else {
            ClearList(h);
        }
    }
    return 0;
}

单链表的逆转求和

#include <bits/stdc++.h>
using namespace std;
#define OK 1
#define ERROR 0
#define LIST_SIZE 100
#define LISTINCREMENT 10
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;
typedef struct Lnode
{
    ElemType data;
    struct Lnode* next;
} Lnode, * LinkList;

Status CreateList_L(LinkList L, int n) {
    Lnode* p, * m;
    ElemType q;
    m = L;
    for (int i = 0; i < n; i++) {
        p = (LinkList)malloc(sizeof(Lnode));
        p->next = NULL;
        cin >> q;
        p->data = q;
        m->next = p;
        m = m->next;
    }
    return OK;
}

Status Reverse(LinkList L) {
    Lnode* p = L->next, * q, * s;
    q = p->next;
    if (!q->next) { //只有两个元素时直接交换
        L->next = q;
        q->next = p;
        p->next = NULL;
        return OK;
    }
    p->next = NULL;
    s = q->next;
    do {
        q->next = p;
        p = q;
        q = s;
        s = s->next;
        
    } while (s);
    q->next = p;
    L->next = q;
    return OK;
}

ElemType add_L(LinkList L) {
    Lnode* p = L->next;
    int sum = 0;
    while (p) { sum += p->data; p = p->next; }
    return sum;
}

Status print_L(LinkList L) {
    Lnode* p = L->next;
    while (p) { printf("%d ",p->data); p = p->next; }
    return OK;
}


int main() {
    Lnode* h = (LinkList)malloc(sizeof(Lnode));
    h->next = NULL;
    int n;
    cin >> n;
    CreateList_L(h, n);
    if(n>1) Reverse(h); //考虑n=1或n=2的情况
    print_L(h);
    printf("\n");
    printf("%d",add_L(h));
    
    return 0;
}

汉诺塔问题

#include <stdio.h>

void move(char A,int n,char C){
    printf("%c->%d->%c\n",A,n,C);
}
void hanoi (int n,char A,char B,char C){
    if(n==1){
        move(A,1,C);
    }
    else {
        hanoi(n-1,A,C,B);
        move(A,n,C);
        hanoi(n-1,B,A,C);
    }
}
int main(){
    int n;
    char a,b,c;
    scanf("%d %c %c %c",&n,&a,&c,&b);
    hanoi(n,a,b,c);
}

循环队列插入与删除操作

#include<cstdio>
#include<cstdlib>
#include<cstring>
#define QUEUE_INIT_SIZE 31000
#define OK 1
#define OVERFLOW -2
#define error -1

typedef int DataType;
typedef int Status;
typedef struct duilie{
    int f;
    int r;
    DataType *base;
}queue;
int dlength(&s){
    return (s.r - s.f + QUEUE_INIT_SIZE) % QUEUE_INIT_SIZE;
}
Status init(queue &s){
    s.base = (DataType*)malloc(QUEUE_INIT_SIZE*sizeof(DataType));
    if(s.f==NULL)return -1;
    s.f = s.r = 0;
    return OK;
}
Status in(queue &s,DataType e){
    if(s.f == (s.r +1)%QUEUE_INIT_SIZE) exit(OVERFLOW);
    s.base[s.r]=e;
    s.r = (s.r +1)%QUEUE_INIT_SIZE;
    return OK;
}
int del(queue &s){
    if(s.f ==s.r) return -1;
    DataType q = s.base[s.f];
    s.f =(s.f+1) %QUEUE_INIT_SIZE;
    return q;
}
int main(){
    queue d;
    init(d);
    int n,i;
    scanf("%d",&n);getchar(); 
    for(i=0;i<n;i++){
        char a[100];
        int x,t;
        scanf("%s", a);
        if(strcmp(a,"enqueue")==0){
            scanf("%d",&x);
            in(d,x);
        }
        if(strcmp(a,"dequeue")==0){
            t=del(d);
            printf("%d\n",t);
        }
    }
    return 0;
}

LOADING

C语言数据结构练习

学习通的作业

实验

实验1 顺序表的基本操作

实验2 链表及其多项式相加

实验3 实践栈结构-括号匹配算法

实验4 实践栈结构-编译器中的表达式求值问题

实验5 字符串的模式匹配(KMP)

实验6 稀疏矩阵的建立与转置

实验7 二叉树的创建及遍历

实验8 树的建立与遍历

实验9 图的建立与遍历（多城市间遍历）

实验10 最小生成树prim算法

实验11 城市畅通工程的问题

实验12 单源最短路径

实验13 拓扑排序

实验14 二叉搜索树的构建与应用

实验15 对大量数据快速排序

实验16 堆的建立和维护

作业

两个有序链表的合并

链表的删除

链表的操作

单链表的逆转求和

汉诺塔问题

循环队列插入与删除操作