《數(shù)據(jù)結(jié)構(gòu)與算法》實(shí)驗(yàn)指導(dǎo)書(shū)范例和任務(wù)參考答案 張彬連

數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)指導(dǎo)書(shū)目錄TOC\o"1-2"\h\z\u第1章順序表 第1章順序表1、范例和任務(wù)參考答案#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAXSIZE100typedefstructStudent{charNo[8];//學(xué)號(hào)charname[16];//姓名charsex;//性別intenglish;//大學(xué)英語(yǔ)成績(jī)intmath;//高等數(shù)學(xué)成績(jī)}Student;typedefstructSqList{Student*elem;//存放學(xué)生信息空間的首地址intlength;//存放的學(xué)生人數(shù)}SqList;//范例1：初始化順序表LintInitSqList(SqList&L){//申請(qǐng)MAXSIZE個(gè)sizeof(Student)大小的內(nèi)存空間，然后將申請(qǐng)到的空間的地址強(qiáng)制轉(zhuǎn)換為Student*類型。L.elem=(Student*)malloc(MAXSIZE*sizeof(Student));if(L.elem==NULL)exit(-1);//退出程序L.length=0;//初始長(zhǎng)度為0return1;}//范例2：輸入n個(gè)學(xué)生信息（方法一），直接將學(xué)生信息輸入到順序表中。voidInputSqList1(SqList&L,intn){inti;for(i=0;i<n;i++){//以下讀入第i個(gè)學(xué)生的信息printf("第%d個(gè)學(xué)生的信息\n",i+1);fflush(stdin);//清空輸入緩沖區(qū)printf("學(xué)號(hào):");gets(L.elem[i].No);fflush(stdin);printf("姓名:");fflush(stdin);gets(L.elem[i].name);printf("性別：");scanf("%c",&L.elem[i].sex);printf("大學(xué)英語(yǔ)成績(jī)：");scanf("%d",&L.elem[i].english);printf("高等數(shù)學(xué)成績(jī)：");scanf("%d",&L.elem[i].math);}L.length=n;//有效數(shù)據(jù)長(zhǎng)度為n}//范例2：輸入n個(gè)學(xué)生信息（方法二），先定義輸入一個(gè)學(xué)生信息的函數(shù)InputOneStu()，//然后在輸入n個(gè)學(xué)生信息函數(shù)InputSqList()中調(diào)用該函數(shù)。voidInputOneStu(Student&stu){fflush(stdin);//清空輸入緩沖區(qū)printf("學(xué)號(hào):");gets(stu.No);fflush(stdin);printf("姓名:");fflush(stdin);gets();printf("性別：");scanf("%c",&stu.sex);printf("大學(xué)英語(yǔ)成績(jī)：");scanf("%d",&stu.english);printf("高等數(shù)學(xué)成績(jī)：");scanf("%d",&stu.math);}//范例2：輸入n個(gè)學(xué)生信息（方法二），先定義輸入一個(gè)學(xué)生信息的函數(shù)InputOneStu()，//然后在輸入n個(gè)學(xué)生信息函數(shù)InputSqList()中調(diào)用該函數(shù)。voidInputSqList(SqList&L,intn){inti;Studenttmpstu;for(i=0;i<n;i++){InputOneStu(tmpstu);L.elem[i]=tmpstu;}L.length=n;//數(shù)據(jù)元素個(gè)數(shù)為n}//范例3：根據(jù)學(xué)生姓名查找學(xué)生信息（方法一），查找后直接將學(xué)生信息輸出。voidSearchElemSqList1(SqListL,char*name){inti;for(i=0;i<L.length;i++)//從第一個(gè)學(xué)生開(kāi)始往后查看{if(strcmp(L.elem[i].name,name)==0)//如果有姓名為參數(shù)name的同學(xué){printf("學(xué)號(hào)：%s\n",L.elem[i].No);printf("姓名：%s\n",L.elem[i].name);printf("性別：%c\n",L.elem[i].sex);printf("大學(xué)英語(yǔ)成績(jī)：%d\n",L.elem[i].english);printf("高等數(shù)學(xué)成績(jī)：%d\n",L.elem[i].math);}}}//范例3：根據(jù)學(xué)生姓名查找學(xué)生信息（方法二），先定義函數(shù)SearchElemSqList()在順序表中查找，找到返回該元素的下標(biāo)，否則返回-1，//然后定義函數(shù)PrintStuInfo(),根據(jù)查找結(jié)果輸出學(xué)生信息。intSearchElemSqList(SqListL,char*name)//函數(shù)的返回值為int類型，表示下標(biāo){inti;for(i=0;i<L.length;i++){if(strcmp(L.elem[i].name,name)==0)//有姓名為參數(shù)name的同學(xué)returni;//返回元素所在的位置（下標(biāo)）}return-1;}//范例3：根據(jù)學(xué)生姓名查找學(xué)生信息（方法二），先定義函數(shù)SearchElemSqList()在順序表中查找，找到返回該元素的下標(biāo)，否則返回-1，//然后定義函數(shù)PrintStuInfo(),根據(jù)查找結(jié)果輸出學(xué)生信息。voidPrintStuInfo(SqListL,inti){printf("學(xué)號(hào)：%s\n",L.elem[i].No);printf("姓名：%s\n",L.elem[i].name);printf("性別：%c\n",L.elem[i].sex);printf("大學(xué)英語(yǔ)成績(jī)：%d\n",L.elem[i].english);printf("高等數(shù)學(xué)成績(jī)：%d\n",L.elem[i].math);}//為了檢測(cè)對(duì)順序表操作是否成功，定義函數(shù)PrintListInfo()輸出順序表中的學(xué)生信息。voidPrintListInfo(SqListL){inti;for(i=0;i<L.length;i++){printf("學(xué)號(hào)：%s\n",L.elem[i].No);printf("姓名：%s\n",L.elem[i].name);printf("性別：%c\n",L.elem[i].sex);printf("大學(xué)英語(yǔ)成績(jī)：%d\n",L.elem[i].english);printf("高等數(shù)學(xué)成績(jī)：%d\n",L.elem[i].math);}}//范例4：在順序表中指定的位置插入一個(gè)學(xué)生信息intInsertElemSqList(SqList&L,Studentstu,inti){//插入位置不在1到MAXSIZE之間，或者空間不夠if(i<1||i>MAXSIZE||L.length==MAXSIZE)return0;//空間夠但是位置不在1-L.length之間，插入到最后一個(gè)元素后面if(i>L.length&&i<=MAXSIZE){L.elem[L.length]=stu;L.length++;return1;}//將元素L.elem[L.length-1]到L.elem[i-1]逐個(gè)往后移動(dòng)一個(gè)位置for(intj=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];L.elem[i-1]=stu;//將x插入到順序表中L.length++;//順序表L的長(zhǎng)度加1return1;}//任務(wù)1：按照指定的格式打印學(xué)生信息，先定義函數(shù)PrintHeader()打印表頭,//然后定義函數(shù)PrintListInfo()輸出順序表中的學(xué)生信息，也可以在輸出學(xué)生信息時(shí)先定義輸出一個(gè)學(xué)生的信息，//在輸出函數(shù)中調(diào)用該函數(shù)逐個(gè)輸出學(xué)生信息。voidShowTitle(){printf("%-8s","學(xué)號(hào)");printf("%-10s","姓名");printf("%-6s","性別");printf("%-10s","大學(xué)英語(yǔ)");printf("%-10s\n","高等數(shù)學(xué)");}voidShowStuInfo(SqListL){inti;ShowTitle();for(i=0;i<L.length;i++){printf("%-8s",L.elem[i].No);printf("%-10s",L.elem[i].name);printf("%-6c",L.elem[i].sex);printf("%-10d",L.elem[i].english);printf("%-10d\n",L.elem[i].math);}}//任務(wù)2：根據(jù)學(xué)號(hào)刪除學(xué)生voidDeleteElemSqList(SqList&L,char*stuNo){inti,j;i=0;while(i<=L.length-1){if(strcmp(L.elem[i].No,stuNo)==0){for(j=i+1;j<L.length;j++){L.elem[j-1]=L.elem[j];}L.length--;printf("刪除成功！\n");return;}elsei++;}if(i>=L.length)printf("沒(méi)找到該學(xué)生！\n");}//任務(wù)3：順序表按照總成績(jī)從高到底排列，輸入一個(gè)學(xué)生信息后仍然按照成績(jī)從高到底排列。//假設(shè)順序表L中的學(xué)生信息已經(jīng)按成績(jī)從高到低排序，stu存儲(chǔ)了將要輸入的學(xué)生信息intInsertElemSqList(SqList&L,Studentstu){intj;if(L.length==0){L.elem[0]=stu;L.length=1;return1;}if(L.length<MAXSIZE){j=L.length-1;while(j>=0&&stu.english+stu.math>L.elem[j].english+L.elem[j].math){L.elem[j+1]=L.elem[j];j=j-1;}L.elem[j+1]=stu;L.length++;return1;}return0;}//任務(wù)4：將學(xué)生信息存入一個(gè)文件中voidSaveInfor_toFile(SqListL){FILE*fp;//1、定義文件指針inti;charfilename[20];fflush(stdin);//清空輸入緩沖區(qū)printf("請(qǐng)輸入文件名（如file1.dat）：");gets(filename);//輸入文件名if((fp=fopen(filename,"wb"))==NULL)//2、打開(kāi)輸出文件，file1.dat{printf("文件未打開(kāi)!\n");return;}for(i=0;i<L.length;i++){if(fwrite(&L.elem[i],sizeof(Student),1,fp)!=1)//3、向文件寫(xiě)數(shù)據(jù)printf("Filewriteerror!");}fclose(fp);//4、關(guān)閉文件printf("有%d位學(xué)生信息保存到文件中！\n",L.length);}//任務(wù)4：從文件中讀入學(xué)生數(shù)據(jù),并存入順序表中voidInputInfor_fromFile(SqList&L){FILE*fp;//1、定義文件指針inti;charfilename[20];//輸入文件名fflush(stdin);//清空輸入緩沖區(qū)printf("請(qǐng)輸入文件名（如file1.dat）：");gets(filename);if((fp=fopen(filename,"rb"))==NULL)//2、打開(kāi)輸入文件file1.dat{printf("文件未打開(kāi)!\n");return;}i=0;while(!feof(fp))//判斷文件是否讀完{if(fread(&(L.elem[i]),sizeof(Student),1,fp)!=1)//3、從文件讀數(shù)據(jù)break;i++;}fclose(fp);//4、關(guān)閉文件L.length=i;printf("讀取了%d位學(xué)生信息!\n",L.length);}//定義菜單函數(shù)intmenu_Select(){intc;printf("===============================================================\n");printf("|學(xué)生信息管理系統(tǒng)|\n");printf("||\n");printf("|1.錄入信息|\n");printf("|2.從文件中讀入信息|\n");printf("|3.瀏覽信息|\n");printf("|4.查詢信息|\n");printf("|5.刪除信息|\n");printf("|6.增加信息|\n");printf("|7.保存信息到文件|\n");printf("|8.退出系統(tǒng)|\n");printf("***************************************************************\n");printf("請(qǐng)輸入（1-8）進(jìn)行操作：\n");scanf("%d",&c);while(!(c>=1&&c<=8)){printf("選擇錯(cuò)誤（1-8之間），請(qǐng)重新輸入！\n");printf("請(qǐng)輸入（1-8）進(jìn)行操作：\n");fflush(stdin);//清空輸入緩沖區(qū)//scanf("%*[^\n]");//清空輸入緩沖區(qū)scanf("%d",&c);};returnc;}voidrun(){SqListstuList;//定義順序表if(InitSqList(stuList))//初始化順序表{//顯示菜單，選擇需要進(jìn)行的操作intselect=menu_Select();charout;intpos;while(1){if(select!=8){switch(select){case1:intn;printf("輸入學(xué)生人數(shù):");scanf("%d",&n);InputSqList(stuList,n);//輸入學(xué)生信息break;case2:InputInfor_fromFile(stuList);//從文件中讀入學(xué)生信息break;case3:ShowStuInfo(stuList);//輸出學(xué)生信息break;case4:charname[16];printf("輸入需要查找的學(xué)生姓名:");fflush(stdin);//清空輸入緩沖區(qū)scanf("%s",name);pos=SearchElemSqList(stuList,name);//根據(jù)姓名查詢信息if(pos>=0&&pos<stuList.length){printf("您查找的學(xué)生信息如下：\n");PrintStuInfo(stuList,pos);}elseprintf("名字為%s的學(xué)生不存在！\n",name);break;case5:charno[8];printf("輸入需要?jiǎng)h除的學(xué)生學(xué)號(hào):");fflush(stdin);//清空輸入緩沖區(qū)scanf("%s",no);DeleteElemSqList(stuList,no);//根據(jù)學(xué)號(hào)刪除學(xué)生信息break;case6:Studentstu;InputOneStu(stu);//輸入待插入的學(xué)生信息printf("輸入待插入的位置（>0）:");scanf("%d",&pos);InsertElemSqList(stuList,stu,pos);//在順序表中指定的位置插入一個(gè)學(xué)生break;case7:SaveInfor_toFile(stuList);//將學(xué)生信息保存到文件中break;}}else{fflush(stdin);//清空輸入緩沖區(qū)printf("確定退出嗎？Y/N");scanf("%c",&out);if(out=='Y')break;}select=menu_Select();printf("\n");}}else{printf("空間分配失??！\n");}}//主函數(shù)intmain(){run();return0;}

第2章鏈表1、范例以及任務(wù)1到任務(wù)3的參考答案#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructStudent{charNo[8];//學(xué)號(hào)charname[16];//姓名charsex;//性別intenglish;//大學(xué)英語(yǔ)成績(jī)intmath;//高等數(shù)學(xué)成績(jī)}Student;//定義結(jié)點(diǎn)類型。typedefstructLNode//定義結(jié)點(diǎn)類型{Studentdata;//數(shù)據(jù)部分structLNode*next;//指向下一個(gè)結(jié)點(diǎn)的指針}LNode,*LinkList;//LinkList為指向LNode的指針類型//范例1：建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表存放n個(gè)學(xué)生的信息//先初始化單鏈表intInitListList(LinkList&L){L=(LinkList)malloc(sizeof(LNode));if(L==NULL)//空間分配失敗exit(-1);L->next=NULL;return1;}//輸入一個(gè)學(xué)生的信息，存入stu中voidInputOneStu(Student&stu){fflush(stdin);//清空輸入緩沖區(qū)printf("學(xué)號(hào):");gets(stu.No);fflush(stdin);printf("姓名:");fflush(stdin);gets();printf("性別：");scanf("%c",&stu.sex);printf("大學(xué)英語(yǔ)成績(jī)：");scanf("%d",&stu.english);printf("高等數(shù)學(xué)成績(jī)：");scanf("%d",&stu.math);}//用尾插法建立長(zhǎng)度為n的單鏈表LvoidCreateLinkList_R(LinkListL,intn){inti;LNode*p,*r;Studentstu;r=L;//r指向當(dāng)前最后一個(gè)結(jié)點(diǎn)printf("輸入%d個(gè)數(shù)據(jù)：\n",n);for(i=0;i<n;i++){//生成結(jié)點(diǎn)pp=(LinkList)malloc(sizeof(LNode));//輸入數(shù)據(jù)到p的數(shù)據(jù)域InputOneStu(stu);//讀入一個(gè)學(xué)生的數(shù)據(jù)，見(jiàn)第1章p->data=stu;p->next=NULL;//將結(jié)點(diǎn)p插入到尾結(jié)點(diǎn)r的后面r->next=p;//r指向新的尾結(jié)點(diǎn)r=p;}}//范例2：在單鏈表L中查找學(xué)號(hào)studID的學(xué)生，找到返回其序號(hào)，否則返回0intLocateElem(LinkListL,char*stuID){LNode*p;intj;p=L->next;//從第一個(gè)結(jié)點(diǎn)開(kāi)始查找j=1;//依次將單鏈表中的元素和stuID進(jìn)行比較while(p&&strcmp(p->data.No,stuID)!=0){p=p->next;j++;}if(p)//p不為空，即找到stuIDreturnj;//返回序號(hào)elsereturn0;}//范例3：刪除鏈表L中姓名為stuName的學(xué)生，返回刪除的學(xué)生人數(shù)intDeleteElem(LinkList&L,char*stuName){LNode*p,*q;intcnt;//計(jì)數(shù)器q=L->next;//初始化工作指針p=L;cnt=0;//初始化計(jì)數(shù)器while(q!=NULL){if(strcmp(q->,stuName)==0)//找到要?jiǎng)h除的結(jié)點(diǎn){p->next=q->next;//將結(jié)點(diǎn)從鏈表中摘除free(q);q=p->next;cnt++;//計(jì)數(shù)器加1}else{//不相等，指針后移，繼續(xù)比較下一個(gè)結(jié)點(diǎn)p=p->next;q=q->next;}}returncnt;}//輸出鏈表中的學(xué)生信息//打印表頭voidPrintHeader(){printf("%-8s","學(xué)號(hào)");printf("%-10s","姓名");printf("%-6s","性別");printf("%-10s","大學(xué)英語(yǔ)");printf("%-10s\n","高等數(shù)學(xué)");}//輸出鏈表L中的學(xué)生信息voidPrintListInfo(LinkListL){inti;PrintHeader();//輸出表頭LNode*p;p=L->next;//從第一個(gè)結(jié)點(diǎn)開(kāi)始while(p){printf("%-8s",p->data.No);printf("%-10s",p->);printf("%-6c",p->data.sex);printf("%-10d",p->data.english);printf("%-10d\n",p->data.math);p=p->next;}}//任務(wù)1：在單鏈表L中的第i個(gè)學(xué)生后面插入一個(gè)新學(xué)生stu。voidInsertElem(LinkList&L,inti,Studentstu){LNode*s,*p,*pre;s=(LinkList)malloc(sizeof(LNode));//生成結(jié)點(diǎn)ss->data=stu;//將x存入結(jié)點(diǎn)的數(shù)據(jù)域p=L;intj=0;//尋找插入位置，并使p指向插入位置的前驅(qū)結(jié)點(diǎn)，即L中的第i個(gè)位置while(p!=NULL&&j<i){pre=p;p=p->next;j++;}if(p==NULL)//若i大于表的長(zhǎng)度，則將s插入到pre之后{s->next=NULL;pre=s;}else//將新結(jié)點(diǎn)s插入到p結(jié)點(diǎn)之后{s->next=p->next;//新結(jié)點(diǎn)指針域指向p的后繼結(jié)點(diǎn)p->next=s;//新結(jié)點(diǎn)成為p的后繼結(jié)點(diǎn)}}//任務(wù)2：統(tǒng)計(jì)單鏈表L中高等數(shù)學(xué)大于x并且大學(xué)英語(yǔ)大于x的學(xué)生人數(shù)。intCountElem(LinkListL,intx){intcnt=0;//計(jì)數(shù)器LNode*p=L->next;//p指向第一個(gè)結(jié)點(diǎn)//將鏈表中的元素逐個(gè)和給定值x進(jìn)行比較，相等則計(jì)數(shù)器加1while(p!=NULL){if(p->data.english>x&&p->data.math>x)//找到一個(gè)符合條件的元素cnt++;p=p->next;//p指向后一個(gè)結(jié)點(diǎn)}returncnt;}//任務(wù)3：在任務(wù)2的基礎(chǔ)上，將單鏈表L中高等數(shù)學(xué)成績(jī)和大學(xué)英語(yǔ)成績(jī)?cè)趍in_score到max_score之間的學(xué)生組織成一個(gè)新的單鏈表L2。intMoveElem(LinkList&L,intmin_score,intmax_score,LinkList&L2){intcnt=0;LNode*p,*q;p=L;while(p!=NULL&&p->next!=NULL){if((p->next->data.english>=min_score&&p->next->data.english<=max_score)&&(p->next->data.math>=min_score&&p->next->data.math<=max_score)){q=p->next;p->next=q->next;//把q結(jié)點(diǎn)從L中移出q->next=L2->next;//把q結(jié)點(diǎn)鏈接到L2表頭的后面L2->next=q;cnt++;}else{p=p->next;}}returncnt;//返回移動(dòng)的結(jié)點(diǎn)數(shù)}//補(bǔ)充：將學(xué)生信息存入一個(gè)文件中voidSaveInfor_toFile(LinkListL){FILE*fp;//1、定義文件指針intcnt=0;LNode*p=L->next;charfilename[20];fflush(stdin);//清空輸入緩沖區(qū)printf("請(qǐng)輸入文件名（如file1.dat）：");gets(filename);//輸入文件名if((fp=fopen(filename,"wb"))==NULL)//2、打開(kāi)輸出文件，file1.dat{printf("文件未打開(kāi)!\n");return;}while(p!=NULL){if(fwrite(&(p->data),sizeof(Student),1,fp)!=1)//3、向文件寫(xiě)數(shù)據(jù)printf("Filewriteerror!");else{cnt++;p=p->next;}}fclose(fp);//4、關(guān)閉文件printf("有%d位學(xué)生信息保存到文件中！\n",cnt);}//補(bǔ)充：從文件中讀入學(xué)生數(shù)據(jù),并存入順序表中voidInputInfor_fromFile(LinkList&L){FILE*fp;//1、定義文件指針inti;Studentstu;LNode*p;charfilename[20];//輸入文件名fflush(stdin);//清空輸入緩沖區(qū)printf("請(qǐng)輸入文件名（如file1.dat）：");gets(filename);if((fp=fopen(filename,"rb"))==NULL)//2、打開(kāi)輸入文件file1.dat{printf("文件未打開(kāi)!\n");return;}i=0;while(!feof(fp))//判斷文件是否讀完{if(fread(&stu,sizeof(Student),1,fp)!=1)//3、從文件讀數(shù)據(jù)break;p=(LNode*)malloc(sizeof(LNode));p->data=stu;p->next=L->next;L->next=p;i++;}fclose(fp);//4、關(guān)閉文件printf("讀取了%d位學(xué)生信息!\n",i);}intmain(){LinkListL,newL;intselect;Studentstudent;charstudNo[8];InitListList(L);printf("是從文件中讀取數(shù)據(jù)還是逐個(gè)輸入學(xué)生信息？\n1--從文件中讀取\n2--逐個(gè)輸入\n");scanf("%d",&select);if(select==1){InputInfor_fromFile(L);}else{CreateLinkList_R(L,5);}PrintListInfo(L);printf("輸入需要查找的學(xué)生的學(xué)號(hào)：");fflush(stdin);//清空輸入緩沖區(qū)gets(studNo);intpos=LocateElem(L,studNo);printf("PeterNo:%d\n",pos);printf("輸入要插入的學(xué)生信息：\n");InputOneStu(student);InsertElem(L,3,student);PrintListInfo(L);printf("高等數(shù)學(xué)和英語(yǔ)都高于75分的同學(xué)有%d位\n",CountElem(L,75));InitListList(newL);intnum=MoveElem(L,80,100,newL);printf("總共移了%d位同學(xué)\n",num);PrintListInfo(L);printf("*******************\n");PrintListInfo(newL);printf("是否將學(xué)生數(shù)據(jù)存入文件中（Y/N）?\n");chars;fflush(stdin);//清空輸入緩沖區(qū)scanf("%c",&s);if(s=='Y'){SaveInfor_toFile(L);}return0;}2、任務(wù)4的參考答案/*編程實(shí)現(xiàn)在雙向循環(huán)鏈表上的插入、刪除和查找操作。（1）輸入鏈表的長(zhǎng)度和各元素的值，用尾插法建立雙向循環(huán)鏈表，并輸出鏈表中各元素值，觀察輸入的內(nèi)容與輸出的內(nèi)容是否一致。（2）在雙向循環(huán)鏈表的第i個(gè)元素之前插入一個(gè)值為x的元素，并輸出插入后的鏈表中各元素值。（3）刪除雙向循環(huán)鏈表中第i個(gè)元素，并輸出刪除后的鏈表中各元素值。（4）在雙向循環(huán)鏈表中查找值為x元素，如果查找成功，則顯示該元素在鏈表中的位置，否則顯示該元素不存在。*/#include<stdio.h>#include<stdlib.h>typedefintDElemType;//雙向循環(huán)鏈表typedefstructNode{//數(shù)據(jù)域DElemTypedata;//指針域structNode*next,*prior;}DNode,*DblCirLinkList;//初始化鏈表intinitDblLinkList(DblCirLinkList&L){//生成頭結(jié)點(diǎn)L=(DNode*)malloc(sizeof(DNode));//指針域指向頭結(jié)點(diǎn)L->next=L;L->prior=L;return1;}//輸入鏈表的長(zhǎng)度和各元素的值，用尾插法建立雙向循環(huán)鏈表intcreateDblLinkList(DblCirLinkList&L){intlength;fflush(stdin);//清空輸入緩沖區(qū)printf("輸入鏈表的元素個(gè)數(shù)：");scanf("%d",&length);//循環(huán)輸入元素，并插入到鏈表中printf("輸入要插入的元素：");for(inti=1;i<=length;i++){//生成插入的結(jié)點(diǎn)DNode*p=(DNode*)malloc(sizeof(DNode));scanf("%d",&p->data);p->next=L;p->prior=L->prior;L->prior->next=p;L->prior=p;}return1;}//輸出雙向循環(huán)鏈表L中各元素值voidprint_DblLinkList(DblCirLinkListL){DNode*p;p=L->next;//開(kāi)始指向第一個(gè)結(jié)點(diǎn)while(p!=L){printf("%d",p->data);p=p->next;}printf("\n");}//找雙向循環(huán)鏈表L中的第i個(gè)元素，找到返回該元素的地址DNode*getElem_DblLinkList(DblCirLinkListL,inti){//判斷i是否小于1，是則返回空if(i<1)returnNULL;//找第i個(gè)元素DNode*p=L->next;intcnt=1;//計(jì)數(shù)器while(p!=L&&cnt<i){p=p->next;//指針后移cnt++;//計(jì)數(shù)器加1}if(p==L)//未找到returnNULL;elsereturnp;}//在雙向循環(huán)鏈表L的第i個(gè)元素之前插入一個(gè)值為x的元素intinsert_DblLinkList(DblCirLinkList&L,inti,DElemTypex){DNode*s;if(i<1)return0;//先判斷i是否等于1，如果等于1，則直接插入到頭結(jié)點(diǎn)之后if(i==1){s=(DNode*)malloc(sizeof(DNode));s->data=x;s->next=L->next;s->prior=L;L->next->prior=s;L->next=s;return1;}//先找到第i-1個(gè)元素DNode*p;p=getElem_DblLinkList(L,i-1);//在L中確定第i-1個(gè)元素的位置pif(p==NULL)//p為空第i-1個(gè)結(jié)點(diǎn)不存在return0;s=(DNode*)malloc(sizeof(DNode));//生成新結(jié)點(diǎn)ss->data=x;//將x存入結(jié)點(diǎn)的數(shù)據(jù)域s->next=p->next;s->prior=p;p->next->prior=s;p->next=s;return1;}//刪除雙向循環(huán)鏈表中第i個(gè)元素intdelete_DblLinkList(DblCirLinkList&L,inti,DElemType&e){//找到第i個(gè)結(jié)點(diǎn)，并用p指向該結(jié)點(diǎn)DNode*p;p=getElem_DblLinkList(L,i);if(p==NULL)//未找到第i個(gè)結(jié)點(diǎn)return0;e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);return1;}//在雙向循環(huán)鏈表中查找值為x元素，如果查找成功，則顯示該元素在鏈表中的位置，否則顯示該元素不存在DNode*search_DblLinkList(DblCirLinkListL,DElemTypex){DNode*p;//從第一個(gè)元素開(kāi)始p=L->next;while(p!=L){if(p->data==x){break;}p=p->next;}//找到則返回該元素的地址，否則返回空if(p!=L)returnp;elsereturnNULL;}intmain(){DblCirLinkListLList;intpos;DElemTypedata;initDblLinkList(LList);//1）輸入鏈表的長(zhǎng)度和各元素的值，用尾插法建立雙向循環(huán)鏈表，并輸出鏈表中各元素值createDblLinkList(LList);print_DblLinkList(LList);//2）在雙向循環(huán)鏈表的第i個(gè)元素之前插入一個(gè)值為x的元素，并輸出插入后的鏈表中各元素值//輸入要插入的數(shù)據(jù)printf("輸入要插入的元素：");scanf("%d",&data);//輸入要插入的位置printf("輸入要插入的位置：");scanf("%d",&pos);if(insert_DblLinkList(LList,pos,data)==1)printf("成功插入一個(gè)元素！\n");elseprintf("插入失敗！\n");print_DblLinkList(LList);//3)刪除雙向循環(huán)鏈表中第i個(gè)元素，并輸出刪除后的鏈表中各元素值//輸入要?jiǎng)h除的元素位置printf("輸入要?jiǎng)h除的元素位置：");scanf("%d",&pos);if(delete_DblLinkList(LList,pos,data)){printf("刪除成功！\n");printf("刪除的元素值為：%d\n",data);}elseprintf("刪除失敗！\n");print_DblLinkList(LList);//4)在雙向循環(huán)鏈表中查找值為x元素，如果查找成功，則顯示該元素在鏈表中的位置，否則顯示該元素不存在printf("輸入要查找的元素：");scanf("%d",&data);DNode*p=search_DblLinkList(LList,data);if(p==NULL){printf("該元素不存在！\n");}else{printf("找到該元素,其地址為%X。\n",p);}return0;}

第3章棧1、范例1的參考答案#include<stdlib.h>#include<stdio.h>#defineMAXSIZE10typedefintSElemType;typedefstructSqStack{SElemType*base;//棧底元素的地址SElemType*top;//表示棧頂元素的地址，實(shí)際上存儲(chǔ)下一個(gè)存儲(chǔ)單元的地址intstacksize;//?？捎玫淖畲笕萘縸SqStack;//初始化一個(gè)空棧SintInitStack(SqStack&S){S.base=(SElemType*)malloc(MAXSIZE*sizeof(SElemType));if(!S.base) return-1;S.top=S.base;//S.top也指向棧底;S.stacksize=MAXSIZE;return1;}//入棧操作，將元素e入棧的函數(shù)如下intPush(SqStack&S,SElemTypee){if(S.top-S.base==S.stacksize)//棧滿return0;*S.top=e;//將e值存入到top所指空間S.top++;//top后移return1;}//出棧操作，將出棧的元素用e返回intPop(SqStack&S,SElemType&e){if(S.top==S.base)//棧為空return0;S.top--;//top減1e=*S.top;//將top所指空間的值存入到ereturn1;}//遍歷棧S中的元素voidPrintStack(SqStackS){SElemType*p=S.base;while(p<S.top){printf("%5d",*p);p++;}printf("\n");}//獲得棧頂元素，將棧頂元素用e返回intGetTop(SqStackS,SElemType&e){if(S.top==S.base)//棧為空return0;e=*(S.top-1);//取棧頂元素的值，并賦給ereturn1;}intmain(){SqStacks;intnum,i;intvalue;//初始化棧if(InitStack(s)!=1){printf("棧初始化失??！\n");return0;}printf("輸入要入棧的元素個(gè)數(shù)：");scanf("%d",&num);i=1;printf("輸入要入棧的元素：");while(i<=num){scanf("%d",&value);if(Push(s,value)==0){printf("%d入棧失??！",value);break;}i++;}printf("棧中的元素有：");PrintStack(s);//棧頂元素出棧if(Pop(s,value)==1){printf("棧頂元素成功出棧！\n");printf("出棧的元素為:%d\n",value);printf("棧頂元素出棧后，棧中的元素有：");PrintStack(s);}else{printf("棧頂元素出棧失?。n");}//獲得棧頂元素if(GetTop(s,value)==1){printf("成功獲取棧頂元素！\n");printf("棧頂?shù)脑貫?%d\n",value);}else{printf("獲取棧頂元素失??！\n");}printf("棧中的元素有：");PrintStack(s);return0;}2、范例2參考答案#include<stdlib.h>#include<stdio.h>typedefintSElemType;typedefstructStackNode{SElemTypedata;structStackNode*next;}StackNode,*LinkStack;//求棧的長(zhǎng)度intGetLength(LinkStackS){StackNode*p=S;intcnt=0;while(p){cnt++;p=p->next;}returncnt;}//判斷棧是否為空，為空則返回1，否則返回0intStackEmpty(LinkStackS){if(S==NULL){return1;}else{return0;}}//輸出棧s中的元素voidPrintStack(LinkStackS){StackNode*p;p=S;while(p!=NULL){printf("%5d",p->data);p=p->next;}printf("\n");}//將元素e入棧intPush(LinkStack&S,SElemTypee){StackNode*p;//生成結(jié)點(diǎn)p=(StackNode*)malloc(sizeof(StackNode));if(p!=NULL){p->data=e;//將e存入到結(jié)點(diǎn)p->next=S;//將新結(jié)點(diǎn)插入到棧頂之前S=p;//將插入結(jié)點(diǎn)作為棧頂return1;}return0;}//出棧，刪除棧頂元素，將刪除元素之用e返回intPop(LinkStack&S,SElemType&e){StackNode*p;if(S!=NULL)//棧不為空{(diào)p=S;S=S->next;e=p->data;free(p);return1;}else{return0;}}//銷毀鏈?zhǔn)綏ntDestroyStack(LinkStack&S){StackNode*p;p=S;while(p!=NULL){S=S->next;free(p);p=S;}S=NULL;return1;}//獲得棧頂元素intGetTop(LinkStackS,SElemType&e){if(S!=NULL)//棧不為空{(diào)e=S->data;//將棧頂元素的值賦給e所指單元return1;}else{return0;}}intmain(){LinkStacks=NULL;intnum,i;intvalue;//建立鏈?zhǔn)綏rintf("輸入要入棧的元素個(gè)數(shù)：");scanf("%d",&num);i=1;printf("輸入要入棧的元素：");while(i<=num){scanf("%d",&value);if(Push(s,value)==0){printf("%d入棧失敗！",value);break;}i++;}printf("棧中的元素有：");PrintStack(s);//棧頂元素出棧if(Pop(s,value)==1){printf("棧頂元素成功出棧！\n");printf("出棧的元素為:%d\n",value);printf("棧頂元素出棧后，棧中的元素有：");PrintStack(s);}else{printf("棧頂元素出棧失??！\n");}//獲得棧頂元素if(GetTop(s,value)==1){printf("成功獲取棧頂元素！\n");printf("棧頂?shù)脑貫?%d\n",value);}else{printf("獲取棧頂元素失敗！\n");}printf("棧中的元素有：");PrintStack(s);DestroyStack(s);return0;}3、任務(wù)1參考答案#include<stdio.h>#include<stdlib.h>#defineMAXSIZE100//最大長(zhǎng)度typedefintSElemType;typedefstruct{SElemTypedata[MAXSIZE];//存儲(chǔ)元素的數(shù)組inttop1,top2;//兩個(gè)棧棧頂元素在數(shù)組中的下標(biāo)intstacksize;//?？捎玫淖畲笕萘縸SqDoubleStack;//初始化操作，建立一個(gè)空棧SintInitSqDoubleStack(SqDoubleStack&S){//給top1和top2賦初值S.top1=-1;S.top2=MAXSIZE;return1;}//將元素e入第stackNumber個(gè)中intPush(SqDoubleStack&S,SElemTypee,intstackNumber){if(S.top1+1==S.top2)//棧滿，不能再插入新元素了{(lán)return0;}if(stackNumber==1)//將元素入棧1{S.top1++;//將top1加1S.data[S.top1]=e;//將元素e放入棧頂位置}if(stackNumber==2)//將元素入棧2{S.top2--;//將top2減1S.data[S.top2]=e;//將元素e放入棧頂位置}else{return0;}return1;}//將第stackNumber個(gè)棧的棧頂元素出棧，并用e返回其值intPop(SqDoubleStack&S,SElemType&e,intstackNumber){if(stackNumber==1){if(S.top1==-1)//棧1為空，操作失敗{return0;}e=S.data[S.top1];//將出棧的元素存入e中S.top1--;//棧頂指針減1}if(stackNumber==2){if(S.top2==MAXSIZE)//棧2為空，操作失敗{return0;}e=S.data[S.top2];//將出棧的元素存入e中S.top2++;//棧頂指針加1}else{return0;}return1;}//獲得第stackNumber個(gè)棧的棧頂元素voidGetTop(SqDoubleStackS,SElemType&e,intstackNumber){if(stackNumber==1&&S.top1!=-1){e=S.data[S.top1];}if(stackNumber==2&&S.top2!=MAXSIZE){e=S.data[S.top2];}}//輸出第stackNumber個(gè)棧中的元素voidPrintStack(SqDoubleStackS,intstackNumber){if(stackNumber==1){if(S.top1!=-1){printf("第%d個(gè)棧中的元素有：",stackNumber);for(inti=0;i<=S.top1;i++){printf("%4d",S.data[i]);}printf("\n");}else{printf("第%d個(gè)棧為空！\n",stackNumber);}}elseif(stackNumber==2){if(S.top2!=MAXSIZE){printf("第%d個(gè)棧中的元素有：",stackNumber);for(inti=MAXSIZE-1;i>=S.top2;i--){printf("%4d",S.data[i]);}printf("\n");}else{printf("第%d個(gè)棧為空！\n",stackNumber);}}else{printf("第%d個(gè)棧不存在！\n",stackNumber);}}intmain(){SqDoubleStackS;intdata;InitSqDoubleStack(S);//將6個(gè)元素分別入兩個(gè)棧Push(S,1,1);Push(S,2,1);Push(S,3,1);Push(S,4,2);Push(S,5,2);Push(S,8,2);//輸出兩個(gè)棧中的元素Prin