文档章节

链表的增删改查的操作

r
 ranjiewen
发布于 2016/11/03 23:48
字数 1910
阅读 46
收藏 0
     看来几篇博客,自己还没有实践

#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(struct student)

/*----------------数据定义----------------------*/ 

//定义一个学生信息的结构体,包括学号,姓名和结构体类型的指针 
struct student
{
    long num;                //学号 
    char name[128];            //姓名 
    struct student *next;    //结构体指针 
};

typedef struct student * stuNode;

int n=0;                    //全局变量,记录链表的长度 
 
/*---------------函数声明---------------------*/
 
stuNode Create();            //创建一个新的链表                     

void Print(stuNode head);    //通过传入的链表头指针打印整个链表 

stuNode Delete(stuNode head,int num);    //通过传入的链表头指针和学生学号删除节点 

stuNode Insert(stuNode head,stuNode newStu);    //依照学生学号的顺序向链表中插入新元素 


/*---------------函数定义----------------------*/

struct student *Create()
{
    struct student *head,*p1,*p2;
    
    //开辟一个LEN大小的空间,并让p1,p2指针指向它 
    p2=p1=(struct student *)malloc(LEN);
    //将头指针置为NULL 
    head=NULL;
    
    //创建链表节点并给节点的元素赋值 
    printf("请输入学生的学号和姓名:");
    scanf("%ld %s",&p1->num,p1->name);
    while(p1->num!=0)
    {
        n=n+1;
        if(NULL==head)
        {
            head=p1;
        }
        else
        {
            p2->next=p1;
        }
        p2=p1;
        p1=(struct student *)malloc(LEN);
        printf("请输入学生的学号和姓名:");
        scanf("%ld %s",&p1->num,p1->name);
    }
    //将尾节点的指针置为NULL 
    p2->next=NULL;
    return head;
}


void Print(struct student *head)
{
    struct student * p;
    p=head;
    
    //判断链表是否为空 
    if(NULL==head)
    {
        printf("链表为空!\n");
        return head;
    }
    else
    {
        //循环打印链表中的元素 
        printf("%d 个记录分别为:\n",n);
        while(p!=NULL)
        {
            printf("%ld %s\n",p->num,p->name);
            //指针指向下一个节点 
            p=p->next;
        }
    }
}


struct student *Delete(struct student * head,int num)
{
    struct student *p1;
    struct student *p2;
    p1=head;
    //判断链表是否为空 
    if(NULL==head)
    {
        printf("链表为空!\n");
        return head;
    }
    //遍历节点,判断当前节点是不是需要删除的节点及是否为尾节点
    //如果找到相应节点,或者已经遍历到尾节点就跳出循环 
    while(p1->num!=num&&p1->next!=NULL)
    {
        p2=p1;
        p1=p1->next;
    }
    //判断是否找到相应节点 
    if(p1->num==num)
    {
        //要删除的节点是不是链表的第一个节点
        //如果是,就将头指针指向该节点的后一个节点
        //如果不是,就将该节点的前一个节点的指针指向该节点的后一个节点 
        if(head==p1)
        {
            head=p1->next;
        }
        else
        {
            p2->next=p1->next;
        }
        n=n-1;
        printf("%ld 节点已删除.\n",num);
    }
    else
    {
        printf("链表中没有要删除的元素.\n");
    }
    return head;
}


struct student *Insert(struct student * head,struct student * newStu)
{
    struct student *p0;
    struct student *p1;
    struct student *p2;
    p0=newStu;
    p1=head;
    //判断链表是否为空,如果是空链表,就将新节点作为第一个节点 
    if(NULL==head)
    {
        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(p1==head)
            {
                head=p0;
            }
            else
            {
                p2->next=p0;
            }
              p0->next=p1;
        }
        else
        {
            p1->next=p0;
            p0->next=NULL;
        }
    }
    //链表长度加1 
    n=n+1;
    printf("%ld 插入成功!\n",newStu->num);
    return head;
}

void main()
{
    struct student *head;
    struct student *stu;
    int num;
    head=Create();
    Print(head);
    printf("请输入要删除的学号:");
    scanf("%ld",&num);
    while(num!=0)
    {
        head=Delete(head,num);
        Print(head);
        printf("请输入要删除的学号:");
        scanf("%ld",&num);
    }
    printf("请输入要插入的节点:");
    stu=(struct student *)malloc(LEN);
    scanf("%ld %s",&stu->num,stu->name);
    while(stu->num!=0)
    {
        head=Insert(head,stu);
        printf("请输入要插入的节点:");
        stu=(struct student *)malloc(LEN);
        scanf("%ld %s",&stu->num,stu->name);
    }
    Print(head);
}

 参考:

#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct student)
struct student{
    int num;
    double score;
    struct student *next;
};
 
//创建一个链表
struct student * create(void){
    struct student *p1,*p2,*head;
    int n = 0;
    p1 = p2 = (struct student *)malloc(LEN);
    scanf("%d%lf",&(p1->num),&(p1->score));
    while(p1->num!=0){
        n++;
        if(n==1){
            head = p1;
        }else{
            p2 = p1;
        }
        p1 = (struct student *)malloc(LEN);
        scanf("%d%lf",&(p1->num),&(p1->score));
        p2->next = p1;
    }
     
    p2->next = NULL;
    return head;
}
struct student *delw(struct student *start,int num){
    struct student *p1,*p2;
    //链表为空
    if(start==NULL){
        printf("\nlist null!\n");
        return NULL;
    }
    p1 = start;
    p2 = NULL;
    //链表不为空
    //链表只有一个元素,且即为所要找的元素
    /*if(p1->next==NULL&&p1->num == num){
        printf("there is only one element and that is it!");
        return NULL;
    }*/
    while(p1->next!=NULL&&p1->num!=num){
        p2 = p1;
        p1 = p1->next;
    }
     
    if(num == p1->num){
        if(p1 == start){
            return start->next;
        }else{
            p2->next = p1->next;
        }
    }else{
        printf("number not found!");
    }
     
    return start;
}
 
struct student *del(struct student *head,long num){
 
    struct student *p1, *p2;
    //链表为空
    if(head == NULL){
        printf("\nlist null!\n");
        return head;
    }
    //链表不为空
    p1 = head;
    while(p1->next!=NULL&&num!=p1->num){
        p2 = p1;
        p1 = p1->next;
    }
    if(num == p1->num){
        if(p1 == head){
            head = p1->next;
        }else{
            p2->next = p1->next;
            printf("delete:%ld\n",num);
        }
    }else
            printf("%ld not been found!\n",num);
    return head;
 
}
//删除一个节点
struct student * deleteNode(struct student *start,int num){
    struct student *p1, *p2,*before,*after;
    //空表
    if(start==NULL){
        printf("the linktable is null");
        return NULL;
    }
    p1 = p2 = start;
    //只有一个节点
    if(start->next==NULL){
        if(start->num==num){
            return NULL;
        }
    }
    //链表不为空(两个以上的节点)
    //1:链表的第一个即为所要找的
    if((start->num == num)&&(start->next!=NULL)){
        return start->next;
    }
    while(p1!=NULL){
        if(p1->num==num){
            before = p2;
            after = p1->next;
        }
        p2 = p1;
        p1 = p1->next;
    }
    before->next = after;
    return start;
}
 
struct student * insert(struct student *head,struct student *stu){
    struct student *p1,*p2, *p0;
    p1 = head;
    p0 = stu;
     
    //链表为空
    if(head == NULL){
        head = p0;
        p0->next = NULL;
        printf("the link is null\n");
        return NULL;
        //链表不为空,比较num,(如22, 33, 55),44应插入至33后面
    }else{
        //一个元素
        //printf("head.next is not null");
        //两个以上元素: 22 55 88
        while(p1->num<p0->num&&p1->next!=NULL){
            p2 = p1;
            p1 = p1->next;
        }
 
        if(p1->num>p0->num){//
            if(p1==head){//p0排到最前
                head = p0;
                p0->next = p1;
            }else{
                //p0排到中间
                p2->next = p0;
                p0->next = p1;
            }
        }else{//p0排到最后
            p1->next = p0;
            p0->next = NULL;
        }
 
        return head;
    }
     
 
}
 
void printLink(struct student *p){
    struct student *p_afterDeal = p;
    p_afterDeal = p;
    while(p_afterDeal!=NULL){
        printf("num = %d, score = %lf\n",p_afterDeal->num,p_afterDeal->score);
        p_afterDeal = p_afterDeal->next;  
    }
}
int main(void){
     
    struct student * p_std, * p_afterDel,*p,*p_afterInsert; 
    struct student newstd = {44,44.4,NULL};
    //创建一个链表
    printf("创建一个链表:\n");
    p_std = create();
    printf("创建的链表如下:\n");
    printLink(p_std);
    //插入一个节点
    printf("插入一个节点:44\n");
    p = &newstd;
    p_afterInsert = insert(p_std,p);
    printf("插入一个节点后的列表如下:\n");
    printLink(p_afterInsert);
    //删除一个节点
    printf("删除一个节点:44\n");
    p_afterDel = deleteNode(p_afterInsert,44);
    printf("删除一个节点后的列表如下:\n");
    printLink(p_afterDel);
    system("pause");
}
/**
 *C语言实现,用了三个指针操作,没用构造函数
 */
#include<iostream> 
using namespace std;
struct student {
    int data;
    struct student* next;
};
int main()
{
    int data;
    struct student *head,*tail,*temp;
    head = NULL;
    while(cin>>data && data!=-1) {
        temp = (struct student*)malloc(sizeof(struct student));
        temp->data = data;
        temp->next = NULL;
        if(head==NULL) {
        head = temp;
            tail = head;
        } else { 
            tail->next = temp;
            tail = temp;        
        }         
    }
       
    tail = head;
    while(tail!=NULL) {
        cout<<tail->data<<endl;
        tail = tail->next;
    }
    system("pause");
    return 0;
}

/**
 *C/C++实现,用了三个指针操作,用了构造函数
 */
#include<iostream> 
using namespace std;
struct student {
    int data;
    struct student* next;
    student(int a) {
        this->data = a;
        this->next = NULL; 
    }
};
int main()
{
    int data;
    struct student *head,*tail,*temp;
    head = NULL;
    while(cin>>data && data!=-1) {       
        if(head==NULL) {
            head = new student(data);
            tail = head;
         } else {
             temp = new student(data);
             //temp用来接收新节点,这样tail的next不会丢失 
             tail->next = temp;
             tail = temp;              
         }         
    }    
       
    tail = head;
    while(tail!=NULL) {
        cout<<tail->data<<endl;
        tail = tail->next;
    }
    system("pause");
    return 0;
}

/**
 *C/C++实现,用了两个指针操作,用了构造函数
 */
#include<iostream> 
using namespace std;
struct student {
    int data;
    struct student* next;
    student(int a) {
        this->data = a;
        this->next = NULL; 
    }
    student(int a, struct student* p) {
        p->next = this;
        this->data = a;
        this->next = NULL;
    }
};
int main()
{
    int data;
    struct student *head,*tail;
    head = NULL;
    while(cin>>data && data!=-1) {           
        if(head==NULL) {
            head = new student(data);
            tail = head;             
         } else {
              tail = new student(data, tail);
         }        
    }
       
    tail = head;
    while(tail != NULL) {
        cout<<tail->data<<endl;
        tail = tail->next;
    }
    system("pause");
    return 0;
}

 

参考:http://www.cnblogs.com/yanghuahui/archive/2012/04/15/2451076.html

http://www.cnblogs.com/ligang305/archive/2012/08/25/2656343.html

http://www.cnblogs.com/wolfred7464/p/4335298.html

http://www.cnblogs.com/xnwyd/archive/2010/04/28/1723151.html

本文转载自:http://www.cnblogs.com/ranjiewen/p/5901241.html

r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问
搞懂 Java LinkedList 源码

LinkedList 源码分析 由于最近工作有点忙,进行了 APP 的部分优化,期间也学习了很多有关于布局优化和其他性能优化的知识,但是仍然觉得不太成体系,期待能有更多的优质的性能优化实战文章能...

群星纪元
03/31
4
0
STL各类容器的API 修正次数 1+

双向链表: list 双向的链表。因此,适用于经常性的增删元素。常量时间 即可完成(在找到合适的插入位置的前提下)。不适合于 大量的查询操作,线性时间完成。因为不支持随机存取。 API incl...

LinuxCPlusPlus
2016/02/24
35
0
Memcached Hash算法

本文来自网易云社区 作者:吕宗胜 Hash算法 1. Memcached Hash介绍 我们在前面的文章中已经介绍过了Memcached的内存管理方式,LRU的策略。由于Memcached的数据存储方式基本上是基于双向链表来...

网易云
2018/09/11
0
0
Java 基础(四)集合源码解析 List

List 接口 前面我们学习了Iterator、Collection,为集合的学习打下了基础,现在我们来学习集合的第一大体系 List。 List 是一个接口,定义了一组元素是有序的、可重复的集合。 List 继承自 ...

diamond_lin
2017/09/26
0
0
JavaScript数据结构 之 链表

一、什么是链表  链表是一种链式存储的线性表,是由一组节点组成的集合,每一个节点都存储了下一个节点的地址;指向另一个节点的引用叫链;和数组中的元素内存地址是连续的相比,链表中的所...

TDX
06/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【运维】记一次上线前的紧急定位与修复-献上九条小经验

1 简介 本文介绍了作者所在团队在某次上线前测试发现问题、定位问题并修复上线的过程,最后给出几点经验总结,希望对大家有用。 2 过程 (1)今天需要上线,但昨晚才合并了所有分支,时间很紧...

南瓜慢说
36分钟前
4
0
Elasticsearch系列---初识Elasticsearch

Elasticsearch是什么? Elasticsearch简称ES,是一个基于Lucene构建的开源、分布式、Restful接口的全文搜索引擎,还是一个分布式文档数据库。天生就是分布式、高可用、可扩展的,可以在很短的...

清茶豆奶
48分钟前
3
0
服务安全之:JWT

JWT是JSON Web Tokens的缩写。既然叫JSON Web Tokens,所以JWT Tokens中真正包含的是多个JSON对象。为什么是多个JSON对象呢?因为SWT Token实际上是由三部分组成,其中有两部分是JSON格式。这...

popgis
今天
4
0
C++ Primer 笔记整理(一)基本语法介绍

C++被称为“完美的程序设计语言”,在chromium内核中应用非常广泛,之前没有系统学习过C++相关的知识,通过看书来学习相关的知识,现在将《C++ Primer》基本知识提取出来,供大家学习。 1.输...

天王盖地虎626
今天
2
0
你知道多少this,new,bind,call,apply?那我告诉你

那么什么是this,new,bind,call,apply呢?这些你都用过吗?掌握这些内容都是基础中的基础了。如果你不了解,那还不赶快去复习复习,上网查阅资料啥的! 通过call,apply,bind可以改变thi...

达达前端小酒馆
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部