3.线性表--大话数据结构

定义

若将线性表记为(a1,....ai-1,ai,ai+1,....,an)，则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai 的直接前驱元素，ai+1是ai的直接后继元素，当i = 1,2, ... n-1时，ai有且仅有一个直接后继，当i = 2,3,...,n时，ai有且仅有一个直接前驱， （通俗来说，就是用一根线将数据串联起来）

线性表的顺序存储结构：

指的是用一段地址连续的存储单元依次存储线性表的数据元素（也就是数组）

优点：1.无须为表示表中元素之间的逻辑关系而增加额外的存储空间 2.可以快速存取表中任一位置的元素
缺点：1.插入和删除操作需要移动大量元素 2.当线性表长度变化较大时，难以确定存储空间的容量
3.造成存储空间的浪费

线性表的链式存储结构

就是链表中包含数据域、指针域，当个数据叫做结点，只包含一个指针域的叫做单链表

1.头指针：

链表第一个结点的存储位置叫做头指针，就相当于 struct Node * n = createNode();n 就为头指针

2.头结点：

在链表的第一个结点前附设一个结点，称为头结点，就是在第一个存储数据结点前面的那个结点，这个结点数据域不存数据

3.异同：

头指针：
1.头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
2.头指针具有标识意义，所以用头指针冠以链表的名字
3.无论链表是否为空，头指针均不为空，头指针是链表的必要元素

头结点：
1.头结点是为了操作的统一和方便而设立的，放在第一个结点之前，其数据域一般无意义
2.有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了，
3.头结点不一定时链表的必须要素

4.当链表的整表创建

4.1头插法

void CreateListHead(LinkList *L,int n){
    LinkList p;
     int i;
     srand(time(0)); //随机产生数
    (*L) = (LinkList) malloc(sizeof(Node));
    (*L)->next = NULL;
  
    for(i = 0;i<n;i++){
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand()%100 +1;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

4.2尾插法

void CreateListHead(LinkList *L,int n){
    LinkList p,r;
     int i;
     srand(time(0)); //随机产生数
    (*L) = (LinkList) malloc(sizeof(Node));
    (*L)->next = NULL;
  
    for(i = 0;i<n;i++){
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand()%100 +1;
        r->next = p;
         r = p;
    }
  r->next = NULL;
}

4.2整表删除

Status ClearList(LinkList *L){

    LInkList p, q;
    p = (*L)->next;
  while(p){
      q = p->pnext;
      free(p);
      p = q;
  }
(*L)->next = NULL;
return OK;
}

5.静态链表

定义：用数组描述的链表，这种方法也叫游标实现法
我们对数组的第一个和最后一个元素作为特殊元素处理，不存数据，我们通常把未被使用的数组元素称为备用链表，而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标，而数组的最后一个元素的cur则存放第一个有数值的元素下标，相当于单链表的头结点作用。

d9e7cb8f702284fdda1d4e654142323.jpg

# define MAXSIZE 1000
typedef stuct{
  ElemType data;
  int cur;
}Component,StaticLinkList[MAXSIZE];
//将这个链表初始化
Status InitList(StaticLinkList space){
    int i;
    for(i = 0;i< MAXSIZE -1;i++){
        space[i].cur = i+1;
      }
space[MAXSIZE].cur = 0;
return OK;
}

5.1静态链表的插入操作

8e6fe780d39cd58116aaa3997d46ce3.jpg

// 这个函数是得到下一个存储空间的下标
int Malloc_SLL(StaticLinkList space){
  int i = space[0].cur;
  if(space[0].cur)
        space[0].cur = space[i].cur;

return i;

}

Status ListInsert(StaticLinkList L,int i,ElemType e){
  int j,k,l;
  k = MAX_SIZE -1; //得到的是第一个有值元素的下标
  if(i < 1 || i > ListLength(L) + 1)
        return ERROR;
  j = Malloc_SSL(L); // 得到插入的下标，并将0下标中备用链表更新；
  if(j){ // 在C 语言中，除了0，都是真
    L[j].data = e;  // 赋值
     //  找到插入下标之前的元素下标 
    for(l = 1;l <= i -1;l++){
      k = L[k].cur;
      }
      //将插入前的那个元素存储的下标赋值给插入的元素，即插入元素执行下一个元素
      L[j].cur = L[k].cur;
      // 前一个元素指向插入元素
      L[k].cur = j;
      return OK;

  }
}

5.2静态链表的删除操作

// 删除在L中第i 个数据元素e
 Status ListDelete(StaticLinkList L,int i){
    int j,k;
    if(i < 1 || i > ListLength(L))
        return ERROR;
     k = MAX_SIZE -1;
      for(j = 1;j<= i -1;j++)
            k = L[k].cur;
      j = L[k].cur;
      L[k].cur = L[j].cur;
      Free_SSL(L,j);
      return OK;
  }

void Free_SSL(StaticLinkList space,int k){
  space[k].cur = space[0].cur;
  space[0].cur = k;
 }

//静态链表长度
int ListLength(StaticLinkList L){
  int j = 0;
  int i = L[MAXSIZE -1].cur;
  while(i){
    i = L[i].cur;
    j++;
  }

return j;
}

6.循环链表

定义：将单链表中终端结点的指针端由空指针改为指向头结点，就是整个单链表形成一个环，这种头尾相接的单链表称为单循环链表。

3a9505df3e84263ef3568f732a6a1f7.jpg

将两个循环链表合为一个的代码

p = rearA->next; //保存A的头结点
rearA->next= rearB->next->next; // 使A指向B的第一个有值元素，
q = rearB->next;//将头结点赋值给q
rearB->next = p;//将B指向A的头结点
free(q);//释放B的头结点

7.双向链表

定义：是在前链表的每个结点中，在设置一个指向其前驱结点的指针域

  ElemType data;
  struct DulNode *prior;
  struct DulNode *next;
}DulNode,* DuLinkList;

插入数据：先搞定插入结点的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继

cfd35ed398d3a35a044f405e1fe2e9d.jpg

删除数据：记得free(p);

fe66e15eb4e4d1666a2e761c41a845c.jpg