越野车网站模板,wordpress category 自定义,做网站怎么上线,沈阳网站建设的公司海~~欢迎来到Tubishu的博客#x1f338;如果你也是一名在校大学生#xff0c;正在寻找各种变成资源#xff0c;那么你就来对地方啦#x1f31f; Tubishu是一名计算机本科生#xff0c;会不定期整理和分享学习中的优质资源#xff0c;希望能为你的编程之路添砖加瓦⭐… 海~~欢迎来到Tubishu的博客如果你也是一名在校大学生正在寻找各种变成资源那么你就来对地方啦 Tubishu是一名计算机本科生会不定期整理和分享学习中的优质资源希望能为你的编程之路添砖加瓦⭐ 当然如果你也好的资源推荐欢迎在评论区分享让我们共同打造一个丰富的编程资源库 本文专栏 ➡️ 数据结构 实验目的 掌握线性表的顺序/链接存储结构 验证顺序表/链表及其基本操作的实现 掌握数据结构及算法的程序实现的基本方法 实验内容
请选择使用顺序表或链表单链表或双链表实现以下操作要求设计菜单并根据菜单提示进行操作
插入一个新元素到第i个位置删除第i个位置的元素显示线性表中所有元素的值检索表中第i个元素求表的长度 顺序表操作
实验产出
1.核心代码
#include bits/stdc.h
using namespace std;#define ERROR 0
#define OK 1
#define ListSize 100typedef char ElemType;
typedef struct
{ ElemType data[ListSize]; // 存放顺序表元素int length; // 存放顺序表的长度
} SeqList; // 顺序表的类型定义// 构造一个空的顺序表L//顺序表的初始化
int InitList_Sq (SeqList *L)
{ L new SeqList; // 为顺序表分配空间if(!L) // 存储分配失败return ERROR; // 初始化失败L-length0; // 空表长度为0return OK; // 初始化成功
}// 销毁顺序表
void DestroyList_Sq(SeqList *L)
{delete L;L NULL;
}// 清空顺序表L
void ClearList_Sq (SeqList *L)
{L-length0; //将线性表的长度置为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 ( i1 || iL-length) return ERROR; // 判断i值是否合理若不合理返回ERRRORe L-data[i-1]; // 数组中第i-1的单元存储着线性表中第i个数据元素的内容return OK;
}// 根据给定的数据元素的值查找
int LocateElem_Sq (SeqList *L, ElemType e)
{for (int i0; i L-length; i)if (L-data[i]e) return i1;return 0;
}// 插入数据元素
int ListInsert_Sq (SeqList *L,int i,ElemType e)
{if (L-length ListSize)return ERROR; // 检查是否有剩余空间if ( i1|| iL-length1)return ERROR; // 检查i值是否合理for (int jL-length-1; ji-1; j--) // 将顺序表第i个元素之后的所有元素向后移动L-data[j1]L-data[j];L-data[i-1]e; // 将新元素的内容放入顺序表的第i个位置L-length; // 表长增1return OK;
}// 删除顺序表中的元素
int ListDelete_Sq (SeqList *L, int i, ElemType e)
{if (ListEmpty_Sq(L)) // 检测顺序表是否为空return ERROR; if (i1||iL-length) // 检查i值是否合理return ERROR; e L-data[i-1]; // 将欲删除的数据元素内容保留在变量e中for (int ji;jL-length-1;j) // 将线性表第i1个元素之后的所有元素向前移动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 (i0;iL-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; // 标志顺序表的存在}elseprintf(初始化失败!\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);PositionLocateElem_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 100typedef 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) {pL;LL-next;delete p; }return OK;
}// 将L重置为空表
void ClearList_L (LinkList L)
{LinkList p,q;pL-next; // p指向第一个结点while(p) { // 没到表尾 qp-next; delete p;pq;}L-nextNULL; // 头结点指针域为空
}// 返回L中数据元素个数
int ListLength_L(LinkList L)
{LinkList pL-next; // p指向第一个结点int i0; while(p) { // 遍历单链表,统计结点数i;pp-next;} return i;
}int ListEmpty_L (LinkList L)
{ // 若L为空表则返回true否则返回falsereturn (L-nextNULL);
}int LocateELem_L(LinkList L, ElemType e)
{ LinkList p;int i1;pL-next; while(p p-data!e){pp-next;i;} return i; // 返回L中值为e的数据元素的位置查找失败返回NULL
}int GetElem_L (LinkList L, int i, ElemType e)
{ // 在带头结点的单链表L中查找第i个元素LinkList pL-next;int j1;while (p ! NULL ji ) {pp-next;j;}if (!p || i1 ) return ERROR;e p-data;return OK;
}int ListInsert_L (LinkList L, int i, ElemType e)
{ // 将值为e的新结点插入到表的第i个结点的位置上LinkList pL, q;int j0; while (pji-1) { // 寻找第i-1个结点 pp-next;j;} if( !p || i1) return ERROR; // i大于表长1或者小于1qnew LNode; // 生成新结点q q-datae; // 将结点q的数据域置为e q-nextp-next; // 将结点q插入L中 p-nextq; return OK;
}// 按序号删除结点
int ListDelete_L( LinkList L, int i,ElemType e)
{LinkList pL, q;int j0; while (p-next ji-1){ // 寻找第i个结点并令p指向其前驱 pp-next; j; } if( !(p-next) || i1)return ERROR; // 删除位置不合理 qp-next; // 临时保存被删结点的地址以备释放 p-nextq-next; // 改变被删除结点前驱结点的指针域 e q-data; // 保存被删除结点的数据域 delete q; // 释放被删除结点的空间 return OK;
} // 按值删除结点
int ListDeleteValue_L( LinkList L, ElemType e)
{LinkList pL, qL-next;while (q q-data ! e){ // 寻找元素值等于e的结点并令p指向其前驱 p q;qq-next; } if( !q) return ERROR; // 没找到值为e的结点 p-nextq-next; // 改变被删除结点前驱结点的指针域 delete q; // 释放被删除结点的空间 return OK;
} // 在单链表的头部插入结点建立单链表
void CreateList_F_L ( LinkList L, int n)
{ // 逆位序输入n个元素的值建立单链表L// 要求在用前插法创建单链表之前需要执行InitList_L()初始化单链表// 即先建立一个带表头结点的空表LinkList p;printf(请按逆序依次输入元素的值: );for (int in; i0; --i ) { p new LNode; // 生成新结点scanf( %c, p-data); // 输入元素值 p-next L-next; L-nextp; // 插入到表头 }
} // 在单链表的尾部插入结点建立单链表
void CreateList_L_L ( LinkList L, int n)
{ // 正位序输入n个元素的值建立带头结点的单链表L// 要求在用尾插法创建单链表之前需要执行InitList_L()初始化单链表// 即先建立一个带表头结点的空表LinkList p, r L;printf(请按正序依次输入元素的值: );for (int i0; in; 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 pL-next;while (p) {printf(%c ,p-data);pp-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 choiceN;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; // 标志顺序表的存在}elseprintf(初始化失败!\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()仍然能够正确地读取数字。
