数据结构与算法
- 1. 绪论
  - 1.1数据结构
  - 1.2 算法
- 2.线性表

数据结构与算法

1. 绪论

1.1数据结构

数据结构三要素：逻辑、物理、数据的运算<br />
    逻辑结构：集合、线性、树型、网状（图形）<br />
    存储结构：顺序、链式、索引、散列<br />
    数据结构的运算：<br />
        - a.原子类型：不可再分的类型。(bool,int)<br />
        - b.结构类型：可分解的类型(struct)<br />
        - c.抽象数据类型：定义了一个数据结构

1.2 算法

算法的特性：
a.有穷性(算法有穷，程序无穷) -b.确定性 -c.可行性 -d.输入与输出
好算法的特点：
a.正确性 -b.可读性 -c.健壮性 -d.高效率与低存储量
算法的效率：时间复杂度、空间复杂度
常对幂指阶：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2) <O(n^3) <O(2^n) <O(n!)<O(n^n)

2.线性表

定义：具有相同数据类型的n个数据元素的有限序列.n为表长，若n=0,则线性表为空表；i为表的位序(从1开始)

a1为线性表的表头；an为线性表的表尾，除表头元素，表中每个元素有且仅有一个直接前驱，除表尾元素，表中每个元素有且仅有一个直接后继
线性表的特点：

元素个数有限
逻辑上的顺序性，元素有先后顺序
元素为数据元素，每个元素都为单个元素
元素数据类型相同，即每个元素占用的存储空间相同
基本操作：
1. 初始化、销毁
2. 插入、删除
3. 按值查找、按位查找
4. 求表长、输出、判空

2.1顺序表

优点：可随机存取，存储密度高
缺点：要求大片连续空间，改变容量不方便
用顺序存储实现的线性表

//静态表
#include <iostream>
using namespace std;
#define MaxSize 10
typedef struct{
    int data[MaxSize];
    int length;
}SeqList;//静态列表
void InitList(SeqList &L){
    for (int i=0;i<=MaxSize;i++)
        L.data[i]=0;
    L.length=0;
}//静态列表初始化
void ListInsert(SeqList &L,int i,int e){
    for(int j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
}//插入操作
void ListDelete(SeqList &L,int i int &e){
    e=L.data[i-1];
    for (int j=i;j<=L.length;j++)
        L.data[j-1]=L.data[j];
    L.length--;
}//删除操作
void GetElem(SeqList L,int i){
    return L.data[i-1];
}//按位查找
void GetValue(SeqList L,int i,int e){
    for(int i =0;i<L.length;i++)
        if (L.data[i]==e)
            return i+1;
}//按值查找
int main()
{
    SeqList L;
    InitList(L);
    int e=-1;
    ListInsert(L,1,3);
    ListInsert(L,2,4);
    ListInsert(L,3,5);
    ListInsert(L,8,7);
    ListInsert(L,9,6);
    for (int i=0;i<MaxSize;i++)
        printf("%d,%d\n",L.data[i],L.length);
   return 0;
}
//3,5
//4,5
//5,5
//0,5
//0,5
//0,5
//0,5
//7,5
//6,5
//0,5

#include <iostream>
using namespace std;
#include <stdlib.h>
#define InitSize 10
typedef struct{
    int *data;
    int MaxSize;
    int length;
}SeqList;//定义线性表
void InitList(SeqList &L){
    L.data=(int *)malloc(InitSize*sizeof(int));//L.data=new int[InitSize];
    L.length=0;
    L.MaxSize=InitSize;
}//初始化动态表
//其余操作与静态表相似
int main(){
    SeqList L;
    InitList(L);
    return 0;
}

2.2链表(链式存储)

2.2.1单链表

定义：用链式存储的方式实现了线性的结构。结点(数据结构+指针)
优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要消耗一定空间存放指针

//不带头节点
#include <iostream>
using namespace std;
typedef struct LNode{
    int data;//每个节点存放数据元素
    struct Lnode *next;//指针指向下一节点
}LNode,*LinkList;
bool InitList(LinkList &L){
    L=NULL;//空表
    return true;
}
bool Empty(LinkList L){
    return (L==NULL);
}
void test(){
    LinkList L;//声明指向单链表的指针
    InitList(L);//初始化空表
}

//带头结点
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));//分配头结点
    if (L==NuLL)//内存不足
        return false;
    L->next =NULL;//头结点后暂时没有结点
    return true;
}
bool Empty(LinkList L){
    if(L->next==NULL)
        return true;
    else
        return false;
}

带头结点——按位插入

bool InsertNextNOde(LNode *p,ElemType e){
    if (p==NULL)
        return false;
    LNode *S=(LNode *)malloc(sizeof(LNode));
    if(S==NULL)
        return false; 
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}//后插操作
bool ListInsert(ListNode &L,int i ,ElempType e){
    if (i<1)//i表示位序，所以不能小于1
        return false;
    LNode *p;//指针扫描当前节点
    int j=0;//当前p指向的结点
    p=L;//L指向头结点，头结点是第0个结点（不存放数据）
    while (p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    return InsertNextNode(p,e);//结点p后插入数据
}

不带头结点

bool ListInsert(ListNode &L,int i ,ElempType e){
    if (i<1)//i表示位序，所以不能小于1
        return false;
    if (i=1){
        LNode=(LNode *)malloc(sizeof(LinkLIst));
        s->data=e;
        s->next=L;
        L=s;
        return true;
        }
    LNode *p;//指针扫描当前节点
    int j=1;//当前p指向的结点
    p=L;//L指向头结点，头结点是第0个结点（不存放数据）
    while (p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    return InsertNextNode(p,e);
}

//前插操作
bool InsertPriorNode(LNode *p,ElemType){
    if (p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if (s==NULL)
        return false;
    s->next=p->next;//新节点指向原结点后的数据
    p->next=s;//原结点指向新节点
    s->data=p->data;//原结点数据赋值给新节点
    p->data=e;//原结点保存插入的数据
    return true;
}

//删除操作-按位删除（带头结点）
bool ListDelete(LinkList &L,int i,ElemType &e){
    if (i<1)
        return false;
    LNode *p;
    int j=0;
    p=L;
    while(p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if (p==NULL)
        return false;
    LNode *q=p->next;
    e=q->data;//返回删除的值
    p->next=q->next;
    free(q);
    return true;
}

删除制定节点P，但是删除表尾元素会导致空指针

bool InsertPriorNode(LNode *p,ElemType){
    if (p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if (s==NULL)
        return false;
    s->next=p->next;//新节点指向原结点后的数据
    if(p->next!=NULL)
        p->next->prio=s;
    s->prio=p;
    p->next=s;
    return true;
}

//按位查找
LNode * GetElem(LinkList L,int i){
    if (i<0)
        return NULL;
    LNode *p;
    int j=0;
    p=L;
    while (p==NULL && j<i){
        p=p->next;
        j++;
    }
    return p;
}

2.2.2双链表

相比单链表，多了一个指向前驱元素的指针，在修改时也要注意修改前驱元素指针

//简单举例
bool DeleteNode(LNode *p){
    if (p==NULL)
        return false;
    LNode *q=p->next;
}
//删除操作简单思路
//删除p的后继结点q
if (p==NULL) return false;
if (q==NULL) return false;
p->next=q->next;//q结点指向的指针让p结点指定
if(q->next !=NULL)
    q->next->prio=p;//q结点后的前指针，指向p，使得q没有被任何结点指向
free(q);//释放q空间

2.2.3循环单链表/循环双链表

在其代码逻辑上与单/双链表毫无区别，主要不同表现在二者表尾/表头或这前驱插入时，在删除时也要将表尾指向表头的指针进行修改

2.2.4静态链表

#define MaxSize 10
typedef struct {
    int data;
    int next;
}SLinkList[MaxSize];

思路：初始化时，头结点的指针指向-1，其余的next指向-2;
插入/删除,修改next指针

2.3.顺序表与链表的比较

顺序表：随机存取，存储密度大，大片连续分配空间不方便，改变容量不便
销毁：静态分配：系统自动回收
动态分配：手动(free)
链式表：改变容量方便，不可随机存取，存储密度低

开放式答题模版：

1.顺序表与链表的逻辑结构都是线性结构，都属于线性表

2.但是二者存储结构不同，顺序表采用顺序存储（优点、缺点），链表采用链式存储（优点、缺点）

3.由于采用不同的存储结构，基础操作实现的效率也有所不同

初始化：….
插入/删除元素：…..
查找元素：…….

1-2绪论与线性表