C语言数据结构 （待完善）

C语言数据结构与算法

算法具有：输入 输出 有穷性 确定性 可行性

1.线性表

由零个或者多个元素组成的有序序列 n为表长

L=（a1，a2，a3.。。。an）

若元素存在多个 这第一个元素无前驱 最后一个无后继

元素是有限的（a1 ,a2,a3,....an）

• 抽象数据类型

  数据是指一个组性质相同的类型 int double long 。。。。。

1.1 线性表的操作

• 初始化操作

  InitList(*L):初始化操作 建立一个空的线性表L

  LIstEmpty（L）:判断线性表是否为空 若线性表为空返回true 否则返回flase

  ClearList（*L）:将线性表清空

  GetElem（L,i,*e）：将线性表中的第i个位置的元素返回给e

  LoccateElem（L，e）：查找线性表中的与e相等的元素 返回0 表示失败

  LIstInsert（*L,i,e）:在线性表L 中的第i个位置插入新的元素e

  ListDelete（L，i，e）删除线性表L中的第i个位置元素，并用e返回

  LIstLength（L）:返回线性表L元素的个数

  注：& 表示引用数据类型（对修改的结果要带回来的话就用&）

  //没返回修改结果
  #include <stdio.h>
  void text(int i);
  int main() {
      int x=1;
      printf("修改前x=%d",x);
      text(x);
      printf("经过text修改后x=%d:",x);
  }
  void text(int x){
      x=10086;
      printf("text函数里面的x=%d",x);
  }
  
  //修改成引用类型
  #include <stdio.h>
  void text(int &  i);
  int main() {
      int x=1;
      printf("修改前x=%d",x);
      text(x);
      printf("经过text修改后x=%d:",x);
  }
  void text(int & x){
      x=10086;
      printf("text函数里面的x=%d",x);
  }
  
  //使用引用数据类型后 成功的修改了x 的值           

1.2 顺序表的定义

1.2.1静态分配

使用数组的方式来

静态分配实现的顺序表的长度是固定的 所以存放的元素的个数是有固定的是不可调的

#include <stdio.h>
#define MaxSize 10 //定义最大长度
typedef struct{
    int data[MaxSize];//用静态数组存放数据元素 
    int length; //顺序表当前的长度 
} SqList;//顺序表的类型定义

//初始化一个顺序表 
void initList(SqList &L){
    for(int i=0;i<MaxSize;i++){
        L.data[i]=0; //将所有的数据元素设置为默认值 
    }
    L.length=0;//顺序表的初始长度为0 
} 
int main(){
    SqList L;//声明一个顺序表 
    initList(L);//初始化顺序表 
    return 0;
}           

1.2.2动态分配

https://www.bilibili.com/video/BV1b7411N798?p=8&spm_id_from=pageDriver

1.3 顺序表的插入和删除

1.4 顺序表的按位查找

ElemType GetElem(SqLIst L,int i){
    return L.data[i-1];
}           

1.5 顺序表的按值查找

int LocatElem(SeqList L,ElemType e){
    for(int i-0;i<L.Length;i++){
        if(e==L.data[i]){
            return i+1;
        }
    }
    return 0;
}           

2. 单链表

链表就是分为两个空间 一个空间存放的是 数据·

另外一个空间存放的是指针 指向的是下一个数据的地址

• 使用代码定义一个单链表

  struct LNode{//定义单链表节点类型
      ElenType data;//每个节点存放一个数据元素
      stuct Lnode *next;//指针指向下一个节点
  };
  struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode));
  //添加一个新的节点：在内存中申请一个节点所需要的空间，使用指针p指向这个节点           

  使用代码定义一个链表

  typedef是起别名的意思

  typedef struct LNode{
   .......;
  }LNode *LinkList;           

  上面的代码等同于

  typedef struct  Lnode LNode;//把struct LNode重命名为LNode
  typedef struct *LinkList;//并且表明这是一个指向struct LNode 的指针           

  上述代码 LNode *和LinkList L虽然是一样的但是所表达的意思是完全不同的

  LNode * 着重强调返回的是一个节点 而LinkLIst强调的是需要返回一个链表

2.1声明一个不带头节点的单链表

2.2声明一个带头节点的链表

2.3单链表插入（带头结点）

2.4 单链表的查找

2.5 单链表按值查找

2.5 单链表长度

2.6 单链表的建立

给你很多元素 -如何把他们存到一个单链表中

2.6.1 尾插法

尾插法是往末尾的一个元素插入元素

头插法是向头元素的后面插入元素 所以头插法的元素是逆置的

3. 双链表

双链表就是在单链表的基础上再增加一个指针域指向前一个元素

3.1 双链表的初始化

typedef struct DNode{s
    ElemType data;
    sttuct DNode *prior,*next;//一个前指针指向前一个元素 一个next指针指向后一个元素
}DNode,*DLinkList;
           

3.2 双链表的插入

3.3 双链表的元素删除

3.4 双链表的遍历

小结：

4.循环单链表和循环双链表

循环链表的最后一个指针指向的是头元素

5 静态链表（了解即可）

第二章

6 栈和队列

栈的概念：类似于盘子堆 只能从顶端拿盘子 从中间或者其他地方拿东西很可能会出现问题

6.1 栈的重要的术语

空栈 就类似于空盒子 里面没有放任何的东西

栈顶： 只允许插入的端

栈底：不允许插入和删除的端

栈是后进先出的

6.2 栈的基本操作

6.3 顺序栈的实现