83.【C语言】数据结构之顺序表的尾部插入和删除
目录
3.操作顺序表
2."伪"插入顺序表的元素
分析尾部插入函数SLPushBack
代码示例
SeqList.h
main.c
free(指针)出错的几种可能的原因
3."伪"删除顺序表元素
2.分析尾部删除函数SLPopBack
代码示例
错误检查
两种解决办法
1.判断size是否为负数
2.assert断言size的大小(直接强制终止运行)
承接82.【C语言】数据结构之顺序表的初始化和销毁的3.操作顺序表
3.操作顺序表
2."伪"插入顺序表的元素
四个"伪"插和"伪"删函数
在SeqList.h中再写入:
void SLPushBack(SL* ps,SLDataType x);//尾部插入
void SLPopBack(SL* ps);//尾部删除
void SLPushFront(SL* ps, SLDataType x);//头部插入
void SLPopFront(SL* ps);//头部删除关于命名的问题:在汇编里,push为入栈(在这里理解为插入),pop为出栈(在这里理解为删除),front为头部,back为尾部
分析尾部插入函数SLPushBack
注意事项
1.每插入一个元素,ps->size++
2.空间不够,需要扩容(realloc)(添加一个判断size和capacity的大小的语句,判断realloc的返回值是否为空指针)
代码示例
SeqList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>typedef int SLDataType;//将int重定义为SLDataType
#define INIT_CAPACITY 4
typedef struct Seqlist
{SLDataType* a;//动态顺序表int size;//有效数据的个数int capacity;//空间的容量
}SL;void SLInit(SL* ps);//声明初始化顺序表的函数
void SLDestory(SL* ps);//声明销毁顺序表的函数
void SLPushBack(SL* ps, SLDataType x);//尾部插入
void SLPopBack(SL* ps);//尾部删除
void SLPushFront(SL* ps, SLDataType x);//头部插入
void SLPopFront(SL* ps);//头部删除
void SLPrint(SL* ps);//打印结构main.c
#include "SeqList.h"
//定义测试顺序表的函数
void TestSeqList1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPrint(&s);SLDestory(&s);
}int main()
{TestSeqList1();return 0;
}SeqList.c
#include "SeqList.h"
void SLInit(SL* ps)
{ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL){perror("malloc");return;//错误返回}ps->size = 0;ps->capacity = INIT_CAPACITY;
}void SLPushBack(SL* ps, SLDataType x)
{if (ps->size == ps->capacity)//size>capacity会越界{//扩大2倍较为合适SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2);if (tmp == NULL){perror("realloc");return;//错误返回}ps->capacity *= 2;ps->a = tmp;//新扩容空间的指针赋值给ps->a}ps->a[ps->size++] = x;//写入数据
}void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}
}void SLDestory(SL* ps)
{free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}
如果多添加几行则会出问题
SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPushBack(&s, 6);
free(指针)出错的几种可能的原因
1.没有从头开始释放空间
2.越界访问(下标越界或空间开辟过少)
这里为第2种情况
改为
SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType)*ps->capacity * 2);成功运行
3."伪"删除顺序表元素
2.分析尾部删除函数SLPopBack
代码示例
头部删除,只需要修改有效个数size的大小即可,不需要修改动态内存的数据
main.c改为
#include "SeqList.h"
//定义测试顺序表的函数
void TestSeqList1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPushBack(&s, 6);SLPushBack(&s, 7);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLDestory(&s);
}int main()
{TestSeqList1();return 0;
}SeqList.c写入
void SLPopBack(SL* ps)
{ps->size--;
}这样写 ps->a[ps->size--] = 0; 没有必要
错误检查
其实上方的代码写的有问题!
多次调用SLPopBack函数可能使size为负数
两种解决办法
1.判断size是否为负数
void SLPopBack(SL* ps)
{if (ps->size == 0){return;//错误返回}ps->size--;
}2.assert断言size的大小(直接强制终止运行)
void SLPopBack(SL* ps)
{assert(ps->size > 0);ps->size--;
}运行结果:
注:有关assert的详细介绍在39.【C语言】指针（重难点）（D）
如果设计头部插入SLPushFront函数和头部删除SLPopFront函数,需要移动其他元素使其向后排,执行效率不高
以下来自《计算机科学导论 第四版》的部分内容
