行业知识
408考研-数据结构-线性表
文章目录
- 考点一:基本定义和结构
- 考点二:线性表的顺序存储
- 基础代码
- 1.1创建顺序表
- 1.2 初始化/销毁顺序表
- 1.3 判断表是否为空
- 1.4 获取表的长度
- 1.5 输出/打印表
- 1.6 返回某个位置的数据的元素值,某个值的位置
- 1.7 插入
- 1.8 删除
- 进阶应用
- 2.1 删除
- 2.2合并表
- 2.3 逆置
- 2.4 基准分割
- 2.5 类型划分
- 题目:
- 其他:
》》 沐沐雪:“代码还是要自己手敲,逻辑思路最好在纸上笔划以下,才能理解的更清晰深刻”
考点一:基本定义和结构
���性表:
()- 具有相同类型的数据元素的有限序列,具有一对一的逻辑关系,相邻元素有前驱和后继的关系
- 元素的下标代表元素在线性表中的位置
- 除第一个元素,其他的都有前驱,除最后一个元素,其他的都有后继
- 空间连续,提前分配;查找容易,增删难
- 逻辑关系是由存储位置表示的
考点二:线性表的顺序存储
顺序表:线性表的节点按照逻辑顺序依次存放到连续的存储单元里面的表
ps:这里的连续指的是内存单元地址的连续
()所以元素的存储位置LOC(ai)满足以下关系
L C O ( a i ) = L O C ( a i ) + L LCO(a_i) = LOC(a_i) + L LCO(ai)=LOC(ai)+L
基础代码
//顺序表基本运算算法#include #include #define MaxSize 50typedef int ElemType;typedef struct{ElemType data[MaxSize];//存放顺序表元素int length;//存放顺序表的长度} SqList;//顺序表的类型1.1创建顺序表
void CreateList(SqList*& L, ElemType a[], int n){L = (SqList*)malloc(sizeof(SqList));for (int i = 0; i data[i] = a[i];L->length = n;}注:
-
这里使用到的malloch函数需要导包:#include
-
SqList* L 和SqList* &L 的区别
&是引用符号
在函数调用的时候,我们传入的都是真实的数据,称之为实参,而函数内代码使用到的叫做形参
在数据传入的时候,会按照你传入的数据copy一份来进行运算,真实的数据并不会加入运算。
但是引用不是,它的参数是直接使用真实的数据的。
1.2 初始化/销毁顺序表
void InitList(SqList*& L){L = (SqList*)malloc(sizeof(SqList));//分配存放线性表的空间L->length = 0;}void DestroyList(SqList*& L){free(L);}1.3 判断表是否为空
bool ListEmpty(SqList* L){return(L->length == 0);}1.4 获取表的长度
int ListLength(SqList* L){return(L->length);}1.5 输出/打印表
void DispList(SqList* L){for (int i = 0; i length; i++)printf("%d ", L->data[i]);printf("\n");}1.6 返回某个位置的数据的元素值,某个值的位置
bool GetElem(SqList* L, int i, ElemType& e){if (iL->length)return false;e = L->data[i - 1];return true;}int LocateElem(SqList* L, ElemType e){int i = 0;while (i length&& L->data[i] != e) i++;if (i >= L->length)return 0;elsereturn i + 1;}需要特别注意:如果你想要返回的是第一个元素,对应的是a[0],而不是a[1]。返回的值,会传给e这个变量
1.7 插入
bool ListInsert(SqList*& L, int i, ElemType e){int j;if (iL->length + 1 || L->length == MaxSize)return false;i--;//转化为elem数组的下标for (j = L->length; j > i; j--) //将data[i]及后面元素后移一个位置L->data[j] = L->data[j - 1];L->data[i] = e;L->length++;//顺序表长度增1return true;}注意:
- 比如说你要插入到第一位,那么原来在第一个位置上的元素,和一后面的元素都得向后移动一位
- 长度也就是顺序表的内元素的个数length要 “+1”
- 插入的条件,你不能在表满的时候插入进去,也不能插入在负数的位置
- 时间复杂度:最好情况O(1),最坏情况O(n)
1.8 删除
bool ListDelete(SqList*& L, int i, ElemType& e){int j;if (iL->length)return false;i--;//将顺序表位序转化为elem下标e = L->data[i];for (j = i; j length - 1; j++)//将data[i]之后的元素前移一个位置L->data[j] = L->data[j + 1];L->length--;//顺序表长度减1return true;}注:
- 同上,删除之后,后面的元素就得往前靠一靠,把空位补上
- 时间复杂度:同上
进阶应用
2.1 删除
题:删除表中所有值等于x的元素
void delnode1(SqList *&L,ElemType x){int k=0,i; //k记录值不等于x的元素个数for (i=0;ilength;i++) if (L->data[i]!=x){L->data[k]=L->data[i];k++; //不等于x的元素增1}L->length=k; //顺序表L的长度等于k}思路:这个方法定义了两个指向,i是原来的,k是修改后的;i扫描元素,如果不等于x就把元素给k,如果等于就不给。一个扫描一个建表
void delnode2(SqList *&L,ElemType x){ int k=0,i=0; //k记录值等于x的元素个数while (ilength) {if (L->data[i]==x) k++;else L->data[i-k]=L->data[i]; //当前元素前移k个位置i++;}L->length-=k;//顺序表L的长度递减k}思路:定义k为移动跨度,如果有两个值等于x,则后面的元素就需要向前补两格
2.2合并表
把表A和表B按从小到大的顺序合并成一个表C,A表B表的元素个数分别为mn
表A,表B均为非递减
void Combination(SqList* L1, SqList* L2, SqList* L3) {int i = 0, j = 0, k = 0;while ((i != L1->length) && (j != L2->length)) { //判断AB表是否为空表if (L1->data[i] > L2->length) {L3->data[k++] = L2->data[j++];}else if (L1->data[i] == L2->length){L3->data[k++] = L2->data[j++];//相同保留一个i++;}else {L3->data[k++] = L1->data[i++];}L3->length++;}// 合并没结束,把剩余的加上去while (i length) {L3->data[k++] = L1->data[i++];L3->length++;}while (j length) {L3->data[k++] = L2->data[j++];L3->length++;}}2.3 逆置
实现顺序表逆置,
int ListOppose(SqList* L) {int i;ElemType x; //数据元素类型for (i = 0; i length / 2; i++) {x = L->data[i];L->data[i] = L->data[L->length - i - 1];L->data[L->length - i - 1] = x;}return 1;}void Reverse(int R[], int from, int to) {int i;int temp;for (i = 0; i2.4 基准分割
以第一个元素为基准,小的在前,大的在后
void move2(SqList *&L){int i=0,j=L->length-1;ElemType base=L->data[0];//以data[0]为基准while (iwhile (ji && L->data[j]>base)j--;//从右向左扫描,找一个小于等于base的data[j]L->data[i]=L->data[j];//找到这样的data[j],放入data[i]处while (idata[i]data[j]=L->data[i];//找到这样的data[i],放入data[j]处}L->data[i]=base;printf("i=%d\n",i);}2.5 类型划分
将所有的奇数移动到偶数前面
void swap(int &x,int &y)//交换x和y{int tmp=x;x=y; y=tmp;}void move1(SqList *&L){int i=0,j=L->length-1;while (iwhile (idata[i],L->data[j]);}}void move2(SqList *&L){int i=-1,j;for (j=0;jlength-1;j++)if (L->data[j]%2==1)//j指向奇数时{i++;//奇数区间个数增1if (i!=j)//若i、j不相等swap(L->data[i],L->data[j]);//L->data[i]和L->data[j]交换}}- 解法一:定义两个指针i,j,左边奇数区域的i从左向右去找偶数,右边偶数区域的j从右向左去找奇数,都找到了就对调
- 解法二:i初始负1,代表为奇数区域的个数为0个,j从左向右去找奇数,找到了奇数就和i指向的奇数换一下,换完之后j++,指向下一个
题目:
在一个长度为n的顺序表中删除第i个元素,需要向前移动()个元素
-
A n-i
-
B n-i+1
-
C. n-i-1
-
D. i+1
答案:A
在长度为n的顺序表中的任何一个位置插入元素的概率相等,则插入一个元素
所需移动的元素的平均个数是()
-
A n/2
-
B. n
-
C. n+1
-
D. (n+1)/2
注:插入位置有n+1个
答案:A
在表长为n的顺序表中,当在任何位置删除一个元素的概率相同时,删除一个
元素所需移动的元素的平均个数为
-
A. (n-1)/2
-
B. n/2
-
C. (n+1)/2
-
D. n
答案:A
在一个长度为n的线性表中顺序查找值为x的元素,查找时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的概率相等)为
- A n
- B (n+1)/2
- C n/2
- D (n-1)/2
答案:B
-1
- D. i+1
答案:A
在长度为n的顺序表中的任何一个位置插入元素的概率相等,则插入一个元素
所需移动的元素的平均个数是()
-
A n/2
-
B. n
-
C. n+1
-
D. (n+1)/2
注:插入位置有n+1个
答案:A
在表长为n的顺序表中,当在任何位置删除一个元素的概率相同时,删除一个
元素所需移动的元素的平均个数为
-
A. (n-1)/2
-
B. n/2
-
C. (n+1)/2
-
D. n
答案:A
在一个长度为n的线性表中顺序查找值为x的元素,查找时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的概率相等)为
- A n
- B (n+1)/2
- C n/2
- D (n-1)/2
答案:B
其他:
-
-
- D. i+1
-
-
-
上一篇:mir4服务器哪里查看?
下一篇:服务器BOSS怎么进入?