【文章內(nèi)容簡介】 elseif (issorted(head,39。d39。)) printf(單鏈表head 是降序排列的！\n)。else printf(單鏈表head 是無序的！\n)。}程序運(yùn)行時(shí)的三種輸出結(jié)果如下圖所示： 設(shè)計(jì)一個(gè)算法，利用單鏈表原來的結(jié)點(diǎn)空間將一個(gè)單鏈表就地轉(zhuǎn)置。【答】：include void verge(linklist head){/*本函數(shù)的功能是就地倒置帶頭結(jié)點(diǎn)的單鏈表*/16linklist p,q。p=headnext。headnext=NULL。while (p) /*每次從原表取一個(gè)結(jié)點(diǎn)插入到新表的最前面*/{q=p。p=pnext。qnext=headnext。headnext=q。}}int main() /*測試函數(shù)*/{linklist head。head=creatlinklist()。 /*創(chuàng)建單鏈表*/print(head)。 /*輸出原單鏈表*/verge(head)。 /*就地倒置單鏈表*/print(head)。 /*輸出倒置后的單鏈表*/} 設(shè)計(jì)一個(gè)算法，將一個(gè)結(jié)點(diǎn)值自然數(shù)的單鏈表拆分為兩個(gè)單鏈表，原表中保留值為偶數(shù)的結(jié)點(diǎn)，而值為奇數(shù)的結(jié)點(diǎn)按它們?cè)谠碇械南鄬?duì)次序組成一個(gè)新的單鏈表。【答】：include linklist sprit(linklist head){ /*將帶頭結(jié)點(diǎn)的單鏈表head 中的奇數(shù)值結(jié)點(diǎn)刪除生成新的單鏈表并返回*/linklist L,pre,p,r。L=r=(linklist)malloc(sizeof(linknode))。rnext=NULL。pre=head。p=headnext。while (p){ if (pdata%2==1) /*刪除奇數(shù)值結(jié)點(diǎn)*/{ prenext=pnext。rnext=p。r=p。p=prenext。}else /*保留偶數(shù)值結(jié)點(diǎn)*/{ pre=p。p=pnext。}17}rnext=NULL。 /*置鏈表結(jié)束標(biāo)記*/return L。}int main() /*測試函數(shù)*/{linklist head,L。head=creatlinklist()。 /*創(chuàng)建單鏈表*/print(head)。 /*輸出原單鏈表*/L=sprit(head)。 /*分裂單鏈表head*/printf(\n 原單鏈表為:\n)。print(head)。 /*輸出倒置后的單鏈表*/printf(\n 分裂所得奇數(shù)單鏈表為:\n)。print(L)。}本程序的一組測試情況如下圖所示。 設(shè)計(jì)一個(gè)算法，對(duì)一個(gè)有序的單鏈表，刪除所有值大于x 而不大于y 的結(jié)點(diǎn)?！敬稹浚篿nclude void deletedata(linklist head,datatype x,datatype y){ /*刪除帶頭結(jié)點(diǎn)單鏈表中所有結(jié)點(diǎn)值大于x 而不大于y 的結(jié)點(diǎn)*/linklist pre=head,p,q。p=headnext。 /*初始化*/while (p amp。amp。 pdata=x) /*找第1 處大于x 的結(jié)點(diǎn)位置*/{ pre=p。p=pnext。}while (p amp。amp。 pdata=y) /*找第1 處小于y 的位置*/p=pnext。q=prenext。 /*刪除大于x 而小于y 的結(jié)點(diǎn)*/prenext=p。pre=qnext。18while (pre!=p) /*釋放被刪除結(jié)點(diǎn)所占用的空間*/{free(q)。q=pre。pre=prenext。}}void main() /*測試函數(shù)*/{ linklist head,L。datatype x,y。head=creatlinklist()。 /*創(chuàng)建單鏈表*/print(head)。 /*輸出原單鏈表*/printf(\n 請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù)區(qū)間:\n)。scanf(%d%d,amp。x,amp。y)。deletedata(head,x,y)。print(head)。 /*輸出刪除后的單鏈表*/} 設(shè)計(jì)一個(gè)算法，在雙鏈表中值為y 的結(jié)點(diǎn)前面插入一個(gè)值為x 的新結(jié)點(diǎn)。即使值為x 的新結(jié)點(diǎn)成為值為y 的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)?！敬稹浚菏紫榷x雙鏈表的數(shù)據(jù)結(jié)構(gòu)，內(nèi)容如下：typedef int datatype。 /*預(yù)定義的數(shù)據(jù)類型*/typedef struct dlink_node{ /*雙鏈表結(jié)點(diǎn)定義*/datatype data。struct dlink_node *llink,*rlink。}dnode。typedef dnode* dlinklist。 /*雙鏈表結(jié)點(diǎn)指針類型定義*//*尾插法創(chuàng)建帶頭結(jié)點(diǎn)的雙鏈表*/dlinklist creatdlinklist(void){ dlinklist head,r,s。datatype x。head=r=(dlinklist) malloc(sizeof(dnode))。 /*建立雙鏈表的頭結(jié)點(diǎn)*/headllink=headrlink=NULL。printf(\n 請(qǐng)輸入雙鏈表的內(nèi)容：（整數(shù)序列，以0 結(jié)束）\n)。scanf(%d,amp。x)。while (x) /*輸入結(jié)點(diǎn)值信息，以0 結(jié)束*/{ s=(dlinklist ) malloc(sizeof(dnode))。sdata=x。srlink=rrlink。 /*將新結(jié)點(diǎn)s 插入到雙鏈表鏈尾*/19sllink=r。rrlink=s。r=s。scanf(%d,amp。x)。}return head。}/*輸出雙鏈表的內(nèi)容*/void print(dlinklist head){ dlinklist p。p=headrlink。printf(\n 雙鏈表的內(nèi)容是：\n)。while (p){ printf(%5d,pdata)。p=prlink。}}本題的求解程序如下：include include void insertxaty(dlinklist head,datatype y,datatype x){ dlinklist s,p。/*首先在雙鏈表中找y 所在的結(jié)點(diǎn)，然后在y 前面插入新結(jié)點(diǎn)*/p=headrlink。while (p amp。amp。 pdata!=y)p=prlink。if (!p) printf(\n 雙鏈表中不存在值為y 的結(jié)點(diǎn),無法插入新結(jié)點(diǎn)!\n)。else /*插入值為x 的新結(jié)點(diǎn)*/{ s=(dlinklist)malloc(sizeof(dnode))。sdata=x。srlink=p。sllink=pllink。pllinkrlink=s。pllink=s。}}void main() /*測試函數(shù)*/{ dlinklist head。datatype x,y。20head=creatdlinklist()。print(head)。printf(\n 請(qǐng)輸入要輸入的位置結(jié)點(diǎn)值y:\n)。scanf(%d,amp。y)。printf(\n 請(qǐng)輸入要輸入的結(jié)點(diǎn)值x:\n)。scanf(%d,amp。x)。insertxaty(head,y,x)。/*在值為y 的結(jié)點(diǎn)前插入值為x 的新結(jié)點(diǎn)*/print(head)。/*輸出新的雙鏈表*/getch()。}本程序的一組測試情況如下圖所示。 設(shè)計(jì)一個(gè)算法，從右向左打印一個(gè)雙鏈表中各個(gè)結(jié)點(diǎn)的值?！敬稹浚?，實(shí)現(xiàn)從右向左打印雙鏈表的各個(gè)結(jié)點(diǎn)的值可以用遞歸程序?qū)崿F(xiàn)如下：include include void vprint(dlinklist head){ /*遞歸方法從右向左打印雙鏈表的值*/if (headrlink){vprint(headrlink)。printf(%5d,headrlinkdata)。}}void main() /*測試函數(shù)*/{ dlinklist head。head=creatdlinklist()。print(head)。printf(\n 從右向左打印的雙鏈表的內(nèi)容是:\n)。21vprint(head)。getch()。}本程序的一組測試情況如下圖所示。 設(shè)計(jì)一個(gè)算法，將一個(gè)雙鏈表改建成一個(gè)循環(huán)雙鏈表?！敬稹浚篿nclude include /*將一個(gè)雙鏈表改成循環(huán)雙鏈表*/void dlinktocdlink(dlinklist head){ dlinklist r。r=head。while (rrlink) /*尋找尾結(jié)點(diǎn)*/r=rrlink。headllink=r。rrlink=head。}void printcdlink(dlinklist head){ /*打印雙鏈表*/dlinklist p。p=headrlink。while (p!=head){printf(%5d,pdata)。p=prlink。}}int main() /*測試函數(shù)*/{ dlinklist head。head=creatdlinklist()。dlinktocdlink(head)。printf(\n 循環(huán)雙鏈表的內(nèi)容是：\n)。printcdlink(head)。}22第4 章 字符串、數(shù)組和特殊矩陣 稀疏矩陣常用的壓縮存儲(chǔ)方法有（ 三元組順序存儲(chǔ) ）和（ 十字鏈表 ）兩種。 設(shè)有一個(gè)10 10 的對(duì)稱矩陣A 采用壓縮方式進(jìn)行存儲(chǔ)，存儲(chǔ)時(shí)以按行優(yōu)先的順序存儲(chǔ)其下三角陣，假設(shè)其起始元素a00 的地址為1，每個(gè)數(shù)據(jù)元素占2 個(gè)字節(jié)，則a65 的地址為（ 53 ）。 若串S =“software”，其子串的數(shù)目為（ 36 ）。 常對(duì)數(shù)組進(jìn)行的兩種基本操作為（ 訪問數(shù)據(jù)元素 ）和（ 修改數(shù)組元素 ）。 要計(jì)算一個(gè)數(shù)組所占空間的大小，必須已知（數(shù)組各維數(shù)）和（每個(gè)元素占用的空間）。 對(duì)于半帶寬為b 的帶狀矩陣，它的特點(diǎn)是：對(duì)于矩陣元素aij ，若它滿足（|ij|b），則aij = 0。 字符串是一種特殊的線性表，其特殊性體現(xiàn)在（ 該線性表的元素類型為字符 ）。 試編寫一個(gè)函數(shù)，實(shí)現(xiàn)在順序存儲(chǔ)方式下字符串的strpare（S1，S2）運(yùn)算。【答】：include include define MAXSIZE 100typedef struct{char str[MAXSIZE]。int length。}seqstring。/* 函數(shù)strpare()的功能是：當(dāng)s1s2 時(shí)返回1，當(dāng)s1==s2 時(shí)返回0，當(dāng)s1s2 時(shí)返回1*/int strpare(seqstring s1,seqstring s2){ int i,m=0,len。len= ?:。for(i=0。i=len。i++)if([i][i]){m=1。break。}else if([i][i]){m=1。break。}return m。}int main(){ seqstring s1,s2。int i,m。printf(input char to s1:\n)。23gets()。=strlen()。printf(input char to s2:\n)。gets()。=strlen()。m=strpare(s1,s2)。if(m==1) printf(s1s2\n)。else if(m==1) printf(s2s1\n)。else if(m==0) printf(s1=s2\n)。} 試編寫一個(gè)函數(shù)，實(shí)現(xiàn)在順序存儲(chǔ)方式下字符串的replace（S，T1，T2）運(yùn)算?！緟⒖汲绦?】：/*本程序用來在順序存儲(chǔ)下用快速匹配模式實(shí)現(xiàn)在字符串S 中用T2 替換所有T1 出現(xiàn)的可能*/includeincludeinclude define maxsize 100typedef struct{char str[maxsize]。int length 。} seqstring。//求next[]函數(shù)void getnext(seqstring*p,int next[]){int i,j。next[0]=1。i=0。j=1。while(iplength){if(j==1||pstr[i]==pstr[j]){++i。++j。next[i]=j。}elsej=next[j]。}}//快速模式匹配算法int kmp(seqstring*t,seqstring*p,int next[],int temppos){int i,j。24i=temppos,j=0。while (itlength amp。amp。 jplength){if(j==1||tstr[i]==pstr[j]){i++。 j++。}else j=next[j]。}if (j==plength) return (iplength)。else return(1)。}