黄色在线观看视频-黄色在线免费看-黄色在线视频免费-黄色在线视频免费看-免费啪啪网-免费啪啪网站

知識:

　　1.數據結構中對象的定義,存儲的表示及操作的實現.
　　2.線性:線性表、棧、隊列、數組、字符串（廣義表不考）
　　　樹：二叉樹
　　　集合：查找，排序
　　　圖(不考)

能力：

　　分析，解決問題的能力

過程：

　　● 確定問題的數據。
　　● 確定數據間的關系。
　　● 確定存儲結構（順序－數組、鏈表－指針）
　　● 確定算法
　　● 編程
　　● 算法評價（時間和空間復雜度，主要考時間復雜度）

一、數組

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

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

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

　　算法

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

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

　　例程：求兩個長整數之和。

　　a=13056952168
　　b=87081299
　　數組:
　　a[]:1 3 0 5 6 9 5 2 1 6 8
　　b[]:8 7 0 8 1 2 9 9 
　　由于以上的結構不夠直觀(一般越是直觀越容易解決) 將其改為:
　　a[]:11　8 6 1 2 5 9 6 5 0 3 1 a[0]=11(位數)
　　b[]: 8　9 9 2 1 8 0 7 8 0 0 0 b[0]=8
　　c進位　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位數)由c[max_s+1]決定!
　　注意:在求C前應該將C(max_s+1)位賦0.否則為隨機數; 較小的整數高位賦0.
　　算法:已知a,b兩個長整數,結果:c=a+b;
　　總共相加次數: 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位數:
　　if(c[max_s+1]==0)
　　　c[0]=max_s;
　　else
　　　c[0]=max_s+1;
　　以下代碼是我編的(畢竟是初學者.不太簡潔大家不要見怪!):
　　/*兩長整數相加*/
　　 #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);
　　}

時間復雜度計算:

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

[1] [2] [3] [4] [5] [6] [7] [8] [9] 下一頁