1.数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科.
2.传统上，我们把数据结构分为逻辑结构和物理结构。
逻辑结构：是指数据对象中数据元素之间的相互关系。
物理结构：是指数据的逻辑结构在计算机中的存储形式。
3.集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他不三不四的关系。
线性结构：线性结构中的数据元素之间是一对一的关系。
树形结构：树形结构中的数据元素之间存在一对多的层次关系。
图形结构：图形结构的数据元素是多对多的关系。
4.存储器主要是针对内存而言的，像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来描述。
6.数据元素的存储结构形式有两种：顺序存储和链式存储
顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
7.clock():捕捉从程序开始运行到clock（）被调用时所耗费的时间。这个时间单位是clock tick，即“时钟打点”。
常数CLK_TCK：机器时钟每秒所走的时钟大点数。
用法模板：
#include<stdio.h> #include<time.h> clock_t start,stop; //clock_t是clock（）函数返回的变量类型 double duration; //记录被测函数运行时间，以秒为单位 int main(） { //不在测试范围内的准备工作写在clock（）调用之前 start=clock();//开始计时 MyFunction()；//把被测函数加在这里 stop=clock()； duration=((double)(stop-start))/CLK_TCK; //其他不再被测范围的处理写在后面，例如输出duration的值 return 0;
8.什么是好的算法：
（1）空间复杂度S(n)：根据算法写成的程序在执行时占用存储单元的长度。
（2）时间复杂度T(n)：根据算法写成的程序在执行时耗费时间的长度。
在分析一般算法的效率时，我们经常关注下面两种复杂度
（1）最坏情况复杂度Tworst（n）
（2）平均复杂度Tavg(n)
Tavg(n)<=Tworst（n）
9.复杂度常用函数比较大小：
1<logn<n<nlog2n<n2<n3<2n<n!
10.链表结点的定义：
链表的结点有两个域：一个是数据域，用来存放数据；另一个是指针域，用来存放下一个结点的位置，如图所示：
因此，链表的结构型定义如下：
typedef struct Node { int data;//这里默认的是int型，如需其他类型那个可直接修改 struct Node *next;//指向Node型变量的指针 }Node;
11.二叉树结点的定义：
typedef struct BTNode { int data; struct BTNode *lchild; struct BTNode *rchild; }BTNode;
12.线性表:由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素成为记录，而由多个记录构成的线性表又称为文件。
非空线性表的结构特性：
(1)有且只有一个根节点a1,它无前件。
(2)有且只有一个终端结点an,它无后件
(3)除根节点和终端节点外，其他所有节点有且只有一个前件，也有且只有一个后件。节点个数n为线性表的长度，当n=0时，称为空表。
13.线性表的顺序存储结构具有以下两个基本特点：
(1)线性表中所有元素的所占存储空间是练习的;
(2)线性表中各数据元素再存储空间中是按逻辑顺序依次存放的。
ai 的存储地址：
ADR(ai)=ADR(ai)+(i-1)K,ADR(ai)为第一个元素的地址，K代表每个元素所占的字节数。
14.顺序表的插入运算：
插入的过程：
首先处理3种异常情况：
(1)当存储空间已满时为“上溢”错误，不能插入，算法结束；
(2)当i>n时，认为在最后一个元素之后插入;
(3)当i<n时，认为在第一个元素之前插入。
然后从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置。
最后将新元素插入到第i个位置，并且将线性表的长度增加1。
15.顺序表的删除元素
删除的过程：
首先处理一下2种异常情况：
(1)当线性表为空(即n=0)时即为“上溢”错误，算法结束；
(2)当i<1或i>n时，
然后从第i+1个元素开始，直到最后一个元素，其中每个元素依次向前移动一个位置。
最后将线性表的长度减少1。
16.所有的指针变量只占4个字节，用第一个字节的地址表示整个变量的地址。
17.顺序表不像链表一样在结点中存在指针域，因此存储密度大。插入运算方便和删除运算方便是链表的优点。线性表的顺序存储结构必须占用一片连续的存储空间，而链表不需要这样。顺序表不便于元素的插入和删除，因为要移动多个元素。链表在插入和删除的过程中不需要移动元素，只需修改指针。线性表是具有相同特性数据元素的一个有序序列。
18.静态链表中指针指示的是链表中下一元素在数组中的地址。虽然静态链表用数组来存储，但其指针域和一般单链表一样，指出了表中下一个结点的位置。静态链表具有链表的的插入和删除方便的特点，也不需要移动较多的元素，这是优于顺序表的地方。
19.KMP算法
(1)字符串查找问题：给定文本串text和模式串pattern，从文本串text中找出模式串pattern第一次出现的位置
(2)最基本的字符串匹配算法：暴力求解(Brute Force):时间复杂度O(m*n)
(3)KMP算法是一种线性时间复杂度的字符串匹配算法，它是对BF算法改进。
(4)记：文本串长度为N，模式串长度为M
(I)BF算法的时间复杂度O(M*N),空间复杂度O(1);
(II)KMP算法的时间复杂度O(M+N),空间复杂度O(N);
(5)KMP算法的核心就是避免不必要的回溯，那么什么事不必要的呢？问题由模式串决定，不是由目标决定。
(6)分析BF与KMP的区别
(I)假设当前文本串text匹配到i位置，模式串pattern串匹配到j位置
(II)BF算法中，如果当前字符串匹配成功，即text[i+j]==pattern[j],令i++,j++，继续匹配下一个字符；如果失败，即text[i+j]=/=（不等于）pattern[j],令i++,j=0;即每次匹配失败的情况下，模式串pattern相对于文本串text向右移动了一位。
(7)KMP算法中，如果当前字符匹配成功，即text[i+j]==pattern[j],令i++,j++,继续匹配下一个字符；如果失败，即text[i+j]=/=(不等于)pattern[j],令i不变，j=next[j],(这里，next[j]<=j-1),即模式串pattern相对于文本串text向右移动了至少1位(移动的实际位数j-next[j]>=1)。
(8)在暴力求解中，为什么模式串的索引会回溯？
因为模式串存在重复字符。
(9)对于模式串的位置j，考察Patternj-1=P0P1...Pj-2Pj-1,查找字符串Patternj-1最大相等k前缀和k后缀。注：计算next[j]时，考察的字符串是模式串的前j-1个字符，与pattern[j]无关。即：查找慢走条件的最大的k，是得P0P1...Pk-2Pk-1 =Pj-kPj-k+1...Pj-2Pj-1 。
(10)next的递推关系：
(I)对于模式串的位置j,有next[j]=k,即：P0P1...Pk-2Pk-1 =Pj-kPj-k+1...Pj-2Pj-1
(II)则，对于模式串的位置j+1,考察Pj;
(III)若p[k]==p[j]
next[j+1]=next[j]+1
(IV)若p[k]=/=p[j],记h=next[k];如果p[h]==p[j],则next[j+1]=h+1,否则重复此过程。
(11)进一步分析next
(I)文本串匹配到i,模式串匹配到j,此时，若text[i]=/=pattern[j],即匹配失败的情况：
(II)若next[j]=k,说明模式串应该从j滑动到k位置;
(III)若此时满足pattern[j]==pattern[k],因为text[i]=/=pattern[j],所以，text[i]=/=pattern[k]
(i)即i和k没有匹配，应该继续滑动到next[k]。
(ii)换句话说：若原始的next数组中，若next[j]=k并且pattern[j]==pattern[k],next[j]可以直接等于next[k]。
(12)代码
//BF算法，暴力算法 int index(Str str,Str substr) { int i=0,j=0,k=i; while(i<str.length&&j<substr.length) { if(str.ch[i]==substr.ch[j]) { ++i; ++j; } else { j=0; i=++k;//匹配失败，i从主串下一位置开始，k种记录了上一次的启示位置 } } if(j==substr.length) return k; else return -1; } //KMP算法 int KMP(Str str,Str substr,int next[]) { int i=0,j=0; while(i<str.length&&j<substr.length) { if(str.ch[i]==substr.ch[j]) { ++i; ++j; }else { j=next[i]; if(j==-1) { j=0; ++i; } } } if(j==substr.length) return i-substr.length; else return -1; } 求next数组的算法如下 void getnext(Str sbustr,int next[]) { int i=0;j=-1; next[0]=-1; while(i<substr.length) { if(j==-1||substr.ch[i]==sbustr.ch[j]) { ++i; ++j; next[i]=j; } else j=next[j]; } }
20.
(1)串是限定了数据元素是字符的线性表，串的数据元素必须是单个字符
(2)串的两种最基本存储方式是顺序存储方式和链式存储方式。
(3)空格字符也是串中的一个字符。
21.希尔排序
#include<stdio.h> #include<math.h> #define MAXNUM 10 //希尔排序 void shellSort(int array[],int n,int t) { int a,dk; for(a=1;a<=t;a++) { dk=(int)(pow(2,t-a+1)-1);//计算增量 int i,j,temp; for(i=dk;i<n;i++)//分别向每组的有序区域进行插入 { temp=array[i]; for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比较与记录后移同时进行 array[j+dk]=array[j]; if(j!=i-dk) array[j+dk]=temp;//插入 } } } void main() { void shellSort(int array[],int n,int t);//t为排序的趟数 int array[MAXNUM],i; for(i=0;i<MAXNUM;i++) scanf("%d",&array[i]); shellSort(array,MAXNUM,(int)(log(MAXNUM+1)/log(2)));//排序趟数应为long2（n+1）的整数部分 for(i=0;i<MAXNUM;i++) printf("%d ",array[i]); printf(" "); }
22.进行冒泡排序
#include <stdio.h> #include <stdlib.h> #define MAXNUM 10 /* run this program using the console pauser or add your own getch, system("pause") or input loop */ void maopaoInsert(int R[],int n) { int i,j,temp; for(j=0;j<n-1;j++)//总共需要排序的次数 { for(i=0;i<n-1-j;i++)//此趟需要排序的个数，也就是从0 .....n-1-j。进行比较 { if(R[i]>R[i+1])//每次进行两两比较 { temp=R[i]; R[i]=R[i+1]; R[i+1]=temp; } } } } void main() { int array[MAXNUM],i; for(i=0;i<MAXNUM;i++) scanf("%d",&array[i]); maopaoInsert(array,MAXNUM);//排序趟数应为long2（n+1）的整数部分 for(i=0;i<MAXNUM;i++) printf("%d ",array[i]); printf(" "); }
23快速排序
#include <stdio.h> #include <stdlib.h> #define MAXNUM 10 void kuaisuSort(int a[],int left,int right) { if(left>=right)//如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了 { return; } int i=left; int j=right; int key=a[left];//以a[left]为轴中心 while(i<j)//控制在当组内寻找一遍 { while(i<j&&key<=a[j])//而寻找结束的条件就是，1，找到一个小于或者大于key的数，没有符合条件1的，并且i与j的大小没有反转 { j--;//向前寻找 } a[i]=a[j];// 找到一个这样的数后就把他赋给前面的被拿走的i的值（如果第一次循环且key是a[left],那么就是key) while(i<j&&key>=a[i])//这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，因为排序思想就是把数组网两边礽，所以左右两边的数大小与key的关系相反 { i++; } a[j]=a[i]; } a[i]=key;//当在当组内找完一遍以后就把中间数key回归 kuaisuSort(a,left,i-1);//最后用同样的方式把对分出来的左边的小组进行同上的做法 kuaisuSort(a,i+1,right);//最后用同样的方式把对分出来的右边的小组进行同上的做法 //当然最后可能会出现很多分左右，直到每一组的i=j为止。 } void main() { int array[MAXNUM],i; for(i=0;i<MAXNUM;i++) scanf("%d",&array[i]); kuaisuSort(array, 0,MAXNUM-1); for(i=0;i<MAXNUM;i++) printf("%d ",array[i]); printf(" "); }
24.简单选择排序
#include <stdio.h> #include <stdlib.h> #define MAXNUM 10 /* run this program using the console pauser or add your own getch, system("pause") or input loop */ void jiandanxuanzeSort(int R[],int n) { int i,j,min;int minR;//储存最小的数组 int temp; for(i=0;i<n;i++) { minR=R[i];////假设R[i]为本轮最小值 min=i;//将 最小值下标存储在min中 for(j=i+1;j<n;j++)//从i到n查找最小值 { if(R[j]<minR)//如果有R[j]小于最小值 { minR=R[j];//那么把R[j]赋值给minR行调换 min=j; } } //将寻找到的最小值R[min]与本轮的R[i]对换 temp=R[i]; R[i]=R[min]; R[min]=temp; } } void main() { int array[MAXNUM],i; for(i=0;i<MAXNUM;i++) scanf("%d",&array[i]); jiandanxuanzeSort(array,MAXNUM); for(i=0;i<MAXNUM;i++) printf("%d ",array[i]); printf(" "); }
25.最大公约数
//最大公约数 int gcd(int v1,int v2) { while(v2) { int temp=v2; v2=v1%v2; v1=temp; } return v1; }
26.交换
(1)指针
#include <iostream> using namespace std; void swap(int *px, int *py) { int temp; temp=*px; *px=*py; *py=temp; } int main() { int a,b; a = 1; b = 10; cout << "传指针的方法: " << endl; cout << "a = " << a << ", b = " << b << endl; //拷贝的指针(地址) swap(&a,&b); cout << "a = " << a << ", b = " << b << endl; return 0; }
(2)宏函数
#include <iostream> #define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t)) using namespace std; int main() { int a, b, temp; a = 1; b = 10; cout << "使用宏定义函数: " << endl; cout << "a = " << a << ", b = " << b << endl; SWAP(a,b,temp); cout << "a = " << a << ", b = " << b << endl; return 0; }
(3)引用
#include <iostream> using namespace std; //引用就是别名 void swap(int &a,int &b) { int temp; temp=a; a=b; b=temp; } int main() { int a,b; a = 1; b = 10; cout << "传引用: " << endl; cout << "a = " << a << ", b = " << b << endl; swap(a,b); cout << "a = " << a << ", b = " << b << endl; return 0; }
(4)C++标准库 swap
#include <iostream> using namespace std; int main() { int a, b; a = 1; b = 10; cout << "使用std::swap函数: " << endl; cout << "a = " << a << ", b = " << b << endl; std::swap(a,b); cout << "a = " << a << ", b = " << b << endl; return 0; }
27.图
(1)邻接矩阵
代码：
#include <iostream> using namespace std; #define MAX_VERTS 20 //保存最多的顶点数 //顶点 class Vertex { public: Vertex(char lab){Label=lab; } private: char Label; }; //图 邻接矩阵 (对称) class Graph { public: Graph(); ~Graph(); void addVertex(char lab);//增加顶点 void addEdge(int start,int end);//增加边 void printMatrix();//打印矩阵 private: Vertex* vertexList[MAX_VERTS];//数组(保存最多的定点数) int nVerts;//实际上的顶点数 int adjMat[MAX_VERTS][MAX_VERTS]; //邻接矩阵 } ; //构造函数，有效点为0，初始化矩阵 Graph::Graph() { nVerts=0; for(int i=0;i<MAX_VERTS;i++) { for(int j=0;j<MAX_VERTS;j++) { adjMat[i][j]=0; } } } //增加点 void Graph::addVertex(char lab) { vertexList[nVerts++]=new Vertex(lab); } // 增加边 (对称) void Graph::addEdge(int start,int end) { adjMat[start][end]=1; adjMat[end][start]=1; } //打印 void Graph::printMatrix() { for(int i=0;i<nVerts;i++) { for(int j=0;j<nVerts;j++) { cout<<adjMat[i][j]<<" "; } cout<<endl; } } //析构函数 Graph::~Graph() { for(int i=0;i<nVerts;i++) { delete vertexList[i]; } } int main() { Graph a; a.addVertex('A');//下标 0 a.addVertex('B');//下标 1 a.addVertex('C');//下标 2 a.addVertex('D');//下标 3 a.addVertex('E');//下标 4 a.addEdge(0,1);//连线 A-B a.addEdge(0,3);//连线 A-D a.addEdge(1,0);//连线 B-A a.addEdge(1,4);//连线 B-E a.addEdge(2,4);//连线 C-E a.addEdge(3,0);//连线 D-A a.addEdge(3,4);//连线 D-E a.addEdge(4,1);//连线 E-B a.addEdge(4,2);//连线 E-C a.addEdge(4,3);//连线 E-D a.printMatrix(); return 0; }
(2)邻接表
#include <iostream> #include <list> using namespace std; class Vertex { public: char Label; Vertex(char lab) { Label = lab; } }; ostream& operator<<(ostream& out, const Vertex& v) { cout << v.Label; return out; } template<class T> class Graph { public: Graph(const int vertices) : n(vertices) { VertexList = new T*[n]; HeadNodes = new list<int>[n]; nVerts = 0; } ~Graph() { delete[] VertexList; delete[] HeadNodes; } void addVertex(T* v); void addEdge(int start, int end); void printVertice(); void printAdjList(); private: T** VertexList; list<int>* HeadNodes; int n; int nVerts; }; template<class T> void Graph<T>::addVertex(T* v) { VertexList[nVerts++] = v; } template<class T> void Graph<T>::addEdge(int start, int end) { HeadNodes[start].push_back(end); } template<class T> void Graph<T>::printVertice() { for(int i=0; i<nVerts; i++) cout << *VertexList[i] << " "; cout << endl; } template<class T> void Graph<T>::printAdjList() { for(int i=0; i<nVerts; i++) { cout << i << " -> "; for(list<int>::iterator iter = HeadNodes[i].begin(); iter != HeadNodes[i].end(); ++iter) cout << *iter << " -> "; cout << "end" << endl; } } int main() { //Graph<char> g(5); //char a = 'A'; //char b = 'B'; //char c = 'C'; //char d = 'D'; //char e = 'E'; Graph<Vertex> g(5); Vertex a('A'); Vertex b('B'); Vertex c('C'); Vertex d('D'); Vertex e('E'); g.addVertex(&a); g.addVertex(&b); g.addVertex(&c); g.addVertex(&d); g.addVertex(&e); g.printVertice(); g.addEdge(0,1); g.addEdge(0,3); g.addEdge(1,0); g.addEdge(1,4); g.addEdge(2,4); g.addEdge(3,0); g.addEdge(3,4); g.addEdge(4,1); g.addEdge(4,2); g.addEdge(4,3); g.printAdjList(); system("pause"); return 0; }
(3)深度优先搜索(DFS) 使用堆栈
代码：(以邻接矩阵图形为案例)
#include <iostream> #include<stack> #define MAX_VERTS 20 using namespace std; class Vertex { public: Vertex(char lab) { Label = lab; wasVisited=false;//新构造的顶点没有访问过 } public: bool wasVisited; char Label; }; class Graph { public: Graph(); ~Graph(); void addVertex(char lab); void addEdge(int start, int end); void printMatrix(); void showVertex(int v);//显示顶点 void DFS();//深度优先搜索 private: Vertex* vertexList[MAX_VERTS]; int nVerts; int adjMat[MAX_VERTS][MAX_VERTS]; int getAdjUnvisitedVertex(int v); //获得临接的下一个且没有访问的顶点 }; void Graph::DFS() { stack<int> gStack; vertexList[0]->wasVisited=true;//顶点 showVertex(0); gStack.push(0);//顶点放入到堆栈 int v; while(gStack.size()>0) { v=getAdjUnvisitedVertex(gStack.top());//总是以堆栈中最上一个为准 if(v==-1)// 如果没有，则返回 gStack.pop(); else//找到 { vertexList[v]->wasVisited=true; showVertex(v); gStack.push(v); //找到放入到堆栈中 } } cout<<endl; for(int j=0;j<nVerts;j++)//设置false 可以多次进行搜索 vertexList[j]->wasVisited=false; } //获得临接的下一个且没有访问的顶点 //是否是邻接的？是否访问过 int Graph::getAdjUnvisitedVertex(int v) { for(int j=0;j<nVerts;j++) if((adjMat[v][j]==1)&&(vertexList[j]->wasVisited==false)) return j; return -1; } void Graph::showVertex(int v) { cout<<vertexList[v]->Label<<" "; } Graph::Graph() { nVerts = 0; for(int i=0; i<MAX_VERTS; i++) for(int j=0; j<MAX_VERTS; j++) adjMat[i][j] = 0; } void Graph::addVertex(char lab) { vertexList[nVerts++] = new Vertex(lab); } void Graph::addEdge(int start, int end) { adjMat[start][end] = 1; adjMat[end][start] = 1; } void Graph::printMatrix() { for(int i=0; i<nVerts; i++) { for(int j=0; j<nVerts; j++) cout << adjMat[i][j] << " "; cout << endl; } } Graph::~Graph() { for(int i=0; i<nVerts; i++) delete vertexList[i]; } int main() { Graph g; g.addVertex('A');// 0 g.addVertex('B');// 1 g.addVertex('C');// 2 g.addVertex('D');// 3 g.addVertex('E');// 4 g.addEdge(0,1); // A-B g.addEdge(0,3); // A-D g.addEdge(1,0); // B-A g.addEdge(1,4); // B-E g.addEdge(2,4); // C-E g.addEdge(3,0); // D-A g.addEdge(3,4); // D-E g.addEdge(4,1); //E-B g.addEdge(4,2);//E-C g.addEdge(4,3);//E-D g.printMatrix(); cout << "深度优先搜索的结果: "; g.DFS(); system("pause"); return 0; }
(4)广度优先搜索(BFS) 使用队列
代码：
#include <iostream> #include <stack> #include<queue> #define MAX_VERTS 20 using namespace std; class Vertex { public: Vertex(char lab) { Label = lab; wasVisited = false; } public: bool wasVisited; char Label; }; class Graph { public: Graph(); ~Graph(); void addVertex(char lab); void addEdge(int start, int end); void printMatrix(); void showVertex(int v); void DFS(); void BFS();//广度优先 private: Vertex* vertexList[MAX_VERTS]; int nVerts; int adjMat[MAX_VERTS][MAX_VERTS]; int getAdjUnvisitedVertex(int v); }; void Graph::DFS() { stack<int> gStack; vertexList[0]->wasVisited = true; showVertex(0); gStack.push(0); int v; while(gStack.size() > 0) { v = getAdjUnvisitedVertex(gStack.top()); if(v == -1) gStack.pop(); else { vertexList[v]->wasVisited = true; showVertex(v); gStack.push(v); } } cout << endl; for(int j=0; j<nVerts; j++) vertexList[j]->wasVisited = false; } void Graph::BFS() { queue<int>gQueue; vertexList[0]->wasVisited=true; //设置顶点为访问过了， showVertex(0); gQueue.push(0);//把顶点放入到队列中 int vert1,vert2; while(gQueue.size()>0) { vert1=gQueue.front();//把队列中顶点拿出来 gQueue.pop();//队列顶点删除 vert2=getAdjUnvisitedVertex(vert1);//邻接且没有访问过的 while(vert2!=-1)//有 邻接且没有访问过的 { vertexList[vert2]->wasVisited=true; showVertex(vert2); gQueue.push(vert2);//放入到队列中 vert2=getAdjUnvisitedVertex(vert1);//继续寻找vert1中其他符合条件的 //(因为getAdjUnvisitedVertex这个函数只是保证找到符合条件就返回) } } cout<<endl; for(int j=0; j<nVerts; j++) vertexList[j]->wasVisited = false; } int Graph::getAdjUnvisitedVertex(int v) { for(int j=0; j<nVerts; j++) if((adjMat[v][j] == 1) && (vertexList[j]->wasVisited == false)) return j; return -1; } void Graph::showVertex(int v) { cout << vertexList[v]->Label << " "; } Graph::Graph() { nVerts = 0; for(int i=0; i<MAX_VERTS; i++) for(int j=0; j<MAX_VERTS; j++) adjMat[i][j] = 0; } void Graph::addVertex(char lab) { vertexList[nVerts++] = new Vertex(lab); } void Graph::addEdge(int start, int end) { adjMat[start][end] = 1; adjMat[end][start] = 1; } void Graph::printMatrix() { for(int i=0; i<nVerts; i++) { for(int j=0; j<nVerts; j++) cout << adjMat[i][j] << " "; cout << endl; } } Graph::~Graph() { for(int i=0; i<nVerts; i++) delete vertexList[i]; } int main() { Graph g; g.addVertex('A');// 0 g.addVertex('B');// 1 g.addVertex('C');// 2 g.addVertex('D');// 3 g.addVertex('E');// 4 g.addEdge(0,1); // A-B g.addEdge(0,3); // A-D g.addEdge(1,0); // B-A g.addEdge(1,4); // B-E g.addEdge(2,4); // C-E g.addEdge(3,0); // D-A g.addEdge(3,4); // D-E g.addEdge(4,1); // E-B g.addEdge(4,2); // E-C g.addEdge(4,3); // E-D g.printMatrix(); cout << "深度优先搜索的结果: "; g.DFS(); cout << "广度优先搜索的结果: "; g.BFS(); cout <<endl; system("pause"); return 0; }
28.红黑树
(1)红黑树特征：节点都有颜色，插入和删除节点时要遵循红黑规则
(2)红黑规则：
(I)每一个节点不是红色的就是黑色的。
(II)根总是黑色的
(III)如果节点时红色的，则它的子节点必须是黑色的
(IV)从根到叶节点的每条路径，必须包含相同数目的黑色节点。
(3)修正方法
(I) 修改节点的颜色
(II)旋转
(4)C++标准库中的红黑树
#include <set> #include <map> using namespace std; int main() { //C++标准库容器（数据结构）：红黑树 set<int> a; multiset<int> b; map<int,int> c; multimap<int,int> d; a.insert(50); a.insert(40); a.insert(30); return 0; }
(5)红黑树(自编)
#include <iostream> #include <sstream> #include <string> #include <vector> // SEE UPDATE COMMENTS AT END OF FILE // 2006-01.29 fixed memory leaks // eliminate need to qualify standard library with std:: using namespace std; // =============================================================== // C++ NEEDS SOME DECLARATIONS BEFORE THE MAIN RedBlackTree class. // skip down a little to line this up with the other side // =============================================================== // requires forward declaration to resolve cycle between NodeVisitor and RedBlackTree template<class T> class RedBlackTree; // use an abstract class for the node visitor. it is templatized to match the templated RedBlackTree declaration template<class T> class NodeVisitor { public: // need a virtual destructor for the concrete classes virtual ~NodeVisitor() {} // ise a pure virtual function so a concrete class must implement // the proper signature virtual void visit(const RedBlackTree<T> *node,int depth) = 0; }; // ============================================= // >>>>>>>>>>>>>>>>> RED BLACK TREE STARTS HERE // ============================================= // in line with the STL conventions, this template uses 'by-value' semantics for the contained // object. This means that the 'T' object will need to have the correct constructor and copy assignment // semantics or it won't work. primitive types are OK but object instances would have to be // put together correctly. template<class T> class RedBlackTree { private: /* Red/Black tree implementation based on Algorithms in C++, Sedgewick Introduction To Algorithms Cormen, Thomas H. / Leiserson, Charl es E . / Rivest, Ronald L . The MIT Press 07/1990 NOTE : LOOK AT END OF FILE TO SEE DIFFERENCES IN TRAVERSAL IDIOMS */ // yes, i could use an enum but since i want to print the values, using an enum is more // trouble than it is worth. static const int red = 0; static const int black = 1; // use a common instance variable naming convention 'm_'. others use a single leading '_' int m_color; T m_val; RedBlackTree *m_left; RedBlackTree *m_right; RedBlackTree(RedBlackTree *b) { m_val = b->m_val; m_left = b->m_left; m_right = b->m_right; m_color = red; } void copy(RedBlackTree *x) { m_val = x->m_val; m_left = x->m_left; m_right = x->m_right; m_color = x->m_color; // UPDATE 2006-01-28 // node pointed to by 'x' is no longer needed, delete it. // first make sure the delete won't descend into other nodes x->m_left = 0; x->m_right = 0; delete x; } RedBlackTree *RBinsertLeft(T k,int sw) { RedBlackTree *l; RedBlackTree *b; l = m_left; if (l == 0) { m_left = b = new RedBlackTree(k); } else { b = l->RBinsert(k,sw); } return b; } RedBlackTree *RBinsertRight(T k,int sw) { RedBlackTree *r; RedBlackTree *b; r = m_right; if (r == 0) { m_right = b = new RedBlackTree(k); } else { b = r->RBinsert(k,sw); } return b; } RedBlackTree *rotLeft() { RedBlackTree *x; RedBlackTree *me; if (m_right == 0) return 0; // make the changes in a copy of current node __self // on return, the caller will copy in 'me' to current node me = new RedBlackTree(this); x = me->m_right; me->m_right = x->m_left; x->m_left = me; return x; } RedBlackTree *rotRight() { RedBlackTree *x; RedBlackTree *me; if (m_left == 0) return 0; // make the changes in a copy of current node __self // on return, the caller will copy in 'me' to current node me = new RedBlackTree(this); x = me->m_left; me->m_left = x->m_right; x->m_right = me; return x; } RedBlackTree *RBinsert(T k,int sw) { RedBlackTree *b = 0; RedBlackTree *x; RedBlackTree *l; RedBlackTree *ll; RedBlackTree *r; RedBlackTree *rr; // if current node is a 4 node, split it by flipping its colors // if both children of this node are red, change this one to red // and the children to black l = m_left; r = m_right; if ((l != 0)&&(l->m_color==red)&&(r != 0)&&(r->m_color==red)) { m_color = red; l->m_color = black; r->m_color = black; } // go left or right depending on key relationship if (k < m_val) { // recursively insert b = RBinsertLeft(k,0); // on the way back up check if a rotation is needed // if search path has two red links with same orientation // do a single rotation and flip the color bits l = m_left; if ((m_color == red)&&(l != 0)&&(l->m_color == red)&&(sw == 1)) { x = rotRight(); if (x != 0) { // copy returned node to 'this' copy(x); } } // flip the color bits l = m_left; if (l != 0) { ll = l->m_left; if (ll != 0) { if ((l->m_color == red)&&(ll->m_color == red)) { x = rotRight(); if (x != 0) { copy(x); } m_color = black; r = m_right; if (r != 0) { r->m_color = red; } } } } } else { b = RBinsertRight(k,1); // on the way back up check if a rotation is needed // if search path has two red links with same orientation // do a single rotation and flip the color bits r = m_right; if ((m_color == red)&&(r != 0)&&(r->m_color == red)&&(sw == 0)) { x = rotLeft(); if (x != 0) { // copy returned node to 'this' copy(x); } } // flip the color bits r = m_right; if (r != 0) { rr = r->m_right; if (rr != 0) { if ((r->m_color == red)&&(rr->m_color == red)) { x = rotLeft(); if (x != 0) { // copy returned node to 'this' copy(x); } m_color = black; l = m_left; if (l != 0) { l->m_color = red; } } } } } return b; } // ================================================== // PUBLIC METHODS // ================================================== public: // construct with an initial value RedBlackTree(T x) { m_val = x; m_left = 0; m_right = 0; m_color = red; } ~RedBlackTree() { if (m_left != 0) { delete m_left; } if (m_right != 0) { delete m_right; } } // return a string representation string str() const { stringstream s(stringstream::out); // m_val (type T) must have the proper ostream insertion operator // or this implementation won't work s << "[" << m_val << "," << m_color << "]"; return s.str(); } // 'const' means this method doesn't change the object state T val() const { return m_val; } // 'const' means this method doesn't change the object state int color() const { return m_color; } // 'const' means this method doesn't change the object state // and it returns a pointer to a const node that the caller // cannot change, only inspect const RedBlackTree *find(const T &key) const { const RedBlackTree *result = 0; if (key == m_val) { result = this; } else if (key < m_val) { if (m_left != 0) { result = m_left->find(key); } } else { if (m_right != 0) { result = m_right->find(key); } } return result; } // 'const' means this method doesn't change the object state // and the visitor is not allowed to change the object state. // that may not be what is desired but is used here to // illustrate something you can do in C++ that you can't do // in the other languages and that illustrates the bias towards // extensive static type checking void inorder(NodeVisitor<T> *visitor,int depth) const { if (m_left != 0) { m_left->inorder(visitor,depth+1); } visitor->visit(this,depth); if (m_right != 0) { m_right->inorder(visitor,depth+1); } } RedBlackTree *insert(T k) { RedBlackTree *b; b = RBinsert(k,0); m_color = black; return b; } }; // define a concrete class for the node visitor class IntNodeVisitor : public NodeVisitor<int> { public: virtual ~IntNodeVisitor() {} // the node is 'const' so the visitor can't change it, only look at it virtual void visit(const RedBlackTree<int> *node,int depth) { if (node->val() != 0) { cout << "(" << node->val() << ":" << node->color() << ":" << depth << "), "; } } }; // ================================== // test program // ================================== int main(int argc,char *argv[]) { int nodelist[] = {11,4,8,14,17,6,9,7,16,15,13,5,19,18,12,10,3,20,1}; NodeVisitor<int> *v; // anonymous class implementing the NodeVisitor interface v = new IntNodeVisitor; // insert all the data into the tree RedBlackTree<int> *root = new RedBlackTree<int>(2); root->insert(11); root->insert(4); root->insert(8); root->insert(14); root->insert(17); root->insert(6); //显示红黑树里的数据 root->inorder(v,0); return 0; // need to do an ugly calculation to figure out length of the nodelist array // if i used a collection object instead of an array, then I couldn't have // done static initialization. so its a tradeoff for(int i=0;i<(sizeof(nodelist)/sizeof(nodelist[0]));i++) { root->insert(nodelist[i]); } // print the header cout << "C++ = "; // visit all the nodes in order root->inorder(v,0); // print a newline cout << endl; // find the specified element and print its value const RedBlackTree<int> *x = root->find(16); cout << x->str() << endl; // no garbage collection, need to explicitly delete delete root; // will recursively delete all the nodes delete v; } // =================================================================== // UPDATE 2006-01-29 // there are memory leaks that need to be fixed. // 1. the algorithm leaks nodes after a rotate // two possible fixes : // find where the leaks occur and do the needed deletes // in this case the 'copy' method handles // deleting unused nodes // use an appropriate smart pointer to handle deleteing // 2. the tree is not properly disposed of when the program completes // In the STL tradition a delete of the tree should // delete all tree resources but not the contained data. the application // should handle deleting the contained data elements, if needed, prior // to deleting the tree. In this case a recursive delete of the // nodes works gets rid of the tree resources // // these issue show that one of the big difficulties in C++ is to // handle disposing of data after you are done with it. that is indeed a // source of many C++ program errors of the type that are related more to // dealing with the complexity of the language rather than the solving // the problem. In this code the leaks are probably fixed but there is always // a lingering doubt "Did I get all the leaks?" // Thats a problem with C++, its hard to be certain. // // a modern approach is to use smart pointers to simulate garbage // collection. the Boost library referenced counted smart pointers // will be included in the next standard revision of the C++ library // so they are used here to handle all the cases. // ===================================================================
(6)红黑树(模版)
#ifndef RED_BLACK_TREE_H_ #define RED_BLACK_TREE_H_ #include "Wrapper.h" #include "Except.h" // Red-black tree class. // // CONSTRUCTION: with negative infinity object // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // void remove( x ) --> Remove x (unimplemented) // Comparable find( x ) --> Return item that matches x // Comparable findMin( ) --> Return smallest item // Comparable findMax( ) --> Return largest item // bool isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // ******************ERRORS******************************** // Throws exceptions as warranted. template <class Comparable> class RedBlackTree; template <class Comparable> class RedBlackNode; template <class Comparable> class RedBlackTree { public: RedBlackTree( const Comparable & negInf ); RedBlackTree( const RedBlackTree & rhs ); ~RedBlackTree( ); Cref<Comparable> findMin( ) const; Cref<Comparable> findMax( ) const; Cref<Comparable> find( const Comparable & x ) const; bool isEmpty( ) const; void makeEmpty( ); void insert( const Comparable & x ); void remove( const Comparable & x ); enum { RED, BLACK }; const RedBlackTree & operator=( const RedBlackTree & rhs ); typedef RedBlackNode<Comparable> Node; private: Node *header; // The tree header (contains negInf) Node *nullNode; // Used in insert routine and its helpers (logically static) Node *current; Node *parent; Node *grand; Node *great; // Usual recursive stuff void reclaimMemory( Node *t ) const; RedBlackNode<Comparable> * clone( Node * t ) const; // Red-black tree manipulations void handleReorient( const Comparable & item ); RedBlackNode<Comparable> * rotate( const Comparable & item, Node *parent ) const; void rotateWithLeftChild( Node * & k2 ) const; void rotateWithRightChild( Node * & k1 ) const; }; template <class Comparable> class RedBlackNode { Comparable element; RedBlackNode *left; RedBlackNode *right; int color; RedBlackNode( const Comparable & theElement = Comparable( ), RedBlackNode *lt = NULL, RedBlackNode *rt = NULL, int c = RedBlackTree<Comparable>::BLACK ) : element( theElement ), left( lt ), right( rt ), color( c ) { } friend class RedBlackTree<Comparable>; }; // Construct the tree. // negInf is a value less than or equal to all others. template <class Comparable> RedBlackTree<Comparable>::RedBlackTree( const Comparable & negInf ) { nullNode = new Node; nullNode->left = nullNode->right = nullNode; header = new Node( negInf ); header->left = header->right = nullNode; } // Copy constructor. template <class Comparable> RedBlackTree<Comparable>::RedBlackTree( const RedBlackTree<Comparable> & rhs ) { nullNode = new Node; nullNode->left = nullNode->right = nullNode; header = new Node( rhs.header->element ); header->left = header->right = nullNode; *this = rhs; } // Destroy the tree. template <class Comparable> RedBlackTree<Comparable>::~RedBlackTree( ) { makeEmpty( ); delete nullNode; delete header; } // Insert item x into the tree. // Throws DuplicateItemException if x is already present. template <class Comparable> void RedBlackTree<Comparable>::insert( const Comparable & x ) { current = parent = grand = header; nullNode->element = x; while( current->element != x ) { great = grand; grand = parent; parent = current; current = x < current->element ? current->left : current->right; // Check if two red children; fix if so if( current->left->color == RED && current->right->color == RED ) handleReorient( x ); } // Insertion fails if already present if( current != nullNode ) throw DuplicateItemException( ); current = new Node( x, nullNode, nullNode ); // Attach to parent if( x < parent->element ) parent->left = current; else parent->right = current; handleReorient( x ); } // Remove item x from the tree. // Not implemented in this version. template <class Comparable> void RedBlackTree<Comparable>::remove( const Comparable & x ) { cout << "Sorry, remove unimplemented; " << x << " still present" << endl; } // Find the smallest item the tree. // Return the smallest item wrapped in a Cref object. template <class Comparable> Cref<Comparable> RedBlackTree<Comparable>::findMin( ) const { if( isEmpty( ) ) return Cref<Comparable>( ); Node *itr = header->right; while( itr->left != nullNode ) itr = itr->left; return Cref<Comparable>( itr->element ); } // Find the largest item in the tree. // Return the largest item wrapped in a Cref object. template <class Comparable> Cref<Comparable> RedBlackTree<Comparable>::findMax( ) const { if( isEmpty( ) ) return Cref<Comparable>( ); Node *itr = header->right; while( itr->right != nullNode ) itr = itr->right; return Cref<Comparable>( itr->element ); } // Find item x in the tree. // Return the matching item wrapped in a Cref object. template <class Comparable> Cref<Comparable> RedBlackTree<Comparable>::find( const Comparable & x ) const { nullNode->element = x; Node *curr = header->right; for( ; ; ) { if( x < curr->element ) curr = curr->left; else if( curr->element < x ) curr = curr->right; else if( curr != nullNode ) return Cref<Comparable>( curr->element ); else return Cref<Comparable>( ); } } // Make the tree logically empty. template <class Comparable> void RedBlackTree<Comparable>::makeEmpty( ) { reclaimMemory( header->right ); header->right = nullNode; } // Test if the tree is logically empty. // Return true if empty, false otherwise. template <class Comparable> bool RedBlackTree<Comparable>::isEmpty( ) const { return header->right == nullNode; } // Deep copy. template <class Comparable> const RedBlackTree<Comparable> & RedBlackTree<Comparable>::operator=( const RedBlackTree<Comparable> & rhs ) { if( this != &rhs ) { makeEmpty( ); header->right = clone( rhs.header->right ); } return *this; } // Internal method to clone subtree. template <class Comparable> RedBlackNode<Comparable> * RedBlackTree<Comparable>::clone( Node * t ) const { if( t == t->left ) // Cannot test against nullNode!!! return nullNode; else return new RedBlackNode<Comparable>( t->element, clone( t->left ), clone( t->right ), t->color ); } // Internal routine that is called during an insertion // if a node has two red children. Performs flip and rotations. // item is the item being inserted. template <class Comparable> void RedBlackTree<Comparable>::handleReorient( const Comparable & item ) { // Do the color flip current->color = RED; current->left->color = BLACK; current->right->color = BLACK; if( parent->color == RED ) // Have to rotate { grand->color = RED; if( item < grand->element != item < parent->element ) parent = rotate( item, grand ); // Start dbl rotate current = rotate( item, great ); current->color = BLACK; } header->right->color = BLACK; // Make root black } // Internal routine that performs a single or double rotation. // Because the result is attached to the parent, there are four cases. // Called by handleReorient. // item is the item in handleReorient. // parent is the parent of the root of the rotated subtree. // Return the root of the rotated subtree. template <class Comparable> RedBlackNode<Comparable> * RedBlackTree<Comparable>::rotate( const Comparable & item, Node *theParent ) const { if( item < theParent->element ) { item < theParent->left->element ? rotateWithLeftChild( theParent->left ) : // LL rotateWithRightChild( theParent->left ) ; // LR return theParent->left; } else { item < theParent->right->element ? rotateWithLeftChild( theParent->right ) : // RL rotateWithRightChild( theParent->right ); // RR return theParent->right; } } // Rotate binary tree node with left child. template <class Comparable> void RedBlackTree<Comparable>:: rotateWithLeftChild( Node * & k2 ) const { Node *k1 = k2->left; k2->left = k1->right; k1->right = k2; k2 = k1; } // Rotate binary tree node with right child. template <class Comparable> void RedBlackTree<Comparable>:: rotateWithRightChild( Node * & k1 ) const { Node *k2 = k1->right; k1->right = k2->left; k2->left = k1; k1 = k2; } // Internal method to reclaim internal nodes in subtree t. template <class Comparable> void RedBlackTree<Comparable>::reclaimMemory( Node *t ) const { if( t != t->left ) { reclaimMemory( t->left ); reclaimMemory( t->right ); delete t; } } #endif
29.冒泡排序
(1)从左到右扫描数据，选择最大的数据，放在右边。
(2)要点:比较相邻的两个树，如果左边的数大于右边的数就进行交换。
(3)代码:
#include <iostream> using namespace std; void BubbleSort(int list[], int n); int main() { int a[] = {2,4,6,8,0,1,3,5,7,9}; BubbleSort(a,10); for(int k=0; k<10; k++) cout << a[k] << " "; cout << endl; return 0; } void BubbleSort(int list[], int n) { for(int i=0; i<n-1; i++){ for(int j=0; j<n-i-1;j++){ if(list[j] > list[j+1]) std::swap(list[j],list[j+1]); } } }
30选择排序
(1)从当前未排序的整数中找一个最小的整数，将它放在已排序的整数列表的最后。
(2)要点：选择排序最小的，往左边选。
#include <iostream> using namespace std; void SelectSort(int *a, const int n); int main() { int x[] = {1,3,5,7,9,0,2,4,6,8}; SelectSort(x,10); for(int k=0; k<10; k++) cout << x[k] << endl; return 0; } void SelectSort(int *list, const int n) { // i<n for(int i=0; i<n-1; i++) { int min = i; //min就是毛巾,毛巾是数组的下标 for(int j=i+1; j<n; j++) { if(list[j] < list[min]) min = j; } swap(list[i],list[min]); } }
31.折半查找
v#include <iostream> using namespace std; int BinarySearch(int *a, const int x, const int n); int BinSearch(int *a, const int x, const int n); int main() { int x[] = {1,2,3,4,5,6,7,8,9,10}; int 结果; int num; num = 6; 结果 = BinSearch(x, num, 10); if(结果 < 0) cout << "没找到! " << endl; else cout << "在x[" << 结果 << "]找到" << num << endl; return 0; } int BinSearch(int *a, const int x, const int n) { int left = 0, right = n-1; while(left<=right) { int middle = (left + right)/2; if(x < a[middle]) right = middle-1; else if(x > a[middle]) left=middle+1; else return middle; } return -1; } int BinarySearch(int *a, const int x, const int n) { int low, high, mid; low = 0, high = n-1; while(low<=high) { mid = (low + high) / 2; if(a[mid] == x) return mid; else if(a[mid] < x) low = mid+1; else if(a[mid] > x) high = mid - 1; } return -1; }
#include <iostream> using namespace std; int BinarySearch_I(int *a, const int x, const int n); int BinarySearch_R(int *a, const int x, const int left, const int right); int main() { int m[] = {1,2,3,4,5,6,7,8,9}; int 结果; int num = 7; if((结果 = BinarySearch_R(m,num,0,8))<0) { cout << "递归算法: 没找到!" << endl; }else{ cout << "递归算法: 在m[" << 结果 << "]找到" << num << endl; } if((结果 = BinarySearch_I(m,num,9))<0) { cout << "迭代算法: 没找到!" << endl; }else{ cout << "迭代算法: 在m[" << 结果 << "]找到" << num << endl; } return 0; } int BinarySearch_I(int *a, const int x, const int n) { int left = 0, right = n-1; while(left <= right) { int middle = (left+right)/2; if(x<a[middle]) right = middle-1; else if(x>a[middle]) left = middle + 1; else return middle; } return -1; } int BinarySearch_R(int *a, const int x, const int left, const int right) { if(left<=right) { int middle = (left+right)/2; if(x<a[middle]) return BinarySearch_R(a,x,left,middle-1); else if(x>a[middle]) return BinarySearch_R(a,x,middle+1,right); else return middle; } return -1; }
32.排列组合
#include <iostream> using namespace std; //字符，开始的下标，最后的下标 void Permutations(char *p,const int k,const int m) { //k的变换， Permutations(p,k+1,m)中的k+1赋值给了k if(k==m)//已经到了最后一个，不需要递归 { cout<<"ddddddddddddd"<<endl; for(int i=0;i<=m;i++) cout<<p[i]; cout<<endl; } else{ for(int i=k;i<=m;i++ ) { swap(p[k],p[i]);//调换开头 abc，让 a,b,c依次开头 Permutations(p,k+1,m);//加入确定了 a 继续让bc依次递归 swap(p[k],p[i]);//还原 } } } int main() { char s[]="abc"; Permutations(s,0,2); return 0; }
33.快速排序
#include <iostream> using namespace std; template<class T> void QuickSort(T *a, const int left, const int right) { if(left<right) { //选枢轴 int i = left; int j = right+1; //为什么要加一? int pivot = a[left]; //划分算法 do{ do i++; while(a[i]<pivot); do j--; while(a[j]>pivot); if(i<j) swap(a[i],a[j]); }while(i<j); swap(a[left],a[j]); QuickSort(a,left,j-1); QuickSort(a,j+1,right); } } int main() { int k[] = {8,6,4,2,0,1,3,5,7,9,99}; QuickSort(k,0,9); for(int i=0; i<10; i++) cout << k[i] << endl; return 0; }
34.约瑟夫问题
据说著名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后，39个犹太人与Josephus以及他的朋友多到一个洞中，39个犹太人决定死也不要被敌人抓住，于是决定了一个自杀方式，41个人排成一个园圈，由第1个人开始报数，每报道第3个个就必须自杀，然后再由下一个重新报数，直到所有人自杀身亡为止。
然而Josephus和它的朋友安排在第16个和第31个为止，于是逃过了这场死亡游戏。
程序模拟给出了死亡游戏自杀顺序。
//n个人围圈报数，报m出列，最后剩下的是几号？ #include <stdio.h> #include <stdlib.h> typedef struct node { int data;//存储了排列的序号。 struct node *next; }node; //创建循环链表 node *create(int n) { node *p = NULL, *head; head = (node*)malloc(sizeof (node )); p = head; node *s; int i = 1; if( 0 != n ) { //尾后插入法 while( i <= n ) { s = (node *)malloc(sizeof (node)); s->data = i++; // 为循环链表初始化，第一个结点为1，第二个结点为2。 p->next = s; p = s; } s->next = head->next;//最后一个节点指向第一个节点(不是头节点) } free(head);//删除头节点 return s->next ;//返回第一个节点 } int main() { int n = 41; int m = 3; int i; node *p = create(n); node *temp; m %= n; // m在这里是等于3 while (p != p->next )//链表剩下最后一个 { for (i = 1; i < m-1; i++)//找到第一个节点 { p = p->next ;//p指向第二节点 } printf("%d->", p->next->data );//打印第三个节点的数值 temp = p->next ; //删除第m个节点 p->next = temp->next ; free(temp); p = p->next ;//p是第四个节点 } printf("%d ", p->data );//打印最后一个 return 0; }