线性表-单链表

特点：
它是一种动态结构
不需预先分配空间
指针占用额外存储空间
不能随机存取，查找速度慢

带头指针的单链表.png

0、定义
n个结点链结成一个链表，每个结点只包含一个指针域，叫做单链表。

线性链表中第一个结点的存储位置叫做头指针，整个链表的存取必须从头指针开始。 线性链表的最后一个结点指针为“空”（通常用NULL或^表示）。

image.png

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

typedef int ElemType ;//数据类型

 typedef struct _LinkList{
    ElemType data;//数据域
    struct _LinkList *next;//节点
    int size;//链表个数
}LinkList;

1、初始化

/**
 * 功能：初始化链表
 * 参数：链表地址
 * 返回值：如果成功，返回链表，失败返回NULL
 */
LinkList* Init_List(){
    LinkList *pList;
    pList=(LinkList*)malloc(sizeof(LinkList));
    if(!pList){
        printf("pList动态内存分配失败！\n");
        return NULL;
    }
    pList->next=NULL;
    pList->size=0;
    printf("初始化成功\n");
    return pList;
}

2、获取链表长度

/**
 * 功能：获取链表长度
 * 参数：链表地址
 * 返回值：链表长度
 */
int Length_List(LinkList *head){
    LinkList* p=head->next;
    int length=0;
    while(p){
        p=p->next;
        length++;
    }
    printf("链表长度为%d\n",length);
    return length;
}

3、插入元素

image.png

  /**
 * 功能：向链表插入数据元素
 * 参数：链表地址 下标  插入的元素
 * 返回值：链表长度
 */
bool Insert_List(LinkList *head,int index, ElemType e){
    if(head==NULL){
        printf("链表未初始化\n");
        return false;
    }
    if(index<1||index>head->size+1){
        printf("下标越界\n");
        return false;
    }
    //开始插入
    int i;
    LinkList* pre=head;
    //遍历获取到插入位置的前一个元素
    for(i=1;i<index&&pre;i++){
        pre=pre->next;
    }
    //校验
    if(!pre||i>index){
        printf("搜索index位置元素失败\n");//已判断下标越界，不会存在这个问题
        return false;
    }
   LinkList* newNode=(LinkList*)malloc(sizeof(LinkList));
   newNode->data=e;
   newNode->next=pre->next;
   pre->next=newNode;
   head->size++;//有效个数加1
   return true;
}

5、展示链表数据

/**
 * 功能：遍历链表
 * 参数：链表地址
 */
void Show_List(LinkList *head){
    if(head==NULL){
        printf("链表未初始化\n");
        return ;
    }
    if(head->next==NULL){
        printf("[]\n");
        return;
    }
    bool flag=true;
    printf("[");
    LinkList *p=head->next;//第一个节点
    while(p){
      if(flag){
         printf("%d",p->data);
         flag=false;
      }else{
         printf(",%d",p->data);
      }
        p=p->next;
    }
    printf("]\n");
}

6、删除元素

image.png

  /**
 * 功能：删除某个下标的数据元素
 * 参数：链表地址 下标  删除的元素
 * 返回值：链表长度
 */
bool Delete_List(LinkList *head,int index, ElemType *e){
    if(head==NULL){
        printf("链表未初始化\n");
        return false;
    }
    if(index<1||index>head->size){
        printf("下标越界\n");
        return false;
    }
    //开始删除
    int i;
    LinkList* pre=head;
    //遍历获取到删除的前一个元素
    for(i=1;i<index&&pre;i++){
        pre=pre->next;
    }
   LinkList* temp=pre->next;
   *e=temp->data;
   pre->next=temp->next;
   free(temp);
   head->size--;//有效个数减1
   return true;
}

7、判断是否为空表

/**
 * 功能：判断链表是否是空表
 * 参数：链表头指针
 * 返回值：true 是  false 否
 */
bool IsEmpty(LinkList *head){
    if(head->next){
        return false;
    }
    return true;
}

8、查找元素

/**
 * 功能：查找元素，返回下标
 * 参数：链表地址 元素
 * 返回值: 下标 -1 为查找不到
 */
int Search_List(LinkList *head,ElemType e){
    if(IsEmpty(head)){
        return -1;
    }
    LinkList *p=head->next;//第一个节点
    int i=1;
    while(p!=NULL){
        if(p->data==e){
            return i;
        }
        p=p->next;
        i++;
    }
    return -1;
}

9、获取下标的元素

/**
 * 功能：获取某个下标的元素
 * 参数：链表地址 下标
 * 返回值: true ,false
 */
bool GetElem(LinkList *head,int index,ElemType *e){
    if(IsEmpty(head)){
        return false;
    }
    if(index<1||index>head->size){
         printf("数组下标越界\n");
         return false;
    }
    LinkList *p=head->next;//第一个节点
    //int j=1;
    // while(p&&j<index){
   //    p=p->next;
   //    j++;
  //}
  //if(!p||j>index)return false;
  //*e=p->data;
    for(int i=1;i<=head->size;i++,p=p->next){
        if(index==i){
            *e=p->data;
            return true;
        }
    }
    return false;
}

10、清空链表

/**
 * 功能：清空线性表
 * 参数：pList：链表地址
 */
bool Clear_List(LinkList *head){
    if(head==NULL){
        return false;
    }
    LinkList *temp,*p;
    p=head->next;//p指向第一个结点
    while(p){//没到表尾

        temp=p->next;
        free(p);
        p=temp;
    }
    head->next=NULL;
    head->size=0;
    return true;
}

11、销毁链表

/**
 * 功能：清空线性表
 * 参数：pList：
 */
bool Destory_List(LinkList *head){
//    LinkList *p;
//   if(head==NULL)
//        return false;
//    while(head)
//    {
//        p=head->next;
//        free(head);
//        head=p;
//    }
    Clear_List(head);
    free(head);
    head=NULL;
    return true;
}

main

int main()
{
    LinkList* pList=NULL;
    pList=Init_List();
    Show_List(pList);
    Insert_List(pList,1,5);
    IsEmpty(pList);
    Insert_List(pList,2,6);
    printf("搜索6的元素的位置%d\n",Search_List(pList,6));
    int index=2,val;
    GetElem(pList,index,&val);
    printf("获取第%d个的元素是%d\n",index,val);
    Clear_List(pList);
    Show_List(pList);
    if(Delete_List(pList,2,&val)){
        printf("删除的元素%d\n",val);
    }
    Show_List(pList);
    printf("搜索5的元素的位置%d\n",Search_List(pList,5));
    Length_List(pList);
    return 0;
}