數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)練習(xí)

實(shí)驗(yàn)一

#include<stdio.h>

#include<stdlib.h>

#defineMAXSIZE100

typedefintElemType;

typedefstructlist

(

日emType*elem;〃指針定義數(shù)組

intlistsize;

intlength;

JSqlist;

voidinitlist_sq(Sqlist*L)

{

L->elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));

if(!L->elem)exit(O);

L->length=O;

L->listsize=MAXSIZE;

}

〃在線性表L的第n個元素之前插入元素x

voidinsert_sq(Sqlist*L,intn,ElemTypex)

(

inti;

〃檢查插入位置n的合法性

if(n<1||n>L->length+1)

(

printf("插入的位置n非法！\n");

return;

)

〃檢查線性表是否為滿

iffL->length>=L->listsize)

(

printf("線性表滿了!\n");

return;

}

〃插入點(diǎn)之后的元素循環(huán)后移一個位置

for(i=L->length;i>=n;i-)

L->elem[i]=L->elem[i-l];

〃將代插入的元素存入到下標(biāo)為n-1的位置

L->elem[n-l]=x;

〃修改線性表的長度

L->length++;

〃利用插入方法實(shí)現(xiàn)創(chuàng)建指定長度的線性表L

voidcreat_sq(Sqlist*L)

(

inttablen,i=l;

ElemTypetemp;

printf(”請輸入順序表的長度\n“);

scanf("%d",&tablen);

print(請輸入%d個數(shù)據(jù)\n，tablen);

do

(

〃輸入待插入的元素temp

scanf("%d",&temp);

〃將元素temp插入到線性表L的第i個位置

insert_sq(L,i,temp);

〃修改i的值，以便下一次進(jìn)行插入

i++；

}while((i<=tablen)&&(i<L->listsize));

)

〃打印線性表中的所有元素

voiddisplay_sq(Sqlist*L)

(

inti;

i=0;

do

(

〃打印線性表L中下標(biāo)為i的元素

printf("%d\t”,L->elem[i]);

while(++i<L->length);

printf（"\n**********順序表打印完畢**********\n\n“）;

//在線性表L中查找元素x,若存在范圍其位置；若不存在返回0

intSearch_sq(Sqlist*L,ElemTypex)

(

inti;

i=0;

do

(

〃比較線性表中下標(biāo)為i的元素與指定值x是否相等，若相等，返回其位置i+1

if(L->elem[i]==x)

returni+1;

}while(++i<L->length);

return0;

}

〃查找線性表L中的第n個元素，返回其值

ElemTypeSearch_sq_byV(Sqlist*L,intn)

(

〃檢查n的取值是否合法，若非法返回0

if(n<111n>L->length)

return0;

〃若n取值合法，返回線性表L中下標(biāo)為n-l的元素

returnL->elem[n-l];

)

〃刪除線性表L中的第n個元素

voiddelete_sq(Sqlist*L,intn)

{

inti;

〃檢查刪除的位置n的合法性

if(n<111n>L->length)

{

printf("刪除的位置n非法!\n");

exit(O);

)

〃若n合法，則刪除點(diǎn)之后的元素循環(huán)向前移動一個位置

i=n;

do

(

〃刪除點(diǎn)之后的元素前移一個位置

L->elem[i-l]=L->elem[i];

}while(++i<L->length);

〃線性表長度減少1

L->length-;

printf("\n**********%ddeleted**********^"^);

)

intmain(void)

(

SqlistLI;

ElemTypetemp;

charcmd;

inti=0;

initlist_sq(&Ll);

printf("X=退出,C=創(chuàng)建尸=打印/=插入,S=查找(按值),V二查找(按位置),D二刪除\n")；

while(l)

(

cmd=getchar();

switch(cmd)

{

case'C:

case'c':

creat_sq(&Ll);

printf(“X=退出,C=創(chuàng)建后打印,1二插入,S=查找(按值)，V二查找(按位置),D二刪除

\n")；

break;

caseT:

caseT:

printf(“請輸入要插入的數(shù)據(jù)：\n“)；

scanf("%d",&temp);

print",請輸入數(shù)據(jù)要插入的位置(l~100)：\n");

scanfC^d';&i);

insert__sq(&Ll,i+l,temp);

printf(”**********順序表插入完成********"\n\n“)；

printf(“X=退出,C=創(chuàng)建后打印,上插入,S=查找(按值)，V=查找(按位置),D二刪除

\n")；

break;

case'S':

case's':

printf(“請輸入要查找的數(shù)據(jù)：\n");

scanf("%d",&temp);

printf("%d\n",Search_sq(&Ll,temp));

printf("X=退出創(chuàng)建,片打印，上插入,S=查找(按值)，V=查找(按位置),D二刪除

\n");

break;

caseV:

case'v':

printf(“請輸入要查找數(shù)據(jù)的位置：\n")；

scanf("%d"z&i);

printf("%d\n",Search_sq_byV(&Ll,i));

printf(“X二退出工二創(chuàng)建片打印/二插入,S二查找(按值)，V=查找(按位置),D二刪除

\n")；

break;

case'P':

case'p':

display_sq(&Ll);

printf(“X=退出,C=創(chuàng)建后打印，匕插入,S二查找(按值)，V;查找(按位置),D二刪除

\n“)；

break;

case'D':

case'd':

printf(“請輸入要刪除元素的位置：");

scanf("%d"z&i);

delete_sq(&Ll,i);

printf(“X=退出,C=創(chuàng)建,白打印，上插入,S二查找(按值)，V=查找(按位置),D二刪除

\n")；

break;

case'X':

case'x':

free(Ll.elem);

return1;

default:break;

)

}

return1;

)

實(shí)驗(yàn)二

#include<stdio.h>

#include<stdlib.h>

#include<string.h>//chara[6]="abcd\O";charb[6];for()b[i]=a[i];

typedefstructnode

(

chardata[10];〃保存字符串9

structnode*next;

JListNode;

typedefListNode*LinkList;

〃==========用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表===========

LinkListCreatListRl()

(

charch[100],chl[10],c;

inti=0,j=0;

LinkListhead=(LinkList)malloc(sizeof(ListNode));〃生成頭結(jié)點(diǎn)

ListNode*s,*r;

r=head;

r->next=NULL;

printf("Input#toend");〃輸入代表輸入結(jié)束

printf("PleaseinputNode_data:");

n〃輸入各結(jié)點(diǎn)的字符串

scanf("%s/Ch);

do

(

c=*(ch+i++)；//ch:bat,cat,eat,A#

*(chl+j++)=c;//chi:bat,

if(c==7)

{//s->data:bat\O

s=(LinkList)malloc(sizeof(ListNode));

for(j=0;(j<10)&&*(chl+j)!=7；j++)*(s->data+j)=*(chl+j);

*(s->data+j)="\O';

//strcpy(s->data,chl);

〃為節(jié)點(diǎn)s的指針域賦值

s->next=NULL;//s->next=r->next;

〃將節(jié)點(diǎn)s連接在尾指針之后

r->next=s;

〃修改尾指針

r=s;

j=0;

)

)

while(c!='#');

returnhead;〃返回頭指針

)

〃==========按值查找結(jié)點(diǎn)，找到則返回該結(jié)點(diǎn)的位置，否則返回NULL

ListNode*LocateNode(LinkListhead,char*key)

ListNode*p=head->next;

inti=l;

while(p&&strcmp(p->data,key)!=O)

(

〃訪問下一個節(jié)點(diǎn)p

p=p->next;

〃計數(shù)器i記錄當(dāng)前節(jié)點(diǎn)的位序

i++；

)

if(P)

(

printf("thelocationofthenodeis:%d\n",i);

)

else

printf("thenodeisnotfound!\n");

returnp;〃若p=NULL則查找失敗，否則p指向找到的值為key的結(jié)點(diǎn)

)

〃二二二二二二二二二二打印鏈表中所有節(jié)點(diǎn)二二二二二二二

voidprintlist(LinkListhead)

(

ListNode*p=head->next;〃從開始結(jié)點(diǎn)打印

while(p)

(

〃打印節(jié)點(diǎn)P中的數(shù)據(jù)

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

〃將節(jié)點(diǎn)P變?yōu)槠浜罄^節(jié)點(diǎn)

p=p->next;

)

printf("\n");

)

〃刪除指定鏈表head中的值為key的節(jié)點(diǎn)

intDeleteNode(LinkListhead,char*key)

(

ListNode*p=head->next;

ListNode*q=head;

while(p&&strcmp(p->data,key)!=O)

(

〃將節(jié)點(diǎn)p后移

p=p->next;

〃同時將節(jié)點(diǎn)q后移

q=q->next;

if(p)〃找到p,則執(zhí)行刪除節(jié)點(diǎn)p

{

〃修改p的前驅(qū)q的指針域，讓其值為P的后繼

q->next=p->next;

〃釋放節(jié)點(diǎn)p所占據(jù)的存儲空間

free(p);

return1;

)

else

(

printf("Pisnotfinded!\n");

return0;

〃==========刪除所有結(jié)點(diǎn)，釋放空間===========

voidDeleteAII(LinkListhead)

(

ListNode*p=head,*r;

while(p->next)

(

r=p->next;

free(p);

P=r;

}

free(p);

)

〃在鏈表中第n個節(jié)點(diǎn)前插入新的節(jié)點(diǎn)，其數(shù)據(jù)為key

intinsert_sq(LinkListheadjntn,char*key)

(

intin=0,i=0;

ListNode*p=head,*s;

while)p->next)〃查找第n-1個節(jié)點(diǎn)，該節(jié)點(diǎn)為p

(

if(in++<n-1)

p=p->next;

else〃找到節(jié)點(diǎn)p時執(zhí)行插入操作

〃生成要插入的節(jié)點(diǎn)s

s=(ListNode*)malloc(sizeof(ListNode));

〃為節(jié)點(diǎn)s的數(shù)據(jù)域賦值

strcpy(s->data,key);

〃為節(jié)點(diǎn)S的指針域賦值

s->next=p->next;

〃將節(jié)點(diǎn)S插入到節(jié)點(diǎn)P之后

p->next=s;

return1;

}

}

if(p->next==NULL&&in==n-1)

(

〃生成要插入的節(jié)點(diǎn)s

s=(ListNode*)malloc(sizeof(ListNode));

〃為節(jié)點(diǎn)s的數(shù)據(jù)域賦值

strcpy(s->data,key);

〃為節(jié)點(diǎn)s的指針域賦值

s->next=p->next;

〃將節(jié)點(diǎn)s插入到節(jié)點(diǎn)p之后

p->next=s;

return1;

)

return-1;

)

〃==========主函數(shù)==========

main()

(

LinkListh;

ListNode*tx;

charcmd;

inti=0;

chartemp[100];

printf("X=EXIT/C=CREAT/P=DISPLA\；l=INSER-T；S=SEARCH\n");

while(l)

(

cmd=getchar();

switch(cmd)

case'C:

case'c':

h=CreatListRl();

,,

p^ntf("X=EXIT,C=CREAT/P=DISPLAY；l=INSERTS=SEARCH\n);

break;

caseT:

caseT:

printf("pleaseinputthenumbertobeinserted,endwith

scanf("%s"ztemp);

printf("pleaseinputthepositiontobeinserted\n");

scanf("%d",&i);

printf("%d\n",insert_sq(hjztemp));

printf("**********Sq「stinserted**********\n")*

printf("X=EXIT/C=CREAT/P=DISPLA\；l=INSER,S=SEARCT\n");

break;

caseS':

case's':

printf("pleaseinputthenumberwanted\n");

scanf("%s",temp);

tx=LocateNode(h,temp);

if(tx!=NULL)printf("thenodefoundis:%s\n"ztx->data);

elseprintf("thenodeisnotfound!\n");

printf("X=EXIT,C=CREAT,P=DISPLAXI=INSER-|；S=SEARC\nu);

break;

case'D':

case'd1:

printf("pleaseinputtheNodewanted\n");

seanf("%s”,temp);

if(DeleteNode(h,temp))printf("TheNodeDeleted!\n");

elseprintf("NodeDeletederror!\n");

printf(“X=EXIT,C=CREAT,P=DISPLAYI=INSERTS=SEARC\n“);

break;

case'P':

case*p':

printlist(h);

printf(“X=EXIT,C=CREAT,P=DISPLAYI=INSER[S=SEARC\n");

break;

case'X':

case'x':

DeleteAII(h);

return1;

default:break;

)

)

實(shí)驗(yàn)三

/*

本程序可以實(shí)現(xiàn)對一個表達(dá)式中括號是否匹配的判定，但是程序還有一定問題，請按注

釋修改；

另請修改程序，將其修改為：

可以選擇"1〃進(jìn)行下一個表達(dá)式括號匹配的判定，選擇〃0〃不再進(jìn)行表達(dá)式括號匹配判

定

7

#include"stdio.h"

include"stdlib.h"

typedefstruct

(

char*base;

char*top;

intstacksize;

Jsqstack;

〃二二二二二二二二二二棧s的初始化，此時棧s非空，其內(nèi)初始時有一個元素#======

voidinitstack(sqstack*s)

(

s->base=(char*)malloc(100*sizeof(char));

if(!s->base)exit(0);

*(s->base)='#';

s->top=s->base+l;

s->stacksize=100;

)

〃==========獲取棧s的棧頂元素======

chargettop(sqstack*s)

(

〃判定棧是否為空，若為空，請請輸出提示信息"?？?并返回k

if(s->base==s->top)

(

printf("棧空!\n")；

return0;

if(s->top==s->base)exit(O);

return*(s->top-l);

)

〃==========在棧中插入一個新的元素e=======

voidpush(sqstack*s,char*e)

(

〃檢查棧是否為滿，若為滿，請輸出提示信息"棧滿"，并退出程序

if(s->base==s->top)

(

printf("棧空!\n");

return;

)

*(s->top++)=*e;

)

〃==========出棧操作=======

voidpop(sqstack*s)

(

〃判定棧是否為空，若為空，請輸出提示信息"?？?，并退出程序

if(s->base+s->stacksize==s->top)

(

printf("?？?\n");

return;

)

s->top-;

)

voidmain()

(

chara[30],*c;

intflag=0;

intchoice=1;

sqstacksq;

while(choice)

(

flag=0;

initstack(&sq);

printf("shurubiaodashi:\n");

scanf("%s"za);

c=a;

while(*c!=*\0,)

(

if(*c=='('||*c=='['||*c==*{,)

push(&sq,c);

if(*c==')')

if(gettop(&sq)=='(')

pop(&sq);

else

(

printf("no\n");

flag=1;

break;

)

if(*c==']')

if(gettop(&sq)=='[')

pop(&sq);

else

(

printf("no\n");

flag=1;

break;

}

if(*c=='}1)

if(gettop(&sq)=='{,)

pop(&sq);

else

(

printf("no\n");

flag=1;

break;

)

C++；

)

if(!flag)

if(gettop(&sq)=='#')

printf("yes\n");

else

printfC'noXn");

printf。請輸入你的選擇：1繼續(xù)，0退出\n“);

scanf("%d",&choice);

實(shí)驗(yàn)四

#include',stdio.h"

#include"stdlib.h"

#defineElemTypeint

typedefstructqnode〃定義記錄類型

(

intdata;〃節(jié)點(diǎn)數(shù)據(jù)域?yàn)閐ata

structqnode*next;

}QNode;

typedefstruct

(

QNode*front,*rear;

JQuType;

〃在隊列qu中查找一個節(jié)點(diǎn)，其數(shù)據(jù)域的值為Num,找到返回L否則返回口

intQuSearch(QuType*qu,intNum)

(

QNode*p=qu->front;

〃循環(huán)查找節(jié)點(diǎn)p,p的數(shù)據(jù)域的值為Num

while(p&&p->data!=Num)

p=p->next;

〃找到數(shù)據(jù)域值為Num的節(jié)點(diǎn)，返回1

if(p)//if(p->data==no)??

return1;

else

return-1;

)

〃打印隊列中所有的元素

voidQuDisplay(QuType*qu)

(

QNode*p=qu->front;

inti=l;

if(p==NULL)

(

printf("******沒有排隊者******\n");

}

while(p!=NULL)

(

printf("第％d個排隊者為:％5d\n",i++,p->data);

p=p->next;

}

)

〃入隊操作，在隊列qu中插入節(jié)點(diǎn)，該節(jié)點(diǎn)的數(shù)據(jù)域的值為Num

intEnQueue(QuType*qu,intNum)

QNode*q=(QNode*)malloc(sizeof(QNode));

if(q==NULL)return-1;

〃節(jié)點(diǎn)q為即將插入的新節(jié)點(diǎn)，為其數(shù)據(jù)域賦值為Num,指針域賦值為NULL

q->data=Num;

q->next=NULL;

if(qu->rear==NULL)〃插入前隊列中沒有節(jié)點(diǎn)，如何插入新節(jié)點(diǎn)

(

qu->front=q;

qu->rear=q;

)

else//插入前隊列中有若干節(jié)點(diǎn)，如何插入新節(jié)點(diǎn)

(

qu->rear->next=q;

qu->rear=q;

)

return1;

)

〃出隊操作，刪除隊列中的隊頭節(jié)點(diǎn)，并用Num保存刪除節(jié)點(diǎn)的數(shù)據(jù)

intOutQueue(QuType*qu,int*Num)

(

QNode*p=qu->front;

〃判斷隊列是否為空，若隊列為空，則返回-1

if(p==NULL)

return-1;

else〃若隊列非空，則刪除隊頭節(jié)點(diǎn)

(

〃使用Num獲取隊頭節(jié)點(diǎn)數(shù)據(jù)域的值

*Num=p->data;

〃隊列中只有一個節(jié)點(diǎn)p,刪除方法？

if(p==qu->rear)

qu->front=qu->rear=NULL;

〃隊列中有多于1個節(jié)點(diǎn)的時候，刪除隊頭節(jié)點(diǎn)P的方法？

else

qu->front=p->next;

free(p);

return1;

}

〃判空隊列，若為空返回1,否則返回

intQueueEmp(QuType*qu)

(

〃隊列為空的條件？

if(qu->front==NULL)

return1;

else

return-1;

)

voidmain(void)

(

intsel,no,temp,flag=l;

QuType*qu;

qu=(QuType*)malloc(sizeof(QuType));

qu->front=qu->rear=NULL;

while(l==flag)

(

printf("\nl:排隊2：就診3：查看隊列4：不再排隊，余下就診5：下班\n

請選擇>>");

scanf("%d",&sel);

switch(sel)

(

case1:

print->>輸入病歷號：”);

scanf("%d",&no);

while(l=QuSearch(qu,no))〃輸入后需要判斷是否重復(fù)

(

prints輸入病歷號重復(fù)，請重新輸入>>")；

scanf("%d",&no);

)

EnQueue(qu,no);

break;

case2:

if(OutQueue(qu,&temp)==-1)

printf(“******沒有排隊的病人******\n“)；

else

printf("病歷號為％d的請就診\n",temp);

break;

case3:

QuDisplay(qu);

break;

case4:

if(QueueEmp(qu)==l)

print"'******沒有排隊的病人******\n“)；

else

(

printf("病人按如下順序就診\n”);

QuDisplay(qu);

)

flag=O;

break;

case5:

printf("己下班，請排隊的病人明天就醫(yī)！\n")；

flag=O;

break;

default:

break;

)

)

getchar();

)

實(shí)驗(yàn)五

#include<stdio.h>

#include<stdlib.h>

//二叉樹的二叉鏈表存儲表示

typedefstructbitnode

(

chardata;

structbitnode*lchild,*rchild;

Jbitnode,*bitree;

〃==========先序遍歷構(gòu)造二叉樹t=======

bitreecreatebitree()

(

charc;

bitreet;

printf("pleaseinputaword:\n");

getchar();

c=getchar();

if(c=='.')

t=NULL;

else

//為樹中節(jié)點(diǎn)t分配存儲空間

t=(bitree)malloc(sizeof(bitnode));

〃為節(jié)點(diǎn)t數(shù)據(jù)域賦值為獲取的字符c

t->data=c;

//為節(jié)點(diǎn)t左子樹賦值

t->lchild=createbitree();

〃為節(jié)點(diǎn)t右子樹賦值

t->rchild=createbitree();

}

returnt;

)

〃==========中序遍歷二叉樹t==========

voidinordertraverse(bitreet)

{

if(t)

(

//中序遍歷t的左子樹

inordertraverse(t->lchild);

〃訪問(打印)t的數(shù)據(jù)域

printf("%c\t",t->data);

〃中序遍歷t的右子樹

inordertraverse(t->rchild);

〃===========前序遍歷===============

voidpretraverse(bitreet)

(

if(t)

(

〃訪問(打印)t的數(shù)據(jù)域

printf("%c\t",t->data);

〃先序遍歷t的左子樹

pretraverse(t->lchild);

〃先序遍歷t的右子樹

pretraverse(t->rchild);

〃===========后序遍歷===============

voidbacktraversefbitreet)

(

if(t)

(

〃后序遍歷t的左子樹

backtraverse(t->lchild);

〃后序遍歷t的右子樹

backtraverse(t->rchild);

〃訪問(打印)t的數(shù)據(jù)域

printf("%c\t",t->data);

)

voiddelete_all(bitreet)

(

if(t)

(

〃刪除t的左子樹

delete_all(t->lchild);

〃刪除t的右子樹

delete_all(t->rchild);

〃訪問(打印)t的數(shù)據(jù)域，并刪除節(jié)點(diǎn)t

printf("%c\t",t->data);

free(t);

}

)

voidmain()

(

bitreeT;

charcmd;

printf("C:CreateTreekinorderP:PreOrderB:backOrder\n")；

while(l)

(

cmd=getchar();

switch(cmd)

case'C:

case'c':

T=createbitree();

printf("TheTreewasCreated!\nH);

break;

caseT:

caseT:

inordertraverse(T);

printf("\n");

break;

caseP:

case'p':

pretraverse(T);

printf("\n")；

break;

case'B':

case'b':

backtraverse(T);

printf("\n");

break;

case'X':

case*x*:

delete_all(T);

printf("\n");

exit(O);

default:break;

)

printf("C:CreateTreel:lnorderP:PreOrderB:backOrder\n");

getchar();

)

getchar();

)

實(shí)驗(yàn)六

#include<stdio.h>

#include<stdlib.h>

#defineMAX_VERTEX_NUM20〃最大頂點(diǎn)數(shù)

typedefintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];〃鄰接矩陣類型

typedefintVertexType;

〃鄰接矩陣定義

typedefstruct

VertexTypevexs[MAX_VERTEX_NUM];〃頂點(diǎn)表

AdjMatrixarcs;〃鄰接矩陣

intvexnum,arcnum;〃圖的頂點(diǎn)數(shù)和弧數(shù)

}MGraph;〃用鄰接矩陣表示的圖的類型MGraph

〃鄰接表定義

〃邊結(jié)點(diǎn)類型定義(鏈表中的節(jié)點(diǎn)類型定義)

typedefstructArcNode

(

intadjvex;

structArcNode*nextarc;

intinfo;

JArcNode;

〃鄰接表定義(表中頭節(jié)點(diǎn)類型定義)

typedefstructVNode

(

VertexTypedata;

ArcNode*firstarc;

}VNode,AdjList[MAX_VERTEX_NUM];

〃用鄰接表表示的圖的類型ALGraph的定義

typedefstruct

{

AdjListvertices;〃鄰接表

intvexnum,arcnum;

JALGraph;

#defineINF32767

〃打印圖g的鄰接矩陣

voidDispMat(MGraph*g)

(

inti,j;

for(i=0;i<g?>vexnum;i++)〃建立鄰接矩陣

(

for0=O;j<g->vexnum;j++)

if(g->arcs[i][j]==INF)

',,,

printf(%3s/"—");

elseprintf("%3d",g->arcs[i][j]);

printf("\n");

〃圖用鄰接矩陣表示為g，用鄰接表表示為G,將g轉(zhuǎn)換成G

voidMatToList(MGraph*g,ALGraph*G)

inti,j,n=g->vexnum;

ArcNode*p;

//G=(ALGraph*)malloc(sizeof(ALGraph));

〃生成鄰接表，即n條帶頭結(jié)點(diǎn)的空的單鏈表

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

G->vertices[i].firstarc=NULL;

〃二重循環(huán)掃描鄰接矩陣

〃外重循環(huán)控制掃描鄰接矩陣的第i行

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

(

〃內(nèi)重循環(huán)控制掃描鄰接矩陣的第j歹U；掃描至右向左進(jìn)行

for(j=n-1;j>=0;j-)

(

if(g->arcs[i]U]!=0)〃若鄰接矩陣的第i行第j列元素非零

{

〃為邊節(jié)點(diǎn)p分配存儲空間

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

〃為節(jié)點(diǎn)P的數(shù)據(jù)域info賦值為非零元素的值

p->info=g->arcs[i][j];

〃為節(jié)點(diǎn)p的數(shù)據(jù)域adjvex賦值為非零元素的列標(biāo)j

p->adjvex=j;

〃為邊節(jié)點(diǎn)p的指針域賦值為第i條單鏈表的頭結(jié)點(diǎn)的指針域

p->nextarc=G->vertices[i].firstarc;

〃將邊節(jié)點(diǎn)p連接在第i條單鏈表的頭結(jié)點(diǎn)之后

G->vertices[i].firstarc=p;

}〃循環(huán)結(jié)束時，完成了圖G的鄰接表的生成

〃為圖G的屬性vexnum賦值

G->vexnum=g->vexnum;

〃為圖G的屬性arcnum賦值

G->arcnum=g->arcnum;

〃打印圖g的鄰接表

voidDispAdj(ALGraph*G)

inti;

ArcNode*p;

for(i=0;i<G->vexnum;i++)〃建立鄰接矩陣

(

p=G->vertices[i].firstarc;

if(p!=NULL)printf("%3d:"J);

while(p!=NULL)

(

n

printf("%3dzp->acljvex);

p=p->nextarc;

}

printfCXn1');

〃圖用鄰接矩陣表示為g，用鄰接表表示為G,將G轉(zhuǎn)換成g

voidListToMat(ALGraph*G,MGraph*g)

{

intiJ,n=G->vexnum;

ArcNode*p;

〃生成圖g的鄰接矩陣，初始化為n行n列的全0矩陣

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

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

g->arcs[i][j]=O;

〃循環(huán)訪問圖G的鄰接表，即訪問n條單鏈表

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

(

p=G->vertices[i].firstarc;

//p非空時，循環(huán)訪問鏈表中的節(jié)點(diǎn)

while(p)

(

//獲取節(jié)點(diǎn)p的數(shù)據(jù)域adjvex,并將其賦值給列標(biāo)j；

j=p->adjvex;

〃修改圖g的鄰接矩陣的第i行第j列的元素的值，將其改為節(jié)點(diǎn)P的數(shù)據(jù)域

info的值

g->arcs[i][j]=p->info;

〃修改節(jié)點(diǎn)P，讓其指向其后繼

p=p->nextarc;

}〃內(nèi)重循環(huán)完成對鄰接矩陣的第i行的修改

}〃外重循環(huán)結(jié)束時，圖g的鄰接矩陣生成完畢

〃為圖g的屬性vexnum賦值

g->vexnum=G->vexnum;

〃為圖g的屬性arcnum賦值

g->arcnum=G->arcnum;

)

voidmain(void)

(

MGraphg,gl;

ALGraph*G;

inti,j;

intA[][6]=

(

05,0,7,0,0},

00,4,0,0,0},

{8,0,0,0,0,9),

{0,0,5,0,0,6},

00,0,5,0,0},

{3,0,0,0,1,0}

}；〃鄰接矩陣內(nèi)容

g.vexnum=6;g.arcnum=10;

for(i=0;i<g.vexnum;i++)〃建立鄰接矩陣

(

for0=O;j<g.vexnum;j++)

g.arcs[i]U]=A[i][j];

)

printf("\n");

printf("有向圖G的鄰接矩陣為:\n");

DispMat(&g);

G=(ALGraph*)malloc(sizeof(ALGraph));

printf("SG的鄰接矩陣轉(zhuǎn)成鄰接表:\n");

MatToList(&g,G);

DispAdj(G);

prin計("圖G的鄰接表轉(zhuǎn)成鄰接矩陣：\n");

ListToMat(G,&gl);

DispMat(&gl);

getchar();

實(shí)驗(yàn)七

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#defineMENUprintf("l:直接插入排序(按學(xué)號)2：簡單選擇排序(按姓名)3：簡單

選擇排序(按學(xué)號)4：冒泡排序0：退出\n“)

#defineMAXSIZE100

typedefstructstu

{

longstuNo;

charstuName[10];

}ElemType;

typedefstructlist

(

ElemType*elem;

intlistsize;

intlength;

JSqlist;

ElemTypeStu[10]={{101J張三，{108J李四){102,“王五”},{109J孫進(jìn)“}，口04J趙六){103」'孫

儷，{106,"陳妍"},{105,"李靜周平"},{107,"鄭濤"}};

/**************初始順J^^^****************/

voidinitlist_sq(Sqlist*L)〃初始化順序表

(

L->elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));

if(!L->elem)exit(O);

L->length=O;

L->listsize=MAXSIZE;

}

/*********倉ij建順序表**********/

voidcreat_sq(Sqlist*L)

(

inttablen,i=0;

printf(“請輸入要創(chuàng)建的線性表的長度(小于10):");

scanf("%d",&tablen);

do

(

L->elem[i]=Stu[i];

i++；

L->length++;

}while(i<tablen);

}

/************打印線性表中元素*************/

voiddisplay_sq(Sqlist*L)〃打印線性表中的元素

inti;

i=0;

printfC序號學(xué)號姓名\n“);

do

printf("%-4d%-8d%-8s\n",i+l/(L->elem+i)->stuNo,(L->elem+i)->stuName);

)

while(++i<L->length);

printf("\n\n");

voidfz(Sqlist&LlzSqlistL)

intn=L.length;

for(inti=0;i<n;i++)

Ll.elem[i]=L.elem[i];

LI.length=n;

)

/*************************/

voidsort_insert_byName(SqIist*L)//按姓名直接插入排序

ElemTypetemp;

intiJ,t=O;

intn=L->length;

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

if(strcmp(L->elem[i].stuName,L->elem[i-l].stuName)<0)

temp=L->elem[i];

j=i-1；

do

L->elemO+l]=L->elem[j];

j-/

}while(strcmp(temp.stuName,L->elem[j].stuName)<0&&j>=0);

L->elemO+l]=temp;

}

)

I*************^E***************/

voidsort_insert_ByNo(Sqlist*L)//按學(xué)號直接插入排序

ElemTypetemp;

inti,Lt=O;

intn=L->length;

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

(

if(L->elem[i].stuNo<L->elem[i-l].stuNo)

(

temp=L->elem[i];

j=i-1;

do

(

L->elem[j+l]=L->elem[j];

j-；

}while(temp.stuNo<L->elem[j].stuNo&&j>=0);

L->elem[j+l]=temp;

)

)

)

/*************^1^^^^用**************/

voidsort_select_ByNo(Sqlist*L)//按學(xué)號排序

(

ElemTypetemp;

intiJt;

intn=L->length;

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

(

t=i;

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

(

if(L->elem[j].stuNo<L->elem[t].stuNo)

t=j；

}

if(t!=i)

(

temp=L->elem[t];

L->elem[t]=L->elem[i];

L->elem[i]=temp;

}

************按姓名簡單選擇排序***************/

voidsort_select_ByName(Sqlist*L)//按姓名排序

{

ElemTypetemp;

intijt;

intn=L->length;

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

(

t=i；

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

(

if(strcmp(L->elem[j].stuName,L->elem[t].stuName)<0)

t=j;

)

if(t!=i)

(

temp=L->elem[t];

L->elem[t]=L->elem[i];

L->elem[i]=temp;

)

}

/*************冒，包外F***************/

voidsort_bubble_ByNo(Sqlist*L)//按學(xué)號排序

ElemTypetemp;

intijflag;

intn=L->length;

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

flag=1;

for(j=0;j<n-l-i;j++)

if(L->elem[j].stuNo>L->elem[j+l].stuNo)

flag=0;

temp=L->elem[j];

L->elem[j]=L->elem[j+l];

L->elem[j+l]=temp;

}

if(flag)

break;

voidmain()

(

SqlistL,L1;

intch;

initlist_sq(&L);

initlist_sq(&Ll);

creat_sq(&L);

fz(Ll,L);

display_sq(&Ll);

MENU;

while(l)

(

printf(“請輸入你的選擇：");

scanf("%d"z&ch);

switch(ch)

(

case0:

exit(O);

break;

case1:

fz(Ll,L);

printf("排序前的數(shù)據(jù)為:\n");

display_sq(&Ll);

sort_insert_ByNo(&Ll);

printf("排序后的數(shù)據(jù)為:\n");

display_sq(&Ll);

MENU;

break;

case2:

fz(Ll,L);

prinH("排序前的數(shù)據(jù)為：\n");

display_sq(&Ll);

sort_select_ByName(&Ll);

printf("排序后的數(shù)據(jù)為:\n");