数据结构

引言

仅用于本人考试复习使用。

顺序表的基本操作

注意插入和删除时的逻辑关系。

#include <stdio.h>
#include <malloc.h>
#define OK 1 
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int

typedef struct {
    int* elem;
    int length;
    int listsize;
} SqList;

int InitList_Sq(SqList& L) {
    L.elem = (int*)malloc(LIST_INIT_SIZE * sizeof(int));
    if (!L.elem) return ERROR;  
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return OK;
}

int Load_Sq(SqList& L) {
    if (L.length == 0) {
        printf("The List is empty!");
    }
    else {
        printf("The List is: ");
        for (int i = 0; i < L.length; i++) {
            printf("%d ", L.elem[i]);
        }
    }
    printf("\n");
    return OK;
}

int ListInsert_Sq(SqList& L, int i, int e) {
    if (i < 1 || i > L.length + 1) return ERROR;

    if (L.length >= L.listsize) {
        int* new_elem = (int*)realloc(L.elem, sizeof(int) * (L.listsize + LISTINCREMENT));
        if (!new_elem) return ERROR; 
        L.elem = new_elem;
        L.listsize += LISTINCREMENT;
    }

    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 OK;
}

int ListDelete_Sq(SqList& L, int i, int& e) {
    if (i < 1 || i > L.length) return ERROR;

    e = L.elem[i - 1]; 

    for (int j = i; j < L.length; j++) {
        L.elem[j - 1] = L.elem[j];
    }

    L.length--;
    return OK;
}

int main() {
    SqList T;
    int a, i;
    ElemType e, x;

    if (InitList_Sq(T)) {
        printf("A Sequence List Has Created.\n");
    }
    else {
        printf("Failed to create the list.\n");
        return 1;
    }

    while (1) {
        printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
        scanf("%d", &a);
        switch (a) {
        case 1:
            scanf("%d%d", &i, &x);
            if (!ListInsert_Sq(T, i, x)) {
                printf("Insert Error!\n");
            }
            else {
                printf("The Element %d is Successfully Inserted!\n", x);
            }
            break;
        case 2:
            scanf("%d", &i);
            if (!ListDelete_Sq(T, i, e)) {
                printf("Delete Error!\n");
            }
            else {
                printf("The Element %d is Successfully Deleted!\n", e);
            }
            break;
        case 3:
            Load_Sq(T);
            break;
        case 0:
            return 0;
        default:
            printf("Invalid choice!\n");
        }
    }
}

合并顺序表

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{	
	vector<int>a;
	vector<int>b;
	int n;
	cin >> n;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		a.push_back(x);
	}

	int m;
	cin >> m;
	for(int i=0;i<m;i++)
	{
		int  x;
		cin >> x;
		b.push_back(x);
		 }
	vector<int>c=a;
	for (int i=0;i<m;i++)
	{
		c.push_back(b[i]);
	}
	sort(c.begin(),c.end());
	cout << "List A:";
	for (int num:a)
	{
		cout <<num<<' ';
	}
	cout << endl;
	cout << "List B:";
	for (int num:b)
	{
		cout << num << ' ';
	}
	cout << endl;
	cout << "List C:";
	for (int num:c)
	{
		cout << num << ' ';
	}
	return 0;
}

顺序表的逆置

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	vector<int>a;
	int n;
	cin >> n;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		a.push_back(x);
	}
	cout << "The List is:";
	for (int num:a)
	{
		cout << num<<' ';
	}
	cout << endl;
	reverse(a.begin(),a.end());
	cout <<"The turned List is:";
	for (int num:a)
	{
		cout << num << ' ';
	}

	return 0;
}

链表的基本操作

#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1 
#define ElemType int

typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode, * LinkList;

int CreateLink_L(LinkList& L, int n) {
	// 创建含有n个元素的单链表
	LinkList p, q;
	int i;
	ElemType e;
	L = new LNode;
	L->next = NULL;              // 先建立一个带头结点的单链表
	q = L;
	for (i = 0; i < n; i++) {
		scanf("%d", &e);
		p = new LNode;// 生成新结点
		p->data = e;
		q->next = p;
		p->next = NULL;
		q = p;
	}
	return OK;
}

int LoadLink_L(LinkList& L) {
	// 单链表遍历
	LinkList p = L->next;
	if (!p)printf("The List is empty!"); // 请填空
	else
	{
		printf("The LinkList is:");
		while (p)    // 请填空
		{
			printf("%d ", p->data);
			p = p->next;    // 请填空
		}
	}
	printf("\n");
	return OK;
}

int LinkInsert_L(LinkList& L, int i, ElemType e) {
	// 算法2.9
	// 在带头结点的单链线性表L中第i个位置之前插入元素e
	if (i<1)
	{
		return ERROR;
	}

	LinkList p = L;
	int count = 0;
	while (p&&count<i-1)
	{
		p = p->next;
		count++;
	}
	if (!p)
	{
		return ERROR;
	}
	LinkList r = new LNode;
	r->data = e;
	r->next = p->next;
	p->next = r;
	return OK;
}

int LinkDelete_L(LinkList& L, int i, ElemType& e) {
	// 算法2.10
	// 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值

	if (i<1)
	{
		return ERROR;
	}

	LinkList p = L;
	int count = 0;
	while (p&&count<i-1)
	{
		p = p->next;
		count++;
	}
	if (!p||!p->next)
	{
		return ERROR;
	}
	e = p->next->data;
	LinkList q = p->next;
	p->next = q->next;
	delete q;
	return OK;
}

int main()
{
	LinkList T;
	int a, n, i;
	ElemType x, e;
	printf("Please input the init size of the linklist:\n");
	scanf("%d", &n);
	printf("Please input the %d element of the linklist:\n", n);
	if (CreateLink_L(T,n))     // 判断链表是否创建成功，请填空
	{
		printf("A Link List Has Created.\n");
		LoadLink_L(T);
	}
	while (1)
	{
		printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
		scanf("%d", &a);
		switch (a)
		{
		case 1: scanf("%d%d", &i, &x);
			if (!LinkInsert_L(T,i,x)) printf("Insert Error!\n"); // 判断i值是否合法，请填空
			else printf("The Element %d is Successfully Inserted!\n", x);
			break;
		case 2: scanf("%d", &i);
			if (!LinkDelete_L(T,i,e)) printf("Delete Error!\n"); // 判断i值是否合法，请填空
			else printf("The Element %d is Successfully Deleted!\n", e);
			break;
		case 3: LoadLink_L(T);
			break;
		case 0: return 1;
		}
	}
}

合并链表（不带头结点）

#include<iostream>
using namespace std;

typedef struct lianbiao
{
	int data;
	struct lianbiao* next;
}node,*list;

void createlist(list&T,int n)
{	
	if (!n)
	{	
		cout << "error!" << endl;
		return;
	}
	T = new node;
	cin >> T->data;
	T->next = nullptr;
	list q = T;
	for (int i=1;i<n;i++)
	{	
		list p = new node;
		cin>>p->data;
		p->next = nullptr;
		q->next = p;
		q = p;
	}
}


void printlist(list L)
{	
	if (!L)
	{	
		cout << "list is empty!"<<endl;
		return;
	}
	list p = L;
	while (p)
	{
		cout << p->data<<' ';
		p = p->next;
	}
	cout << endl;
}

list merge(list a,list b)
{
	if (!a||!b) return nullptr;
	list head = nullptr;
	list tail = nullptr;

	if (a->data<=b->data)
	{
		head = a;
		a = a->next;
	}

	else {
		head = b;
		b = b->next;
	}
	tail = head;
	while (a&&b)
	{
		if (a->data<=b->data)
		{
			tail->next = a;
			a = a->next;
		}

		else
		{
			tail->next = b;
			b = b->next;
		}

		tail = tail->next;
	}
	tail->next = a ? a : b;
	return head;
}



int main()
{
	list a, b,c;
	int n, m;
	cin >> n;
	createlist(a,n);
	cin >> m;
	createlist(b,m);
	cout << "List A:";
	printlist(a);
	cout << "List B:";
	printlist(b);
	c=merge(a,b);
	cout << "List C:";
	printlist(c);
	return 0;
}

反转链表

void reverseList(LNode*&L)
{  LNode* p = L->next;
   LNode* q=p->next;
   LNode* r = nullptr;
   delete L;
   while (q)
   {
       p->next = r;
       r = p;
       p = q;
       q = q->next;
   }
   p->next = r;
   L = new LNode;
   L->next = p;
}

栈的基本操作

#include<malloc.h> 
#include<stdio.h> 
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10 // 存储空间分配增量

typedef int SElemType; // 定义栈元素类型
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等

struct SqStack
{
	SElemType* base; // 在栈构造之前和销毁之后，base的值为NULL
	SElemType* top; // 栈顶指针
	int stacksize; // 当前已分配的存储空间，以元素为单位
}; // 顺序栈

Status InitStack(SqStack& S)
{
	// 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE
	S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if (!S.base)
	{
		return ERROR;
	}
	S.stacksize = STACK_INIT_SIZE;
	S.top=S.base;
	return OK;
}

Status Push(SqStack& S, SElemType e)
{
	// 在栈S中插入元素e为新的栈顶元素
	if (S.top-S.base>=S.stacksize)
	{
		S.base = (SElemType*)realloc(S.base,sizeof(SElemType)*(S.stacksize+STACKINCREMENT));
		if (!S.base)
		{
			return ERROR;
		}
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;	
	return OK;
}

Status Pop(SqStack& S, SElemType& e)
{
	// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
	if (S.top==S.base)
	{
		return ERROR;
	}

	e = *--S.top;
	return OK;
}

Status GetTop(SqStack S, SElemType& e)
{
	// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
	if (S.top==S.base)
	{
		return ERROR;
	}

	e = *(S.top - 1);
	return OK;
}

int StackLength(SqStack S)
{
	// 返回栈S的元素个数
	return S.top - S.base;

}

Status StackTraverse(SqStack S)
{
	// 从栈顶到栈底依次输出栈中的每个元素
	SElemType* p = S.top;        //请填空
		if (p==S.base)printf("The Stack is Empty!"); //请填空
		else
		{
			printf("The Stack is: ");
			while (p!=S.base)            //请填空
			{
				p--;               //请填空
					printf("%d ", *p);

			}
		}
	printf("\n");
	return OK;
}

int main()
{
	int a;
	SqStack S;
	SElemType x, e;
	if (InitStack(S))    // 判断顺序表是否创建成功，请填空
	{
		printf("A Stack Has Created.\n");
	}
	while (1)
	{
		printf("1:Push \n2:Pop \n3:Get the Top \n4:Return the Length of the Stack\n5:Load the Stack\n0:Exit\nPlease choose:\n");
		scanf("%d", &a);
		switch (a)
		{
		case 1: scanf("%d", &x);
			if (!Push(S,x)) printf("Push Error!\n"); // 判断Push是否合法，请填空
			else printf("The Element %d is Successfully Pushed!\n", x);
			break;
		case 2: if (!Pop(S,e)) printf("Pop Error!\n"); // 判断Pop是否合法，请填空
			  else printf("The Element %d is Successfully Poped!\n", e);
			break;
		case 3: if (!GetTop(S,e))printf("Get Top Error!\n"); // 判断Get Top是否合法，请填空
			  else printf("The Top Element is %d!\n", e);
			break;
		case 4: printf("The Length of the Stack is %d!\n", StackLength(S)); //请填空
			break;
		case 5: StackTraverse(S);  //请填空
			break;
		case 0: return 1;
		}
	}
}

循环队列的应用

这里注意循环队列空的是条件是Q.rear==Q.front，超过最大size的条件是(Q.rear+1)%MAXQSIZE==Q.front，删除和更新时的操作是(Q.rear+1)%MAXQSIZE和(Q.front+1)%MAXQSIZE，个数是(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE。

#include<malloc.h> 
#include<stdio.h> 
#define OK 1
#define ERROR 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int QElemType;
#define MAXQSIZE 100 // 最大队列长度(对于循环队列，最大队列长度要减1)

typedef struct
{
	QElemType* base; // 初始化的动态分配存储空间
	int front; // 头指针,若队列不空,指向队列头元素
	int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置
}SqQueue;

Status InitQueue(SqQueue& Q)
{
	Q.base = (QElemType*)malloc(sizeof(QElemType)*MAXQSIZE);
	if (!Q.base)  return ERROR;
	Q.front = Q.rear=0;
	return OK;
}

Status EnQueue(SqQueue& Q, QElemType e)
{
	if ((Q.rear + 1) % MAXQSIZE == Q.front)
	{
		return ERROR;
	}
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MAXQSIZE;
	return OK;
}



Status DeQueue(SqQueue& Q, QElemType& e)
{
	// 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR
	if (Q.front==Q.rear)
	{
		return ERROR;
	}
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXQSIZE;
	return OK;
}

Status GetHead(SqQueue Q, QElemType& e)
{
	// 若队列不空，则用e返回队头元素，并返回OK，否则返回ERROR
	if (Q.rear == Q.front) return ERROR;
	e= Q.base[Q.front];
	return OK;
}

int QueueLength(SqQueue Q)
{
	// 返回Q的元素个数
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;

}

Status QueueTraverse(SqQueue Q)
{
	// 若队列不空，则从队头到队尾依次输出各个队列元素，并返回OK；否则返回ERROR.
	int i;
	i = Q.front;
	if (Q.rear==Q.front)printf("The Queue is Empty!");  //请填空
	else {
		printf("The Queue is: ");
		while (i!=Q.rear)     //请填空
		{
			printf("%d ", Q.base[i]);   //请填空
			i = (i+1)%MAXQSIZE;   //请填空
		}
	}
	printf("\n");
	return OK;
}

int main()
{
	int a;
	SqQueue S;
	QElemType x, e;
	if (InitQueue(S))    // 判断顺序表是否创建成功，请填空
	{
		printf("A Queue Has Created.\n");
	}
	while (1)
	{
		printf("1:Enter \n2:Delete \n3:Get the Front \n4:Return the Length of the Queue\n5:Load the Queue\n0:Exit\nPlease choose:\n");
		scanf("%d", &a);
		switch (a)
		{
		case 1: scanf("%d", &x);
			if (!EnQueue(S,x)) printf("Enter Error!\n"); // 判断入队是否合法，请填空
			else printf("The Element %d is Successfully Entered!\n", x);
			break;
		case 2: if (!DeQueue(S,e)) printf("Delete Error!\n"); // 判断出队是否合法，请填空
			  else printf("The Element %d is Successfully Deleted!\n", e);
			break;
		case 3: if (!GetHead(S,e))printf("Get Head Error!\n"); // 判断Get Head是否合法，请填空
			  else printf("The Head of the Queue is %d!\n", e);
			break;
		case 4: printf("The Length of the Queue is %d!\n", QueueLength(S));  //请填空
			break;
		case 5: QueueTraverse(S);//请填空
			break;
		case 0: return 1;
		}
	}
}

栈的应用–进制转换

其实数组也可以做。。

#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
int main()
{	
	int n;
	cin >> n;
	stack<int>s;
	while (n)
	{
		s.push(n % 8);
		n /= 8;
	}
	while (!s.empty())
	{
		cout << s.top();
		s.pop();
	}
	return 0;
}

括号匹配检验

其实逻辑挺简单的，用栈来找括号匹不匹配，读到左括号入栈，读到右括号分两种情况，空的话就直接判定失败输出结果，不空再判定

栈顶的括号是否对的上，最后再来根据栈是否为空来判断结果。

#include<iostream>
#include<stack>
#include<string>
using namespace std;

int main()
{
	stack<char>s;
	string str;
	getline(cin,str);
	for (int i=0;i<str.size();i++)
	{
		if (str[i]=='('||str[i]=='['||str[i]=='{')
		{
			s.push(str[i]);
		}

		else if (str[i]==')'||str[i]==']'||str[i]=='}')
		{
			if (s.empty())
			{
				cout << "lack of left parenthesis"<<endl;
				return 0;
			}

			else
			{	
				auto p = s.top();

				if (str[i]==')')
				{
					if (p == '(')
					{
						s.pop();
					}

					else
					{
						cout << "isn't matched pairs" << endl;
						return 0;
					}
				}
				if (str[i] == ']')
				{
					if (p == '[')
					{
						s.pop();
					}

					else
					{
						cout << "isn't matched pairs" << endl;
						return 0;
					}
				}
				if (str[i]=='}')
				{
					if (p == '{')
					{
						s.pop();
					}

					else
					{
						cout << "isn't matched pairs" << endl;
						return 0;
					}
				}
			}
		}
	}
	if (!s.empty())
	{
		cout << "lack of right parenthesis" << endl;
	}
	else
	{
		cout << "matching" << endl;
	}
	return 0;
}

行编辑程序

框架已经给出来了，只要填的话还是比较简单的。

typedef char SElemType;
#include"malloc.h" 
#include"stdio.h"
#include"math.h"
#include"stdlib.h" // exit()
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACKINCREMENT 2 // 存储空间分配增量
struct SqStack
{
    SElemType* base; // 在栈构造之前和销毁之后，base的值为NULL
    SElemType* top; // 栈顶指针
    int stacksize; // 当前已分配的存储空间，以元素为单位
}; // 顺序栈

Status InitStack(SqStack& S)
{ 
    S.base = (SElemType*)malloc(sizeof(SElemType)*STACK_INIT_SIZE);
    if (!S.base)
    {
        return ERROR;
    }
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}
Status StackEmpty(SqStack S)
{ // 若栈S为空栈，则返回TRUE，否则返回FALSE
    if (S.top == S.base)
    {
        return TRUE;
    }
    else return FALSE;
}
Status ClearStack(SqStack& S)
{ // 把S置为空栈
    S.top = S.base;
    return OK;
}
Status DestroyStack(SqStack& S)
{ // 销毁栈S，S不再存在
    free(S.base);
    S.base = NULL;
    S.top = NULL;
    S.stacksize = 0;
    return OK;
}
Status Push(SqStack& S, SElemType e)
{ // 插入元素e为新的栈顶元素
    if (S.top-S.base>=S.stacksize)
    {
        S.base = (SElemType*)realloc(S.base,sizeof(SElemType)*(S.stacksize+STACKINCREMENT));
        if (!S.base)
        {
            return ERROR;
        }
        S.top = S.base+S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
   * S.top++ = e;
   return OK;
}
Status Pop(SqStack& S, SElemType& e)
{ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
    if (S.top==S.base)
    {
        return ERROR;
    }
    e = *--S.top;
    return OK;
}
Status StackTraverse(SqStack S, Status(*visit)(SElemType))
{ // 从栈底到栈顶依次对栈中每个元素调用函数visit()。
  // 一旦visit()失败，则操作失败
    while (S.top > S.base)
        visit(*S.base++);
    printf("\n");
    return OK;
}
Status visit(SElemType c)
{
    printf("%c", c);
    return OK;
}
void LineEdit()
{ // 利用字符栈s，从终端接收一行并送至调用过程的数据区。算法3.2
    SqStack s;
    char ch, c;
    int n, i;
    InitStack(s);
    scanf("%d", &n);
    ch = getchar();
    for (i = 1; i <= n; i++)
    {
        ch = getchar();
        while (ch != '\n')
        {
            switch (ch)
            {
            case '#':Pop(s, c);
                break; // 仅当栈非空时退栈
            case '@':ClearStack(s);
                break; // 重置s为空栈
            default:Push(s,ch); // 有效字符进栈
            }
            ch=getchar(); // 从终端接收下一个字符
        }
        StackTraverse(s, visit); // 将从栈底到栈顶的栈内字符输出
        ClearStack(s); // 重置s为空栈
    }
    DestroyStack(s);
}
int main()
{
    LineEdit();
    return 0;
}

汉诺塔

之后会试着用递归的方法做一下。。

#include<iostream>
using namespace std;

void hanoi(int n,char from,char to,char aux)
{
	if (n==1)
	{
		cout << from << "->" << n << "->" << to<<endl;
		return;
	}
	hanoi(n-1,from,aux,to);
	cout << from << "->" << n << "->" << to<<endl;
	hanoi(n-1,aux,to,from);
}


int main()
{
	int n;
	char a, b, c;
	cin >> n >> a >> b >> c;
	hanoi(n,a,b,c);
	return 0;
}

阿克曼函数

这是一道水题。照着题目就能写出来。。

#include<iostream>
using namespace std;

int akm(int m,int n)
{
	if (m==0)
	{
		return n + 1;
	}

	else if (m>0&&n==0)
	{
		return akm(m-1,1);
	}

	else if (m>0&&n>0)
	{
		return akm(m-1,akm(m,n-1));
	}
}


int main()
{

	int n,m;
	cin >> m>>n;
	cout<<akm(m,n);

	return 0;
}

求next数组和kmp算法

没啥好说的，就纯靠记忆吧

void get_next(SString T, int next[]) {
    // 算法4.7
    // 求模式串T的next函数值并存入数组next
       // 请补全代码
    int i = 1;
    int j = 0;
    next[1] = 0;
    while (i<T[0])
    {
        if (j==0||T[i]==T[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

int Index_KMP(SString S, SString T, int pos) {
    // 算法4.6
    // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置
    // KMP算法。请补全代码
    int i = pos;
    int j = 1;
    while (i <= S[0] && j <= T[0])
    {
        if (j == 0 || T[j] == S[i])
        {
            i++;
            j++;

        }
        else j = next[j];
    }
    if (j > T[0])
    {
        return i - T[0];
    }

    else return 0;

}

不完整的排序

用双指针的方法进行排序

#include<iostream>
#include<vector>
using namespace std;


int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		vector<int>nums(n);
		for (int&p:nums)
		{
			cin >> p;
		}
		int i = 0, j = n - 1;
		while (i<j)
		{	
			int flag1=1,flag2=1;
			if (nums[i]<=0)
			{
				i++;
				flag1 = 0;
			}

			if (nums[j]>0)
			{
				j--;
				flag2 = 0;
			}

			if (flag1&&flag2)
			{
				swap(nums[i],nums[j]);
			}
		}
		for (int k:nums)
		{
			cout << k<<' ';
		}
		cout << endl;
	}

	return 0;
}

二叉树的基本操作

#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int  Status;

typedef char  ElemType;
typedef struct BiTNode {
    ElemType data;
    struct BiTNode* lchild, * rchild;//左右孩子指针
} BiTNode, * BiTree;

Status CreateBiTree(BiTree& T) {  // 算法6.4
    // 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
    // 构造二叉链表表示的二叉树T。
    char ch;
    scanf("%c", &ch);
    if (ch == '#') T = NULL;
    else {
        if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) return ERROR;
        T->data = ch; // 生成根结点
        CreateBiTree(T->lchild);   // 构造左子树
        CreateBiTree(T->rchild);  // 构造右子树
    }
    return OK;
} // CreateBiTree





Status PreOrderTraverse(BiTree T) {
    // 前序遍历二叉树T的递归算法
    //补全代码,可用多个语句
    if (!T)
    {
        return 0;
    }
    printf("%c",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
} // PreOrderTraverse

Status InOrderTraverse(BiTree T) {
    // 中序遍历二叉树T的递归算法
   //补全代码,可用多个语句
    if (!T)
    {
        return 0;
    }

    InOrderTraverse(T->lchild);
    printf("%c",T->data);
    InOrderTraverse(T->rchild);

} // InOrderTraverse

Status PostOrderTraverse(BiTree T) {
    // 后序遍历二叉树T的递归算法
    //补全代码,可用多个语句
    if (!T)
    {
        return 0;
    }

    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c",T->data);

} // PostOrderTraverse



int main()   //主函数
{   
    BiTree T;
    CreateBiTree(T);
    PreOrderTraverse(T);
    printf("\n");
    InOrderTraverse(T);
    printf("\n");
    PostOrderTraverse(T);
    printf("\n");
}//main

求二叉树各种结点数

这个代码的话其实挺简单的，但是要注意细节，不要漏了情况

#include<iostream>
using  namespace std;

typedef struct tr
{
	char data;
	struct tr * lchild;
	struct tr* rchild;
}binode,*bitree;

void createbitree(bitree &T)
{	
	T = new binode;
	char ch;
	cin >> ch;
	if (ch=='#')
	{
		T = NULL;
		return;
	}
	T->data = ch;
	createbitree(T->lchild);
	createbitree(T->rchild);
}

int node0(bitree&T)
{	
	if (!T)
	{
		return 0;
	}

	if (!T->lchild&&!T->rchild)
	{
		return 1;
	}

	return node0(T->lchild)+node0(T->rchild);
}

int node1(bitree&T)
{
	if(!T)
	{
		return 0;
	}

	if ((T->lchild&&!T->rchild)||(!T->lchild&&T->rchild))
	{
		return 1+node1(T->lchild)+node1(T->rchild);
	}

	return node1(T->lchild) + node1(T->rchild);
}

int node2(bitree&T)
{
	if (!T)
	{
		return 0;
	}

	if (T->lchild&&T->rchild)
	{
		return 1+ node2(T->lchild) + node2(T->rchild);

	}

	return node2(T->lchild) + node2(T->rchild);
}


int main()
{
	bitree T;
	createbitree(T);
	cout << node2(T)<<endl;
	cout << node1(T) << endl;
	cout <<  node0(T) << endl;

	return 0;
}

二叉树的最大宽度

思路：首先分配连续的一片空间，接着创建二叉树，利用广度优先搜索遍历二叉树，得到最大的宽度。

#include<iostream>
#include<queue>
using namespace std;

typedef struct tr {
	int data;
	struct tr* lchild;
	struct tr* rchild;
}binode,*bitree;


bitree createbitree(int n)
{	

	bitree* node = new bitree[n + 1];
	for (int i=1;i<=n;i++)
	{
		node[i] = new binode;
		node[i]->data = i;
		node[i]->lchild = nullptr;
		node[i]->rchild = nullptr;
	}

	for (int i=1;i<=n-1;i++)
	{
		int x, y;
		cin >> x >> y;
		if (!node[x]->lchild)
		{
			node[x]->lchild = node[y];
		}

		else node[x]->rchild = node[y];
	}

	bitree root=node[1];

	return root;
}


void postorder(bitree T)
{
	if (!T)
	{
		return;
	}

	postorder(T->lchild);
	postorder(T->rchild);
	cout << T->data;
}

int bfs(bitree T)
{	
	if (!T)
	{
		return 0;
	}
	queue<bitree>q;
	q.push(T);
	int maxwidth=0;
	while (!q.empty())
	{
		int level_size = q.size();
		maxwidth = max(maxwidth,level_size);
		for (int i=0;i<level_size;i++)
		{	
			bitree current = q.front();
			q.pop();
			if (current->lchild)
			{
				q.push(current->lchild);
			}

			if (current->rchild)
			{
				q.push(current->rchild);
			}
		}
	}
	return maxwidth;
}

int main()
{
	int n;
	cin >> n;
	bitree T;
	T=createbitree(n);
	cout << bfs(T);
	return 0;
}

二叉树的遍历运算

思路：记得构建左右子树的参数。。

#include<iostream>
#include<cstring>
using namespace std;
char pre[1000], in[1000], post[1000];

void Post(char pre[],char in[],int len,int postroot)//函数参数为前序序列，中序序列，树的结点数，以及后序序列的根节点
{
	if (len<=0)//递归结束条件：长度小于等于0
	{
		return;
	}
	char root = pre[0];
	int i = 0;
	while (len > 0 && in[i] != pre[0]) i++;//得到先序序列中第一个元素在中序序列中的位置
	Post(pre+1,in,i,postroot-(len-i));//构建左子树
	Post(pre+i+1,in+i+1,len-i-1,postroot-1);//构建右子树
	post[postroot] = root;//将先序序列中的第一个元素赋给后序序列的最后一个元素
}

int main()
{

	cin >> pre >> in;
	int len = strlen(in);
	Post(pre,in,len,len-1);
	cout << post<<endl;
	return 0;
}

二叉树的直径

建树方法和上面的一样，利用了静态变量。。

#include<iostream>
#include<queue>
using namespace std;

typedef struct tr
{
	int data;
	struct tr* lchild;
	struct tr* rchild;
}binode,*bitree;

bitree createbitree(int n)
{
	bitree* node = new bitree[n + 1];

	for (int i=1;i<=n;i++)
	{	
		node[i] = new binode;
		node[i]->data = i;
		node[i]->lchild = nullptr;
		node[i]->rchild = nullptr;
	}
	for (int i=1;i<=n-1;i++)
	{
		int x, y;
		cin >> x >> y;
		if (!node[x]->lchild)
		{
			node[x]->lchild = node[y];
		}

		else node[x]->rchild = node[y];
	}

	bitree root = node[1];
	return root;
}


int deep(bitree&T)
{
	if (!T)
	{
		return 0;
	}
	return max(deep(T->lchild),deep(T->rchild))+1;
}

int radius(bitree&T)
{
	static int ans = 0;
	 ans = max(deep(T->lchild)+deep(T->rchild),ans);
	 if (T->lchild)
	 {
		 radius(T->lchild);
	 }
	 if (T->rchild)
	 {
		 radius(T->rchild);
	}
	 return ans;
}

int main()
{	
	int n;
	cin >> n;
	bitree T = createbitree(n);
	cout << radius(T);
	return 0;
}

顺序查找

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int>nums(n);
	for (int &k:nums)
	{
		cin >> k;
	}
	int key;
	cin >> key;
	int i;
	for ( i=0;i<n;i++)
	{
		if (nums[i]==key)
		{
			cout << "The element position is " << i + 1<<'.';
			break;
		}
	}

	if (i==n)
	{
		cout << "The element is not exist.";
	}

	return 0;
}

二分查找

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


int main()
{
	
	int n;
	cin >> n;
	vector<int>nums;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}
	int k;
	cin >> k;
	int low = 0, high = n - 1;
	while (low<=high)
	{
		int mid = (low+high) / 2;
		if (nums[mid] == k)
		{	
			cout << "The element position is " << mid<<'.';
			return 0;
		}

		else if (nums[mid] < k)
		{
			low = mid + 1;
		}

		else high = mid - 1;
	}

	cout << "The element is not exist.";
	return 0;
}

哈希查找

还能怎么说呢，纯靠记忆呗。。

unsigned Hash(ElemType K)
{ /* 一个简单的哈希函数*/
	return K * 3 % length;
}
void collision(int* p) /*线性探测再散列 */
{ /* 开放定址法处理冲突 */
	*p = (*p + 1) % length;
}

直接插入排序

简单说明一下思路：其实就是将每个元素与其前面的已经排好的序列，寻找插入的位置，找到第一个离自己最近的比自己小的元素，再插入在其后面。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{	
	vector<int>nums;
	int n;
	cin >> n;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}
	for (int i=1;i<nums.size();i++)
	{	
		int tmp = nums[i];
		int j;
		for (j=i-1;j>=0;j--)
		{
			if (nums[j]<tmp)
			{
				break;
			}
		}
		for (int k=i-1;k>j;k--)
		{
			nums[k + 1] = nums[k];
		}
		nums[j + 1] = tmp;
		for (int p:nums)
		{
			cout << p << ' ';
		}
		cout << endl;

	}
	return 0;
}

折半插入排序

思路：和插入排序的思路差不多，不过寻找元素的过程换成了二分查找。插入位置是nums[low].

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{	
	vector<int>nums;
	int n;
	cin >> n;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}
	for (int i=1;i<nums.size();i++)
	{
		int tmp = nums[i];
		int low = 0;
		int high = i - 1;
		while (low<=high)
		{
			int mid = (low+high) / 2;
			if (nums[mid] < tmp)
			{
				low = mid + 1;
			}

			else high = mid - 1;
		}
		for (int j=i-1;j>=low;j--)
		{
			nums[j + 1] = nums[j];
		}
		nums[low] = tmp;
		for (int p:nums)
		{
			cout << p << ' ';
		}
		cout << endl;

	}
	return 0;
}

希尔排序

思路：直接插入排序的改进算法，时间复杂度优化为O(n^1.3)，思路在于找一个gap，每次排序得到一个基本有序序列，最后gap一定为1，保证排完序之后序列一定有序。

#include<iostream>
#include<vector>
using namespace std;



int main()
{
	int n;
	cin >> n;
	vector<int>nums;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}
	for (int gap=n/2;gap>0;gap/=2)
	{	
		for (int i=gap;i<n;i++)
		{
			int tmp = nums[i];
			int j;
			for (j=i;j>=gap&&nums[j-gap]>=tmp;j-=gap)
			{
				nums[j] = nums[j - gap];
			}
			nums[j] = tmp;
		}
		for (int k:nums)
		{
			cout << k << ' ';
		}
		cout << endl;
	}


	return 0;
}

冒泡排序

思路：其实就是把元素与下有一个元素进行比较，如果下一个元素更小的话就把两个元素交换，依次将最大的元素排到后面。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{	
	vector<int>nums;
	int n;
	cin >> n;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}
	for (int i=nums.size()-1;i>0;i--)
	{
		int flag=1;
		for (int j=0;j<i;j++)
		{
			if (nums[j]>nums[j+1])
			{	
				flag = 0;
				swap(nums[j],nums[j+1]);
			}
		}
		for (int k:nums)
		{
			cout << k<<' ';
		}
		if (flag)
		{
			break;
		}
		cout << endl;
	}
	return 0;
}

快速排序

思路：任选一个标兵，将比标兵大的元素派右边，比标兵小的元素排左边，然后再对已排好的序列进行相同的操作，此处用递归的方式实现。

#include<iostream>
#include<vector>
using namespace std;

void quicksort(vector<int>&nums,int low,int high)
{
	if (low<high)
	{	
		int i = low;
		int j = high;
		int x = nums[low];
		while (i<j)
		{	
			while (i<j && nums[j]>=x)
			{
				j--;
			}
			if (i<j)
			{
				nums[i++] = nums[j];
			}
			while (i<j&&nums[i]<=x)
			{
				i++;
			}
			if (i<j)
			{
				nums[j--] = nums[i];
			}
		}
		nums[i] = x;
		for (int k:nums)
		{
			cout << k << ' ';
		}
		cout << endl;
		quicksort(nums,low,i-1);
		quicksort(nums,i+1,high);
	}
}


int main()
{
	int n;
	cin >> n;
	vector<int>nums;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}
	
	quicksort(nums,0,nums.size()-1);

	return 0;
}

简单选择排序

思路：这个的话就是找到当前元素之后的序列中最小的然后在于当前元素交换位置就可以了。。。

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int>nums;
	int n;
	cin >> n;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}
	for (int i=0;i<n-1;i++)
	{	
		int tmp = nums[i];
		int mi = i;
		for (int j=i+1;j<n;j++)
		{
			if (nums[j]<tmp)
			{
				mi = j;
				tmp = nums[j];
			}
		}
		swap(nums[i], nums[mi]);
		for (int k:nums)
		{
			cout << k << ' ';
		}
		cout << endl;
	}
	return 0;
}

堆排序

思路：这个可能是目前为止最难的一个排序算法，，，首先将待排序列构造成一颗完全二叉树，然后再调整为大根堆，调整的算法是从最后一个非叶子节点(2*n-1)往回走，比较与左右孩子的大小，将最大的与根节点交换，然后再对根节点进行相同的操作，然后堆排序没什么好说的，因为每次调整成堆之后最前面的元素一定是最大的，所以每次只要调整完后第一个都与最后一个元素进行交换，再调整剩下的序列，直到整个序列有序为止。。

#include<iostream>
#include<vector>
using namespace std;

void heapif(vector<int>&nums,int n,int i)
{
	int largest = i;
	int left = 2 * i + 1;
	int right = 2 * i + 2;
	if (left<n&&nums[left]>nums[largest])
	{
		largest = left;
	}

	if (right<n&&nums[right]>nums[largest])
	{
		largest = right;
	}

	if (i!=largest)
	{
		swap(nums[largest],nums[i]);
		heapif(nums,n,largest);
	}
}

void load(vector<int>&nums)
{
	for (int k:nums)
	{
		cout << k << ' ';
	}
	cout << endl;
}

void heapsort(vector<int>&nums)
{
	int n = nums.size();
	for (int i=2*n-1;i>=0;i--)
	{
		heapif(nums,n,i);
	}
	for (int i=n-1;i>0;i--)
	{	
		load(nums);
		swap(nums[0],nums[i]);
		heapif(nums,i,0);
	}
	load(nums);
}


int main()
{	
	int n;
	cin >> n;
	vector<int>nums(n);
	for (auto& p : nums)
	{
		cin >> p;
	}
	heapsort(nums);
	return 0;
}

非递归的归并排序

#include <vector>
#include <algorithm>
#include<iostream>
using namespace std;

void load(vector<int>&nums)
{
    for (int i:nums)
    {
        cout << i << ' ';
    }
    cout << endl;
}

void mergesort(vector<int>&nums)
{   
    int n = nums.size();
    vector<int>tmp(n);
    for (int size=1;size<n;size*=2)
    {   
        for (int left=0;left<n;left+=2*size)
        {
            int mid = min(left+size,n);
            int right = min(left+2*size,n);
            int i = left, j = mid, k = left;
            while (i<mid&&j<right)
            {
                if (nums[i] <= nums[j])
                {
                    tmp[k++] = nums[i++];
                }

                else tmp[k++] = nums[j++];
            }

            while (i<mid)
            {
                tmp[k++] = nums[i++];
            }
            while (j<right)
            {
                tmp[k++] = nums[j++];
            }

            for (int p=left;p<right;p++)
            {
                nums[p] = tmp[p];
            }
        }
        load(nums);
    }
}

int main()
{

    int n;
    cin >> n;
    vector<int>nums(n);
    for (int&i:nums)
    {
        cin >> i;
    }
    mergesort(nums);
    return 0;
}

邻接矩阵法表示有向图的存储结构

#include<iostream>
using namespace std;
int main()
{
	int g[100][100] = {0};
	int n, m;
	cin >> n >> m;
	for (int i=0;i<m;i++)
	{
		int x, y;
		cin >> x >> y;
		g[x][y] = 1;
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			cout << g[i][j] << ' ';
		}
		cout << endl;
	}


	return 0;
}

图的深度优先遍历

图的生成代码和其他代码在此省略（主要是太长了。。）

void print(char* i)
{
	printf("%s ", i);
}

/*深度遍历*/
int visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量),未访问标记0，访问标记1 */
void(*VisitFunc)(char* v); /* 函数变量(全局量) */
void DFS(ALGraph G, int v)
{ /* 从第v个顶点出发递归地深度优先遍历图G。算法7.5 */
/* 设置访问标志为TRUE(已访问) */
/* 访问第v个顶点 */
/* 对v的尚未访问的邻接点w递归调用DFS */
	ArcNode* p;
	visited[v] = 1;
	print(G.vertices[v].data);
	for (p=G.vertices[v].firstarc;p;p = p->nextarc)
	{
		if (!visited[p->adjvex])
		{
			DFS(G,p->adjvex);
		}
	}
}
void DFSTraverse(ALGraph G)
{ /* 对图G作深度优先遍历。算法7.4 */
/* 使用全局变量VisitFunc,使DFS不必设函数指针参数 */
/* 访问标志数组初始化 */
/* 对尚未访问的顶点调用DFS */
	int v;
	for (v=0;v<G.vexnum;v++)
	{
		visited[v] = 0;
	}
	for (v=0;v<G.vexnum;v++)
	{
		if (!visited[v])
		{
			DFS(G,v);
		}
	}
	printf("\n");
}

图的深度优先遍历和广度优先遍历

一招鲜，吃遍天

#include<iostream>
#include<queue>
#include<stack>
#include<string>
using namespace std;

int n, m;

void bfs(int x,vector<stack<int>>&e,vector<int>&visit,vector<string>v)
{
	queue<int>q;
	q.push(x);
	visit[x] = 1;
	while (!q.empty())
	{	
		int t = q.front();
		cout << v[t] << ' ';
		q.pop();
		int size = e[t].size();
		for (int i=1;i<=size;i++)
		{
			int y = e[t].top();
			e[t].pop();
			if (!visit[y])
			{
				visit[y] = 1;
				q.push(y);
			}
		}
	}
}

void dfs(int x, vector<stack<int>>& e, vector<int>& visit, vector<string>v)
{	
	if (visit[x])
	{
		return;
	}
	visit[x] = 1;
	cout << v[x] << ' ';
	int size = e[x].size();
	for (int i=1;i<=size;i++)
	{	
		int t = e[x].top();
		e[x].pop();
		if (!visit[t])
		{
			visit[t] = 1;
			cout << v[t] << ' ';
			dfs(t,e,visit,v);
		}
	}
}


int main()
{
	int type;
	cin >> type;
	cin >> n >> m;
	vector<stack<int>>e(n+1);
	vector<string>v(n+1);
	vector<int>visit(n+1,0);
	for (int i=1;i<=n;i++)
	{
		cin >> v[i];
	}
	string a, b;
	int w;
	for (int i=1;i<=m;i++)
	{
		if (type == 0 || type == 2)
		{
			cin >> a >> b;
		}
		else cin >> a >> b >> w;
		int x = -1, y = -1;
		for (int j=1;j<=n;j++)
		{
			if (v[j]==a)
			{
				x = j;
			}
			if (v[j] == b)
			{
				y = j;
			}
			if (x!=-1&&y!=-1)
			{
				break;
			}
		}
		if (type<=1)
		{
			e[x].push(y);
		}
		else
		{
			e[x].push(y);
			e[y].push(x);
		}
	}
	for (int i=1;i<=n;i++)
	{
		if (!visit[i])
		{
			dfs(i,e,visit,v);
		}
	}
	return 0;
}

拓扑排序

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	
	int n, m;
	cin >> n >> m;
	vector<vector<int>>arrow(n+1, vector<int>(n+1,0));
	vector<int>ans;
	vector<bool>mark(n+1,false);
	for (int i=1;i<=m;i++)
	{
		int x, y;
		cin >> x >> y;
		arrow[x][y] = 1;
	}
	while (ans.size()<n)
	{
		for (int i=1;i<=n;i++)
		{
			int flag=1;

			if (mark[i])
			{
				continue;
			}

				for (int j = 1; j <= n; j++)
				{
					if (arrow[j][i])
					{
						flag = 0;
						break;
					}
				}


			if (flag)
			{
				ans.push_back(i);
				mark[i] = true;
				for (int k=1;k<=n;k++)
				{
					arrow[i][k] = 0;
				}
				break;
			}
		}
	}
	for (int i:ans)
	{
		cout << i << ' ';
	}
	cout << endl;
	return 0;
}

关键路径

基于拓扑排序的基础上进行修改得到

#include<iostream>
#include<vector>
using namespace std;

int dp[101][101];

int main()
{
	
	int n, m;
	cin >> n >> m;
	vector<int>len;
	vector<vector<int>>arrow(n+1, vector<int>(n+1,0));
	vector<int>ans;
	vector<bool>mark(n+1,false);
	for (int i=1;i<=m;i++)
	{
		int x, y, v;
		cin >> x >> y >> v;
		arrow[x][y] = 1;
		dp[x][y]=v;
	}
	while (ans.size()<n)
	{
		for (int i=1;i<=n;i++)
		{
			int flag=1;

			if (mark[i])
			{
				continue;
			}

				for (int j = 1; j <= n; j++)
				{
					if (arrow[j][i])
					{
						flag = 0;
						break;
					}
				}


			if (flag)
			{
				for (int k=1;k<=n;k++)
				{
					if (arrow[i][k])
					{
						dp[1][k] = max(dp[1][i] + dp[i][k],dp[1][k]);
					}
				}
				mark[i] = true;
				ans.push_back(i);
				for (int k = 1; k <= n; k++) {
					arrow[i][k] = 0;
				}
				break;
			}
		}
	}
	cout << dp[1][n] << endl;
	return 0;
}