目录
注：部分素材来源于我的大学老师
线性表的抽象数据类型的定义
ADT List{
数据对象：D={ai|ai∈Elemset,i=1,2,…,n,n≥0}
数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}
基本操作：
(1) 初始化：InitList(&L)。
操作前提：L为未初始化线性表。
操作结果：将L初始化为空表。
(2) 销毁表：DestroyList(&L)。
操作前提：线性表L已存在。
操作结果：释放L空间，将L销毁
(3) 清空表：ClearList(&L)。
操作前提：线性表L已存在。
操作结果：将表L置为空表。
(4) 判断表是否为空：ListEmpty (L)。
操作前提：线性表L已存在。
操作结果：如果L为空表则返回真，否则返回假。
(5) 求长度：ListLength(L)。
操作前提：线性表L已存在。
操作结果：如果L为空表则返回0，否则返回表中的元素个数。
(6) 查找元素：LocateElem(L,e)。
操作前提：表L已存在，e为合法元素值。
操作结果：如果L中存在元素e，则将“当前指针”指向首次找到的其值为e的元素所在位置并返回真，否则返回假。
(7) 取元素：GetElem(L,i,&e)。
操作前提：表L存在，且i值合法，即1≤i≤ListLength(L)。
操作结果：用e返回线性表L中第i个元素的值。
(8) 插入元素：InsertList(&L,i,e)。
操作前提：表L已存在，e为合法元素值，且 1≤i≤ListLength(L) + 1。
操作结果：在L中第i个位置插入新的数据元素e，L的长度加1。
(9) 删除元素：DeleteList(&L,i,&e)。
操作前提：表L已存在且非空，1≤i≤ListLength(L)。
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。
(10) 显示线性表：Display(L)。
操作前提：线性表L已存在且不为空。
操作结果：依次显示表中所有元素的值。
}ADT List
上述是线性表抽象数据类型的定义，其中只是一些基本操作，另外可以更复杂。 如：将两个线性表合并等。 复杂的操作可用基本操作实现。
线性表的顺序表示和实现
线性表的顺序表示又称为顺序存储结构或顺序映像。
>>顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
>>简言之，逻辑上相邻，物理上也相邻
>>顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。
例1
顺序表存储结构的实现
#define MAXSIZE 100 //最大长度
typedef struct {
ElemType *elem; //指向数据元素的基地址
int length; //线性表的当前长度
}SqList；
元素类型：
例 typedef int ElemType;
例 typedef struct card
{ int num;
char name[20];
char author[10];
char pub[30];
float price;
}ElemType;
图书表的顺序存储结构类型定义
#define MAXSIZE 10000 //图书表可能达到的最大长度
typedef struct //图书信息定义
{
char no[20]; //图书ISBN
char name[50]; //图书名字
float price; //图书价格
}Book;
typedef struct
{
Book *elem; //存储空间的基地址
int length; //图书表中当前图书个数
}SqList; //图书表的顺序存储结构类型为SqList
补充：C语言的动态分配函数（ <stdlib.h> ）
malloc(m)：开辟m字节长度的地址空间，并返回这段空间的首地址
sizeof(x)：计算变量x的长度
free(p)：释放指针p所指变量的存储空间，即彻底删除一个变量
补充：C++的动态存储分配
new 类型名T（初值列表）
>>功能： 申请用于存放T类型对象的内存空间，并依初值列表赋以初值
>>结果值：
成功：T类型的指针，指向新分配的内存
失败：0（NULL）
int *p1= new int;
或
int *p1 = new int(10);
delete 指针P
>>功能： 释放指针P所指向的内存。
>>P必须是new操作的返回值
delete p1;
补充：C++中的参数传递
1.函数调用时传送给形参表的实参必须与形参在类型、个数、顺序上保持一致
2.参数传递有两种方式
>>传值方式（参数为整型、实型、字符型等）
>>传地址
参数为指针变量
参数为引用类型
参数为数组名
传值方式
1.把实参的值传送给函数局部工作区相应的副本中，函数使用这个副本执行必要的功能。
2.函数修改的是副本的值，实参的值不变
#include <iostream>
void swap(float m,float n)
{float temp;
temp=m;
m=n;
n=temp;
}
int main()
{float a,b;
cin>>a>>b;
swap(a,b);
cout<<a<<endl<<b<<endl;
return 0;
}
传地址方式
>>指针变量作参数
形参变化影响实参
#include <iostream>
void swap(float *m,float *n)
{float t;
t=*m;
*m=*n;
*n=t;
}
int main()
{float a,b,*p1,*p2;
cin>>a>>b;
p1=&a; p2=&b;
swap(p1, p2);
cout<<a<<endl<<b<<endl;
return 0;
}
形参变化不影响实参？？
#include <iostream>
void swap(float *m,float *n)
{float *t;
t=m;
m=n;
n=t;
}
int main()
{float a,b,*p1,*p2;
cin>>a>>b;
p1=&a; p2=&b;
swap(p1, p2);
cout<<a<<endl<<b<<endl;
return 0;
}
>>引用类型作参数
引用：它用来给一个对象提供一个替代的名字。
#include<iostream>
int main(){
int i=5;
int &j=i;
i=7;
cout<<"i="<<i<<" j="<<j;
return 0;
}
//j是一个引用类型, 代表i的一个替代名,i值改变时,j值也跟着改变，所以会输出i=7 j=7
#include <iostream>
void swap(float＆ m,float＆ n)
{float temp;
temp=m;
m=n;
n=temp;
}
int main()
{float a,b;
cin>>a>>b;
swap(a,b);
cout<<a<<endl<<b<<endl;
return 0;
}
引用类型作形参的三点说明：
（1）传递引用给函数与传递指针的效果是一样的，形参变化实参也发生变化。
（2）引用类型作形参，在内存中并没有产生实参的副本，它直接对实参操作；而一般变量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。因此，当参数传递的数据量较大时，用引用比用一般变量传递参数的时间和空间效率都好。
（3）指针参数虽然也能达到与使用引用的效果，但在被调函数中需要重复使用“*指针变量名”的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用变量的地址作为实参。
>>数组名作参数
1.传递的是数组的首地址
2.对形参数组所做的任何改变都将反映到实参数组中
#include<iostream>
void sub(char);
int main（void ）
{ char a[10]=“hello”;
sub(a);
cout<<a<<endl;
return 0;
}
void sub(char b[ ])
{ b[ ]=“world”;}
//用数组作函数的参数，求10个整数的最大数
#include <iostream>
#define N 10
int max(int a[]);
int 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;
return 0;
}
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;
}