C语言线性表

大二

C语言

发布日期: 2020-09-29

更新日期: 2021-12-01

文章字数: 1.5k

阅读时长: 8 分

前言

文件结构：

l.cpp 定义链表功能函数

#include "l.h"

功能一。。。
功能二。。。

l.h 存放链表函数原型，结构体定义

#ifndef __L_H__
#define __L_H__

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

结构体定义
函数原型

#endif

main.cpp 执行链表的操作
```
#include "l.h"
void main(){
    ...
}
```

单链表

分为不带头，带头，无说明则代码通用。 ***说明通用

l.h

node 链表的节点
nodep 指向该节点的指针

typedef int elemtype;
typedef struct lnode {
    elemtype data;
    struct lnode *next;
}node;

typedef node* nodep;

void init(nodep& p);
void create_h(nodep& p);
void create_t(nodep& p);
void free(nodep& p);
void travel(const nodep& p);
int len(const nodep& p);
int locate(const nodep& head,int n);
void insert(nodep& head);
void del(nodep& head);
void clear(nodep& head);

init ***

void init(nodep& p) {
    p = NULL;
}

create

带头：

void create_h(nodep& head) {
    head = new node;
    head->next = NULL;

    int cnt = 0, n;
    printf("input the node num:\n");
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        nodep tmp = new node;
        scanf("%d", &tmp->data);
        tmp->next = head->next;
        head->next = tmp;
    }
}

不带头：

void create_h(nodep& head) {
    head = new node;
    head->next = NULL;
    
    int cnt = 0, n;
    printf("input the node num:\n");
    scanf("%d", &n);

    scanf("%d", &head->data);
    for (int i = 1; i < n; i++) {
        nodep tmp = new node;
        scanf("%d", &tmp->data);
        tmp->next = head;      //步骤一：将新建的节点连上去
        head = tmp;            //步骤二：改变头指针的位置
    }
}
//多了在首处填值的步骤

free ***

void free(nodep& head) {
    while (head) {
        nodep tmp = head->next;
        delete head;
        head = tmp;
    }
}

travel

void travel(const nodep& head) {
    nodep tmp = head->next; //带头，不带头的将tmp指向头
    int cnt = 1;
    while (tmp) {
        printf("%d: %d\n", cnt, tmp->data);
        tmp = tmp->next;
        cnt++;
    }
}

len

int len(const nodep& head) {
    int cnt = 0;
    nodep tmp = head->next; //带头，不带头的将tmp指向头
    while (tmp) {
        cnt += 1;
        tmp = tmp->next;
    }
    return cnt;
}

locate

int locate(const nodep& head,int n) {
    nodep tmp = head->next; //带头，不带头的将tmp指向头
    int i=1;
    while (tmp) {
        if ((tmp->data) == n) return i;
        else {
            tmp = tmp->next;
            i += 1;
        }
    }
    return 0;
}

insert

不带头：

void insert(nodep& head) {
    int n, num,i=2;
    printf("input the address:\n");
    scanf("%d", &n);
    printf("input the num:\n");
    scanf("%d", &num);

    if (n == 1) {
        nodep m = new node;
        m->data = num;
        m->next = head;
        head = m;
        return;
    }

    nodep p = head;
    while (p) {
        if (i == n) {
            nodep m = new node;
            m->data = num;
            m->next = p->next;
            p->next = m;
            printf("complete\n");
            return;
        }
        else {
            i += 1;
            p = p->next;
        }
    }
    printf("error input\n ");
    return;
}

带头：

void insert(nodep& head) {
    int n, num, i = 1;
    printf("input the address:\n");
    scanf("%d", &n);
    printf("input the num:\n");
    scanf("%d", &num);

    nodep p = head;
    while (p) {
        if (i == n) {
            nodep m = new node;
            m->data = num;
            m->next = p->next;
            p->next = m;
            printf("complete\n");
            return;
        }
        else {
            i += 1;
            p = p->next;
        }
    }
    printf("error input\n ");
    return;
}

del

不带头：

void del(nodep& head) {
    int n,i=1;
    printf("input the num should del:\n");
    scanf("%d", &n);

    nodep p, q;
    if (n == 1) {
        q = head;
        head = head->next;
    }
    else {
        p = head;
        while (p != NULL && i < n - 1) {
            p = p->next;
            i++;
        }
        if (p == NULL || p->next == NULL) {
            printf("error");
            return;
        }
        else {
            q = p->next;
            p->next = q->next;
        }
        delete q;
    }
}

带头：

void del(nodep& head) {
    int n, i = 1;
    printf("input the num should del:\n");
    scanf("%d", &n);

    nodep p, q;
    p = head;
    while (p != NULL && i < n - 1) {
        p = p->next;
        i++;
    }
    if (p == NULL || p->next == NULL) {
        printf("error");
        return;
    }
    else {
        q = p->next;
        p->next = q->next;
    }
    delete q;
}

clear

void clear(nodep& head) {
    nodep p = head->next; //带头，不带头的将p指向头
    while (p) {
        p->data = 0;
        p = p->next;
    }
}

双向循环链表

分为不带头，带头，无说明则代码通用。 ***说明通用

l.h

node 链表的节点
nodep 指向该节点的指针

typedef int elemtype;
typedef struct lnode {
    elemtype data;
    struct lnode *next, *pre;
}node;

typedef node* nodep;

void init(nodep& p);
void create_h(nodep& p); //头插
void create_t(nodep& p); //尾插
void free(nodep& p);
void travel(const nodep& p);
int len(const nodep& p);
int locate(const nodep& head, int n);
void insert(nodep& head);
void del(nodep& head);
void clear(nodep& head);

init ***

void init(nodep& p) {
    p = new node;
    if (p == NULL) {
        printf("error");
        exit(1);
    }
    p->next = p->pre = p;
}

create

不带头：

void create_t(nodep& head) {
    nodep p = head, q;
    int n;
    printf("input the node num:\n");
    scanf("%d", &n);
    n -= 1;
    scanf("%d", &head->data);
    while (n--) {
        q = new node;
        scanf("%d", &q->data);
        p->next = q;
        q->pre = p;
        q->next = head;
        head->pre = q;
        p = q;
    }
}

带头：

void create_t(nodep& head) {
    nodep p = head, q;
    int n;
    printf("input the node num:\n");
    scanf("%d", &n);
    while (n--) {
        q = new node;
        scanf("%d", &q->data);
        p->next = q;
        q->pre = p;
        q->next = head;
        head->pre = q;
        p = q;
    }
}

free ***

void free(nodep& head) {
    nodep p;
    head->pre->next = NULL; //设置断点
    while (head->next) {
        p = head->next;
        head->next = p->next;
        delete p;
    }
}

travel

void travel(const nodep& head) {
    nodep tmp = head->next;  //带头，不带头的将tmp指向头
    int cnt = 1;
    do {
        printf("%d: %d\n", cnt, tmp->data);
        tmp = tmp->next;
        cnt++;
    } while (tmp != head);
}

len

不带头：

int len(const nodep& head) {
    int cnt = 0;
    nodep tmp = head;
    do {
        cnt += 1;
        tmp = tmp->next;
    } while (tmp != head);
    return cnt;
}

带头：

int len(const nodep& head) {
    int cnt = 0;
    nodep tmp = head->pre;
    while (tmp != head) {
        cnt++;
        tmp = tmp->pre;
    }
    return cnt;
}

locate

不带头：

int locate(const nodep& head, int n) {
    nodep tmp = head;
    int i = 1;
    do {
        if ((tmp->data) == n) return i;
        else {
            tmp = tmp->next;
            i++;
        }
    } while (tmp != head);
    return 0;
}

带头：

int locate(const nodep& head, int n) {
    nodep tmp = head->next;
    int i = 1;
    while (tmp != head) {
        if ((tmp->data) == n) return i;
        else {
            tmp = tmp->next;
            i++;
        }
    }
    return 0;
}

insert

不带头：

void insert(nodep& head) {
    int n, num, i = 2;
    printf("input the address where insert:\n");
    scanf("%d", &n);
    printf("input the num:\n");
    scanf("%d", &num);

    nodep p = head;
    if (n == 1) {
        nodep m = new node;
        m->data = num;
        m->pre = head->pre;
        m->next = head;
        head->pre->next = m;
        head->pre = m;
        head = m; 
        return;
    }
    while (p) {
        if (i == n) {
            nodep m = new node;
            m->data = num;
            m->pre = p;
            m->next = p->next;
            p->next->pre = m;
            p->next = m;
            printf("complete\n");
            return;
        }
        else {
            i += 1;
            p = p->next;
        }
    }
    printf("error input\n ");
    return;
}

带头：

void insert(nodep& head) {
    int n, num, i = 1;
    printf("input the address where to insert:\n");
    scanf("%d", &n);
    printf("input the num:\n");
    scanf("%d", &num);

    nodep p = head;
    while (p) {
        if (i == n) {
            nodep m = new node;
            m->data = num;

            m->pre = p;
            m->next = p->next;
            p->next->pre = m;
            p->next = m;
            printf("complete\n");
            return;
        }
        else {
            i += 1;
            p = p->next;
        }
    }
    printf("error input\n ");
    return;
}

del

不带头：

void del(nodep& head) {
    int n, i = 1;
    printf("input the address of num should del:\n");
    scanf("%d", &n);

    nodep p = head, q;
    do {
        if (i == n) {
            p->pre->next = p->next;
            p->next->pre = p->pre;
            delete p;
            return;
        }
        i++; 
        p = p->next;
    } while (p != head);
}

带头：

void del(nodep& head) {
    int n, i = 1;
    printf("input the address of num should del:\n");
    scanf("%d", &n);

    nodep p = head->next;
    while (p != head) {
        if (i == n) {
            p->pre->next = p->next;
            p->next->pre = p->pre;
            delete p;
            return;
        }
        i++;
        p = p->next;
    }
}

clear

void clear(nodep& head) {
    nodep p = head->next; //带头，不带头的将p指向头
    do {
        p->data = 0;
        p = p->next;
    } while (p != head);
}

小结

c语言真累。。。

╯晓~

https://www.unielu.com/posts/fd16.html

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !

大二

表达式求值

使用C语言，栈的应用

2020-09-29 C语言

大二

math模块

参照官方文档

2020-09-22 python

python模块