数据结构课程设计

线性表

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

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

#include \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

#include \"malloc.h\"

#define SIZE sizeof(employee)

typedef struct employee

{

char name[20] ;

int number ;

char post[20] ;

employee *next ;

}employee ;

int n ;

employee *s ;

void InitComp()

{

printf(\"start create:\\n\") ;

int i = 0 ;

employee *p , *q =NULL ;

while(i < n)

{

p = (employee *)malloc(SIZE) ;

printf(\"please enter name\\n\");

scanf_s(\"%s\",&(p->name),20);

printf(\"please enter number\\n\");

scanf_s(\"%d\",&(p->number));

printf(\"please enter post\\n\");

scanf_s(\"%s\",&(p->post),20);

p->next = NULL ;

i++ ;

if(i == 1)

{

s = p ;

q = p ;

}

else{

q->next = p ;

q = q->next ;

}

}

}

void EmpInsert()

{

employee *p ,*q = s;

while(q->next!=NULL)

q = q->next ;

p = (employee *)malloc(SIZE) ;

printf(\"please enter name\\n\");

scanf_s(\"%s\",&p->name,20);

printf(\"please enter number\\n\");

scanf_s(\"%d\",&p->number);

printf(\"please enter post\\n\");

scanf_s(\"%s\",&p->post,20);

q->next = p ;

p->next = NULL ;

n++ ;

}

void EmpDelete(int num)

{

employee *p=s,*q=s;

int i=0,j = 0;

while(ji=p->number;

if(i==num){

if(p==s){

s = s->next;

}

else{

q->next = p->next;

}

n--;

return ;

}

else {

q = p;

p = p->next;

j++;

}

}

printf(\"number not found\\n\") ;

}

void EmpPrint()

{

employee *p = s;

printf(\"the list of employees\\n\") ;

while(p !=NULL)

{

printf(\"%s\%d\%s\\n\",p->name,p->number,p->post) ;

p = p->next ;

}

}

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

{

int l ,m;

printf(\"create list,please enter the number of the employee\\n\");

scanf_s(\"%d\",&n) ;

InitComp() ;

EmpPrint() ;

while(1)

{

printf(\"enter number to choose action:1 for indert ,2 for delete\\n\") ;

scanf_s(\"%d\",&l) ;

switch(l)

{

case 1:

EmpInsert() ;

EmpPrint() ;

break ;

case 2:

printf(\"please enter the number of the employee you delete\\n\") ;

scanf_s(\"%d\",&m) ;

EmpDelete(m) ;

EmpPrint() ;

break ;

default:

EmpPrint() ;

}

}

system(\"pause\");

return 0;

}

2、 约瑟夫（Josephus）环问题：编号为1,2,3,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一人开始重新从1报数，如此下去，直到所有人全部出列为止。

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

#include \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

struct person

{

int num ;

int code ;

person *next ;

} ;

person *h ;

void CreaCircle()

{

int n ,i ;

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

printf(\"please enterthr nember of people:\\n\");

scanf_s(\"%d\",&n) ;

for(i = 1; i < n+1; i++)

{

p = (person *) malloc(sizeof(person)) ;

p->num = i ;

printf(\"please enter the code of the %d person:\\n\",i);

scanf_s(\"%d\",&p->code) ;

p->next = NULL ;

if(i ==1)

{

h = p ;

q = p ;

}

q->next = p ;

q = p ;

}

q->next = h ;

}

void RunGame()

{

int m , i;

person * r , * t = h;

printf(\"please enter the first code :\\n\") ;

scanf_s(\"%d\",&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(\"the %d person is kicked\\n\",r->num);

}

}

int main(){

CreaCircle() ;

RunGame() ;

system(\"pause\");

return 0 ;

}

栈和队列

3、 某商场有一个100个车位的停车场，当车位未满时，等待的车辆可以进入并计时；当车位已满时，必须有车辆离开，等待的车辆才能进入；当车辆离开时计算停留的的时间，并且按照每小时1元收费。

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

#include

#include \"time.h\"

#include \"stdlib.h\"

#include

#include \"stdio.h\"

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(\"ParkList:\\n\");

for(int j=0;j{

printf(\"%d %s\\n\",pc[j].carnumber,ctime(&pc[j].entertime));

}

printf(\"\\n\");

}

}

void showWaitList(WaitList WL){

WaitList p = WL;

printf(\"WaitList:\\n\");

while(p){

printf(\"%d %s\\n\",p->WaitCar.carnumber,ctime(&(p->WaitCar.entertime)));

p = p->next;

}

}

void showLeaveList(LeaveList L){

LeaveList p = L->next;

printf(\"LeaveList:\\n\");

while(p){

printf(\"%d %s\\n\",p->LeaveCar.carnumber,

ctime(&(p->LeaveCar.entertime)));

printf(\"%s %d\\n\",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 \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

typedef struct Cost

{

int num ;

Cost * next ;

}Cost , * CostList ;

void InitCL(CostList & CL , int number)

{

CL = (CostList)malloc(sizeof(Cost)) ;

CL->num = number ;

CL->next = NULL ;

}

void PutCL(CostList & CL , int number)

{

CostList p = CL , q;

if(CL == NULL)

InitCL(CL , number) ;

else

{

while(p->next)

p = p->next ;

q= (CostList)malloc(sizeof(Cost)) ;

q->num = number ;

p->next = q;

q->next = NULL ;

}

}

void PopCL(CostList & CL , int & number)

{

CostList p = CL ;

if(CL == NULL)

number = 0 ;

else

{

number = CL->num ;

CL = CL->next ;

free( p ) ;

}

}

void ShowCL(CostList & CL)

{

CostList p = CL ;

while(p)

{

printf(\"%d \",p->num ) ;

p = p->next ;

}

printf(\"\\n\") ;

}

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.业务办理完成\\n5.显示当前窗口营业状态\\n6.显示当前排队情况\\n\") ;

scanf_s(\"%d\",&n) ;

switch(n)

{

case 1 :

i++ ;

printf(\"您的序号为：%d\\n\",i) ;

if(CL1 == NULL)

InitCL(CL1 , i) ;

else

PutCL(CL1 , i) ;

break ;

case 2 :

i++ ;

printf(\"您的序号为：%d\\n\",i) ;

if(CL2 == NULL)

InitCL(CL2 , i) ;

else

PutCL(CL2 , i) ;

break ;

case 3 :

i++ ;

printf(\"您的序号为：%d\\n\",i) ;

if(CL3 == NULL)

InitCL(CL3 , i) ;

else

PutCL(CL3 , i) ;

break ;

case 4 :

printf(\"正在营业的窗口:\\n\") ;

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

{

if(a[j] != 0)

printf(\"%d \",j+1) ;

}

printf(\"\\n\");

printf(\"请选择业务办理完成的窗口号：\\n\") ;

scanf_s(\"%d\",&m) ;

a[m-1] = 0;

break ;

case 5 :

printf(\"窗口营业情况:\\n\") ;

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

{

if(a[j] != 0)

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

}

break ;

case 6 :

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

ShowCL(CL1) ;

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

ShowCL(CL2) ;

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

ShowCL(CL3) ;

}

if(a[0] == 0)

{

PopCL(CL1 ,costnum) ;

a[0] = costnum ;

}

if(a[4] == 0)

{

PopCL(CL3 , costnum) ;

a[4] = costnum ;

}

if(a[5] == 0)

{

PopCL(CL3 , costnum) ;

a[5] = costnum ;

}

if(a[1] == 0)

{

if(CL2 != NULL)

{

PopCL(CL2 , costnum) ;

a[1] = costnum ;

}

else

{

PopCL(CL3 , costnum) ;

a[1] = costnum ;

}

}

if(a[2] == 0)

{

if(CL2 != NULL)

{

PopCL(CL2 , costnum) ;

a[2] = costnum ;

}

else

{

PopCL(CL3 , costnum) ;

a[2] = costnum ;

}

}

if(a[3] == 0)

{

if(CL2 != NULL)

{

PopCL(CL2 , costnum) ;

a[3] = costnum ;

}

else

{

PopCL(CL3 , costnum) ;

a[3] = costnum ;

}

}

}

system(\"pause\") ;

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 \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

int f[100] = {0,0,0,1};

int count = 4 ;

struct number

{

int n ;

number * next ;

} ;

number * h ;

void InitCircle()

{

int i ;

number * p , * q = NULL ;

for(i = 1 ; i < 5 ; i++)

{

p = (number *)malloc(sizeof(number)) ;

p->n = 0 ;

p->next = NULL ;

if(i == 1)

{

h = p ;

q = p ;

}

q->next = p ;

q = p ;

}

q->next = h ;

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

}

void run()

{

number * p =h ;

while(p->n < 200 && p->n + p->next->n < 200 && p->next->next->n < 200 && p->next->next->next->n < 200){

p->n = p->n + p->next->n + p->next->next->n + p->next->next->next->n ;

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

p = p->next ;

}

count-- ;

}

void print()

{

int i ;

printf(\"here are fibonaccique number within 200 :\\n\") ;

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

printf(\"%d\\n\",f[i]) ;

}

int _tmain()

{

InitCircle() ;

run() ;

print() ;

system(\"pause\") ;

return 0 ;

}

5、 八皇后问题：设8皇后问题的解为 (x1, x2, x3, …,x8), 约束条件为：在8x8的棋盘上，其中任意两个xi 和xj不能位于棋盘的同行、同列及同对角线。要求用一位数组进行存储，输出所有可能的排列。

#include \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

#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-- ;

jj-- ;

if(a[ii] == jj)

ok = 0 ;

}

ii = i - 1 ;

jj = j ;

while((ii > 0)&&(jj{

ii-- ;

jj++ ;

if(a[ii] == jj)

ok = 0 ;

}

return ok ;

}

void queen(int i)

{

if(i <= N )

{

for(int j = 1 ;j <= N ;j++)

{

if(position(i,j))

{

a[i-1] = j ;

queen(i+1) ;

}

}

}

else

{

count++ ;

printf(\"the %d way to position:\\n\", count);

for(int j = 1 ;j <= N ;j++)

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

printf(\"\\n\\n\") ;

for(int i = 0 ;i < N ;i++)

{

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

for(int j = 0 ;j < N ;j++)

{

printf(\"%d \\",b[i][j]);

}

printf(\"\\n\");

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

}

}

}

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

{

queen(1) ;

system(\"pause\") ;

return 0;

6、 }

数组与广义表

10、 鞍点问题： 若矩阵A中的某一元素A[i,j]是第i行中的最小值，而又是第j列中的最大值，则称A[i,j]是矩阵A中的一个鞍点。写出一个可以确定鞍点位置的程序。

#include \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

void found()

{

int m , n , i , j , b , k , q , f = 1;

printf(\"请输入数组行数：\\n\") ;

scanf_s(\"%d\",&m) ;

printf(\"请输入数组列数：\\n\") ;

scanf_s(\"%d\",&n) ;

int *a = (int*)malloc(sizeof(int)*m*n) ;

printf(\"请输入数组值：\\n\") ;

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

{

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

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

}

printf(\"输入数组为：\\n\");

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

{

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

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

printf(\"\\n\");

}

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

{

b = *(a+i*m) ;

q = 0 ;

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

{

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

{

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

q = j ;

}

}

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

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(\"pause\") ;

return 0;

11、 }

12、 稀疏矩阵转置： 输入稀疏矩阵中每个元素的行号、列号、值，建立稀疏矩阵的三元组存储结构，并将此矩阵转置，显示转置前后的三元组结构。

#include \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

typedef struct

{

int i , j , v ;

}Triple ;

typedef struct

{

Triple data[100] ;

int ii , jj , cc ;

}Matrix ;

void In_Mat(Matrix * m)

{

printf(\"请输入矩阵行数：\\n\") ;

scanf_s(\"%d\",&m->ii) ;

printf(\"请输入矩阵列数：\\n\") ;

scanf_s(\"%d\",&m->jj) ;

printf(\"请输入非零元素个数：\\n\") ;

scanf_s(\"%d\",&m->cc) ;

printf(\"请依次输入非零元素所在的行数、列数和其值：\\n\") ;

for(int c = 0 ; c < m->cc ; c++)

scanf_s(\"%d%d%d\",&m->data[c].i , &m->data[c].j , &m->data[c].v) ;

}

void Out_Mat(Matrix m)

{

printf(\"行\列\值\\n\") ;

for(int c = 0 ; c < m.cc ; c++)

printf(\"%d\%d\%d\\n\",m.data[c].i , m.data[c].j , m.data[c].v) ;

}

void Tra_Mat(Matrix * m ,Matrix * n)

{

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 ;

}

}

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

{

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(\"pause\");

return 0;

13、 }

树和二叉树

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

14、 按先序遍历的扩展序列建立二叉树的存储结构

15、 二叉树先序、中序、后序遍历的递归算法

16、 二叉树中序遍历的非递归算法

17、 二叉树层次遍历的非递归算法

18、 求二叉树的深度(后序遍历)

#include \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

typedef struct BiTr

{

int data ;

struct BiTr * lc , * rc ;

}BiTr , * BT ;

struct

{

BT q[100] ;

int h , r ;

}queue ;

void CrBiTr(BT & b)

{

int a ;

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

printf(\"请输入该结点的值,值为零表示删除该结点：\\n\") ;

scanf_s(\"%d\",&a) ;

if(a == 0)

b = NULL ;

else

{

b->data = a ;

CrBiTr(b->lc) ;

CrBiTr(b->rc) ;

}

}

void visit(BT b)

{

printf(\"%d\\" , b->data) ;

}

void PreOrderTraverse(BT b)

{

visit(b) ;

PreOrderTraverse(b->lc);

PreOrderTraverse(b->rc);

}

void InOrderTraverse(BT b)

{

InOrderTraverse(b->lc);

visit(b) ;

InOrderTraverse(b->rc);

}

void PostOrderTraverse(BT b)

{

PreOrderTraverse(b->lc);

PreOrderTraverse(b->rc);

visit(b) ;

}

void InOrderTraverse1(BT b)

{

BT s[500] , p ;

int i = -1 ;

p = b ;

while(p)

{

if(p)

{

i++ ;

s[i] = p;

p = p->lc ;

}

else

{

p = s[i];

i--;

printf(\"%d\\",p->data);

p = p->rc ;

}

}

}

void CengciTraverse(BT b)

{

BT p = b ;

queue.h = 0 ;

queue.r = 0 ;

if(b)

printf(\"%d\",p->data) ;

queue.q[queue.r] = p ;

queue.r++ ;

while(queue.h < queue.r)

{

p = queue.q[queue.h] ;

queue.h++ ;

if(p->lc)

{

printf(\"%d\",p->lc->data) ;

queue.q[queue.r] = p->lc ;

queue.r++ ;

}

if(p->rc)

{

printf(\"%d\",p->rc->data) ;

queue.q[queue.r] = p->rc ;

queue.r++ ;

}

}

}

int Depth(BT b)

{

int dep = 0 ,dep1 ,dep2 ;

if (b = NULL)

return 0 ;

else

{

dep1 = Depth(b->lc) ;

dep2 = Depth(b->rc) ;

if(dep1 > dep2)

dep = dep1 + 1 ;

else

dep = dep2 + 1 ;

return dep ;

}

}

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

{

int a = 1;

BT b = NULL ;

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

printf(\"1.按先序遍历的扩展序列建立二叉树的存储结构：\\n\") ;

printf(\"2.二叉树先序、中序、后序遍历的递归算法：\\n\") ;

printf(\"3.二叉树中序遍历的非递归算法：\\n\") ;

printf(\"4.二叉树层次遍历的非递归算法：\\n\") ;

printf(\"5.求二叉树的深度(后序遍历)：\\n\") ;

scanf_s(\"%d\",&a) ;

while(a != 0)

{

switch(a)

{

case 1 :

{

printf(\"开始创建：\\n\") ;

CrBiTr(b) ;

break ;

}

case 2 :

{

printf(\"先序遍历如下：\\n\") ;

PreOrderTraverse(b) ;

printf(\"中序遍历如下：\\n\") ;

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(\"pause\") ;

return 0;

}

19、 建立树的存储结构

20、 求树的深度

#include \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

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(\"%d\",&a) ;

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(\"%d\", Depth(p)) ;

system(\"pause\") ;

return 0;

}

图

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

#include \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

typedef struct

{

int v ,e ;

int edges[10][10] ;

}Mgraph ;

void create(Mgraph & m)

{

int s , t;

printf(\"请输入网的顶点个数：\\n\");

scanf_s(\"%d\",&(m.v)) ;

printf(\"请输入网的边数：\\n\");

scanf_s(\"%d\",&(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条边的顶点：\",i+1);

scanf_s(\"%d%d\",&s,&t) ;

printf(\"请输入第%d条边的权值：\",i+1);

scanf_s(\"%d\",&(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\",s,t,m.edges[s][t]) ;

}

for(int i = 0 ; i < 10 ; i++)

{

if(a[i] == 1)

c = 1 ;

}

shortest = 100 ;

}

printf(\"最小生成树的总长度为：%d\\n\",route) ;

}

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

{

Mgraph mg ;

create(mg) ;

MiniSpanTree(mg , 1) ;

system(\"pause\") ;

return 0;

}

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

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

#include \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

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(\"%d%d\",&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(\"%d%d%d\",&v1,&v2,&w) ;

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(\"%d\\n\",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;iif(!visited[i])

DFS(G,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(\"%d\\n\",u+1) ;

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(\"pause\");

return 0;

}

查找

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

#include \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

typedef struct tree

{

struct tree *left;

struct tree *right;

int key;

} BSTNode , * BSTree;

void insertBST(BSTree &T,int key)

{

BSTree f = NULL , p = T;

while(p)

{

if(p->key == key)

return ;

f = p;

if(key < p->key)

p = p->left ;

else

p = p->right ;

}

p = (BSTree)malloc(sizeof(BSTNode));

p->key = key ;

p->left = p->right = NULL;

if(T == NULL)

T = p;

else

{

if(key < f->key)

f->left = p;

else

f->right = p;

}

}

void createBST(BSTree &t)

{

int key;

printf(\"请输入第一个结点的值（0表示结束）：\\n\") ;

scanf_s(\"%d\",&key);

while(key != 0)

{

insertBST(t , key);

printf(\"请输入下一个结点的值（0表示结束）：\\n\") ;

scanf_s(\"%d\" , &key);

}

}

void InOrder(BSTree t)

{

BSTree p = t;

if(p != NULL)

{

InOrder(p->left);

printf(\"中序遍历当前二叉树：\\n\") ;

printf(\"%d\\",p->key );

InOrder(p->right );

}

}

int searchBST(BSTree t , int key)

{

if(key == t->key)

return 1;

if(t==NULL)

return 0;

if(keykey)

return searchBST(t->left , key);

else

return searchBST(t->right , 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 ;

else

p = p->right ;

}

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(\"\\n\\n中序遍历二叉树:\");

InOrder(t);

printf(\"输入你要删除结点的关键字：\\n\");

scanf_s(\"%d\",&key);

t=deleteBST(t,key);

if(t==NULL)

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

else

printf(\"\\n成功删除结点%d.\\n\",key);

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

InOrder(t);

system(\"pause\") ;

return 0;

}

24、 设定哈希函数 H(key) = key MOD 11 ( 表长=11 )，输入一组关键字序列，根据线性探测再散列解决冲突的方法建立哈希表的存储结构，显示哈希表，任意输入关键字，判断是否在哈希表中。

#include \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

#include \"math.h\"

typedef struct

{

int data ;

}elemtype ;

typedef struct SQList

{

elemtype * elem ;

}SQList ;

void Insert(SQList &s , int i)

{

int a = i % 11 ;

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

s.elem[a].data = i ;

else

{

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

{

if(a == 11)

a = 1 ;

else

a = a + 1 ;

}

s.elem[a].data = i ;

}

}

void Print(SQList s)

{

printf(\"哈希表存储如下：\") ;

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

{

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

}

}

int Search(SQList s , int a)

{

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

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

return 1 ;

return 0 ;

}

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(\"%d\",&a) ;

Insert(s , a) ;

}

Print(s) ;

system(\"pause\") ;

return 0;

}

排序

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

25、折半插入排序

26、冒泡排序

27、快速排序

28、简单选择排序

29、归并排序

30、堆排序

#include \"stdafx.h\"

#include \"stdio.h\"

#include \"stdlib.h\"

typedef struct

{

int data ;

}elemtype ;

typedef struct SQList

{

elemtype * elem ;

int len ;

}SQList ;

void Create(SQList &s)

{

printf(\"请输入数字个数：\\n\") ;

scanf_s(\"%d\",&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(\"%d\",&(s.elem[i].data)) ;

}

}

void Print(SQList s)

{

printf(\"线性表输出如下：\\n\");

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

printf(\"%d\\",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)

{

m=(low+high)/2;

if(L.elem[0].keyhigh=m-1;

else low=m+1;

}

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

L.r[j+1]=L.r[j];//记录后移

L.r[high+1]=L.r[0];//插入

}

}

void 冒泡排序(SQList &s)

{

int i = s.len ;

while(i > 1)

{

int last = 1 ;

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

{

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 ;

}

}

i = last ;

}

}

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

{

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

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

while(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] ;

}

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

return low ;

}

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

{

if(i < j)

{

int pivotloc = Partition(s,i,j) ;

快速排序(s , i , pivotloc-1) ;

快速排序(s , pivotloc+1 , j) ;

}

}

int SelectMindata(SQList s , int i)

{

int MK = i ;

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

{

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

MK = j ;

}

return MK;

}

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

{

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

{

int j = SelectMindata(s,i) ;

if(i != j)

{

s.elem[0]=s.elem[j] ;

s.elem[j]=s.elem[i] ;

s.elem[i]=s.elem[0] ;

}

}

}

void Merge(elemtype SR[],elemtype TR[],int i,int m,int n)

{

int j,k;

for(j=m+1,k=i;i<=m && j<=n;++k)

{

if(SR[i].dataTR[k]=SR[i++];

else

TR[k]=SR[j++];

}

while(i<=m)

TR[k++]=SR[i++];

while(j<=n)

TR[k++]=SR[j++];

}

void MSort(elemtype SR[] , elemtype TR1[] , int i , int j)

{

int m ;

elemtype TR2[10] ;

if(i == j)

TR1[i] = SR[i] ;

else

{

m = (i + j) / 2;

MSort(SR , TR2 , i , m);

MSort(SR , TR2 , m+1 , j);

Merge(TR2 , TR1 , i , m , j);

}

}

void 归并排序(SQList &s)

{

MSort(s.elem , s.elem , 1 , s.len);

}

void HeapAdjust(SQList &s , int i , int j)

{

elemtype rc = s.elem[i];

for(int k = 2 * i ; k <= j ; k *= 2)

{

if(k < j&&s.elem[k+1].data > s.elem[k].data)

k++;

if(rc.data >= s.elem[k].data)

break;

s.elem[i] = s.elem[j];

i = k;

}

s.elem[i] = rc;

}

void 堆排序(SQList &s)

{

for(int i = s.len/2 ; i > 0 ; --i)

{

HeapAdjust(s , i , s.len);

}

for(int i = s.len ; i > 1 ; --i)

{

s.elem[0] = s.elem[i];

s.elem[i] = s.elem[1];

s.elem[1] = s.elem[0];

HeapAdjust(s,1,i-1);

}

}

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

{

SQList s ;

printf(\"生成线性表：\\n\") ;

Create(s) ;

Print(s) ;

printf(\"折半插入排序结果:\\n\") ;

折半插入排序(s) ;

Print(s) ;

printf(\"冒泡排序结果:\\n\") ;

冒泡排序(s) ;

Print(s) ;

printf(\"快速排序结果:\\n\") ;

快速排序(s , 1 , s.len) ;

Print(s) ;

printf(\"简单选择排序结果:\\n\") ;

简单选择排序(s) ;

Print(s) ;

printf(\"归并排序结果:\\n\") ;

归并排序(s) ;

Print(s) ;

printf(\"堆排序结果:\\n\") ;

堆排序(s) ;

Print(s) ;

system(\"pause\") ;

return 0;

}