数据结构之线性表

前段时间被大佬虐菜,内心是拔凉拔凉的,决定再次拿出封存2年的程序员教程第五版,恶补下数据结构和算法;首先从较简单的线性表入手,治疗下那颗脆弱的心.

数据结构的基本概念和术语

【数据元素】
【数据项】是元素的最小单位
【数据对象】具有相同性质元素的集合，数据对象包含数据元素 数据元素包含数据项
【数据结构】= D + S 顾名思义 就是数据对象的关系

1 线性表的基本定义

线性表是n个元素构成的有限序列,可以表示为{a1,a2,...an}.
线性表的抽象数据类型(数据结构+ 操作)为:

image.png

2 线性表的存储结构(重点)

线性表存储结构分为顺序存储和链式存储

2.1 顺序存储

线性表的顺序存储是指同一地址连续存储单元依次存储线性表,从而使得两个相邻元素在物理位置上相邻.通过物理结构表示元素的逻辑结构.
线性表中某个元素的存储位置为:
LOC(ai) = LOC(a1) + (i-1)d 其中 LOC(a1)是第一个元素的存储位置,d表示某个元素所占存储单元的个数.
顺序存储优点是可以随机取出元素,而且速度快,缺点是删除和插入元素需要移动元素.
线性表使用顺序存储插入一个新元素,需要平均移动n/2个元素;删除一个元素,需要平均移动(n - 1)/2个元素.

2.2 链式存储

使用链式存储,数据元素是用结点来存储,链表中结点的基本结构为:

结点的结构
数据域:用来存储数据结构的值.
指针域:用来存储当前元素的直接前驱或直接后续的位置信息,里面信息是个指针或者叫做链.
如果节点中只有一个指针域,则称为线性链表或者叫做单链表(这里只介绍单链表存储线性表,其他链表存储不再介绍)
线性表的单链表存储
在链式存储中,一般只要得到指向第一个节点的指针(图中的Head)就可以顺序的访问到表中的任意一个元素(一般头结点的数据域用来存储链表的长度信息或者不用);所以在链式存储下进行插入和删除,其实质就是对指针进行修改.

如果线性表的数据是字符型,那么单链表的结点类型为:

#include <stdio.h>
#include <stdlib.h>
  typedef  struct  node{
     // 数据域
   char  data;
   // 指针域
   struct node *next;
}NODE, *LinkList;

1. 初始化链表

LinkList linkListInit(){
 
NODE *link;
// 申请空间
link =(NODE *)malloc(sizeof(NODE));

if(!link)
  printf("空间申请失败");
// 长度为0的单链表
link->next = NULL;

return link;

}

2.创建一个单链表
头插法:

尾插法:

int main(int argv, char *argc[]){
 
    char array[] = {'d','c','b','a'};
   // 初始化一个头结点
    LinkList link = linkListInit(); //{a,b,c,d}
    link->next = NULL;
    LinkList r;
// 指向 表尾结点
     r  = L;
  
   //通过结点生成链表
   int count = sizeof(array)/sizeof(char);
   for(int i = 0; i < count;i++){
    // 申请结点
     NODE *p;
     p = (NODE *)malloc(sizeof(NODE));
     p->data = array[i];
     // p的指针域指向头指针的后继结点,开始的时候后续节点的指针指向NULL
     p->next = link->next;
     // 把头结点的指针改成指向p的结点
     //尾插法
     link->next = p;

   /** 头插法
     p-next  = NULL;
     r->next = p; 
     r =  r->next// r指向当前的表尾 

*/

   }
  //link ->next = NULL;
   printInfLink(link); 

}

3.单链表的插入操作

// 查询位置k的结点
LinkList  FindList(LinkList p,int k){
  LinkList temp =  p;
  int  i = 0;
  while(temp ->next && i < k){
    temp = temp ->next;
    i++;
  }
  if(i == k && p)
  return temp;
  
  return NULL;
}

 // 单链表插入一个元素
/**
  L 头指针
  将elem插入到k个元素之前
*/

void InsetList(LinkList L,int k,char elem)
{
// 执行第k-1元素的结点
  LinkList p;
// 创建一个新的节点
  LinkList newList;
  if(k == 1){
      p = L;
  }else{
     // 查询k前面的一个节点
     p = FindList(L,k-1);
  }
  
  if(!p) return ;

 newList = (NODE *)malloc(sizeof(NODE));

if(!newList) return ;

 newList ->data = elem;
 newList ->next = p -> next;
 p->next = newList;

}

4.单链表的删除操作

image.png

// 删除第k个元素

void Delect_List(LinkList L ,int k){

// p是删除元素的前驱结点
// s是要删除的结点
  LinkList p,s;
  
  if(k == 1) p = L;
  else p = FindList(L,k-1);
   
  if(!p || !p ->next) return;
 
  //删除节点
  p->next = p->next->next;

 // 或者 s = p->next;p->next = s->next

  free(s);

}