title: 数据结构
date: 2019-03-11 20:43:34
categories:
- 数据结构
tags:
- 数据结构
数据结构
数据：所有能够输入到计算机中，并且能被计算机处理的符号的集合。
ADT：抽象数据类型
线性表
- 特征：所有元素属于同一数据类型
- 有限：数据元素个数是有限的
- 序列：数据元素由逻辑符号唯一确定，一个线性表中允许有相同值元素
- 线性表基本运算：
- 初始化线性表InitList(&L):构造空的线性表L
- 销毁线性表DestoryList(&L): 释放线性表L占用的空间
- 判断线性表是否为空值ListEmpty(L): L为真返回空，否，返回假
- 求线性表长度ListLength：返回L中元素n
- ...
- 定义：
typedef struct{
ElemType data[MAXSIZE];
int length;
}SqList;
- 逻辑位序和物理位序正好相差1
- 输出型参数 都在前面加上&
- 初始化
void InitList(SqList *L){
L=(*SqList)malloc(sizeof(SqList));
L->length=0;
}
- 销毁
vold DestoryList(SqList *L){}
free(L);
}
- 是否为空
bool ListEmpty(SqList *L){
return(L->length==0);
}
- 长度
int ListLength(Sqlist *L){
return L->length;
}
- 输出线性表
void DispList(SqList *L){
int i=0;
if(L->length==0) return;
for(i;i<L->length;i++){
printf("%c",L->data[i]);
}
}
顺序表
1、实现删除顺序表中所有为x的元素
- 方法1：利用旧的顺序表里新建顺序表
void Func(SqList *&A,ElemType x){
int k=0,i=0;
for(i;i<A->length;i++){
if(A->data[i]!=x){
A->data[k]=A->data[i];
k++;
}
}
A->length=k;
}
- 方法2：将不为x的元素迁移K个位置，最后修改A的长度
void Func(SqList *&A,ElemType x){
int k=0,i=0;
while(i<A->length){
if(A->length==x)
k++;
else
A->data[i-k]=A->data[i];
i++;
}
A->length=A->length-k;
}
2、实现长度为10的顺序表，以第一个元素为分界线，将小于他的元素移到该基准前面，大于的放在后面。
- 方法1：拿出基准，i从左往右扫描，j从右往左，找到合适的元素交换顺序，直到i=j，将基准放入i=j位置
void move(SqList *&L){
int i=0,j=L->length;
ElemType tmp;
ElemType pivot=L->data[0]);
while(i<j){
while(i<j&&L->data[j]>pivot)
j--;
while(i<j&&L->data[i]<=pivot)
i++;
if(i<j){
tmp=L->data[i];
L->data[i]=L->data[j];
L->data[j]=tmp;
}
}
tmp=L->data[0];
L->data[0]=L->data[j];
L->data[j]=tmp;
}
线性表和链表的区别
- 顺序表具有随机存储的特性，存储密度大，但是插入和删除需要移动大量的数据，初始化分配空间难以确定
- 链表采用动态分配内存的方法，具有良好的适应性，插入删除只需要修改相关的指针域，不需要移动元素，但是存储密度小，需要有额外的
存储空间，指针域，不具有随机存储特性
双链表
优点：从任一节点出发可以 找到其前驱节点和后继节点，从任一点出发可以访问其他节点。
循环单链表
- 链表没有空指针域
栈
- 定义：栈是一种只能在同一段插入或删除的线性表，栈只能选取同一个短点进行插入或删除操作(栈顶)，另一端为栈底
- 后进先出
马克 马克 马克
