6-1 線性表元素的區(qū)間刪除

List Delete(List L, ElementType minD, ElementType maxD) {
    int i, p = 0;
    for (i = 0; i <= L->Last; i++) {
        if (L->Data[i] <= minD || L->Data[i] >= maxD) {
            L->Data[p++] = L->Data[i];
        }
    }
    L->Last = p - 1;
    return L;
}

6-2 有序表的插入

void ListInsertSort(SqList *L, DataType x) {
    int i;
    int temp = 1;

    for (i = 0; L->items[i] < x; i++) {
        temp++;
    }

    ListInsert(L, temp, x);
}

6-3 合并兩個(gè)有序數(shù)組

void merge(int *a, int m, int *b, int n, int *c) {
    int i, j, k;
    while (i < m && j < n) {
        if (a[i] < b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    }
    while (i < m) {
        c[k++] = a[i++];
    }
    while (j < n) {
        c[k++] = b[j++];
    }
}

6-4 順序表操作集

List MakeEmpty() {
    List list;
    list = (List) malloc(sizeof(struct LNode));
    list->Last = -1;
    return list;
}

Position Find(List L, ElementType X) {
    int i;
    for (i = 0; i < MAXSIZE; i++) {
        if (L->Data[i] == X)
            return i;
    }
    return ERROR;
}

bool Insert(List L, ElementType X, Position P) {
    int i;

    if (L->Last == MAXSIZE - 1) {
        printf("FULL");
        return false;
    }

    if (P < 0 || P > L->Last + 1) {
        printf("ILLEGAL POSITION");
        return false;
    }

    for (i = L->Last; i >= P; i--) {
        L->Data[i + 1] = L->Data[i];
    }
    L->Data[P] = X;
    L->Last++;
    return true;

}

bool Delete(List L, Position P) {
    int i;

    if (P < 0 || P > L->Last) {
        printf("POSITION %d EMPTY", P);
        return false;
    }

    for (i = P; i < L->Last; i++) {
        L->Data[i] = L->Data[i + 1];
    }
    L->Last--;

    return true;
}

6-5 遞增的整數(shù)序列鏈表的插入

List Insert(List L, ElementType X) {
    List p, s;
    p = L;
    s = (List) malloc(sizeof(struct Node));
    s->Data = X;

    while (p->Next && p->Next->Data < X) {
        p = p->Next;
    }
    s->Next = p->Next;
    p->Next = s;

    return L;
}

6-6 刪除單鏈表偶數(shù)節(jié)點(diǎn)

struct ListNode *createlist() {
    int m;
    struct ListNode *p, *s, *l;
    p = (struct ListNode *) malloc(sizeof(struct ListNode));

    scanf("%d", &m);
    if (m == -1)
        return NULL;
    p->data = m;
    p->next = NULL;
    s = p;

    while (1) {
        scanf("%d", &m);
        if (m == -1)
            break;
        l = (struct ListNode *) malloc(sizeof(struct ListNode));
        l->data = m;
        l->next = NULL;
        s->next = l;
        s = l;
    }
    return p;

}

struct ListNode *deleteeven(struct ListNode *head) {
    struct ListNode *p = NULL, *s = NULL;

    while (head && head->data % 2 == 0) {
        p = head;
        head = head->next;
        free(p);
    }
    if (head == NULL)
        return NULL;
    s = head;
    while (s->next) {
        if (s->next->data % 2 == 0)
            s->next = s->next->next;
        else
            s = s->next;
    }
    return head;
}

6-7 逆序數(shù)據(jù)建立鏈表

struct ListNode *createlist() {
    int m;
    struct ListNode *head, *p;
    head = (struct ListNode *) malloc(sizeof(struct ListNode));
    head->next = NULL;

    while (1) {
        scanf("%d", &m);
        if (m == -1)
            break;
        p = (struct ListNode *) malloc(sizeof(struct ListNode));
        p->next = head->next;
        p->data = m;
        head->next = p;
    }
    return head->next;
}

6-8 求鏈表的倒數(shù)第m個(gè)元素

ElementType Find(List L, int m) {
    int i;
    PtrToNode p, s;
    p = s = L;

    for (i = 0; i < m; i++) {
        p = p->Next;
        if (!p)
            return ERROR;
    }
    while (p) {
        s = s->Next;
        p = p->Next;
    }

    return s->Data;
}

6-9 兩個(gè)有序鏈表序列的合并

List Merge( List L1, List L2 )
{
    List pa,pb,pc;
    pa=L1->Next;
    pb=L2->Next;
    List L=(List)malloc(sizeof(List));
    pc=L;
    
    while(pa&&pb)
    {
        if(pa->Data>pb->Data)
        {
            pc->Next=pb;
            pb=pb->Next;
        }
        else{
            pc->Next=pa;
            pa=pa->Next;
        }
        pc=pc->Next;
    }
    
    if(pa)
        pc->Next = pa;
    if(pb)
        pc->Next = pb;
    L1->Next=NULL;
    L2->Next=NULL;
    
    return L;
}

6-10 二叉樹的遍歷

void InorderTraversal(BinTree BT) {//中序遍歷
    if (BT) {
        InorderTraversal(BT->Left);
        printf(" %c", BT->Data);
        InorderTraversal(BT->Right);
    }
}

void PreorderTraversal(BinTree BT) {//先序遍歷
    if (BT) {
        printf(" %c", BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }
}

void PostorderTraversal(BinTree BT) {//后序遍歷
    if (BT) {
        PostorderTraversal(BT->Left);
        PostorderTraversal(BT->Right);
        printf(" %c", BT->Data);
    }
}

void LevelorderTraversal(BinTree BT) {
    BinTree B[100];//結(jié)構(gòu)體數(shù)組
    BinTree T;
    int i = 0, j = 0;
    if (!BT)return;//樹為空，返回
    if (BT)//不為空
    {
        B[i++] = BT;//根節(jié)點(diǎn)入隊(duì)
        while (i != j)//隊(duì)列不空
        {
            T = B[j++];//出隊(duì)
            printf(" %c", T->Data);
            if (T->Left) B[i++] = T->Left;
            if (T->Right) B[i++] = T->Right;
        }
    }
} 

6-11 二叉樹的非遞歸遍歷

void InorderTraversal( BinTree BT ){//中序遍歷
    BinTree T=BT;
    Stack S =CreateStack();
    while(T||!IsEmpty(S)){
        while(T!=NULL){
            Push(S,T);
            T=T->Left;
        }
        T=Pop(S);
        printf(" %c",T->Data);
        T=T->Right;
    }
}
void PreorderTraversal( BinTree BT ){//先序遍歷
    BinTree T=BT;
    Stack S =CreateStack();
    while(T||!IsEmpty(S)){
        while(T!=NULL){
            Push(S,T);
            printf(" %c",T->Data);
            T=T->Left;
        }
        T=Pop(S);
        T=T->Right;
    }
}
void PostorderTraversal( BinTree BT ){//后序遍歷
    BinTree T=BT;
    Stack S =CreateStack();
    while(T||!IsEmpty(S)){
        while(T!=NULL){
            T->flag=0;
            Push(S,T);
            T=T->Left;
        }
        T=Peek(S);
        if(T->flag==0){
            T->flag++;
            T=T->Right;
        }
        else{
            T=Pop(S);
            printf(" %c",T->Data);
            T=NULL;
        }
    }
}

6-12 求二叉樹高度

int GetHeight(BinTree BT) {
    int lNum, rNum, Height;
    if (BT) {
        lNum = GetHeight(BT->Left);
        rNum = GetHeight(BT->Right);
        if (lNum > rNum)
            Height = lNum;
        else
            Height = rNum;
        return Height + 1;
    } else {
        return 0;
    }
}

6-13 鄰接矩陣存儲(chǔ)圖的深度優(yōu)先遍歷

void DFS(MGraph Graph, Vertex V, void (*Visit)(Vertex)) {
    Vertex i;
    Visit(V);
    Visited[V] = true;
    for (int i = 0; i < Graph->Nv; i++) {
        if (Graph->G[V][i] == 1 && !Visited[i]) {
            DFS(Graph, i, Visit);//進(jìn)行遞歸
        }
    }
}

6-14 鄰接表存儲(chǔ)圖的廣度優(yōu)先遍歷

void BFS(LGraph Graph, Vertex S, void (*Visit)(Vertex)) {
    Visited[S] = true;//標(biāo)記起始點(diǎn)
    Visit(S);
    int queue[1000], front = 0, rear = 0;
    queue[rear++] = S;//起始點(diǎn)入隊(duì)列
    PtrToAdjVNode temp;//temp就代表當(dāng)前點(diǎn)的鄰接點(diǎn)的下標(biāo)
    while (front < rear) {//隊(duì)伍不為空
        temp = Graph->G[queue[front++]].FirstEdge;
        while (temp) {
            int p = temp->AdjV;//把temp中的下標(biāo)提取出來(lái)
            if (!Visited[p]) {//如果p點(diǎn)沒(méi)有被標(biāo)記的話
                Visited[p] = true;
                Visit(p);
                queue[rear++] = p;//儲(chǔ)存在隊(duì)列中
            }
            temp = temp->Next;//指向下一個(gè)鄰接點(diǎn)
        }
    }
}

7-1 一元多項(xiàng)式的乘法與加法運(yùn)算

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct LNode *List;

struct LNode {
    ElementType coe;//系數(shù)
    ElementType exp;//指數(shù)
    List Next;//下一個(gè)節(jié)點(diǎn)
};

void Insert(List L, ElementType coe, ElementType exp);//插入
List Multi(List p1, List p2);//乘法
List Plus(List p1, List p2);//加法
int compare(List p1, List p2);//比較系數(shù)大小

int main() {
    List p1, p2;
    List p;
    int num1, num2, coe, exp;
    int i;
    p1 = (List) malloc(sizeof(struct LNode));
    p2 = (List) malloc(sizeof(struct LNode));
    p1->Next = NULL;
    p2->Next = NULL;

    scanf("%d", &num1);
    for (i = 0; i < num1; i++) {
        scanf("%d %d", &coe, &exp);
        Insert(p1, coe, exp);
    }
    scanf("%d", &num2);
    for (i = 0; i < num2; i++) {
        scanf("%d %d", &coe, &exp);
        Insert(p2, coe, exp);
    }
    //乘法運(yùn)算
    p = Multi(p1->Next, p2->Next);
    while (p) {
        if (p->Next != NULL) {
            printf("%d %d ", p->coe, p->exp);//非最后一個(gè)節(jié)點(diǎn),不換行打印,后接空格
        } else {
            printf("%d %d\n", p->coe, p->exp);//最后一個(gè)節(jié)點(diǎn),換行打印
        }
        p = p->Next;
    }
    //加法運(yùn)算
    p = Plus(p1->Next, p2->Next);
    if (p) {
        while (p) {
            if (p->Next != NULL) {
                printf("%d %d ", p->coe, p->exp);
            } else {
                printf("%d %d\n", p->coe, p->exp);
            }
            p = p->Next;
        }
    } else {//防止出現(xiàn)p1,p2抵消為零的情況
        printf("0 0\n");
    }
    return 0;
}

/**
 * 向鏈表中添加元素
 * @param L 需要添加的鏈表
 * @param coefficient 系數(shù)
 * @param exponent 指數(shù)
 */
void Insert(List L, ElementType coe, ElementType exp) {
    List s, p;
    p = L;

    while (p->Next)//找到最后一個(gè)節(jié)點(diǎn)
        p = p->Next;

    s = (List) malloc(sizeof(struct LNode));
    s->Next = NULL;
    s->coe = coe;
    s->exp = exp;

    p->Next = s;
}

/**
 * 兩個(gè)多項(xiàng)式相乘
 * @param p1 代表多項(xiàng)式1的鏈表
 * @param p2 代表多項(xiàng)式2的鏈表
 * @return p 相乘后生成的新鏈表
 */
List Multi(List p1, List p2) {
    List p, p1a, p2a, s;
    int flag = 1;
    p = (List) malloc(sizeof(struct LNode));
    p->Next = NULL;
    p1a = p1;

    while (p1a) {
        p2a = p2;//確保p1多項(xiàng)式中的每一項(xiàng)可以與p2多項(xiàng)式中的每一項(xiàng)分別相乘
        s = (List) malloc(sizeof(struct LNode));
        s->Next = NULL;

        while (p2a) {//與p2多項(xiàng)式中的每一項(xiàng)分別相乘
            Insert(s, p1a->coe * p2a->coe, p1a->exp + p2a->exp);
            p2a = p2a->Next;
        }
        s = s->Next;

        if (flag == 1) {
            p = p->Next;
            /*
             * 如果是p1第一項(xiàng)與p2每一項(xiàng)相乘,那么先將鏈表p向后移一位,將頭結(jié)點(diǎn)屏蔽
             * 因?yàn)槟J(rèn)初始化的P1頭結(jié)點(diǎn)有默認(rèn)的exp = 0,coe = 0,這兩個(gè)數(shù)據(jù)是多余的
             * 如果不后移,那么頭結(jié)點(diǎn)默認(rèn)的數(shù)值0將會(huì)一直尾隨整個(gè)乘法運(yùn)算,導(dǎo)致最后的結(jié)果后面多兩個(gè)0 0
             */
            flag = 0;

        }
        p = Plus(p, s);//相加,確保同類項(xiàng)合并
        p1a = p1a->Next;
        free(s);
    }

    return p;
}

/**
 * 比較兩多項(xiàng)式指數(shù)大小
 * @param p1 代表多項(xiàng)式1的鏈表
 * @param p2 代表多項(xiàng)式2的鏈表
 * @return 返回值為0時(shí)表示兩指數(shù)相同,可以進(jìn)行加法運(yùn)算
 */
int compare(List p1, List p2) {
    if (p1->exp > p2->exp)
        return 1;//p1指數(shù)大
    else if (p1->exp < p2->exp)
        return -1;//p1指數(shù)小
    else
        return 0;//指數(shù)相同
}

/**
 * 兩個(gè)多項(xiàng)式相加
 * @param p1 代表多項(xiàng)式1的鏈表
 * @param p2 代表多項(xiàng)式2的鏈表
 * @return p 相加后生成的新鏈表
 */
List Plus(List p1, List p2) {
    List p, p1a, p2a;
    int temp;
    p = (List) malloc(sizeof(struct LNode));
    p->Next = NULL;
    p1a = p1;
    p2a = p2;

    while (p1a && p2a) {
        temp = compare(p1a, p2a);
        //判斷指數(shù)大小,同指數(shù)才可以運(yùn)算
        switch (temp) {
            case 1:
                //當(dāng)前p1a的指數(shù)大,將當(dāng)前p1a的數(shù)據(jù)放入新鏈表
                Insert(p, p1a->coe, p1a->exp);
                p1a = p1a->Next;//p1a向后移動(dòng),p2a不改變
                break;
            case -1:
                //當(dāng)前p2a的指數(shù)大,將當(dāng)前p2a的數(shù)據(jù)放入新鏈表
                Insert(p, p2a->coe, p2a->exp);
                p2a = p2a->Next;//p2a向后移動(dòng),p1a不改變
                break;
            case 0:
                //指數(shù)相同,進(jìn)行運(yùn)算
                if ((p1a->coe + p2a->coe) == 0) {
                    //系數(shù)為0,數(shù)據(jù)不放入新鏈表,直接將p1a和p2a后移
                    p1a = p1a->Next;
                    p2a = p2a->Next;
                } else {
                    //數(shù)據(jù)放入新鏈表,p1a和p2a后移
                    Insert(p, p1a->coe + p2a->coe, p2a->exp);
                    p1a = p1a->Next;
                    p2a = p2a->Next;
                }
                break;
            default:
                break;
        }
    }
    while (p1a) {
        //p1a的項(xiàng)數(shù)多,將剩余項(xiàng)放入鏈表
        Insert(p, p1a->coe, p1a->exp);
        p1a = p1a->Next;
    }
    while (p2a) {
        //p2a的項(xiàng)數(shù)多,將剩余項(xiàng)放入鏈表
        Insert(p, p2a->coe, p2a->exp);
        p2a = p2a->Next;
    }
    p = p->Next;
    return p;
}

7-2 符號(hào)配對(duì)

#include <stdio.h>
#include <stdlib.h>

#define Maxsize 105
typedef struct StackRecord *Stack;
struct StackRecord {
    int top;
    char *array;
};

Stack creat();//創(chuàng)建空棧
int cheekEmpty(Stack s);//判斷棧是否為空
void push(Stack s, char x);//添加新元素
void pop(Stack s);//刪除
char top(Stack s);//取出

char a[100];
char str[200];

int main() {
    int i, j = 0, flag = 0;
    char ch;
    Stack s = creat();

    while (gets(str)) {
        if (str[0] == '.' && !str[1])
            break;
        for( i=0; str[i]; i++){
            if(str[i]=='('||str[i]=='['||str[i]=='{'||str[i]==')'||str[i]=='}' ||str[i]==']')
                a[j++]=str[i];
            else if(str[i]=='/'&&str[i+1]=='*'){
                a[j++]='<';
                i++;
            }else if(str[i]=='*'&&str[i+1]=='/'){
                a[j++]='>';
                i++;
            }
        }
    }

    for (i = 0; i < j; i++) {
        if (a[i] == '(' || a[i] == '[' || a[i] == '{' || a[i] == '<') {
            push(s, a[i]);
        } else if (a[i] == ')') {
            if (s->top != -1 && top(s) == '(') {
                pop(s);
            } else {
                ch = a[i];
                flag = 1;
                break;
            }
        } else if (a[i] == ']') {
            if (s->top != -1 && top(s) == '[') pop(s);
            else {
                ch = a[i];
                flag = 1;
                break;
            }
        } else if (a[i] == '}') {
            if (s->top != -1 && top(s) == '{') pop(s);
            else {
                ch = a[i];
                flag = 1;
                break;
            }
        } else if (a[i] == '>') {
            if (s->top != -1 && top(s) == '<') pop(s);
            else {
                ch = a[i];
                flag = 1;
                break;
            }
        }
    }

    if (!flag && cheekEmpty(s)) {
        printf("YES\n");
    } else {
        printf("NO\n");
        if (!cheekEmpty(s)) {
            if (top(s) == '<') printf("/*-?\n");
            else printf("%c-?\n", top(s));
        } else {
            if (ch == '>') printf("?-*/\n");
            else printf("?-%c\n", ch);
        }
    }

    return 0;
}

/**
 * 創(chuàng)建新棧
 * @return
 */
Stack creat() {
    Stack s = (Stack) malloc(sizeof(struct StackRecord));
    s->top = -1;
    s->array = (char *) malloc(sizeof(char) * Maxsize);
    return s;
}

/**
 * 判斷是否為空棧
 * @param s
 * @return
 */
int cheekEmpty(Stack s) {
    if (s->top == -1)
        return 1;
    else
        return 0;
}

/**
 *添加元素
 * @param s
 * @param x
 */
void push(Stack s, char x) {
    s->array[++(s->top)] = x;
}

/**
 *刪除
 * @param s
 */
void pop(Stack s) {
    s->top--;
}

/**
 *取出
 * @param s
 */
char top(Stack s) {
    return s->array[s->top];
}

7-3 銀行業(yè)務(wù)隊(duì)列簡(jiǎn)單模擬

#include <stdio.h>

const int MAX = 1010;

int main() {

    int a[MAX], b[MAX], cnta, cntb;
    cnta = cntb = 0;
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int temp;
        scanf("%d", &temp);
        if (temp % 2) a[++cnta] = temp;
        else b[++cntb] = temp;
    }
    int flag = 0, x = 1, y = 1;
    while (x <= cnta || y <= cntb) {
        if (x <= cnta) {
            if (flag++) printf(" ");
            printf("%d", a[x++]);
        }
        if (x <= cnta) {
            if (flag++) printf(" ");
            printf("%d", a[x++]);
        }
        if (y <= cntb) {
            if (flag++) printf(" ");
            printf("%d", b[y++]);
        }
    }
    return 0;
}

7-4 順序存儲(chǔ)的二叉樹的最近的公共祖先問(wèn)題

#include <stdio.h>

int find(int i, int j);

int main() {
    int n, i, j, m;
    int a[1000];
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%d %d", &i, &j);

    if (a[i] == 0)//查錯(cuò)
    {
        printf("ERROR: T[%d] is NULL\n", i);
        return 0;
    }
    if (a[j] == 0)//查錯(cuò)
    {
        printf("ERROR: T[%d] is NULL\n", j);
        return 0;
    }
    m = find(i, j);
    printf("%d %d", m, a[m]);
    return 0;
}

/**
 * 查找公共祖先,二分查找
 * @param i 
 * @param j 
 * @return 
 */
int find(int i, int j) {
    if (i == j) {
        return i;
    } else if (i > j) {
        return find(i / 2, j);
    } else if (i < j) {
        return find(i, j / 2);
    }
}

7-5 修理牧場(chǎng)

#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;
typedef struct HuffmanTreeNode {
    ElemType data;  //哈夫曼樹中節(jié)點(diǎn)的權(quán)值
    struct HuffmanTreeNode *left;
    struct HuffmanTreeNode *right;
} HuffmanTreeNode, *HuffmanTree;

HuffmanTree createHuffmanTree(ElemType arr[], int N) {
    HuffmanTree treeArr[N];
    HuffmanTree tree, pRoot = NULL;

    for (int i = 0; i < N; i++) {  //初始化結(jié)構(gòu)體指針數(shù)組,數(shù)組中每一個(gè)元素為一個(gè)結(jié)構(gòu)體指針類型
        tree = (HuffmanTree) malloc(sizeof(HuffmanTreeNode));
        tree->data = arr[i];
        tree->left = tree->right = NULL;
        treeArr[i] = tree;
    }

    for (int i = 1; i < N; i++) {  //進(jìn)行 n-1 次循環(huán)建立哈夫曼樹

        //k1為當(dāng)前數(shù)組中第一個(gè)非空樹的索引，k2為第二個(gè)非空樹的索引
        int k1 = -1, k2 = 0;
        for (int j = 0; j < N; j++) {
            if (treeArr[j] != NULL && k1 == -1) {
                k1 = j;
                continue;
            }
            if (treeArr[j] != NULL) {
                k2 = j;
                break;
            }
        }
        //循環(huán)遍歷當(dāng)前數(shù)組，找出最小值索引k1,和次小值索引k2
        for (int j = k2; j < N; j++) {
            if (treeArr[j] != NULL) {
                if (treeArr[j]->data < treeArr[k1]->data) {//最小
                    k2 = k1;
                    k1 = j;
                } else if (treeArr[j]->data < treeArr[k2]->data) {//次小
                    k2 = j;
                }
            }
        }
        //由最小權(quán)值樹和次最小權(quán)值樹建立一棵新樹,pRoot指向樹根結(jié)點(diǎn)
        pRoot = (HuffmanTree) malloc(sizeof(HuffmanTreeNode));
        pRoot->data = treeArr[k1]->data + treeArr[k2]->data;
        pRoot->left = treeArr[k1];
        pRoot->right = treeArr[k2];

        treeArr[k1] = pRoot; //將新生成的數(shù)加入到數(shù)組中k1的位置
        treeArr[k2] = NULL; //k2位置為空
    }

    return pRoot;
}

ElemType calculateWeightLength(HuffmanTree ptrTree, int len) {
    if (ptrTree == NULL) { //空樹返回0
        return 0;
    } else {
        if (ptrTree->left == NULL && ptrTree->right == NULL) { //訪問(wèn)到葉子節(jié)點(diǎn)
            return ptrTree->data * len;
        } else {
            return calculateWeightLength(ptrTree->left, len + 1) + calculateWeightLength(ptrTree->right, len + 1); //向下遞歸計(jì)算
        }
    }
}

int main() {
    ElemType arr[10001];
    int i = 0, N;
    scanf("%d", &N);

    while (i < N)
        scanf("%d", &arr[i++]);

    HuffmanTree pRoot = createHuffmanTree(arr, N);  //返回指向哈夫曼樹根節(jié)點(diǎn)的指針

    printf("%d", calculateWeightLength(pRoot, 0));

    return 0;
}

7-6 公路村村通

#include <stdio.h>
#include <stdlib.h>

int fa[1005];

typedef struct {
    int l;
    int r;
    int weight;
} Node;

Node p[3005];
int n, m, sum, cnt;

int cmp(const void *a, const void *b) {
    Node *p1 = (Node *) a;
    Node *p2 = (Node *) b;
    return p1->weight - p2->weight;
}

int Find(int x) {
    return (x == fa[x]) ? (x) : (fa[x] = Find(fa[x]));
}

void Union(int x, int y) {
    fa[Find(x)] = Find(y);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 0; i < m; i++)
        scanf("%d %d %d", &p[i].l, &p[i].r, &p[i].weight);
    qsort(p, m, sizeof(Node), cmp);
    for (int i = 0; i < m; i++) {
        if (Find(p[i].l) != Find(p[i].r)) {
            sum += p[i].weight;
            Union(p[i].l, p[i].r);
            cnt++;
        }
        if (cnt == n - 1)
            break;
    }
    if (cnt == n - 1)
        printf("%d\n", sum);
    else
        printf("-1\n");
    return 0;
}

7-7 暢通工程之最低成本建設(shè)問(wèn)題

#include <stdio.h>
#include <stdlib.h>

struct path {
    int a, b, c;
} p[3000];
int f[1001], n, m;

void init() {
    for (int i = 1; i <= n; i++) f[i] = i;
}

int getf(int k) {
    if (f[k] == k) return f[k];
    return f[k] = getf(f[k]);
}

int cmp(const void *a, const void *b) {
    return ((struct path *) a)->c - ((struct path *) b)->c;
}

int main() {
    scanf("%d%d", &n, &m);
    init();
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c);
    }
    qsort(p, m, sizeof(p[0]), cmp);
    int c = 0, ans = 0;
    for (int i = 0; i < m; i++) {
        if (getf(p[i].a) != getf(p[i].b)) {
            ans += p[i].c;
            c++;
            f[getf(p[i].a)] = getf(p[i].b);
        }
    }
    if (c < n - 1) printf("Impossible\n");
    else printf("%d\n", ans);
    return 0;
}

7-8 最短工期

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n, m, ans;
int mp[100][100];
int l[100], q[100], t[100];

int main() {
    int a, b, c, head = 0, tail = 0;
    scanf("%d%d", &n, &m);
    memset(mp, -1, sizeof(mp));
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        mp[a][b] = c;
        l[b]++;
    }
    for (int i = 0; i < n; i++) {
        if (!l[i]) {
            q[tail++] = i;
        }
    }
    while (head < tail) {
        int temp = q[head++];
        if (t[temp] > ans) ans = t[temp];
        for (int i = 0; i < n; i++) {
            if (mp[temp][i] != -1) {
                l[i]--;
                if (!l[i]) q[tail++] = i;
                if (t[i] < t[temp] + mp[temp][i]) {
                    t[i] = t[temp] + mp[temp][i];
                }
            }
        }
    }
    if (tail < n) printf("Impossible");
    else printf("%d", ans);
}

7-9 哈利·波特的考試

/**
 * 7-9 哈利·波特的考試
 *  最短路徑     迪杰斯特拉算法
 */
#include<stdio.h>
#include<string.h>

#define maxInt 2147483647

typedef struct {
    int arcs[102][102];
    int vexnum, arcnum;
} MGraph;

int final[102];//final[w]=1表示求得頂點(diǎn)v0至vw的最短路徑 
int D[102];  //記錄v0到vi的當(dāng)前最短路徑長(zhǎng)度
int P[102]; //記錄v0到vi的當(dāng)前最短路徑vi的前驅(qū)

int i, u, j, m, v, min, w, k, a, b, c, min1 = 999999, max = -991111, p = 0;

void Dijkstra(MGraph G, int v0) {
    for (v = 0; v < G.vexnum; v++)    //初始化數(shù)據(jù)
    {
        final[v] = 0;            //全部頂點(diǎn)初始化為未知最短路徑狀態(tài)
        D[v] = G.arcs[v0][v];// 將與v0點(diǎn)有連線的頂點(diǎn)加上權(quán)值
        P[v] = -1;                //初始化路徑數(shù)組P為-1
    }

    D[v0] = 0;  //v0至v0路徑為0
    final[v0] = 1;    // v0至v0不需要求路徑
    // 開始主循環(huán)，每次求得v0到某個(gè)v頂點(diǎn)的最短路徑
    for (v = 1; v < G.vexnum; v++) {
        min = maxInt;    // 當(dāng)前所知離v0頂點(diǎn)的最近距離
        for (w = 0; w < G.vexnum; w++) // 尋找離v0最近的頂點(diǎn)
        {
            if (!final[w] && D[w] < min) {
                k = w;
                min = D[w];    // w頂點(diǎn)離v0頂點(diǎn)更近
            }
        }
        final[k] = 1;    // 將目前找到的最近的頂點(diǎn)置為1
        for (w = 0; w < G.vexnum; w++) // 修正當(dāng)前最短路徑及距離
        {
            // 如果經(jīng)過(guò)v頂點(diǎn)的路徑比現(xiàn)在這條路徑的長(zhǎng)度短的話
            if (!final[w] && (min + G.arcs[k][w] < D[w])) { // 說(shuō)明找到了更短的路徑，修改D[w]和P[w]
                D[w] = min + G.arcs[k][w];  // 修改當(dāng)前路徑長(zhǎng)度
                P[w] = k;
            }
        }
    }
}

int main() {
    MGraph G;
    memset(final, 0, sizeof(final));
    memset(D, 0x3f3f3f3f, sizeof(D));
    memset(G.arcs, 0x3f3f3f3f, sizeof(G.arcs));   //鄰接矩陣一定要初始化
    scanf("%d %d", &G.vexnum, &m);
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        G.arcs[a - 1][b - 1] = c;
        G.arcs[b - 1][a - 1] = c;
    }
    for (u = 0; u < G.vexnum; u++) {
        max = -9999999;
        Dijkstra(G, u);
        for (j = 0; j < G.vexnum; j++) {
            if (D[j] > max)
                max = D[j];
        }
        if (max < min1) {
            min1 = max;
            p = u + 1;
        }

    }
    if (p == 0)
        printf("0");
    else
        printf("%d %d\n", p, min1);
    return 0;
}

7-10 旅游規(guī)劃

/**
 * 7-10 旅游規(guī)劃
 *  最短路徑  弗洛伊德算法
 */

#include<stdio.h>

#define MAXN 500
#define ERROR -1
#define Infinite 65534

int N, M, S, D;//城市的個(gè)數(shù) 高速公路的條數(shù) 出發(fā)地 目的地
int Dist[MAXN][MAXN], Cost[MAXN][MAXN];//距離與花費(fèi)矩陣
int dist[MAXN], cost[MAXN], visit[MAXN];//最短距離與花費(fèi) 標(biāo)記數(shù)組

void Inicialization(void);

void FindTheWay(void);

int FindMinWay(void);

int main() {
    scanf("%d %d %d %d", &N, &M, &S, &D);//城市的個(gè)數(shù) 高速公路的條數(shù) 出發(fā)地 目的地
    Inicialization();//初始化
    FindTheWay();
    printf("%d %d", dist[D], cost[D]);
    return 0;
}

void Inicialization(void) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            Dist[i][j] = Cost[i][j] = Infinite;//矩陣初始化為無(wú)限值

    int v1, v2, d, c;
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d %d", &v1, &v2, &d, &c);
        Dist[v1][v2] = Dist[v2][v1] = d;//輸入距離路徑
        Cost[v1][v2] = Cost[v2][v1] = c;//輸入花費(fèi)路徑
    }

    for (int i = 0; i < N; i++)
        dist[i] = cost[i] = Infinite;//矩陣初始化為無(wú)限值
}

void FindTheWay(void) {
    dist[S] = cost[S] = 0;//出發(fā)地為0
    visit[S] = 1;//出發(fā)地訪問(wèn)標(biāo)記
    int v;
    for (int i = 0; i < N; i++)//記錄出發(fā)地直達(dá)的路徑
        if (!visit[i] && Dist[S][i] < Infinite) //如果沒(méi)訪問(wèn) 且有路徑
        {
            dist[i] = Dist[S][i];
            cost[i] = Cost[S][i];
        }
    while (1) {
        v = FindMinWay();//找出最短出發(fā)地直達(dá)且未訪問(wèn)的城市
        if (v == ERROR) break;
        visit[v] = 1;//找出城市的訪問(wèn)標(biāo)記

        for (int i = 0; i < N; i++)//循環(huán)每個(gè)城市
            if (!visit[i] && Dist[v][i] < Infinite)//如果未訪問(wèn)且有路徑
                if ((dist[v] + Dist[v][i] < dist[i]) ||
                    (dist[v] + Dist[v][i] == dist[i] && cost[v] + Cost[v][i] < cost[i])) {//如果從先到該城市再到另一城市距離小于直接到另一城市
                    //或者從先到該城市再到另一城市距離等于直接到另一城市，且花費(fèi)少
                    dist[i] = dist[v] + Dist[v][i];//更新最短路徑
                    cost[i] = cost[v] + Cost[v][i];
                }
    }
}

int FindMinWay(void) {
    int min = Infinite;
    int temp;

    for (int i = 0; i < N; i++)//循環(huán)每個(gè)城市 找出最短的路徑
        if (!visit[i] && dist[i] < min) {
            min = dist[i];
            temp = i;
        }
    if (min == Infinite) return ERROR;
    return temp;
}

7-11 QQ帳戶的申請(qǐng)與登陸

/**
 * 7-11 QQ帳戶的申請(qǐng)與登陸
 *  哈希表  分離鏈接法
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

/*賬號(hào)與密碼最大長(zhǎng)度的定義
它們的最大長(zhǎng)度需要比題目所給的大一位
這是因?yàn)檫€需要一個(gè)位置來(lái)儲(chǔ)存'\0'來(lái)判斷字符串的結(jié)尾*/
#define Max_Password_Len 17
#define Max_Account_Len 11
#define MaxTableSize 1000000

/*各種狀態(tài)的定義
最好用正數(shù)表示成功的狀態(tài)
用負(fù)數(shù)或0表示失敗的狀態(tài)
這樣會(huì)讓強(qiáng)迫癥看了舒服一點(diǎn)*/
#define ERROR_WrongPW   -2
#define ERROR_Exist     -1
#define ERROR_NOTExist  0
#define New_OK          1
#define Login_OK        2

typedef char AccountType[Max_Account_Len];//賬號(hào)類型定義
typedef char PasswordType[Max_Password_Len];//密碼類型定義
typedef int Index;
typedef enum {
    New, Log
} Pattern;//兩種模式，新建賬號(hào)與登入賬號(hào)

typedef struct {
    AccountType Account;
    PasswordType Password;
} ElemType;//數(shù)據(jù)類型的定義，每個(gè)對(duì)應(yīng)一個(gè)用戶，內(nèi)含用戶的賬號(hào)和密碼

//鏈表指針的定義
typedef struct LNode *PtrToLNode;
//鏈表結(jié)點(diǎn)的定義
typedef struct LNode {
    PtrToLNode Next;
    ElemType Data;
} LNode;
typedef PtrToLNode List;//鏈表的定義
typedef PtrToLNode Position;//哈希表中結(jié)點(diǎn)位置的定義

//哈希表的定義
typedef struct TblNode *HashTable;
typedef struct TblNode {
    int TableSize;//哈希表的大小
    List Heads;//儲(chǔ)存各個(gè)列表頭節(jié)點(diǎn)的數(shù)組
} TblNode;

int NextPrime(int N)//返回N的下一個(gè)素?cái)?shù)
{
    int i, P;
    P = N % 2 ? N + 2 : N + 1;
    //P為N之后的第一個(gè)奇數(shù)
    while (P < MaxTableSize) {
        for (i = (int) sqrt(P); i > 2; i--)//因?yàn)橹豢紤]奇數(shù)，所以i為2時(shí)就結(jié)束了
            if (P % i == 0)
                break;
        if (i == 2)
            break;//i為2說(shuō)明P為素?cái)?shù)
        else
            P += 2;//i!=2說(shuō)明P不是素?cái)?shù)，則P指向下一個(gè)奇數(shù)
    }
    return P;
}

int Hash(int Key, int TableSize) {//返回Key值相對(duì)應(yīng)的哈希值，即其在哈希表中的儲(chǔ)存下標(biāo)
    return Key % TableSize;
}

HashTable CreateTable(int TableSize) {    //構(gòu)造空的哈希表
    HashTable H;
    int i;
    H = (HashTable) malloc(sizeof(TblNode));
    H->TableSize = NextPrime(TableSize);
    H->Heads = (List) malloc(sizeof(LNode) * H->TableSize);
    for (i = 0; i < H->TableSize; i++) {
        H->Heads[i].Data.Account[0] = '\0';
        H->Heads[i].Data.Password[0] = '\0';
        H->Heads[i].Next = NULL;
    }
    return H;
}

Position Find(HashTable H, ElemType Key) {
    Position Pos;
    Index p;
    if (strlen(Key.Account) > 5) //賬號(hào)大于5位時(shí)取最后5位
        p = Hash(atoi(Key.Account +
                      strlen(Key.Account) - 5), H->TableSize);
    else//賬號(hào)不大于5位則等于它本身
        p = Hash(atoi(Key.Account), H->TableSize);
    Pos = H->Heads[p].Next;
    while (Pos && strcmp(Key.Account, Pos->Data.Account))
        Pos = Pos->Next;
    return Pos;//Pos指向用戶數(shù)據(jù)的位置，沒(méi)有注冊(cè)就返回NULL
}

int NewOrLog(HashTable H, ElemType Key, Pattern P) {    //返回狀態(tài)參數(shù)
    Position Pos, NewPos;
    Index p;
    Pos = Find(H, Key);
    switch (P) {
        case Log:
            if (Pos == NULL)
                return ERROR_NOTExist;//登陸時(shí)不存在賬號(hào)
            else if (strcmp(Pos->Data.Password, Key.Password) ||
                     (strlen(Key.Password) > 16 || strlen(Key.Password) < 6))
                return ERROR_WrongPW; //密碼錯(cuò)誤或格式錯(cuò)誤
            else
                return Login_OK;//賬號(hào)和密碼均正確，可以登錄
        case New:
            if (Pos != NULL)
                return ERROR_Exist; //新建賬號(hào)時(shí)發(fā)現(xiàn)已經(jīng)存在這樣的賬號(hào)了
            else {
                NewPos = (Position) malloc(sizeof(LNode));
                strcpy(NewPos->Data.Account, Key.Account);
                strcpy(NewPos->Data.Password, Key.Password);
                if (strlen(Key.Account) > 5)
                    p = Hash(atoi(Key.Account +
                                  strlen(Key.Account) - 5), H->TableSize);
                else
                    p = Hash(atoi(Key.Account), H->TableSize);
                NewPos->Next = H->Heads[p].Next;
                H->Heads[p].Next = NewPos;
                return New_OK; //插入新值并返回插入成功
            }
    }
}

void DestroyTable(HashTable H) {    //銷毀哈希表
    PtrToLNode p, q;
    int i;
    for (i = 0; i < H->TableSize; i++) {
        q = H->Heads[i].Next;
        while (q) {
            p = q->Next;
            free(q);
            q = p;
        }
    }
    free(H);
}

int main(void) {
    int N, i;
    ElemType Key;
    char Input;
    Pattern P;
    HashTable H;
    scanf("%d", &N);
    H = CreateTable(2 * N);
    for (i = 0; i < N; i++) {
        scanf("\n%c %s %s", &Input, Key.Account, Key.Password);
        P = (Input == 'L') ? Log : New;
        switch (NewOrLog(H, Key, P)) {//最后根據(jù)不同返回值輸出對(duì)應(yīng)狀態(tài)即可
            case ERROR_Exist:
                printf("ERROR: Exist\n");
                break;
            case ERROR_NOTExist:
                printf("ERROR: Not Exist\n");
                break;
            case ERROR_WrongPW:
                printf("ERROR: Wrong PW\n");
                break;
            case Login_OK:
                printf("Login: OK\n");
                break;
            case New_OK:
                printf("New: OK\n");
                break;
        }
    }
    DestroyTable(H);
    return 0;
}

7-12 人以群分

/**
 * 7-12 人以群分
 *  排序
 */

#include <stdio.h>
#include <stdlib.h>

int comfunc(const void *elem1, const void *elem2);

void sort_character(int *p, int n);

int main() {
    int n, i;
    int a[100001];

    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    qsort(a, n, sizeof(int), comfunc);
    sort_character(a, n);

    return 0;
}

int comfunc(const void *elem1, const void *elem2) {
    int *p1 = (int *) elem1;
    int *p2 = (int *) elem2;

    return *p1 - *p2;
}

void sort_character(int *p, int n) {
    int i, j, n1, n2, sum1, sum2, dif, dif1, dif2;

    sum1 = sum2 = 0;
    dif = dif1 = dif2 = 0;
    if (n % 2 == 0) {
        n1 = n2 = n / 2;
        for (i = 0; i < n1; i++)
            sum1 += p[i];
        for (i = n1; i < n; i++)
            sum2 += p[i];
        dif = abs(sum2 - sum1);
    } else {
        n1 = n2 = n / 2;
        for (i = 0; i < n1; i++)
            sum1 += p[i];
        for (i = n / 2 + 1; i < n; i++)
            sum2 += p[i];
        dif1 = abs(sum1 + p[n1] - sum2);
        dif2 = abs(sum2 + p[n2] - sum1);
        dif = (dif1 > dif2) ? dif1 : dif2;
        if (dif1 > dif2)
            n1++;
        else
            n2++;
    }
    printf("Outgoing #: %d\n", n2);
    printf("Introverted #: %d\n", n1);
    printf("Diff = %d\n", dif);

}

7-13 尋找大富翁

/**
 * 7-13 尋找大富翁
 *  堆排序和選擇排序
 */

#include <stdio.h>   //堆排序；  注意:此算法中，下標(biāo)從1開始

#define max 1000010
int num[max];

void sift(int *num, int low, int high)  //將下標(biāo)為low位置上的點(diǎn)調(diào)到適當(dāng)位置
{
    int i, j, temp;
    i = low;
    j = 2 * i;   //num[j]是num[i]的左孩子結(jié)點(diǎn)；
    temp = num[i];  //待調(diào)整的結(jié)點(diǎn)
    while (j <= high) {
        if (j < high && num[j] < num[j + 1])   //如果右孩子比較大，則把j指向右孩子，j變?yōu)?*i+1；
            ++j;
        if (temp < num[j]) {
            num[i] = num[j];    //將num[j]調(diào)整到雙親結(jié)點(diǎn)的位置上；
            i = j;   //修改i和j的值，以便繼續(xù)向下調(diào)整；
            j = i * 2;
        } else break;     //調(diào)整結(jié)束；
    }
    num[i] = temp;   //被調(diào)整的結(jié)點(diǎn)放入最終位置
}

int main() {
    int n, m, i, temp, count = 0;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++)
        scanf("%d", &num[i]);
    if (n < m) m = n;   //注意，有一個(gè)測(cè)試點(diǎn)是n小于m的情況，這時(shí)，只用排前n個(gè);
    for (i = n / 2; i >= 1; i--)  //所有結(jié)點(diǎn)建立初始堆
        sift(num, i, n);
    for (i = n; i >= 2; i--)   //進(jìn)行n-1次循環(huán)，完成堆排序
    {
        /*以下3句換出了根節(jié)點(diǎn)中的關(guān)鍵字，將其放入最終位置*/
        temp = num[1];
        num[1] = num[i];
        num[i] = temp;
        count++;
        if (count == 1)
            printf("%d", num[i]);
        else
            printf(" %d", num[i]);
        if (count == m) break;  //打印前m個(gè)；
        sift(num, 1, i - 1);    //減少了1個(gè)關(guān)鍵字的無(wú)序序列，繼續(xù)調(diào)整。
    }
    if (m == n) printf(" %d", num[1]);  //當(dāng)n<m的特殊情況下，上面只打印了n~2，還有最后一個(gè)下標(biāo)為1的沒(méi)有打印，故再打印一個(gè)。
    return 0;
}

7-14 PAT排名匯總

/**
 * 7-14 PAT排名匯總
 *  快速排序
 */
#include <stdio.h>
#include <string.h>

struct stu {
    char id[14];                //考號(hào)
    int score;                  //分?jǐn)?shù)
    int kc;                     //考場(chǎng)
};
struct stu a[30000];

int bigger(const char *s1, const char *s2) {
    for (int i = 0; i < 13; i++)
        if (s1[i] > s2[i])
            return 1;
        else if (s1[i] < s2[i])
            return 0;
    return 1;
}

void qsort(int l, int r) {
    if (l >= r)
        return;

    int i = l;
    int j = r;

    struct stu t = a[l];
    while (i != j) {
        while (i < j && (a[j].score < t.score || a[j].score == t.score && bigger(a[j].id, t.id)))
            j--;
        while (i < j && (a[i].score > t.score || a[i].score == t.score && bigger(t.id, a[i].id)))
            i++;
        if (i < j) {
            struct stu s = a[i];
            a[i] = a[j];
            a[j] = s;
        }
    }
    a[l] = a[i];
    a[i] = t;

    qsort(l, i - 1);
    qsort(i + 1, r);

    return;
}

void Copy(int *b2, int *b1, int n) {
    for (int i = 1; i <= n; i++)
        b2[i] = b1[i];
}

int main() {
    int n, j, i, top = 0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        int k;
        scanf("%d", &k);
        for (j = 0; j < k; j++) {
            char id[14];
            int score;
            scanf("%s %d", id, &score);
            a[top].score = score;
            a[top].kc = i;
            strcpy(a[top].id, id);
            top++;
        }
    }
    qsort(0, top - 1);

    int levall = 1, b1[n + 1], b2[n + 1], score = a[0].score;

    for (i = 1; i <= n; i++)
        b1[i] = 1, b2[i] = 1;
    printf("%d\n", top);
    printf("%s %d %d %d\n", a[0].id, 1, a[0].kc, 1);
    int llevall = 1;            //上一個(gè)總排名
    levall = 2;                   //總排名

    Copy(b2, b1, n);
    b1[a[0].kc]++;
    for (i = 1; i < top; i++) {
        if (a[i].score == a[i - 1].score) {
            printf("%s %d %d %d\n", a[i].id, llevall, a[i].kc, b2[a[i].kc]);
            levall++;
            b1[a[i].kc]++;
        } else {
            printf("%s %d %d %d\n", a[i].id, levall, a[i].kc, b1[a[i].kc]);
            llevall = levall;
            levall++;

            Copy(b2, b1, n);
            b1[a[i].kc]++;                    //考場(chǎng)的排名
        }
    }
    return 0;
}

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-499221.html

到了這里，關(guān)于鄭州輕工業(yè)大學(xué)2022-2023（2）數(shù)據(jù)結(jié)構(gòu)題目集（精簡(jiǎn)版）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！