知識(shí):

　　1.數(shù)據(jù)結(jié)構(gòu)中對(duì)象的定義,存儲(chǔ)的表示及操作的實(shí)現(xiàn).
　　2.線性:線性表、棧、隊(duì)列、數(shù)組、字符串（廣義表不考）
　　　樹(shù)：二叉樹(shù)
　　　集合：查找，排序
　　　圖(不考)

能力：

　　分析，解決問(wèn)題的能力

過(guò)程：

　　● 確定問(wèn)題的數(shù)據(jù)。
　　● 確定數(shù)據(jù)間的關(guān)系。
　　● 確定存儲(chǔ)結(jié)構(gòu)（順序－數(shù)組、鏈表－指針）
　　● 確定算法
　　● 編程
　　● 算法評(píng)價(jià)（時(shí)間和空間復(fù)雜度，主要考時(shí)間復(fù)雜度）

一、數(shù)組

　　1、存放于一個(gè)連續(xù)的空間
　　2、一維～多維數(shù)組的地址計(jì)算方式
　　　已知data[0][0]的內(nèi)存地址，且已知一個(gè)元素所占內(nèi)存空間Ｓ求data[i][j]在內(nèi)存中的地址。
　　　公式：（add+(i*12+j)*S)(假設(shè)此數(shù)組為data[10][12])

　　注意：起始地址不是data[0][0]時(shí)候的情況。起始地址為data[-3][8]和情況；

　　3、順序表的定義
　　　存儲(chǔ)表示及相關(guān)操作
　　4、順序表操作中時(shí)間復(fù)雜度估計(jì)
　　5、字符串的定義（字符串就是線性表），存儲(chǔ)表示
　　　模式匹配算法（簡(jiǎn)單和KMP（不考））
　　6、特殊矩陣：存儲(chǔ)方法（壓縮存儲(chǔ)（按行，按列））
　　　三對(duì)角：存儲(chǔ)于一維數(shù)組
　　　三對(duì)角問(wèn)題：已知A_ij能求出在一維數(shù)組中的下標(biāo)k;已知下標(biāo)k求A_ij。
　　7、稀疏矩陣：定義，存儲(chǔ)方式：三元組表、十字鏈表（屬于圖部分，不考）

　　算法

　　● 數(shù)組中元素的原地逆置； 對(duì)換
　　● 在順序表中搜索值為X的元素；
　　● 在有序表中搜索值為X的元素；（折半查找）
　　● 在順序表中的第i個(gè)位置插入元素X；
　　● 在順序表中的第i個(gè)位置刪除元素X；
　　● 兩個(gè)有序表的合并；算法？

　　線性表數(shù)據(jù)結(jié)構(gòu)定義：
　　　Typedef struct {
　　　　int data[max_size];
　　　　int len;
　　　}linear_list;
　　● 模式匹配
　　● 字符串相加
　　● 求子串
　　● （i,j）<=>K 注意：不同矩陣所用的公式不同；
　　● 稀疏矩陣的轉(zhuǎn)置（兩種方式，后種為妙）
　　● 和數(shù)組有關(guān)的算法

　　例程：求兩個(gè)長(zhǎng)整數(shù)之和。

　　a=13056952168
　　b=87081299
　　數(shù)組:
　　a[]:1 3 0 5 6 9 5 2 1 6 8
　　b[]:8 7 0 8 1 2 9 9 
　　由于以上的結(jié)構(gòu)不夠直觀(一般越是直觀越容易解決) 將其改為:
　　a[]:11　8 6 1 2 5 9 6 5 0 3 1 a[0]=11(位數(shù))
　　b[]: 8　9 9 2 1 8 0 7 8 0 0 0 b[0]=8
　　c進(jìn)位　0 1 1 0 0 1 1 1 1 0 0 
　　c[]:11　7 6 4 3 3 0 4 4 2 3 1 c[0]的值(C位數(shù))由c[max_s+1]決定!
　　注意:在求C前應(yīng)該將C(max_s+1)位賦0.否則為隨機(jī)數(shù); 較小的整數(shù)高位賦0.
　　算法:已知a,b兩個(gè)長(zhǎng)整數(shù),結(jié)果:c=a+b;
　　總共相加次數(shù): max_s=max(a[],b[])
　　程序:
　　for(i=1;i<=max_s;i++) {
　　　k=a[i]+b[i]+c[i];
　　　c[i]=k%10;
　　　c[i+1]=k/10;
　　}
　　求c位數(shù):
　　if(c[max_s+1]==0)
　　　c[0]=max_s;
　　else
　　　c[0]=max_s+1;
　　以下代碼是我編的(畢竟是初學(xué)者.不太簡(jiǎn)潔大家不要見(jiàn)怪!):
　　/*兩長(zhǎng)整數(shù)相加*/
　　 #include<stdio.h>
　　 #include<string.h>
　　#define PRIN printf("\n");

　　int flag=0; /*a[0]>b[0]?1:0*/

　　/* max(a[],b[]) {}*/

　　change(char da[],char db[],int a[],int b[],int c[]) {
　　　int i;
　　　if(a[0]>b[0]) {
　　　　for(i=1;i<=a[0];a[i]=da[a[0]-i]-'0',i++); /*a[0]-'0' so good!*/
　　　　for(i=1;i<=b[0];b[i]=db[b[0]-i]-'0',i++);
　　　　for(i=b[0]+1;i<=a[0];b[i]=0,i++);
　　　　for(i=1;i<=a[0]+1;c[i]=0,i++);
　　　　flag=1;
　　　}
　　　else {
　　　　for(i=1;i<=b[0];b[i]=db[b[0]-i]-'0',i++);
　　　　for(i=1;i<=a[0];a[i]=da[a[0]-i]-'0',i++);
　　　　for(i=a[0]+1;i<=b[0];a[i]=0,i++);
　　　　for(i=1;i<=b[0]+1;c[i]=0,i++);
　　　}
　　}

　　add(int a[],int b[],int c[]) {
　　　int i,sum;
　　　if(flag==1) {
　　　　for(i=1;i<=a[0];i++) {
　　　　　sum=a[i]+b[i]+c[i];
　　　　　c[i+1]=sum/10;
　　　　　c[i]=sum%10;
　　　　}
　　　　if(c[a[0]+1]==0)
　　　　　c[0]=a[0];
　　　　else
　　　　　c[0]=a[0]+1;
　　　}
　　　else {
　　　　for(i=1;i<=b[0];i++) {
　　　　　sum=a[i]+b[i]+c[i];
　　　　　c[i+1]=sum/10;
　　　　　c[i]=sum%10;
　　　　}
　　　　if(c[b[0]+1]==0)
　　　　　c[0]=b[0];
　　　　else
　　　　　c[0]=b[0]+1;
　　　}
　　}

　　void print(int m[]) {
　　　int i;
　　　for(i=m[0];i>=1;i--)
　　　　printf("%d,",m[i]); PRIN
　　}

　　main(){
　　　int s;
　　　int a[20],b[20],c[20];
　　　char da[]={"123456789"};
　　　char db[]={"12344443"};
　　　a[0]=strlen(da);
　　　b[0]=strlen(db);
　　　printf("a[0]=%d\t",a[0]);
　　　printf("b[0]=%d",b[0]); PRIN
　　　change(da,db,a,b,c);
　　　printf("flag=%d\n",flag); PRIN
　　　printf("-----------------\n");
　　　if(flag==1) {
　　　　print(a); PRIN
　　　　s=abs(a[0]-b[0]);
　　　　printf("+");
　　　　　for(s=s*2-1;s>0;s--)
　　　　　　printf(" ");
　　　　　　print(b); PRIN
　　　}
　　　else {
　　　　s=abs(a[0]-b[0]);
　　　　printf("+");
　　　　for(s=s*2-1;s>0;s--)
　　　　　printf(" ");
　　　　　print(a); PRIN
　　　　　print(b); PRIN
　　　}
　　　add(a,b,c);
　　　printf("-----------------\n");
　　　print(c);
　　}

時(shí)間復(fù)雜度計(jì)算:

　　● 確定基本操作
　　● 計(jì)算基本操作次數(shù)
　　● 選擇T(n)
　　● lim(F(n)/T(n))=c
　　● 0(T(n))為時(shí)間復(fù)雜度
　　上例子的時(shí)間復(fù)雜度為O(max_s);

[1] [2] [3] [4] [5] [6] [7] [8] [9] 下一頁(yè)