数据结构笔记

抽象数据类型线性表

单链表基本操作

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int d;
    Node *nxt;
    
    Node() {
        this->d = 0;
        this->nxt = NULL;
    }
};
struct ADTList {
    Node *head;
    int size;
    
    ADTList() {
        this->size = 0;
        this->head = NULL;
    }
};
void InitList(ADTList* &L) {
    L = new ADTList();
}
void DestoryList(ADTList* &L) {
    delete L;
    L = NULL;
}
void ClearList(ADTList* &L) {
    delete L;
    InitList(L);
}
bool ListEmpty(ADTList* L) {
    if(L == NULL || L->size == 0) return true;
    return false; 
}
int ListLength(ADTList* L) {
    if(L == NULL) return 0;
    return L->size;
}
void GetElem(ADTList* L, int i, int &e) {
    if(L == NULL || i<1 || i>ListLength(L)) {
        e = 0; return;
    }
    Node *p=L->head;
    for(int j=1; j<i; j++) p=p->nxt;
    e = p->d;
    return;
}
int LocateElem(ADTList* L, int e) {
    if(L == NULL) return 0;
    int counter = 0;
    for(Node *p=L->head; p; p=p->nxt) {
        counter++;
        if(e == p->d) return counter;
    }
    return 0;
}
void PriorElem(ADTList *L, int cur_e, int &pre_e) {
    int loc = LocateElem(L, cur_e);
    GetElem(L, loc-1, pre_e);
}
void NextElem(ADTList *L, int cur_e, int &next_e) {
    int loc = LocateElem(L, cur_e);
    GetElem(L, loc+1, next_e);
}
/*
void PriorElem(ADTList *L, int cur_e, int &pre_e) {
	if(L == NULL || L->size<2) {
		pre_e = 0;
		return;
	}
	for(Node *p=L->head->nxt, *q=L->head; p; q=p, p=p->nxt) {
		if(cur_e == p->d) { pre_e = q->d; return; }
	}
	pre_e = 0; return;
}
void NextElem(ADTList *L, int cur_e, int &next_e) {
	if(L == NULL || L->size<2) { next_e = 0; return; }
	for(Node *p=L->head; p; p=p->nxt) {
		if(cur_e == p->d && p->nxt != NULL) { next_e = p->nxt->d; return; }
	}
	next_e = 0; return;
}*/
void ListInsert(ADTList* &L, int i, int e) {
    if(L==NULL || i<1 || i>ListLength(L)+1) return;
    if(i == 1) {
        Node *p = new Node();
        p->d = e; p->nxt = L->head;
        L->head = p; L->size++;
        return; 
    }
    Node *p = L->head;
    for(int j=2; j<i; j++, p=p->nxt);
    Node *tmp = p->nxt;
    p->nxt = new Node();
    p->nxt->d = e, p->nxt->nxt = tmp;
    L->size++;
    return;
}
void ListDelete(ADTList* &L, int i, int &e) {
    if(L == NULL || i<1 || i>ListLength(L)) { e=0; return; }
    if(i == 1) {
        e = L->head->d;
        L->head = L->head->nxt; L->size--;
        return;
    }
    Node *p = L->head;
    for(int j=2; j<i; j++, p=p->nxt);
    e = p->nxt->d;
    p->nxt = p->nxt->nxt;
    L->size--;
}
bool ListTraverse(ADTList* L) {
    if(L==NULL) return false;
    for(Node *p=L->head; p; p=p->nxt) printf("%d%c", p->d, " -"[p->nxt!=NULL]);
    return true;
}

相关测试代码…可能还是有bug的

void Test1() {
    ADTList *L;
    InitList(L);
    cout << ListEmpty(L) << endl;
    ListInsert(L, 1, 3);
    ListTraverse(L);
    cout << "ok" << endl;
    ListInsert(L, 1, 4);
    ListTraverse(L);
    cout << "ok" << endl;
    ListInsert(L, 2, 5);
    ListTraverse(L);
    cout << "ok" << endl;
    ListInsert(L, 4, 6);
    ListTraverse(L);
    cout << "ok" << endl;
    cout << ListLength(L) << endl;
    int x;
    ListDelete(L, 2, x);
    cout << x << endl;
    ListTraverse(L);
    cout << "ok" << endl;
    cout << ListLength(L) << endl;
    
    cout << "----------------------" << endl;
    
    ListInsert(L, 3, 7);
    ListTraverse(L);
    cout << "ok" << endl;
    cout << ListLength(L) << endl;
    
    NextElem(L, 6, x);
    cout << x << endl;
    PriorElem(L, 6, x);
    cout << x << endl;
    NextElem(L, 7, x);
    cout << x << endl;
    GetElem(L, 3, x);
    cout << x << endl;
    cout << ListEmpty(L) << endl;
    DestoryList(L);
    cout << ListEmpty(L) << endl;
}

单链表操作 - 翻转

void ListReverse(ADTList *L) {
    if(L == NULL) return;
    Node *p, *q, *r;
    for(p=L->head, q=NULL, r; p; p=r) {
        r = p->nxt;
        p->nxt = q;
        q = p;
    } L->head = q;
}

测试

void Test3() {
    ADTList *La;
    InitList(La);
    ListInsert(La, 1, 10);
    ListInsert(La, 1, 9);
    ListInsert(La, 1, 7);
    ListTraverse(La);
    ListReverse(La);
    ListTraverse(La);
}

多链表操作

void Union(ADTList* &La, ADTList* Lb) {
    int La_len=ListLength(La), Lb_len=ListLength(Lb);
    for(int i=1; i<=Lb_len; i++) {
        int e;
        GetElem(Lb, i, e);
        if(!LocateElem(La, e)) ListInsert(La, ++La_len, e);
    }
}
void UnionWithOrder(ADTList* &La, ADTList* Lb) {
    int La_len = ListLength(La), Lb_len = ListLength(Lb);
    int i=1;
    for(int j=1; j<=Lb_len; j++) {
        int e_a, e_b; GetElem(Lb, j, e_b);
        GetElem(La, i, e_a);
//        if(LocateElem(La, e_b)) continue;
        while(i<=La_len && e_a < e_b) { i++; GetElem(La, i, e_a); }
        cout << e_b << " " << i << endl;
        ListInsert(La, i, e_b); La_len++;
    }
}
void MergeList(ADTList* La, ADTList* Lb, ADTList* &Lc) {
    InitList(Lc);
    int La_len = ListLength(La), Lb_len = ListLength(Lb), Lc_len=ListLength(Lc);
    int i=1, j=1;
    for( ;i<=La_len && j<=Lb_len; ) {
        int e_a, e_b;
        GetElem(La, i, e_a); GetElem(Lb, j, e_b);
        if(e_a <= e_b) { ListInsert(Lc, ++Lc_len, e_a); ++i; }
        else { ListInsert(Lc, ++Lc_len, e_b); ++j; }
    }
    for(; i<=La_len; i++) {
        int e_a; GetElem(La, i, e_a);
        ListInsert(Lc, ++Lc_len, e_a);
    }
    for(; j<=Lb_len; j++) {
        int e_b; GetElem(Lb, i, e_b);
        ListInsert(Lc, ++Lc_len, e_b);
    }
}

相关测试代码，同上…可能有错

void Test2() {
    ADTList *La, *Lb;
    InitList(La); InitList(Lb);
    ListInsert(La, 1, 10);
    ListInsert(La, 1, 9);
    ListInsert(La, 1, 7);
    ListTraverse(La);
    
    ListInsert(Lb, 1, 8);
    ListInsert(Lb, 1, 6);
    ListInsert(Lb, 1, 5);
    ListTraverse(Lb);
    
//    Union(La, Lb);
//    UnionWithOrder(La, Lb);
    ADTList *Lc;
    MergeList(La, Lb, Lc);
    ListTraverse(Lc);
}

双向链表

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *pre, *nxt;
    Node() {
        this->data = 0;
        this->pre = NULL;
        this->nxt = NULL;
    }
};

struct DLL { // Double_Linked_List
    Node *head;
    int size;
    
    DLL() {
        this->head = NULL;
        this->size = 0;
    }
};
void InitList(DLL* &L) {
    L = new DLL();
}
void DestoryList(DLL* &L) {
    if(L == NULL) return;
    if(L->size != 0) delete L;
    L = NULL;
}
void ClearList(DLL* &L) {
    if(L == NULL) return;
    if(L->size) L = new DLL();
}
int ListEmpty(DLL *L) {
    if(L == NULL) return true;
    if(L->size) return false;
    return true;
}
int ListLength(DLL *L) {
    if(L == NULL) return 0;
    return L->size;
}
void GetElem(DLL *L, int i, int &e) {
    if(L == NULL || i<1 || i>ListLength(L)) { e=0; return; }
    Node *p=L->head;
    for(int j=1; j<i; j++)  p=p->nxt;
    e=p->data;
}
int LocateElem(DLL *L, int e) {
    if(L == NULL) return 0;
    int counter = 0;
    for(Node *p=L->head; p; p=p->nxt) {
        ++counter;
        if(p->data == e) return counter;
    } return 0;
}
void PriorElem(DLL *L, int cur_e, int &pre_e) {
    int loc = LocateElem(L, cur_e);
    GetElem(L, loc-1, pre_e);
}
void NextElem(DLL *L, int cur_e, int &next_e) {
    int loc = LocateElem(L, cur_e);
    GetElem(L, loc+1, next_e);
}
void ListInsert(DLL* &L, int i, int e) {
    if(L==NULL || i<1 || i>ListLength(L)+1) return;
    if(i==1) {
        Node *q=new Node();
        q->data = e; q->nxt = L->head; q->pre = NULL;
        if(L->head) L->head->pre = q; L->head = q; L->size++;
        return;
    }
    Node *p=L->head;
    for(int j=1; j<i-1; j++) p=p->nxt;
    Node *q = new Node();
    q->data = e; q->pre = p; q->nxt = p->nxt;
    if(p->nxt) p->nxt->pre = q;
    p->nxt = q;
    L->size++;
}
void ListDelete(DLL* &L, int i, int &e) {
    if(L==NULL || i<1 || i>ListLength(L)) { e=0; return; }
    Node *p = L->head; L->size--;
    for(int j=1; j<i; j++) p=p->nxt;
    e = p->data;
    if(p->pre) p->pre->nxt = p->nxt;
    if(p->nxt) p->nxt->pre = p->pre;
}
bool ListTraverse(DLL* L) {
    if(L==NULL) return false;
    for(Node *p=L->head; p; p=p->nxt) printf("%d%c", p->data, " -"[p->nxt!=NULL]);
    return true;
}

相关测试代码，用的上面的

void Test1() {
    DLL *L;
    InitList(L);
    cout << ListEmpty(L) << endl;
    ListInsert(L, 1, 3);
    ListTraverse(L);
    cout << "ok" << endl;
    ListInsert(L, 1, 4);
    ListTraverse(L);
    cout << "ok" << endl;
    ListInsert(L, 2, 5);
    ListTraverse(L);
    cout << "ok" << endl;
    ListInsert(L, 4, 6);
    ListTraverse(L);
    cout << "ok" << endl;
    cout << ListLength(L) << endl;
    int x;
    ListDelete(L, 2, x);
    cout << x << endl;
    ListTraverse(L);
    cout << "ok" << endl;
    cout << ListLength(L) << endl;
    
    cout << "----------------------" << endl;
    
    ListInsert(L, 3, 7);
    ListTraverse(L);
    cout << "ok" << endl;
    cout << ListLength(L) << endl;
    
    NextElem(L, 6, x);
    cout << x << endl;
    PriorElem(L, 6, x);
    cout << x << endl;
    NextElem(L, 7, x);
    cout << x << endl;
    GetElem(L, 3, x);
    cout << x << endl;
    cout << ListEmpty(L) << endl;
    DestoryList(L);
    cout << ListEmpty(L) << endl;
}

多项式

#include <bits/stdc++.h>
using namespace std;

struct Node {
    double a;
    int n;
    Node* nxt;
    Node() {
        a=0; n=0; nxt=NULL;
    }
    Node(double a, int n, Node* nxt=NULL) {
        this->a = a; this->n = n; this->nxt = nxt;
    }
};

struct Polynomial {
    Node* head;
    int size;
    Polynomial() { this->head=NULL; this->size=0; }
};
void CreatePolyn(Polynomial* &P, int m) {
    P = new Polynomial();
    Node *p=P->head,*q=NULL;
    for(int i=1; i<=m; i++) {
        int x,y;
        cin >> x >> y;
        p = new Node(x, y);
        if(i==1) P->head=p;
        if(q) q->nxt=p;
        q=p;
    } P->size = m;
}
void DestroyPolyn(Polynomial* &P) {
    for(Node* p=P->head, *q=NULL; p; p=p->nxt) {
        if(q) delete q; q=p;
    }
    delete P;
}
void PrintPolyn(Polynomial *P) {
    if(P==NULL) return;
    cout << "f(x) = ";
    if(!P->size) cout << "0"; 
    for(Node *p=P->head; p; p=p->nxt) {
        if(p->a > 0) cout << "+";
        cout << p->a << "x^" << p->n << " ";
    }cout << endl;
}
int PolynLength(Polynomial *P) {
    if(P==NULL) return 0;
    return P->size;
}
void AddPolyn(Polynomial *&Pa, Polynomial *&Pb) {
    if(Pa==NULL || Pb == NULL) return;
    if(Pa->size == 0) { swap(Pa, Pb); return; }
    if(Pb->size == 0) { return; }
    if(Pa->head->n > Pb->head->n) swap(Pa, Pb);
    int Lb = PolynLength(Pb);
    Node *p=Pa->head, *q=Pb->head;
    for(int i=1; i<=Lb; i++) {
        while(p->nxt && p->nxt->n <= q->n) p=p->nxt;
        if(p->n == q->n) p->a+=q->a;
        else {
            Node *r = new Node(q->a, q->n, p->nxt);
            p->nxt = r; p=r; Pa->size++;
        }
        q=q->nxt;
    }
//    PrintPolyn(Pa);
    for(q=NULL, p=Pa->head; p; p=p->nxt) {
        if(p->a==0) {
            if(q) q->nxt = p->nxt;
            else Pa->head = p->nxt;
        } else q=p;
    }
    DestroyPolyn(Pb);
}
void SubtractPolyn(Polynomial *&Pa, Polynomial *&Pb) {
    if(Pa==NULL || Pb == NULL) return;
    for(Node *q=Pb->head; q; q=q->nxt) q->a = -q->a;
    AddPolyn(Pa, Pb);
}
void MultiplyPolyn(Polynomial *&Pa, Polynomial *&Pb) {
    if(Pa==NULL || Pb == NULL) return;
    Polynomial *Pc = new Polynomial();
    Node *q=Pb->head;
    for(; q; q=q->nxt) {
        Polynomial *Pd = new Polynomial();
        for(Node *p=Pa->head, *lr=NULL; p; p=p->nxt) {
            Node *r=new Node(p->a*q->a, p->n+q->n);
            if(lr) lr->nxt=r;
            else Pd->head=r;
            lr=r;
        } Pd->size = Pa->size;
//        PrintPolyn(Pd);
        AddPolyn(Pc, Pd);
//        PrintPolyn(Pc);
//        cout << "------" << endl;
    }
    DestroyPolyn(Pa);
    Pa=Pc;
    DestroyPolyn(Pb);
}

测试代码 仅经过小数据测试233

void test() {
    Polynomial *Pa, *Pb;
    CreatePolyn(Pa, 3);
    PrintPolyn(Pa);
    
    CreatePolyn(Pb, 3);
    PrintPolyn(Pb);
    
//    AddPolyn(Pa, Pb);
//    SubtractPolyn(Pa, Pb);
    MultiplyPolyn(Pa, Pb);
    PrintPolyn(Pa);
}

栈和队列

栈的几个应用

进制转换

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
struct Stack {
    int a[N];
    int tp;
    
    Stack() { tp = 0; }
    int top() { return a[tp]; }
    void push(int x) { a[++tp]=x; }
    void pop() { --tp; }
    int empty() { return tp==0; }
} stk;

int main() {
    int x, y;
    cin >> x >> y;
    for(;x;) {
        stk.push(x%y); x/=y;
    }
    for(;!stk.empty(); stk.pop()) cout << stk.top();
    return 0;
}

括号匹配

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
struct Stack {
    int a[N];
    int tp;
    
    Stack() { tp = 0; }
    int top() { return a[tp]; }
    void push(int x) { a[++tp]=x; }
    void pop() { --tp; }
    int empty() { return tp==0; }
} stk;

int main() {
    string s;
    cin >> s;
    for(int i=0; i<s.length(); i++) {
//        cout << i << " " << s[i] << endl;
        if(s[i]=='(' || s[i]=='[') stk.push(s[i]);
        else if(s[i]==')') {
            if(stk.empty() || stk.top()!='(') { cout << "error" << endl;return 0; }
            else stk.pop();
        } else if(s[i]==']') {
            if(stk.empty() || stk.top()!='[') { cout << "error" << endl;return 0; }
            else stk.pop();
        }
    }
    if(!stk.empty()) cout << "error" << endl;
    else cout << "right" << endl;
    return 0;
}

栈

#include <bits/stdc++.h>
using namespace std;

const int N = 105;

struct Stack {
    int stk[N], top;
    Stack() {
        memset(stk, 0, sizeof(stk));
        top = 0;
    }
};

void InitStack(Stack* &S) {
    S=new Stack();
}
void DestoryStack(Stack *&S) {
    if(S!=NULL) delete S;
}
void ClearStack(Stack *&S) {
    memset(S->stk, 0, sizeof(S->stk));
    S->top=0;
}
int StackEmpty(Stack *S) {
    return S==NULL || S->top == 0;
}
int StackLength(Stack *S) {
    return S==NULL ? 0 : S->top;
}
void GetTop(Stack *S, int &e) {
    e=(S==NULL?0:S->stk[S->top]);
}
void Push(Stack* &S, int e) {
    if(S==NULL) return;
    S->stk[++S->top] = e;
}
void Pop(Stack* &S, int &e) {
    if(S==NULL || S->top==0) { e=0; return; }
    e = S->stk[S->top--];
}
void StackTraverse(Stack *S) {
    if(S==NULL) return;
    for(int i=1; i<=S->top; i++) cout << S->stk[i] << "- "[i==S->top];
    cout << endl; 
}

测试代码

void Test() {
    Stack *S; int top;
    InitStack(S);
    cout << StackLength(S) << endl;
    Push(S, 1);
    GetTop(S, top);
    cout << top << endl;
    StackTraverse(S);
    Push(S, 2);
    StackTraverse(S);
    Pop(S, top);
    cout << top << endl;
    StackTraverse(S);
    Push(S, 3);
    StackTraverse(S);
}

1234出栈顺序

DFS搜索回溯 一共14种

#include <bits/stdc++.h>
using namespace std;

const int N = 105;

struct Stack {
    int stk[N], top;
    Stack() {
        memset(stk, 0, sizeof(stk));
        top = 0;
    }
};

void InitStack(Stack* &S) {
    S=new Stack();
}
void DestoryStack(Stack *&S) {
    if(S!=NULL) delete S;
}
void ClearStack(Stack *&S) {
    memset(S->stk, 0, sizeof(S->stk));
    S->top=0;
}
int StackEmpty(Stack *S) {
    return S==NULL || S->top == 0;
}
int StackLength(Stack *S) {
    return S==NULL ? 0 : S->top;
}
void GetTop(Stack *S, int &e) {
    e=(S==NULL?0:S->stk[S->top]);
}
void Push(Stack* &S, int e) {
    if(S==NULL) return;
    S->stk[++S->top] = e;
}
void Pop(Stack* &S, int &e) {
    if(S==NULL || S->top==0) { e=0; return; }
    e = S->stk[S->top--];
}
void StackTraverse(Stack *S) {
    if(S==NULL) return;
    for(int i=1; i<=S->top; i++) cout << S->stk[i] << "- "[i==S->top];
    cout << endl; 
}

void StackCopy(Stack *S, Stack *T) {
    if(T) delete T;
    InitStack(T);
    memcpy(T->stk ,S->stk, sizeof(S->stk));
    T->top = S->top;
}

void DFS(int i, Stack *S, Stack *rec) {
    if(i>4) {
        int tmp=StackLength(rec), tmp1;
        while(!StackEmpty(S)) {
            int e; Pop(S, e);
            Push(rec, e);
        } StackTraverse(rec);
        while(StackLength(rec) != tmp) {
            Pop(rec, tmp1);
            Push(S, tmp1); 
        }
        return;
    }
    int tmp, ls = StackLength(S);
    // 不出栈
    Push(S, i); // 入栈
    DFS(i+1, S, rec);
    Pop(S, tmp); 
    
    // 出栈 
    for(int j=1; j<=ls; j++) {
        for(int k=0; k<j; k++) {
            int tmp1;
            Pop(S, tmp1);
            Push(rec, tmp1);
        }
        Push(S, i);
        DFS(i+1, S, rec);
        Pop(S, tmp);
        for(int k=0; k<j; k++) {
            int tmp1;
            Pop(rec, tmp1);
            Push(S, tmp1);
        }
    }
}
int main() {
    Stack *S, *rec;
    InitStack(S); InitStack(rec);
    DFS(1, S, rec);
    return 0;
}

迷宫问题

输出所有可能路径

#include <bits/stdc++.h>
using namespace std;

const int N = 105;

struct Stack {
    int stk[N], top;
    Stack() {
        memset(stk, 0, sizeof(stk));
        top = 0;
    }
};

void InitStack(Stack* &S) {
    S=new Stack();
}
void DestoryStack(Stack *&S) {
    if(S!=NULL) delete S;
}
void ClearStack(Stack *&S) {
    memset(S->stk, 0, sizeof(S->stk));
    S->top=0;
}
int StackEmpty(Stack *S) {
    return S==NULL || S->top == 0;
}
int StackLength(Stack *S) {
    return S==NULL ? 0 : S->top;
}
void GetTop(Stack *S, int &e) {
    e=(S==NULL?0:S->stk[S->top]);
}
void Push(Stack* &S, int e) {
    if(S==NULL) return;
    S->stk[++S->top] = e;
}
void Pop(Stack* &S, int &e) {
    if(S==NULL || S->top==0) { e=0; return; }
    e = S->stk[S->top--];
}
void StackTraverse(Stack *S) {
    if(S==NULL) return;
    for(int i=1; i<=S->top; i++) cout << "(" << S->stk[i]/10 << "," << S->stk[i]%10 << ")" << "- "[i==S->top];
    cout << endl; 
}

void StackCopy(Stack *S, Stack *T) {
    if(T) delete T;
    InitStack(T);
    memcpy(T->stk ,S->stk, sizeof(S->stk));
    T->top = S->top;
}

int mp[10][10] = {
 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
 {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
 {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
 {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
 {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
 {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
 {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
 {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
 {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

int tx[] = {0, 0, 1, -1};
int ty[] = {1, -1, 0, 0};

void Search(int x, int y, int dx, int dy, Stack *S) {
    Push(S, x*10+y); mp[x][y]=1;
    if(x==dx && y==dy) {
        StackTraverse(S);
        int tmp;
        Pop(S, tmp); mp[x][y]=0;
        return;
    }
    for(int i=0; i<4; i++) {
        int ttx=x+tx[i], tty=y+ty[i];
        if(!mp[ttx][tty]) {
            Search(ttx, tty, dx, dy, S);
        }
    }
    int tmp;
    Pop(S, tmp); mp[x][y]=0;
}
int main() {
    Stack *S; InitStack(S);
    Search(1, 1, 8, 8, S);
    return 0;
}

队列

#include <bits/stdc++.h>
using namespace std;

const int N = 105;

struct Queue {
    int a[N];
    int head, tail;
    Queue() {
        memset(a, 0, sizeof(a));
        head = 1; tail = 0;
    }
};

void InitQueue(Queue *&Q) {
    Q = new Queue();
}
void DestroyQueue(Queue *&Q) {
    if(Q) delete Q;
}
void ClearQueue(Queue *&Q) {
    memset(Q->a, 0, sizeof(Q->a));
    Q->head = 1; Q->tail = 0;
}
int QueueEmpty(Queue *Q) {
    return Q->head == Q->tail;
}
int QueueLength(Queue *Q) {
    return Q->tail-Q->head+1;
}
void GetHead(Queue *Q, int &e) {
    e=(Q==NULL?0:Q->a[Q->head]);
}
void EnQueue(Queue *&Q, int e) {
    if(Q==NULL) return;
    Q->a[++Q->tail] = e;
}
void DeQueue(Queue *&Q, int &e) {
    if(Q==NULL) { e=0; return; }
    e=Q->a[Q->head++];
}
void QueueTraverse(Queue *Q) {
    for(int i=Q->head; i<=Q->tail; i++) cout << Q->a[i] << "- "[i==Q->tail];
    cout << endl;
}

测试不全面

void Test() {
    Queue *Q; int e;
    InitQueue(Q);
    EnQueue(Q, 1);
    GetHead(Q, e);
    cout << e << endl;
    cout << QueueLength(Q) << endl;
    EnQueue(Q, 2);
    EnQueue(Q, 4);
    QueueTraverse(Q);
    cout << QueueLength(Q) << endl;
    DeQueue(Q, e);
    cout << e << endl;
    QueueTraverse(Q);
}

串

我的下标是从0开始的，课本是从1开始的，所以有很多pos--的操作

#include <bits/stdc++.h>
using namespace std;

const int N = 255;
typedef char SString[N];

void StrAssign(SString &T, char* chars) {
//  strcpy(T, chars);
    for(int i=0; *chars; chars++, i++) T[i]=*chars;
}
void StrCopy(SString &T, SString S) {
    if(strlen(S)!=0) StrAssign(T, S);
}
int StrEmpty(SString S) {
    if(S==NULL || strlen(S)==0) return true;
    return false;
}
int StrLength(SString S) {
    int l=0;
    for( ;S[l++];);
    return l-1;
}
int StrCompare(SString S, SString T) {
//  return strcmp(S, T);
    for(int i=0; i<min(StrLength(S), StrLength(T)); i++)
        if(S[i]>T[i]) return 1;
        else if(S[i]<T[i]) return -1;
    if(StrLength(S) < StrLength(T)) return 1;
    else if(StrLength(S) == StrLength(T)) return 0;
    return -1;
}
void ClearString(SString &S) {
    memset(S, 0, sizeof(S));
}
void Concat(SString &T, SString S1, SString S2) {
    if(StrEmpty(S1)) { StrCopy(T, S2); return; }
    if(StrEmpty(S2)) { StrCopy(T, S1); return; }
    StrCopy(T, S1);
    for(int i=0; i<StrLength(S2); i++) T[StrLength(S1)+i]=S2[i];
}
void SubString(SString &sub, SString S, int pos, int len) {
    pos--;
    ClearString(sub);
    for(int i=pos; i<min(StrLength(S), pos+len); i++) 
        sub[i-pos]=S[i];
}
int Index(SString S, SString T, int pos) {
    pos--;
    if(pos<0) return 0;
    int n=StrLength(S), m=StrLength(T);
    for(int i=pos; i<n-m+1; i++) {
        SString sub;
        SubString(sub, S, i+1, m);
        if(StrCompare(sub, T)==0) return i+1;
    } return 0;
}
void StrInsert(SString &S, int pos, SString T) {
    pos--;
    if(pos<0 || pos>StrLength(S)) return;
    int lt=StrLength(T), ls=StrLength(S);
    for(int i=ls-1; i>=pos; --i) {
        S[i+lt] = S[i];
    }
    for(int i=pos; i<pos+lt; i++) S[i]=T[i-pos];
}
void StrDelete(SString &S, int pos, int len) {
    pos--;
    if(pos<0 || pos+len>StrLength(S)) return;
    int ls=StrLength(S);
    for(int i=pos+len; i<ls; i++) S[i-len]=S[i];
    for(int i=ls-len; i<ls; i++) S[i]=0;
}
void Replace(SString &S, SString T, SString V) {
    int lt=StrLength(T), lv=StrLength(V);
    for(int i=0; i<StrLength(S); i++) {
        SString sub;
        SubString(sub, S, i+1, lt);
        if(StrCompare(sub, T)==0) {
            StrDelete(S, i+1, lt);
            StrInsert(S, i+1, V);
            i=i+lv-1;
        }
    }
}
void DestroyString(SString &S) {
    delete S;
}

测试

void test() {
    SString S1, S2, S3;
    ClearString(S1), ClearString(S2), ClearString(S3);
    StrAssign(S1, "hello");
    StrAssign(S2, "world");
    cout << S1 << endl;
    cout << S2 << endl;
    cout << strlen(S1) << " " << StrLength(S1) << endl;
    cout << strlen(S2) << " " << StrLength(S2) << endl;
//  assert(strlen(S1)==StrLength(S1));
//  assert(strlen(S2)==StrLength(S2));
    cout << StrCompare(S1, S2) << endl;
    cout << StrCompare("a", "aa") << endl;
    cout << StrCompare("a", "a") << endl;
    cout << StrCompare("aa", "a") << endl;
    
    Concat(S3, S1, S2); cout << S3 << endl;
    
    SubString(S3, S1, 2, 3); cout << S3 << endl;
    cout << Index(S1, "l", 1) << endl;
    cout << Index(S1, "l", 5) << endl;
    
    StrDelete(S1, 2, 3); cout << S1 << endl;
    StrInsert(S1, 1, "ool"); cout << S1 << endl;
    Replace(S1, "o", "l"); cout << S1 << endl;
    Replace(S1, "l", "ll"); cout << S1 << endl;
}

数组

没时间了…不是自己写的，照着打的…

#include <bits/stdc++.h>
using namespace std;

#define MAX_ARRAY_DIM 8
typedef int ElemType;
typedef struct {
    ElemType *base;
    int dim;
    int *bounds;
    int *constants;
} Array;

int InitArray(Array &A, int dim, ...) {
    if(dim<1 || dim>MAX_ARRAY_DIM) return 0;
    A.dim=dim;
    A.bounds=(int*) malloc(dim*sizeof(int));
    int elemtotal=1;
    va_list ap;
    va_start(ap, dim);
    for(int i=0; i<dim; i++) {
        A.bounds[i]=va_arg(ap, int);
        if(A.bounds[i]<0) return 0;
        elemtotal *= A.bounds[i];
    }
    va_end(ap);
    A.base=(ElemType *)malloc(elemtotal * sizeof(ElemType));
    if(A.base) return 0;
    A.constants=(int*)malloc(dim*sizeof(int));
    A.constants[dim-1]=1;
    for(int i=dim-2; i>=0; --i)
        A.constants[i]=A.bounds[i+1]*A.constants[i+1];
    return 1;
}
int DestroyArray(Array &A) {
    if(!A.base) return 0;
    free(A.base); A.base=NULL;
    if(!A.bounds) return 0;
    free(A.bounds); A.bounds=NULL;
    if(!A.constants) return 0;
    free(A.constants); A.constants=NULL;
    return 1;
}
int Locate(Array A, va_list ap, int &off) {
    off=0;
    for(int i=0; i<A.dim; i++) {
        int ind = va_arg(ap, int);
        if(ind<0 || ind>=A.bounds[i]) return 0;
        off+=A.constants[i]*ind;
    } return 1;
}
int Value(Array A, ElemType &e, ...) {
    va_list ap;
    va_start(ap, e);
    int result, off;
    if((result=Locate(A, ap, off))<=0) return result;
    e=*(A.base+off);
    return 1;
}
int Assign(Array &A, ElemType e,...) {
    va_list ap;
    va_start(ap, e);
    int result, off;
    if((result=Locate(A, ap, off))<=0) return result;
    *(A.base+off)=e;
    return 1;
}

树

二叉树

基本功能和操作

#include <bits/stdc++.h>
using namespace std;

typedef int TElemType;


struct BiTNode {
    TElemType data;
    BiTNode *lc, *rc, *f;
    
    BiTNode() {
        this->data = 0;
        this->lc = this->rc = this->f = NULL;
    }
    BiTNode(TElemType d, BiTNode *l=NULL, BiTNode *r=NULL, BiTNode *f = NULL) {
        this->data = d;
        this->lc = l;
        this->rc = r;
        this->f = f;
    }
};
typedef BiTNode *BiTree;

void InitBiTree(BiTree &T) {
    if(T) delete T;
    T = NULL;
}
void DestroyBiTree(BiTree &T) {
    if(!T) return;
    DestroyBiTree(T->lc);
    DestroyBiTree(T->rc);
    if(T) delete T;
    T = NULL;
}
void CreateBiTree(BiTree &T) {
    int x; cin >> x;
    if(x==0) { T=NULL; return; }
    T = new BiTNode(x);
    CreateBiTree(T->lc);
    CreateBiTree(T->rc);
    if(T->lc) T->lc->f=T;
    if(T->rc) T->rc->f=T;
}
void ClearBiTree(BiTree &T) {
    if(!T) return;
    ClearBiTree(T->lc);
    ClearBiTree(T->rc);
    delete T; T=NULL;
}
int BiTreeEmpty(BiTree T) {
    return T?1:0;
}
int BiTreeDepth(BiTree T) {
    if(!T) return 0;
    return max(BiTreeDepth(T->lc), BiTreeDepth(T->rc));
}
BiTree Root(BiTree T) {
    while(T->f) T=T->f;
    return T;
}
int Value(BiTree T, BiTree e) {
    if(e) return e->data;
//    if(!T) return 0;
//    if(T==e) return e->data;
//    int lcv = Value(T->lc, e);
//    int rcv = Value(T->rc, e);
//    if(lcv) return lcv;
//    if(rcv) return rcv;
//    return 0;
}
void Assign(BiTree T, BiTree &e, TElemType value) {
    if(e) e->data = value;
//    if(!T) return 0;
//    if(T==e) { e->data = value; return; }
//    Assign(T->lc, e, value);
//    Assign(T->rc, e, value);
}
BiTree Parent(BiTree T, BiTree e) {
    if(e) return e->f;
    return NULL;
}
BiTree LeftChild(BiTree T, BiTree e) {
    if(e) return e->lc;
    return NULL;
}
BiTree RightChild(BiTree T, BiTree e) {
    if(e) return e->rc;
    return NULL;
}
BiTree LeftSibling(BiTree T, BiTree e) {
    if(!e->f) return NULL;
    if(e==e->f->rc) return e->f->lc;
    return NULL;
}
BiTree RightSibling(BiTree T, BiTree e) {
    if(!e->f) return NULL;
    if(e==e->f->lc) return e->f->rc;
    return NULL;
}
void InsertChild(BiTree T, BiTree p, int LR, BiTree c) {
    if(LR==0) {
        c->rc = p->lc;
        if(p->lc) p->lc->f = c;
        c->f = p; p->lc = c;
    } else {
        c->rc = p->rc;
        if(p->rc) p->rc->f = c;
        c->f = p; p->rc = c;
    }
}
void DeleteChild(BiTree T, BiTree p, int LR) {
    if(LR==0) {
        DestroyBiTree(p->lc);
    } else {
        DestroyBiTree(p->rc);
    }
}

void PreOrderTraverse(BiTree T) {
    if(!T) return;
    cout << T->data << " ";
    PreOrderTraverse(T->lc);
    PreOrderTraverse(T->rc);
}
void InOrderTraverse(BiTree T) {
    if(!T) return;
    InOrderTraverse(T->lc);
    cout << T->data << " ";
    InOrderTraverse(T->rc);
}
void PostOrderTraverse(BiTree T) {
    if(!T) return;
    PostOrderTraverse(T->lc);
    PostOrderTraverse(T->rc);
    cout << T->data << " ";
}
void LevelOrderTraverse(BiTree T) {
    queue<BiTree> q;
    q.push(T);
    for(;!q.empty();) {
        BiTree t=q.front(); q.pop();
        if(!t) continue;
        q.push(t->lc); q.push(t->rc);
        cout << t->data << " ";
    }
}
void PrePrderTraverseWithNonRecursive(BiTree T) { // 前序遍历非递归实现 
    stack<BiTree> q;
    q.push(T);
    for(;!q.empty();) {
        BiTree x=q.top(); q.pop();
        cout << x->data << " ";
        if(x->rc) q.push(x->rc);
        if(x->lc) q.push(x->lc); 
    }
}
void InPrderTraverseWithNonRecursive(BiTree T) { // 中序遍历非递归实现 
    stack<BiTree> q; map<BiTree, bool> mp;
    q.push(T);
    for(;!q.empty();) {
        BiTree x=q.top(); q.pop();
        if(mp.count(x)) { cout << x->data << " "; continue; }
        mp[x]=1;
        if(x->rc) q.push(x->rc);
        q.push(x);
        if(x->lc) q.push(x->lc); 
    }
}
void PostPrderTraverseWithNonRecursive(BiTree T) { // 后序遍历非递归实现 
    stack<BiTree> q; map<BiTree, bool> mp;
    q.push(T);
    for(;!q.empty();) {
        BiTree x=q.top(); q.pop();
        if(mp.count(x)) { cout << x->data << " "; continue; }
        mp[x]=1;
        q.push(x);
        if(x->rc) q.push(x->rc);
        if(x->lc) q.push(x->lc); 
    }
}


void test() {
    BiTree T=NULL;
    InitBiTree(T);
    CreateBiTree(T); // Enter: 1 2 0 0 3 4 0 0 5 0 0
    /* BiTree
    1
    | \
    2  3
       | \
       4  5
    */
    PreOrderTraverse(T); cout << endl;
    InOrderTraverse(T); cout << endl;
    PostOrderTraverse(T); cout << endl;
    LevelOrderTraverse(T); cout << endl;
    PrePrderTraverseWithNonRecursive(T); cout << endl;
    InPrderTraverseWithNonRecursive(T); cout << endl;
     PostPrderTraverseWithNonRecursive(T); cout << endl;
}
int main() {
    test();
    return 0;
}

二叉线索树

简单来说就是利用左右为空的节点，建立线索树，也就是中序遍历的前驱和后继

#include <bits/stdc++.h>
using namespace std;

typedef int TElemType;
enum PointerTag { Link, Thread };
struct BiThrNode {
    TElemType data;
    BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
};
typedef BiThrNode* BiThrTree;
int InOrderTraverse_Thr(BiThrTree T) {
    BiThrTree p=T->lchild;
    for(; p!=T; p=p->rchild) {
        while(p->LTag == Link) p=p->lchild;
        cout << p->data << endl;
        while(p->RTag == Thread && p->rchild!=T) {
            p=p->rchild; cout << p->data << endl;
        } p=p->rchild;
    } return 0;
}
BiThrTree pre;
void InThreading(BiThrTree p) {
    if(!p) return;
    InThreading(p->lchild);
    if(!p->lchild) { p->LTag=Thread; p->lchild=pre; }
    if(!pre->rchild) { pre->RTag = Thread; pre->rchild = p; }
    pre = p;
    InThreading(p->rchild);
}
int InOrderThreading(BiThrTree &Thrt, BiThrTree T) {
    if(!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(1);
    Thrt->LTag = Link; Thrt->RTag=Thread;
    Thrt->rchild = Thrt;
    if(!T) Thrt->lchild = Thrt;
    else {
        Thrt->lchild = T;
        pre = Thrt;
        InThreading(T);
        pre->rchild = Thrt; pre->RTag = Thread;
        Thrt->rchild = pre;
    } return 0;
}
int main() {
    
    return 0;
}

哈夫曼树和哈夫曼编码

贪心合并

#include <bits/stdc++.h>
using namespace std;

struct HTNode {
    int weight;
    int parent, lchild, rchild;
};
typedef HTNode *HuffmanTree;
typedef char **HuffmanCode;

void Select(HuffmanTree HT, int n, int &s1, int &s2) {
    s1=0;
    for(int i=1; i<=n; i++) if(HT[i].parent==0) {
        if(s1==0 || HT[i].weight<HT[s1].weight) s1=i;
    }
    s2=0;
    for(int i=1; i<=n; i++) if(HT[i].parent==0 && i!=s1) {
        if(s2==0 ||  HT[i].weight<HT[s2].weight) s2=i;
    }
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {
    if(n<=1) return;
    int m = 2*n-1;
    HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
//    cout << " init ok " << endl;
    HuffmanTree p=HT+1;
    int i;
    for(i=1; i<=n; i++, p++, ++w) *p={*w, 0, 0, 0};
    for(;i<=m; i++, p++) *p={0, 0, 0, 0};
//    for(int i=1; i<=m; i++) cout << HT[i].weight << " " << HT[i].parent << " " << HT[i].lchild << " " << HT[i].rchild << endl;
//    cout << " init ok " << endl;
    for(i=n+1; i<=m; i++) {
        int s1, s2;
        Select(HT, i-1, s1, s2);
//        cout << s1 << " " << s2 << endl;
        HT[s1].parent = HT[s2].parent = i;
        HT[i].lchild = s1; HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
//    cout << "HuffmanTree ok" << endl;
//    for(int i=1; i<=m; i++) cout << HT[i].weight << " " << HT[i].parent << " " << HT[i].lchild << " " << HT[i].rchild << endl;
    HC = (HuffmanCode)malloc((n+1)*sizeof(char*));
    char *cd = (char *)malloc(n*sizeof(char));
    cd[n-1]='\0';
    for(i=1; i<=n; i++) {
        int start = n-1;
        for(int c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent)
            if(HT[f].lchild == c) cd[--start]='0';
            else cd[--start]='1';
        HC[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy(HC[i], &cd[start]);
    } free(cd);
//    cout << "HuffmanCode ok" << endl;
}
void Traverse(HuffmanTree HT, int rt) {
    queue<int> q;
    q.push(rt);
    for(;!q.empty();) {
        int x; x=q.front(); q.pop();
        if(HT[x].lchild) q.push(HT[x].lchild), q.push(HT[x].rchild);
        else cout << HT[x].weight << endl;
    }
}
void test() { // test
    int n = 4;
    int w[] = {3, 1, 2, 1}; // 'ABACCDA' A-3, B-1, C-2, D-1
    HuffmanTree HT;
    HuffmanCode HC;
    HuffmanCoding(HT, HC, w, n);
    cout << "Traverse the tree" << endl; 
    Traverse(HT, 2*n-1); // traverse the tree by preorder
    cout << "HuffmanCode: " << endl;
    for(int i=1; i<=n; i++) cout <<(char)('A'+i-1) << ": " << HC[i] << endl; // A-0 C-10 B-110 D-111
}
int main() {
    test();
    return 0; 
}

图

邻接矩阵

#include <bits/stdc++.h>
using namespace std;

#define INF INT_MAX
#define MAX_VERTEX_NUM 20


#define Status int
#define ERROR 0
#define OK 1
typedef int VRType;
typedef int InfoType;
typedef int VertexType;


typedef enum { DG, DN, UDG, UDN } GraphKind;

typedef struct {
    VRType adj;
    InfoType *info;
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
    int vexnum, arcnum;
    GraphKind kind;
} MGraph;

int LocateVec(MGraph &G, int x) { return x; }
void Input(ArcCell &x, int y) { x.adj=y; }
Status CreateDG(MGraph &G) {
    int IncInfo;
    scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
    for(int i=0; i<G.vexnum; i++) scanf("%d", &G.vexs[i]);
    for(int i=0; i<G.vexnum; i++) for(int j=0; j<G.vexnum; j++) G.arcs[i][j]= { INF, NULL };
    for(int k=0; k<G.arcnum; k++) {
        int v1, v2, w;
        scanf("%d%d%d", &v1, &v2, &w);
        v1=LocateVec(G, v1), v2=LocateVec(G, v2);
        if(IncInfo) Input(G.arcs[v1][v2], w);
    } return OK;
}
Status CreateDN(MGraph &G) {
    int IncInfo;
    scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
    for(int i=0; i<G.vexnum; i++) scanf("%d", &G.vexs[i]);
    for(int i=0; i<G.vexnum; i++) for(int j=0; j<G.vexnum; j++) G.arcs[i][j]= { INF, NULL };
    for(int k=0; k<G.arcnum; k++) {
        int v1, v2, w;
        scanf("%d%d%d", &v1, &v2, &w);
        v1=LocateVec(G, v1), v2=LocateVec(G, v2);
        if(IncInfo) Input(G.arcs[v1][v2], w);
    } return OK;
}
Status CreateUDG(MGraph &G) {
    int IncInfo;
    scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
    for(int i=0; i<G.vexnum; i++) scanf("%d", &G.vexs[i]);
    for(int i=0; i<G.vexnum; i++) for(int j=0; j<G.vexnum; j++) G.arcs[i][j]= { INF, NULL };
    for(int k=0; k<G.arcnum; k++) {
        int v1, v2, w;
        scanf("%d%d%d", &v1, &v2, &w);
        v1=LocateVec(G, v1), v2=LocateVec(G, v2);
        if(IncInfo) Input(G.arcs[v1][v2], w);
        G.arcs[v2][v1]=G.arcs[v1][v2];
    } return OK;
}
Status CreateUDN(MGraph &G) {
    int IncInfo;
    scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
    for(int i=0; i<G.vexnum; i++) scanf("%d", &G.vexs[i]);
    for(int i=0; i<G.vexnum; i++) for(int j=0; j<G.vexnum; j++) G.arcs[i][j]= { INF, NULL };
    for(int k=0; k<G.arcnum; k++) {
        int v1, v2, w;
        scanf("%d%d%d", &v1, &v2, &w);
        v1=LocateVec(G, v1), v2=LocateVec(G, v2);
        if(IncInfo) Input(G.arcs[v1][v2], w);
        G.arcs[v2][v1]=G.arcs[v1][v2];
    } return OK;
}
Status CreateGraph(MGraph &G) {
    scanf("%d", &G.kind);
    switch(G.kind) {
        case DG: return CreateDG(G);
        case DN: return CreateDN(G);
        case UDG: return CreateUDG(G);
        case UDN: return CreateUDN(G);
        default: return ERROR;
    }
}
void test() {
    /* p152 graph7.9
1 6 10 1
0 1 2 3 4 5
0 1 5
0 3 7
1 2 4
2 0 8
2 5 9
3 2 5
3 5 6
4 3 5
5 0 3
5 4 1
    */
    MGraph G;
    CreateGraph(G);
    for(int i=0; i<G.vexnum; i++) for(int j=0; j<G.vexnum; j++) printf("%d%c", G.arcs[i][j].adj, " \n"[j+1==G.vexnum]);
}
int main() {
    test();
    return 0;
}

邻接表

#include <bits/stdc++.h>
using namespace std;

#define MAX_VERTEX_NUM 20

#define Status int
#define ERROR 0
#define OK 1
typedef int VRType;
typedef int InfoType;
typedef int VertexType;

typedef enum { DG, DN, UDG, UDN } GraphKind;
struct ArcNode {
    int adjvex;
    ArcNode* nextarc;
    InfoType *info;
};
typedef struct {
    VertexType data;
    ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];
struct ALGraph {
    AdjList vertices;
    int vexnum, arcnum;
    int kind;
};
int LocateVec(ALGraph &G, int x) { return x; }
void AddEdge(VNode &x, int y, int w, int IncInfo) {
    ArcNode *t=new ArcNode();
    t->adjvex=y;
    if(IncInfo) t->info=new int(w);
    t->nextarc=x.firstarc;
    x.firstarc=t; x.data++;
}
Status CreateDG(ALGraph &G) {
    int IncInfo;
    scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
    for(int i=0; i<G.vexnum; i++) G.vertices[i].firstarc=NULL, G.vertices[i].data=0;
    for(int k=0; k<G.arcnum; k++) {
        int v1, v2, w=0;
        scanf("%d%d", &v1, &v2);
        if(IncInfo) scanf("%d", &w);
        v1=LocateVec(G, v1), v2=LocateVec(G, v2);
        AddEdge(G.vertices[v1], v2, w, IncInfo);
    } return OK;
}
Status CreateDN(ALGraph &G) {
    int IncInfo;
    scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
    for(int i=0; i<G.vexnum; i++) G.vertices[i].firstarc=NULL, G.vertices[i].data=0;
    for(int k=0; k<G.arcnum; k++) {
        int v1, v2, w=0;
        scanf("%d%d", &v1, &v2);
        if(IncInfo) scanf("%d", &w);
        v1=LocateVec(G, v1), v2=LocateVec(G, v2);
        AddEdge(G.vertices[v1], v2, w, IncInfo);
    } return OK;
}
Status CreateUDG(ALGraph &G) {
    int IncInfo;
    scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
    for(int i=0; i<G.vexnum; i++) G.vertices[i].firstarc=NULL, G.vertices[i].data=0;
    for(int k=0; k<G.arcnum; k++) {
        int v1, v2, w=0;
        scanf("%d%d", &v1, &v2);
        if(IncInfo) scanf("%d", &w);
        v1=LocateVec(G, v1), v2=LocateVec(G, v2);
        AddEdge(G.vertices[v1], v2, w, IncInfo); AddEdge(G.vertices[v2], v1, w, IncInfo);
    } return OK;
}
Status CreateUDN(ALGraph &G) {
    int IncInfo;
    scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
    for(int i=0; i<G.vexnum; i++) G.vertices[i].firstarc=NULL, G.vertices[i].data=0;
    for(int k=0; k<G.arcnum; k++) {
        int v1, v2, w=0;
        scanf("%d%d", &v1, &v2);
        if(IncInfo) scanf("%d", &w);
        v1=LocateVec(G, v1), v2=LocateVec(G, v2);
        AddEdge(G.vertices[v1], v2, w, IncInfo); AddEdge(G.vertices[v2], v1, w, IncInfo);
    } return OK;
}
Status CreateGraph(ALGraph &G) {
    scanf("%d", &G.kind);
    switch(G.kind) {
        case DG: return CreateDG(G);
        case DN: return CreateDN(G);
        case UDG: return CreateUDG(G);
        case UDN: return CreateUDN(G);
        default: return ERROR;
    }
}
void test() {
    /* p152 graph7.9
1 6 10 1
0 1 5
0 3 7
1 2 4
2 0 8
2 5 9
3 2 5
3 5 6
4 3 5
5 0 3
5 4 1
    */
    ALGraph G;
    CreateGraph(G);
    for(int i=0; i<G.vexnum; i++) {
        cout << G.vertices[i].data << " :: -> ";
        for(ArcNode *j=G.vertices[i].firstarc; j; j=j->nextarc) cout << *(j->info) << " ";
        cout<< endl;
    }
}
int main() {
    test();
    return 0;
}

十字链表

#include <bits/stdc++.h>
using namespace std;

#define MAX_VERTEX_NUM 20

#define Status int
#define ERROR 0
#define OK 1
typedef int InfoType;
typedef int VertexType;

typedef enum { DG, DN, UDG, UDN } GraphKind;
struct ArcBox {
    int tailvex, headvex;
    ArcBox *hlink, *tlink;
    InfoType *info;
};
struct VexNode {
    VertexType data;
    ArcBox *firstin, *firstout;
};
struct OLGraph {
    VexNode xlist[MAX_VERTEX_NUM];
    int vexnum, arcnum;
    int kind;
};
int LocateVec(OLGraph &G, int x) { return x; }
void Input(InfoType &x) { scanf("%d", &x); }
Status CreateDG(OLGraph &G) {
    int IncInfo;
    scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
    for(int i=0; i<G.vexnum; i++) {
        scanf("%d", &G.xlist[i].data);
        G.xlist[i].firstin=NULL, G.xlist[i].firstout=NULL;
    }
    for(int k=0; k<G.arcnum; k++) {
        int v1, v2;
        scanf("%d%d", &v1, &v2);
        v1=LocateVec(G, v1); v2=LocateVec(G, v2);
        ArcBox *p=(ArcBox *)malloc(sizeof(ArcBox));
        *p={v1, v2, G.xlist[v2].firstin, G.xlist[v1].firstout, NULL};
        G.xlist[v2].firstin=G.xlist[v1].firstout=p;
        if(IncInfo) Input(*p->info);
    } return OK;
}
Status CreateDN(OLGraph &G) {
    int IncInfo;
    scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
    for(int i=0; i<G.vexnum; i++) {
        scanf("%d", &G.xlist[i].data);
        G.xlist[i].firstin=NULL, G.xlist[i].firstout=NULL;
    }
    for(int k=0; k<G.arcnum; k++) {
        int v1, v2;
        scanf("%d%d", &v1, &v2);
        v1=LocateVec(G, v1); v2=LocateVec(G, v2);
        ArcBox *p=(ArcBox *)malloc(sizeof(ArcBox));
        *p={v1, v2, G.xlist[v2].firstin, G.xlist[v1].firstout, NULL};
        G.xlist[v2].firstin=G.xlist[v1].firstout=p;
        if(IncInfo) Input(*p->info);
    } return OK;
}
Status CreateUDG(OLGraph &G) {
    int IncInfo;
    scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
    for(int i=0; i<G.vexnum; i++) {
        scanf("%d", &G.xlist[i].data);
        G.xlist[i].firstin=NULL, G.xlist[i].firstout=NULL;
    }
    for(int k=0; k<G.arcnum; k++) {
        int v1, v2;
        scanf("%d%d", &v1, &v2);
        v1=LocateVec(G, v1); v2=LocateVec(G, v2);
        ArcBox *p=(ArcBox *)malloc(sizeof(ArcBox));
        *p={v1, v2, G.xlist[v2].firstin, G.xlist[v1].firstout, NULL};
        G.xlist[v2].firstin=G.xlist[v1].firstout=p;
        if(IncInfo) Input(*p->info);
        swap(v1, v2);
        v1=LocateVec(G, v1); v2=LocateVec(G, v2);
        ArcBox *q=(ArcBox *)malloc(sizeof(ArcBox));
        *q={v1, v2, G.xlist[v2].firstin, G.xlist[v1].firstout, NULL};
        G.xlist[v2].firstin=G.xlist[v1].firstout=q;
        if(IncInfo) *(q->info)=*p->info;
    } return OK;
}
Status CreateUDN(OLGraph &G) {
    int IncInfo;
    scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
    for(int i=0; i<G.vexnum; i++) {
        scanf("%d", &G.xlist[i].data);
        G.xlist[i].firstin=NULL, G.xlist[i].firstout=NULL;
    }
    for(int k=0; k<G.arcnum; k++) {
        int v1, v2;
        scanf("%d%d", &v1, &v2);
        v1=LocateVec(G, v1); v2=LocateVec(G, v2);
        ArcBox *p=(ArcBox *)malloc(sizeof(ArcBox));
        *p={v1, v2, G.xlist[v2].firstin, G.xlist[v1].firstout, NULL};
        G.xlist[v2].firstin=G.xlist[v1].firstout=p;
        if(IncInfo) Input(*p->info);
        swap(v1, v2);
        v1=LocateVec(G, v1); v2=LocateVec(G, v2);
        ArcBox *q=(ArcBox *)malloc(sizeof(ArcBox));
        *q={v1, v2, G.xlist[v2].firstin, G.xlist[v1].firstout, NULL};
        G.xlist[v2].firstin=G.xlist[v1].firstout=q;
        if(IncInfo) *(q->info)=*p->info;
    } return OK;
}
Status CreateGraph(OLGraph &G) {
    scanf("%d", &G.kind);
    switch(G.kind) {
        case DG: return CreateDG(G);
        case DN: return CreateDN(G);
        case UDG: return CreateUDG(G);
        case UDN: return CreateUDN(G);
        default: return ERROR;
    }
}

void test() {
    /* p152 graph7.9
1 6 10 1
0 1 5
0 3 7
1 2 4
2 0 8
2 5 9
3 2 5
3 5 6
4 3 5
5 0 3
5 4 1
    */
    OLGraph G;
    CreateGraph(G);
}
int main() {
    test();
    return 0;
}