链表

花了半天终于把链表弄清楚了,一个字——爽!

新建链表

#include <stdio.h>
#include <stdlib.h>
//这里创建一个结构体用来表示链表的结点类型
struct node
{
    int data;
    struct node *next;
};
int main()
{
    struct node *head, *p, *q, *t;
    int i, n, a;
    scanf("%d", &n);
    head = NULL;//头指针初始为空
    for (i = 1; i <= n; i++)//循环读入n个数
    {
        scanf("%d", &a);
        //动态申请一个空间,用来存放一个结点,并用临时指针p指向这个结点
        p = (struct node *)malloc(sizeof(struct node));
        p->data = a;//将数据存储到当前结点的data域中
        p->next = NULL;//设置当前结点的后继指针指向空,也就是当前结点的下一个结点为空
        if (head == NULL)
            head = p;//如果这是第一个创建的结点,则将头指针指向这个结点
        else
            q->next = p;//如果不是第一个创建的结点,则将上一个结点的后继指针指向当前结点
        q = p;//指针q也指向当前结点
    }
    //输出链表中的所有数
    t = head;
    while (t != NULL)
    {
        printf("%d ", t->data);
        t = t->next;//继续下一个结点
    }
    getchar(); getchar();
    return 0;
}

完整代码(增删)

#include <stdio.h>
#include <iostream>
using namespace std;
struct student
{
    int num;
    float score;
    struct student *next;
};

int n = 0;  //全局变量,用于记录链表结点数

int main()
{
    student *create();
    student *insert(student *head, student *stu);
    student *del(student *head, int num);
    void print(student *head);                      //函数提前声明

    student *head, stu;             //*head为新建的链表,stu为新增的数据
    int  del_num;
    head = create();                //新建链表
    print(head);
    cout << "Input the deleted number : \n";
    cin >> del_num;
    head = del(head, del_num);      //删除数据
    print(head);
    cout << "Input the inserted record : \n";
    cin >> stu.num >> stu.score;
    head = insert(head, &stu);      //添加数据
    print(head);                    //打印数据
    return 0;
}

student *create() {
    student *head, *p1, *p2;
    head = NULL;        //头指针初始为空

    p1 = p2 = new student;            //用new在内存中开辟一个结构体变量的空间,将地址赋给p1,p2
    cin >> p1->num >> p1->score;      //将数据赋给刚开辟的变量空间
    while (p1->num != 0) {
        n = n + 1;
        if (head == NULL)
            head = p1;       //如果这是第一个创建的结点,则将头指针指向这个结点
        else {
            p2->next = p1;  //如果不是第一个创建的结点,则将上一个结点的后继指针指向当前结点
            p2 = p1;        //指针p2也指向当前结点,因为等会儿p1又要指向新创建的数据
            p1 = new student;
            cin >> p1->num >> p1->score;
        }
    }
    p2->next = NULL;
    return (head);
}

void print(student *head) {
    student *p;
    p = head;
    while (p != NULL)
    {
        cout << p->num << '\t' << p->score << '\n';
        p = p->next;
    }
}

student *insert(student *head,student *stu) {
    student  *p0, *p1, *p2;
    p1 = head;    p0 = stu;     //p0指向要插入的结点
    if (head == NULL) {
        head = p0;  
        p0->next = NULL;    //链表为空
    }
    else {
        while ((p0->num > p1->num) && (p1->next != NULL)) {     //未找到结点,循环
            p2 = p1;  
            p1 = p1->next;
        }
        if (p0->num <= p1->num) {   //找到结点
            if (head == p1)  
                head = p0;  //插入在第一个结点前
            else              
                p2->next = p0;
            p0->next = p1;
        }
        else { 
            p1->next = p0;  
            p0->next = NULL;    //插入在最后一个后
        }
    }
    n = n + 1;          
    return (head);
}

student *del(student *head,int num) {
    struct  student  *p1, *p2;
    if (head == NULL) {
        cout << "list null\n";  
        return  NULL;           //链表为空
    }
    p1 = head;
    while (num != p1->num && p1->next != NULL) {    //判断p1所指向的结点是否是要删除的结点
        p2 = p1;  p1 = p1->next;    //未找到结点,循环。继续判断下一个结点是否是要删除的结点
    }
    if (num == p1->num) {   //p1当前指向的结点就是要删除的结点 
        if (num == head->num)   
            head = p1->next;    //结点为第一个
        else  
            p2->next = p1->next;    //找到结点。将p2的指针成员指向p1所指的下一个结点
        n = n - 1;
    }
    else  cout << "Not  found\n";   //循环结束,没有要找的结点
    return  head;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容