數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題與答案

1、數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題及答案1、對(duì)帶表頭結(jié)點(diǎn)的有序單鏈表，編寫算法向單鏈表中插入元素X,使其保持有序。答案：typedef datatype int;struct node /結(jié)點(diǎn)結(jié)構(gòu)datatype data;node * next;；/ 注：也可以用自然語言描述void insertOrder(node *head, datatype x) /統(tǒng)計(jì)node *s; p=head;while (p-next -datanext;s=( node *)malloc(sizeof(node);s-data=x;s-next= p-next;p-next=s;2、對(duì)帶表頭結(jié)點(diǎn)的單鏈表，編寫算法求單鏈表

2、的長度。答案：typedef datatype int;struct node / 結(jié)點(diǎn)結(jié)構(gòu)datatype data;node * next;/ 注：也可以用自然語言描述int Length(node *head) /求單鏈表的長度int num=0;node *p=head-next;while (p)num+ ;p=p-next;return num;3、試寫出單鏈表的插入與刪除算法，并用C編寫相應(yīng)的程序。答案：typedef datatype int;struct node / 結(jié)點(diǎn)結(jié)構(gòu)datatype data;node * next;單鏈表的插入?yún)⒖妓惴ǎ涸诎豿的結(jié)點(diǎn)前插入新

3、元素bvoid ins_linked_LList(node * head , datatype x, datatype b) node *p, *q;p=new node ;/申請(qǐng)一個(gè)新結(jié)點(diǎn)p-d=b;/置新結(jié)點(diǎn)的數(shù)據(jù)域if (head=NULL)/原鏈表為空head=p; p-next=NULL; return;if (head-d=x)/在第一個(gè)結(jié)點(diǎn)前插入 p-next=head;head=p;return; q=head;while (q-next!=NULL)&(q-next)-d)!=x)q=q-next;/尋找包含元素x的前一個(gè)結(jié)點(diǎn)q p-next=q-next;q-next=p;

4、/ 新結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后 return;單鏈表的刪除參考算法：int del_linked_LList(node * head ,T x) /刪除包含元素 x 的結(jié)點(diǎn)元素node *p, *q;if (head=NULL) return(0); /鏈表為空，無刪除的元素if (head-d)=x)/刪除第一個(gè)結(jié)點(diǎn) p=head-next; delete head; head=p; return(1); q=head;while (q-next!=NULL)&(q-next)-d)!=x)q=q-next;/ 尋找包含元素 x的前一個(gè)結(jié)點(diǎn) qif (q-next=NULL)return(0)

5、; / 鏈表中無刪除的元素p=q-next; q-next=p-next;/刪除 q 的下一個(gè)結(jié)點(diǎn) pdelete p;/ 釋放結(jié)點(diǎn)p的存儲(chǔ)空間 return(1);4、對(duì)帶表頭結(jié)點(diǎn)的單鏈表，編寫算法統(tǒng)計(jì)單鏈表中大于x的元素個(gè)數(shù)。答案：typedef datatype int;struct node / 結(jié)點(diǎn)結(jié)構(gòu) datatype data;node * next;/ 注：也可以用自然語言描述int CountX(node *head, datatype x) /統(tǒng)計(jì)int num=0;p=head-next;while (p)if(p-datax) num+ ;p=p-next;return

6、 num;5、對(duì)帶表頭結(jié)點(diǎn)的單鏈表，編寫算法將單鏈表就地逆置。答案：typedef datatype int;struct node / 結(jié)點(diǎn)結(jié)構(gòu)datatype data;node * next;/注：也可以用自然語言描述void ReverseList(node *head) /將單鏈表就地逆置node *q, *p=head-next;head-next=NULL ；while (p)q=p;p=p-next;q-next= head-next;head-next=q ;6、寫出鏈隊(duì)列的入隊(duì)、出隊(duì)的算法。答案：typedef datatype int;struct node /結(jié)點(diǎn)結(jié)構(gòu)d

7、atatype data;node * next;/注：也可以用自然語言描述struct LinkQueue /結(jié)點(diǎn)結(jié)構(gòu) node * front;node * rear;int EnterQueue(LinkQueue *q, datatype e)/帶頭結(jié)點(diǎn)的鏈隊(duì)列入隊(duì)q-rear-next=( node *)malloc(sizeof(node);q-rear-data=e;q-rear= q-rear-next;return 1;int DeleteQueue(LinkQueue *q, datatype *e)/帶頭結(jié)點(diǎn)的鏈隊(duì)列出隊(duì)if(q-rear= q-front) return

8、 0;p= q-front-next;*e= p-data;q-front-next=p-next;free(p);if(q-front-next=NULL)q-rear= q-front;return 1;7、編寫算法對(duì)二叉鏈表存儲(chǔ)的二叉樹進(jìn)行前序遍歷，并統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)數(shù)。答案：typedef datatype int;struct node /結(jié)點(diǎn)結(jié)構(gòu) datatype data;node * Ichild, *rchild;；/注：也可以用自然語言描述void preOrder(node* root) /if(root=NULL) return ; / printf(%5d, ro

9、ot-data); preOrder (root-lchild );/ preOrder (root-rchild ); /前序遍歷空樹前序遍歷根的左子樹前序遍歷根的右子樹int numOfLeaf (node* root) /統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)總數(shù)if(root=NULL) return 0; /空樹if(root-lchild =NULL)& (root-rchild =NULL)return 1; /葉子return numOfLeaf (root-lchild )+ numOfLeaf (root-rchild );/說明：算法的表達(dá)形式及方法多種多樣，不可拘泥于固法。8、對(duì)以二叉鏈表存

10、儲(chǔ)的二叉樹，編寫對(duì)二叉樹進(jìn)行中序遍歷的算法， 的算法。以及求二叉樹高度答案：typedef datatype int;struct node / 結(jié)點(diǎn)結(jié)構(gòu) datatype data; node *lchild, *rchild;/注：也可以用自然語言描述 void inOrder(node* root) / if(root=NULL) return ; / inOrder (root-lchild );/ printf(%5d, root-data); inOrder (root-rchild ); / 前序遍歷空樹中序遍歷根的左子樹中序遍歷根的右子樹int height (node* ro

11、ot) /求二叉樹的高度 int h1,h2if(root=NULL) return 0; /空樹h1=height (root-lchild );h2= height (root-rchild );return 1+(h1=h2)?h1:h2;/說明：算法的表達(dá)形式及方法多種多樣，不可拘泥于固法。9、編寫對(duì)有序順序表的折半查找算法。答案：#define MaxSize 100typedef struct( KeyType key; OtherTypeotherData;datatype;struct SeqList /結(jié)點(diǎn)結(jié)構(gòu) datatype dataMaxSize; /0號(hào)單元不用int len;int BinSearch(SeqList SL, KeyType k) low=1, high=SL.len;while(low=high) mid=( low+high)/2;if(SL.datamid.key=k)return mid; /查找成功if(SL.datamid.keyk)high= mid-1;elselow= mid+1;Return 0;/ 查找失敗10、試寫一個(gè)算法，判別一行字符中的圓括號(hào)是否配對(duì)。答案：int BracketMatch(cha