顺序表的特点
- 物理存储上元素空间连续：顺序表在内存中占据一块连续的内存空间，便于通过下标快速访问元素。
- 随机访问：由于元素连续存储，顺序表支持根据下标直接访问任意位置的元素，时间复杂度为O(1)。
- 插入和删除操作可能涉及元素移动：在顺序表中插入或删除元素，可能需要移动大量元素以保证元素的连续性，导致操作效率较低。
顺序表的缺点：
- 空间利用率不高：顺序表需要提前分配固定大小的内存空间，如果数据量较小，可能导致空间浪费；如果数据量较大，可能导致内存不足。
- 扩容操作复杂：当顺序表已满需要扩容时，需要重新分配内存空间并将原数据复制到新空间，操作复杂且耗时。
顺序表总结：遍历快，插入慢
链表的特点
- 物理存储上元素空间不连续：链表中的元素可以分散存储在内存的任意位置，通过指针或引用连接。
- 插入和删除操作高效：在链表中插入或删除元素只需修改指针，无需移动大量元素，因此操作效率较高。
- 动态分配内存：链表可以根据需要动态分配内存空间，空间利用率较高。
链表的缺点：
- 访问元素效率低：链表不支持随机访问，只能通过从头节点开始遍历的方式访问元素，时间复杂度较高。
- 需要额外的空间存储指针或引用：链表中的每个节点除了存储数据外，还需要存储指向下一个节点的指针或引用，增加了空间开销。
链表总结：遍历慢，插入快
PS:链表在插入元素的时候一定要先链接后断开。
顺序表例子
①先创建一个自定义类型
//指的是顺序表中的元素的数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造记录顺序表SequenceList各项参数(顺序表的首地址 + 顺序表的容量 + 顺序表中最后有效元素的下标)的结构体
typedef struct SequenceList
{
DataType_t * Addr; //记录顺序表首地址
unsigned int Size; //记录顺序表的容量
int Last; //顺序表中最后元素的下标
}SeqList_t;
②创建顺序表并对顺序表进行初始化
SeqList_t * SeqList_Create(unsigned int size)
{
//1.利用calloc为顺序表的管理结构体申请一块堆内存
SeqList_t *Manager = (SeqList_t *)calloc(1,sizeof(Manager));
if(NULL == Manager)
{
perror("calloc memory for manager is failed");
exit(-1); //程序异常终止
}
//2.利用calloc为所有元素申请堆内存
Manager->Addr = (DataType_t *)calloc(size,sizeof(DataType_t));
if (NULL == Manager->Addr)
{
perror("calloc memory for element is failed");
free(Manager);
exit(-1); //程序异常终止
}
//3.对管理顺序表的结构体进行初始化（元素容量 + 最后元素下标）
Manager->Size = size; //对顺序表中的容量进行初始化
Manager->Last = -1; //由于顺序表为空，则最后元素下标初值为-1
return Manager;
}
③判断顺序表是否已满
bool SeqList_IsFull(SeqList_t *Manager)
{
return (Manager->Last + 1 == Manager->Size) ? true : false;
}
④向顺序表的尾部加入元素
bool SeqList_TailAdd(SeqList_t *Manager, DataType_t Data)
{
//1.判断顺序表是否已满
if ( SeqList_IsFull(Manager) )
{
printf("SequenceList is Full!\n");
return false;
}
//2.如果顺序表有空闲空间，则把新元素添加到顺序表尾部
Manager->Addr[++Manager->Last] = Data;
return true;
}
⑤向顺序表的头部加入元素
bool SeqList_HeadAdd(SeqList_t *Manager, DataType_t Data)
{
//1.判断顺序表是否已满
if ( SeqList_IsFull(Manager) )
{
printf("SequenceList is Full!\n");
return false;
}
//2.如果顺序表有空闲空间，则需要把顺序表所有元素向后移动1个单位
for (int i = Manager->Last;i >= 0;i--)
{
Manager->Addr[i+1] = Manager->Addr[i];
}
//3把新元素添加到顺序表的头部,并且更新管理结构体中的元素下标+1
Manager->Addr[0] = Data;
Manager->Last++;
return true;
}
⑥判断顺序表是否已满
bool SeqList_IsEmpty(SeqList_t *Manager)
{
return (-1 == Manager->Last) ? true : false;
}
⑦删除顺序表的元素
bool SeqList_Del(SeqList_t *Manager,DataType_t DestVal)
{
int temp = -1; //记录要删除的元素的下标
//1.判断顺序表是否为空
if ( SeqList_IsEmpty(Manager) )
{
printf("SequenceList is Empty!\n");
return false;
}
//2.此时需要查找目标值是否在顺序表中
for (int i = 0; i <= Manager->Last; ++i)
{
//如果目标值和顺序表中元素的值相同
if (DestVal == Manager->Addr[i])
{
temp = i; //把目标元素的下标备份到变量temp中
break;
}
}
//3.如果顺序表没有目标值的元素则直接终止函数
if (-1 == temp)
{
printf("destval [%d] is not found\n",DestVal);
return false;
}
//4.如果找到了目标元素，则直接把该元素的后继元素向前移动一个单位
for (int i = temp ; i < Manager->Last ; ++i)
{
Manager->Addr[i] = Manager->Addr[i+1];
}
//5.由于删除了一个元素，则需要让顺序表的有效元素下标-1
Manager->Last--;
return true;
}
⑧遍历顺序表的元素
void SeqList_Print(SeqList_t *Manager)
{
for (int i = 0; i <= Manager->Last; ++i)
{
printf("Element[%d] = %d\n",i,Manager->Addr[i]);
}
}
int SeqList_Remove(*L,int p)
{
//判断顺序表的地址是否有效
if(NULL == L)
{
return 0;
}
int e = 0; //变量e，记录待删除元素的值
//把待删除元素的值备份到变量e中
e = L[p];
//把待删除元素的后继元素向前移动一个单位
for (int i = p; i < length; ++i)
{
L[i] = L[i+1];
}
return 1;
}
⑨递增排序
void SeqList_Insert(SeqList *L,int x)
{
int temp = -1; //记录待插入元素的下标
//遍历顺序表，找到插入位置，比较元素
for (int i = 0; i <= last; ++i)
{
if (x < L[i])
{
temp = i;
break;
}
}
if( -1 == temp)
{
L[last+1] = x;
return;
}
//把待插入位置的后继元素向后移动
for (int i = last; i >= temp; i--)
{
L[i+1] = L[i];
}
L[temp] = x;
}
int main(int argc, char const *argv[])
{
//1.创建顺序表
SeqList_t * Manager = SeqList_Create(10);
//2.向顺序表中的尾部插入新元素
SeqList_TailAdd(Manager,5);
SeqList_TailAdd(Manager,2);
SeqList_TailAdd(Manager,1);
SeqList_TailAdd(Manager,4);
SeqList_TailAdd(Manager,6);
//3.遍历顺序表
SeqList_Print(Manager); // -- 5 2 1 4 6
printf("\n");
//4.向顺序表中的头部插入新元素
SeqList_HeadAdd(Manager,9);
SeqList_HeadAdd(Manager,7);
SeqList_HeadAdd(Manager,8);
SeqList_HeadAdd(Manager,0);
SeqList_HeadAdd(Manager,10);
//5.遍历顺序表
SeqList_Print(Manager); // --10 0 8 7 9 5 2 1 4 6
printf("\n");
//6.删除顺序表的元素
SeqList_Del(Manager,20);
SeqList_Del(Manager,5);
SeqList_Del(Manager,10);
SeqList_Del(Manager,0);
SeqList_Del(Manager,30);
//7.遍历顺序表
SeqList_Print(Manager); // --8 7 9 2 1 4 6
printf("\n");
return 0;
}
链表例子
①我们通过c语言去构建一个链表结构
//由于不确定存储的数据类型，我们自定义一个数据类型
typedef int DataType_t;
//构造链表的结点，链表中所有的结点的数据类型应该是相同的
typedef struct LinkedList
{
DataType_t data;//结点指向的数据
stryct LinkedList *next;//指针域
}LList_t;
②创建一个空链表，链表应该有一个头结点，对链表进行初始化
LList_t * LList_Create(void)
{
//创建一个头结点与申请内存（头结点指向第一个结点）
LList_t *Head = (LList_t *)calloc(1,sizeof(LList_t));
if (NULL == Head)
{
perror("申请头结点堆内存错误\n");
exit(-1);
}
//对头结点进行初始化，
Head->next = NULL;
//把头结点的地址返回
return Head;
}
③创建一个新结点并初始化
LList_t * LList_NewNode(DataType_t data)
{
//1.创建一个新结点并对新结点申请内存
LList_t *New = (LList_t *)calloc(1,sizeof(LList_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
//2.对新结点的数据域和指针域进行初始化
New->data = data;
New->next = NULL;
return New;
}
④链表结构头部插入新的元素
bool LList_HeadInsert(LList_t *Head,DataType_t data)
{
//1.创建新的结点，并对新结点进行初始化
LList_t *New = LList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node\n");
return false;
}
//2.判断链表是否为空，如果为空，则直接插入即可
if (NULL == Head->next)
{
Head->next = New;
return true;
}
//3.如果链表为非空，则把新结点插入到链表的头部
New->next = Head->next;
Head->next = New;
return true;
}
⑤遍历
void LList_Print(LList_t *Head)
{
//对链表的头文件的地址进行备份
LList_t *Phead = Head;
//首结点
while(Phead->next)
{
//把头的直接后继作为新的头结点
Phead = Phead->next;
//输出头结点的直接后继的数据域
printf("data = %d\n",Phead->data);
}
}