1.线性表的基本定义
| 知识点1 | 线性表：简称表，是n（n>=0）个数据元素的有限序列。L=（a1,a2,a3,……,an）长度：线性表中数据元素的个数称为线性表的长度。 长度等于零的线性表称为空表。 |
|---|
| 知识点2 | 线性表的逻辑特征：第一个元素无前驱，其余元素有且仅有一个前驱；最后一个元素无后继，其余元素有且仅有一个后继。 | | 知识点3 | 数据最常用的五个运算：插入、删除、修改、查找、排序 | | 知识点4 | 线性表的顺序存储结构寻址公式：loc(ai)=loc(a1)+(i-1)*C |
（线性表随机存取结构）定义：
typedef ?struct ? { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Datatype data[MaxSize]； ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? int length； ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }seqlist；
2.1顺序表的算法
2.1.1初始化空表 T(n)=O(1)
seqlist * Initlist()
{
? seqlist *L;
? L->length=0;
? return (L);
}
2.1.2初始化非空表 T(n)=O(n)
seqlist *L；
int createlist（seqlist *L,datatype r[],int n）
{ int i;
? if(n>MaxSize)
? {printf("空间不足"); return 0；}
? ?for(i=0;i<n;i++)
? ? ? ?L->data[i]=r[i];
? ?L->length=n;
? ?return 1;
}
2.1.3判定表是否为空 T(n)=O(1)
int empty（seqlist *L）
{
? if（L->length==0） return 1;
?else return 0;
}
2.1.4求顺序表的长度 T(n)=O(1)
int length(seqlist *L)
{
? ?return L->length;
}
2.1.5顺序表遍历 T(n)=O(n)
void printList(seqlist *L)
{
? for(i=0;i<L->length;i++)
? ? printf("%d",L->data[i]);
}
2.1.6查找i位置的数据元素 T(n)=O(1)
datatype Get（seqlist *L,int i,datatype *ptr）
{
? if(i<1||i>L->length)
? { printf("参数异常")；return 0;}
?else { *prt=L->data[i-1] ?return 1;}
}
2.1.7查找值为x的数据元素 T(n)=O(n)
int ?Locate(Seqlist *L, datatype x)
{
? for(i=0;i<L->length;i++)
? {
? ? ?if(x==L->data[i]) return (i+1);
? }
? return 0;
}
2.1.8插入算法 T(n)=O(n)
int insertlist（seqlist *L,int i,datatype x）
{
? ?if(L->length>=Maxsize)
? ? {
? ? ? ?printf("上溢异常！")；return 0；}
? ?if(i<1||i>L->length+1)
? ? {
? ? ? ?printf("位置异常！")；return 0；}
? ?for(j=L->length ;j>=i; j--)
? ? {
? ? ? L->data[j]=L->data[j-1]
? ? ? L->data[i-1]=x;
? ? ? L->length++;
? ? ? ?return 1; }
}
2.1.9删除算法 T(n)=O(n)
int deletelist(seqlist *L,int i,datatype *ptr)
{ ?
? ? if(L->length<=0)
? ? {
? ? ? ?printf("下溢异常！")；return 0；}
? ? if(i<1||i>L->length)
? ? {
? ? ? ? printf("位置异常！")；return 0；}
? ? ?*ptr=L->data[i-1];
? ? ?for(j=i;j<=L->length-1;j++)
? ? ? {
? ? ? ? ?L->data[j-1] =L->data[j]
? ? ? ? ?L->length--;
? ? ? ? ?return 1;}
}
2.1.10逆置算法 T(n)=O(n)
void reverse（int r[],int n）
{ ?int i;
? ?for(i=0;i<n/2,i++)
? {
? ? ? ? t=r[i] ;r[i]=r[n-1-i]; r[n-1-i]=t;
? }
} ?
2.1.11循环左移K的位置的算法 T(n)=O(n)
void reverse（int r[],int s,int e）
{ ?int i;
? ?for(i=s,j=e;i<j;i++,j--)
? {
? ? ? ? t=r[i] ;r[i]=r[j]; r[j]=t;
? }
}
void move(int r[], int n,int k)
{ ? reverse(r[],0,k-1);
? ?reverse(r[],k,n-1);
? ?reverse(r[],0,n-1);
}
2.1.12奇偶划分 T(n)=O(n);
void divide(int r[],int n)
{
? i=0;j=n-1;
? while(i<j)
? ? { ?
? ? ? while(r[i]%2==1 && i<j) i++;
? ? ? while(r[j]%2==0 && i<j) j--;
? ? ? if(i<j)
? ? ? ? {
? ? ? ? ? t=r[i];r[i]=r[j];r[j]=t;
? ? ? ? ? i++;j--
? ? ? ? }
? ? }
}
|