[数据结构]基本概念、单链表操作

1.数据在内存中的存储方式

数据在计算机程序中都是存储在内存空间中的.

1. 连续内存空间，比如申请一个数组，申请内存的大小事先知道。【数组】
2. 非连续内存空间，特点是申请次数无限制，每次固定大小。【链表】

2.时间复杂度和空间复杂度

• 时间复杂度：同一问题可用不同的算法解决，一个算法的质量优劣将影响算法乃至程序的效率。算法的时间复杂度是一个函数，定量描述算法的运行时间，通常用O表示.
• 空间复杂度：一个算法在运行过程中占用存储空间大小的度量，包括算法本身所占的存储空间、数据输出数据所占用的存储空间的大学、运行过程中临时占用的存储空间的大小这三个方面。

3.衡量一个算法的优劣的标准

• 正确性.
  所写算法能满足具体问题的要求，对于任何合法的输入可以得出正确的结果。
• 可读性.
  晦涩难懂的算法不易于交流、推广、修改、拓展、维护，在写算法的时候，要尽量写的简明易懂。
• 健壮性.
  输入数据非法时，算法也会做出相应的判断，不会因为输入的错误造成程序瘫痪。
• 时间复杂度和空间复杂度.
  理想的算法应该是时间复杂度和空间复杂度都最佳。对于一个算法，时间复杂度和空间复杂度往往相互影响。

4.链表基本操作

4.1链表结构体定义

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

typedef struct linklist
{
     int data;
     struct linklist *next;  //单链表   

}linknode,*linklistp;

4.2.头部插入新节点

//返回头部
linklistp insert_head(linklistp head,linklistp newnode){
    newnode->next=head;
    head=newnode;
    return head;
}

4.3. 尾部插入新节点

linklistp insert_tail(linklistp head,linklistp newnode){
   if(head==NULL){
     head=newnode;
   }else{

       linklistp temp=head;
       while(temp->next!=NULL){
         temp=temp->next;
       }
       newnode->next=temp->next;
       temp->next=newnode;
   }
   return head;
}

4.4 删除子节点

//删除节点
  linklistp list_delete(linklistp head,int a){
       linklistp temp=head;
       //1.temp为空，返回NULL
       if(temp==NULL){ 
        printf("链表为空\n");
        return NULL;
      }  
       //2.正好是首节点
       if(temp->data==a){
           head=head->next;
           free(temp);
           return head;
       }
       //3.不在首节点
       linklistp prev=head;
       temp=head->next;

       while(temp!=NULL&&temp->data!=a){
           prev=temp;
           temp=temp->next;
       }

       //3.1 没找到

       if(temp==NULL){ 
        printf("不存在\n");
        return NULL; 
      }
       prev->next=temp->next;
       return head;

  }

4.5查找节点

//查找第i个元素
  int getElem(linklistp head,int i,int a){
      if (head->next==NULL)
      {
          printf("link list is NULL");
          return 0;
      }

      linklistp temp=head;
      int j=0;
      while(temp->next&&j<i){
         temp=temp->next;
         ++j;
      }

      if(!temp||j>i){
        printf(" 不存在第i个元素\n");
      }

      a=temp->data;
      return a;
  }

4.6 判断链表是否为空

  //判断链表是否为空

  _Bool isEmpty(linklistp head){
     if (head->next==NULL)
     {
         printf("链表为空\n");
         return 1;
     }
     return 0;

  }

4.7遍历链表

 void output(linklistp head){
     linklistp temp=head;
     while(temp){
        printf("%d\t", temp->data);
        temp=temp->next;
     }
     printf("\n");
 }

4.8 测试代码

int main(){
    linklistp head=NULL;
    for (int i = 0; i < 10; ++i)
    {
        /* code */
        linklistp  newnode=(linklistp)malloc(sizeof(linknode));
        newnode->data=i*10+2;
        newnode->next=NULL;
        head=insert_head(head,newnode);

    }

    output(head);

    printf("*********删除节点*******\n");
    int data=0;
    printf("请输入要删除的数据：\n");
    scanf("%d",&data);
  linklistp temp=list_delete(head,data);
  if (temp==NULL)
  {
    printf("def failture or not has this node");
  }else{
    head=temp;
    output(head);
  }

  printf("**************************\n");
  printf("enter the num you want to find:\n");

  printf("%d\n",getElem(head,2,data));  
    return 0;

}