动态分配的顺序线性表的十五种操做—C语言实现

2021年09月15日 阅读数:2
这篇文章主要向大家介绍动态分配的顺序线性表的十五种操做—C语言实现,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

线性表c++

定义:是最经常使用的,也是最简单的数据结构,是长度为n个数据元素的有序的序列。算法

含有大量记录的线性表叫文件数组

记录:稍微复杂的线性表里,数据元素为若干个数据项组成,这时把一个数据元素叫记录数据结构

结构特色:在非空有限的条件下,存在惟一的一个表头结点,惟一的一个表尾结点,除去第一个元素以外,每一个数据元素都只有一个前驱,除去最后一个元素以外,每个数据元素都只有一个后继。ide

注意:线性表中的数据元素能够是各类各样的,但同一线性表中的元素一定具备相同特性(属于同一数据对象,相似数组)。线性表的数据元素间有序偶关系。函数

 

线性表的顺序表示和实现spa

有一组地址连续的内存单元,在这些连续的内存单元里,顺次地存储线性表里的数据元素操作系统

特色:逻辑地址和物理地址都是连续的,适合随机存取。假设&a1为线性表的基址,每一个数据元素占据L个存储单位。那么表里第i个元素的存储地址:指针

&a(i) = &a(1) + (i - 1)x Lcode

线性表的顺序表示结构(顺序映象)也叫顺序表,顺序表中元素的逻辑关系和物理位置一致,是一种随机存取的存储结构。

(相似高级语言里的数组,一般用数组描述数据结构的顺序存储结构)。

 

若是用数组表示顺序表,那很简单,也不实用,不能改变存储容量,下面是动态分配的顺序表的表示和操做

ADT.h头文件

动态分配的顺序线性表的十五种操做—C语言实现_记录 头文件

ADTList.c文件

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 /************************************************************************/ 2 /*函数定义在此文件                                                    */ 3 /************************************************************************/ 4 #include "ADT.h" 5 /************************************************************************/ 6 /*第一类:初始化操做,记住各类数据结构开始使用都要初始化                */ 7 /************************************************************************/ 8  9 //注意c数组下标从0开始,可是用户并不知道,通常都是选择从1到length的位置,以用户的角度看问题10 11 //一、线性表的初始化,构造一个空的线性表,由于要改变线性表,必须用指针作参数12 int InitList(SqList *L)13 {14     //在堆中为线性表分配内存,初始化elem为该内存空间的首地址(基址)15     L->elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int));//结构里只是存储了表的地址值,而表自己存储在其余地方16     //判断是否分配成功17     if (!L->elem)//若是 !L->elem 为真(为空),执行下面代码18     {19         printf("线性表内存分配失败!退出程序。\n");20         exit(1);//函数异常退出,返回给操做系统121     }22     //表内存空间分配成功23     L->length = 0;//开始是空表,没有存储任何元素,故表长置为024     //当前为线性表分配的存储容量25     L->listsize = LIST_INIT_SIZE;//初始化表的存储容量,这是当前表最大的存储量26     return 0;//分配成功返回027 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

虽然在堆开辟了一块内存空间给线性表,可是须要设置一个变量listsize,来显式的代表表的最大存储容量的数值,方便程序使用(分配的空间内存大小和表长是两回事,表长是表内当前的元素个数,也就是此时线性表当前的存储容量)

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 /************************************************************************/ 2 /*第二类:销毁操做,记住各类数据结构使用了都要有销毁的步骤              */ 3 /************************************************************************/ 4  5 //二、释放内存,销毁表操做,直接把内存释放的操做!相似free()和c++的delete操做符 6 //注意:用malloc函数分配的空间在释放时是连续释放的,即将物理地址相邻的若干空间所有释放 7 //因此顺序表销毁能够只释放基址,就自动释放全部空间,而链表要一个一个的把节点删除 8 void Destory(SqList *L) 9 {10     if (L->elem)//若是当前表还存在11     {12         free(L->elem);//销毁之13         //内存都没了,整个表也就不存在了,别的不用管。14         printf("本线性表已销毁!\n");15     }16 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

注意:用malloc函数分配的空间在释放时是连续释放的,即将物理地址相邻的若干空间所有释放,因此顺序表销毁能够只释放基址自动释放全部空间,而链表要一个一个的把节点删除

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 /************************************************************************/ 2 /* 第三类:引用型操做,操做不改变线性表里的数据元素,也不改变他们之间的关系 3 /************************************************************************/ 4  5 //三、判空操做 6 void ListEmpty(SqList L) 7 { 8     //判断表是否存在 9     if (L.elem)10     {11         //判断是否存储了内容12         if (0 == L.length)13         {14             puts("本表为空!");//自动换行15         }16         else17         {18             puts("表不为空!");19         }20     }21     else22     {23         puts("表不存在!");24     }25 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

0 == L.length,我的喜欢这种写法,避免出错,若是一时疏忽,写=,则编译报错!常量不能做为左值出现,来提醒本身

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 //四、求长度操做,若线性表已经存在,则返回表L中元素个数 2 int ListLength(SqList L) 3 { 4     if (L.elem) 5     { 6         return L.length; 7     } 8     puts("表不存在,没法求长度!"); 9     return 0;10 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 //五、定位操做:线性表 L 已存在,返回 L 中第 1 个与 e 知足相等关系的元素位置。 2 int LocateElem(SqList L, int e) 3 { 4     int i;//定位 5     for (i = 0; i < L.length; i++) 6     { 7         //数组名自己就是数组的首地址 8         if (e == L.elem[i] && i < L.length) 9         {10             printf("定位成功,该元素的位置 = %d\n", i + 1);11             return i + 1;12         }13     }14     puts("定位失败!没有找到该元素");15     return 0;16 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

我的以为由于已经有初始化操做和判空操做,则其他函数不用再写判断表存在否的语句

c的数组下标从0开始,可是仍是习惯1对应第一个数据元素,以此类推……

一、定位算法的时间复杂度分析

假设表长为n

最好的状况,若是第一个元素就知足关系,那么时间复杂度为0(1)

最坏的状况,若是最后一个元素知足关系或者没有知足关系的(依然仍是比较了),时间复杂度为0(n)

二、算法平均时间复杂度:

显然是和表长成正比的,为0(n)

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 //六、求元素后继,线性表 L 已存在。若 cur_e是 L 中的元素,返回后继 2 void NextElem(SqList L, int cur_e) 3 { 4     int i = LocateElem(L, cur_e);//先定位参照元素的位置 5  6     if (0 != i) 7     { 8         if (i == L.length) 9         {10             puts("这是最后一个元素,没有后继!");11         }12         else13         {14             printf("%d的后继是%d\n", L.elem[i - 1], L.elem[i]);15         }16     }17     else18     {19         puts("表中没有这个元素!");20     }21 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

注意:区分数组角度看问题和用户角度看问题,表长范围等不要混淆。

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 //七、获得指定的元素值,线性表 L 已存在, e 返回 L 中第 i 个元素的值。  2 int GetElem(SqList L, int i, int e) 3 { 4     if (i < 1 || i > L.length) 5     { 6         puts("超出了查找范围,从新输入!"); 7         return 0; 8     } 9     e = L.elem[i - 1];10     return e;11 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

这里没有打印,只是返回了值,不太好,由于出现了一个问题,函数内部的e是局部变量,且是值传递参数类型,函数执行完毕,e的内存消失,再也不起做用,对实参没有影响。在函数外打印e的值得不到正确值

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 int GetElem(SqList L, int i, int *e) 2 { 3     if (i < 1 || i > L.length) 4     { 5         puts("超出了查找范围,从新输入!"); 6         return 0; 7     } 8     *e = L.elem[i - 1]; 9     printf("%d\n", *e);10     return *e;11 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

改进:或者增长函数内的打印语句,或者把e变为指针类型的变量,能够修改实参,相应的声明里也要修改!

 

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 /八、求元素前驱,线性表L已经存在,若cur_e是L的数据,则返回前驱 2 void PriorElem(SqList L, int cur_e) 3 { 4     int i = LocateElem(L, cur_e);//若是定位失败返回0 5  6     if (0 != i) 7     { 8         if (1 == i) 9         {10             puts("这是第一个元素,没有前驱!");11         }12         else13         {14             printf("找到了%d的前驱%d \n",  L.elem[i - 1], L.elem[i - 2]);15         }16     } 
17     else18     {19         puts("找不到这个元素!");20     }21 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

注意一下: L.elem[i - 1]和 L.elem[i - 2]与i的关系

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 //九、遍历表中元素,线性表 L 已存在,打印出表中每一个元素  2 void ListTraverse(SqList L) 3 { 4     int i; 5  6     for (i = 0; i < L.length; i++) 7     { 8         printf("%5d", L.elem[i]); 9     }10 11 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

%5d,宽度为5打印输出

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 /************************************************************************/ 2 /* 第四类:加工型操做                                                   */ 3 /************************************************************************/ 4  5 //十、把表清空(不释放内存),线性表 L 已存在,将 L 重置为空表。  6 void ClearList(SqList *L) 7 { 8     if (L->elem) 9     {10         L->length = 0;//顺序表置空,表长为0便可11     }12 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

和销毁内存区分

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 //十一、给表元素赋值,线性表 L 已存在,1≤i≤LengthList(L) 2 //L 中第 i 个元素赋值为 e   3 void PutElem(SqList *L, int i, int e ) 4 { 5     if (i < 1 || i > L->length) 6     { 7         puts("超出表范围!"); 8     } 9     L->elem[i - 1] = e;10 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

经常使用的,也是比较重要的插入和删除算法

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 //十二、插入操做,线性表 L 已存在,1≤i≤LengthList(L)+1。在 L 的第 i 个元素以前插入新的元素 e,L 的长度增 1。  2 void ListInsert(SqList *L, int i, int e ) 3 { 4     SqList *NL;//声明一个额外的结构指针指向从新分配的表内存空间 5     int *j; 6     int *k; 7     //注意c数组下标从0开始,可是用户并不知道,通常都是选择从1到length的位置,以用户的角度看问题 8     //在元素i以前插入,则把i和i后面的所有元素顺次后移一位 9     if (i < 1 || i > L->length + 1)//最后一个元素后一位插入合法,不用移动直接插便可10     {11         puts("超出表范围!");12     }13     //考虑问题要全,由于可能会不止一次插入操做,迟早会超出表的存储容量14     else if (L->length >= L->listsize)15     {16         //从新分配内存,增长存储空间17         NL->elem = (int *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(int));18         if (!NL->elem)//分配失败,返回NULL19         {20             exit(0);//退出21         }22         //分配成功23         L->elem = NL->elem;//获得扩大以后的新基址24     }25     //指示用户的实际插入位置26     j = &(L->elem[i - 1]);//数组下标从0开始27     //最后一个数据元素的实际位置是length-128     for (k = &(L->elem[L->length - 1]); k >= j; k--)//这里k--不是1的减量!而是指针的减量操做,每次是int类型字节大小变化29     {30         *(k + 1) = *k;//从j到k的元素顺次后移一位31     }32     *j = e;//完成插入33     L->length++;//别忘表长加134 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

一、须要注意一下运算符优先级,箭头(间接运算符)的优先级很高,高于取地址&

二、解析realloc函数

它能够对给定的指针所指的空间进行扩大或者缩小,原有内存的中内容将保持不变。对于缩小,则被缩小的那一部分的内容会丢失 ,realloc 并不保证调整后的内存空间和原来的内存空间保持同一内存地址。realloc 返回的指针极可能指向一个新的地址。由于realloc是从堆上分配内存,当扩大内存空间,realloc直接从堆上现存的数据后面的那些字节中得到附加的字节,但若是数据后字节不够,就用堆上第一个有足够大小的自由块,现存的数据被拷贝至新的位置,而老块则放回到堆上。

在代码中,若是咱们采用i = (int*)realloc(i, 2*sizeof(int))的从新分配内存方式,有如下两种状况:

分配成功:
realloc函数完成后,i 曾经指向的旧内存自动free掉。

分配失败,返回NULL值:
此时,i 原来指向的内存尚未被free掉,而如今又找不到地址,这样就出现memory leak!

解决办法:定义另外一个指针j用于接收realloc返回值,判断是否成功,成功则将 j 赋给 i

三、插入算法的时间复杂度分析:

问题规模是表的长度,值为 n。 算法的时间主要花费,在向后移动元素的 for 循环语句上。该语句的循环次数为 (n– i +1),新航道雅思培训所需移动结点的次数不只依赖于表的长度 n,并且还与插入位置 i 有关。

当插入位置在表尾 (i=n +1) 时,不须要移动任何元素;这是最好状况,其时间复杂度 O(1)。

当插入位置在表头 (i = 1) 时,全部元素都要向后移动,循环语句执行 n 次,这是最坏状况,其时间复杂度 O(n)。

 

四、插入算法的平均时间复杂度:

设 pi 为第 i 个元素以前插入一个元素的几率,则在长度为 n 的线性表中插入一个元素时所需移动元素次数的指望值为 

动态分配的顺序线性表的十五种操做—C语言实现_动态_28

假设在n+1个位置上,插入的几率同样,那么pi = 1/(n+1);

E = pi【(n)+(n-1)+ ……+ 3 + 2 + 1】 =pi x( n(n+1)/ 2) = n / 2

因而可知,在顺序表上作插入运算,平均要移动 

一半元素。当表长 n 较大时,算法的效率至关低。

 

 

 

插入

 

算法的

 

平均时间复杂度为 O(n)。

 

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 //1三、删除操做,表 L 已存在且非空,1≤i≤LengthList(L)。删除 L 的第 i 个元素,并用 e 返回其值,长度减 1。  2 void ListDelete(SqList *L, int i, int *e ) 3 { 4     int *p; 5  6     if (i < 1 || i > L->length) 7     { 8         puts("i的值不合法!从新输入!"); 9     } 
10     else11     {12         //找到被删除元素的实际位置13         p = &(L->elem[i - 1]);14         *e = L->elem[i - 1];15         //p(不包含p)后面的元素依次前移一位16         for (; p < &(L->elem[L->length - 1]); p++)17         {18             *p = *(p + 1);19         }20         L->length--;21     }22 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

一、这里e使用指针变量,这样形参就能够修改实参!

二、删除算法的时间复杂度分析

算法的时间主要花费在向前移动元素的 for 循环语句上。该语句的循环次数为 (n – i)。由此可看出,所需移动结点的次数不只依赖于表的长度 n,并且还与删除位置 i 有关。

当删除位置在表尾 (i = n) 时,不须要移动任何元素;这是最好状况,其时间复杂度 O(1)。

当删除位置在表头 (i = 1) 时,有 n -1 个元素要向前移动,循环语句执行 n -1 次,这是最坏状况其时间复杂度 O(n)。

 

三、算法的平均时间复杂度:

设 qi 为删除第 i 个元素的几率,则在长度为 n 的线性表中删除一个元素时所需移动元素次数的指望值为

动态分配的顺序线性表的十五种操做—C语言实现_记录_31 

假设,每个位置的元素被删除的几率都同样,那么qi = 1 / n

E = qi【(n-1)+(n-2)+……+3+2+1】=1/n x ((n-1)n / 2)=(n - 1)/ 2

可见,在顺序表上作删除运算,平均也要移动表上 

一半元素。当表长 n 较大时,算法的效率至关低。算法的平

均时间复杂度为 O(n)。 

 

 

 

 

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 /************************************************************************/ 2 /* 额外的几个复杂操做                                                   */ 3 /************************************************************************/ 4  5 //一、合并线性表AB,把在线性表B里,但不存在于线性表A的元素插入到A中 6 //只改变A,不修改B 7 void Union(SqList *LA, SqList LB) 8 { 9     int i;10     int e;11     int lengthA = LA->length;12     int lengthB = LB.length;13 14     //在B里依次取得每一个数据元素,顺序在A里比较,若不存在则插入15     for (i = 1; i <= lengthB; i++)16     {17         GetElem(LB, i, &e);18         if (!LocateElem(*LA, e))//A里没有这个元素19         {20             //插入到A尾部21             /*lengthA++;22             ListInsert(LA, lengthA, e);*/23             ListInsert(LA, ++lengthA, e);24         }25     }26     Destory(&LB);27 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

算法复杂度分析:

GetElem函数执行和表长没有关系,插入函数每次都在最后一位插入,执行时间和表长也没有关系,而LocateElem函数执行时间和表长有关系,无序合并算法的时间复杂度主要取决于LocateElem的执行时间,前面分析过,LocateElem时间复杂度:0(lengthA),那么本算法的时间复杂度为:O(lengthA x lengthB)

 

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 //二、合并线性表AB,AB的元素按值非递减有序的排列,要把A和B归并为一个新表C,且C的元素依然是按照值非递减的有序排列 2 void MergeList(SqList LA, SqList LB, SqList *LC) 3 { 4     InitList(LC);//构造新表c 5     int lengthA = LA.length; 6     int lengthB = LB.length; 7     int lengthC = LC->length;//C表初始化为空表,0 8     int i = 1;//i标记LA 9     int j = 1;//j标记LB10     int iLA;11     int jLB;12 13     while ((i <= lengthA) && (j <= lengthB))14     {15         //分别取得元素值,比较16         GetElem(LA, i, &iLA);17         GetElem(LB, j, &jLB);18         if (iLA <= jLB)//LA,LB都是非递减排列19         {20             lengthC++;//总在末尾插入21             ListInsert(LC, lengthC, iLA);22             i++;23         }24         else25         {26             ListInsert(LC, ++lengthC, jLB);27             j++;28         }29     }30     //AB不会同时比完,必定会有一个表彻底插入到c以后,另外一表剩余31     while (i <= lengthA)32     {33         GetElem(LA, i++, &iLA);34         ListInsert(LC, ++lengthC, iLA);//原本AB就有序,直接所有插入到C末尾便可35     }36     //or37     while (j <= lengthB)38     {39         GetElem(LB, j++, &jLB);40         ListInsert(LC, ++lengthB, jLB);41     }42 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

算法时间复杂度分析:

不论表AB,哪一个表,确定有一个表先彻底比完,好比是LA,比较了lengthA次。以后,两个while语句,就执行一个,就是LB剩余的元素顺次插入C表剩余次数的过程,加上以前LB和LA的比较次数,那么综合得其时间复杂度为0(lengthA + lengthB)

 

本算法的另外一种思路,不依靠前面已经定义好,能拿来就用的函数,使用指针进行比较,赋值

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

 1 //二、合并线性表AB,AB的元素按值非递减有序的排列,要把A和B归并为一个新表C,且C的元素依然是按照值非递减的有序排列 2 void MergeList(SqList LA, SqList LB, SqList *LC) 3 { 4     //仍是先构造表C,不用下标,只能使用指针来操做 5     LC->listsize = LA.length + LB.length; 6     LC->length = LA.length + LB.length; 7     int *c = (int *)malloc((LC->listsize) * sizeof(int)); 8     int *a = LA.elem; 9     int *b = LB.elem;10     int *lastA = LA.elem + (LA.length - 1) * sizeof(int);11     int *lastB = LB.elem + (LB.length - 1) * sizeof(int);12     LC->elem = c;13     if (!LC->elem)14     {15         puts("c表构建失败!");16         exit(-1);17     }18     while (a <= lastA && b <= lastB)19     {20         if (*a <= *b)21         {22             *c++ = *a++;//从右到左运算,先计算*c = *a,后a++,c++23         }24         else25         {26             *c++ = *b++;27         }28     }29     while (a <= lastA)30     {31         *c++ = *a++;32     }33     while (b <= lastB)34     {35         *c++ = *b++;36     }37 }

动态分配的顺序线性表的十五种操做—C语言实现_动态_02

一、时间复杂度仍是0(lengthA + lengthB)

二、这里发现,当线性表的元素无序的时候,进行插入操做的时间复杂度比有序的时候的时间复杂度要大的多。

由于,有序的线性表AB,好比依次递增(都不相等),则比较AB元素大小时,不用把B的每个元素都和A比较!由于能够保证前面的元素确定是小于后面的。这样大大节省了运行时间!

三、还有发现若是是两表归并到新表里,那么新表开始就是空的,只须要依次插入便可(换句话说就是依次赋值便可),不用移动元素,而若是是A归并到B里(反之亦然),那么保持有序的话,就须要B的元素时不时的移动,耽误时间。

故,当使用线性表表示数组或者集合等等吧,进行操做的时候,最好是先给表排序,或者有归并,则归并到新的空表。

 

到此,关于线性表里的顺序表的概念和经常使用算法就算分析完毕,常常用的操做的是初始化,销毁,清空,判空,定位,插入,删除,遍历,前驱,后继,赋值,获得元素,求长度,接下来分析的是常常用到的链表。