1.线性表的定义与基本操作
1)定义
具有相同类型数据的有限序列(有次序)。表长、空表、位序(是线性表中第几个元素,从1开始)
2)基本操作
初始化:InitList(&L);
增加元素:ListInsert(&L,i,e);
删除元素:LisDelete(&L,i,&e);//用e返回删除元素的值,要把数据“带回来”,传地址,其实也可以传e,用return语句带回来
销毁:DestroyList(&L);
按值查找:LacateElem(L,e);
按位查找:GetElem(L,i);
输出:PrintList(L);
判空:Empty(L);
.线性表的顺序表示
1)顺序表的定义
顺序存储实现的线性表。第一个a1元素位置,LOC(L);后续元素ai位置,LOC(L)+(i-1)*sizeof(ElemType)。
2)顺序表的实现
静态分配:
#define MaxSize 50 typedef struct{ int data[MaxSize]; int length; }SqlList; void InitList(SqlList &L) { int i; for(i=0;i<L.length;i++) L.data[i]=0; L.length=0; } int main(void) { SqlList L; InitList(L); int i; for(i=0;i<L.length;i++)printf("%d ",L.data[i]); return 0; }
动态分配:
#include<stdio.h> #include<stdlib.h> #define InitSize 4 //默认长度 typedef struct{ int * data; int MaxSize; int length; }SeqList; void InitList(SeqList &L) { L.data=(int *)malloc(InitSize*sizeof(int)); L.length=0; L.MaxSize=InitSize; } void IncreaseSize(SeqList &L,int len) { int * p=L.data; L.data=(int *)malloc((L.MaxSize+len)*sizeof(int)); for(int i=0;i<L.MaxSize;i++) L.data[i]=p[i]; free(p); L.MaxSize=L.MaxSize+len; } int main(void) { SeqList L; InitList(L); //这种插入数据的方式不规范,并没有改变length L.data[0]=1; L.data[1]=2; L.data[2]=3; L.data[3]=4; for(int i=0;i<L.MaxSize;i++) printf("a[%d]=%d,",i,L.data[i]); printf("\n"); IncreaseSize(L,3); for(int i=0;i<L.MaxSize;i++) printf("a[%d]=%d,",i,L.data[i]); return 0; }
3)顺序表的四大特点
可以随机访问。
存储密度高,只需存数据,不需存指针。
扩展容量不方便,静态分配无法扩展,动态分配需要把存储的内容复制到新分配的区域。
插入、删除效率低。
4)顺序表的基本操作
插入
#include<stdio.h> #include<stdlib.h> #define InitSize 10 typedef struct{ int * data; int length; int MaxSize; }SeqList; void InitList(SeqList &L) { int i=0; L.data=(int *)malloc(InitSize*sizeof(int)); for(i=0;i<L.MaxSize;i++)L.data[i]=0; L.length=0; L.MaxSize=InitSize; } bool ListInsert(SeqList &L,int i,int e)//i是位序,不是数组下标 { if(i<1||i>L.length+1) return false; if(i>L.MaxSize) return false; int j; for(j=L.length;j>=i;j--) L.data[j]=L.data[j-1]; //1 L.data[i-1]=e; L.length++; return true; } int main(void) { SeqList L; InitList(L); ListInsert(L,1,1); ListInsert(L,2,2); ListInsert(L,3,3); for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]); printf("\n"); ListInsert(L,1,0); for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]); return 0; }
最优时间复杂度:O(1),即插入到表尾——位序n+1处,不需要执行最深层的for循环(1处);
最坏时间复杂度:O(n),插入到表头——位序为1处,最深层for循环执行n次;
平均复杂度:O(n),每个位序插入的可能性是1/(n+1),(0+1+...+n)/(n+1)=n*(n+1)/2 /(n+1)=n/2;
删除
#include <stdio.h> #include <stdlib.h> #define InitSize 10 typedef struct{ int * data; int MaxSize; int length; }SeqList; void InitList(SeqList &L) { int i; L.data=(int *)malloc(InitSize*sizeof(int)); L.MaxSize=InitSize; for(i=0;i<L.MaxSize;i++) L.data[i]=0; L.length=0; } bool ListInsert(SeqList &L,int i,int e) { int j; if(i<1||i>L.length+1)return false; if(i>L.MaxSize)return false; for(j=L.length;j>=i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=e; L.length++; return true; } //按位删除 bool ListDelete(SeqList &L,int i,int &e) //此处传入的参数i是位序为i的元素,即删除对应下标为i-1的元素 { if(i<1||i>L.length)return false; e=L.data[i-1]; int j; for(j=i;j<L.length;j++) L.data[j-1]=L.data[j]; L.length--; return true; } int main(void) { int e=-1; SeqList L; InitList(L); ListInsert(L,1,1); ListInsert(L,2,2); ListInsert(L,3,3); for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]); printf("\n"); if(ListDelete(L,1,e)) printf("Delete %d\n",e); else printf("Failure!\n"); for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]); return 0; }
最好时间复杂度:O(1);
最坏时间复杂度:O(n);
平均复杂度:O(n);
按位查找
#include<stdio.h> # define MaxSize 10 typedef struct{ int data[MaxSize]; int length; }SeqList; void InitList(SeqList &L) { int i; for(i=0;i<MaxSize;i++)L.data[i]=0; L.length=0; } bool ListInsert(SeqList &L,int i,int e) { int j; if(i<1||i>L.length+1)return false; if(i>MaxSize)return false; for(j=L.length;j>=i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=e; L.length++; return true; } int GetElem(SeqList L,int i){ if(i<1||i>L.length) return -1; return L.data[i-1]; } int main(void) { SeqList L; InitList(L); ListInsert(L,1,1); ListInsert(L,2,2); ListInsert(L,3,3); printf("%d,",GetElem(L,1)); printf("%d\n",GetElem(L,0)); return 0; }
时间复杂度:O(1)
按值查找
int LocateElem(SeqList L,int e) { int i; for(i=0;i<L.length;i++) if(L.data[i]==e)return i+1; return 0; }
最好时间复杂度:O(1)
最坏时间复杂度:O(n)
平均时间复杂度:O(n)
5)练习题
T1 删除顺序表中的最小值(假设唯一),并由函数返回被删元素的值。若顺序表为空则显示出错信息并退出运行
//删除最小元素,并返回该元素的值 bool ListDelete(SeqList &L,int &min) { int i; int index=0;//记录最小元素的位序 if(L.length==0) return false; //如果链表为空,则返回false min=L.data[0]; //查找最小的元素 for(i=1;i<L.length;i++) { if(L.data[i]<min) min=L.data[i]; index=i+1; } //将空出来的位置由最小的元素代替 L.data[index]=L.data[L.length-1]; L.length--; return true; }
T2 设计算法将顺序表中的元素逆序,要求算法的空间复杂度O(1);
bool ReverseList(SeqList &L) { if(L.length==0)return false; int i; int j; int temp; for(i=0;i<(L.length)/2;i++) { j=L.length-i-1; temp=L.data[i]; L.data[i]=L.data[j]; L.data[j]=temp; } return true; }
*T3 长度为n的顺序表L,编写一个时间复杂度为O(n),空间复杂度为O(1)的算法。该算法删除线性表中所有值为x的元素。
void DeleteByValue(SeqList &L,int 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++; } } L.length=k; }
T4 从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素,如果s或者t不合理或顺序表为空,则显示出错信息并退出运行。
bool DeleteBetweenValue(SeqList &L,int s,int t,int &start,int &end) { if(L.length==0) return false; if(s>=t) return false; int i; for(i=0;i<L.length;i++) { if(L.data[i]==s)start=i+1; if(L.data[i]==t)end=i+1; } return true; } int main(void) { int e=0; SeqList L; InitList(L); int start; int end; ListInsert(L,1,1); ListInsert(L,2,2); ListInsert(L,3,3); for(int i=0;i<L.length;i++)printf("%d,",L.data[i]); DeleteBetweenValue(L,1,2,start,end); printf("\n"); int k=end-start+1; for(int j=0;j<k;j++) ListDelete(L,start,e); for(int i=0;i<L.length;i++)printf("%d,",L.data[i]); return 0; }