各大网站收录入口,广州市财贸建设开发监理网站,做网站属于广告公司吗,公众号开发者密码怎么启用第五章 数组与广义表 n维数组看作数据元素为n-1维数组的线性表
数组地址计算:略
特殊矩阵压缩:
三角矩阵;三对角矩阵(带状矩阵);
稀疏矩阵:存储数据总量小于百分之三十
稀疏矩阵用三元组(行,列,值)储存,定义如下: typedef struct{ int row, col;//行,列 int e; }…第五章 数组与广义表 n维数组看作数据元素为n-1维数组的线性表
数组地址计算:略
特殊矩阵压缩:
三角矩阵;三对角矩阵(带状矩阵);
稀疏矩阵:存储数据总量小于百分之三十
稀疏矩阵用三元组(行,列,值)储存,定义如下: typedef struct{ int row, col;//行,列 int e; }Triple;
typedef struct{ Triple data[MAX1]; int m, n, len;//行,列,数据总个数 }TSMtrix;
普通双for循环算法 void TransMatrix(int a[m][n], b[m][n]){ int i, j; for(i 0; i m; i) for(j 0; j n; j) b[j][i] a[i][j]; }
稀疏矩阵递增转置法 void TransposeTSMatrix(TSMatrix A, TSMatrix *B){ int i, j, k; B-m A.n; B-n A.m; B-len A.len; //多次扫描,找到A列中对应B中的行的元素,一共扫描A.n次 if(B-len){ j 1; for(k 1;k A.n;k)//A.n为列数 for(i0 ;i A.len;i) if(A.data[i].col k) { B-data[j].row A.data[i].col; B-data[j].col A.data[i].row; B-data[j].e A.data[i].e; j; } } }
//一次快速定位转置法 void FastTransposeTSMatrix(TSMatrix A, TSMatrix *B) { int col, i, j ,k; //值得注意的是Triple定义的数组data[]保存的是存在元素(非0元素),值为零的不存 int num[MAXSIZE],position[MAXSIZE]; B-m A.n; B-n A.m; B-len A.len; if(B-len){ num[] {0}; //循环清0也可以 for(t 1;t A.len;t) num[A.data[t].col];//统计第col列的数据个数 position[1] 1; for(col 2;colA.len;col)//根据num每一列个数得到每一个新列第一个元素的位置 position[col] position[col-1]num[col-1]; //position为第几个元素 for(p 1;p { col A.data[p].col; q position[col];//找到该列第一个元素的位置 B-data[q].row A.data[p].col; B-data[q].col A.data[p].row; B-data[q].e A.data[p].e; position[col]; //下一个列号为col的非零元素再B中存放位置 } } }
十字链表 typedef ElemType int typedef struct OLNode { int col, row; ElemType value; struct OLNode *right, *down; }OLNode, *OLink;
typedef struct { OLink *row_head, *col_head;//注意这个是行列头指针链表的指针数组 int m, n, len; //行列长度 }CrossList;
//建立十字链表 bool CreateCrossList(CrossList *M){ //先输入矩阵M的相关信息 //为指针数组分配空间并且初始化 //输入十字链表每个节点的相关信息 //判断是否输入正确 //正确则进行创建结点并且插入链表 int m, n, len; int col, row; ElemType value; int i; OLink *q,*p; scanf(m, n, len); M-len len; M-m m; M-n n; if(!(M-row_head (* OLink)malloc(m * sizeof(OLink)))) return false; if(!(M-col_head (* OLink)malloc(n * sizeof(OLink)))) return false; //以下可以直接写M-row_head[ ] NULL; for(i 0; i m; i) M-row_head[i] NULL; for(i 0;i n; i) M-col_head[i] NULL; for(scanf(row, col, value); row ! -1; scanf(row, col, value)) { if(!(p (OLNode *)malloc(sizeof(OLNode)))) return false; p-col col; p-row row; p-value value; //先插行再插列互相不干扰 if(M-row_head[row] NULL) M-row_head[row] p; else{ q M-row_head[row]; while(q-right q-right-row row) q q-right; //q此时指向该行链表最后一个元素 //类似与尾插 p-right q-right; q-right p; } if(M-col_head[col] NULL) M-col_head[col] p; else{ q M-col_head[col]; while(q-down q-down-col col){ q q-down; } p-down q-down; q-down p; } } }
广义表:递归定义, 可以为无限序列(线性表为有限序列).表头为第一个元素,其余为表尾. 定义: typedef enum{ ATOM, LIST }Elemtag;//atom为原子结点标志,list为表结点标志
typedef struct GLNode{ ElemTag tag; union{//以下表明二选一 AtomType atom; struct{ struct GLNode *hp, *tp; }htp; }atom_htp; }GLNode , *GList; 广义表操作:略 第六章: 树与二叉树!!!!!!!!!!! 定义:根,子树,结点,度,高度(深度), 分支结点, 叶子节点, 森林, 孩子.兄弟.祖先.堂兄弟.子孙.双亲结点, 前/后辈. 树的图解表示法 1.树形表示法(倒置树结构) 2.文氏图表示法 3.广义表示形式(嵌套括号表示法) 4.凹入表示法 二叉树!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 性质:第i层至多2^(i-1)个结点; 前k层至多2^(k-1)个结点. 叶子结点为n,度数为2结点为m,则n m 1. 区别:!!!满二叉树和完全二叉树 完全二叉树为:其深度下的1~n的位置序号分别与等高的满二叉树一一对应. 其深度计算log2(n)向下取整1 //相当于python里面的floor(log2(n)) log2(7)1 3
存储结构: 顺序存储结构:按照结点的层序编号以此存储到数组(向量)对应位置 链式存储结构: 定义如下: typedef DataType int typedef struct Node{ DataType data; struct Node *LChild; struct Node *RChild; }BiTNode, *BiTree;
必考点!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!二叉树的遍历!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
遍历规则:大致按照左中右,然后先/中/后序列代表着访问根的先后顺序,先序就先访问 先序遍历:先遍历根,再左子树,再右子树. 中序遍历:先遍历左子树,再根,再右子树. 后序遍历:...
应用广泛:表达式求值--前缀表达式为波兰表达式, 后缀表达式为逆波兰表达式,后缀表达式易于求值 略
递归算法: 先/中/后序遍历只是访问根结点先后顺序不一样而已
//二叉树的遍历 //先序遍历 DLR
void PreOrder(BiTree root){ if(root ! NULL){ Visit(root-data); PreOrder(root-LChild); PreOrder(root-RChild); } } //中序遍历 LDR void InOrder(BiTree root){ if(root ! NULL){ InOrder(root-LChild); Visit(root-data); InOrder(root-RChild); } }
//后序遍历 LRD void PostOrder(BiTree root){ if(root ! NULL){ PostOrder(root-LChild); PostOrder(root-RChild); Visit(root-data); } }
//输出二叉树中的结点 void PreOrder(BiTree root){ if(root ! NULL){ printf(root-data); PreOrder(root-LChild); PreOrder(root-RChild); } } //输出二叉树中的叶子结点 //先序遍历 void PreOrder(BiTree root){ if(root! NULL){ if(root-LChild NULL root-RChild NULL) printf(root-data); PreOrder(root-LChild); PreOrder(root-RChild); } }
//统计叶子节点的数目 //法1 //设置全局变量!!!! int LeafCount 0; void leaf(BiTree root) { leaf(root-LChild); leaf(root-RChild); if(root-LChild NULL root-RChild NULL){ LeafCount; } } //法2 分治算法 这个有点妙! int leaf(BiTree root) { if(root NULL) LeafCount 0; else if(root-LChild NULL || root-RChild NULL){ LeafCount; } else LeafCount leaf(root-LChild) leaf(root-RChild); return LeafCount; } //建立二叉树链表方式储存二叉树 //扩展先序遍历方式创建二叉树链表 原理:一棵树先序遍历得到结点的所有值;那么一堆值根据先序遍历得到树 void CreatBiTree(BiTree *bt){ char ch; ch getchar(); if(ch .) *bt NULL; else{ *bt (BiTree) malloc(sizeof(BiNode)); (*bt)-data ch; CreateBiTree((*bt)-LChild) ; CreateBiTree(((*bt)-RChild); } }
//求二叉树的高度 //后序遍历, 求高度, 递归 int PostTreeDepth(BiTree bt) { int hl, hr, max; if(bt ! NULL){ hl PostTreeDepth(bt-LChild); hr PostTreeDepth(bt-RChild); max hl hr ? hl : hr;//三元运算符 return max 1 ; } else return 0; } //先序遍历实现 int depth 0; void PreTreeDepth(BiTree bt, int h){ if(bt ! NULL){ if(h depth) depth h; PreTreeDepth(bt-LChild, h1); PreTreeDepth(bt-RChild, h1); } }
!!!!!!!!!!!!!!!!!!!!!!!!!!!!二叉树的层次遍历算法!!!!!!!!!!!!!很可能大题 void LevelOrder(BiTree bt){ BiTree Queue[MAX]; //将队列与二叉树结合, 重点!!!! int front, rear; if(bt NULL) return; front rear 0; Queue[rear] bt;//根节点入队,队尾入队哈! rear;//尾指针移走 //当front!rear即队列不为空 while(rear ! front){ printf(%d, Queue[front]);//visit(xxx);//访问刚刚出队的元素 if(Queue[front]-LChild){ Queue[rear] Queue[front]-LChild;//存在左孩子则入队 rear; } if(Queue[front]-RChild){ Queue[rear] Queue[front]-RChild; rear; } front;//出队的最后操作 } }
//基于栈的递归消除 //中序遍历二叉树的非递归算法 void inorder(BiTree root){ Stack s[m]; int top 0; BiTNode *p; p root; do{ while(p ! NULL){ if(top m) return; // 栈满 top; s[top] p; p p-LChild; //遍历左子树 } if(top ! 0){//栈空为0 p s[top]; top--; Visit(p-data); p p-RChild; } }while(p ! NULL || top ! 0); //当前结点存在则入栈, 然后遍历左子树 //不在, 退栈, 访问右子树 }
//法2 //中序遍历非递归算法 void Inorder(BiTree root) { Stack s; InitStack(s); BiTNode *p root; while(p ! NULL || !IsEmpty(S)) {//栈空, p指向NULL, 结束 if (p){ Push(S, p); p p-LChild; } else { Pop(s, p); Visit(p-data); p p-RChild; } } } //后序遍历二叉树的非递归算法 void PostOrder(BiTree root){ BiTNode *p, *q; Stack S; q NULL; p root; Init(Stack); while(p ! NULL || !IsEmpty(S)){ if(p){ Push(S, p); p p-LChild; } else{ GetTop(S, p); if(p-RChild NULL || p-RChild q){//第二个条件判断是否也已经遍历过.类似于指针跟踪技术 visit(p-data); q p; Pop(S, p); p NULL; } else p p-RChild; } } }
//后序遍历法2 void PostOrder(BiTree root){ Stack st; BiTNode *p, *q, *r; p root; InitStack(st); bool flag; do{ while(p ! NULL){ Push(st, p); p p-LChild; } r NULL; flag true; while(!IsEmpty(st) flag){ GetTop(st, p); if(p-RChild r){ Visit(p-data); Pop(st, p); r p; } else{ p p-LChild; flag false; } } }while(!IsEmpty(st)); DestroyStack(st); } 线索二叉树: 原理:n个结点的二叉树有2n个链域,而只有n-1条边(离散),n1个链空浪费
// LChild Ltag data Rtag RChild
typedef struct Node{ int data; struct Node *LChild; struct Node *RChild; int Rtag;//0,指示结点的右孩子,1指示结点的遍历后继 int Ltag;//0,指示结点的左孩子,1指示结点的遍历前驱 }BiTNode, *BiTree; void Inthread(BiTree root){ if(root ! NULL){ Inthread(root-LChild);//线索化左子树 if(root-LChild NULL){ root-Ltag 1; root-LChild pre; } if(pre ! NULL pre-RChild NULL){ pre-RChild root; pre-Rtag 1; } pre root; Inthread(root-RChild); } }
//在中序线索树中找结点前驱 BiTNode *InPre(BiTNode *p){ BiTNode *q, *pre; if(p-Ltag 1) pre p-LChild; else{ //在p的左子树中找最右下端点 for(q p-LChild; q-Rtag 0; q q-RChild) ; pre q; } return pre; } //在中序线索树中找后继结点 BiTNode* InNext(BiTNode *p){ if(p-Rtag 1){ Next p-RChild; else{ for(q p-RChild; q-Ltag 0; q q-LChild) ; Next q; } return Next; } }
//找中序遍历线索树第一个节点 BiTNode *InFirst(BiTNode *p){ if(!p) return NULL; while(p-Ltag 0) p p-LChild; return p; } //遍历中序线索二叉树 void TInOrder(BiTNode Bt){ BITNode *p; p InFirst(Bt); while(p){ visit(p); p InNext(p); } }
遍历确定二叉树:只有先序中序, 后序中序可以 尝试还原: 先序 ABCDEFGHI 中序 BCAEDGHFI 二叉树参考: A B------------D -C E----------F -G------I -H
树的存储结构:
//双亲表示法 typedef struct TNode{ int data; int parent; }TNode;
typedef struct{ TNode tree[MAX]; int nodenum; }ParentTree;
//孩子兄弟表示法 重点!!! typedef DataNode int typedef struct ChildNode{//孩子链表结点定义 int Child; struct ChildNode *next; }ChildNode;
typedef struct{//顺序表结点定义 DataNode data; ChildNode *FirstChild; }DataNode;
typedef struct{ DataNode nodes[MAX]; int root; int num; }ChildTree;
//孩子表示法 tepedef struct CSNode{ int data; struct CSNode *FirstChild; struct CSNode *NextChild; }CSNode, *CSTree; 森林,树,二叉树: 任意树转化为二叉树:兄弟加平行线,删右侧加线端点的与双亲的连线,旋转 森林转化二叉树:第一颗二叉树不懂,后面的二叉树的根依次作为二前一棵二叉树的右孩子
注意:树的先根遍历--转换后二叉树的先序遍历 树的后根遍历--转换后二叉树的中序遍历 树的遍历算法://孩子兄弟链表实现对树的先根遍历 void RootFirst(CSTree root){ if(root ! NULL){ Visit(root-data); p root-FirstChild; while(p ! NULL) { RpptFirst(p); p p-NextSbling; } } }
void RootFirst(CST root){ if(root ! NULL){ Visit(root-data); RootFirst(root-FirstChild); RootFirst(root-NextSibling); } }
哈夫曼树:带权叶子节点构成路径长度最短的二叉树,称最优二叉树 路径,路径长度,结点的权,带权路径长度 类型定义: #define N 20 #define M 2 * N -1 typedef struct{ int weight; int parent; int LChild; int RChild; }HTNode, HuffmanTree[M1];
//Create the Tree void CrtHuffmanTree(HuffmanTree ht, int w[], int n){ //create ht[M1], w[]存放n个权值 for(i 1; i n; i) ht[i] {w[i], 0, 0, 0}; //Attention, start from 1, not 0 . So the length of ht is M 1, not M. for(i n 1; n M; i) ht[i] {0, 0, 0, 0}; for(i n 1; i M; i){ select(ht,i-1, s1, s2); //从ht[1]~ht[i-1]中选择两个parent 0且weight最小的结点 其序号赋值给s1, s2 ht[i].weight ht[s1].weight ht[s2].weight; ht[s1].parent i; ht[s2].parent i; ht[i].LChild s1; ht[i].RChild s2; } }
//对于第三个for 循环如下 for(i n 1; i M;i ){ s1 s2 32767; Inode rnode -1; for(k 0; k i -1 ;k){ if(ht[k].parent -1){ if(ht[k].weight s1){ s2 s1; rnode Inode; s1 ht[k].weight; Inode k; } else if(ht[k].weight s2){ s2 ht[k].weight; rnode k; } } } }
//哈夫曼编码_不用管,下一个可以看看 void encoding(HuffmanTree ht, HuffmanCode hc, int n){ //n 为叶子结点个数 int start n - 1; char *cd; cd (char *)malloc((n 1) * sizeof(char)); //暂时存入字符编码的字符数组 cd[n] \0; for(i 1; i n; i){ start n; c i; p ht[i].parent; while(p ! -1){ start--; if(ht[p].LChild c) cd[start] 0; else cd[start] 1; c p; p ht[p].parent;//倒着存入的思想 } hc[i] (char *)malloc((n1-start) * sizeof(char)); strcpy(hc[i], cd[start]); cd {\0}; } free(cd); }
#define LEN 100 typedef struct{ char ch; //存储字符 char code[LEN]; //存放编码 }TCode;//每个字符都对应唯一编码,因为哈夫曼树为前缀编码 TCode CodeBook[LEN];//编码本
//哈夫曼编码算法_2 void encoding1(HTNode ht[], TCode book[], int n){ char *str (char *)malloc((n 1) * sizeof(char));//存放编码 str[n] \0; int i, j, idx, p; //哈夫曼树某个叶结点下标idxa,用parent找到父节点idxb for(i 0; i n; i){//依次求叶子结点ht[i]的编码 book[i].ch ht[i].ch; idx i; j n; while(p ht[idx].parent 0){ if(ht[p].LChild idx){ j--; str[j] 0;//左孩子 } else{ j--; str[j] 1;//右孩子 } idx p;// idx 为下一轮找双亲的孩子,因为p ht[idx].parent; } strcpy(book[i].code, str[j]); } } //解码运算算法 void decoding(HTNode ht[], char *codes, int n){ int p 2 * n -2;//p为表中最后一个结点的指针, (总共2n-1个结点, 0开始), ht[p]代表root int i, j; i 0; while(codes[i]! \0){ while(ht[p].LChild !-1 ht[p].RChild ! -1){ if(codes[i] 0) p ht[p].LChild; else p ht[p].LChild; i; } printf(%c, ht[p].ch); p 2 * n -2; } }
第六章总结:
存储结构: 二叉树采用顺序储存与二叉链表储存 哈夫曼树概念,了解相关实现. 遍历必考!
//icoding例题 假设二叉树采用二叉链表方式存储 root指向根结点node 指向二叉树中的一个结点 编写函数 path计算root到 node 之间的路径该路径包括root结点和 node 结点。path 函数声明如下 bool path(BiTNode* root, BiTNode* node, Stack* s); 其中root指向二叉树的根结点node指向二叉树中的另一结点s 为已经初始化好的栈 该栈用来保存函数所计算的路径如正确找出路径则函数返回 true此时root在栈底node在栈顶 如未找到则函数返回 false, 二叉树的相关定义如下 typedef int DataType; typedef struct Node{ DataType data; struct Node* left; struct Node* right; }BiTNode, *BiTree; 栈的相关定义及操作如下 #define Stack_Size 50 typedef BiTNode* ElemType; typedef struct{ ElemType elem[Stack_Size]; int top; }Stack; void init_stack(Stack *S); // 初始化栈 bool push(Stack* S, ElemType x); //x 入栈 bool pop(Stack* S, ElemType *px); //出栈元素保存到px所指的单元函数返回true,栈为空时返回 false bool top(Stack* S, ElemType *px); //获取栈顶元素将其保存到px所指的单元函数返回true栈满时返回 false bool is_empty(Stack* S); // 栈为空时返回 true否则返回 false #include bitree.h //请不要删除否则检查不通过 #include #include
bool path(BiTNode* root, BiTNode* node, Stack* s) { BiTNode *p, *q; int i 0; p root; q NULL; init_stack(s); if (p NULL || node NULL) return false; if (p node) { push(s, p); return true; } while (p ! NULL || !is_empty(s)) { while (p) { push(s, p); if (p node) return true; p p-left; } top(s, p); if (p-right q || p-right NULL) { q p; pop(s, p); p NULL; } else { p p-right; } } return false; } 第七章 图
概念:vertex, head, arc, tail, edge.子图,邻接点,邻接边,度,入/出度,网,路径长度,回路,连通图.... 分类:稀疏图,完全图,稠密图
图的存储结构://重点
//邻接表 //分为表头结点表和边表 //前者是一个指针类型的结构数组 每一个结构包括结点域和链域 //边表储存弧结点, 弧结点结构分为三个域, 第一个储存弧结点相关信息, //第二个一般可以储存权重, 第三个链域存表头结点的下一个邻结点的弧
#define MAX_VERTEX_NUM 20 typedef enum{DG, DN, UDG, UDN } GraphKind; typedef char VertexData
typedef struct ArcNode{//弧结点 int adj; int info; struct ArcNode *nextarc;//指向下一条弧的指针 }ArcNode;
typedef struct VertexNode{//表头结点 VertexData data; ArcNode *firstarc; }VertexNode;
typedef struct{ VertexNode vertex[MAX_VERTEX_NUM]; int vexnum, arcnumber; GraphKind kind; }AdjList; //邻接矩阵 #define MAX_VERTEX_NUM 20 #define IFINITY typedef enum{DG, DN, UDG, UDN } GraphKind; typedef char VertexData typedef struct ArcNode{ int adj; }ArcNode; typedef struct{ VertexData vertex[MAX_VERTEX_NUM]; ArcNode arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum, arcnumber; GraphKind kind; }AdjMatrix;
//求顶点位置函数 int LocateVertex(AdjMatrix *G, VertexData v){ int i 0; for(; i G-vexnum; i){ if(G-vertex[i] v) return i; } return -1; } //创建一个有向网 int CreateDN(AdjMatrix *G){ int vexnum, arcnum; VertexData v1, v2; int i, j, k, weight; scanf(%d, %d, vexnum, arcnum); for(i 0; i G-vexnum; i) scanf(%c, G-vertex[i]); for(i 0; i G-vexnum; i) for(j 0; j G-vexnum; j) G-arc[i][j] IFINITY; for(k 0; k G-arcnumber; k){ scanf(%c, %c, %d, v1, v2, weight); i LocateVertex(G, v1); j LocateVertex(G, v2); G-arc[i][j] weight; } return OK; }
//十字链表 #define MAX_VERTEX_NUM 20 typedef enum{DG, DN, UDG, UDN } GraphKind; typedef char VertexData typedef struct ArcNode{ int tailvex; //储存当前结点信息 int headvex; //储存下一个结点信息 struct ArcNode *hlink;//入度 struct ArcNode *tlink;//出度, 相当于邻接表 int info; //可以存权 }ArcNode; typedef struct VertexNode{ VertexData data; //顶点信息 ArcNode *firstin; //入度的第一条弧//以该顶点为弧头的第一个弧顶点 ArcNode *firstout; //以该顶点为弧尾的第一个弧顶点 }VertexNode;
typedef struct{ VertexNode vertex[MAX_VERTEX_NUM]; int vexnum, arcnum; GraphKind kind; }OrthList;
//创建十字链表算法 void CrtOrthList(OrthList *g){ int vexnum, arcnum; int i, j, k; VertexData vh, vt; ArcNode *p; scanf(%d, %d, vexnum, arcnum); g-vexnum vexnum; g-arcnum arcnum; for(i 0; i vexnum; i){ scanf(%c, (g-vertex[i].data)); g-vertex[i].firstin NULL; g-vertex[i].firstout NULL; } for(k 0; k arcnum; k){ scanf(%c, %c, vh, vt); i LocateVertex(g, vt); j LocateVertex(g, vh); p (ArcNode *)malloc(sizeof(ArcNode)); p-tailvex i; p-headvex j; //类似于头插 p-tlink g-vertex[i].firstout; g-vertex[i].firstout p; p-hlink g-vertex[j].firstin; g-vertex[j].firstin p; } } //邻接多重表 //邻接多重表与邻接表不同, 前者主要记录边的信息 //该表有标志域, 记录是否被搜索过, 两个顶点, 分别与两个顶点关联的边 #define MAX_VERTEX_NUM 20 typedef enum{DG, DN, UDG, UDN } GraphKind; typedef char VertexData typedef struct EdgeNode{ int mark; int ivex, jvex; struct EdgeNode *ilink; struct EdgeNode *jlink;//用于指向下一条依附于顶点jvex的边 //顶点的邻接边 }EdgeNode; typedef struct{ VertexData data; EdgeNode *firstedge; }VertexNode; typedef struct{ VertexNode vertex[MAX_VERTEX_NODE]; int arcnum, vexnum; GraphKind kind; }AdjMulList; 总结: //邻接矩阵:二维数组, 一维数组组成, 邻接矩阵存是否两个顶点之间有边 //邻接表:顶点指针结构数组, 弧结点构成以顶点为头结点的链表 , 节省稀疏图对邻接矩阵造成的的空间浪费 //邻接多重表:标志域, 两个结点域, 两个链域分别对应域两个顶点的邻接边信息 //十字链表: 邻接表和逆邻接表的结合, 每一个结点有两个链域存出度和入度信息, 两个数据域存结点信息
