关于电商平台_有意思的网站_营销型网站建设步骤_最新seo网站优化教程

链表

设计链表

#include <iostream>
using namespace std;struct linknode
{int val;linknode* next;linknode(int val):val(val),next(NULL){};
};
linknode* _dummyhead;// 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
int _size;//链表的大小//初始化链表 
void init()
{_dummyhead=new linknode(0);_size=0;
}//获取第index个节点的值 ,如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
int get(int index)
{if(index>=_size||index<0){return -1;}linknode* cur=_dummyhead->next;while(index--){cur=cur->next;}return cur->val;
}// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
void addh(int val)
{linknode *newnode=new linknode(val);newnode->next=_dummyhead->next;_dummyhead->next=newnode;_size++;
} // 在链表最后面添加一个节点
void adde(int val)
{linknode* newnode =new linknode(val);linknode* cur=_dummyhead;while(cur->next!=NULL){cur=cur->next;}cur->next=newnode;_size++;
} // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果index大于链表的长度，则返回空
// 如果index小于0，则在头部插入节点
void addi(int index,int val)
{if(index>_size)return;if(index<0)index=0;linknode* newnode=new linknode(val);linknode* cur=_dummyhead;while(index--){cur=cur->next;} newnode->next=cur->next;cur->next=newnode;_size++;
}//删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
void deletei(int index)
{if(index>=_size||index<0){return ;}linknode* cur = _dummyhead;while (index--) {cur = cur->next;}linknode* tmp=cur->next;cur->next=cur->next->next;delete tmp;tmp=NULL;_size--;
}//打印链表 
void printlist()
{linknode* cur=_dummyhead;while(cur->next!=NULL){cout<<cur->next->val<<" ";cur=cur->next;}cout<<endl;
}
int main()
{return 0;
}

1.进制转换

1.设计一个算法，用带头结点的单链表实现非负十进制整数转二进制数。

思路：通过头插法这样我们在进行进制转换时就不用reverse了

#include <iostream>
using namespace std;
struct linknode
{int digit;  // 存储二进制的每一位linknode* next;linknode(int digit) :digit(digit), next(NULL) {}
};
linknode* _dummyhead=new linknode(0);//虚拟头节点
// 十进制数转二进制数的函数
void transform(int n)
{if (n < 0){cout << 0;return;}while (n>0){int remainder = n % 2;//获取余数linknode* newnode = new linknode(remainder);newnode->next = _dummyhead->next;_dummyhead->next = newnode;n /= 2;}
}
// 输出链表的内容（即二进制位）
void print()
{linknode* cur = _dummyhead;while (cur->next !=NULL){cur = cur->next;cout << cur->digit;}
}
int main()
{int n;cin >> n;transform(n);print();return 0;
}

2.顺序表逆置

2.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为 O(1)。

#include <iostream>
using namespace std;
#define MAXLEN 100
typedef int datatype;
// 顺序表结构定义
struct seqlist 
{datatype data[MAXLEN];  // 存储顺序表的元素int Length;             // 顺序表的当前长度
};
// 逆置顺序表的函数
void reverseList(seqlist& L) 
{int left = 0;                // 左指针，指向顺序表的开始int right = L.Length - 1;    // 右指针，指向顺序表的末尾while (left < right) {// 交换L.data[left]和L.data[right]swap(L.data[left], L.data[right]);// 移动指针left++;right--;}
}
// 打印顺序表的函数
void printList(const seqlist& L) 
{for (int i = 0; i < L.Length; i++) {cout << L.data[i] << " ";}cout << endl;
}
int main() 
{seqlist L = { {1, 2, 3, 4, 5}, 5 };  // 顺序表元素为1, 2, 3, 4, 5，长度为5cout << "原顺序表：";printList(L);  // 输出原顺序表reverseList(L);  // 逆置顺序表cout << "逆置后的顺序表：";printList(L);  // 输出逆置后的顺序表return 0;
}

3.链表转置

思路：
首先定义一个cur指针，指向虚拟头结点的下一个节点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们_dummyhead->next = pre; 就可以了，pre指针就指向了新的头结点。

#include <iostream>
using namespace std;
struct linknode
{int val;  linknode* next;linknode(int val) :val(val), next(NULL) {}
};
linknode* _dummyhead = new linknode(0);//虚拟头节点
// 在链表尾插入节点
void adde(int val)
{linknode* newnode = new linknode(val);linknode* cur =_dummyhead;while (cur->next != NULL){cur = cur->next;}cur->next = newnode;newnode->next = NULL;
}
void reverselist()
{linknode* cur = _dummyhead->next;linknode* temp; // 保存cur的下一个节点linknode* pre = NULL;while (cur!=NULL){temp = cur->next;// 保存一下 cur的下一个节点，因为接下来要改变cur->nextcur->next = pre;// 翻转操作// 更新pre 和 cur指针pre = cur; cur = temp;}_dummyhead->next = pre;  // 将头结点的next指向反转后的链表头
}
// 打印链表
void print() 
{linknode* cur = _dummyhead;while (cur->next != NULL) {cout << cur->next->val << " ";cur = cur->next;}cout << endl;
}
int main()
{adde(1);adde(2);adde(3);adde(4);adde(5);// 输出原链表cout << "原链表: ";print();// 逆置链表reverselist();// 输出逆置后的链表cout << "逆置后的链表: ";print();return 0;
}

栈

栈的实现

#include <iostream>using namespace std;const int N = 100;
// 假设栈的初始化、入栈、出栈和栈空判断等基本操作已经实现// 栈的结构定义
struct seqstack {int data[N];  // 栈的存储空间int top;        // 栈顶指针
};// 初始化栈
void init(seqstack* s) {s->top = -1;
}// 入栈操作
void push(seqstack* s, int x) {if (s->top < N) {  // 防止栈溢出s->top++;s->data[s->top] = x;}
}// 出栈操作
bool pop(seqstack* s, int& x) {if (s->top == -1) return false;  // 栈为空，无法出栈x = s->data[s->top];s->top--;return true;
}// 栈空判断
bool empty(seqstack* s) {return s->top == -1;
}// 非负十进制整数转八进制数
void transform(int n) {seqstack s;init(&s);// 特殊情况：如果n为0，直接输出0if (n == 0) {cout << 0 << endl;return;}// 进行转换while (n > 0) {push(&s, n % 8);  // 余数入栈n = n / 8;        // 更新n为商}// 弹出栈内元素并输出，得到八进制数while (!empty(&s)) {int digit;pop(&s, digit);cout << digit;}cout << endl;
}int main() {int decimalNum;cout << "请输入一个非负十进制整数: ";cin >> decimalNum;cout << "该整数的八进制表示为: ";transform(decimalNum);return 0;
}

队列

队列实现

#include <iostream>
using namespace std;#define maxsize 50
typedef int datatype;typedef struct {datatype data[maxsize];int front;int rear;
} sqqueue;// 初始化队列
void initque(sqqueue &q) {q.rear = q.front = 0;
}// 判断队列是否为空
bool isempty(sqqueue &q) {return q.front == q.rear;
}// 入队操作
bool enqueue(sqqueue &q, datatype x) {if ((q.rear + 1) % maxsize == q.front) {return false; // 队列满}q.data[q.rear] = x;q.rear = (q.rear + 1) % maxsize;return true;
}// 出队操作
bool dequeue(sqqueue &q, datatype &x) {if (isempty(q)) {return false; // 队列空}x = q.data[q.front];q.front = (q.front + 1) % maxsize;return true;
}// 获取队列大小
int que_size(sqqueue &q) {return (q.rear + maxsize - q.front) % maxsize;
}// 显示队列内容
void showqueue(sqqueue &q) {int p = q.front;if (isempty(q)) {cout << "队空" << endl;return;}while (p != q.rear) {cout << q.data[p] << " ";p = (p + 1) % maxsize;}cout << endl;
}int main() {sqqueue Q;initque(Q);int n;cin >> n; // 输入命令的数量while (n--) {int command, x;cin >> command; // 输入命令类型switch (command) {case 1:  // 入队操作cin >> x;if (!enqueue(Q, x)) {cout << "队列满" << endl;  // 队列满时输出提示}break;case 2:  // 出队操作if (dequeue(Q, x)) {cout << x << endl;  // 输出出队的元素} else {cout << "no" << endl;  // 队列为空时输出提示}break;case 3:  // 查询队列大小cout << que_size(Q) << endl;break;}}return 0;
}

1.逆置队列

#include <iostream>
#include <stack>using namespace std;#define MAXSIZe 50  // 队列最大容量// 队列的定义
typedef struct {int data[MAXSIZe];int front, rear;
} Queue;// 栈的定义
typedef stack<int> Stack;// 初始化队列
void init(Queue& q) {q.front = q.rear = 0;
}// 判断队列是否为空
bool isempty(Queue& q) {return q.front == q.rear;
}// 判断队列是否满
bool isfull(Queue& q) {return (q.rear + 1) % MAXSIZe == q.front;
}// 入队
bool enqueue(Queue& q, int value) {if (isfull(q)) {return false;  // 队列满}q.data[q.rear] = value;q.rear = (q.rear + 1) % MAXSIZe;return true;
}// 出队
bool dequeue(Queue& q, int& value) {if (isempty(q)) {return false;  // 队列空}value = q.data[q.front];q.front = (q.front + 1) % MAXSIZe;return true;
}// 获取队列大小
int queuesize(Queue& q) {return (q.rear - q.front + MAXSIZe) % MAXSIZe;
}// 显示队列
void showQueue(Queue& q) {if (isempty(q)) {cout << "队列为空" << endl;return;}int i = q.front;while (i != q.rear) {cout << q.data[i] << " ";i = (i + 1) % MAXSIZe;}cout << endl;
}// 逆置队列
void reversequeue(Queue& q) {Stack s;int temp;// Step 1: 将队列中的所有元素压入栈while (!isempty(q)) {dequeue(q, temp);s.push(temp);}// Step 2: 将栈中的元素重新入队while (!s.empty()) {enqueue(q, s.top());s.pop();}
}int main() {Queue q;init(q);// 向队列中添加元素enqueue(q, 1);enqueue(q, 2);enqueue(q, 3);enqueue(q, 4);enqueue(q, 5);// 显示队列cout << "原队列： ";showQueue(q);// 逆置队列reversequeue(q);// 显示逆置后的队列cout << "逆置后的队列： ";showQueue(q);return 0;
}

二叉树

遍历顺序

#include <iostream>
#include <queue>
using namespace std;struct treenode 
{int val;treenode* left;treenode* right;treenode(int x) : val(x), left(NULL), right(NULL) {}
};void preorder(treenode* cur)//前序遍历
{if (cur == NULL)return;cout << cur->val;preorder(cur->left);preorder(cur->right);
}void inorder(treenode* cur)//中序遍历
{if (cur == NULL) return;inorder(cur->left);cout << cur->val;inorder(cur->right);
}void postorder(treenode* cur)//后序遍历
{if (cur == NULL)return;postorder(cur->left);postorder(cur->right);cout << cur->val;
}// 层序遍历（广度优先遍历）
void levelOrder(treenode* root) 
{if (root == NULL) return;queue<treenode*> q;  // 创建一个队列q.push(root);  // 将根节点入队while (!q.empty()) {treenode* cur = q.front();  // 访问队头元素q.pop();  // 出队cout << cur->val << " ";  // 访问节点// 将左子节点和右子节点入队if (cur->left) q.push(cur->left);if (cur->right) q.push(cur->right);}
}int main()
{return 0;
}

1.树的深度

编写一个递归算法，实现的功能是：求二叉树的深度并返回。有如下二叉树的存储结构：
typedef struct tnode
{DataType   data;   //结点数据域 struct  tnode  *lchild,*rchild; //左右孩子指针
}BTree; 
该函数原型说明为：int TreeDepth(BTree *T); //T是二叉树

函数

// 递归函数：计算二叉树的深度
int treeDepth(BTree *T) {if (T == NULL) {return 0;  // 空树的深度是 0}// 递归计算左子树和右子树的深度int leftDepth = treeDepth(T->lchild);int rightDepth = treeDepth(T->rchild);// 返回左右子树深度的较大值加 1return max(leftDepth, rightDepth) + 1;
}

完整代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;struct treenode
{int val;treenode* left;treenode* right;treenode(int x):val(x), left(NULL), right(NULL) {}
};
void preorder(treenode* cur)//前序遍历
{if (cur == NULL)return;cout << cur->val;preorder(cur->left);preorder(cur->right);
}void inorder(treenode* cur)//中序遍历
{if (cur == NULL)return;inorder(cur->left);cout << cur->val;inorder(cur->right);
}void postorder(treenode* cur)//后序遍历
{if (cur == NULL)return;postorder(cur->left);postorder(cur->right);cout << cur->val;
}// 层序遍历（广度优先遍历）
void levelOrder(treenode* root)
{if (root == NULL){return;}queue<treenode*> q;q.push(root);while (!q.empty()){treenode* cur = q.front();q.pop();cout << cur->val << " ";if (cur->left)q.push(cur->left);if (cur->right)q.push(cur->right);}
}int treedepth(treenode* root)
{if (root == NULL)return 0;// 空树的深度是 0// 递归计算左子树和右子树的深度int leftdepth = treedepth(root->left);int rightdepth = treedepth(root->right);// 返回左右子树深度的较大值加 1return max(leftdepth, rightdepth) + 1;
}
int main()
{// 创建一个简单的二叉树//         1//       /   \//      2     3//     / \   / \//    4   5 6   7treenode* root = new treenode(1);root->left = new treenode(2);root->right = new treenode(3);root->left->left = new treenode(4);root->left->right = new treenode(5);root->right->left = new treenode(6);root->right->right = new treenode(7);cout << "层序遍历的结果为: ";levelOrder(root);cout << endl;cout << "树的深度是：" << treedepth(root);return 0;
}

2.左右子树交换

编写一个递归算法，实现的功能是：将二叉树中的每一个结点的左子树和右子树互换。有如下二叉树的存储结构：
typedef struct tnode
{DataType   data;   //结点数据域 struct  tnode  *lchild,*rchild; //左右孩子指针
}BTree; 
该函数原型说明为：void exchange(BTree *T);

函数

// 递归函数：交换二叉树的每个节点的左右子树
void exchange(BTree *T) {if (T == NULL) {return;  // 如果节点为空，直接返回}// 交换当前节点的左右子树BTree *temp = T->lchild;T->lchild = T->rchild;T->rchild = temp;// 递归交换左右子树exchange(T->lchild);exchange(T->rchild);
}

完整代码

#include <iostream>
#include <queue>
using namespace std;struct treenode
{int val;treenode* left;treenode* right;treenode(int x):val(x), left(NULL), right(NULL) {}
};
void preorder(treenode* cur)//前序遍历
{if (cur == NULL)return;cout << cur->val;preorder(cur->left);preorder(cur->right);
}void inorder(treenode* cur)//中序遍历
{if (cur == NULL)return;inorder(cur->left);cout << cur->val;inorder(cur->right);
}void postorder(treenode* cur)//后序遍历
{if (cur == NULL)return;postorder(cur->left);postorder(cur->right);cout << cur->val;
}// 层序遍历（广度优先遍历）
void levelOrder(treenode* root)
{if (root == NULL){return;}queue<treenode*> q;q.push(root);while (!q.empty()){treenode* cur = q.front();q.pop();cout << cur->val << " ";if (cur->left)q.push(cur->left);if (cur->right)q.push(cur->right);}
}
void exchange(treenode* root)
{if (root == NULL)return;// 交换当前节点的左右子树treenode* temp = root->left;root->left = root->right;root->right = temp;// 递归交换左子树和右子树exchange(root->left);exchange(root->right);
}int main()
{// 创建一个简单的二叉树//         1//       /   \//      2     3//     / \   / \//    4   5 6   7treenode* root = new treenode(1);root->left = new treenode(2);root->right = new treenode(3);root->left->left = new treenode(4);root->left->right = new treenode(5);root->right->left = new treenode(6);root->right->right = new treenode(7);cout << "层序遍历的结果为: ";levelOrder(root);cout << endl;// 交换左右子树exchange(root);cout << "交换左右子树后层序遍历的结果为: ";levelOrder(root);cout << endl;//      1//     / \//    3   2//   / \ / \//  7  6 5  4return 0;
}

3.输出并求出非叶子节点个数

编写一个算法，实现的功能是：输出二叉树中所有非叶子结点，并求出非叶子结点的个数返回。有如下二叉树的存储结构：
typedef char DataType ;
typedef struct tnode
{DataType   data;   //结点数据域 struct  tnode  *lchild,*rchild; //左右孩子指针
}BTree; 
该函数原型说明为：int Nonleafnum(BTree *T);  //T是二叉树

函数

// 递归函数：计算并输出二叉树中的所有非叶子节点
int Nonleafnum(BTree *T) {if (T == NULL) {return 0;  // 空树没有非叶子节点}int count = 0;// 判断当前节点是否是非叶子节点if (T->lchild != NULL || T->rchild != NULL) {cout << T->data << " ";  // 输出非叶子结点count = 1;  // 当前结点是非叶子节点，计数为 1}// 递归计算左子树和右子树的非叶子结点数count += Nonleafnum(T->lchild);count += Nonleafnum(T->rchild);return count;  // 返回非叶子结点的总数
}

完整代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;struct treenode {int val;treenode* left;treenode* right;treenode(int x) : val(x), left(NULL), right(NULL) {}
};// 前序遍历
void preorder(treenode* cur) {if (cur == NULL) return;cout << cur->val << " ";preorder(cur->left);preorder(cur->right);
}// 中序遍历
void inorder(treenode* cur) {if (cur == NULL) return;inorder(cur->left);cout << cur->val << " ";inorder(cur->right);
}// 后序遍历
void postorder(treenode* cur) {if (cur == NULL) return;postorder(cur->left);postorder(cur->right);cout << cur->val << " ";
}// 层序遍历（广度优先遍历）
void levelOrder(treenode* root) {if (root == NULL) {return;}queue<treenode*> q;q.push(root);while (!q.empty()) {treenode* cur = q.front();q.pop();cout << cur->val << " ";if (cur->left) q.push(cur->left);if (cur->right) q.push(cur->right);}
}// 求非叶子节点个数的函数
int Nonleafnum(treenode* T) {if (T == NULL) return 0;  // 空树没有非叶子节点int count = 0;// 判断当前节点是否是非叶子节点if (T->left != NULL || T->right != NULL) {count = 1;  // 当前节点是非叶子节点，计数为 1}// 递归计算左子树和右子树的非叶子节点数count += Nonleafnum(T->left);count += Nonleafnum(T->right);return count;  // 返回非叶子节点的总数
}int main() {// 创建一个简单的二叉树//         1//       /   \//      2     3//     / \   / \//    4   5 6   7treenode* root = new treenode(1);root->left = new treenode(2);root->right = new treenode(3);root->left->left = new treenode(4);root->left->right = new treenode(5);root->right->left = new treenode(6);root->right->right = new treenode(7);// 层序遍历的结果cout << "层序遍历的结果为: ";levelOrder(root);cout << endl;// 输出非叶子节点个数int nonLeafCount = Nonleafnum(root);cout << "非叶子节点的个数是: " << nonLeafCount << endl;return 0;
}

图

1.邻接矩阵转换成临界表

1. 编写一个算法，实现的功能是：将无权无向图的邻接矩阵转换成邻接表。
有如下存储结构：
#define MAX 100 
typedef  struct 
{int  n,e;        //顶点数、边数 char  vexs[MAX];      //顶点数组 int  edges[MAX][MAX]; //边的邻接矩阵
}MGraph;    //图的邻接矩阵类型 typedef char VertexType ;
typedef  struct  node   //定义边表结点 
{int adjvex;   //邻接点域 struct node  *next; //指向下一个邻接点的指针域 
}EdgeNode;    //边表类型
typedef  struct  vexnode //定义顶点表结点 
{VertexType  data;  //顶点域 EdgeNode *firstedge;  //指向第一条边结点的指针域 
}VHeadNode;    //邻接表结点类型 
typedef  struct
{VHeadNode  adjlist[MAX];  //邻接表结点数组 int  n,e;    //顶点数、边数 
}AdjList;    //图的邻接表类型 该函数原型说明为：AdjList *MatToList(MGraph g)  
//g是邻接矩阵，返回一个邻接表

函数

// 将邻接矩阵转换为邻接表
AdjList* MatToList(MGraph g) 
{int i, j;// 动态分配邻接表内存AdjList* adjlist = new AdjList;adjlist->n = g.n;adjlist->e = g.e;// 初始化邻接表的顶点数据和边表for (i = 0; i < g.n; i++) {adjlist->adjlist[i].data = g.vexs[i];adjlist->adjlist[i].firstedge = NULL; // 初始化每个顶点的边表为空}// 遍历邻接矩阵，填充邻接表for (i = 0; i < g.n; i++) {for (j = i + 1; j < g.n; j++) { // 修改此处，j从i+1开始，确保只插入一次边if (g.edges[i][j] == 1) {// 插入的边从 i 到 jEdgeNode* newEdge = new EdgeNode;newEdge->adjvex = j;newEdge->next = adjlist->adjlist[i].firstedge;adjlist->adjlist[i].firstedge = newEdge;// 插入的边从 j 到 iEdgeNode* newEdgeRev = new EdgeNode;newEdgeRev->adjvex = i;newEdgeRev->next = adjlist->adjlist[j].firstedge;adjlist->adjlist[j].firstedge = newEdgeRev;}}}return adjlist;
}

完整代码

#include <iostream>
using namespace std;#define MAX 100
typedef struct 
{int n, e;        // 顶点数、边数 char vexs[MAX];  // 顶点数组 int edges[MAX][MAX]; // 邻接矩阵
} MGraph; // 图的邻接矩阵类型 typedef char VertexType;typedef struct node 
{ // 定义边表结点 int adjvex;      // 邻接点域 struct node* next; // 指向下一个邻接点的指针域 
} EdgeNode; // 边表类型typedef struct vexnode { // 定义顶点表结点 VertexType data;     // 顶点域 EdgeNode* firstedge; // 指向第一条边结点的指针域 
} VHeadNode; // 邻接表结点类型 typedef struct 
{VHeadNode adjlist[MAX]; // 邻接表结点数组 int n, e; // 顶点数、边数 
} AdjList; // 图的邻接表类型 // 将邻接矩阵转换为邻接表
AdjList* MatToList(MGraph g) 
{int i, j;// 动态分配邻接表内存AdjList* adjlist = new AdjList;adjlist->n = g.n;adjlist->e = g.e;// 初始化邻接表的顶点数据和边表for (i = 0; i < g.n; i++) {adjlist->adjlist[i].data = g.vexs[i];adjlist->adjlist[i].firstedge = NULL; // 初始化每个顶点的边表为空}// 遍历邻接矩阵，填充邻接表for (i = 0; i < g.n; i++) {for (j = i + 1; j < g.n; j++) { // 修改此处，j从i+1开始，确保只插入一次边if (g.edges[i][j] == 1) {// 插入的边从 i 到 jEdgeNode* newEdge = new EdgeNode;newEdge->adjvex = j;newEdge->next = adjlist->adjlist[i].firstedge;adjlist->adjlist[i].firstedge = newEdge;// 插入的边从 j 到 iEdgeNode* newEdgeRev = new EdgeNode;newEdgeRev->adjvex = i;newEdgeRev->next = adjlist->adjlist[j].firstedge;adjlist->adjlist[j].firstedge = newEdgeRev;}}}return adjlist;
}// 打印邻接表
void printAdjList(AdjList* adjList) 
{for (int i = 0; i < adjList->n; i++) {cout << adjList->adjlist[i].data << ": "; // 打印顶点EdgeNode* p = adjList->adjlist[i].firstedge;while (p != NULL) {cout << adjList->adjlist[p->adjvex].data << " "; // 打印邻接点p = p->next;}cout << endl;}
}int main() 
{MGraph g = {5, 6,{'A', 'B', 'C', 'D', 'E'},{{0, 1, 0, 1, 0},{1, 0, 1, 0, 1},{0, 1, 0, 1, 1},{1, 0, 1, 0, 0},{0, 1, 1, 0, 0}}};// 调用函数转换邻接矩阵为邻接表AdjList* adjList = MatToList(g);// 打印邻接表printAdjList(adjList);// 释放内存for (int i = 0; i < adjList->n; i++) {EdgeNode* p = adjList->adjlist[i].firstedge;while (p != NULL) {EdgeNode* temp = p;p = p->next;delete temp; // 释放边节点内存}}delete adjList; // 释放邻接表内存return 0;
}
//因为是从头部插入进去的，所以输出是
//A: D B
//B : E C A
//C : E D B
//D : C A
//E : C B

2.深度优先搜索

编写一个算法，实现的功能是：从某个顶点开始深度优先搜索用邻接表存储表示的图。
有如下存储结构：
#define MAX 100 
typedef char VertexType ;
typedef  struct  node   //定义边表结点 
{int adjvex;   //邻接点域 struct node  *next; //指向下一个邻接点的指针域 
}EdgeNode;    //边表类型
typedef  struct  vexnode //定义顶点表结点 
{VertexType  data;  //顶点域 EdgeNode *firstedge;  //指向第一条边结点的指针域 
}VHeadNode;    //邻接表结点类型 
typedef  struct
{VHeadNode  adjlist[MAX];  //邻接表结点数组 int  n,e;    //顶点数、边数 
}AdjList;    //图的邻接表类型 
int visited[MAX];   //标志顶点是否被访问过的数组
该函数原型说明为：void DFS(AdjList *g,int vi); 
//从顶点vi开始深度优先搜索用邻接表存储的图g

函数

int visited[MAX]; // 标志顶点是否被访问过的数组// 深度优先搜索
void DFS(AdjList* g, int vi) {// 访问当前顶点cout << "Visited " << g->adjlist[vi].data << endl;visited[vi] = 1;  // 标记当前顶点为已访问// 遍历当前顶点的邻接点EdgeNode* p = g->adjlist[vi].firstedge;while (p) {int w = p->adjvex;  // 邻接点索引if (!visited[w]) {  // 如果邻接点未访问DFS(g, w);  // 递归访问邻接点}p = p->next;  // 移动到下一个邻接点}
}

完整代码

#include <iostream>
#include <cstdlib>using namespace std;#define MAX 100typedef char VertexType;// 定义边表结点
struct EdgeNode 
{int adjvex;           // 邻接点EdgeNode* next;      // 指向下一个邻接点的指针
};// 定义顶点表结点
struct VHeadNode 
{VertexType data;     // 顶点数据EdgeNode* firstedge; // 指向第一条边的指针
};// 邻接表类型
struct AdjList 
{VHeadNode adjlist[MAX]; // 邻接表数组int n, e;               // 图的顶点数和边数
};int visited[MAX]; // 标志顶点是否被访问过的数组// 深度优先搜索
void DFS(AdjList* g, int vi) {// 访问当前顶点cout << "Visited " << g->adjlist[vi].data << endl;visited[vi] = 1;  // 标记当前顶点为已访问// 遍历当前顶点的邻接点EdgeNode* p = g->adjlist[vi].firstedge;while (p) {int w = p->adjvex;  // 邻接点索引if (!visited[w]) {  // 如果邻接点未访问DFS(g, w);  // 递归访问邻接点}p = p->next;  // 移动到下一个邻接点}
}int main() 
{AdjList* g = new AdjList;  // 使用 new 创建图的邻接表cout << "请输入图的顶点数和边数（例如：5 6）: ";cin >> g->n >> g->e;// 初始化访问标志数组for (int i = 0; i < MAX; i++) {visited[i] = 0;}// 初始化图的顶点cout << "请输入图的每个顶点数据（例如：A B C D E）: ";for (int i = 0; i < g->n; i++) {cin >> g->adjlist[i].data;g->adjlist[i].firstedge = NULL;  // 初始化邻接表为空}// 输入图的边cout << "请输入图的每条边（格式：起点 终点）: " << endl;for (int i = 0; i < g->e; i++) {char start, end;cin >> start >> end;int startIndex = -1, endIndex = -1;// 查找起点和终点的索引for (int j = 0; j < g->n; j++) {if (g->adjlist[j].data == start) {startIndex = j;}if (g->adjlist[j].data == end) {endIndex = j;}}// 处理起点到终点的边if (startIndex != -1 && endIndex != -1) {// 创建边表节点EdgeNode* eNode = new EdgeNode;eNode->adjvex = endIndex;eNode->next = g->adjlist[startIndex].firstedge;g->adjlist[startIndex].firstedge = eNode;}}// 从顶点0（假设A）开始深度优先搜索cout << "从顶点 " << g->adjlist[0].data << " 开始深度优先搜索:" << endl;DFS(g, 0);// 释放动态分配的内存delete g;return 0;
}

查找

折半查找算法

 编写一个折半查找递归算法，实现功能是：递归折半查找关键字为k的位置并返回，若找到则返回相应位置，找不到则返回-1。
有如下折半查找的线性表结构：
typedef int KeyType;
typedef struct
{KeyType key;
}SearchL;
该函数原型说明为：int BSearch(SearchL r[],KeyType k,int low,int high); 
//r为线性表，k为查找关键字，low, high分别是低位下标和高位下标

函数

int BSearch(SearchL r[], KeyType k, int low, int high)
{if (low > high){return -1;}int mid = (low+high) / 2;if (r[mid].key == k){return mid;}else if (r[mid].key > k){return BSearch(r, k, low, mid - 1);}else{return BSearch(r, k, mid + 1, high);}
}

完整代码

#include <iostream>
using namespace std;
const  int N = 100;
typedef int KeyType;typedef struct
{KeyType key;}SearchL;int BSearch(SearchL r[], KeyType k, int low, int high)
{if (low > high){return -1;}int mid = (low+high) / 2;if (r[mid].key == k){return mid;}else if (r[mid].key > k){return BSearch(r, k, low, mid - 1);}else{return BSearch(r, k, mid + 1, high);}
}int main()
{int n;cout << "请输入线性表的大小: ";cin >> n;SearchL r[N];cout << "请输入线性中元素（按顺序输入）：";for(int i=0;i<n;i++){cin >> r[i].key;}KeyType k;cout << "请输入要查找的关键字：";cin >> k;int result = BSearch(r, k, 0, n - 1);if (result != -1){cout << "关键字" << k << "的位置是：" << result<<endl;}else{cout << "关键字" << k << "不存在于线性表中"<<endl;}return 0;
}

排序

快速排序

 编写一个快速排序算法，实现功能是：用快速排序算法对排序表中的记录按关键字key进行从小到大排序。
有如下排序记录的存储结构：
typedef int KeyType;
typedef struct
{KeyType key;	
}LineList;
该函数原型说明为：void QuickSort(LineList r[],int low,int high); 
//r为排序表，low, high分别是低位下标和高位下标

函数

// 交换两个元素的位置
void Swap(LineList& a, LineList& b) {LineList temp = a;a = b;b = temp;
}// 快速排序算法（将分区函数合并进来）
void QuickSort(LineList r[], int low, int high) {if (low < high) {// 选择基准元素，通常选择中间的元素int pivot = r[(low + high) / 2].key;int i = low - 1;  // i 表示小于基准元素的部分的最后一个元素的索引int j = high + 1;  // j 表示大于基准元素的部分的第一个元素的索引// 分区操作while (true) {// 寻找第一个大于或等于基准的元素do i++; while (r[i].key < pivot);// 寻找第一个小于或等于基准的元素do j--; while (r[j].key > pivot);// 如果 i < j, 则交换 r[i] 和 r[j]if (i < j) {Swap(r[i], r[j]);}else {// 否则返回 j 作为基准的位置break;}}// 递归地对基准元素左侧和右侧的部分进行快速排序QuickSort(r, low, j);QuickSort(r, j + 1, high);}
}

完整代码

#include <iostream>
using namespace std;const int N = 100;
typedef int KeyType;typedef struct {KeyType key;
} LineList;// 交换两个元素的位置
void Swap(LineList& a, LineList& b) {LineList temp = a;a = b;b = temp;
}// 快速排序算法（将分区函数合并进来）
void QuickSort(LineList r[], int low, int high) {if (low < high) {// 选择基准元素，通常选择中间的元素int pivot = r[(low + high) / 2].key;int i = low - 1;  // i 表示小于基准元素的部分的最后一个元素的索引int j = high + 1;  // j 表示大于基准元素的部分的第一个元素的索引// 分区操作while (true) {// 寻找第一个大于或等于基准的元素do i++; while (r[i].key < pivot);// 寻找第一个小于或等于基准的元素do j--; while (r[j].key > pivot);// 如果 i < j, 则交换 r[i] 和 r[j]if (i < j) {Swap(r[i], r[j]);}else {// 否则返回 j 作为基准的位置break;}}// 递归地对基准元素左侧和右侧的部分进行快速排序QuickSort(r, low, j);QuickSort(r, j + 1, high);}
}// 输出排序后的数组
void PrintArray(LineList r[], int n) {for (int i = 0; i < n; i++) {cout << r[i].key << " ";}cout << endl;
}int main() {int n;cout << "请输入排序表的大小: ";cin >> n;LineList r[N];  // 创建排序表cout << "请输入排序表中的元素（按顺序输入）：";for (int i = 0; i < n; i++) {cin >> r[i].key;}// 调用快速排序QuickSort(r, 0, n - 1);// 输出排序后的数组cout << "排序后的元素为：";PrintArray(r, n);return 0;
}