第二章線性表的概念;
順序儲存和鏈結儲存的線性表的資料結構、特性;
順序儲存的特性:查詢方便,不易擴充
鏈結儲存的特性:插入刪除方便
順序儲存和鏈結儲存的線性表的基本演算法:建立、插入、查詢、刪除等;
鍊錶的其他形式(帶表頭、迴圈、雙向、雙向迴圈等)的概念及基本演算法(與一般鍊錶的不同處)。
帶表頭:便於其後結點執行標準化操作
迴圈:首尾相接
雙向:既可以查詢前繼又可以查詢後繼
雙向迴圈:結合以上兩點
鍊錶逆轉;
第二章相關演算法列舉如下
1.。順序線性表的插入
int sq_insert(int list,int *p_n,int i,int x)
2.順序線性表的刪除
int sq_delete(int list,int *p_n,int i)
3.鏈式線性表的建立
node *create_link_list(int n)
q->link=null;
return(p_head);/*返回的是假頭*/
※4.鏈式線性表的插入(i之後)
int insert(node* *p_head,int i,int a)
r=new(node);
r->data=a;
r->link=q->link;
q->link=r;
}※5.鏈式線性表的刪除
int del(node* *p_head,int i)
if(p==null) return(0);
q->link=p->link;
delete(p);
return(1);
}6.單鏈表的逆置
node * reverse(node *head)
return(head);
}7.試寫一高效的演算法,刪除表中所有大於mink且小於maxk的元素
void delete_between(int a,int mink,int maxk)
}第三章
棧與佇列的概念;
棧:只允許在一端進行插入和刪除的線性表
佇列:只允許在一端進行插入,且只允許在另一端進行刪除的線性表
順序棧和鏈棧的資料結構與基本演算法;
順序佇列(尤其是迴圈佇列)和鏈佇列的資料結構與基本演算法;
棧的應用演算法;
如何判斷順序棧的空與滿、如何判斷迴圈佇列的空與滿;
判斷順序棧的空與滿:
若top的初始值是-1 則判空條件是if(top==-1) 判滿條件是if(top==maxn)
若top的初始值是0 則判空條件是if(top==0) 判滿條件是if(top==maxn-1)
判斷迴圈佇列的空與滿
中綴表示式與字尾表示式規則以及兩者間的轉換。
見書p20頁
第三章相關演算法列舉如下:
1.順序棧的插入和刪除
#define maxn 26
char stack[maxn]
int top=0;
int push(char x)
int pop(char *p_y)
3.普通佇列的進隊和出隊演算法
#define maxn 26
char q[maxn];
int head=-1;,tail=-1;
int en_queue(char x)
int de_queue(char *p_y)
2.鏈結棧的插入和刪除
#include
struct node
;typedef struct node node ;
node * top=null;
void push_linkstack(char x)
int pop_linkstack(char *p_y)
第四章二維陣列的元素在順序儲存線性表中的相對位址;
假設有二維陣列a[t1][t2],則&a[i][j]=&a[0][0]+(i*t2+j)*s
壓縮儲存下三角矩陣的做法以及矩陣元素與線性表陣列元素的對應關係;
n階下三角矩陣:&a[i][j]=&a[0][0]+[i*(i+1)/2+j]*s
壓縮儲存稀疏矩陣的演算法;
三元組表示的稀疏矩陣的快速轉置
void mat_fast_transpose(int a[3],int b[3])}}
計算乙個三元組表示的稀疏矩陣的對角線元素之和
解:對n階矩陣,主對角線上的元素滿足i=j關係;而另一條次主對角線上的元素滿足滿足n-1-i=j關係,在三元組表示的稀疏矩陣中,元素下標符合這兩個條件的就是對角線元素。
int mat_sum(int a[3])
return(sum1+sum2);
}廣義表的概念與資料結構,取頭操作與取尾操作以及其應用;見書p56
串與子串的概念、基本演算法,以及進一步演算法(如在串中插入子串、將串或某個子串逆置等);
在串中插入字串的演算法
int strins(char s1,int i,char s2)
※串的逆置演算法
void reverse_string(char s)
資料結構複習提綱
如 以10,15 20,5,1,30,23為權值構造一棵哈夫曼樹並求出wpl,最後確定葉子結點的哈夫曼編碼。5 雜湊表的構造及在雜湊表上查詢的效率分析 6 拆半查詢的效能分析 通過判定樹 7 二叉排序樹的構造及其查詢的效能分析 8 二叉平衡樹的構造及其查詢效能分析 9 寫出各種排序下的資料變化過程 ...
《資料結構》複習提綱2019
江蘇城市職業學院五年制高職 資料結構 課程複習提綱 2008 級計算機應用技術專業 第五學期 用 一 考核說明 本複習提綱依據的教材為 許樂平主編,廣播電視大學出版社出版的 資料結構 c 描述 許樂平主編,廣播電視大學出版社出版的 資料結構實驗指導與測試 考核形式 考試課。考核方法 期末考試以筆試為...
資料結構複習提綱考試重點
一 基礎知識 第1章緒論 1 什麼是資料結構,分類 2 抽象資料型別的形式定義 3 邏輯結構 物理結構 儲存結構 4 什麼是演算法 5 時間複雜度 第2章線性表 6 線性表的定義和術語 7 線性表的儲存結構 順序錶鏈表 線性鍊錶 單鏈表 迴圈鍊錶 雙向鍊錶 第3章棧和佇列 8 棧 順序棧鏈式棧9 佇...