参考网课数据结构-青岛大学-王卓-第二周
参考书籍《数据结构C语言版第二版》 中国工信出版集团 人民邮电出版社出版 严蔚敏 编著
2线性表
线性表定义
定义：有n个数据元素（结点）组成的有限序列，元素间要具有相同特性。
线性表的顺序存储
知道头元素地址可以实现计算任意一个元素的地址。若一个元素占用个单位，则
线性表的类型定义例子
#define MAXSIZE 10000 /／图书表可能达到的最大长度
typedef struct{
char no[20];
char name[50];
float price;
}Book;
typedef struct{
Book *elem;
int length ;
}SqList;
补充-C数组动态内存分配
typedef struct{
ElemType *data
int length
}SqList
Sqlist L;
L.data=(ElemType*)malloc(sizeof(ElemType)*MaxSize)
free(p) //释放p指针指向的储存空间，即彻底删除一个变量若把*data改为data[]就是静态分配的写法。
Warning
需要加载头文件
<stdlib.h>
Note
malloc(m) //函数效果开辟m个单位的内存并返回头元素地址
补充-C++动态内存分配
int *p1 = new int；
或
int *p1 = new int(10);
delete *p1 \\释放指针p补充-C语言函数的变量传递
值传递：函数内改变传入值，不影响外部的变量。形参改变不影响实参。
两种指针传递的对比
情形一：
#include<iostream.h>
void swap(float *m; float *n){
float t;
t=*m;
*m=*n;
*n=t;
}
void main(){
float a,b,*p1,*p2;
cin>>a>>b;
p1=&a;p2=&b;
swap(p1,p2);
cout<<a<<endl<<b<<endl;
}这种情形会导致外部的实参发生交换。
情形二：
#include<iostream.h>
void swap(float *m; float *n){
float *t;
t=m;
m=n;
n=t;
}
void main(){
float a,b,*p1,*p2;
cin>>a>>b;
p1=&a;p2=&b;
swap(p1,p2);
cout<<a<<endl<<b<<endl;
}
这种情形不会导致外部的实参发生交换。
Note
指针变量的地址是自己的地址，但是，值是
指向的变量的地址。
Warning
两个情形的主要区别在于交换函数交换的东西不同，情形1交换的是指针指向的内容；情形2交换的是指针的指向
引用类型作为参数
- 效果上，和指针传递一样，会改变实参。
- 内存中不会产生实参的副本，效率会更高。
- 后续十分常用。
数组做函数的参数
#include<iostream.h>
#define N 10
int max(int a[]) \\这是一个对函数的声明
void main(){
int a[10];
int i,m;
for(i=0;i<N;i++)
cin>>a[i];
m=max(a); \\在这里传入的是列表的头元素指针
cout<<"the max number is:"<<m;
}
int max(int b[]){
int i,n;
n=b[0];
for(i=1;i<N;i++)
if(n<b[i])
n=b[i];
return n;
}线性表的顺序储存表示
Warning
逻辑结构（从1开始）与物理结构（从0开始）的储存标号差1
若如下定义一个顺序表，有两种常用访问元素方法
#define MAXSIZE 100
typedef struct{
ElemType *data
int length
}SqList调用元素方式1
SqList L;
L.elem[0]
L.elem[1]
调用元素方式2
SqList *L;
L->elem[0]
L->elem[1]Note
Status指的通常是返回值类型elemtype指的通常是元素类型
顺序表的基本操作的实现
线性表的初始化（参数用引用）
Status InitList(SqList &L){ \\这是一种动态分配，可通过销毁操作释放储存空间
L.elem=new ElemType[MAXSIZE];
if (!L.elem) exit (OVERFLOW);\\表示储存分配失败退出
L. length=O ;
return OK;
}
销毁线性表
void DestroyList(SqList &L){
if (L.elem) delete L.elem;
}清空线性表
void Clearlist(Sqlist &L){
L.length = 0;
}求表长
int GetLength(SqList L){
return (L.length);
}Note
在这里不传入引用是因为函数不会对实参做出改变。
判断表是否为空
int IsEmpty(SqList L){
if (L.length==0) return 1;
else return 0;
}顺序表的取值
int GetElem(SqList L,int i,ElemType &e){
if(i<1||i>L.length) return ERROR;
e=L.elem[i-1];
return OK;
}Note
顺序表的主要好处：随机存取机制。存取任何一个元素都可以用下标直接获得，算法复杂度常数阶。
顺序表的查找
int LocateElem(SqlList L, ElemType e){
for(i=0;i<L.length;i++)
if(L.elem[i]==e)
return i+1;
return 0;
}顺序查找的平均查找长度,其中表示第个记录呗查找的概率，表示第个记录被查找需要比较的次数（循环要执行多少次）
平均移动次数与时间复杂度：
顺序表的插入
ListInsert(&L,i,e) —在表L的第i个位置的前面，插入元素e
Hint
这样使得插入之后的第个元素是e！
Status ListInsert_Sq(SqList &L,int i,ElemType e){
if(i<1||i>L.length+1) return ERROR; \\判断是否为合法位置
if(L.length==MAXSIZE) return ERROR; \\判断是否为合法位置
for(j=L.length-1;j>=i-1;j--)
L.elem[i-1]=e;
L.length++;
return OK;
}平均移动次数与时间复杂度：
顺序表的删除
Status ListDelete Sq(SqList &L,int i){
if((i<1)||(i>L.length)) return ERROR; \\判断是否为合法位置
for(j=i;j<=L.length-1;j++)
L.elem[j-1]=L.elem[j];
--L.length;
return OK;
}平均移动次数与时间复杂度：
Note
上面三个是重点基本操作，时间复杂度均为，空间复杂度均为
Hint
顺序表的缺点：
插入元素时候需要移动大量元素 浪费储存空间 数据元素个数不能自由扩充