143. 枚舉元素本身由系統定義了一個表示序號的數值,從0 開始順序定義為0,1,2…。如在weekday中,sun值為0,mon值為1, …,sat值為6。
main(){
enum weekday
{
sun,mon,tue,wed,thu,fri,sat
} a,b,c;
a=sun;
b=mon;
c=tue;
printf("%d,%d,%d",a,b,c);
}?
只能把枚舉值賦予枚舉變量,不能把元素的數值直接賦予枚舉變量。如:a=sum;b=mon; 是正確的。而:a=0;b=1; 是錯誤的。如一定要把數值賦予枚舉變量,則必須用強制類型轉換,如:a=(enum weekday)2;其意義是將順序號為2的枚舉元素賦予枚舉變量a,相當于:a=tue; 還應該說明的是枚舉元素不是字符常量也不是字符串常量, 使用時不要加單、雙引號。
main(){
enum body
{
a,b,c,d
} month[31],j;
int i;
j=a;
for(i=1;i<=30;i++){
month[i]=j;
j++;
if (j>d) j=a;
}
for(i=1;i<=30;i++){
switch(month[i])
{
case a:printf(" %2d %c\t",i,'a'); break;
case b:printf(" %2d %c\t",i,'b'); break;
case c:printf(" %2d %c\t",i,'c'); break;
case d:printf(" %2d %c\t",i,'d'); break;
default:break;
}
}
printf("\n");
}
144.用折半查找法求一個數? 數組a已按從小到大的順序排列
while((!sign) && (bott <= top))
{
mid=(bott + top)/2;
?? ? if(number ==a[mid])
{
local=mid;
printf(“the local is %d\n”,local);
printf(“the number is%d\n”, number);
sign =true;
}
else if(number <a[min])
?? top = mid -1;
else
?? bott=mid+1;
}
145.有一個字符串,將字符串從第m個字符開始全部復制到另一個新字符串?
void copystr( char *p1, char *p2, int m)
{
int n=0;
while(n<m-1)
{
n++;
p1++;
}
while(*p1 !=’/0’)
{
*p2=*p1;
p1++;
p2++;
}
*p2=’/0’;
}
146.排序問題:
問題一:寫出冒泡排序
void pop_sort(int a[],int N)
{ int tmp, i , j;
for(j=0; j<N; j++)
for( i=0; i<N-j; i++)
if( a[i]>a[i+1])
{tmp=a[i];
a[i]=a[i+1];
a[i+1]=tmp;
}
}
問題一:寫出選擇法排序
void select_sort(int a[],int N)
{ int? i , j, k, t;
for(i=0; i<N; i++)
{
k=i;
? ? for( j=i+1; j<N; j ++)
if( a[j]<a[k])
? k=j;
tmp=a[k];
a[k]=a[i];
a[i]=tmp;
}
}
注釋:
以下為一個用C描述的函數實現上述排序:?
void sort(int array[],int n)?
{ // n 為數組元素個數?
int i,j,k,temp; // i 為基準位置,j 為當前被掃描元素位置,k 用于暫存出現的較小的元素的位置?
for(i=0;i<n-1;i++)?
{k=i;//初始化為基準位置?
for(j=i+1;j<n;j++)?
{?
if (array[j]<array[k]) k=j ; // k 始終指示出現的較小的元素的位置?
if(k!=i)?
{ temp=array[i];?
array[i]=array[k];?
array[k]=temp; // 將此趟掃描得到的最小元素與基準互換位置?
}?
} //for?
}?
}?
其實現相對簡單,效率比較低,時間復雜度為O(n2) (n 的平方) ,為就地排序。?
*鏈表問題匯總*
179寫一函數creat, 用來建立一個動態鏈表,各結點數據由鍵盤輸入。
struct student
?{
? long num;
? float score;
? stuent *next;
?};
?
?student *creat (void)
?{
? student *head;
? student *p1=null,*p2=null;
? int n=0;
? p1=p2=new student;
? cin>>p1->num>>p1->score;
? head=null;
? while(p1->num !=0)
? {
? n=n+1;
? if(1==n) head=p1;
? else ?
? p2->next=p1;
? p2=p1;
? p1= new student;
? cin>>p1->mum>>p1->score;
? }
? p2->next =NULL;
? return (head);
?}
?
180,寫一print函數,將鏈表中的各數據遍歷輸出
? void print(student *head )
? {
? student *p;
? cout<<"there"<<n<<"records"<<endl;
? p=head;
? if(head!=NULL)
? do
? {
? cout<<p->num<<" "<<p->score<<endl;
? p=p->next;
? }while(p!=NULL)
? }
?
?181.寫一del函數,用來刪除動態鏈表中,指定的結點數據
?void *del(student *head, long num)
?{
? student *p1,*p2;
? if(head==NULL)
? {return (head);}
? p1=head;
? while(num!=p1->num && p1->next !=NULL)
? {
? p2=p1;
? p1=p1->next;
? }
? if(num == p1->num)
? {
? if(p1==head)
? head=p1->next;
? else
? p2->next=p1->next;
? cout<<"delete:"<<num<<endl;
? n=n-1;
? }
? else
? cout<<"can not find"<<num;
? return(head);
?}
?182 寫一函數insert,用來向動態鏈表插入一結點
?Student *insert(student *head, student *stud)
?{
? student *p0 ,*p1, *p2;
? p1=head;
? p0=stud;
? if(head == NULL)
? {
? head=p0;
? p0->next=NULL;
? }
? else
? {
? while((p0->num >p1->num) && (p1->next!=NULL) )
? {
? p2=p1;
? p1=p1->next;
? }
? if(p0->num <= p1->num)
? {
? if(head ==p1)
? head=p0;
? else
? p2->next=p0;
? p0->next=p1;
? }
? else
? {
? p1->next=p0;
? p0->next=NULL;
? }
? }
? n=n+1;
? return(head);
??
?}
183 鏈表題:一個鏈表的結點結構
struct Node
{
int data ;
Node *next ;
};
typedef struct Node Node ;
(1)已知鏈表的頭結點head,寫一個函數把這個鏈表逆序 ( Intel)
Node * ReverseList(Node *head) //鏈表逆序
{
if ( head == NULL || head->next == NULL )
return head;
Node *p1 = head ;
Node *p2 = p1->next ;
Node *p3 = p2->next ;
p1->next = NULL ;
while ( p3 != NULL )
{
p2->next = p1 ;
p1 = p2 ;
p2 = p3 ;
p3 = p3->next ;
}
p2->next = p1 ;
head = p2 ;
return head ;
}
(2)已知兩個鏈表head1 和head2 各自有序,請把它們合并成一個鏈表依然有序。(保留所有結點,即便大小相同)
Node * Merge(Node *head1 , Node *head2)
{
if ( head1 == NULL)
return head2 ;
if ( head2 == NULL)
return head1 ;
Node *head = NULL ;
Node *p1 = NULL;
Node *p2 = NULL;
if ( head1->data < head2->data )
{
head = head1 ;
p1 = head1->next;
p2 = head2 ;
}
else
{
head = head2 ;
p2 = head2->next ;
p1 = head1 ;
}
Node *pcurrent = head ;
while ( p1 != NULL && p2 != NULL)
{
if ( p1->data <= p2->data )
{
pcurrent->next = p1 ;
pcurrent = p1 ;
p1 = p1->next ;
}
else
{
pcurrent->next = p2 ;
pcurrent = p2 ;
p2 = p2->next ;
}
}
if ( p1 != NULL )
pcurrent->next = p1 ;
if ( p2 != NULL )
pcurrent->next = p2 ;
return head ;
}
(3)已知兩個鏈表head1 和head2 各自有序,請把它們合并成一個鏈表依然有序,這次要求用遞歸方法進行。 (Autodesk)
答案:
Node * MergeRecursive(Node *head1 , Node *head2)
{
if ( head1 == NULL )
return head2 ;
if ( head2 == NULL)
return head1 ;
Node *head = NULL ;
if ( head1->data < head2->data )
{
head = head1 ;
head->next = MergeRecursive(head1->next,head2);
}
else
{
head = head2 ;
head->next = MergeRecursive(head1,head2->next);
}
return head ;
}
184.利用鏈表實現將兩個有序隊列A和B合并到有序隊列H中,不準增加其他空間。
請提供全一點的程序
以升序為例:
while(a != NULL && b!= NULL)
{
if (a->data < b->data)
{
h->data = a->data;
a = a->next;
}
else if (a->data == b->data)
{
h->data = a->data;
a = a->next;
b = b->next;
}
else
{
h->data = b->data;
b = b->next
}
h = h->next;
}
if (a == NULL)
{
while (b != NULL)
{
h->data = b->data;
h = h->next;
b = b->next;
}
}
else
{
while(a != NULL)
{
h->data = a->next;
h = h->next;
a = a->next;
}
}
185單向鏈表的反轉是一個經常被問到的一個面試題,也是一個非常基礎的問題。比如一個鏈表是這樣的: 1->2->3->4->5 通過反轉后成為5->4->3->2->1。最容易想到的方法遍歷一遍鏈表,利用一個輔助指針,存儲遍歷過程中當前指針指向的下一個元素,然后將當前節點元素的指針反轉后,利用已經存儲的指針往后面繼續遍歷。源代碼如下:
struct linka {
?? ? int data;
?? ? linka* next;
};
void reverse(linka*& head)
{
?? ? if(head ==NULL)
? ? ? ? ? return;
?? ? linka*pre, *cur, *ne;
?? ? pre=head;
?? ? cur=head->next;
?? ? while(cur)
?? ? {
? ? ? ? ? ne = cur->next;
? ? ? ? ? cur->next = pre;
? ? ? ? ? pre = cur;
? ? ? ? ? cur = ne;
?? ? }
?? ? head->next = NULL;
?? ? head = pre;
}
還有一種利用遞歸的方法。這種方法的基本思想是在反轉當前節點之前先調用遞歸函數反轉后續節點。源代碼如下。不過這個方法有一個缺點,就是在反轉后的最后一個結點會形成一個環,所以必須將函數的返回的節點的next域置為NULL。因為要改變head指針,所以我用了引用。算法的源代碼如下:
linka* reverse(linka* p,linka*& head)
{
?? ? if(p == NULL || p->next == NULL)
?? ? {
? ? ? ? ? head=p;
? ? ? ? ? return p;
?? ? }
?? ? else
?? ? {
? ? ? ? ? linka* tmp = reverse(p->next,head);
? ? ? ? ? tmp->next = p;
? ? ? ? ? return p;
?? ? }
}
186 對如下雙鏈表
typedef struct _node
{
int iData;
struct _node *pPrev;
struct _node *pNext;
}node;
a.請寫出代碼,將node*n插入到node*p后。
b.如果多線程同時訪問此鏈表,需要加鎖,請說明以下步驟
(a)申請內存給n.
(b)N數據初始化。
(c)插入
注意加鎖和解鎖的時機。
node* insert(node* p, node* n)
{
if ((p == NULL) || (n == NULL))
{
return NULL;
}
if (p->pNext != NULL)
{
p->pNext->pPrev = n;
}
n->pPrev = p;
n->pNext = p->pNext;
p->pNext = n;
return n;
}
187、試創建二叉數,并寫出常見的幾種遍歷方式 ?
#include "stdio.h"
#include "string.h"
#include <stdlib.h>
#define NULL 0
typedef struct BiTNode{
? ? char data;
? ? struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree Create(BiTree T){
? ? char ch;
? ? ch=getchar();
? ? if(ch=='0')
T=NULL;
? ? else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
? ? printf("Error!");
T->data=ch;
T->lchild=Create(T->lchild);
T->rchild=Create(T->rchild);
? ? }
? ? return T;
}
void Preorder(BiTree T){
?? ? if(T){
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}//先序遍歷
void Inorder(BiTree T){
? ? if(T){
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}//中序遍歷
void Postorder(BiTree T){
? ? if(T){
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}//后序遍歷
188、 前序遍歷輸入,如圖所示,寫出后序遍歷輸出結果?
?例如二叉樹:
?
?
?
輸入序列ABD..EH...CF.I..G..
輸出結果為:?
答案:
輸出結果為:DHEBIFGCA
★不用庫函數,用C語言實現將一整型數字轉化為字符串★
方法1:
int getlen(char *s){
int n;
for(n = 0; *s != '\0'; s++)
n++;
return n;
}
void reverse(char s[])
{
int c,i,j;
for(i = 0,j = getlen(s) - 1; i < j; i++,j--){
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
void itoa(int n,char s[])
{
int i,sign;
if((sign = n) < 0)
n = -n;
i = 0;
do{/*以反序生成數字*/
s[i++] = n%10 + '0';/*get next number*/
}while((n /= 10) > 0);/*delete the number*/
if(sign < 0)
s[i++] = '-';
s[i] = '\0';
reverse(s);
}
方法2:
#include <iostream>
using namespace std;
void itochar(int num);
void itochar(int num)
{
int i = 0;
int j ;
char stra[10];
char strb[10];
while ( num )
{
stra[i++]=num%10+48;
num=num/10;
}
stra[i] = '\0';
for( j=0; j < i; j++)
{
strb[j] = stra[i-j-1];
}
strb[j] = '\0';
cout<<strb<<endl;
}
int main()
{
int num;
cin>>num;
itochar(num);
return 0;
}