数据结构课程设计

线性表

1、 某软件公司大约有30名员工，每名员工有姓名、工号、职务等属性，每年都有员工离

职和入职。

把所有员工按照顺序存储结构建立一个线性表，建立离职和入职函数，当有员工离职或入职时，修改线性表，并且打印最新的员工名单。

#include \ #include \ #include \ #include \

#define SIZE sizeof(employee)

typedef struct employee { int n ; employee *s ;

void InitComp() {

printf(\) ; int i = 0 ;

employee *p , *q =NULL ; while(i < n) {

p = (employee *)malloc(SIZE) ; printf(\); scanf_s(\,&(p->name),20); printf(\); scanf_s(\,&(p->number)); printf(\); scanf_s(\,&(p->post),20); p->next = NULL ; i++ ; if(i == 1) { }

s = p ; q = p ;

char name[20] ; int number ; char post[20] ; employee *next ;

}employee ;

}

}

else{ }

q->next = p ; q = q->next ;

void EmpInsert() { }

void EmpDelete(int num) {

employee *p=s,*q=s; int i=0,j = 0; while(j

i=p->number; if(i==num){ } else {

q = p; p = p->next; j++; if(p==s){ } else{ } n--; return ;

q->next = p->next; s = s->next;

employee *p ,*q = s; while(q->next!=NULL)

q = q->next ;

p = (employee *)malloc(SIZE) ; printf(\); scanf_s(\,&p->name,20); printf(\); scanf_s(\,&p->number); printf(\); scanf_s(\,&p->post,20); q->next = p ; p->next = NULL ; n++ ;

}

}

}

printf(\) ;

void EmpPrint() { }

int _tmain(int argc, _TCHAR* argv[]) {

while(1) {

printf(\) ; scanf_s(\,&l) ; switch(l) { case 1: }

EmpInsert() ; EmpPrint() ; break ;

printf(\) ; scanf_s(\,&m) ; EmpDelete(m) ; EmpPrint() ; break ; EmpPrint() ;

int l ,m;

printf(\); scanf_s(\,&n) ; InitComp() ;

EmpPrint() ;

employee *p = s;

printf(\) ;

while(p !=NULL) { }

printf(\,p->name,p->number,p->post) ; p = p->next ;

case 2:

default:

}

system(\); return 0; }

2、 约瑟夫（Josephus）环问题：编号为1,2,3,…,n的n个人按顺时针方向围坐一圈，每

人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一人开始重新从1报数，如此下去，直到所有人全部出列为止。

建立n个人的单循环链表存储结构，运行结束后，输出依次出队的人的序号。

#include \ #include \ #include \

struct person { } ;

person *h ;

void CreaCircle() {

int n ,i ;

person *p , *q = NULL, *r = NULL;

printf(\); scanf_s(\,&n) ; for(i = 1; i < n+1; i++) { }

p = (person *) malloc(sizeof(person)) ; p->num = i ;

printf(\,i); scanf_s(\,&p->code) ; p->next = NULL ; if(i ==1) { }

q->next = p ; q = p ;

h = p ; q = p ;

int num ; int code ; person *next ;

}

q->next = h ;

void RunGame() { }

int main(){

CreaCircle() ; RunGame() ; system(\); return 0 ; }

int m , i;

person * r , * t = h;

printf(\) ; scanf_s(\,&m) ; while(t->next != t) { }

for(i = 1; i < m - 1; i++)

t = t->next ; r = t->next ; m = r->code ; t->next = r->next ;

printf(\,r->num);

栈和队列

3、 某商场有一个100个车位的停车场，当车位未满时，等待的车辆可以进入并计时；当车

位已满时，必须有车辆离开，等待的车辆才能进入；当车辆离开时计算停留的的时间，并且按照每小时1元收费。

汽车的输入信息格式可以是（进入/离开，车牌号，进入/离开时间），要求可以随时显示停车场内的车辆信息以及收费历史记录。

#include #include \ #include \ #include #include \ using namespace std;

#define LIST_INIT_SIZE 10 #define PRICE 1

typedef struct Car

{

int carnumber; int money; time_t entertime; time_t leavetime; }Car;

typedef struct ParkList{ Car *head; int length; int listsize; }ParkList;

typedef struct WaitNode{ Car WaitCar; WaitNode *next; }WaitNode,*WaitList;

typedef struct LeaveNode{ Car LeaveCar; LeaveNode *next; }LeaveNode,*LeaveList;

int init_LeaveList(LeaveList &L){

L = (LeaveList)malloc(sizeof(LeaveNode)); L->next = NULL; }

int init_WaitList(WaitList &WL,Car wc){ WL = (WaitList)malloc(sizeof(WaitNode)); WL->WaitCar = wc; WL->next = NULL; }

void Put_LeaveList(LeaveList &L,Car lc){ LeaveList p = L; if(p==NULL){ return ; }

while(p->next){ p = p->next; }

LeaveList q = (LeaveList)malloc(sizeof(LeaveNode)); q->LeaveCar = lc;

p->next = q; q->next = NULL;

q->LeaveCar.money = (q->LeaveCar.leavetime-q->LeaveCar.entertime)*PRICE; }

void Putelem_WaitList(WaitList &WL,Car wc){ WaitList p = WL; if(p==NULL){

init_WaitList(WL,wc); return ; }

while(p->next){ p = p->next; }

WaitList q = (WaitList)malloc(sizeof(WaitNode)); q->WaitCar = wc; p->next = q; q->next = NULL; }

void delete_WaitList(WaitList &WL,Car &c){ if(WL==NULL){ return ; }

WaitList p = WL; c = p->WaitCar; if(WL->next==NULL){ WL=NULL; } else {

WL = WL->next; } free(p); }

Car CreateCar(int carnum){

Car *pc = (Car *)malloc(sizeof(Car)); pc->carnumber = carnum; pc->entertime = time(NULL); return *pc; }

int init_Parklist(ParkList &p) {

p.head = (Car *)malloc(LIST_INIT_SIZE*sizeof(Car)); if(!p.head) return 0; p.length = 0;

p.listsize = LIST_INIT_SIZE; return 1; }

int put_ParkList(ParkList &p,WaitList &WL,Car c) {

if(p.length==p.listsize){ if(WL==NULL) {

init_WaitList(WL,c); }

else Putelem_WaitList(WL,c); return 0; }

Car *pc = p.head; pc[p.length] = c; p.length += 1; return 1; }

int insert_ParkList(ParkList &p,WaitList &WL,int i) {

Car c;

delete_WaitList(WL,c);

if(i<0||i>=p.length){ return 0;} Car *pc = p.head;

for(int j=p.length-1;j>i-1;j--) {

pc[j+1]=pc[j]; } pc[i]=c; p.length += 1; return 1; }

int delete_ParkList(ParkList &p,LeaveList &L,int i) {

if(i>=0&&i

Car *pc = p.head;

pc[i].leavetime = time(NULL); Put_LeaveList(L,pc[i]);

for(int j=i;j

pc[j]=pc[j+1]; }

p.length -= 1; return 1; }

else return 0; }

void showParkList(ParkList p) {

if(p.head!=NULL) {

Car *pc = p.head; printf(\); for(int j=0;j

printf(\,pc[j].carnumber,ctime(&pc[j].entertime)); }

printf(\); } }

void showWaitList(WaitList WL){ WaitList p = WL; printf(\); while(p){

printf(\,p->WaitCar.carnumber,ctime(&(p->WaitCar.entertime))); p = p->next; } }

void showLeaveList(LeaveList L){ LeaveList p = L->next; printf(\); while(p){

printf(\,p->LeaveCar.carnumber, ctime(&(p->LeaveCar.entertime)));

printf(\,ctime(&(p->LeaveCar.leavetime)),p->LeaveCar.money); p = p->next; } }

int main() {

ParkList p; LeaveList L; WaitList WL=NULL; init_LeaveList(L); init_Parklist(p); srand(time(NULL)); Car c;

int i = 1,n=0; int dic = 0; int index = 0; int time = 0; while(i<=100){ dic = rand()%2; switch(dic){ case 1:

c = CreateCar(1000+i); put_ParkList(p,WL,c); break; case 0:

if(p.length==0){ break; } else {

index = rand()%p.length; delete_ParkList(p,L,index); if(WL!=NULL){

insert_ParkList(p,WL,index); } break; } default: break; } i++; }

showParkList(p); showWaitList(WL); showLeaveList(L);

}

4、 某银行营业厅共有6个营业窗口，设有排队系统广播叫号，该银行的业务分为公积金、

银行卡、理财卡等三种。公积金业务指定1号窗口，银行卡业务指定2、3、4号窗口，理财卡业务指定5、6号窗口。但如果5、6号窗口全忙，而2、3、4号窗口有空闲时，

理财卡业务也可以在空闲的2、3、4号窗口之一办理。

客户领号、业务完成可以作为输入信息，要求可以随时显示6个营业窗口的状态。

#include \ #include \ #include \

typedef struct Cost {

void InitCL(CostList & CL , int number) { }

void PutCL(CostList & CL , int number) { }

void PopCL(CostList & CL , int & number) {

CostList p = CL ; if(CL == NULL) {

number = CL->num ; CL = CL->next ; number = 0 ; else

CostList p = CL , q; if(CL == NULL) { }

while(p->next)

p = p->next ;

q= (CostList)malloc(sizeof(Cost)) ; q->num = number ; p->next = q; q->next = NULL ; InitCL(CL , number) ; else

CL = (CostList)malloc(sizeof(Cost)) ; CL->num = number ; CL->next = NULL ; int num ; Cost * next ;

}Cost , * CostList ;

}

}

free( p ) ;

void ShowCL(CostList & CL) { }

int _tmain(int argc, _TCHAR* argv[]) {

int a[6] = {0}, n , costnum=0 , i = 0 , j = 0 , m; CostList CL1 = NULL ,CL2 = NULL , CL3 = NULL ; while(1) {

printf(\请选择业务种类\\n1.公积金业务\\n2.银行卡业务\\n3.理财卡业务\\n4.业务办理完scanf_s(\,&n) ; switch(n) { case 1 :

i++ ;

printf(\您的序号为：%d\\n\,i) ; if(CL1 == NULL)

InitCL(CL1 , i) ; PutCL(CL1 , i) ; else break ; i++ ;

printf(\您的序号为：%d\\n\,i) ; if(CL2 == NULL)

InitCL(CL2 , i) ; PutCL(CL2 , i) ; else break ;

CostList p = CL ; while(p) { }

printf(\) ;

printf(\,p->num ) ; p = p->next ;

成\\n5.显示当前窗口营业状态\\n6.显示当前排队情况\\n\) ;

case 2 :

case 3 :

}

i++ ;

printf(\您的序号为：%d\\n\,i) ; if(CL3 == NULL)

InitCL(CL3 , i) ; PutCL(CL3 , i) ; else break ;

printf(\正在营业的窗口:\\n\) ; for(j = 0 ; j < 6 ; j++) { }

printf(\);

printf(\请选择业务办理完成的窗口号：\\n\) ; scanf_s(\,&m) ; a[m-1] = 0; break ;

printf(\窗口营业情况:\\n\) ; for(j = 0 ; j < 6 ; j++) { } break ;

printf(\办理公积金业务的客户有：\\n\) ; ShowCL(CL1) ;

printf(\办理银行卡业务的客户有：\\n\) ; ShowCL(CL2) ;

printf(\办理理财卡业务的客户有：\\n\) ; ShowCL(CL3) ;

if(a[j] != 0)

printf(\号窗口正在为%d号客户服务\\n\,j+1 ,a[j]) ; if(a[j] != 0)

printf(\,j+1) ;

case 4 :

case 5 :

case 6 :

if(a[0] == 0) { }

if(a[4] == 0) {

PopCL(CL3 , costnum) ; a[4] = costnum ; PopCL(CL1 ,costnum) ; a[0] = costnum ;

}

if(a[5] == 0) { }

if(a[1] == 0) { }

if(a[2] == 0) { }

if(a[3] == 0) {

if(CL2 != NULL) { } else {

PopCL(CL3 , costnum) ; PopCL(CL2 , costnum) ; a[3] = costnum ; if(CL2 != NULL) { } else { }

PopCL(CL3 , costnum) ; a[2] = costnum ; PopCL(CL2 , costnum) ; a[2] = costnum ; if(CL2 != NULL) { } else { }

PopCL(CL3 , costnum) ; a[1] = costnum ; PopCL(CL2 , costnum) ; a[1] = costnum ; PopCL(CL3 , costnum) ; a[5] = costnum ;

} }

}

a[3] = costnum ;

system(\) ; return 0; }

5、4阶斐波那契序列如下：f0=f1=f2=0, f3=1,…,fi=fi-1+fi-2+fi-3+fi-4，

利用容量为k=4的循环队列，构造序列的前n+1项（f0, f1 , f2 ,… fn ），要求满足fn ≤200而fn+1 >200。

#include \ #include \ #include \

int f[100] = {0,0,0,1}; int count = 4 ; struct number { } ;

number * h ;

void InitCircle() { }

int i ;

number * p , * q = NULL ; for(i = 1 ; i < 5 ; i++) { }

q->next = h ;

h->next->next->next->n = 1 ;

p = (number *)malloc(sizeof(number)) ; p->n = 0 ; p->next = NULL ; if(i == 1) { }

q->next = p ; q = p ;

h = p ; q = p ;

int n ;

number * next ;

void run() { }

void print() { }

int _tmain() {

InitCircle() ; run() ; print() ;

system(\) ; return 0 ; } int i ;

printf(\) ; for(i = 0 ; i < count ; i++)

printf(\,f[i]) ; number * p =h ;

while(p->n < 200 && p->n + p->next->n < 200 && p->next->next->n < 200 && } count-- ;

p->n = p->n + p->next->n + p->next->next->n + p->next->next->next->n ; f[count++] = p->n ; p = p->next ;

p->next->next->next->n < 200){

5、 八皇后问题：设8皇后问题的解为 (x1, x2, x3, …,x8), 约束条件为：在8x8的棋盘上，

其中任意两个xi 和xj不能位于棋盘的同行、同列及同对角线。要求用一位数组进行存储，输出所有可能的排列。

#include \ #include \ #include \ #define N 8

int count , a[N] ,b[N][N];

int position(int i , int j) {

int ii = i - 1 ,jj = j , ok = 1 ; while((ii > 0)&&ok) {

ii-- ;

if(a[ii] == jj)

}

}

ok = 0 ;

ii = i - 1 ; jj = j ;

while((ii > 0)&&(jj > 1)&&ok) { }

ii = i - 1 ; jj = j ;

while((ii > 0)&&(jj

return ok ;

ii-- ; jj++ ;

if(a[ii] == jj)

ok = 0 ; ii-- ; jj-- ;

if(a[ii] == jj)

ok = 0 ;

void queen(int i) {

if(i <= N ) { } else {

count++ ;

printf(\, count); for(int j = 1 ;j <= N ;j++)

printf(\,a[j-1]); printf(\) ;

for(int i = 0 ;i < N ;i++) for(int j = 1 ;j <= N ;j++) { }

if(position(i,j)) { }

a[i-1] = j ; queen(i+1) ;

{ {

b[i][a[i]-1] = 1;

for(int j = 0 ;j < N ;j++) printf(\,b[i][j]); }

printf(\); b[i][a[i]-1] = 0; }

int _tmain(int argc, _TCHAR* argv[]) {

queen(1) ; system(\) ; return 0; }

}

6、 }

数组与广义表

10、鞍点问题： 若矩阵A中的某一元素A[i,j]是第i行中的最小值，而又是第j列中的最

大值，则称A[i,j]是矩阵A中的一个鞍点。写出一个可以确定鞍点位置的程序。

#include \ #include \ #include \

void found() {

int m , n , i , j , b , k , q , f = 1; printf(\请输入数组行数：\\n\) ; scanf_s(\,&m) ;

printf(\请输入数组列数：\\n\) ; scanf_s(\,&n) ;

int *a = (int*)malloc(sizeof(int)*m*n) ; printf(\请输入数组值：\\n\) ; for(i = 0 ; i < m ; i++) { }

printf(\输入数组为：\\n\); for(i = 0 ; i < m ; i++) {

for(j = 0 ; j < n ; j++) for(j = 0 ; j < n ; j++)

scanf_s(\,a+i*n+j) ;

}

printf(\,*(a+i*n+j)) ;

printf(\);

for( i = 0 ; i < m ; i++) {

b = *(a+i*m) ; q = 0 ;

for(j = 0 ; j < n ; j++) { }

b = *(a+i*n+q) ;

if(*(a+i*n+j) < b) { }

b = *(a+i*n+j) ; q = j ;

for(k = 0; k < m; k++) {

if(b < *(a+k*n+q)) break; }

if(k == m) {

printf(\该数组鞍点为第%d行第%d列的数字：%d\\n\ , i+1 , q+1 , b); f = 0 ; } } if(f)

printf(\没有找到鞍点。\\n\); }

int _tmain(int argc, _TCHAR* argv[]) {

found() ;

system(\) ; return 0;

11、}

12、稀疏矩阵转置： 输入稀疏矩阵中每个元素的行号、列号、值，建立稀疏矩阵的三元组

存储结构，并将此矩阵转置，显示转置前后的三元组结构。

#include \ #include \ #include \

typedef struct

{

typedef struct {

void In_Mat(Matrix * m) { }

void Out_Mat(Matrix m) { }

void Tra_Mat(Matrix * m ,Matrix * n) { }

int _tmain(int argc, _TCHAR* argv[])

n->ii = m->jj ; n->jj = m->ii ; n->cc = m->cc ;

for(int t = 0 ; t < n->cc ; t++) { }

n->data[t].i = m->data[t].j ; n->data[t].j = m->data[t].i ; n->data[t].v = m->data[t].v ; printf(\行\\t列\\t值\\n\) ; for(int c = 0 ; c < m.cc ; c++)

printf(\,m.data[c].i , m.data[c].j , m.data[c].v) ; printf(\请输入矩阵行数：\\n\) ; scanf_s(\,&m->ii) ;

printf(\请输入矩阵列数：\\n\) ; scanf_s(\,&m->jj) ;

printf(\请输入非零元素个数：\\n\) ; scanf_s(\,&m->cc) ;

printf(\请依次输入非零元素所在的行数、列数和其值：\\n\) ; for(int c = 0 ; c < m->cc ; c++)

scanf_s(\,&m->data[c].i , &m->data[c].j , &m->data[c].v) ; Triple data[100] ; int ii , jj , cc ; int i , j , v ; }Triple ;

}Matrix ;

{

Matrix m , n ; Matrix * mm = &m ; Matrix * nn = &n ; In_Mat( mm ) ; Tra_Mat(mm , nn) ;

printf(\转置前矩阵非零元素：\\n\) ; Out_Mat(m) ;

printf(\转置后矩阵非零元素：\\n\) ; Out_Mat(n) ; system(\); return 0;

13、}

树和二叉树

以下问题要求统一在一个大程序里解决。

14、按先序遍历的扩展序列建立二叉树的存储结构 15、二叉树先序、中序、后序遍历的递归算法 16、二叉树中序遍历的非递归算法 17、二叉树层次遍历的非递归算法 18、求二叉树的深度(后序遍历)

#include \ #include \ #include \

typedef struct BiTr { struct {

void CrBiTr(BT & b) {

int a ;

b = (BT)malloc(sizeof(BiTr)) ;

printf(\请输入该结点的值,值为零表示删除该结点：\\n\) ; scanf_s(\,&a) ; BT q[100] ; int h , r ; int data ;

struct BiTr * lc , * rc ;

}BiTr , * BT ;

}queue ;

}

if(a == 0) { }

b->data = a ; CrBiTr(b->lc) ; CrBiTr(b->rc) ; b = NULL ; else

void visit(BT b) { }

void PreOrderTraverse(BT b) { }

void InOrderTraverse(BT b) { }

void PostOrderTraverse(BT b) { }

void InOrderTraverse1(BT b) {

BT s[500] , p ; int i = -1 ; p = b ; while(p) {

PreOrderTraverse(b->lc); PreOrderTraverse(b->rc); visit(b) ;

InOrderTraverse(b->lc); visit(b) ;

InOrderTraverse(b->rc); visit(b) ;

PreOrderTraverse(b->lc); PreOrderTraverse(b->rc); printf(\ , b->data) ;

}

}

if(p) {

i++ ; s[i] = p; p = p->lc ;

} else { }

p = s[i]; i--;

printf(\,p->data); p = p->rc ;

void CengciTraverse(BT b) { }

BT p = b ; queue.h = 0 ; queue.r = 0 ; if(b)

printf(\,p->data) ; queue.q[queue.r] = p ; queue.r++ ;

while(queue.h < queue.r) { }

p = queue.q[queue.h] ; queue.h++ ; if(p->lc) { }

if(p->rc) { }

printf(\,p->rc->data) ; queue.q[queue.r] = p->rc ; queue.r++ ;

printf(\,p->lc->data) ; queue.q[queue.r] = p->lc ; queue.r++ ;

int Depth(BT b) { }

int _tmain(int argc, _TCHAR* argv[]) {

int a = 1; BT b = NULL ;

printf(\二叉树的操作，请选择序号：\\n\) ;

printf(\按先序遍历的扩展序列建立二叉树的存储结构：\\n\) ; printf(\二叉树先序、中序、后序遍历的递归算法：\\n\) ; printf(\二叉树中序遍历的非递归算法：\\n\) ; printf(\二叉树层次遍历的非递归算法：\\n\) ; printf(\求二叉树的深度(后序遍历)：\\n\) ; scanf_s(\,&a) ; while(a != 0)

{

switch(a) { case 1 :

{ } {

printf(\先序遍历如下：\\n\) ; PreOrderTraverse(b) ; printf(\中序遍历如下：\\n\) ; printf(\开始创建：\\n\) ; CrBiTr(b) ; break ;

int dep = 0 ,dep1 ,dep2 ; if (b = NULL) { }

dep1 = Depth(b->lc) ; dep2 = Depth(b->rc) ; if(dep1 > dep2)

dep = dep1 + 1 ; dep = dep2 + 1 ; else

return dep ; return 0 ; else

case 2 :

}

}

} { } { } { }

InOrderTraverse(b) ;

printf(\后序遍历如下：\\n\) ; PostOrderTraverse(b) ; break ;

case 3 :

printf(\中序遍历的非递归算法：\\n\); InOrderTraverse1(b) ; break ;

case 4 :

printf(\层次遍历的非递归算法\) ; CengciTraverse(b); break ;

case 5 :

printf(\二叉树的深度为：\\n\) ; Depth( b ) ; break ;

system(\) ; return 0;

}

19、建立树的存储结构 20、求树的深度 #include \#include \#include \

typedef struct TreeNode { int data ; struct TreeNode * chil , * bro ; }TreeNode , * Tree ;

void Create(Tree & b) { int a ; b = (Tree)malloc(sizeof(TreeNode)) ;

printf(\请输入该结点的值,值为零表示删除该结点：\\n\ scanf_s(\ if(a == 0) { b = NULL ; } else { b->data = a ; Create(b->chil) ; Create(b->bro) ; } }

int Depth(Tree b) { int dep1,dep2; if(!b) return 0; else { dep1=Depth(b->chil); dep2=Depth(b->bro); if(dep1+1>dep2) return (dep1+1); else return dep2; } }

int _tmain(int argc, _TCHAR* argv[]) { Tree p = NULL ; printf(\建立树的存储结构：\\n\ Create(p) ; printf(\树的深度为：\\n\ printf(\ system(\ return 0; }

图

21、输入任意的一个网，用普里姆(Prim)算法构造最小生成树。

#include \#include \#include \

typedef struct { int v ,e ; int edges[10][10] ; }Mgraph ;

void create(Mgraph & m) { int s , t; printf(\请输入网的顶点个数：\\n\ scanf_s(\m.v)) ; printf(\请输入网的边数：\\n\ scanf_s(\m.e)) ; for(int i = 0 ; i < m.v ; i++) for(int j = 0 ; j < m.v ; j++) m.edges[i][j] = 100 ; printf(\请输入各条边的信息：\\n\ for(int i =0 ; i < m.e ; i++) { printf(\请输入第%d条边的顶点：\ scanf_s(\ printf(\请输入第%d条边的权值：\ scanf_s(\m.edges[s-1][t-1])); m.edges[t][s] = m.edges[s-1][t-1] ; } }

void MiniSpanTree(Mgraph m , int u) { int a[10] , b[10] , s , t , c = 1 ,shortest = 100 , route = 0 ; for(int i = 0 ; i < m.v ; i++) a[i] = 1 ; for(int i = m.v ; i < 10 ; i++) a[i] = 0 ; for(int i = 0 ; i < 10 ; i++) b[i] = 0 ; a[u] = 0 ; b[u] = 1 ; c = 1 ; while(c)

{ for(int i = 0 ; i < 10 ; i++) { for(int j = 0 ; j < 10 ; j++) { if(a[i] == 1 && b[j] == 1) { if(shortest > m.edges[i][j]) { shortest = m.edges[i][j] ; s = i ; t = j ; c = 0 ; } } } } if(shortest != 100) { route +=shortest ; a[s] = 0 ; b[s] = 1 ; printf(\下一条最短路线为%d到%d，长度为%d\\n\m.edges[s][t]) ; } for(int i = 0 ; i < 10 ; i++) { if(a[i] == 1) c = 1 ; } shortest = 100 ; } printf(\最小生成树的总长度为：%d\\n\ }

int _tmain(int argc, _TCHAR* argv[]) { Mgraph mg ; create(mg) ; MiniSpanTree(mg , 1) ; system(\ return 0; }

22、要求建立图的存储结构（邻接表或邻接矩阵），输入任意的一个图，显示图的深度优先

搜索遍历路径。

23、要求建立图的存储结构（邻接表或邻接矩阵），输入任意的一个图，显示图的广度优先

搜索遍历路径。 #include \#include \#include \

typedef struct Arc { int next ; int weight ; struct Arc * nextArc ; }Arc ;

typedef struct Node { int data ; Arc * firstArc ; }Node , List[10] ;

typedef struct { List ver ; int nnum , anum ; }Graph ;

typedef struct QNode { int data ; struct QNode * next ; }QNode , * Queue ;

typedef struct { Queue head ; Queue rear ; }LinkQueue ;

void InitQueue(LinkQueue &Q) { Q.head = Q.rear = (Queue)malloc(sizeof(QNode)) ; Q.head->next = NULL ; }

void EnQueue(LinkQueue &Q , int e)

{ Queue p ; p = (Queue)malloc(sizeof(QNode)) ; p->data = e ; p->next = NULL ; Q.rear->next = p ; Q.rear = p ; }

void DeQueue(LinkQueue &Q , int &e) { Queue p ; p = Q.head->next ; e = p->data ; Q.head->next = p->next ; free(p); if(Q.head->next == NULL) Q.rear = Q.head ; }

int QueueEmp(LinkQueue &Q) { if(Q.head == Q.rear) return 1 ; else return 0 ; }

int visited[10] ;

void Create(Graph &G) { int v1 , v2 , w ; Arc *p,*q ; printf(\请输入顶点数和边数：\\n\ scanf_s(\G.nnum,&G.anum) ; for(int i = 0 ; i < G.nnum ; i++) { G.ver[i].data = i ; G.ver[i].firstArc = NULL ; } printf(\请输入边的信息（顶点/顶点/权重）\\n\ for(int i = 0 ; i < G.anum ; i++) {

p = (Arc *)malloc(sizeof(Arc)) ; scanf_s(\ p->next = v2-1 , p->weight = w ; p->nextArc = G.ver[v1-1].firstArc ; G.ver[v1-1].firstArc = p ; q = (Arc *)malloc(sizeof(Arc)) ; q->next = v1-1 , q->weight = w ; q->nextArc = G.ver[v2-1].firstArc ; G.ver[v2-1].firstArc = q ; } }

void DFS(Graph &G , int v) { Arc * p ; printf(\v+1) ; visited[v] = 1; p = G.ver[v].firstArc ; while(p) { if(!visited[p->next]) DFS(G,p->next) ; p = p->nextArc ; } }

void DFSTra(Graph &G) { for(int i = 0 ; i < G.nnum ; i++) visited[i] = 0 ;

for(int i = 0;i

void BFSTra(Graph &G) { LinkQueue Q ; InitQueue(Q) ; for(int i = 0 ; i < G.nnum ; i++) visited[i] = 0 ; for(int i = 0 ; i< G.nnum ; i++) {

if(!visited[i]) { EnQueue(Q,i); visited[i] = 1 ; while(!QueueEmp(Q)) { int u ; DeQueue(Q,u) ; printf(\ for(Arc * a = G.ver[u].firstArc ; a!=NULL ; a = a->nextArc) if(!visited[a->next]){ EnQueue(Q,a->next); visited[a->next] = 1 ; } } } } }

int main() { Graph G ; Create(G) ; printf(\深度优先搜索：\\n\ DFSTra(G) ; printf(\广度优先搜索：\\n\ BFSTra(G) ; system(\ return 0; }

查找

设计一个读入一串整数构成一颗二叉排序树的程序，从二叉排序树中删除一个结点，使该二叉树仍保持二叉排序树的特性。

#include \ #include \ #include \

typedef struct tree {

struct tree *left; struct tree *right; int key;

} BSTNode , * BSTree;

void insertBST(BSTree &T,int key) { }

void createBST(BSTree &t) { }

void InOrder(BSTree t) {

BSTree p = t; int key;

printf(\请输入第一个结点的值（0表示结束）：\\n\) ; scanf_s(\,&key); while(key != 0) { }

insertBST(t , key);

printf(\请输入下一个结点的值（0表示结束）：\\n\) ; scanf_s(\ , &key); BSTree f = NULL , p = T; while(p) { }

p = (BSTree)malloc(sizeof(BSTNode)); p->key = key ;

p->left = p->right = NULL; if(T == NULL) { }

if(key < f->key)

f->left = p; f->right = p; else T = p; else

if(p->key == key)

return ; f = p;

if(key < p->key)

p = p->left ; p = p->right ; else

}

if(p != NULL) { }

InOrder(p->left);

printf(\中序遍历当前二叉树：\\n\) ; printf(\,p->key ); InOrder(p->right );

int searchBST(BSTree t , int key) { }

BSTree deleteBST(BSTree T , int key) {

BSTree p,tmp,parent = NULL; p = T; while(p) {

if(p->key == key) break; parent = p;

if(key < p->key)

p = p->left ; p = p->right ; else

if(key == t->key)

return 1; return 0;

return searchBST(t->left , key); return searchBST(t->right , key); if(t==NULL) if(keykey) else

} if(!p)

return NULL;

tmp=p;

if(!p->right&&!p->left) {

if(!parent) T = NULL;

else if(p == parent->right) parent->right = NULL;

else

parent->left = NULL; free(p); }

else if(!p->right) {

p = p->left; if(!parent) T = p;

else if(tmp == parent->left) parent->left = p; else

parent->right = p; free(tmp); }

else if(!p->left) {

p = p->right; if(!parent) T = p;

else if(tmp == parent->left) parent->left = p ; else

parent->right = p; free(tmp); }

else if(p->right&&p->left) {

parent = p; p = p->right; while(p->left) {

parent = p; p = p->left; }

tmp->key = p->key; if(p == parent->left) parent->left = NULL; else

parent->right = NULL; free(p); }

} return T;

int _tmain(int argc, _TCHAR* argv[]) {

int key; BSTree t;

printf(\创建二叉树：\\n\); createBST(t);

printf(\中序遍历二叉树:\);

InOrder(t);

printf(\输入你要删除结点的关键字：\\n\); scanf_s(\,&key); t=deleteBST(t,key); if(t==NULL)

printf(\对不起，你所删除的结点%d不存在!\\n\,key); else

printf(\成功删除结点%d.\\n\,key); printf(\中序遍历二叉树:\); }

InOrder(t); system(\) ; return 0;

24、设定哈希函数 H(key) = key MOD 11 ( 表长=11 )，输入一组关键字序列，根据线性探测

再散列解决冲突的方法建立哈希表的存储结构，显示哈希表，任意输入关键字，判断是否在哈希表中。

#include \ #include \ #include \ #include \

typedef struct {

typedef struct SQList {

void Insert(SQList &s , int i) {

int a = i % 11 ; if(s.elem[a].data == 0)

s.elem[a].data = i ; elemtype * elem ; }SQList ;

int data ; }elemtype ;

}

else { }

while(s.elem[a].data != 0) { }

s.elem[a].data = i ;

if(a == 11)

a = 1 ; a = a + 1 ; else

void Print(SQList s) { }

int Search(SQList s , int a) { }

int _tmain(int argc, _TCHAR* argv[]) {

SQList s ; int a ;

s.elem = (elemtype *)malloc(12*sizeof(elemtype)) ; for(int i = 1 ; i <= 11 ; i++)

s.elem[i].data = 0 ;

printf(\请依次输入要插入的数据：\) ; for(int i = 0 ; i < 11 ; i++) { }

scanf_s(\,&a) ; Insert(s , a) ;

for(int i = 1 ; i <= 11 ; i++)

if(a == s.elem[i].data)

return 1 ;

printf(\哈希表存储如下：\) ; for(int i = 1 ; i <= 11 ; i++) { }

printf(\,s.elem[i].data) ;

return 0 ;

}

Print(s) ; system(\) ; return 0;

排序

以下问题要求统一在一个大程序里解决。 25、折半插入排序 26、冒泡排序 27、快速排序

28、简单选择排序 29、归并排序 30、堆排序

#include \ #include \ #include \

typedef struct {

typedef struct SQList {

void Create(SQList &s) { }

void Print(SQList s) {

printf(\线性表输出如下：\\n\); printf(\请输入数字个数：\\n\) ; scanf_s(\,&s.len ) ;

s.elem = (elemtype *)malloc((s.len+1)*sizeof(elemtype)) ; printf(\请依次输入数字：\\n\) ; for(int i = 1 ; i <= s.len ; i++) { }

printf(\第%d个数字：\,i);

scanf_s(\,&(s.elem[i].data)) ; elemtype * elem ; int len ; int data ; }elemtype ;

}SQList ;

} { }

for(int i = 1 ; i <= s.len ; i++)

printf(\,s.elem[i].data) ;

void zheban(SQList &L)

int i,low,high,m,j; for(i=2;i<=L.len;++i) { }

L.elem[0]=L.elem[i]; low=1; high=i-1; while(low<=high) { }

for(j=i-1;j>=high+1;--j)

L.r[j+1]=L.r[j];//记录后移 L.r[high+1]=L.r[0];//插入

m=(low+high)/2;

if(L.elem[0].key

high=m-1; else low=m+1;

void 冒泡排序(SQList &s) { }

int i = s.len ; while(i > 1) { }

int last = 1 ;

for(int j = 1; j < i ; j++) { }

i = last ;

if(s.elem[j].data > s.elem[j+1].data) { }

s.elem[0] = s.elem[j+1] ; s.elem[j+1] = s.elem[j] ; s.elem[j] = s.elem[0] ; last = j ;

int Partition (SQList &s , int low , int high) { }

void 快速排序(SQList &s , int i , int j) { }

int SelectMindata(SQList s , int i) { }

void 简单选择排序(SQList &s) {

for(int i = 1 ; i < s.len ; i++) {

int j = SelectMindata(s,i) ; int MK = i ;

for(int j = i ; j <= s.len ; j++) { }

return MK;

if(s.elem[j].data < s.elem[MK].data)

MK = j ;

if(i < j) { }

int pivotloc = Partition(s,i,j) ; 快速排序(s , i , pivotloc-1) ; 快速排序(s , pivotloc+1 , j) ; s.elem[0]=s.elem[low] ;

int pivotloc = s.elem[low].data; while(low

s.elem[low] = s.elem[0] ; return low ;

while(low < high&&s.elem[high].data >= pivotloc)

high-- ;

s.elem[low] = s.elem[high];

while(low < high&&s.elem[low].data <= pivotloc)

low++ ;

s.elem[high] = s.elem[low] ;

本文来源：https://www.bwwdw.com/article/3kbg.html