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

1、數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題及答案1、對帶表頭結(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 ->data<x)p=p->next;s=( node *)malloc(sizeof(node) ;s->data=x;s->next= p-&g

2、t;next;p->next=s;)2、對帶表頭結(jié)點(diǎn)的單鏈表,編寫算法求單鏈表的長度.答案：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

3、 /結(jié)點(diǎn)結(jié)構(gòu) datatype data;node * next;);單鏈表的插入?yún)⒖妓惴ǎ涸诎豿的結(jié)點(diǎn)前插入新元素bvoid ins_linked_LList(node * head , datatype x, datatype b) node *p, *q;p=new node ;/申請一個(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-

4、>next!=NULL)&&(q->next)->d)!=x) q=q->next; 尋找包含元素 x的前一個(gè)結(jié)點(diǎn) q p->next=q->next;q->next=p;/ 新結(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; d

5、elete 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); /鏈表中無刪除的元素p=q->next; q->next=p->next;/ 刪除 q 的下個(gè)結(jié)點(diǎn) p delete p;/釋放結(jié)點(diǎn)p的存儲(chǔ)空間return(1);x的元素個(gè)數(shù).4、對帶表頭結(jié)點(diǎn)的單鏈表,編寫算法統(tǒng)計(jì)單鏈表中大于答案：typedef datatype

6、 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->data>x) num+ ; p=p->next;return num;5、對帶表頭結(jié)點(diǎn)的單鏈表,編寫算法將單鏈表就地逆置.答案：typedef datatype int;struct node /結(jié)點(diǎn)結(jié)構(gòu) datatype data;node * next;)；/ 注：也可以用自然語言描述

7、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) datatype data; node * next;);/ 注：也可以用自然語言描述struct LinkQueue /結(jié)點(diǎn)結(jié)構(gòu) node * front; nod

8、e * 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 0;p= q->front->next;*e= p-&g

9、t;data;q->front->next=p->next;free(p);if(q->front->next=NULL) q->rear= q->front;return 1;7、編寫算法對二叉鏈表存儲(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(ro

10、ot=NULL) return ; / printf("%5d", root->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 )+ nu

11、mOfLeaf (root->rchild ); )/說明：算法的表達(dá)形式及方法多種多樣,不可拘泥于固法.8、對以二叉鏈表存儲(chǔ)的二叉樹,編寫對二叉樹進(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 );/

12、 printf("%5d", root->data);inOrder (root->rchild ); /)int height (node* root) /求二叉樹的高度 int h1,h2if(root=NULL) return 0; /空樹h1=height (root->lchild );h2= height (root->rchild ); return 1+(h1>=h2)?h1:h2;)/說明：算法的表達(dá)形式及方法多種多樣,不可拘泥于固法.9、編寫對有序順序表的折半查找算法.答案：#define MaxSize 100 typed

13、ef struct KeyType key;OtherType otherData;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.key<k) high= mid-1; elselow= mid+1;Return 0;查找失敗 10、試寫一個(gè)算法,判別一行字符中的圓括號(hào)是否配對.答案：int BracketMatch(char*str)圓括號(hào)