作为学习数据结构最开始接触的内容，回顾总结时不免感慨万分
首先先明确要用顺序表解决什么问题，或者说初学者刚接触要能通过顺序表实现什么
1.建立顺序表并实现插入、删除、查找
2.删除顺序表中重复元素
3.创造新的顺序表存放合并后的顺序表（交集和并集）
4.通过某种判断方法比较两个顺序表大小
开始前的知识点补充：引用类型
#include
void main()
{
int i = 5;
int& j = i;
j = 7;
printf("%d %d", i, j);
} 输出结果均为7
引用类型和实参共用同一个地址，可以像传递指针一样形参该改变实参也改变。
不同点在于引用类型作为形参，内存中没有产生实参的副本，他直接对实参 *** 作，而一般的变量作为参数形参实参占不同的储存单元，可以理解为他是用来给一个对象提供替代的名字
1.题目内容： 编程实现顺序表的下列基本 *** 作函数。
(1) void InitList(SqList & L) //建立空的顺序表
(2) void ListInsert(SqList & L, int i, ElemType e) //在顺序表中第i个位置插入元素函数e
(3) void ListDelete(SqList & L, int i, ElemType & e) //删除顺序表L的第i个数据元素，并用e返回其值。
(4) void PrintList(SqList L) // 输出顺序表
(5) int Locate(SqList L, ElemType e) //若顺序表L中存在数据元素e，则返回e在顺序表L中第一次出现的位序;否则返回0
输入格式： 四行数据，第一行的整数表示要建立的顺序表的元素个数，
第二行整数表示依次输入的数据，两个整数之间以空格分隔，
第三行的整数表示要删除数的位置，第四行表示要查找的数。
输出格式： 三行数据，第一行表示程序执行后顺序表的数据元素(依次从表头至表尾), 第
二行整数表示已删除的数，第三行表示要查找的数的位置或者没有找到。
#include
#include
#define OVERFLOW -2
#define ERROR 0
#define INIT_LIST_SIZE 6 //初始分配量
#define INCREASELIST 3 //分配增量
typedef int ElemType; //顺序表中存放的是整数，用ElemType定义int类型，这样以后表达保持代码的统一性
typedef struct{
ElemType *elem; //存储空间基址
ElemType length; //当前长度
ElemType listsize; //当前分配的存储容量
}SqList;//结构类型名称，注意以后会出现*指针类型，这里未用到
int main()
{
void InitList(SqList &L);//用引用类型因为要建立顺序表也就是说要改变顺序表
void ListInsert(SqList &L,int i,ElemType e);//这里e没有用引用类型，因为他只需要传值不需要返回
void ListDelete(SqList &L,int i,ElemType &e);//这里用引用类型因为e要储存删除的元素并返回，可以理解为
//传回来时改变了e的值，所以为了获取这个值，用引用类型
void PrintList(SqList L);
int Locate(SqList L,ElemType e);
//函数声明
int n, i;
int e1,e2,t;//e1是已删除的数字，e2是要查找的数,t是要删除元素的位置(位置序号不是下标！)
ElemType x;//声明一个ElemType的数x
SqList K;//初始化顺序表K
InitList(K);//顺序表初始化
printf("请输入顺序表的元素个数：\n");
scanf("%d",&n);
printf("请输入%d个元素：\n",n);
for(i=0;iL.length+1)//注意传入的i是为序不是下标，所有从1开始到length+1结束
{
printf("Insertion location Error!");
return;//什么也不返回，直接返回主调函数
}
if(L.length>=L.listsize)//如果表长>=其所占空间的长度，那么就要为其分配新的空间，让他还有空间可以存元素
{
newbase=(ElemType*)realloc(L.elem,(L.listsize+INCREASELIST)*sizeof(ElemType));
//realloc函数分配一个listsize+increaselist大小的新内存，并把原来L.base里面数据复制过去
if(!newbase) exit(OVERFLOW);//没分配到就exit
L.elem=newbase;//再令L.base等于newbase，这样相当于重新搞了一个新空间新地址，把原来地址转变成新的地址
L.listsize=L.listsize+INCREASELIST;//分配结束后顺序表总大小相比原来增加了increaselist大小空间
}
q=&(L.elem[i-1]);//q取要插入的位置，注意i是为序，不是下标，对应的第i个下标是i-1
for(p=&(L.elem[L.length-1]);p>=q;--p)//p取表尾
*(p+1)=*p;//从表尾开始移动，表尾元素到表尾后面一个位置，前面依次向后面移动一位
*q=e;//最后第i个与第i+1个元素值都一样，把第i个元素赋值为e
L.length++;//增加了一个元素，表长要+1
}
void ListDelete(SqList &L,int i,ElemType &e)//删除顺序表L的第i个数据元素，并用e返回其值
{
ElemType* p = NULL;
ElemType* q = NULL;
if(i<1||i>L.length)
printf("删除位置错误\n");
p=&L.elem[i-1];//p取要删除的元素位置
q=L.elem+L.length-1;//q取表尾元素位置
e=L.elem[i-1];//先储存要删除元素的值
for(;p 注意删除循环次数要比插入少一次！！！for循环判断时等号两个一个没有一个有
2.题目内容： 已知顺序表中的元素依值递增有序排列，要求将x插入到顺序表的适当位置上，
使得插入 *** 作后的顺序表仍保持有序性。
输入格式： 三行数据，第一行的整数表示要建立的顺序表的元素个数，
第二行整数表示依次输入的数据，两个整数之间以空格分隔，
第三行的整数表示要插入的数x。
输出格式： 一行整数，从表头开始依次显示插入 *** 作后顺序表的数据元素。
主要函数如下
void SortListInsert(SqList& L, ElemType e)
{
ElemType* p = NULL;
ElemType* q = NULL;
ElemType* newbase;
int i = 0;
if (L.length >= L.listsize) {
newbase = (ElemType*)realloc(L.elem, (L.listsize +INCREASELIST) * sizeof(ElemType));
L.elem = newbase;
L.listsize = L.listsize +INCREASELIST;
}
for (i = 0; i < L.listsize; i++)
{
if (e <= L.elem[0] && e < L.elem[1])//之所以这样还附加一个e= q; p--) {
*(p + 1) = *p;
}
*q = e;
L.length++;
break;//因为就插入一个元素，完成后跳出结束就行
}
else if (e >= L.elem[i] && e < L.elem[i + 1])//刚刚例子2 2 2 3 4 5，就进入这里，插在23之间
//注意前取等后不取等
{
p = L.elem + L.length - 1;
q = &(L.elem[i + 1]);//插在i+1处
for (; p >= q; p--) {
*(p + 1) = *p;
}
*q = e;
L.length++;
break;
}
else if (e >= L.elem[L.length - 1])//如果是2 2 2 2 你插入2也不用担心，你前面两个条件进不去
//这个就相当于插队尾了
{
*(L.elem + L.length) = e;
L.length++;
break;
}
}
} 3.题目内容： 已知顺序表中的元素依值递增有序排列，
要求删除表中所有值相同的多余元素（使得 *** 作后的顺序表中所有元素的值均不相同）
输入样例： 2 5 5 8 11 20 20 20
输出样例： 2 5 8 11 20
主要函数如下：
void deletelist2(Sqlist& L, Elemtype& e)
{
ElemType* p = NULL;
ElemType *q = NULL;
int i;
for (i = 0; i < L.length-1; i++)
{
if (L.elem[i] == L.elem[i + 1])//如果前后两个元素相等，将i+1后面所有元素向前移动一位，把i+1元素覆盖
//覆盖i也可以，不过会多一点运算
{
*p = &L.elem[i + 1];
q = L.elem + L.length - 1;
for (; p < q; p++) {
*p = *(p + 1);
}
i--;//原来移动前的第i位还是第i位，不过i+1位变了，再第i位和现在的第i+1位比
L.length--;
}
}
}4.题目内容： 假设以两个元素依值递增有序排列的顺序表A和B
分别表示两个集合（同一表中的元素值各不相同），
现要求另辟空间构成一个顺序表C，其元素为A和B元素的交集，
且表C中的元素也是依值递增有序排列。
输入样例：
5
2 5 8 11 20
6
3 8 9 11 15 20
输出样例： 8 11 20
4'大致如上，不过取并集，也就是输出2 3 5 8 9 11 15 20
#include
#include
#define INIT_LIST_SIZE 6
#define LISTINCREMENT 3
#define OVERFLOW -2
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
int main()
{
void InitList(SqList &L);//建立空的顺序表
void ListInsert(SqList &L,int i,ElemType e);//在顺序表中第i个位置插入元素函数e
void PrintList(SqList L);
void ContactList(SqList La,SqList Lb,SqList &Lc);//求线性表A和B的交集
SqList La,Lb,Lc;
ElemType x;
int n,i;
InitList(La);
InitList(Lb);
printf("请输入顺序表A的元素个数：\n");
scanf("%d",&n);
printf("请输入顺序表A中的元素：\n");
for(i=0;iL.length+1)
printf("Insertion Location Error!\n");
if(L.length>=L.listsize)
{
newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
L.elem=newbase;
L.listsize = L.listsize + LISTINCREMENT;
}
q=&L.elem[i-1];//q指向要插入的位置
for(p=L.elem+L.length-1;p>=q;p--)
*(p+1)=*p;
*q=e;
L.length++;
}
void PrintList(SqList L)
{
int i;
for(i=0;i=Lb.length)
Lc.listsize=Lb.length;
else
Lc.listsize=La.length;
Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));
if(!Lc.elem) exit(OVERFLOW);
Lc.length=0;
pc=Lc.elem;
while(pa<=La.elem+La.length-1&&pb<=Lb.elem+Lb.length-1)
{
if(*pa<*pb)
pa++;
else if(*pa>*pb)
pb++;
else
{
*pc=*pa;
pa++;
pb++;
pc++;
Lc.length++;
}
}
}*/
void ContactList(SqList La, SqList Lb, SqList& Lc)//取并集
{
ElemType* p = NULL;
ElemType* q = NULL;
ElemType* r = NULL;
p = La.elem;
q = Lb.elem;
Lc .listsize = La.length + Lb.length;
Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));
if (!Lc.elem) exit(OVERFLOW);
Lc.length = 0;
r = Lc.elem;
while ((p <= La.elem + La.length - 1 )&& (q <= Lb.elem + Lb.length - 1))//若都未指向空
{
if (*p < *q) {
*r++ = *p++;//*r=*q;r++;q++
Lc.length++;
}
else if (*p > *q) {
*r++ = *q++;
Lc.length++;
}
else {
*r++ = *p++;
q++;
Lc.length++;
}
}
while (p <= La.elem + La.length-1)//如果p没指空，L2空了，把L1剩下的全插入L3
{
*r++ = *p++;
Lc.length++;
}
while (q <= Lb.elem + Lb.length-1)
{
*r++ = *q++;
Lc.length++;
}
} 5.题目内容： 设A=(a1,…,am)和B=(b1,…,bn)均为顺序表，
A’和B’分别为A和B中除去最大共同前缀后的子表，
若A’＝B’＝空表，则A=B;若A’=空表，而B’!=空表，
或者两者都不为空表，且A’的首元小于B’的首元，
则A
#include
#include
#define INIT_LIST_SIZE 6
#define LISTINCREMENT 3
#define OVERFLOW -2
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
int main()
{
void InitList(SqList &L);
void ListInsert(SqList &L,int i,ElemType e);
int CompareList(SqList L1,SqList L2);
int a,b,i,x;
SqList L1,L2;
InitList(L1);
InitList(L2);
printf("请输入顺序表A的元素个数：\n");
scanf("%d",&a);
printf("请输入顺序表A的所有元素：\n");
for(i=0;ib");
if (k == -1)
printf("aL.length+1)
printf("Insertion Location Error!\n");
if(L.length>=L.listsize)
{
newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
L.elem = newbase;
L.listsize = L.listsize + LISTINCREMENT;
}
q=&L.elem[i-1];
for(p=L.elem+L.length-1;p>=q;p--)
*(p+1)=*p;
*q=e;
L.length++;
}
int CompareList(SqList L1, SqList L2)
{
ElemType* p = NULL;
ElemType* q = NULL;
p = L1.elem;
q = L2.elem;
while (p < L1.elem + L1.length && q < L2.elem + L2.length)//pq都没指空
{
if (*p < *q)//p在该位置的值小于q，A就小于B
return -1;
else if (*p > *q)
return 1;
else//如果相等比较下面一个位置的元素的值
{
p++;
q++;
}
}
if (p == L1.elem + L1.length && q == L2.elem + L2.length)//两个同时指空，则A=B
return 0;
else if (p == L1.elem + L1.length)//如果p空了，此时q没空，A 以上是5个常见的情况例题
掌握顺序表在于理解 *** 作的意义，比如插入删除从什么开始，进行多少次，位序和下标的关系，再就是注意切入方法，当然简单的方法需要更高的思维层次，从最基础做起，慢慢领悟才是常态
顺序表特点是利用元素的存储位置表示线性表中相邻元素的前后关系（逻辑结构与存储结构一致）
顺序表优点是随机存取，存储密度大，但是插入删除需移动大量元素，浪费存储空间，而且属于静态存储形式，元素个数不能自由扩充，下面将引入的链表刚好和其互补
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）