该网站未在腾讯云备案,移动网站套餐,用竹片做的网站,怎么做网站的思维导图目录#x1f60b;
任务描述 相关知识
一、线性表的基本概念
二、初始化线性表
三、销毁线性表
四、判定是否为空表
五、求线性表的长度
六、输出线性表
七、求线性表中某个数据元素值
八、按元素值查找
九、插入数据元素
十、删除数据元素
测试说明
通关代码
测…目录
任务描述 相关知识
一、线性表的基本概念
二、初始化线性表
三、销毁线性表
四、判定是否为空表
五、求线性表的长度
六、输出线性表
七、求线性表中某个数据元素值
八、按元素值查找
九、插入数据元素
十、删除数据元素
测试说明
通关代码
测试结果 任务描述 本关任务实现顺序表的基本运算 相关知识 为了完成本关任务你需要掌握 线性表的基本概念初始化线性表销毁线性表判定是否为空表求线性表的长度输出线性表求线性表中某个数据元素值按元素值查找插入数据元素删除数据元素 一、线性表的基本概念 线性表是一种基本的数据结构它是由 nn ≥ 0个具有相同类型的数据元素组成的有限序列。可以将线性表想象成一个队伍队伍中的每个人数据元素都有自己的位置并且他们的类型是相同的比如都是学生。常见的线性表有顺序表和链表 二、初始化线性表 顺序表初始化以 C 为例 顺序表通常是用数组来实现的。初始化时需要定义数组的大小并且可以将线性表的长度当前存储的元素个数初始化为 0。 示例代码 #define MAX_SIZE 100 // 假设顺序表最大容量为100
template typename T
class SeqList {
public:T data[MAX_SIZE];int length;SeqList() {length 0;}
}; 链表初始化以单链表为例 单链表由节点组成每个节点包含数据域和指针域。初始化时头节点如果有的指针通常设为 NULL表示链表为空。 示例代码 template typename T
struct ListNode {T data;ListNodeT *next;ListNode(T x) : data(x), next(NULL) {}
};
// 初始化一个空链表只需要定义头节点并将其next指针设为NULL
ListNodeint *head new ListNodeint(0);
head-next NULL; 三、销毁线性表 顺序表销毁 对于顺序表如果是静态分配的数组如上述示例在程序结束时自动销毁。如果是动态分配的数组需要使用delete[]来释放内存。不过一般简单的顺序表在程序结束时会自动回收内存不需要手动销毁。 链表销毁 对于链表需要遍历链表逐个释放节点占用的内存。从链表的头节点开始先保存下一个节点的指针然后释放当前节点再将指针指向下一个节点直到链表为空。 示例代码 template typename T
void destroyList(ListNodeT *head) {ListNodeT *current head;ListNodeT *next;while (current! NULL) {next current-next;delete current;current next;}
}四、判定是否为空表 顺序表判定 只需检查线性表的长度是否为 0。如果length 0则顺序表为空。 示例代码 template typename T
bool isEmpty(SeqListT list) {return list.length 0;
}链表判定 对于链表检查头节点的下一个节点是否为 NULL。如果head-next NULL则链表为空。 示例代码 template typename T
bool isEmpty(ListNodeT *head) {return head-next NULL;
}五、求线性表的长度 顺序表求长度 直接返回顺序表中记录长度的变量的值如return length;。 链表求长度 需要遍历链表从链表头节点开始不计算头节点本身如果有头节点的话每经过一个节点长度加 1直到链表结束。 示例代码 template typename T
int length(ListNodeT *head) {int len 0;ListNodeT *current head-next;while (current! NULL) {len;current current-next;}return len;
}六、输出线性表 顺序表输出 遍历顺序表数组中从 0 到length - 1的元素逐个输出元素。 示例代码 template typename T
void printSeqList(SeqListT list) {for (int i 0; i list.length; i) {std::cout list.data[i] ;}std::cout std::endl;
}链表输出 从链表头节点的下一个节点如果有头节点开始遍历链表输出每个节点的数据域内容直到链表结束。 示例代码 template typename T
void printList(ListNodeT *head) {ListNodeT *current head-next;while (current! NULL) {std::cout current-data ;current current-next;}std::cout std::endl;
}七、求线性表中某个数据元素值 顺序表求元素值 给定元素的位置索引i如果0 i length则返回data[i]否则可能需要根据具体情况返回错误信息如抛出异常或者返回一个特殊值表示位置无效。 链表求元素值 首先遍历链表当遍历到第i个节点假设链表头节点不算在内从 0 开始计数时返回该节点的数据域的值。这可能需要一个计数器来记录当前遍历到的节点位置。 八、按元素值查找 顺序表按元素值查找 遍历顺序表数组从 0 到length - 1比较每个元素和目标元素的值。如果找到相等的元素返回该元素的索引如果遍历完整个顺序表都没有找到可能返回一个特殊值如 - 1表示未找到。 示例代码 template typename T
int findElement(SeqListT list, T target) {for (int i 0; i list.length; i) {if (list.data[i] target) {return i;}}return -1;
}链表按元素值查找 从链表头节点的下一个节点开始遍历链表比较每个节点的数据域和目标元素的值。如果找到相等的元素返回该节点或者返回节点的索引这取决于具体要求如果遍历完整个链表都没有找到返回一个表示未找到的特殊值。 九、插入数据元素 顺序表插入元素 如果是在位置i插入元素需要先判断i的合法性如0 i length。如果i合法将i及以后的元素向后移动一位从最后一个元素开始移动然后将新元素插入到i位置最后长度加 1。 示例代码 template typename T
void insertElement(SeqListT list, T element, int i) {if (i 0 || i list.length) {std::cout 插入位置无效 std::endl;return;}if (list.length MAX_SIZE) {std::cout 顺序表已满 std::endl;return;}for (int j list.length; j i; j--) {list.data[j] list.data[j - 1];}list.data[i] element;list.length;
}链表插入元素 插入位置分为在头节点后插入、在中间节点插入和在尾节点插入。如果是在头节点后插入只需修改新节点的指针和头节点的指针在中间节点插入需要先找到插入位置的前一个节点然后修改指针来插入新节点在尾节点插入找到链表的最后一个节点将新节点插入到最后一个节点之后。 十、删除数据元素 顺序表删除元素 给定要删除元素的位置i先判断i的合法性如0 i length。如果i合法将i 1位置的元素向前移动到i位置直到最后一个元素然后长度减 1。 示例代码 template typename T
void deleteElement(SeqListT list, int i) {if (i 0 || i list.length) {std::cout 删除位置无效 std::endl;return;}for (int j i; j list.length - 1; j) {list.data[j] list.data[j 1];}list.length--;
}链表删除元素 同样需要先找到要删除的节点。如果是删除头节点后的节点修改头节点的指针如果是删除中间节点找到要删除节点的前一个节点修改指针跳过要删除的节点如果是删除尾节点找到倒数第二个节点将其指针设为 NULL。 测试说明 平台会对你编写的代码进行测试 测试输入 3
4 预期输出 (1)初始化顺序表L
(2)依次插入a,b,c,d,e元素
(3)输出顺序表L:a b c d e
(4)顺序表L长度:5
(5)顺序表L为非空
(6)顺序表L的第3个元素:c
(7)元素a的位置:1
(8)在第4个元素位置上插入f元素
(9)输出顺序表L:a b c f d e
(10)删除L的第3个元素
(11)输出顺序表L:a b f d e
(12)释放顺序表L 开始你的任务吧祝你成功 通关代码
// 请在Begin-End之间添加你的代码
//实现顺序表的如下基本运算假设顺序表的元素类型为char//
//(1)初始化顺序表L//
//(2)依次插入a,b,c,d,e元素//
//(3)输出顺序表L//
//(4)输出顺序表L的长度//
//(5)判断顺序表L是否为空输出判断结果//
//(6)输出顺序表L的第m个元素m由用户输入//
//(7)输出元素a的位置//
//(8)在第n个元素位置上插入f元素n由用户输入//
//(9)输出顺序表L//
//(10)删除顺序表L的第m个元素延用第6的m//
//(11)输出顺序表L//
//(12)释放顺序表L//
/********** Begin *********/
#include iostream
#include stringusing namespace std;#define MAX_SIZE 100typedef char ElemType;typedef struct {ElemType data[MAX_SIZE];int length;
} SeqList;void InitList(SeqList L) { L.length 0; }void PrintList(SeqList L) {for (int i 0; i L.length; i) {cout L.data[i] ;}cout endl;
}
int InsertList(SeqList *L, int i, ElemType e) {if (i 1 || i L-length 1 || L-length MAX_SIZE)return 0;for (int j L-length; j i; j--) {L-data[j] L-data[j - 1];}L-data[i - 1] e;L-length;return 1;
}bool GetElem(SeqList L, int i, ElemType e) {if (i 1 || i L.length)return false;e L.data[i - 1];return true;
}int LocateElem(SeqList L, ElemType e) {for (int i 0; i L.length; i) {if (L.data[i] e)return i 1;}return 0;
}bool ListInsert(SeqList L, int i, ElemType e) {if (i 1 || i L.length 1)return false;for (int j L.length; j i; j--) {L.data[j] L.data[j - 1];}L.data[i - 1] e;L.length;return true;
}bool ListDelete(SeqList L, int i, ElemType e) {if (i 1 || i L.length)return false;e L.data[i - 1];for (int j i; j L.length; j) {L.data[j - 1] L.data[j];}L.length--;return true;
}int main() {SeqList L;InitList(L);int pos1, pos2;cin pos1 pos2;cout (1)初始化顺序表L endl;char elements[] {a, b, c, d, e};for (int i 0; i 5; i) {InsertList(L, i 1, elements[i]);}cout (2)依次插入a,b,c,d,e元素 endl;cout (3)输出顺序表L:;PrintList(L);cout (4)顺序表L长度: L.length endl;cout (5)顺序表L为非空 endl;ElemType e;if (GetElem(L, pos1, e)) {cout (6)顺序表L的第 pos1 个元素: e endl;}int pos LocateElem(L, a);cout (7)元素a的位置: pos endl;ListInsert(L, pos2, f);cout (8)在第 pos2 个元素位置上插入f元素 endl;cout (9)输出顺序表L:;PrintList(L);ListDelete(L, pos1, e);cout (10)删除L的第 pos1 个元素 endl;cout (11)输出顺序表L:;PrintList(L);cout (12)释放顺序表L;return 0;
}
/********** End **********/ 测试结果
