数据结构上机实践 线性链表实现

╮ 潜心 ╰ edited 2 年,3 月前

复习时顺便把顺序链表的题也用链式的实现了一遍
只打了前三题 分别是线性表、线性表比较和顺序表去重
后续有补充再更吧

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

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

node *Creat_List (int n) {
//创建一个长度为n的线性链表,并返回表头
    node *head = (node *)malloc(sizeof(node));
    head->next = NULL;
    int input;
    node *p = head;
    while (n--) {
        scanf("%d", &input);
        node *q = (node *)malloc(sizeof(node));
        q->data = input;
        p->next = q;
        q->next = NULL;
        p = q;
    }
    return head;
}
void Print_List (node *head) {
//输出线性表中所有元素(元素用空格分隔,行末无空格)
    node *p = head->next;
    while (p != NULL) {
        printf("%d%c", p->data, p->next == NULL? '\n': ' ');
        p = p->next;
    }
}
void Destroy_List (node *head) {
//销毁线性链表
    node *p;
    while (head) {
        p = head->next;
        free(head);
        head = p;
    }
}
int Delete_Elem (node *head, int pos) {
//删除线性链表的第n个元素(索引起始为1),下标非法返回-1,合法返回删除元素的值
    int cnt = 0, elem;
    node *p = head, *q;   //q为待删节点
    while (p->next && cnt < pos - 1) {
        ++cnt;
        p = p->next;
    }
    if (!p->next || cnt > pos - 1) return -1;
    q = p->next;
    p->next = q->next;
    elem = q->data;
    free(q);
    return elem;
}
int comp (node *a, node *b) {
//线性表比较:a>b返回1,a==b返回0,a<b返回-1
    node *p = a->next, *q = b->next;
    while (p && q) {
        if (p->data > q->data) return 1;
        else if (p->data < q->data) return -1;
        p = p->next;
        q = q->next;
    }
    if (!p || p->data < q->data) return -1;
    else if (!q || p->data > q->data) return 1;
    else return 0;
}
void Reverse_List (node *head) {
    node *p = head->next, *p_next = NULL, *p_prev;
    head->next = NULL;
    while (p) {
        p_prev = p->next;
        p->next = p_next;
        p_next = p;
        p = p_prev;
    }
    head->next = p_next;
}
int main()
{
    //freopen("testin.txt", "r", stdin);
    /*
    //线性表删除的主函数
    int n, m, pos;
    scanf("%d", &n);
    node *head = Creat_List (n);
    scanf("%d", &m);
    while (m--) {
        scanf("%d", &pos);
        printf("%d\n", Delete_Elem(head, pos));
    }
    Destroy_List(head);

    //线性表比较的主函数
    int na, nb;
    scanf("%d%d", &na, &nb);
    node *a = Creat_List (na);
    node *b = Creat_List (nb);
    printf("%d\n", comp(a, b));
    Destroy_List(a);
    Destroy_List(b);

    //倒置顺序表的主函数
    int n;
    scanf("%d", &n);
    node *head = Creat_List (n);
    Print_List(head);
    Reverse_List (head);
    Print_List(head);
    Destroy_List(head);
    */
    return 0;
}

Comments

Obliviate

666

10175102204

你当前正在回复 博客/题目
存在问题!