CC++ 数据结构 顺序存储代码总结&&算法练习

数据结构-线性表-顺序表

1.顺序表——用顺序存储的方式实现

2.顺序表的定义（静态分配）：

#define MaxSize 10 //定义最大长度 typedef struct{ ElemType data[MaxSize]; //静态数组存放元素 int length; //顺序表当前长度 }SqList; //顺序表的类型定义

初始化一个顺序表——实际代码：

#include <stdio.h> #define MaxSize 10 typedef struct{ int data[MaxSize]; int length; }SqList; void InitList(SqList &L){ for(int i=0;i<MaxSize;i++) L.data[i] = 0; L.length = 0; } int main(){ SqList L; InitList(L); /* ......相关操作 */ return 0; }

注意问题：

1.void InitList(SqList &L) 中的“&”是C++里面的内容，文件后缀名需要改成.cpp,使用.c会报错 2. void InitList(SqList &L){ for(int i=0;i<MaxSize;i++) L.data[i] = 0; //设置默认值 L.length = 0; //不可省 } 设置默认值这一步最好写上，因为内存中可能遗留有“脏数据”。

3.顺序表的定义（动态分配）：

#define InitSize 10 //初始长度 typedef struct{ ElemType *data; //动态分配数组的指针 int MaxSize; //顺序表的最大宽度 int length; //当前的长度 }SeqList; key:动态申请和释放内存空间 c ————mallo | free 函数 L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize); 前一个ElemType：强制类型转换 后一个ELemType: 计算该数据类型的单个所占字节（4B,8B,16B）

实际代码：

#include <stdlib.h> #define InitSize 10 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 IncreaseSzie(SeqList &L, int len){ int *p = L.data; L.data = (int*)malloc((L.MaxSize+len)*sizeof(int)); for(int i=0;i<L.length;i++){ L.data[i] = p[i]; } L.MaxSize = L.MaxSize+len; free(p); } int main(){ SeqList L; InitList(L); /* .......相关操作 */ IncreaseSzie(L,5); return 0; }

注意问题：

1.#include <stdlib.h> 要使用malloc | free 函数必须引入该头文件 2.申请了新的空间后，以前的空间记得free()掉

4.顺序表的插入

定义：ListInsert(&L,i,e)，在表L中的第i个位置插入指定元素e

#include <stdio.h> #define MaxSize 10 typedef struct{ int data[MaxSize]; int length; }SqList; void ListInsert(SqList &L,int i,int e){ if(i<1||i>L.length+1) return false; if(L.length>=MaxSize) return false; for(int j=L.length;j>=i;j--){ L.data[j] = L.data[j-1]; } L.data[i-1] = e; L.length++; } int main(){ SqList L; InitList(L); /* .......相关操作 */ ListInsert(L,3,3); return 0; }

注意问题：

1.为了函数的健壮性和高可用性，注意做好相应的判断： if(i<1||i>L.length+1) return false; if(L.length>=MaxSize) return false; 2.时间复杂度： 最好：循环0次，O(1) 最坏：循环n次，O(n) 平均: 概率相同p=1/(n+1),平均循环次数=np+(n-1)p+(n-2)p+......+1p = [(n(n+1))/2]*[1/(n+1)] = n/2, O(n)

5.顺序表的删除

bool ListDelete(SqList &L,int i,int &e){ if(i<1||i>L.length) return false; e = L.data[i-1]; for(int j=i;j<L.length;j++) L.data[j-1] = L.data[j]; L.length--; return true; } int main(){ ...... int e = -1; if(ListDelete(L,3,e)) printf("已删除\n"); else printf("Error\n"); ...... }

注意问题：

1.e这个值要带回来，所以函数调用的时候要加“&”，引用类型 2.时间复杂度： 最好：O(1) 最坏：O(n) 平均：O(n/2) = O(n)

6.顺序表按位查找

定义：GetElem(L,I): 获取表L中的第i个位置的元素

时间复杂度：O（1）

#define MaxSize 10 typedef struct{ ElemType data[MaxSzie]; int length; } ElemType GetElem(SqList L,int i){ return L.data[i-1] } #define InitSize 10 //初始长度 typedef struct{ ElemType *data; //动态分配数组的指针 int MaxSize; //顺序表的最大宽度 int length; //当前的长度 }SeqList; ElemType GetElem(SqList L,int i){ return L.data[i-1] }

7.顺序表按值查找

#define InitSize 10 //初始长度 typedef struct{ ElemType *data; //动态分配数组的指针 int MaxSize; //顺序表的最大宽度 int length; //当前的长度 }SeqList; int LocateElem(SeqList L,int e){ for(int i=0;i<L.length;i++) if(L.data[i]==e) return 1; return 0 }

注意问题：

1.如果数组里面的数据元素为结构体，则不能直接用"=="来判断，可以另写一个函数，判断里面的每一个成员是否相等 2.时间复杂度： 最好：O(1) 最坏:O(n) 平均：O(n)

8.代码示例

#include <stdio.h> #include<string.h> #define MaxSize 10 typedef struct{ int data[MaxSize]; int length; }SqList; //初始化顺序表 void InitList(SqList &L){ for(int i=0;i<MaxSize;i++) L.data[i] = 0; L.length = 0; } //给顺序表赋值 void AddNumList(SqList &L,int *arr,int arr_length){ if(arr_length>MaxSize) printf("所给的数组范围已超%d\t个",MaxSize); for(int i=0;i<arr_length;i++,*arr++){ L.data[i] = *arr; L.length +=1; } printf("\n"); } //输出顺序表 void PrintList(SqList L){ for(int i=0;i<L.length;i++) printf("%d ",L.data[i]); printf("\n"); } //顺训表的插入 bool ListInsert(SqList &L,int i,int e){ if(i<1||i>L.length+1) return false; if(L.length>=MaxSize) return false; for(int j=L.length;j>=i;j--) L.data[j] = L.data[j-1]; L.data[i-1] = e; L.length++; } //顺序表的删除 void ListDelete(SqList &L,int i,int &e){ if(i<1||i>L.length) printf("error"); e = L.data[i-1]; for(int j=i;j<L.length;j++) L.data[j-1] = L.data[j]; L.length--; } //顺序表按位查找 int GetElem(SqList L,int i){ return L.data[i-1]; } //顺序表按值查找 int LocateElem(SqList L,int e){ for(int i=0;i<L.length;i++) if(L.data[i]==e) return i+1; return 0; } int main(){ SqList L; int arr[] = {12,4,5,9,98,34,26}; int arr_length = sizeof(arr)/sizeof(int); printf("数组arr的数据为:\n"); for(int i=0;i<(sizeof(arr)/sizeof(int));i++) printf("%d ",arr[i]); printf("\n正在初始化顺序表data\n"); InitList(L); printf("\n初始化完成，此时表长为: %d\n",L.length); printf("\n正在给顺序表赋值\n"); AddNumList(L,arr,arr_length); printf("\nok,此时表长为：%d\n",L.length); printf("表中元素为---\n"); PrintList(L); int i=-1; int e=-1; printf("\n插入操作开始-------\n"); printf("\n请输入插入位置和插入元素\n"); scanf("%d %d",&i,&e); ListInsert(L,i,e); printf("\n插入后表中元素为---\n"); PrintList(L); printf("\n表长为：%d\n",L.length); int m=-1; int n=-1; printf("\n删除操作开始-------\n"); printf("\n请输入删除位置\n"); scanf("%d",&m); ListDelete(L,m,n); printf("\n删除后表中元素为---\n"); PrintList(L); printf("\n表长为：%d\n",L.length); printf("\n输入你想查找的数\n"); int t=-1; scanf("%d",&t); int q = LocateElem(L,t); printf("位置在第%d个\n",q); return 0; }

顺序表习题练习

1.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除的元素的值，空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行

//由于自己编写的，与课本标准有差异，但是效果无差别 void ListDeleteMin(SqList &L,int &min){ if(L.length==0) printf("error,array is null"); min = L.data[0]; int t = 0; for(int i=0;i<L.length;i++){ if(L.data[i]<min){ min = L.data[i]; t = i; } } L.data[t] = L.data[L.length-1]; L.length--; }

注意点：

L.data[t] = L.data[L.length-1]; 这段代码将顺序表最后面的元素赋值给了最小值的位置，执行这段代码之后，最后面的值为null了，并不会遗留有原数据。 猜测原因：可能是指针级的操作导致的。

2.设计一个高效算法，将顺序表L的所以元素逆置，要求算法的空间复杂度为O(1)

//算法原地工作是指算法所需的辅助空间为常量，即O(1) void ListReverse(SqList &L){ int temp; for(int i=0;i<L.length/2;i++){ temp = L.data[i]; L.data[i] = L.data[L.length-1-i]; L.data[L.length-1-i] = temp; } }

注意：

上面的函数中只有两个辅助变量temp,i;所需要的空间大小为sizeof(int)*2; 如果辅助变量的个数涉及到与问题规模n有关，那么它的空间复杂度就不在是O(1)

3.对于长度为n的顺序表L,编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法。该算法删除线性表中的所以值为x的数据元素。

问题分析：

1.由题可知，需要把整个顺序表遍历一遍（L++），结合时间复杂度要求为O(n),那么可以这样理解，设计的算法不能存在嵌套循环，可以用多个并行循环。 2.空间复杂度O(1),即辅助变量个数与问题规模n无关，最直接的，不要使用递归。 void ListDeleteMultipleValueOfX(SqList &L,int x){ int k=0; for(int i=0;i<L.length;i++){ if(L.data[i]!=x){ L.data[k]=L.data[i]; k++; } } L.length = k; } //用k记录顺序表L中不等于x的元素个数，边扫描L边统计K,并将不等于x的元素向前移动k个单位，最后修改L的长度。

4.从有序顺序表中删除其值在给定值s和t之间（要求s<t）的所以元素，如果s或者t不合理或者顺序表为空，则显示错误信息并退出运行。

void PrintfStoT(SqList &L,int s,int t){ int i,j; if(L.length==0||s>=t) printf("error"); for(i=0;i<L.length&&L.data[i]<s;i++);//寻找到大于等于s值的前一个元素 if(i>=L.length) printf("i已经超范围了，或者已经到达尾部，后面不存在%d元素\n",t); for(j=i;j<L.length&&L.data[j]<=t;j++); //寻找大于t的第一个元素 for(;j<L.length;i++,j++) L.data[i] = L.data[j]; L.length = i; }

注意问题：

1.对于更多的思考判读可以做部分省略，比如s,t语言是否在L里面，根据题意，对于异常条件的判断，做出题中要求的即可 2.算法思想：先寻找大于等于s的第一个元素（第一个要删除的元素），然后寻找值大于t的第一个元素，要将这段元素删除，只需要直接将后面的元素前移即可。 3.可能疑问点： 3.1 for(i=0;i<L.length&&L.data[i]<s;i++);//寻找到大于等于s值的第一个元素 这条语句寻找大于等于s值的第一个元素的为什么不是L.data[i]>=s？这样理解似乎更符合人们 的逻辑啊？ 答：这里面涉及到c语言for()循环执行过程的问题。c语言for()循环的执行过程如下： ----------------------------------------------------------------------- for (表达式1; 表达式2; 表达式3) { 语句; } 下面来看看它的执行过程： 1.求解表达式1。 2.求解表达式2。若其值为真，则执行 for 语句中指定的内嵌语句，然后执行第3步；若表达式2 值为假，则结束循环，转到第5步。 3.求解表达式3。 4.转回上面第2步继续执行。 5.循环结束，执行 for 语句下面的语句。 从这个执行过程中可以看出，“表达式1”只执行一次，循环是在“表达式2”“表达式3”和“内嵌语 句”之间进行的。 ---------------------------------------------------------------------- 由此可想，执行完L.data[i]<s后，跳出循环，但是i会自动加一，所以就会跳到s的下标去。 我们可以做一个测验： ---------------------------------------------------------------------- #include <stdio.h> int main(){ int a[10]={1,2,3,4,5,6,7,8,9}; int i; for(i=0;i<10&&a[i]<3;i++){ printf("a:%d,i:%d\n",a[i],i); } printf("i:%d\n",i); return 0; } 执行结果： a:1,i:0 a:2,i:1 i:2 3.2 for(j=i;j<L.length&&L.data[j]<=t;j++); //寻找大于t的第一个元素 与上个问题同问同解

5.从有序顺序表中删除其值在给定值s和t之间（包括s,t,要求s<t）的所以元素，如果s或者t不合理或者顺序表为空，则显示错误信息并退出运行。

void Del_s_t(SqList &L,int s,int t){ int i,k=0; if(L.length==0||s>=t) printf("error"); for(i=0;i<L.length;i++){ if(L.data[i]>=s&&L.data[i]<=t) k++; else L.data[i-k]=L.data[i]; } L.length-=k; }

6.从有序表中删除所有其值重复的元素，使表中的所有元素的值均不同。

​ 思考：有序表相同元素一定连续

void Del_Same(SqList &L){ if(L.length==0) printf("Error"); int i,j; for(i=0,j=1;j<L.length;j++){ if(L.data[i]!=L.data[j]) L.data[++i]=L.data[j]; } L.length=i+1; }

7.将两个有序的顺序表合并为一个新的顺序表，并由函数返回结果顺序表

本题算法方法非常经典

bool Merge(SeqList A,SeqList B,SeqList &c){ if(A.Length+B.Length>C.MaxSize) return false; int i=0,j=0,k=0; while(i<A.length&&j<B.length){ if(A.data[i]<=B.data[j]){ C.data[k++] = A.data[i++]; } else{ C.data[k++] = B.data[j++]; } } while(i<A.length) C.data[k++] = A.data[i++]; while(j<B.length) C.data[k++] = B.data[j++]; C.length = k; return true; }