数据结构练习二习题

第七题：

#include<bits/stdc++.h>
using namespace std;#define MaxSize 100  // 定义顺序表的最大长度typedef int ElemType;  // 定义元素类型为inttypedef struct {ElemType data[MaxSize];  // 存储数据的数组int length;              // 当前顺序表的长度
} SqList;// 插入函数：在有序顺序表中插入元素x
void charu(SqList *&L, ElemType x) {if (L->length >= MaxSize) {  // 检查顺序表是否已满cout << "顺序表已满，无法插入！" << endl;return;}int i = 0;// 找到插入位置while (i < L->length && L->data[i] < x) {i++;}// 将插入位置后的元素后移for (int j = L->length - 1; j >= i; j--) {L->data[j + 1] = L->data[j];}// 插入元素xL->data[i] = x;L->length++;  // 顺序表长度加1
}int main() {SqList *L = new SqList();  // 动态分配顺序表内存L->length = 0;             // 初始化顺序表长度为0int n;cout << "请输入有序表的初始元素个数（不超过" << MaxSize << "）：";cin >> n;if (n > MaxSize) {cout << "输入的元素个数超过顺序表最大容量！" << endl;return 0;}cout << "请输入" << n << "个有序的整数：" << endl;for (int i = 0; i < n; i++) {cin >> L->data[i];L->length++;  // 每输入一个元素，顺序表长度加1}int x;cout << "请输入要插入的数值x: ";cin >> x;// 调用插入函数charu(L, x);// 输出插入后的顺序表cout << "插入后的顺序表: ";for (int i = 0; i < L->length; i++) {cout << L->data[i] << " ";}cout << endl;delete L;  // 释放动态分配的内存return 0;
}

第八题：

#include<bits/stdc++.h>
using namespace std;#define MaxSize 100  // 定义顺序表的最大长度typedef int ElemType;  // 定义元素类型为inttypedef struct {ElemType data[MaxSize];  // 存储数据的数组int length;              // 当前顺序表的长度
} SqList;// 调序函数：将顺序表中的负数移到前面，非负数移到后面
void tiaoxu(SqList *&L) {int i = 0;int j = L->length - 1;while (i < j) {while (L->data[i] < 0) i++;  // 从左往右找到第一个非负数while (L->data[j] >= 0) j--; // 从右往左找到第一个负数if (i < j) {swap(L->data[i], L->data[j]);  // 交换两个元素}}
}int main() {SqList *L = new SqList();  // 动态分配顺序表内存L->length = 0;             // 初始化顺序表长度为0int n;cout << "请输入顺序表的初始元素个数（不超过" << MaxSize << "）：";cin >> n;if (n > MaxSize) {cout << "输入的元素个数超过顺序表最大容量！" << endl;return 0;}cout << "请输入" << n << "个整数：" << endl;for (int i = 0; i < n; i++) {cin >> L->data[i];L->length++;  // 每输入一个元素，顺序表长度加1}// 调用调序函数tiaoxu(L);// 输出调序后的顺序表cout << "调序后的顺序表: ";for (int i = 0; i < L->length; i++) {cout << L->data[i] << " ";}cout << endl;delete L;  // 释放动态分配的内存return 0;
}

第十一题：

第十二题：

#include <iostream>
using namespace std;// 定义链表结点结构
typedef int ElemType;  // 定义元素类型为inttypedef struct LinkNode {ElemType data;              // 数据域struct LinkNode* next;      // 指针域
} LinkNode;// 创建链表
void CreateList(LinkNode*& L, int n) {L = new LinkNode();  // 创建头结点L->next = nullptr;   // 初始化为空链表LinkNode* tail = L;  // 尾指针，初始指向头结点cout << "请输入" << n << "个整数：" << endl;for (int i = 0; i < n; i++) {LinkNode* newNode = new LinkNode();  // 创建新结点cin >> newNode->data;newNode->next = nullptr;tail->next = newNode;  // 将新结点插入链表尾部tail = newNode;        // 更新尾指针}
}// 逆置链表
void Reverse(LinkNode*& L) {if (L == nullptr || L->next == nullptr) {return;  // 空链表或只有一个结点，无需逆置}LinkNode* p = L->next;  // 当前结点（从第一个有效结点开始）LinkNode* q = nullptr;  // 后继结点L->next = nullptr;      // 头结点的指针域置空while (p != nullptr) {q = p->next;        // 保存后继结点p->next = L->next;  // 将当前结点插入到头结点之后L->next = p;        // 更新头结点的指针域p = q;              // 当前结点后移}
}// 输出链表
void Displist(LinkNode* L) {LinkNode* p = L->next;  // 从第一个有效结点开始while (p != nullptr) {cout << p->data << " ";p = p->next;}cout << endl;
}// 销毁链表
void DestroyList(LinkNode*& L) {LinkNode* p = L;while (p != nullptr) {LinkNode* temp = p;p = p->next;delete temp;  // 释放结点内存}L = nullptr;  // 头指针置空
}int main() {LinkNode* L = nullptr;  // 链表头指针int n;cout << "请输入链表的初始元素个数：";cin >> n;if (n <= 0) {cout << "输入的元素个数无效！" << endl;return 0;}// 创建链表CreateList(L, n);// 输出原始链表cout << "原始链表: ";Displist(L);// 逆置链表Reverse(L);// 输出逆置后的链表cout << "逆置后的链表: ";Displist(L);// 销毁链表DestroyList(L);return 0;
}

第十三题：

#include <bits/stdc++.h>
using namespace std;
typedef int ElemType;  
typedef struct LinkNode {ElemType data;             struct LinkNode* next;     
} LinkNode;
// 创建链表
void CreateList(LinkNode*& L, int n) {L = new LinkNode();  L->next = nullptr;   LinkNode* tail = L;  cout << "请输入" << n << "个整数：" << endl;for (int i = 0; i < n; i++) {LinkNode* newNode = new LinkNode(); cin >> newNode->data;newNode->next = nullptr;tail->next = newNode; tail = newNode;      }
}
// 找到链表的中间元素
ElemType zhongjian(LinkNode* L) {if (L == nullptr || L->next == nullptr) {return -1;  }LinkNode*p=L->next,*q=p;while (p->next!=NULL && p->next->next!=NULL){p=p->next->next;q=q->next;}return q->data;  
}
// 输出链表
void Displist(LinkNode* L) {LinkNode* p = L->next;  while (p != nullptr) {cout << p->data << " ";p = p->next;}cout << endl;
}
// 销毁链表
void DestroyList(LinkNode*& L) {LinkNode* p = L;while (p != nullptr) {LinkNode* temp = p;p = p->next;delete temp;  }L = nullptr;  
}
int main() {LinkNode* L = nullptr; int n;cout << "请输入链表的初始元素个数：";cin >> n;if (n <= 0) {cout << "输入的元素个数无效！" << endl;return 0;}CreateList(L, n);cout << "原始链表: ";Displist(L);ElemType mid = zhongjian(L);if (mid != -1) {cout << "中间位置元素: " << mid << endl;} else {cout << "链表为空或只有一个元素，无法找到中间位置！" << endl;}DestroyList(L);return 0;
}

第十四题：

#include <bits/stdc++.h>
using namespace std;typedef int ElemType;  // 定义元素类型为inttypedef struct LinkNode {ElemType data;              // 数据域struct LinkNode* next;      // 指针域
} LinkNode;// 创建链表
void CreateList(LinkNode*& L, int n) {L = new LinkNode();  // 创建头结点L->next = nullptr;   // 初始化为空链表LinkNode* tail = L;  // 尾指针，初始指向头结点cout << "请输入" << n << "个整数：" << endl;for (int i = 0; i < n; i++) {LinkNode* newNode = new LinkNode();  // 创建新结点cin >> newNode->data;newNode->next = nullptr;tail->next = newNode;  // 将新结点插入链表尾部tail = newNode;        // 更新尾指针}
}// 在第一个最大值结点之前插入值为x的结点
void InsertBeforeMax(LinkNode*& L, ElemType x) {if (L == nullptr || L->next == nullptr) {cout << "链表为空，无法插入！" << endl;return;}LinkNode* p = L->next;  // 当前结点（从第一个有效结点开始）LinkNode* prev = L;     // 前驱结点（初始指向头结点）ElemType maxVal = p->data;  // 最大值初始化为第一个结点的值LinkNode* maxPrev = L;  // 最大值结点的前驱结点// 找到第一个最大值结点及其前驱结点while (p != nullptr) {if (p->data > maxVal) {maxVal = p->data;maxPrev = prev;}prev = p;p = p->next;}// 在最大值结点之前插入新结点LinkNode* newNode = new LinkNode();newNode->data = x;newNode->next = maxPrev->next;maxPrev->next = newNode;
}// 输出链表
void Displist(LinkNode* L) {LinkNode* p = L->next;  // 从第一个有效结点开始while (p != nullptr) {cout << p->data << " ";p = p->next;}cout << endl;
}// 销毁链表
void DestroyList(LinkNode*& L) {LinkNode* p = L;while (p != nullptr) {LinkNode* temp = p;p = p->next;delete temp;  // 释放结点内存}L = nullptr;  // 头指针置空
}int main() {LinkNode* L = nullptr;  // 链表头指针int n;cout << "请输入链表的初始元素个数：";cin >> n;if (n <= 0) {cout << "输入的元素个数无效！" << endl;return 0;}// 创建链表CreateList(L, n);// 输出原始链表cout << "原始链表: ";Displist(L);// 插入值为x的结点ElemType x;cout << "请输入要插入的值x: ";cin >> x;InsertBeforeMax(L, x);// 输出插入后的链表cout << "插入后的链表: ";Displist(L);// 销毁链表DestroyList(L);return 0;
}

第十七题：

#include <bits/stdc++.h>
using namespace std;typedef int ElemType;  // 定义元素类型为inttypedef struct LinkNode {ElemType data;              // 数据域struct LinkNode* next;      // 指针域
} LinkNode;// 创建链表
void CreateList(LinkNode*& L, int n) {L = new LinkNode();  // 创建头结点L->next = nullptr;   // 初始化为空链表LinkNode* tail = L;  // 尾指针，初始指向头结点cout << "请输入" << n << "个整数：" << endl;for (int i = 0; i < n; i++) {LinkNode* newNode = new LinkNode();  // 创建新结点cin >> newNode->data;newNode->next = nullptr;tail->next = newNode;  // 将新结点插入链表尾部tail = newNode;        // 更新尾指针}
}// 合并两个单链表
void Merge(LinkNode* ha, LinkNode* hb, LinkNode*& hc) {hc = ha;  // hc 指向 ha 的头结点LinkNode* p = ha->next;  // p 指向 ha 的第一个有效结点LinkNode* q = hb->next;  // q 指向 hb 的第一个有效结点// 找到 ha 的尾结点while (p->next != nullptr) {p = p->next;}// 将 hb 的结点连接到 ha 的尾部p->next = q;// 释放 hb 的头结点delete hb;hb = nullptr;
}// 输出链表
void Displist(LinkNode* L) {LinkNode* p = L->next;  // 从第一个有效结点开始while (p != nullptr) {cout << p->data << " ";p = p->next;}cout << endl;
}// 销毁链表
void DestroyList(LinkNode*& L) {LinkNode* p = L;while (p != nullptr) {LinkNode* temp = p;p = p->next;delete temp;  // 释放结点内存}L = nullptr;  // 头指针置空
}int main() {LinkNode* ha = nullptr;  // 链表 ha 的头指针LinkNode* hb = nullptr;  // 链表 hb 的头指针LinkNode* hc = nullptr;  // 合并后的链表 hc 的头指针int n1, n2;cout << "请输入链表 ha 的初始元素个数：";cin >> n1;if (n1 <= 0) {cout << "输入的元素个数无效！" << endl;return 0;}CreateList(ha, n1);  // 创建链表 hacout << "请输入链表 hb 的初始元素个数：";cin >> n2;if (n2 <= 0) {cout << "输入的元素个数无效！" << endl;return 0;}CreateList(hb, n2);  // 创建链表 hb// 输出原始链表cout << "链表 ha: ";Displist(ha);cout << "链表 hb: ";Displist(hb);// 合并链表Merge(ha, hb, hc);// 输出合并后的链表cout << "合并后的链表 hc: ";Displist(hc);// 销毁链表DestroyList(hc);return 0;
}

第十八题：

#include <bits/stdc++.h>
using namespace std;typedef int ElemType;  // 定义元素类型为int// 定义双向链表结点结构
typedef struct DLinkNode {ElemType data;              // 数据域struct DLinkNode* prev;     // 前驱指针struct DLinkNode* next;     // 后继指针
} DLinkNode;// 创建循环双链表
void CreateList(DLinkNode*& head, int n) {head = new DLinkNode();  // 创建头结点head->prev = head;       // 头结点的前驱指向自己head->next = head;       // 头结点的后继指向自己DLinkNode* tail = head;  // 尾指针，初始指向头结点cout << "请输入" << n << "个整数：" << endl;for (int i = 0; i < n; i++) {DLinkNode* newNode = new DLinkNode();  // 创建新结点cin >> newNode->data;newNode->prev = tail;  // 新结点的前驱指向尾结点newNode->next = head;  // 新结点的后继指向头结点tail->next = newNode;  // 尾结点的后继指向新结点head->prev = newNode;  // 头结点的前驱指向新结点tail = newNode;        // 更新尾指针}
}// 插入算法
void Insert(DLinkNode*& ha, DLinkNode*& hb, int i) {if (ha == nullptr || hb == nullptr) {cout << "链表为空，无法插入！" << endl;return;}DLinkNode* p = ha->next;  // 当前结点（从第一个有效结点开始）int count = 1;            // 计数器，用于找到第 i 个结点// 找到第 i 个结点while (p != ha && count < i) {p = p->next;count++;}if (i == 0) {// 将 hb 插入到 ha 的前面DLinkNode* hbTail = hb->prev;  // hb 的尾结点hbTail->next = ha->next;       // hb 的尾结点指向 ha 的第一个有效结点ha->next->prev = hbTail;       // ha 的第一个有效结点的前驱指向 hb 的尾结点ha->next = hb->next;           // ha 的头结点指向 hb 的第一个有效结点hb->next->prev = ha;           // hb 的第一个有效结点的前驱指向 ha 的头结点} else if (p != ha) {// 将 hb 插入到 ha 的第 i 个结点后面DLinkNode* hbTail = hb->prev;  // hb 的尾结点hbTail->next = p->next;        // hb 的尾结点指向 p 的后继结点p->next->prev = hbTail;        // p 的后继结点的前驱指向 hb 的尾结点p->next = hb->next;            // p 的后继指向 hb 的第一个有效结点hb->next->prev = p;            // hb 的第一个有效结点的前驱指向 p} else {// 将 hb 插入到 ha 的后面DLinkNode* haTail = ha->prev;  // ha 的尾结点haTail->next = hb->next;       // ha 的尾结点指向 hb 的第一个有效结点hb->next->prev = haTail;       // hb 的第一个有效结点的前驱指向 ha 的尾结点hb->prev->next = ha;           // hb 的尾结点指向 ha 的头结点ha->prev = hb->prev;           // ha 的头结点的前驱指向 hb 的尾结点}// 释放 hb 的头结点delete hb;hb = nullptr;
}// 输出循环双链表
void Displist(DLinkNode* head) {if (head == nullptr || head->next == head) {cout << "链表为空！" << endl;return;}DLinkNode* p = head->next;  // 从第一个有效结点开始while (p != head) {cout << p->data << " ";p = p->next;}cout << endl;
}// 销毁循环双链表
void DestroyList(DLinkNode*& head) {if (head == nullptr) {return;}DLinkNode* p = head->next;  // 从第一个有效结点开始while (p != head) {DLinkNode* temp = p;p = p->next;delete temp;  // 释放结点内存}delete head;  // 释放头结点head = nullptr;
}int main() {DLinkNode* ha = nullptr;  // 链表 ha 的头指针DLinkNode* hb = nullptr;  // 链表 hb 的头指针int n1, n2;cout << "请输入链表 ha 的初始元素个数：";cin >> n1;if (n1 <= 0) {cout << "输入的元素个数无效！" << endl;return 0;}CreateList(ha, n1);  // 创建链表 hacout << "请输入链表 hb 的初始元素个数：";cin >> n2;if (n2 <= 0) {cout << "输入的元素个数无效！" << endl;return 0;}CreateList(hb, n2);  // 创建链表 hb// 输出原始链表cout << "链表 ha: ";Displist(ha);cout << "链表 hb: ";Displist(hb);int i;cout << "请输入插入位置 i: ";cin >> i;// 插入链表 hbInsert(ha, hb, i);// 输出插入后的链表cout << "插入后的链表 ha: ";Displist(ha);// 销毁链表DestroyList(ha);return 0;
}

实验题2实验5

#include "cdlinklist.cpp"
int main() {DLinkNode *h;ElemType e;cout<<"双链表的基本运算如下："<<endl;cout<<"（1）初始化单链表h"<<endl;InitList(h);cout<<"（2）依次采用尾插法插入a,b,c,d,e元素"<<endl;ListInsert(h,1,'a');ListInsert(h,2,'b');ListInsert(h,3,'c');ListInsert(h,4,'d');ListInsert(h,5,'e');cout<<"（3）输出双链表h:";DisList(h);printf("（4）双链表h长度：%d\n",ListLength(h));printf("（5）双链表h为%s\n",(ListEmpty(h))?"空":"非空")；GetElem(h,3,e);printf("（6）双链表h的第3个元素:%c\n",e);printf("（7）元素a的位置：%d\n",LocateElem(h,'a'));printf("（8）在第4个元素位置上插入f元素\n");ListInsert(h,4,'f');cout<<"（9）输出双链表h：";ListInsert(h);cout<<"（10）删除h的第3个元素\n";ListDelete(h,3,e);cout<<"（11）输出双链表h：";DisList(h);cout<<"（12）释放双链表h:\n";DestroyList(h);return 1;
}

实验6

#include <iostream>
using namespace std;typedef struct LinkNode {int data;struct LinkNode* next;
} LinkNode;// 创建单链表
void CreateList(LinkNode*& L, int a[], int n) {L = new LinkNode();  // 头结点L->next = nullptr;LinkNode* tail = L;for (int i = 0; i < n; i++) {LinkNode* newNode = new LinkNode();newNode->data = a[i];newNode->next = nullptr;tail->next = newNode;tail = newNode;}
}// 按基准值x划分单链表
void Partition(LinkNode*& L, int x) {if (L->next == nullptr || L->next->next == nullptr) return;LinkNode* lessHead = new LinkNode();  // 小于x的链表头LinkNode* greaterHead = new LinkNode();  // 大于等于x的链表头LinkNode* lessTail = lessHead, *greaterTail = greaterHead;LinkNode* p = L->next;while (p != nullptr) {if (p->data < x) {lessTail->next = p;lessTail = p;} else {greaterTail->next = p;greaterTail = p;}p = p->next;}// 合并两个链表lessTail->next = greaterHead->next;greaterTail->next = nullptr;L->next = lessHead->next;// 释放临时头结点delete lessHead;delete greaterHead;
}// 输出链表
void Displist(LinkNode* L) {LinkNode* p = L->next;while (p != nullptr) {cout << p->data << " ";p = p->next;}cout << endl;
}// 销毁链表
void DestroyList(LinkNode*& L) {LinkNode* p = L;while (p != nullptr) {LinkNode* temp = p;p = p->next;delete temp;}L = nullptr;
}int main() {LinkNode* L;int a[] = {3, 5, 8, 5, 10, 2, 1};int n = sizeof(a) / sizeof(a[0]);int x = 5;  // 基准值CreateList(L, a, n);cout << "原始链表: ";Displist(L);Partition(L, x);cout << "划分后链表: ";Displist(L);DestroyList(L);return 0;
}