实验1
实验报告
（ 2025 ～ 2026 学年 秋季学期）
课程代码 B070730608002
课程名称 数据结构 专业班级 25虚拟1班 学生学号 253051601132 学生姓名 战忠沅 指导教师 曹梅春
信息工程学院
2026年3月24日
实验（训）项目名称 | 线性表的操作 | ||||
实验（训）地点 | 明远楼C110 | 实验（训）日期 | 2026.3.24 | ||
小组成员 | 无 | ||||
小组成员 分工情况 | 无 | ||||
实验（训）所用设备、材料、软件等： Win10操作系统计算机 VC++ 2010学习版软件 | |||||
实验（训）目的： 1、理解和掌握线性表的顺序和链式存储结构类型定义方法； 2、掌握建立、显示、插入、删除、查找、拆分、合并顺序表和链表的基本方法。 | |||||
实验（训）内容、步骤、结果、心得体会： 一、实验内容 （一）顺序存储 1.输入一组整型元素序列，建立线性表的顺序存储结构。 2.实现该线性表的遍历。 3.在该顺序表中查找某一元素,查找成功显示查找元素，否则显示查找失败。 4.在该顺序表中删除或插入指定元素。 5.建立两个按值递增有序的顺序表，将他们合并成一个按值递增有序的顺序表。 （二）链式存储 1.输入一组整型元素序列，使用尾插法建立一个带有头结点的单链表。 2.实现该线性表的遍历。 3.在该单链表的第i个元素前插入一个整数。 4.删除该单链表中的第i个元素，其值通过参数将其返回。 5.建立两个按值递增有序的单链表，将他们合并成一个按值递减有序的单链表。要求利用原来的存储空间 二、实验步骤 （一） #include <iostream> using namespace std; #define MAXSIZE 100 #define OK 1 #define ERROR 0 #define OVERFLOW -1 typedef struct { int elem[MAXSIZE]; int length; } Sqlist; int init(Sqlist &L) { L.length = 0; return OK; } int create(Sqlist &L) { int n; cout << "请输入线性表的长度："; cin >> n; cout << "请输入线性表的元素："; for (int i = 0; i < n; i++) { cin >> L.elem[i]; } L.length = n; return OK; } int traverse(Sqlist L) { cout << "线性表的元素为："; for (int i = 0; i < L.length; i++) { cout << L.elem[i] << " "; } cout << endl; return OK; } int find(Sqlist L, int e) { for (int i = 0; i < L.length; i++) { if (L.elem[i] == e) { return i; } } return -1; } bool insert(Sqlist &L, int i, int e) { if (i < 1 || i > L.length + 1) { return false; } if (L.length >= MAXSIZE) { return false; } for (int j = L.length - 1; j >= i - 1; j--) { L.elem[j + 1] = L.elem[j]; } L.elem[i - 1] = e; L.length++; return true; } bool remove(Sqlist &L, int i) { if (i < 1 || i > L.length) { return false; } for (int j = i - 1; j < L.length - 1; j++) { L.elem[j] = L.elem[j + 1]; } L.length--; return true; } int merge(Sqlist A, Sqlist B, Sqlist &C) { int i = 0, j = 0, k = 0; while (i < A.length && j < B.length) { if (A.elem[i] < B.elem[j]) { C.elem[k++] = A.elem[i++]; } else { C.elem[k++] = B.elem[j++]; } } while (i < A.length) { C.elem[k++] = A.elem[i++]; } while (j < B.length) { C.elem[k++] = B.elem[j++]; } C.length = k; return OK; } int main() { Sqlist L, A, B, C; int x, pos; init(L); create(L); traverse(L); cout << "请输入要查找的元素："; cin >> x; int idx = find(L, x); if (idx != -1) { cout << "元素" << x << "在第" << idx + 1 << "个位置" << endl; } else { cout << "元素" << x << "不在表中" << endl; } cout << "请输入要插入的位置和元素："; cin >> pos >> x; if (insert(L, pos, x)) { cout << "插入成功" << endl; traverse(L); } else { cout << "插入失败" << endl; } cout << "请输入要删除的位置："; cin >> pos; if (remove(L, pos)) { cout << "删除成功" << endl; traverse(L); } else { cout << "删除失败" << endl; } init(A); init(B); init(C); create(A); create(B); merge(A, B, C); traverse(C); return 0; } 输出结果：
（二） #include <iostream> using namespace std; typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; int init(LinkList &L) { L = new LNode; L->next = NULL; return 1; } int create(LinkList &L) { int n, x; cout << "请输入链表长度："; cin >> n; cout << "请输入元素："; LNode *tail = L; for (int i = 0; i < n; i++) { cin >> x; LNode *s = new LNode; s->data = x; s->next = NULL; tail->next = s; tail = s; } return 1; } int traverse(LinkList L) { cout << "链表元素为："; LNode *p = L->next; while (p) { cout << p->data << " "; p = p->next; } cout << endl; return 1; } bool insert(LinkList &L, int i, int e) { if (i < 1) return false; LNode *p = L; int j = 0; while (p && j < i - 1) { p = p->next; j++; } if (!p) return false; LNode *s = new LNode; s->data = e; s->next = p->next; p->next = s; return true; } bool remove(LinkList &L, int i, int &e) { if (i < 1) return false; LNode *p = L; int j = 0; while (p->next && j < i - 1) { p = p->next; j++; } if (!p->next) return false; LNode *q = p->next; e = q->data; p->next = q->next; delete q; return true; } int merge(LinkList A, LinkList B, LinkList &C) { LNode *pa = A->next, *pb = B->next, *pc; C = A; C->next = NULL; pc = C; while (pa && pb) { if (pa->data <= pb->data) { LNode *s = pa; pa = pa->next; s->next = C->next; C->next = s; } else { LNode *s = pb; pb = pb->next; s->next = C->next; C->next = s; } } while (pa) { LNode *s = pa; pa = pa->next; s->next = C->next; C->next = s; } while (pb) { LNode *s = pb; pb = pb->next; s->next = C->next; C->next = s; } delete B; return 1; } int main() { LinkList L, A, B, C; int x, pos, e; init(L); create(L); traverse(L); cout << "请输入插入位置和元素："; cin >> pos >> x; if (insert(L, pos, x)) { cout << "插入成功" << endl; traverse(L); } else { cout << "插入失败" << endl; } cout << "请输入删除位置："; cin >> pos; if (remove(L, pos, e)) { cout << "删除成功，元素为：" << e << endl; traverse(L); } else { cout << "删除失败" << endl; } init(A); init(B); create(A); create(B); merge(A, B, C); cout << "合并后递减有序链表："; traverse(C); return 0; } 输出结果：
心得体会： | |||||
教师评语： | |||||
成绩评定 | 教师签名 | ||||
