基本结构
首先我们声明我们所使用的数据类型(也可不做此声明，后续的dataType换成你所用的类型即可)
typedef int dataType;
定义基本数据结构，数组or链表
//数组表示
typedef struct
{
vector val; //vector定义
//或 dataType *val; //指针形式定义
int length;
}Array;
//链表形式
typedef struct node
{
dataType val;
struct node *next;
}Node;
typedef struct
{
Node *head;
int length;
}List;
后续的基本操作中我们也会对两种表示形式分别编写相关代码
线性表的创建(初始化)
由于在数组形式中，用vector定义的val和指针类型的val初始化时会有所区别，这里也分别进行介绍
这里我们用一个已经存有数据的数组去初始化我们的线性表
//L为线性表的引用，num是已有数据的数组，n为num中元素个数，且num中元素位置为0-n-1
//数组表示( vector val; )
void InitArray(Array &L,dataType *num,int n)
{
int i;
L.val.resize(n);
L.length = n;
for(i=0;inext = new Node;
p = p->next;
p->val = num[i];
}
p->next = NULL; //链表的结束
}
线性表的显示
//数组表示
void ShowArray(Array &L)
{
int i;
for(i=0;inext;
while(p)
{
cout << p->val << ' ';
p = p->next;
}
cout << endl;
}
数据插入
//num为插入值,n为插入的位置,由于数组从0开始,实际插入位置为n-1
//数组表示( vector val; )
void InsertData_array(Array &L,dataType num,int n)
{
int i;
L.length++;
L.val.reserve(L.length); //在空间不够时会补足空间
for(i=L.length-1;i>=n;i--)
L.val[i] = L.val[i-1];
L.val[i] = num;
}
//数组表示( dataType *val; )
void InsertData_array(Array &L,dataType num,int n)
{
//必须保证数组有足够的空间,不然会报错
int i;
L.length++;
for(i=L.length-1;i>=n;i--)
L.val[i] = L.val[i-1];
L.val[i] = num;
}
//链表形式
void InsertData_list(List &L,datetype num,int n)
{
int i = 0;
Node *p = L.head;
Node *temp = new Node;
temp->val = num;
L.length++;
while(p->next)
{
i++;
if(i==n)
{
temp->next = p->next;
p->next = temp;
break;
}
p = p->next;
}
if(n == L.length) //如果加在末尾
{
p->next = temp;
temp->next = NULL;
}
}
数据删除
查找指定元素并进行删除第一次出现的该元素,删除成功返回1,为找到该元素删除失败返回0
//数组表示
int DeleteData_array(Array &L,dataType num)
{
int i,j;
for(i=0;inext)
{
if(p->next->val==num)
{
temp = p->next;
p->next = p->next->next;
delete temp;
L.length--;
return 1;
}
p = p->next;
}
return 0;
}
线性表的归并
对于数组表示的线性表来讲,将两个有序线性表归并到其中一个里,需要将其后的部分整体后移,会一定程度地增大时间复杂度,因此我们采取异地归并的策略,即将两个有序线性表归并到另一个线性表中;而对于链表形式做本地归并即可
//注意要保证存放结果的L有充足的空间
//数组表示
void MergeArray(Array &L1,Array &L2,Array &L)
{
int i=0,j=0,k=0;
while(inext && L2.head->next)
{
if(p->next->valnext->val)
{
p = p->next;
}
else
{
temp = L2.head->next;
L2.head->next = L2.head->next->next;
temp->next = p->next;
p->next = temp;
}
}
if(L2.head->next)
{
p->next = L2.head->next;
L2.head->next =NULL;
}
L1.length+=L2.length;
}
Original: https://www.cnblogs.com/Vergissmeinnicht-rj/p/16359495.html
Author: Vergissmeinnicht_z
Title: 数据结构基础——线性表的基本操作
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605137/
转载文章受原作者版权保护。转载请注明原作者出处！