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
文章來(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)!