目錄
6-1 線性表元素的區(qū)間刪除 ? ????????????????????????????????6-2 有序表的插入
6-3 合并兩個(gè)有序數(shù)組 ? ???????????????????????????????????????6-4 順序表操作集
6-5 遞增的整數(shù)序列鏈表的插入 ? ?????????????????????????6-6 刪除單鏈表偶數(shù)節(jié)點(diǎn) ?
6-7 逆序數(shù)據(jù)建立鏈表 ? ????????????????????????????????????6-8 求鏈表的倒數(shù)第m個(gè)元素 ?
6-9 兩個(gè)有序鏈表序列的合并? ? ? ? ? ? ? ? ? ? ? ? ? ? 6-10二叉樹(shù)的遍歷
6-11 二叉樹(shù)的非遞歸遍歷? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?6-12 求二叉樹(shù)高度
6-13 鄰接矩陣存儲(chǔ)圖的深度優(yōu)先遍歷? ? ? ? ? ? ? ??6-14 鄰接表存儲(chǔ)圖的廣度優(yōu)先遍歷
7-1 一元多項(xiàng)式的乘法與加法運(yùn)算 ? ??????????????????7-2 符號(hào)配對(duì)? ?
7-3 銀行業(yè)務(wù)隊(duì)列簡(jiǎn)單模擬? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 7-4 順序存儲(chǔ)的二叉樹(shù)的最近的公共祖先問(wèn)題?
7-5 修理牧場(chǎng)????????????????????????????????????????????????????????7-6 公路村村通
7-7 暢通工程之最低成本建設(shè)問(wèn)題????????????????????????7-8 最短工期
7-9 哈利·波特的考試?????????????????????????????????????????????7-10 旅游規(guī)劃
7-11 QQ帳戶的申請(qǐng)與登陸???????????????????????????????????7-12 人以群分
7-13 尋找大富翁???????????????????????????????????????????????????7-14 PAT排名匯總
精簡(jiǎn)版：鄭州輕工業(yè)大學(xué)2022-2023（2）數(shù)據(jù)結(jié)構(gòu)題目集（精簡(jiǎn)版）
6-1 線性表元素的區(qū)間刪
給定一個(gè)順序存儲(chǔ)的線性表，請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)刪除所有值大于min而且小于max的元素。刪除后表中剩余元素保持順序存儲(chǔ)，并且相對(duì)位置不能改變。
函數(shù)接口定義：
List Delete( List L, ElementType minD, ElementType maxD );
其中List結(jié)構(gòu)定義如下：
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存線性表中最后一個(gè)元素在數(shù)組中的位置 */
};
L是用戶傳入的一個(gè)線性表，其中ElementType元素可以通過(guò)>、==、<進(jìn)行比較；minD和maxD分別為待刪除元素的值域的下、上界。函數(shù)Delete應(yīng)將Data[]中所有值大于minD而且小于maxD的元素刪除，同時(shí)保證表中剩余元素保持順序存儲(chǔ)，并且相對(duì)位置不變，最后返回刪除后的表。
裁判測(cè)試程序樣例：
#include <stdio.h>
#define MAXSIZE 20
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存線性表中最后一個(gè)元素的位置 */
};
List ReadInput(); /* 裁判實(shí)現(xiàn)，細(xì)節(jié)不表。元素從下標(biāo)0開(kāi)始存儲(chǔ) */
void PrintList( List L ); /* 裁判實(shí)現(xiàn)，細(xì)節(jié)不表 */
List Delete( List L, ElementType minD, ElementType maxD );
int main()
{
List L;
ElementType minD, maxD;
int i;
L = ReadInput();
scanf("%d %d", &minD, &maxD);
L = Delete( L, minD, maxD );
PrintList( L );
return 0;
}
/* 你的代碼將被嵌在這里 */
輸入樣例：
10
4 -8 2 12 1 5 9 3 3 10
0 4
輸出樣例：
4 -8 12 5 9 10
代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????200 ms
內(nèi)存限制????????????????????????????????????????64 MB
參考代碼：?
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 有序表的插入
設(shè)順序表中的數(shù)據(jù)元素是按值非遞減有序排列的，試編寫(xiě)一算法，將x插入到順序表的適當(dāng)位置上，以保持順序表的有序性。
函數(shù)接口定義：
void ListInsertSort(SqList *L, DataType x);
其中?L?和?x?都是用戶傳入的參數(shù)。?L?表示順序表，?x?是要插入的元素。
裁判測(cè)試程序樣例：
#include"stdio.h"
#define LISTSIZE 100
typedef int DataType;
typedef struct{
DataType items[LISTSIZE];
int length;
}SqList;
/* 本題要求函數(shù) */
void ListInsertSort(SqList *L, DataType x);
int InitList(SqList *L)
{/*L為指向順序表的指針*/
L->length=0;
return 1;
}
int ListLength(SqList L)
{/*L為順序表*/
return L.length;
}
int ListInsert(SqList *L,int pos,DataType item)
{/*L為指向順序表的指針,pos為插入位置,item為待插入的數(shù)據(jù)元素*/
int i;
if(L->length>=LISTSIZE){
printf("順序表已滿，無(wú)法進(jìn)行插入操作！");return 0;}
if(pos<=0 || pos>L->length+1){
printf("插入位置不合法，其取值范圍應(yīng)該是[1,length+1]");
return 0; }
for(i=L->length-1; i>=pos-1; i--) /*移動(dòng)數(shù)據(jù)元素*/
L->items[i+1]=L->items[i];
L->items[pos-1]=item; /*插入*/
L->length++; /*表長(zhǎng)增一*/
return 1; }
int TraverseList(SqList L)
{/*L為順序表*/
int i;
for(i=0;i<L.length;i++) printf("%d ",L.items[i]);
printf("\n");
return 1;
}
void main()
{
int i,input,x;
SqList L1; //定義順序表
InitList(&L1); //初始化建空表
for(i=0;;i++)
{
scanf("%d",&input);
if(input==-1)break;
ListInsert(&L1, i+1, input); //插入數(shù)據(jù)
}
scanf("%d",&x);
ListInsertSort(&L1, x); // 本題要求函數(shù)在主函數(shù)中的調(diào)用
TraverseList(L1); //遍歷
}
/* 請(qǐng)?jiān)谶@里填寫(xiě)答案 */
輸入樣例：
在這里給出一組輸入。例如：
1 3 6 7 8 9 -1
3
輸出樣例：
在這里給出相應(yīng)的輸出。例如：
1 3 3 6 7 8 9 代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????200 ms
內(nèi)存限制????????????????????????????????????????64 MB
?參考代碼：
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ù)組
要求實(shí)現(xiàn)一個(gè)函數(shù)merge，將長(zhǎng)度為m的升序數(shù)組a和長(zhǎng)度為n的升序數(shù)組b合并到一個(gè)新的數(shù)組c，合并后的數(shù)組仍然按升序排列。
函數(shù)接口定義：
void printArray(int* arr, int arr_size); /* 打印數(shù)組,細(xì)節(jié)不表 */
void merge(int* a, int m, int* b, int n, int* c); /* 合并a和b為c */
其中a和b是按升序排列的數(shù)組，m和n分別為數(shù)組a、b的長(zhǎng)度；c為合并后的升序數(shù)組。
裁判測(cè)試程序樣例：
#include <stdio.h>
#include <stdlib.h>
void printArray(int* arr, int arr_size); /* 打印數(shù)組,細(xì)節(jié)不表 */
void merge(int* a, int m, int* b, int n, int* c); /* 合并a和b為c */
int main(int argc, char const *argv[])
{
int m, n, i;
int *a, *b, *c;
scanf("%d", &m);
a = (int*)malloc(m * sizeof(int));
for (i = 0; i < m; i++) {
scanf("%d", &a[i]);
}
scanf("%d", &n);
b = (int*)malloc(n * sizeof(int));
for (i = 0; i < n; i++) {
scanf("%d", &b[i]);
}
c = (int*)malloc((m + n) * sizeof(int));
merge(a, m, b, n, c);
printArray(c, m + n);
return 0;
}
/* 請(qǐng)?jiān)谶@里填寫(xiě)答案 */
輸入樣例：
輸入包含兩行。
第一行為有序數(shù)組a，其中第一個(gè)數(shù)為數(shù)組a的長(zhǎng)度m，緊接著m個(gè)整數(shù)。
第二行為有序數(shù)組b，其中第一個(gè)數(shù)為數(shù)組b的長(zhǎng)度n，緊接著n個(gè)整數(shù)。
7 1 2 14 25 33 73 84
11 5 6 17 27 68 68 74 79 80 85 87
輸出樣例：
輸出為合并后按升序排列的數(shù)組。
1 2 5 6 14 17 25 27 33 68 68 73 74 79 80 84 85 87代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????200 ms
內(nèi)存限制????????????????????????????????????????64 MB
參考答案：
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 順序表操作集
本題要求實(shí)現(xiàn)順序表的操作集。
函數(shù)接口定義：
List MakeEmpty();
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );
其中List結(jié)構(gòu)定義如下：
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存線性表中最后一個(gè)元素的位置 */
};
各個(gè)操作函數(shù)的定義為：
List MakeEmpty()：創(chuàng)建并返回一個(gè)空的線性表；
Position Find( List L, ElementType X )：返回線性表中X的位置。若找不到則返回ERROR；
bool Insert( List L, ElementType X, Position P )：將X插入在位置P并返回true。若空間已滿，則打印“FULL”并返回false；如果參數(shù)P指向非法位置，則打印“ILLEGAL POSITION”并返回false；
bool Delete( List L, Position P )：將位置P的元素刪除并返回true。若參數(shù)P指向非法位置，則打印“POSITION P EMPTY”（其中P是參數(shù)值）并返回false。裁判測(cè)試程序樣例：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
#define ERROR -1
typedef enum {false, true} bool;
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存線性表中最后一個(gè)元素的位置 */
};
List MakeEmpty();
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );
int main()
{
List L;
ElementType X;
Position P;
int N;
L = MakeEmpty();
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
if ( Insert(L, X, 0)==false )
printf(" Insertion Error: %d is not in.\n", X);
}
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
P = Find(L, X);
if ( P == ERROR )
printf("Finding Error: %d is not in.\n", X);
else
printf("%d is at position %d.\n", X, P);
}
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &P);
if ( Delete(L, P)==false )
printf(" Deletion Error.\n");
if ( Insert(L, 0, P)==false )
printf(" Insertion Error: 0 is not in.\n");
}
return 0;
}
/* 你的代碼將被嵌在這里 */
輸入樣例：
6
1 2 3 4 5 6
3
6 5 1
2
-1 6
輸出樣例：
FULL Insertion Error: 6 is not in.
Finding Error: 6 is not in.
5 is at position 0.
1 is at position 4.
POSITION -1 EMPTY Deletion Error.
FULL Insertion Error: 0 is not in.
POSITION 6 EMPTY Deletion Error.
FULL Insertion Error: 0 is not in.代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????200 ms
內(nèi)存限制????????????????????????????????????????64 MB
參考代碼：
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ù)序列鏈表的插入
本題要求實(shí)現(xiàn)一個(gè)函數(shù)，在遞增的整數(shù)序列鏈表（帶頭結(jié)點(diǎn)）中插入一個(gè)新整數(shù)，并保持該序列的有序性。
函數(shù)接口定義：
List Insert( List L, ElementType X );
其中List結(jié)構(gòu)定義如下：
typedef struct Node *PtrToNode;
struct Node {
ElementType Data; /* 存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù) */
PtrToNode Next; /* 指向下一個(gè)結(jié)點(diǎn)的指針 */
};
typedef PtrToNode List; /* 定義單鏈表類(lèi)型 */
L是給定的帶頭結(jié)點(diǎn)的單鏈表，其結(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)是遞增有序的；函數(shù)Insert要將X插入L，并保持該序列的有序性，返回插入后的鏈表頭指針。
裁判測(cè)試程序樣例：
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 細(xì)節(jié)在此不表 */
void Print( List L ); /* 細(xì)節(jié)在此不表 */
List Insert( List L, ElementType X );
int main()
{
List L;
ElementType X;
L = Read();
scanf("%d", &X);
L = Insert(L, X);
Print(L);
return 0;
}
/* 你的代碼將被嵌在這里 */
輸入樣例：
5
1 2 4 5 6
3
輸出樣例：
1 2 3 4 5 6 代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????200 ms
內(nèi)存限制????????????????????????????????????????64 MB
參考代碼：
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)
本題要求實(shí)現(xiàn)兩個(gè)函數(shù)，分別將讀入的數(shù)據(jù)存儲(chǔ)為單鏈表、將鏈表中偶數(shù)值的結(jié)點(diǎn)刪除。鏈表結(jié)點(diǎn)定義如下：
struct ListNode {
int data;
struct ListNode *next;
};
函數(shù)接口定義：
struct ListNode *createlist();
struct ListNode *deleteeven( struct ListNode *head );
函數(shù)createlist從標(biāo)準(zhǔn)輸入讀入一系列正整數(shù)，按照讀入順序建立單鏈表。當(dāng)讀到?1時(shí)表示輸入結(jié)束，函數(shù)應(yīng)返回指向單鏈表頭結(jié)點(diǎn)的指針。
函數(shù)deleteeven將單鏈表head中偶數(shù)值的結(jié)點(diǎn)刪除，返回結(jié)果鏈表的頭指針。
裁判測(cè)試程序樣例：
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *createlist();
struct ListNode *deleteeven( struct ListNode *head );
void printlist( struct ListNode *head )
{
struct ListNode *p = head;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main()
{
struct ListNode *head;
head = createlist();
head = deleteeven(head);
printlist(head);
return 0;
}
/* 你的代碼將被嵌在這里 */
輸入樣例：
1 2 2 3 4 5 6 7 -1
輸出樣例：
1 3 5 7 代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????200 ms
內(nèi)存限制????????????????????????????????????????64 MB
參考代碼:
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ù)建立鏈表
本題要求實(shí)現(xiàn)一個(gè)函數(shù)，按輸入數(shù)據(jù)的逆序建立一個(gè)鏈表。
函數(shù)接口定義：
struct ListNode *createlist();函數(shù)createlist利用scanf從輸入中獲取一系列正整數(shù)，當(dāng)讀到?1時(shí)表示輸入結(jié)束。按輸入數(shù)據(jù)的逆序建立一個(gè)鏈表，并返回鏈表頭指針。鏈表節(jié)點(diǎn)結(jié)構(gòu)定義如下：
struct ListNode {
int data;
struct ListNode *next;
};
裁判測(cè)試程序樣例：
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *createlist();
int main()
{
struct ListNode *p, *head = NULL;
head = createlist();
for ( p = head; p != NULL; p = p->next )
printf("%d ", p->data);
printf("\n");
return 0;
}
/* 你的代碼將被嵌在這里 */
輸入樣例：
1 2 3 4 5 6 7 -1
輸出樣例：
7 6 5 4 3 2 1 代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????200 ms
內(nèi)存限制????????????????????????????????????????64 MB
參考代碼:
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è)元素
請(qǐng)?jiān)O(shè)計(jì)時(shí)間和空間上都盡可能高效的算法，在不改變鏈表的前提下，求鏈?zhǔn)酱鎯?chǔ)的線性表的倒數(shù)第m（>0）個(gè)元素。
函數(shù)接口定義：
ElementType Find( List L, int m );
其中List結(jié)構(gòu)定義如下：
typedef struct Node *PtrToNode;
struct Node {
ElementType Data; /* 存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù) */
PtrToNode Next; /* 指向下一個(gè)結(jié)點(diǎn)的指針 */
};
typedef PtrToNode List; /* 定義單鏈表類(lèi)型 */
L是給定的帶頭結(jié)點(diǎn)的單鏈表；函數(shù)Find要將L的倒數(shù)第m個(gè)元素返回，并不改變?cè)湵?。如果這樣的元素不存在，則返回一個(gè)錯(cuò)誤標(biāo)志ERROR。
裁判測(cè)試程序樣例：
#include <stdio.h>
#include <stdlib.h>
#define ERROR -1
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 細(xì)節(jié)在此不表 */
void Print( List L ); /* 細(xì)節(jié)在此不表 */
ElementType Find( List L, int m );
int main()
{
List L;
int m;
L = Read();
scanf("%d", &m);
printf("%d\n", Find(L,m));
Print(L);
return 0;
}
/* 你的代碼將被嵌在這里 */
輸入樣例：
5
1 2 4 5 6
3
輸出樣例：
4
1 2 4 5 6 代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????200 ms
內(nèi)存限制????????????????????????????????????????64 MB
參考代碼:
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è)有序鏈表序列的合并
本題要求實(shí)現(xiàn)一個(gè)函數(shù)，將兩個(gè)鏈表表示的遞增整數(shù)序列合并為一個(gè)非遞減的整數(shù)序列。
函數(shù)接口定義：
List Merge( List L1, List L2 );其中List結(jié)構(gòu)定義如下：
typedef struct Node *PtrToNode;
struct Node {
ElementType Data; /* 存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù) */
PtrToNode Next; /* 指向下一個(gè)結(jié)點(diǎn)的指針 */
};
typedef PtrToNode List; /* 定義單鏈表類(lèi)型 */
L1和L2是給定的帶頭結(jié)點(diǎn)的單鏈表，其結(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)是遞增有序的；函數(shù)Merge要將L1和L2合并為一個(gè)非遞減的整數(shù)序列。應(yīng)直接使用原序列中的結(jié)點(diǎn)，返回歸并后的帶頭結(jié)點(diǎn)的鏈表頭指針。
裁判測(cè)試程序樣例：
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 細(xì)節(jié)在此不表 */
void Print( List L ); /* 細(xì)節(jié)在此不表；空鏈表將輸出NULL */
List Merge( List L1, List L2 );
int main()
{
List L1, L2, L;
L1 = Read();
L2 = Read();
L = Merge(L1, L2);
Print(L);
Print(L1);
Print(L2);
return 0;
}
/* 你的代碼將被嵌在這里 */
輸入樣例：
3
1 3 5
5
2 4 6 8 10
輸出樣例：
1 2 3 4 5 6 8 10
NULL
NULL代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????200 ms
內(nèi)存限制????????????????????????????????????????64 MB
參考代碼:
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 二叉樹(shù)的遍歷
本題要求給定二叉樹(shù)的4種遍歷。
函數(shù)接口定義：
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );
其中BinTree結(jié)構(gòu)定義如下：
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
要求4個(gè)函數(shù)分別按照訪問(wèn)順序打印出結(jié)點(diǎn)的內(nèi)容，格式為一個(gè)空格跟著一個(gè)字符。
裁判測(cè)試程序樣例：
#include <stdio.h>
#include <stdlib.h>
typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
BinTree CreatBinTree(); /* 實(shí)現(xiàn)細(xì)節(jié)忽略 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );
int main()
{
BinTree BT = CreatBinTree();
printf("Inorder:"); InorderTraversal(BT); printf("\n");
printf("Preorder:"); PreorderTraversal(BT); printf("\n");
printf("Postorder:"); PostorderTraversal(BT); printf("\n");
printf("Levelorder:"); LevelorderTraversal(BT); printf("\n");
return 0;
}
/* 你的代碼將被嵌在這里 */
輸出樣例（對(duì)于圖中給出的樹(shù)）：
Inorder: D B E F A G H C I
Preorder: A B D F E C G H I
Postorder: D E F B H G I C A
Levelorder: A B C D F G I E H代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????400 ms
內(nèi)存限制????????????????????????????????????????64 MB
?參考代碼:
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;//樹(shù)為空，返回
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 二叉樹(shù)的非遞歸遍歷
本題要求用非遞歸的方法實(shí)現(xiàn)對(duì)給定二叉樹(shù)的 3 種遍歷。
函數(shù)接口定義：
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
其中BinTree結(jié)構(gòu)定義如下：
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
int flag;
};
要求 3 個(gè)函數(shù)分別按照訪問(wèn)順序打印出結(jié)點(diǎn)的內(nèi)容，格式為一個(gè)空格跟著一個(gè)字符。
此外，裁判程序中給出了堆棧的全套操作，可以直接調(diào)用。
裁判測(cè)試程序樣例：
#include <stdio.h>
#include <stdlib.h>
typedef enum { false, true } bool;
typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
int flag;
};
/*------堆棧的定義-------*/
typedef Position SElementType;
typedef struct SNode *PtrToSNode;
struct SNode {
SElementType Data;
PtrToSNode Next;
};
typedef PtrToSNode Stack;
/* 裁判實(shí)現(xiàn)，細(xì)節(jié)不表 */
Stack CreateStack();
bool IsEmpty( Stack S );
bool Push( Stack S, SElementType X );
SElementType Pop( Stack S ); /* 刪除并僅返回S的棧頂元素 */
SElementType Peek( Stack S );/* 僅返回S的棧頂元素 */
/*----堆棧的定義結(jié)束-----*/
BinTree CreateBinTree(); /* 裁判實(shí)現(xiàn)，細(xì)節(jié)不表 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
int main()
{
BinTree BT = CreateBinTree();
printf("Inorder:"); InorderTraversal(BT); printf("\n");
printf("Preorder:"); PreorderTraversal(BT); printf("\n");
printf("Postorder:"); PostorderTraversal(BT); printf("\n");
return 0;
}
/* 你的代碼將被嵌在這里 */
輸入樣例：
輸出樣例：
Inorder: D B E F A G H C I
Preorder: A B D F E C G H I
Postorder: D E F B H G I C A代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????400 ms
內(nèi)存限制????????????????????????????????????????64 MB
?參考代碼:
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 求二叉樹(shù)高度
本題要求給定二叉樹(shù)的高度。
函數(shù)接口定義：
int GetHeight( BinTree BT );
其中BinTree結(jié)構(gòu)定義如下：
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
要求函數(shù)返回給定二叉樹(shù)BT的高度值。
裁判測(cè)試程序樣例：
#include <stdio.h>
#include <stdlib.h>
typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
BinTree CreatBinTree(); /* 實(shí)現(xiàn)細(xì)節(jié)忽略 */
int GetHeight( BinTree BT );
int main()
{
BinTree BT = CreatBinTree();
printf("%d\n", GetHeight(BT));
return 0;
}
/* 你的代碼將被嵌在這里 */
輸出樣例（對(duì)于圖中給出的樹(shù)）：
4代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????400 ms
內(nèi)存限制????????????????????????????????????????64 MB
?參考代碼:
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)先遍歷
試實(shí)現(xiàn)鄰接矩陣存儲(chǔ)圖的深度優(yōu)先遍歷。
函數(shù)接口定義：
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );其中 MGraph 是鄰接矩陣存儲(chǔ)的圖，定義如下?
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; /* 頂點(diǎn)數(shù) */
int Ne; /* 邊數(shù) */
WeightType G[MaxVertexNum][MaxVertexNum]; /* 鄰接矩陣 */
};
typedef PtrToGNode MGraph; /* 以鄰接矩陣存儲(chǔ)的圖類(lèi)型 */
函數(shù)DFS應(yīng)從第V個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖Graph，遍歷時(shí)用裁判定義的函數(shù)Visit訪問(wèn)每個(gè)頂點(diǎn)。當(dāng)訪問(wèn)鄰接點(diǎn)時(shí)，要求按序號(hào)遞增的順序。題目保證V是圖中的合法頂點(diǎn)。
裁判測(cè)試程序樣例：
#include <stdio.h>
typedef enum {false, true} bool;
#define MaxVertexNum 10 /* 最大頂點(diǎn)數(shù)設(shè)為10 */
#define INFINITY 65535 /* ∞設(shè)為雙字節(jié)無(wú)符號(hào)整數(shù)的最大值65535*/
typedef int Vertex; /* 用頂點(diǎn)下標(biāo)表示頂點(diǎn),為整型 */
typedef int WeightType; /* 邊的權(quán)值設(shè)為整型 */
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; /* 頂點(diǎn)數(shù) */
int Ne; /* 邊數(shù) */
WeightType G[MaxVertexNum][MaxVertexNum]; /* 鄰接矩陣 */
};
typedef PtrToGNode MGraph; /* 以鄰接矩陣存儲(chǔ)的圖類(lèi)型 */
bool Visited[MaxVertexNum]; /* 頂點(diǎn)的訪問(wèn)標(biāo)記 */
MGraph CreateGraph(); /* 創(chuàng)建圖并且將Visited初始化為false；裁判實(shí)現(xiàn)，細(xì)節(jié)不表 */
void Visit( Vertex V )
{
printf(" %d", V);
}
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );
int main()
{
MGraph G;
Vertex V;
G = CreateGraph();
scanf("%d", &V);
printf("DFS from %d:", V);
DFS(G, V, Visit);
return 0;
}
/* 你的代碼將被嵌在這里 */輸入樣例：給定圖如下
5
輸出樣例：
DFS from 5: 5 1 3 0 2 4 6
代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????400 ms
內(nèi)存限制????????????????????????????????????????64 MB
?參考代碼：
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ) {
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)先遍歷
試實(shí)現(xiàn)鄰接表存儲(chǔ)圖的廣度優(yōu)先遍歷。
函數(shù)接口定義：
void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) );其中LGraph是鄰接表存儲(chǔ)的圖，定義如下：
/* 鄰接點(diǎn)的定義 */
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex AdjV; /* 鄰接點(diǎn)下標(biāo) */
PtrToAdjVNode Next; /* 指向下一個(gè)鄰接點(diǎn)的指針 */
};
/* 頂點(diǎn)表頭結(jié)點(diǎn)的定義 */
typedef struct Vnode{
PtrToAdjVNode FirstEdge; /* 邊表頭指針 */
} AdjList[MaxVertexNum]; /* AdjList是鄰接表類(lèi)型 */
/* 圖結(jié)點(diǎn)的定義 */
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; /* 頂點(diǎn)數(shù) */
int Ne; /* 邊數(shù) */
AdjList G; /* 鄰接表 */
};
typedef PtrToGNode LGraph; /* 以鄰接表方式存儲(chǔ)的圖類(lèi)型 */
函數(shù)BFS應(yīng)從第S個(gè)頂點(diǎn)出發(fā)對(duì)鄰接表存儲(chǔ)的圖Graph進(jìn)行廣度優(yōu)先搜索，遍歷時(shí)用裁判定義的函數(shù)Visit訪問(wèn)每個(gè)頂點(diǎn)。當(dāng)訪問(wèn)鄰接點(diǎn)時(shí)，要求按鄰接表順序訪問(wèn)。題目保證S是圖中的合法頂點(diǎn)。
裁判測(cè)試程序樣例：
#include <stdio.h>
typedef enum {false, true} bool;
#define MaxVertexNum 10 /* 最大頂點(diǎn)數(shù)設(shè)為10 */
typedef int Vertex; /* 用頂點(diǎn)下標(biāo)表示頂點(diǎn),為整型 */
/* 鄰接點(diǎn)的定義 */
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex AdjV; /* 鄰接點(diǎn)下標(biāo) */
PtrToAdjVNode Next; /* 指向下一個(gè)鄰接點(diǎn)的指針 */
};
/* 頂點(diǎn)表頭結(jié)點(diǎn)的定義 */
typedef struct Vnode{
PtrToAdjVNode FirstEdge; /* 邊表頭指針 */
} AdjList[MaxVertexNum]; /* AdjList是鄰接表類(lèi)型 */
/* 圖結(jié)點(diǎn)的定義 */
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; /* 頂點(diǎn)數(shù) */
int Ne; /* 邊數(shù) */
AdjList G; /* 鄰接表 */
};
typedef PtrToGNode LGraph; /* 以鄰接表方式存儲(chǔ)的圖類(lèi)型 */
bool Visited[MaxVertexNum]; /* 頂點(diǎn)的訪問(wèn)標(biāo)記 */
LGraph CreateGraph(); /* 創(chuàng)建圖并且將Visited初始化為false；裁判實(shí)現(xiàn)，細(xì)節(jié)不表 */
void Visit( Vertex V )
{
printf(" %d", V);
}
void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) );
int main()
{
LGraph G;
Vertex S;
G = CreateGraph();
scanf("%d", &S);
printf("BFS from %d:", S);
BFS(G, S, Visit);
return 0;
}
/* 你的代碼將被嵌在這里 */輸入樣例：給定圖如下
2
輸出樣例：
BFS from 2: 2 0 3 5 4 1 6
代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????400 ms
內(nèi)存限制????????????????????????????????????????64 MB
?參考代碼：
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)算
設(shè)計(jì)函數(shù)分別求兩個(gè)一元多項(xiàng)式的乘積與和。
輸入格式:
輸入分2行，每行分別先給出多項(xiàng)式非零項(xiàng)的個(gè)數(shù)，再以指數(shù)遞降方式輸入一個(gè)多項(xiàng)式非零項(xiàng)系數(shù)和指數(shù)（絕對(duì)值均為不超過(guò)1000的整數(shù)）。數(shù)字間以空格分隔。
輸出格式:
輸出分2行，分別以指數(shù)遞降方式輸出乘積多項(xiàng)式以及和多項(xiàng)式非零項(xiàng)的系數(shù)和指數(shù)。數(shù)字間以空格分隔，但結(jié)尾不能有多余空格。零多項(xiàng)式應(yīng)輸出0 0。
輸入樣例:
4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
輸出樣例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????200 ms
內(nèi)存限制????????????????????????????????????????64 MB
參考代碼:
#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);//相加,確保同類(lèi)項(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ì)
請(qǐng)編寫(xiě)程序檢查C語(yǔ)言源程序中下列符號(hào)是否配對(duì)：/*與*/、(與)、[與]、{與}。
輸入格式:
輸入為一個(gè)C語(yǔ)言源程序。當(dāng)讀到某一行中只有一個(gè)句點(diǎn).和一個(gè)回車(chē)的時(shí)候，標(biāo)志著輸入結(jié)束。程序中需要檢查配對(duì)的符號(hào)不超過(guò)100個(gè)。
輸出格式:
首先，如果所有符號(hào)配對(duì)正確，則在第一行中輸出YES，否則輸出NO。然后在第二行中指出第一個(gè)不配對(duì)的符號(hào)：如果缺少左符號(hào)，則輸出?-右符號(hào)；如果缺少右符號(hào)，則輸出左符號(hào)-?。
輸入樣例1：
void test()
{
int i, A[10];
for (i=0; i<10; i++) { /*/
A[i] = i;
}
.
輸出樣例1：
NO
/*-?
輸入樣例2：
void test()
{
int i, A[10];
for (i=0; i<10; i++) /**/
A[i] = i;
}]
.
輸出樣例2：
NO
?-]
輸入樣例3：
void test()
{
int i
double A[10];
for (i=0; i<10; i++) /**/
A[i] = 0.1*i;
}
.
輸出樣例3：
YES
鳴謝用戶 王淵博 補(bǔ)充數(shù)據(jù)！
代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????400 ms
內(nèi)存限制????????????????????????????????????????64 MB
?參考代碼:
#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)單模擬
設(shè)某銀行有A、B兩個(gè)業(yè)務(wù)窗口，且處理業(yè)務(wù)的速度不一樣，其中A窗口處理速度是B窗口的2倍 —— 即當(dāng)A窗口每處理完2個(gè)顧客時(shí)，B窗口處理完1個(gè)顧客。給定到達(dá)銀行的顧客序列，請(qǐng)按業(yè)務(wù)完成的順序輸出顧客序列。假定不考慮顧客先后到達(dá)的時(shí)間間隔，并且當(dāng)不同窗口同時(shí)處理完2個(gè)顧客時(shí)，A窗口顧客優(yōu)先輸出。
輸入格式:
輸入為一行正整數(shù)，其中第1個(gè)數(shù)字N(≤1000)為顧客總數(shù)，后面跟著N位顧客的編號(hào)。編號(hào)為奇數(shù)的顧客需要到A窗口辦理業(yè)務(wù)，為偶數(shù)的顧客則去B窗口。數(shù)字間以空格分隔。
輸出格式:
按業(yè)務(wù)處理完成的順序輸出顧客的編號(hào)。數(shù)字間以空格分隔，但最后一個(gè)編號(hào)后不能有多余的空格。
輸入樣例:
8 2 1 3 9 4 11 13 15
輸出樣例:
1 3 2 9 11 4 13 15代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????400 ms
內(nèi)存限制????????????????????????????????????????64 MB
參考代碼:?
#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ǔ)的二叉樹(shù)的最近的公共祖先問(wèn)題
設(shè)順序存儲(chǔ)的二叉樹(shù)中有編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)，請(qǐng)?jiān)O(shè)計(jì)算法求出它們最近的公共祖先結(jié)點(diǎn)的編號(hào)和值。
輸入格式:
輸入第1行給出正整數(shù)n（≤1000），即順序存儲(chǔ)的最大容量；第2行給出n個(gè)非負(fù)整數(shù)，其間以空格分隔。其中0代表二叉樹(shù)中的空結(jié)點(diǎn)（如果第1個(gè)結(jié)點(diǎn)為0，則代表一棵空樹(shù)）；第3行給出一對(duì)結(jié)點(diǎn)編號(hào)i和j。
題目保證輸入正確對(duì)應(yīng)一棵二叉樹(shù)，且1≤i,j≤n。
輸出格式:
如果i或j對(duì)應(yīng)的是空結(jié)點(diǎn)，則輸出ERROR: T[x] is NULL，其中x是i或j中先發(fā)現(xiàn)錯(cuò)誤的那個(gè)編號(hào)；否則在一行中輸出編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)最近的公共祖先結(jié)點(diǎn)的編號(hào)和值，其間以1個(gè)空格分隔。
輸入樣例1：
15
4 3 5 1 10 0 7 0 2 0 9 0 0 6 8
11 4
輸出樣例1：
2 3
輸入樣例2：
15
4 3 5 1 0 0 7 0 2 0 9 0 0 6 8
12 8
輸出樣例2：
ERROR: T[12] is NULL
代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????400 ms
內(nèi)存限制????????????????????????????????????????64 MB
?參考代碼:?
#include <stdio.h>
int find(int i, int j);
/**
* 7-4 順序存儲(chǔ)的二叉樹(shù)的最近的公共祖先問(wèn)題
*/
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;
}?7-5 修理牧場(chǎng)
農(nóng)夫要修理牧場(chǎng)的一段柵欄，他測(cè)量了柵欄，發(fā)現(xiàn)需要N塊木頭，每塊木頭長(zhǎng)度為整數(shù)Li?個(gè)長(zhǎng)度單位，于是他購(gòu)買(mǎi)了一條很長(zhǎng)的、能鋸成N塊的木頭，即該木頭的長(zhǎng)度是Li?的總和。
但是農(nóng)夫自己沒(méi)有鋸子，請(qǐng)人鋸木的酬金跟這段木頭的長(zhǎng)度成正比。為簡(jiǎn)單起見(jiàn)，不妨就設(shè)酬金等于所鋸木頭的長(zhǎng)度。例如，要將長(zhǎng)度為20的木頭鋸成長(zhǎng)度為8、7和5的三段，第一次鋸木頭花費(fèi)20，將木頭鋸成12和8；第二次鋸木頭花費(fèi)12，將長(zhǎng)度為12的木頭鋸成7和5，總花費(fèi)為32。如果第一次將木頭鋸成15和5，則第二次鋸木頭花費(fèi)15，總花費(fèi)為35（大于32）。
請(qǐng)編寫(xiě)程序幫助農(nóng)夫計(jì)算將木頭鋸成N塊的最少花費(fèi)。
輸入格式:
輸入首先給出正整數(shù)N（≤104），表示要將木頭鋸成N塊。第二行給出N個(gè)正整數(shù)（≤50），表示每段木塊的長(zhǎng)度。
輸出格式:
輸出一個(gè)整數(shù)，即將木頭鋸成N塊的最少花費(fèi)。
輸入樣例:
8
4 5 1 2 1 3 1 1
輸出樣例:
49代碼長(zhǎng)度限制????????????????????????????????16 KB
時(shí)間限制????????????????????????????????????????400 ms
內(nèi)存限制????????????????????????????????????????64 MB
參考代碼:??
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct HuffmanTreeNode {
ElemType data; //哈夫曼樹(shù)中節(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)體指針類(lèi)型
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)建立哈夫曼樹(shù)
//k1為當(dāng)前數(shù)組中第一個(gè)非空樹(shù)的索引，k2為第二個(gè)非空樹(shù)的索引
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)值樹(shù)和次最小權(quán)值樹(shù)建立一棵新樹(shù),pRoot指向樹(shù)根結(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) { //空樹(shù)返回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); //返回指向哈夫曼樹(shù)根節(jié)點(diǎn)的指針
printf("%d", calculateWeightLength(pRoot, 0));
return 0;
}?7-6 公路村村通
現(xiàn)有村落間道路的統(tǒng)計(jì)數(shù)據(jù)表中，列出了有可能建設(shè)成標(biāo)準(zhǔn)公路的若干條道路的成本，求使每個(gè)村落都有公路連通所需要的最低成本。
輸入格式:
輸入數(shù)據(jù)包括城鎮(zhèn)數(shù)目正整數(shù)N（≤1000）和候選道路數(shù)目M（≤3N）；隨后的M行對(duì)應(yīng)M條道路，每行給出3個(gè)正整數(shù)，分別是該條道路直接連通的兩個(gè)城鎮(zhèn)的編號(hào)以及該道路改建的預(yù)算成本。為簡(jiǎn)單起見(jiàn)，城鎮(zhèn)從1到N編號(hào)。
輸出格式:
輸出村村通需要的最低成本。如果輸入數(shù)據(jù)不足以保證暢通，則輸出?1，表示需要建設(shè)更多公路。
輸入樣例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
輸出樣例:
12
參考代碼：
#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)題
?某地區(qū)經(jīng)過(guò)對(duì)城鎮(zhèn)交通狀況的調(diào)查，得到現(xiàn)有城鎮(zhèn)間快速道路的統(tǒng)計(jì)數(shù)據(jù)，并提出“暢通工程”的目標(biāo)：使整個(gè)地區(qū)任何兩個(gè)城鎮(zhèn)間都可以實(shí)現(xiàn)快速交通（但不一定有直接的快速道路相連，只要互相間接通過(guò)快速路可達(dá)即可）?，F(xiàn)得到城鎮(zhèn)道路統(tǒng)計(jì)表，表中列出了有可能建設(shè)成快速路的若干條道路的成本，求暢通工程需要的最低成本。
輸入格式:
輸入的第一行給出城鎮(zhèn)數(shù)目N?(1<N≤1000)和候選道路數(shù)目M≤3N；隨后的M行，每行給出3個(gè)正整數(shù)，分別是該條道路直接連通的兩個(gè)城鎮(zhèn)的編號(hào)（從1編號(hào)到N）以及該道路改建的預(yù)算成本。
輸出格式:
輸出暢通工程需要的最低成本。如果輸入數(shù)據(jù)不足以保證暢通，則輸出“Impossible”。
輸入樣例1:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
輸出樣例1:
12
輸入樣例2:
5 4
1 2 1
2 3 2
3 1 3
4 5 4
輸出樣例2:
Impossible
參考代碼：
#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 最短工期
?一個(gè)項(xiàng)目由若干個(gè)任務(wù)組成，任務(wù)之間有先后依賴順序。項(xiàng)目經(jīng)理需要設(shè)置一系列里程碑，在每個(gè)里程碑節(jié)點(diǎn)處檢查任務(wù)的完成情況，并啟動(dòng)后續(xù)的任務(wù)?，F(xiàn)給定一個(gè)項(xiàng)目中各個(gè)任務(wù)之間的關(guān)系，請(qǐng)你計(jì)算出這個(gè)項(xiàng)目的最早完工時(shí)間。
輸入格式：
首先第一行給出兩個(gè)正整數(shù)：項(xiàng)目里程碑的數(shù)量?N（≤100）和任務(wù)總數(shù)?M。這里的里程碑從 0 到?N?1?編號(hào)。隨后?M?行，每行給出一項(xiàng)任務(wù)的描述，格式為“任務(wù)起始里程碑 任務(wù)結(jié)束里程碑 工作時(shí)長(zhǎng)”，三個(gè)數(shù)字均為非負(fù)整數(shù)，以空格分隔。
輸出格式：
如果整個(gè)項(xiàng)目的安排是合理可行的，在一行中輸出最早完工時(shí)間；否則輸出"Impossible"。
輸入樣例 1：
9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4
輸出樣例 1：
18
輸入樣例 2：
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5
輸出樣例 2：
Impossible
參考代碼：
#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 哈利·波特的考試
?哈利·波特要考試了，他需要你的幫助。這門(mén)課學(xué)的是用魔咒將一種動(dòng)物變成另一種動(dòng)物的本事。例如將貓變成老鼠的魔咒是haha，將老鼠變成魚(yú)的魔咒是hehe等等。反方向變化的魔咒就是簡(jiǎn)單地將原來(lái)的魔咒倒過(guò)來(lái)念，例如ahah可以將老鼠變成貓。另外，如果想把貓變成魚(yú)，可以通過(guò)念一個(gè)直接魔咒lalala，也可以將貓變老鼠、老鼠變魚(yú)的魔咒連起來(lái)念：hahahehe。
現(xiàn)在哈利·波特的手里有一本教材，里面列出了所有的變形魔咒和能變的動(dòng)物。老師允許他自己帶一只動(dòng)物去考場(chǎng)，要考察他把這只動(dòng)物變成任意一只指定動(dòng)物的本事。于是他來(lái)問(wèn)你：帶什么動(dòng)物去可以讓最難變的那種動(dòng)物（即該動(dòng)物變?yōu)楣げㄌ刈约簬サ膭?dòng)物所需要的魔咒最長(zhǎng)）需要的魔咒最短？例如：如果只有貓、鼠、魚(yú)，則顯然哈利·波特應(yīng)該帶鼠去，因?yàn)槭笞兂闪硗鈨煞N動(dòng)物都只需要念4個(gè)字符；而如果帶貓去，則至少需要念6個(gè)字符才能把貓變成魚(yú)；同理，帶魚(yú)去也不是最好的選擇。
輸入格式:
輸入說(shuō)明：輸入第1行給出兩個(gè)正整數(shù)N?(≤100)和M，其中N是考試涉及的動(dòng)物總數(shù)，M是用于直接變形的魔咒條數(shù)。為簡(jiǎn)單起見(jiàn)，我們將動(dòng)物按1~N編號(hào)。隨后M行，每行給出了3個(gè)正整數(shù)，分別是兩種動(dòng)物的編號(hào)、以及它們之間變形需要的魔咒的長(zhǎng)度(≤100)，數(shù)字之間用空格分隔。
輸出格式:
輸出哈利·波特應(yīng)該帶去考場(chǎng)的動(dòng)物的編號(hào)、以及最長(zhǎng)的變形魔咒的長(zhǎng)度，中間以空格分隔。如果只帶1只動(dòng)物是不可能完成所有變形要求的，則輸出0。如果有若干只動(dòng)物都可以備選，則輸出編號(hào)最小的那只。
輸入樣例:
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
輸出樣例:
4 70
參考代碼：
/**
* 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不需要求路徑
// 開(kāi)始主循環(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ī)劃
?有了一張自駕旅游路線圖，你會(huì)知道城市間的高速公路長(zhǎng)度、以及該公路要收取的過(guò)路費(fèi)?，F(xiàn)在需要你寫(xiě)一個(gè)程序，幫助前來(lái)咨詢的游客找一條出發(fā)地和目的地之間的最短路徑。如果有若干條路徑都是最短的，那么需要輸出最便宜的一條路徑。
輸入格式:
輸入說(shuō)明：輸入數(shù)據(jù)的第1行給出4個(gè)正整數(shù)N、M、S、D，其中N（2≤N≤500）是城市的個(gè)數(shù)，順便假設(shè)城市的編號(hào)為0~(N?1)；M是高速公路的條數(shù)；S是出發(fā)地的城市編號(hào)；D是目的地的城市編號(hào)。隨后的M行中，每行給出一條高速公路的信息，分別是：城市1、城市2、高速公路長(zhǎng)度、收費(fèi)額，中間用空格分開(kāi)，數(shù)字均為整數(shù)且不超過(guò)500。輸入保證解的存在。
輸出格式:
在一行里輸出路徑的長(zhǎng)度和收費(fèi)總額，數(shù)字間以空格分隔，輸出結(jié)尾不能有多余空格。
輸入樣例:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
輸出樣例:
3 40
參考代碼：
/**
* 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)與登陸
?實(shí)現(xiàn)QQ新帳戶申請(qǐng)和老帳戶登陸的簡(jiǎn)化版功能。最大挑戰(zhàn)是：據(jù)說(shuō)現(xiàn)在的QQ號(hào)碼已經(jīng)有10位數(shù)了。
輸入格式:
輸入首先給出一個(gè)正整數(shù)N（≤105），隨后給出N行指令。每行指令的格式為：“命令符（空格）QQ號(hào)碼（空格）密碼”。其中命令符為“N”（代表New）時(shí)表示要新申請(qǐng)一個(gè)QQ號(hào)，后面是新帳戶的號(hào)碼和密碼；命令符為“L”（代表Login）時(shí)表示是老帳戶登陸，后面是登陸信息。QQ號(hào)碼為一個(gè)不超過(guò)10位、但大于1000（據(jù)說(shuō)QQ老總的號(hào)碼是1001）的整數(shù)。密碼為不小于6位、不超過(guò)16位、且不包含空格的字符串。
輸出格式:
針對(duì)每條指令，給出相應(yīng)的信息：
1）若新申請(qǐng)帳戶成功，則輸出“New: OK”；
2）若新申請(qǐng)的號(hào)碼已經(jīng)存在，則輸出“ERROR: Exist”；
3）若老帳戶登陸成功，則輸出“Login: OK”；
4）若老帳戶QQ號(hào)碼不存在，則輸出“ERROR: Not Exist”；
5）若老帳戶密碼錯(cuò)誤，則輸出“ERROR: Wrong PW”。
輸入樣例:
5
L 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
L 1234567890 myQQ@qq
L 1234567890 myQQ@qq.com
輸出樣例:
ERROR: Not Exist
New: OK
ERROR: Exist
ERROR: Wrong PW
Login: OK
參考代碼：
/**
* 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)類(lèi)型定義
typedef char PasswordType[Max_Password_Len];//密碼類(lèi)型定義
typedef int Index;
typedef enum {
New, Log
} Pattern;//兩種模式，新建賬號(hào)與登入賬號(hào)
typedef struct {
AccountType Account;
PasswordType Password;
} ElemType;//數(shù)據(jù)類(lèi)型的定義，每個(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) { //銷(xiāo)毀哈希表
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 人以群分
?社交網(wǎng)絡(luò)中我們給每個(gè)人定義了一個(gè)“活躍度”，現(xiàn)希望根據(jù)這個(gè)指標(biāo)把人群分為兩大類(lèi)，即外向型（outgoing，即活躍度高的）和內(nèi)向型（introverted，即活躍度低的）。要求兩類(lèi)人群的規(guī)模盡可能接近，而他們的總活躍度差距盡可能拉開(kāi)。
輸入格式：
輸入第一行給出一個(gè)正整數(shù)N（2≤N≤105）。隨后一行給出N個(gè)正整數(shù)，分別是每個(gè)人的活躍度，其間以空格分隔。題目保證這些數(shù)字以及它們的和都不會(huì)超過(guò)231。
輸出格式：
按下列格式輸出：
Outgoing #: N1
Introverted #: N2
Diff = N3
其中N1是外向型人的個(gè)數(shù)；N2是內(nèi)向型人的個(gè)數(shù)；N3是兩群人總活躍度之差的絕對(duì)值。
輸入樣例1：
10
23 8 10 99 46 2333 46 1 666 555
輸出樣例1：
Outgoing #: 5
Introverted #: 5
Diff = 3611
輸入樣例2：
13
110 79 218 69 3721 100 29 135 2 6 13 5188 85
輸出樣例2：
Outgoing #: 7
Introverted #: 6
Diff = 9359
參考代碼：
/**
* 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 尋找大富翁
??胡潤(rùn)研究院的調(diào)查顯示，截至2017年底，中國(guó)個(gè)人資產(chǎn)超過(guò)1億元的高凈值人群達(dá)15萬(wàn)人。假設(shè)給出N個(gè)人的個(gè)人資產(chǎn)值，請(qǐng)快速找出資產(chǎn)排前M位的大富翁。
輸入格式:
輸入首先給出兩個(gè)正整數(shù)N（≤106）和M（≤10），其中N為總?cè)藬?shù)，M為需要找出的大富翁數(shù)；接下來(lái)一行給出N個(gè)人的個(gè)人資產(chǎn)值，以百萬(wàn)元為單位，為不超過(guò)長(zhǎng)整型范圍的整數(shù)。數(shù)字間以空格分隔。
輸出格式:
在一行內(nèi)按非遞增順序輸出資產(chǎn)排前M位的大富翁的個(gè)人資產(chǎn)值。數(shù)字間以空格分隔，但結(jié)尾不得有多余空格。
輸入樣例:
8 3
8 12 7 3 20 9 5 18
輸出樣例:
20 18 12
參考代碼：
/**
* 7-13 尋找大富翁
* 堆排序和選擇排序
*/
#include <stdio.h> //堆排序； 注意:此算法中，下標(biāo)從1開(kāi)始
#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排名匯總
計(jì)算機(jī)程序設(shè)計(jì)能力考試（Programming Ability Test，簡(jiǎn)稱(chēng)PAT）旨在通過(guò)統(tǒng)一組織的在線考試及自動(dòng)評(píng)測(cè)方法客觀地評(píng)判考生的算法設(shè)計(jì)與程序設(shè)計(jì)實(shí)現(xiàn)能力，科學(xué)的評(píng)價(jià)計(jì)算機(jī)程序設(shè)計(jì)人才，為企業(yè)選拔人才提供參考標(biāo)準(zhǔn)（網(wǎng)址http://www.patest.cn）。
每次考試會(huì)在若干個(gè)不同的考點(diǎn)同時(shí)舉行，每個(gè)考點(diǎn)用局域網(wǎng)，產(chǎn)生本考點(diǎn)的成績(jī)。考試結(jié)束后，各個(gè)考點(diǎn)的成績(jī)將即刻匯總成一張總的排名表。
現(xiàn)在就請(qǐng)你寫(xiě)一個(gè)程序自動(dòng)歸并各個(gè)考點(diǎn)的成績(jī)并生成總排名表。
輸入格式:
輸入的第一行給出一個(gè)正整數(shù)N（≤100），代表考點(diǎn)總數(shù)。隨后給出N個(gè)考點(diǎn)的成績(jī)，格式為：首先一行給出正整數(shù)K（≤300），代表該考點(diǎn)的考生總數(shù)；隨后K行，每行給出1個(gè)考生的信息，包括考號(hào)（由13位整數(shù)字組成）和得分（為[0,100]區(qū)間內(nèi)的整數(shù)），中間用空格分隔。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-496168.html
輸出格式:
首先在第一行里輸出考生總數(shù)。隨后輸出匯總的排名表，每個(gè)考生的信息占一行，順序?yàn)椋嚎继?hào)、最終排名、考點(diǎn)編號(hào)、在該考點(diǎn)的排名。其中考點(diǎn)按輸入給出的順序從1到N編號(hào)。考生的輸出須按最終排名的非遞減順序輸出，獲得相同分?jǐn)?shù)的考生應(yīng)有相同名次，并按考號(hào)的遞增順序輸出。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-496168.html
輸入樣例:
2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85
輸出樣例:
9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4
參考代碼：
/**
* 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;
}到了這里，關(guān)于鄭州輕工業(yè)大學(xué)2022-2023（2）數(shù)據(jù)結(jié)構(gòu)題目集的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
