C语言线性表


前言

文件结构:

  • 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语言真累。。。


文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录