数据结构三要素
-
逻辑结构
集合，线性结构，树形结构，图状，网状
-
存储结构
顺序存储，链式存储，索引存储（索引表），散列存储（哈希存储）
-
数据运算
相同数据类型的有限序列
线性表是一种逻辑结构，顺序表和链表是指存储结构
- 顺序表可以实现随机存取
- 链表适合频繁进行插入，删除操作
顺序表的定义
逻辑顺序与物理顺序相同
#include <stdio.h>
#define MaxSize 10//定义最大长度
typedef struct{
int data[MaxSize];//用静态的“数组”存放数据元素
int length;//当前长度
}SqList;//类型定义，别名
//初始化一个顺序表
void InitSqList(SqList &L){
for(int i=0;i<L.length;i++){
L.data[i]=0;//分配的空间会有一些脏数据，所以进行初始化
}
L.length=0;
}
int main(){
SqList L;
InitList(L);
return 0;
}
动态分配
#include<stdlib.h>
#define InitSize 10//默认最大长度
typedef struct{
int *data;//知识动态分配数组的指针
int MaxSize;//顺序表的最大容量
int length;//当前长度
}SqList;
//初始化
void InitList(SqList &L){
L.data=(int *)malloc(InitSize*sizeof(int));//表L的data指针指向分配的块内存的首地址
L.lenght=0;
L.MaxSize=InitSize;
}
//增加动态数组的长度
void IncreaseSize(SqList &L,int len){
int *p=L.data;//p指向原来的块内存首地址
L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
for(int i=0;i<L.length;i++){
L.data[i]=p[i];//复制到新表
}
L.MaxSize=L.MaxSize+len;//最大长度加len
free(p);//释放原来的内存空间
}
int main(){
SqList L;
InitList(L);
IncreaseSize(L,5);
return 0;
}
插入
//静态顺序表
#define MaxSize 10
typedef struct{
int data[MaxSize];
int length;
}SqList;
//在L的位序i处插入元素e
bool ListInsert(SqList &L,int i,int e){
//位序i；i从1开始
if(i<1||i>L.length+1)//i不合法
return false;
if(L.length>=MaxSize)//存储空间已满
return false;
for(int j=L.length;j>=i;j--){//第i个之后的元素后移
L.data[j]=L.data[j-1];
}
L.data[i-1]=e;
L.length++;
return true;
}
删除
//删除顺序表L中第i个元素，将其赋值给e返回
bool ListDelete(SqList &L,int i;int &e){
if(i<1||i>L.length)
return false;
e=L.data[i-1];
for(int j=i;j<L.length;j++){//将第i个位置后的元素前移
L.data[j-1]=L.data[j];
}
L.length--;
return true;
}
按位查找
typedef struct{
int *data;//知识动态分配数组的指针
int MaxSize;//顺序表的最大容量
int length;//当前长度
}SqList;
ElemType GetElem(SqList L,int i){
return L.data[i-1];//指针访问
}
按值查找
//查找值为e的元素，返回其位序
int LocateElem(SqList L,int e){
for(int i=0;i<L.length;i++){
if(L.data[i]==e)
return i+1//返回位序，位序是从1开始的,静态顺序表从0开始
}
return 0;
}
常用操作
bool Merge(SqList A,SqList B,SqList &C){
if(A.length+B.length>C.MaxSize){
return false;
}
int i=0,j=0,k=0;
while(i<A.length && j<B.length){//两两比较，小者存入结果表
if(A.data[i] <= B.data[j]){
C.data[k++]=A.data[i++];
}
else{
C.data[k++]=B.data[j++];
}
}
while(i<A.length)//还剩一个没有比较完的顺序表
C.data[k++]=A.data[i++];
while(j<B.length)
C.data[k++]=B.data[j++];
C.length=k;
return true;
}
妙的算法
对长度为n的顺序表L，编写一个时间复杂度为
O(n)，空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素
//用k记录顺序表L中不等于x的元素个数（即需要保存到元素个数），边扫描L边统计k,并将不等于x的元素向前移动k个元素，最后修改表长
void del_x(SqList &L,ElemType x){
int k=0;//记录不等于x的元素个数
for(int i=0;i<L.length;i++){
if(L.data[i]!=x){
L.data[k]=L.data[i];
k++;不等于k的元素增1
}
L.length=k;//顺序表L的长度等于k
}
}
从顺序表中删除其值在给定值
s与t之间（包含s和t,要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示错误信息并退出
//从前向后扫描顺序表L,用k记录元素值在s到t之间元素的个数（初始时k=0）,对于当前扫描的元素，若其值不在s到t之间，则前移k个位置；否则执行k++;(每个不在s到t之间的元素仅移动一次，效率高)
bool Del_s_t(SqList &L,ElemType s,ElemType t){
int i,k=0;
if(L.length==0||s>t){
return false;
}
for(int i=0;i<L.length;i++){
if(L.data[i]>=s && L.data[i]<=t){//s至t之间的数量
k++;
}
else{
L.data[i-k]=L.data[i];//当前元素前移k个位置
}
}
L.length-=k;//长度减少
return true;
}
