数据结构——实验一·线性表
海~~欢迎来到Tubishu的博客🌸如果你也是一名在校大学生，正在寻找各种变成资源，那么你就来对地方啦🌟
Tubishu是一名计算机本科生，会不定期整理和分享学习中的优质资源，希望能为你的编程之路添砖加瓦⭐🔥
当然，如果你也好的资源推荐，欢迎在评论区分享，让我们共同打造一个丰富的编程资源库！🔥
本文专栏 ➡️ 数据结构
实验目的：
- 掌握线性表的顺序/链接存储结构
- 验证顺序表/链表及其基本操作的实现
- 掌握数据结构及算法的程序实现的基本方法
实验内容：
请选择使用顺序表或链表（单链表或双链表）实现以下操作，要求设计菜单，并根据菜单提示进行操作：
- 插入一个新元素到第i个位置
- 删除第i个位置的元素
- 显示线性表中所有元素的值
- 检索表中第i个元素
- 求表的长度
顺序表操作
实验产出：
1.核心代码：
#include <bits/stdc++.h>
using namespace std;
#define ERROR 0
#define OK 1
#define ListSize 100
typedef char ElemType;
typedef struct
{ ElemType data[ListSize]; // 存放顺序表元素
int length; // 存放顺序表的长度
} SeqList; // 顺序表的类型定义
// 构造一个空的顺序表L//顺序表的初始化
int InitList_Sq (SeqList *&L)
{
L = new SeqList; // 为顺序表分配空间
if(!L) // 存储分配失败
return ERROR; // 初始化失败
L->length=0; // 空表长度为0
return OK; // 初始化成功
}
// 销毁顺序表
void DestroyList_Sq(SeqList *&L)
{
delete L;
L = NULL;
}
// 清空顺序表L
void ClearList_Sq (SeqList *L)
{
L->length=0; //将线性表的长度置为0
}
// 求顺序表L的长度
int ListLength_Sq (SeqList *L)
{
return (L->length);
}
// 判断顺序表L是否为空
int ListEmpty_Sq (SeqList *L)
{
return L->length == 0;
}
// 根据给定元素的序号查找。
int GetElem_Sq (SeqList *L, int i, ElemType &e)
{
if ( i<1 || i>L->length)
return ERROR; // 判断i值是否合理，若不合理，返回ERRROR
e = L->data[i-1]; // 数组中第i-1的单元存储着线性表中第i个数据元素的内容
return OK;
}
// 根据给定的数据元素的值查找
int LocateElem_Sq (SeqList *L, ElemType e)
{
for (int i=0; i< L->length; i++)
if (L->data[i]==e)
return i+1;
return 0;
}
// 插入数据元素
int ListInsert_Sq (SeqList *L,int i,ElemType e)
{
if (L->length == ListSize)
return ERROR; // 检查是否有剩余空间
if ( i<1|| i>L->length+1)
return ERROR; // 检查i值是否合理
for (int j=L->length-1; j>=i-1; j--) // 将顺序表第i个元素之后的所有元素向后移动
L->data[j+1]=L->data[j];
L->data[i-1]=e; // 将新元素的内容放入顺序表的第i个位置，
L->length++; // 表长增1
return OK;
}
// 删除顺序表中的元素
int ListDelete_Sq (SeqList *L, int i, ElemType &e)
{
if (ListEmpty_Sq(L)) // 检测顺序表是否为空
return ERROR;
if (i<1||i>L->length) // 检查i值是否合理
return ERROR;
e = L->data[i-1]; // 将欲删除的数据元素内容保留在变量e中
for (int j=i;j<=L->length-1;j++) // 将线性表第i+1个元素之后的所有元素向前移动
L->data[j-1]=L->data[j];
L->length--;
return OK;
}
void DispList_Sq(SeqList *L) //输出线性表
{
int i;
printf("顺序表：");
if (ListEmpty_Sq(L)) {
printf("表空！\n");
return;
}
for (i=0;i<L->length;i++)
printf("%c ",L->data[i]);
printf("\n");
}
// 显示菜单
void showmenu()
{
printf("\n\n\n");
printf(" --线性表顺序存储基本运算演示-- \n");
printf("********************************************\n");
printf("* 1-------顺序表的初始化 *\n");
printf("* 2-------销毁顺序表 *\n");
printf("* 3-------清空顺序表 *\n");
printf("* 4-------求顺序表的长度 *\n");
printf("* 5-------判断顺序表是否为空 *\n");
printf("* 6-------检索表中第i个元素的值 *\n");
printf("* 7-------检索元素值为e的位序 *\n");
printf("* 8-------插入数据元素 *\n");
printf("* 9-------删除数据元素 *\n");
printf("* *\n");
printf("* 0-------退出 *\n");
printf("********************************************\n");
}
void List_Sq()
{
int choice;
ElemType item;
int Position;
SeqList *L = NULL;
int flag =0; // 是否创建好了顺序表
while (choice!=0)
{
//flushall();
printf("\n请选择菜单号(0--9): ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("初始化顺序表操作\n");
if (InitList_Sq(L))
{
printf("初始化成功!\n");
flag = 1; // 标志顺序表的存在
}
else
printf("初始化失败!\n");
break;
case 2:
if (flag) // 顺序表存在
{
DestroyList_Sq(L);
flag = 0; // 顺序表已删除
printf("顺序表删除成功！\n");
}else {
printf("顺序表不存在，操作失败！\n");
}
break;
case 3:
if (flag) // 顺序表存在
{
ClearList_Sq (L);
printf("顺序表清空成功！\n");
DispList_Sq(L); //输出线性表
}else {
printf("顺序表不存在，操作失败！\n");
}
break;
case 4:
if (flag) // 顺序表存在
{
printf("顺序表元素个数为 %d \n",ListLength_Sq(L));
DispList_Sq(L); //输出线性表
}else {
printf("顺序表不存在，操作失败！\n");
}
break;
case 5:
if (flag) // 顺序表存在
{
printf("顺序表%s。\n",ListEmpty_Sq(L)?"空":"不空");
DispList_Sq(L); //输出线性表
}else {
printf("顺序表不存在，操作失败！\n");
}
break;
case 6:
if (flag) // 顺序表存在
{
printf("请输入元素的位序号:");
scanf("%d",&Position);
if (GetElem_Sq(L,Position,item)){
printf("第%d个元素为：%c\n",Position,item);
}else {
printf("输入的位序号错误！\n");
}
DispList_Sq(L); //输出线性表
}else {
printf("顺序表不存在，操作失败！\n");
}
break;
case 7:
if (flag) // 顺序表存在
{
printf("请输入元素的值:");
//flushall();
scanf(" %c", &item);
Position=LocateElem_Sq(L,item);
if (Position){
printf("该元素找到，位序是%d。\n",Position);
}else {
printf("该元素没找到！\n");
}
DispList_Sq(L); //输出线性表
}else {
printf("顺序表不存在，操作失败！\n");
}
break;
case 8:
if (flag) // 顺序表存在
{
printf("请输入元素的值:");
scanf(" %c", &item);
printf("请输入要插入数据元素的位置序号:");
scanf("%d",&Position);
if (ListInsert_Sq (L, Position, item))
printf("该元素插入成功。\n");
else
printf("输入的位序号错误！\n");
DispList_Sq(L); //输出线性表
}else {
printf("顺序表不存在，操作失败！\n");
}
break;
case 9:
if (flag) // 顺序表存在
{
printf("请输入要删除元素的位置序号:");
scanf("%d",&Position);
if (ListDelete_Sq (L, Position, item)) {
printf("删除的元素为 %c \n",item);
} else {
printf("输入的位序号错误！\n");
}
DispList_Sq(L); //输出线性表
}else {
printf("顺序表不存在，操作失败！\n");
}
break;
case 0:
printf("\t 程序结束！\n");
DestroyList_Sq(L);
break;
default:
printf("\t 选择错误，请重新输入！\n");
break;
}
}
}
int main()
{
showmenu();
List_Sq();
return 0;
}
2.运行结果：
3.性能分析：
时间复杂度：
插入操作：由于需要从插入点开始向后移动所有后续元素，时间复杂度为O(n)。当插入位置接近表尾时效率较高，但插入到表头的效率较低。
删除操作：与插入类似，需要移动所有后续元素，时间复杂度也是O(n)。
检索操作：顺序表通过数组下标直接访问目标元素，时间复杂度为O(1)。
空间复杂度：
顺序表使用连续的数组存储元素，其空间复杂度为O(n)，但需事先预留空间。如果表的最大容量（MaxSize）设置过大，可能导致空间浪费；若容量不足，则无法继续插入新元素。
实验总结与体会
(1) 掌握了线性表的顺序结构；
(2) 熟悉了顺序表及其基本操作的实现；
(3) 掌握了相关数据结构及算法的程序实现的基本方法。
单链表操作
实验产出：
1.核心代码：
#include <stdio.h>
#define ERROR 0
#define OK 1
#define ListSize 100
typedef char ElemType;
typedef struct Node{
ElemType data; // 存放单链表元素值
struct Node *next;
} LNode, *LinkList;
// 构造一个空的单链表L
int InitList_L (LinkList &L)
{
L = new LNode; // 为头结点分配存储单元
if (!L)
return ERROR; // 无足够的内存空间，初始化失败
L->next = NULL;
return OK;
}
// 销毁链表
int DestroyList_L (LinkList &L)
{
LinkList p;
while(L) {
p=L;
L=L->next;
delete p;
}
return OK;
}
// 将L重置为空表
void ClearList_L (LinkList & L)
{
LinkList p,q;
p=L->next; // p指向第一个结点
while(p) { // 没到表尾
q=p->next;
delete p;
p=q;
}
L->next=NULL; // 头结点指针域为空
}
// 返回L中数据元素个数
int ListLength_L(LinkList L)
{
LinkList p=L->next; // p指向第一个结点
int i=0;
while(p) { // 遍历单链表,统计结点数
i++;
p=p->next;
}
return i;
}
int ListEmpty_L (LinkList L)
{ // 若L为空表，则返回true，否则返回false
return (L->next==NULL);
}
int LocateELem_L(LinkList L, ElemType e)
{
LinkList p;
int i=1;
p=L->next;
while(p && p->data!=e){
p=p->next;
i++;
}
return i; // 返回L中值为e的数据元素的位置，查找失败返回NULL
}
int GetElem_L (LinkList L, int i, ElemType &e)
{ // 在带头结点的单链表L中查找第i个元素
LinkList p=L->next;
int j=1;
while (p != NULL && j<i ) {
p=p->next;
j++;
}
if (!p || i<1 ) return ERROR;
e = p->data;
return OK;
}
int ListInsert_L (LinkList &L, int i, ElemType e)
{ // 将值为e的新结点插入到表的第i个结点的位置上
LinkList p=L, q;
int j=0;
while (p&&j<i-1) { // 寻找第i-1个结点
p=p->next;
++j;
}
if( !p || i<1) return ERROR; // i大于表长+1或者小于1
q=new LNode; // 生成新结点q
q->data=e; // 将结点q的数据域置为e
q->next=p->next; // 将结点q插入L中
p->next=q;
return OK;
}
// 按序号删除结点
int ListDelete_L( LinkList &L, int i,ElemType &e)
{
LinkList p=L, q;
int j=0;
while (p->next && j<i-1){ // 寻找第i个结点，并令p指向其前驱
p=p->next;
++j;
}
if( !(p->next) || i<1)
return ERROR; // 删除位置不合理
q=p->next; // 临时保存被删结点的地址以备释放
p->next=q->next; // 改变被删除结点前驱结点的指针域
e = q->data; // 保存被删除结点的数据域
delete q; // 释放被删除结点的空间
return OK;
}
// 按值删除结点
int ListDeleteValue_L( LinkList &L, ElemType e)
{
LinkList p=L, q=L->next;
while (q && q->data != e){ // 寻找元素值等于e的结点，并令p指向其前驱
p = q;
q=q->next;
}
if( !q) return ERROR; // 没找到值为e的结点
p->next=q->next; // 改变被删除结点前驱结点的指针域
delete q; // 释放被删除结点的空间
return OK;
}
// 在单链表的头部插入结点建立单链表
void CreateList_F_L ( LinkList &L, int n)
{ // 逆位序输入n个元素的值，建立单链表L
// 要求，在用前插法创建单链表之前，需要执行InitList_L()初始化单链表，
// 即先建立一个带表头结点的空表
LinkList p;
printf("请按逆序依次输入元素的值: ");
for (int i=n; i>0; --i ) {
p= new LNode; // 生成新结点
scanf(" %c", &p->data); // 输入元素值
p->next = L->next;
L->next=p; // 插入到表头
}
}
// 在单链表的尾部插入结点建立单链表
void CreateList_L_L ( LinkList &L, int n)
{ // 正位序输入n个元素的值，建立带头结点的单链表L
// 要求，在用尾插法创建单链表之前，需要执行InitList_L()初始化单链表，
// 即先建立一个带表头结点的空表
LinkList p, r = L;
printf("请按正序依次输入元素的值: ");
for (int i=0; i<n; i++ ) {
p= new LNode; // 生成新结点
scanf(" %c", &p->data); // 输入元素值
p->next = NULL;
r->next = p; // 插入到表尾
r = p; // r指向新的尾结点
}
}
void DispList_L(LinkList L) //输出线性表
{
printf("单链表：");
if (ListEmpty_L(L)) {
printf("表空！\n");
return;
}
LinkList p=L->next;
while (p) {
printf("%c ",p->data);
p=p->next;
}
printf("\n");
}
// 显示菜单
void showmenu()
{
printf("\n\n\n");
printf(" --线性表链式存储基本运算演示-- \n");
printf("********************************************\n");
printf("* 1-------单链表的初始化 *\n");
printf("* 2-------销毁单链表 *\n");
printf("* 3-------清空单链表 *\n");
printf("* 4-------求单链表的长度 *\n");
printf("* 5-------判断单链表是否为空 *\n");
printf("* 6-------检索表中第i个元素的值 *\n");
printf("* 7-------检索元素值为e的元素 *\n");
printf("* 8-------插入数据元素 *\n");
printf("* 9-------按序号删除数据元素 *\n");
printf("* a-------按值删除数据元素 *\n");
printf("* b-------按头插法创建单链表 *\n");
printf("* c-------按尾插法创建单链表 *\n");
printf("* *\n");
printf("* 0-------退出 *\n");
printf("********************************************\n");
}
void List_L()
{
char choice='N';
ElemType item;
int Position;
int number;
LinkList L;
int flag =0; // 是否创建好了单链表
while (choice!='0')
{
//flushall();
printf("\n请选择菜单号(0--c): ");
scanf(" %c",&choice);
switch(choice)
{
case '1':
printf("初始化单链表操作\n");
if (InitList_L(L)) {
printf("初始化成功!\n");
flag = 1; // 标志顺序表的存在
}
else
printf("初始化失败!\n");
break;
case '2':
if (flag) { // 单链表存在
DestroyList_L(L);
flag = 0; // 单链表已删除
printf("单链表删除成功！\n");
}else {
printf("单链表不存在，操作失败！\n");
}
break;
case '3':
if (flag) { // 单链表存在
ClearList_L(L);
printf("单链表清空成功！\n");
DispList_L(L); //输出线性表
}else {
printf("单链表不存在，操作失败！\n");
}
break;
case '4':
if (flag) { // 单链表存在
printf("单链表元素个数为 %d \n",ListLength_L(L));
DispList_L(L); //输出线性表
}else {
printf("顺序表不存在，操作失败！\n");
}
break;
case '5':
if (flag) { // 单链表存在
printf("单链表%s。\n",ListEmpty_L(L)?"空":"不空");
DispList_L(L); //输出线性表
}else {
printf("单链表不存在，操作失败！\n");
}
break;
case '6':
if (flag) { // 单链表存在
printf("请输入元素的位序号:");
scanf("%d",&Position);
if (GetElem_L(L,Position,item)){
printf("第%d个元素为：%c\n",Position,item);
}else {
printf("输入的位序号错误！\n");
}
DispList_L(L); //输出线性表
}else {
printf("单链表不存在，操作失败！\n");
}
break;
case '7':
if (flag) { // 单链表存在
printf("请输入元素的值:");
//flushall();
scanf(" %c",&item);
//LinkList P = LocateELem_L(L,item);
int P = LocateELem_L(L,item);
if (P){
//printf("该元素找到，地址为%x!\n",P);
printf("该元素找到，地址为%d\n",P);
}else {
printf("该元素没找到！\n");
}
DispList_L(L); //输出线性表
}else {
printf("单链表不存在，操作失败！\n");
}
break;
case '8':
if (flag) { // 单链表存在
printf("请输入元素的值:");
//flushall();
scanf(" %c",&item);
printf("请输入要插入数据元素的位置序号:");
scanf("%d",&Position);
if (ListInsert_L(L, Position, item))
printf("该元素插入成功。\n");
else
printf("输入的位序号错误！\n");
DispList_L(L); //输出线性表
}else {
printf("单链表不存在，操作失败！\n");
}
break;
case '9':
if (flag) { // 单链表存在
printf("请输入要删除元素的位置序号:");
scanf("%d",&Position);
if (ListDelete_L(L, Position, item)) {
printf("删除的元素为 %c \n",item);
} else {
printf("输入的位序号错误！\n");
}
DispList_L(L); //输出线性表
}else {
printf("单链表不存在，操作失败！\n");
}
break;
case 'a':
case 'A':
if (flag) { // 单链表存在
printf("请输入要删除元素的值:");
//flushall();
scanf(" %c",&item);
if (ListDeleteValue_L(L, item)) {
printf("删除的元素为 %c \n",item);
} else {
printf("改元素不存在，删除失败！\n");
}
DispList_L(L); //输出线性表
}else {
printf("单链表不存在，操作失败！\n");
}
break;
case 'b':
case 'B':
if (flag) { // 单链表存在
ClearList_L(L); // 清空单链表
printf("按头插法创建单链表\n");
printf("请输入要插入数据元素的个数:");
scanf("%d",&number);
//flushall();
CreateList_F_L(L, number);
DispList_L(L); //输出线性表
}else {
printf("单链表不存在，操作失败！\n");
}
break;
case 'c':
case 'C':
if (flag) { // 单链表存在
ClearList_L(L); // 清空单链表
printf("按尾插法创建单链表\n");
printf("请输入要插入数据元素的个数:");
scanf("%d",&number);
//flushall();
CreateList_L_L(L, number);
DispList_L(L); //输出线性表
}else {
printf("单链表不存在，操作失败！\n");
}
break;
case '0':
printf("\t 程序结束！\n");
DestroyList_L(L);
break;
default:
printf("\t 选择错误，请重新输入！\n");
break;
}
}
}
int main()
{
showmenu();
List_L();
return 0;
}
2.运行结果：
3.性能分析：
时间复杂度：
插入操作：链表的插入只需找到第i-1个节点并修改指针，时间复杂度为O(n)（查找节点耗时），但不涉及元素移动操作。因此链表的插入效率比顺序表高，尤其在插入到表头或表尾时表现更为突出。
删除操作：链表删除同样需要找到目标节点及其前驱节点，时间复杂度为O(n)。与插入类似，删除操作无需移动后续节点，因此效率高于顺序表。
检索操作：由于链表需逐节点遍历才能找到目标元素，时间复杂度为O(n)，随机访问效率较低。
空间复杂度：
链表的空间复杂度也是O(n)，但因其动态分配存储空间，节省了顺序表中预留的多余空间。然而，链表每个节点需要额外存储一个指针，因此比顺序表更占用内存。
总结
在C语言中，scanf()函数用于从标准输入（通常是键盘）读取格式化输入。然而，scanf()函数在读取输入时会留下换行符（‘\n’）在输入缓冲区中，如果后面紧接着有需要读取字符的函数，比如getchar()，那么这个换行符就会被getchar()读取，导致程序的行为可能不是预期的。
使用getchar()来清除缓冲区中的换行符是一种常见的做法，这样可以确保下一次读取字符时，不会立即读取到这个残留的换行符。这样做可以避免程序逻辑中的错误，特别是在需要精确控制输入和输出时。
在scanf()函数中，在格式字符串的‘%’符号前加一个空格同样可以解决这个问题，这是用来告诉scanf()忽略任何空白字符，包括空格、制表符和换行符。这意味着，当在‘%’前面加一个空格时，scanf()会跳过这些空白字符，直到遇到非空白字符才开始匹配格式字符串。
这个空格告诉scanf()忽略前面的所有空白字符，所以即使用户在输入数字之前按下了空格键或者输入数字后按下了回车键，scanf()也会忽略这些空白字符，直接读取数字。
这样做的好处是，它不仅会忽略用户输入的换行符，还会忽略其他任何形式的空白字符，使得输入更加灵活。用户可以在数字之间插入任意数量的空格，而scanf()仍然能够正确地读取数字。