数据结构笔记(DataStruct).doc

1vocabulary:.predecessor:前任，前辈immediate predecessor:直接前趋immediate successor:直接后继crunode/node:节点algorithm:算法algorithm analysis:算法分析stack:堆积pop:突然离去 pop off:突然死去parameter:参数substring:子串，子链concatenation:联接，一系列nave:朴素的，无经验的，单纯的，天真的，轻信的NaiveStrMatch:朴素的串匹配算法tuple:元组，数组trituple:三元数组matrix:矩阵 (pl):matrices/matrixes:inverse matrix:逆矩阵correlation matrix:相关矩阵，转矩阵transposed matrix:转置矩阵discrete:分离的，不相关联的descend:下来，下去 descendable:可遗传的descendance:后裔 descendant:后代，后裔traversal:遍历，（横向）往返移动preorder traversal:前序遍历postorder traversal:后序遍历probability:概率vertex:顶，顶点edge:边，棱，边缘multibaseoutput:多基输出base:基，基数adjacent:邻近的，邻近点adjacence:接近，毗连factorial:阶乘，阶乘积 factor:因子，因数，因素，要素variable:可变因数，变数，弯化的，可变的，易变的，变量local variable:局布变量symmetry:对称（性），匀称，整齐infinity:无穷大，无限大spanning:生成的spanning tree:生成树 spanning set:生成集 spanning space:生成空间 spanning forest:生成森林 spanning subgraph:生成子树in-place sort:就地排序sentinel:(n):哨兵，(vt):守卫，放哨pivot:(n):枢轴；中心点；基准，支点partition:划分；分开；分割，heap:堆，许多，累积；(vt):堆，堆积；（vi）堆起来heapify:堆化merge:合并，使合并；吞没；融合encode:把译成密码（或电码）；把.编码decode:解码radix:根；数基数 -pl:radices/radixescylinder:柱面，圆筒，汽缸track/magnetic track:磁道hash:（n）:剁碎的食物，杂乱无章的一大堆.(vt):切碎dense index:稠密索引sparse index:稀疏索引sequential storage structure:顺序存储结构linked storage structure:链接存储结构binary tree:二叉树sibling:兄弟 ancestor:祖先Huffman:哈夫曼WPL(Weighted Path Length of Tree):带树路径长度2.线性表：Linear List 约定俗的，线性表就形如：（a1,a2,a3,.,an）,但在计算机中数组是从a0开始的，这里就有个转化问题 基本操作： 1:InitList(L) 2:ListLength(L) 3:GetNode(L,i) 4:LocateNode(L,x) /在线性表中按关键词x查找 5:InsertList(L,x,i) 6:DeleteList(L,i) 2.1:顺序表（Sequential List）定义：#define ListSize 100typedef int DataType;typedef struct DataType dataListSize; int length;Seqlist;顺序表上实现的操作：void InsertList(SeqList *L,DataType x,int i) int j; if(iL-length+1) printf(“position error!n”); exit(1); if(L-length=ListSize) printf(“overflow”); exit(1); for(j=L-length-1;j=i-1;j-) L-dataj+1=L-dataj; L-datai-1=x; L-length+;void DeleteList(SeqList *L,int i) int j; if(iL-length) printf(“position errorn”); exit(1); if(L-length=0) printf(“underflown”); exit(1); for(j=i-1;jlength-1;j+) L-dataj=L-dataj+1; L-length-;2.2 链表（Linked List） 2.21 单链表（Single Linked List） 结构描述：typedef char DataType; typedef struct node DataType data; struct node *next; ListNode; typedef ListNode *LinkList; ListNode *p; LinkList head; 单链表的建立： 1).头插法建立单链表： LinkList CreateListF(void) char ch;ListNode *s; /工作结点；LinkList head; /头指针head=NULL;ch=getchar();while(ch!=n) s=(ListNode *)malloc(sizeof(ListNode); s-data=ch; s-next=head; head=s; ch=getchar();return head; 2).尾插法建立单链表： LinkList CreateListR(void) LinkList head; ListNode *s,*r; /r为尾指针 char ch; head=r=NULL; while(ch=getchar()!=n) s=(ListNode *)malloc(sizeof(ListNode); s-data=ch; if(head=NULL) head=s; else r-next=s; r=s; / end of while if(r!=NULL) r-next=NULL; return head; 3).尾插法建立带头结点的单链表： LinkList CreateListR1(void) char ch;ListNode *s,*r; LinkList head=(LinkList)malloc(sizeof(ListNode); r=head; while(ch=getchar()!=n) s=(ListNode *)malloc(sizeof(ListNode); s-data=ch; r-next=s; r=s; r-next=NULL; return head; 单链表的查找运算： 1).按序号查找： ListNode *GetNode(LinkList head,int i) int j; ListNode *p; p=head; j=0; while(p-next&jnext; j+; if(i=j) return p; return NULL; 2).按值查找：(以带头结点为例：) ListNode *LocateNode(LinkList head,DataType key) ListNode *p=head-next; while(p&p-data!=key) /细细体会其中的思想 p=p-next; return p; 单链表的插入运算(仍以带头结点为例)： void InsertList(LinkList head,DataType x,int i) ListNode *p; ListNode *s; p=GetNode(head,i-1); if(p=NULL) printf(“position error!n”); exit(1); s=(ListNode *)malloc(sizeof(ListNode)s-data=x; p-next=s; s-next=p-next; 单链表的删除运算(仍以带头结点为例)： void DeleteList(LinkList head,int i) ListNode *p,*r; p=GetNode(head,i-1); if(p=NULL|p-next=NULL) /注意这个条件很重要，仔细思考一下。 printf(“position error!n”); exit(1); r=p-next; p-next=r-next; free (r); 2.22.循环链表（Circular Linked List）:即首尾相接的链表： 2.23.双链表（Double Linked List） 描述： typedef char DataType; typedef struct dlistnode DataType data; struct dlistnode *prior,*next; DListNode; typedef DListNode *DLinkList; DLinkList head; 双链表的前插操作： void DInsertBefore(DListNode *p,DataType x) DListNode *s=(DListNode *)malloc(sizeof(DListNode); s-data=x; s-prior=p-prior; s-next=p; p-prior-next=s; p-prior=s; 双链表上删除操作： void DDeleteNode(DListNode *p) p-prior-next=p-next; p-next-prior=p-prior; free(p); 3.栈（stack） 约定好的，栈顶用Top，栈底用Bottom; 栈的基本操作： 1).InitStack(S) 2).StackEmpty(S) 3).StackFull(S) 4).Push(S,x) 5).Pop(S) 6).StackTop(S) 3.1:顺序栈结构描述：#define StackSize 100typedef char DataType;typedef struct DataType dataStackSize; int top;SeqStack;基本操作的实现：void InitStack(SeqStack *S) S-top=-1;int StackEmpty(SeqStack *S) return S-top=-1;int StackFull(SeqStack *S) return S-top=StackSize-1;void Push(SeqStack *S,DataType x) if(StackFull(S) printf(“Stack overflow!n”); exit(1); S-data+S-top=x;DataType Pop(SeqStack *S) if(StackEmpty(S) printf(“Stack underflow!n”); exit(1); return S-dataS-top-;DataType StackTop(SeqStack *S) if(StackEmpty(S) printf(“Stack is empty!n”); exit(1); return S-dataS-top; 3.2.链栈 结构描述： typedef char DataType; typedef struct stacknode DataType data; struct stacknode *next; StackNode; typedef struct StackNode *top; LinkStack; 基本操作的实现： void InitStack(LinkStack *S) S-top=NULL: int StackEmpty(LinkStack *S) return S-top=NULL; void Push(LinkStack *S,DataType x) StackNode *p=(StackNode *)malloc(sizeof(StackNode); p-data=x; p-next=S-top; S-top=p; DataType Pop(LinkStack *S) DataType temp; StackNode *p=S-top;if(StackEmpty(S) printf(“Stack underflow!n”); exit(1); temp=p-data; S-top=p-next; free(p); return temp;DataType StackTop(LinkStack *S) if(StackEmpty(S) printf(“Stack is empty!n”); exit(1); return S-top-data;4.队列（Queue） 队列上实现的操作： 1).InitQueue（Q） 2).QueueEmpty(Q) 3).QueueFull(Q) 4).EnQueue(Q) 5).DeQueue(Q) 6)QueueFront(Q) 4.1.顺序队列（循环队列）结构描述：#define QueueSize 100typedef char DataType;typedef struct DataType dataQueueSize;int front;int rear;int count;CirQueue;基本操作的实现：/这里要清楚，队列中的rear指针始终是指向下一个将要被插入的数据的位置，而这个位置，理论是应该是空的内存块。void InitQueue(CirQueue *Q)Q-front=Q-rear=0;/联想到循环队列的圆盘模型，仅从Q-front=Q-rear无法判定该队列是空还是满，所以必须加下第二个语句。Q-count=0;int QueueEmpty(CirQueue *Q)return Q-count=0;int QueueFull(CirQueue *Q)return Q-count=QueueSize;void EnQueue(CirQueue *Q,DataType x)if(QueueFull(Q)printf(“Queue overflow!n”);exit(1);Q-dataQ-rear=x;Q-rear=(Q-rear+1)%QueueSize; /更新尾指针指向。Q-count+; /更新数据个数DataType DeQueue(CirQueue *Q)DataType temp;if(QueueEmpty(Q)printf(“Queue underflow!n”);exit(1);temp=Q-dataQ-front;Q-count-;Q-front=(Q-front+1)%QueueSize;return temp;DataType QueueFront(CirQueue *Q)if(QueueEmpty(Q)printf(“Queue is empty!n”);exit(1);return Q-dataQ-front; 4.2.链队列： 结构描述：typedef char DataType; / front-|-|-|typedef struct queuenode / rear-DataType data;struct queuenode *next;QueueNode;typedef struct QueueNode *front;QueueNode *rear; /实际这里考虑实际应用，可以再加上一个结点计数器int count;LinkQueue; 基本操作的实现：void InitQueue(LinkQueue *Q)Q-front=Q-rear=NULL;int QueueEmpty(LinkQueue *Q)return Q-front=NULL;void EnQueue(LinkQueue *Q,DataType x) QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode); p-data=x; p-next=NULL;/为了防止指针乱指，一开始就令指针域为NULL；防患于未然if(QueueEmpty(Q) Q-front=Q-rear=p;/注意第一个数据的插入方法 else Q-rear-next=p; Q-rear=p; DataType DeQueue(LinkQueue *Q) DataType temp; QueueNode *p;if(QueueEmpty(Q) printf(“Queue underflow!n”); exit(1); p=Q-front; temp=p-data; Q-front=p-next; if(Q-rear=p) /*这点必须考虑到，当队列中只有一个节点时，尾指针的处理。 Q-rear=NULL; free(p); return temp;DataType QueueFront(LinkQueue *Q) if(QueueEmpty(Q) printf(“Queue is empty!n”); exit(1); return Q-front-data;5.串（String） d 注意区分”空串”和”空白串”的概念 空串：指长度为零的串 空白串：指仅由一个或多个空格组成的串。 串上的基本操作,在中： int strlen(char *s); char *strcpy(char *to,char *from); char *strcat( char *to,char *from); int strcmp(char *s1,char *s2); char *strchr(char *s,char c);/返回c在s中第一次出现的位置，找不到就返回NULL; 5.1.串的存储结构： 5.11.串的顺序存储： 串的静态顺序存储： Way1: #define MaxStrSize 256 typedef char SeqStringMaxStrSize; SeqString S; Way2: #define MaxStrSize 256 typedef struct char chMaxStrSize; int length; SeqString; 串的动态顺序存储： typedef struct char *s; int length; HString;5.12.串的链式存储： typedef struct node char data; struct node *next; LinkStrNode; typedef LinkStrNode *LinkString; LinkString S; 在实际应用中，可以根据结点的类型不同而设定一下： #define NodeSize 80 typedef struct node char dataNodeSize; struct node *next; LinkStrNode; typedef LinkStrNode *LinkString; LinkString S; 5.2.串上的操作（子串定位） 子串定位又称模式匹配（Pattern Matching）或串匹配（String Matching） 在串匹配中，一般将主串称为目标（串），子串称为模式（串），假设以T为目标（串），P为模式（串），形如： T=”t(0)t(1)t(2)t(n-1)”,P=”p(0)p(1)p(2)p(m-1)”, (0m=n); 也可记为：T0n-1,P0m-1; 匹配方法就是依次比较Tii+m-1和P0m-1,(其中0=i=n-m); 下面给出最简单的串匹配算法：朴素的串匹配算法(NaiveStrMatch)1. 顺序串上实现朴素的串匹配算法(NaiveStrMatch)这里串结构用： /* #define MaxStrSize 256 typedef struct char chMaxStrSize; int length; SeqString; */int NaiveStrMatch(SeqString T,SeqString P) int i ,j; for(i=0;i=T.length-P.length;i+) j=0;k=i; while(jdata=p-data) t=t-next; p=p-next; else shift=shift-next; t=shift; p=P; /end of while if(p=NULL) return shift; /匹配成功 elsereturn NULL; 下面是我自己写的算法，并且调试好了，也能达到预期的效果。LinkStrNode *LinkStrMatch(LinkString T,LinkString P)LinkStrNode *m,*n;while(T)m=T;n=P;while(m-data=n-data&n!=NULL) m=m-next; n=n-next;if(n=NULL)return T; T=T-next;return NULL;6多维数组和广义表： 数组的两种顺序存储方法： 1).行优先顺序：形如：a11,a12,a1n,a21,a22,a2n,am1,am2,amn; 2).列优先顺序：形如：a11,a21,am1,a12,a22,am2,a13,a23,am3; 默认的都以行优先顺序存储数组，其地址计算方法也模式化了： 二维数组Amn: LOC(aij)=LOC（a11）+(i-1)*n+(j-1)*d; 三维数组Amnp: LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+(k-1)*d; *注：这里二维数组可以看成是m长n宽的矩形，三维数组可以看成是m长n宽p高，这里d表示存储单元长度（逻辑上可以认为是1）； 7.矩阵的压缩存储： 7.1.特殊矩阵： 7.11对称矩阵：即在n阶方阵A中，元素满足：aij=aji,0=i,j=j) 对于aij,在i行之前有0,1,i-1,又第i行有i+1个元素，在j之前有0,1,j-1,也有j个元素，于是： k=i(i+1)/2+j; 0=kn(n+1)/2; 对于下三角矩阵：(i=j) 同理可推导出aij与sak的关系，因为aij=aji,所以只是把式子中的i与j调换一下，遂有： k=j(j+1)/2+i; 0=kn(n+1)/2; 应用中，令I=max(i,j),J=min(i,j),则k与i,j的关系为： k=I(I+1)/2+J; 0=kn(n+1)/2; 即aij=saI(I+1)/2+J;7.12.三角矩阵：这里矩阵的行数和列数都一样，都为n,分为上三角矩阵和下三角矩阵，上三角矩阵是左下边（不含对角线上的全为常数c（一般为0 ），而下三角矩阵正好相反。形如： 上三角： 1 3 4 下三角：1 0 0 0 2 6 9 5 0 0 0 8 7 8 1 三角矩阵的重复元素可以共享一个存储空间，其余元素正好有n(n+1)/2个,所以一共有n(n+1)/2+1个元素，因此三角矩阵可以存储到向量sa0n(n+1)/2，其中常数c存放在最后一个分量中， 对于上三角矩阵： k=i(2*n-i+1)/2+j-i 当ij /这里是常数c存储的位置 对于下三角矩阵： k=i(i+1)/2 当i=j k=n(n+1)/2 当im=a-n; b-n=a-m; b-t=a-t; q=0; if(b-t=0) printf(“Matrix a=0n”); exit(1); for(col=0;coln;col+) for(p=0;pt;p+) if(a-datap.j=col) b-dataq.i=a-datap.j; b-dataq.j=a-datap.i; b-dataq.v=a-datap.v; q+; /TransMatrix7.22.带行表的三元组表：有时为了方便某些矩阵运算，可以在按行优先存储的三元组表中，加入一个行表(RowTab)来记录稀疏矩阵中每行的非零元在三元组表中的起始位置，当将行表作为三元组表的一个新增属性加以描述 时，就会得到稀疏矩阵的另一种顺序存储结构:带行表的三元组表.其类型描述如下： #define MaxSize 100 /按实际需要可以更改 #define MaxRow 100 /在三元组表定义前加入此最大行定义typedef int DataType; typedef struct int i,j; DataType v; /非零元素的值value TriTupleNode; typedef struct TriTupleNode dataMaxSize; int RowTabMaxRow; int m,n,t; RTriTupleTable;7.3.广义表的概念：广义表（Lists,又称列表）是线性表的推广，线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身构这就产生了广义表的概念。EG：E=()L=(a,b)A=(x,L)=(x,(a,b)B=(A,y)=(x,(a,b),y)