C++数据结构常用操作的实现

文章目录
C++数据结构常用操作的实现
- 1. 线性表
- - 1.1 顺序表（顺序存储结构）
  - 1.2.链表（链式存储结构）
  - - 1.2.1 单链表
    - 1.2.2 单向有序循环链表
    - 1.2.3 双向链表
- 2 栈
- - 2.1 顺序栈
  - 2.2 链栈
- 3. 队列
- - 3.1 链队列
  - 3.2 循环队列
- 4.串
- - 暴力匹配法
  - KMP算法
- 5.数组
- - 稀疏矩阵与三元组
  - - 矩阵转置
    - - 1.矩阵转置简单算法
      - 2. 按照source的行序进行转置（快速转置）
- 6.**广义表**
- 7.树
- - 7.1 二叉树
  - - 二叉树的遍历：
    - 二叉树的深度
  - 7.2 线索二叉树及其遍历
  - 7.3树
  - 7.4 哈夫曼树 **(** **huffman** )
- 8. 图
- - 8.1 数组表示法（邻接矩阵表示）
  - 8.2 最小生成树
  - - 8.2.1普朗姆算法求最小生成树
- 9.排序
- - 9.1**插入排序** Insertion Sort
  - - 9.1.1直接插入排序算法
    - 9.1.2 折半插入排序算法
1. 线性表 1.1 顺序表（顺序存储结构）
#include
#include 
#include 
#define maxsize 100
#define datatype int
using namespace std;
typedef  struct
{
    int elem[maxsize];//也可以写成*data
    datatype last;
} SepList;
 
void InitList(SepList *L) {//初始化线性表
    L->last = 0;
}

int InsList(SepList* L, int i, datatype e)//i为位置，e为值
{
    if ((i < 1) || (i > L->last + 2)) //首先判断插入的位置是否合法
    {
        printf("插入的位置i值不合法");
        return 0;
    }
    if (L->last >= maxsize - 1)
    {
        printf("表已插满无法再插n");
        return 0;
    }

    for (int k = L->last; k >= i - 1; k--)
        L->elem[k + 1] = L->elem[k];//i后的元素都向后移动一位
    L->elem[i - 1] = e;
    L->last++;//下标值加一
    return 1;
}

int DelList(SepList* L, int i, datatype* e)//删除线性表的一位
{
    if (i<1 || i>L->last + 1)
    {
        cout<<"删除位置不合法！";
        return 0;
    }

    *e = L->elem[i - 1];
    for (int k = i; k < L->last; k++)
    {
        L->elem[k - 1] = L->elem[k];

    }
    L->last--;
    return 1;
}

datatype GetData(SepList L, int i) {
    return L.elem[i - 1];
}

void ListAll(SepList L) {
    for (int i = 0; i < L.last; i++) {
        cout << L.elem[i] << ' ';
    }
    cout << endl;
}
 
void update(SepList *L,int i,datatype e) {
    if (i<1 || i>L->last + 1)
    {
        cout << "修改位置不合法！";
        return;
    }

    L->elem[i] = e;
}
int main() {
    SepList L;
    InitList(&L);
    InsList(&L, 1, 10);//增添数据
    InsList(&L, 2, 30);
    cout< 
1.2.链表（链式存储结构） 
链表定义: 
采用链式存储结构的线性表称为链表 。现在我们从两个角度来讨论链表： 
从实现角度看，链表可分为动态链表和静态链表；
从链接方式的角度看，链表可分为单链表、循环链表和双链表。 
 
1.2.1 单链表 
#include 
#include 
#include 
#define datatype int
using namespace std;

typedef struct Node
{
    datatype data;
    struct Node* next;
}Node, * LinkList;

void InitList(LinkList* L) //初始化链表
{
    (*L) = new Node();//建立头节点
    (*L)->next = NULL;                 //建立空的单链表L
}

void  CreateFromHead(LinkList L)//头插法创建链表
{
    Node* s; 
    int flag = 1;
    datatype c;
    
    while (flag)
    {
        cin>>c;
        if (c != 0) 
        {
            s = new Node();
            s->data = c;
            s->next = L->next; 
            //以上为创建新的节点
            L->next = s;//不断更新L的下一个节点形成：| L | s | L->next |L->next->next|的结构
        }
        else
            flag = 0;//退出循环
    }
}


void CreateFromTail(LinkList L)//尾插法
{
    datatype a;
    LinkList p,pf;
    pf = L;
    cin >> a;
    while(a!=0){
        p = new Node();
        p->data = a;
        p->next = NULL;
        
        pf->next = p;
        pf = pf->next;

        cin >> a;
    }
}


void DeleteNode(LinkList L,int n) {//删除第N个节点
    LinkList p,pl;
    pl = L;
    p = L;
    for (int i = 0; i < n; i++) {
        pl = p;
        p = p->next;
    }
    if (pl != NULL) {
        pl->next = p->next;
        free(p);
    }
}
void InsertNode(LinkList L, int n, datatype v) //在第n个插入值为v的节点
{
    LinkList p,pl;
    p = L;
    pl = L;
    for (int i = 0; i < n; i++) {
        pl = p;
        p = p->next;
    }
    LinkList s;
    s = new Node();
    s->data = v;
    s->next = p;
    pl->next = s;
}
void selectAll(LinkList L) {
    LinkList p;
    p = L->next;
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}
int main() {
    LinkList L;//Node* L便于操作
    InitList(&L);
    CreateFromHead(L);//写入8 6 4 1
    //CreateFromTail(L);
    selectAll(L);   //1 4 6 8
    DeleteNode(L, 1);
    selectAll(L);   //4 6 8
    InsertNode(L, 1, 3);
    selectAll(L);   //3 4 6 8
    return 0;
}
 
1.2.2 单向有序循环链表 
#include 
#include 
#include 
#define datatype int
using namespace std;

typedef struct Node {
    datatype data;
    struct Node* next;
}Node, * LinkList;

void InitCLinkList(LinkList* CL)
{
    *CL = new Node();
    (*CL)->next = *CL;//形成循环，初始时，链表的下一个节点是指向头，形成循环
}
void CreateCLinkList(LinkList CL)
{
    Node* rear, * s;//rear指的是后部的节点，即头部的前一个节点
    rear = CL;
    datatype c;
    cin >> c;
    while (c != 0)
    {
        s = new Node();//开辟s的新空间
        s->data = c; //s的值为c
        rear->next = s; //将CL的next指向s
        rear = s;
        cin >> c;
    }
    rear->next = CL; //最后再将rear的next指向头，形成闭环
}

void selectAll(LinkList L) {
    Node* rear;
    rear = L->next;
    while (rear != L) {
        cout << rear->data << " ";
        rear = rear->next;
    }
    cout << endl;
}
int main() {
    LinkList L;
    InitCLinkList(&L);
    CreateCLinkList(L); //1 2 3 4 5 6 7 8 0
    selectAll(L);       //1 2 3 4 5 6 7 8

}
 
其他操作与单链表一般无二，不再赘述 
1.2.3 双向链表 
Double Linked List 
#include 
#include 
#include 
#define datatype int
using namespace std;

typedef struct tagNode
{
    datatype data;
    struct tagNode* pre;
    struct tagNode* next;
}Node, * LinkList;

void InitList(LinkList* L)
{
    *L = new Node();
    (*L)->next = (*L)->pre = *L;
}

void CreateTail(LinkList L)//尾插法
{
    LinkList p = L;
    LinkList q;
    datatype a;
    cin >> a;
    while (a != 0)
    {
        q = new Node();
        q->data = a;

        p->next = q;
        q->pre = p;

        q->next = L;
        L->pre = q;

        p = q;
        cin >> a;
    }
}
void BubbeSort(LinkList L)
{
    LinkList p1 = L->next;
    LinkList p2 = L->next->next;
    int temp;
    while (p1 != L)
    {
        while (p2 != L)
        {
            if (p1->data > p2->data)
            {
                temp = p1->data;
                p1->data = p2->data;
                p2->data = temp;
            }
            p2 = p2->next;
        }
        p1 = p1->next;
        p2 = p1->next;
    }
}

void selectAll(LinkList L) {
    LinkList p;
    p = L->next;
    while (p != L) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    LinkList L;
    InitList(&L);
    CreateTail(L); // 8 5 2 6 7 0
    selectAll(L);  // 8 5 2 6 7
    BubbeSort(L);
    selectAll(L);  // 2 5 6 7 8
}
 
2 栈 
2.1 顺序栈 
#include 
#include 
#include 
#define datatype int
#define Stack_Size 20
using namespace std;

typedef struct {
    datatype elem[Stack_Size]; //elem是存放栈中元素的一维数组
    int top;    //top用来存放栈顶元素的下标，top为-1表示空栈
}SeqStack;

void InitStack(SeqStack* S) //初始化栈
{
    S->top = -1;
}

int Push(SeqStack* S, datatype x) //插入元素x为栈S新的栈顶元素
{
    if (S->top == Stack_Size - 1)
        return 0;//满
    S->top++;
    S->elem[S->top] = x;
    return 1;
}

int Pop(SeqStack* S, datatype* x)
{
    if (S->top == -1)
    {
        return 0;//栈空
    }
    else {
        *x = S->elem[S->top];
        S->top--;
        return 1;
    }
}

int GetType(SeqStack* S, datatype* x)//操作结果：用x返回栈S的栈顶元素
{
    if (S->top == -1)
    {
        return 0;//栈空
    }
    else {
        *x = S->elem[S->top];
        return 1;
    }
}

int IsFull(SeqStack* S)

{
    return(S->top == Stack_Size - 1 ? true : false);
}
bool IsEmpty(SeqStack* S) //判空
{
    return(S->top == -1 ? true : false);
}

int main()
{
    SeqStack S;
    InitStack(&S);
    Push(&S, 2);
    int x;
    Pop(&S, &x);
    cout << x< 
2.2 链栈 
#include 
#include 
#include 
#define datatype int
#define Stack_Size 20
using namespace std;
typedef struct node
{
	datatype  data;
	struct node* next;
}LinkStackNode, * LinkStack;

void InitStack(LinkStack* LS)
{
	(*LS) = new LinkStackNode();
}

int Push(LinkStack top, datatype x)
{
	LinkStackNode* temp;
	temp = (LinkStackNode*)malloc(sizeof(LinkStackNode));
	temp->data = x;
	temp->next = top->next;
	top->next = temp;   
	return(true);
}

int Pop(LinkStack top, datatype* x)
{
	LinkStackNode* temp; 
	temp = top->next;
	if (temp == NULL)  
		return(false);
	top->next = temp->next; 
	*x = temp->data;
	free(temp);   
	return(true);
}

int main() {
	LinkStack stack;
	InitStack(&stack);
	Push(stack, 2);
	int x;
	Pop(stack, &x);
	cout << x;
}
 
3. 队列 
先进先出 
3.1 链队列 
#include 
#include 
#include 
#define datatype int
#define Stack_Size 20
using namespace std;
typedef struct Node  //节点定义
{
	datatype data;
	struct Node* next;
}LinkQueueNode;

typedef struct //链队列定义
{
	LinkQueueNode* front;
	LinkQueueNode* rear;
}LinkQueue;
 
3.2 循环队列 
#include 
#include 
#include 
#define datatype int
#define Stack_Size 20
#define MAXSIZE 50//队列最大长度
using namespace std;

typedef struct
{
	datatype element[MAXSIZE];
	int front;
	int rear;
}SeqQueue;

void InitQueue(SeqQueue* Q)
{
	Q->front = Q->rear = 0;
}

int EnterQueue(SeqQueue* Q, datatype x)
{
	if ((Q->rear + 1) % MAXSIZE == Q->front)
		return 0;
	Q->element[Q->rear] = x;
	Q->rear = (Q->rear + 1) % MAXSIZE;
	return 1;
}

int DeleteQueue(SeqQueue* Q)
{
	datatype x;
	if (Q->front == Q->rear)
	{
		return 0;
	}
	x = Q->element[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;
	return x;
}

int main() {
	//操作简单，略
}

 
4.串 
串是零个或多个字符组成的有限序列。
一般记作S=“ a0a1a2…an-1 “ (n>=0)
ai(0≦i≦n-1)可以是字母、数字或其它字符； 
#include 
#include 
#include 
#define datatype int
#define Stack_Size 20
#define MAXLEN 50//队列最大长度
using namespace std;

typedef struct {
    char ch[MAXLEN];
    int len;
}SString;

void CreateString(SString *str) {
    cin >> str->ch;
    str->len = strlen(str->ch);
}

int StrDelete(SString* s, int pos, int len)//顺序串删除函数

{
    int i;
    if(pos<0 || pos>(s->len-len)) 
        return(0);
    for(i=pos+len;ilen;i++)
        s->ch[i-len]=s->ch[i];
    s->len=s->len-len;
    return(1);
}
int StrCompare(SString s, SString t)//串比较函数
//若s==t,返回0;s>t,返回正数;s
    int i;
    for (i = 0; i < s.len && i < t.len; i++)
        if (s.ch[i] != t.ch[i])
            return(s.ch[i] - t.ch[i]);
    return(s.len - t.len);
}
int StrInsert(SString* s, int pos, SString t)

{
    int i;
    if (pos<0 || pos>s->len) {
        cout << "插入位置不合法" << endl;
        return 0;
    }
    if (s->len + t.len <= MAXLEN)
    {
        for (i = s->len + t.len - 1; i >= t.len + pos; i--)
            s->ch[i] = s->ch[i - t.len];
        for (i = 0; i < t.len; i++)s->ch[i + pos] = t.ch[i];
        s->len = s->len + t.len;
    }
    else if (pos + t.len <= MAXLEN)
    {
        for (i = MAXLEN - 1; i > t.len + pos - 1; i--)s->ch[i] = s->ch[i - t.len];
        for (i = 0; i < t.len; i++)s->ch[i + pos] = t.ch[i];
        s->len = MAXLEN;
    }
    else {  //插入后串长>MAXLEN,并且串t的部分字符也要舍弃
        for (i = 0; i < MAXLEN - pos; i++)s->ch[i + pos] = t.ch[i]; s->len = MAXLEN;
        return(1);
    }
}
void Print(SString a) {
    for (int i = 0; i < a.len; i++) {
        cout << a.ch[i];
    }
    cout << endl;
}
int main() {
    SString a;
    SString b;
    CreateString(&a);//aaaaa
    CreateString(&b);//bb
    StrInsert(&a, 2, b);
    Print(a);//aabbaaa
    StrDelete(&a,1,3);
    Print(a);//aaaaa

}

 
暴力匹配法 
最坏时间复杂度为O ( n m ) O(nm)O(nm) 
#include 
#include 
#include 
using namespace std;

typedef struct {
    char ch[MAXLEN];
    int len;
}SString;

void CreateString(SString *str) {
    cin >> str->ch;
    str->len = strlen(str->ch);
}
int Index(SString S, SString T) {
	int i = 0, j = 0;
	while (i <= S.len && j <= T.len) {
		if (S.ch[i] == T.ch[j]) {
			++i; 
			++j;	//继续比较后继字符
		}
		else {
			//指针后退重新开始匹配
			i = i - j;
			j = 0;
		}
		if (j == T.len)
		{
			break;
		}

	}
	if (j >= T.len) {
		return i - T.len;
	}
	else {
		cout << "不匹配";
		return 0;
	}
}

int main() {
    SString a;
    SString b;
	CreateString(&a);//abcdefg
	CreateString(&b);//defg
	cout << Index(a, b);//3

}

 
KMP算法 
KMP算法的特点就是：仅仅后移模式串，比较指针不回溯。 
#include 
#include 
#include 
#define MAXLEN 50//队列最大长度
using namespace std;

typedef struct {
    char ch[MAXLEN];
    int len;
}SString;

void CreateString(SString *str) {
    cin >> str->ch;
    str->len = strlen(str->ch);
}

void Print(SString a) {
    for (int i = 0; i < a.len; i++) {
        cout << a.ch[i];
    }
    cout << endl;
}
void GetNext(SString t, int next[])		//由模式串t求出next值
{
	int j, k;
	j = 0; k = -1;
	next[0] = -1;//第一个字符前无字符串，给值-1
	while (j < t.len - 1)
		//因为next数组中j最大为t.len-1,而每一步next数组赋值都是在j++之后
		//所以最后一次经过while循环时j为t.len-2
	{
		if (k == -1 || t.ch[j] == t.ch[k]) 	//k为-1或比较的字符相等时
		{
			j++; k++;
			next[j] = k;
			//对应字符匹配情况下，s与t指向同步后移
			//通过字符串"aaaaab"求next数组过程想一下这一步的意义
			//printf("(1) j=%d,k=%d,next[%d]=%dn",j,k,j,k);
		}
		else
			k = next[k];
			//我们现在知道next[k]的值代表的是下标为k的字符前面的字符串最长相等前后缀的长度
			//也表示该处字符不匹配时应该回溯到的字符的下标
			//这个值给k后又进行while循环判断，此时t.ch[k]即指最长相等前缀后一个字符**
			//为什么要回退此处进行比较，我们往下接着看。其实原理和上面介绍的KMP原理差不多
			//printf("(2) k=%dn",k);
		
	}
}
int KMPIndex(SString s, SString t)  //KMP算法
{

	int next[MAXLEN], i = 0, j = 0;
	GetNext(t, next);
	while (i < s.len && j < t.len)
	{
		if (j == -1 || s.ch[i] == t.ch[j])
		{
			i++; j++;  			//i,j各增1
		}
		else j = next[j]; 		//i不变,j后退，现在知道为什么这样让子串回退了吧
	}
	if (j >= t.len)
		return(i - t.len);  	//返回匹配模式串的首字符下标
	else
		return(-1);        		//返回不匹配标志
}



int main() {
    SString a;
    SString b;
	CreateString(&a);//abcdefg
	CreateString(&b);//defg
	cout << KMPIndex(a, b) << endl;
}

 
5.数组 
数组和广义表，其共同特点是：
 （1）从逻辑结构上看它们，可看成是线性结构的一种扩展；
 （2）数据元素本身也是一个数据结构； 
稀疏矩阵与三元组 
 
#include 
#include 
#include 
#define MAXSIZE 1000
#define datatype int
using namespace std;
typedef struct
{
    int row, col;  //行列下标
    datatype e;  //元素值
}Triple;

typedef struct
{
    Triple data[MAXSIZE + 1];  //三元数组
    int m, n, len;             //矩阵行数，列数和非零元素个数
}TSMatrix;

void CreateTS(TSMatrix* ts,int arr[3][3]) {
    ts->len = 0;
    ts->m = 3;
    ts->n = 3;
    for(int i=0;i<3;i++)
        for (int j = 0; j < 3; j++)
        {
            if (arr[i][j] != 0) {
                Triple p;
                p.row = i;
                p.col = j;
                p.e = arr[i][j];
                ts->data[ts->len++] = p;
            }
        }
}
void Print(TSMatrix ts) {
    int k = 0;
    for (int i = 0; i < ts.m; i++)
    {
        for (int j = 0; j < ts.n; j++)
        {
            if (ts.data[k].row == i && ts.data[k].col == j) {
                cout<
               cout<<0<<" ";
            }

        }
        printf("n");
    }
}

int main() {
    int arr[3][3] = { 1,2,0,
                      0,3,1,
                      0,0,7 };
    TSMatrix tr;
    CreateTS(&tr, arr);
    Print(tr);
}

 
矩阵转置 
1.矩阵转置简单算法 
 算法的时间耗费主要是在双重循环中，其时间复杂度为O（cols×num）, 最坏(不稀疏了)情况下，当num与cols×rows同数量级时，时间复杂度为O（rows×cols2）。采用正常方式实现矩阵转置的算法时间复杂度为O（cols×rows）。 
#include 
#include 
#include 
#define MAXSIZE 1000
#define datatype int
using namespace std;
typedef struct
{
    int row, col;  //行列下标
    datatype e;  //元素值
}Triple;

typedef struct
{
    Triple data[MAXSIZE + 1];  //三元数组
    int m, n, len;             //矩阵行数，列数和非零元素个数
}TSMatrix;

void CreateTS(TSMatrix* ts,int arr[3][3]) {
    ts->len = 0;
    ts->m = 3;
    ts->n = 3;
    for(int i=0;i<3;i++)
        for (int j = 0; j < 3; j++)
        {
            if (arr[i][j] != 0) {
                Triple p;
                p.row = i;
                p.col = j;
                p.e = arr[i][j];
                ts->data[ts->len++] = p;
            }
        }
}
void Print(TSMatrix ts) {
    int k = 0;
    for (int i = 0; i < ts.m; i++)
    {
        for (int j = 0; j < ts.n; j++)
        {
            if (ts.data[k].row == i && ts.data[k].col == j) {
                cout<
               cout<<0<<" ";
            }

        }
        printf("n");
    }
}

void TransposeTSMatrix(TSMatrix A, TSMatrix* B)
{
    int i,j,k;
    B->m=A.n;
    B->n=A.m;
    B->len=A.len;
    if(B->len>0)
    {
        j=0;
        for(k=0;k<=A.n;k++)
             for(i=0;i<=A.len;i++)
                   if(A.data[i].col==k)
                   {
                       B->data[j].row=A.data[i].col;
                       B->data[j].col=A.data[i].row;
                       B->data[j].e=A.data[i].e;
                       j++;
                   }
    } 
}
int main() {
    int arr[3][3] = { 1,2,0,
                      0,3,1,
                      0,0,7 };
    TSMatrix tr;
    CreateTS(&tr, arr);
    Print(tr);
    TSMatrix tr2;
    cout << endl;
    TransposeTSMatrix(tr, &tr2);
    Print(tr2);
}

 
 
2. 按照source的行序进行转置（快速转置） 
 依次按source三元组表的行序次序进行转置，转置后直接放到dest三元组表的正确位置上。 
为了能将待转置source三元组表中元素一次定位到dest三元组表的正确位置上，需要预先计算以下数据： 
(1) 待转置矩阵source每一列中第一个非零元素在dest三元组表中的正确位置（即转置后矩阵dest每一行中第一个非零元素在dest三元组中的正确位置) ； 
(2) 待转置矩阵source每一列中非零元素的个数（即转置后矩阵dest每一行中非零元素的个数） 
6.广义表 
广义表（General List）----人工智能等领域的LISP语言使用的一种数据结构，是对线性表的一个推广 。 
广义表的概念:
 n(>=0)个表元素组成的有限序列
 记作 GL = (a1, a2, a3, …, an) 
#include 
#include 
#include 
#define MAXSIZE 1000
#define AtomType int
using namespace std;

typedef enum {ATOM,LiST} ElemTag;
typedef struct GLNode
{
	ElemTag tag;
	union
	{
		AtomType atom;
		struct {
			struct GLNode* hp, * tp;
		}htp;
	}atom_htp;
}GLNode,*GList;


 
7.树 
树是常用的数据组织形式 
有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织 
7.1 二叉树 
二叉树的分类： 
一、满二叉树
 除了最后一层的节点没有任何子节点外，每层上的所有节点都有两个节点的二叉树 
 
二、完全二叉树
 一颗二叉树的深度为h，除了第h层外，其他各层的节点都有两个子节点，且第h层的所有节点都集中在最左边
 （满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树） 
 
三、二叉搜索树
 左子树的所有节点的值均小于它的根节点的值
 右子树的所有节点的值均大于它的根节点的值
 它的左右子树也分别为二叉搜索树 
四、平衡二叉树 
两个条件： 
1. 是「二叉排序树」
2. 任何一个节点的左子树或者右子树都是「平衡二叉树」（左右高度差小于等于 1） 
 
#include 
#include 
#define DataType int
typedef struct Node
{
    DataType data;
    struct Node* LChild;
    struct Node* RChild;

}BiTNode,*BiTree;
 
二叉树的遍历： 
#include
#include
typedef struct BiTNode
{
    char data;
    struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
void PreOrderTraverse(BiTree T)//二叉树的先序遍历
{
    if (T == NULL) {
        printf("# ");
        return;
    }
    printf("%c ", T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T)//二叉树的中序遍历
{
    if (T == NULL) {
        printf("# ");
        return;
    }

    InOrderTraverse(T->lchild);
    printf("%c ", T->data);
    InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T)//后序遍历
{
    if (T == NULL) {
        printf("# ");
        return;
    }
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ", T->data);
}
void CreateBiTree(BiTree& T) // 二叉树的创建
{
    char ch;
    scanf("%c", &ch);
    if (ch == '#')
        T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
int main()
{
    BiTree T;
    CreateBiTree(T);	//ABDG##H###CE#I##F##
    printf("先序遍历:");
    PreOrderTraverse(T);//先序遍历:A B D G # # H # # # C E # I # # F # #
    printf("n");
    printf("中序遍历:");
    InOrderTraverse(T);//中序遍历:# G # D # H # B # A # E # I # C # F #
    printf("n");
    printf("后序遍历:");
    PostOrderTraverse(T);//后序遍历:# # G # # H D # B # # # I E # # F C A
    return 0;
}
 
对知识点的补充： （1）建立二叉树时，这里是以前序遍历的方式，输入的是扩展二叉树，也就是要告诉计算机什么是叶结点，否则将一直递归，当输入“#”时，指针指向NULL，说明是叶结点。 
如图为扩展二叉树：（前序遍历为：ABDG##H###CE#I##F##） 
 
二叉树的深度 
#include 
#include
#include
using namespace std;
typedef struct BiTNode
{
    char data;
    struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;

void CreateBiTree(BiTree& T) // 二叉树的创建
{
    char ch;
    scanf("%c", &ch);
    if (ch == '#')
        T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

int HeightCount(BiTree r)
// 操作结果：返回以r为根的二叉树的高
{
    if (r == NULL) return 0;	// 空二叉数高为0
    else
    {
        int lHeight, rHeight;
        lHeight = HeightCount(r->lchild);
        rHeight = HeightCount(r->rchild);
        return 1 + (lHeight > rHeight ? lHeight : rHeight);
    }
}

int main()
{
    BiTree T;
    CreateBiTree(&T);//ABDG##H###CE#I##F##
    cout<<"深度:"< 
7.2 线索二叉树及其遍历 
把某结点原来空的左（右）指针域用于存放指向其前趋（后继）结点的指针，也叫左（右）线索。
 对一个二叉树中的所有结点的空指针域按照某种遍历次序加线索的过程叫作线索化，被线索化了的二叉树称作线索二叉树。 
 
#include 
#include
#include
using namespace std;
typedef enum PointTag//提高可读性
{
    Link, Thread//Link==0:指针,线索
};

typedef struct BiThrNode
{
    char data;
    struct BiThrNode* lchild, * rchild;
    PointTag LTag, RTag;
}BiThrNode, * BiThrTree;

BiThrTree pre;

void InThread(BiThrTree root)
{
    if (root != NULL)//根不为空时
    {
        InThread(root->lchild);

        if (root->lchild != NULL)
        {
            root->LTag = Thread;
            root->lchild = pre;
        }
        else {
            root->LTag = Link;
        }

        if (root->rchild != NULL)
        {
            root->RTag = Thread;
        }

        if (!pre->rchild) {
            pre->RTag = Thread;
            pre->rchild = root;
        }
        else {
            root->RTag = Link;
        }
        pre = root;
        InThread(root->rchild);

    }
}

void CreateBiThrTree(BiThrTree& T)
{
    char ch;
    scanf("%c", &ch);
    if (ch == '#')
        T = NULL;
    else
    {
        T = (BiThrTree)malloc(sizeof(BiThrNode));
        T->data = ch;
        CreateBiThrTree(T->lchild);
        CreateBiThrTree(T->rchild);
    }
}


int main()
{
    BiThrTree T;
    CreateBiThrTree(T);//ABDG##H###CE#I##F##

    return 0;
}
 
7.3树 
(1) 双亲表示法
 采用一组连续空间存储树的结点，通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。 
 
struct ParentTreeNode{
  ElemType data;
  int parent;
};
 
（2）孩子双亲表示法： 
把每个结点的孩子结点排列起来，看成一个线性表 
struct ChildParentTreeNode{
  ElemType data;
  LinkList childLkList;
  int parent;
};
 
 
 
（3）孩子兄弟表示法 
struct ChildSiblingTreeNode
{  
     ElemType  data;
     ChildSiblingTreeNode *firstChild,
     ChildSiblingTreeNode * rightSibling;
};
 
7.4 哈夫曼树 ( huffman ) 
1、哈夫曼树的概念 
路径：从一个结点到另一个结点之间的若干个分支；
路径长度：路径上的分支数目称为路径长度；
结点的路径长度：从根到该结点的路径长度；
树的路径长度：树中所有叶子结点的路径长度之和；一般记为PL。 
在结点数相同的条件下，完全二叉树是路径最短的二叉树。 
 
结点的权：根据应用的需要可以给树的结点赋权值；
结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；
树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 
 
哈夫曼树：假设有n个权值(w1, w2, … , wn )，构造有n个叶子结点的二叉树，每个叶子结点带权为 wi，则其中带权路径长度WPL最小的二叉树称为哈夫曼树或者最优二叉树。 
#include
#include
#include
#define maxsize 300
#define DataType int
using namespace std;


typedef struct HTNode //单个结点的信息
{
	DataType weight; //权值
	int parent; //父节点
	int lc, rc; //左右孩子
}*HuffmanTree;


//在下标为1到i-1的范围找到权值最小的两个值的下标，其中s1的权值小于s2的权值
void Select(HuffmanTree& HT, int n, int& s1, int& s2)
{
	int min;
	//找第一个最小值
	for (int i = 1; i <= n; i++)
	{
		if (HT[i].parent == 0)
		{
			min = i;
			break;
		}
	}
	for (int i = min + 1; i <= n; i++)
	{
		if (HT[i].parent == 0 && HT[i].weight < HT[min].weight)
			min = i;
	}
	s1 = min; //第一个最小值给s1
	//找第二个最小值
	for (int i = 1; i <= n; i++)
	{
		if (HT[i].parent == 0 && i != s1)
		{
			min = i;
			break;
		}
	}
	for (int i = min + 1; i <= n; i++)
	{
		if (HT[i].parent == 0 && HT[i].weight < HT[min].weight && i != s1)
			min = i;
	}
	s2 = min; //第二个最小值给s2
}

//构建哈夫曼树
void CreateHuff(HuffmanTree& HT, DataType* w, int n)
{
	int m = 2 * n - 1; //哈夫曼树总结点数
	HT = (HuffmanTree)calloc(m + 1, sizeof(HTNode)); //开m+1个HTNode，因为下标为0的HTNode不存储数据
	for (int i = 1; i <= n; i++)
	{
		HT[i].weight = w[i - 1]; //赋权值给n个叶子结点
	}
	for (int i = n + 1; i <= m; i++) //构建哈夫曼树
	{
		//选择权值最小的s1和s2，生成它们的父结点
		int s1, s2;
		Select(HT, i - 1, s1, s2); //在下标为1到i-1的范围找到权值最小的两个值的下标，其中s1的权值小于s2的权值
		HT[i].weight = HT[s1].weight + HT[s2].weight; //i的权重是s1和s2的权重之和
		HT[s1].parent = i; //s1的父亲是i
		HT[s2].parent = i; //s2的父亲是i
		HT[i].lc = s1; //左孩子是s1
		HT[i].rc = s2; //右孩子是s2
	}
	//打印哈夫曼树中各结点之间的关系
	printf("哈夫曼树为:>n");
	printf("下标   权值     父结点   左孩子   右孩子n");
	printf("0                                  n");
	for (int i = 1; i <= m; i++)
	{
		printf("%-4d   %-6.2lf   %-6d   %-6d   %-6dn", i, HT[i].weight, HT[i].parent, HT[i].lc, HT[i].rc);
	}
	printf("n");
}

typedef char** HuffmanCode;

//生成哈夫曼编码
void HuffCoding(HuffmanTree& HT, HuffmanCode& HC, int n)
{
	HC = (HuffmanCode)malloc(sizeof(char*) * (n + 1)); //开n+1个空间，因为下标为0的空间不用
	char* code = (char*)malloc(sizeof(char) * n); //辅助空间，编码最长为n(最长时，前n-1个用于存储数据，最后1个用于存放'')
	code[n - 1] = ''; //辅助空间最后一个位置为''
	for (int i = 1; i <= n; i++)
	{
		int start = n - 1; //每次生成数据的哈夫曼编码之前，先将start指针指向''
		int c = i; //正在进行的第i个数据的编码
		int p = HT[c].parent; //找到该数据的父结点
		while (p) //直到父结点为0，即父结点为根结点时，停止
		{
			if (HT[p].lc == c) //如果该结点是其父结点的左孩子，则编码为0，否则为1
				code[--start] = '0';
			else
				code[--start] = '1';
			c = p; //继续往上进行编码
			p = HT[c].parent; //c的父结点
		}
		HC[i] = (char*)malloc(sizeof(char) * (n - start)); //开辟用于存储编码的内存空间
		strcpy(HC[i], &code[start]); //将编码拷贝到字符指针数组中的相应位置
	}
	free(code); //释放辅助空间
}

int main()
{
	int n = 0;
	printf("请输入数据个数:>");
	scanf("%d", &n);
	DataType* w = (DataType*)malloc(sizeof(DataType) * n);
	if (w == NULL)
	{
		printf("malloc failn");
		exit(-1);
	}
	printf("请输入数据:>");
	for (int i = 0; i < n; i++)
	{
		scanf("%2f", &w[i]);
	}
	HuffmanTree HT;
	CreateHuff(HT, w, n); //构建哈夫曼树

	HuffmanCode HC;
	HuffCoding(HT, HC, n); //构建哈夫曼编码

	for (int i = 1; i <= n; i++) //打印哈夫曼编码
	{
		printf("数据%.2lf的编码为:%sn", HT[i].weight, HC[i]);
	}
	free(w);
	return 0;
}

 
8. 图 
定义:图是由顶点集合(vertex)及边的集合组成的一种数据结构：
 Graph＝( V, R )
 其中: V = { x | x子集于某个数据对象}
 是顶点的有穷非空集合；
 R = {(u, v) | u, v  V }
 是顶点之间关系的有穷集合，也叫做边(edge)集合。 
如： 
G1=
V1={v1,v2,v3,v4 ,v5 }
R1={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}
 
8.1 数组表示法（邻接矩阵表示） 
图的建立
广度优先算法
深度优先 
#include
#include
#include
#include
#define MaxVertexNum 20	//最大顶点数
using namespace std;
typedef struct node		//表边结点
{
	int adjvex;			//顶点编号
	struct node* next;	//邻接点域a->b->c->d
	//若要表示边上权信息，则应增加一个数据域info
}EdgeNode;

typedef struct vnode	//顶点表结点
{
	int vertex;			//顶点域（相当于一个序号标识符）
	EdgeNode* firstedge;//边表头指针
}VertexNode;

typedef VertexNode AdjList[MaxVertexNum];//顶点数组

typedef struct
{
	AdjList adjlist;
	int vexnum;	//点数
	int arcnum;	//边数
}ALGraph; //图，邻接表方式存储的

void CreateALGraph(ALGraph*& G)
{
	int i, j, k; EdgeNode* s;
	G = (ALGraph*)malloc(sizeof(ALGraph));		//初始化图
	printf("请输入顶点数和边数（输入格式：顶点数，边数）：n");
	scanf("%d,%d", &(G->vexnum), &(G->arcnum));
	printf("请输入顶点号(用逗号间隔)：n");
	for (i = 0; i < G->vexnum; i++)
	{
		scanf("%d,", &(G->adjlist[i].vertex));
		G->adjlist[i].firstedge = NULL;
	}
	printf("请输入边的信息（输入格式为：i,j）:n");

	for (k = 0; k < G->arcnum; k++)
	{
		scanf("n%d,%d", &i, &j);
		s = (EdgeNode*)malloc(sizeof(EdgeNode));
		s->adjvex = j;
		s->next = G->adjlist[i].firstedge;
		G->adjlist[i].firstedge = s;//插入

		s = (EdgeNode*)malloc(sizeof(EdgeNode));
		s->adjvex = i;
		s->next = G->adjlist[j].firstedge;
		G->adjlist[j].firstedge = s;//无向联通，两个都要加上，单向联通则不需要
	}
}
void PrintALGraph(ALGraph* G)//输出邻接表存储
{
	int i; EdgeNode* p;
	for (i = 0; i < G->vexnum; i++)
	{
		printf("v%d", (G->adjlist[i].vertex));
		p = G->adjlist[i].firstedge;
		while (p != NULL) { printf("→%d", p->adjvex); p = p->next; }
		printf("∧n");
	}
}

void DFSAL(ALGraph* G, int i, int visited[MaxVertexNum])
{

	EdgeNode* p;
	printf("V%d ", G->adjlist[i].vertex);

	visited[i] = 1;
	p = G->adjlist[i].firstedge;

	while (p)
	{
		if (!visited[p->adjvex])
			DFSAL(G, p->adjvex, visited);
		p = p->next;
	}
}

void DFSTraverse(ALGraph* G)
{
	int i, visited[MaxVertexNum];
	for (i = 0; i < G->vexnum; i++) visited[i] = 0;
	for (i = 0; G->vexnum; i++)
		if (!visited[i]) DFSAL(G, i, visited);
}

void BFSAL(ALGraph* G, int i, int visited[MaxVertexNum])
{
	EdgeNode* p; int w;
	int queue[MaxVertexNum], front = 0, rear = 0;
	printf("V%d ", G->adjlist[i].vertex);
	visited[i] = 1;
	rear = (rear + 1) % MaxVertexNum;
	queue[rear] = i;
	while (front != rear)
	{
		front = (front + 1) % MaxVertexNum;
		w = queue[front];
		p = G->adjlist[w].firstedge;
		while (p != NULL)
		{
			if (!visited[p->adjvex])
			{
				printf("V%d ", p->adjvex);
				visited[p->adjvex] = 1;
				rear = (rear + 1) % MaxVertexNum;
				queue[rear] = p->adjvex;
			}
			p = p->next;
		}
	}
}
void BFSTraverse(ALGraph* G)
{
	int i, visited[MaxVertexNum];
	for (i = 0; i < G->vexnum; i++) visited[i] = 0;
	for (i = 0; i < G->vexnum; i++)
		if (!visited[i])
			BFSAL(G, i, visited);

}

int main()
{
	int t; ALGraph* G;
	CreateALGraph(G);
	PrintALGraph(G);
	cout << endl;
	do
	{
		printf("请选择遍历方式：n");
		printf("1 深度优先遍历n");
		printf("2 广度优先遍历n");
		printf("3 结束程序运行   n");
		cin>>t;
		switch (t)
		{
		case 1:
			printf("深度优先遍历序列：n");
			DFSTraverse(G);
			printf("n");
			break;
		case 2:
			printf("广度优先遍历序列：n");
			BFSTraverse(G);
			printf("n");
			break;
		case 3:
			exit(0);
			break;
		default:
			printf("输入错误，只能选择1或2！");
		}
	} while (t <= 3);
}
 
8,9
0,1,2,3,4,5,6,7
0,1
0,2
1,3
1,4
2,5
2,6
3,7
4,7
5,6
请选择遍历方式：
1 深度优先遍历
2 广度优先遍历
3 结束程序运行
2
广度优先遍历序列：
V0 V2V1V6V5V4V3V7
 
 
8.2 最小生成树 
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图
一个有n个顶点的连通图的生成树有n-1条边
生成树中任意两个顶点间的路径是唯一的 
最小代价生成树 
普朗姆算法
克鲁斯卡尔算法 
8.2.1普朗姆算法求最小生成树 
9.排序 
9.1插入排序 Insertion Sort 
排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。 
9.1.1直接插入排序算法 
#include
#include
#include
using namespace std;
#define ElemType int 
void StraightInsertSort(ElemType elem[], int n)
// 操作结果:对数组elem作直接插入排序
{
	for (int i = 1; i < n; i++)
	{	// 第i趟直接插入排序
		ElemType e = elem[i];	// 暂存elem[i]
		int j;			// 临时变量
		for (j = i - 1;e < elem[j]; j--)
		{	// 将比e大的计录都后移
			elem[j + 1] = elem[j];	// 后移
		}
		elem[j + 1] = e;	// j+1为插入位置
	}
}

int main() {
	int arr[10] = { 1, 4, 2, 5, 9, 3, 8, 6, 7, 0 };
	StraightInsertSort(arr, 10);
	for (int i = 0; i < 10; i++) {
		cout << arr[i]<<" ";
	}
}
 
9.1.2 折半插入排序算法 
#include
#include
#include
using namespace std;
#define ElemType int 
int binarySearch(ElemType numbers[], int n, int value) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (value <= numbers[middle]) {
            right = middle - 1;
        }
        else if (value > numbers[middle]) {
            left = middle + 1;
        }
    }
    // 当 left >= n 时，则说明预插入数与其之前的有序序列
    // 已经形成有序序列了，因此不需要做插入操作
    return (left < n) ? left : -1;
}
void binaryInsertionSort(ElemType elem[], int n)
{
    for (int i = 1; i 
        // 获取插入位置
        int insert_index = binarySearch(elem, i, elem[i]);
        // 当 insert_index = -1 时，不必做插入操作
        if (insert_index != -1) {
            // 一下是插入排序
            int temp = elem[i];
            int j = i - 1;
            while (j >= insert_index) {
                elem[j + 1] = elem[j];
                j--;
            }
            elem[j + 1] = temp;
        }
    }
}

int main() {
	int arr[10] = { 1, 4, 2, 5, 9, 3, 8, 6, 7, 0 };
    binaryInsertionSort(arr, 10);
	for (int i = 0; i < 10; i++) {
		cout << arr[i]<<" ";
	}
    return 0;
}
C++数据结构常用操作的实现

C/C++/C#相关栏目本月热门文章
