用C语言创建一个链表数据结构

浏览数:472

2019-8-31

链表是一种数据结构，对于要学习数据结构的人学习好链表是非常重要的。
一个链表需要包含什么呢，我的理解就是：1、有n个节点离散分配，2、每个节点通过指针来连接，3、每个节点都有一个前驱节点和一个后驱节点，4、首节点没有前驱节点，尾节点没有后驱节点。

一、节点的构造

typedef struct Nod
{
  int data;//存放数据的域
  struct Node *pNext;  //定义一个结构体指针，指向下一个数据类型相同的节点    
}NODE,*PNODE; //NODE等价于 struct Node; PNODE等价于struct Node *； 此处用大写是为了与变量区分，可以让人容易变出是个数据类型

typedef 只是给数据类型取个别名，即 typedef 数据类型别名；我们知道struct Node 是我们定义的数据类型；
（2）链表的创建
在创建链表之前，我们需要需要了解一下专业术语：
首节点：存放第一个有效数据的节点；
尾节点：存放最后一个有效数据的节点；
头节点：头节点的数据类型与首节点的数据类型相同，并且头节点是首节点前面的那个节点，并不存放有效数据；头节点的存在只是为了方便链表的操作。
头指针：指向头节点的指针；
尾指针：指向尾节点的指针；

二、在头节点后面插入一个节点

PNODE Create_Lise(void){
    int len;//存放链表的长度
    int i;//循环变量
    int val;//用来临时存放变量
    PNODE Lise;
    PNODE pHead=(PNODE) malloc(sizeof(NODE));//分配一个节点
    if(pHead==NULL){
        printf("请输入链表的值");
        exit(-1); 
    }else{
        PNODE pTail=pHead;
        pHead->pNext=null;
        printf("需要一个指针指向结尾");
        scanf("%d",&len);
        for(i=o;i<len;i++){
            PNODE p=(PNODE)malloc(sizeof(NODE));
            if(null=p){
                printf("插入了");
                exit(-1); 
            } else{
                printf("我在最后插入");
                scanf("%d",&val);
                p->data=val;
                pTail->pNext=p;
                p->pNext=null;
                pTail=p; 
            }
        } 
    }
}

三、向链表插入元素

//链表的第pos有效元素前面插入元素val，首先我们应该找到第pos个元素前面一个元素的位置；  
//当链表有3个元素时，pos=4，将不会进行插入操作  
 bool Insert_List(PNODE pHead,int pos,int val){
    int i=0;
    PNODE p=pHead;
    while((Null!=p)&&(i<pos-1)){
        p=p->pNext;
        i++
     }
     if(p==null||i>pos-1)//把链表为空的情况考虑进去了；i>pos-1可以防止用户输入错误；
     return false;
     
     //程序执行到这之后，i=pos-1；p指针指向链表第pos个有效节点前驱，即指向第pos-1节点；
     PNODE q=(PNODE)malloc(sizeof(NODE));
     q->data=val;
     q->pNext=p->pNext;
     p->pNext=q; 
 }

四、删除链表中的元素

 bool Delete_Lise(PNODE pHead,int pos,int *var){
    int i=0;
    PNODE p=pHead;
    while((NULL!=p)&&(i<pos-1)){
        p=p->pNext;
        i++; 
    } 
    if(p==null||i>pos-1) //把链表表为空的情况去了
    return false;
    
     //程序执行到这后，i=pos-1；
     PNODE q=p->pNext;//q指向待删除的节点
     *val=q->data;
     p->pNext=q->pNext;//修改链表的指向
     free(q);          //释放q所指向节点的内存 
     q=NULL;  //如果不清空，会出现野指针 
 }

五来来来冒泡排序一下

void Sort_List(PNODE pHead){
    int i,j;
    int temp;
    int len=length_List(pHead);
    PNODE p,q;
    for(i=0,p-pHeda->pNext;i<len-1;i++,p->pNext){
        for(j=i+1,q=p->pNext;i<len;j++,q=q->pNext){
            
            //交换数据
              if(p->data>q->data){
                temp=p->data;
                p->data=q->data;
                q->data=temp;
              } 
          }
      } 
  }

作者：顾四秋

原文地址：https://www.jianshu.com/p/ccebe9fd66c6

喜欢 0

用C语言创建一个链表数据结构

相关推荐