Ⅰ 廣義表和線性表的區別
一、含義不同：
1、線性表，最基本、最簡單、也是最常用的一種數據結構。線性表（linear list）是數據結構的一種，一個線性表是n個具有相同特性的數據元素的有限序列。
2、廣義表(Lists，又稱列表)，一種非線性的數據結構，是線性表的一種推廣。即廣義表中放鬆對表元素的原子限制，容許它們具有其自身結構。
二、用途不同：
1、時間有序表、排序表、和頻率有序表都可以看做是線性表的推廣。如果按照結點到達結構的時間先後，作為確定結點之間關系的，這樣一種線性結構稱之為時間有序表。
2、廣義表被廣泛的應用於人工智慧等領域的表處理語言LISP語言中。在LISP語言中，廣義表是一種最基本的數據結構，就連LISP 語言的程序也表示為一系列的廣義表。
(1)廣義表為什麼不能存儲樹擴展閱讀：
由於廣義表是對線性表和樹的推廣，並且具有共享和遞歸特性的廣義表可以和有向圖建立對應，因此廣義表的大部分運算與這些數據結構上的運算類似。
在此，只討論廣義表的兩個特殊的基本運算：取表頭head(Ls)和取表尾tail(Ls)。
根據表頭、表尾的定義可知：任何一個非空廣義表的表頭是表中第一個元素，它可以是原子，也可以是子表，而其表尾必定是子表。
Ⅱ 二叉樹怎樣用廣義表表示
二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態： (1)空二叉樹——(a)； (2)只有一個根結點的二叉樹——(b)； (3)右子樹為空的二叉樹——(c)； (4)左子樹為空的二叉樹——(d)； (5)完全二叉樹——(e)注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。 二叉樹 (binary tree) 是另一種樹型結構，它的特點是每個結點至多隻有二棵子 樹 (即二叉樹中不存在度大於 2的結點 )，並且，二叉樹的子樹有左右之分，其次序不能任意顛倒 . 二叉樹是一種數據結構
Ⅲ 廣義表與線性表、樹、圖的關系
說有關系也沒關系說沒關系也有關系。他們只是為了解決不同問題而提出的不同結構，可以互相演化但是沒有必要演化。
Ⅳ 學了一個學期了，很多地方都不會，廣義表是怎麼回事啊
這頁的可以編譯通過了：
#include <stdio.h>
#include <stdlib.h>
#define STACK_MAX_SIZE 30
#define QUEUE_MAX_SIZE 30
#ifndef elemType
typedef char elemType;
#endif
/************************************************************************/
/* 以下是關於二叉樹操作的11個簡單演算法 */
/************************************************************************/
struct BTreeNode{
elemType data;
struct BTreeNode *left;
struct BTreeNode *right;
};
/* 1.初始化二叉樹 */
void initBTree(struct BTreeNode* *bt)
{
*bt = NULL;
return;
}
/* 2.建立二叉樹(根據a所指向的二叉樹廣義表字元串建立) */
void createBTree(struct BTreeNode* *bt, char *a)
{
struct BTreeNode *p;
struct BTreeNode *s[STACK_MAX_SIZE];/* 定義s數組為存儲根結點指針的棧使用 */
int top = -1; /* 定義top作為s棧的棧頂指針，初值為-1,表示空棧 */
int k; /* 用k作為處理結點的左子樹和右子樹，k = 1處理左子樹，k = 2處理右子樹 */
int i = 0; /* 用i掃描數組a中存儲的二叉樹廣義表字元串，初值為0 */
*bt = NULL; /* 把樹根指針置為空，即從空樹開始建立二叉樹 */
/* 每循環一次處理一個字元，直到掃描到字元串結束符\0為止 */
while(a[i] != '\0'){
switch(a[i]){
case ' ':
break; /* 對空格不作任何處理 */
case '(':
if(top == STACK_MAX_SIZE - 1){
printf("棧空間太小！\n");
exit(1);
}
top++;
s[top] = p;
k = 1;
break;
case ')':
if(top == -1){
printf("二叉樹廣義表字元串錯誤!\n");
exit(1);
}
top--;
break;
case ',':
k = 2;
break;
default:
p = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
p->data = a[i];
p->left = p->right = NULL;
if(*bt == NULL){
*bt = p;
}else{
if( k == 1){
s[top]->left = p;
}else{
s[top]->right = p;
}
}
}
i++; /* 為掃描下一個字元修改i值 */
}
return;
}
/* 3.檢查二叉樹是否為空，為空則返回1,否則返回0 */
int emptyBTree(struct BTreeNode *bt)
{
if(bt == NULL){
return 1;
}else{
return 0;
}
}
/* 4.求二叉樹深度 */
int BTreeDepth(struct BTreeNode *bt)
{
if(bt == NULL){
return 0; /* 對於空樹，返回0結束遞歸 */
}else{
int dep1 = BTreeDepth(bt->left); /* 計算左子樹的深度 */
int dep2 = BTreeDepth(bt->right); /* 計算右子樹的深度 */
if(dep1 > dep2){
return dep1 + 1;
}else{
return dep2 + 1;
}
}
}
/* 5.從二叉樹中查找值為x的結點，若存在則返回元素存儲位置，否則返回空值 */
elemType *findBTree(struct BTreeNode *bt, elemType x)
{
if(bt == NULL){
return NULL;
}else{
if(bt->data == x){
return &(bt->data);
}else{ /* 分別向左右子樹遞歸查找 */
elemType *p;
if(p = findBTree(bt->left, x)){
return p;
}
if(p = findBTree(bt->right, x)){
return p;
}
return NULL;
}
}
}
/* 6.輸出二叉樹(前序遍歷) */
void printBTree(struct BTreeNode *bt)
{
/* 樹為空時結束遞歸，否則執行如下操作 */
if(bt != NULL){
printf("%c", bt->data); /* 輸出根結點的值 */
if(bt->left != NULL || bt->right != NULL){
printf("(");
printBTree(bt->left);
if(bt->right != NULL){
printf(",");
}
printBTree(bt->right);
printf(")");
}
}
return;
}
/* 7.清除二叉樹，使之變為一棵空樹 */
void clearBTree(struct BTreeNode* *bt)
{
if(*bt != NULL){
clearBTree(&((*bt)->left));
clearBTree(&((*bt)->right));
free(*bt);
*bt = NULL;
}
return;
}
/* 8.前序遍歷 */
void preOrder(struct BTreeNode *bt)
{
if(bt != NULL){
printf("%c ", bt->data); /* 訪問根結點 */
preOrder(bt->left); /* 前序遍歷左子樹 */
preOrder(bt->right); /* 前序遍歷右子樹 */
}
return;
}
/* 9.前序遍歷 */
void inOrder(struct BTreeNode *bt)
{
if(bt != NULL){
inOrder(bt->left); /* 中序遍歷左子樹 */
printf("%c ", bt->data); /* 訪問根結點 */
inOrder(bt->right); /* 中序遍歷右子樹 */
}
return;
}
/* 10.後序遍歷 */
void postOrder(struct BTreeNode *bt)
{
if(bt != NULL){
postOrder(bt->left); /* 後序遍歷左子樹 */
postOrder(bt->right); /* 後序遍歷右子樹 */
printf("%c ", bt->data); /* 訪問根結點 */
}
return;
}
/* 11.按層遍歷 */
void levelOrder(struct BTreeNode *bt)
{
struct BTreeNode *p;
struct BTreeNode *q[QUEUE_MAX_SIZE];
int front = 0, rear = 0;
/* 將樹根指針進隊 */
if(bt != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = bt;
}
while(front != rear){ /* 隊列非空 */
front = (front + 1) % QUEUE_MAX_SIZE; /* 使隊首指針指向隊首元素 */
p = q[front];
printf("%c ", p->data);
/* 若結點存在左孩子，則左孩子結點指針進隊 */
if(p->left != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->left;
}
/* 若結點存在右孩子，則右孩子結點指針進隊 */
if(p->right != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->right;
}
}
return;
}
/************************************************************************/
int main(int argc, char *argv[])
{
struct BTreeNode *bt; /* 指向二叉樹根結點的指針 */
char *b; /* 用於存入二叉樹廣義表的字元串 */
elemType x, *px;
initBTree(&bt);
printf("輸入二叉樹廣義表的字元串：\n");
/* scanf("%s", b); */
b = "a(b(c), d(e(f, g), h(, i)))";
createBTree(&bt, b);
if(bt != NULL)
printf(" %c ", bt->data);
printf("以廣義表的形式輸出：\n");
printBTree(bt); /* 以廣義表的形式輸出二叉樹 */
printf("\n");
printf("前序："); /* 前序遍歷 */
preOrder(bt);
printf("\n");
printf("中序："); /* 中序遍歷 */
inOrder(bt);
printf("\n");
printf("後序："); /* 後序遍歷 */
postOrder(bt);
printf("\n");
printf("按層："); /* 按層遍歷 */
levelOrder(bt);
printf("\n");
/* 從二叉樹中查找一個元素結點 */
printf("輸入一個待查找的字元：\n");
scanf(" %c", &x); /* 格式串中的空格跳過空白字元 */
px = findBTree(bt, x);
if(px){
printf("查找成功：%c\n", *px);
}else{
printf("查找失敗！\n");
}
printf("二叉樹的深度為：");
printf("%d\n", BTreeDepth(bt));
clearBTree(&bt);
return 0;
}
Ⅳ 廣義表一般採用鏈式存儲結構,而不採用順序存儲結構,是什麼原因
廣義表 的元素可以是廣義表 順序存儲的話 如果添加或者刪除一個元素的話 開銷太大吧
Ⅵ 任何廣義表都可以用樹形結構表示
錯誤，樹結構可以用廣義表表示
Ⅶ 如何用廣義表建樹～
void CreateBiTree(BiTree *T,char *a)
{
BiTree s[10];
int j, k;
BiTree p;
int top=-1;
T=NULL;
printf("輸入樹共有多少個結點\n");
scanf("%d",&j);
s=(BiTree *)malloc(j*sizeof(BiTNode));
if(!s)
exit(OVERFLOW);
int i=0;
while(a[i]!='\0')
{
switch(a[i])
{
case ' ':
break;
case '(':
if(top==10)
{
printf("空間太小\n");
exit(1);
}
top++;
s[top]=p;
k=1;
break;
case ')':
if(top==-1)
{
printf("二叉樹廣義表字元串有錯\n");
exit(-1);
}
top--;
break;
case ',':
k=2;
break;
default:
p=(BiTree)malloc(sizeof(BiTNode));
if(!p)
exit(OVERFLOW);
p->data=a[i];
p->Lchild=p->Rchild=NULL;
if(T==NULL)
{
T=&p;
}
else
{
if(k==1)
s[top]->Lchild=p;
else
s[top]->Rchild=p;
}
}
i++;
}
}
Ⅷ 廣義表的兩種存儲結構有什麼不同
CPU內部
第一層：通用寄存器文件
第二層：指令和數據緩沖棧
第三層：緩存
第四層：主存儲器（DRAM）
第五層：在線外部存儲（硬碟驅動器）
第六層：離線外部存儲（磁帶，光碟存儲器等）
層次結構，主要體現在內存的存取速度~~~ ~~
①多個內存和使它們並行工作。本質：添加瓶頸的數目份，使它們並行地工作，從而減緩固定的瓶頸。
②多級存儲系統，特別是高速緩存技術，該技術是一種影響系統的性能，以減少存儲器的帶寬，該方案的最佳結構。本質的：瓶頸構件分割成多個管道組件，並增加運行時間的重疊，以增加速度，減緩固定瓶頸。
③設置各種內部緩沖存儲器的微處理器，以減少對存儲器的訪問的壓力。增加寄存器的數量在CPU中，也大大緩解了存儲器中的壓力。精華液：緩沖技術來減緩臨時瓶頸。
Ⅸ 數據結構廣義表的問題
第一章 數據結構基本概念
1、基本概念：理解什麼是數據、數據對象、數據元素、數據結構、數據的邏輯結構與物理結構、邏輯結構與物理結構間的關系。
2、面向對象概念：理解什麼是數據類型、抽象數據類型、數據抽象和信息隱蔽原則。了解什麼是面向對象。由於目前關於這個問題有許多說法，我們採用了一種最流行的說法，即Coad與Yourdon 給出的定義：面向對象 = 對象 + 類 + 繼承 + 通信。
要點：
·抽象數據類型的封裝性
·面向對象系統結構的穩定性
·面向對象方法著眼點在於應用問題所涉及的對象
3、數據結構的抽象層次：理解用對象類表示的各種數據結構
4、演算法與演算法分析：理解演算法的定義、演算法的特性、演算法的時間代價、演算法的空間代價。
要點：·演算法與程序的不同之處需要從演算法的特性來解釋
·演算法的正確性是最主要的要求
·演算法的可讀性是必須考慮的
·程序的程序步數的計算與演算法的事前估計
·程序的時間代價是指演算法的漸進時間復雜性度量
第二章 數組
1、作為抽象數據類型的數組：數組的定義、數組的按行順序存儲與按列順序存儲
要點：
·數組元素的存放地址計算
2、順序表：順序表的定義、搜索、插入與刪除
要點：
·順序表搜索演算法、平均比較次數的計算
·插入與刪除演算法、平均移動次數的計算
3、多項式：多項式的定義
4、字元串：字元串的定義及其操作的實現
要點：
·串重載操作的定義與實現
第三章 鏈接表
1、單鏈表：單鏈表定義、相應操作的實現、單鏈表的游標類。
要點：
·單鏈表的兩種定義方式（復合方式與嵌套方式）
·單鏈表的搜索演算法與插入、刪除演算法
·單鏈表的遞歸與迭代演算法
2、循環鏈表：單鏈表與循環鏈表的異同
3、雙向鏈表：雙向鏈表的搜索、插入與刪除演算法、鏈表帶表頭結點的優點
4、多項式的鏈接表示
第四章 棧與隊列
1、棧：棧的特性、棧的基本運算
要點：
·棧的數組實現、棧的鏈表實現
·棧滿及棧空條件、抽象數據類型中的先決條件與後置條件
2、棧的應用：用後綴表示計算表達式，中綴表示改後綴表示
3、隊列：隊列的特性、隊列的基本運算
要點：
·隊列的數組實現：循環隊列中隊頭與隊尾指針的表示，隊滿及隊空條件
·隊列的鏈表實現：鏈式隊列中的隊頭與隊尾指針的表示、
4、雙向隊列：雙向隊列的插入與刪除演算法
5、優先順序隊列：優先順序隊列的插入與刪除演算法
第五章 遞歸與廣義表
1、遞歸：遞歸的定義、遞歸的數據結構、遞歸問題用遞歸過程求解
要點：·鏈表是遞歸的數據結構，可用遞歸過程求解有關鏈表的問題
2、遞歸實現時棧的應用
要點：·遞歸的分層（樹形）表示：遞歸樹
·遞歸深度（遞歸樹的深度）與遞歸工作棧的關系
·單向遞歸與尾遞歸的迭代實現
3、廣義表：廣義表定義、廣義表長度、廣義表深度、廣義表表頭、廣義表表尾
要點：
·用圖形表示廣義表的存儲結構
·廣義表的遞歸演算法
第六章 樹與森林
1、樹：樹的定義、樹的基本運算
要點：
·樹的分層定義是遞歸的
·樹中結點個數與高度的關系
2、二叉樹：二叉樹定義、二叉樹的基本運算
要點：
·二叉樹性質、二叉樹中結點個數與高度的關系、不同種類的二叉樹棵數
·完全二叉樹的順序存儲、完全二叉樹的雙親、子女和兄弟的位置
·二叉樹的前序·中序·後序·層次遍歷
·前序
·中序
·後序的線索化二叉樹、前驅與後繼的查找方法
3、霍夫曼樹：霍夫曼樹的構造方法、霍夫曼編碼、帶權路徑長度的計算
4、樹的存儲：樹的廣義表表示、樹的雙親表示、樹與二叉樹的對應關系、樹的先根·中根·後根·層次遍歷。
5、堆：堆的定義、堆的插入與刪除演算法
要點：
·形成堆時用到的向下調整演算法及形成堆時比較次數的上界估計
·堆插入時用到的向上調整演算法
第七章 集合與搜索
1、集合的概念：集合的基本運算、集合的存儲表示
要點：
·用位數組表示集合時集合基本運算的實現
·用有序鏈表表示集合時集合基本運算的實現
2、並查集：並查集定義、並查集的三種基本運算的實現
3、基本搜索方法
要點：
·對一般表的順序搜索演算法（包括有監視哨和沒有監視哨）
·對有序順序表的順序搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
·對有序順序表的折半搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
4、二叉搜索樹：
要點：
·動態搜索樹與靜態搜索樹的特性
·二叉搜索樹的定義、二叉搜索樹上的搜索演算法、二叉搜索樹搜索時的平均搜索長度（成功與不成功）的計算。
·AVL樹結點上的平衡因子、AVL樹的平衡旋轉方法
·高度為h的AVL樹上的最少結點個數與最多結點個數
· AVL樹的搜索方法、插入與刪除方法
第八章 圖
1、圖：圖的定義與圖的存儲表示
要點：
·鄰接矩陣表示（通常是稀疏矩陣）
·鄰接表與逆鄰接表表示
·鄰接多重表(十字鏈表)表示
2、深度優先遍歷與廣度優先遍歷
要點：
·生成樹與生成樹林的定義
·深度優先搜索是個遞歸的過程，而廣度優先搜索是個非遞歸的過程
·為防止重復訪問已經訪問過的頂點，需要設置一個訪問標志數組visited
3、圖的連通性
要點：
·深度優先搜索可以遍歷一個連通分量上的所有頂點
·對非連通圖進行遍歷，可以建立一個生成森林
·對強連通圖進行遍歷，可能建立一個生成森林
·關節點的計算和以最少的邊構成重連通圖
4、最小生成樹
要點：
·對於連通網路、可用不會構成環路的權值最小的n-1條邊構成最小生成樹
·會畫出用Kruskal演算法及Prim演算法構造最小生成樹的過程
5、單源最短路徑
要點：
·採用逐步求解的方式求某一頂點到其他頂點的最短路徑
·要求每條邊的權值必須大於零
6、活動網路
要點：
·拓撲排序、關鍵路徑、關鍵活動、AOE網
·拓撲排序將一個偏序圖轉化為一個全序圖。
·為實現拓撲排序，要建立一個棧，將所有入度為零的頂點進棧
·關鍵路徑的計算
第九章 排序
1、基本概念：關鍵碼、初始關鍵碼排列、關鍵碼比較次數、數據移動次數、穩定性、附加存儲、內部排序、外部排序
2、插入排序：
要點：
·當待排序的關鍵碼序列已經基本有序時，用直接插入排序最快
3、選擇排序：
要點：
·用直接選擇排序在一個待排序區間中選出最小的數據時，與區間第一個數據對調，而不是順次後移。這導致方法不穩定。
·當在n個數據（n很大）中選出最小的5 ~ 8個數據時，錦標賽排序最快
·錦標賽排序的演算法中將待排序的數據個數n補足到2的k次冪2k-1<n≤2k
·在堆排序中將待排序的數據組織成完全二叉樹的順序存儲。
4、交換排序：
要點：
·快速排序是一個遞歸的排序方法
·當待排序關鍵碼序列已經基本有序時，快速排序顯著變慢。
5、二路歸並排序：
要點：
·歸並排序可以遞歸執行
·歸並排序需要較多的附加存儲。可以採用一種"推拉法"（參見教科書上習題）實現歸並排序，演算法的時間復雜度為O (n)、空間復雜度為O(1)
·歸並排序對待排序關鍵碼的初始排列不敏感，排序速度較穩定
6、外排序
要點：
·多路平衡歸並排序的過程、I/O緩沖區個數的配置
·外排序的時間分析、利用敗者樹進行多路平衡歸並
·利用置換選擇方法生成不等長的初始歸並段
·最佳歸並樹的構造及WPL的計算
第十章 索引與散列
1、線性索引：
要點：
·密集索引、稀疏索引、索引表計算
·基於屬性查找建立倒排索引、單元式倒排表
2、動態搜索樹
要點：
·平衡的m路搜索樹的定義、搜索演算法
·B樹的定義、B樹與平衡的m路搜索樹的關系
·B樹的插入（包括結點分裂）、刪除（包括結點調整與合並）方法
·B樹中結點個數與高度的關系
·B+樹的定義、搜索、插入與刪除的方法
3、散列表
要點：
·散列函數的比較
·裝填因子 a 與平均搜索長度的關系，平均搜索長度與表長m及表中已有數據對象個數n的關系
·解決地址沖突的（閉散列）線性探查法的運用，平均探查次數的計算
·線性探查法的刪除問題、散列表類的設計中必須為各地址設置三個狀態
·線性探查法中的聚集問題
·解決地址沖突的（閉散列）雙散列法的運用，平均探查次數的計算
·雙散列法中再散列函數的設計要求與表長m互質，為此m設計為質數較宜
·解決地址沖突的（閉散列）二次散列法的運用，平均探查次數的計算
·注意：二次散列法中裝填因子 a 與表長m的設置
·解決地址沖突的（開散列）鏈地址法的運用，平均探查次數的計算
我們原來也學過數據結構，個人覺得數組，棧與隊列 ，遞歸與廣義表，樹與
森林（尤其是二叉樹），圖 ，排序這些比較重要，應該好好看