小工具知识网

当前位置: 首页 > 行业知识 > 408考研-数据结构-线性表

行业知识

408考研-数据结构-线性表

2026-11-18 01:16:34 来源:互联网转载

文章目录

    • 考点一:基本定义和结构
    • 考点二:线性表的顺序存储
      • 基础代码
        • 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 类型划分
          • 题目:
          • 其他:

            》》 沐沐雪:“代码还是要自己手敲,逻辑思路最好在纸上笔划以下,才能理解的更清晰深刻”

            考点一:基本定义和结构

            ���性表:

            ()
            1. 具有相同类型的数据元素的有限序列,具有一对一的逻辑关系,相邻元素有前驱和后继的关系
            2. 元素的下标代表元素在线性表中的位置
            3. 除第一个元素,其他的都有前驱,除最后一个元素,其他的都有后继
            4. 空间连续,提前分配;查找容易,增删难
            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; i  
                  2.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

                                    其他:

上一篇:mir4服务器哪里查看?

下一篇:服务器BOSS怎么进入?