#00 数据结构总结

C/C++实现线性表、栈、队列、二叉树、图、查找、串、排序

/*===============================顺序表=======================================*/
#define MaxSize 50
typedef struct {
        ElemType data[MaxSize];
        int length;
} SqList;

#define InitSize 100
typedef struct {
        ElemType* data;
        int MaxSize, length;
} SeqList;
//C
L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
//C++
L.data = new ElemType[InitSize];

bool ListInsert(SqList& L, int i, ElemType e)
{
        if (i < 1 || i > L.length + 1) //实际位置
                return false;
        if (L.length >= MaxSize)
                return false;
        for (int j = L.length; j >= i; j--)
                L.data[j] = L.data[j - 1]; //数组索引
        L.data[i - 1] = e;                 //数组索引
        L.length++;
        return true;
}

bool ListDelete(SqList& L, int i, ElemType& e)
{
        if (i < 1 || i > L.length + 1)
                return false;
        e = L.data[i - 1]; //数组索引
        for (int j = i; j < L.length; j++)
                L.data[j - 1] = L.data[j];
        L.length--;
        return true;
}

int LocateElem(SqList L, ElemType e)
{
        int i;
        for (i = 0; i < L.length; i++)
                if (L.data[i] == e)
                        return i + 1; //实际位置
        return 0;
}

/*=================================链表=======================================*/
typedef struct LNode {
        ElemType data;
        struct LNode* next;
} LNode, *LinkList;

LinkList List_HeadInsert(LinkList& L) //头插法
{
        LNode* s;
        int x;
        L = (LinkList)malloc(sizeof(LNode)); //LinkList本身就是指针
        L->next = NULL;
        scanf("%d", &x);
        while (x != 999) {
                s = (LNode*)malloc(sizeof(LNode));
                s->data = x;
                s->next = L->next;
                L->next = s;
                scanf("%d", &x);
        }
        return L;
}

LinkList List_TailInsert(LinkList& L) //尾插法
{
        int x;
        L = (LinkList)malloc(sizeof(LNode));
        LNode *s, *r = L; //r是尾指针
        scanf("%d", &x);
        while (x != 9999) {
                s = (LNode*)malloc(sizeof(LNode));
                s->data = x;
                r->next = s;
                r = s;
                scanf("%d", &x);
        }
        r->next = NULL;
        return L;
}

LNode* GetElem(LinkList L, int i) //由于存在头指针L，i既是索引也是实际位置
{
        int j = 1;
        LNode* p = L->next;
        if (i == 0)
                return L;
        if (i < 1)
                return NULL;
        while (p && j < i) {
                p = p->next;
                j++;
        }
        return p:
}

LNode* LocateElem(LinkList L, ElemType e)
{
        LNode* p = L->next;
        while (p && p->data != e)
                p = p->next;
        return p;
}

typedef struct DNode { //双向链表
        ElemType data;
        struct DNode *prior, *next;
} DNode, *DLinkList;

#define MaxSize 50
typedef struct { //数组链表
        ElemType data;
        int next;
} SLinkList[MaxSize];

/*==================================栈========================================*/
#define MaxSize = 50
typedef struct { //顺序栈
        ElemType data[MaxSize];
        int top;
} SqStack;

void InitStack(SqStack& S)
{
        S.top = -1;
}

bool StackEmpty(SqStack S)
{
        if (S.top == -1) //顺序栈的判空条件
                return true;
        else
                return false;
}

bool Push(SqStack& S, ElemType x)
{
        if (S.top == MaxSize - 1) //索引
                return false;
        S.data[++S.top] = x; //先加一，再压数
        return true;
}

bool Pop(SqStack& S, ElemType& x)
{
        if (S.top == -1) //栈空
                return false;
        x = S.data[S.top--]; //先弹数，再减一
        return true;
}

bool GetTop(SqStack S, ElemType& x)
{
        if (S.top == -1)
                return false;
        x = S.data[S.top];
        return true;
}

typedef struct Linknode { //链栈
        ElemType data;
        struct Linknode* next;
} * LiStack;

/*===================================循环队列=================================*/
//在有数据的情况下，队头指针指向第一个数据结点
//队尾指针指向最后一个数据结点的下一个结点
//循环队列存在队空和队满无法判断的情况，解决方案如下三种：
//1. 牺牲一个单元来区分队空和队满
//队满：(Q.rear+1)%MaxSize == Q.front
//队空：Q.front == Q.rear
//队中元素个数：(Q.rear - Q.front + MaxSize) % MaxSize
//2. 结构体中增设表示元素个数的数据成员size
//队满：Q.size == MaxSize
//队空：Q.size == 0
//3. 结构体中增设用于区分队满队空数据成员tag
//队空：tag == 1 且因删除导致 Q.front == Q.rear
//队满：tag == 0 且因插入导致 Q.front == Q.rear
#define MaxSize 50
typedef struct {
        ElemType data[MaxSize];
        int front, rear;
} SqQueue;

void InitQueue(SqQueue& Q)
{
        Q.rear = Q.front = 0;
}

bool isEmty(SqQueue Q)
{
        if (Q.rear == Q.front) //循环队列的判空条件
                return true;
        else
                return false;
}

bool EnQueue(SqQueue& Q, ElemType x) //使用模队长的算法体现循环
{
        if ((Q.rear + 1) % MaxSize == Q.front) //循环队满
                return false;
        Q.data[Q.rear] = x;
        Q.rear = (Q.rear + 1) % MaxSize;
        return true;
}

bool DeQueue(SqQueue& Q, ElemType& x)
{
        if (Q.rear == Q.front)
                return false;
        x = Q.data[Q.front];
        Q.front = (Q.front + 1) % MaxSize;
        return true;
}

//链队与循环队列结构不同，具体表现在队头、队尾指针的位置
//链队队头指针的next域指向第一个数据结点
//链队队尾指针之乡最后一个数据节点，next域为NULL
typedef struct LinkNode { //链队
        ElemType data;
        struct LinkNode* next;
} LinkNode;
typedef struct {
        LinkNode *front, *rear;
} LinkQueue;

void InitQueue(LinkQueue& Q)
{
        Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
        Q.front->next = NULL;
}

bool IsEmpty(LinkQueue Q)
{
        if (Q.front == Q.rear) //链队判空条件
                return true;
        else
                return false;
}

void EnQueue(LinkQueue& Q, ElemType x)
{
        LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
        s->data = x;
        s->next = NULL;
        Q.rear->next = s;
        Q.rear = s;
}

void DeQueue(LinkQueue& Q, ElemType& x)
{
        if (Q.front == Q.rear)
                return false;
        LinkNode* p = Q.front->next;
        x = p->data;
        Q.front->next = p->next;
        if (Q.rear == p) //判空
                Q.rear = Q.front;
        free(p); //malloc分配的堆内存空间必须手动用free释放
        return true;
}

/*===========================递归实现斐波算法=================================*/
int Fib(int n)
{
        if (n == 0)
                return 0;
        else if (n == 1)
                return 1;
        else
                return Fib(n - 1) + Fib(n - 2);
}

/*===============================二叉树=======================================*/
typedef struct BiTNode {
        ElemType data;
        struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void PreOrder(BiTree T) //前序遍历, OLR
{
        if (T != NULL) {
                visit(T);
                PreOrder(T->lchild);
                PreOrder(T->rchild);
        }
}

void InOrder(BiTree T) //中序遍历，LOR
{
        if (T != NULL) {
                InOrder(T->lchild);
                visit(T);
                InOrder(T->rchild);
        }
}

void PostOrder(BiTree T) //后序遍历，LRO
{
        if (T != NULL) {
                PostOrder(T->lchild);
                PostOrder(t->rchild);
                visit(T);
        }
}

void InOrder2(BiTree T) //非递归实现中序遍历，使用栈
{
        InitStack(S);
        BiTree p = T;
        while (p || !IsEmpty(S)) {
                if (p) {
                        Push(S, p);
                        p = p->lchild;
                } else {
                        Pop(S, p);
                        visit(p);
                        p = p->rchild;
                }
        }
}

void LevelOrder(BiTree T) //层次遍历，使用队列
{
        InitQueue(Q);
        BiTree p;
        EnQueue(Q, T);
        while (!IsEmpty(Q)) {
                DeQueue(Q, p);
                visit(p);
                if (p->lchild != NULL)
                        EnQueue(Q, p->lchild);
                if (p->rchild != NULL)
                        EnQueue(Q, p->rchild);
        }
}

//ltag = 0 表示lchild域指向左孩子
//ltag = 1 表示lchild域指向前驱结点
//rtag = 0 表示rchild域指向右孩子
//rtag = 1 表示rchild域指向后继结点
typedef struct ThreadNode { //线索二叉树
        ElemType data;
        struct ThreadNode *lchild, *rchild;
        int ltag, rtag;
} ThreadNode, *ThreadTree;

void InThread(ThreadTree& p, ThreadTree& pre) //线索化
{
        if (p != NULL) {
                InThread(p->lchild, pre);
                if (p->lchild == NULL) {
                        p->lchild = pre;
                        p->ltag = 1;
                }
                if (pre != NUL && pre->rchild == NULL) {
                        pre->rchild = p;
                        pre->rtag = 1;
                }
                pre = p;
                InThread(p->rchild, pre);
        }
}

void CreateInThread(ThreadTree T)
{
        ThreadTree pre = NULL;
        if (T != NULL) {
                InThread(T, pre);
                pre->rchild = NULL;
                pre->rtag = 1;
        }
}

ThreadNode* Firstnode(ThreadNode* p) //求中序序列下的第一个结点
{
        while (p->ltag == 0)
                p = p->lchild;
        return p;
}

ThreadNode* Nextnode(ThreadNode* p) //求中序序列下的后继结点
{
        if (p->rtag == 0)
                return Firstnode(p->rchild);
        else
                return p->rchild;
}

void InOrder3(ThreadNode* T) //使用线索二叉树中序遍历
{
        for (ThreadNode* p = Firstnode(T); p != NULL; p = Nextnode(p))
                visit(p);
}

//双亲表示法
#define MAX_TREE_SIZE 100
typedef struct {
        ElemType data;
        int parent;
} PTNode;
typedef struct {
        PTNode nodes[MAX_TREE_SIZE];
        int n; //结点数
} PTree;

//兄弟孩子表示法
typedef struct CSNode {
        ElemType data;
        struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;

/*===================================并查集===================================*/
#define SIZE 100
int UFSets[SIZE];

//将集合S中的每个元素初始化为只有一个单元素的子集合
void Initial(int S[])
{
        for (int i = 0; i < size; i++)
                S[i] = -1;
}

//查找集合S中单元素x所在的子集合
int Find(int S[], int x)
{
        while (S[x] >= 0)
                x = S[x];
        return x;
}

//将集合S中的子集合Root2合并到子集合Root1中
void Unin(int S[], int Root1, int Root2)
{
        S[Root2] = Root1;
}

/*=====================================二叉排序树=============================*/
BSTNode* BST_Search(BiTree T, ElemType key, BSTNode*& p) //问题？p的意义何在
{
        p = NULL;
        while (T != NULL && key != T->data) { //非递归实现
                p = T;
                if (key < T->data)
                        T = T->lchild;
                else
                        T = T->rchild;
        }
        return T;
}

int BST_Insert(BiTree& T, KeyType k) //递归实现
{
        if (T == NULL) {
                T = (BiTree)malloc(sizeof(BSTNode));
                T->key = k;
                T->lchild = T->rchild = NULL;
                return 1;
        } else if (k == T->key)
                return 0;
        else if (k < T->key)
                return BST_Insert(T->lchild, k);
        else
                return BST_Insert(T->rchild, k);
}

//相同数据不同排序得到的BST不同
void Creat_BST(BiTree& T, KeyType str[], int n)
{
        T = NULL;
        int i = 0;
        while (i < n) {
                BST_Insert(T, str[i]);
                i++;
        }
}

//BST删除结点的4种情况
void RotateRight(BTNode* root)
{
        BTNode* p = root;
        BTNode* pl = p->lchild;
        BTNode* plr = pl->rchild;
        p->lchild = plr;
        pl->rchild = p;
}

void RotateLeft(BTNode* root)
{
        BTNode* p = root;
        BTNode* pr = root->rchild;
        BTNode* prl = pr->lchild;
        p->rchild = prl;
        pr->rchild = p;
}

void RotateLeftRight(BTNode* root)
{
        RotateLeft(root->lchild);
        Rotateright(root);
}

void RotateRightLeft(BTNode* root)
{
        RotateRight(root->rchild);
        RotateLeft(root);
}

/*=======================================图===================================*/
//邻接矩阵法
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct {
        VertexType Vex[MaxVertexNum];
        EdgeType Edge[MaxVertexNum][MaxVertexNum];
        int vexnum, arcnum;
} MGraph;

//邻接表法
#define MaxVertexNum 100
typedef struct ArcNode {
        int adjvex; //该弧所指向的顶点位置
        struct ArcNode* next;
        //InfoType info;
} ArcNode;
typedef struct VNode {
        VertexType data;
        ArcNode* first;
} VNode, AdjList[MaxVertexNum];
typedef struct {
        AdjList vettices;
        int vexnum, arcnum;
} ALGraph;

//十字链表，只适用于有向图
#define MaxVertexNum 100
typedef struct ArcNode {
        int tailvex, headvex;
        struct ArcNode *hlink, *tlink;
        //InfoType info;
} ArcNode;
typedef struct VNode {
        VertexType data;
        ArcNode *firstin, *firstout;
} VNode;
typedef struct {
        VNode xlist[MaxVertexNum];
        int vexnum, arcnum;
} GLGraph;

//邻接多重表，只适用与无向图
#define MaxVertexNum 100
typedef struct ArcNode {
        bool mark;
        int ivex, jvex;
        struct ArcNode *ilink, *jlink;
        //InfoType info;
} ArcNode;
typedef struct VNode {
        VertexType data;
        ArcNode* firstedge;
} VNode;
typedef struct {
        VNode adjmulist[MaxVertesNum];
        int vexnum, arcnum;
} AMLGraph;

//广度优先遍历，队列
bool visited[Max_Vertex_Num];
void BFSTraverse(Graph G)
{
        for (i = 0; i < G.vexnum; ++i)
                vistied[i] = false;
        InitQueue(Q);
        for (i = 0; i < G.vexnum; ++i)
                if (!visited[i])
                        BFS(G, i);
}
void BFS(Graph G, int v)
{
        visit(v);
        visited[v] = true;
        Enqueue(Q, v);
        while (!isEmpty(Q)) {
                DeQueue(Q, v);
                for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
                        if (!visited[w]) {
                                visit(w);
                                visited[w] = true : EnQueue(Q, w);
                        }
        }
}

//求无权图单源最短路径
void BFS_MIN_Distance(Graph G, int u)
{
        for (i = 0; i < G.vexnum; ++i)
                d[i] = 99999999;
        visited[u] = true;
        d[u] = 0;
        EnQueue(Q, u);
        while (!isEmpty(Q)) {
                DeQueue(Q, u);
                for (w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))
                        if (!visited[w]) {
                                visited[w] = true;
                                d[w] = d[u] + 1;
                                EnQueue(Q, w);
                        }
        }
}

//深度优先遍历，递归
bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G)
{
        for (v = 0; v < G, vexnum; ++v)
                visited[v] = false;
        for (v = 0; v < G, vexnum; ++v)
                if (!visited[v])
                        DFS(G, v);
}
void DFS(Graph G, int v)
{
        visit(v);
        visited[v] = true;
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
                if (!visited[w]) {
                        DFS(G, w);
                }
}

/*=================================顺序查找===================================*/
typedef struct {
        ElemType* elem;
        int TableLen;
} SSTable;

int Search_Seq(SSTable ST, ElemType key)
{
        ST.elem[0] = key; //哨兵，防止索引越界
        for (i = ST.TableLen; ST.elem[i] != key; --i)
                ;
        return i;
}
/*================================折半查找====================================*/
//要求苛刻：有序的顺序表
int Binary_Search(SeqList L, elemType key)
{
        int low = 0, high = L.TableLen - 1, mid; //索引
        while (low <= high) {
                mid = (low + high) / 2;
                if (L.elem[mid] == key)
                        return mid;
                else if (l.elem[mid] > key)
                        high = mid - 1;
                else
                        low = mid + 1;
        }
        return -1;
}

/*=====================================串=====================================*/
//定长顺序存储
#define MAXLEN 255
typedef struct {
        char ch[MAXLEN];
        int length;
} SString;

//堆分配存储
typedef struct {
        char* ch;
        int length;
} HString;

/*==================================直接插入排序==============================*/
void InsertSort(ElemType A[], int n)
{
        int i, j;
        for (i = 2; i <= n; i++)
                if (A[i].key < A[i - 1].key) {
                        A[0] = A[i]; //哨兵
                        for (j = i - 1; A[0].key < A[j].key; --j)
                                A[j + 1] = A[j];
                        A[j + 1] = A[0];
                }
}

/*==================================折半插入排序==============================*/
void InsertSort(ElemType A[], int n)
{
        int i, j, low, high, mid;
        for (i = 2; i <= n; i++) {
                A[0] = A[i];
                low = 1;
                high = i - 1;
                while (low <= high) {
                        mid = (low + high) / 2;
                        if (A[mid].key > A[0].key)
                                heigh = mid - 1;
                        else
                                low = mid + 1;
                }
                for (j = 8 - 1; j >= high + 1; --j)
                        a[j + 1] = A[j];
                A[high + 1] = A[0];
        }
}

/*================================希尔排序====================================*/
void ShellSort(ElemType A[], int n)
{
        for (dk = n / 2; dk >= 1; dk = dk / 2)
                for (i = dk + 1; i <= n; ++i)
                        if (A[i].key < A[i - dk].key) {
                                A[0] = A[i]; //不是哨兵，只是暂存单元
                                for (j - i - dk;
                                     j > 0 && A[0].key < A[j].key; j -= dk)
                                        A[j + dk] = A[0];
                        }
}

/*===================================冒泡排序=================================*/
void BubbleSort(ElemType A[], int n)
{
        for (i = 0; i < n - 1; i++) {
                flag = false;
                for (j = n - 1; j > i; j--)
                        if (A[j - 1].key > A[j].key) {
                                swap(A[j - 1], A[j]);
                                flag = true;
                        }
                if (flag == false)
                        return;
        }
}

/*==================================快速排序==================================*/
void QuickSort(ElemType A[], int low, int high)
{
        if (low < high) {
                int pivotpos = Partition(A, low, high);
                QuickSort(A, low, pivotpos - 1);
                QuickSort(A, pivotpost + 1, high);
        }
}
int Partition(ElemType A[], int low, int high)
{
        ElemType pivot = A[low];
        while (low < high) {
                while (low < high && A[high] >= pivot)
                        --high;
                A[low] = A[high];
                while (low < high && A[low] <= pivot)
                        ++low;
        }
        A[low] = pivot;
        return low;
}

/*=============================选择排序=======================================*/
void SelectSort(ElemType A[], int n)
{
        for (i = 0; i < n - 1; i++) {
                min = i;
                for (j = i + 1; j < n; j++)
                        if (A[j] < A[min])
                                min = j;
                if (min != i)
                        swap(A[i], A[min]);
        }
}

/*==============================堆排序========================================*/
void BuldMaxHeap(ElemType A[], int len)
{
        for (int i = len / 2; i > 0; i--)
                AdjustDown(A, i, len);
}

//向下调整
void AdjustDown(ElemType A[], int k, int len)
{
        A[0] = A[k];
        for (i = 2 * k; i <= len; i *= 2) {
                if (i < len && A[i] < A[i + 1])
                        i++;
                if (A[0] >= A[i])
                        break;
                else {
                        A[k] = A[i];
                        k = i;
                }
        }
        A[k] = A[0];
}

void HeapSort(ElemType A[], int len)
{
        BuildMaxHeap(A, len);
        for (i = len; i > 1; i--) {
                Sqap(A[i], A[1]);
                AdjustDown(A, 1, i - 1);
        }
}

//向上调整
void AdjustUp(ElemType A[], int k)
{
        A[0] = A[k];
        int i = k / 2;
        while (i > 0 && A[i] < A[0]) {
                A[k] = A[i];
                k = i;
                i = k / 2;
        }
        A[k] = A[0];
}

/*=================================归并排序===================================*/
//前提：A[low...mid] 和 A[mid+1...high]各自有序
ElemType* B = (ElemType*)malloc((n + 1) * sizeof(ElemType));
void Merge(ElemType A[], int low, int mid, int high)
{
        for (int k = low; k <= high; k++)
                b[k] = A[k];
        for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
                if (B[i] <= B[j])
                        A[k] = B[i++];
                else
                        A[k] = B[j++];
        }
        while (i <= mid)
                A[k++] = B[i++];
        while (j <= high)
                A[k++] = B[k++];
}

void MergeSort(ElemType A[], int low, int high)
{
        if (low < high) {
                int mid = (low + high) / 2;
                MergeSort(A, low, mid);
                MergeSort(A, mid + 1, high);
                Merge(A, low, mid, high);
        }
}